動(dòng)態(tài)分區(qū)分配存儲(chǔ)管理系統(tǒng)

1、.動(dòng)態(tài)分區(qū)分配存儲(chǔ)管理系統(tǒng) 學(xué) 院 專(zhuān) 業(yè) 學(xué) 號(hào) 學(xué) 生 姓 名 指 導(dǎo) 老 師 2014年3月19日 目錄一、設(shè)計(jì)目的與內(nèi)容3 1、設(shè)計(jì)目的3 2、設(shè)計(jì)內(nèi)容3 3、設(shè)計(jì)要求3二、算法的基本思想31、首次適應(yīng)算法32、循環(huán)首次適應(yīng)算法3三、主要功能模塊流程圖4 1、主函數(shù)流程圖.4 2、首次適應(yīng)算法流程圖.5 3、循環(huán)首次適應(yīng)算法流程圖.6四、系統(tǒng)測(cè)試.7輸入界面，按要求輸入：7五、結(jié)論8六、源程序91、 設(shè)計(jì)目的與內(nèi)容設(shè)計(jì)的目的 操作系統(tǒng)課程設(shè)計(jì)是計(jì)算機(jī)專(zhuān)業(yè)重要的教學(xué)環(huán)節(jié)，它為學(xué)生提供了一個(gè)既動(dòng)手又動(dòng)腦，將課本上的理論知識(shí)和實(shí)際有機(jī)的結(jié)合起來(lái)，獨(dú)立分析和解決實(shí)際問(wèn)題的機(jī)會(huì)。 l 進(jìn)一步鞏固

2、和復(fù)習(xí)操作系統(tǒng)的基礎(chǔ)知識(shí)。 l 培養(yǎng)學(xué)生結(jié)構(gòu)化程序、模塊化程序設(shè)計(jì)的方法和能力。 l 提高學(xué)生調(diào)試程序的技巧和軟件設(shè)計(jì)的能力。 l 提高學(xué)生分析問(wèn)題、解決問(wèn)題以及綜合利用 C 語(yǔ)言進(jìn)行程序設(shè)計(jì)的能力。 設(shè)計(jì)內(nèi)容：用高級(jí)語(yǔ)言編寫(xiě)和調(diào)試一個(gè)動(dòng)態(tài)分區(qū)內(nèi)存分配程序，演示實(shí)現(xiàn)下列兩種動(dòng)態(tài)分區(qū)分配算法 1. 首次適應(yīng)算法2. 循環(huán)首次適應(yīng)算法 設(shè)計(jì)要求：1. 內(nèi)存中有0-100M 的空間為用戶(hù)程序空間，最開(kāi)始用戶(hù)空間是空閑的 2. 作業(yè)數(shù)量、作業(yè)大小、進(jìn)入內(nèi)存時(shí)間、運(yùn)行時(shí)間需要通過(guò)界面進(jìn)行輸入 3. 可讀取樣例數(shù)據(jù)（要求存放在外部文件中）進(jìn)行作業(yè)數(shù)量、作業(yè)大小、進(jìn)入內(nèi)存時(shí)間、運(yùn)行時(shí)間的初始化 4. 根據(jù)作

3、業(yè)進(jìn)入內(nèi)存的時(shí)間，采用簡(jiǎn)單的先進(jìn)先出原則進(jìn)行從外存到內(nèi)存的調(diào)度，作業(yè)具有等待（從外存進(jìn)入內(nèi)存執(zhí)行）、裝入（在內(nèi)存可執(zhí)行）、結(jié)束（運(yùn)行結(jié)束，退出內(nèi)存）三種狀態(tài)。（為了簡(jiǎn)化，不考慮CPU 的調(diào)度與切換，運(yùn)行時(shí)間為作業(yè)在內(nèi)存中駐留的時(shí)間） 5. 能夠自動(dòng)進(jìn)行內(nèi)存分配與回收，可根據(jù)需要自動(dòng)進(jìn)行緊湊與拼接操作，所有過(guò)程均有動(dòng)態(tài)圖形變化的顯示 6. 采用可視化界面，可隨時(shí)暫停顯示當(dāng)前內(nèi)存分配和使用情況圖。二、算法的思想1、首次適應(yīng)算法 空閑分區(qū)鏈以地址遞增的次序鏈接，分配內(nèi)存時(shí)，從鏈?zhǔn)组_(kāi)始順序查找，直至找到一個(gè)大小能滿(mǎn)足要求的空閑分區(qū)為止；然后再按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，取消

