空閑磁盤存儲(chǔ)空間的管理_OS課程設(shè)計(jì)

1、OS 課程設(shè)計(jì)空閑磁盤存儲(chǔ)空間的管理1、 、 課程設(shè)計(jì)任務(wù)、要求、目的我們組選的題目是第17 題：空閑磁盤存儲(chǔ)空間的管理：簡(jiǎn)單方法。具體要求如下：建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)；磁盤上建立一個(gè)文件，文件長(zhǎng)度設(shè)為10MB ，用該文件來(lái)模擬一個(gè)磁盤，磁盤的物理塊大小為 512 字節(jié)。建立進(jìn)程的數(shù)據(jù)結(jié)構(gòu)；時(shí)間的流逝可以用下面幾種方法模擬：(a) 按鍵盤，每按一次可認(rèn)為過(guò)一個(gè)時(shí)間單位；(b) 響應(yīng) WM_TIMER ；將一批進(jìn)程對(duì)磁盤的請(qǐng)求的情況存磁盤文件，以后可以讀出并重放；使用兩種方式產(chǎn)生進(jìn)程對(duì)磁盤的請(qǐng)求：(a) 自動(dòng)產(chǎn)生(b) 手工輸入顯示每次磁盤的請(qǐng)求和空間釋放后的相關(guān)數(shù)據(jù)結(jié)構(gòu)的狀態(tài)；顯示每次磁盤的請(qǐng)求和

2、空間釋放后狀態(tài)；支持的管理方法：空閑表法、空閑鏈表法、位示圖法、UNIX 成組鏈接法。該課程設(shè)計(jì)的目的：磁盤初始化時(shí)把磁盤存儲(chǔ)空間分成許多塊(扇區(qū))，這些空間可以被多個(gè)用戶共享。用戶作業(yè)在執(zhí)行期間常常要在磁盤上建立文件或把已經(jīng)建立在磁盤上的文件刪去，這就涉及到磁盤存儲(chǔ)空間的分配和回收。一個(gè)文件存放到磁盤上，可以組織成順序文件(連續(xù)文件)、鏈接文件(串聯(lián)文件)、索引文件等，因此，磁盤存儲(chǔ)空間的分配有兩種方式，一種是分配連續(xù)的存儲(chǔ)空間，另一種是可以分配不連續(xù)的存儲(chǔ)空間。怎樣有效地管理磁盤存儲(chǔ)空間是操作系統(tǒng)應(yīng)解決的一個(gè)重要問(wèn)題，通過(guò)這個(gè)課程設(shè)計(jì)可以使我們更好地熟悉掌握磁盤存儲(chǔ)管理 的原理和分配與回收

3、算法，進(jìn)一步掌握軟件開發(fā)方法并提高解決實(shí)際問(wèn)題的能力。2、 原理與算法描述我們組將題目中所給的方法分為連續(xù)存儲(chǔ)空間法和鏈接存儲(chǔ)空間法，并選取其中最具代表性的位示圖法和UNIX 成組鏈接法（連續(xù)存儲(chǔ)與鏈接存儲(chǔ)的結(jié)合）來(lái)進(jìn)行代碼的編寫。位示圖法原理：位示圖用來(lái)指出磁盤塊的使用情況，位示圖中各個(gè)元素的取值只有“0”和“ 1 ”兩種，其中“ 1狀態(tài)表示相應(yīng)的磁盤塊已經(jīng)被占用，“0”狀態(tài)表示該磁盤塊空閑。申請(qǐng)磁盤塊時(shí)，分配函數(shù)查詢第一個(gè)空閑塊所屬的位置，然后從該位置往后選取對(duì)應(yīng)數(shù)目的空閑塊進(jìn)行分配，將相應(yīng)位置的位示圖上相應(yīng)元素置為“1 ?！?為了編程方便，我們查閱資料，假設(shè)一個(gè)磁盤有8 個(gè)柱面，每個(gè)柱面

4、有2 個(gè)磁道，每個(gè)磁道有4 個(gè)物理記錄。釋放磁盤塊時(shí)與分配磁盤塊是相反的操作， 由釋放函數(shù)找到第一個(gè)空閑磁盤塊，并從該位置往前一單位將被占用的相應(yīng)數(shù)目的磁盤塊釋放，將位示圖上相應(yīng)元素置為“0”。成組鏈接法原理：成組鏈接法常應(yīng)用于UNIX 系統(tǒng)中，其主要思想是將結(jié)合順序表和鏈表進(jìn)行擇優(yōu)組合，即定義組內(nèi)為順序表，最大值為MAXGROUP ，大于 MAXGROUP 的磁盤塊另行分組，構(gòu)成新的順序表；但是這些順序表之間用鏈表的結(jié)構(gòu)進(jìn)行連接，相當(dāng)于添加一個(gè)新的節(jié)點(diǎn)。3、 開發(fā)環(huán)境由于我們只是簡(jiǎn)單的對(duì)磁盤處理進(jìn)行模擬，所以就在自己的個(gè)人PC 上進(jìn)行，用的IDE是 DEV C+ （ Eclipse 上 JA

