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

1、word可编辑试验三：用C语言模拟实现可变式分区存储管理一、試驗目标：   1、通过编写可变式分区存储管理的C语言程序，使学生加强对可变式分区存储管理的认识。   2、掌握操作系统设计的根本原理、方法和一般步骤。 二、試驗内容：用C語言編寫一個实现可变式的分区管理的模擬程序。  *复习相关的知识：   1、分区管理的原理：将存储器划分成假设干段大小固定的区域，一个区域里只能运行一个程序，程序只能在其自身所在的分区中活动。   2、固定式分区管理的原理：区域大小及起始地址是固定的。一个分区只能存放

2、一个程序。需要设置一个分区说明表来标明内存的使用状态。根据分区说明表来给程序分配相应的区域。由于程序不可能刚刚占有一个分区的大小 ，这样就会在一个分区之中留下零头，造成了极大的浪费。  3、可变式分区管理的原理：区域的大小及起始地址是可变的，根据程序装入时的大小动态地分配一个区域。保证每个区域之中刚好放一个程序。这样可以充分地利用存储空间，提高内存的使用效率。如果一个程序运行完毕，就要释放出它所占有的分区，使之变成空闲区。这样就会出现空闲区与占用区相互交错的情况。这样就需要P表，F表来分别表示内存的占用区状态与空闲区的状态。  *确定该系统所使用的数据结构： &#

3、160;    我们可以把内存表示为一个数组的形式。这个数组中的每一个单元都是一个无符号的字符型的数据类型。这样一个单元刚好占用一个字节的大小。这一个字节的地址可以用它在此数组中的下标来表示。如果一个程序占用了一定的区域，那么这个区域的大小就可以用它占有的字节数的个数来表示。用C语言可以表述如下：    unsigned char memory1024    它就可以表示一个1K的内存空间。    为了实现可变式的分区管理，还需要设立两个表，一个是P表，一个是F表，它们分别表

4、示内存的占用区状态。由于在该程序运行的过程之中需要不断地修改P表和F表，所以这两个表不适合于用数组的形式来表示；而应该使用单链表的形式。这样就要给单链表中的结点确立一个数据结构。很显然，P表中的每一个结点至少要包括以下的几项：占用的程序名、占用区的起始地址、占用区的大小、指向下一个结点的指针。F表中的结点可以不需要程序名这一项。但是为了统一起见，我们就统一地采用P表中的这种结点的结构。可以用C语言描述如下：   struct node           char name10; &#

5、160;        int start, length;         struct node  *next;             ;     struct node  *p, *f;    还要为它们确立一个初始的状态。这两个链表最好带有一个头结点

6、。     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 -> le

7、ngth = 1024;   f->next ->next = NULL;  *、实现分配与回收一个占用区的算法：    1、分配函数的执行过程：按最正确分配法执行。       查找F表，在其中找到一个满足要求的空闲块。如果没有找到那么提示用户。       申请一个新的P结点，进行填写相关的数据，将其挂接在P表的尾部。       修改原空闲

8、区结点，并将其从F表中提出来。       将修改后的结点插入到适宜的位置，保证F表中的结点是按照地址空间的大小由小到大地进行排序。       返回新生成P表结点的首地址。    2、回收函数的执行过程：       查找P表，找到需要回收的程序的占用区结点。将它提出P表。       生成一个新的空闲结点，填写它。表示新生成

9、了一个空闲区。       观察F表，看其中是否有旧的空闲区和新的空闲区相邻。如果有，就将它与新 的空闲区结合点合并成一个大的空闲区。       将新生成的空闲区结点插入到F表中的适宜的位置。三试验要求：设计一个可变长分区的存储器分配程序。四试验报告要求1写出试验目的 2。写出试验要求 3。写出试验内容包括可变长分区算法描述、实验结果及分析附录1：   分配函数fenpei和回收函数free的C语言源程序：    

10、     int fenpei(char *c, int room, struct node *p, *f)                             struct node *p1, *f1, *f2;      

