第三節(jié)首次適應(yīng)算法的分析

第三節(jié)首次適應(yīng)算法的分析第一頁(yè)，共三十一頁(yè)，2022年，8月28日深刻理解計(jì)算機(jī)上機(jī)編程：分配器首次適應(yīng)算法、最佳適應(yīng)算法、下一次適應(yīng)算法第二頁(yè)，共三十一頁(yè)，2022年，8月28日首次適應(yīng)算法分析#include<stdlib.h>void*malloc(size_t,size);malloc函數(shù)返回一個(gè)指針，指向大小為至少size字節(jié)的存儲(chǔ)器塊。如果malloc遇到問(wèn)題，那么返回NULL。注意：與教材中的malloc函數(shù)不同。第三頁(yè)，共三十一頁(yè)，2022年，8月28日f(shuō)ree函數(shù)釋放已經(jīng)分配的malloc塊#include<stdlib.h>voidfree(void*ptr)Ptr參數(shù)必須指向一個(gè)從malloc獲得的已經(jīng)分配塊的起始位置。第四頁(yè)，共三十一頁(yè)，2022年，8月28日malloc和free分配和釋放塊1234malloc(4*sizeof(int))123456789malloc(5*sizeof(int))1234free第二次分配的5個(gè)int123456malloc(2*sizeof(int))第五頁(yè)，共三十一頁(yè)，2022年，8月28日malloc算法分析首次適應(yīng)算法：從頭開(kāi)始搜索空閑鏈表，選擇第一個(gè)合適的空閑塊。將大的空閑塊保留在鏈表的后面。鏈表起始處留下小的空閑塊的碎片，增加了對(duì)較大塊的搜索時(shí)間。首次適應(yīng)算法速度很快，因?yàn)樗M可能少地搜索鏈表結(jié)點(diǎn)。下一次適應(yīng)算法和首次適應(yīng)算法很相似，是不過(guò)不是從鏈表的起始處開(kāi)始每次搜索，而是從上一次查詢(xún)結(jié)束的地方開(kāi)始。若上一次在一個(gè)空閑塊中發(fā)現(xiàn)足夠的空間，那么這一次也能在這個(gè)剩余塊中發(fā)現(xiàn)所需空間。比首次適應(yīng)算法快，利用率卻低。最佳適應(yīng)算法檢查數(shù)組的每一個(gè)空閑塊，選擇適合所需請(qǐng)求大小的最小空閑塊。第六頁(yè)，共三十一頁(yè)，2022年，8月28日內(nèi)存管理：使用coremap[]coremap[]按照map的起始地址排序。

