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

模擬實(shí)現(xiàn)用位示圖法管理文件存儲(chǔ)空間的分配與回收1模擬實(shí)現(xiàn)用位示圖法管理文件存儲(chǔ)空間的分配與回收1模擬實(shí)現(xiàn)用位示圖法管理文件存儲(chǔ)空間的分配與回收1xxx公司模擬實(shí)現(xiàn)用位示圖法管理文件存儲(chǔ)空間的分配與回收1文件編號(hào)：文件日期：修訂次數(shù)：第1.0次更改批準(zhǔn)審核制定方案設(shè)計(jì)，管理制度計(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è)計(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)容[問題描述]設(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)。否則,給出無法分配的信息。顯示位示圖。（4）回收時(shí)：給出回收的具體塊號(hào)。顯示位示圖。[基本要求]（1）理解文件存儲(chǔ)空間的分配與回收的基本概念，掌握產(chǎn)生文件存儲(chǔ)空間的分配與回收的幾種方法，體會(huì)位示圖算法是管理文件存儲(chǔ)空間的分配與回收的一種行之有效的方法。（2）通過編寫程序?qū)崿F(xiàn)位示圖算法，進(jìn)一步理解位示圖算法的原理和執(zhí)行過程，掌握位示圖算法的描述和應(yīng)用，進(jìn)一步熟練掌握文件存儲(chǔ)空間的分配與回收的方法。[測(cè)試要求]對(duì)每一個(gè)模塊的功能進(jìn)行黑盒測(cè)試，保證各個(gè)模塊功能的正確性。指導(dǎo)教師：時(shí)間：年月5日目錄TOC\o"1-3"\h\u第一章功能需求描述 1功能列表與說明 1操作界面 1界面操作 1第二章系統(tǒng)設(shè)計(jì)描述 2任務(wù)分解說明 2主要數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)說明 2主要函數(shù)接口說明 2第三章算法設(shè)計(jì)描述 5主要函數(shù)和函數(shù)的流程圖 5盤塊的分配算法流程圖 5盤塊的回收算法流程圖 6第四章開發(fā)過程描述 7程序源碼 7程序中遇到的錯(cuò)誤及錯(cuò)誤原因 7測(cè)試程序功能所用的數(shù)據(jù)和測(cè)試方法 7第五章設(shè)計(jì)心得體會(huì) 8附錄1程序源代碼 9第一章功能需求描述功能列表與說明功能名稱功能描述分配文件文件分配回收文件回收文件退出退出程序操作界面文件的存取和回收1.分配文件2.回收文件3.退出請(qǐng)輸入選項(xiàng)：界面操作如圖可以很清楚的看到可以輸入123三個(gè)數(shù)分別對(duì)應(yīng)分配文件、回收文件、退出三種操作。

