Chapter 25 of 38

Contiguous Memory Allocation & Fragmentation

In Memory Management Basics we saw the simplest kind of MMU: a relocation (base) register and a limit register. That hardware assumes something important: each process sits in one continuous block of physical memory. If the process starts at address 300 000 and is 120 000 bytes long, it owns every byte from 300 000 to 419 999 and nothing else.

This idea is called contiguous memory allocation. It is the oldest and simplest way to share RAM between processes, and it leads straight to one of the most important problems in memory management: fragmentation, free memory that exists but cannot be used.

In this chapter we will learn fixed and variable partitioning, the four placement algorithms (first fit, next fit, best fit, worst fit) with full traces, internal vs external fragmentation, compaction, and the buddy system that Linux still uses today. Understanding these problems is what makes Paging (the next chapter) feel like the obvious solution.


What is Contiguous Memory Allocation?

Contiguous memory allocation is a memory management technique in which each process is given a single, continuous section of physical memory.

Main memory is usually divided into two parts:

  • One part for the operating system (on many systems it sits in high memory, on others in low memory; the idea is the same).

  • The rest for user processes, which is the part we have to divide up.

  Physical memory
 +----------------------+  0
 |  Operating system    |
 +----------------------+
 |  Process P1          |  <- one continuous block
 +----------------------+
 |  Process P2          |  <- one continuous block
 +----------------------+
 |  (free)              |
 +----------------------+
 |  Process P3          |
 +----------------------+  max

Protection is done exactly as in the previous chapter: when the CPU scheduler picks a process, the dispatcher loads that process's base and limit into the MMU. Every logical address is checked against the limit and then added to the base. A process simply cannot form an address outside its own block.

The question this chapter answers is: how does the OS decide where each block goes, and what happens to the gaps? There are two main schemes: fixed partitioning and variable partitioning.


Fixed (Static) Partitioning

The oldest method divides user memory into a number of partitions when the system starts (historically set by the operator at boot time). The partition sizes then never change. Each partition can hold exactly one process.

IBM's OS/360 used this scheme and called it MFT (Multiprogramming with a Fixed number of Tasks).

The partitions can be:

  • Equal-sized: simple, but a small process wastes most of its partition, and a process bigger than the partition can never run.

  • Unequal-sized: some small and some large partitions, so each process can be placed in the smallest partition that fits it.

Worked example

User memory is split into four partitions of 100, 200, 300 and 400 KB. Five processes arrive in this order, and each one is placed in the smallest free partition that is big enough:

Process

Size

Partition given

Wasted inside partition

P1

90 KB

100 KB

10 KB

P2

250 KB

300 KB

50 KB

P3

150 KB

200 KB

50 KB

P4

350 KB

400 KB

50 KB

P5

120 KB

none free, must wait

-

+-------------------+
| P1  90 KB | 10 KB |  partition 1 (100 KB)
+-------------------+
| P3 150 KB | 50 KB |  partition 2 (200 KB)
+-------------------+
| P2 250 KB | 50 KB |  partition 3 (300 KB)
+-------------------+
| P4 350 KB | 50 KB |  partition 4 (400 KB)
+-------------------+
              ^^^^^
              wasted: 10 + 50 + 50 + 50 = 160 KB

Look at what happened. 160 KB of memory is unused, which is more than the 120 KB that P5 needs, yet P5 has to wait. The free space is trapped inside partitions that already belong to other processes. This waste is called internal fragmentation.

Problems with fixed partitioning

  • Internal fragmentation: a process rarely fills its partition exactly.

  • Fixed degree of multiprogramming: with 4 partitions, at most 4 processes can be in memory, no matter how small they are.

  • Size limit: a process larger than the biggest partition can never run (unless the programmer uses tricks like overlays).

Its advantage is simplicity: the OS only needs a small table saying which partitions are busy.


Variable (Dynamic) Partitioning

To avoid internal fragmentation, we can make each partition exactly as big as the process. Partitions are created at run time, when processes arrive. OS/360 called this MVT (Multiprogramming with a Variable number of Tasks).

The OS keeps track of:

  • which parts of memory are allocated, and

  • which parts are free. A free block of memory is called a hole.

At the start, all user memory is one big hole. As processes arrive and leave, memory becomes a mix of allocated blocks and holes of different sizes scattered around.

