12.txt

用C实现的可变分区管理教案

用C语言模拟实现可变式分区存储管理（教案）- -
                                       


教学目标：
   1、通过编写可变式分区存储管理的C语言程序，使学生加强对可变式分区存储管理的认识。
   2、掌握操作系统设计的基本原理、方法和一般步骤。
   3、复习巩固C语言的一些基础知识、函数、指针的使用，感受用C语言编制系统软件的优越性。
     4、复习巩固单链表这种数据结构的操作方法。
教学的重点和难点：
   1、如何确立程序设计的思路及其步骤。
   2、如何选择合适的数据结构与对应的算法。
   3、如何使用模块化、自顶向下的方式来编制程序。


 



用C语言模拟实现可变式分区存储管理（教案）

教学目标：
   1、通过编写可变式分区存储管理的C语言程序，使学生加强对可变式分区存储管理的认识。
   2、掌握操作系统设计的基本原理、方法和一般步骤。
   3、复习巩固C语言的一些基础知识、函数、指针的使用，感受用C语言编制系统软件的优越性。
     4、复习巩固单链表这种数据结构的操作方法。
教学的重点和难点：
   1、如何确立程序设计的思路及其步骤。
   2、如何选择合适的数据结构与对应的算法。
   3、如何使用模块化、自顶向下的方式来编制程序。

教学内容：
  一、复习相关的知识：
   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、对每个模块确定它的数据结构和算法，搞清楚它的大致的步骤。
        4、对每个步骤逐步细化，直至以某种语言将其编写出来。
        5、充分考虑不同的情况，不断地修改直至完善。

                                                              任课教师：罗进

 

附录：
   分配函数（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->length<= 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 = p ->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);             /*返回值*/
               }