动态分区分配存储基础管理系统

动态分辨别配存储管理系统

学院计算机科学与技术

专业一计算机科学与技术

学号__________________________

学生姓名_________________________

指引教师姓名_________________________

目录

一、课程设计目的.....................错误！未定义书签。

1、背景..............................错误！未定义书签。

2、目的］..............................错误！未定义书签。

二、课题任务描述.....................错误！未定义书签.

三、课题研发有关知识.................错误！未定义书签。

1、最佳适应算法(bestfit)..................错误！未定义书签。

2、最坏适应算法(worstfit)......................................1

3、回收内存.....................1、错误！未定义书签。

4、库函数的简介......................错误！未定义书签。

四、课题设计.........................错误！未定义书签。

1、总体构造.....................错误！未定义书签八3

2、数据构造......................…错误！未定义书签。

3、重要功能的流程图.........................5、6

4、程序的技术路线.............................7

五、带有具体注解的I源程序......................7-18

六、运营与测试...............................18-19

七、收获及改善意见..............................20

一、课程设计目的

1、背景

主存是CPU可直接访问的信息空间，合理而有效的使用贮存将在很大限度上

影响整个计算机系统日勺性能。

本课题规定模拟实现分区式主存管理机制。模拟实现多种分区管理措施以及

相应口勺主存分派以及回收算法。

2、目的

•进一步巩固和复习操作系统R勺基本知识。

•培养学生构造化程序、模块化程序设计的措施和能力。

•提高学生调试程序H勺技巧和软件设计的能力。

•提高学生分析问题、解决问题以及综合运用c语言进行程序设计的

能力。

二、课题任务描述

用高档语言编写和调试一种动态分区内存分派程序，演示实现下列两种动态

分辨别配算法

1.最佳适应算法

2.最坏适应算法

三、课题研发有关知识（涉及所用库函数的简介）

1、最佳适应算法（bestfit）

所谓“最佳”是指每次为作业分派内存时，总是把能满足规定、又是最小的

空闲分辨别配给作业，避免“大材小用”。为了加速寻找，该算法规定将所有的

空闲分区按其容量以从小到大的顺序形成一空闲分区链。这样，第一次找到日勺能

满足规定H勺空闲区，必然是最佳的。这样，在存储器中会留下许多难以运用H勺小

空闲区。

2、最坏适应算法(worstfit)

要扫描整个空闲分区表或链表，总是挑选一种最大的空闲辨别割给作业使

用，其K处是可使剩余的空闲区不至于太小，产生碎片的几率最小，对■中小作业

有力，查找效率很高。但是它会使存储器中缺少大H勺空闲分区。

3、回收内存

当进程运营完毕释放内存时，系统根据会收取口勺首址，从空闲区链中找到相

应的插入点，并考虑回收区前后与否有空闲分区，如果有，则把两个分区合并成

一种大H勺空闲分区。

4、库函数的简介

1)stdio就是指^standardbufferedinput&outpurn意思就是说带缓冲的

原则输入输出！因此了，用到原则输入输出函数时就要调用这个头文献！

2)Stdlib.h即standardlibrary原则库文献。Stdlib头文献里涉及了

C,C++语言日勺最常用的系统函数。Stdlib.h里面定义了五中类型，某些宏和通用

工具函数。类型例如:size_t,wchar_t,div_t,ldiv_t,lldiv_t;宏例如:

