首页 > 编程语言 >头歌 计算机操作系统 动态分区算法

头歌 计算机操作系统 动态分区算法

时间：2024-12-11 15:59:07浏览次数：7  
标签：last 操作系统 分区 next 头歌 内存 data size

第1关：首次适应算法

任务描述


假设初始状态下可用的内存空间为55MB，并有如下的请求序列：
作业1申请15MB
作业2申请30MB
作业1释放15MB
作业3分配8MB
作业4分配6MB
作业2释放30MB
请采用首次适应算法进行内存块的分配和回收，并打印出空闲内存分区链的情况

相关知识


为了完成本关任务，你需要掌握使用首次适应算法进行内存块的分配与回收。

内存分配


空闲分区链按地址递增的顺序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首到链尾都找不到一个能满足要求的分区，则表明系统没有足够大的内存分配给该进程，内存分配失败返回。

内存回收


当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一： 
(1) 回收区与插入点的前一个空闲分区F1相邻接，此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。
(2) 回收分区与插入点的后一空闲分区F2相邻接，此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。
(3) 回收区同时与插入点的前、后两个分区F1和F2邻接，此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。
(4) 回收区前后没有空闲分区。这时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置

编程要求


空闲分区采用带头结点的双向链表来管理，主函数、链表初始化函数和打印函数已实现，只需要补充首次适应算法分配内存的函数 first_fit以及内存回收的函数recycle()即可。

bool first_fit(int id,int m_size)//使用首次适应算法给作业分配内存，id为作业号，m_size为作业大小
void recycle(int id)//回收内存,id为释放内存的作业号 

测试说明


平台会对你编写的代码进行测试：

解答：

#include <stdio.h>
#include <stdlib.h>
const int Max_length=55;//最大内存
struct areaNode//管理分区的结构体
{
    int ID;//分区号 
    int size;//分区大小 
    int address;//分区地址 
    int flag;//使用状态，0为未占用，1为已占用
};
typedef struct DuNode//双向链表结点
{
  struct areaNode data;//数据域 
  struct DuNode *prior;//指针域 
  struct DuNode *next;
}*DuLinkList;
DuLinkList m_head = new DuNode, m_last = new DuNode;//双向链表首尾指针
void init()//分区链表初始化
{
  m_head->prior = NULL;
  m_head->next = m_last;
  m_last->prior = m_head;
  m_last->next = NULL;
  m_head->data.size = 0;
  m_last->data.address = 0;
  m_last->data.size = Max_length;
  m_last->data.ID = 0;
  m_last->data.flag = 0;
}
void show()
{
  DuNode *p = m_head->next;//指向空闲区队列的首地址 
  printf("+++++++++++++++++++++++++++++++++++++++\n");
  while (p)
  {
    printf("分区号：");
 if (p->data.ID == 0)
   printf("FREE\n");
 else
   printf("%d\n",p->data.ID);
 printf("分区起始地址：%d\n",p->data.address);
 printf("分区大小：%d\n",p->data.size);
 printf("分区状态：");
 if (p->data.flag)
   printf("已被占用\n");
 else
   printf("空闲\n");
 printf("——————————————————\n");
 p = p->next;
  }
}
bool first_fit(int id,int m_size)//首次适应算法,id为作业号，m_size为作业大小 
{
     //请补充使用首次适应算法给作业分配内存的函数代码
    DuLinkList p = m_head;
    while(p != m_last) {
        DuLinkList n = p->next;
        if(!n->data.flag && n->data.size >= m_size) {
            DuLinkList t = new DuNode();
            t->data.ID = id;
            t->data.size = m_size;
            t->data.address = n->data.address;
            t->data.flag = 1;
            n->data.address += m_size;
            n->data.size -= m_size;
            t->prior = p;
            t->next = n;
            p->next = t;
            n->prior = t;
        }
        p = n;
    }
}
void recycle(int id)//回收内存,id为释放内存的作业号 
{
    DuLinkList p = m_head;
    while(p != m_last) {
        DuLinkList n = p->next;
        if(n->data.ID == id) {
            p->next = n->next;
            n->next->prior = p;
            n->next->data.address -= n->data.size;
            m_last->data.size += n->data.size;
            delete n;
            n = n->next;
        }
        if(n != m_last)
            n->next->data.address = n->data.address + n->data.size;
        p = n;
    }
}
int main()
{
 init();
    printf("首次适应算法：\n");
 first_fit(1,15);
 first_fit(2,30);
 recycle(1);
 first_fit(3,8);
 first_fit(4,6);
 recycle(2);
 show();
 DuNode *p = m_head;
 while(p != NULL)
 {
  DuNode *temp =  p;
  p = p->next;
  delete(temp);
  temp = NULL;
 }
 return 0;
}

