精华内容
下载资源
问答
  • 动态内存分配算法实验报告包括:实验题目,实验目的,实验要求,实验内容,实验结果,实验总结及后附有详细源代码 实验内容 1,确定定内存空闲分配表和进程内存分配表 2,采用首次适应算法完成内存空间的分配 3,...
  • 动 态 内 存 分 配 算 法 实 验 报 告 院系:计算机与通信工程学院 班级:计科08-1班 姓名:胡太祥 学号:200807010112 一实验题目动态内存分配算法实验目的 深入了解动态分区存储管理方式内存分配与回收的实现 三...
  • 掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。二、实验内容和要求主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配.就是解决多道作业或多进程如何共享主存空间的...

    文档介绍:

    一、实验目的熟悉主存的分配与回收。理解在不同的存储管理方式下.如何实现主存空间的分配与回收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。二、实验内容和要求主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配.就是解决多道作业或多进程如何共享主存空间的问题。所谓回收.就是当作业运行完成时将作业或进程所占的主存空间归还给系统。可变分区管理是指在处理作业过程中建立分区.使分区大小正好适合作业的需求.并且分区个数是可以调整的。当要装入一个作业时.根据作业需要的主存量查看是否有足够的空闲空间.若有.则按需要量分割一个分区分配给该作业;若无.则作业不能装入.作业等待。随着作业的装入、完成.主存空间被分成许多大大小小的分区.有的分区被作业占用.而有的分区是空闲的。实验要求使用可变分区存储管理方式.分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行.分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。同时.要求设计一个实用友好的用户界面.并显示分配与回收的过程。同时要求设计一个实用友好的用户界面,并显示分配与回收的过程。三、实验主要仪器设备和材料实验环境硬件环境:PC或兼容机软件环境:VC++6.0四、实验原理及设计分析某系统采用可变分区存储管理.在系统运行当然开始.假设初始状态下.可用的内存空间为640KB.存储器区被分为操作系统分区(40KB)和可给用户的空间区(600KB)。(作业1申请130KB、作业2申请60KB、作业3申请100KB、作业2释放60KB、作业4申请200KB、作业3释放100KB、作业1释放130KB、作业5申请140KB、作业6申请60KB、作业7申请50KB)当作业1进入内存后.分给作业1(130KB).随着作业1、2、3的进入.分别分配60KB、100KB.经过一段时间的运行后.作业2运行完毕.释放所占内存。此时.作业4进入系统.要求分配200KB内存。作业3、1运行完毕.释放所占内存。此时又有作业5申请140KB.作业6申请60KB.作业7申请50KB。为它们进行主存分配和回收。1、采用可变分区存储管理.使用空闲分区链实现主存分配和回收。空闲分区链:使用链指针把所有的空闲分区链成一条链.为了实现对空闲分区的分配和链接.在每个分区的起始部分设置状态位、分区的大小和链接各个分区的前向指针.由状态位指示该分区是否分配出去了;同时.在分区尾部还设置有一后向指针.用来链接后面的分区;分区中间部分是用来存放作业的空闲内存空间.当该分区分配出去后.状态位就由“0”置为“1”。设置一个内存空闲分区链.内存空间分区通过空闲分区链来管理.在进行内存分配时.系统优先使用空闲低端的空间。设计一个空闲分区说明链.设计一个某时刻主存空间占用情况表.作为主存当前使用基础。初始化空间区和已分配区说明链的值.设计作业申请队列以及作业完成后释放顺序.实现主存的分配和回收。要求每次分配和回收后显示出空闲内存分区链的情况。把空闲区说明链的变化情况以及各作业的申请、释放情况显示打印出来。2.采用可变分区存储管理.分别采用首次适应算法、最佳适应算法和最坏适应算法实现主存分配和回收。3、主存空间分配(1)首次适应算法在该算法中.把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时.从上次找到的空闲分区的下一个空闲分区开始查找.直到找到第一个能满足要求的空闲区.从中划出与请求的大小相等的存储空间分配给作业.余下的空闲区仍留在空闲区链中。(2)最佳适应算法在该算法中.把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时.从上次找到的空闲分区的下一个空闲分区开始查找.直到找到一个能满足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都小.从中划出与请求的大小相等的存储空间分配给作业.余下的空闲区仍留在空闲区链中(3)最坏适应算法在该算法中.把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时.从上次找到的空闲分区的下一个空闲分区开始查找.直到找到一个能满足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都大.从中划出与请求的大小相等的存储空间分配给作业.余下的空闲区仍留在空闲区链中。4、主存空间回收当一个作业执行完成撤离时.作业所占的分区应该归还给系统。归还的分区如果与其它空闲区相邻.则应合成一个较大的空闲区.登记在空闲区说明链中.此时.相邻空闲区的合并问题.要求考虑四种情况:释放区下邻空闲区(低地址邻接)释放区上邻空闲区(高地址邻接)释放区上下都与空闲区邻接释放区上下邻都与空闲区不邻接五、程序流程图main函数里的流程图初始化first和end整理分区序号显示空闲分区链选择算法aa=1,首次适应算法a=2,最佳适应

    内容来自淘豆网www.taodocs.com转载请标明出处.

    展开全文
  • 实验名称 内存分配与回收算法实现 同组人姓名 实验性质 基本操作 验证性 综合性 设计性 实验日期 2010-5-17 实验成绩 教师评价 实验预习 实验操作 实验结果 实验报告 其它 教师签名 一实验目的及要求 掌握为实现多道...
  • 实验四动态分区分配算法实验报告及程序实验报告四 动态分区分配算法班级 学号姓名一、 实验目的动态分区分配是根据进程的实际需要,动态地为之分配内存空间,而在分配时,须按照一定的分配算法,从空闲分区表或空闲...

    动态分区分配算法实验报告(共10篇)

    动态分区分配算法实验报告(共10篇) 实验四动态分区分配算法实验报告及程序

    实验报告四 动态分区分配算法

    班级 学号姓名

    一、 实验目的

    动态分区分配是根据进程的实际需要,动态地为之分配内存空间,而在分配时,须按照一定的分配算法,从空闲分区表或空闲分区链中选出一分区分配给该作业。在本实验中运用了四种分配算法,分别是1.首次适应算法,2.循环首次适应算法,3.最坏适应算法4.最佳适应算法。

    二、 实验环境

    普通的计算机一台,编译环境Microsoft Visual C++ 6.0

    三、 算法思想 1. 数据结构

    (1) 分区开始地址startaddress (2) 分区大小size (3) 分区状态state

    2. 功能介绍

    (1) 首次适应算法

    在首次适应算法中,是从已建立好的数组中顺序查找,直至找到第一个大小能满足要求的空闲分区为止,然后再按照作业大小,从该分区中划出一块内存空间分配给请求者,余下的空间令开辟一块新的地址,大小为原来的大小减去作业大小,若查找结束都不能找到一个满足要求的分区,则此次内存分配失败。

    (2) 循环首次适应算法

    该算法是由首次适应算法演变而成,在为进程分配内存空间时,不再是每次都从第一个空间开始查找,而是从上次找到的空闲分区的下一个空闲分区开始查找,直至找到第一个能满足要求的空闲分区,从中划出一块与请求大小相等的内存空间分配给作业,为实现本算法,设置一个全局变量f,来控制循环查找,当f%N==0时,f=0;若查找结束都不能找到一个满足要求的分区,则此次内存分配失败。

    (3) 最坏适应算法

    最坏适应分配算法是每次为作业分配内存时,扫描整个数组,总是把能满足条件的,又是最大的空闲分区分配给作业。

    (4) 最佳适应算法

    最坏适应分配算法是每次为作业分配内存时,扫描整个数组,总是把能满足条件的,又是最小的空闲分区分配给作业。

    四、 源程序

    #include stdio.h #define L 10

    typedef struct LNode {int startaddress; int size; int state; }LNode; LNode

    P[L]={{0,128,0},{200,256,0},{500,512,0},{1500,1600,0},{5000,150,0}}; int N=5; int f=0; void print() {int i;

    printf(起始地址 分区 状态\n); for(i=0;iN;i++)

    printf(%3d %8d %4d\n,P[i].startaddress,P[i].size,P[i].state);} void First() { int i,l=0,m;

    printf(\n输入请求分配分区的大小:); scanf(%d,&m); for(i=0;iN;i++) {if(P[i].sizem)continue;

    else if(P[i].size==m){ P[i].state=1;l=1;break; }else{

    P[N].startaddress=P[i].startaddress+m; P[N].size=P[i].size-m;

    P[i].size=m;P[i].state=1;

    l=1; N++; break; } } if(l==1||iN)

    { printf(地址成功分配\n\n); printf(地址分配成功后的状态:\n); print(); } else

    printf(没有可以分配的地址空间\n); } void CirFirst() { int l=0,m,t=0;

    printf(\n输入请求分配分区的大小:); scanf(%d,&m); while(fN)

    {if(P[f].sizem){ f=f+1;

    if(f%N==0) { f=0;t=1;} continue; }

    if(P[f].size==m && P[f].state!=1) { P[f].state=1;l=1; f++;break; }

    if(P[f].sizem && P[f].state!=1) { P[N].startaddress=P[f].startaddress+m; P[N].size=P[f].size-m; P[f].size=m; P[f].state=1; l=1; N++; f++; break;} } if(l==1)

    { printf(地址成功分配\n\n);

    printf(地址分配成功后的状态:\n);

    print(); } else

    pri

    展开全文
  • 实验四:内存分配算法 ——动态分区方式主存的分配和回收 本机操作系统:macOS Big Sur 一、前言 一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器,而且要能合理地分配和使用这些存储...

    实验四:内存分配算法

    ——动态分区方式主存的分配和回收

    本机环境:macOS Big Sur

    一、前言
    一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器,而且要能合理地分配和使用这些存储空间。当用户提出申请主存储器空间时,存储管理必须根据申请者的要求,按一定的策略分析主存空间的使用情况,找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时,则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现是与主存储器的管理方式有关的,软件模拟内存的分配。

    二、实验目的
    通过本实验帮助学生理解在动态分区管理方式下应怎样实现主存空间的分配和回收。

    三、实验内容
    在动态分区管理方式下采用不同的分配算法实现主存分配和实现主存回收。

    四、实验要求

    • (1)可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时,根据作业需要的主存量查看是否有足够的空闲空间,若有,则按需要量分割一个分区分配给该作业;若无,则作业不能装入。随着作业的装入、撤离、主存空间被分成许多个分区,有的分区被作业占用,而有的分区是空闲的。例如:
      为了说明哪些区是空闲的,可以用来装入新作业,必须要有一张空区说明表,格式如下:
      其中,起址——指出一个空闲区的主存起始地址。
      长度——指出从起始地址开始的一个连续空闲区的长度。
      状态——有两种状态,一种是“未分配”状态,指出对应的由起址指出的某个长度的区域是空闲区;另一种是“空表目”状态,表示表中对应的登记项目是空白(无效),可用来登记新的空闲区(例如,作业撤离后,它所占的区域就成了空闲区,应找一个“空表目”栏登记归还区的起址和长度且修改状态)。由于分区的个数不定,所以空闲区说明表中应有适量的状态为“空表目”的登记栏目,否则造成表格“溢出”无法登记。
      上述的这张说明表的登记情况是按提示(1)中的例所装入的三个作业占用的主存区域后填写的。
    • (2)当有一个新作业要求装入主存时,必须查空闲区说明表,从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量,这时应把原来的空闲区变成两部分:一个部分分给作业占用;另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的“碎片”,在作业请求装入时,尽可能地利用主存的低地址部分的空闲区,而尽量保存高地址部分有较大的连续空闲区域,以利于大型作业的装入。为此,在空闲区说明表中,把每个空闲区按其地址顺序登记,即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”,总是让“空表目”栏集中在表格的后部。
    • (3)采用首次适应算法或循环首次算法或最佳适应算法分配主存空间。由于本实验是模拟主存的分配,所以当把主存区分配给作业后并不实际启动装入程序装入作业,而用输出“分配情况”来代替。(即输出当时的空闲区说明表及其内存分配表)
    • (4)当一个作业执行结束撤离时,作业所占的区域应该归还,归还的区域如果与其它空闲区相邻,则应合成一个较大的空闲区,登记在空闲区说明表中。例如,在提示(1)中列举的情况下,如果作业2撤离,归还所占主存区域时,应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。
    • (5)请按首次适应算法或循环首次算法或最佳适应算法设计主存分配和回收的程序。然后按(1)中假设主存中已装入三个作业,且形成两个空闲区,确定空闲说明表的初值。现有一个需要主存量为6K的作业4 申请装入主存;然后作业3 撤离;再作业2 撤离。请你为它们进行主存分配和回收,把空闲区
      说明表的初值以及每次分配或回收后的变化显示出来或打印出来。

    五、测试数据文件格式
    打印程序运行时的初值和运行结果,要求如下:

    • 打印空闲区说明表的初始状态,作业4 的申请量以及为作业4 分配后的空闲区说明表状态;
    • 再依次打印作业3 和作业2 的归还量以及回收作业3,作业2 所占主存后的空闲区说明表。

    六、源代码

    #include <iostream>
    #include <list>
    #include <iomanip>
    #include <string>
    using namespace std;
    
    struct Node{
        int start;
        int end;
        bool occupied;
        int size(){
            return end-start;
        }
        void set(int start, int end, bool occupied=0){
            this->start=start;
            this->end=end;
            this->occupied=occupied;
        }
        void printNode(){
            cout<<"start:"<<start<<" end:"<<end<<" size:"<<this->size()<<endl;
        }
        Node(int start, int end, bool occupied=0){
            this->start=start;
            this->end=end;
            this->occupied=occupied;
        }
        Node(){}
    };
    
    
    bool request(list<Node>*, int, bool); //采用首次适应算法
    bool release(list<Node>*, int);
    void printList(list<Node>*);
    void mergeList(list<Node>*);
    
    
    //bool类型请求函数 如果请求成功会返回1
    bool request(list<Node>* l, int need, bool flag_add){
        if(l->size()==0) return 0;
        for(list<Node>::iterator iter=l->begin(); iter!=l->end(); iter++){
            if(iter->size() >= need && iter->occupied==0){
                //如果找到了合适的位置 则将原iter处一分为二,在前半部分放need,occupied置一
                if(flag_add == 1){
                    Node t_rest(iter->start, iter->start+need, 1); //采用首次适应算法 按顺序找到第一个可以用的
                    list<Node>::iterator iter1;
                    iter1 = l->insert(iter , t_rest);
                    iter->start = iter->start+need;
                }
                return 1;
            }
        }
        return 0;
    }
    
    bool release(list<Node>* l, int index){
        if(l->size()==0) return 0;
        int i=0;
        for(list<Node>::iterator iter=l->begin(); iter!=l->end(); iter++){
            if(i==index && iter->occupied==1){
                iter->occupied=0;
                mergeList(l);
                return 1;
            }
            else i++;
        }
        return 0;
    }
    
    //将连续的空区域合并
    void mergeList(list<Node>* l){
        if(l->size()<=1) return;
        list<Node>::iterator foot1 = l->begin();
        list<Node>::iterator foot2 = l->begin();
        ++foot2; //foot2指向第二个
        while(true){
            if(l->size()==1) break;
            if(foot1->occupied==0 && foot2->occupied==0){
                foot1->end += foot2->size();
                if (foot2==l->end()){
                    l->pop_back();
                    break;
                }
                else if(foot2!=l->end()) foot2=l->erase(foot2);
                else break;
            }
            else{
                foot1++;
                foot2++;
            }
            if(foot2 == l->end()) break;
        }
    }
    
    //打印整个“内存”
    void printList(list<Node>* l){
        list<Node>::iterator iter = l->begin();
        for(int i=0;i<l->size();i++){
            cout<<"No."<<i<<"  /  ";
            cout<<"start:"<<setw(4)<<iter->start<<"  /  end:"<<setw(4)<<iter->end<<"  /  used:"<<iter->occupied<<endl;
            iter++;
        }
    }
    
    int main(){
        list<Node> M;
        Node initialize_m(0,1024);
        M.push_back(initialize_m);
        cout<<"//Memory Management System//"<<endl;
        cout<<"Memory size overall: 1024K"<<endl;
        while(true){
            cout<<"///"<<endl;
            cout<<"PrintMemoryList:"<<endl;
            printList(&M);
            cout<<"Enter 1 to request memory..."<<endl;
            cout<<"Enter 2 to release memory..."<<endl;
            cout<<"Enter 0 to EXIT..."<<endl;
            int i=0;
            cin>>i;
            if(i==0){
                cout<<"MMS EXIT with Code 0"<<endl;
                break;
            }
            else if(i==1){
                cout<<"Enter memory size you request..."<<endl;
                int need;
                cin>>need;
                if(request(&M, need, 1)) cout<<"SUCCEEDED!"<<endl;
                else cout<<"FAILED!"<<endl<<endl;;
            }
            else if(i==2){
                cout<<"Enter memory index you want to release..."<<endl;
                int index;
                cin>>index;
                if(release(&M, index)) cout<<"SUCCEEDED!"<<endl;
                else cout<<"FAILED!"<<endl<<endl;
            }
            else{
                cout<<"MMS EXIT with Code -1"<<endl;
                break;
            }
            cout<<"Press the ENTER key to continue..."<<endl;
            getchar();
            getchar();
        }
        
    }
    
    
    
    展开全文
  • 实验目的 通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解熟悉可变分区存 储管理的内存分配和回收 二实验内容 确定内存空间分配表 采用最优适应算法完成内存空间的分配和回收 编写主函数对所做工作...
  • 使用C语言模拟了最先适应法、最佳适应法及最坏适应法三种算法进行内存分配
  • 能够模拟动态内存分配算法对进程分配内存空间。该程序具备的基本功能为: (1)能够以空闲分区表的形式显示某一时刻内存空间的使用情况。 (2)能够创建进程即输入进程信息,包括进程名称和进程需要的内存量, 系统...
  • 实验目的 熟悉主存的分配与回收理解在不同的存储管理方式下如何实现主存空间的分配与 回收掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现 过程 二实验内容和要求 主存的分配和回收的...
  • 实 验 报 告 课程名称 数据结构 实验项目 单链表及合并算法实现 专 业 班 级 姓 名 学 号 指导教师 张靖 实验成绩 年 月 日 实验目的: 1. 理解单链表的定义和特性 2. 初步掌握单链表及简单应用的程序编写技术 实验...
  • 动态分区分配算法 操作系统实验报告 实验四 动态分区分配算法 学号: 班级: 姓名: 实验目的 通过这次实验加深对动态分区分配算法的理解进一步掌握首次适应算法 循环首次适应算法最佳适应算法和最坏适应算法的实现方法...
  • (1)采用页式分配存储方案,通过分别计算不同算法的命中率来比较算法的优劣,同时也考虑页面大小及内存实际容量对命中率的影响; (2)实现OPT 算法 (最优置换算法) 、LRU 算法 (Least Recently) 、 FIFO 算法 ...
  • 实验报告 实验二 实验题目存储器管理 系别计算机科学与技术 系 班级 姓名 学号2 一实验目的 深入理解动态分区存储管理方式下的内存空间的分配与回收 二实验内容 编写程序完成动态分区存储管理方式下的内存分配和回收...
  • 带有流程图及注释源代码编写程序完成可变分区存储管理方式的内存分配回收。 具体包括:确定内存空间分配表; 采用最优适应算法完成内存空间的分配和回收; 编写主函数对所做工作进行测试。
  • 实验报告 实验二 实验题目存储器管理 系别计算机科学与技术系 班级 姓名 学号2 一实验目的 深入理解动态分区存储管理方式下的内存空间的分配与回收 二实验内容 编写程序完成动态分区存储管理方式下的内存分配和回收...
  • 第一题:在可变分区管理方式下采用首次适应算法实现主存空间的分配和回收,采用空闲区说明表数据结构。 1, 按下图从键盘输入并显示内存空间的分配现状,每个分区有四个数据项:起始地址,大小,状态,进程号。起始...
  • 内存分配的基本单位为1KB,同时要求支持至少两种分配策略,并进行测试和对不同分配策略的性能展开比较评估。 最佳适应算法(Best Fit): 它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区,这种方法...
  • 可变分区存储管理方式的内存分配回收 一实验目的 1深入了解可变分区存储管理方式的内存分配回收的实现实验内容 编写程序完成可变分区存储管理方式的内存分配回收 要求有内存空间分配表 并采用 最优适应算法完成...
  • 工具:Eclipse Java ...内存分配:首次适应算法FF、循环首次适应算法NF、最佳适应算法BF、最坏适应算法三种算法WF 前两个实验在别人基础上添加修改功能,界面还可以,后一个自己实现存在小瑕疵,请注意。
  • 1.通过使用位图或空闲表,跟踪内存使用情况,模拟和评价不同的内存分配算法; 2.熟悉内存分配和回收管理过程。 实验要求: 1.要求用你熟悉的程序设计语言编写和调试一个内存分配和回收模拟程序;要求在主函数中测试...

    内存的分配与回收

    北京师范大学珠海分校

    实验目的

    1.通过使用位图或空闲表,跟踪内存使用情况,模拟和评价不同的内存分配算法;

    2.熟悉内存分配和回收管理过程。

    实验要求

    1.要求用你熟悉的程序设计语言编写和调试一个内存分配和回收模拟程序;要求在主函数中测试。

    2.实验报告中必须包括:设计思想、数据定义(包括详细说明)、处理流程(详细算法描述和算法流程图)、源代码、运行结果、体会等部分。

    3.必须模拟该4种内存分配算法:first fit,next fit,best fit和worst fit中的至少2种。

    4.需显示出每次分配和回收后的空闲分区链的情况来以及内存占用情况图。

    5.(可选:)计算2个性能参数:碎片数(小于2个单元(units)的空闲区数)、完成一次内存分配的空闲区比较(搜索)次数,也即经过几次比较完成某次请求的内存分配。

    实验内容

    假设内存容量为256KB,并且划分成1KB大小的块,也即每个内存单元为1KB。一个进程所需要的内存为3到10个单元。同时假设一个作业在运行过程中所需内存的大小不变。

    模拟包括3部分:
    1.实现特定的内存分配算法
    2.实现内存回收模拟
    3.每种内存分配策略对应的碎片数统计(可选)

    实验步骤

    1.确定内存空间分配表

    1)数据项设计
    2)存储结构确定

    内存空间分配表采用双向链表的数据形式

    分配空间块的数据结构为:
    前向指针:before 初始值为-1 指向该结点的上一个节点的位置
    进程块在内存中的位置: strtLocation 表示该内存块的位置信息
    进程块id:标志被占用的内存块
    空间大小 :size 表示占用内存的大小
    后向指针: next 初始值为-1 表示该节点的下一个结点位置

    空闲块的数据结构:
    前向指针:before 初始值为-1 指向该空闲块的上一个空闲块的位置
    空闲块在内存中的位置: strtLocation 表示该空闲块的位置信息
    空间大小 :size 表示空闲空间的大小
    后向指针: next 初始值为-1 表示该节点的下一个空闲块的位置

    作业块链表数据结构

    在这里插入图片描述

    空闲块链表数据结构

    在这里插入图片描述

    2.采用某2种算法完成内存空间的分配和回收

    1)算法分析
    2)算法流程图绘制
    3)编码
    4)调试
    3.编写主函数对所做工作进行测试。

    分配回收算法

    1.首次适应算法FirstFit——空闲链表按地址递增的次序链接,优先分配内存中低址部分的空闲区。可保留高址大空闲区。

    2.循环适应算法NextFit——从上次找到的空闲分区的下一个空闲分区开始查找。应设置一起始查询指针。该算法使空闲分区分布得更均匀。

    3.最佳适应算法BestFit——空闲链表按分区大小递增的次序链接,优先分配内存中满足条件的最小的空闲区。

    4.最坏适应算法WorstFit——空闲链表按分区大小递减的次序链接,优先分配内存中最大的空闲区。

    实现

    一、首次适应算法

    1.核心思想

    在分配一个作业块时,按照内存中空闲块的位置依次查找,直到找到合适大小的内存块(空闲块的大小大于等于作业块的大小)

    2.难点分析

    在回收内存块时,内存列表会有以下三种情况:
    (1)在该回收块的左右两边都有相邻的空闲块;
    (2)在该回收块的左边或者右边有相邻的空闲块;
    (3)在该回收块的左边和右边都没有相邻的回收块;

    3.问题解决

    第(1)种情况:将三个空闲块合并;
    第(2)种情况:将相邻的两个空闲块合并;
    第(3)种情况:将空闲块加入到空闲链表中;

    4.算法流程图

    分配作业块

    在这里插入图片描述

    回收

    在这里插入图片描述

    代码实现

    ProcessNode类
    //初始化作业块和空闲块

    package com.it.bnuz.yzy;
    
    public class ProcessNode {
        private int id;
        private int size;
    
        public ProcessNode(int id, int size) {
            this.id = id;
            this.size = size;
        }
    
        public int getId() {
            return id;
        }
    
        public void setId(int id) {
            this.id = id;
        }
    
        public int getSize() {
            return size;
        }
    
        public void setSize(int size) {
            this.size = size;
        }
    }
    
    

    UseNode类:
    //作业块

    package com.it.bnuz.yzy;
    
    public class UseNode implements Comparable<UseNode> {
        private int before = -1;//初始为-1,-1表示表头
        private int startLocation;
        private int id;
        private int size;
        private int next = -1;//初始为-1,-1表示表尾
    
        public UseNode(int id, int size) {
            this.id = id;
            this.size = size;
        }
    
        public int getBefore() {
            return this.before;
        }
    
        public void setBefore(int before) {
            this.before = before;
        }
    
        public int getStartLocation() {
            return this.startLocation;
        }
    
        public void setStartLocation(int startLocation) {
            this.startLocation = startLocation;
        }
    
        public int getId() {
            return this.id;
        }
    
        public void setId(int id) {
            this.id = id;
        }
    
        public int getSize() {
            return this.size;
        }
    
        public void setSize(int size) {
            this.size = size;
        }
    
        public int getNext() { return this.next; }
    
        public void setNext(int next) {
            this.next = next;
        }
    
        public int compareTo(UseNode o) {
            return this.startLocation - o.getStartLocation();
        }
    
        public String toString() {
            String str = "[before:" + this.before + " startLocation:" + this.startLocation + " id:" + this.id + " size:" + this.size + " next:" + this.next + "]";
            return str;
        }
    }
    
    

    FreeNode类:
    //空闲块

    package com.it.bnuz.yzy;
    
    public class FreeNode implements Comparable<FreeNode> {
        private int before = -1;
        private int startLocation;
        private int size;
        private int next = -1;
    
        public FreeNode(int size) {
            this.size = size;
        }
    
        public int getBefore() {
            return before;
        }
    
        public void setBefore(int before) {
            this.before = before;
        }
    
        public int getStartLocation() {
            return startLocation;
        }
    
        public void setStartLocation(int startLocation) {
            this.startLocation = startLocation;
        }
    
        public int getSize() {
            return size;
        }
    
        public void setSize(int size) {
            this.size = size;
        }
    
        public int getNext() {
            return next;
        }
    
        public void setNext(int next) {
            this.next = next;
        }
    
        @Override
        public int compareTo(FreeNode o) {
            return this.startLocation - o.getStartLocation();
        }
    
        @Override
        public String toString() {
            String str = "[before:"+before+" startLocation:"+startLocation+" size:"+size+" next:"+next+"]";
            return str;
        }
    }
    
    

    内存Map

    private String[] memory_space = new String[256];
    

    初始状态下的内存情况:
    //内存空间为16 * 16 的矩形空间,大小为256k,一个单元代表1k
    //0代表空闲区

    在这里插入图片描述

    作业链表:

    private List<UseNode> useSpaceList = new ArrayList<>();
    

    空闲链表:

    private List<FreeNode> freeSpaceList = new ArrayList<>();
    

    FirstFit分配算法:

    /*
        *FirstFit首次适应算法 分配算法
        * */
        void FirstFit_distribution(ProcessNode p){
            UseNode useNode = new UseNode(p.getId(),p.getSize());
            int size = p.getSize();
            int count = 0;
            for(int i = 0; i < freeSpaceList.size();i++){//循环寻找是否有合适大小的空闲块
                count++;
                if(size <= freeSpaceList.get(i).getSize()){
                    //先处理空闲快链表
                    FreeNode freeNode = freeSpaceList.get(i);
                    useNode.setStartLocation(freeNode.getStartLocation());//插入进的占用块结点的起始位置为这个空闲块的起始位置
    
                    if(size < freeNode.getSize()){//插入块的大小小于该空闲块的大小时,该空闲块的起始位置发生改变,大小发生改变
                        freeSpaceList.get(i).setStartLocation(freeNode.getStartLocation() + p.getSize());
                        freeSpaceList.get(i).setSize(freeNode.getSize() - p.getSize());
                    }
                    else{//如果插入块的大小和该空闲块的大小相同,从链表中删除这个空闲块
                        if(i == 0){
                            freeSpaceList.get(i+1).setBefore(-1);//如果这个空闲块是表头,那么将下一个空闲块的before置为-1;
                        }
                        else{
                            freeSpaceList.get(i-1).setNext(freeSpaceList.get(i).getNext());
                            freeSpaceList.get(i+1).setBefore(freeSpaceList.get(i).getBefore());
                        }
                    }
                    //在内存中显示分配情况
                    for(int j = useNode.getStartLocation();j < useNode.getStartLocation() + useNode.getSize();j++){
                        if(j == useNode.getStartLocation()){
                            memory_space[j] = ""+useNode.getId()+" ";
                        }
                        else{
                            memory_space[j] = "+ ";
                        }
                    }
                    showMemory();
                    //对分配列表进行操作
                    firstFit_add(useNode);
                    showUseSpaceList();
                    showFreeSpaceList();
                    return;
                }
                else {
                    continue;
                }
            }
            if(count == freeSpaceList.size()){
                System.out.println("没有合适的空闲块,插入失败");
                return;
            }
        }
    

    分配算法中,对作业链表操作的函数:
    firstFit_add(UseNode useNode)
    再插入作业链表时,该作业列表的位置分为3种情况:
    1.表头
    2.表中
    3.表尾

    /*
        * firstFit加入分配空间
        * */
        private  void firstFit_add(UseNode useNode){
            //操作占用块链表
            useSpaceList.add(useNode);
            if(useSpaceList.size() > 1){
                useSpaceList.sort(UseNode::compareTo);//通过起始地址号进行排序,模拟插入链表
                for(int k = 0;k < useSpaceList.size();k++){
                    if(useNode.getId() == useSpaceList.get(k).getId()){
                        if(k == 0){
                            useSpaceList.get(k).setNext(useSpaceList.get(k+1).getStartLocation());//如果该占用块插到表头,将next指向源列表的表头起始地址
                            useSpaceList.get(k+1).setBefore(0);//将原表头的before指向表头
                        }
                        else if(k == useSpaceList.size()-1){
                            useSpaceList.get(k).setBefore(useSpaceList.get(k-1).getStartLocation());
                            useSpaceList.get(k-1).setNext(useSpaceList.get(k).getStartLocation());
                        }
                        else{
                            useSpaceList.get(k).setBefore(useSpaceList.get(k-1).getStartLocation());
                            useSpaceList.get(k).setNext(useSpaceList.get(k+1).getStartLocation());
    
                            useSpaceList.get(k-1).setNext(useSpaceList.get(k).getStartLocation());
                            useSpaceList.get(k+1).setBefore(useSpaceList.get(k).getStartLocation());
                        }
                    }
                }
            }
        }
    

    FirstFit回收

    /*
        * firstFit首次适应算法,内存空间的释放
        * 根据分配链表查找到要释放的内存空间地址
        * 在空闲内存链表中添加空闲块
        * */
        public void firstFit_free(int id){
            //查找该块的内存块
            UseNode free_node = find_useNode(id);
            if(free_node != null){
                useSpaceList.remove(free_node);
                FreeNode freeNode = new FreeNode(free_node.getSize());
                freeNode.setStartLocation(free_node.getStartLocation());
                freeSpaceList.add(freeNode);
                freeSpaceList.sort(FreeNode::compareTo);
                for(int i = 0;i < freeSpaceList.size();i++){
                    if(freeSpaceList.get(i).getStartLocation() == freeNode.getStartLocation()){
                        if(i == 0){//如果该空闲块为链表的表头
                            if((freeNode.getStartLocation() + freeNode.getSize()) == freeSpaceList.get(i+1).getStartLocation()){//如果两个空闲块相邻,拓展为一块
                                freeSpaceList.get(i).setSize(freeNode.getSize() + freeSpaceList.get(i).getSize());//合并两个空闲块
                                if(freeSpaceList.get(i+1).getNext() == -1){//如果相邻块是最后一个空闲块
                                    freeSpaceList.remove(freeSpaceList.get(i+1));//将相邻空闲块删除
                                    setFreeSpace(freeSpaceList.get(i).getStartLocation(),freeSpaceList.get(i).getSize());
                                    break;
                                }
                                else{
                                    freeSpaceList.get(i).setNext(freeSpaceList.get(i+1).getNext());//将空闲块的Next指向相邻块的下一个空闲块
                                    freeSpaceList.get(i+2).setBefore(freeNode.getStartLocation());//将相邻块的下一个空闲块的before指向该空闲块
                                    freeSpaceList.remove(freeSpaceList.get(i+1));
                                    setFreeSpace(freeSpaceList.get(i).getStartLocation(),freeSpaceList.get(i).getSize());
                                    break;
                                }
                            }
                            else{//如果两个空闲块不相邻
                                freeSpaceList.get(i).setNext(freeSpaceList.get(i+1).getStartLocation());
                                freeSpaceList.get(i+1).setBefore(freeSpaceList.get(i).getStartLocation());
                                setFreeSpace(freeSpaceList.get(i).getStartLocation(),freeSpaceList.get(i).getSize());
                            }
                        }
                        else if(i == (freeSpaceList.size() - 1)){//如果该空闲块位于链表表尾
                            FreeNode beforeNode = freeSpaceList.get(i-1);//空闲快的的前结点
                            if((beforeNode.getStartLocation() + beforeNode.getSize()) == free_node.getStartLocation()){//如果两个空闲块相邻
                                freeSpaceList.get(i-1).setSize(beforeNode.getSize() + freeNode.getSize());//合并
                                freeSpaceList.remove(freeNode);
                                setFreeSpace(freeNode.getStartLocation(),freeNode.getSize());
                                break;
                            }
                        }
                        else{//该空闲块在表中
                            FreeNode beforeNode = freeSpaceList.get(i-1);
                            FreeNode nextNode = freeSpaceList.get(i+1);
                            //分三种情况讨论:三个空闲块都相邻;只与左或右节点相邻;都不相邻
                            //都相邻
                            if((beforeNode.getStartLocation() + beforeNode.getSize() == freeNode.getStartLocation()) && (freeNode.getStartLocation() + freeNode.getSize() == nextNode.getStartLocation())){
                                freeSpaceList.get(i-1).setSize(beforeNode.getSize() + freeNode.getSize() + nextNode.getSize());
                                freeSpaceList.get(i-1).setNext(nextNode.getNext());
                                freeSpaceList.remove(freeNode);
                                freeSpaceList.remove(nextNode);
                                setFreeSpace(freeNode.getStartLocation(),freeNode.getSize());
                                break;
                            }
                            //与左相邻
                            else if(beforeNode.getStartLocation() + beforeNode.getSize() == freeNode.getStartLocation()){
                                freeSpaceList.get(i-1).setSize(beforeNode.getSize()+freeNode.getSize());
                                setFreeSpace(freeNode.getStartLocation(),freeNode.getSize());
                                break;
                            }
                            //与右相邻
                            else if(freeNode.getStartLocation() + freeNode.getSize() == nextNode.getStartLocation()){
                                freeSpaceList.get(i).setSize(freeNode.getSize()+nextNode.getSize());
                                freeSpaceList.get(i).setBefore(nextNode.getBefore());
                                freeSpaceList.get(i).setNext(nextNode.getNext());
                                freeSpaceList.remove(nextNode);
                                setFreeSpace(freeNode.getStartLocation(),freeNode.getSize());
                                break;
                            }
                            //都不相邻
                            else{
                                freeSpaceList.get(i).setBefore(beforeNode.getStartLocation());
                                freeSpaceList.get(i).setNext(nextNode.getStartLocation());
                                setFreeSpace(freeNode.getStartLocation(),freeNode.getSize());
                                break;
                            }
                        }
                    }
                }
                showMemory();
                showUseSpaceList();
                showFreeSpaceList();
            }
        }
    

    查询回收块的信息函数,返回一个UseNode对象

    /*
        * 通过分配链表useSpaceList查询内存块,返回该内存快的信息
        * */
        private UseNode find_useNode(int id){
            for(int i = 0;i < useSpaceList.size();i++){
                if(useSpaceList.get(i).getId() == id){
                    if(useSpaceList.size() > 1){
                        if(i == useSpaceList.size()-1){
                            useSpaceList.get(i-1).setNext(-1);
                        }
                        else if(i == 0){
                            useSpaceList.get(i+1).setBefore(-1);
                        }
                        else {
                            useSpaceList.get(i-1).setNext(useSpaceList.get(i).getNext());
                            useSpaceList.get(i+1).setBefore(useSpaceList.get(i).getBefore());
                        }
                    }
                    return useSpaceList.get(i);
                }
            }
            return null;
        }
    

    结果显示

    分配作业块

    请输入id:1
    请输入占用内存大小:35

    请输入id:2
    请输入占用内存大小:85

    请输入id:3
    请输入占用内存大小:9

    请输入id:4
    请输入占用内存大小:21

    请输入id:5
    请输入占用内存大小:19

    请输入id:6
    请输入占用内存大小:23

    请输入id:7
    请输入占用内存大小:15

    请输入id:8
    请输入占用内存大小:3

    请输入id:9
    请输入占用内存大小:6

    分配后的内存情况:

    在这里插入图片描述

    分配后的作业块链表:

    在这里插入图片描述

    分配后的空闲快链表:

    在这里插入图片描述

    回收

    回收id=5的作业块

    在这里插入图片描述

    作业链表:

    在这里插入图片描述

    空闲块链表:

    在这里插入图片描述

    两边都有空闲块的情况:

    回收前

    在这里插入图片描述

    回收后

    在这里插入图片描述

    作业块链表

    在这里插入图片描述

    空闲快链表

    在这里插入图片描述

    再插入

    在这里插入图片描述
    在这里插入图片描述

    二、循环适应算法

    1.核心思想

    在空闲块列表中加标记。在插入一个作业块时,从上一次标记的空闲块的下一个空闲块开始查找合适的空闲块进行插入。

    2.算法流程图

    在这里插入图片描述
    回收算法的流程与first fit一致,这里就不做重复了。

    3.代码实现

    nextFit算法,这里只给出核心的分配算法,插入作业链表和插入空闲链表的算法与上述一致。

        /*
         * NextFit算法 循环适应算法
         * */
        public int nextFit_distribution(ProcessNode p,int flag){
            UseNode useNode = new UseNode(p.getId(),p.getSize());
            int size = p.getSize();
            int count = 0;
            for(int i = flag; i < freeSpaceList.size();i++){//从上一次插入的空闲块的下一个空闲块开始循环寻找是否有合适大小的空闲块
                count++;
                if(size <= freeSpaceList.get(i).getSize()){
                    //先处理空闲快链表
                    FreeNode freeNode = freeSpaceList.get(i);
                    useNode.setStartLocation(freeNode.getStartLocation());//插入进的占用块结点的起始位置为这个空闲块的起始位置
    
                    if(size < freeNode.getSize()){//插入块的大小小于该空闲块的大小时,该空闲块的起始位置发生改变,大小发生改变
                        freeSpaceList.get(i).setStartLocation(freeNode.getStartLocation() + p.getSize());
                        freeSpaceList.get(i).setSize(freeNode.getSize() - p.getSize());
                    }
                    else{//如果插入块的大小和该空闲块的大小相同,从链表中删除这个空闲块
                        if(i == 0){
                            freeSpaceList.get(i+1).setBefore(-1);//如果这个空闲块是表头,那么将下一个空闲块的before置为-1;
                        }
                        else{
                            freeSpaceList.get(i-1).setNext(freeSpaceList.get(i).getNext());
                            freeSpaceList.get(i+1).setBefore(freeSpaceList.get(i).getBefore());
                        }
                    }
                    //在内存中显示分配情况
                    for(int j = useNode.getStartLocation();j < useNode.getStartLocation() + useNode.getSize();j++){
                        if(j == useNode.getStartLocation()){
                            memory_space[j] = ""+useNode.getId()+" ";
                        }
                        else{
                            memory_space[j] = "+ ";
                        }
                    }
                    showMemory();
                    //对分配列表进行操作
                    addSpaceList(useNode);
                    showUseSpaceList();
                    showFreeSpaceList();
                    if(i == freeSpaceList.size()-1){//如果该空闲块是最后一个空闲块,将flag置为0
                        flag = 0;
                    }
                    else {//否则将flag指向下一个空闲块
                        flag = i + 1;
                    }
                    return flag;
                }
                else {
                    continue;
                }
            }
            if(count == freeSpaceList.size() - flag){
                System.out.println("没有合适的空闲块,插入失败");
            }
            return flag;
        }
    
    

    4.结果显示

    内存初始情况和链表情况:

    在这里插入图片描述
    在这里插入图片描述

    插入作业块:

    请输入id:2
    请输入占用内存大小:15
    在这里插入图片描述
    在这里插入图片描述

    插入的空闲块的位置是第一个空闲块,那么在下次插入时从第2个开始找

    插入第二个作业块:

    在这里插入图片描述

    在这里插入图片描述

    分配到了上次分配的空闲块的下一个空闲块

    插入大小为30的作业块:

    请输入id:6
    请输入占用内存大小:30
    在这里插入图片描述

    再进行插入,回到第一个空闲块

    在这里插入图片描述
    此时的链表情况
    在这里插入图片描述

    完整项目下载地址

    内存分配和释放完整项目包

    展开全文
  • 1 需求分析 1 需求分析 1本...时还必须使用首次适应算法最后还要显示内存块分配和回收后空闲内存分区 链的情况 链的情况 2要实现对作业的内存分配首先要有一个对作业进行创建和分配内存的 2要实现对作业的内存分配
  • 数据结构实验报告 八种排序算法实验报告 一 实验内容 编写关于八种排序算法的 C 语言程序要求包含直接插入排序希尔排序简单选择排序堆排序冒泡排序快速排序归并排序和基数排序 二 实验步骤 各种内部排序算法的比较 ...
  • 班 级 学 号 姓 名 时间 地点 计算机科学系 计科1201 2014/12/29 机房 c105 课程名称 计算机操作系统 实验名称 内存管理 实 验 过 程 一实验目的 了解内存管理的功能 掌握进程可变内存管理的几种内存分配与回收算法 ...
  • 操作系统实验 文档+实验目的+原理+内容+结果+小结 采用可变式分区管理,使用首次获最佳适应算法实现内存分配与回收 学会可变式分区管理的原理是即在处理作业过程中建立分区,使分区大小正好适合作业的需要,并且分区...
  • 内存空闲区使用自由链管理,采用最坏适应算法从自由链中寻找空闲区进行分配内存回收时假定不做与相邻空闲区的合并。 假定系统的内存共 640K,初始状态为操作系统本身占用 64K。在 t1 时间之后,有作业 A、B、C、D ...
  • 实用标准 操作系统实验报告 实验题目 : 首次适应算法 学生学号 : 学生姓名 : 专业年级 : 开课学期 : 指导教师 : 文档大全 1 实验名 首次适应算法 2 实验目的 采用可变式分区管理使用首次适应算法实现内存分配与回收 ...
  • 实验一 DFS与BFS 3 实验二 最近点对问题 7 实验三 拓扑排序 10 实验四 N皇后问题 12 实验五 0-1背包问题 16 实验六 最短路径 20
  • 操作系统实验四 动态分区分配算法(内含源代码和详细实验报告),详细介绍:http://blog.csdn.net/xunciy/article/details/79239096
  • 内存分页管理的实验报告作者:huang_2008报告时间:2006-8-22实验时间:3天实验代码:HelloOS所有代码 http://flash.xxsyzx.com/learnos/内存分页管理设想:以HelloOS(实验系统名称)为基础进行内存分页管理实验,386...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,812
精华内容 3,924
关键字:

内存分配算法的实现实验报告