2023年操作系统实验报告4

计算机科学与应用系

课程设计报告

操作系统原理

姓名学号指导教师

专业计算机科学与技术S日期2023年6月5日成绩

题目动态分区分派算法的模拟

指

导

教

师

评

语

目录

1题目简述...................................错误!未定义书签。

2需求分析...................................错误!未定义书签。

2.1设计思想。错误!未定义书签。

2.2规定....................................错误!未定义书签。

2.3任务..........错误!未定义书签。

2.4运营环境......错误!未定义书签。

2.5开发工具.......错误!未定义书签。

3概要设计与具体设计错误!未定义书签。

3.1系统流程图。错误!未定义书签。

3.2算法流程图。错误!未定义书签。

4编码与实现...............................错误!未定义书签。

4.1数据结构和算法设计。错误!未定义书签。

4.2程序调试与截图...........................错误!未定义书签。

5课程设计总结18。

参考文献......................................错误!未定义书签。

附录。错误!未定义书签。

动态分区分派算法的模拟

1题目简述

动态分区分派是根据进程的实际需要，动态地为之分派内存空间。在实现可变分区分派时，

将涉及到分区分派中所用到的数据结构、分派算法和分区的分派与回收操作。常用的数据结构有

空闲分区表和空闲分区链两种，分区分派算法重要有初次适应算法、最佳适应算法、最坏适应算

法等。

本次实验通过C语言进行编程调试并运营，形象地表现出动态分区分派方式，直观地展示了

初次适应算法、最佳适应算法、最坏适应算法对内存的释放和回收方式之间的区别。加深了我对

三种算法优缺陷的理解,帮助我了解一些数据结构和分派算法，进一步加深我对动态分区存储器

管理方式及其实现过程的理解。重要问题在于，如何解决三种算法对内存的释放和回收空间的表

达。

动态分区分派又称为可变分区分派，这种分派方式并不是事先将主存划提成一块块的分区，

而是在作业进入主存时，根据作业的大小动态地建立分区，并使分区的大小正好适适应作业的需

要。因此，分区中的大小是可变的，分区的数目也是可变的。

2需求分析

2.1设计思想

(1)初次适应算法(Firstfit)

空闲分区链以地址递增的顺序连接。在分派内存时，从联手开始顺序查找，直到找到一个大小

能满足规定的空闲分区为止；然后再按照作业大小，从该分区划出一块内存空间给请求者,余下的

空闲分区仍然留在空闲链中。若从链首直至链尾都找不到一个能满足规定的分区，则本次内存分派

失败。

(2)最佳适应算法(Best—fit)

它从所有空闲区中找出能满足作业规定的、且大小最小的空闲分区，这种方法能使碎片尽量

小。为适应此算法，空闲分区表(空闲区链)中的空闲分区要按从小到大进行排序，自表头开始查找

到第一个满足规定的自由分区分派。该算法保存大的空闲区，但导致许多小的空闲区。

(4)最坏适应算法(Worstfit)

最坏适应分派算法要扫描整个空闲分区或链表，总是挑选一个最大的空闲分区分割给作业使

用。该算法规定将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链，查找时只要看第一

个分区能否满足作业规定。优点是可使剩下的空闲分区不至于太小，产生碎片的几率最小，对中、

小作业有利,同时该算法查找效率很高。

(4)内存回收(Free)

将释放作业所在内存块若改为空闲状态，删除其作业名，变为空。然后判断该空闲块是否与

其他空闲块相连,若释放的内存空间与空闲块相连时，则合并其为同一个空闲链表，同时修改开始

地址及分区大小。

2.2规定

(I)用C++语言实现程序设计；

(2)运用结构体进行相关信息解决；

(3)画出查询模块的流程图；

(4)界面和谐(良好的人机互交)，程序要有注释。

2.3任务

(1)掌握为实现多道程序并发执行，操作系统是如何通过作业调度选择作业进入内存；

(2)系统如何为进入内存的作业分派内存空间，实现多道作业同时驻留内存，就绪进程队列中

的多个进程是如何以分式方式共享CPU,作业运营完毕离开系统时，系统如何进行内存回

