logo资料库

计算机操作系统实验报告_动态分区分配方式的模拟.doc

发布时间：2022-06-15 发布人：admin 分类：说明书 资料大小：0.10M 资料格式：doc 举报 版权申诉
第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
资料共12页，剩余部分请下载后查看
    计算机操作系统实验报告 姓名： 班级: 学号： 题目：动态分区分配方式的模拟 实习 内容 简要 描述 实验 分析 算法 介绍 结果 分析 （思 考题 解 答； 错误 原因 分 析） 本次实验要完成两部分内容： 一是用 C 语言实现对采用首次适应算法和最佳适应算法的动态分区分配过程 ALLOC（） 和回收过程 FREE（），其中空闲分区由空闲分区链来管理，进行分配时，系统优先使用 空闲区底端空间。 二是假设初始状态下，可用内存空间为 640KB。按照题目要求的作业顺序，以及各个作 业分配和回收的内存空间。分别采用首次适应法和最佳适应法，对内存进行分配和回收， 要求每次分配和回收后显示空闲内存分区链的情况。 本次实验通过用 C 语言进行编程并调试、运行，形象地表现出动态分区的分配方式，直 观地展现了首次适应算法和最佳适应算法对内存的释放和回收方式之间的区别。加深了 我们对两种算法优缺点的理解，帮助我们了解一些数据结构和分配算法，进一步加深我 们对动态分区存储器管理方式及其实现过程的理解。主要的问题在于，如何解决两种算 法对内存的释放和回收空间的表示。 动态分区分配：又称为可变分区分配，这种分配方式并不事先先将主存划分成一块块的 分区，而是在作业进入主存时，根据作业的大小动态地建立分区。并使分区的大小正好 适应作业的需要。因此系统中分区的大小是可变的，分区的数目也是可变的。 分区分配算法：（两者的空闲块链接方式不同） ①首次适应法： 为作业选择分区时总是按地址从高到低搜索，只要找到可以容纳该作业的空白块， 就把该空白块分配给该作业。 特点：优先利用内存中底地址部分的空闲分区 (将所有空闲区,按其地址递增的顺序链 接) ②最佳适应算法： 接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配;为作业 选择分区时总是寻找其大小最接近于作业所要求的存储区域。 特点：用最小空间满足要求 (将所有空闲区,按其大小递增的顺序联接成空闲区链) 运行结果分析： 1、 参考程序方法 1 中，用两个独立的程序分别实现首次适应算法和最佳适应算法的分 配和回收过程。首次适应算法，在进行内存分配时，从空闲分区链首开始顺序查找， 能满足其大小要求的空闲分区为止。然后，再按照作业大小，从该分区中划出一块 内存空间分配给请求者，余下的空闲分区仍然留在空闲分区链中。最佳适应算法， 在进行内存分配时，从空闲分区链首开始顺序查找，直至找到第一个能满足其大小 要求的空闲分区为止。如果给空闲分区大于作业的大小，则从该分区中划出一块内 存空间分配给请求者，将剩余空闲区仍然留在空闲区分链中。当作业运行完成时， 对已使用完的分区进行回收，系统根据回收分区的大小及首地址，在空闲分区链中 检查是否有邻接的空闲区，如有相邻空闲区则合并成一个大的空闲区，然后修改有 关的分区状态信息。 2、 参考程序方法 2 中，只用了一个程序来实现整个操作内容：首先确定内存空间分配 表；然后编写主函数实现所需功能；最后分别采用首次和最佳适应算法完成内存空
    间的分配和回收。 结果 分析 （思 考题 解 答； 错误 原因 分 析） 思考题解答： 1、 首次适应算法分配时从表头指针开始查找可利用空间表，将找到的第一个大小不小 于“请求”的空闲块的一部分分配给用户。可利用空间表本身既不按节点的初始地址有 序，也不按节点的大小有序。用户释放内存，回收时只是将空闲块插入在链表的表头即 可。 最佳适应算法将可利用空间表中一个大小不小于“请求”且最接近“请 求”的空闲块的一部分分配给用户。分配与回收都需要对可利用空间表从头至尾查询一 遍。为了避免每次分配都要查询整个链表，通常要求节点从大到小排序，由此只需找到 第一个足够大的空闲块即可予以分配。但回收时，必须把回收的空闲块放置在符合大小 顺序关系的链表位置。 因此，首次适应算法分配和回收的速度更快，用时更少。 2、 经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小， 不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片。造成存储资源 的浪费，我们可以通过紧凑技术来解决，即通过在内存移动程序，将所有小的空闲区域 合并为大的空闲区域（紧缩技术，紧致技术，浮动技术，搬家技术）。 错误原因： 方法 1：直接运行便可得到正确的结果。 方法 2：参考程序直接运行会出现 11errors，需改正才能正常运行，其涉及错误有： ①用 getch();缺少头函数：#include ；②在程序一开始处缺少函数定义 int wum(long return_pointer,long size,char name[]);；③定义类型出错，应将 long (*test_alloc)();改为 long (*test_alloc)(long alloc_size,char name[]);。 主要 代码 结构 （附 注 释） /*sequence number of work 序列号的工作*/ /*space taken up 占用空间*/ /*首次适应算法*/ #include "stdlib.h" #include "stdio.h" /*定义空闲分区链结构*/ struct Node { int num; int space; struct Node *next; //指向下一个节点的指针域，后向指针 }; typedef struct Node Node; Node *head=NULL; //头指针，赋空 Node *newNode() { return (Node*)malloc(sizeof(Node)); } void init() { head=newNode();
    head->next=NULL;//判断头指针的下个节点是否为空 } /*内存分配*/ void ALLOC(int num, int space) { Node *p=newNode();//为 p 分配一个 Node 类型所占的空间， p 指向所分配的内存的首 地址 Node *q=head->next; Node *s=newNode(); Node *n=newNode(); if(head->next==NULL)//如果指针指向的下个位置为空则分配 { 主要 代码 结构 （附 注 释） p->space=640; p->num=0; p->next=NULL; // 插入尾最后一个结点 head->next=p; if(p->space>=space) { s=newNode(); s->space=space; //赋值数据 s->num=num; p->space-=space; s->next=p; //把 p 链接到最后一个结点的 next head->next=s; return; } printf("Out of Memory!\n"); return; } if(q->num==0&&q->space>=space) { s=newNode(); s->space=space; s->num=num; q->space-=space; s->next=q; //把 q 链接到最后一个结点的 next head->next=s; return; } p=q->next; while(p!=NULL)
    { if(p->num==0) { if(p->space>=space) { n=newNode(); n->space=space; n->num=num; p->space-=space; n->next=p; //把 p 链接到最后一个结点的 next q->next=n; //把 n 链接到最后一个结点的 next return; 主要 代码 结构 （附 注 释） } } p=p->next; //下移 q=q->next; //下移 } printf("Out of Memory!\n"); } /*内存回收*/ void FREE(int num) { Node *q=head; int i=1; Node *p=head; Node *t=newNode(); while(q->num!=num) { q=q->next; i++; } q->num=0; /*表示此段空间已经回收*/ /*查找有无连续空闲存储空间,如果有则回收*/ while(p->next!=NULL) { if(p->num==0&&p->next->num==0) { t=p->next; p->next=t->next; p->space+=t->space; free(t); }
    p=p->next; } } /*查看分配*/ void show() { int account_space=0; Node *p=newNode(); printf("Distribution of memory:\n"); for(p=head->next;p!=NULL;p=p->next) { if(p->num==0) printf("free :%d\n",p->space); else printf("work%d:%d\n",p->num,p->space); account_space+=p->space; } printf("--------------------------------"); } /*主函数*/ int main() { 主要 代码 结构 （附 注 释） init(); /*初始化,建立一个头指针指向内存区*/ ALLOC(1,130); //作业 1 申请 130KB show(); getchar(); /*控制显示,运行时用户每从键盘上输入一次回车,内存分配变 化一次*/ ALLOC(2,60); show(); getchar(); ALLOC(3,100); show(); getchar(); FREE(2);//释放空间：FREE（p） show(); getchar(); ALLOC(4,200); show(); getchar(); FREE(3); show(); getchar();
    FREE(1); show(); getchar(); ALLOC(5,140); show(); getchar(); ALLOC(6,60); show(); getchar(); ALLOC(7,50); show(); getchar(); FREE(6); show(); printf("\nThe end!\n"); getchar(); return 0; } /*最佳适应算法*/ #include "stdlib.h" #include "stdio.h" #include /*定义空闲分区链结构*/ struct Node { 主要 代码 结构 （附 注 释） int num; int space; struct Node *next;//后向指针 /*sequence number of work 序列号的工作*/ /*space taken up 占用空间*/ }; typedef struct Node Node; Node *head=NULL; //头指针，赋空 Node * array[10]; Node * before_array[10]; /*数组,用来存放 num=0 点的指针*/ /*存放 array[i]对应的前一指针*/ Node *newNode() { return (Node*)malloc(sizeof(Node)); //返回带头结点的链表 }
    void init() { head=newNode(); head->next=NULL; } /*内存分配*/ void ALLOC(int num, int space) { int i=0,j; Node *temp=newNode(); Node *p=newNode(); Node *q=head->next; Node *s=newNode(); Node *r=newNode(); if(head->next==NULL) { p->space=640; p->num=0; p->next=NULL; head->next=p; if(p->space>=space) { s->space=space; s->num=num; p->space-=space; s->next=p; head->next=s; return; 主要 代码 结构 （附 注 释） } printf("Out of Memory!\n"); return; } p=head; q=p->next; while(q!=NULL) { if(q->num==0&&q->space>=space) { array[i]=q; before_array[i]=p; i++; }
    q=q->next; p=p->next; } if(i>1) { for(j=0;jspace<=array[j+1]->space) temp=before_array[j]; else temp=before_array[j+1]; } } else 主要 代码 结构 （附 注 释） temp=before_array[0]; r->space=space; r->num=num; temp->next->space-=space; r->next=temp->next; temp->next=r; return; } /*内存回收*/ void FREE(int num) { Node *q=head; int i=1; Node *p=head; Node *t=newNode(); while(q->num!=num) { q=q->next; i++; } q->num=0; /*表示此段空间已经回收*/ /*查找有无连续空闲存储空间,如果有则回收*/ while(p->next!=NULL) { if(p->num==0&&p->next->num==0) { t=p->next;
    分享到：
    赞 收藏

    相关推荐

    资料库

    后端

    共收录2142份资料，累计10个分类，关注成员有19位，主要包括：Perl,Docker,Delphi,VB,PHP,Java,C,C#,Python,C++

    热门标签

    Perl Docker Delphi VB PHP Java C C# Python C++

    最新资料