CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 2 of 7 · 3 min read

Placement

In plain words: A long parking lot holds cars of different lengths. When a car leaves, its space becomes a gap. A new car must fit entirely inside one gap, since a car cannot be split across two gaps. The analogy stops in one place: cars never need to be moved, but the kernel can, at a price (section 5).

With variable-sized regions, the memory is a mix of used blocks and free holes. When a process starts, the kernel must find a hole at least as big as the process, give it the part it needs, and keep the rest as a smaller hole. When a process ends, its block becomes a hole, and the kernel joins it with any hole that touches it. Three rules choose the hole:

  • First fit: take the first hole, searching from the start of memory, that is big enough. It is fast, since the search stops early.
  • Best fit: take the smallest hole that is big enough. It must look at all holes, unless they are kept in order of size. It leaves the smallest remainder.
  • Worst fit: take the largest hole. The idea is that the remainder will be big enough to be useful.

Here is a made-up example. The memory has six holes, listed from the start with their sizes: 10, 4, 20, 7, 15 and 5 units. Three requests arrive in turn: 12, 10 and 9.

Rule Request 12 Request 10 Request 9 Holes left
First fit hole 20 → leaves 8 hole 10 → leaves 0 hole 15 → leaves 6 4, 8, 7, 6, 5
Best fit hole 15 → leaves 3 hole 10 → leaves 0 hole 20 → leaves 11 4, 11, 7, 3, 5
Worst fit hole 20 → leaves 8 hole 15 → leaves 5 hole 10 → leaves 1 1, 4, 8, 7, 5, 5

The tracing is by hand: the first-fit row takes, for request 12, the first hole of at least 12 units, which is the hole of 20. For request 10, the first hole that fits is the first hole of the list, of exactly 10. For request 9, the first hole of at least 9 is the one of 15. Check the other two rows the same way.

Now a fourth request of 11 units arrives. Under best fit, a hole of exactly 11 exists, so the request is granted. Under first fit and worst fit, the largest hole is 8, so it fails, although the total free space is 30 units in both cases. No rule is best for every sequence, but the table shows how the choice shapes the holes that remain.

Hole

A hole is a contiguous block of free memory between used blocks; a request can be placed only inside a single hole, never across two, even when they are neighbours with a used block in between.

Example: a memory with holes of 8 and 6 units cannot grant a request of 10 units, although 14 units are free in total.

Check yourself: 1. Which rule searches the whole list of holes in every case? 2. In the table, which rule leaves a hole of 11 units, and why does that matter for the next request? 3. What does the kernel do with two holes that touch after a process ends?