空闲磁盘存储空间的管理-OS课程设计

OS课程设计空闲磁盘存储空间的管理1、课程设计任务、要求、目的我们组选的题目是第17题：空闲磁盘存储空间的管理：简单方法。具体要求如下：建立相应的数据结构；磁盘上建立一个文件，文件长度设为10MB，用该文件来模拟一个磁盘，磁盘的物理块大小为512字节。建立进程的数据结构；时间的流逝可以用下面几种方法模拟：(a)按键盘，每按一次可认为过一个时间单位；(b)响应WM_TIMER；将一批进程对磁盘的请求的情况存磁盘文件，以后可以读出并重放；使用两种方式产生进程对磁盘的请求：(a)自动产生(b)手工输入显示每次磁盘的请求和空间释放后的相关数据结构的状态；显示每次磁盘的请求和空间释放后状态；支持的管理方法：空闲表法、空闲链表法、位示图法、UNIX成组链接法。该课程设计的目的：磁盘初始化时把磁盘存储空间分成许多块（扇区），这些空间可以被多个用户共享。用户作业在执行期间常常要在磁盘上建立文件或把已经建立在磁盘上的文件删去，这就涉及到磁盘存储空间的分配和回收。一个文件存放到磁盘上，可以组织成顺序文件（连续文件）、链接文件（串联文件）、索引文件等，因此，磁盘存储空间的分配有两种方式，一种是分配连续的存储空间，另一种是可以分配不连续的存储空间。怎样有效地管理磁盘存储空间是操作系统应解决的一个重要问题，通过这个课程设计可以使我们更好地熟悉掌握磁盘存储管理的原理和分配与回收算法，进一步掌握软件开发方法并提高解决实际问题的能力。2、原理与算法描述我们组将题目中所给的方法分为连续存储空间法和链接存储空间法，并选取其中最具代表性的位示图法和UNIX成组链接法（连续存储与链接存储的结合）来进行代码的编写。位示图法原理：位示图用来指出磁盘块的使用情况，位示图中各个元素的取值只有“0”和“1”两种，其中“1”状态表示相应的磁盘块已经被占用，“0”状态表示该磁盘块空闲。申请磁盘块时，分配函数查询第一个空闲块所属的位置，然后从该位置往后选取对应数目的空闲块进行分配，将相应位置的位示图上相应元素置为“1”。为了编程方便，我们查阅资料，假设一个磁盘有8个柱面，每个柱面有2个磁道，每个磁道有4个物理记录。释放磁盘块时与分配磁盘块是相反的操作，由释放函数找到第一个空闲磁盘块，并从该位置往前一单位将被占用的相应数目的磁盘块释放，将位示图上相应元素置为“0”。成组链接法原理：成组链接法常应用于UNIX系统中，其主要思想是将结合顺序表和链表进行择优组合，即定义组内为顺序表，最大值为MAXGROUP，大于MAXGROUP的磁盘块另行分组，构成新的顺序表；但是这些顺序表之间用链表的结构进行连接，相当于添加一个新的节点。3、开发环境由于我们只是简单的对磁盘处理进行模拟，所以就在自己的个人PC上进行，用的IDE是DEVC++（Eclipse上JAVA写的界面被老师打回来了。。。）。4、重要算法和设计思路描述设计思路：对于位示图法，我们就是定义一个矩阵用来可视化磁盘空间的使用情况，出于对控制台界面的考虑，我们将条件简化为：假设一个磁盘有3个柱面，每个柱面有2个磁道，每个磁道有4个物理记录，将矩阵简化为8*3的规模。然后分别建立process顺序表数据结构，存储申请的物理块信息；bitmap位示图类来存储位示图的数据和相应的操作，这些操作包括位示图二维数组bitmap[M][N]来存储位示图信息，Initbitmap()初始化位示图，spaceisok()判断位示图是否合理，displaybitmap()用来打印位示图信息。对于成组链接法，我们定义组结构体group和进程结构体process，定义顺序表最大值MAXGROUP为20，大于MAXGROUP的磁盘块另行分组，构成新的顺序表；但是这些顺序表之间用链表的结构进行连接，相当于添加一个新的group节点。用distribute()函数分配内存块，用recycle()函数撤消进程，回收内存块。用·view()函数显示一些进程和数据结构的相应信息。5、程序实现—数据结构我们组选的题目是第17题：空闲磁盘存储空间的管理：简单方法6、程序实现—程序清单位示图法：#includeiostream#includecstring#includeconio.husingnamespacestd;constintcylinder=3,track=2,sector=4;//柱面、磁道、物理块号#defineSIZE100//最大块数constintM=cylinder,N=track*sector;structprocess//process顺序表数据结构，存储申请的物理块信息{charname[20];intc[SIZE],t[SIZE],s[SIZE];intn;};processprocesstable[SIZE];//process格式表intppointer=-1;//process指针classbitmap//位示图结构体{public:intbitmap[M][N];voidInitbitmap();//初始化位示图boolspaceisok(intn);//位示图符合判断voiddisplaybitmap();//打印};bitmapbm;//全局位示图，为所有进程共享voidbitmap::Initbitmap(){inti,j;cout**********************************************\n;cout位示图初始化\n;cout**********************************************\n;for(i=0;iM;i++){for(j=0;jN;j++){bitmap[i][j]=0;}}//getchar();displaybitmap();//初始化后位示图getchar();//system(cls);}boolbitmap::spaceisok(intn)//判断位示图空闲物理块是否足够{intcount=0;for(inti=0;iM;i++){for(intj=0;jN;j++){if(bitmap[i][j]==0){count++;}}}if(countn)returnfalse;elsereturntrue;}voidbitmap::displaybitmap()//打印位示图{inti,j;cout\n当前位示图信息如下：\n;cout\n***********************************************************************\n;for(i=0;iM;i++){for(j=0;jN;j++){cout\tbitmap[i][j];}coutendl;}cout\n***********************************************************************\n;if(ppointer0){cout\n尚未分配磁盘空间\n;return;}else{cout\n当前分配信息如下：\n;cout\n#######################################################;cout\n进程名\t\t分配的物理块数\n;//cout\n进程名\t\t分配的物理块数\t\t物理块信息\n;for(inti=0;i=ppointer;i++){if(processtable[i].n==0)continue;else{cout\nprocesstable[i].name\t\tprocesstable[i].n;/*for(j=0;jprocesstable[i].n;j++){if(j==0){cout\t\t\t(processtable[i].c[j],processtable[i].t[j],processtable[i].s[j])\n;}else{cout\t\t\t\t\t(processtable[i].c[j],processtable[i].t[j],processtable[i].s[j])\n;}}*/}}cout\n#######################################################\n;}}voiddistribute(charname[20],intn)//分配{inti,j;intcount=0;/*计数器*/for(i=0;i=ppointer;i++)//processtable中逐个搜索指定进程{if(!strcmp(processtable[i].name,name)){cout\n进程名重复，请检查后命名。\n;gotoend;}}if(!bm.spaceisok(n)){cout空间不足，找不到n块物理块，分配失败!;return;}ppointer++;strcpy(processtable[ppointer].name,name);//分配的物理块赋予名字processtable[ppointer].n=n;//物理块数for(i=0;iM;i++)//二维数组逐个搜索空闲物理块{for(j=0;jN;j++)if(bm.bitmap[i][j]==0){processtable[ppointer].c[count]=i;/*柱面号*/processtable[ppointer].t[count]=j/4;/*磁道号*/processtable[ppointer].s[count]=j%4;/*物理记录号*/bm.bitmap[i][j]=1;//cout666666endl;count++;if(count==n)return;}}end:return;}voidrecycle(charname[20])//回收内存{inti,j,flag=0;for(i=0;i=ppointer;i++)//processtable中逐个搜索指定进程{if(!strcmp(processtable[i].name,name)){for(j=0;jprocesstable[i].n;j++)bm.bitmap[processtable[i].c[j]][4*processtable[i].t[j]+processtable[i].s[j]]=0;//位示图相应置零for(intk=i;k=ppointer-i;k++)//process表项移动{strcpy(processtable[k].name,processtable[k+1].name);//删除，前移processtable[k].n=processtable[k+1].n;for(intl=0;lprocesstable[k].n;l++){processtable[k].c[l]=processtable[k+1].c[l];processtable[k].t[l]=processtable[k+1].t[l];processtable[k].s[l]=processtable[k+1].s[l];}}ppointer--;flag=1;//delay();cout\n找到进程，回收完毕。\n;}}if(flag==0)cout\n未找到进程名为name的进程！！可能尚未此进程分配物理块\n;}intmain(){intchoice,n;charname[20];bm.Initbitmap();while(1){getch();//system(cls);cout\n请输入选择:;cout1--分配，2--回收，3--显示位示图，0--退出\n;cinchoice;switch(choice){case1:{cout请