Step-by-step trace

User memory is 1000 KB (addresses written relative to the start of user memory). Four processes arrive: P1 = 200 KB, P2 = 300 KB, P3 = 150 KB, P4 = 250 KB.

Step 1: load P1, P2, P3, P4          Step 2: P2 and P4 finish

   0 +-----------+                       0 +-----------+
     | P1 200 KB |                         | P1 200 KB |
 200 +-----------+                     200 +-----------+
     | P2 300 KB |                         | hole      |  300 KB
 500 +-----------+                     500 +-----------+
     | P3 150 KB |                         | P3 150 KB |
 650 +-----------+                     650 +-----------+
     | P4 250 KB |                         | hole      |  350 KB
 900 +-----------+                         |           |  (P4's 250 KB merged with
     | hole 100  |                         |           |   the 100 KB hole after it)
1000 +-----------+                    1000 +-----------+

Notice that when P4 left, its block was next to the existing 100 KB hole, so the two were merged (coalesced) into one 350 KB hole. Merging adjacent holes is essential, otherwise memory would break into smaller and smaller pieces.

Now a new process P5 needs 400 KB.

  • Total free memory = 300 + 350 = 650 KB, which is plenty.

  • Largest single hole = 350 KB, which is too small.

P5 cannot be loaded, because contiguous allocation needs all 400 KB in one piece. This is external fragmentation: enough total free memory exists, but it is split into holes that are each too small. We will fix this example with compaction later in the chapter.

Variable partitioning has no internal fragmentation (in theory; see the note on tiny holes below), but it suffers from external fragmentation instead. It also creates a new question: when several holes are big enough, which one should we use?


Placement Algorithms: First, Next, Best and Worst Fit

This is called the dynamic storage-allocation problem: how to satisfy a request of size n from a list of free holes. The four classic strategies are:

Algorithm

Rule

Search needed

First fit

Scan holes from the beginning of memory; take the first hole that is big enough.

Stops early

Next fit

Like first fit, but start scanning from where the last search ended, wrapping around.

Stops early

Best fit

Take the smallest hole that is big enough.

Whole list (unless kept sorted by size)

Worst fit

Take the largest hole.

Whole list (unless kept sorted by size)

In every case, the chosen hole is split: the process gets the first part, and the leftover becomes a smaller hole.

The thinking behind each rule:

  • First fit: "Don't waste time searching, just take something that works."

  • Best fit: "Keep the big holes for big processes; leave the smallest possible leftover."

  • Worst fit: "Leave the biggest possible leftover, so that it is still useful for someone else."

  • Next fit: "Don't keep cutting up the start of memory; spread allocations evenly."

Worked example

Memory has five holes, in address order: 150, 400, 250, 600 and 300 KB. Four processes arrive in order: P1 = 220 KB, P2 = 380 KB, P3 = 130 KB, P4 = 560 KB. Let us apply each algorithm.

First fit

  • P1 (220): 150 is too small; 400 fits. Hole 2 becomes 400 − 220 = 180.

  • P2 (380): 150, 180, 250 are too small; 600 fits. Hole 4 becomes 220.

  • P3 (130): 150 fits (first hole). Hole 1 becomes 20.

  • P4 (560): holes are now 20, 180, 250, 220, 300. None is ≥ 560. P4 waits.

Next fit (the search pointer starts at hole 1)

  • P1 (220): from hole 1: 150 no, 400 yes. Hole 2 becomes 180. Pointer stays at hole 2.

  • P2 (380): from hole 2: 180 no, 250 no, 600 yes. Hole 4 becomes 220. Pointer at hole 4.

  • P3 (130): from hole 4: 220 fits. Hole 4 becomes 90. (First fit would have gone back to hole 1.)

  • P4 (560): 90, 300, 150, 180, 250, no hole is big enough. P4 waits.

Best fit

  • P1 (220): holes that fit are 400, 250, 600, 300; smallest is 250. Leftover 30.

  • P2 (380): holes that fit are 400, 600; smallest is 400. Leftover 20.

  • P3 (130): holes that fit are 150, 600, 300; smallest is 150. Leftover 20.

  • P4 (560): only 600 fits. Leftover 40. All four processes are loaded.

