動態(tài)分區(qū)分配管理系統(tǒng)

1、動態(tài)分區(qū)分配管理系統(tǒng)學 院 專 業(yè) 學 號 學 生 姓 名2014年3月 14 日目錄1程序設計的內容和相關的要求-22程序總的功能說明-33程序的模塊的說明-44程序設計的流程圖-55程序的操作說明及運行結果-76源程序-117心得體會-271程序設計的內容和相關的要求：課程設計的目的：操作系統(tǒng)課程設計是計算機學院重要的教學環(huán)節(jié)，它為學生提供了一個既動手又動腦，將課本上的理論知識和實際有機的結合起來，獨立分析和解決實際問題的機會。 進一步鞏固和復習操作系統(tǒng)的基礎知識。 培養(yǎng)學生結構化程序、模塊化程序設計的方法和能力。 提高學生調試程序的技巧和軟件設計的能力。 提高學生分析問題、解決問題以及綜

2、合利用C語言進行程序設計的能力。實現(xiàn)的任務：編寫一個動態(tài)分區(qū)分配程序。設計內容：用高級語言編寫和調試一個動態(tài)分區(qū)內存分配程序，演示實現(xiàn)下列兩種動態(tài)分區(qū)分配算法1.首次適應算法2.循環(huán)首次適應算法設計要求：1.內存中有0-100M的空間為用戶程序空間，最開始用戶空間是空閑的；2.作業(yè)數量、作業(yè)大小、進入內存空間、運行時間需要通過界面進行輸入；3.可讀取樣例數據（要求存放在外部文件夾中）進行作業(yè)數量、作業(yè)大小、進圖內存時間、運行時間的初始化；4.根據作業(yè)進圖內存的時間，采用簡單的先進先出原則進行從外村到內存的調度，作業(yè)具有等待（從外存進入內存執(zhí)行）、裝入（在內存可執(zhí)行）、結束（運行結束，退出內存）

3、三種狀態(tài)。（為了簡化，不考慮cpu的調度與切換，運行時間為作業(yè)在內存中駐留的時間）；5.能夠自動進行內存分配與回收，可根據需要自動進行緊湊與拼接操作，所有過程均有動態(tài)圖形變化的顯示；6.采用可視化界面，可隨時暫停顯示當前內存分配和使用情況圖。2程序總的功能說明：本程序可以從界面直接輸入作業(yè)并進行動態(tài)的內存分配，也可以自動地生成作業(yè)文件并自行調度進行內存分配，每次分配可以選擇兩種算法（首次適應算法和循環(huán)首次算法）中的一種，每次作業(yè)結束后可以進入操作主界面進行再次作業(yè)的操作。 首次適應算法（First-fit）：當要分配內存空間時，就查表，在各空閑區(qū)中查找滿足大小要求的可用塊。只要找到第一個足以滿

4、足要球的空閑塊就停止查找，并把它分配出去；如果該空閑空間與所需空間大小一樣，則從空閑表中取消該項；如果還有剩余，則余下的部分仍留在空閑表中，但應修改分區(qū)大小和分區(qū)始址。循環(huán)首次首次適應算法（Next-first）：在為進程分配內存空間時，不再是每次都從鏈首開始查找，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直到找到一個能滿足要求的空閑分區(qū)，從中劃一塊與要求大小相等的內存空間分配給作業(yè)。內存回收：將釋放作業(yè)所在內存塊的狀態(tài)改為空閑狀態(tài)，刪除其作業(yè)名，設置為空。并判斷該空閑塊是否與其他空閑塊相連，若釋放的內存空間與空閑塊相連時，則合并為同一個空閑塊，同時修改分區(qū)大小及起始地址。3程各模塊的

5、功能說明：（1） 界面顯示函數：showInterface(PL p,Job job)；顯示操作界面showJob(Job job)；顯示作業(yè)鏈表；showPartitiion(PL pl)顯示分區(qū)鏈表（2） 執(zhí)行練習的功能函數：copyJob(Job p)；作業(yè)鏈表復制函數函數InitpartitionList(PL &p)；鏈表初始化分區(qū)函數函數CreateJoblist(Job &job,int count)；創(chuàng)建作業(yè)鏈表函數InsertNode(Job p,Job &job)；按時間順序創(chuàng)建鏈表函數InitpartitionList(PL &p)；初始化

