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

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

《空闲磁盘存储空间的管理OS课程设计.docx》由会员分享，可在线阅读，更多相关《空闲磁盘存储空间的管理OS课程设计.docx（25页珍藏版）》请在冰点文库上搜索。

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

-CAL-FENGHAI-（2020YEAR-YICAI）_JINGBIAN

空闲磁盘存储空间的管理-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、程序实现—程序清单

位示图法：

#include

#include

#include

usingnamespacestd;

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;i

{

for（j=0;j

{

bitmap[i][j]=0;

}

}

//getchar（）;

displaybitmap（）;//初始化后位示图

getchar（）;

//system（"cls"）;

}

boolbitmap:

:

spaceisok（intn）//判断位示图空闲物理块是否足够

{

intcount=0;

for（inti=0;i

{

for（intj=0;j

{

if（bitmap[i][j]==0）

{

count++;

}

}

}

if（count

returnfalse;

else

returntrue;

}

voidbitmap:

:

displaybitmap（）//打印位示图

{

inti,j;

cout<<"\n当前位示图信息如下：

\n";

cout<<"\n***********************************************************************\n";

for（i=0;i

{

for（j=0;j

{

cout<<"\t"<

}

cout<

}

cout<<"\n***********************************************************************\n";

if（ppointer<0）

{

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<<"\n"<

/*

for（j=0;j

{

if（j==0）

{

cout<<"\t\t\t（"<

}

else

{

cout<<"\t\t\t\t\t（"<

}

}

*/

}

}

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<<"空间不足，找不到"<

";

return;

}

ppointer++;

strcpy（processtable[ppointer].name,name）;//分配的物理块赋予名字

processtable[ppointer].n=n;//物理块数

for（i=0;i

{

for（j=0;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;

//cout<<666666<

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;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;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未找到进程名为"<

！

可能尚未此进程分配物理块\n";

}

intmain（）

{

intchoice,n;charname[20];

bm.Initbitmap（）;

while

（1）

{

getch（）;

//system（"cls"）;

cout<<"\n请输入选择:

";

cout<<"1--分配，2--回收，3--显示位示图，0--退出\n";

cin>>choice;

switch（choice）

{

case1:

{

cout<<"请输入进程名和需要分配的物理块数：

";

cin>>name>>n;

distribute（name,n）;

break;

}

case2:

{

cout<<"给出要回收的进程名：

";

cin>>name;

recycle（name）;

break;

}

case3:

bm.displaybitmap（）;

break;

case0:

exit（0）;

default:

cout<<"选择错误！

";

break;

}

}

return0;

}

位示图结果截图如下：

成组链接法：

#include

#include

#include

#include

usingnamespacestd;

constintMAXGROUP=20;//定义组的大小为20

constintMAXPROCESS=100;//定义一个进程最大能申请的块数

//组结构体

typedefstructnode{

intnum_gp;//组中元素计数

intcell[MAXGROUP];//组中元素存放的数组

structnode*next;//指向链表下一节点的指针

}group;

group*g_GroupHead;//全局组链表头，为所有进程共享

//进程结构体

typedefstructnode1{

charname[20];//进程名

intnum_ps;//进程个数

intcell[MAXPROCESS];//进程号数组

structnode1*next;

}process;

process*g_processHead;//定义进程链表头，为全局变量

intidletotal;//当前剩余总空闲块数

//初始化组函数

group*initial_group（）

{

inti;

cout<<"\n**********************************************\n";

cout<<"组初始化\n";

group*p;

p=newgroup;

p->num_gp=0;

p->next=NULL;

for（i=0;i

{

p->cell[i]=-1;

}

//cout<<"**********************************************\n";

returnp;

}

//初始化进程函数

process*initial_process（）

{

inti;

cout<<"**********************************************\n";

cout<<"进程初始化\n";

cout<<"**********************************************\n";

process*p;

p=newprocess;

strcpy（p->name,""）;

p->num_ps=0;

p->next=NULL;

for（i=0;i

{

p->cell[i]=-1;

}

returnp;

}

//读入空闲块文件并组织成成组链表

voidreadData（）

{

FILE*fp;

charfname[20]="Test.txt";

inttemp;

group*p;

while（（fp=fopen（fname,"r"））==NULL）

{

//打开默认的文件TestUnix.txt

//fp=fopen（"TestUnix.txt","r"）;

if（NULL==fp）

{

cout<<"错误,文件"<

}

//打开成功后就不要输入文件名了直接返回

else

{

break;

}

//如果默认的文件打不开，手动输入文件名打开

cout<<"请输入初始空闲块数据文件名:

";

cin>>fname;

}

cout<<"**************************************************"<

cout<<"从文件"<

";

while（!

feof（fp））

{

fscanf（fp,"%d",&temp）;

if（g_GroupHead->num_gp

{

g_GroupHead->cell[g_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->cell[p->num_gp]=temp;

p->num_gp++;

}

if（0==idletotal++%20）//一组20一行

{

cout<

}

//输出初始数据

printf（"%04d",temp）;

//cout<

}

cout<

"<

}

voidinit（）

{

//初始化组链表

g_GroupHead=initial_group（）;

//初始化计数器

idletotal=0;

//初始化作业链表

g_processHead=initial_process（）;

//从文件读取数据

readData（）;

}

//分配内存块

voiddistribute（）

{

charprocessname[20];

intnumber;

inti;

process*p;

cout<<"**********************************"<

cout<<"请输入新进程名:

";

cin>>processname;

cout<<"所需内存块数:

";

cin>>number;

if（number>idletotal）

{

cout<<"所需内存块数大于当前空闲块数,分配失败!

"<

}

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

{

if（g_GroupHead->num_gp>1）

{

cout<cell[g_GroupHead->num_gp-1]<<"";

g_GroupHead->num_gp--;

p->cell[i]=g_GroupHead->cell[g_GroupHead->num_gp-1];

}

else

{

cout<cell[0]<<"";

p->cell[i]=g_GroupHead->cell[g_GroupHead->num_gp-1];

g_GroupHead->num_gp--;

if（g_GroupHead->next!

=NULL）

{

g_GroupHead=g_GroupHead->next;

}

}

idletotal--;

}

}

cout<

}

//撤消进程，回收内存块

voidrecycle（）

{

charprocessname[20];

inti;

proces