Worst fit

  • P1 (220): largest hole is 600. Leftover 380.

  • P2 (380): holes are 150, 400, 250, 380, 300; largest is 400. Leftover 20.

  • P3 (130): largest is now 380. Leftover 250.

  • P4 (560): largest hole is 300. P4 waits.

Here is a small C program that simulates all four algorithms on the same input. It keeps only the hole sizes, because that is all the placement decision depends on:

#include <stdio.h>

enum fit { FIRST, NEXT, BEST, WORST };
static const char *names[] = { "First fit", "Next fit", "Best fit", "Worst fit" };

/* Pick a hole for a request of 'req' KB. Returns its index, or -1 if none fits. */
static int choose(const int h[], int n, int req, enum fit f, int *next)
{
    if (f == NEXT) {
        for (int k = 0; k < n; k++) {
            int i = (*next + k) % n;              /* resume where we stopped */
            if (h[i] >= req) { *next = i; return i; }
        }
        return -1;
    }
    int pick = -1;
    for (int i = 0; i < n; i++) {
        if (h[i] < req) continue;                 /* too small, skip */
        if (f == FIRST) return i;                 /* first one that fits */
        if (pick == -1 ||
            (f == BEST  && h[i] < h[pick]) ||     /* smallest that fits */
            (f == WORST && h[i] > h[pick]))       /* largest of all     */
            pick = i;
    }
    return pick;
}

static void run(const int sizes[], int n, const int req[], int m, enum fit f)
{
    int h[16], next = 0;
    for (int i = 0; i < n; i++) h[i] = sizes[i];  /* fresh copy for each algorithm */

    printf("%s:\n", names[f]);
    for (int j = 0; j < m; j++) {
        int i = choose(h, n, req[j], f, &next);
        if (i < 0) { printf("  P%d (%3d KB) -> must WAIT\n", j + 1, req[j]); continue; }
        printf("  P%d (%3d KB) -> hole %d (%3d KB), leftover %3d KB\n",
               j + 1, req[j], i + 1, h[i], h[i] - req[j]);
        h[i] -= req[j];                           /* the rest stays a (smaller) hole */
    }
    printf("  holes left:");
    for (int i = 0; i < n; i++) printf(" %d", h[i]);
    printf("\n");
}

int main(void)
{
    const int holes[] = { 150, 400, 250, 600, 300 };   /* in address order */
    const int reqs[]  = { 220, 380, 130, 560 };
    for (int f = FIRST; f <= WORST; f++)
        run(holes, 5, reqs, 4, (enum fit)f);
    return 0;
}

Compiled with gcc -std=c17 -Wall -Wextra fits.c -o fits and run on Linux, it prints:

First fit:
  P1 (220 KB) -> hole 2 (400 KB), leftover 180 KB
  P2 (380 KB) -> hole 4 (600 KB), leftover 220 KB
  P3 (130 KB) -> hole 1 (150 KB), leftover  20 KB
  P4 (560 KB) -> must WAIT
  holes left: 20 180 250 220 300
Next fit:
  P1 (220 KB) -> hole 2 (400 KB), leftover 180 KB
  P2 (380 KB) -> hole 4 (600 KB), leftover 220 KB
  P3 (130 KB) -> hole 4 (220 KB), leftover  90 KB
  P4 (560 KB) -> must WAIT
  holes left: 150 180 250 90 300
Best fit:
  P1 (220 KB) -> hole 3 (250 KB), leftover  30 KB
  P2 (380 KB) -> hole 2 (400 KB), leftover  20 KB
  P3 (130 KB) -> hole 1 (150 KB), leftover  20 KB
  P4 (560 KB) -> hole 4 (600 KB), leftover  40 KB
  holes left: 20 20 30 40 300
Worst fit:
  P1 (220 KB) -> hole 4 (600 KB), leftover 380 KB
  P2 (380 KB) -> hole 2 (400 KB), leftover  20 KB
  P3 (130 KB) -> hole 4 (380 KB), leftover 250 KB
  P4 (560 KB) -> must WAIT
  holes left: 150 20 250 250 300

The output matches our hand traces. Summary of this example:

Algorithm

P1

P2

P3

P4 (560 KB)

First fit

400

600

150

waits

Next fit

400

600

220 (left of 600)

waits

Best fit

250

400

150

600, loaded

Worst fit

