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

计算机操作系统实验报告

姓名： 班级： 学号：

题目：动态分区分配方式的模拟

实习 内容 简要 描述

本次实验要完成两部分内容：

一是用C语言实现对采用首次适应算法和最佳适应算法的动态分区分配过程 ALLOCo

和回收过程FREE（）,其中空闲分区由空闲分区链来管理，进行分配时，系统优先使用 空闲区底端空间。

二是假设初始状态下，可用内存空间为 640KBO按照题目要求的作业顺序，以及各个作

业分配和回收的内存空间。

　分别采用首次适应法和最佳适应法， 对内存进行分配和回收，

要求每次分配和回收后显示空闲内存分区链的情况。

实验 分析 算法 介绍

本次实验通过用 C语言进行编程并调试、运行，形象地表现出动态分区的分配方式， 直

观地展现了首次适应算法和最佳适应算法对内存的释放和回收方式之间的区别。 加深了

我们对两种算法优缺点的理解，帮助我们了解一些数据结构和分配算法， 进一步加深我

们对动态分区存储器管理方式及其实现过程的理解。 主要的问题在于，如何解决两种算

法对内存的释放和回收空间的表示。

动态分区分配：又称为可变分区分配， 这种分配方式并不事先先将主存划分成一块块的 分区，而是在作业进入主存时，根据作业的大小动态地建立分区。 并使分区的大小正好

适应作业的需要。因此系统中分区的大小是可变的，分区的数目也是可变的。

分区分配算法：（两者的空闲块链接方式不冋）

首次适应法：

为作业选择分区时总是按地址从高到低搜索，只要找到可以容纳该作业的空白块，

就把该空白块分配给该作业。

特点：优先利用内存中底地址部分的空闲分区 （将所有空闲区，按其地址递增的顺序链

接）

最佳适应算法：

接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配 ；为作业

选择分区时总是寻找其大小最接近于作业所要求的存储区域。

特点：用最小空间满足要求 （将所有空闲区，按其大小递增的顺序联接成空闲区链 ）

结果 分析

（思 考题 解 答； 错误 原因 分 析）

运行结果分析：

1、 参考程序方法1中，用两个独立的程序分别实现首次适应算法和最佳适应算法的分

配和回收过程。首次适应算法，在进行内存分配时，从空闲分区链首开始顺序查找， 能满足其大小要求的空闲分区为止。然后，再按照作业大小，从该分区中划出一块 内存空间分配给请求者，余下的空闲分区仍然留在空闲分区链中。 最佳适应算法，

在进行内存分配时，从空闲分区链首开始顺序查找，直至找到第一个能满足其大小 要求的空闲分区为止。如果给空闲分区大于作业的大小，则从该分区中划出一块内 存空间分配给请求者，将剩余空闲区仍然留在空闲区分链中。当作业运行完成时， 对已使用完的分区进行 回收，系统根据回收分区的大小及首地址，在空闲分区链中 检查是否有邻接的空闲区，如有相邻空闲区则合并成一个大的空闲区，然后修改有 关的分区状态信息。

2、 参考程序方法2中，只用了一个程序来实现整个操作内容：首先确定内存空间分配 表；然后编写主函数实现所需功能；最后分别采用首次和最佳适应算法完成内存空

结果 分析

(思 考题 解 答； 错误 原因 分 析)

间的分配和回收。

思考题解答：

1、 首次适应算法分配时从表头指针开始查找可利用空间表， 将找到的第一个大小不小

于“请求”的空闲块的一部分分配给用户。 可利用空间表本身既不按节点的初始地址有

序，也不按节点的大小有序。 用户释放内存，回收时只是将空闲块插入在链表的表头即

可。

最佳适应算法将可利用空间表中一个大小不小于“请求”且最接近“请求”的

空闲块的一部分分配给用户。 分配与回收都需要对可利用空间表从头至尾查询一遍。 为

了避免每次分配都要查询整个链表， 通常要求节点从大到小排序， 由此只需找到第一个

足够大的空闲块即可予以分配。 但回收时，必须把回收的空闲块放置在符合大小顺序关

系的链表位置。

因此，首次适应算法分配和回收的速度更快，用时更少。

2、 经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，

不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片。造成存储资源 的浪费，我们可以通过紧凑技术来解决， 即通过在内存移动程序， 将所有小的空闲区域 合并为大的空闲区域(紧缩技术，紧致技术，浮动技术，搬家技术) 。

错误原因：

方法1:直接运行便可得到正确的结果。

