1、學(xué)號(hào)P 專業(yè)計(jì)算機(jī)科學(xué)與技術(shù) 姓名實(shí)驗(yàn)日期 2017/11/23 教師簽字 成績 實(shí)驗(yàn)報(bào)告【實(shí)驗(yàn)名稱】 基于順序搜索的動(dòng)態(tài)分區(qū)分配算法(二)【實(shí)驗(yàn)?zāi)康摹坷斫庠谶B續(xù)分區(qū)動(dòng)態(tài)的存儲(chǔ)管理方式下，如何實(shí)現(xiàn)貯存空間的分配與回收。采用可變式分區(qū)管理，使用最佳適應(yīng)算法實(shí)現(xiàn)主存空間的分配與回收。采用可變式分區(qū)管理，使用最壞適應(yīng)算法實(shí)現(xiàn)主存空間的分配與回收?！緦?shí)驗(yàn)原理】C+語言程序設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)最佳適應(yīng)算法最壞適應(yīng)算法數(shù)據(jù)結(jié)構(gòu)和符號(hào)說明1、bool ROMN; /定義主存信息，如果內(nèi)存被占用，則標(biāo)記為1，否則標(biāo)記為0，設(shè)置內(nèi)存單元為10242、pcb num20;/定義作業(yè)數(shù)組，最大支持20個(gè)作業(yè)3、typede

2、f struct Pcb /定義作業(yè)結(jié)構(gòu)體，包括名稱，開始時(shí)間，大小，是否執(zhí)行狀態(tài) char name10; int start; int size; int state=0; pcb;主要函數(shù)：void find_free_rom()；/尋找空閑區(qū)void sort1()；/對(duì)空閑區(qū)進(jìn)行排序從小到大void sort1()；/對(duì)空閑區(qū)進(jìn)行排序從大到小void show()；/顯示函數(shù)void insert_pcb1(pcb &a)；/最佳適應(yīng)算法void insert_pcb2(pcb &a)；/最壞適應(yīng)算法void init();/初始化函數(shù)算法流程圖：最佳適應(yīng)算法：最壞適應(yīng)算法：#inc

3、lude#include#define N 1024bool ROMN;int p=0;int count=0;int free_rom_counter=0;/空閑區(qū)數(shù)目typedef struct Pcb /進(jìn)程結(jié)構(gòu)體 char name10; int start; int size;/大小 int state=0; /狀態(tài) pcb;pcb num20;/進(jìn)程數(shù)組typedef struct Free_rom/空閑區(qū)結(jié)構(gòu)體 int num; int start; int end; int space;/空閑區(qū)大小 Free_room;Free_rom free_rom100;/空閑區(qū)數(shù)組vo

4、id show()/顯示空閑區(qū)信息 printf(*nn); printf(空閑區(qū)名t開始地址tt大小tt結(jié)束地址ttn); for (int i=1; i= free_rom_counter; i+) printf(%dtt%dttt%dtt%dttn,free_rom i.num,free_rom i.start, free_rom i.space,free_rom i.end); printf(n); printf(*nn);void find_free_rom()/尋找空閑區(qū)，更新空閑區(qū)數(shù)組 free_rom_counter=0; int i,j,p; for(i=0; iN; i+)

5、 if(ROMi=0) p=i; for(j=i; jN; j+) if(ROMj=0) i=j; continue; if(ROMj=1)/找到就更新信息 free_rom_counter+; free_rom free_rom_counter.num= free_rom_counter; free_rom free_rom_counter.start=p; free_rom free_rom_counter.end=j-1; free_rom free_rom_counter.space=j-p; i=j+1; break; if(j=N&ROMj-1=0)/對(duì)最后一個(gè)內(nèi)存進(jìn)行特殊處理 f