5、VA 寫的界面被老師打回來(lái)了。 。 ） 。4、 重要算法和設(shè)計(jì)思路描述設(shè)計(jì)思路：對(duì)于位示圖法，我們就是定義一個(gè)矩陣用來(lái)可視化磁盤空間的使用情況，出于對(duì)控制臺(tái)界面的考慮，我們將條件簡(jiǎn)化為：假設(shè)一個(gè)磁盤有3 個(gè)柱面，每個(gè)柱面有2 個(gè)磁道，每個(gè)磁道有 4 個(gè)物理記錄，將矩陣簡(jiǎn)化為8*3 的規(guī)模。 然后分別建立process 順序表數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)申請(qǐng)的物理塊信息；bitmap 位示圖類來(lái)存儲(chǔ)位示圖的數(shù)據(jù)和相應(yīng)的操作，這些操作包括位示圖二維數(shù)組bitmapMN 來(lái)存儲(chǔ)位示圖信息，Initbitmap() 初始化位示圖，spaceisok()判斷位示圖是否合理，displaybitmap() 用來(lái)打印位示

6、圖信息。對(duì)于成組鏈接法，我們定義組結(jié)構(gòu)體group 和進(jìn)程結(jié)構(gòu)體process ，定義順序表最大值MAXGROUP 為 20，大于 MAXGROUP 的磁盤塊另行分組，構(gòu)成新的順序表；但是這些順序表之間用鏈表的結(jié)構(gòu)進(jìn)行連接，相當(dāng)于添加一個(gè)新的group 節(jié)點(diǎn)。 用 distribute() 函數(shù)分配內(nèi)存塊，用recycle。函數(shù)撤消進(jìn)程，回收內(nèi)存塊。用view()函數(shù)顯示一些進(jìn)程和數(shù)據(jù)結(jié)構(gòu)的相應(yīng)信息。5、 程序?qū)崿F(xiàn)數(shù)據(jù)結(jié)構(gòu)我們組選的題目是第17 題：空閑磁盤存儲(chǔ)空間的管理：簡(jiǎn)單方法6、 程序?qū)崿F(xiàn)程序清單位示圖法：#include <iostream>#include <cst

7、ring>#include <conio.h>using namespace std;const int cylinder=3,track=2,sector=4;/ 柱面、磁道、物理塊號(hào)#define SIZE 100/ 最大塊數(shù)const int M=cylinder,N=track*sector;struct process/process 順序表數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)申請(qǐng)的物理塊信息char name20;int cSIZE,tSIZE,sSIZE;int n;process processtableSIZE;/process 格式表int ppointer=-1;/proce

8、ss 指針class bitmap/ 位示圖 結(jié)構(gòu)體public:int bitmapMN;void Initbitmap();/ 初始化位示圖bool spaceisok(int n);/ 位示圖符合判斷void displaybitmap();/ 打印;bitmap bm;/ 全局位示圖，為所有進(jìn)程共享void bitmap:Initbitmap()int i,j;cout<<"*n"cout<<" 位示圖初始化n"cout<<"Q*n"for(i=0;i<M;i+)for(j=0;j&l

9、t;N;j+)bitmapij=0;/ getchar();displaybitmap();/ 初始化后位示圖getchar();/system("cls");bool bitmap:spaceisok(int n)/ 判斷位示圖空閑物理塊是否足夠int count=0;for(int i=0;i<M;i+)for(int j=0;j<N;j+)if(bitmapij=0)count+;if(count<n)return false;elsereturn true;void bitmap:displaybitmap()/ 打印位示圖int i,j;cout

10、<<"n 當(dāng)前位示圖信息如下：n"cout<<"n*n"for(i=0;i<M;i+)for(j=0;j<N;j+)cout<<"t"<<bitmapij;cout<<endl;cout<<"n*n"if(ppointer<0)cout<<"n 尚未分配磁盤空間n"return;elsecout<<"n 當(dāng)前分配信息如下：n"cout<<"n

11、#"cout<<"n 進(jìn)程名 tt 分配的物理塊數(shù)n"/cout<<"n 進(jìn)程名 tt 分配的物理塊數(shù)tt 物理塊信息n"for(int i=0;i<=ppointer;i+) if(processtablei.n=0)continue;else(cout«"n"««"tt "«processtablei.n;/*for(j=0;j<processtablei.n;j+)(if(j=O)(cou

