動(dòng)態(tài)分區(qū)分配算法 實(shí)驗(yàn)報(bào)告

1、操作系統(tǒng)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)二: 動(dòng)態(tài)分區(qū)分配算法 .學(xué) 生： 學(xué) 號(hào)： 學(xué) 院： 系 別： 專 業(yè)： 實(shí)驗(yàn)時(shí)間： 報(bào)告時(shí)間： 一、實(shí)驗(yàn)內(nèi)容 編寫一個(gè)內(nèi)存動(dòng)態(tài)分區(qū)分配模擬程序，模擬內(nèi)存的分配和回收的完整過(guò)程。一個(gè)好的計(jì)算機(jī)系統(tǒng)不僅要有一個(gè)足夠容量的、存取速度高的、穩(wěn)定可靠的主存儲(chǔ)器，而且要能合理地分配和使用這些存儲(chǔ)空間。當(dāng)用戶提出申請(qǐng)存儲(chǔ)器空間時(shí)，存儲(chǔ)管理必須根據(jù)申請(qǐng)者的要求，按一定的策略分析主存空間的使用情況，找出足夠的空閑區(qū)域分配給申請(qǐng)者。當(dāng)作業(yè)撤離或主動(dòng)歸還主存資源時(shí)，則存儲(chǔ)管理要收回作業(yè)占用的主存空間或歸還部分主存空間。主存的分配和回收的實(shí)現(xiàn)與主存儲(chǔ)器的管理方式有關(guān)的，通過(guò)本實(shí)驗(yàn)幫助學(xué)生理解在

2、可變分區(qū)管理方式下應(yīng)怎樣實(shí)現(xiàn)主存空間的分配和回收。三、實(shí)驗(yàn)原理模擬在可變分區(qū)管理方式下采用最先適應(yīng)算法實(shí)現(xiàn)主存分配和回收。(1)可變分區(qū)方式是按作業(yè)需要的主存空間大小來(lái)分割分區(qū)的。當(dāng)要裝入一個(gè)作業(yè)時(shí)，根據(jù)作業(yè)需要的主存量查看是否有足夠的空閑空間，若有，則按需要量分割一個(gè)分區(qū)分配給該作業(yè)；若無(wú)，則作業(yè)不能裝入。隨著作業(yè)的裝入、撤離，主存空間被分成許多個(gè)分區(qū)，有的分區(qū)被作業(yè)占用，而有的分區(qū)是空閑的。例如：05k10k14k26k32k512k操作系統(tǒng)作業(yè)1作業(yè)3空閑區(qū)作業(yè)2空閑區(qū)為了說(shuō)明哪些區(qū)是空閑的，可以用來(lái)裝入新作業(yè)，必須要有一張空閑區(qū)說(shuō)明表，格式如下：起 址長(zhǎng) 度狀 態(tài)第一欄14 K12 K

3、未 分 配第二欄32 K96 K未 分 配MMMM其中，起址指出一個(gè)空閑區(qū)的主存起始地址。 長(zhǎng)度指出從起始地址開始的一個(gè)連續(xù)空閑的長(zhǎng)度。 狀態(tài)有兩種狀態(tài)，一種是“未分配”狀態(tài)，指出對(duì)應(yīng)的由起址指出的某個(gè)長(zhǎng)度的區(qū)域是空閑區(qū)。 (2) 當(dāng)有一個(gè)新作業(yè)要求裝入主存時(shí)，必須查空閑區(qū)說(shuō)明表，從中找出一個(gè)足夠大的空閑區(qū)。有時(shí)找到的空閑區(qū)可能大于作業(yè)需要量，這時(shí)應(yīng)把原來(lái)的空閑區(qū)變成兩部分：一部分分給作業(yè)占用；另一部分又成為一個(gè)較小的空閑區(qū)。為了盡量減少由于分割造成的空閑區(qū)，而盡量保存高地址部分有較大的連續(xù)空閑區(qū)域，以利于大型作業(yè)的裝入。為此，在空閑區(qū)說(shuō)明表中，把每個(gè)空閑區(qū)按其地址順序登記，即每個(gè)后繼的空閑區(qū)

