分页式管理实验报告.doc

个人收集整理 勿做商业用途

题 目 连续式与分页式主存管理模式的模拟实现

学生姓名

学 号

学 院

专 业 计算机科学与技术专业

指导教师 赵晓平

二Ｏ一二年六月十一日

一、实验目的
模拟在连续分配与分页管理两种方式下,主存空间的分配与回收，帮助学生加深了解存储器管理的工作过程.
注意，该实验为模拟实验，并不要求进行真正的内存分配与回收,主要是编写程序模拟其中过程即可.
二、实验内容
1 连续式分配
1、 在连续分配方式下,设计一个动态分区分配与回收的内存管理程序.
2、 动态分区分配按作业需要的主存大小来分割分区。当要装入一个作业时，根据作业需要、、的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。
3、 设置一张全局分区状态表说明当前内存分配状态，例如下所示：
0
5k
10k
14k
26k
32k

640k

操作系统区
作业1
作业3
空闲区
作业2

空闲区

4、 设置一张空闲分区表描述当前空闲分区分布状况，可采用数组或链表来实现,数组可参考以下格式：

起 址
长 度
状 态
第一栏
14 K
12 K
未 分 配
第二栏
32 K
96 K
未 分 配
M
M

空 表 目

空 表 目

M
说明：
起址——指出一个空闲区的主存起始地址。
长度-—指出从起始地址开始的一个连续空闲的长度.
状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目"状态，表示表中对应的登记项目是空白(无效），可用来登记新的空闲区。

5、 在作业撤销后，系统需要回收分区。在空闲分区表中找到一个空表目登记回收分区的起址和长度,并且修改表目状态为未分配.
注意：由于分区的个数不定，所以空闲分区表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出"无法登记。
6、 在回收分区时，应考虑相邻空闲分区合并。
7、 在完成一次作业装入后，都需要输出：本次分配的分区起址与长度,全局分区状态表,空闲分区表的内容。若在分配中发生分割，需要说明分割后新空白分区的起址与长度。
8、 在完成一次作业撤销后，都需要输出：本次回收的分区起址与长度，全局分区状态表，空闲分区表的内容。若发生相邻空闲分区合并,需要说明哪几个分区合并在一起,合并后的起址与长度
2、分页式管理
1、 设计一个基本分页存储管理程序
2、 分页式存储器把主存分成大小相等的若干块，作业的信息也按块的大小分页,作业装入主存时按页分散存放在主存的空闲块中。
3、 系统用一张块表记录物理块分配的情况，如下图所示，其中状态0表示未分配，1表示已分配。另外增加一个空闲块数,记录当前可用的物理块总数。

状态
第0块
1
第1块
1
第2块
0
第3块
1
第4块
0
M
M

4、 需要为每个作业设置一张页表，记录页号与块号的对应关系.

页 号
块 号
0
168
1
72
2
56
M
M

5、 作业装入内存时，分配过程如下:
a) 将空闲块数乘上每块空间，计算出可用空间总数，然后与作业需要空间比较，若不能满足需要,提示不能装入。
b) 若能满足需要，为作业创建页表，在块表中寻找足够的空白块，将页号与块号一一对应，并填入页表。同时修改块表中各个块的状态
c) 修改空闲块数，记录剩下空白块总数。
6、 作业撤销后，需要回收物理块，回收过程如下：
a) 根据页表，修改块表中对应各个物理块的状态
b) 修改空闲块数，记录回收后空白块总数。
c) 撤销页表
7、 每次作业装入或回收,都需要输出块表、页表的内容，发生变化的块号，以及空闲块数。若块表太大，可以用二维表格的方式输出,或只输出发生变化的块号。

