Compaction in OS

As we know, fixed and dynamic partitioning suffers from external fragmentation. However, this issue can be overcome through compaction.

In compaction, all the holes are contiguous, and OS combines all the loaded processes in different partitions. 

Now, merged holes can accommodate new processes according to their needs. This method is also known as de-fragmentation. Let us explain through the diagram.

After compaction, the process P8 can be loaded into the main memory easily because contiguous space is available now.

Problems with Compaction in OS

The system’s efficiency also decreases because the CPU is set to idle at the time of compaction.

Explanation: At the time of compaction, the CPU stops the execution of the current process because it will resume the process from somewhere else after compaction. If the CPU does not stop the execution of a process, then it may execute the instructions from somewhere else locations instead of the next instruction of the same process in memory.

Note: Consider an OS that requires 6 NS time to transfer 1-B. Then, 1 MB transfer needs (1 X 2^20) X (6 X 10 ^ -9) seconds. So, transferring a large amount of data requires a huge amount of time.

In Fixed partitioning, the list of partitions is made once and will never change.

But In Dynamic partitioning, Allocation and de-allocation take place very frequently. So, partition size also changes each time in allocation and de-allocation. That’s why it is very difficult for OS to manage everything at a time. OS uses the following data structures for memory allocation and de-allocation.

1. Bit Map
2. Linked List

1. 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.

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.

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.

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.

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 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.

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. Lets understand it

2. Linked List In Dynamic Partitioning

A linked list is used to find free or filled partitions in dynamic partitioning. In the link list, there are different nodes and partitions available where one node represents one partition, and the other node represents the other node. OS maintains the Link List.

Every node has three fields.

• First field: The first field of the node holds a flag bit (0, 1), which shows whether the partition is a free/hole or some process is inside.
• Second field: The second field of the node stores the starting index of the partition.
• Third field: The third field of the node stores the end index of the partition.

Types of Linked Lists in Dynamic Partitioning

1. Single Link List

Single link list, traverse only in the forward direction. It can detect only holes or processes but cannot merge the adjacent holes.

2. Double Link List

Double link list, traverse in both forward and backward directions. It can detect holes and merge the adjacent partitions of holes.

Advantages of double linked list over single link list

Reduce the No. of Partitions will increase the degree of multi-programming.