動態(tài)可變分區(qū)存儲管理模擬系統(tǒng)

1、青 島 農(nóng) 業(yè) 大 學理學與信息科學學院操 作 系 統(tǒng) 課 程 設(shè) 計 報 告 設(shè) 計 題 目 仿真實現(xiàn)動態(tài)可變分區(qū)存儲管理模擬系統(tǒng) 最佳適應(yīng)算法和最先適應(yīng)算法 學生專業(yè)班級 計算機科學與技術(shù)2011級03班 學生姓名（學號） 張明珠（H20110684 ） 設(shè)計小組其他同學姓名（學號） 劉玉婷（H20110661） 宋璇（H20110162） 指 導 教 師 牟春蓮 完 成 時 間 2014. 06.15 實 習（設(shè)計）地點 信息樓218 2014年6月16日一、課程設(shè)計目的操作系統(tǒng)的理論知識只有通過操作系統(tǒng)的實際操作和編程才能真正地理解和掌握，沒有實踐操作系統(tǒng)的操作和編程，學習操作系統(tǒng)就是

2、紙上談兵。操作系統(tǒng)課程設(shè)計是在學習完操作系統(tǒng)課程后進行的一次全面、綜合實習，是計算機科學與技術(shù)專業(yè)的重要實踐性教學環(huán)節(jié)。通過課程設(shè)計，達到如下目的：1、鞏固和加深對操作系統(tǒng)原理的理解，提高綜合運用本課程所學知識的能力。2、培養(yǎng)學生選用參考書，查閱手冊及文獻資料的能力；培養(yǎng)獨立思考、深入研究、分析問題、解決問題的能力。3、通過實際操作系統(tǒng)的分析設(shè)計、編程調(diào)試，掌握系統(tǒng)軟件的分析方法和工程設(shè)計方法。4、能夠按要求編寫課程設(shè)計報告書，能正確闡述設(shè)計過程和實驗結(jié)果、正確繪制系統(tǒng)和程序框圖。5、通過課程設(shè)計，培養(yǎng)學生嚴謹?shù)目茖W態(tài)度、嚴肅認真的工作作風和團隊協(xié)作精神。二、設(shè)計任務(wù)題目描述：仿真實現(xiàn)動態(tài)可變

3、分區(qū)存儲管理模擬系統(tǒng)。內(nèi)存調(diào)度策略可采用最先適應(yīng)算法、最佳適應(yīng)法等，并對各種算法進行性能比較。為了實現(xiàn)分區(qū)分配，系統(tǒng)中必須配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用來描述空閑區(qū)和已分配區(qū)的情況，為分配提供依據(jù)。常用的數(shù)據(jù)結(jié)構(gòu)有兩種形式：空閑分區(qū)表和空閑分區(qū)鏈。為把一個新作業(yè)裝入內(nèi)存，須按照一定的算法，從空閑分區(qū)表或空閑分區(qū)鏈中選出一個分區(qū)分配給該作業(yè).設(shè)計要求：1采用指定算法模擬動態(tài)分區(qū)管理方式的主存分配。能夠處理以下的情形： 隨機出現(xiàn)的進程i申請jKB內(nèi)存，程序能判斷是否能分配，如果能分配，要求輸出分配的首地址Faddress，并要求輸出內(nèi)存使用情況和空閑情況。內(nèi)存情況輸出的格式為：Faddress該分區(qū)的首地

4、址；Eaddress該分區(qū)的尾地址Len 分區(qū)長度；Process 如果使用，使用的進程號，否則為0。 主存分配函數(shù)實現(xiàn)尋找空閑區(qū)、空閑區(qū)表的修改、已分配區(qū)表的修改功能。成員分工：張明珠 申請內(nèi)存、查看進程之間的前后的區(qū)域狀態(tài)、釋放進程劉玉婷 最先適應(yīng)算法、將其釋放的內(nèi)存插入空閑塊中、初始化宋璇 最佳適應(yīng)算法、將新項插入已分配表中、退出張明珠 宋璇 劉玉婷 整個界面的優(yōu)化 、界面設(shè)計、總體思路三、分析與設(shè)計1設(shè)計思路存儲器是計算機的重要組成部分,存儲空間是操作系統(tǒng)管理的寶貴資源,雖然其容量在不斷擴大,但仍然遠遠不能滿足軟件發(fā)展的需要。對存儲資源進行有效的管理,不僅關(guān)系到存儲器的利用率,而且還對

