模擬實(shí)現(xiàn)用位示圖法管理文件存儲(chǔ)空間的分配與回收1

1、 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院操作系統(tǒng)綜合試驗(yàn)報(bào)告 （2016/2017學(xué)年 第一學(xué)期）學(xué)生姓名：學(xué)生專業(yè)： 網(wǎng)絡(luò)工程學(xué)生班級(jí)： 網(wǎng)絡(luò)班學(xué)生學(xué)號(hào)：2指導(dǎo)教師： 2016年12月12日計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院綜合試驗(yàn)任務(wù)書(shū)課程設(shè)計(jì)名稱操作系統(tǒng)課程設(shè)計(jì)課程設(shè)計(jì)題目模擬實(shí)現(xiàn)用位示圖法管理文件存儲(chǔ)空間的分配與回收學(xué)生姓名專業(yè)班級(jí)網(wǎng)學(xué)號(hào)2綜合試驗(yàn)任務(wù)內(nèi)容問(wèn)題描述 設(shè)計(jì)實(shí)現(xiàn)一個(gè)綜合的應(yīng)用程序。內(nèi)容如下： （1）首先對(duì)位示圖算法原理進(jìn)行深刻的理解和掌握； （2）程序首先要給出位示圖初態(tài)。分配時(shí),參數(shù)為文件名及需要分配的塊 數(shù)?；厥諘r(shí)，參數(shù)為文件名。 （3)回答信息：分配時(shí)，能夠分配時(shí)，給出文件名和分配的具體塊號(hào)。 否則

2、,給出無(wú)法分配的信息。顯示位示圖。 （4）回收時(shí)：給出回收的具體塊號(hào)。顯示位示圖。 基本要求 （1）理解文件存儲(chǔ)空間的分配與回收的基本概念，掌握產(chǎn)生文件存儲(chǔ)空間的分配與回收的幾種方法，體會(huì)位示圖算法是管理文件存儲(chǔ)空間的分配與回收的一種行之有效的方法。（2）通過(guò)編寫(xiě)程序?qū)崿F(xiàn)位示圖算法，進(jìn)一步理解位示圖算法的原理和執(zhí)行過(guò)程，掌握位示圖算法的描述和應(yīng)用，進(jìn)一步熟練掌握文件存儲(chǔ)空間的分配與回收的方法。測(cè)試要求 對(duì)每一個(gè)模塊的功能進(jìn)行黑盒測(cè)試，保證各個(gè)模塊功能的正確性。指導(dǎo)教師： 時(shí) 間： 年 月 5 日目錄第一章 功能需求描述11.1功能列表與說(shuō)明11.2 操作界面11.3 界面操作1第二章 系統(tǒng)設(shè)計(jì)

3、描述22.1 任務(wù)分解說(shuō)明22.2主要數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)說(shuō)明22.3主要函數(shù)接口說(shuō)明2第三章算法設(shè)計(jì)描述53.1主要函數(shù)和函數(shù)的流程圖53.1.1. 盤(pán)塊的分配算法流程圖53.2.2.盤(pán)塊的回收算法流程圖6第四章 開(kāi)發(fā)過(guò)程描述74.1 程序源碼74.2 程序中遇到的錯(cuò)誤及錯(cuò)誤原因74.3測(cè)試程序功能所用的數(shù)據(jù)和測(cè)試方法7第五章 設(shè)計(jì)心得體會(huì)8附錄1 程序源代碼9第一章 功能需求描述1.1功能列表與說(shuō)明功能名稱功能描述分配文件文件分配回收文件回收文件退出退出程序1.2 操作界面文件的存取和回收1.分配文件2.回收文件3.退出請(qǐng)輸入選項(xiàng)：1.3 界面操作如圖可以很清楚的看到可以輸入1 2 3 三個(gè)數(shù)分別