11、                              /*f2是f1的跟随指针*/                 f1 = f->nex

12、t;  f2 = f;                while (f1!=NULL)    /*查找F表，看是否有满足条件的一个结点，如果没有那么提示出错了*/                    

13、60;                          if (f1->length >=room)                   

14、0;          break;                           f1 = f1 -> next; f2 = f2->next;       &

15、#160;                              if (f1 = NULL)                  

16、60;                                 printf("no enough space!n");            

17、;                    return (-1);                        /*定位到P表的末尾，生成一个新的结点，联接到后面。*/ 

18、0;                                 p1 = p;                 while(

19、p1->next != NULL)                        p1 = p1 ->next;                  p1->next = (struc

20、t node *)malloc(sizeof(struct node);                  p1 = p1->next ;                  p1->length = room;   &

21、#160;              strcpy(p1->name, c);                  p1->start = f1 -> start;          

22、        p1->next = NULL;                   /*修改F表中被分配的节点*/                  f1->leng

23、th = f1->length - room;                  f1->start = f1->start + room;                  f2->next = f1 ->next; 

24、                               if (f1->length !=0)                 

25、  /*如果修改后的节点大小为0，那么舍弃之。*/                                             f2 = f;

26、60;                         while(f2->next!=NULL)&&(f2->next->length<= f1->length)            

27、60;                  f2 = f2 ->next;                         f1 ->next = f2 ->next;

28、60;                        f2->next = f1;                         &

29、#160;                               return (p1->start) ;                 

30、;      struct node *free (char *c, struct node *p, *f)                                     struct no

31、de *p1, *p2, *f1, *f2, *f3;                    p1 = p->next ;                   p2 = p;    &

32、#160;                     /*p2是p1是跟随指针*/                    while(p1!= NULL)     

33、;                                 /*按外界提供的程序名在P表中查找其结点，假设没找到，那么返回NULL*/            &#

34、160;                                            if (!(strcmp(p1->name,c) break; &#

35、160;                             p1 = p1->next;                  &#

36、160;            p2 = p2->next;                                    &

37、#160;           if (p1=NULL)                                      

38、;                    printf("No find the program!n");                       

39、0;             return (NULL);                                    

40、        p2->next = p1 -> next ;             /*将找到的结点取出*/                    f1 = (struct node *)malloc(s

41、izeof(struct node);/*据此生成一个新的空闲结点*/                    f1->start = p1 ->start ;                    f1 -&

42、gt;length = p1 ->length;                     /*在F表中依次观察各个结点，看是否能与此新的空闲结点合并*/                    f2 = f

43、->next;                      f3 = f;                           

44、0;              while (f2!= NULL)                                  

45、60;                          if (f1->start + f1 ->length = f2->start)                &

46、#160;                                                  

47、            f1->length += f2->length;                                 

48、0;        f3->next = f2->next;                                      &

49、#160;  f2 = f2->next;                                              

50、                            else if (f2->start + f2->length = f1->start )              

51、;                                                  

52、0;                       f1->start = f2 ->start;                       

53、60;                        f1 ->length += f2->length;                     

54、                          f3 ->next = f2 ->next ;                    

55、                           f2 = f2->next;                     

56、                                                   

57、;     else f2=f2->next ;   f3 = f3->next;                                      

58、          f2 = f;   /*再寻找一个适宜的地方插入此空闲结点*/                    while  (f2->next!=NULL)&&(f2->next->length<=f1->length) 

59、                            f2 = f2->next;                   f1->next

60、 = f2->next;                   f2 ->next = f1;                    return (f1);     &

61、#160;       /*返回值*/               附录2：可变长分区存储分配完整程序/*可变分区的模拟*/ #include<stdio.h> unsigned char memory1024; struct node char name5; int start,length; struct node *next; ; struct node *p, *f, *pp,

62、*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

63、 (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(

64、"%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,%dn",pp->name,pp->start, pp->length);pp=pp->next; /*打印空闲表 */ printf(