5、操作系統(tǒng)的性能和效率有很大的影響。操作系統(tǒng)的存儲管理的基本功能有：存儲分配、地址轉(zhuǎn)換和存儲保護、存儲共享、存儲擴充。存儲分配指為選中的多道運行的作業(yè)分配主存空間；地址轉(zhuǎn)換是把邏輯地址空間中的用戶程序通過靜態(tài)重定位或動態(tài)重定位轉(zhuǎn)換和映射到分給的物理地址空間中,以便用戶程序的執(zhí)行；存儲保護指各道程序只能訪問自己的存儲區(qū)域,而不能互相干擾,以免其他程序受到有意或無意的破壞；存儲共享指主存中的某些程序和數(shù)據(jù)可供不同用戶進程共享。最簡單的單道系統(tǒng)中,一旦一個程序能裝入主存,它將一直運行直到結(jié)束。如果程序長度超出了主存的實際容量,可以通過覆蓋和交換的技術(shù)獲得解決。更多的操作系統(tǒng)支持多個用戶進程在主存同時執(zhí)

6、行,能滿足多道程序設(shè)計需要的最簡單的存儲管理技術(shù)是分區(qū)方式,有分固定分區(qū)和可變分區(qū)?？勺兎謪^(qū)的分配（如圖（1）所示）算法包括：最先適應(yīng)、下次適應(yīng)、最佳適應(yīng)、最壞適應(yīng)和快速適應(yīng)等分配算法。圖（1）動態(tài)內(nèi)存分配采用分區(qū)方式管理存儲器,每道程序總是要求占用主存的一個或幾個連續(xù)的存儲區(qū)域,主存中會產(chǎn)生許多碎片。因此,有時為了接納一個新的作業(yè)而往往要移動已在主存的信息,這不僅不方便,而且開銷不小?，F(xiàn)代計算機都有某種虛存硬設(shè)備支持,簡單也是常用的虛存是請求分頁式虛存管理,于是允許把一個進程的頁面存放到若干不相鄰的主存頁框中。 從搜索速度上看，最先適應(yīng)算法具有最佳性能。從回收過程來看，最先適應(yīng)法也是最佳的。

7、最先適應(yīng)算法要求可用表或自由鏈接按起始地址遞增的次序排列。該算法的最大特點是一旦找到大于或等于所要求內(nèi)存的長度的分區(qū)，則搜索結(jié)束。其優(yōu)點：（1）、在釋放內(nèi)存分區(qū)時，如果有相鄰的空白區(qū)就進行合并，使其成為一個較大的空白區(qū)；（2）、本算法的實質(zhì)是盡可能的利用存儲器的低地址部分，在高地址部分則保留較多的或較大的空白區(qū)，以后如果需要較大的空白區(qū)，就容易能夠滿足。最佳適應(yīng)算法：從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能使碎片盡量小。為適應(yīng)此算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按從小到大進行排序，自表頭開始查找到第一個滿足要求的自由分區(qū)分配。該算法保留大的空閑區(qū)，但造成許多