4、對(duì)應(yīng) 分配文件、回收文件、退出三種操作。第二章 系統(tǒng)設(shè)計(jì)描述2.1 任務(wù)分解說(shuō)明1. 位示圖法系統(tǒng)初始化。2 .位示圖法分配與回收算法。2.2主要數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)說(shuō)明1.空閑區(qū)結(jié)構(gòu)體定義 typedef struct nodeint start_location; /空閑區(qū)對(duì)象變量的開(kāi)始位置int free_number; /空閑區(qū)塊數(shù)目struct node*next; /指向下一個(gè)空閑區(qū)的指針free_link; 2. 申請(qǐng)空間作業(yè)結(jié)構(gòu)體定義typedef struct linkchar office20;/作業(yè)名int begin_location;/作業(yè)申請(qǐng)空間后的開(kāi)始位置int offi

5、ce_number;/作業(yè)申請(qǐng)空間區(qū)的數(shù)目struct link *next;/指向下一個(gè)申請(qǐng)空閑區(qū)的作業(yè)指針office;3. 相關(guān)位示圖操作的結(jié)構(gòu)體定義typedef struct free_link *p;/空間區(qū)鏈表指針office *q;/作業(yè)鏈表指針work;2.3主要函數(shù)接口說(shuō)明1.顯示菜單函數(shù) void menu() 2. 置空位示圖進(jìn)行初始化 void zero_wst() int i; for(i=0;iflag;switch(flag)case 1:w=request(w,WST);break;case 2:w=delect(w,WST);break;case 3:exi

6、t(0);default:printf(輸入錯(cuò)誤,請(qǐng)重新輸入!n);break;第三章算法設(shè)計(jì)描述3.1主要函數(shù)和函數(shù)的流程圖3.1.1. 盤(pán)塊的分配算法流程圖Request()分配輸入文件名,和塊數(shù).strcmp(s-office,u-office)=0該文件是否已存在否r-free_number=s-office_number能否查找到一個(gè)足夠的空閑區(qū)域是否將該作業(yè)結(jié)點(diǎn)插入作業(yè)鏈表表尾,從該區(qū)域分配出對(duì)應(yīng)大小空間,修改位示圖是當(dāng)前空盤(pán)區(qū)塊數(shù)是否分配完否是釋放該空閑區(qū)結(jié)點(diǎn),把修改work里面兩個(gè)首地址返回圖3-1 盤(pán)塊的分配3.2.2.盤(pán)塊的回收算法流程圖Delect()回收輸入要查找的文件

7、名,查找能否找到對(duì)應(yīng)文件要回收的單元前為空是是把該單元塊數(shù)加入前一個(gè)空閑區(qū)結(jié)點(diǎn) 否要回收的單元后為空是否把空閑區(qū)起始地址該為當(dāng)前開(kāi)始盤(pán)塊空閑區(qū)盤(pán)塊增加要回收的單元前后都空結(jié)點(diǎn)空盤(pán)起始地址改為前一個(gè),空閑區(qū)盤(pán)塊增加要回收的單元自成空盤(pán)區(qū)結(jié)點(diǎn)否把該結(jié)點(diǎn)插入空閑區(qū)鏈表是修改位示圖對(duì)應(yīng)盤(pán)塊的的內(nèi)容,刪除該文件結(jié)點(diǎn). 修改work里面兩個(gè)首地址返回圖3-2 盤(pán)塊的回收算法流程圖第四章 開(kāi)發(fā)過(guò)程描述4.1 程序源碼由于源碼較長(zhǎng)，單獨(dú)附加在后面，見(jiàn)附錄1-程序源碼4.2 程序中遇到的錯(cuò)誤及錯(cuò)誤原因編程中幾乎沒(méi)有遇到什么大的問(wèn)題，只有一些語(yǔ)法中的小錯(cuò)誤，編譯器就解決完畢。4.3測(cè)試程序功能所用的數(shù)據(jù)和測(cè)試方法

8、此次測(cè)試使用黑盒測(cè)試方法，目的是測(cè)試功能是否跟預(yù)期一樣測(cè)試用例預(yù)期輸出實(shí)際輸出輸入1選擇分配功能輸出請(qǐng)輸入文件名和塊數(shù)輸出請(qǐng)輸入文件名和塊數(shù)輸入文件名和塊數(shù)顯示已有文件名：塊數(shù)顯示已有文件名：塊數(shù)輸入2選擇回收輸出請(qǐng)輸入文件名輸出請(qǐng)輸入文件名第五章 設(shè)計(jì)心得體會(huì)1.準(zhǔn)備越充分，實(shí)驗(yàn)越順利。古人云，磨刀不誤砍柴工。前期的知識(shí)儲(chǔ)備、文獻(xiàn)儲(chǔ)備、材料準(zhǔn)備、方法準(zhǔn)備可以避免手忙腳亂，充分的預(yù)實(shí)驗(yàn)使你充滿信心。一步一個(gè)腳印，就不必“從頭再來(lái)”。最不能容忍的是在開(kāi)始的幾步偷懶，造成后面總有一些無(wú)法排除的障礙。2.交流是最好的老師做實(shí)驗(yàn)遇到困難是家常便飯。你的第一反應(yīng)是什么？反復(fù)嘗試？放棄？看書(shū)？這些做法都有

9、道理，但首先應(yīng)該想到的是交流。對(duì)有身份的人，私下的請(qǐng)教體現(xiàn)你對(duì)他的尊重；對(duì)同年資的人，公開(kāi)的討論可以使大家暢所欲言，而且出言謹(jǐn)慎。千萬(wàn)不能閉門(mén)造車(chē)。一個(gè)實(shí)驗(yàn)折騰半年，后來(lái)別人告訴你那是死路，豈不冤大頭？3.一半時(shí)間做實(shí)驗(yàn)，一半時(shí)間看文獻(xiàn)。千萬(wàn)不能把時(shí)間全部消耗在實(shí)驗(yàn)臺(tái)上?？次墨I(xiàn)、看書(shū)、看別人的操作、聽(tīng)別人的經(jīng)驗(yàn)、研究別人的思路，邊做邊思考。要學(xué)會(huì)比較，不要盲從。否則，會(huì)被一些小小的問(wèn)題困擾許久。附錄1 程序源代碼#includestdio.h#includemalloc.h#includewindows.h#includestring.h/#includeiostream.h#include

10、using namespace std;int WST256;/*空閑區(qū)結(jié)構(gòu)體定義start_location 空閑區(qū)對(duì)象變量的開(kāi)始位置free_number 空閑區(qū)塊數(shù)目next 指向下一個(gè)空閑區(qū)的指針*/typedef struct nodeint start_location;int free_number;struct node*next;free_link;/*申請(qǐng)空間作業(yè)結(jié)構(gòu)體定義office 作業(yè)名begin_location 作業(yè)申請(qǐng)空間后的開(kāi)始位置office_number 作業(yè)申請(qǐng)空間區(qū)的數(shù)目next 指向下一個(gè)申請(qǐng)空閑區(qū)的作業(yè)指針*/typedef struct link

11、char office20;int begin_location;int office_number;struct link *next;office;/*相關(guān)位示圖操作的結(jié)構(gòu)體定義p 空間區(qū)鏈表指針q 作業(yè)鏈表指針*/typedef struct free_link *p;office *q;work;/*程序菜單*/void menu()printf( 文件的存取和回收n);printf( 1-分配文件n);printf( 2-回收文件n);printf( 3-退出nt);printf( 請(qǐng)輸入選項(xiàng): );/*置空位示圖進(jìn)行初始化*/void zero_wst()int i;for(i=0

12、;i256;i+)WSTi=0;/*位示圖輸出顯示將初始化或者申請(qǐng)或者回收后的位示圖進(jìn)行顯示*/void print_wst(int WST256)int i,j=0;printf(%3s,);for(i=0;i16;i+)printf(%3d,i);printf(n);printf(%3d,0);for(i=0;iq;q=q-next;if(q!=NULL)printf(已有文件:n);while(q!=NULL)printf(t%s:%d-%dn,q-office,q-begin_location,q-begin_location+q-office_number-1);q=q-next;/

13、*位示圖操作的初始化包括:空閑區(qū)鏈表的初始化作業(yè)鏈表的初始化*/work *start()free_link *p;office *q;work *w;w=(work *)malloc(sizeof(work);p=(free_link*)malloc(sizeof(free_link);p-start_location=0;p-free_number=256;p-next=NULL;q=(office *)malloc(sizeof(office);q-next=NULL;w-p=p;w-q=q;return w;/*申請(qǐng)空間操作*/work *request(work *w,int WST

14、256)int i,m,n,flag=0;free_link *p,*r,*e;/r-free_number 用于查找空閑區(qū)的塊數(shù)office *q,*s,*t,*u;/s 創(chuàng)建新節(jié)點(diǎn),存儲(chǔ)新建文件的信息,n用于查找是否有重復(fù)節(jié)點(diǎn)p=w-p;r=p;q=w-q;t=q;u=q-next;printf(請(qǐng)輸入文件名和塊數(shù):);s=(office*)malloc(sizeof(office);s-next=NULL;while(t-next!=NULL)t=t-next;scanf(%s%d,&(s-office),&(s-office_number);while(u!=NULL)if(strcm

15、p(s-office,u-office)=0)flag=1;printf(對(duì)不起,該文件已存在!n);free(s);break;u=u-next;if(flag=0)while(r!=NULL)if(r-free_number)=(s-office_number)/用于查找空閑區(qū)中空閑塊數(shù)是否大于欲分配的塊數(shù)break;r=r-next;if(r=NULL)printf(對(duì)不起,沒(méi)有足夠的空間分配失敗!n);free(s);elset-next=s;m=r-start_location;/空閑區(qū)的起始地址s-begin_location=r-start_location;/作業(yè)從空閑區(qū)的起始

16、地址開(kāi)始分配r-start_location=r-start_location+s-office_number;/改變空閑區(qū)空閑塊數(shù)的起始地址r-free_number=r-free_number-s-office_number;/改變空間區(qū)塊數(shù)的大小n=(r-start_location-1);/新的空間區(qū)的起始地址-1for(i=m;ifree_number=0)if(p=r)/p=r說(shuō)明內(nèi)存中只有一個(gè)整塊的空閑區(qū)free(r);p=NULL;elsee=p;while(e!=NULL)if(e-next=r)break;e=e-next;e-next=r-next;free(r);w-p

17、=p;w-q=q;return w;/*回收空間操作*/work *delect(work *w,int WET)char name20;int i;free_link *p,*r,*t;office *q,*s,*e;p=w-p;r=p;t=p;q=w-q;s=q;e=q;s=s-next;if(s=NULL)printf(沒(méi)有可以回收的文件!n);else printf(請(qǐng)輸入文件名:);cinname;while(s!=NULL)if(strcmp(s-office,name)=0)break;s=s-next;if(s=NULL)coutbegin_location-1=0&WSTs-

18、begin_location+s-office_number=1&s-begin_location-1=0)|(WSTs-begin_location-1=0&s-begin_location+s-office_number=256&s-begin_location-1=0)while(r!=NULL)if(r-start_location+r-free_number)=s-begin_location)break;r=r-next;r-free_number=r-free_number+s-office_number;if(WSTs-begin_location-1=1&WSTs-begin

19、_location+s-office_number=0&s-begin_location+s-office_numberbegin_location=0&WSTs-begin_location+s-office_number=0&s-begin_location+s-office_numberbegin_location+s-office_number)=r-start_location)break;r=r-next;r-start_location=r-start_location-s-office_number;r-free_number=r-free_number+s-office_nu

20、mber;if(WSTs-begin_location-1=0&WSTs-begin_location+s-office_number=0&s-begin_location-1=0&s-begin_location+s-office_numberbegin_location+s-office_number)=r-start_location)t=r;break;r=r-next;r-free_number=r-free_number+s-office_number+t-free_number;free(t);if(WSTs-begin_location-1=1&WSTs-begin_locat

21、ion+s-office_number=1&s-begin_location-1=0&s-begin_location+s-office_numberbegin_location=0&WSTs-begin_location+s-office_number=1& s-begin_location+s-office_numberbegin_location-1=1&s-begin_location+s-office_number=256&s-begin_location-1=0)|(s-begin_location=0&s-begin_location+s-office_number=256)t=(free_link*)malloc(sizeof(free_link);t-next=NULL;t-start_location=s-begin_location;t-free_number=s-office_number;if(r=NULL)p=t;if(r!=N