三、实验要求
1、 根据例程，尝试采用首次适应算法、循环首次适应算法、最佳适应算法其中的一种或多种算法实现3.2.1的动态分区分配.算法思想请参考课本的分区分配算法。
2、 根据例程，尝试实现3。2。1的分区回收功能。
3、 根据例程，尝试实现3.2。2的分页系统功能
4、 至少完成上述三项实验内容中的一个。
5、 自行设定内存总空间，大小单位为KB，分页管理需要设定每个页的大小。
6、 随机设置当前内存分配状态.
7、 自行设计作业队列，队列中至少要有5个作业,设定各个作业空间大小，大小要适中。
8、 输出结果要尽量详细清晰，如果输出内容比较多，可以考虑把输出结果保存到文件中，通过文件来查看。
9、 程序代码要尽量加入注释，提高程序的清晰度与可读性。
10. 在实验报告中，一方面可以对实验结果进行分析，一方面可以对两种分配方式进行比较，分析它们的优劣。

四、实验过程
1.分页式:
//分页存储管理程序

＃include 〈stdio。h>
＃include<iostream。h>
＃include〈string.h〉
＃include <stdlib。h〉
＃include 〈time.h>
#define n 11 //模拟实验中允许的最大进程数为n
#define m 11 //模拟实验中允许的最大分区个数为m
＃define M_SIZE 2000
struct
{
float address; //分配给进程的起始地址
float length; //分配给进程的空闲区长度，单位为字节
int flag； //分配区表标志，用"0”已分配,用"1"表示未分配
｝Used_Table[m]; //分配分区表

struct
｛
float address;
float length；
int flag;
}Free_table［m]；

float stand_length（int k)//随机产生一个分区大小的函数
｛
float st_length[20];
srand（(unsigned）time（NULL)）;//srand（）函数产生一个当前时间开始的随机种子
for （int i=0;i〈20;i++）
st_length[i］=float (rand()%1000）;
return st_length［k］;
｝

float process_length（int k)//随机产生一个进程大小的函数
{
float pt_length[20]；
srand（（unsigned)time(NULL)）；//srand（）函数产生一个当前时间开始的随机种子
for （int i=0；i<20;i++）
pt_length[i］= float （rand()％500);
return pt_length[k］;
}
int process_num（)//随机产生一个进程个数的函数
{
int num；
int A［10］=｛1，2，3,4,5，6，7，8,9，10};
srand（（unsigned)time（NULL)）;
num=rand()％10;
return A［num］；
}

