试验三：用C语言模拟实现可变式分区存储管理
一、試驗目标：
1、通过编写可变式分区存储管理的C语言程序，使学生加强对可变式分区存储管理的认识。
2、掌握操作系统设计的基本原理、方法和一般步骤。
二、試驗内容：用C語言編寫一個实现可变式的分区管理的模擬程序。
*复习相关的知识：
1、分区管理的原理：将存储器划分成若干段大小固定的区域，一个区域里只能运行一个程序，程序只能在其自身所在的分区中活动。
2、固定式分区管理的原理：区域大小及起始地址是固定的。一个分区只能存放一个程序。需要设置一个分区说明表来标明内存的使用状态。根据分区说明表来给程序分配相应的区域。由于程序不可能刚刚占有一个分区的大小，这样就会在一个分区之中留下零头，造成了极大的浪费。
3、可变式分区管理的原理：区域的大小及起始地址是可变的，根据程序装入时的大小动态地分配一个区域。保证每个区域之中刚好放一个程序。这样可以充分地利用存储空间，提高内存的使用效率。如果一个程序运行完毕，就要释放出它所占有的分区，使之变成空闲区。这样就会出现空闲区与占用区相互交错的情况。这样就需要P表，F表来分别表示内存的占用区状态与空闲区的状态。
*确定该系统所使用的数据结构：
我们可以把内存表示为一个数组的形式。这个数组中的每一个单元都是一个无符号的字符型的数据类型。这样一个单元刚好占用一个字节的大小。这一个字节的地址可以用它在此数组中的下标来表示。如果一个程序占用了一定的区域，那么这个区域的大小就可以用它占有的字节数的个数来表示。用C语言可以表述如下：
unsigned char memory[1024]
它就可以表示一个1K的内存空间。
为了实现可变式的分区管理，还需要设立两个表，一个是P表，一个是F表，它们分别表示内存的占用区状态。由于在该程序运行的过程之中需要不断地修改P表和F表，所以这两个表不适合于用数组的形式来表示；而应该使用单链表的形式。这样就要给单链表中的结点确立一个数据结构。很显然，P表中的每一个结点至少要包括以下的几项：占用的程序名、占用区的起始地址、占用区的大小、指向下一个结点的指针。F表中的结点可以不需要程序名这一项。但是为了统一起见，我们就统一地采用P 表中的这种结点的结构。可以用C语言描述如下：
struct node
{
char name[10];
int start, length;
struct node*next;
};
struct node*p, *f;
还要为它们确立一个初始的状态。这两个链表最好带有一个头结点。
p = (struct node *)malloc (sizeof(struct node));
p->next = NULL;
f = (struct node *) malloc (sizeof(struct node));
f->next = (struct node *)malloc (sizeof(struct node));
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语言源程序：
int fenpei(char *c, int room, struct node *p, *f)
{
struct node *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("no enough space!!!\n");
return (-1);
}/*定位到P表的末尾，生成一个新的结点，联接到后面。*/
p1 = p;
while(p1->next != NULL)
p1 = p1 ->next;
p1->next = (struct node *)malloc(sizeof(struct node));
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->leng th<= f1->length))
f2 = f2 ->next;
f1 ->next = f2 ->next;
f2->next = f1;
}
return (p1->start) ;
}
struct node *free (char *c, struct node *p, *f)
{
struct node *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("No find the program!!!\n");
return (NULL);
}
p2->next = p1 -> next ;/*将找到的结点取出*/
f1 = (struct node *)malloc(sizeof(struct node));/*据此生成一个新的空闲结点*/
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->le ngth += f2->length;
f3->ne xt = f2->next;
f2 =
f2->next;
}
else if (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->l ength))
f2 = f2->next;
f1->next = f2->next;
f2 ->next = f1;
return (f1);/*返回值*/
}
附录2：可变长分区存储分配完整程序
/*可变分区的模拟*/
#include
unsigned char memory[1024];
struct node
{
char name[5];
int start,length;
struct node *next;
} ;
struct node *p, *f, *pp,*ff;
/* 还要为它们确立一个初始的状态。这两个链表最好带有一个头结点。*/
struct node *free(char *c, struct node *p,struct node *f);
main()
{ int t=1,xz;
char name[5];
unsigned int size;
p = (struct node *)malloc (sizeof(struct node));
p->next = NULL;
f = (struct node *) malloc (sizeof(struct node));
f->next = (struct node *)malloc (sizeof(struct node));
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)
{ case 1:
{printf("请输入请求进程的进程名(<=5个字符)：");
scanf("%s",name);
printf("请输入请求进程所需空间(起始可用内存1024）：");
scanf("%d",&size);
fenpei(name,size,p,f);
print(); /*打印分配表空闲表*/
}
break;
case 2: {printf("请输入终止进程的进程名：");scanf("%s,%d",name);
ff=free(name,p,f );
print();/*打印分配表空闲表*/
}
break;
case 3: 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;}
}
/*为进程分配空间函数*/
int fenpei(char *c, int room, struct node *p,struct node *f)
{ struct node *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 = (struct node *)malloc(sizeof(struct node));
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) ;
}
/*回收进程所占空间函数*/
struct node *free(char *c, struct node *p,struct node *f)
{
struct node *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 = (struct node *)malloc(sizeof(struct node));/*据此生成一个新的空闲结点*/ 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;
}
else if (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); /*返回值*/
}