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

1、淮北師范大學(xué)程序設(shè)計(jì)課程設(shè)計(jì)動(dòng)態(tài)分區(qū)分配存儲(chǔ)管理系統(tǒng)學(xué) 院 計(jì)算機(jī)科學(xué)與技術(shù)專 業(yè)學(xué) 號(hào) 學(xué) 生 姓 名指導(dǎo)教師姓名2012年3月 15 日一、設(shè)計(jì)目的與內(nèi)容用高級(jí)語言編寫和調(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)算法1. 內(nèi)存中有0-100M 的空間為用戶程序空間，最開始用戶空間是空閑的。2. 作業(yè)數(shù)量、作業(yè)大小、進(jìn)入內(nèi)存時(shí)間、運(yùn)行時(shí)間需要通過界面進(jìn)行輸入。3. 可讀取樣例數(shù)據(jù)（要求存放在外部文件中）進(jìn)行作業(yè)數(shù)量、作業(yè)大小、進(jìn)入內(nèi)存時(shí)間、運(yùn)行時(shí)間的初始化。4. 根據(jù)作業(yè)進(jìn)入內(nèi)存的時(shí)間，采用簡(jiǎn)單的先進(jìn)先出原則進(jìn)行從外存到內(nèi)存的調(diào)度，作業(yè)

2、具有等待（從外存進(jìn)入內(nèi)存執(zhí)行）、裝入（在內(nèi)存可執(zhí)行）、結(jié)束（運(yùn)行結(jié)束，退出內(nèi)存）三種狀態(tài)。5. 能夠自動(dòng)進(jìn)行內(nèi)存分配與回收，可根據(jù)需要自動(dòng)進(jìn)行緊湊與拼接操作。二、算法的基本思想1、定義基本結(jié)構(gòu)：1作業(yè)結(jié)構(gòu)：typedef struct JOBint num; /作業(yè)號(hào)int size; /作業(yè)大小int ctime; /作業(yè)進(jìn)入時(shí)間int rtime; /作業(yè)運(yùn)行時(shí)間int state; /作業(yè)狀態(tài)Job;2)分區(qū)結(jié)構(gòu)：typedef struct DuLNodeint ID; /分區(qū)號(hào)int start; /開始地址int size; /大小int state; /0=尚未使用 1=使用 2

3、=釋放struct DuLNode *prior;/前驅(qū)指針struct DuLNode *next; /后即指針DuLNode, * DuLinkList;2、基本操作：int Firstfit(int);/首次適應(yīng)算法int Next_fit(int); /循環(huán)首次適應(yīng)算法void showJob(int); /顯示作業(yè)表void showPartiton(DuLinkList);/顯示分區(qū)表DuLinkList InitpartitionList(DuLinkList &p);/初始化void huishou(DuLinkList pl3,DuLinkList &pl);

4、/回收函數(shù)int Putin(int &n);/輸入函數(shù)，輸入作業(yè)相關(guān)信息3、首次適應(yīng)算法空閑分區(qū)鏈以地址遞增的次序鏈接，分配內(nèi)存時(shí)，從鏈?zhǔn)组_始順序查找，直至找到一個(gè)大小能滿足要求的空閑分區(qū)為止；然后再按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，取消的空閑分區(qū)仍留在空閑鏈中。若從鏈?zhǔn)字敝伶溛捕疾荒苷业揭粋€(gè)能滿足要求的分區(qū)，則此次內(nèi)存分配失敗，返回。4、循環(huán)首次適應(yīng)算法在為進(jìn)程分配內(nèi)存空間時(shí)，不再是每次都從鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找，直至找到一個(gè)能滿足要求的空閑分區(qū)，從中劃出一塊與請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè)。三、主要功能模塊流程圖主函

5、數(shù)：首次適應(yīng)算法： 循環(huán)首次適應(yīng)算法四、系統(tǒng)測(cè)試程序運(yùn)行實(shí)例如下：1、輸入界面，按要求輸入：2、選擇算法及分區(qū)首地址：3、運(yùn)行結(jié)束后顯示，并繼續(xù)選擇：4、退出：五、結(jié)論作業(yè)采用數(shù)組形式進(jìn)行存儲(chǔ)，起初想用數(shù)組模擬分區(qū)，但劃分記錄比較不易，時(shí)間空間復(fù)雜度較大，容易混亂，遂決定用鏈表形式模擬分區(qū)情況。基本能運(yùn)行符合要求，能模擬出動(dòng)態(tài)分區(qū)過程及最終結(jié)果。六、源程序及系統(tǒng)文件使用說明#include <stdio.h>#include <stdlib.h>#include <iostream.h>#include <windows.h>#define Fr

6、ee 0#define Use 1#define MAX_length 100 /最大內(nèi)存空間為100MB/-作業(yè)結(jié)構(gòu)體數(shù)組-typedef struct JOBint num; /作業(yè)號(hào) int size; /作業(yè)大小 int ctime; /作業(yè)進(jìn)入時(shí)間 int rtime; /作業(yè)運(yùn)行時(shí)間 int state; /作業(yè)狀態(tài)Job;typedef struct DuLNodeint ID; /分區(qū)號(hào)int start; /開始地址 int size; /大小 int state; /0=尚未使用 1=使用 2=釋放 struct DuLNode *prior;/前驅(qū)指針 struct Du