收，计算进程周转时间；

(3)画出所有模块的流程图；

⑷编写代码；

(5)程序分析与调试。

2.4运营环境

(l)WINDOWS2023/XP系统

(2)MicrosoftVisualC++6.0编译环境

2.5开发工具

C++语言

本程序采用C语言编写，在Windows下的VisualC++环境下编译,模拟可变分区存储管

分派与回收。

计与具体设计

程图

系统流程图

图3.1.1系统流程图

3.2算法流程图

3.2.1内存分派流程图

图3.2.1内存分派流程图

3.2.2.初次适应算法流程图

图3.2.2初次适应算法流程图

3.2.3最佳适应算法流程图

图3.2.3最佳适应算法流程图

3.2.4最坏适应算法流程图

图3.2.4最坏适应算法流程图

3.2.5内存回收流程图

图3.2.5内存回收流程图

4编码与实现

4.1数据结构和算法设计

相关数据结构定义：

空闲分区结构：typedefstructfreearea0

线性链表结构：typedefstructDuLNode()

带头结点内存空间链表结构：StatusInitb1ock()

内存分派：Statusa11oc()

显示主存:voidshow()

测试类(主函数类):c1assTestForMemManage

4.2程序调试与截图

1)首界面

二二二m懑懑熊籁懑

<1)首次适应算法<2)最佳适应算法(3〉最坏适应算法

卜青选容分者己算法：.

2)初次适应算法

测试数据：为作业申请空闲区800KB。作业1申请资源lOOkb,作业2申请资源120kb,作业

3申请资源13Okb,作业4申请资源140kb,释放作业1和作业3,作业5申请资源160kb,

这时,按照表从头开始查询，第一个找到满足条件的就停止查找,并分派资源。运营结果如下图所

示：

＜1＞首次适应算法＜2＞最佳适应算法＜3＞最坏适应算法

号变垮啰漫空1,^

2：哂收内存

。：退出

请簸入.好臊祚一

请输入器业⑵区号＞，1

请输入需要分配的主存大小（单位:KB＞：100

分配成功!

炳

划收

内北

/存2

普

1:W退

栏0

3:你

入:1

区

需

入

业

嘉

盘:2

晅

需

次

人

存

要20

功

成

配！

1：分配内存2:回收内存

3：查看分配0：退出

请

请版人祥业⑵区号M3

请隔人需要分配的主存大小（单位:KB＞,130

分刻成功!

内

收内

1:1回

3:退

入

森

请

戳

人

请H

篇

人

分

^翳

<成

配

刀

一

二

一„„

讷

存

收内

/2回

幺

1:W退

用0

3:你

请

入:1

区

常

业

篇

请

入

盘

珀

需

请

人

要

功

分

成

配

收内

2回S

0退

3

主存分配情况

1

:区楼0

100KB

已分配

又a

2

_地

大100

120KB

已分配

区区s

3

始

地

区220

大t

130KB

已分配

区X5

地4

始

区350

大4

140KB

已分配

2始地昴；490

1:2：哂收内存

3:：退由

人0

H主

入

十

月1

3）最佳适应算法

测试数据:为作业申请空闲区800KBo作业1申请资源105kb,作业2申请资源115kb,

作业3申请资源125kb,作业4申请资源135kb,释放作业2和作业4,作业5申请资源145kb,

这时,在每次的分派内存中，总是找到既满足规定又是最小空闲分区,然后分派资源，这样,就避免

了“大材小用”的问题。运营结果如下图所示：

＜1＞首次适应算法＜2＞最佳适应算法＜3＞最坏适应算法

青选择分配算法：2

内

存

”收

内

2回2

一

1:0退

翻

主

3:入

E0

主

入

»<翳

工

EB翕.

存

单缶

至

入

E0知KK

个

成

配

收内

1/2回

:翁

0退

你

H•3:入

里

崔

入2

里.

需.1

存

R入S

功

分

成

田

一

收内

鬻

i2回S

退

1:的0

主

3:入

业

星

入3

星

要n

大

入

可

成

配

・

介

收内

鬻

宗

2回

退

