動(dòng)態(tài)分區(qū)存儲(chǔ)管理設(shè)計(jì)報(bào)告

《操作系統(tǒng)》課程設(shè)計(jì)報(bào)告書題目：動(dòng)態(tài)分區(qū)存儲(chǔ)管理系別：學(xué)號：學(xué)生姓名：指導(dǎo)教師：完成日期：2013/6/12源代碼可在VisualC++里成功運(yùn)行目錄TOC\o"1-2"\h\z\u一、實(shí)驗(yàn)?zāi)康?動(dòng)態(tài)分區(qū)存儲(chǔ)管理一、實(shí)驗(yàn)?zāi)康牧私鈩?dòng)態(tài)分區(qū)分配中使用的數(shù)據(jù)結(jié)構(gòu)和分配算法，并進(jìn)一步加深對動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式及其實(shí)現(xiàn)過程的理解。二、實(shí)驗(yàn)內(nèi)容用C語言或C++語言分別實(shí)現(xiàn)采用首次適應(yīng)算法和最佳適應(yīng)算法的動(dòng)態(tài)分區(qū)分配過程alloc()和回收過程free()。其中，空閑分區(qū)通過空閑分區(qū)鏈表來管理，在進(jìn)行內(nèi)存分配時(shí)，系統(tǒng)優(yōu)先使用空閑區(qū)低端的空間。假設(shè)初始狀態(tài)如下，可用的內(nèi)存空間為640KB，并有下列的請求序列；作業(yè)1申請130KB作業(yè)2申請60KB作業(yè)3申請100KB作業(yè)2釋放60KB作業(yè)4申請200KB作業(yè)3釋放100KB作業(yè)1釋放130KB作業(yè)5申請140KB作業(yè)6申請60KB作業(yè)7申請50KB作業(yè)6釋放60KB請分別采用首次適應(yīng)算法和最佳適應(yīng)算法進(jìn)行內(nèi)存塊的分配和回收，同時(shí)顯示內(nèi)存塊分配和回收后空閑內(nèi)存分區(qū)鏈的情況。三、設(shè)計(jì)分析1．?dāng)?shù)據(jù)結(jié)構(gòu)作業(yè)隊(duì)列數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)待處理作業(yè)；阻塞作業(yè)隊(duì)列數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)阻塞的作業(yè)。已分配內(nèi)存塊的雙向鏈表，記錄當(dāng)前系統(tǒng)已分配的各個(gè)內(nèi)存塊；未分配內(nèi)存塊的雙向鏈表，記錄系統(tǒng)中剩余的各個(gè)內(nèi)存塊；系統(tǒng)內(nèi)存分配總情況的結(jié)點(diǎn)對象，記錄系統(tǒng)中阻塞的作業(yè)總數(shù)，已分配的內(nèi)存塊數(shù)，剩余的內(nèi)存塊數(shù)。2．主函數(shù)對作業(yè)隊(duì)列、阻塞隊(duì)列、已分配內(nèi)存塊鏈表、未分配內(nèi)存塊鏈表、系統(tǒng)總內(nèi)存分配情況結(jié)點(diǎn)對象進(jìn)行初始化，調(diào)用分配函數(shù)或回收函數(shù)，循環(huán)處理11個(gè)作業(yè)步。3．分配函數(shù)alloc()首次適應(yīng)算法檢索未分配的內(nèi)存塊鏈表，若找到合適的內(nèi)存塊，則加以判斷，空閑內(nèi)存塊大小減去作業(yè)去請求內(nèi)存塊大小小于系統(tǒng)額定的最小碎片值，把空閑塊全部分配，否則進(jìn)行分割分配，最后顯示分配的內(nèi)存信息。4．回收函數(shù)free()首次適應(yīng)算法檢索已分配的內(nèi)存塊鏈表，找到要釋放的內(nèi)存塊后，在已分配鏈表中刪除該結(jié)點(diǎn)，并把該結(jié)點(diǎn)掛到未分配內(nèi)存塊鏈表的結(jié)尾處，然后進(jìn)行兩次調(diào)整，把未分配的內(nèi)存塊鏈表調(diào)整為首地址從小到大的排列順序，并且物理上相鄰的空閑內(nèi)存塊要進(jìn)行合并，以方便下次進(jìn)行分配。調(diào)度分配函數(shù)，循環(huán)處理阻塞作業(yè)隊(duì)列，最后顯示回收后的內(nèi)存情況。5．調(diào)度圖主函數(shù)主函數(shù)Alloc()Alloc()Free()6．運(yùn)行環(huán)境硬件：計(jì)算機(jī)軟件：windowsXPvc++6.07．開發(fā)工具和編程語言開發(fā)工具：vc++6.0編程語言：C語言四、源代碼#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAX_SIZE32767typedefstructnode//定義分區(qū)描述器的結(jié)構(gòu){intid;//編號intadr;//分區(qū)首地址intsize;//分區(qū)大小structnode*next;//指向下一個(gè)分區(qū)的指針}Node;Node*head1,*head2,*back1,*back2,*assign;/*head--空閑區(qū)隊(duì)列首指針back--指向釋放區(qū)Node結(jié)構(gòu)的指針assign-指向申請的內(nèi)存分區(qū)Node結(jié)構(gòu)的指針*/intrequest;//用戶申請存儲(chǔ)區(qū)的大小（由用戶輸入）intcheck(intadd,intsiz,charc)//用于檢查指定的釋放塊（由用戶鍵入）的合法性{Node*p,*head;intcheck=1;if(add<0||siz<0)check=0;/*地址和大小不能為負(fù)*/if(c=='f'||c=='F')head=head1;elsehead=head2;p=head->next;while((p!=NULL)&&check)/*地址不能和空閑區(qū)表中結(jié)點(diǎn)出現(xiàn)重疊*/if(((add<p->adr)&&(add+siz>p->adr))||((add>=p->adr)&&(add<p->adr+p->size)))check=0;elsep=p->next;if(check==0)printf("\t輸入釋放區(qū)地址或大小有錯(cuò)誤?。?！\n");returncheck;/*返回檢查結(jié)果*/}voidinit()//初始化，生成兩個(gè)帶頭節(jié)點(diǎn)的空閑隊(duì)列指針，{//head1指向first-fit的空閑隊(duì)列頭，head2指向best-fit的空閑隊(duì)列頭Node*p,*q;head1=(Node*)malloc(sizeof(Node));head2=(Node*)malloc(sizeof(Node));p=(Node*)malloc(sizeof(Node));q=(Node*)malloc(sizeof(Node));head1->next=p;head2->next=q;p->size=q->size=MAX_SIZE;p->adr=q->adr=0;p->next=q->next=NULL;p->id=q->id=0;}Node*assignment1(intnum,intreq)//實(shí)現(xiàn)首次適應(yīng)算法的分配{Node*before,*after,*ass;ass=(Node*)malloc(sizeof(Node));before=head1;after=head1->next;ass->id=num;ass->size=req;while(after->size<req){before=before->next;after=after->next;}if(after==NULL){ass->adr=-1;//分配失敗}else{if(after->size==req){//空閑分區(qū)恰好等于所申請的內(nèi)存大小before->next=after->next;ass->adr=after->adr;}else{//空閑分區(qū)大于所申請的內(nèi)存大小after->size-=req;ass->adr=after->adr;after->adr+=req;}}returnass;}voidacceptment1(intaddress,intsiz,intrd)//實(shí)現(xiàn)首次適應(yīng)算法的回收{(diào)Node*before,*after;intinsert=0;back1=(Node*)malloc(sizeof(Node));before=head1;after=head1->next;back1->adr=address;back1->size=siz;back1->id=rd;back1->next=NULL;while(!insert&&after){//將要被回收的分區(qū)插入空閑區(qū)（按首址大小從小到大插入）if((after==NULL)||((back1->adr<=after->adr)&&(back1->adr>=before->adr))){before->next=back1;back1->next=after;insert=1;}else{before=before->next;after=after->next;}}if(insert){if(back1->adr==before->adr+before->size){//和前邊分區(qū)合并before->size+=back1->size;before->next=back1->next;free(back1);}elseif(after&&back1->adr+back1->size==after->adr){//和后邊分區(qū)合并back1->size+=after->size;back1->next=after->next;back1->id=after->id;free(after);after=back1;}printf("\t首先分配算法回收內(nèi)存成功?。?！\n");}elseprintf("\t首先分配算法回收內(nèi)存失敗?。?！\n");}Node*assignment2(intnum,intreq)//實(shí)現(xiàn)最佳適應(yīng)算法的分配{Node*before,*after,*ass,*q;ass=(Node*)malloc(sizeof(Node));q=(Node*)malloc(sizeof(Node));before=head2;after=head2->next;ass->id=num;ass->size=req;while(after->size<req){before=before->next;after=after->next;//printf("\nzphzph1\n");}if(after==NULL){ass->adr=-1;//分配失敗//printf("\nzphzph2\n");}else{if(after->size==req){//空閑分區(qū)恰好等于所申請的內(nèi)存大小before->next=after->next;ass->adr=after->adr;//printf("\nzphzph3\n");}else{//空閑分區(qū)大于所申請的內(nèi)存大小q=after;before->next=after->next;ass->adr=q->adr;q->size-=req;q->adr+=req;//printf("\nzphzph4\n");before=head2;after=head2->next;//printf("\nzphzph4\n");if(after==NULL){//printf("\nzphzph5\n");before->next=q;q->next=NULL;after=q;}else{//printf("\nzphzph6\n");while(after&&((after->size)<(q->size))){printf("\nzphzph7\n");before=before->next;after=after->next;}//printf("\nzphzph8\n");before->next=q;q->next=after;after=q;}}}return(ass);}voidacceptment2(intaddress,intsiz,intrd)//實(shí)現(xiàn)最佳適應(yīng)算法的回收{(diào)Node*before,*after;intinsert=0;//是否被回收的標(biāo)志back2=(Node*)malloc(sizeof(Node));before=head2;after=head2->next;back2->adr=address;back2->size=siz;back2->id=rd;back2->next=NULL;if(head2->next==NULL){//空閑隊(duì)列為空head2->next=back2;//head2->size=back2->size;}else{//空閑隊(duì)列不為空while(after){if(back2->adr==after->adr+after->size){//和前邊空閑分區(qū)合并before->next=after->next;after->size+=back2->size;back2=after;after=before->next;}else{before=before->next;after=after->next;}}before=head2;after=head2->next;while(after){if(after->adr==back2->adr+back2->size){//和后邊空閑區(qū)合并before->next=after->next;back2->size+=after->size;after=before->next;}else{before=before->next;after=after->next;}}before=head2;after=head2->next;while(!insert){//將被回收的塊插入到恰當(dāng)?shù)奈恢茫ò捶謪^(qū)大小從小到大）if(after==NULL||((after->size>back2->size)&&(before->size<back2->size))){before->next=back2;back2->next=after;insert=1;break;}else{before=before->next;after=after->next;}}}if(insert)printf("\t最佳適應(yīng)算法回收內(nèi)存成功?。?！\n");elseprintf("\t最佳適應(yīng)算法回收內(nèi)存失?。。。n");}voidprint(charchoice)//輸出空閑區(qū)隊(duì)列信息{Node*p;if(choice=='f'||choice=='F')p=head1->next;elsep=head2->next;if(p){printf("\n空閑區(qū)隊(duì)列的情況為：\n");printf("\t編號\t首址\t終址\t大小\n");while(p){printf("\t%d\t%d\t%d\t%d\n",p->id,p->adr,p->adr+p->size-1,p->size);p=p->next;}}}voidmenu()//菜單及主要過程{charchose;intch,num,r,add,rd;while(1){system("cls");printf("\t\t存儲(chǔ)管理動(dòng)態(tài)分區(qū)分配及回收算法模擬\n\n");printf("\tF.最先適應(yīng)算法(First-Fit)\n\n");printf("\tB.最佳適應(yīng)算法(Best-Fit)\n\n");printf("\tE.退出程序\n\n");printf("\t你選擇（f/b）:");scanf("%c",&chose);if(chose=='e'||chose=='E')exit(0);else{system("cls");while(1){if(chose=='f'||chose=='F')printf("\t\t最先適應(yīng)算法(First-Fit)模擬\n\n");if(chose=='b'||chose=='B')printf("\t\t最佳適應(yīng)算法(Best-Fit)模擬\n\n");printf("\t1.分配內(nèi)存\t\t2.回收內(nèi)存\n\n");printf("\t3.查看內(nèi)存\t\t4.返回\n\n");printf("\t你選擇（1/2/3/4）:");scanf("%d",&ch);fflush(stdin);switch(ch){case1:printf("輸入分區(qū)號：");scanf("%d",&num);printf("輸入申請的分區(qū)大?。?);scanf("%d",&r);if(chose=='f'||chose=='F')assign=assignment1(num,r);elseassign=assignment2(num,r);if(assign->adr==-1){printf("分配內(nèi)存失?。n");}else