Memory Allocation and Reclamation

1. Memory Allocation

There are three main allocation methods:

1.1. Single Contiguous Allocation

Can only be used in single-user, single-process operating systems. Memory is divided into a system area and a user area. The system area is used to run the operating system, and the user area is used to run a process.

1.2. Fixed Partition Allocation

Supports multiprogramming. Memory space is divided into several fixed-size areas. Each partition is provided to only one program and they do not interfere with each other.

1.3. Dynamic Partition Allocation

Memory space is allocated dynamically according to the actual needs of the process.

1.3.1. Data Structures

1.3.1.1. Free Table

As shown in the figure, an array is used to describe memory space: 0 means free, and 1 means not free.

1.3.1.2. Free List

As shown in the figure, a linked list is used to describe memory space, and each node records storage capacity. Adjacent free memory spaces can be merged.

1.3.2. Allocation Algorithms

1.3.2.1. First Fit (FF)

Search sequentially from the beginning for a suitable free space; if none is found, allocation fails.

1.3.2.2. Best Fit (BF)

Sort free spaces first, then traverse them to find the most suitable free area.

1.3.2.3. Quick Fit (QF)

There are multiple free lists, and each list stores free areas of the same capacity.

2. Memory Reclamation

There are mainly four cases:

In every case, partitions are merged and the starting address is used.