操作系统课程设计-模拟设计页式存储管理的分配与回收.docx

操作系统课程设计-模拟设计页式存储管理的分配与回收

———————————————————————————————— 作者：
———————————————————————————————— 日期：

2

武汉理工大学《操作系统》课程设计说明书

学 号：
0120910340228

课 程 设 计

题 目
模拟设计页式存储管理的分配与回收
学 院
计算机科学与技术
专 业
计算机科学与技术
班 级
XX
姓 名
XX
指导教师
XXX

2011
年
01
月
09
日
课程设计任务书
学生姓名： XX 专业班级： 计算机0902班
指导教师： XXX 工作单位：计算机科学与技术学院
题 目: 模拟设计页式存储管理的分配与回收
初始条件：
1．预备内容：阅读操作系统的内存管理章节内容，了解有关虚拟存储器、页式存储管理等概念，并体会页式管理内存的分配和回收过程。
2．实践准备：掌握一种计算机高级语言的使用。
要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
1．采用页式管理方案实施内存分配和回收。能够处理以下的情形
⑴ 能够输入给定的内存页面数，页面大小，进程的个数及每个进程的页数。
⑵ 要求当某进程提出申请空间的大小后，显示能否满足申请，以及为该进程分配资源后内存空间的使用情况（被进程占用的页面，空闲的页面）。
2．设计报告内容应说明：
⑴ 课程设计目的与功能；
⑵ 需求分析，数据结构或模块说明(功能与框图)；
⑶ 源程序的主要部分；
⑷ 测试用例，运行结果与运行情况分析；
⑸ 自我评价与总结：
i）你认为你完成的设计哪些地方做得比较好或比较出色；
ii）什么地方做得不太好，以后如何改正；
iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；
iv）完成本题是否有其他的其他方法（如果有，简要说明该方法）；
v）对实验题的评价和改进意见，请你推荐设计题目。
时间安排：
设计安排一周：周1、周2：完成程序分析及设计。
周2、周3：完成程序调试及测试。
周4、周5：验收，撰写课程设计报告。

（注意事项：严禁抄袭，一旦发现，抄与被抄的一律按0分记）

指导教师签名： 年 月 日
系主任（或责任教师）签名： 年 月 日
模拟设计页式存储管理
的分配与回收
1需求分析

页式管理是一种内存空间存储管理的技术，页式管理分为静态页式管理和动态页式管理。基本原理是将各进程的虚拟空间划分成若干个长度相等的页(page)，页式管理把内存空间按页的大小划分成片或者页面（page frame），然后把页式虚拟地址与内存地址建立一一对应页表，并用相应的硬件地址变换机构，来解决离散地址变换问题。页式管理采用请求调页或预调页技术实现了内外存存储器的统一管理。

图1 页的划分

图2 基本页表示例

静态分页管理的第一步是为要求内存的作业或进程分配足够的页面。系统通过
存储页面表、请求表以及页表来完成内存的分配工作。页表指的是内存中的一块固定存储区。页式管理时每个进程至少有一个页表。请求表指的是用来确定作业或进程的虚拟空间的各页在内存中的实际对应位置；另外整个系统有一个存储页面表，其描述了物理内存空间的分配使用状况。
图3 请求表的示例

存储页面表有两种构成方法：
1、位示图法
　2、空闲页面链表法

模拟设计页式存储管理的分配与回收要求能够满足如下的要求:
(1) 输入给定的内存页面数，页面大小，进程的个数及每个进程的页数。
(2) 要求当某进程提出申请空间的大小后，显示能否满足申请，以及为该进程分配资源后内存空间的使用情况（被进程占用的页面，空闲的页面）。

2 功能设计
2.1 算法分析
首先，请求表给出进程或作业要求的页面数。然后，由存储页面表检查是否有足够的空闲页面，如果没有，则本次无法分配。如果有则首先分配设置页表，并请求表中的相应表项后，按一定的查找算法搜索出所要求的空闲页面，并将对应的页好填入页表中。
图4 分配页面的算法流程