4、其起始地址總是比前者大。(3) 采用最先適應(yīng)算法（順序分配算法）分配主存空間。按照作業(yè)的需要量，查空閑區(qū)說(shuō)明表，順序查看登記欄，找到第一個(gè)能滿足要求的空閑區(qū)。當(dāng)空閑區(qū)大于需要量時(shí)，一部分用來(lái)裝入作業(yè)，另一部分仍為空閑區(qū)登記在空閑區(qū)說(shuō)明表中。由于本實(shí)驗(yàn)是模擬主存的分配，所以把主存區(qū)分配給作業(yè)后并不實(shí)際啟動(dòng)裝入程序裝入作業(yè)，而用輸出“分配情況”來(lái)代替。(4) 當(dāng)一個(gè)作業(yè)執(zhí)行結(jié)束撤離時(shí)，作業(yè)所占的區(qū)域應(yīng)該歸還，歸還的區(qū)域如果與其它空閑區(qū)相鄰，則應(yīng)合成一個(gè)較大的空閑區(qū)，登記在空閑區(qū)說(shuō)明表中。(5) 請(qǐng)按最先適應(yīng)算法設(shè)計(jì)主存分配和回收的程序。假設(shè)初始時(shí)主存中沒有作業(yè)，現(xiàn)按下面序列進(jìn)行內(nèi)存的申請(qǐng)與釋放：作

5、業(yè)1申請(qǐng)300K，作業(yè)2申請(qǐng)100K，作業(yè)1釋放300K，作業(yè)3申請(qǐng)150K，作業(yè)4申請(qǐng)30K， 作業(yè)5申請(qǐng)40K， 作業(yè)6申請(qǐng)60K， 作業(yè)4釋放30K。 請(qǐng)你為它們進(jìn)行主存分配和回收，把空閑區(qū)說(shuō)明表的初值以及每次分配或回收后的變化顯示出來(lái)或打印出來(lái)。四、實(shí)驗(yàn)報(bào)告(1) 畫出最先適應(yīng)分配算法流程圖、歸還主存時(shí)的回收算法流程圖。最先適應(yīng)分配算法流程圖：輸入作業(yè)對(duì)象改變空閑區(qū)塊隊(duì)列+改變作業(yè)隊(duì)列順序遍歷空閑區(qū)塊隊(duì)列輸出結(jié)果是否有足夠空間的空閑區(qū)塊NY歸還主存時(shí)的回收算法流程圖：輸入作業(yè)對(duì)象改變空閑區(qū)塊隊(duì)列+改變作業(yè)隊(duì)列是否存在該作業(yè)？N輸出結(jié)果Y(2) 程序中使用的數(shù)據(jù)結(jié)構(gòu)及符號(hào)說(shuō)明。答：本程序

6、用c+語(yǔ)言編寫，其中用到了class類、指針，利用指針將class Table(空閑表類)和class Pro(作業(yè)類)用鏈?zhǔn)酱鎯?chǔ)的方式進(jìn)行插入、刪除、新建、排序等工作。(3) 打印一份源程序并附上注釋。#include<iostream.h>#include<string.h>class Pro /作業(yè)對(duì)象 public:Pro()Size=0;next=NULL;Start=0;Name0='0'Pro(int Si,char Na)Size=Si;next=NULL;Start=0;strcpy(Name,Na);void printf()cout

7、<<Name<<"t"<<Start<<endl;void Arrange(int Sta,Pro &Ne)Start=Sta;next=&Ne;Pro *next;/用來(lái)指向下一個(gè)輸入的作業(yè) int Size;/作業(yè)大小 char Name10;/作業(yè)名稱 int Start;/在內(nèi)存中存放的起始地址 ;class Table/空閑表 public:Table *next;/指向下一個(gè)空閑區(qū)塊 int Size;/空閑區(qū)塊大小 Table()Table(int Sta,int Siz)Start=Sta;Si

8、ze=Siz;Over=Sta+Siz;next=NULL;int Start;/空閑區(qū)塊起始地址int Over;/空閑區(qū)塊結(jié)束地址 ; void Pri(Pro *ph)if(ph)cout<<endl<<"內(nèi)存中的作業(yè)"<<endl<<"作業(yè)名"<<"t"<<"起始地址"<<endl;for(Pro *p=ph;p;p=p->next)p->printf();cout<<endl;elsecout<

9、;<"作業(yè)已全部運(yùn)行完畢！"<<endl;void Prik(Table *h)if(h)cout<<"空閑區(qū)塊分配情況"<<endl<<"空閑區(qū)塊起始地址"<<"t"<<"空閑區(qū)塊大小"<<endl;for(;h;h=h->next)cout<<"t"<<h->Start<<"ttt"<<h->Siz

