Malloc分配方案

Question

是的，我正在參加計算機系統課程。 我有幾個關於實現malloc的分配方案的問題。 對於顯式列表，如果我使用類LIFO堆棧實現malloc，指向先前釋放內存的指針的目的究竟是什麼？就像爲什麼你需要雙向鏈表？單鏈表不會同樣工作嗎？

Malloc lecture. 我發現這個鏈接在線，你可以看看幻燈片7看看我在說什麼。

查看分隔列表分配方案時，這些列表是單向的嗎？而且，合併機制到底是什麼？比如說，如果釋放4個單詞，當你將它插回到相應的隔離鏈接列表中之前，你是否會首先嚐試並在它周圍的空閒空間中加入它？或者，您是否會簡單地將4個字塊插入相應分離鏈接列表的「4個字」部分？

謝謝。

Answer 1

由於釋放塊總是有兩個指針的空間，爲什麼不雙向鏈接列表？它簡化了合併代碼，因此在遍歷列表時不必維護尾隨指針。它還允許在任何方向上遍歷列表，以防列表中的哪一端可能更接近開始搜索。我曾經看過的一個不起眼的系統在最後一次活動發生的「中間」保留了一個指針。

釋放塊時。只有四種可能的情況：

• 空閒塊是相鄰的後一個空閒塊。
• 免費區塊在之前是相鄰的免費區塊。
• 空閒塊在它之前和之後的兩個空閒塊之間並且相鄰。
• 空閒塊不與任何空閒塊相鄰。

聚結相鄰的空閒塊的目的是：

• 降低鏈表的長度
• 以準確地反映一個空閒塊的尺寸而無需負擔分配器向前看看如果兩個塊是相鄰

排序空閒塊成特定長度的空閒列表通常具有的好處，但在大多數實際實施方式中，聚結是一個優先級，以便一個alloc()當有許多不同大小的空閒塊時，不會不恰當地拒絕請求不同大小的塊。