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

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

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

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

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

5、ce_number;/作業(yè)申請空間區(qū)的數(shù)目struct link *next;/指向下一個申請空閑區(qū)的作業(yè)指針office;3. 相關(guān)位示圖操作的結(jié)構(gòu)體定義typedef struct free_link *p;/空間區(qū)鏈表指針office *q;/作業(yè)鏈表指針work;2.3主要函數(shù)接口說明1.顯示菜單函數(shù) void menu() 2. 置空位示圖進行初始化 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(輸入錯誤,請重新輸入!n);break;第三章算法設(shè)計描述3.1主要函數(shù)和函數(shù)的流程圖3.1.1. 盤塊的分配算法流程圖Request()分配輸入文件名,和塊數(shù).strcmp(s-office,u-office)=0該文件是否已存在否r-free_number=s-office_number能否查找到一個足夠的空閑區(qū)域是否將該作業(yè)結(jié)點插入作業(yè)鏈表表尾,從該區(qū)域分配出對應(yīng)大小空間,修改位示圖是當前空盤區(qū)塊數(shù)是否分配完否是釋放該空閑區(qū)結(jié)點,把修改work里面兩個首地址返回圖3-1 盤塊的分配3.2.2.盤塊的回收算法流程圖Delect()回收輸入要查找的文件

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

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

9、道理，但首先應(yīng)該想到的是交流。對有身份的人，私下的請教體現(xiàn)你對他的尊重；對同年資的人，公開的討論可以使大家暢所欲言，而且出言謹慎。千萬不能閉門造車。一個實驗折騰半年，后來別人告訴你那是死路，豈不冤大頭？3.一半時間做實驗，一半時間看文獻。千萬不能把時間全部消耗在實驗臺上?？次墨I、看書、看別人的操作、聽別人的經(jīng)驗、研究別人的思路，邊做邊思考。要學(xué)會比較，不要盲從。否則，會被一些小小的問題困擾許久。附錄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ū)對象變量的開始位置free_number 空閑區(qū)塊數(shù)目next 指向下一個空閑區(qū)的指針*/typedef struct nodeint start_location;int free_number;struct node*next;free_link;/*申請空間作業(yè)結(jié)構(gòu)體定義office 作業(yè)名begin_location 作業(yè)申請空間后的開始位置office_number 作業(yè)申請空間區(qū)的數(shù)目next 指向下一個申請空閑區(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( 請輸入選項: );/*置空位示圖進行初始化*/void zero_wst()int i;for(i=0

12、;i256;i+)WSTi=0;/*位示圖輸出顯示將初始化或者申請或者回收后的位示圖進行顯示*/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;/*申請空間操作*/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é)點,存儲新建文件的信息,n用于查找是否有重復(fù)節(jié)點p=w-p;r=p;q=w-q;t=q;u=q-next;printf(請輸入文件名和塊數(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(對不起,該文件已存在!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(對不起,沒有足夠的空間分配失敗!n);free(s);elset-next=s;m=r-start_location;/空閑區(qū)的起始地址s-begin_location=r-start_location;/作業(yè)從空閑區(qū)的起始

16、地址開始分配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說明內(nèi)存中只有一個整塊的空閑區(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(沒有可以回收的文件!n);else printf(請輸入文件名:);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