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

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

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

第13頁，共31頁，2023年，2月20日，星期三malloc()for(bp=mp;bp->m_size;bp++)//搜索coremap[]if(bp->m_size>=size)//找到第一個空白區(qū)m_size>=size，則分配。a=bp->m_addr;//返回值為分配區(qū)域的起始塊號bp->m_addr=+size;//空白區(qū)的起始地址變化if((bp->m_size=-size)==0)//若此map區(qū)域全部分配，則不能再認(rèn)為是coremap[]數(shù)組中的元素do{bp++;//從bp++開始元素向前移動一個位置(bp-1)->m_addr=bp->m_addr;第14頁，共31頁，2023年，2月20日，星期三malloc()}while((bp-1)->m_size=bp->m_size);//最后一個元素的長度為0，結(jié)束移動return(a);//malloc()成功，則返回分配區(qū)的起始地址a}}return(0);}第15頁，共31頁，2023年，2月20日，星期三所找到的空白區(qū)起始地址的改變所分配空白區(qū)的起始地址變化的原因：return(a)，而且a=m_addr若此空白區(qū)的起始地址不變化，則與a相同，引起混淆。所以，m_addr=m_addr+m_size第16頁，共31頁，2023年，2月20日，星期三2.mfree()回收算法《現(xiàn)代操作系統(tǒng)》P105回收時有四種情況：1.aa與前空白區(qū)(bp-1)相鄰(bp-1).m_size=+size2.aa與前、后空白區(qū)相鄰(bp-1).m_size=+bp.m_sizecoremap[]元素向前移動一個位置3.aa與后空白區(qū)相鄰bp.m_addr=aabp.m_size=+size4.aa不與任何空白區(qū)相鄰bp.m_addr=aa;bp.m_size=size;coremap[]的元素向后移動一個位置，bp++第17頁，共31頁，2023年，2月20日，星期三mfree()mfree(mp,size,aa)Structmap*mp;{registerstructmap*bp;registerintt;registerinta;第18頁，共31頁，2023年，2月20日，星期三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)回收到上一個空白區(qū)(bp-1)if(a+size==bp->m_addr){//第二種情況(bp-1)->m_size=+bp->m_size;//map(aa,size)使上一個和下一個空白區(qū)連起

第19頁，共31頁，2023年，2月20日，星期三mfree()while(bp->m_size){//第二種情況coremap[]元素向前移動一個位置bp++;(bp-1)->m_addr=bp->m_addr;(bp-1)->m_size=bp->m_size;}}}第20頁，共31頁，2023年，2月20日，星期三mfree()else{//第三種情況map(aa,size)與下一個空白區(qū)相鄰if(a+size==bp->m_addr&&bp->m_size){bp->m_addr=-size;bp->m_size=+size;}第21頁，共31頁，2023年，2月20日，星期三mfree()elseif(size)do{//不能與上一個下一個空白塊合并t=bp->m_addr;//coremap[]增加一個節(jié)點(diǎn)bp->m_addr=a;//coremap[]數(shù)組的元素向后移動一個位置a=t;t=bp->m_size;bp->m_size=size;bp++;}while(size=t);}}第22頁，共31頁，2023年，2月20日，星期三教材p79的例題例題3.coremap[]:回收區(qū)大小size=5，起始地址aa=40（1）搜索coremap[]，找到比回收區(qū)起始地址aa大的第一個空閑區(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第23頁，共31頁，2023年，2月20日，星期三（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開始，向后移動一位。第24頁，共31頁，2023年，2月20日，星期三教材p79的例題例題3.coremap[]:回收區(qū)大小size=10，起始地址aa=40（1）搜索coremap[]，找到比回收區(qū)起始地址aa大的第一個空閑區(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第25頁，共31頁，2023年，2月20日，星期三例題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ù)組元素不必改變位置。第26頁，共31頁，2023年，2月20日，星期三下一次適應(yīng)算法最佳適應(yīng)算法最差適應(yīng)算法《現(xiàn)代操作系統(tǒng)》P105第27頁，共31頁，2023年，2月20日