6、ree_rom_counter+; free_rom free_rom_counter.num= free_rom_counter; free_rom free_rom_counter.start=p; free_rom free_rom_counter.end=j-1; free_rom free_rom_counter.space=j-p; void sort1()/最佳適應(yīng)算法對(duì)空閑區(qū)從小到大排序 find_free_rom(); Free_rom a; for(int i=1; ifree_rom_counter; i+) for(int j=1; j free_romj+1.spac

7、e) a=free_romj; free_romj=free_romj+1; free_romj+1=a; void sort2()/最壞適應(yīng)算法對(duì)空閑區(qū)從大到小排序 find_free_rom(); Free_rom a; for(int i=1; ifree_rom_counter; i+) for(int j=1; jfree_rom_counter; j+) if( free_romj.space free_romj+1.space) a=free_romj; free_romj=free_romj+1; free_romj+1=a; void init()/初始化 for(int i

8、=0; iN; i+) ROMi=0;void input(pcb &a)/輸入 char name10; printf(輸入進(jìn)程名n); scanf(%s,&); printf(輸入進(jìn)程大小n); scanf(%d,&a.size);void insert_pcb1(pcb &a)/最佳適應(yīng)算法插入進(jìn)程 find_free_rom(); sort1(); int i,j,k; for(i=1; i=free_rom_counter; i+)/判斷插入 if(a.size= free_romi.space) for(j= free_romi.start; jfree_romi.st

9、art+a.size; j+) ROMj=1; a.state=1; a.start=free_romi.start; numcount+=a; break; if(i=free_rom_counter+1)/插入失敗 printf(可用空間不足!n);void insert_pcb2(pcb &a)/最壞適應(yīng)算法插入find_free_rom();sort2();int i,j,k;for(i=1; i=free_rom_counter; i+) if(a.size= free_romi.space) for(j= free_romi.start; jfree_romi.start+a.si

10、ze; j+)/尋找 ROMj=1; a.state=1; a.start=free_romi.start; numcount+=a; break; if(i=free_rom_counter+1)/插入失敗 printf(可用空間不足!n);void Delete(pcb &a)/內(nèi)存中釋放進(jìn)程 int i; for(i=a.start; ia.start+a.size; i+) ROMi=0;/更新內(nèi)存信息，更新進(jìn)程狀態(tài)數(shù)組 a.state=0; printf(刪除成功n); find_free_rom();int main()/主函數(shù) init(); find_free_rom(); i

11、nt choose1; int choose; char name10; printf(1、最佳適應(yīng)算法n);/主界面 printf(2、最壞首次適應(yīng)算法n); scanf(%d,&choose1); pcb a; do printf(nn1、插入進(jìn)程n); printf(2、刪除進(jìn)程n); printf(3、顯示進(jìn)程信息n); printf(4、顯示空余內(nèi)存信息n); scanf(%d,&choose); if(choose=1)/選擇 input(a); if(choose1=1) insert_pcb1(a); else insert_pcb2(a); else if(choose=2)

12、 printf(輸入刪除進(jìn)程的名字n); scanf(%s,&name); for(int i=0; icount; i+) if( !strcmp(,name) Delete(numi); else if(choose=3) printf(*nn); printf(進(jìn)程名tt開始地址tt大小tt結(jié)束地址ttn);/輸出內(nèi)存信息 for(int i=0; icount; i+) if(numi.state!=0) printf(%stt%dttt%dtt%dttn,,numi.start,numi.size,numi.size+numi.start-1);

13、printf(n*nn); else if(choose=4) find_free_rom(); show(); else break; while(1); return 0;截圖：構(gòu)造如下空閑區(qū)： 此時(shí)插入一個(gè)進(jìn)程 G，大小為80H，應(yīng)插入到第二塊空閑區(qū)再插入一個(gè)大小為30的進(jìn)程H，應(yīng)插入到第三塊中再插入一個(gè)小進(jìn)程，大小為5，插入到第二塊空閑區(qū)，查看進(jìn)程信息和空閑區(qū)信息：最佳適應(yīng)算法成立。最壞適應(yīng)算法：構(gòu)造如下空閑區(qū)：插入一個(gè)大小為80的進(jìn)程G，插入到第一塊空閑區(qū)。在插入一個(gè)大小為20的進(jìn)程H，插入到第三塊空閑區(qū)。再插入一個(gè)大小為20的進(jìn)程，插入到第三塊空閑區(qū)。最壞適應(yīng)算法成立?！拘〗Y(jié)或討論】1、 本次實(shí)驗(yàn)涉及到兩個(gè)表，空閑區(qū)登記表和進(jìn)程分配表，分配空間需要進(jìn)程所需空間的大小，給出過分配后進(jìn)程的起始地址；回收空間除了需要進(jìn)程所需空間的大小以外，還需要知道進(jìn)程的起始地址，再進(jìn)行一系列判斷然后回收。2、 本次實(shí)驗(yàn)的兩個(gè)算法是在首次適應(yīng)算法的基礎(chǔ)上進(jìn)行的改進(jìn)，最佳適應(yīng)算法是將所有區(qū)按照區(qū)的大小進(jìn)行升序排列，再從第一個(gè)區(qū)即最小的區(qū)開始檢索分配內(nèi)存；最壞適應(yīng)算法是將所有區(qū)按照