主存空间地分配与回收

1、操作系统实验报告实验三：主存空间的分配与回收实验题目采用可变式分区管理，使用首次或最佳适应算法实现主存的分配与回收实验内容主存是中央处理机能直接存取指令和数据的存储器。能否合理而有效地使用主存，在很 大程度上将影响到整个计算机系统的性能。本实验采用可变式分区管理，使用首次或最 佳适应算法实现主存空间的分配与回收。要求采用分区说明表进行。实验目的通过本次实验，帮助学生理解在可变式分区管理方式下，如何实现主存空间的分配与回 收。提示：（1）可变式分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需要,并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量，查看 是否有足够的

2、空闲空间，若有，则按需求量分割一部分给作业；若无，则作业等待。 随着作业的装入、完成，主存空间被分割成许多大大小小的分区。有的分区被作业 占用，有的分区空闲。例如，某时刻主存空间占用情况如图1所示。010K20K45K65K110K256K操作系统（10KB）作业 1（ 10KB）作业 4 （25KB）空闲区1（ 20KB）作业 2（ 45KB）空闲区2（ 146KB）表1空闲区说明表起始地址长度状态45K20KB未分配1110K146KB未分配空表目空表目空表目图1主存空间占用情况为了说明哪些分区是空闲的， 可以用来装入新的作业，必须要有一张空闲区说明表，如表1所示。其中，起始地址指出各空闲

3、区的主存起始地址，长度指出空闲区大小。状态栏未分配指该栏目是记录的有效空闲区，空表目指没有登记信息。由于分区个数不定，所以空闲区说明表中应有足够的空表目项，否则造成溢出，无法登记。同样，再设一个已分配区表，记录作业或进城的主存占用情况。(2) 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空 闲区。有时找到的空闲区可能大于作业需求量，这时应该将空闲区一分为二。一个 分给作业，另一个仍作为空闲区留在空闲区表中。为了尽量减少由于分割造成的碎 片，尽可能分配低地址部分的空闲区，将较大空闲区留在高地址端，以利于大作业 的装入。为此在空闲区表中，按空闲区首地址从低到高进行登记。为

4、了便于快速查 找，要不断地对表格进行紧缩，即让“空表目”项留在表的后部。其分配框图如图(3) 当一个作业执行完时，作业所占用的分区应归还给系统。在归还时要考虑相邻空闲区4种情况考虑:合并的问题。作业的释放区与空闲区的邻接分一下 A 释放区下邻（低地址邻接）空闲区；B 释放区上邻（高地址邻接）空闲区；C.释放区上下都与空闲区邻接；D .释放区与空闲区不邻接。首次适应算法回收框图如图 3所示。开始S=释放区始址L =释放区长度查空闲区说明表N有与释放区的 高地址邻接（上邻） 的空闲区吗？Y有与释放区下邻的空闲区吗？L =L+上邻空 闲区长度在空闲区说明表中找 一空闲表目登记： 始址=S长度二L 状

5、态=未分配把下邻空闲区登记 栏中的长度改为： 长度二长度+ L按地址顺序调 整和紧缩空闲 区说明表把上邻空闲区登记 栏中的状态置为“空表目”，且将 空表目向后调整Y有与释放区下邻的空闲区吗？N把上邻空闲区登 记栏中的始址改 为S，长度为L返回唤醒等待的作JP!业并返回有等待装入的作业吗？图3首次适应算法回收框图若采用最佳适应算法，则空闲区说明表中的空闲区按其大小排序。有关最佳适应算法 的分配和回收框图由学生自己给出。（4 ）请按首次（或最佳）适应算法设计主存分配和回收程序。以图1作为主存当前使用的基础，初始化空闲区和已分配区说明表的值。学生自己设计一个作业申请队列以及作业完成后的释放顺序，实现

6、主存的分配与回收。把空闲区说明表的变化情况以及各作业的申请、放情况显示或打印出来。为了说明哪些分区是空闲的，必须要有一张空闲区说明表，格式如下表所示:起始地址长度状态20K20K180K50K1150K100K1300K30K0 （空表目）600K100K1空表目:四、代码及运行结果分析Main .javapackage Exp4;import java.util.ArrayList;import java.util.Sca nner;public class Mai n static Scanner sca nner = new Sca nn er(System.i n);static Ar

7、rayListblockListnewArrayList();static int applicati on;static int adr;static int size;public static void main(String args) in italize();public static void in italize() /将整个存储区作为freeBlock初始化并显示信息FreeBlock freeBlock = new FreeBlock(0, 32767);blockList.add(freeBlock);pri ntAll();prin t(Please in put th

8、e way (1-best,2-first):);int way = sca nner.n ext In t();if (way = 1) bestClass();/最佳适应算法 else if (way = 2) firstClass();首次适应算法 else prin t(Error!n);public static void bestClass() int type = getRequest();if (type = 1) assig n(1, applicatio n); else if (type = 2) accept(adr, size); else prin t(Error!

9、n);bestClass();public static void firstClass() int type = getRequest();if (type = 1) assig n(2, applicatio n); else if (type = 2) accept(adr, size); else prin t(Error!n);firstClass();public static void printAII() pri nt(adrte ndtsize n);print(”n);for (FreeBlock block : blockList) block.pri ntME();pu