1:的0

青.

3:入

你

业

主

律

入

呈

要

需

R入

分

功

成

配

！

收内

鲁酉世

回

1:

退

潘

铲

3:入

鳌

青

日

程

入

生

也5

冬

R入

需

医

次

青

成

功

介

配

1：至尊内存2:增收内存

3：查看分配。：退出

青输入您赫根：3

H+++++++++++++++++++++++++++++++++'

4）最坏适应算法

测试数据：为作业申请空闲区800KB。作业1申请资源80kb,作业2申请资源10Okb,作

业3申请资源120kb，作业4申请资源140kb,释放作业1和作业3,作业5申请资源160kb,

这时，在扫描整个空闲分区链表时，总是找到既满足规定又是最大空闲分区，然后把它分割给作

业。运营结果如下图所示：

鬻

收内

回

1:退

3:的

青

入

・

业•

号

青

入1

一

要

青

入KB80

！

分

成

di小

收内

W2回8

1:0退

3:保

入

青

—

盘

备

入

青F2

需

大

入

青

功

配

成

分

Y2M

收

窜

鬻

内

12回

1:

退

的0

3:

入_

青

你

业

入

崔

青3

入

要

次

需

青20

成

功

配

！

分

02

收

存

内

/2回8

冬

1:退

栏

一0

青3:

入

体

区:

青

业

人

号

很4

一

的

青

入

要

需

分

成

配

功

！

收

苴

酱

内

"2回

1:退

的0

3:

青

入

你

业

青

入

番

要

位

青

入

需

单KB

分

成

功

配

！

1:2：哂收内存

3：查第0：退出

青输入您的;3

++++++

*主存分配情况

++O

+区+

始

区

心

区区,

始

地

区尘

大

:

区区

始

地

区

大

心

分谕

也

区

底

心

区

X次

地

始

区

大

尘

主存分配情况

Free

0

80KB

空闲

区号：2

始地址：80

区大小：100KB

急已分配

4区号：Free

坝台地址：180

:区大尘：120KB

，匕、：空闲

又

区

一4

始

地300

区

大140KB

已分配

440

160KB

已分配

,区号：Free

始地址：600

,区大小：200KB

恚：空闲

5课程设计总结

为期五周的课程设计，对于我个人来说是相称有难度的。在设计的过程中，有很多问题不是

很清楚,所以做起来就就很困难，刚开始的时候都有点无从下手的感觉。很多时候在碰到问题时，

基本知识都了解，但是就不知道怎么才干把它们都整合到一块，也就是说知识都是很零散的，没

有一个完整的系统。并且，又由于基础知识不牢固，使得我在这次的课程设计中感到更加力不从

心。

在设计的过程中，每走一步就会发现，思绪想出来很容易，但涉及到实现的时候，总是有点手

无足措。对于本次的课程设计，里面尚有很多需要改善的地方。一个程序的顺利出炉，少不了反

复地调试和修改。在调试的过程中，总是会发生很多错误，但在解决这些错误的时候，开始很模

糊的概念就会变得越来越清楚。其实很多错误都是很类似的，只要解决了一个，其余的就会迎刃

而解了。

“千里之行，始于足下”，通过这次课程设计,我深深体会到这句千古名言的真正含义，我今

天认真的进行课程设计，学会脚踏实地迈开这一步，就是为明天能稳健地在社会大潮中奔跑打下

坚实的基础。这次的课程设计,使我树立了对的的设计思想，培养实事求是、严厉认真、高度负责

的学习作风，加强操作能力的训练和培养严谨求实的科学作风更尤为重要。在这次设计过程中,

充足体现出自己单独设计课程的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动

成果的喜悦心情，从中发现自己平时学习的局限性和薄弱环节，从而加以填补。

通过本次实验，我掌握了实现多道程序并发执行，操作系统是如何通过作业调，选择作业进

入内存以及系统是如何为进入内存的作业分派内存空间，实现多道作业同时驻留内存，就绪进程

队列中的多个进程是如何以分式方式共享CPU,作业运营完毕离开系统时，系统如何进行内存回

收。

