操作系统实验报告②_编写c语言程序,模拟实现首次、最佳、最坏适应三种算法的内存块分配和回收。假

编写C语言程序，模拟实现首次/最佳/最坏适应算法(选择其中之一即可)的内存块分配和回收，要求每次分配和回收后显示出空闲分区和已分配分区的情况。假设初始状态下，可用的内存空间为640KB。

假设下列作业请求序列：

（1）作业1 申请130 KB （2）作业2 申请60 KB （3）作业3 申请100 KB

（4）作业2 释放60 KB （5）作业3 释放100 KB （6）作业1 释放130 KB

显示每次作业申请或释放后当前内存情况。

分析设计：

分析设计如下：

（1）程序初始需要提供用户选择方式。选择首次适应算法，还是最佳是适应算法，选择作业的回收，作业的展示，程序的退出能。

（2）当用户选择首次适应算法或者最佳适应算法，需要用户输入分配内存的大小。在输入大小时在根据算法的设计进行分配。

（3）当内存分配过后，如果分配成功就需要提示成功，如果失败则需要提示失败。

（4）内存回收需要用户输入回收作业的ID，根据作业的ID对内存进行回收。在回收时要分多种情况进行判断。

（5）作业展示，需要向用户展示，作业的ID，起始地址，内存大小，状态是已分配还是空闲。

（6）一个作业需要用到数据结构中的双向列表，用一个双向列表来表示节点。

程序代码：

#include <stdio.h>
#include <stdlib.h>
 
struct area
{
  int id;             // 编号
  int addr_front;     //首地址
  int addr_end;      //结束地址
  int size;           //分区大小
  int flag;           //分配标志,0表示空闲，1表示占用
  struct area *front; //上一分区
  struct area *next;  //下一分区
};
 
typedef struct area partion;
 
partion *head = NULL; //分区队列头节点
int need;             //需求
int choice = 1;       //操作选项
 
partion *createPartion(int id, int addr_front, int size, int flag); //生成一个节点
void inputNeed();                                                   //输入需求量
void assign(partion *ptr, int need);                                //分配分区
void first_fit();                                                   //首次适应算法
void best_fit();                                                    //最佳适应算法
void showMemoryInfo();                                              //打印分区分配状况
void recovery();                                                    //分区回收
void changeIdValue(partion *ptr, int delta);                        //改变从ptr开始所有节点的id值
 
int main(void)
{
  head = createPartion(0, 0, 640, 0);
  while (choice != 0)
  {
    puts("-------------------\n请选择操作:\n1:首次适应;\n2:最佳适应;\n3:内存回收;\n4:展示详细信息;\n0:推出......\n-------------------");
    scanf("%d", &choice);
    switch (choice)
    {
    case 1:
      inputNeed();
      first_fit();
      break;
    case 2:
      inputNeed();
      best_fit();
      break;
    case 3:
      recovery();
      showMemoryInfo();
      break;
    case 4:
      showMemoryInfo();
      break;
    case 0:
      puts("byebye");
      break;
    default:
      break;
    }
  }
 
  return 0;
}
 
//创建一个节点
partion *createPartion(int id, int addr_front, int size, int flag)
{
  partion *p = (partion *)malloc(sizeof(partion));
  p->id = id;
  p->addr_front = addr_front;
  p->addr_end=addr_front+size-1;
  p->size = size;
  p->flag = flag;
  p->front = NULL;
  p->next = NULL;
  return p;
}
 
void inputNeed()
{
  printf("请输入需要的内存大小:");
  scanf("%d", &need);
}
 
void first_fit()
{
  partion *fit = NULL;
  partion *ptr = head;
  while (ptr != NULL)
  {
    if (ptr->size >= need && ptr->flag == 0)//如果是空闲并且大小大于则给予分配
    {
      fit = ptr;
      break;
    }
    ptr = ptr->next;
  }
  if (fit != NULL)
  {
    assign(fit, need);
    printf("内存分配成功,分配如下：\n");
    showMemoryInfo();
  }
  else
  {
    puts("抱歉，内存分配失败!");
    free(fit);
  }
}
 