10、blic static int getRequest() pr in t(Assig n or Accept (1-Assig n,2-Accept):);int type = sca nner.n ext In t();if (type = 1) prin t(i nput Applicati on:”)；applicati on 二 sca nn er .n ext In t(); else if (type = 2) prin t(i nput adr and size:);adr = sca nner.n ext In t();size = sca nner.n ext In t();

11、 else prin t(Error!n);retur n type;public static boolea n assig n(i nt p_way, int p_applicati on) /判断是否有空闲区if (blockList.isEmpty() print(没有任何空闲区域可供分配！n);return false;/按各自的原则查找空闲区if (p_way = 1) / bestin t min Size = 32767;int minln dex = -1;for (FreeBlock block : blockList) if (block.getSize() = p_ap

12、plicati on) min Size = block.getSize();if (mi nln dex = -1) print(”没有符合要求的空闲区域！n);return false; else FreeBlock tempBlock1 = blockList.get(mi nln dex);if (tempBlock1.getSize() = p_application) blockList.remove(tempBlock1);prin tAll();retur n true;FreeBlocktempBlock2=newFreeBlock(tempBlock1.getAdr(),t

13、empBlock1.getSize() - p_applicati on);blockList.set( minln dex, tempBlock2);pri ntAll();return true; else if (p_way = 2) / firstint minAdr = 32766;for (FreeBlock block : blockList) if (block.getAdr() = p_applicati on) min Adr = block.getSize();minln dex = blockList.i ndexOf(block);if (mi nln dex = -

14、1) print(”没有符合要求的空闲区域！n);return false; else FreeBlock tempBlock1 = blockList.get(mi nln dex);if (tempBlock1.getSize() = p_application) blockList.remove(tempBlock1);prin tAll();retur n true;FreeBlocktempBlock2=newFreeBlock(tempBlock1.getAdr(),tempBlock1.getSize() - p_applicati on);pri ntAll();return

15、true; else prin t(Error!n);return false;public static boolean accept(int p_adr, int p_size) int p_end = adr + size - 1;/检查：首地址小于最小地址(0)if (p_adr 32766) print(错误：回收空间大于最大空间(32766)！ n); return false;/检查：回收空间和空闲空间重叠for (FreeBlock block : blockList) if (p_adr = block.getAdr() & p_adr = block.getAdr() &

16、p_end 0) retur n adr + size - 1; else return 0;public int getAdr() return adr; public void setAdr(i nt adr) this.adr = adr;public int getSize() retur n size;public void setSize(i nt size) this.size = size;最佳适应算法结果x |Javal run) K Jaa2l run) f*2I7 run:鹭言.-adrendsize3276632767Please input the way (1bes

17、tj 2first) :1Assign or Accept. (1-Assign, 2-Accept) : 1 input Applicat ion:32 767adrendsizeAssign or Accept (1 -AssignT 2-Accept.) : 1 input Application:1000没白任何空闲区域可供分配！Assign or Accept (L-Aseign, 2-Aecept):2 input adr and size: L000 3000adrendsize100039993000Java2I run) K JavaSl (run) B2HrU run:皤a

18、drendsize03276632767Please input th总 way (1-best, 2-flrst) : 1 Assign or Accept ( L-Assign, 2-Accept) :1 input Application:32767adr end sizeAssign or Accept (1-Assign* 2-Accept):1 input Applicat ion：1000 没有任何空闲区域可供分配！Asaign or Accept (L-Asaign, 2-Accept):2 input adr and size:1000 300Gadrendsize10003

19、9993000菌出K |Java21 (run) x Java21 (run) #2回 run:adr end size03276632767Please input the way (l-bestt 2first):1 Assign or Accept (1-Assign 2Acce卩t):1 input Application:32767adr end sizeAssign or Accept (1-Assign, 2-Accept):1 input Application:1000没有任何空闲区域可供分fE!Assign or Accept (1-Assign, 2-Accept) in

20、put adr and size:1000 3000 adr end sise100039993000Midi兀_Java21. run)x JavaZlL es;t T 2ft):1Ass i 尽nor Accept(1=As 吕2 Ac c ept) i1inpLitAppl iciiT ion : 32767ad itends i z eAss i gnor Accept(.1 As 吕i国n*1Ac c e-pt):1input Appl ic :2input： fidi- cnT 导 1廷轸：1 GOO 3000ic3i-eilI宮 ize1OOO39993000首次适应算法结果_Jhvr.! 1irun)*x-uin) ft-4run :邑日工*ends i ze03276632767Please input the way (1best* 2first) :2Axmijgri or A.C. c E?p t (. 1 Ak-e i gn fc 2Ac c e?p t) i 1 input App1ica