最后，感谢我们的荆立夏老师，老师严谨细致、一丝不苟的作风将会一直是我工作、学习中的

楷模；老师循循善诱的教导和不拘一格的教学思绪给予我无尽的启迪;这次课程设计的每个实验

细节和每个数据，都离不开老师您的细心指导。而您开朗的个性和宽容的态度，帮助我可以很顺

利的完毕了这次课程设计。祝愿老师您在以后的工作和生活中继续保持健康的身体和快乐的心情,

再次感谢!同时，也很感谢对我帮助过的同学们，谢谢你们对我的帮助和支持，让我感受到同学的

友谊和温暖。

参考文献

[1]李玲玲.C语言程序设计[M].辽宁大学出版社，2023.1

谭浩强.程序设计基础与C语言.沈阳：辽宁大学出版社,2023.1

[3]严蔚敏、吴伟民等.数据结构（C语言版）.北京:清华大学出版社，2023.

[4]汤子瀛、梁红兵等.《计算机操作系统第三版》.北京:西安电子科技大学出版社,2023.

附录

源代码

#include<iostream.h>

#include<stdlib.h>

#defineFree0//空闲状态

#defineBusy1//己用状态

^defineOK1〃完毕

#defineERROR0//犯错

#defineMAX_1ength800〃最大内存空间为800KB

typedefintStatus;

typedefstructfreearea//定义•个空闲区说明表结构

(

intID;〃分区号

Iongsize;//分区大小

Iongaddress;〃分区地址

intstate;〃状态

}ElemType；

//-----------线性表的双向链表存储结构---------------

typedefstructDuLNode//doub1elinkedlist

(

E1emTypedata；

structDuLNode*prior;〃前趋指针

structDuLNode*next;〃后继指针

}DuLNode,*DuLinkList；

DuLinkListb1ock_first;//头结点

DuLinkListblock_last；//尾结点

Statusalloc(int)；〃内存分派

Statusfreednt)；〃内存回收

StatusFirstfit(int,int);〃初次适应算法

StatusBest_fit(int,int);//最佳适应算法

StatusWorst_fit(int,int);//最坏适应算法

voidshow();〃查看分派

StatusInitblock()；//开创空间表

//--------------开创带头结点的内存空间链表---------------

StatusInitblock()

(

block_first=(DuLinkList)malloc(sizeof(DuLNode));

block_last=(DuLinkList)malloc(sizeof(DuLNode));

b1ock_first->prior=NULL;

blockfirst->next=block_1ast；

block_last->prior=block_first;

block_last->next=NULL;

biock_last—>data.address=0;

block_last—>data.size=MAX_length；

block1ast—>data.ID=0；

block_last->data.state=Free;

returnOK;

Statusal1oc(intch)

intID,request;

coutvv〃请输入作业（分区号）：”

cin»ID；

coutVC”请输入需要分派的主存大小（单位:KB）

cin>>request;

if(request<0||request==0)

cout〈V〃分派大小不合适，请重试！"«endl;

returnERROR;

}

if(ch==2)//选择最佳适应算法

(

if(Best_fit(ID,request)—OK)

。coutV〈"分派成功!〃<<end1;

eIse

。ocout<V”内存局限性，分派失败！〃<<endl;

returnOK;

)

else//默认初次适应算法

(

if(First_fit(lD,request)==0K)

c分派成功！“<Vendl;

else

次:outV<“内存局限性，分派失败!H«end1；

returnOK;

)

if(ch==3)//选择最坏适应算法

(

if(Worst_fit(ID,request)—0K)

cout<<"分派成功!”<<end1;

e1se

cout«〃内存局限性,分派失败！〃<<endl;

returnOK;

)

else〃默认初次适应算法

(

if(Firstfit(ID,request)==0K)

*cout<<"分派成功！"<<endl；

else

cout<<”内存局限性,分派失败！"<<endl;

returnOK；

)

)

//----------------------初次适应算法---------------------------------

StatusFirst_fit(intID,intrequest)〃传入作业名及申请量