void best_fit()
{
  partion *fit = NULL;
  partion *ptr = head;
  int flag = 0; //flag 表示是否找到可分配的分区
  while (ptr != NULL)
  {
    if (ptr->flag == 0 && ptr->size >= need)
    {
      if (flag == 0)
      {
        //只有遇到的第一个可分配分区会执行此操作
        fit = ptr;
        flag = 1;
      }
      else
      {
        //若遇到可分配且分区更小即更适合的则更新
        if (ptr->size < fit->size)
        {
          fit = ptr;
        }
      }
    }
    ptr = ptr->next;
  }
  //先处理没找到合适分区的情况
  if (flag == 0)
  {
    puts("抱歉，未找到合适的分区!");
    free(fit);
    return;
  }
  //找到则分配
  assign(fit, need);
  puts("内存分配成功，分配如下:\n!");
  showMemoryInfo();
}
 
void showMemoryInfo()
{
  partion *ptr = head;
  puts("\n\n---------------------------------------------");
  puts("总内存分配情况如下:");
  puts("---------------------------------------------");
  puts("序号ID****开始地址****结束地址****内存大小****状态****");
  while (ptr != NULL)
  {
    printf("%-12d%-12d%-12d%-12d",ptr->id,ptr->addr_front,ptr->addr_end,ptr->size);
   // printf("序号id:%21d%10c\n开始地址:%10d%10c\n", ptr->id, '|', ptr->addr_front, '|');
    //printf("结束地址:%10d%10c\n", ptr->addr_end, '|');
    //printf("内存大小:%11d%10c\n", ptr->size, '|');
    printf("%-12s\n", ptr->flag == 0 ? "空闲" : "已分配");
    puts("-----------------------------------------------------");
    ptr = ptr->next;
  }
  puts("---------------------------------------------\n\n");
}
 
void assign(partion *ptr, int need)
{
 
  if (need == ptr->size)//空闲的空间恰好等同需要的空间
  {
    ptr->flag = 1;
    return;
  }
  //空闲的空间大于需要的空间
  partion *assigned = createPartion(ptr->id, ptr->addr_front, need, 1);
  assigned->next = ptr;
  assigned->front = ptr->front;
  changeIdValue(ptr, 1);//把后面的节点的id值都增加1
  ptr->addr_front += need;
  ptr->size -= need;
  if (ptr->front != NULL)//空闲区的头不空，就在前一个节点后面添加分配的节点
  {
    ptr->front->next = assigned;
  }
  else//空闲节点前没有节点
  {
    head = assigned;
  }
 
  ptr->front = assigned;//空闲节点的头指向新分配的
}
 
