Contiguous allocation: fit policies and coalescing
Goals and model
Trace first fit, best fit and worst fit through a sequence of requests; distinguish splitting, coalescing and compaction; and count alignment overhead. Prerequisite: internal/external fragmentation from the paging lesson. We use variable-sized contiguous allocations. Each request must fit in one hole; there is no paging or request splitting across holes. In the first examples sizes are arbitrary units, headers/alignment cost zero, requests consume the low-address end of a hole and any remainder stays free. Initial holes are separated by allocated regions, so their free sizes cannot simply be merged.
1. Three rules for choosing one empty space
Picture a row of parking gaps for vehicles of different lengths. First fit scans gaps in a stated order and stops at the first large enough. Best fit chooses the smallest sufficient gap. Worst fit chooses the largest sufficient gap. These are placement rules, not guarantees that the entire future request sequence will fit. “Best” refers to the local gap choice, not universal optimality.
Our free-list scan order is increasing address. Equal-size ties choose the lowest-address hole. Splitting a 350-unit hole for a 160-unit request allocates 160 and leaves a 190-unit free remainder. That remainder is free external space, not unused internal space inside the new allocation, because our model gives the requester exactly 160.
2. Run every policy from the same initial state
Initial holes in address order are H1=120, H2=350, H3=180, H4=420. These labels identify the original hole locations; remainders retain their label and place in address order. Requests are 160, then 300, then 100. Restart from the initial state for each policy, rather than running best fit on first fit's leftover state.
First fit:
- 160: H1 is too small; split H2. Holes become (120,190,180,420).
- 300: only H4 fits among the scanned holes. Holes become (120,190,180,120).
- 100: H1 is the first sufficient hole. Final holes=(20,190,180,120).
Total free space=510; largest hole=190. A following unsplittable 400-unit request fails, despite sufficient total free space.
Best fit:
- 160: choose H3=180, leaving 20. Holes=(120,350,20,420).
- 300: choose H2=350, leaving 50. Holes=(120,50,20,420).
- 100: choose H1=120, leaving 20. Final holes=(20,50,20,420).
Total is again 510; largest hole=420. A following request of 400 succeeds here and leaves 20 in H4. The successful later request is a fact about this sequence, not proof that best fit always outperforms first fit.
Worst fit:
- 160: choose H4=420, leaving 260. Holes=(120,350,180,260).
- 300: choose H2=350, leaving 50. Holes=(120,50,180,260).
- 100: choose H4=260, leaving 160. Final holes=(120,50,180,160).
Total is 510; largest hole=180. The same later request of 400 fails. Re-evaluate the largest hole after every allocation: the initially largest location is not always chosen next.
3. Conservation is a useful independent check
Initial free total=120+350+180+420=1070. Successful requests consume 160+300+100=560. With zero overhead and no releases, every policy must end with 1070−560=510 free units. Different largest-hole values are compatible with the same free total. A calculation that changes the total without an allocation, release or stated metadata cost is wrong.
Do not silently discard small remainders. Real allocators can have minimum block sizes and metadata requirements, but those must be part of the model. If a remainder is handed to the client as extra allocated space, that extra can become internal waste rather than a free hole.
4. Coalescing requires physical adjacency
Suppose free regions are [0,100) and [150,250), while [100,150) is allocated. They are not adjacent and cannot yet coalesce. When the middle allocation is freed, [0,100), [100,150) and [150,250) become one free [0,250) region of length 250. Endpoints use half-open intervals, so adjacent intervals share a boundary without sharing an allocated byte.
Coalescing merges adjacent free blocks without moving live allocations. Compaction moves live allocations to gather separated free space into a larger region. Compaction needs a way to relocate or update references and has copying cost; it is not automatically valid for arbitrary raw pointers. Neither operation can create more total free capacity. A larger contiguous hole can become possible by changing layout while the total remains constant.
5. Account for metadata and alignment explicitly
Now use byte units and a different model: every allocation contains an 8-byte header before its payload; its total block size is rounded up to a multiple of 16 bytes. A 100-byte payload needs 108 bytes before rounding, then ceiling(108/16)×16=112 bytes. Payload is 100, header is 8 and alignment slack is 4. Total non-payload space is 12, but not all of it is padding. A hole of 108 bytes is insufficient under this alignment rule.
Next fit is another policy that resumes a scan near where the previous search stopped; it is not the same as first fit restarting at the lowest address. Its exact cursor behavior must be stated for a trace. This lesson does not invent a next-fit cursor when a question asks only for first fit.
Exam checklist
State hole order, tie rules, overhead, splitting and coalescing assumptions. For each successful request, subtract it from exactly one sufficient hole and preserve the remainder's location. For a failure, verify the largest hole as well as total free space. Distinguish logical free-list neighbors from physically adjacent address ranges.
Original practice: six single-correct MCQs
Choose exactly one option. Each question states its own required assumptions.
AL01. Address-ordered holes are 120,350,180,420 units. First fit allocates requests 160,300,100 in order, splitting with zero overhead and no coalescing. What is the largest final hole?
A. 120 B. 180 C. 190 D. 420
Answer: C
A: 120 is the final H4 size, not the largest.
B: H3 is 180, but H2 retains 190.
C: Final holes are 20,190,180,120; largest=190.
D: H4 was reduced by the 300-unit request.
AL02. Start independently with holes 120,350,180,420. Best fit allocates 160,300,100 with zero overhead, splitting and no coalescing. Can a subsequent contiguous 400-unit request fit?
A. No, because only 510 total units remain B. Yes, in the remaining 420-unit hole C. Yes, by adding all smaller holes D. No, because best fit never splits
Answer: B
A: 510 total exceeds 400; the issue is a sufficient individual hole.
B: The first allocations use 180,350,120, leaving the 420 hole intact.
C: The request cannot be split across separated holes.
D: Splitting is explicitly allowed.
AL03. Address-ordered holes 120,350,180,420 serve 160,300,100 using worst fit, splitting and zero overhead. What is the final hole-size list in the original address order?
A. 20,190,180,120 B. 20,50,20,420 C. 120,50,180,160 D. 120,350,20,120
Answer: C
A: This is first fit for the stated sequence.
B: This is best fit.
C: Choose H4 for 160, H2 for 300, then H4 for 100.
D: This does not apply the largest-hole rule and all three requested subtractions correctly.
AL04. Free intervals are [0,100) and [150,250). The allocated interval [100,150) is freed, and adjacent free blocks are coalesced. What single free interval results?
A. [0,200) B. [0,250) C. [100,250) D. No merge is possible
Answer: B
A: This omits the newly freed 50 units from the full span.
B: All three now-adjacent intervals unite into [0,250).
C: This omits the original first free interval.
D: They are physically adjacent after the middle interval is freed.
AL05. A 350-unit free hole is split to give a client exactly 160 units, with no headers/alignment cost. What is the 190-unit remainder?
A. Internal padding within the 160-unit allocation B. A free hole available for later allocation C. Automatically allocated to the client D. Lost memory that cannot be tracked
Answer: B
A: It is outside the exact requested allocation.
B: 350−160=190 remains on the free-space structure.
C: The model gives the client exactly 160.
D: The allocator retains the remainder in its free list.
AL06. An allocation has a 100-byte payload and an 8-byte header. Its total size is rounded up to a multiple of 16 bytes. What total block size is needed?
A. 100 B. 108 C. 112 D. 128
Answer: C
A: This omits header and rounding.
B: 108 includes the header but is not a multiple of 16.
C: ceil((100+8)/16)×16=112.
D: 112 is already a sufficient multiple; 128 over-rounds.
Sources and scope
This original lesson extends the existing OS foundations in the GATE 2026 course. It maps to Section 8 of the official 2026 syllabus; it is not a claim of complete OS coverage or GATE 2027 completeness. Practice questions are original, not past-exam questions.
Sources checked 2026-10-14.
Sign in to keep your progress. Sign in