在C內存池中對內存塊進行碎片整理

我在C中構建了一個簡單的內存池，並且我還實現了在此池中實現內存塊的功能。在C內存池中對內存塊進行碎片整理

內存塊本身非常簡單，只是一個帶有空白標誌和大小屬性的雙向鏈表。

我現在要做的是創建一個函數，該函數需要一個指向我的內存池的指針並對內部的內存塊進行碎片整理，以便分配的（free == 0）塊朝向池的開始並釋放塊正朝着游泳池的盡頭。

舉例來說，如果我有記憶的塊結構喜歡這個之前，我打電話給我的碎片整理功能：

Block Size: 25 (41 w/ header), Free: 1 
Block Size: 100 (116 w/ header), Free: 0 
Block Size: 25 (41 w/ header), Free: 1 
Block Size: 100 (116 w/ header), Free: 0 
Block Size: 100 (116 w/ header), Free: 0 
Block Size: 54 (70 w/ header), Free: 1

然後打電話給我的功能之後塊將被安排像這樣：

Block Size: 100 (116 w/ header), Free: 0 
Block Size: 100 (116 w/ header), Free: 0 
Block Size: 100 (116 w/ header), Free: 0 
Block Size: 25 (41 w/ header), Free: 1 
Block Size: 25 (41 w/ header), Free: 1 
Block Size: 54 (70 w/ header), Free: 1

我已經試圖建立功能，但是我遇到了移動正確的塊周圍的問題似乎因爲這是我的輸出後函數被稱爲：

Block Size: 100 (116 w/ header), Free: 0 
Block Size: 25 (41 w/ header), Free: 1 
Block Size: 100 (116 w/ header), Free: 0 
Block Size: 1744830464 (1744830480 w/ header), Free: 21

我並不確定函數執行的是不正確的操作，所以希望有人能爲我闡明一些。

我的碎片整理功能：

void defragment(Pool* pool) 
{ 
    if(pool && pool->root) 
    { 
     Block* current = pool->root; 

     while(current) 
     { 
      if(!current->free) 
      { 
       Block* current_prev = current->prev; 

       if(current_prev && current_prev->free) 
       { 
        Block* prev_prev = current_prev->prev; 
        int new_block_size = current_prev->size; 

        Block* moved_current = memmove(current_prev, current, sizeof(Block) + current->size); 

        if(!moved_current) 
        { 
         printf("couldn't move memory\n"); 
        } 
        else 
        { 
         Block* new_block = initBlock((((char*)moved_current) + sizeof(Block) + moved_current->size), new_block_size); 
         new_block->prev = moved_current; 
         new_block->next = moved_current->next; 

         moved_current->prev = prev_prev; 
         moved_current->next = new_block; 

         if(prev_prev) 
         { 
          prev_prev->next = moved_current; 
         } 

         current = moved_current; 
         continue; 
        } 
       } 
      } 

      current = current->next; 
     } 

     //Join Contiguous Blocks 
    } 
}

到initBlock函數的調用只是需要一個內存地址，將其視爲一個塊結構，然後設置自由屬性爲true和大小屬性爲給定大小。

我正在使用帶-std = C99標誌的GCC編譯器。

來源

2016-04-14 Liam Potter

分配的塊的所有者在重定位後會做什麼？ –

@WeatherVane目前，我並不需要擁有所有者持有的指針，因爲這是指向uni的指針。雖然擁有分配的中間目錄並且指針持續存在會使我獲得更高的分數，但它不是低分的要求。 –

碎片整理程序不知道用戶放置內存指針的位置，因此您無法更新它們。當然，你只能整理未使用的區域。就像您在整理硬盤時一樣，打開的文件無法移動。 –

看起來你沒有在交換一對塊之後更新下一個塊的prev字段。所以當你前進到下一個塊並檢查前面的塊是否空閒時，你將會訪問垃圾。你需要像

if (newblock->next) 
    new_block->next->prev = new_block;

在上面的else部分。

其他關注

這將嚴重行爲不當，如果你的塊不直接相鄰，並在游泳池內秩序。您可能確保整個池是一個連續的memeory塊，但如果其他例程重新排序，您可能仍會遇到問題。對於偏執狂編程來說，堅持斷言以確保這些不變式不被侵犯是一個好主意。
任何外部指針到池中，將垃圾這個操作
後，如果有奇數大小的塊（你出現），你會得到不對齊的指針，這充其量是低效的和最差可能會崩潰。
像你所描述的那樣，池中有一個包含指向池的指針的固定大小的「句柄」的關聯數組是非常正常的，並且每當你移動一個非空閒塊時，都需要更新指針對應的手柄。手柄還可能有禁止移動塊的「鎖定」標誌 - 在這種情況下，您需要檢查該標誌並僅移動未鎖定的塊，並且當您移動塊時，可能需要移動到不相鄰的塊中。這可能會讓你陷入上面的第一點。

來源

2016-04-14 20:18:12

在C內存池中對內存塊進行碎片整理

回答

相關問題