合肥学院计算机科学与技术系实验报告2013 ～2014 学年第一学期课程操作系统原理实验名称模拟实现一个简单的可变分区存储管理系统学生姓名专业班级指导教师谢雪胜2013 年12 月1．实验目的模拟实现一个简单的固定（或可变）分区存储管理系统2．实验内容本实验要求完成如下任务：（1）建立相关的数据结构，作业控制块、已分配分区及未分配分区（2）实现一个分区分配算法，如最先适应分配算法、最优或最坏适应分配算法（3）实现一个分区回收算法（4）给定一批作业/进程，选择一个分配或回收算法，实现分区存储的模拟管理。

3．实验步骤（1）任务分析本实验要实现的功能是模拟分区管理系统，即输入一个批作业，由程序根据各个作业的大小为批作业分配分区。

如果能找到满足条件的分区，则分配成功，否则分配失败。

对于程序的输入，输入用户程序所要请求的分区大小，-1表示输入完成。

程序输入分配分区后各个分区的使用情况，然后回收分区，程序输出回收分区后各个分区的使用情况。

（2）概要设计对于分区的定义，定义的数据结构如下所示typedef struct{int no; //定义分区编号int size; //定义大小int start; //定义分区起始位置int state; //定义分区状态，已分配或未分配}fenqubiao;fenqubiao arr[50];其中，no表示分区的编号，size表示当前分区块的大小，start表示当前分区的起始位置，state表示当前分区的状态，已分配或空闲。

Arr[50]表示当前系统所有分区情况。

主程序的流程图如下：（3）详细设计一、初始化分区Fenqubiao arr[50]={{1,10,0,0},{2,20,10,1},{3,10,30,0},{4,12,40,0},{5,30,52,1},{6,25,82,0},{7,20,107,0},{8,5,127,1},{9,64,132,0},{10,32,196,0}};二、分区分配函数采用的分区分配函数是最先适应法，每次从地址部分开始遍历。

本程序用的是编号作为遍历的关键字，方便处理。

如果当前分区的大小大于所请求的大小，并且分区处于空闲状态，则进行分区，划出满足请求大小的分区，并修改状态为已分配。

如果所划分分区所剩空间不为0，则修改其首址，设定其大小，添加到分区表中。

如果当前分区不满足请求，则继续查找，直至所有分区遍历完成。

然后返回分配失败给请求者。

具体代码如下：int fun_allocate(int x,int *num,fenqubiao *arr){int i=0,p;fenqubiao t={0,0,0,0};for(i=0;i<*num;i++){if(arr[i].size>=x && arr[i].state==0) break;0 10 30 40 52 82 107 127 132 196 228if(i==*num)return 0;p=i;t.no=arr[i].no+1;t.size=arr[i].size-x;t.start=arr[i].start+x;t.state=0;arr[i].size=x;arr[i].state=1;if(t.size!=0){for(i=*num;i>p;i--){arr[i]=arr[i-1];arr[i].no=arr[i].no+1;}arr[p+1]=t;*num=*num+1;}return *num;}三、输出分区使用情况对分区表进行遍历，输出各个分区的信息（编号，大小，起始，状态）。

其中为了简单易懂，若状态为0则输出空闲，否则输出已分配。

void fun_print(fenqubiao *arr,int num){int i=0;printf("编号大小起始状态\n");for(i=0;i<num;i++)printf("%2d%7d%7d",arr[i].no,arr[i].size,arr[i].start);if(arr[i].state==1)printf(" 已分配\n");elseprintf(" 空闲\n");}}四、回收分区对所要回收的分区，则有四种情况。

1、上临空闲，下临空闲：修改上一个分区大小为三个分区大小之和，下临区之后的分区改变其分区编号，往前移两个。

2、上临空闲：修改上一个分区大小为两个分区大小之和，下临区之后的分区上移一个单位。

3、下临空闲：修改当前分区大小为两个分区大小之和，修改状态为未分配。

然后下临区之后的分区上移一个单位。

4、上下均无空闲：直接修改状态为未分配。

如果具体代码如下:void fun_huishou(int no,int *num,fenqubiao *arr){int i=0;int p=0;for(i=1;i<=*num;i++){if(arr[i].no==no){p=i;break;}}if(arr[p-1].state==0 && arr[p+1].state==0)//上下临区arr[p-1].size=arr[p-1].size+arr[p].size+arr[p+1].size;for(i=p;i<*num-1;i++){arr[i]=arr[i+2];arr[i].no=arr[i].no-2;}*num=*num-2;}else if(arr[p+1].state==0)//下临区{arr[p].size=arr[p].size+arr[p+1].size;arr[p].state=0;for(i=p+1;i<*num;i++){arr[i]=arr[i+1];arr[i].no=arr[i].no-1;}*num=*num-1;}else if(arr[p-1].state==0) //上临区{arr[p-1].size=arr[p-1].size+arr[p].size;for(i=p;i<*num;i++){arr[i]=arr[i+1];arr[i].no=arr[i].no-1;}*num=*num-1;}else //无相邻分区{arr[p].state=0;}}(4)调试分析实验结果截图如下：4．实验总结首次适应算法，分配时，当进程申请大小为SIZE的内存时，系统从空闲区表的第一个表目开始查询，直到首次找到等于或大于SIZE的空闲区。

从该区中划出大小为SIZE的分区分配给进程，余下的部分仍作为一个空闲区留在空闲区表中，但要修改其首址和大小。

回收时，按释放区的首址，查询空闲区表，若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个空闲区，将其大小和首址按照首地址大小递增的顺序插入到空闲区表的适当位置。

这里，采用数组的方式，模拟内存分配首次适应算法，动态的为作业分配内存块。

可以根据作业名称回收已分配的内存块，当空闲内存块相邻时，则合并，不相邻是，直接插入。

通过此次的实验，让我对内存分配中首次适应算法更加熟悉，还通过这次实验了解了分配空间的另外两种方法：最佳和最坏算法。

通过编程模拟实现操作系统的可变分区存储管理的功能，一方面加深对原理的理解，另一方面提高根据已有原理通过编程解决实际问题的能力，为进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。

5．附录程序源代码#include <stdio.h>typedef struct{int no; //定义分区编号int size; //定义大小int start; //定义分区起始位置int state; //定义分区状态，已分配或未分配}fenqubiao;int fun_allocate(int x,int *num,fenqubiao *arr);//分区算法,分配成功返回分区数，否则返回0void fun_print(fenqubiao *arr,int num); //输出当前分区表状态void fun_huishou(int no,int *num,fenqubiao *arr);int main(){fenqubiaoarr[50]={{1,10,0,0},{2,20,10,1},{3,10,30,0},{4,12,40,0},{5,30,52,1}, {6,25,82,0},{7,20,107,0},{8,5,127,1},{9,64,132,0},{10,32,196,0}};int num=10; //用于统计分区个数int i=0,x,t;puts("||====================操作系统大实验==================||");puts("|| ||");puts("|| 题目：模拟实现一个可变分区存储管理系统 ||");puts("|| ||");puts("|| ||");puts("|| 制作者信息： ||");puts("|| ||");puts("|| 姓名学号 ||");puts("|| 万定国 1104032034 ||");puts("|| 刘国庆 1104032035 ||");puts("|| 许成谦 1104032036 ||");puts("|| 祁益祥 1104032037 ||");puts("|| 朱旭 1104032038 ||");puts("|| ||");puts("||====================================================||");system("pause");system("cls");printf("初始分区情况:\n");printf("编号大小起始状态\n");for(i=0;i<10;i++){printf("%2d%7d%7d",arr[i].no,arr[i].size,arr[i].start);if(arr[i].state==1)printf(" 已分配\n");elseprintf(" 空闲\n");}printf("====请求资源====\n");printf("输入请求大小(-1结束):\n");while(scanf("%d",&x) && x!=-1){t=fun_allocate(x,&num,arr);if(t==0)printf("分配失败!\n");else{num=t;fun_print(arr,num);}}printf("====回收资源=====\n");printf("请输入回收分区的编号(-1结束):\n");while(scanf("%d",&x) && x!=-1){fun_huishou(x,&num,arr);fun_print(arr,num);}}int fun_allocate(int x,int *num,fenqubiao *arr) {int i=0,p;fenqubiao t={0,0,0,0};for(i=0;i<*num;i++){if(arr[i].size>=x && arr[i].state==0)break;}if(i==*num)return 0;p=i;t.no=arr[i].no+1;t.size=arr[i].size-x;t.start=arr[i].start+x;t.state=0;arr[i].size=x;arr[i].state=1;if(t.size!=0){for(i=*num;i>p;i--){arr[i]=arr[i-1];arr[i].no=arr[i].no+1;}arr[p+1]=t;*num=*num+1;}return *num;}void fun_print(fenqubiao *arr,int num){int i=0;printf("编号大小起始状态\n");for(i=0;i<num;i++){printf("%2d%7d%7d",arr[i].no,arr[i].size,arr[i].start);if(arr[i].state==1)printf(" 已分配\n");elseprintf(" 空闲\n");}}void fun_huishou(int no,int *num,fenqubiao *arr){int i=0;int p=0;for(i=1;i<=*num;i++){if(arr[i].no==no){p=i;break;}}if(arr[p-1].state==0 && arr[p+1].state==0)//上下临区{arr[p-1].size=arr[p-1].size+arr[p].size+arr[p+1].size;for(i=p;i<*num-1;i++){arr[i]=arr[i+2];arr[i].no=arr[i].no-2;}*num=*num-2;}else if(arr[p+1].state==0)//下临区{arr[p].size=arr[p].size+arr[p+1].size;arr[p].state=0;for(i=p+1;i<*num;i++){arr[i]=arr[i+1];arr[i].no=arr[i].no-1;}*num=*num-1;}else if(arr[p-1].state==0) //上临区{arr[p-1].size=arr[p-1].size+arr[p].size;for(i=p;i<*num;i++){arr[i]=arr[i+1];arr[i].no=arr[i].no-1;}*num=*num-1;}else //无相邻分区{arr[p].state=0;}}。