Bit Map in Dynamic Partitioning

A Bit Map is a data structure that stores the details about the allocation and reallocation of processes. For this purpose, the main memory is divided into the number of allocation units. One or more allocation units may assign to single process according to the need of that process. Size of each allocation unit is same which is fix by OS, that never changed. Although, the partition size from process to process may vary due to dynamic partitioning.

The main task of OS is to check whether the partitions are filled or free. For this purpose, flag bits are used. either process or hole in Allocation memory is represented by a flag bit of bitmap. 0 represents the Hole, and 1 represents the Process in the bit map.

Let’s explain Bit Map in Dynamic Partitioning with Example

Suppose we have a main memory of 7 Byte. Where 2Bytes are allocated to Process 1, 3Bytes are allocated to Process 2, and 2Bytes are allocated to Process 3. After some time, Process 2 complete its execution, which creates a hole of 3 bytes in the main memory shown in the below diagram.

Bit Map in Dynamic Partitioning

Let’s divide the main memory in allocation units and size of each allocation unit is fix to 4-bit (1/2Byte). As the size of the allocation unit is Half Byte, Process 1 will occupy  4 allocation units because of the 2Byte Memory size, and in the same way, Process 2 will contain 6 allocation units as shown in the below diagram.

Bit Map in Dynamic Partitioning example- to solution

To keep track allocated and holes OS use Bit map data structure in main memory. Bit map contains either value 1 or 0.  The total No of bits in the bit map will always equal the Total No of Allocation units in the main memory. In using diagram 14 allocation units are required to represent 7-Byte memory So, 14 bits are required for bit map. Each allocation unit is represented by 1-bit of bit-map data structure as shown in the following diagram. The corresponding bit for the process is 1, and for hole is 0.

Bit Map in Dynamic Partitioning

Assume a process 4 of size 1Byte wants to load in main memory then OS will scan the Bit map and search the contagious number of Zero’s. If space is available, then that process will load successfully. So P4 will load successfully, and its corresponding bits turn to 1 as shown in the below diagram.

bit map in dynamic partitioning example to solution

At this point suppose Process 3 is complete then its corresponding bits in bit-Map turn to 0 as explain in the following diagram.

Bit Map in Dynamic Partitioning example

Conclusion:

When a process complete it execution period, then its memory becomes free available which is a de-allocation method. And all its corresponding bits in bit-Map turn to Zero.

when a process loads in the main memory, then its corresponding bits in bit-Map turn to 1, which is an allocation method.

Disadvantages of Using Bitmap

1. The OS has to assign some memory for bitmap to store the details about allocation and de-allocation.

The smaller the size of the allocation unit, the more will be memory required for Bit-Map. Explained Under

if Size of 1 allocation unit = 4 bits (1/2 Byte) then
Size of bitmap = total main memory/ (size of allocation unit in bit + bit required for bit-map) 
                      = 1/(4+1)= 1/5 of total main memory.   

If Size of 1 allocation unit = 8 bits (1 Byte) 
Size of bitmap = total main memory/ (size of allocation unit in bit + bit required for bit-map) 
                      = 1/ (8+1) = 1/9 of total main memory.   

If we increase the size of allocation unit then size of bit-map will reduced but some space may waste as given below in diagram. Because, two processes cannot exist in one allocation unit at a time, but one process can exist in more than one contiguous allocation units.

Bit Map in Dynamic Partitioning disadvantages

2. To find any hole in the memory, the OS has to search for 0s in the bitmap. This search takes a lot of time, which makes the system inefficient.

This search happens through link-list. we will see the link-list in the next post.