链表动态分区

跟踪自由或填充分区的更好和最流行的方法是使用链表。

在这种方法中，操作系统维护一个链表，每个节点代表每个分区。 每个节点都有三个字段。

1. 节点的第一个字段存储一个标志位，该标志位显示该分区是一个洞还是某个进程在里面。
2. 第二个字段存储分区的起始索引。
3. 第三个字段存储分区的结束索引。

如果某个分区在某个时间点被释放，那么该分区将与其相邻的空闲分区合并，而不会做任何额外的工作。

在使用这种方法时需要注意一些要点。

1. 操作系统必须非常清楚要添加到链表中的新节点的位置。 但是，根据起始索引的增加顺序添加节点是可以理解的。
2. 由于双链表中的节点也可以跟踪其之前的节点，所以使用双链表将会对性能产生一些积极影响。