第七頁(yè)，共三十一頁(yè)，2022年，8月28日首次適應(yīng)算法存儲(chǔ)管理器對(duì)coremap[]進(jìn)行搜索，直到找到一個(gè)足夠大的空閑區(qū)。若空閑區(qū)大小和要分配的空間大小正好一樣，否則將該空閑區(qū)分為兩部分，一部分供進(jìn)程使用，另一部分形成新的空閑區(qū)。第八頁(yè)，共三十一頁(yè)，2022年，8月28日教材p77的例題例題1.coremap[]:進(jìn)程申請(qǐng)空間大小是15（1）搜索coremap[]，找到第一個(gè)長(zhǎng)度>=15的空閑區(qū)2010coremap[2]5030coremap[1]10020coremap[0]0coremap[CMAPSIZ]……2010coremap[0]m_size=30>15，首次找到一個(gè)足夠大的空閑區(qū)5030coremap[1]m_size=10<15第九頁(yè)，共三十一頁(yè)，2022年，8月28日（2）空閑區(qū)的分配新的coremap[]數(shù)組5030coremap[1]分配15個(gè)塊出去，則：m_size=30-15=15，m_addr=50+15=65。2010coremap[2]6515coremap[1]10020coremap[0]0coremap[CMAPSIZ-1]……第十頁(yè)，共三十一頁(yè)，2022年，8月28日教材p78的例題例題2.coremap[]:進(jìn)程申請(qǐng)空間大小是30（1）搜索coremap[]，找到第一個(gè)長(zhǎng)度>=15的空閑區(qū)2010coremap[2]5030coremap[1]10020coremap[0]0coremap[CMAPSIZ]……2010coremap[0]m_size=30>=30，首次找到一個(gè)足夠大的空閑區(qū)5030coremap[1]m_size=10<15第十一頁(yè)，共三十一頁(yè)，2022年，8月28日例題2（2）空閑區(qū)的分配若m_size==0,則應(yīng)刪除這個(gè)元素，coremap[]數(shù)組剩下的元素向前移動(dòng)一個(gè)位置。5030coremap[1]分配30個(gè)塊出去，則：m_size=30-30=0，m_addr=50+30=80201010020coremap[1]coremap[0]0coremap[CMAPSIZ-2]……800coremap[1]有變化第十二頁(yè)，共三十一頁(yè)，2022年，8月28日malloc()函數(shù)malloc(mp,size)Structmap*mp;{registerinta;//a是malloc返回的分配區(qū)的起始?jí)K號(hào)registerstructmap*bp;//bp是工作塊

第十三頁(yè)，共三十一頁(yè)，2022年，8月28日malloc()for(bp=mp;bp->m_size;bp++)//搜索coremap[]if(bp->m_size>=size)//找到第一個(gè)空白區(qū)m_size>=size，則分配。a=bp->m_addr;//返回值為分配區(qū)域的起始?jí)K號(hào)bp->m_addr=+size;//空白區(qū)的起始地址變化if((bp->m_size=-size)==0)//若此map區(qū)域全部分配，則不能再認(rèn)為是coremap[]數(shù)組中的元素do{bp++;//從bp++開(kāi)始元素向前移動(dòng)一個(gè)位置(bp-1)->m_addr=bp->m_addr;第十四頁(yè)，共三十一頁(yè)，2022年，8月28日malloc()}while((bp-1)->m_size=bp->m_size);//最后一個(gè)元素的長(zhǎng)度為0，結(jié)束移動(dòng)return(a);//malloc()成功，則返回分配區(qū)的起始地址a}}return(0);}第十五頁(yè)，共三十一頁(yè)，2022年，8月28日所找到的空白區(qū)起始地址的改變所分配空白區(qū)的起始地址變化的原因：return(a)，而且a=m_addr若此空白區(qū)的起始地址不變化，則與a相同，引起混淆。所以，m_addr=m_addr+m_size第十六頁(yè)，共三十一頁(yè)，2022年，8月28日2.mfree()回收算法《現(xiàn)代操作系統(tǒng)》P105回收時(shí)有四種情況：1.aa與前空白區(qū)(bp-1)相鄰(bp-1).m_size=+size2.aa與前、后空白區(qū)相鄰(bp-1).m_size=+bp.m_sizecoremap[]元素向前移動(dòng)一個(gè)位置3.aa與后空白區(qū)相鄰bp.m_addr=aabp.m_size=+size4.aa不與任何空白區(qū)相鄰bp.m_addr=aa;bp.m_size=size;coremap[]的元素向后移動(dòng)一個(gè)位置，bp++第十七頁(yè)，共三十一頁(yè)，2022年，8月28日mfree()mfree(mp,size,aa)Structmap*mp;{registerstructmap*bp;registerintt;registerinta;第十八頁(yè)，共三十一頁(yè)，2022年，8月28日mfree()a=aa;for(bp=mp;bp->m_addr<=a&&bp->m_size!=0;bp++);if(bp>mp&&(bp-1)->m_addr+(bp-1)->m_size==a){//第一種情況(bp-1)->m_size=+size;//map(aa,size)回收到上一個(gè)空白區(qū)(bp-1)if(a+size==bp->m_addr){//第二種情況(bp-1)->m_size=+bp->m_size;//map(aa,size)使上一個(gè)和下一個(gè)空白區(qū)連起

第十九頁(yè)，共三十一頁(yè)，2022年，8月28日mfree()while(bp->m_size){//第二種情況coremap[]元素向前移動(dòng)一個(gè)位置bp++;(bp-1)->m_addr=bp->m_addr;(bp-1)->m_size=bp->m_size;}}}第二十頁(yè)，共三十一頁(yè)，2022年，8月28日mfree()else{//第三種情況map(aa,size)與下一個(gè)空白區(qū)相鄰if(a+size==bp->m_addr&&bp->m_size){bp->m_addr=-size;bp->m_size=+size;}第二十一頁(yè)，共三十一頁(yè)，2022年，8月28日mfree()elseif(size)do{//不能與上一個(gè)下一個(gè)空白塊合并t=bp->m_addr;//coremap[]增加一個(gè)節(jié)點(diǎn)bp->m_addr=a;//coremap[]數(shù)組的元素向后移動(dòng)一個(gè)位置a=t;t=bp->m_size;bp->m_size=size;bp++;}while(size=t);}}第二十二頁(yè)，共三十一頁(yè)，2022年，8月28日教材p79的例題例題3.coremap[]:回收區(qū)大小size=5，起始地址aa=40（1）搜索coremap[]，找到比回收區(qū)起始地址aa大的第一個(gè)空閑區(qū)。2010coremap[2]5030coremap[1]10020coremap[0]0coremap[CMAPSIZ]……2010coremap[0]m_addr=50>40，找到比回收區(qū)aa高的空閑區(qū)，bp=&coremap[1]5030coremap[1]m_addr=20<40第二十三頁(yè)，共三十一頁(yè)，2022年，8月28日（2）回收區(qū)的回收新的coremap[]數(shù)組405coremap[1]20+10<4040+5<50第四種情況2010coremap[2]405coremap[1]5030coremap[0]0coremap[CMAPSIZ-1]……coremap[2]10020coremap[]數(shù)組的元素從bp開(kāi)始，向后移動(dòng)一位。第二十四頁(yè)，共三十一頁(yè)，2022年，8月28日教材p79的例題例題3.coremap[]:回收區(qū)大小size=10，起始地址aa=40（1）搜索coremap[]，找到比回收區(qū)起始地址aa大的第一個(gè)空閑區(qū)。2010coremap[2]5030coremap[1]10020coremap[0]0coremap[CMAPSIZ]……2010coremap[0]m_addr=50>40，找到比回收區(qū)aa高的空閑區(qū)，bp=&coremap[1]5030coremap[1]m_addr=20<40第二十五頁(yè)，共三十一頁(yè)，2022年，8月28日例題4（2）回收區(qū)的回收新的coremap[]數(shù)組4010coremap[1]20+10<4040+10=50第三種情況2010coremap[2]4040coremap[1]10020coremap[0]0coremap[CMAPSIZ-1]……4040coremap[1]m_addr=40m_size=10+30=40coremap[]數(shù)組元素不必改變位置。第二十六頁(yè)，共三十一頁(yè)，2022年，8月28日下一次適應(yīng)算法最佳適應(yīng)算法最差適應(yīng)算法《現(xiàn)代操作系統(tǒng)》P105第二十七頁(yè)，共三十一頁(yè)，2022年，8