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.

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

linked-list-three-nodes

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.

SINGLE linked list in Dynamic-Partitioning

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.

Double linked list in Dynamic-Partitioning exp

Advantages of double linked list over single link list

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