方法2：参考程序直接运行会出现 Ilerrors ,需改正才能正常运行，其涉及错误有：

①用 getch();缺少头函数：#include VConio.h> ;②在程序一开始处缺少函数疋义 int WUm(IOngretUrn Pointer,lOng size,char name[]); :③疋义类型出错，应将 Iong

(*test_alloc)(); 改为 Iong (*test_allOC)(IOng alloc_size,Char name[]); 。

主要 代码 结构

(附 注 释)

/*首次适应算法*/

#i nclude "stdlib.h"

#i nclude "stdio.h"

/*定义空闲分区链结构*/

StrUCt Node

{

int num; /*sequence number of work 序列号的工作 */

int space; /*space taken UP 占用空间 */

StrUCt Node *n ext; // 指向下一个节点的指针域，后向指针

};

typedef StrUCt Node Node;

Node *head=NULL; // 头指针，赋空

Node *n ewNode()

{

retur n (Node*)malloc(sizeof(Node));

}

void in it()

{

head=n ewNode();

head-〉next=NULL;// 判断头指针的下个节点是否为空

}

/*内存分配*/

void ALLOC(i nt num, int SPaCe)

{

P指向所分配的内存的首Node *p=newNode();// 为P分配一个Node

P指向所分配的内存的首

Node *q=head->n ext;

Node *s=n ewNode();

Node *n=n ewNode();

if(head-> next==NULL)// 如果指针指向的下个位置为空则分配

{

p->space=640;

主要 代码 结构（附 注 释）

主要 代码 结构

（附 注 释）

p-> next=NULL; // 插入尾最后一个结点

head->n ext=p;

if(p->space>=space)

{

s=n ewNode();

s->space=space; // 赋值数据

s->num=num;

p->space-=space;

s->next=p; // 把P链接到最后一个结点的 next

head->n ext=s;

return;

}

Prin tf("Out of Memory!?n");

return;

}

if(q_>num==O&&q_ >space>=space)

{

s=n ewNode();

s->space=space;

s->num=num;

q->space-=space;

s->next=q; // 把q链接到最后一个结点的 next

head->n ext=s;

return;

}

p=q->n ext;

WhiIe(P!=NULL)

if(p->num==0)

{

if(p->space>=space)

{

n=n ewNode();

n->space=space;

把P

把P链接到最后一个结点的 next 把n链接到最后一个结点的 next

主要代码

主要

代码

结构

}

P=P->n ext; // 下移 q=q->n ext; // 下移

(附 注 释)}/*}Printf("0ut Of Memory!?

(附 注 释)

}

/*

}

Printf("0ut Of Memory!?n");

内存回收*/

void FREE( int num)

{

Node *q=head; in t i=1;

Node *p=head;

Node *t=n ewNode(); while(q-> nu m!=num) {

q=q->n ext; i++;

}

q->num=O;

表示此段空间已经回收*/

/*查找有无连续空闲存储空间，如果有则回收*/

WhiIe(p-> next!=NULL)

{

/*

if(p->num==0&&p->n ext- >num==0) {

t=p->n ext; p->n ext=t- >n ext;

p->space+=t->space;

free(t);

}

P=P->n ext;

}

}

/*查看分配*/

Void show()

{

int acco Un t_SPaCe=0;

Node *p=n ewNode();

Prin tf("Distributi On Of memory:' n"); for(p=head->n ext;p!=NULL;P=P->n ext) {

if(P->num==0)

Prin tf("free :%d\n",p->space);

主要 代码 结构（附 注 释）

主要 代码 结构

（附 注 释）

Prin tf("work%d:%d\n",p->nu m,p->space); acco Un t_space+=p->space;

}

Printf(" ");

}

/*主函数*/

int mai n()

{

*/init(); /*初始化，建立一个头指针指向内存区

*/

ALLoe(1,130); // 作业 1 申请 130KB

show();

,内存分配变getchar(); /*控制显示，

,内存分配变

化一次*/

ALLOe(2,60);

show();

getchar();

ALLOe(3,100);

show();

getchar();

FREE(2);// 释放空间：FREE(P)

show();

getchar();

ALLOe(4,200);

show();

getchar();

FREE(3);

show();

getchar();

主要 代码 结构

（附 注 释）

FREE(I);

show();

getchar();

ALLoe(5,140);

show();

getchar();

ALLOe(6,60);

show();

getchar();

ALLOe(7,50);

show();

getchar();

FREE(6);

show();

Prin tf("?nThe en d!?n");

getchar();

return 0;

}

/*最佳适应算法*/

#i nclude "stdlib.h"

#i nclude "stdio.h"

#in clude <malloc.h>

/*定义空闲分区链结构*/

StrUCt Node

{

int num; /*sequence number of work 序列号的工作 */

int space; /*space taken UP 占用空间 */

StrUCt Node *n ext;// 后向指针

};

typedef StrUCt Node Node;

Node *head=NULL; // 头指针，赋空

Node * array[10]; /*数组，用来存放 num=0点的指针*/

Node * before_array[10]; /* 存放 array[i] 对应的前一指针 */

Node *n ewNode()

{

return (Node*)malloc(sizeof(Node)); // 返回带头结点的链表

}

Void in it()

{

head=newNode();

head-〉next=NULL;

}

/*内存分配*/

void ALLOC(i nt num, int SPaCe)

{

int i=0,j;

Node *temp=n ewNode();

Node *p=n ewNode();

Node *q=head->n ext;

Node *s=n ewNode();

主要 代码 结构（附 注 释）

主要 代码 结构

（附 注 释）

p->space=640; p->num=O; p-> next=NULL; head->n ext=p; if(p->space>=space) { s->space=space; s->num=num; p->space-=space; s->n ext=p; head->n ext=s; return;

}

Prin tf("Out of Memory!?n");

return;

}

p=head;

q=p->n ext;

while(q!=NULL)

{ if(q_>num==O&&q_ >space>=space) {

array[i]=q; before_array[i]=p; i++;

主要 代码 结构

（附 注 释）

q=q->n ext;

P=P->n ext;

}

if(i>1)

{

for(j=0;j<i-1;j++)

{

if(array[j]->space<=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->n ext->space-=space;

r->n ext=temp-> next;

temp->n ext=r;

return;

}

/*内存回收*/

void FREE( int num)

{

Node *q=head;

in t i=1;

Node *p=head;

Node *t=n ewNode();

while(q->num!=num)

{

q=q->n ext;

i++;

}

q-> nu m=0; /* 表示此段空间已经回收 */

/*查找有无连续空闲存储空间，如果有则回收*/

WhiIe(p-> next!=NULL)

{

if(p->num==0&&p->n ext- >num==0)

{

t=p->n ext;

主要

代码

结构

(附

释)

p->n ext=t- >n ext; p->space+=t->space; free(t);

}

P=P->n ext;

}

}

/*查看分配*/

Void show()

int acco Un t_SPaCe=0;

Node *p=n ewNode();

Prin tf("Distributi On Of memory:' n"); for(p=head->n ext;p!=NULL;P=P->n ext) {

if(p->num==0)

Prin tf("free :%d\n",p->space);

else

Prin tf("work%d:%d\n",p->nu m,p->space); acco Un t_space+=p->space;

/*

}

Printf(" ");

主函数*/

int mai n()

{

init(); /*初始化，建立一个头指针指向内存区 */

ALLoe(1,130);

show();

getchar(); /*控制显示，运行时用户每从键盘上输入一次回车

,内存分配变

化一次*/

ALLOe(2,60); show(); getchar();

ALLOe(3,100); show();

getchar();

FREE(2); show(); getchar();

ALLOe(4,200); show();

getchar();

FREE(3); show();

getchar();

FREE(I); show();

getchar();

ALLoe(5,140); show();

getchar();

ALLOe(6,60); show();

getchar();

主要 代码 结构（附 注 释）

主要 代码 结构

（附 注 释）

getchar();

FREE(6); show();

Prin tf("?nThe en d!?n"); getchar();

return 0;

}

运行结果：

DiStribUti On Of memory: work1:130 free :510

DiStribUtion of memory: work1:130 work2:60 free :450

DiStribUtion of memory: work1:130 work2:60

work3:100

free :350

DiStribUtion of memory: work1:130 free :60 work3:100

free :350

DiStribUti On Of memory: work1:130 free :60

work3:100 work4:200 free :150

DiStribUtion of memory: work1:130 free :160

work4:200

主要 代码 结构（附 注 释）

主要 代码 结构

（附 注 释）

DiStribUtion of memory: free :290

work4:200

free :150

DiStribUtion of memory: work5:140

free :150

work4:200 free :150

DiStribUtion of memory: work5:140 work6:60 free :90 work4:200 free :150

DiStribUtion of memory: work5:140 work6:60 work7:50 free :40 work4:200 free :150

DiStribUtion of memory:

work5:140

主要

free :60

代码

work7:50

结构

free :40

work4:200

（附 注

free :150

释）

The end!

注释：上述表格空间不够，可以另附表格进行说明