EXIT_FALIRE,EXIT_SUCCESS,RAND_MAX和MB_CUR_MAX(>

如下是某些常用的函数：dec置基数为10相称于'％d〃；hex置基数为16相

称于〃%X〃；oct置基数为8相称于〃%。〃；setw(n)设域宽为n个字符

四、课题设计：总体构造、所使用的数据构造、重要功能的流程图、

程序的技术路线

1、总体构造

本系统采用了最佳适应算法和最坏适应算法模拟存储器动态分区。系统运用

其中某种分派算法，从空闲分区链中找到满足祈求内存大小的分区并分派内存给

作业。假设总的内存大小为size,作业祈求H勺内存大小为request,内存碎片最

小为f。当rcqucst>siz。时，内存溢出，浮现系统错误；当roqucst〈=siz。时，

在内存中根据上述算法寻找最佳的内存分辨别配给作业。寻找到合适H勺内存分区

之后，如果size-requestCf,将此分区上口勺内存所有分派给作业；如果

size-request>f,就在此分区上分割request大小的J内存给作业，剩余内存继续

留在Id前日勺分区中。当进程运营完毕，系统找到该进程并释放其内存，根据所释

放内存H勺位置对内存进行合并。

系统流程图：如图1

国11

系统框架图：如图2

2、数据构造

(1)定义口勺全局变量：

#dcfineSIZE100//内存初始大小

SdefineMINSIZE0//碎片最小值

enumSTATE{Free,Busy}〃枚举类型，记录分区与否空闲的状态量

(2)定义H勺构造体：structsubAreaNodeo记录分区的重要数据。

(3)函数

1)voidintSubAreaO：分派初始分区内存。

2)intbestFit(inttaskld,intsize)：最佳适应算法实现函数，taskld

为作业名，size为作业申请的I内存大小。

3)intworstFit(inttaskld,intsize)：最坏适应算法实现函数，taskld

为作业名，siz。为作业申请的内存大小.

4)intfrecSubArca(inttaskld)：内存回收函数,该函数重要用于实现内

存口勺回收，根据回收内存的位置对分区进行合并操作。其中taskld为所

需回收内存的作业号。

5)voidshowSubArea()：显示空闲分区链状况。涉及起始地址，空间大小。

工作状态。作业号。

6)intmainO：主函数，重要用于显示操作界面，调用各个子函数等功能。

3、重要功能的流程图

(1)最佳适应算法Best_fit(int,int);流程图(图3)

图3

(3)最坏适应算法Worst_fit(int,int);流程图(图4)

闵A

4.程序的技术路线

本程序采用C语言编写，在windows下的VisualC++中编译，模拟可变分

区存储管理方式於J内存分派与回收。假定系统的最大内存空间为100M,判断与

否划分空闲区H勺最小限值为MINSTZE=O。初始化顾客可占用内存区的首地址为0,

大小为OMo定义一种构造体及其对象subhead实现内存H勺分派回收及分派表和

空闲表H勺登记。用最佳分派算法实现动态分派时，调用intbestFit(inttaskld,

intsize)内存分派函数，设定循环条件查找最佳空闲分区，根据找到的空闲区

大小和作业大小判断是整个分派给作业还是切割空闲区后再分派给作业,并在

“内存分派表”和“空闲分区表”中作登记。调用intfreeSubAreaCinttaskld)

函数实现内存H勺回收。顺序循环“内存分派表”找到要回收H勺作业，设立标志位

flag,当门ag=l时表达回收成功。回收内存时需考虑内存的14种合并方式，即

合并上下分区、合并上分区、合并下分区、上下分区都不合并。

五、带有具体注解的源程序

#include<stdio.h>

#include<time.h>

#include<stdlib.h>

#defineSIZE100//内存初始大小

#defineMINSIZE0//碎片最小值

enumSTATE{Free,Busy);

staticintss=0,ee=0;

structsubAreaNode{

intaddr;//起始地址

intsize;//分区大小

inttaskId;//作业号

STATEstate;//分区状态

subAreaNode*pre;//分区前向指针

subAreaNode*nxt;//分区后向指针

}subHead;

//初始化空闲分区链

voidintSubArea()

(//分派初始分区内存

subAreaNode*fir=(subAreaNode*)maIIoc(sizeof(subAreaNode));

//给首个分区赋值

fir->addr=0;

fir->size=SIZE;

fir->state=Free;

fir->taskld=-1;

fir->pre=&subHead;

fir->nxt=NULL;

//初始化分区头部信息

subHead.pre=NULL;

subHead.nxt=fir;

)

//最佳适应算法

intbestFit(inttaskId,intsize)

1

subAreaNode*tar=NULL;

inttarSize=SIZE+1;

subAreaNode*p=subHead,nxt;

while(p!=NULL)

