Summary of Free Space List (FSL) Management for Contiguous Memory Management

Summary of Free Space List (FSL) Management for Contiguous Memory Management

The FSL is just a linked list of “holes” (unused blocks) of main memory:

We only need two pieces of information about a hole: its size and its base physical address in memory. Not that it really matters  we’re not going to be coding this stuffbut here’s what the key declarations might look like in the C code of the operating system:

typedefstruct hole

{

unsigned intsizeOfHole;

unsigned intbaseOfHole;

struct hole *nextHole; /* pointer to the next hole in the FSL */

} HOLE;

HOLE *FSL;

A process’s physical address space, you should remember, comes in four sections:

1. Text section (a.k.a. code section), containing the instructions produced by the compiler
2. Data section, containing global and static variables produced by the compiler
3. Stack section, where local variables and function arguments are placed and removed dynamically (by your program during its execution) as blocks or functions are entered and exited dynamically
4. Heap section, where storage dynamically requested by the program (e.g., malloc) is allocated

Whenever a new process applies for admission, the amount of memory it needs is equal to the size of the load module for the program that will execute in the process plus the OS default for the stack section plus the OS default for the heap section. (The load module created by the compiler and linker already contains the text and data sections.)

The long term scheduler asks the free space manager if there’s enough memory for the new process. The free space manager searches the free space list. Assuming a big enough hole exists, it is removed from the free space list and its base address supplied to the loader. The free space manager than creates a new, smaller hole whose size is what was left over after some of the old hole was allocated to the new process and whose base address is the old hole’s base plus the size of the new process. E.g., if the old hole started at address 15000 and was of size 4K and the new process needed 3K, the new process will be loaded at 15000 and the new hole of size 1K starts at 18000. The new hole must then be inserted into the free space list

When a process is terminated, the free space manager reclaims its memory by creating a new hole where the process used to be, searching the FSL to see if the new hole is adjacent to some existing hole and, if so, merging them into a bigger new hole, and then inserting the new (possibly now bigger) holeinto the free space list.

• The FSL is an unordered list
• When a process needs memory for admission, the list is searched from the beginning and the first hole found that’s big enough is the one that gets used.
• When a new hole is created (after a new process’s required memory is taken from a bigger hole or after a process terminates and its memory is released), it doesn’t matter where it goes in the list, we can put it (the new hole) wherever is easiest (usually the front of the list)

1. Fastest insertion into FSL  whenever a new hole is created, it can go right at the front of the list, no searching for the right spot to insert it.
2. Less likely than best fit to create stupidly small holes, so it delays external fragmentation better than best-fit

• The FSL is an ordered list, ordered by ascending size, smallest hole at the front.
• When admitting a new process and thus searching for the best fit, the first hole that’s big enough is the best fit (since the list is ordered).
• Inserting a new hole also requires searching for the right spot to keep the list ordered.

1. Creates smaller holes than the other alternatives so excessive fragmentation (unusable memory in many small holes) happens earliest.
2. Searching to find the right spot to admit a new process or to insert a new hole usually takes longer than first fit since the list must be searched from the front and the front fills up with the unusable small holes.

• The FSL is an ordered list, ordered by descending size, largest hole at the front.
• Admitting a new process uses the first hole on the list.
• Inserting a new hole still requires searching the list to find the right spot (to keep the list ordered)

1. Fastest at finding the right hole to admit a new process, it’s memory is always taken from the biggest hole which is always at the front, so the list doesn’t have to be searched at all to admit a process.
2. Least likely to create a useless small hole so it delays excessive external fragmentation the longest