void recovery()
{
  printf("请输入需要回收作业的ID号：");
  int id, flag = 0;
  scanf("%d", &id);
  partion *ptr = head;
  while (ptr != NULL)
  {
    if (id == ptr->id)
    {
      flag = 1;
      break;
    }
    ptr = ptr->next;
  }
  if (flag == 0)
  {
    puts("没有找到你需要回收的作业！");
    return;
  }
  if (ptr->flag == 0)
  {
    puts("该ID已经是空闲的了");
    return;
  }
  if (ptr->front == NULL)
  {
    //第一个分区
 
    if (ptr->next == NULL || ptr->next->flag == 1)
    {
      //后面不空或后面没有
      ptr->flag = 0;
      return;
    }
    if (ptr->next->flag == 0)
    {
      //后面空
      ptr->size += ptr->next->size;
      ptr->flag = 0;//标记为空闲
      if (ptr->next->next != NULL)//把下一个节点的头指向该节点
      {
        ptr->next->next->front = ptr;
      }
      ptr->next = ptr->next->next;//合并两个节点
 
      free(ptr->next);//真实释放节点
      return;
    }
  }
  if (ptr->next == NULL)
  {
    //最后一个分区
    if (ptr->front == NULL || ptr->front->flag == 1)
    {
      //前面不空或者前没有
      ptr->flag = 0;
      return;
    }
    if (ptr->front->flag == 0)
    {
      //前面为空
      ptr->front->size += ptr->size;
      ptr->front->next = NULL;
      free(ptr);
      return;
    }
  }
  if (ptr->front->flag == 0 && ptr->next->flag == 0)
  {
    //上下都空
    ptr->front->size += ptr->size + ptr->next->size;
    ptr->front->next = ptr->next->next;
    if (ptr->next->next != NULL)
    {
      ptr->next->next->front = ptr->front;
    }
    changeIdValue(ptr->front->next, -2); //更改id
    free(ptr->next);
    free(ptr);
    return;
  }
  if (ptr->front->flag == 0 && ptr->next->flag == 1)
  {
    //上空下不空
    ptr->front->size += ptr->size;
    ptr->front->next = ptr->next;
    ptr->next->front = ptr->front;
    changeIdValue(ptr->front->next, -1);
    free(ptr);
    return;
  }
  if (ptr->front->flag == 1 && ptr->next->flag == 0)
  {
    //上不空下空
    ptr->size += ptr->next->size;
    if (ptr->next->next != NULL)
    {
      ptr->next->next->front = ptr;
    }
    partion *p_next = ptr->next;  //保存一下下方为空的那个分区，以便一会释放 
    ptr->next = ptr->next->next;
    ptr->flag = 0;
    changeIdValue(ptr->next, -1);
    free(p_next);
    return;
  }
  if (ptr->front->flag == 1 && ptr->next->flag == 1)
  {
    //上下都不空
    ptr->flag = 0;
    return;
  }  
}.
 
void changeIdValue(partion *ptr, int delta)
{
  while (ptr != NULL)
  {
    ptr->id += delta;
    ptr = ptr->next;
  }
}

编译运行截图：

首次适应算法流程图：

最佳适应算法流程图：

内存回收流程图：

首次适应算法，首先用户输入作业需要的内存大小，然后程序从低地址向高地址寻找空间空间，如果找到空闲空间，如果空闲空间的大小比作业需要的空间大则进行分配，如果空闲空间比作业需要的空间小，则继续寻找下一个空闲空间。如果所有的空闲空间都寻找完也没有符合要求的，那么作业的内存分配失败。

最佳适应算法，首页用户输入作业需要的内存空间，程序从低地址开始寻找空闲空间，如果第一次找合适的空间分配，就临时存储这个空间地址，继续向下继续寻找符合的地址空间，如果寻找到合适的空间空间范围，且新的空间大小比临时存储的空间大小还小，则新的符合空间更新为临时符合空间，依次类推到最后。如果程序没有临时最佳的地址空间，则并没有分配到内存，所以作业内存分配失败。如果有临时最佳空间地址，则把最佳的地址空间分配给作业。

作业回收，首先需要需要输入回收作业的ID，先判断作业ID是否存在，存在才能进行释放，在ID存在的前提下判断，该ID的作业状态，只有为已分配状态猜才进行释放。释放则的分情况讨论。释放的节点分为头部，中间，尾部。如果释放的节点前后已经有空闲空间，就需要进行合并。

首次适应算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区，这为以后到达的大作业分配大的内存空间创造了条件。缺点是：低址部分不断被划分，会留下许多难以利用的，很小的空闲分区，称为碎片。而每次查找又都是从低址部分开始的，这无疑又会增加查找可用空闲分区时的开销。

最佳适应算法的一个主要缺点是,空闲区一般不可能正好和要求的大小相等,因而要将其分割成两部分,这往往使剩下的空闲区非常小,以至小到几乎无法使用。换句话说,分割发展下去只能是得到许多非常小的分散的空闲区,造成主存空间的浪费。