4、的空閑分區(qū)仍留在空閑鏈中。若從鏈?zhǔn)字敝伶溛捕疾荒苷业揭粋€(gè)能滿(mǎn)足要求的分區(qū)，則此次內(nèi)存分配失敗，返回。2、循環(huán)首次適應(yīng)算法 在為進(jìn)程分配內(nèi)存空間時(shí)，不再是每次都從鏈?zhǔn)组_(kāi)始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開(kāi)始查找，直至找到一個(gè)能滿(mǎn)足要求的空閑分區(qū)，從中劃出一塊與請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè)三、主要功能模塊流程圖主函數(shù)開(kāi)始Dulinklistpf 否Inputchoice(ch) 是Ch=2breakCh=1 結(jié)束multiplexInitpartitionlist(p) 否 是 否multiplex 是首次適應(yīng)算法： 開(kāi)始 Intt=1T&num 否 是Dulinklistpll

5、=block.Intx=0Xn 否 是multiplex X+multiplexmultiplex結(jié)束循環(huán)首次適應(yīng)算法開(kāi)始 Intt=1T&num 否 是Dulinklistpll=block.Intm=0mn 否 是multiplex m+multiplexmultiplex結(jié)束四、系統(tǒng)測(cè)試程序運(yùn)行實(shí)例如下：輸入界面，按要求輸入：五、結(jié)論 作業(yè)采用數(shù)組形式進(jìn)行存儲(chǔ)，起初想用數(shù)組模擬分區(qū)，但劃分記錄比較不易，時(shí)間空間復(fù)雜度較大，容易混亂，遂決定用鏈表形式模擬分區(qū)情況?；灸苓\(yùn)行符合要求，能模擬出動(dòng)態(tài)分區(qū)過(guò)程及最終結(jié)果六源程序#include #include #include #include

6、 #define Free 0#define Use 1#define MAX_length 100 /最大內(nèi)存空間為100MB#define MaxNumber 100int FreePartitionMaxNumber=16,16,8,32,64,32,8,16,64;/空閑分區(qū)int ProcessNeedMaxNumber=7,18,9,20,35,8;/每個(gè)進(jìn)程需求int FirstPartitionMaxNumber;/首次int CycleFirstPartitionMaxNumber;/循環(huán)int PartitionNumber=9,ProcessNum=6;/空閑分區(qū)數(shù)及進(jìn)程

7、數(shù)bool v();bool v()int j; cout首次適應(yīng)算法endl; / FirstPartitionMethod();for(int i=0;iProcessNum;i+)/進(jìn)程 for(j=0;j=ProcessNeedi) FirstPartitioni =j; FreePartitionj-=ProcessNeedi; break; / c_out(FirstPartition); for(i=0;iProcessNum;i+) coutFreePartitioni ; coutendl; / Beginning(); FreePartition0=16; FreePart

8、ition1=16; FreePartition2=8; FreePartition3=32; FreePartition4=64; FreePartition5=32; FreePartition6=8; FreePartition7=16; FreePartition8=64;cout循環(huán)首次適應(yīng)算法endl; /CycleFirstPartitionMethod(); j=0; for(i=0;i=ProcessNeedi) CycleFirstPartitioni=j; FreePartitionj-=ProcessNeedi; break; j+; j=j%PartitionNumb

