操作系统实验报告---主存分配与回收（最佳适应算法）

   动态分区主存的分配与回收

                                                                      16网络工程二班 孙书魁

目的：

           1，了解动态分区分配中，使用的数据结构和算法

          2，深入了解动态分区存储管理方式，主存分配与回收的实现

          3，进一步加深动态分区存储管理方式及其实现过程的了解

具体实现：

            确定主存分配表，然后采用最佳适应算法，完成完成主存分配和回收，最后编写主函数，进行主函数进行测试。

具体实现：

            主存分配之前的之态，主存分配过程中的状态，回收后的状态

#include <stdio.h>   
#include <string.h>
#define MAX 600  //设置总内存大小为512k

struct partition {
    char    pn[10];//分区名字
    int     begin;//起始地址
    int     size;//分区大小 
    int     end;//结束地址
    char    status;//分区状态
 };
 struct partition    part[MAX];
 int    p = 0; //标记上次扫描结束处 
 
 void Init()//初始化分区地址、大小以及状态
{
    int i;
    for ( i = 0; i < MAX; i++ )
         part[i].status = '-';
     strcpy( part[0].pn, "SYSTEM" );
     part[0].begin    = 0;
     part[0].size    = 100;
     part[0].status    = 'u';
  
     strcpy( part[1].pn, "-----" );
     part[1].begin    = 100;
     part[1].size    = 100;
     part[1].status    = 'f';
     strcpy( part[2].pn, "A" );
     part[2].begin    = 200;
     part[2].size    = 50;
     part[2].status    = 'u';
     strcpy( part[3].pn, "-----" );
     part[3].begin    = 250;
     part[3].size    = 50;
     part[3].status    = 'f';
     strcpy( part[4].pn, "B" );
     part[4].begin    = 300;
     part[4].size    = 100;
     part[4].status    = 'u';
     strcpy( part[5].pn, "-----" );
     part[5].begin    = 400;
     part[5].size    = 200;
     part[5].status    = 'f';
     for ( i = 0; i < MAX; i++ )
         part[i].end = part[i].begin + part[i].size-1;
 }
  

  void Output( int i ) //以行的形式输出结构体的数据
 {
     printf( "\t%s", part[i].pn );
     printf( "\t%d", part[i].begin );
     printf( "\t%d", part[i].size );
     printf( "\t%d", part[i].end );
     printf( "\t%c", part[i].status );
 }
 

 void display() //显示分区 
 {
     int    i;
     int    n; //用n来记录分区的个数
	 printf("\n");
     printf( "\n        已分配分区表Used:" );
     printf( "\n\tNo.\tproname\tbegin\tsize\tend\tstatus" );
	 printf("\n");
     n = 1;
     for ( i = 0; i < MAX; i++ )
     {
         if ( part[i].status == '-' )
             break;
         if ( part[i].status == 'u' )
         {
             printf( "\n\tNo.%d", n );
             Output( i );
             n++;// 记录已分配使用的分区个数
         }
     }
	 printf("\n");
     printf( "\n        空闲分区表Free:" );
     printf( "\n\tNo.\tproname\tbegin\tsize\tend\tstatus" );
	 printf("\n");
     n = 1;
     for ( i = 0; i < MAX; i++ )
     {
         if ( part[i].status == '-' )
              break;
        if ( part[i].status == 'f' )
          {
              printf( "\n\tNo.%d", n );
           Output( i );
              n++;  //记录空闲分区的个数
          }
    }
    // printf( "\n" );
	 printf("\n");
     printf( "\n        内存使用情况，按起始址增长的排:" );
     //printf( "\n        printf sorted by address:" );
     printf( "\n\tNo.\tproname\tbegin\tsize\tend\tstatus" );
	 printf("\n");
     n = 1;
     for ( i = 0; i < MAX; i++ )
     {
         if ( part[i].status == '-' )
             break;
         printf( "\n\tNo.%d", n );
         Output( i );
        n++;//记录已分配分区以及空闲分区之和的总个数
    }
     getch();
 }
 
 void Fit( int a, char workName[], int workSize ) //新作业把一个分区分配成两个分区：已使用分区和空闲分区 
 {
     int i;
     for ( i = MAX; i > a + 1; i-- )
     {
        //通过逆向遍历，把在a地址后的所有分区往后退一个分区，目的在于增加一个分区
         if ( part[i - 1].status == '-' )
             continue;
         part[i]=part[i-1];
    }
     strcpy( part[a + 1].pn, "-----" );
     part[a + 1].begin    = part[a].begin + workSize;
     part[a + 1].size    = part[a].size - workSize;
     part[a + 1].end        = part[a].end-1;
     part[a + 1].status    = 'f';
    strcpy( part[a].pn, workName );
     part[a].size    = workSize;
     part[a].end    = part[a].begin + part[a].size-1;
     part[a].status    = 'u';
 }
 void fenpei() // 分配 
 {
     int    i;
     int    a;
    int    workSize;
     char    workName[10];
     int    pFree;
     printf( "\n请输入作业名称：" );
     scanf( "%s", &workName );
     for(i=0;i<MAX;i++)
    {
         if(!strcmp(part[i].pn,workName))//判断作业名称是否已经存在
         {
             printf("\n作业已经存在，不必再次分配！\n");
            return;
         }
     }
     printf( "请输入作业大小(k)：" );
     scanf( "%d", &workSize );
     for ( i = 0; i < MAX; i++ )//通过循环在空闲区找是否有适合区间存储作业
     {
         if ( part[i].status == 'f' && part[i].size >= workSize )
         {
             pFree = i;
             break;
         }
    }
    if ( i == MAX )
    {
         printf( "\n该作业大小超出最大可分配空间" );
         getch();
         return;
     }
     
         for ( i = 0; i < MAX; i++ )//最佳适应算法
            if ( part[i].status == 'f' && part[i].size >= workSize )
                 if ( part[pFree].size > part[i].size )
                     pFree = i;//通过遍历所有区间，每次都找到最小空闲分区进行分配
         Fit( pFree, workName, workSize );
    printf( "\n分配成功！" );
    getch();
 }
 void hebing() //合并连续的空闲分区 
 {
    int i = 0;
    while ( i != MAX - 1 )
    {
        for ( i = 0; i < MAX - 1; i++ )
        {
            if ( part[i].status == 'f' )
                 if ( part[i + 1].status == 'f' )
                {
                     part[i].size    = part[i].size + part[i + 1].size;
                     part[i].end    = part[i].begin + part[i].size-1;
                     i++;
                     for ( i; i < MAX - 1; i++ )
                    {
                        if ( part[i + 1].status == '-' )
                        {
                            part[i].status = '-';
                            break;
  
                        }
						
                        part[i]=part[i+1];
                    }
                     part[MAX - 1].status = '-';
                     break;
                 }
        }
    }
 }
 
 
 void huishou() // 回收分区 
 {
     int    i;
     int    number;
     int    n=0;
     printf( "\n请输入回收的分区号：" );
     scanf( "%d", &number );
     if ( number == 1 )
     {
         printf( "\n系统分区无法回收" );
         return;
     }
     for ( i = 0; i < MAX; i++ )//通过循环查找要回收的已使用分区区号
     {
         if ( part[i].status == 'u' )
         {
             n++;
             if ( n == number )
            {
                 strcpy( part[i].pn, "-----" );
                 part[i].status = 'f';
            }
         }
     }
     if ( i == MAX - 1 )
     {
         printf( "\n找不到分区" );
         return;
     }
     hebing();//合并连续的空闲分区
     printf( "\n回收成功！" );
     getch();
 }
 
 
 void main()
{
     int selection;
     Init();
     printf( "初始化完成，设内存容量%dk", MAX );
     printf( "\n系统文件从低址存储，占%dk", part[0].size );
     while ( 1 )
     {
         printf( "\n----------选择----------" );
         printf( "\n|  0、退出系统         |" );
         printf( "\n|  1、显示分区         |" );
         printf( "\n|  2、分配分区         |" );
         printf( "\n|  3、回收分区         |" );
		 printf( "\n------------------------");
        printf( "\n请选择 > " );
         while ( 1 )
         {
             scanf( "%d", &selection );
             if ( selection == 0 ||selection == 1 || selection == 2 || selection == 3 )
                 break;
             printf( "输入错误，请重新输入：" );
         }
         switch ( selection )
         {
           case 0:
           exit(0); //退出系统
             break;
         case 1:
             display(); //显示分区
             break;
        case 2:
             fenpei(); //分配作业
             break;
         case 3:
             huishou();  //回收分区
             break;
         default:
             break;
         }
     }
 }