內存分配算法

我們如何可以實現分配&軌道內存有以下限制內存分配算法

比方說你有記憶1個KB單位。需要2kB的之間分配 -

對於例如

A- 1

B-1

C-4

d-2

0 64KB的存儲1 2 3 4 5 6 7 8 9 10

X A X BCCCCD d X

如果我們在最小地址可用分配內存，當我們的分類（顯示爲X以上）存儲器，我們將有碎片。所以在上面的例子中，即使3單元是空閒的，我們也不能分配3個連續單元的內存。

「最小碎片」是不是約束，而是一個優化目標。 – nneonneo 2013-02-20 01:55:24

是的 - 它是，堆內存管理難題簡而言之:)將剩餘的3K分配爲一個塊的唯一方法是重新定位已分配的塊，這意味着要跟蹤指向它的指針。 – 2013-02-20 01:58:48

即使有一個表維護引用空閒空間的指針列表，我們如何獲得O（1）我正在尋找設計DS解決此問題的方法。 – SheldonCooper 2013-02-20 02:04:26

搜索「好友系統」或「哥們內存分配」。這可能是您找到的最佳解決方案。雖然，它不純粹是O（1），它由一些內部分裂受到影響，外部碎片還可能發生......

你能避免內部碎片完全通過使用擴充樹，但後來操作採取O（日誌N）時間。而且你仍然有外部碎片。

2013-02-20 03:46:55 comocomocomocomo

回答