600

400

380 (left of 600)

waits

Why did best fit win? It was the only algorithm that left the 600 KB hole untouched. First fit, next fit and worst fit all cut a piece out of the 600 KB hole early, and then nothing big was left for P4. Notice also the price best fit paid: its leftovers are 20, 20, 30 and 40 KB, tiny holes that are probably too small for any future process.

No algorithm always wins

It is tempting to conclude "best fit is best". It is not always. Take two holes, 650 KB and 600 KB, and requests 500, 550 and 125 KB:

Request

First fit

Best fit

500 KB

650 → leftover 150

600 → leftover 100

550 KB

600 → leftover 50

650 → leftover 100

125 KB

150 → leftover 25 ✔

holes are 100 and 100 → waits ✘

Here first fit succeeds and best fit fails, because best fit split the space "evenly" into two medium holes, neither of which can hold 125 KB. You can build an example to make any of these algorithms look good or bad. That is why the comparison is based on simulations with realistic workloads, not single examples.

What simulations show

  • First fit and best fit are both better than worst fit in terms of memory utilisation and speed.

  • Neither first fit nor best fit is clearly better at utilisation, but first fit is usually faster, because it stops at the first match.

  • Best fit tends to create many tiny holes that are almost useless.

  • Worst fit quickly destroys all large holes, so large processes starve.

  • Next fit spreads allocations over all of memory; in practice it often performs slightly worse than first fit because it also breaks up the large hole at the end of memory.

For GATE and interviews, the safe one-liner is: first fit is generally the best practical choice (fast and good utilisation); worst fit is generally the worst.


Internal vs External Fragmentation

We have now met both kinds of fragmentation. They are easy to confuse, so let us put them side by side.

Internal fragmentation is unused memory inside an allocated block: the block given to a process is larger than what the process asked for.

External fragmentation is free memory outside allocated blocks that is split into pieces too small to satisfy a request, even though the total free memory would be enough.

Internal fragmentation                 External fragmentation

+--------------------+                 +--------+
| process data       |                 |   P1   |
|                    |                 +--------+
+ - - - - - - - - - -+                 | hole 1 |  <- 300 KB free
| allocated but      | <- wasted,      +--------+
| unused             |    inside       |   P3   |
+--------------------+    the block    +--------+
                                       | hole 2 |  <- 350 KB free
                                       +--------+
                                     Request of 400 KB fails,
                                     although 650 KB is free.

Point

Internal fragmentation

External fragmentation

Where is the waste?

Inside an allocated block

Between allocated blocks (in holes)

Cause

Memory is handed out in fixed-size units (partitions, pages, power-of-2 blocks)

Memory is handed out in exact, variable sizes; processes leave holes when they exit

Who can use the waste?

Nobody, it belongs to the owning process until it exits

Anyone, if the pieces were joined together

Seen in

Fixed partitioning, paging (last page), buddy system

Variable partitioning, segmentation

Main fixes

Smaller allocation units

Compaction, or non-contiguous allocation (paging)

Tiny holes and why a little internal fragmentation is accepted

Suppose a hole is 10 004 bytes and a process asks for 10 000 bytes. Giving exactly 10 000 bytes leaves a 4-byte hole. Keeping track of that hole in the free list costs more memory than the hole itself. So real allocators round requests up to some minimum unit and give the whole small leftover to the process. That means even "variable" partitioning has a little internal fragmentation in practice.

The 50-percent rule

How bad is external fragmentation in practice? Donald Knuth's analysis of first fit, known as the 50-percent rule, says that in a steady state, if there are N allocated blocks, there are about N/2 holes. Operating systems textbooks state the practical consequence like this: given N allocated blocks, another 0.5N blocks are lost to fragmentation, so up to about one-third of memory may be unusable. That is a lot of RAM to waste, and it is the main motivation for compaction and paging.


Freeing Memory and Merging Holes

When a process ends, its block becomes a hole. The OS must check its neighbours. There are four cases:

Neighbour above

Neighbour below

What happens

Allocated

Allocated

A new separate hole is added to the free list

Hole

Allocated

Merge with the hole above

Allocated

Hole

Merge with the hole below

Hole

Hole

Merge all three into one hole (the free list gets one entry shorter)