(

//为申请作业开辟新空间且初始化

DuLinkListtemp=(DuLinkList)mal1oc(sizeof(DuLNode));

temp->data.ID=ID;

temp->data.size=request;

temp—>data.state=Busy;

DuLNode*p=blockfirst->next；

whi1e(p)

(

if(p->data.state==Free&&p->data.size==request)

(

。//有大小恰好合适的空闲块

p->data.state=Busy;

p—>data.ID=ID;

returnOK;

break；

)

if(p->data.state==Free&&p->data.size>request)

(

〃有空闲块能满足需求且有剩余”

temp->prior=p->prior;

temp->next=p；

temp->data.address=p—>data.address;

p->prior->next=temp;

p->prior=temp；

p->data.address=temp->data.address+temp—>data.size；

p->data.size—=request;

returnOK；

break；

}

p=p->next;

}

returnERROR；

1

//-----------------------最佳适应算法-----------------------------

StatusBest_fit(intID,intrequest)

{

intch;〃记录最小剩余空间

DuLinkListtemp=(DuLinkList)malloc(sizeof(DuLNode));

temp—>data.ID=ID;

temp->data.size=request;

temp—>data.state=Busy;

DuLNode*p=b1ock_first—>next;

DuLNode*q=NULL;〃记录最佳插入位置

whi1e(p)〃初始化最小空间和最佳位置

if(p->data.state==Free&&

(p->data.size>request|Ip—>data.size==request))

q二P；

ch=p->data.size—request;

break;

)

p=p->next;

)

whi1e(p)

(

if(p->data.state==Free&&p->data.size==request)

{

。//空闲块大小恰好合适

p->data.ID=ID;

p->data.state=Busy;

returnOK;

break;

)

if(p->data.state==Free&&p->data.size>request)

(

//空闲块大于分派需求

if(p->data.size-request<ch)〃剩余空间比初值还小

{

ch=p->data.size-request;//更新剩余最小值

q=P；〃更新最佳位置指向

)

}

p=p->next；

)

if(q==NULL)returnERROR;〃没有找到空闲块

eIse

(

“/找到了最佳位置并实现分派

temp->prior=q->prior；

temp->next=q;

temp->data.address=q->data.address

q->prior->next=temp;

q->prior=temp;

q—>data.addressd-=request;

q->data.size=ch;

returnOK;

)

//------------------------最坏适应算法--------

StatusWorst_fit(intID,intrequest)

(

intch;〃记录最大剩余空间

DuLinkListtemp=(DuLinkList)ma1loc(sizeof(DuLNode));

temp->data.ID=ID；

temp->data.size=request;

temp->data.state=Busy;

DuLNode*p=block_first->next;

DuLNode*q=NULL;〃记录最佳插入位置

whi1e(p)〃初始化最大空间和最佳位置

(

if(p->data.state==Free&&

(p->data.size>request|Ip->data.size==request))

{

q=P;

ch=p->data.size-request；

break；

)

p=p->next;

)

while(p)

(

if(p->data.state==Free&&p->data.size==request)

{

8〃空闲块大小恰好合适

p—>data.ID=ID；

p->data.state=Busy；

returnOK；

break;

)

if(p->data.state==Free&&p->data.size>request)

//空闲块小于分派需求

if(p->data.size-request>ch)//剩余空间比初值还大

ch=p—>data.size-request；〃更新剩余最大值

q=P；//更新最佳位置指向

)

)

p=p->next;

)

if(q==NULL)returnERROR;〃没有找到空闲块

else

(

M/找到了最佳位置并实现分派

temp->prior=q—>prior；

temp->next=q;

temp->data.address=q—>data.address;

q->prior->next=temp;

q->prior=temp;

q->data.address+=request；

q—>data.size=ch；

returnOK;

)

)

//-------------------------内存回收

Statusfree(intID)

DuLNode*p=block_first;

while(p)

(

if(p—>data.ID==ID)

(

p->data.state二Free;

p—>data.ID=Free;

if(p->prior->data.state==Free)〃与前面的空闲块相连

I

p->prior->data.size+=p->data,size;

p->prioi—>next=p—>next;

p->next->prior=p->prior;

)

if(p->next->data.state二二Free)//与后面