char srand_name（int k）//随机产生一个进程的名字
{
char A[26］=｛’A’，'B’，’C','D','E’,’F','G’,’H’，'I',
’J’，’K','L’，'M',’N'，’O'，’P',’Q’,'R','S’，'T’，'U’,’V’,'W'，’X’，'Y’，’Z'｝；
return A［k]；

｝

void allocate(char PRS_NAME,float X_K) //采用最优分配算法为进程PRS_NAME分配X_K大小的空间
{
int i，k;
float ad；
k=—1;
for（i=0；i〈m；i++) //寻找空间大于X_K的最小空闲区登记项k
if（Free_table［i］。length〉=X_K＆&Free_table[i]。flag==1）
if(k==-1||Free_table[i］。length〈Free_table[k].length)
k=i；
if（k==—1)//未找到可用空闲分区，返回
｛
printf（"无可用空闲区\n"）；
return；
}
//找到可用空闲区，开始分配：
if（Free_table［k]。length—X_K〈=M_SIZE)
｛
Free_table[k].flag=0；
ad=Free_table［k］.address；
X_K=Free_table［k].length；
｝
else
{
Free_table[k］。length=Free_table[k］.length—X_K；
ad=Free_table[k］.address+Free_table[k］.length;
｝
//修改已分配区表
i=0;
while（Used_Table[i］.flag！=0&&i<n） //寻找空表目
i++;
if（i>=n） //无表目填写已分分区
{
printf("无表目填写已分分区，错误\n”)；
//修正空闲区表
if（Free_table［k］.flag==0)
//前面找到的是整个空闲分区
Free_table［k］。flag=1；
else
{//前面找到的是某个空闲分区的一部分
Free_table［k]。length=Free_table[k］。length+X_K;
return;
｝
｝
else
{//修改已分配表
Used_Table［i].address=ad；
Used_Table［i]。length=X_K；
Used_Table[i］.flag=PRS_NAME;
｝
return；
}//内存分配函数结束

void reclaim(char PRS_NAME） //回收进程名为PRS_NAME的进程所占内存空间
｛
int i,k，j，s,t；
float S,L；
//寻找已分配表中对应登记项
s=0；
while（（Used_Table［s].flag!=PRS_NAME｜｜Used_Table［s]。flag==0)&＆s〈n)
s++；
if(s〉=n)//在已分配表中找不到名字为PRS_NAME的进程
{
cout<<”找不到该进程”〈<endl;
return；
}
//修改已分配表
Used_Table［s］。flag=0； //取得归还分区的起始地址S和长度L
S=Used_Table[s］.address;
L=Used_Table[s］。length；
j=-1；k=—1;i=0；
//寻找回收分区的空闲上下邻，上邻表目k,下邻表目j
while（i〈m&＆(j==-1｜｜k==—1))
{
if(Free_table[i］。flag==1)
{
if（Free_table［i］。address+Free_table[i］。length==S)k=i;//找到上邻
if(Free_table［i]。address==S+L)j=i;//找到下邻
}
i++;
｝
if(k！=—1)
if(j!=—1)
// 上邻空闲区，下邻空闲区,三项合并
｛
Free_table[k]。length=Free_table［j］。length+Free_table［k]。length+L；
Free_table［j]。flag=1;
｝
else
//上邻空闲区，下邻非空闲区，与上邻合并
Free_table［k]。length=Free_table[k]。length+L；
else
if（j！=-1)
//上邻非空闲区，下邻为空闲区，与下邻合并
｛
Free_table[j].address=S;
Free_table［j］.length=Free_table[j]。length+L；
}
else //上下邻均为非空闲区，回收区域直接填入
｛
//在空闲区表中寻找空栏目
t=0；
while（Free_table［t］.flag==1&＆t〈m)
t++;
if（t>=m)//空闲区表满，回收空间失败,将已分配表复原
{
cout<<"内存空闲表没有空间,回收空间失败”〈〈endl；
Used_Table［s].flag=j;
return;
｝
Free_table[t］。address=S；
Free_table［t］。length=L；
Free_table[t］。flag=1;
｝
return；
｝

void main（ ）
｛
int i，a；
float p_length;
char p_name；
//空闲分区表初始化：
int t_P；
Free_table[0］.address=1000；
for（t_P=0； t_P〈m； t_P++）
｛
Free_table[t_P］.length=stand_length（t_P）；
Free_table［t_P]。flag=1;
}

for(t_P=1；t_P〈m；t_P++）
｛
Free_table[t_P］。address=Free_table[t_P—1].address+Free_table[t_P—1］。length;
} //空闲分区表初始化结束
//已分配表初始化:
for(i=0;i<n;i++)
Used_Table［i].flag=0;
cout<〈”*＊*＊＊＊****＊＊＊**＊**＊*＊分页式主存管理的模拟实现**＊＊*＊＊*＊**＊*＊*”〈<endl<〈endl；
cout〈<"＊**＊*＊*＊＊*＊＊***＊*＊**＊选择以下标号实现其功能*＊＊**＊**＊＊＊＊＊＊*＊**＊***＊＊＊*＊＊＊”〈<endl；
cout〈<”＊ 0:退出 2：回收进程和内存 ＊”〈〈endl;
cout<<”＊ 1:随机产生进程并分配内存 3:显示内存分配记录 ＊"<〈endl；
cout<<"*＊＊＊＊*＊*＊**＊*＊*****＊＊＊**＊*＊＊**＊＊**＊＊＊**＊＊**＊*＊*＊＊*＊***＊＊*＊"〈〈endl;
while（1)
｛

cout〈<"请输入一个功能项（0—-3) ：”<<endl;
cin>〉a；
switch（a）
｛
case 0: return; //a=0选择退出程序结束
case 1： //a=1开始随机的产生进程并分配空间
{
int p_num=process_num();
cout<〈”随机产生"<〈p_num〈<”个进程”<<endl；
int p_p;
cout<<”进程名 进程大小”<<endl;
for（p_p=0;p_p<p_num;p_p++)
｛
p_name=srand_name(p_p）;
p_length= process_length（p_p)；
cout〈〈p_name〈<" ”〈〈p_length〈〈endl；
allocate（p_name,p_length); //分配内存空间
}
cout〈<”要查看内存分配请在提示命令出现后输入’3’回车"〈<endl;
}
break；
case 2： //a=2回收内存空间
cout〈〈”输入要回收分区的进程名”；
cin〉>p_name；
reclaim(p_name）； //回收内存空间
break；
case 3: //a=3显示内存情况

cout〈〈”输出空闲区表：”〈<endl；
cout<〈”—-———---—--—---—----——-——--————-------------———-—--—--"〈〈endl；
cout<〈"起始地址 分区大小 标志(0—已分配，1—未分配）"〈<endl；
for（i=0；i<m；i++）
printf(”％6。0f％9.0f%6d\n"，Free_table［i］。address，Free_table［i]。length, Free_table[i］.flag）；
cout<〈"已分配分区表：”〈〈endl；
cout〈<”———-----—-----—-—----—-—--—-—----——--———————----—-----”<〈endl;
cout〈〈"起始地址 分区大小 进程名"<〈endl；
for（i=0；i<n;i++)
if（Used_Table［i].flag！=0)
printf（"%6。0f%9。0f％6c\n”，Used_Table［i].address,Used_Table［i]。length， Used_Table[i].flag);
break；
default：
cout<〈”请输入正确的选项！"<<endl;
}
｝
｝
截图：