Keeping the free list sorted by address makes this check cheap, because the neighbours of a block are next to each other in the list. This is one reason first fit, which scans in address order, is popular: the same list serves both allocation and merging. Best fit and worst fit would prefer a list sorted by size, which makes merging harder.


Compaction

The most direct fix for external fragmentation is to shuffle the processes together so all the holes join into one big hole.

Compaction is the process of moving allocated blocks in memory so that all free memory is collected into one large contiguous block.

Back to our trace, where P5 (400 KB) could not be loaded. If the OS moves P3 down to address 200, the two holes join:

Before compaction                     After compaction (move P3 only)

   0 +-----------+                       0 +-----------+
     | P1 200 KB |                         | P1 200 KB |
 200 +-----------+                     200 +-----------+
     | hole 300  |                         | P3 150 KB |
 500 +-----------+                     350 +-----------+
     | P3 150 KB |                         |           |
 650 +-----------+                         | hole      |  650 KB, now P5 (400 KB)
     | hole 350  |                         |           |  fits easily
1000 +-----------+                    1000 +-----------+

Data copied: 150 KB (only P3 moved)

Choosing which blocks to move matters. Moving P1 instead would not have helped, and moving everything to one end is simple but can copy far more data than necessary. Finding the cheapest compaction is a hard problem in general, so real systems use simple heuristics.

When is compaction possible?

Compaction is only possible if relocation is dynamic, done at execution time (see Address Binding in Memory Management Basics). After copying a process to a new place, the OS just updates its base register; the process's logical addresses do not change. If addresses were fixed at compile time or load time, the copied program would still contain the old physical addresses and would break.

Why compaction is expensive

  • It copies large amounts of memory. Even at several GB per second, moving gigabytes takes a noticeable amount of time, and the processes being moved cannot run during their copy.

  • I/O problem: if a device is doing DMA into a process's buffer, moving that process would make the device write into the wrong place. Such processes must be kept in place (pinned) or I/O must be done only through OS buffers.

  • It must be repeated, because fragmentation comes back as processes keep arriving and leaving.

The better long-term fix is to drop the "one contiguous block" rule altogether, which is exactly what Paging and Segmentation do.


The Buddy System

Fixed partitions waste space inside blocks; variable partitions waste space between blocks and make merging messy. The buddy system is a clever compromise between the two, and it is still in use: the Linux kernel allocates physical page frames with a buddy allocator.

In the buddy system, memory is allocated in blocks whose sizes are powers of 2. A request is rounded up to the next power of 2. A larger free block is split in half repeatedly until a block of the right size exists; the two halves of a split are called buddies. When a block is freed and its buddy is also free, they are merged back into the larger block.

Worked example

We start with one free block of 1024 KB (addresses 0 to 1023 KB). Four requests arrive: A = 100 KB, B = 240 KB, C = 60 KB, D = 130 KB.

A = 100 KB → round up to 128 KB. No 128 KB block exists, so we split:

1024  ->  512 @0   + 512 @512
 512 @0  ->  256 @0   + 256 @256
 256 @0  ->  128 @0   + 128 @128
A gets 128 @0      (wasted 128 - 100 = 28 KB)

B = 240 KB → round up to 256 KB. A free 256 KB block exists at 256. B gets it (wasted 16 KB).

C = 60 KB → 64 KB. Split the free 128 KB block at 128 into 64 @128 and 64 @192. C gets 64 @128 (wasted 4 KB).

D = 130 KB → 256 KB. No free 256 KB block left, so split the 512 KB block at 512 into 256 @512 and 256 @768. D gets 256 @512 (wasted 126 KB).

   0        128   192   256              512              768             1024
   +---------+-----+-----+----------------+----------------+----------------+
   | A (128) |  C  |free |    B (256)     |    D (256)     |   free (256)   |
   | uses 100| 64  | 64  |    uses 240    |    uses 130    |                |
   +---------+-----+-----+----------------+----------------+----------------+

Free lists:  64 KB: [192]     256 KB: [768]
Internal fragmentation: 28 + 16 + 4 + 126 = 174 KB

Look at D: it asked for 130 KB but got 256 KB, wasting almost half. Rounding up to powers of 2 can waste nearly 50% of a block in the worst case. This is the buddy system's weakness: internal fragmentation.

