實現顯式空閒列表內存分配

作爲賦值的一部分，我們必須實現（基本）malloc函數（我們應該以某種方式模擬動態內存分配）。我已經實現了基於隱式自由列表的解決方案，但問題是我得到的利用率僅爲50％，吞吐量僅爲9％（我必須獲得90％的利用率+吞吐量）。隱式自由列表的問題是需要大量的時間搜索空閒塊。所以我想實施explicit free list看看程序能改進多少。現在的問題是我必須跟蹤免費塊的next/prev指針。由於我只能使用標量變量，並且不能使用任何類型的數據結構，例如：鏈表，結構等，我無法實現它。有人能指出我如何跟蹤C中的（虛擬）指針嗎？實現顯式空閒列表內存分配

感謝，

來源

2014-10-18 aaa

你是什麼意思「不能使用任何類型的數據結構，如：鏈表」，但不知何故，你*可以*有「下一個/先行指針」？有些東西沒有意義。 – 2014-10-18 10:24:28

@luserdroog所以我們不允許使用任何類型的數據結構。但明確的空閒列表跟蹤下一個/ prev空閒塊。換句話說，顯式自由列表是一種算法，我必須實現它。[顯式免費列表]（http://www.eecs.harvard.edu/~mdw/course/cs61/mediawiki/images/b/b9 /Lectures-malloc2.pdf） – aaa 2014-10-18 10:36:13

好的。所以你不能「使用（預先寫好的）鏈表」，因爲*這是一個鏈表。對？ – 2014-10-18 10:58:37

從幻燈片（在評論的鏈接）的圖像，我覺得你預計存儲鏈接作爲整數偏移。

在C中，這真的是最好的結構描述。

struct alloc_cell { 
    int size; 
    int forward; 
    int back; 
    int data[]; 
};

現在，他也有在最後重複的大小，這是很難用結構來描述。 ~~目前尚不清楚它有多必要。~~它用於邊界合併。

編輯：很久以後，考慮評論。

即使您不能在代碼中使用結構，您仍然可以在僞代碼中使用它們來幫助組織您的思維。結構字段都是相同的類型，自然映射到一個數組，該數組可以通過指向第一個成員/元素的指針訪問。

struct alloc_cell { // int *cell; 
    int size;   // cell[0] // *cell 
    int forward;  // cell[1] 
    int back;   // cell[2] 
    int data[];  // (cell+3)[...] // &cell[3] 
};

你甚至可以走那麼遠，給這些偏移記憶的名字（但是這可能被視爲矯枉過正和不必要的混淆）。

enum { SIZE, FORWARD, BACK, DATA }; 

cell[SIZE];     // alloc_cell.size 
cell[FORWARD];    // alloc_cell.forward 
cell[BACK];     // alloc_cell.back 
cell+DATA; // &cell[DATA]  // alloc_cell.data

來源

2014-10-18 11:06:38

以及我想使用結構，但正如我所說，結構也是不允許的。只有標量變量， – aaa 2014-10-18 12:15:25

實現顯式空閒列表內存分配

回答

相關問題