第2关：最佳适应算法

假设初始状态下可用的内存空间为55MB，并有如下的请求序列：
作业1申请15MB
作业2申请30MB
作业1释放15MB
作业3分配8MB
作业4分配6MB
作业2释放30MB
请采用最佳适应算法进行内存块的分配和回收，并打印出空闲内存分区链的情况

相关知识


为了完成本关任务，你需要掌握使用最佳适应算法进行内存块的分配与回收。

内存分配


每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。若从链首到链尾都找不到一个能满足要求的分区，则表明系统没有足够大的内存分配给该进程，内存分配失败返回。

内存回收


当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一： 
(1) 回收区与插入点的前一个空闲分区F1相邻接，此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。
(2) 回收分区与插入点的后一空闲分区F2相邻接，此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。
(3) 回收区同时与插入点的前、后两个分区F1和F2邻接，此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。
(4) 回收区前后没有空闲分区。这时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置

编程要求


空闲分区采用带头结点的双向链表来管理，主函数、链表初始化函数和打印函数已实现，只需要补充最佳适应算法分配内存的函数 best_fit以及内存回收的函数recycle()即可。

bool best_fit(int id,int m_size)//使用最佳适应算法给作业分配内存，id为作业号，m_size为作业大小
void recycle(int id)//回收内存,id为释放内存的作业号 

测试说明


平台会对你编写的代码进行测试：

预期输出：

开始你的任务吧，祝你成功！

#include <stdio.h>
#include <stdlib.h>
const int Max_length=55;//最大内存
struct areaNode//管理分区的结构体
{
    int ID;//分区号 
    int size;//分区大小 
    int address;//分区地址 
    int flag;//使用状态，0为未占用，1为已占用
};
typedef struct DuNode//双向链表结点
{
  struct areaNode data;//数据域 
  struct DuNode *prior;//指针域 
  struct DuNode *next;
}*DuLinkList;
DuLinkList m_head = new DuNode, m_last = new DuNode;//双向链表首尾指针
void init()//分区链表初始化
{
  m_head->prior = NULL;
  m_head->next = m_last;
  m_last->prior = m_head;
  m_last->next = NULL;
  m_head->data.size = 0;
  m_last->data.address = 0;
  m_last->data.size = Max_length;
  m_last->data.ID = 0;
  m_last->data.flag = 0;
}
void show()
{
  DuNode *p = m_head->next;//指向空闲区队列的首地址 
  printf("+++++++++++++++++++++++++++++++++++++++\n");
  while (p)
  {
    printf("分区号：");
 if (p->data.ID == 0)
   printf("FREE\n");
 else
   printf("%d\n",p->data.ID);
 printf("分区起始地址：%d\n",p->data.address);
 printf("分区大小：%d\n",p->data.size);
 printf("分区状态：");
 if (p->data.flag)
   printf("已被占用\n");
 else
   printf("空闲\n");
 printf("——————————————————\n");
 p = p->next;
  }
}
bool best_fit(int id, int m_size)//最佳适应算法，其中需要查找最佳的存放位置
{
      //请补充使用最佳适应算法给作业分配内存的函数代码
    DuLinkList p = m_head;
    DuLinkList t = nullptr;
    while(p != m_last) {
        DuLinkList n = p->next;
        if(!n->data.flag && n->data.size >= m_size) {
            if(t == nullptr || t->data.size > n->data.size){
                t = n;
            }
        }
        p = n;
    }
    if(t == nullptr)
        return false;
    if(t->data.size == m_size) {
        t->data.flag = 1;
        t->data.ID = id;
    }
    else {
        DuLinkList t2 = new DuNode();
        t2->next = t;
        t2->prior = t->prior;
        t->prior->next = t2;
        t->prior = t2;
        t2->data.ID = id;
        t2->data.flag = 1;
        t2->data.address = t->data.address;
        t->data.address += m_size;
        t2->data.size = m_size;
        t->data.size -= m_size;
    }
    return true;
}
void recycle(int id)//回收内存,id为释放内存的作业号 
{
     //请补充回收作业内存的函数代码
    DuLinkList p = m_head;
    DuLinkList n = nullptr;
    while(p != m_last) {
        n = p->next;
        if(n->data.ID == id) {
            break;
        }
        p = n;
    }
    if(n == nullptr || n == m_last)
        return;
    n->data.flag = 0;
    n->data.ID = 0;
    DuLinkList np = n->prior;
    DuLinkList nn = n->next;
    if(np != m_head && np->data.flag == 0) {
        np->prior->next = n;
        n->prior = np->prior->next;
        n->data.address = np->data.address;
        n->data.size += np->data.size;
        delete np;
    }
    if((nn != nullptr || nn != m_last) && nn->data.flag == 0) {
        nn->next->prior = n;
        n->next = nn->next->prior;
        n->data.size += nn->data.size;
        delete nn;
    }
}
int main()
{
 init();
    //最佳适应算法
 printf("最佳适应算法：\n");
 init();
 best_fit(1,15);
 best_fit(2,30);
 recycle(1);
 best_fit(3,8);
 best_fit(4,6);
 recycle(2);
 show();
 DuNode *p = m_head;
 while(p != NULL)
 {
  DuNode *temp =  p;
  p = p->next;
  delete(temp);
  temp = NULL;
 }
 return 0;
}

