[發明專利]一種恢復被破壞的空閑內存鏈表的方法

有效

• 申請號: 201310204921.5
• 申請日: 2013-05-28
• 公開（公告）號: CN104182291B
• 公開（公告）日: 2018-04-20
• 發明（設計）人: 汪革;茍利平;李俊盛;劉基永;于雯
• 申請（專利權）人: 上海博達數據通信有限公司
• 主分類號: G06F11/08
• 分類號: G06F11/08
• 代理公司: 上海天翔知識產權代理有限公司31224
• 代理人: 劉粉寶

1.一種恢復被破壞的空閑內存鏈表的方法，其特征在于，所述方法利用內存管理冗余信息恢復被破壞的空閑內存鏈表；所述方法恢復被破壞的空閑內存鏈表的具體步驟如下：

（1）形成所有空閑地址為連續的空閑內存鏈表，且空閑鏈表控制塊記錄空閑塊的首地址、空閑塊的大小和結束地址信息；

（2）從空閑內存鏈表分配地址時，檢查空閑塊是否有效；組成的空閑內存鏈表進行內存分配時，檢查鏈表控制塊C中記錄的空閑塊數目是否為0，如果為0，表明本空閑鏈表已經全部分配出去，返回空指針，結束處理；否則從鏈表控制塊C中得到空閑鏈表指針L，取L的首節點N，并檢查其有效性，方法為查看N地址在不在鏈表控制塊C中記錄的起始地址和結束地址范圍內，N地址與C中記錄的起始地址之差是不是空閑塊大小(空閑鏈表中所有空閑塊大小都相同，其大小在鏈表控制塊C中記錄)的整數倍，檢查成功，則設置節點N中的冗余頭部中各域：記錄分配內存地址、設置標志位為分配狀態，并把節點N中記錄的下一空閑塊指針賦值于鏈表控制塊C中的空閑鏈表指針域，把鏈表控制塊C中記錄的空閑塊數目減1，此次內存分配成功，返回空閑塊地址，記為F，結束處理；

（3）檢查到空閑塊出現錯誤時，設置標志，表明此空閑內存鏈表出現錯誤，后續禁止從該鏈分配地址，并根據空閑鏈表控制塊記錄的空閑塊首地址、空閑塊大小和結束地址等冗余信息開始該內存鏈表的整理過程；

（4）從空閑塊的起始地址開始，把所有空閑的空閑塊重新組成一空閑鏈表；

（5）把在上述整理過程中釋放的內存塊組成另一空閑鏈表；

（6）將上述兩個鏈表合并，組成新的空閑內存鏈表；

（7）處理結束，后續內存申請從新的鏈表中分配。

2.根據權利要求1所述的一種恢復被破壞的空閑內存鏈表的方法，其特征在于，所述步驟（1）中組成空閑內存鏈表的過程如下：

（11）首先，根據鏈表中空閑塊數目和每塊大小及其鏈表控制塊等冗余信息計算出此空閑鏈表需要的所有內存大小，并分配內存；

（12）把分配內存的地址即空閑塊的起始地址、結束地址、空閑塊大小、數目等記錄到鏈表控制快中，每個空閑塊具有冗余頭部，用來記錄分配的地址、該塊內存處于分配或空閑狀態及下一塊的指針，并初始化每塊頭部，所有空閑塊組成空閑內存鏈表。

3.根據權利要求1所述的一種恢復被破壞的空閑內存鏈表的方法，其特征在于，所述步驟（6）鏈表合并方法為將步驟（4）形成的空閑鏈表插入到步驟（5）中空閑鏈表的尾部，形成一個新的空閑鏈表。