第二章系統(tǒng)設(shè)計(jì)描述任務(wù)分解說明1.位示圖法系統(tǒng)初始化。2.位示圖法分配與回收算法。主要數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)說明 1.空閑區(qū)結(jié)構(gòu)體定義typedefstructnode{ intstart_location;申請(qǐng)空間作業(yè)結(jié)構(gòu)體定義typedefstructlink{ charoffice[20]; 相關(guān)位示圖操作的結(jié)構(gòu)體定義 typedefstruct{ free_link*p; 示菜單函數(shù) voidmenu(){}2.置空位示圖進(jìn)行初始化 voidzero_wst(){ inti; for(i=0;i<256;i++) WST[i]=0;}3.位示圖輸出顯示將初始化或者申請(qǐng)或者回收后的位示圖進(jìn)行顯示voidprint_wst(intWST[256]){}4.已經(jīng)申請(qǐng)空間的作業(yè)相關(guān)情況輸出顯示包括:作業(yè)名、申請(qǐng)空間的開始位置和截至位置 voidprint_office(work*w){}5.位示圖操作的初始化包括:空閑區(qū)鏈表的初始化、作業(yè)鏈表的初始化 work*start(){}6.申請(qǐng)空間操作 work*request(work*w,intWST[256]){}7.回收空間操作work*delect(work*w,intWET[]){}8.主函數(shù)voidmain(){ intflag; work*w; zero_wst(); w=start(); while(1){ system("cls"); print_wst(WST); print_office(w); menu(); cin>>flag; switch(flag){ case1:w=request(w,WST);break; case2:w=delect(w,WST);break; case3:exit(0); default:printf("輸入錯(cuò)誤,請(qǐng)重新輸入!\n");break; } }}

第三章算法設(shè)計(jì)描述主要函數(shù)和函數(shù)的流程圖盤塊的分配算法流程圖RRequest()分配輸入文件名,輸入文件名,和塊數(shù).strcmp(s->office,u->office)==0strcmp(s->office,u->office)==0該文件是否已存在否r->free_number>=s->office_number能否查找到一個(gè)足r->free_number>=s->office_number能否查找到一個(gè)足夠的空閑區(qū)域否將該作業(yè)結(jié)點(diǎn)插入作業(yè)鏈表表尾,,將該作業(yè)結(jié)點(diǎn)插入作業(yè)鏈表表尾,,從該區(qū)域分配出對(duì)應(yīng)大小空間,修改位示圖當(dāng)前空盤區(qū)塊數(shù)是否分配完當(dāng)前空盤區(qū)塊數(shù)是否分配完否是釋放該空閑區(qū)結(jié)點(diǎn)釋放該空閑區(qū)結(jié)點(diǎn),把修改work里面兩個(gè)首地址返回返回圖3-1盤塊的分配盤塊的回收算法流程圖DelectDelect()回收輸入要查找的文件名輸入要查找的文件名,查找能否找到對(duì)應(yīng)文件能否找到對(duì)應(yīng)文件要回收的單元前為空是要回收的單元前為空是把該單元塊數(shù)加入前一個(gè)空閑區(qū)結(jié)點(diǎn)否把該單元塊數(shù)加入前一個(gè)空閑區(qū)結(jié)點(diǎn)要回收的單元后為空要回收的單元后為空是否把空閑區(qū)起始地址該為當(dāng)前開始盤塊空閑區(qū)盤塊增加要回收的單元前后都空把空閑區(qū)起始地址該為當(dāng)前開始盤塊空閑區(qū)盤塊增加要回收的單元前后都空結(jié)點(diǎn)空盤起始地址改為前一個(gè),空閑區(qū)盤塊增加結(jié)點(diǎn)空盤起始地址改為前一個(gè),空閑區(qū)盤塊增加要回收的單元自成空盤區(qū)結(jié)點(diǎn)否要回收的單元自成空盤區(qū)結(jié)點(diǎn)把該結(jié)點(diǎn)插入空閑區(qū)鏈表是把該結(jié)點(diǎn)插入空閑區(qū)鏈表修改位示圖對(duì)應(yīng)盤塊的的內(nèi)容修改位示圖對(duì)應(yīng)盤塊的的內(nèi)容,刪除該文件結(jié)點(diǎn).修改work里面兩個(gè)首地址返回返回圖3-2盤塊的回收算法流程圖第四章開發(fā)過程描述程序源碼 由于源碼較長(zhǎng)，單獨(dú)附加在后面，見附錄1-程序源碼程序中遇到的錯(cuò)誤及錯(cuò)誤原因 編程中幾乎沒有遇到什么大的問題，只有一些語法中的小錯(cuò)誤，編譯器就解決完畢。測(cè)試程序功能所用的數(shù)據(jù)和測(cè)試方法 此次測(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è)腳印，就不必“從頭再來”。最不能容忍的是在開始的幾步偷懶，造成后面總有一些無法排除的障礙。2.交流是最好的老師做實(shí)驗(yàn)遇到困難是家常便飯。你的第一反應(yīng)是什么反復(fù)嘗試放棄看書這些做法都有道理，但首先應(yīng)該想到的是交流。對(duì)有身份的人，私下的請(qǐng)教體現(xiàn)你對(duì)他的尊重；對(duì)同年資的人，公開的討論可以使大家暢所欲言，而且出言謹(jǐn)慎。千萬不能閉門造車。一個(gè)實(shí)驗(yàn)折騰半年，后來別人告訴你那是死路，豈不冤大頭3.一半時(shí)間做實(shí)驗(yàn)，一半時(shí)間看文獻(xiàn)。千萬不能把時(shí)間全部消耗在實(shí)驗(yàn)臺(tái)上?？次墨I(xiàn)、看書、看別人的操作、聽別人的經(jīng)驗(yàn)、研究別人的思路，邊做邊思考。要學(xué)會(huì)比較，不要盲從。否則，會(huì)被一些小小的問題困擾許久。附錄1程序源代碼#include""#include""#include""#include""http:///#include""#include<iostream>usingnamespacestd;intWST[256];/*************************************空閑區(qū)結(jié)構(gòu)體定義start_location空閑區(qū)對(duì)象變量的開始位置free_number空閑區(qū)塊數(shù)目next指向下一個(gè)空閑區(qū)的指針**************************************/typedefstructnode{ intstart_location; intfree_number; structnode*next; }free_link;/*************************************申請(qǐng)空間作業(yè)結(jié)構(gòu)體定義office[]作業(yè)名begin_location作業(yè)申請(qǐng)空間后的開始位置office_number作業(yè)申請(qǐng)空間區(qū)的數(shù)目next指向下一個(gè)申請(qǐng)空閑區(qū)的作業(yè)指針**************************************/typedefstructlink{ charoffice[20]; intbegin_location; intoffice_number; structlink*next; }office;/**************************************相關(guān)位示圖操作的結(jié)構(gòu)體定義p空間區(qū)鏈表指針q作業(yè)鏈表指針***************************************/typedefstruct{ free_link*p; office*q;}work;/***************************************程序菜單****************************************/voidmenu(){ printf("文件的存取和回收\(chéng)n"); printf("1--分配文件\n"); printf("2--回收文件\n"); printf("3--退出\n\t"); printf("請(qǐng)輸入選項(xiàng):");}/***************************************置空位示圖進(jìn)行初始化****************************************/voidzero_wst(){ inti; for(i=0;i<256;i++) WST[i]=0;}/****************************************位示圖輸出顯示將初始化或者申請(qǐng)或者回收后的位示圖進(jìn)行顯示*****************************************/voidprint_wst(intWST[256]){ inti,j=0; printf("%3s",""); for(i=0;i<16;i++) printf("%3d",i); printf("\n"); printf("%3d",0); for(i=0;i<256;i++){ j++; printf("%3d",WST[i]); if(j%16==0&&i!=0&&j!=256){ printf("\n"); printf("%3d",j/16); } } printf("\n");}/**************************************已經(jīng)申請(qǐng)空間的作業(yè)相關(guān)情況輸出顯示包括:作業(yè)名申請(qǐng)空間的開始位置和截至位置***************************************/voidprint_office(work*w){ office*q; q=w->q; q=q->next; if(q!=NULL){ printf("已有文件:\n"); while(q!=NULL){printf("\t%s:%d-%d\n",q->office,q->begin_location,q->begin_location+q->office_number-1); q=q->next; } }}/*************************************位示圖操作的初始化包括:空閑區(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; returnw;}/**************************************申請(qǐng)空間操作***************************************/work*request(work*w,intWST[256]){ inti,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(strcmp(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ì)不起,沒有足夠的空間分配失敗!\n"); free(s); } else{ t->next=s; m=r->start_location;//空閑區(qū)的起始地址 s->begin_location=r->start_location;//作業(yè)從空閑區(qū)的起始地址開始分配 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ū)的起始地址-1 for(i=m;i<=n;i++)//模擬分配 WST[i]=1; if(r->free_number==0){ if(p==r){//p==r說明內(nèi)存中只有一個(gè)整塊的空閑區(qū) free(r); p=NULL; } else{ e=p; while(e!=NULL){ if(e->next==r) break; e=e->next; } e->next=r->next; free(r); } } } } w->p=p; w->q=q; returnw;}/*********************************************回收空間操作**********************************************/work*delect(work*w,intWET[]){ charname[20]; inti; 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("請(qǐng)輸入文件名:"); cin>>name; while(s!=NULL){ if(strcmp(s->office,name)==0) break; s=s->next; } if(s==NULL){ cout<<"對(duì)不起沒有找到相關(guān)文件!\n"; } else{ if((WST[s->begin_location-1]==0&&WST[s->begin_location+s->office_number]==1&&s->begin_location-1>=0) ||(WST[s->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((WST[s->begin_location-1]==1&&WST[s->begin_location+s->office_number]==0&&s->begin_location+s->office_number<256)||(s->begin_location==0&& WST[s->begin_location+s->office_number]==0&&s->begin_location+s->office_number<256)){ while(r!=NULL){ if((s->begin_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_number; }if(WST[s->begin_location-1]==0&&WST[s->begin_location+s->office_number]==0&&s->begin_location-1>=0&&s->begin_location+s->office_number<256){ while(r!=NULL){ if((s->begin_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((WST[s->begin_location-1]==1&&WST[s->begin_location+s->office_number]==1&&s->begin_location-1>=0 &&s->begin_location+s->office_number<256)||(s->begin_location==0&&WST[s->begin_location+s->office_number]==1&&s->begin_location+s->office_number<256) ||(WST[s->begin_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->offic