(//寻找最佳空闲区间

if(p->state==Free&&p->size>=size&&p->size<tarSize){

tar=p;

tarSize=p->size;

1

p=p->nxt;

)

if(tar!=NULL){

//找到要分派的空闲分区

if(tar->size-size<=MINSIZE){

//整块分派

tar->state=Busy;

tar->taskld=taskld;

}eIse

//分派大小为size的区间

subAreaNode*node=(subAreaNode*)maIIoc(sizeof(subA

reaNode));

node->addr=tar->addr+size;

node->size=tar->size-size;

node->state=Free;

node->taskId=-1;

//修改分区链节点指针

node->pre=tar;

node->nxt=tar->nxt;

if(tar->nxt!=NULL){

tar->nxt->pre=node;

)

tar->nxt=node;

//分派空闲区间

tar->size=size;

tar->state=Busy;

tar->taskId=taskld;

1

printf("内存分派成功！\n");

return1;

}eIse{

//找不到合适的空闲分区

printf("找不到合适的内存分区，分派失败...\n”)；

return0;

)

)

intworstFit(inttaskId,intsize)

(

subAreaNode*tar=NULL;

inttarSize;

intmm=1;

subAreaNode*p=subHead,nxt;

while(p!=NULL&&mm==1)

{//寻找最佳空闲区间

if(p->state==Free&&p->size>=size){

tar=p;

tarSize=p->size;

mm=0;

)

eIse

p=p->nxt;

)

p=subHead.nxt;

while(p!=NULL)

{

//寻找最大空闲区间

if(p->state==Free&&p->size>=tarSize&&p->size>=size)

tar=p;

tarSize二p->size;//遍历找到最大空床区间

p=p->nxt;

1

eIse

p=p->nxt;

)

if(tar!=NULL)(

//找到要分派日勺空闲分区

if(tar->size-size<=MINSIZE){

//整块分派

tar->state=Busy;

tar->taskId=taskId;

1eIse(

//分派大小为size的区间

subAreaNode*node=(subAreaNode*)ma11oc(sizeof(subAreaNod

e));

node->addr=tar->addr+size;

node->size=tar->size-size;

node->state=Free;

node->taskId=-1;

//修改分区链节点指针

node->pre=tar;

node->nxt=tar->nxt;

if(tar->nxt!=NULL){

tar->nxt->pre=node;

)

tar->nxt=node;

//分派空闲区间

tar->size=size;

tar->state=Busy;

tar->taskId=taskId;

]

printf("内存分派成功！\n");

return1;

}eIse(

//找不到合适的空闲分区

printf("找不到合适的内存分区，分派失败...\n")

return0;

)

)

//回收内存

intfreeSubArea(inttaskId)

(

intfIag=0;

subAreaNode*p=subHead,nxt,*pp;

while(p!=NULL)

(

if(p->state==Busy&&p->taskId==taskId)\

flag=1;

if((p->pre!=&subHead&&p->pre->state==Free)

&&(p->nxt!=NULL&&p->nxt->state=Free)){

//状况1：合并上下两个分区

//先合并上区间

PP=P；

P-p->pre;

p->size+=pp->size;

p->nxt=pp->nxt;

pp->nxt->pre=p;

free(pp);

//后合并下区间

pp=p->nxt;

p->size+=pp->size;

p->nxt=pp->nxt;

if(pp->nxt!=NULL){

pp->nxt->pre=p;

)

free(pp);

}eIseif((p->pre==&subHead||p->pre->state==Busy)

&&(p->nxt!=NULL&&p->nxt->state==Free)){

//状沆2：只合并下面日勺分区

pp=p->nxt;

p->size+=pp->size;

p->state=Free;

p->taskId=-1;

p->nxt=pp->nxt;

if(pp->nxt!=NULL){

pp->nxt->pre=p;

)

free(pp);

seif(]p-)pre!=&subHead&&p->pre->state==Free)

&&(p->nxt==NULL||p->nxt->state==Busy))(

〃状况3：只合并上面日勺分区

PP=P；

p=p->pre;

p->size+=pp->size;

p->nxt=pp->nxt;

if(pp->nxt!=NULL){

pp->nxt->pre=p;

1

free(pp);

1eIse（

//状况4：上下分区均不用合并

p->state=Free;

p->taskId=-1;

1

）

p=p->nxt;

）

if（flag=1）{

//回收成功

printf（"内存分区回收成功...\n"）;

return1;

}eIse（

//找不到目日勺作业，回收失败

printf（"找不到目的作业，内存分区回收失败..八n"）;

return0;

)

)

//显示空闲分区链状况

voidshowSubArea()

printf("*********************************************\n")；

printf("**目前的内存分派状况如下:

printf("*********************************************\n")；

printfC'**起始地址I空间大小I工作状态I作业号**\n");

subAreaNode*p=subHead,nxt;

while(p!=NULL)

printfC***-------------------------------------------------**\n");

printf("**");

printf("%5dM|",p->addr);

printf("%5dM|",p->size);

printf("%5s|",p->state==Free?"Free":"Busy")：

if(p->taskld>0){

printf("%5d",p->taskId);

}eIse{

printf("")；

)

printf("**\n");

p=p->nxt;

1

printf("*********************************************\n")；

1

boolchecks(inttask)〃检测与否作业已存在，存在返回假，不存在返回真

subAreaNode*p=subHead,nxt;

while(p!=NULL)

if(p->state==Busy&&task==p->taskld)

returnfalse;

p=p->nxt;

1

1

returntrue;

)

intmain()

intoption,ope,taskld,size;

//初始化空闲分区链

intSubArea();

//选择分派算法

11:while(1)

prjntf("**********************\n")；

printf("请选择要模拟的分派算法:\n1表达最佳适应算法\n2表达最

坏适应算法\n3退出\n");

prjntf("**********************\n")；

scanf("%d",&option);

system("cIs");

if(option==1)(

printf(“你选择了最佳适应算法，下面进行算法的模拟\n");

break;

}elseif(option==2){

printf(“你选择了最坏适应算法，下面进行算法的模拟\n”);

break;

1

eIseif(option==3){

exit(0);

)

printf("错误:请输入0/1\n\n");

)

I

//模拟动态分辨别配算法

while(1)

printf("\n");

pf।ntf("*********************************************\n")"

printf("1:分派内存\n2:回收内存\n3:返回上一级菜

单\n0:退出\n\n");

printf("*********************************************\n")；

scanf("%d",&ope);

system("cIs");

if(ope=0)break;

if(ope==1){

//模拟分派内存

printf(”请输入作业号：");

scanf("%d",&taskld);

printf(”请输入需要分派的内存大小(M)：");

scanf("%d",&size);

if(size<=0){

printf("错误:分派内存大小必须为正值\n");

continue;

1

//调用分派算法

if(option==1){

bestFit(taskId,size);

1

else

worstFit(taskld,size);

//显示空闲分区链状况

showSubArea();

)eIseif(ope==2){

//模拟回收内存

printf("请输入要回收的作业号：");

scanf("%d",&taskld);

freeSubArea(taskId);

//显示空闲分区链状况

showSubArea();

}elseif(ope==3)(

goto11;

)

eIse{

printf("错误：请输入0/1/2\n");

1

)

printf("分派算法模拟结束\n");

return0;

1

六、运营与测试(调试通过的程序，重要测试用例和运营界面截图)

1.测试数据：预设总的J内存大小为100M。选择最佳适应算法，分别输入作

业号及作业H勺大小(1,10M),(2,20M),(3,10M),然后回收作业2,最后退出系统。

2.运营截图如下：

1.主界面：图5

"C:\DocuaentsandSettings\jsjxy\臬面'

选

拟的

法

请

择

八

算

配

詈r

应

适

表

示

1瞽W

售

应

适

表

2-取t

61

3退3^

图5

2.选择最佳适应算法：图6

*C:\DocuBentsandSettings\jsjxy\^ffi\Debug

E收I

分

存

配

回

收

冤

返

菜单

上

叵

退

出

图6

3.运用最佳适应算法分派内存：图7

“C:\Docu»entsandSettjxy\^ffi\Debug\te:

罂交霍基嘉己於内存大小g：10

存分配成功!

当前的内存分配情况如下:

XX-XXXXXXX,-XXXXXX-XXXXXXX-XXXXXXX-XXXX

XX起始地址:空间大小：工作状态：作业号XX

MM-------———————————————————————————————————————

图7

4.回收内存：图8

埴鲍入要回收的作业号：2

内存分区回收成功...