動態(tài)分區(qū)分配算法 實驗報告

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

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

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

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

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

6、：本程序用c+語言編寫，其中用到了class類、指針，利用指針將class Table(空閑表類)和class Pro(作業(yè)類)用鏈?zhǔn)酱鎯Φ姆绞竭M(jìn)行插入、刪除、新建、排序等工作。(3) 打印一份源程序并附上注釋。#include<iostream.h>#include<string.h>class Pro /作業(yè)對象 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()

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

8、a;Size=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;elsecou

9、t<<"作業(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->

10、;Size<<endl;cout<<endl;elsecout<<"無空閑區(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-&

11、gt;Start>=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)/檢查有無空閑區(qū)塊 ,當(dāng)空閑區(qū)塊是原空閑塊時會去除重新分配 h=p;elseif(h->next=NULL)p->next=h;h=p;elsefor(;hp;hp=hp->next)if(p->Size<hp->Siz

12、e)p->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->Sta

13、rt)/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

14、=pph->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

15、(h,n);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(T

16、able *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

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

18、h;int 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è)隊列尾部插入新作業(yè)對象pp->next=p;elsecout<<"沒有足夠的空間分配！"<<endl;int main()cout<<"這是一個采用最先適應(yīng)算法（順序分配算法）分配主存空間的小測試。"<<endl;cout<<"這里一共有1000kb內(nèi)存可供使用，有三種選擇："<<endl&