4.2.23 · D1Operating Systems

Foundations — Memory allocation — contiguous (first-fit, best-fit, worst-fit)

1,806 words8 min readBack to topic

Before we can talk about "first-fit vs best-fit", we must earn every word the parent note leaned on: cell, address, block, hole, base + length, the set symbol , size , the request , the inequality , and leftover . We build each from a picture.


1. A memory cell and its address

Why the topic needs it. Every later idea — "a block at base ", "a hole from address 200 to 400" — is just a range of these numbered boxes. If you cannot see the ruler of addresses, none of the (base, length) language makes sense. The address is the coordinate system of memory.


2. A block: base + length

Why "contiguous" (unbroken) matters. A program expects its memory to be one straight stretch so it can walk from cell to cell by simple counting (, then , then ...). If the OS gave it two separate pieces, address might land in someone else's memory. That single word — contiguous — is the entire reason placement is hard.


3. A hole: free space between blocks

Why the topic needs it. The whole game is: a program asks for room, and the OS must find a hole big enough. The parent note's "Swiss cheese" picture is exactly figure s03 — filled blocks (busy) alternating with holes (free). The placement rules are all recipes for choosing which hole.


4. The free list and the set symbol

Why this notation. We need to talk about "all the holes" without knowing in advance how many there are. The subscript lets us say general things like "for every hole " instead of writing by hand. It is bookkeeping shorthand, nothing more.


5. The request and the inequality

Why an inequality and not equals. Requests almost never match a hole exactly. We do not demand a perfect-size hole; we demand a big-enough one, then cut the piece we need. The captures exactly that "big enough" idea — the single most-used test in the whole topic.


6. Leftover: the subtraction

Why this single formula is the heart of the topic. Every placement rule is judged by the leftover it creates. Best-fit tries to make small (tight fit); worst-fit tries to make large (reusable chunk). The subtraction is literally the number that first-fit, best-fit, and worst-fit argue about.


7. Fragmentation: two flavours

Why both matter. These two words name the failure modes the placement rules fight over. See Fragmentation for the full treatment; here we only need to recognise them by picture: external = wasted between blocks, internal = wasted inside a block.


Prerequisite map

Byte and address ruler

Block = base plus length

Hole = an empty block

Free list h1 h2 h3 with braces

Size bars of hole

Request size s

Fits test size ge s

Leftover H minus s

Fragmentation external and internal

Placement rules first best worst fit

Read top to bottom: the address ruler makes blocks meaningful, blocks make holes meaningful, holes gather into a free list, the size bars let us test , that test plus the leftover drive the placement rules — and the leftovers pile up into fragmentation. Now the parent note (parent topic) reads as plain English.


Equipment checklist

Cover the right side and answer; reveal to check.

An address is
the permanent number naming the position of one byte-box in the memory line ().
A contiguous block is
a run of consecutive boxes with no gaps, described by base and length .
The last address of a block with base , length is
(not ).
The braces mean
the collection (set) of all current holes, tagged by subscript.
means
the size (number of free boxes) of hole .
means
the size of the memory request a program is making.
The test asks
is this hole at least as big as the request? (equality counts as fitting).
Why an inequality, not equals?
requests rarely match a hole exactly; we only need "big enough", then cut the piece.
Leftover after placing in hole is
; if the hole vanishes, else a smaller hole remains at base .
External fragmentation is
enough total free memory, but split into holes each too small (not contiguous).
Internal fragmentation is
wasted free space inside an allocated block.
Why is contiguity the whole difficulty?
a program needs one unbroken run, so free cannot serve a request of .