6、分區(qū)鏈表函數（3）文件函數openFile()；打開文件函數ReadFile()；讀取文件函數RandomParameter()；隨即參數讀入文件函數main()/主函數4程序設計的流程圖 ：總體設計流程圖：首次適應算法：回收函數：五 程序操作說明書及結果：在vc+6.0環(huán)境中運行本程序，先進行編譯，然后再進行鏈接，在進行執(zhí)行將會出現(xiàn)顯示界面。按照顯示界面上顯示的提示進行操作，就可以實現(xiàn)相應的功能：六 源程序：#include<time.h>#include <conio.h>#include<stdio.h>#include<stdlib.h>

7、#include <windows.h>#define MemorySize 100/為空閑分區(qū)分配的最大空間（按題目要求）int workload;/輸入作業(yè)的數量；typedef struct jobListint id; / 作業(yè)的name int size; / 作業(yè)大小（需要的存儲空間大?。?int intime; /進入時間 int runtime; /運行時間 int state; /作業(yè)的狀態(tài)（0表示等待，1表示執(zhí)行，2/ 作業(yè)鏈表指針 表示結束并釋放） struct jobList *next; *Job;typedef struct partitionListi

8、nt id; int startAddress; /分區(qū)起始地址 int size; /分區(qū)大小 int state; /分區(qū)的狀態(tài) struct partitionList *prior; struct partitionList *next; / 分區(qū)鏈表指針*PL;FILE *fp;/*打開文件*/void openFile()if(fp=(fopen("D:作業(yè)文件.txt","w")=NULL) printf("無法打開文件!n"); exit(0);/*讀取文件*/void ReadFile()if(fp=(fopen(&

9、quot;D:作業(yè)文件.txt","r")=NULL) printf("無法打開文件!n");exit(0);/*將隨機產生進程的參數寫入文件*/ void RandomParameter()for(int i=0;i<workload;i+) fprintf(fp,"%d %d %d %d %dn",i+1,rand()%80,rand()%20,rand()%10+1,0); openFile(); fclose(fp);/*顯示分區(qū)函數*/void showPartitiion(PL pl)printf(&quo

10、t;t*n");printf("t* StartAddrtidtsize state *n");printf("t*n"); while(pl) printf("t* %dtt%dt%dt%d *",pl->startAddress,pl->id,pl->size,pl->state); printf("n"); pl=pl->next;printf("t*n");Sleep(1000);if(kbhit()=1)system(“pause”);/*按進入

11、時間順序創(chuàng)建一個作業(yè)鏈表*/void InsertNode(Job p,Job &job) /將創(chuàng)建的新結點插入到鏈表中Job q1,q2; q1=job; 12q2=job->next;int i=0;if(!q2)p->next=q2;q1->next=p;while(q2!=NULL&&q2->intime<p->intime)q1=q2;q2=q2->next;i=1;if(!q2&&i=1)p->next=q2;q1->next=p;if(q2!=NULL&&p->in

12、time<=q2->intime)p->next=q2;q1->next=p;Job CreateJoblist(Job &job,int count)/創(chuàng)建作業(yè)鏈表job=(Job)malloc(sizeof(jobList);if(!job)exit(0);job->next=NULL;Job p;printf("idtsizetintimetruntimen");for(int i=0;i<count;i+)p=(Job)malloc(sizeof(jobList);if(!p)exit(0);scanf("%dt

13、%dt%dt%d",&p->id,&p->size,&p->intime,&p->runtime); p->state=0;if(p->size>100)printf("作業(yè)過大不能為之分配內存，請重新輸入的作業(yè)：n"); 13scanf("%dt%dt%dt%d",&p->id,&p->size,&p->intime,&p->runtime);p->state=0;InsertNode(p,job);else

14、 return job; InsertNode(p,job);/*從外部文件讀入數據并進行作業(yè)初始化*/ Job ReadInitJob(Job &job)ReadFile(); job=(Job)malloc(sizeof(jobList); if(!job) exit(0); job->next=NULL; Job p; for(int i=0;i<workload;i+) p=(Job)malloc(sizeof(jobList); if(!p)exit(0); fscanf(fp,"%d %d %d %d %d",&p->id,&a

15、mp;p->size,&p->intime,&p->runtime,&p->state); InsertNode(p,job);return job;/*初始化分區(qū)鏈表*/PL InitpartitionList(PL &p)p=(PL)malloc(sizeof(partitionList); if(!p) exit(0); p->size=MemorySize; printf("輸入分區(qū)首地址:"); scanf("%d",&p->startAddress); p->s

16、tate=0; p->id=0; p->next=NULL; p->prior=NULL; 14return p;/*將一個作業(yè)鏈表復制到另一個鏈表*/Job copyJob(Job p)Job q,L,s=p,r;L=(Job)malloc(sizeof(jobList);L->next=NULL;r=L;s=s->next;while(s)q=(Job)malloc(sizeof(jobList);q->id=s->id;q->state=0;q->intime=s->intime;q->runtime=s->runt

17、ime;q->size=s->size;r->next=q;q->next=NULL;r=q;s=s->next;return L;/*將一個分區(qū)鏈表復制到另一個鏈表*/PL copypartition(PL p)PL q,L,s=p,r;L=(PL)malloc(sizeof(partitionList);L->next=NULL;r=L;s=s->next;while(s)q=(PL)malloc(sizeof(partitionList); q->size=s->size; q->startAddress=s->start

18、Address; q->state=s->state; r->next=q; q->next=NULL; r=q; s=s->next; return L;/*作業(yè)鏈表*/void showJob(Job job)job=job->next; printf("n將作業(yè)按進入時間排序表示:n"); printf("t*n"); printf("t* idtsizetintimetruntimetstate *n"); printf("t*n"); while(job)%dt%dt%

19、dt%dt%d printf("t*",job->id,job->size,job->intime,job->runtime,job->state);printf("n"); job=job->next; printf("t*n"); printf("n");/*回收內存*/void Recover(PL pl3,PL &pl)while(pl3) if(pl3->next&&pl3->prior&&pl3->prior-

20、>state=0&&pl3->next->state=1) pl3->size+=pl3->prior->size;if(pl3->state=0)pl3->startAddress=pl3->prior->startAddress;pl3->state=0;pl3->id=0;if(pl3->prior->prior)pl3->prior->prior->next=pl3;pl3->prior=pl3->prior->prior;elsepl3->pr

21、ior=pl3->prior->prior;pl=pl3;pl3=pl;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->next=pl3-&

22、gt;next->next;elsepl3->next=pl3->next->next;else if(!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->next=pl3->next->next;elsepl3->state=0;else if(!pl

23、3->next)if(pl3->prior->state=0)pl3->size+=pl3->prior->size;pl3->state=0;pl3->id=0;pl3->startAddress=pl->startAddress;if(pl3->prior->prior)pl3->prior->prior->next=pl3;pl3->prior=pl3->prior->prior;else pl3->prior=NULL;pl=pl3;pl3=pl;elsepl3->s

24、tate=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->startAddress=pl3->prior->startAddress;if(pl3->next->next)pl

25、3->next->next->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;/*首次適應算法*/void Cycle

26、FirstFit(PL pl,Job job)int t=0;int n=workload;while(t+1&&n)PL pl1=pl,pl2;printf("時鐘:%dn",t);Job job1=job;job1=job1->next;Job j1=job;j1=j1->next;Job j2=job;j2=j2->next;Job j3=job;j3=j3->next; PL pl3=pl; while(j2) if(j2->intime+j2->runtime=t)printf("作業(yè)id:%d運行結束

27、,釋放內存!",j2->id); n=n-1;j2->state=2;showJob(job);showPartitiion(pl);j2=j2->next;while(j1)if(j1->intime=t)printf("作業(yè)id:%d開始運行,對其分配!",j1->id); j1->state=1;j1=j1->next;while(job1)if(t=job1->intime)while(pl1&&(pl1->size<job1->size|pl1->state=1) p

28、l1=pl1->next;if(pl1)pl2=(PL)malloc(sizeof(partitionList);pl2->startAddress=pl1->startAddress+job1->size;pl2->state=0;pl2->id=0;pl2->size=pl1->size-job1->size; if(pl2->size>5)pl1->size=job1->size;pl1->state=1;存釋放在進行分配!n",job1->id); pl1->id=job1->

29、;id; if(pl1->next) pl1->next->prior=pl2; pl2->next=pl1->next; pl2->prior=pl1; pl1->next=pl2; pl1=pl; else pl1->state=1; pl1->id=job1->id; showJob(job); showPartitiion(pl); else printf("內存不足,將作業(yè):%d置于等待狀態(tài)!等待內 Job j=job1; while(j) j->intime+=1; j->state=0; j=j-&

30、gt;next; Job jj=job; jj=jj->next; while(jj) if(jj->state=2) while(pl3) if(pl3->id=jj->id) pl3->state=0; pl3=pl3->next; jj=jj->next; pl3=pl; 21Recover(pl3,pl);job1=job1->next;t=t+1;Sleep(500);PL p=pl;while(p)p->state=0;p=p->next;showJob(job);showPartitiion(pl);printf(&qu

31、ot;所有進程分配完畢!n");/*循環(huán)首次算法*/ void FirstFit(PL pl,Job job)int t=0;int n=workload;while(t+1&&n)PL pl1=pl,pl2;printf("時鐘:%dn",t);Job job1=job;job1=job1->next;Job j1=job;j1=j1->next;Job j2=job;j2=j2->next;Job j3=job;j3=j3->next;PL pl3=pl;while(j2)if(j2->intime+j2->

32、runtime=t)printf("作業(yè)id:%d運行結束,釋放內存!n",j2->id); n=n-1;j2->state=2; pl3=pl; while(pl3) if(pl3->id=j2->id) pl3->state=0; pl3=pl3->next;showJob(job);showPartitiion(pl);/進程運行結束時進行內存回收 j2=j2->next;while(j1)if(j1->intime=t)printf("作業(yè)id:%d開始運行,對其進行分配!",j1->id);

33、 j1->state=1;j1=j1->next;while(job1)if(t=job1->intime)while(pl1&&(pl1->size<job1->size|pl1->state=1) pl1=pl1->next;if(pl1)pl2=(PL)malloc(sizeof(partitionList);pl2->startAddress=pl1->startAddress+job1->size;pl2->state=0;pl2->id=0;pl2->size=pl1->siz

34、e-job1->size;if(pl2->size>=5) /碎片最大值設為 5pl1->size=job1->size;pl1->state=1;pl1->id=job1->id; else if(pl1->next) pl1->next->prior=pl2; pl2->next=pl1->next; pl2->prior=pl1; pl1->next=pl2; pl1=pl;pl1->state=1;pl1->id=job1->id; showJob(job); showParti

35、tiion(pl);else printf("內存不足,將作業(yè):%d置于等待狀態(tài)!等待內 Job j=job1; while(j) j->intime+=1; j->state=0; j=j->next;存釋放在進行分配!n",job1->id);pl3=pl;Recover(pl3,pl);job1=job1->next; t=t+1; Sleep(500);PL p=pl; while(p) p->state=0; p=p->next; showJob(job);showPartitiion(pl);printf("所

36、有進程分配完畢!n");/*界面顯示*/ void showInterface(PL p,Job job)int a,con=0;Job j1,j2;while(1)printf("t1.首次適應nn");printf("t2.循環(huán)首次適應nn");printf("t3.退出n請選擇:n");if(con=0|con=1)scanf("%d",&a);switch(a)case 1: InitpartitionList(p);j1=copyJob(job);FirstFit(p,j1);break;case 2: InitpartitionList(p);j2=copyJob(job);CycleFirstFit( p,j2);break;case 3:exit(0);brea