8、小的空閑區(qū)。最佳適應(yīng)算法將可利用空間表中一個大小不小于“請求”且最接近“請求”的空閑塊的一部分分配給用戶。分配與回收都需要對可利用空間表從頭至尾查詢一遍。為了避免每次分配都要查詢整個鏈表，通常要求節(jié)點從大到小排序，由此只需找到第一個足夠大的空閑塊即可予以分配。但回收時，必須把回收的空閑塊放置在符合大小順序關(guān)系的鏈表位置。在分配時容易產(chǎn)生太小而無法利用的內(nèi)存碎片，同時這種做法也保留了那些很大的內(nèi)存塊以備響應(yīng)將來發(fā)生的內(nèi)存量較大的用戶“請求”，從而使整個鏈表逐漸趨向于節(jié)點大小差別甚遠的狀態(tài)。這種分配算法適合請求分配內(nèi)存大小范圍較廣的系統(tǒng)，此算法比較費時間。在進行內(nèi)存分配時，從空閑分區(qū)表(或空閑分區(qū)

9、鏈)首開始順序查找，直到找到第一個能滿足其大小要求的空閑分區(qū)為止。如果該空閑分區(qū)大于作業(yè)的大小，則從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，將剩余空閑區(qū)仍然留在空閑分區(qū)表(或空閑分區(qū)鏈)中。最佳適應(yīng)算法的特點：按最佳適應(yīng)算法為作業(yè)分配內(nèi)存，就能把既滿足作業(yè)要求又與作業(yè)大小最接近的空閑分區(qū)分配給作業(yè)。保留了大的空閑區(qū)，但分割后的剩余空閑區(qū)很小。本課程設(shè)計就是分析動態(tài)分區(qū)法，與固定分區(qū)法相比，動態(tài)分區(qū)法在作業(yè)執(zhí)行前并不建立分區(qū)，分區(qū)的建立是在作業(yè)的處理過程中進行的。且其大小可隨作業(yè)或進程對內(nèi)存的要求而改變分區(qū)的建立是在作業(yè)的處理過程中進行的。且其大小可隨作業(yè)或進程對內(nèi)存的要求而改變。這就改變了固定分

10、區(qū)法中那種即使是小作業(yè)也要占據(jù)大分區(qū)的浪費現(xiàn)象，從而提高了內(nèi)存的利用率。2. 概要設(shè)計 動態(tài)分區(qū)分配是根據(jù)進程的實際需要，動態(tài)地為之分配內(nèi)存空間。在實現(xiàn)可變分區(qū)分配時，將涉及到分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)、分區(qū)分配算法和分區(qū)的分配和回收操作這樣三個問題。為了實現(xiàn)分區(qū)分配，系統(tǒng)中必須配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用來描述空閑區(qū)和已分配區(qū)的情況，為分配提供依據(jù)。常用的數(shù)據(jù)結(jié)構(gòu)有兩種形式：空閑分區(qū)表和空閑分區(qū)鏈。為把一個新作業(yè)裝入內(nèi)存，須按照一定的算法，從空閑分區(qū)表或空閑分區(qū)鏈中選出一個分區(qū)分配給該作業(yè)。目前常用的分配算法有：首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法和快速適應(yīng)算法。在動態(tài)分區(qū)存儲

11、管理方式中，主要操作是分配內(nèi)存和回收.系統(tǒng)模塊劃分：動態(tài)可變分區(qū)存儲管理模擬系統(tǒng)退出查看內(nèi)存狀態(tài)查看已分配區(qū)查看空閑區(qū)釋放內(nèi)存申請內(nèi)存初始化內(nèi)存最佳適應(yīng)算法最先適應(yīng)算法 圖（2）各模塊劃分圖主流程圖：開始初始內(nèi)存,開始分配內(nèi)存switch 釋放內(nèi)存最先適應(yīng)算法查看內(nèi)存分配狀態(tài)最佳適應(yīng)算法 圖（3）主流程圖各程序模塊的調(diào)用層次：分配內(nèi)存 查看內(nèi)存分配狀態(tài) 釋放內(nèi)存空閑區(qū)最先適應(yīng)算法最佳適應(yīng)算法已分區(qū) 圖（4）各程序調(diào)用圖3詳細設(shè)計、數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)體定義進程struct areaint start;int end;int len;int sign;struct area * next;5個數(shù)據(jù)成員，