7、LNode *next; /后即指針DuLNode, * DuLinkList;/-int Firstfit(int);/首次適應(yīng)算法int Next_fit(int); /循環(huán)首次適應(yīng)算法void showJob(int); /顯示作業(yè)表void showPartiton(DuLinkList);/顯示分區(qū)表/-/-全局變量-int f;Job *A; /排序前Job *a; /排序后Job *temp;/-功能函數(shù)- void delay()/- /-初始化- DuLinkList InitpartitionList(DuLinkList &p)p=(DuLinkList)mall

8、oc(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; /分區(qū)號(hào) p->next=NULL; p->prior=NULL; for(int x = 10000;x>0;x-) for(int y = 1000;y>0;y-);return p;/-/-輸入函數(shù)- int Putin(int &a

9、mp;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;i<n;i+) printf("n"); printf("信息輸入:nn"); printf("作業(yè)號(hào):"); scanf("%d",&ai.num); printf("作業(yè)大小:");

10、 scanf("%d",&ai.size); printf("作業(yè)進(jìn)入時(shí)間:"); scanf("%d",&ai.ctime); printf("作業(yè)運(yùn)行時(shí)間:"); scanf("%d",&ai.rtime); ai.state=0; /默認(rèn)狀態(tài)為Free Ai = ai; for(int j = 0;j < n;j+) for(i = j;i< n;i+) if(aj.ctime > ai.ctime) temp = aj; aj = ai; ai

11、= 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"); return 1;/- /-讀文件- int order(int &n)Job temp; pr

12、intf("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;i<n;i+) scanf("%d",&ai.num); scanf("%d",&ai.size); scanf("%d",&ai.ctime); scanf(&q

13、uot;%d",&ai.rtime); fclose(stdin); freopen("CON","r",stdin); for(int j = 0;j < n;j+) for(i = j;i< n;i+) if(aj.ctime > ai.ctime) temp = aj; aj = ai; ai = temp;return 1;/- /-顯示分區(qū)- void showPartition(DuLinkList pl)printf("nttt分區(qū)表n"); printf("t-n"

14、;); printf("t 開始地址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; printf("t-n");/-/-回收函數(shù)- void hu

15、ishou(DuLinkList pl3,DuLinkList &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->pri

16、or->prior) pl3->prior->prior->next=pl3; pl3->prior=pl3->prior->prior; else pl3->prior=pl3->prior->prior; pl=pl3; pl3=pl; else if(pl3->prior&&pl3->next&&pl3->next->state=0&&pl3->prior->state=1) else if(!pl3->prior) if(pl3->

17、next->state=0) pl3->size+=pl3->next->size; pl3->state=0; pl3->ID=0; if(pl3->next->next) else pl3->next->next->prior=pl3; pl3->next=pl3->next->next; pl3->size+=pl3->next->size; pl3->state=0; pl3->ID=0; if(pl3->next->next) pl3->next->

18、;next->prior=pl3; else pl3->next=pl3->next->next; pl3->next=pl3->next->next; pl3->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->

19、;prior->prior->next=pl3; pl3->prior=pl3->prior->prior; else pl3->state=0; else pl3->prior=NULL; pl=pl3; pl3=pl; else if(pl3->next&&pl3->prior&&pl3->next->state=0&&pl3->prior->state=0) pl3->size=pl3->size+pl3->next->size+pl3-&

20、gt;prior->size; pl3->state=0; pl3->ID=0; pl3->start=pl3->prior->start; if(pl3->next->next) pl3->next->next->prior=pl3; if(pl3->prior->prior) pl3->prior->prior->next=pl3; pl3->next=pl3->next->next; pl3->prior=pl3->prior->prior; else pl

21、3->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) for(int m=0;m<n;m+) if(t=am.ctime+am.rtime) num-=1; am.state=2; while(q) if(q->ID=am.num)

22、 q->state=Free; q=q->next; DuLinkList pl1=block_first,pl2,pl3=block_first; printf("時(shí)鐘:%dn",t); DuLNode *p=block_first; DuLNode *q=block_first; showJob(n); showPartition(block_first); for( m=0;m<n;m+) if(am.ctime=t) am.state=1; printf("作業(yè):%d開始運(yùn)行,對(duì)其分配!",am.num); for( m=0;m

23、<n;m+) if(t=am.ctime) while(pl1&&(pl1->state = 1|pl1->size<am.size) pl1=pl1->next; 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->size>5) else pl1->state=1;

24、 pl1->ID=am.num; 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; pl1->next=pl2; pl1=block_first; showJob(n); showPartition(block_first); else cout<<"內(nèi)存不足，等待釋放"<<endl; for(

25、int i=m;i<n;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(int m=0;m<n;m+) printf("t %dt %dt%dt %dt",am.num,am.

26、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;

27、 while(t&&num) DuLinkList pl1=block_first,pl2,pl3=block_first; printf("時(shí)鐘:%dn",t); DuLNode *p=block_first; DuLNode *q=block_first; for(int m=0;m<n;m+) if(t=am.ctime+am.rtime) num-=1; am.state=2; while(q) if(q->ID=am.num) q->state=Free; q=q->next; showJob(n); showPartiti

28、on(block_first);for( m=0;m<n;m+) for( m=0;m<n;m+) if(t=am.ctime) while(flag&&(flag->state = 1|flag->size<am.size) flag=flag->next; pl1=flag; if(pl1) else pl2=(DuLinkList)malloc(sizeof(DuLNode); pl2->start=pl1->start+am.size; pl2->state=0; pl2->ID=0; pl2->size

29、=pl1->size-am.size; if(pl2->size>5) else flag=pl2; showJob(n); showPartition(block_first); pl1->state=1; pl1->ID=am.num; 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; pl1->next=pl2; pl1=block_first; i