2.2 数据结构
页式管理把内存空间按页的大小划分成片或者页面,再按照一定的规律建立起页表,并通过请求表将分配内容显示出来.将页表和请求表的内容使用结构体来定义是比较方便的.

//页表项结构
typedef struct _pagetableitem
{
pageid pagenum; //页号
blockid blocknum; //块号
}pgtabitem; //页表
typedef pgtabitem * pagetable;

//请求表结构
typedef struct _reqtable
{
unsigned pid; //进程号
unsigned reqpagenum; //请求页面数
pagetable pgtabadr; //页表始址
bool state; //状态
} reqtabitem;

请求表还引入了支持快速插入和删除的list顺序容器来进行相关操作.
list<reqtabitem> reqtable

因为模拟设计的关系,页面的起始地址均应该为随机的数值,所以程序在
设计过程中加入了随机数类的编写.
class RandomNumber
{
private:
unsigned long randseed;
public:
RandomNumber(unsigned long s=0);
unsigned short Random(unsigned long n);
double fRandom(void);
};
采用当前系统的时间值来生成伪随机数分配地址.

定义随机数产生器:RandomNumber random
定义内存页面数:int pagenum
定义页面大小:int pagesize
定义进程个数:int pnum
用整数数组模拟分配的内存页面数int * mempage=new int[pagenum]

2.3模块说明
2.3.1 主函数
主函数依次运行了程序中所实现的关键函数.
int main(){
InitSys(); //初始化系统
MainChoice();//输出系统菜单
Destroy(); //释放申请的动态内存
return 0;}

2.3.2 各个功能函数
初始化内存页面: void Init_Mempage(void)
获取内存使用情况: int Get_Mempagenum(void)
初始化默认的请求表: void Init_Reqtable(void)
为默认的进程分配内存: void Init_DistMem(void)
手动创建进程,并分配内存: void Dist_Mem(void)
释放申请的动态内存: void Destroy(void)
结束指定进程: void Kill(void)

2.3.3 打印函数
　 打印出进程请求表: void PrintReqtable(void)
打印出页表: void PrintPageTable(void)
打印出内存使用情况: void PrintMem(void)
打印出物理块的大小: void PrintBlockSize(void)

2.3.4 其他函数
初始化系统: void InitSys(void)
输出主菜单: void MainMenu(void)
选择运行分支:void MainChoice()

3开发平台
3.1开发平台
(1) 使用系统：Windows 7
(2) 使用语言：C++
(3) 开发工具：Visual C++ 2008

4测试用例，运行结果与运行情况分析
4.1测试方法
通过输入正常数据以及非正常数据对程序进行全方位测试
4.2测试结果
(1)程序主界面
(2)输入进程号和页面数:
(3)显示进程页表:
(4)显示请求表

(5)显示内存使用情况以及物理块大小

(6)错误检验

5源程序的主要部分

#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <list>
#include "page.h"
#include "Random.h"

using namespace std;

list<reqtabitem> reqtable;

RandomNumber random; //随机数产生器
unsigned pagenum=random.Random(80)+21; //内存页面数21-100
unsigned pagesize=random.Random(16)+5; //页面大小 5-20
unsigned pnum=random.Random(4)+5;//进程的个数5-8
int * mempage=new int[pagenum]; //用整数数组模拟内存页面数

/*初始化内存页面*/
void Init_Mempage(void)
{
int i=0;
for(i=0;i<int(pagenum);i++)
mempage[i]=0; //数组全部赋初值
}

/*获取内存的使用情况*/
int Get_Mempagenum(void)
{
int sum=0;
for(int i=0;i<int(pagenum);i++)
if(mempage[i]==0)
sum++;
return sum; //判断有多少内存页面已经被使用
}

