精选资料，欢迎下载
精选资料，欢迎下载
'?南昌大学实验报告
学生姓名： 马江涛 学 号：8000612091 专业班级： 计算机软件 121班
实验类型：□验证□综合□设计□创新实验日期：2014-05-08 实验成绩:
【实验要求】
1、 编程实现首次适应算法和最佳适应算法的动态分区分配的分配过程和回 收过程。其中，空闲分区通过分区链来管理；在进行内存分配时，系统优先使用 空闲区低端的空间。
2、 假设初始状态下，可用内存空间为 640K,并依次有下列请求序列：
1） 作业1申请130KB
2） 作业2申请60KB
3） 作业3申请100KB
4） 作业2释放60KB
5） 作业4申请200KB
6） 作业3释放100KB
7） 作业1释放130KB
8） 作业5申请140KB
9） 作业6申请60KB
10） 作业7申请50KB
11） 作业6释放60KB
请分别用首次适应算法和最佳适应算法进行内存块的分配和回收， 要求每次
分配和回收后显示出空闲内存分区链的情况【可参考后文的实验提示】 。
3、 上机时认真的进行测试，输入不同的资源分配请求，写出实验结果；
4、 具体要求：
（1） 对你的程序关键代码处进行注释。
（2） 给出实验数据，对结果进行分析，说明对相关知识点的理解。
【实验目的】
了解动态分区分配方式中使用的数据结构和分配算法， 并进一步加深对动态
分区存储管理方式及其实现过程的理解。
【实验思路】
首次适应算法（First-fit ）：当要分配内存空间时，就查表，在各空闲区中 查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查 找，并把它分配出去；如果该空闲空间与所需空间大小一样， 则从空闲表中取消
该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区 始址。
最佳适应算法（Best-fit ）:当要分配内存空间时，就查找空闲表中满足要 求的空闲块，并使得剩余块是最小的。然后把它分配出去，若大小恰好合适，则
直按分配；若有剩余块，则仍保留该余下的空闲分区，并修改分区大小的起始地 址。
内存回收：将释放作业所在内存块的状态改为空闲状态， 删除其作业名，设 置为空。并判断该空闲块是否与其他空闲块相连， 若释放的内存空间与空闲块相 连时，则合并为同一个空闲块，同时修改分区大小及起始地址。
【实验结果分析】
【实验提示】
你的动态分区的分配与回收，程序运行结果要可视化。可参考如下运行结果 的模式。请分析如下这个结果来自于哪一种动态分配算法？？
实现可变分区的分配和回收，主要考虑的问题有三个：
第一，设计记录内存使用情况的数据表格，用来记录空闲区和作业占用的区 域；
第二，在设计的数据表格基础上设计内存分配算法；
第三，在设计的数据表格基础上设计内存回收算法。
首先，考虑第一个问题，设计记录内存使用情况的数据表格， 用来记录空间 区和作业占用的区域。
由于可变分区的大小是由作业需求量决定的，故分区的长度是预先不固定 的，且分区的个数也随内存分配和回收变动。总之，所有分区情况随时可能发生 变化，数据表格的设计必须和这个特点相适应。 由于分区长度不同，因此设计的表格应该包括分区在内存中的起始地址和长度。
由于分配时空闲区有时会变成两 个分区：空闲区和已分分区，回收内存分区时，可能会合并空闲分区，这样如果 整个内存采用一张表格记录己分分区和空闲区， 就会使表格操作繁琐。分配内存
时查找空闲区进行分配，然后填写己分配区表，主要操作在空闲区；某个作业执 行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲 区。由此可见，内存的分配和回收主要是对空闲区的操作。
这样为了便于对内存 空间的分配和回收，就建立两张分区表记录内存使用情况， 一张表格记录作业占 用分区的“己分分区表”；一张是记录空闲区的“空闲区表”。这两张表的实现方 法一般有两种：一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形 式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分分区表” 还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数。
+++++++++++++++++++++++++++++++++++++++ +++ 主存分配情况 +++
+++++++++++++++++++++++++++++++++++++++ 分区号：1
起始地址：0
分区大小：130 KB
状 态：已分配 分区号：Free
起始地址： 130 分区大小： 60 KB 状 态：空 闲
分 区 号:
3
起始地址:
190
分区大小:
100 KB
状
态:
已分配
分 区 号:
Free
起始地址:
290
分区大小:
350 KB
状
态:
空闲
********************************************
** 1: 分配内存 2: 回收内存 ** ** 3: 查看分配 0: 退 出 **
********************************************
请输入您的操作 ： 1
请输入作业 （分区号 ）：4
请输入需要分配的主存大小 （单位:KB） : 200
分配成功！
********************************************
** 1: 分配内存 2: 回收内存 **
** 3: 查看分配 0: 退 出 **
********************************************
请输入您的操作 : 3 +++++++++++++++++++++++++++++++++++++++ +++ 主 存 分 配 情 况 +++
+++++++++++++++++++++++++++++++++++++++ 分 区 号: 1
起始地址: 0
分区大小: 130 KB
状 态:已分配 分 区 号: Free
起始地址: 130
分区大小: 60 KB
状 态:空 闲 分 区 号: 3 起始地址: 190 分区大小: 100 KB 状 态:已分配
分 区 号：
4
起始地址：
290
分区大小：
200 KB
状
态：
已分配
分 区 号：
Free
起始地址：
490
分区大小：
150 KB
状
态：
空闲
********************************************
** 1: 分配内存 2: 回收内存 ** ** 3: 查看分配 0: 退 出 **
********************************************
请输入您的操作 ： 2 请输入您要释放的分区号： 3
********************************************
** 1: 分配内存 2: 回收内存 ** ** 3: 查看分配 0: 退 出 **
********************************************
请输入您的操作 ： 3 +++++++++++++++++++++++++++++++++++++++ +++ 主 存 分 配 情 况 +++ +++++++++++++++++++++++++++++++++++++++ 分 区 号：1 起始地址： 0 分区大小： 130 KB 状 态：已分配 分 区 号： Free 起始地址： 130 分区大小： 160 KB 状 态：空 闲 分 区 号：4 起始地址： 290 分区大小： 200 KB 状 态：已分配 分 区 号： Free 起始地址： 490 分区大小： 150 KB 状 态：空 闲
********************************************
** 1: 分配内存 2: 回收内存 ********************************************** 1: 分配内存 2: 回收内存 **** 3: 查看分配
********************************************
** 1: 分配内存 2: 回收内存 **
** 3: 查看分配 0: 退 出 **
********************************************
请输入您的操作 ： 1
请输入作业 （分区号 ）：5
请输入需要分配的主存大小 （单位:KB） : 140
分配成功！
********************************************
** 1: 分配内存 2: 回收内存 **
3: 查看分配 0: 退 出 **
********************************************
请输入您的操作 ： 3
+++++++++++++++++++++++++++++++++++++++
********************************************
请输入您的操作 ： 2 请输入您要释放的分区号： 1
********************************************
** 1: 分配内存 2: 回收内存 ** ** 3: 查看分配 0: 退 出 **
********************************************
请输入您的操作 ： 3 +++++++++++++++++++++++++++++++++++++++ +++ 主 存 分 配 情 况 +++ +++++++++++++++++++++++++++++++++++++++ 分 区 号： Free 起始地址： 0 分区大小： 290 KB 状 态：空 闲
分 区 号：
4
起始地址：
290
分区大小：
200 KB
状
态：
已分配
分 区 号：
Free
起始地址：
490
分区大小：
150 KB
状
态：
空闲
+++
主存分配情况
+++
+++++++++++++++++++++++++++++++++++++++
分 区 号:
5
起始地址:
0
分区大小:
140 KB
状
态:
已分配
分 区 号:
Free
起始地址:
140
分区大小:
150 KB
状
态:
空闲
分 区 号：4 起始地址： 290 分区大小： 200 KB 状 态：已分配
分 区 号:
Free
起始地址:
490
分区大小:
150 KB
状 态:
空闲
********************************************
** 1:
分配内存
2:
回收内存
**
** 3:
查看分配
0:
退
出
**
********************************************
请输入您的操作 ： 1
请输入作业 （分区号 ）：6
请输入需要分配的主存大小 （单位:KB） : 60
分配成功！
********************************************
** 1: 分配内存 2: 回收内存 **
** 3: 查看分配 0: 退 出 **
********************************************
请输入您的操作 : 3
+++++++++++++++++++++++++++++++++++++++
+++
主 存 分 配 情 况
+++
+++++++++++++++++++++++++++++++++++++++
分 区 号:
5
起始地址:
0
分区大小:
140 KB
状 态:
已分配
分 区 号: 6
起始地址： 140
分区大小： 60 KB 状 态：已分配 分 区 号： Free 起始地址： 200 分区大小： 90 KB 状 态：空 闲 分 区 号：4 起始地址： 290 分区大小： 200 KB 状 态：已分配
Free490150
Free
490
150 KB
空闲
********************************************
** 1: 分配内存 2: 回收内存 ** ** 3: 查看分配 0: 退 出 **
********************************************
请输入您的操作 ： 1 请输入作业 （分区号 ）：7 请输入需要分配的主存大小 （单位:KB） : 50 分配成功！
********************************************
** 1: 分配内存 2: 回收内存 **
** 3: 查看分配 0: 退 出 **
********************************************
请输入您的操作 : 3 +++++++++++++++++++++++++++++++++++++++ +++ 主 存 分 配 情 况 +++
+++++++++++++++++++++++++++++++++++++++ 分 区 号: 5 起始地址: 0 分区大小: 140 KB 状 态:已分配 分 区 号: 6 起始地址: 140 分区大小: 60 KB 状 态:已分配
分 区 号：
7
起始地址：
200
分区大小：
50 KB
状
态：
已分配
分 区 号：
Free
起始地址：
250
分区大小：
40 KB
状
态：
空闲
分 区 号：4 起始地址： 290 分区大小： 200 KB 状 态：已分配
分 区 号：
Free
起始地址：
490
分区大小：
150 KB
状 态：
空闲
********************************************
** 1:
分配内存
2:
回收内存
**
** 3:
查看分配
0:
退
出
**
********************************************
请输入您的操作 ： 2
请输入您要释放的分区号： 6
********************************************
** 1: 分配内存 2: 回收内存 ** ** 3: 查看分配 0: 退 出 **
********************************************
请输入您的操作 ： 3
+++++++++++++++++++++++++++++++++++++++
+++
++++++++ 分 区 号： 起始地址： 分区大小： 状 态：
主存分配情况 ++++++++++++++++++++ 5
0
140 KB
已分配
+++
++++++++++
分 区 号：
Free
起始地址：
140
分区大小：
60 KB
状 态：
空闲
分区号：7
起始地址：200
分区大小：50 KB 状 态：已分配 分区号：Free 起始地址：250 分区大小：40 KB 状 态：空闲 分区号：4
起始地址：290
分区大小：200 KB 状 态：已分配 分区号：Free
起始地址：490 分区大小：150 KB
状 态：空闲
********************************************
** 1: 分配内存 2: 回收内存 **
** 3: 查看分配 0: 退 出 **
********************************************
请输入您的操作 ：0
Press any key to con ti nue
【首次适应算法】
作业1申请130KB 作业2申请60KB 作业3申请100KB
C c "C;\DOCUMENTS AND 5ETTINOS\ADMINISTRATOR\S.[ftl\iiC4；rxriJT\Hh^^lX 常配谆试\_Drbu(A动宸:
动态分区分配方式的模拟
KXXKKXXIMKXXKKKXKKKXKKKXKKKXKIMXXKKKXK
宀1、首次适应算法 财最佳适竝算法 F
KiMKIMXKiMKXKKHiMKKHiMXKXXKXXKXXXKXXXKXXX
请选择分配萍法：i
** 丄=分配內住
** 3 :査有分配
2=回收:內存 **
氐退 tu ww
sxn.
1
入入入成
1JM
1：分配內存
□:査看片配
2：回收山存
0=退 m
範入您的扌眾作=1
命入隹业I弁区号〉.2
幕入需妥外配自勺主存大小￡甲位 亡应功！
:KB>
6S
存配
内耸
分査
存出 内
收
■ - ■-
2 0
鹤OiMS单笹
：1(D>
:100
口
具体分配情况如下:
?: ? "CiXDOCUMENTS AND SETTINCS\ADMINISTRATOR\^而'试雅六MJT'l,动喜分区分配算法\Debug\动岩分...
请输入您的揀作：3
++“号址尘沁 ++才地大 “+“国始区 二芥起龍
+ + 十况一 十邑 + + + _IL + + @ + + + + + * f 4 + +
KB配
<=分
心「」
起
IX 始地 IX大
3： 奎;
2
13 ￡0 己
0
K
幷
1
区 始地 区大
S：
3
19
10
己
0 0 分
1
区 区夫
S： X;
Fr
29
25
空
ee
&
0
□J B pu D R B酉 K西 M怀 K^T - 孑-e
夕一 0 0 4Z - 0 0 0
请输入您的操作:
2.作业2释放60KB
的分区号匚2
M M
+ + +
XX 1 :
W* 3:
1-1-1-1-
主存分 配情況
*=?==?==?==?==?==?==?==?==?==?==?=*=?==?==?==?=
一丨口丨対
薯驿蛊 0=昙收內當
HXXXHXXXHXXXHXXXHXXXHXXXHXXXXXXXXXXXXXXXXXXX
二土;
"入您
1=分配内存 吐回妆内存
□:査看分配 氐退 出
算料図鬓梵覽鬓買覽買覽覽梵買買賞梵買覽覽梵買疋寰鬓鬓買疋賢買買覽呉買鬓覽費買覽買贺覽；Kjt
1
K售状
13 诃 KB
已分配
区戮
B闲
K
0
30F
1 6 5
SA*
蠱
1MM KB
己分配
3.作业4申请200KB
e< "CADOCUMENTS AMD 5ETTINOS\ADMINISTRflTORX^面I试聲>\^1打1功專井区分配弊袪\D亡buql动奁:
?*
2：回收内存 氐退 m
请输入您的操作：
+ + + + *?- + + + + + + + + + + + *** 主存
++++++++++++
分配情况
,120 KB
=已分配
分聲伏
IX
K 0
3 0
1 6
父心
Z地大
区始区
B S
K西
M 0勺 21910己
区饌 分翠伏
KB即
艺地大 区始区 廿起疔状
B司
K蘇 0 0
9 5^VK
4 15
4.作业3释放100KB
C-A "I Ml IMIH AIMI1 HI I I IIMKH\AI>nilMIH I HA I I Hi \ I I \^J^S ^>|x 讣配 fl；A\I >r*hl lO\=*
Free
2ldld KB
已分配
惠捡也览4
?■ ?■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
**-** 1:
3；
誦悅鶴魁驛偏G專区° = 3
Z ■ iW ■ ■ ■ If ■ K ? ZEE
** 1=分配内耘
?* 3=査看?分酉己 I
诘输入您的操作?3
主行耸配情況
2：叵1收内T7 毗退 由
2：叵1收內TT
H=退 由
分E
叮止包@
；:力、B ±30 KB
jfe；己分配
“,
Free
1 30
160 KB
亩闲
490
15M
空
l(B
闹
5.作业1释放130KB
邛"LixDOCUMENTS AND 5ETTING5\ADMINI5TRATOR\^面\试鑿六阿JT\动喜分区分配算法\Debug\动臺分...
-la|x|
?* “分配内存 姑回收内存 **
** 3：香看分配 农退 由 林
脣獸驟輟腐区号;1
ww
2：回收内存 **
0： fi. tl| 林
请输入您的操作；3
+++
主存分配情况
+++
；Free
；0
■ 290 KB
=空闲
区S 分起分状
4
290
200 KB
己分配
Is 区地大 区始区 分起分状
Free
490
150 KB
空闲
l-H-HiH-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-WHiH-H-WH-H-H-WH-H-H-WH-H-HiH-H-H-H-H-H-H-H-Hf
6.作业5申请140KB 作业6申请60KB 作业7申请50KB
S "C;\DOCUMENTS AND SETTINGS\ADMINISTRATOR\ilftl\iH? AMJT\Sh^分区归 Bd耳(S'DubucA
莒霓尘心 “Z地大 -E侵 「芥起分状
主存务配情况
140 KB
己分配
6
14@
&0 KB
己分配
T7址-^ e 襄茯
200
50 KD
已分配
介起分状
Free
25@
40 KB
空闹
蓋務
4
290
200 KB
已分配
分起分状
Free
490
ICQ ](D
空闹
7.作业6释放60KB
B己
K酉
0 0 韦..
42920己
一号址小态 一蠱
一分起分状
B闲 一ee0 K 一FF2540空
- 一食
一分起分状
己
B酉
0 /T.
72050己
O迅* 一蠱 一分起分状
B 一eK 一re400 一 F :空 一食 一分起分状
KB闲 0 0
9 5 P.匸
4 1.3
【最佳适应算法】
1.作业1申请130KB 作业2申请60KB 作业3申请100KB
i：CA ”U\r)n「l IMFNTS AND 5ETTINC5\ftDMINI5TRftTOR\^面\试雅育HJT\动壽分区井配诗袪\Dubu°\动态分■“ FF F+++配++分+++ ++ +十况 ++情十存 十主++口耳 ￡++区地大++区始区++++KB配
i：
CA ”U\r)n「l IMFNTS AND 5ETTINC5\ftDMINI5TRftTOR\^面\试雅育HJT\动壽分区井配诗袪\Dubu°\动态分■“ FF F
+
++配
++分
+
+
+ +
+ +
十况 ++情
十存 十主
++口耳 ￡
++区地大
++区始区
++
++KB配
++0 分
++1013已
KB闲
e
e 0 0
r9 5^vr-
F 2
話￡
也弋 区妲区 分起分状
si
区地大 区始区 分起分状
3
KB配
0 0/^-
1910已
21360已
区饌
分起分状
B配
作业2释放60KB 作业4申请200KB
ca ■■C:\DOCUMENTS AND SETTINGS\ADMINISTRATOR\^面\试崟天MJT\动壽分区分配豈圍。曲如\动誉乐?FFT
++区地大++区始区++分起分状0130 KB己分配H 区地大 区始区 分起分状Free130 6Q KB 空闲口 Ipr^-^K
++区地大
++区始区
++分起分状
0
130 KB
己分配
H 区地大 区始区 分起分状
Free
130 6Q KB 空闲
口 Ipr^-^K心
区地大 区始区 分起分状
3
190
100 KB
己分配
小太心
E哋大
区
区妞
分樹分状
4
290
2QQ KB
己分配
口 小态 区地大 区始区 分起分状
Free
490
150 KB
空闲
作业3释放100KB
ca "ClXDOCUMENTS AND 5ETTING5\ADMINI5TRATOR\^面'试鑿六MJT\动誉分区分配宜袪辺皀bug\动”况 ++情 + ?+++配 +++分 卄存 +++主 +++++区地大++区始区卄分起分状KB配0八刀13已号址^K心区地大 区始区 分起分状ee 0-Inlxl口僅小态 区地大 区始区 分起分状:4；290
ca "ClXDOCUMENTS AND 5ETTING5\ADMINI5TRATOR\^面'试鑿六MJT\动誉分区分配宜袪辺皀bug\动
”况 ++情 + ?
+++配 +++分 卄存 +++主 +
++
++区地大
++区始区
卄分起分状
KB配
0八刀
13已
号址^K心
区地大 区始区 分起分状
e
e 0
-Inlxl
口僅小态 区地大 区始区 分起分状
:4
；290
:200 KB
：已分配
口丐±1-^-^心
也弋
区螂区
分起分状
Free
490
150 KB
空闲
** 1=分配内存 2：回收内存 ** 创
4.作业1释放130KB
4
29Q
200 KB
己分配
Free
0
290 KB 空闲
+++++++++++++++++++++++++++++++++++++++
主存分配情况
+++++++++++++++++++++++++++++++++++++++
请输入您的操作:3
冥貝貝貝弹貝貝貝区貝貝貝区咸貝貝区貝貝]<]<]< 貝KICK貝貝]<]<貝]|(]<]<]<貝]<]|(]<貝]<]<]|[貝
0、"[!\DOCUMENTS AND SETTINGS^ ADMINISTRATOR'^ [fil\MS AM JT\动喜分医分配障袪\%bug\动誉分■“
区地大 区始区 分起分状
区地大 区始区 分起分状
口 IPZ^-^K心 区地大 区始区 分起分状
KB闲
6
C 0 0 r 9 su^t
F 4
-Inlxl
** 1：分配内存 2：回收内存 **
?* 3：查看分配 乐退 出
请输入您的操作： J
5.作业5申请140KB 作业6申请60KB 作业7申请50KB"L:\DULUMtM1AMD bbl 11ML.5>\ADMINISTRATOR\^
5.作业5申请140KB 作业6申请60KB 作业7申请50KB
"L:\DULUMtM1AMD bbl 11ML.5>\ADMINISTRATOR\^面\试鑿六MJTl动态分医分RS-^\DebiigX^b^t分…
请愉入您的揀作
4-4- + + 4-4- + 4-4-4- + 4-4-4-
十 半
4-4-4-
60 KB
7
6Q
SO KE
己配
3AA
地大
殆区
介聲状
Free
110
介区＜:4
脸殆地±1； 290
好应夭4" 2on KR 伏 A:己分酉C
養*
X地大 分起龍
B2
K酉
M m分
5MI4巳
分区号：Free
起始地址；biiB
6.作业6释放60KB
-Jnl
C I "L;\DULUMENTS AND SETTINGSXADMINiS I RA I 山牍桌面\试整人 MJT'动态;W 区分配算桜\D电bu(j\动］
BW
K
60空
+
“区地大
++尽始区
”分起分状
己
B酉
K分
0 0 □
7 6 5-匚
口！^ 心 X地大 区始区 分起分状
KB闲
H
H 0 0
FF111H空
口！
X地大 E始区 分起分状
KB配
0 0为
42920已
2=回收内冇
"已
；Frc c
:630
:10 KB
=空闲
心 X地大 区始区 分起分状
区籐 分起分状
** ±=分配内冇
代码实现】
//***************************************************************
//********
动态分区分配方式的模拟
//********
制作者：马江涛
*********
*********
//********
学号：
8000612091
*********
//********
班级：计算机软件 121 班
*********
//*************************************************************** #include<iostream.h>
#include<stdlib.h> #define Free 0 // 空闲状态
#define Busy 1 // 已用状态
#define OK 1 // 完成
#define ERROR 0 // 出错
#define MAX_length 640 // 最大内存空间为 640KB
typedef int Status;
typedef struct freearea// 定义一个空闲区说明表结构
{
int ID; // 分区号
long size; // 分区大小
long address; // 分区地址
int state; // 状态
}ElemType;
// 线性表的双向链表存储结构
typedef struct DuLNode //double linked list
{
ElemType data;
struct DuLNode *prior; // 前趋指针
struct DuLNode *next; // 后继指针
}DuLNode,*DuLinkList;
DuLinkList block_first; // 头结点
DuLinkList block_last; // 尾结点
Status alloc(int);// 内存分配
Status free(int); // 内存回收
Status First_fit(int,int);// 首次适应算法
Status Best_fit(int,int); // 最佳适应算法
void show();// 查看分配
Status Initblock();// 开创空间表
Status Initblock()// 开创带头结点的内存空间链表
{
block_first=(DuLinkList)malloc(sizeof(DuLNode));
block_last=(DuLinkList)malloc(sizeof(DuLNode));
block_first->prior=NULL;
block_first->next=block_last;
block_last->prior=block_first;
block_last->next=NULL;
block_last->data.address=0;
block_last->data.size=MAX_length;
block_last->data.ID=0;
block_last->data.state=Free;
return OK;
}
// 分 配 主 存
Status alloc(int ch)
{
int ID,request;
cout<<" 请输入作业 (分区号 )：";
cin>>ID;
cout<<"请输入需要分配的主存大小 (单位:KB):";
cin>>request;
if(request<0 ||request==0)
{
cout<<" 分配大小不合适，请重试！ "<<endl;
return ERROR;
}
if(ch==2) // 选择最佳适应算法
{
"<<endl;"<<endl;if(Best_fit(ID,request)==OK) cout<<" 分配成功！
"<<endl;
"<<endl;
else cout<<" 内存不足，分配失败！ "<<endl; return OK;
}
else // 默认首次适应算法
{
if(First_fit(ID,request)==OK) cout<<" 分配成功！
else cout<<" 内存不足，分配失败！ "<<endl;
return OK;
}
// 首次适应算法
Status First_fit(int ID,int request)// 传入作业名及申请量
{
// 为申请作业开辟新空间且初始化
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); temp->data.ID=ID;
temp->data.size=request; temp->data.state=Busy;
DuLNode *p=block_first->next;
while(p)
{
if(p->data.state==Free && p->data.size==request)
{// 有大小恰好合适的空闲块
p->data.state=Busy;
p->data.ID=ID;
return OK;
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;
return OK;
break;
}
p=p->next;
}
return ERROR;
}
// 最佳适应算法
Status Best_fit(int ID,int request)
{
int ch; // 记录最小剩余空间 DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); temp->data.ID=ID;
temp->data.size=request;
temp->data.state=Busy;
DuLNode *p=block_first->next;
DuLNode *q=NULL; // 记录最佳插入位置 while(p) // 初始化最小空间和最佳位置 {
if(p->data.state==Free &&
(p->data.size>request || p->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)
{// 空闲块大小恰好合适
p->data.ID=ID; p->data.state=Busy; return OK; 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) return ERROR;// 没有找到空闲块
else
{// 找到了最佳位置并实现分配 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;
return OK;
}
}
// 主 存 回 收
Status free(int ID)
{
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)// 与前面的空闲块相连 {
p->prior->data.size+=p->data.size;
p->prior->next=p->next;
p->next->prior=p->prior;
}
if(p->next->data.state==Free)// 与后面的空闲块相连
{
p->data.size+=p->next->data.size;
p->next->next->prior=p;
p->next=p->next->next;
}
break;
}
p=p->next;
}
return OK;
}
// 显示主存分配情况
void show()
{
cout<<"+++++++++++++++++++++++++++++++++++++++\n"; cout<<"+++ 主 存 分 配 情 况 +++\n";
cout<<"+++++++++++++++++++++++++++++++++++++++\n";
DuLNode *p=block_first->next;
while(p)
{
cout<<" 分 区 号： ";
if(p->data.ID==Free) cout<<"Free"<<endl;
else cout<<p->data.ID<<endl;
cout<<" 起始地址： "<<p->data.address<<endl;
cout<<" 分区大小： "<<p->data.size<<" KB"<<endl;
cout<<" 状 态： ";
if(p->data.state==Free) cout<<" 空 闲 "<<endl; else cout<<" 已分配 "<<endl;
cout<<" "<<endl;
p=p->next;
}
}
//
主 函 数
void main()
system("color 79");
int ch;// 算法选择标记
cout<<" 动态分区分配方式的模拟 \n";
**\n";cout<<"
**\n";
cout<<"** 1) 首次适应算法 2) 最佳适应算法 **\n";
cout<<"1************************************\n";
cout<<"
1**********************************
**\n";
cout<<" 请选择分配算法：
cin>>ch;
Initblock(); // 开创空间表
int choice; // 操作选择标记
while(1)
cout<<"
******************************************
**\n";
cout<<"** 1: 分配内存 2: 回收内存
cout<<"** 3: 查看分配 0: 退 出
**\n";
**\n";
cout<<"
******************************************
**\n";
cout<<" 请输入您的操作
cin>>choice;
if(choice==1) alloc(ch); // 分配内存 else if(choice==2) // 内存回收 {
int ID;
cout<<" 请输入您要释放的分区号： cin>>ID;
free（ID）;
}
else if(choice==3) show();// 显示主存
else if(choice==0) break; // 退出
else // 输入操作有误
{
cout<<" 输入有误，请重试！ "<<endl; continue;
}
}
}
实验总结与分析】
通过本次实验，我掌握为实现多道程序并发执行，操作系统是如何通过作业 调度选择作业进入内存以及系统是如何为进入内存的作业分配内存空间， 实现多 道作业同时驻留内存，就绪进程队列中的多个进程是如何以分式方式共享 CPU，
作业运行完成离开系统时，系统如何进行内存回收。
（1）回收分区的上邻分区是空闲的，需要将这两个相邻的空闲区合并成一 个更大的空闲区，修改空闲区表。
（2）回收分区的下邻分区是空闲的，需要将这两个相邻的空闲区合并成一 个更大的空闲区，修改空闲区表。
（3）回收分区的上邻分区和下邻分区是空闲的，需要将这三个相邻的空闲 区合并成一个更大的空闲区，修改空闲区表。
（4）回收分区的上邻和下邻分区都不是空闲的，则直接将空闲区记录在空 闲区表中 ! 还加深理解了双向链表的一些操作！
Welcome !!!
欢迎您的下载,