Memory management with Linked list and Bit maps

Lists of Descriptive Questions Answers and Short Study Notes On Operating System – Memory management with Linked list and Bit maps

  • (1) Explain memory management with Linked list and Bit maps.


Question- Explain memory management with Linked list and Bit maps.


  • 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.
  • Figure below 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 Fig. below(a) is represented in Fig. below(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

Memory Management with Bitmap

Figure (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 Fig. below. In Fig. below(a) updating the list requires replacing a P by an H. In Fig. below(b) and Fig. below(c) two entries are merged into one, and the list becomes one entry shorter.
  • In Fig. below(d), three entries are merged and two items are removed from the list.

Memory Management with Bitmap-2