Bit Map in Dynamic Partitioning

Bit Map is a data structure to store the details about allocation and reallocation of process. 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 Hole and 1 represents the Process in bit map.

Let’s explain Bit Map in Dynamic Partitioning with Example

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

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

To keep track allocated and holes OS use Bit map data structure in main memory. Bit map contains either value 1 or 0.  Total No of bits in bit map will always equal to Total No of Allocation units in 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. Corresponding bit for process is 1 and for hole is 0.

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 turns to 1 as shown in below diagram.

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

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 turns to Zero.

when a process load in main memory then its corresponding bits in bit-Map turns to 1 which is a 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.

Smaller the size of allocation unit more will be the 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.

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

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