2. 首次适应算法实现动态分区分配
代码：＃include〈stdio。h>
＃include〈stdlib。h〉
#include〈conio。h>
#include〈string。h>
#define getpch(type) (type＊）malloc(sizeof(type)）
/＊/＃define NULL 0＊/

struct table｛
char name［10]；
char state； /* D（分配） or N(空闲)＊/
int size； /*分区大小*/
int addr； /*起始地址＊/
struct table ＊next；
struct table *prev；
}*tab=NULL，*p；
typedef struct table TABLE;

UI(){
printf（"~～～~～~～~～～～~~~~~～~~～~～～～~~～~～～~～~~～～~～~～～~~~～~~~~~～～～～～～～～~～\n"）；
printf(” 首次适应算法 \n”);
printf(" \n");
printf（” 计科3班 顾志祥 20101308103 \n"）;
printf("~~～～~～~~~~～~～～～～~～~~~～～～～~～~～~～～~~～~～～～～～～~~～～～~～~～～～～～~~～～～\n”）;
}

recycle(char n［10］）{
TABLE ＊pr=NULL；
for（pr=tab；pr!=NULL;pr=pr->next）｛
if（！strcmp（pr->name，n)＆&pr->state==’D'){
if(pr—〉prev!=NULL&&pr—〉prev—>state=='N'){ /＊回收区的前一分区空闲*/
if(pr—〉next-〉state==’N') ｛ /＊回收区的前后分区都空闲*/
pr—>state='N’;
pr-〉prev->size+=(pr—>size+pr->next-〉size)； /＊合并分区大小＊/
pr—>prev—>next=pr—>next—>next； /*删除回收分区及其后一空闲分区表项＊/
pr—〉next—>next-〉prev=pr—>prev；
return 0；
}
else {
pr—〉state=’N’；
pr-〉prev->size+=pr—>size;
pr—>next—〉prev=pr—>prev;
pr—>prev->next=pr-〉next;
return 0；
｝
｝
else if（pr-〉next!=NULL&&pr—>next-〉state==’N’)｛
pr—〉state=’N'；
pr->size+=pr-〉next—>size;
if(pr-〉next—〉next!=NULL)｛
pr—>next—>next—〉prev=pr；
pr—>next=pr—〉next-〉next；
}
else pr—>next=NULL;
return 0；
｝
}
｝
if(pr==NULL） printf（"错误！此分区不存在或未分配作业或前后分区都不空闲!\n"）;
else printf（”分区％s回收完毕！\n",pr—〉name）;
return 0；
｝
allocate(int s)｛
TABLE ＊pt=NULL，＊q;
for（pt=tab;pt!=NULL;pt=pt—>next）｛
if(pt—〉size>=s&&pt->state=='N'）{
pt—〉state=’D';
if(pt->size>s）{
q=getpch(TABLE）;
printf（”请输入分割出的分区ID:\n");
scanf（"％s"，q->name);
q—>size=pt—>size—s; /*分割分区*/
pt—〉size—=q->size;
q-〉state=’N’;
q—〉addr=pt-〉addr+pt—>size;
if（pt—>next！=NULL）{
pt-〉next->prev=q； /*在空闲链中插入新的分区*/
q->next=pt->next;
pt—〉next=q;
q-〉prev=pt;
return 0；
}
pt->next=q；
q—>prev=pt;
q->next=NULL;
}
return 0；
｝
｝/*for＊/
printf（"没有合适的分区，此次分配失败！\n”）;
return 0；
}
display(）{
TABLE *pt=tab；
if（pt==NULL) return 0；
printf("------—--空闲分区情况————-—--—\n”);
printf（"ID\t状态\t大小\t起始地址\n");
while(pt！=NULL)｛
printf(”％2s\t%3c\t%3d\t％5d\n”,pt—>name,pt->state，pt-〉size，pt->addr);
pt=pt—〉next；
｝
return 0;
｝

sorttable(）{ /*分区按升序排列*/
TABLE *first， ＊second；
if(tab==NULL){
p-〉next=tab;
tab=p;
｝
else｛
first=tab；
second=first—>next;
while（second！=NULL）{
first=first-〉next;
second=second->next;
｝
first->next=p;
}
}