Now the strength: freeing and merging is very fast.

  • Free A (128 @0). Its buddy is 128 @128, but that block is split (C lives in it). No merge. Free lists: 64: [192], 128: [0], 256: [768].

  • Free C (64 @128). Its buddy 64 @192 is free → merge into 128 @128. That block's buddy 128 @0 (old A) is free → merge into 256 @0. Its buddy 256 @256 is B, still in use → stop. Free lists: 256: [0, 768].

  • Free B (256 @256). Its buddy 256 @0 is free → merge into 512 @0. Its buddy 512 @512 contains D → stop. Free lists: 256: [768], 512: [0].

Why finding a buddy is so cheap

For a block of size s (a power of 2) at address a (always a multiple of s), the buddy's address is just a XOR s. For example, the buddy of 64 @128 is 128 XOR 64 = 192, and the buddy of 128 @128 is 128 XOR 128 = 0. No searching through a list of neighbours is needed. Only two blocks that came from the same split can merge; 256 @256 and 256 @512 are adjacent but not buddies, so they never merge directly.

The buddy system on a real Linux machine

Linux shows the state of its buddy allocator in /proc/buddyinfo. Each column counts the free blocks of one order: order k means a block of 2k contiguous pages. Here is the real output from a WSL2 Linux system (kernel 6.18, page size 4096 bytes):

cat /proc/buddyinfo
Node 0, zone    DMA32      1      1      0      0      1      2      1      0      2      2    973
Node 0, zone   Normal    614    103     99    126     38     24     56     34     27     15   1338

The columns are orders 0 to 10. In the Normal zone there are 614 free single pages (4 KB), 103 free blocks of 2 pages (8 KB), and so on up to 1338 free blocks of order 10 (210 × 4 KB = 4 MB each). Your numbers will be different and change from moment to moment. If the right-hand columns drop towards zero while the left-hand columns are large, physical memory has become fragmented: plenty of free pages, but few large contiguous runs. The kernel needs such runs for things like huge pages and some device buffers, which is why Linux also has its own memory compaction.

So even on a modern system that uses paging for processes, the fragmentation ideas from this chapter are alive inside the kernel, and inside user-space allocators like malloc, which must carve variable-sized blocks out of the heap.


Contiguous Allocation Schemes Compared

Feature

Fixed partitioning

Variable partitioning

Buddy system

Block sizes

Set at boot, never change

Exactly the request size

Powers of 2

Internal fragmentation

Yes

No (except tiny rounding)

Yes, up to almost 50% of a block

External fragmentation

No new holes form, but free partitions can be too small for a waiting process

Yes, the main problem

Yes, but reduced by fast merging

Degree of multiprogramming

Fixed (= number of partitions)

Varies with process sizes

Varies

Bookkeeping

Very simple table

Free list; merging needed

One free list per size; buddy found with XOR

Example use

IBM OS/360 MFT, simple embedded systems

IBM OS/360 MVT

Linux physical page allocator


Practice Numericals

Q1. Fixed partitions of 200, 400, 600 and 500 KB (in that order). Processes of 357, 210, 468 and 491 KB arrive in order. Using best fit, which process cannot be allocated, and what is the total internal fragmentation of the others?

357 → 400 (43 left). 210 → the free partitions that fit are 600 and 500; the smallest is 500 (290 left). 468 → 600 (132 left). 491 → only 200 is free, too small, so 491 KB waits. Internal fragmentation = 43 + 290 + 132 = 465 KB.

Q2. Holes of 300, 120, 500 and 200 KB (in address order). A request of 180 KB arrives. Which hole does each of first, best and worst fit choose?

First fit: 300 (first one ≥ 180). Best fit: 200 (smallest ≥ 180). Worst fit: 500 (largest).

Q3. In a buddy system with 512 KB of memory, how much memory is actually given for requests of 33 KB, 64 KB and 65 KB?

33 KB → 64 KB (31 KB wasted). 64 KB → 64 KB (no waste). 65 KB → 128 KB (63 KB wasted). Requests just above a power of 2 waste nearly half the block.

Q4. Memory has holes of 100, 50 and 80 KB scattered between processes. A 200 KB process arrives. Can it be loaded? What can the OS do?

