FOR FREE YEAR SOLVED

Bit Map for Dynamic Partitioning

For the compaction method in dynamic memory allocation, we need to maintain the number of holes (free space) and the number of allocated space in memory. One of the data-structure to keep track of these holes and allocation areas is Bit Map or Bit vector. 

In the bit map, each block is represented by 1 bit. If the block is free, the bit is 1; if the block is allocated, the bit is 0.

For example, consider a memory where blocks 1, 2, 3, 8, and 9 are free and the rest of the blocks are allocated. The free-space bit map would be

Advantage:

The main advantage of this approach is its relative simplicity and its efficiency in finding the first free block or consecutive free holes on memory. 

For example, if P1 allocated unit 4,5,6 and 7 so, when P1 is finished then, then all allocation unit of this space is going to one and there is no need to combine other holes (1's), it is automatically combined with other 1's and make a hole.

Disadvantage:

It is a complex thing to find the free hole from memory, it requires a complex algorithm to check the hole by check contiguous 0's.

Another disadvantage if the allocation unit is large, i.e. if the allocation unit large one of the allocated processes may contain half of the allocation unit and it is not possible to maintain half of the allocation is a hole and half of the allocation process (allocated), it can do one thing either 0 or 1.  So, half of the allocation unit is wastage.

Anyway, the bitmap is not an efficient data structure compared to a linked list.   A long-ago bit map was used, but now bit map is not used nowadays.

Free space (holes) management by Linked List at Dynamic Partition

Free hole management by Linked List:

Now consider a memory scenario

# Here 0-99 memory is occupied by P1 and 200-299 is occupied by P2.  Other (100-199), (300-399) is a hole (free space).

Now we use a data structure linked list to maintain the number of holes and allocated space in the memory

Here design the link linked where inserts data or information memory allocation into the node as allocation as increasing order of start position because if one process will free and brought out, then it is easier to merge the hole.

# And it is better to use a double-linked list, to keep track of the previous one, if P2 is certainly free then it checks not only forward for hole, it also checks that previous one is a hole or not, then merge together.

# Here linked list takes lesser memory compare to the bit map.

Necessary criteria

1) Increasing order of start address

2) Double linked list