10、e<<endl;cout<<endl;elsecout<<"無(wú)空閑區(qū)塊！"<<endl; void PX(Table *&h,Table *p)/排序順序空閑區(qū)塊 Table *hp=h->next;Table *hf=h;Table *hf2=h;Table *hf1=h;if(p->Start=1000)return;for(;hf1;hf1=hf1->next)/檢查新增空閑區(qū)塊是否是原空閑區(qū)塊if(hf1->Start<p->Over && hf1->S

11、tart>=p->Start && hf1=h)h=h->next;else if(hf1->Start<p->Over && hf1->Start>=p->Start)hf2->next=hf1->next;hf2=hf1;if(!h)/檢查有無(wú)空閑區(qū)塊 ,當(dāng)空閑區(qū)塊是原空閑塊時(shí)會(huì)去除重新分配 h=p;elseif(h->next=NULL)p->next=h;h=p;elsefor(;hp;hp=hp->next)if(p->Size<hp->Size)p-

12、>next=hp;hf->next=p;break;hf=h;if(!hp)hf->next=p;void ZJKX(Table *&h,Pro *p,Pro *pp)/空閑區(qū)塊的改變 int pos=p->Start+p->Size,jugy=0;Table *ph1=h;for(Table *ph=h;ph;ph=ph->next)if(ph->Start=pos)jugy=1;Table *pph1=h;Table *pph=h;for(;pph;pph=pph->next)if(pph->Over=p->Start)/

13、3pph1->next=pph->next;ph1->next=ph->next;Table *n=new Table(pph->Start,ph->Size+pph->Size+p->Size);PX(h,n);break;pph1=pph;if(!pph)/4ph->Size=ph->Size+p->Size;ph->Start=p->Start;PX(h,ph);ph1=ph;if(!jugy)Table *pph1=h;for(Table *pph=h;pph && !jugy;pph=pph

14、->next)for(Pro *pp1=pp;pp1;pp1=pp1->next)if(p->Start=(pp1->Start+pp1->Size)/2for(Table *h2=h;h2;h2=h2->next)if(p->Start+p->Size)=h2->Start)Table *n=new Table(p->Start,p->Size+h2->Size);PX(h,n);jugy=1;break;if(!jugy)Table *n=new Table(p->Start,p->Size);PX(h,n

15、);jugy=1;break;else if(p->Start+p->Size)=pp1->Start)/1for(Table *h1=h;h1;h1=h->next)if(h1->Over=p->Start)Table *n=new Table(h1->Start,p->Size+h1->Size);PX(h,n);jugy=1;break;if(!jugy)Table *n=new Table(p->Start,p->Size);PX(h,n);jugy=1;break;pph1=pph;if(!jugy)for(Table

16、 *pph=h;pph;pph=pph->next)/5if(pph->Over=p->Start)pph->Size=pph->Size+p->Size;pph->Over=pph->Over+p->Size;PX(h,pph);break;if(!h)Table *x=new Table(p->Start,p->Size);h=x;void SF(Pro *&ph,char N,Table *&h)/釋放作業(yè) int jugy=0;Pro *pp=ph;if(!strcmp(ph->Name,N)ZJK

17、X(h,ph,ph);ph=ph->next;jugy=1;elsefor(Pro *p=ph->next;p;p=p->next)if(!strcmp(N,p->Name)/完成作業(yè)的刪除 :刪除作業(yè)對(duì)象+增加空閑區(qū)塊對(duì)象，并檢查是否可以合并 ZJKX(h,p,ph);pp->next=p->next;jugy=1;pp=p;if(!jugy)cout<<"隊(duì)列中沒有這個(gè)作業(yè)!"<<endl;void JR(Pro *&ph,Pro *p,Table *&h)/加入作業(yè) Pro *pp=ph;in

18、t jugy=0;/分割空閑區(qū)塊 Table *hpp=h;for(Table *hp=h;hp;hp=hp->next)if(p->Size<=hp->Size)p->Start=hp->Start;if(p->Start+p->Size=1000)if(hpp=hp)h=NULL;elsehpp->next=NULL;jugy=1;elsehp->Size=hp->Size-p->Size;hp->Start=p->Start+p->Size;jugy=1;break;if(jugy)if(!ph)ph=p;elsefor(;pp->next;pp=pp->next);/作業(yè)隊(duì)列尾部插入新作業(yè)對(duì)象pp->next=p;elsecout<<"沒有足夠的空間分配！"<<endl;int main()cout<<"這是一個(gè)采用最先適應(yīng)算法（順序分配算法）分配主存空間的小測(cè)試。"<<endl;cout<<"這里一共有1000kb內(nèi)存可供使用，有三種選擇："<<endl