Total free = 230 KB, but the largest hole is 100 KB, so it cannot be loaded with contiguous allocation (external fragmentation). The OS can compact memory (if relocation is done at execution time) to create one 230 KB hole, or the process waits. With paging, the problem would not arise.


Common Mistakes

  • Mixing up internal and external fragmentation. Ask "is the wasted space inside a block someone owns?" If yes, it is internal. If it is free but in pieces that are too small, it is external.

  • Saying variable partitioning has internal fragmentation. In theory it does not; that is the whole point of sizing partitions exactly. Its problem is external fragmentation.

  • Forgetting to update the hole after allocation. In numericals, the leftover part of a hole stays in the list and can be used by the next request. Many wrong answers come from treating the whole hole as used.

  • Running worst fit on the original sizes. After every allocation the hole sizes change, so "the largest hole" must be recomputed each time.

  • Next fit pointer. Next fit continues from the hole where the last allocation happened, not from the hole after it, and it wraps around to the beginning.

  • Thinking compaction is always possible. It needs execution-time address binding, and it cannot freely move memory that a device is using for DMA.

  • Thinking best fit is always best. It leaves tiny useless holes, and counter-examples exist where first fit succeeds and best fit fails.

  • Merging blocks that are adjacent but not buddies in the buddy system. Only the two halves of the same split can merge.


Interview Questions

What is contiguous memory allocation?

Each process is given one single continuous block of physical memory. It is implemented with base (relocation) and limit registers, and it suffers from fragmentation.

What is the difference between internal and external fragmentation?

Internal fragmentation is wasted space inside an allocated block, because the block is bigger than the request. External fragmentation is free space split into holes that are each too small for a request, even though their total is enough.

Which fragmentation occurs in fixed partitioning, and which in variable partitioning?

Fixed partitioning mainly suffers from internal fragmentation. Variable partitioning suffers from external fragmentation.

Explain first fit, best fit and worst fit. Which is generally best?

First fit takes the first hole that is large enough, best fit the smallest hole that is large enough, worst fit the largest hole. Simulations show first fit and best fit beat worst fit; first fit is usually preferred because it is faster with similar utilisation.

What is the disadvantage of best fit?

It must search the whole list (unless the list is sorted by size), and it leaves very small leftover holes that are usually too small to be useful, increasing external fragmentation.

What is compaction and what does it require?

Compaction moves processes so that all free holes join into one large block. It requires dynamic (execution-time) relocation so a moved process keeps working after its base register is updated. It is expensive because it copies memory and must be repeated.

What is the 50-percent rule?

From Knuth's analysis of first fit: in steady state, with N allocated blocks there are about N/2 holes, so roughly 0.5N blocks are lost to fragmentation, meaning up to one-third of memory may be unusable.

How does the buddy system work, and where is it used?

Memory is handed out in power-of-2 blocks. Larger blocks are split in halves until the right size is reached, and a freed block is merged with its buddy (found by XOR of the address with the block size) when the buddy is also free. Linux uses it to allocate physical page frames.

How do paging and segmentation solve the problems of contiguous allocation?

They allow a process to be stored in several non-contiguous pieces. Paging uses fixed-size frames, which eliminates external fragmentation completely; segmentation uses variable-size segments, which reduces the problem but does not remove it.


Summary

  • Contiguous allocation gives each process one continuous block of physical memory, protected by base and limit registers.

  • Fixed partitioning (MFT) divides memory into partitions at boot; simple, but causes internal fragmentation and limits the number and size of processes.

  • Variable partitioning (MVT) creates exact-size partitions at run time; no internal fragmentation, but external fragmentation as holes form.

  • Placement: first fit (first big-enough hole), next fit (first fit from the last position), best fit (smallest big-enough hole), worst fit (largest hole). First fit and best fit beat worst fit; first fit is usually fastest.

  • Freed blocks must be merged with neighbouring holes.

  • The 50-percent rule: about N/2 holes for N blocks, so up to one-third of memory can be wasted.

  • Compaction joins the holes by moving processes; it needs execution-time binding and is expensive.

  • The buddy system uses power-of-2 blocks and fast XOR-based merging; it trades external fragmentation for internal fragmentation and is used by the Linux page allocator.

The real cure is to stop requiring one continuous block. In the next chapter, Paging, we cut both processes and memory into equal-sized pieces so that any free frame can hold any page, and external fragmentation disappears.