9、er; /c_out(CycleFirstPartition);for(i=0;iProcessNum;i+) coutCycleFirstPartitioni ;cout0;x-)for(int y = 1000;y0;y-);/-/-初始化-DuLinkList InitpartitionList(DuLinkList &p)p=(DuLinkList)malloc(sizeof(DuLNode);/申請(qǐng)空間if(!p)exit(0);p-size=100; /初始化大小printf(輸入分區(qū)首地址:);scanf(%d,&p-start);p-state=0; /狀態(tài)置空閑p-ID=0;

10、 /分區(qū)號(hào)p-next=NULL;p-prior=NULL;return p;/-/-輸入函數(shù)-int Putin(int &n)int i;Job temp;printf(請(qǐng)輸入任務(wù)數(shù)目:);scanf(%d,&n);a=(Job*)malloc(n*sizeof(Job);A=(Job*)malloc(n*sizeof(Job);for(i=0;in;i+)printf(n);printf(信息輸入:nn);printf(作業(yè)號(hào):);scanf(%d,&ai.num);printf(作業(yè)大小:);scanf(%d,&ai.size);printf(作業(yè)進(jìn)入時(shí)間:);scanf(%d,&ai

11、.ctime);printf(作業(yè)運(yùn)行時(shí)間:);scanf(%d,&ai.rtime);ai.state=0; /默認(rèn)狀態(tài)為FreeAi = ai;for(int j = 0;j n;j+) for(i = j;i ai.ctime) temp = aj;aj = ai;ai = temp;/冒泡排序freopen(data.txt,w,stdout);for (i = 0;i n;i+)printf(%d %d %d %dn,ai.num,ai.size,ai.ctime,ai.rtime);fclose(stdout);freopen(CON,w,stdout);printf(保存成功nn

12、);return 1;/-/-讀文件-int order(int &n)Job temp;printf(Input the number of the task:n);scanf(%d,&n);a=(Job*)malloc(n*sizeof(Job);freopen(data.txt,r,stdin);for(int i=0;in;i+)scanf(%d,&ai.num);scanf(%d,&ai.size);scanf(%d,&ai.ctime);scanf(%d,&ai.rtime);fclose(stdin);freopen(CON,r,stdin);for(int j = 0;j n;

13、j+) for(i = j;i ai.ctime) temp = aj;aj = ai;ai = temp;return 1;/-/-顯示分區(qū)-void showPartition(DuLinkList pl)printf(nttt分區(qū)表n);printf(t-n);printf(t 開(kāi)始地址t分區(qū)號(hào)t大小 狀態(tài) n);printf(t-n);while(pl)printf(t %dtt%dt%dt,pl-start,pl-ID,pl-size);if(pl-state = 0)printf(空閑 n);if(pl-state = 1)printf(已分配 n);pl=pl-next;prin

14、tf(t-n);/-/-回收函數(shù)-void huishou(DuLinkList pl3,DuLinkList &pl)/pl3是分區(qū)鏈表指針 pl頭while(pl3) if(pl3-state=0) if(pl3-next&pl3-prior&pl3-prior-state=0&pl3-next-state=1)/pl3-size+=pl3-prior-size; pl3-start=pl3-prior-start;pl3-state=0;pl3-ID=0; if(pl3-prior-prior) pl3-prior-prior-next=pl3;/pl3與最前一個(gè) pl3-prior=p

15、l3-prior-prior;/else pl3-prior=pl3-prior-prior;/pl3指向空pl=pl3;pl3=pl;/pl3與頭else if(pl3-prior&pl3-next&pl3-next-state=0&pl3-prior-state=1)pl3-size+=pl3-next-size;pl3-state=0;pl3-ID=0;if(pl3-next-next)pl3-next-next-prior=pl3;/建立新鏈表pl3與最后一個(gè)結(jié)點(diǎn)pl3-next=pl3-next-next;/elsepl3-next=pl3-next-next;/指向空else if

16、(!pl3-prior) if(pl3-next-state=0)pl3-size+=pl3-next-size;pl3-state=0;pl3-ID=0; if(pl3-next-next)pl3-next-next-prior=pl3;/pl3與最后pl3-next=pl3-next-next;/elsepl3-state=0;else if(!pl3-next)if(pl3-prior-state=0)pl3-size+=pl3-prior-size;pl3-state=0;pl3-ID=0;pl3-start=pl-start; if(pl3-prior-prior)pl3-prior

17、-prior-next=pl3;/pl3與最前 pl3-prior=pl3-prior-prior;/elsepl3-prior=NULL;/pl3指向空pl=pl3;/pl3與頭pl3=pl;/elsepl3-state=0;else if(pl3-next&pl3-prior&pl3-next-state=0&pl3-prior-state=0)pl3-size=pl3-size+pl3-next-size+pl3-prior-size;pl3-state=0;pl3-ID=0;pl3-start=pl3-prior-start;if(pl3-next-next)pl3-next-next

18、-prior=pl3;if(pl3-prior-prior)pl3-prior-prior-next=pl3;pl3-next=pl3-next-next;/指向空pl3-prior=pl3-prior-prior;elsepl3-next=pl3-next-next;/指向空pl3-prior=pl3-prior-prior;/指向頭pl=pl3;pl3=pl;pl3=pl3-next;/-/-首次適應(yīng)算法-void Firstfit(DuLinkList block_first,int n)int t=1;int num=n;while(t&num)DuLinkList pl1=block

19、_first,pl2,pl3=block_first;printf(時(shí)鐘:%dn,t);DuLNode *p=block_first;DuLNode *q=block_first; for(int x=0;xn;x+)if(t=ax.ctime+ax.rtime) ax.state=2;for(int m=0;mID=am.num)/分區(qū)號(hào)等于作業(yè)號(hào)時(shí)q-state=Free;/在作業(yè)完成時(shí)，作業(yè)號(hào)等于分區(qū)號(hào)時(shí)空閑q=q-next;showJob(n);showPartition(block_first);for( m=0;mn;m+)if(am.ctime=t)am.state=1;prin

20、tf(作業(yè):%d開(kāi)始運(yùn)行,對(duì)其分配!,am.num);for( m=0;mstate = 1|pl1-sizenext;if(pl1)pl2=(DuLinkList)malloc(sizeof(DuLNode);pl2-start=pl1-start+am.size;pl2-state=0;pl2-ID=0;pl2-size=pl1-size-am.size;if(pl2-size5)pl1-size=am.size;pl1-state=1;pl1-ID=am.num;if(pl1-next) pl1-next-prior=pl2;pl2-next=pl1-next;pl2-prior=pl1

21、;pl1-next=pl2;pl1=block_first;elsepl1-state=1;pl1-ID=am.num;showJob(n);showPartition(block_first);elsecout內(nèi)存不足，等待釋放endl;for(int i=m;in;i+)ai.ctime+=1;p=block_first;huishou(p, block_first);t+=1;/-/-顯示作業(yè)-void showJob(int n)printf(nttt作業(yè)表:n);printf(t-n);printf(t 作業(yè)號(hào)t大小t進(jìn)入時(shí)間t運(yùn)行時(shí)間t狀態(tài) n);printf(t-n);for(i

22、nt m=0;mn;m+)printf(t %dt %dt%dt %dt,am.num,am.size,am.ctime,am.rtime);if(am.state = 0)printf( 等待 n);if(am.state = 1)printf( 裝入 n);if(am.state = 2)printf( 結(jié)束 n);printf(t-n);/-/- 循 環(huán) 首 次 適 應(yīng) 算 法 -void Nextfit(DuLinkList block_first,int n)int t=1;int num=n;DuLinkList flag;flag=block_first;while(t&num)

23、DuLinkList pl1=block_first,pl2,pl3=block_first;printf(時(shí)鐘:%dn,t);DuLNode *p=block_first;DuLNode *q=block_first;for(int m=0;mID=am.num)q-state=Free;q=q-next;showJob(n);showPartition(block_first);for( m=0;mn;m+)if(am.ctime=t)am.state=1;printf(作業(yè):%d開(kāi)始運(yùn)行,對(duì)其分配!,am.num);for( m=0;mstate = 1|flag-sizenext;pl1=flag;if(pl1)pl2=(DuLinkList)malloc(sizeof(DuLNode);pl2-start=pl1-start+am.size;pl2-state=0;pl2-ID=0;pl2-size=pl1-size-a