12、分別為： start（分區(qū)的首地址）、end、（分區(qū)尾地址）len（分區(qū)的長度）、sign（標志進程狀態(tài)）、next（指針用來指向下一個進程）。內(nèi)存分配表的圖類似與圖（5）所示：區(qū)號分區(qū)長度起始地址118K40K525K80K79K100K96K120K圖（5）內(nèi)存分配圖最先適應(yīng)算法流程如下圖所示 請求SIZE大小的分區(qū)：從空閑區(qū)表順序查找是否查完表無法分配該空閑去長度是否SIZE取下一表項否該空閑區(qū)長度=SIZE否從可用表中移去該表項，調(diào)整可用表是從空閑區(qū)中取所需大小，修改可用表返回分配起始地址 圖（6）最先適應(yīng)算法流程圖 最佳適應(yīng)算法流程如下圖所示：從空閑區(qū)表中順序查找 p=av 

13、;,p= av p.len<X q=p, p=p->next 否是p.lenX> 是否將p指向的分區(qū)分割，前面p.len-X大小的作為自由分區(qū)，修改長度信息，將之摘除。將后面X大小的分區(qū)進行分配直接分配p所指全部空間，并摘除自由鏈表中p所指分區(qū)將p所指分區(qū)按長度升序重新插入自由鏈表中 結(jié)束圖（7）最佳適應(yīng)算法流程圖4、 系統(tǒng)實施在模擬過程中，沒有充分理解操作系統(tǒng)教程上關(guān)于動態(tài)分區(qū)法、最先適應(yīng)法、最優(yōu)適應(yīng)法的概念，造成了對設(shè)計的目的設(shè)計不清楚，不能很好地表達出此設(shè)計的功能尋找空白區(qū)方法的不同：分區(qū)分配是對可用表（或自由鏈）數(shù)據(jù)結(jié)構(gòu)進行操作，空閑區(qū)表

14、可以按空閑區(qū)大小的升序（降序）和空閑區(qū)首址升序（降序）兩種方法進行組織。才開始并沒有理解這兩種分配方式對這最佳適應(yīng)算法和最先適應(yīng)算法的影響，導致混淆，出現(xiàn)了錯誤。 對題目理解有誤，對模塊之間的關(guān)系設(shè)計不是很清晰。 圖（8）初始化圖 圖(9) 申請內(nèi)存圖 圖（10）查看已分配區(qū)圖 圖（11）查看空閑區(qū)圖 圖（12）釋放內(nèi)存圖 圖（13）查看內(nèi)存狀態(tài)圖最佳算法和最先算法的比較： 圖（13）兩算法的對比圖 五、程序清單#include<iostream>using namespace std;#include<fstream>struct areaint start; 定義分

15、區(qū)的首地址int end;定義分區(qū)的尾地址int len;定義分區(qū)的長度int sign;定義分區(qū)的進程號struct area * next;定義進程的指針; struct area*freehead=NULL;聲明 freehead 是型結(jié)構(gòu)指針。 初始freehead指針為空。 struct area*usedhead=NULL;聲明 usedhead 是型結(jié)構(gòu)指針。初始usedhead指針為空。void create();創(chuàng)建內(nèi)存區(qū)void print(area*);void ask(area*);void ask1(area*);void correct(area*,int);are

16、a * delempty();初始化void inserused(area *,int ,int );void inserfree(area * );void setfree();void listID();/最先適應(yīng)法void listlen();/最優(yōu)適應(yīng)法void swap(area *,area *);/初始化area * delempty() area * p1=freehead;把空閑區(qū)首地址賦值給p1 if(p1->len=0) if(p1->next=NULL)return NULL; else p1=p1->next;指向下一個地址 /最優(yōu)適應(yīng)法void l