/*初始化默认的请求表*/
void Init_Reqtable(void)
{
int i;
for(i=1;i<=int(pnum);i++)
{
reqtabitem preq;
preq.pid=i;
preq.reqpagenum=random.Random(4)+2;//进程请求的页面大小-5
preq.state=false;
preq.pgtabadr=NULL;
reqtable.push_back(preq); //依次压入容器
}
}

/*为默认的进程分配内存*/
void Init_DistMem(void)
{
int reqpnum; //进程请求页面数
int i;

list<reqtabitem>::iterator pos=reqtable.begin();

for(;pos!=reqtable.end();pos++)
{
reqpnum=(*pos).reqpagenum;
if(reqpnum>int(Get_Mempagenum())) //判断请求的内存页面数目是否大于剩余的
{
cout<<"没有足够的内存!"<<endl;
cout<<endl;
}
else
{
(*pos).state=true;
pagetable temp = new pgtabitem[reqpnum]; //新建临时页表项数组
if(temp==NULL)
{
cout<<"内存分配失败!"<<endl;
exit(0);
}
(*pos).pgtabadr=temp;
for(i=0;i<reqpnum;i++)
{
temp[i].pagenum=i; //页表的页号

int randnum=random.Random(pagenum)+1;//随机产生一个块号
while(mempage[randnum]==1)
randnum=random.Random(pagenum)+1;
temp[i].blocknum=randnum;//页表的块号
mempage[randnum]=1;
}
}
}
}

/*手动创建进程,并分配内存*/
void Dist_Mem(void)
{
int i;
reqtabitem preq; //新创建进程记录
int pid; //进程号
int reqpnum; //请求页面数
bool flag=false;

do{
cout<<"请输入进程号:";
flag=false;
cin>>pid;
for(list<reqtabitem>::iterator pos=reqtable.begin();pos!=reqtable.end();pos++)
{
if((*pos).pid==pid)
{
flag=true;
cout<<"该进程号已经存在,请重新输入"<<endl;
cout<<endl;
break;
}
}
}while(flag==true); //循环直到输入的Pid满足条件
preq.pid=pid;
cout<<"请输入需要的页面数:";
cin>>reqpnum;
preq.reqpagenum=reqpnum;
preq.state=false;
preq.pgtabadr=NULL;

reqpnum=preq.reqpagenum;
if(reqpnum>Get_Mempagenum())
{
cout<<"没有足够的内存,进程创建失败!"<<endl;
cout<<endl;
}
else
{
preq.state=true;
pagetable temp = new pgtabitem[reqpnum];
if(temp==NULL)
{
cout<<"内存分配失败!"<<endl;
exit(0);
}
preq.pgtabadr=temp;
for(i=0;i<int(reqpnum);i++)
{
temp[i].pagenum=i; //页表的页号

int randnum=random.Random(pagenum)+1;//随机产生一个块号
while(mempage[randnum]==1)
randnum=random.Random(pagenum)+1;
temp[i].blocknum=randnum;//页表的块号
mempage[randnum]=1;
}
}
reqtable.push_back(preq); //将该进程的记录加入请求表
}

/*程序结束时,释放申请的动态内存*/
void Destroy(void)
{
list<reqtabitem>::iterator pos=reqtable.begin();
for(pos=reqtable.begin();pos!=reqtable.end();pos++)
{
if((*pos).state==true)
delete [](*pos).pgtabadr;
}
reqtable.clear();
}

