Computer Science

FreetheMalloc Special – Chapter 1: Computer Memory: Memory Management

But wait, How does the Operating System decide which free block in memory to use?

Selection Strategies for Linked Lists

  • Best-Fit: Allocate the smallest but sufficient Piece of memory
    • In an ideal use case, there should be no waste of memory
  • Nearest-Fit: Select an arbitrary point for Allocation and starting that point run the First-Fit search.
    • Not relevant to RAM, but for Hard-Drives:
      • minimum head movement
      • better positioning of often used data
  • Worst-Fit: Find and allocate the biggest free memory block
    • biggest possible rest block is still free

Allocation Architecture Idea 2: Object Pools/Slabs

The biggest problem of linked list architecture is its tendency to external fragmentation.

A Solution:

Supply often used allocation sizes – independent from word size of memory – without causing fragmentation.

But How?

Slab allocation was first introduced in Solaris 2.4 kernel and used widely by many *nix-like operating systems.

The main idea behind Slab Allocation is that the initialization and destruction of data in memory outweigh the cost of memory allocation. In other words, effect of consuming CPU cycles for mentioned mechanism on performance is more important than memory allocation, mainly because of low memory costs compared to CPU’s

I am not going to dive deep into Slab allocation, because it needs an article of its own, but you can check out the Wikipedia Article.

  • At first memory demand that passes one of the often-used memory size (say 10kb), a slab of pre-defined total size will be created
an example slab

After the initialization of slab, only thing left to do is to update the free-list, or rarely when all slabs are full, creating another slab.

No Fragment while pre-defined sizeDifferent sized memory allocations cause internal fragmentation
Easy (fast) to find a free block
– total full slabs can be just skipped
– only the passing sized slabs are considered
– no traversing, only a glance at slab’s free-list
Bad choice of sizes or too random behaviour cause too much empty slabs
– gigantic overhead

Leave a Reply

Your email address will not be published. Required fields are marked *