實(shí)驗(yàn)三 可變分區(qū)存儲(chǔ)管理.docx

實(shí)驗(yàn)三 可變分區(qū)存儲(chǔ)管理1目的和要求通過(guò)這次實(shí)驗(yàn)，加深對(duì)內(nèi)存管理的認(rèn)識(shí)，進(jìn)一步掌握內(nèi)存的分配、回收算法的思想。2實(shí)驗(yàn)內(nèi)容閱讀教材計(jì)算機(jī)操作系統(tǒng)第四章，掌握存儲(chǔ)器管理相關(guān)概念和原理。編寫程序模擬實(shí)現(xiàn)內(nèi)存的動(dòng)態(tài)分區(qū)法存儲(chǔ)管理。內(nèi)存空閑區(qū)使用自由鏈管理，采用最壞適應(yīng)算法從自由鏈中尋找空閑區(qū)進(jìn)行分配，內(nèi)存回收時(shí)假定不做與相鄰空閑區(qū)的合并。假定系統(tǒng)的內(nèi)存共640K，初始狀態(tài)為操作系統(tǒng)本身占用64K。在t1時(shí)間之后，有作業(yè)A、B、C、D分別請(qǐng)求8K、16K、64K、124K的內(nèi)存空間；在t2時(shí)間之后，作業(yè)C完成；在t3時(shí)間之后，作業(yè)E請(qǐng)求50K的內(nèi)存空間；在t4時(shí)間之后，作業(yè)D完成。要求編程序分別輸出t1、t2、t3、t4時(shí)刻內(nèi)存的空閑區(qū)的狀態(tài)。3實(shí)驗(yàn)環(huán)境Windows操作系統(tǒng)、VC+6.0C語(yǔ)言4. 實(shí)驗(yàn)要求：1) 上機(jī)前認(rèn)真使用C語(yǔ)言編寫好程序，采用Visual C+6.0作為編譯環(huán)境；2) 上機(jī)時(shí)獨(dú)立調(diào)試程序3) 根據(jù)具體實(shí)驗(yàn)要求，填寫好實(shí)驗(yàn)報(bào)告（包括目的和要求、實(shí)驗(yàn)內(nèi)容、實(shí)驗(yàn)環(huán)境、設(shè)計(jì)思想、源程序、實(shí)例運(yùn)行結(jié)果、總結(jié)）。5. 設(shè)計(jì)思想：本次實(shí)驗(yàn)編寫的程序主要涉及四個(gè)函數(shù)start ( ), requireMemo ( ) ， freeMemo ( )和past( )。1. start()這個(gè)函數(shù)主要用來(lái)建立自由鏈隊(duì)列和占用區(qū)隊(duì)列，這兩個(gè)隊(duì)列用來(lái)分別存放自由節(jié)點(diǎn)和占用節(jié)點(diǎn)。在初始狀態(tài)下，操作系統(tǒng)本身占用64k,它存放在占用區(qū)隊(duì)列里，因此自由鏈隊(duì)列里只有640-64=576k的空間，且起始地址為64。2. requireMemo()函數(shù)是該程序的核心算法，用來(lái)分配內(nèi)存空間，該函數(shù)帶兩個(gè)參數(shù)，用來(lái)表示作業(yè)或進(jìn)程名的name和表示作業(yè)或者進(jìn)程名所申請(qǐng)空間的大小的require。由于此算法采用的是最壞適應(yīng)算法，所以自由鏈隊(duì)列中的空閑分區(qū)是按其容量從大到小的順序排列的。因此在這里需要分三種情況：自由鏈隊(duì)列的第一個(gè)空閑分區(qū)的容量大于require；自由鏈隊(duì)列的第一個(gè)空閑分區(qū)的容量等于require；自由鏈隊(duì)列的第一個(gè)空閑分區(qū)的容量小于require。在情況下分配完后還需把剩余的部分重新按照容量大小給它在自由鏈隊(duì)列里找到新位置。在情況下只需分配，分配即把符合要求的空閑分區(qū)從自由鏈隊(duì)列刪除，并且插入到占用區(qū)隊(duì)列的尾部。在刪除需注意把原來(lái)處于分配分區(qū)的前后鏈接起來(lái)，否則隊(duì)列將斷掉。在情況下，只需提示用戶無(wú)法分配即可。3. freeMemo ()函數(shù)也是該程序的核心算法，是用來(lái)回收作業(yè)完成后不需使用的內(nèi)存空間，它根據(jù)從main()函數(shù)中傳遞過(guò)來(lái)的參數(shù)name，遍尋占用區(qū)隊(duì)列，找到與name匹配的作業(yè)，把他從占用區(qū)隊(duì)列刪除，插入到自由鏈隊(duì)列里。在插入時(shí)，由于涉及到鄰接區(qū)的合并問(wèn)題，所以必須先遍尋整個(gè)自由鏈隊(duì)列，找到是否有從占用區(qū)隊(duì)列回收回來(lái)的空間鄰接區(qū)，如果有，就將他們合并。做完鄰接區(qū)的合并之后，再根據(jù)內(nèi)存空間的大小，將整個(gè)自由鏈隊(duì)列排序。6. 源程序：1）程序中所定義的數(shù)據(jù)結(jié)構(gòu)和全局變量/程序中自由鏈隊(duì)列的結(jié)點(diǎn)類型可描述如下struct freelink int len, address; / len為分區(qū)長(zhǎng)度 / address為分區(qū)起始地址 struct freelink *next;/內(nèi)存占用區(qū)用鏈表描述，其結(jié)點(diǎn)類型描述如下struct busylink char name; / 作業(yè)或進(jìn)程名 name=S 表示OS占用 int len , address; struct busylink *next;/并設(shè)全程量struct freelink *free_head=NULL; /自由鏈隊(duì)列（帶頭結(jié)點(diǎn)）隊(duì)首指針 struct busylink *busy_head=NULL, /占用區(qū)隊(duì)列隊(duì)（帶頭結(jié)點(diǎn)）首指針 *busy_tail=NULL; /占用區(qū)隊(duì)列隊(duì)隊(duì)尾指針2）requireMemo（）函數(shù)的具體實(shí)現(xiàn)：/模擬內(nèi)存分配函數(shù)void requireMemo(char name, int require) struct busylink *p; struct freelink *w,*u,*v; if( free_head-next-len=require) if(free_head-next-lenrequire) p=(struct busylink*)malloc(sizeof(struct busylink); p-name=name; p-address=free_head-next-address; p-len=require; p-next=NULL; busy_tail-next=p; busy_tail=p; w=free_head-next; free_head-next=w-next; w-len=w-len-require; w-address=w-address+require; u=free_head; v=free_head-next; while(v!=NULL)u=v; v=v-next; u-next=w; w-next=v;else p=(struct busylink*)malloc(sizeof(struct busylink); p-name=name; p-address=free_head-next-address; p-len=require; p-next=NULL; busy_tail-next=p; busy_tail=p; w=free_head-next; free_head-next=w-next; free(w);else printf(not allocat);3) freeMemo( )函數(shù)的具體實(shí)現(xiàn)：/模擬內(nèi)存回收函數(shù)void freeMemo(char name) int len,address; struct busylink *p,*q; struct freelink *w,*u,*v; q=busy_head; p= busy_head-next; while(p!=NULL)&(p-name!=name) q=p; p=p-next; if(p=NULL) printf(%c is not exist,name); else if(p=busy_tail) busy_tail=q; q-next=p-next; len=p-len; address=p-address; free(p); w=( struct freelink*) malloc(sizeof(struct freelink); w-len=len; w-address=address; u=free_head; v=free_head-next; while(v!=NULL)&(v-lenw-len) u=v; v=v-next; if(u-address+u-len=w-address)|(w-len+w-address=u-address) /處理w鄰接于u的情況 if(w-address =u-address) w-address=u-address; w-len=u-len+w-len; w-next=v; free(u); if(v!=NULL&(w-address+w-len=v-address)|(v-address+v-len=w-address) /處理v鄰接于w的情況 if(v-addressaddress) w-address=v-address; w-len=w-len+v-len; u-next=v-next; free(v); u=free_head; v=free_head-next; while(v!=NULL)&(v-lenw-len) u=v;v=v-next; w-next=v; u-next =w; 7. 實(shí)例運(yùn)