12、t«"ttt("«processtablei.cj«","«processtablei.tj«","«processtablei.sj «")n")else(cout«"ttttt("«processtablei.cj«","«processtablei.tj«","«processtablei. sj«")

13、n") */cout<<"n#n"void distribute(char name20,int n)/ 分配int i,j;int count=0;/* 計(jì)數(shù)器 */for(i=0;i<=ppointer;i+)/processtable 中逐個(gè)搜索指定進(jìn)程if(!strcmp(,name)cout<<"n 進(jìn)程名重復(fù)，請(qǐng)檢查后命名。n"goto end;if(!bm.spaceisok(n)cout<<" 空間不足，找不到"<<n&

14、lt;<" 塊物理塊，分配失敗!"return;ppointer+;strcpy(,name);/ 分配的物理塊賦予名字processtableppointer.n=n;/ 物理塊數(shù)for(i=0;i<M;i+)/ 二維數(shù)組逐個(gè)搜索空閑物理塊for(j=0;j<N;j+)if(bm.bitmapij=0)processtableppointer.ccount=i;/* 柱面號(hào) */processtableppointer.tcount=j/4;/* 磁道號(hào) */ processtableppointer.s

15、count=j%4;/* 物理記錄號(hào)*/bm.bitmapij=1;/cout<<666666<<endl;count+;if(count=n)return;end:return;void recycle(char name20)/ 回收內(nèi)存int i,j,flag=0;for(i=0;i<=ppointer;i+)/processtable 中逐個(gè)搜索指定進(jìn)程if(!strcmp(,name)for(j=0;j<processtablei.n;j+)bm.bitmapprocesstablei.cj4*processta

16、blei.tj+processtablei.sj=0;/位示圖 相應(yīng)置零for(int k=i;k<=ppointer-i;k+)/process 表項(xiàng)移動(dòng)strcpy(,processtablek+1.name);/ 刪除，前移processtablek.n=processtablek+1.n;for(int l=0;l<processtablek.n;l+)processtablek.cl=processtablek+1.cl;processtablek.tl=processtablek+1.tl;processtablek.sl=proce

17、sstablek+1.sl;ppointer-;flag=1;/delay();cout<<"n 找到進(jìn)程，回收完畢。n"if(flag=0)cout<<"n 未找到進(jìn)程名為"<<name<<" 的進(jìn)程！ ！可能尚未此進(jìn)程分配物理塊n"int main()int choice,n;char name20;bm.Initbitmap();while(1)getch();/ system("cls");cout<<"n 請(qǐng)輸入選擇:"cou

18、t<<"1- 分配， 2-回收，3-顯示位示圖，0-退出n"cin>>choice;switch(choice)case 1:cout<<" 請(qǐng)輸入進(jìn)程名和需要分配的物理塊數(shù)：cin>>name>>n;distribute(name,n);break;case 2:cout<<" 給出要回收的進(jìn)程名："cin>>name;recycle(name);break;case 3:bm.displaybitmap();break;case 0:exit(0);defa

19、ult:cout<<" 選擇錯(cuò)誤！"break;return 0;位示圖結(jié)果截圖如下：成組鏈接法:#include <iostream>#include <cstring>#include <conio.h>#include <time.h>using namespace std;const int MAXGROUP=20;/ 定義組的大小為20const int MAXPROCESS=100;/ 定義一個(gè)進(jìn)程最大能申請(qǐng)的塊數(shù)/組結(jié)構(gòu)體typedef struct nodeint num_gp;/ 組中元素計(jì)數(shù)in

20、t cellMAXGROUP; / 組中元素存放的數(shù)組struct node *next;/ 指向鏈表下一節(jié)點(diǎn)的指針group;group *g_GroupHead;/ 全局組鏈表頭，為所有進(jìn)程共享/進(jìn)程結(jié)構(gòu)體typedef struct node1char name20;/ 進(jìn)程名int num_ps;/ 進(jìn)程個(gè)數(shù)int cellMAXPROCESS;/ 進(jìn)程號(hào)數(shù)組struct node1 *next;process;process *g_processHead;/ 定義進(jìn)程鏈表頭，為全局變量int idletotal;/ 當(dāng)前剩余總空閑塊數(shù)/初始化組函數(shù)group *initial_gro

21、up()int i;cout<<"n*n"cout<<"組初始化n"group *p;p= new group;p->num_gp=0;p->next=NULL;for(i=0;i<MAXGROUP;i+)p->celli=-1;/cout<<"*n"return p;/初始化進(jìn)程函數(shù) process *initial_process() int i;cout<<"*n"cout<<"進(jìn)程初始化n"cout<

22、;<"*n"process *p;p=new process;strcpy(p->name,"");p->num_ps=0;p->next=NULL;for(i=0;i<MAXGROUP;i+)p->celli=-1;return p;/讀入空閑塊文件并組織成成組鏈表void readData()FILE *fp;char fname20 = "Test.txt"int temp;group *p;while( (fp=fopen(fname,"r") = NULL )/打開默認(rèn)

23、的文件TestUnix.txt/fp=fopen("TestUnix.txt","r");if (NULL = fp)cout<<" 錯(cuò)誤 ,文件 "<< fname << " 打不開 "<<endl;/打開成功后就不要輸入文件名了直接返回elsebreak;/如果默認(rèn)的文件打不開，手動(dòng)輸入文件名打開cout<<" 請(qǐng)輸入初始空閑塊數(shù)據(jù)文件名:"cin>>fname;cout<<"*"<

24、<endl;cout<<" 從文件 " << fname << " 讀入的初始空閑塊號(hào)為:" while(!feof(fp) fscanf(fp,"%d ",&temp);if(g_GroupHead->num_gp<MAXGROUP)g_GroupHead->cellg_GroupHead->num_gp=temp;g_GroupHead->num_gp+;else所存儲(chǔ)的空閑塊號(hào)大于MAXGROUP時(shí)需要另申請(qǐng)節(jié)點(diǎn)p=initial_group();/

25、*p->head->a>b->c->*/p->next=g_GroupHead; / 將申請(qǐng)的p 節(jié)點(diǎn)插入到鏈?zhǔn)譯_GroupHead=p;p->cellp->num_gp=temp;p->num_gp+;if (0 = idletotal+%20 )/ 一組 20 一行cout << endl;/輸出初始數(shù)據(jù)printf("%04d ",temp);/cout<<temp<<" "cout<<endl<<" 當(dāng)前總空閑塊數(shù):&qu

26、ot;<<idletotal<<endl;void init()/初始化組鏈表 g_GroupHead=initial_group();/初始化計(jì)數(shù)器 idletotal=0;/初始化作業(yè)鏈表 g_processHead=initial_process();/從文件讀取數(shù)據(jù) readData();/分配內(nèi)存塊 void distribute()char processname20;int number;int i;process *p;cout<<"*"<<endl;cout<<" 請(qǐng)輸入新進(jìn)程名cin&

27、gt;>processname;cout<<" 所需內(nèi)存塊數(shù): cin>>number;if(number > idletotal)cout<<" 所需內(nèi)存塊數(shù)大于當(dāng)前空閑塊數(shù),分配失敗!"<<endl;elsep=initial_process(); strcpy(p->name,processname);/* 將節(jié)點(diǎn) p 插入鏈表*/p->next=g_processHead->next;g_processHead->next=p;p->num_ps=number;cou

28、t<<" 申請(qǐng)成功，所申請(qǐng)到的空閑塊號(hào)依次為:"for(i=0;i<number;i+)if(g_GroupHead->num_gp > 1)cout<<g_GroupHead->cellg_GroupHead->num_gp-1<<" " g_GroupHead->num_gp-;p->celli=g_GroupHead->cellg_GroupHead->num_gp-1;elsecout<<g_GroupHead->cell0<<

29、" "p->celli=g_GroupHead->cellg_GroupHead->num_gp-1;g_GroupHead->num_gp-;if(g_GroupHead->next!=NULL)g_GroupHead=g_GroupHead->next;idletotal-;cout<<endl;/撤消進(jìn)程，回收內(nèi)存塊void recycle()char processname20;int i;process *p,*q;group *r;cout<<" 請(qǐng)輸入要撤消的進(jìn)程名:"cin>

30、;>processname;q=g_processHead;p=g_processHead->next;while(p!=NULL)&&(strcmp(p->name,processname) / 遍歷，尋找指定進(jìn)程q=q->next;p=p->next;if(p=NULL) cout<<"Sorry, 沒有該進(jìn)程"<<endl;elsefor(i=0;i<p->num_ps;i+)/ 釋放物理塊到相應(yīng)的組鏈表if(g_GroupHead->num_gp<MAXGROUP)g_Gr

31、oupHead->cellg_GroupHead->num_gp=p->celli;g_GroupHead->num_gp+;else / 新建組r=initial_group();r->next=g_GroupHead;g_GroupHead=r;r->cellr->num_gp=p->celli;r->num_gp+;idletotal+=p->num_ps; /p 進(jìn)程多個(gè)物理塊q->next=p->next;/ 進(jìn)程鏈表中刪除指定進(jìn)程節(jié)點(diǎn)delete p;void view()cout<<"*"<<endl;cout<<endl<<" 總空閑塊數(shù):&q