InitTab(){
int num;
int i，paddr=0；
TABLE *pn; /＊指向前一结点*/
pn=NULL；
printf（”\t———---—Initialize table——————-\n\n")；
printf(”请输入分区个数:\n”）;
scanf（”%d"，＆num);
for(i=0；i<num;i++）｛
p=getpch（TABLE);
printf("输入分区NO。%d的ID：\n”，i)；
scanf（”％s",p—>name）；
p-〉state=’N'；
printf("输入分区大小:\n”);
scanf(”％d"，&p—>size)；
p—>addr=paddr;
paddr=p—〉addr+p-〉size;
p-〉prev=pn;
pn=p；
p—>next=NULL;
sorttable（）; /* 按分区起始地址排序*/
}

}

main(){
int ch=1；
int size;
char name[10］，c=’y';
UI（)；
InitTab（）；
system（"cls”）;
UI()；
display(）；
getch（);
system("cls");
while（c！=’n’＆＆c!=’N'）｛
UI（);
printf(”选择你要进行的操作\n1--分配作业\n2--回收分区\n0/其他--退出\n\n")；
scanf（”%d",&ch);
system（”cls"）;
switch（ch）
｛
case 1：
UI()；
display();
printf（"请输入作业大小：\n”)；
scanf(”％d”，＆size）；
allocate(size);
break;
case 2:
UI();
display()；
printf（"请输入待回收分区的ID:\n"）;
scanf（"％s”，name);
recycle(name)；
break;
case 0:
default ：exit(0）;
｝
display（)；
printf("是否继续？y/n\n")；
c=getch（);
system（”cls"）；
}
｝
截图：

五、实验小结
此次实验， 动手实践模拟在连续分配与分页管理两种方式下，主存空间的分配与回收,加深了解存储器管理的工作过程。尝试采用首次适应算法、循环首次适应算法、最佳适应算法其中的一种或多种算法实现动态分区分配,分页式主存管理系统等等.实验过程中，深刻了解了分页式与连续式之间的区别与相似处，更好的对主存管理、回收、装入等等有了更加深入的了解.