Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 66 ยท Memory Management

The Buddy System and Swapping

See how the buddy allocator splits and merges power-of-two blocks, why the buddy address is a single XOR, and how swapping moves whole processes to disk.

Variable partitions waste little memory inside blocks, but they leave holes that are slow to search and hard to merge. Fixed partitions are simple but waste space. The buddy system is a compromise that is still used today inside the Linux kernel's page allocator. This lesson also covers swapping, the technique that lets the total memory demand of all processes exceed physical memory.

The buddy system

Memory is treated as one large block whose size is a power of two (for example 1024 KB). Every allocation request is rounded up to the next power of two. To serve a request, the allocator:

  1. Finds the smallest free block that is large enough.
  2. If that block is much bigger than needed, splits it into two equal halves, called buddies. One half is kept for further splitting, the other goes on the free list.
  3. Repeats until the block is the right size, then hands it out.

When a block is freed, the allocator looks at its buddy. If the buddy is also free, the two merge back into a block of double size, and the check repeats upward.

flowchart TD
    A["1024"] --> B["512"]
    A --> C["512 (free)"]
    B --> D["256"]
    B --> E["256 (free)"]
    D --> F["128: allocated (request 100)"]
    D --> G["128 (free)"]

A 100 KB request becomes 128 KB. Splitting 1024 left behind free blocks of 512, 256 and 128.

Finding the buddy with XOR

Because blocks are aligned to their size, two buddies differ in exactly one bit of their address: the bit equal to the block size. So

buddy_address = address XOR size

A block of size 128 at address 256 has its buddy at 256 XOR 128 = 384; the block at 384 has its buddy at 256. No search is required, which makes merging fast.

Python A buddy allocator you can watch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After the last release, everything merges back into one 1024 block: the free-list structure recovers completely, which is the strength of the design. The weakness is internal fragmentation: a request for 129 units takes 256, wasting almost half. On average the waste is about 25 percent.

Because of this, the Linux kernel uses the buddy system for page frames (blocks of 1, 2, 4, ... pages, called "orders"), where requests are naturally page-sized, and then puts a slab allocator on top to carve small kernel objects (such as process descriptors or file structures) out of those pages without waste.

Swapping

A process must be in memory to run, but not all processes need to be in memory all the time. Swapping temporarily moves a whole process out of main memory to a backing store (a fast disk or SSD area) and brings it back later. The total memory of all processes can then exceed physical RAM, which raises the degree of multiprogramming.

  • Swap out: the OS picks a process (a blocked or low-priority one), writes its memory image to the swap area, and frees its memory.
  • Swap in: when the process should run again, it is read back, possibly into a different location (this needs execution-time binding).

A process waiting for I/O on a buffer in its own memory must not be swapped out, because the I/O device would write into memory that now belongs to someone else. The OS either never swaps such processes or performs the I/O into kernel buffers.

The cost of swapping

Swapping is slow because it copies a lot of data. The transfer time is proportional to the amount of memory moved. A swap out followed by a swap in costs two transfers plus disk latency.

Python How long does a swap take?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With a spinning disk, swapping a 200 MB process out and in takes about 4 seconds, so a scheduler that swaps on every time slice would spend almost all its time moving data. This is why the scheduler gives swapped-out processes a long time in memory once they are brought in, and why standard swapping of whole processes is rare today.

Swapping in modern systems

Modern operating systems do not swap complete processes. They swap pages (paging): only some parts of a process are moved to disk, and only when memory is short. Terminology still uses "swap": the Linux swap partition/file and the Windows pagefile are page-level swap areas. In a phone or tablet OS there is usually no swap at all: flash storage wears out and is slow compared to RAM, so these systems instead ask apps to free memory and may terminate background apps, relying on apps to save their state.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A buddy allocator with 1024 KB receives a request for 70 KB. What size block does it hand out?

    Requests are rounded up to the next power of two: 70 becomes 128.
  2. 2. Where is the buddy of a 64 KB block at address 192?

    192 XOR 64 = 128: the buddy is found by flipping the bit equal to the block size.
  3. 3. Which problem does the buddy system mostly suffer from?

    Rounding requests up wastes space inside allocated blocks, on average about a quarter.
  4. 4. Why can a process with pending I/O into its own memory not simply be swapped out?

    The device uses physical addresses. After the memory is reused the incoming data would corrupt another process.
  5. 5. Why do phone operating systems usually avoid swapping to flash storage?

    Heavy swap traffic would shorten flash life and make the device slow.

Summary

  • The buddy system hands out power-of-two blocks, splitting larger ones and merging free buddies; the buddy address is address XOR size.
  • It merges quickly and avoids external fragmentation of the large blocks, at the cost of internal fragmentation (about 25% on average).
  • Linux uses it for page frames, with slab allocators for small kernel objects.
  • Swapping moves processes (today, mostly individual pages) between RAM and a backing store; transfer time makes it expensive.

Next: Paging and Page Tables