3.用C语言模拟实现可变式分区存储管理

试验三：用C语言模拟实现可变式分区存储管理一、試驗目标： 1、通过编写可变式分区存储管理的C语言程序，使学生加强对可变式分区存储管理的认识。 2、掌握操作系统设计的基本原理、方法和一般步骤。二、試驗内容：用C語言編寫一個实现可变式的分区管理的模擬程序。 *复习相关的知识： 1、分区管理的原理：将存储器划分成若干段大小固定的区域，一个区域里只能运行一个程序，程序只能在其自身所在的分区中活动。 2、固定式分区管理的原理：区域大小及起始地址是固定的。一个分区只能存放一个程序。需要设置一个分区说明表来标明内存的使用状态。根据分区说明表来给程序分配相应的区域。由于程序不可能刚刚占有一个分区的大小 ，这样就会在一个分区之中留下零头，造成了极大的浪费。 3、可变式分区管理的原理：区域的大小及起始地址是可变的，根据程序装入时的大小动态地分配一个区域。保证每个区域之中刚好放一个程序。这样可以充分地利用存储空间，提高内存的使用效率。如果一个程序运行完毕，就要释放出它所占有的分区，使之变成空闲区。这样就会出现空闲区与占用区相互交错的情况。这样就需要P表，F表来分别表示内存的占用区状态与空闲区的状态。 *确定该系统所使用的数据结构： 我们可以把内存表示为一个数组的形式。这个数组中的每一个单元都是一个无符号的字符型的数据类型。这样一个单元刚好占用一个字节的大小。这一个字节的地址可以用它在此数组中的下标来表示。如果一个程序占用了一定的区域，那么这个区域的大小就可以用它占有的字节数的个数来表示。用C语言可以表述如下： unsigned char memory1024 它就可以表示一个1K的内存空间。 为了实现可变式的分区管理，还需要设立两个表，一个是P表，一个是F表，它们分别表示内存的占用区状态。由于在该程序运行的过程之中需要不断地修改P表和F表，所以这两个表不适合于用数组的形式来表示；而应该使用单链表的形式。这样就要给单链表中的结点确立一个数据结构。很显然，P表中的每一个结点至少要包括以下的几项：占用的程序名、占用区的起始地址、占用区的大小、指向下一个结点的指针。F表中的结点可以不需要程序名这一项。但是为了统一起见，我们就统一地采用P表中的这种结点的结构。可以用C语言描述如下： struct node char name10; 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-lengthlength) 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-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-lengthlength) f2 = f2-next; f1-next = f2-next; f2 -next = f1; return (f1); /*返回值*/ 附录2：可变长分区存储分配完整程序/*可变分区的模拟*/ #include unsigned char memory1024; struct node char name5; 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 name5; 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(请输入请求进程的进程名(next; while (pp!=NULL) printf(%5s,%d,%dn,pp-name,pp-start, pp-length);pp=pp-next; /*打印空闲表 */ printf(空闲表n); ff=f-next; while (ff!=NULL) printf( %d,%dn,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-lengthlength) 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