使用位圖與鏈接列表的內存管理

有兩種內存管理方式：使用位和使用鏈表。在使用位，我們維持大小等於分配單元數的位圖在使用喜歡的列表中，我們維護兩個鏈表：一個是分配的內存，以及一個用於孔使用位圖與鏈接列表的內存管理

有人可以幫我鑑定利弊以及這兩種方法的缺點，以及我們何時應該寧願選擇另一種方法。我已經理解了這兩種方法，但是當我更喜歡一種方法時，無法確定情況。

爲了進一步闡明，這兩種技術都是操作系統書籍中使用的標準技術。

2012-02-12 TimeToCodeTheRoad

如何考慮上下文中的兩個結構？例如。如果你需要分配，你使用每種方法做什麼，它有多容易，有多快，它有多大的可擴展性？然後想想每個結構本身。考慮到系統中N個字節的內存總數，每個內存需要多少內存？然後想一想，如果你能做出改進，比如加速搜索漏洞。這不是非常困難，只要把事情放在正確的背景下。 – 2012-02-12 10:29:05

鏈表

優點：小空間的需求，因爲每個區塊可存儲一個指向下一個空閒塊。

缺點：要遍歷列表，您需要讀取每個塊！而且，爲了避免碎片化（考慮以更聰明的方式更新列表的成本，而不是在最後追加每個新的空閒塊的成本），以「連續」方式維護列表是昂貴的。

通過在每個塊中存儲多個空閒塊ID（因此需要更少的I/O來檢索一定量的空閒塊），可以使鏈接列表方案稍微高效。

位圖

優點：隨機分配：檢查是否一個塊空閒只需要讀取的相應位;此外，檢查一個大的連續區域是相對較快的（因爲您可以在一次讀取中檢查位圖中字的大小）。快速刪除：只需輕輕一點就可以「釋放」一個塊，而不會覆蓋數據。

缺點：需要更高的內存需求，因爲每塊需要一位（1KB塊的1TB磁盤需要128MB）。

交易性

如果磁盤幾乎已滿，它可能是有意義的使用鏈表，因爲這將需要比位圖少塊。但是，大多數情況下位圖將存儲在主內存中，這會使其比鏈接列表更有效。我想如果磁盤快滿了，你可以將鏈表存儲在主內存中，那麼這也是一個很好的選擇。

另請參閱：https://en.wikipedia.org/wiki/Free_space_bitmap

來源

2016-12-20 17:42:10 Bacon

使用位圖與鏈接列表的內存管理

回答

相關問題