17、istlen()int n=0; 初始為零area *p9=freehead->next,*p0=freehead,*p11,*p12,*p13;while(p0!=NULL)不為空p0=p0->next;指向下一個地址n+;n加一p0=freehead;把空閑區(qū)賦值給p0if (n=1)return;else while(p9!=NULL)p12=p0; 把p0空閑區(qū)給p12p13=p9;把p9空閑區(qū)給p13p0=p0->next; p0指向下一個地址p9=p9->next; while(p13!=NULL)/把空閑區(qū)按從小到大的順序排列 if(p12->len

18、)>(p13->len)如果p12長度>p13長度p11=new area;/把p13給p11p11->end=p13->end;p11->len=p13->len;p11->sign=p13->sign;p11->start=p13->start;p11->next=NULL;swap(p13,p12);交換兩個P13，P12swap(p12,p11);交換兩個P12，P11 p13=p13->next;void swap(area *p13,area *p14)p13->len=p14->len;p1

19、3->sign=p14->sign;p13->end=p14->end;p13->start=p14->start;/最先適應(yīng)法void listID()int n=0;area *p9=freehead->next,*p0=freehead,*p11,*p12,*p13;while(p0!=NULL)p0=p0->next;n+;p0=freehead;if (n=1)return;else while(p9!=NULL)p12=p0;p13=p9;p0=p0->next; p9=p9->next; while(p13!=NULL)

20、/把地址按遞增順序排列 if(p12->start)>(p13->start)p11=new area;p11->end=p13->end;p11->len=p13->len;p11->sign=p13->sign;p11->start=p13->start;p11->next=NULL;swap(p13,p12);swap(p12,p11); p13=p13->next;void inserfree(area * p3)查看進程之間的前后的區(qū)域狀態(tài)int flag=0;area *pf=freehead,*pe=f

21、reehead,*pe1; while(pf!=NULL)if(pf->end!=p3->start)/判斷是否有前繼空閑塊pf=pf->next; else break; if(pf!=NULL)flag=5;/flag=5 有前置空閑塊else flag=1;/沒有置1 while(pe!=NULL)/判斷是否有后繼空閑塊if(pe->start!=p3->end)pe1=pe; pe=pe->next;else break; if(pe!=NULL) if(flag=5) flag=6; else flag=4; /有前置且有后置FLAG=6，只有后置

22、=4 else if(flag=1) flag=2; /前后都沒有置2 switch(flag) case 5:pf->end=pf->end+p3->len;前置空閑塊 pf->len=pf->len+p3->len; break; case 4:pe->start=pe->start-p3->len;只有后置 pe->len=pe->len+p3->len; break; case 2: area* p8; p8=new area; p8->start=p3->start; p8->len=p3-&g

23、t;len; p8->sign=0; p8->end=p3->end; p8->next=freehead; freehead=p8; break; case 6:pf->end=pe->end;有前置與后置 pf->len=pf->len+pe->len+p3->len; if(pe->next=NULL) pe1->next=NULL; delete pe; else if(pe=freehead)freehead=pe->next;delete pe;else pe1->next=pe->next;

24、delete pe; break; default :break; void setfree() 釋放進程int chose;cout<<"選擇一個要釋放的任務(wù) :" cin>>chose; area*p7=usedhead,*p2;while( p7!=NULL) /尋找有無此進程if( p7->sign!=chose )p2=p7;p7=p7->next;else break;if(p7=NULL)cout<<"沒有此進程，釋放內(nèi)存失敗，返回修改!"<<endl;return;inserfr

25、ee(p7);/將其釋放的內(nèi)存插入空閑塊中 if(p7=usedhead &&p7->next=NULL) usedhead=NULL; elseif(p7->next=NULL)p2->next=NULL;delete p7;/將次進程從已分配表中刪除else if(p7=usedhead)usedhead=p7->next;delete p7;else p2->next=p7->next;delete p7; cout<<"成功釋放所選任務(wù)的內(nèi)存！當前內(nèi)存狀況為："<<endl;print(fr

26、eehead);print(usedhead);cout<<endl;void inserused(area *p3,int num,int need)/將新項插入已分配表中area*p5;if(usedhead=NULL)p5=new area;p5->start=p3->start;p5->len=need; p5->sign=num;p5->end=p3->start+need;p5->next=NULL;usedhead=p5;elsep5=new area;p5->start=p3->start;p5->len=