/* 打印出进程请求表*/
void PrintReqtable(void)
{

cout<<endl;
cout<<"|--------------------------------------------------------------------|"<<endl;
cout<<"| 进程请求表 |"<<endl;
cout<<"|--------------------------------------------------------------------|"<<endl;
cout<<"|"<<setw(8)<<"进程号"
<<setw(16)<<"请求页面数"
<<setw(16)<<"页表起始地址"
<<setw(16)<<"页表长度"
<<setw(16)<<"状态 |"<<endl;
cout<<"|---------------------------------------------------------------------|"<<endl;
list<reqtabitem>::iterator pos=reqtable.begin();
for(pos=reqtable.begin();pos!=reqtable.end();pos++)
{

cout<<"|"<<setw(8)<<(*pos).pid
<<setw(16)<<(*pos).reqpagenum
<<setw(16)<<(*pos).pgtabadr
<<setw(16)<<((*pos).reqpagenum) * pagesize;

if((*pos).state)
cout<<setw(4)<<"已分配 |"<<endl;
else
cout<<setw(4)<<"未分配 |"<<endl;
if((*pos).pid!=reqtable.back().pid)
cout<<"|--------------------------------------------------------------------|"<<endl;
else
cout<<"|--------------------------------------------------------------------|"<<endl;
}

}

/*打印页表*/
void PrintPageTable(void)
{
unsigned pid;
int i;
bool flag=false;
cout<<"请输入进程号:";
cin>>pid;
list<reqtabitem>::iterator pos=reqtable.begin();
for(pos=reqtable.begin();pos!=reqtable.end();pos++)
{
if((*pos).pid==pid&&(*pos).state==true)
{
flag=true;
cout<<"|---------------------------|"<<endl;
cout<<"| 此进程的页表 |"<<endl;
cout<<"|---------------------------|"<<endl;
cout<<"|"<<setw(16)<<"页号"
<<setw(6)<<"块号 |"<<endl;
cout<<"|---------------------------|"<<endl;
int reqpagenum=(*pos).reqpagenum;
for(i=0;i<reqpagenum;i++)
{
cout<<"|"<<setw(16)<<(*pos).pgtabadr[i].pagenum
<<setw(6)<<(*pos).pgtabadr[i].blocknum<<" |"<<endl;
if(i!=reqpagenum-1)
cout<<"|---------------------------|"<<endl;
else
cout<<"|---------------------------|"<<endl;

}
}
}
if(flag==false)
cout<<"系统中不存在该进程或者该进程还没有被分配内存!\n";
cout<<endl;
}

void PrintMem(void)
{
cout<<"内存总块数为"<<pagenum<<",已经使用了"<<pagenum-Get_Mempagenum()<<"块!"<<endl;
cout<<"现在还有"<<Get_Mempagenum()<<"块内存区域空闲!"<<endl;
cout<<endl;
}

void PrintBlockSize(void)
{
cout<<"物理块大小为:"<<pagesize<<"KB"<<endl;
cout<<endl;
}

/*结束指定进程*/
void Kill(void)
{
bool flag;
int i;
reqtabitem temp;
list<reqtabitem>::iterator pos=reqtable.begin();
int pid;
do{
cout<<"请输入进程号:";
flag=false;
cin>>pid;
for(pos=reqtable.begin();pos!=reqtable.end();pos++)
{
if((*pos).pid==pid)
{
flag=true;
temp=*pos;
break;
}
}
if(flag==false)
cout<<"系统中不存在该进程!"<<endl;
cout<<endl;
}while(flag==false);
for(i=0;i<int(temp.reqpagenum);i++)
mempage[temp.pgtabadr[i].blocknum]=0;
reqtable.remove(temp);
//重新为没有分配到内存的进程分配内存
for(pos=reqtable.begin();pos!=reqtable.end();pos++)
{
if((*pos).state==false)
{
int reqpnum;
reqpnum=(*pos).reqpagenum;
if(reqpnum<=Get_Mempagenum())
{
(*pos).state=true;
pagetable temp = new pgtabitem[reqpnum];
if(temp==NULL)
{
cout<<"内存分配失败!"<<endl;
cout<<endl;
exit(0);
}
(*pos).pgtabadr=temp;
for(i=0;i<int(reqpnum);i++)
{
temp[i].pagenum=i; //页表的页号

int randnum=random.Random(pagenum)+1;//随机产生一个块号
while(mempage[randnum]==1)
randnum=random.Random(pagenum)+1;
temp[i].blocknum=randnum;//页表的块号
mempage[randnum]=1;
}
}
}
}

}

