【正文】 (1) 為了說明哪些分區(qū)是空閑的，可以用來裝入新作業(yè)，必須要有一張空閑區(qū)說明表，如表 31 所示。 31 主存空間占用情況 表 31 空閑區(qū)說明表 其中，起始地址指出各空閑區(qū)的主存起始地址，長度指出空閑區(qū)大小。 狀態(tài)有： 未分配：該欄目是記錄的有效空閑區(qū)。 操作系統(tǒng)(10KB) 作業(yè)1(10KB) 作業(yè)4(25KB) 空閑區(qū)1(20KB) 作業(yè)2(45KB) 空閑區(qū)2(146KB) 起始地址 長度 狀態(tài) 45K 20KB 未分配 110K 146KB 未分配 空表目 空表目 空表目 … … … 0 10K 20K 45K 65K 110K 256K 內(nèi)蒙古工業(yè)大學(xué) 課設(shè) 4 空表目：沒有登記信息。 由于分區(qū)個數(shù)不定，所以空閑區(qū)說明表中應(yīng)有足夠的 空表目項。否則造成溢出，無法登記。 同樣，再設(shè)一個已分配區(qū)表，記錄作業(yè)或進(jìn)程的主存占用情況。 (2) 當(dāng)有一個新作業(yè)要求裝入主存時，必須查空閑區(qū)說明表，從中找出一個足夠大的空閑區(qū)。有時找到的空閑區(qū)可能大于作業(yè)需求量，這時應(yīng)將空閑區(qū)一分為二。一個分給作業(yè)；另一個仍作為空閑區(qū)留在空閑區(qū)表中。為了盡量減少由于分割造成的碎片，盡可能分配低地址部分的空閑區(qū)，將較大空閑區(qū)留在高地址端，以利于大作業(yè)的裝入。為此在空閑區(qū)表中，按空閑區(qū)首地址從低到高進(jìn)行登記。為了便于快速查找，要不斷地對表格進(jìn)行緊縮，即讓“空表目”項留在表的 后部。 (3) 當(dāng)一個作業(yè)執(zhí)行完成時，作業(yè)所占用的分區(qū)應(yīng)歸還給系統(tǒng)。在歸還時要考慮相鄰空閑區(qū)合并的問題。作業(yè)的釋放區(qū)與空閑區(qū)的鄰接分以下 4 種情況考慮： A．釋放區(qū)下鄰 (低地址鄰接 )空閑區(qū)； B．釋放區(qū)上鄰 (高地址鄰接 )空閑區(qū)； C．釋放區(qū)上下都與空閑區(qū)鄰接； D．釋放區(qū)與空閑區(qū)不鄰接。 數(shù)據(jù) 結(jié)構(gòu) 的設(shè)計 區(qū)說明表的設(shè)計 struct freearea { int startaddress。 /*空閑區(qū)的起始地址號 */ int size。 /*空閑區(qū)的大小 */ int state。 /*空 閑區(qū) 狀態(tài)： 0 為 空表目 ,1 為 可用空 閑塊 */ }freeblock[N]={{100,100,1},{10,10,1},{300,50,0},{20,35,1},{250 ， 30,1},{600,200,0}}。 說明：設(shè)置空閑區(qū) 為結(jié)構(gòu)體類型 ，并且為其初始化 ，構(gòu)成空閑區(qū)表的分區(qū) 內(nèi)蒙古工業(yè)大學(xué) 課設(shè) 5 已分配區(qū)說明表設(shè)計 struct fullarea { int address。 /*分配作業(yè)的首地址 */ int sizes。 /*分配作業(yè)的大小 */ }fullblock[N]。 說明：設(shè)置已分配區(qū)說明表為結(jié)構(gòu)體類型，構(gòu)成已分配區(qū)表的分區(qū) 內(nèi)蒙古工業(yè)大學(xué) 課設(shè) 6 第 四 章 詳細(xì)設(shè)計 菜單模塊 為了操作界面的人性化和美觀，為模擬系統(tǒng)開辟一個操作菜單，通過 switch() case 的方法來實現(xiàn)，其核心代碼為 int start。 char t。 while(c) { system(cls)。 muen()。 printf( 請選擇操作編號 :)。 scanf(%d,amp。b)。 switch(b) { case 1: system(cls)。 printf(\n 系統(tǒng)原有內(nèi)存空閑區(qū)分表和已分配表區(qū)如下 :\n\n)。 order()。order1()。show()。 printf(\n 請輸入作業(yè)申請量 :)。 scanf(%d,amp。a)。 order()。 start=alloc(a,d)。d++。 if(start==1) { system(cls)。 printf(\n \1 內(nèi)存中沒有符合的空閑區(qū)可供分配 !等待釋放內(nèi)存中 ~~\n)。 內(nèi)蒙古工業(yè)大學(xué) 課設(shè) 7 Sleep(1*1000)。system(cls)。 show()。 setfree()。 break。 } system(cls)。 printf(\n \1 系統(tǒng)采用最佳適應(yīng)算法正在為作業(yè)分配內(nèi)存中?? \n\n)。 Sleep(1*1000)。system(cls)。 printf(\n \1 系統(tǒng)為作業(yè)分配內(nèi)存成功 !:\n\n)。 order()。order1()。 Sleep(1*1000)。system(cls)。 break。 case 2: system(cls)。 order()。show()。setfree()。system(cls)。 order1()。 for(i=0。iN。i++) { if(fullblock[i].address==0) { d=i。 break。 } } printf(\n \1 系統(tǒng)正在回收為作業(yè)分配的內(nèi)存中?? \n\n)。 Sleep(1*1000)。system(cls)。 printf(\n \1 系統(tǒng)回收內(nèi)存成功 !:\n\n)。 order()。 Sleep(1*1000)。system(cls)。 內(nèi)蒙古工業(yè)大學(xué) 課設(shè) 8 break。 case 3: system(cls)。 t=getchar()。 printf(\n)。 order()。 show()。 printf(\n \1 按回車鍵返回主菜單 ~\n\n)。 if((t=getchar())==39。\n39。) break。 case 0: if(b==0) c=0。 break。 default: system(cls)。 printf(\n 輸入有誤 ,請重新選擇 !\n)。 Sleep(2*1000)。system(cls)。 } } 分配方法模塊 首次適應(yīng)算法分配概念 首次適應(yīng)算法要求可用表或自由鏈按起始地址遞增的次序排列。該算法的最大特點是一旦找到大于或等于所要求內(nèi)存長度的分區(qū)，則結(jié)束探索。然后該算法從所找到分區(qū)中畫出所要求的內(nèi)存長度分配給用戶，把余下的部分進(jìn)行合并（如果有相鄰空閑區(qū)存在）后留在可用表中，但要修改其相應(yīng)的表項。 內(nèi)蒙古工業(yè)大學(xué) 課設(shè) 9 等于 小于 大于 N Y N Y 數(shù)據(jù)流程圖 核心代碼 int alloc(int a,int b) { int i,j,tag=0。j=b。 for(i=0。iN。i++) if(freeblock[i].state==1amp。amp。freeblock[i].sizea) 開始 申請XK 主存 J=0 J=J+1 查看第 J個表目的登記項 狀態(tài)為“未分配”嗎 ? 長度 =XK? 置狀態(tài)為“空表目” 將空表目向后移 長度 =長度－ XK 始址 =始址＋ XK 作業(yè)等待 返回 登記已分配區(qū)表和空閑區(qū)表，輸出系統(tǒng)中各數(shù)據(jù)結(jié)構(gòu)的值。返回分配給作業(yè)的主存始址。 J 為空閑區(qū)說明表的最后一個表目？ 內(nèi)蒙古工業(yè)大學(xué) 課設(shè) 10 { freeblock[i].startaddress=freeblock[i].startaddress+a。 freeblock[i].size=freeblock[i].sizea。 fullblock[j].address=freeblock[i].startaddressa。 fullblock[j].sizes=a。 tag=1。 return freeblock[i].startaddressa。 break。 } else if (freeblock[i].state==1amp。amp。freeblock[i].size==a) { freeblock[i].state=0。 fullblock[j].address=freeblock[i].startaddress。 fullblock[j].sizes=a。 tag=1。 return freeblock[i].startaddress。 break。} if(tag==0) return 1。} 內(nèi)存釋放模塊 概念 當(dāng)一個作業(yè)執(zhí)行完成時，作業(yè)所占用的分區(qū)應(yīng)歸還給系統(tǒng)。由于每個作業(yè)或進(jìn)程所用的內(nèi)存長度不一 樣而出現(xiàn)大量分散，較小的空閑區(qū)。這樣造成內(nèi)存大量的浪費。解決這個辦法之一就是在空閑區(qū)回收時，把不連續(xù)的空閑區(qū)集中起來。 釋放區(qū)與上下臨界區(qū)的關(guān)系 A．釋放區(qū)下鄰 (低地址鄰接 )空閑區(qū)：將釋放區(qū)與下空閑區(qū)合并，將其釋放區(qū)的首地址作為合并區(qū)的首地址，合并區(qū)的長度為釋放區(qū)與下空閑區(qū)長度之和。 B．釋放區(qū)上鄰 (高地址鄰接 )空閑區(qū)：將釋放區(qū)與下空閑區(qū)合并，將其上臨區(qū)的首地址作為合并區(qū)的首地址，合并區(qū)的長度為釋放區(qū)與下空閑區(qū)長度之和。 C．釋放區(qū)上下都與空閑區(qū)鄰接：釋放區(qū)作為一個新的可用區(qū)插入可用表。 D．釋 放區(qū)與空閑區(qū)不鄰接：將三個空閑區(qū)合并為一個空閑區(qū)，新空閑區(qū)的首地址為上空閑區(qū)的首地址，大小為三個空閑區(qū)之和。合并后，取消可用表下空閑區(qū)，修改上空閑區(qū)的對應(yīng)項。 內(nèi)蒙古工業(yè)大學(xué) 課設(shè) 11 N Y N Y Y N Y N 數(shù)據(jù)流程圖 開始 S=釋 放區(qū)始址 L= 釋放區(qū)長度 查空閑區(qū)說明表 有與釋放區(qū)的高地址鄰接 (上鄰 )的空閑區(qū)嗎？ 有與釋放區(qū)下鄰的空閑區(qū)嗎？ 在空閑區(qū)說明表中找一空表目登記：始址 =S 長度=L 狀態(tài) =未分配 按地址順序調(diào)整和緊縮空閑區(qū)說明表 上空閑區(qū)首地址為總地址，大小為兩個大小之和 上空閑區(qū)首地址為總地址，大小為兩個大小之和 L=L＋上鄰空閑區(qū)長度 有與釋放區(qū)下鄰的空閑區(qū)嗎？ 把上鄰空閑區(qū)登記欄中的始址改為 S，長度改為 L 把上鄰空閑區(qū)登記欄中的狀態(tài)置為“空表目”，且將空表目向后調(diào)整。 把下鄰空閑區(qū)登記欄中的長度改為： 長度 =長度＋L 有等待裝入的作業(yè)嗎？ 返回 喚醒等待的作業(yè)并返回 圖 33 首次適應(yīng)算法回收框圖 內(nèi)蒙古工業(yè)大學(xué) 課設(shè) 12 核心代碼 voidsetfree() { int s,l,i,j,k。 /*tagl 代表釋放區(qū)的高地址是否鄰接一個空閑區(qū) ,tag2 代表釋放區(qū)的高低地址是否都鄰接一個空閑區(qū) ,tag3 代表釋放區(qū)的低地址是否鄰接一個空閑區(qū) */ printf(\n\n 請輸入需要釋作業(yè)的首地址 :)。 scanf(%d,amp。s)。 /*輸入釋放區(qū)的開始地址 */ printf(\n 輸入作業(yè)的大小 :)。 scanf( %d,amp。l)。 /*輸入釋放區(qū)的大小 */ for(k=0。kN。k++) { if(fullblock[