27、need; p5->sign=num;p5->end=p3->start+need;p5->next=usedhead;usedhead=p5;void correct(area*p3,int need1)修改列表p3->len=p3->len-need1;p3->start=p3->start+need1;void create() 創(chuàng)建地址長度area* p1;p1=new area;p1->start=0;p1->end=999;p1->len=999;p1->sign=0;p1->next=NULL;free

28、head= p1;void ask1(area*freehead)/讀文件初始化，只用一次int num,need; area*p3=freehead;ifstream infile("123.TXT");while(infile>>num) infile>>need; if(p3->len<need) cout<<"內(nèi)存不足，分配失敗！"<<endl; return; else inserused(p3,num,need);correct(p3,need);void ask(area*free

29、head)申請內(nèi)存int num,need; area*p3=freehead,*p31=freehead;cout<<"input num and need! "<<endl;cin>>num;cin>>need;while( p3!=NULL)if(p3->len<need)p31=p3;p3=p3->next;else break; if(p3=NULL)cout<<"內(nèi)存不足，分配失??！"<<endl;return;inserused(p3,num,need

30、);correct(p3,need); freehead=delempty();cout<<"成功分配申請，當前內(nèi)存狀況為："<<endl;print(freehead);print(usedhead);cout<<endl;void print(area*pp)顯示頁面area*p;p=pp;cout<<"n"if(p=NULL)cout<<"empty list!"<<endl; cout<<"n"return;elsedoco

31、ut<<"start:"<<p->start<<" end:"<<p->end<<" len:"<<p->len<<" sign:"<<p->sign<<endl; p=p->next;while(p!=NULL);cout<<"n"int main() int yourchose,flag1=0,flag2=0; int what; cout&l

32、t;<">>>>現(xiàn)在初始化內(nèi)存>>>>>>>n" cout<<"請選擇：1.手動初始化 2.讀取文件初始化 :" cin>>flag2; create(); if(flag2=2)ask1(freehead); cout<<"內(nèi)存初始狀態(tài)為：n" print(freehead);print(usedhead);cout<<endl; cout<<"-菜單選項-n"cout<<

33、;"1.申請內(nèi)存 2.釋放作業(yè)的內(nèi)存n"cout<<"3.查看空閑塊鏈 4.查看已分配塊鏈n"cout<<"5.查看內(nèi)存狀態(tài) 0.退出n"cout<<"-"<<endl;while(flag1=0) cout<<"-請選擇操作- ：" cin>>yourchose; switch(yourchose) case 1: cout<<"選擇哪種方式？1.最先適應(yīng) 2.最優(yōu)適應(yīng): " cin>

34、>what;if(what=1)listID();else listlen(); ask(freehead);break; case 2:setfree();.釋放作業(yè)的內(nèi)存break; case 3:print(freehead);查看空閑塊鏈break; case 4:print(usedhead);查看已分配塊鏈break;case 5: print(freehead);查看內(nèi)存狀態(tài) print(usedhead);break;case 0:flag1=1;退出break;default: break; return 0;6、 總結(jié)與體會 在一開始老師布置這次的實驗題目時，自己根本不知道要干什么，因為在上課時對動態(tài)分區(qū)分配這節(jié)內(nèi)容不是太了解，所以在上機時不知道如何下手，后來，將本章內(nèi)容反復(fù)的看了幾遍之后，終于有了自己的思路。在模擬過程中，要充分理解操作系統(tǒng)上關(guān)于：1、動態(tài)分區(qū)法：動態(tài)分區(qū)法在作業(yè)執(zhí)行前并不建立分區(qū)，分區(qū)的建立是在作業(yè)的處理過程中進行的。且其大小可隨作業(yè)或進程對內(nèi)存的要求而改變分區(qū)的建立是在作業(yè)的處理過程中進行的。且其大小可隨作業(yè)或進程對內(nèi)存的要求而改變。這就改變了固定分區(qū)法中那種即使是小作業(yè)也要占據(jù)大分區(qū)的浪費