連結串列動態分割區


跟蹤自由或填充分割區的更好和最流行的方法是使用連結串列。

在這種方法中,作業系統維護一個連結串列,每個節點代表每個分割區。 每個節點都有三個欄位。

  1. 節點的第一個欄位儲存一個標誌位,該標誌位顯示該分割區是一個洞還是某個進程在裡面。
  2. 第二個欄位儲存分割區的起始索引。
  3. 第三個欄位儲存分割區的結束索引。

如果某個分割區在某個時間點被釋放,那麼該分割區將與其相鄰的空閒分割區合併,而不會做任何額外的工作。

在使用這種方法時需要注意一些要點。

  1. 作業系統必須非常清楚要新增到連結串列中的新節點的位置。 但是,根據起始索引的增加順序新增節點是可以理解的。
  2. 由於雙連結串列中的節點也可以跟蹤其之前的節點,所以使用雙連結串列將會對效能產生一些積極影響。