計(jì)算機(jī)操作系統(tǒng)內(nèi)存管理系統(tǒng)可變分區(qū)存儲(chǔ)管理方式的內(nèi)存分配回收

/課程設(shè)計(jì)2可變分區(qū)存儲(chǔ)管理方式的內(nèi)存分配回收一、課程設(shè)計(jì)目的深入了解采用可變分區(qū)存儲(chǔ)管理方式的內(nèi)存分配回收的實(shí)現(xiàn)。二、預(yù)備知識(shí)存儲(chǔ)管理中可變分區(qū)的管理方式。三、小組成員四、課程設(shè)計(jì)內(nèi)容編寫程序完成可變分區(qū)存儲(chǔ)管理方式的內(nèi)存分配回收。具體包括：確定內(nèi)存空間分配表；采用最優(yōu)適應(yīng)算法完成內(nèi)存空間的分配和回收；編寫主函數(shù)對(duì)所做工作進(jìn)行測(cè)試。五、設(shè)計(jì)思路：整體思路：可變分區(qū)管理方式將內(nèi)存除操作系統(tǒng)占用區(qū)域外的空間看做一個(gè)大的空閑區(qū)。當(dāng)作業(yè)要求裝入內(nèi)存時(shí),根據(jù)作業(yè)需要內(nèi)存空間的大小查詢內(nèi)存中的各個(gè)空閑區(qū),當(dāng)從內(nèi)存空間中找到一個(gè)大于或等于該作業(yè)大小的內(nèi)存空閑區(qū)時(shí),選擇其中一個(gè)空閑區(qū),按作業(yè)需求量劃出一個(gè)分區(qū)裝人該作業(yè),作業(yè)執(zhí)行完后,其所占的內(nèi)存分區(qū)被收回,成為一個(gè)空閑區(qū)。如果該空閑區(qū)的相鄰分區(qū)也是空閑區(qū),則需要將相鄰空閑區(qū)合并成一個(gè)空閑區(qū)。設(shè)計(jì)所才用的算法：采用最優(yōu)適應(yīng)算法,每次為作業(yè)分配內(nèi)存時(shí),總是把既能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)。但最優(yōu)適應(yīng)算法容易出現(xiàn)找到的一個(gè)分區(qū)可能只比作業(yè)所需求的長(zhǎng)度略大一點(diǎn)的情行,這時(shí),空閑區(qū)分割后剩下的空閑區(qū)就很小以致很難再使用,降低了內(nèi)存的使用率。為解決此問題,設(shè)定一個(gè)限值minsize,如果空閑區(qū)的大小減去作業(yè)需求長(zhǎng)度得到的值小于等于minsize,不再將空閑區(qū)分成己分分區(qū)和空閑區(qū)兩部分,而是將整個(gè)空閑區(qū)都分配給作業(yè)。內(nèi)存分配與回收所使用的結(jié)構(gòu)體：為便于對(duì)內(nèi)存的分配和回收,建立兩張表記錄內(nèi)存的使用情況。一張為記錄作業(yè)占用分區(qū)的"內(nèi)存分配表",內(nèi)容包括分區(qū)起始地址、長(zhǎng)度、作業(yè)名/標(biāo)志〔為0時(shí)作為標(biāo)志位表示空欄目；一張為記錄空閑區(qū)的"空閑分區(qū)表",內(nèi)容包括分區(qū)起始地址、長(zhǎng)度、標(biāo)志〔0表空欄目,1表未分配。兩張表都采用順序表形式。關(guān)于分配留下的內(nèi)存小碎片問題：當(dāng)要裝入一個(gè)作業(yè)時(shí),從"空閑分區(qū)表"中查找標(biāo)志為"1"〔未分配且滿足作業(yè)所需內(nèi)存大小的最小空閑區(qū),若空閑區(qū)的大小與作業(yè)所需大小的差值小于或等于minsize,把該分區(qū)全部分配給作業(yè),并把該空閑區(qū)的標(biāo)志改為"0"〔空欄目。同時(shí),在已分配區(qū)表中找到一個(gè)標(biāo)志為"0"的欄目登記新裝人作業(yè)所占用分區(qū)的起始地址,長(zhǎng)度和作業(yè)名。若空閑區(qū)的大小與作業(yè)所需大小的差值大于minsize。則把空閑區(qū)分成兩部分,一部分用來裝入作業(yè),另外一部分仍為空閑區(qū)。這時(shí)只要修改原空閑區(qū)的長(zhǎng)度,且把新裝人的作業(yè)登記到已分配區(qū)表中。內(nèi)存的回收：在可變分區(qū)方式下回收內(nèi)存空間時(shí),先檢查是否有與歸還區(qū)相鄰的空閑區(qū)〔上鄰空閑區(qū),下鄰空閑區(qū)。若有,則將它們合件成一個(gè)空閑區(qū)。程序?qū)崿F(xiàn)時(shí),首先將要釋放的作業(yè)在"內(nèi)存分配表"中的記錄項(xiàng)的標(biāo)志改為"0"〔空欄目,然后檢查"空閑區(qū)表"中標(biāo)志為‘1’〔未分配的欄目,查找是否有相鄰的空閑區(qū),若有,將之合并,并修改空閑區(qū)的起始地址和長(zhǎng)度。六：數(shù)據(jù)結(jié)構(gòu)〔1已分配表的定義：struct{floataddress;//已分分區(qū)起始地址floatlength; //已分分區(qū)長(zhǎng)度,單位為字節(jié)intflag; //已分配區(qū)表登記欄標(biāo)志,"0"表示空欄目,實(shí)驗(yàn)中只支持一個(gè)字符的作業(yè)名}used_table[n]; //已分配區(qū)表〔2空閑分區(qū)表的定義：struct{floataddress; //空閑區(qū)起始地址floatlength; //空閑區(qū)長(zhǎng)度,單位為字節(jié)intflag; //空閑區(qū)表登記欄標(biāo)志,用"0"表示空欄目,用"1"表示未分配}free_table[m]; //空閑區(qū)表<3>全局變量floatminsize=5;#definen10 //假定系統(tǒng)允許的最大作業(yè)數(shù)量為n#definem10 //假定系統(tǒng)允許的空閑區(qū)表最大為m七、核心算法：//最優(yōu)分配算法實(shí)現(xiàn)的動(dòng)態(tài)分區(qū)intdistribute<intprocess_name,floatneed_length>{ inti,k=-1; //k用于定位在空閑表中選擇的未分配欄 floatads,len; intcount=0; i=0; //核心的查找條件,找到最優(yōu)空閑區(qū)while<i<=m-1>//循環(huán)找到最佳的空閑分區(qū) { if<free_table[i].flag==1&&need_length<=free_table[i].length> { count++; if<count==1||free_table[i].length<free_table[k].length> k=i; } i=i+1; } if<k!=-1> { if<<free_table[k].length-need_length><=minsize>//整個(gè)分配 { free_table[k].flag=0; ads=free_table[k].address; len=free_table[k].length; } else { //切割空閑區(qū) ads=free_table[k].address; len=need_length; free_table[k].address+=need_length; free_table[k].length-=need_length; } i=0; //循環(huán)尋找內(nèi)存分配表中標(biāo)志為空欄目的項(xiàng)while<used_table[i].flag!=0> {i=i+1;} if<i<=n-1>//找到,在已分配區(qū)表中登記一個(gè)表項(xiàng) { used_table[i].address=ads; used_table[i].length=len; used_table[i].flag=process_name; count1++; }else//已分配區(qū)表長(zhǎng)度不足 { if<free_table[k].flag==0>//將已做的整個(gè)分配撤銷 { free_table[k].flag=1; free_table[k].address=ads; free_table[k].length=len; }else//將已做的切割分配撤銷 { free_table[k].address=ads; free_table[k].length+=len; } cout<<"內(nèi)存分配區(qū)已滿,分配失敗！\n"; return0; } } else { cout<<"無法為該作業(yè)找到合適分區(qū)！\n"; return0; } returnprocess_name;}八、程序流程圖：作業(yè)分配流程圖：內(nèi)存回收流程圖：九、程序說明：本程序采用VisualC++編寫,模擬可變分區(qū)存儲(chǔ)管理方式的內(nèi)存分配與回收。假定系統(tǒng)允許的最大作業(yè)數(shù)量為n=10,允許的空閑區(qū)表最大項(xiàng)數(shù)為m=10,判斷是否劃分空閑區(qū)的最小限值為minsize=5。初始化用戶可占用內(nèi)存區(qū)的首地址為1000,大小為1024B。定義兩個(gè)結(jié)構(gòu)體及其對(duì)象free_table[m]和used_table[n]實(shí)現(xiàn)內(nèi)存的分配回收及分配表和空閑表的登記。用最優(yōu)分配算法實(shí)現(xiàn)動(dòng)態(tài)分配時(shí),調(diào)用intdistribute<intprocess_name,floatneed_length>內(nèi)存分配函數(shù),設(shè)定循環(huán)條件查找最佳空閑分區(qū),定義intk以記錄最佳空閑區(qū)的首地址,根據(jù)找到的空閑區(qū)大小和作業(yè)大小判斷是整個(gè)分配給作業(yè)還是切割空閑區(qū)后再分配給作業(yè),并在"內(nèi)存分配表"和"空閑分區(qū)表"中作登記。調(diào)用intrecycle<intprocess_name>函數(shù)實(shí)現(xiàn)內(nèi)存的回收。順序循環(huán)"內(nèi)存分配表"找到要回收的作業(yè),將標(biāo)志位設(shè)為"0",定義floatrecycle_address,recycle_length;用recycle_address記下回收作業(yè)的首地址,recycle_length記下回收作業(yè)長(zhǎng)度。查找空閑表,如果<free_table[i].address+free_table[i].length>==recycle_address,說明有上鄰接空閑區(qū),這時(shí)上鄰接區(qū)的起始地址不變,長(zhǎng)度+recycle_address；如果<recycle_address+recycle_length>==free_table[i].address,說明有下鄰接,這時(shí)下鄰接空閑區(qū)的起始地址改為回收作業(yè)的起始地址recycle_address,長(zhǎng)度+recycle_length。如果同時(shí)有上下鄰接空閑區(qū),則上鄰接的起始地址不變,長(zhǎng)度+recycle_address+下鄰接的長(zhǎng)度,下鄰接標(biāo)志設(shè)為"0"否則,要回收的內(nèi)存沒有鄰接空閑區(qū),在空閑區(qū)中找到一個(gè)標(biāo)志為"0"的空欄目登記回收的內(nèi)存。十、內(nèi)存分配回收實(shí)現(xiàn)截圖：1、后臺(tái)代碼的截圖：<1>、假定系統(tǒng)內(nèi)存分配表允許的最大作業(yè)項(xiàng)為10,當(dāng)分配超過10時(shí),提示"內(nèi)存分配區(qū)已滿,分配失敗"。<2>、回收作業(yè)所占內(nèi)存時(shí),當(dāng)輸入的作業(yè)名不存在,回收失敗,提示"該作業(yè)不存在"。<3>、當(dāng)要釋放某個(gè)作業(yè)時(shí),將已分配表中此作業(yè)的標(biāo)志置為‘0’<4>、分配的作業(yè)大小21B與找到的最優(yōu)空閑區(qū)大小25B差值小于5B,所以將整塊空閑區(qū)直接分配給作業(yè)。<5>、分配的作業(yè)大小14B與找到的最優(yōu)空閑區(qū)大小20B差值大于5B,所以將整塊空閑區(qū)分割成兩部分,然后修改空閑表。<6>、要回收的內(nèi)存在空閑表中有上鄰,將其合并<7>、空閑區(qū)有兩個(gè)長(zhǎng)度分別為20B和18B的未分配爛,現(xiàn)為作業(yè)6分配14B的內(nèi)存,用最佳分配算法找到空閑區(qū)。2、制作界面的實(shí)現(xiàn)截圖十、源程序：#include<iostream.h>#include<iomanip.h>//全局變量floatminsize=5;intcount1=0;intcount2=0;#definem10 //假定系統(tǒng)允許的空閑區(qū)表最大為m#definen10 //假定系統(tǒng)允許的最大作業(yè)數(shù)量為n//已分配表的定義struct{floataddress;//已分分區(qū)起始地址floatlength; //已分分區(qū)長(zhǎng)度,單位為字節(jié)intflag; //已分配區(qū)表登記欄標(biāo)志,"0"表示空欄目}used_table[n]; //已分配區(qū)表對(duì)象名//空閑區(qū)表的定義：struct{floataddress; //空閑區(qū)起始地址floatlength; //空閑區(qū)長(zhǎng)度,單位為字節(jié)intflag; //空閑區(qū)表登記欄標(biāo)志,用"0"表示空欄目,用"1"表示未分配}free_table[m]; //空閑區(qū)表對(duì)象名//函數(shù)聲明voidinitialize<void>;intdistribute<int,float>;intrecycle<int>;voidshow<>;//初始化兩個(gè)表voidinitialize<void>{ inta; for<a=0;a<=n-1;a++> used_table[a].flag=0; //已分配表的表項(xiàng)全部置為空表項(xiàng) free_table[0].address=1000; free_table[0].length=1024; free_table[0].flag=1; //空閑區(qū)表的表項(xiàng)全部為未分配}//最優(yōu)分配算法實(shí)現(xiàn)的動(dòng)態(tài)分區(qū)intdistribute<intprocess_name,floatneed_length>{ inti,k=-1; //k用于定位在空閑表中選擇的未分配欄 floatads,len; intcount=0; i=0; while<i<=m-1>//循環(huán)找到最佳的空閑分區(qū) { if<free_table[i].flag==1&&need_length<=free_table[i].length> { count++; if<count==1||free_table[i].length<free_table[k].length> k=i; } i=i+1; } if<k!=-1> { if<<free_table[k].length-need_length><=minsize>//整個(gè)分配 { free_table[k].flag=0; ads=free_table[k].address; len=free_table[k].length; } else { //切割空閑區(qū) ads=free_table[k].address; len=need_length; free_table[k].address+=need_length; free_table[k].length-=need_length; } i=0; //循環(huán)尋找內(nèi)存分配表中標(biāo)志為空欄目的項(xiàng)while<used_table[i].flag!=0> {i=i+1;} if<i<=n-1>//找到,在已分配區(qū)表中登記一個(gè)表項(xiàng) { used_table[i].address=ads; used_table[i].length=len; used_table[i].flag=process_name; count1++; }else//已分配區(qū)表長(zhǎng)度不足 { if<free_table[k].flag==0>//將已做的整個(gè)分配撤銷 { free_table[k].flag=1; free_table[k].address=ads; free_table[k].length=len; }else//將已做的切割分配撤銷 { free_table[k].address=ads; free_table[k].length+=len; } cout<<"內(nèi)存分配區(qū)已滿,分配失??！\n"; return0; } } else { cout<<"無法為該作業(yè)找到合適分區(qū)！\n"; return0; } returnprocess_name;}intrecycle<intprocess_name>{inty=0; floatrecycle_address,recycle_length; inti,j,k; //j欄是下鄰空閑區(qū),k欄是上欄空閑區(qū) intx;//在內(nèi)存分配表中找到要回收的作業(yè) while<y<=n-1&&used_table[y].flag!=process_name> { y=y+1;} if<y<=n-1>//找到作業(yè)后,將該欄的標(biāo)志置為‘0{ recycle_address=used_table[y].address; recycle_length=used_table[y].length; used_table[y].flag=0; count2++; }else//未能找到作業(yè),回收失敗{ cout<<"該作業(yè)不存在！\n"; return0; } j=k=-1; i=0;while<!<i>=m||<k!=-1&&j!=-1>>>//修改空閑分區(qū)表{if<free_table[i].flag==1>{ if<<free_table[i].address+free_table[i].length>==recycle_address> k=i; //判斷是否有上鄰接 if<<recycle_address+recycle_length>==free_table[i].address> j=i; //判斷是否有下鄰接 } i=i+1; } //合并空閑區(qū) if<k!=-1>//回收區(qū)有上鄰接{ if<j!=-1>{ //回收區(qū)也有下鄰接,和上下領(lǐng)接合并 free_table[k].length+=free_table[j].length+recycle_length; free_table[j].flag=0; //將第j欄的標(biāo)記置為‘0 } else //不存在下鄰接,和上鄰接合并 free_table[k].length+=recycle_length; } elseif<j!=-1>{ //只有下鄰接,和下鄰接合并 free_table[j].length+=recycle_length; free_table[j].address=recycle_address;} else{ //上下鄰接都沒有 x=0; while<free_table[x].flag!=0> x=x+1; //在空閑區(qū)表中查找一個(gè)狀態(tài)為‘0’ if<x<=m-1>{ //找到后,在空閑分區(qū)中登記回收的內(nèi)存 free_table[x].address=recycle_address; free_table[x].length=recycle_length; free_table[x].flag=1; }else{ //空閑表已滿,執(zhí)行回收失敗 used_table[y].flag=process_name; cout<<"空閑區(qū)已滿,回收失敗！\n"; return0; } } returnprocess_name;}voidshow<>//程序執(zhí)行時(shí)輸出模擬的內(nèi)存分配回收表{ cout<<"+++++++++++++++++++++++++++++++++++++++\n";cout<<"+++++++空閑區(qū)+++++++\n";cout<<"+++++++++++++++++++++++++++++++++++++++\n"; for<inti=0;i<=count2;i++>cout<<"地址："<<free_table[i].address<<""<<"作業(yè)長(zhǎng)度："<<free_table[i].length<<""<<"狀態(tài)："<<free_table[i].flag<<endl; cout<<"+++++++++++++++++++++++++++++++++++++++\n";cout<<"+++++++已分配區(qū)++++++\n";cout<<"+++++++++++++++++++++++++++++++++++++++\n";for<intj=0;j<count1;j++>cout<<"地址："<<used_table[j].address<<""<<"作業(yè)長(zhǎng)度："<<used_table[j].length<<""<<"作業(yè)名："<<used_table[j].flag<<endl;}voidmain<>//主函數(shù)調(diào)用各功能函數(shù)對(duì)所有工作進(jìn)行測(cè)試{ intchoice;//用來選擇將要進(jìn)行的操作 intjob_name; floatneed_memory; boolexitFlag=false; cout<<"動(dòng)態(tài)分區(qū)分配方式的模擬\n";cout<<"************************************\n";cout<<"請(qǐng)選擇操作類型：\n";initialize<>;//開創(chuàng)空閑區(qū)和已分配區(qū)兩個(gè)表 while<!exitFlag> { cout<<"********************************************\n";cout<<"**1:分配內(nèi)存2:回收內(nèi)存**\n";cout<<"**3:查看分配0:退出**\n";cout<<"********************************************\n";cout<<"請(qǐng)輸入您的操作：";cin>>choice; switch<choice> {case0: exitFlag=true;//退出操作break;case1:cout<<"請(qǐng)輸入作業(yè)名和所需內(nèi)存："; cin>>job_name>>need_memory; distribute<job_name,need_memory>;//分配內(nèi)存break;case2:intID;cout<<"請(qǐng)輸入您要釋放的分區(qū)號(hào)：";cin>>ID;recycle<ID>;//回收內(nèi)存break; case3: show<>; break; } }}十一、心得體會(huì)：每一次的實(shí)踐,都會(huì)有很大的收獲。決定做這個(gè)題目的時(shí)候,就針對(duì)此題要解決的幾個(gè)問題反復(fù)思考,重新翻