标签：last,操作系统,分区,next,头歌,内存,data,size
From： https://blog.csdn.net/2302_79714797/article/details/144402401

相关文章

  • 操作系统中的死锁
    什么是死锁一组进程中的每一个进程都在等待仅由该组进程中其他进程才能引发的事件，这样就形成死锁了。死锁的原因竞争不可抢占的资源竞争可消耗资源进程推进顺序不当死锁产生的必要条件1.互斥条件：对资源互斥访问2.请求和保持：进程已经拥有了一个资源，还需要拥有其他资源，此......
  • 在 Windows 中，恢复分区通常会使用特定的 GUID（全球唯一标识符）来标识。你提到的 EBD0A0A
    在Windows中，恢复分区通常会使用特定的GUID（全球唯一标识符）来标识。你提到的EBD0A0A2-B9E5-4433-87C0-68B6B72699C7是一个典型的恢复分区的GUID。这种GUID用来标识特定类型的分区，特别是Windows恢复环境（WindowsRE）分区。这个GUID是由Microsoft定义的，用于标识系统分区的......
  • windows系统基础(一)：操作系统基础与管理技巧
    文章目录windows系统基础Windows内核模式与用户模式Windows服务和进程管理机制任务管理与性能监控注册表(WindowsRegistry)线程和线程池dos、cmd、powershell虚拟化技术Hyper-V文件系统**一、文件系统概述****二、Windows文件系统类型详解****三、Windows文件系统......
  • Windows Image Acquisition (WIA) 服务是 Windows 操作系统中的一个关键服务，主要用于
    WindowsImageAcquisition(WIA)服务是Windows操作系统中的一个关键服务，主要用于扫描仪、数码相机等设备的图像采集和管理。它为这些设备提供必要的软件接口，使得用户可以通过标准应用程序（如Windows照片查看器、扫描仪应用等）来获取图像数据。1. WIA服务概述服务名称： St......
  • 记一次spark聚合清洗数据分区裁剪失效的问题
    背景公司有一套大数据的清洗流程，模式是：sparkwithhive。在执行聚合原始表的操作当中，有一个sparksql过滤条件，如下：yyyy='${yyyy}'andmm='${mm}'anddd='${dd}'andhh='${hh}'and(dimen='303'or(dimen='302'andas_burl=1))在跑任务......
  • 【Linux探索学习】第二十弹——基础IO：深入理解C语言文件I/O与Linux操作系统中的文件操
    Linux学习笔记：https://blog.csdn.net/2301_80220607/category_12805278.html?spm=1001.2014.3001.5482前言：文件I/O（输入输出）操作是现代计算机系统中的重要组成部分，几乎所有的程序都需要与文件进行交互。无论是读取配置文件、写入日志文件，还是处理用户数据，文件操作都是不可避......
  • Windows事件日志文件 .evt 和 .evtx 是用于存储和管理系统、应用程序、和安全事件的两
    Windows事件日志文件.evt和.evtx是用于存储和管理系统、应用程序、和安全事件的两种文件格式。它们在Windows操作系统中都起到了记录日志的作用，但有一些关键的差异。以下是.evt和.evtx文件格式的对比表格：特性.evt文件.evtx文件文件扩展名.evt.evtx引入......
  • 【数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】
    目录......
  • 10大白帽黑客专用的 Linux 操作系统
    揭秘十大黑客专用渗透测试的工具的操作系统，这里我把Kali Linux 列为首位，是因为它在渗透测试中非常流行，它的开发团队Offensivesecurity同时也是开发  BackTrack的团队。我们没有列出  BackTrack，是因为在它的官方站点上已经无法下载了，它已经被KaliLinux所取代了。这......
  • MySQL分区
    1. 什么是表分区？mysql数据库中的数据是以文件的形势存在磁盘上的，默认放在/mysql/data下面（可以通过my.cnf中的datadir来查看），一张表主要对应着三个文件，一个是frm存放表结构的，一个是myd存放表数据的，一个是myi存表索引的。如果一张表的数据量太大的话，那么myd,myi就会变的很大，查找数......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99