Solution

• When memory is assigned dynamically, the operating system must manage it.

• In general there are two ways to keep track of memory usage.

• Memory Management with Bitmap.
• Memory Management with Linked List.

Memory Management with Bitmap

• With bitmap, memory is divided into allocation units.

• Corresponding to each allocation unit there is a bit in a bitmap.

• Bit is 0 if the unit is free.

• Bit is 1 if unit is occupied.

• The size of allocation unit is an important design issue, the smaller the size, the larger the bitmap.

• The main problem is that when it has been decided to bring a k unit process, the memory manager must search the bitmap to find a run of k consecutive 0 bits in the map.

• Searching a bitmap for a run of a given length is a slow operation.

• Figure1 shows part of memory and the corresponding bitmap.

Memory Management with Linked List

• Another way to keep track of memory is to maintain a linked list of allocated and free memory segments, where segment either contains a process or is an empty hole between two processes.

• The memory of Fig1(a) is represented in Fig1(c) as a linked list of segments.

• Each entry in the list specifies a hole (H) or process (P), the address at which it starts the length and a pointer to the next entry.

Figure1(a) A part of memory with five processes and three holes. The tick marks show the memory allocation units. The shaded regions (0 in the bitmap) are free. (b) The corresponding bitmap. (c) The same information as a list.

• The segment list is kept sorted by address. Sorting this way has the advantage that when a process terminates or is swapped out, updating the list is straightforward.

• A terminating process normally has two neighbors (except when it is at the very top or bottom of memory).

• These may be either processes or holes, leading to the four combinations of Fig2. In Fig2(a) updating the list requires replacing a P by an H. In Fig2(b) and Fig2(c) two entries are merged into one, and the list becomes one entry shorter.

• In Fig2(d),three entries are merged and two items are removed from the list.

Figure2. Four neighbor combinations for the terminating process X.