[發(fā)明專利]面向?qū)崟r系統(tǒng)的內(nèi)存算法

有效

• 申請?zhí)枺?/td>: 201210263549.0
• 申請日: 2012-07-28
• 公開（公告）號: CN102880555A
• 公開（公告）日: 2013-01-16
• 發(fā)明（設(shè)計）人: 吳英杰;王一蕾;夏李波;唐文斌;許孝盛
• 申請（專利權(quán)）人: 福州大學(xué)
• 主分類號: G06F12/06
• 分類號: G06F12/06
• 代理公司: 福州元創(chuàng)專利商標(biāo)代理有限公司 35100
• 代理人: 蔡學(xué)俊

1.一種面向?qū)崟r系統(tǒng)的內(nèi)存算法，其特征在于：采用紅黑樹數(shù)據(jù)結(jié)構(gòu)用于快速查找所需的內(nèi)存塊；該算法定義以下四類紅黑樹：

占用紅黑樹???????????????????????????????????????????????：用于存放被占用的內(nèi)存塊信息，同時將該內(nèi)存塊的內(nèi)存ID作為比較規(guī)則，當(dāng)程序釋放內(nèi)存時迅速根據(jù)內(nèi)存ID定位到該內(nèi)存塊，釋放內(nèi)存；

空閑紅黑樹數(shù)組：定義到共18棵紅黑樹，分別對應(yīng)內(nèi)存大小標(biāo)記為1，2，3，4，6，…，，，…，512單位的內(nèi)存塊，每組紅黑樹以地址為比較規(guī)則，存放大小大于等于該組標(biāo)記但小于下一組標(biāo)記的內(nèi)存塊信息；

向后合并紅黑樹：用于在內(nèi)存回收過程中快速查找到能與釋放內(nèi)存塊向后合并的內(nèi)存塊；當(dāng)有內(nèi)存釋放時，將與釋放內(nèi)存塊相鄰的下一內(nèi)存塊的首地址作為比較規(guī)則，迅速查找出可合并塊，并定位到空閑紅黑樹數(shù)組的相應(yīng)位置進(jìn)行相關(guān)內(nèi)存合并操作；

向前合并紅黑樹：用于在內(nèi)存回收過程中快速查找到能與釋放內(nèi)存塊向前合并的內(nèi)存塊；當(dāng)有內(nèi)存釋放時，將與釋放內(nèi)存塊相鄰的上一內(nèi)存塊的尾地址作為比較規(guī)則，迅速查找出可合并塊，并定位到空閑紅黑樹數(shù)組的相應(yīng)位置進(jìn)行相關(guān)內(nèi)存合并操作；

當(dāng)有一個大小為d的內(nèi)存申請時，按如下方法進(jìn)行內(nèi)存分配：

步驟1.1：通過查詢的大小域，定位到第一個滿足需求d的組，即；從k鏈表開始，為后面的每一個鏈表的統(tǒng)計值加1，表明從k鏈表開始的所有后續(xù)鏈表里的內(nèi)存塊都有能力提供需求為d的內(nèi)存；由于及后面各組紅黑樹內(nèi)的任意一個內(nèi)存塊均大于等于d，可選取該列表中的第一塊內(nèi)存；如果的鏈表為空，則該內(nèi)存區(qū)間不存在空閑的內(nèi)存塊，繼續(xù)向后面的紅黑樹尋找直至找到存在空閑塊的組，獲取該組的第一塊；如果后續(xù)組別中均不存在空閑塊，返回第一個滿足需求d的組的前一個組，該組里的內(nèi)存塊大小在區(qū)間內(nèi)，可能存在滿足需求的塊；

步驟1.2：獲取滿足需求的空閑內(nèi)存塊，如果的大小剛好滿足需求d，即，該塊將被完全占用；如果的大小超出需求d，則判斷是否需要分割，如果被分割，將產(chǎn)生大小為的剩余塊，判斷剩余塊大小是否小于限定值，是則將直接完全分配而不做分割，否則將分割，插入相應(yīng)的空閑組中；

步驟1.3：維護(hù)相關(guān)紅黑樹：將滿足需求的空閑內(nèi)存塊從、、中刪除，并加入；如果有剩余塊產(chǎn)生，根據(jù)剩余塊的大小，加入相應(yīng)的組內(nèi)，同時以的首尾地址為比較規(guī)則，分別加入和；

當(dāng)有一個ID為id、大小為d的內(nèi)存塊需要釋放時，按如下方法進(jìn)行內(nèi)存釋放：

步驟2.1：在中查詢ID為id的內(nèi)存塊，根據(jù)該塊的首地址和末尾地址查詢和，判斷是否存在可與合并的向前合并塊、向后合并塊或其中之一，如果存在，將合并為新的大內(nèi)存塊，然后插入相關(guān)紅黑樹，如果不存在，則直接將插入相關(guān)紅黑樹；

步驟2.2：更新紅黑樹：將從中刪除；如果存在和或其中之一，將、或其中之一從相應(yīng)、、中刪除，并將合并后的新的大內(nèi)存塊加入相應(yīng)的、、，如果不存在，則直接將加入相應(yīng)的、、。