/*初始化系统*/
void InitSys(void)
{
cout.setf(ios::left);//左对齐
Init_Mempage();
Init_Reqtable();
Init_DistMem();
}
/*输出主菜单*/
void MainMenu(void)
{
cout<<"页式存储管理的分配与回收"<<endl;
cout<<"1.手动创建进程"<<endl;
cout<<"2.显示进程页表"<<endl;
cout<<"3.显示请求表"<<endl;
cout<<"4.撤销进程"<<endl;
cout<<"5.显示内存使用情况"<<endl;
cout<<"6.显示物理块大小"<<endl;
cout<<"7.退出系统"<<endl;
cout<<"请输入您的选择(0--7):";
}
/*选择函数*/
void MainChoice()
{
int choice;
do{
MainMenu();
cin>>choice;
switch(choice)
{
case 1:
Dist_Mem();
break;
case 2:
PrintPageTable();
break;
case 3:
PrintReqtable();
break;
case 4:
Kill();
break;
case 5:
PrintMem();
break;
case 6:
PrintBlockSize();
break;
case 7:
break;
default :cout<<"输入有误，请重新输入.\n";
cout<<endl;
break;
}
}while(choice!=7);
}

int main()
{
InitSys();//初始化系统
MainChoice();//输出系统菜单
Destroy();//释放申请的动态内存
return 0;
}

6自我评价与总结
此次试验是完全在自己独立完成的，首先在分析问题并把问题转化为编程问题，我觉得个人把握的很好，对页式管理的基本原理理解的比较透彻；其次我用了个随机函数来模拟页表起始地址和物理块大小等变量，使得输出的结果显得随机性较强,符合系统真实分配的情况. 另外对于进程请求表使用顺序容器操作,结构体保存项目的设计也独具匠心,配合迭代器的使用达到类似栈的用途,输出请求表的时候比较清晰明了.

但是程序还有不足之处，程序仅仅只能从直观数值上来体现页式管理的随机分配的特性,并没有办法像linux之类操作系统一般真正的进行内存分配与回收,这是课后深入研究的一个方面。再有就是程序有些代码部分是可以复用的，可以把这些重复执行的代码写成函数，需要用时直接调用代码函数。

这次自己的收获还是不小，首先使我提高了分析问题，并根据需求转化成相应的程序结构的能力；其次也丰富了自己编写程序，调试程序的经验，这使得我编程时可能出现的错误的认识，并如何去避免产生了新的认识。在编写程序的过程中翻阅了大量相关书籍,保证在页式管理基本原理透彻了解情况下进行设计,事半功倍,让我认识到磨刀不误砍柴工的道理

总的来说这次试验比较成功，加深我对页式管理的理解，同时也提高了自己的编程的能力。编程是个长久的过程，平时要多去动手实践，去提高自己分析问题、发现问题、解决问题的能力。路漫漫其修远兮，吾将上下而求索!

7 参考文献
（1） 《计算机操作系统教程（第3版）》 张尧学 史美林 张高编著
（2） 《深入解析Windows操作系统》 M.Russunovich著 潘爱民译
（3） 《C++ Primer第四版》 B.Lippman著

本科生课程设计成绩评定表
班级：XX　 姓名：XX 学号：XX
序号
评分项目
满分
实得分
1
学习态度认真、遵守纪律
10

2
设计分析合理性
10

3
设计方案正确性、可行性、创造性
20

4
设计结果正确性
40

5
设计报告的规范性
10

6
设计验收
10

总得分/等级

评语：

注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、
及格（60-69分）、60分以下为不及格

　　　　　　　　　　　　　　　　　　　　指导教师签名：
　　　　　　　　　　　　　　　　　　201 年　月　日
25