用C语言模拟实现可变式分区存储管理.docx
《用C语言模拟实现可变式分区存储管理.docx》由会员分享，可在线阅读，更多相关《用C语言模拟实现可变式分区存储管理.docx（14页珍藏版）》请在冰点文库上搜索。
用C语言模拟实现可变式分区存储管理
用C语言模拟实现可变式分区存储管理（总12页）
试验三：
用C语言模拟实现可变式分区存储管理
一、試驗目标：
1、通过编写可变式分区存储管理的C语言程序，使学生加强对可变式分区存储管理的认识。
2、掌握操作系统设计的基本原理、方法和一般步骤。
二、試驗内容：
用C語言編寫一個实现可变式的分区管理的模擬程序。
*复习相关的知识：
1、分区管理的原理：
将存储器划分成若干段大小固定的区域，一个区域里只能运行一个程序，程序只能在其自身所在的分区中活动。
2、固定式分区管理的原理：
区域大小及起始地址是固定的。
一个分区只能存放一个程序。
需要设置一个分区说明表来标明内存的使用状态。
根据分区说明表来给程序分配相应的区域。
由于程序不可能刚刚占有一个分区的大小，这样就会在一个分区之中留下零头，造成了极大的浪费。
3、可变式分区管理的原理：
区域的大小及起始地址是可变的，根据程序装入时的大小动态地分配一个区域。
保证每个区域之中刚好放一个程序。
这样可以充分地利用存储空间，提高内存的使用效率。
如果一个程序运行完毕，就要释放出它所占有的分区，使之变成空闲区。
这样就会出现空闲区与占用区相互交错的情况。
这样就需要P表，F表来分别表示内存的占用区状态与空闲区的状态。
*确定该系统所使用的数据结构：
我们可以把内存表示为一个数组的形式。
这个数组中的每一个单元都是一个无符号的字符型的数据类型。
这样一个单元刚好占用一个字节的大小。
这一个字节的地址可以用它在此数组中的下标来表示。
如果一个程序占用了一定的区域，那么这个区域的大小就可以用它占有的字节数的个数来表示。
用C语言可以表述如下：
unsignedcharmemory[1024]
它就可以表示一个1K的内存空间。
为了实现可变式的分区管理，还需要设立两个表，一个是P表，一个是F表，它们分别表示内存的占用区状态。
由于在该程序运行的过程之中需要不断地修改P表和F表，所以这两个表不适合于用数组的形式来表示；而应该使用单链表的形式。
这样就要给单链表中的结点确立一个数据结构。
很显然，P表中的每一个结点至少要包括以下的几项：
占用的程序名、占用区的起始地址、占用区的大小、指向下一个结点的指针。
F表中的结点可以不需要程序名这一项。
但是为了统一起见，我们就统一地采用P表中的这种结点的结构。
可以用C语言描述如下：
structnode
{
charname[10];
intstart,length;
structnode *next;
} ;
structnode *p,*f;
还要为它们确立一个初始的状态。
这两个链表最好带有一个头结点。
p=（structnode*）malloc（sizeof（structnode））;
p->next=NULL;
f=（structnode*）malloc（sizeof（structnode））;
f->next=（structnode*）malloc（sizeof（structnode））;
f->next->start=0;
f->next->length=1024;
f->next->next=NULL;
*、实现分配与回收一个占用区的算法：
1、分配函数的执行过程：
（按最佳分配法执行。
）
＃查找F表，在其中找到一个满足要求的空闲块。
如果没有找到则提示用户。
＃申请一个新的P结点，进行填写相关的数据，将其挂接在P表的尾部。
＃修改原空闲区结点，并将其从F表中提出来。
＃将修改后的结点插入到合适的位置，保证F表中的结点是按照地址空间的大小由小到大地进行排序。
＃返回新生成P表结点的首地址。
2、回收函数的执行过程：
＃查找P表，找到需要回收的程序的占用区结点。
将它提出P表。
＃生成一个新的空闲结点，填写它。
表示新生成了一个空闲区。
＃观察F表，看其中是否有旧的空闲区和新的空闲区相邻。
如果有，就将它与新的空闲区结合点合并成一个大的空闲区。
＃将新生成的空闲区结点插入到F表中的合适的位置。
三．试验要求：
设计一个可变长分区的存储器分配程序。
四．试验报告要求
1．写出试验目的
2。
写出试验要求
3。
写出试验内容（包括可变长分区算法描述、实验结果及分析）
附录1：
分配函数（fenpei）和回收函数（free）的C语言源程序：
intfenpei（char*c,introom,structnode*p,*f）
{
structnode*p1,*f1,*f2; /*f2是f1的跟随指针*/
f1=f->next; f2=f;
while（f1!
=NULL） /*查找F表，看是否有满足条件的一个结点，如果没有则提示出错了*/
{
if（f1->length>=room）
break;
f1=f1->next;f2=f2->next;
}
if（f1==NULL）
{
printf（"noenoughspace!
!
!
\n"）;
return（-1）;
} /*定位到P表的末尾，生成一个新的结点，联接到后面。
*/
p1=p;
while（p1->next!
=NULL）
p1=p1->next;
p1->next=（structnode*）malloc（sizeof（structnode））;
p1=p1->next;
p1->length=room;
strcpy（p1->name,c）;
p1->start=f1->start;
p1->next=NULL; /*修改F表中被分配的节点*/
f1->length=f1->length-room;
f1->start=f1->start+room;
f2->next=f1->next;
if（f1->length!
=0） /*如果修改后的节点大小为0，则舍弃之。
*/
{
f2=f;
while（（f2->next!
=NULL）&&（f2->next->length<=f1->length））
f2=f2->next;
f1->next=f2->next;
f2->next=f1;
}
return（p1->start）;
}
structnode*free（char*c,structnode*p,*f）
{
structnode*p1,*p2,*f1,*f2,*f3;
p1=p->next;
p2=p; /*p2是p1是跟随指针*/
while（p1!
=NULL）
/*按外界提供的程序名在P表中查找其结点，若没找到，则返回NULL*/
{
if（!
（strcmp（p1->name,c）））break;
p1=p1->next;
p2=p2->next;
}
if（p1==NULL）
{
printf（"Nofindtheprogram!
!
!
\n"）;
return（NULL）;
}
p2->next=p1->next; /*将找到的结点取出*/
f1=（structnode*）malloc（sizeof（structnode））;/*据此生成一个新的空闲结点*/
f1->start=p1->start;
f1->length=p1->length;
/*在F表中依次观察各个结点，看是否能与此新的空闲结点合并*/
f2=f->next;
f3=f;
while（f2!
=NULL）
{
if（f1->start+f1->length==f2->start）
{
f1->length+=f2->length;
f3->next=f2->next;
f2=f2->next;
}
elseif（f2->start+f2->length==f1->start）
{
f1->start=f2->start;
f1->length+=f2->length;
f3->next=f2->next;
f2=f2->next;
}
else{f2=f2->next; f3=f3->next;}
}
f2=f; /*再寻找一个合适的地方插入此空闲结点*/
while （（f2->next!
=NULL）&&（f2->next->length<=f1->length））
f2=f2->next;
f1->next=f2->next;
f2->next=f1;
return（f1）; /*返回值*/
}
附录2：
可变长分区存储分配完整程序
/*可变分区的模拟*/
#include
unsignedcharmemory[1024];
structnode
{
charname[5];
intstart,length;
structnode*next;
};
structnode*p,*f,*pp,*ff;
/*还要为它们确立一个初始的状态。
这两个链表最好带有一个头结点。
*/
structnode*free（char*c,structnode*p,structnode*f）;
main（）
{intt=1,xz;
charname[5];
unsignedintsize;
p=（structnode*）malloc（sizeof（structnode））;
p->next=NULL;
f=（structnode*）malloc（sizeof（structnode））;
f->next=（structnode*）malloc（sizeof（structnode））;
f->next->start=1;
f->next->length=1024;
f->next->next=NULL;
printf（"可变式内存管理模拟\n"）;
while（t==1）
{
printf（"1:
运行进程；2:
终止进程；3:
退出请选择：
"）;
scanf（"%d",&xz）;
switch（xz）
{case1:
{printf（"请输入请求进程的进程名（<=5个字符）：
"）;
scanf（"%s",name）;
printf（"请输入请求进程所需空间（起始可用内存1024）：
"）;
scanf（"%d",&size）;
fenpei（name,size,p,f）;
print（）;/*打印分配表空闲表*/
}
break;
case2:
{printf（"请输入终止进程的进程名：
"）;scanf（"%s,%d",name）;
ff=free（name,p,f）;
print（）;/*打印分配表空闲表*/
}
break;
case3:
t=0;break;
}
}
}
/*打印分配表空闲表函数*/
print（）
{/*打印分配表*/
printf（"分配表\n"）;
pp=p->next;
while（pp!
=NULL）
{printf（"%5s,%d,%d\n",pp->name,pp->start,pp->length）;pp=pp->next;}
/*打印空闲表*/
printf（"空闲表\n"）;
ff=f->next;
while（ff!
=NULL）
{printf（"%d,%d\n",ff->start,ff->length）;ff=ff->next;}
}
/*为进程分配空间函数*/
intfenpei（char*c,introom,structnode*p,structnode*f）
{structnode*p1,*f1,*f2;/*f2是f1的跟随指针*/
f1=f->next;f2=f;
while（f1!
=NULL）/*查找F表，看是否有满足条件的一个结点，如果没有则提示出错了*/
{if（f1->length>=room）
break;
f1=f1->next;f2=f2->next;}
if（f1==NULL）
{printf（"没有足够的空间，不能实施分配!
!
!
\n"）;
return（-1）;
}
/*定位到P表的末尾，生成一个新的结点，联接到后面。
*/
p1=p;
while（p1->next!
=NULL）
p1=p1->next;
p1->next=（structnode*）malloc（sizeof（structnode））;
p1=p1->next;
p1->length=room/*-1*/;
strcpy（p1->name,c）;
p1->start=f1->start;
p1->next=NULL;/*修改F表中被分配的节点*/
f1->length=f1->length-room;
f1->start=f1->start+room;
f2->next=f1->next;
if（f1->length!
=0）/*如果修改后的节点大小为0，则舍弃之。
*/
{f2=f;
while（（f2->next!
=NULL）&&（f2->next->length<=f1->length））
f2=f2->next;
f1->next=f2->next;
f2->next=f1;}
return（p1->start）;
}
/*回收进程所占空间函数*/
structnode*free（char*c,structnode*p,structnode*f）
{
structnode*p1,*p2,*f1,*f2,*f3;
p1=p->next;
p2=p;/*p2是p1是跟随指针*/
while（p1!
=NULL）
/*按外界提供的程序名在P表中查找其结点，若没找到，则返回NULL*/
{
if（!
（strcmp（p1->name,c）））break;
p1=p1->next;
p2=p2->next;
}
if（p1==NULL）
{
printf（"没找到该进程!
!
!
\n"）;
return（NULL）;
}
p2->next=p1->next;/*将找到的结点取出*/
f1=（structnode*）malloc（sizeof（structnode））;/*据此生成一个新的空闲结点*/
f1->start=p1->start;
f1->length=p1->length;
/*在F表中依次观察各个结点，看是否能与此新的空闲结点合并*/
f2=f->next;
f3=f;
while（f2!
=NULL）
{
if（f1->start+f1->length==f2->start）
{
f1->length+=f2->length;
f3->next=f2->next;
f2=f2->next;
}
elseif（f2->start+f2->length==f1->start）
{
f1->start=f2->start;
f1->length+=f2->length;
f3->next=f2->next;
f2=f2->next;
}
else{f2=f2->next;f3=f3->next;}
}
f2=f;/*再寻找一个合适的地方插入此空闲结点*/
while（（f2->next!
=NULL）&&（f2->next->length<=f1->length））
f2=f2->next;
f1->next=f2->next;
f2->next=f1;
return（f1）;/*返回值*/
}
升级会员 