空闲磁盘存储空间的管理-OS课程设计(共15页).docx

精选优质文档-倾情为你奉上OS课程设计空闲磁盘存储空间的管理1、 课程设计任务、要求、目的我们组选的题目是第17题：空闲磁盘存储空间的管理：简单方法。具体要求如下：l 建立相应的数据结构；l 磁盘上建立一个文件，文件长度设为10MB，用该文件来模拟一个磁盘，磁盘的物理块大小为512字节。l 建立进程的数据结构；l 时间的流逝可以用下面几种方法模拟：(a)按键盘，每按一次可认为过一个时间单位；(b) 响应WM_TIMER；l 将一批进程对磁盘的请求的情况存磁盘文件，以后可以读出并重放；l 使用两种方式产生进程对磁盘的请求：(a) 自动产生 (b) 手工输入l 显示每次磁盘的请求和空间释放后的相关数据结构的状态；l 显示每次磁盘的请求和空间释放后状态；l 支持的管理方法：空闲表法、空闲链表法、位示图法、UNIX成组链接法。该课程设计的目的：磁盘初始化时把磁盘存储空间分成许多块（扇区），这些空间可以被多个用户共享。用户作业在执行期间常常要在磁盘上建立文件或把已经建立在磁盘上的文件删去，这就涉及到磁盘存储空间的分配和回收。一个文件存放到磁盘上，可以组织成顺序文件（连续文件）、链接文件（串联文件）、索引文件等，因此，磁盘存储空间的分配有两种方式，一种是分配连续的存储空间，另一种是可以分配不连续的存储空间。怎样有效地管理磁盘存储空间是操作系统应解决的一个重要问题，通过这个课程设计可以使我们更好地熟悉掌握磁盘存储管理的原理和分配与回收算法，进一步掌握软件开发方法并提高解决实际问题的能力。2、 原理与算法描述我们组将题目中所给的方法分为连续存储空间法和链接存储空间法，并选取其中最具代表性的位示图法和UNIX成组链接法（连续存储与链接存储的结合）来进行代码的编写。位示图法原理：位示图用来指出磁盘块的使用情况，位示图中各个元素的取值只有“0”和“1”两种，其中“1”状态表示相应的磁盘块已经被占用，“0”状态表示该磁盘块空闲。申请磁盘块时，分配函数查询第一个空闲块所属的位置，然后从该位置往后选取对应数目的空闲块进行分配，将相应位置的位示图上相应元素置为“1”。为了编程方便，我们查阅资料，假设一个磁盘有8个柱面，每个柱面有2个磁道，每个磁道有4个物理记录。释放磁盘块时与分配磁盘块是相反的操作，由释放函数找到第一个空闲磁盘块，并从该位置往前一单位将被占用的相应数目的磁盘块释放，将位示图上相应元素置为“0”。成组链接法原理：成组链接法常应用于UNIX系统中，其主要思想是将结合顺序表和链表进行择优组合，即定义组内为顺序表，最大值为MAXGROUP，大于MAXGROUP的磁盘块另行分组，构成新的顺序表；但是这些顺序表之间用链表的结构进行连接，相当于添加一个新的节点。3、 开发环境由于我们只是简单的对磁盘处理进行模拟，所以就在自己的个人PC上进行，用的IDE是DEV C+（Eclipse上JAVA写的界面被老师打回来了。）。4、 重要算法和设计思路描述设计思路：对于位示图法，我们就是定义一个矩阵用来可视化磁盘空间的使用情况，出于对控制台界面的考虑，我们将条件简化为：假设一个磁盘有3个柱面，每个柱面有2个磁道，每个磁道有4个物理记录，将矩阵简化为8*3的规模。然后分别建立process顺序表数据结构，存储申请的物理块信息；bitmap位示图类来存储位示图的数据和相应的操作，这些操作包括位示图二维数组bitmapMN来存储位示图信息，Initbitmap()初始化位示图，spaceisok() 判断位示图是否合理，displaybitmap()用来打印位示图信息。对于成组链接法，我们定义组结构体group和进程结构体process，定义顺序表最大值MAXGROUP为20，大于MAXGROUP的磁盘块另行分组，构成新的顺序表；但是这些顺序表之间用链表的结构进行连接，相当于添加一个新的group节点。用distribute()函数分配内存块，用recycle()函数撤消进程 ，回收内存块 。用·view()函数显示一些进程和数据结构的相应信息。5、 程序实现数据结构我们组选的题目是第17题：空闲磁盘存储空间的管理：简单方法6、 程序实现程序清单位示图法：#include <iostream>#include <cstring>#include <conio.h>using namespace std;const int cylinder=3,track=2,sector=4;/柱面、磁道、物理块 号 #define SIZE 100/最大块数 const int M=cylinder,N=track*sector;struct process/process顺序表数据结构，存储申请的物理块信息 char name20;int cSIZE,tSIZE,sSIZE;int n;process processtableSIZE;/process格式表 int ppointer=-1;/process指针 class bitmap/位示图 结构体 public:int bitmapMN;void Initbitmap();/初始化位示图bool spaceisok(int n);/位示图符合判断void displaybitmap();/打印 ;bitmap bm;/全局位示图，为所有进程共享 void bitmap:Initbitmap()int i,j; cout<<"*n" cout<<"位示图初始化n" cout<<"*n" for(i=0;i<M;i+) for(j=0;j<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<<"n当前位示图信息如下：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当前分配信息如下：n"cout<<"n#"cout<<"n进程名tt分配的物理块数n"/cout<<"n进程名tt分配的物理块数tt物理块信息n"for(int i=0;i<=ppointer;i+)if(processtablei.n=0)continue;elsecout<<"n"<<processtablei.name<<"tt "<<processtablei.n;/*for(j=0;j<processtablei.n;j+)if(j=0)cout<<"ttt("<<processtablei.cj<<","<<processtablei.tj<<","<<processtablei.sj<<")n"elsecout<<"ttttt("<<processtablei.cj<<","<<processtablei.tj<<","<<processtablei.sj<<")n"*/cout<<"n#n" void distribute(char name20,int n)/分配 int i,j; int count=0;/*计数器*/ for(i=0;i<=ppointer;i+)/processtable中逐个搜索指定进程 if(!strcmp(processtablei.name,name)cout<<"n进程名重复，请检查后命名。n"goto end; if(!bm.spaceisok(n) cout<<"空间不足，找不到"<<n<<"块物理块，分配失败!"return; ppointer+; strcpy(processtableppointer.name,name);/分配的物理块赋予名字 processtableppointer.n=n;/物理块数 for(i=0;i<M;i+)/二维数组逐个搜索空闲物理块 for(j=0;j<N;j+)if(bm.bitmapij=0) processtableppointer.ccount=i;/*柱面号*/processtableppointer.tcount=j/4;/*磁道号*/processtableppointer.scount=j%4;/*物理记录号*/bm.bitmapij=1;/cout<<<<endl;count+;if(count=n)return; end: return;void recycle(char name20)/回收内存 int i,j,flag=0;for(i=0;i<=ppointer;i+)/processtable中逐个搜索指定进程 if(!strcmp(processtablei.name,name)for(j=0;j<processtablei.n;j+)bm.bitmapprocesstablei.cj4*processtablei.tj+processtablei.sj=0;/位示图相应置零 for(int k=i;k<=ppointer-i;k+)/process表项移动strcpy(processtablek.name,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=processtablek+1.sl;ppointer-;flag=1;/delay();cout<<"n找到进程，回收完毕。n"if(flag=0)cout<<"n未找到进程名为"<<name<<"的进程！可能尚未此进程分配物理块n"int main()int choice,n;char name20;bm.Initbitmap();while(1) getch();/ system("cls"); cout<<"n请输入选择:" cout<<"1-分配，2-回收，3-显示位示图，0-退出n" cin>>choice; switch(choice) case 1: cout<<"请输入进程名和需要分配的物理块数：" cin>>name>>n; distribute(name,n); break; case 2: cout<<"给出要回收的进程名：" cin>>name; recycle(name); break; case 3: bm.displaybitmap(); break; case 0: exit(0); default: cout<<"选择错误！" break; return 0; 位示图结果截图如下：成组链接法：#include <iostream>#include <cstring>#include <conio.h>#include <time.h>using namespace std;const int MAXGROUP=20;/定义组的大小为20const int MAXPROCESS=100;/定义一个进程最大能申请的块数 /组结构体typedef struct nodeint num_gp;/组中元素计数 int cellMAXGROUP; /组中元素存放的数组 struct node *next;/指向链表下一节点的指针 group;group *g_GroupHead;/全局组链表头，为所有进程共享/进程结构体 typedef struct node1char name20;/进程名int num_ps;/进程个数int cellMAXPROCESS;/进程号数组struct node1 *next;process; process *g_processHead;/定义进程链表头，为全局变量int idletotal;/当前剩余总空闲块数/初始化组函数group *initial_group()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; /初始化进程函数process *initial_process()int i;cout<<"*n" cout<<"进程初始化n" cout<<"*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 )/打开默认的文件TestUnix.txt/fp=fopen("TestUnix.txt","r");if (NULL = fp)cout<<"错误,文件"<< fname << "打不开"<<endl; /打开成功后就不要输入文件名了直接返回elsebreak;/如果默认的文件打不开，手动输入文件名打开cout<<"请输入初始空闲块数据文件名:" cin>>fname;cout<<"*"<<endl; cout<<"从文件" << fname << "读入的初始空闲块号为:" 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/所存储的空闲块号大于MAXGROUP时需要另申请节点 p=initial_group();/*p- ->head->a->b->c->.*/p->next=g_GroupHead; /将申请的p节点插入到链首g_GroupHead=p; p->cellp->num_gp=temp; p->num_gp+; if (0 = idletotal+%20 )/一组20一行 cout << endl;/输出初始数据 printf("%04d ",temp);/cout<<temp<<" "cout<<endl<<"当前总空闲块数:"<<idletotal<<endl; void init()/初始化组链表 g_GroupHead=initial_group();/初始化计数器idletotal=0;/初始化作业链表g_processHead=initial_process();/从文件读取数据readData(); /分配内存块 void distribute() char processname20; int number; int i; process *p; cout<<"*"<<endl; cout<<"请输入新进程名:" cin>>processname; cout<<"所需内存块数:" cin>>number; if(number > idletotal) cout<<"所需内存块数大于当前空闲块数,分配失败!"<<endl; else p=initial_process(); strcpy(p->name,processname);/* 将节点p插入链表 */p->next=g_processHead->next; g_processHead->next=p; p->num_ps=number; cout<<"申请成功，所申请到的空闲块号依次为:"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; else cout<<g_GroupHead->cell0<<" " 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; /撤消进程 ，回收内存块 void recycle() char processname20; int i; process *p,*q; group *r;cout<<"请输入要撤消的进程名:" cin>>processname; q=g_processHead; p=g_processHead->next; while(p!=NULL)&&(strcmp(p->name,processname) /遍历，寻找指定进程 q=q->next; p=p->next; if(p=NULL) cout<<"Sorry,没有该进程"<<endl; else for(i=0;i<p->num_ps;i+)/释放物理块到相应的组链表 if(g_GroupHead->num_gp<MAXGROUP) g_GroupHead->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进程多个物理块 q->next=p->next;/进程链表中删除指定进程节点 delete p; void view()cout<<"*"<<endl;cout<<endl<<"总空闲块数:"<<idletotal<<endl; cout<<"当前组号为:"<<(g_GroupHead->cellg_GroupHead->num_gp/20)+1<<endl; cout<<"*"<<endl;cout<<"当前组内空闲块号为:"<<endl; for(int i=0;i<g_GroupHead->num_gp;i+) cout<<g_GroupHead->celli<<" " cout<<endl;cout<<"*"<<endl; int main()bool flag = 1;int choice,n;char name20;init();while(flag) getch(); cout<<"n请输入选择:" cout<<"1-分配，2-回收，3-显示信息，0-退出n" cin>>choice; switch(choice) case 0: flag=0; break; case 1:distribute(); break; case 2:recycle(); break; case 3: view(); break; default: cout<<"选择错误！" break; return 0; 成组链接法结果如下所示：当读取不到文件时：7、 总结通过本次的空闲磁盘存储空间的管理的课程设计，我们将对平时学习的理论知识与实际操作相结合，加深了对于磁盘空间管理原理的理解和相应算法的掌握。在做课程设计的过程中，我深深感到理论和实践之间的距离，遇到了许多未曾预料到的问题，不过好在最终都得到了解决。这次课设使我对于操作系统这门课程有了进一步的了解，也锻炼了我写代码、综合运用所学知识和独立思考、解决问题的能力。当然这也多亏了我的队友和老师、同学们的帮助。8、 参考文献专心-专注-专业