Chapter 17 free space management

The problems to be solved in this chapter are :

To meet variable length allocation requests , How to manage free space ? What strategies can minimize fragmentation ? How about the time and space cost of different methods ?

17.1 hypothesis

A data structure that manages free space on the heap is often called a free list (free list). This structure contains references that manage all free blocks in the memory area .

17.2 Underlying mechanism

1. Split and merge
2. Track the size of allocated space
3. Embed free list
4. Let the heap grow

17.3 Basic strategy

1. The best match ： First, traverse the entire free list , Find a free block of the same or larger size as the request , And then go back to the smallest one in the group .
2. The worst match ：, It tries to find the largest free block , After segmenting and meeting user needs , Put the remaining blocks ( It's big ) Join the free list
3. Match for the first time ： Find the first big enough block , Return the requested space to the user
4. Next time match ： A pointer , Point to where the last lookup ended

17.4 The other way

Detach the free list ： If an application frequently applies for one ( Or several ) Size of memory space , So use a separate list , Only manage objects of this size . Requests of other sizes are allocated to more general memory allocators

Buddy system ： In this system , Free space is first conceptually considered to be the size of 2N The big space . When there is a memory allocation request , Free space is recursively split in two , Until it just meets the size of the request ( It's not enough to divide into two ). At this time , The requested block is returned to the user .