主存空间的分配教(学)案回收

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

2、是否有足够的空闲空间，若有 ，则按需求量分割一部分给作业；若无 ，则作业.专业学习资料.等待 。 随着作业的装入 、完成 ，主存空间被分割成许多大大小小的分区。有的分区被作业占用 ，有的分区空闲 。 例如，某时刻主存空间占用情况如图1所示。0操作系统 （ 10KB ）表 1空闲区说明表10K作业 1（10KB ）20K作业 4（25KB ）45K空闲区 1（ 20KB ）起始地址长度状态65K作业 2（45KB ）45K20KB未分配110K110K146KB未分配空闲区 2 （ 146KB ）空表目256K空表目图 1主存空间占用情况空表目为了说明哪些分区是空闲的，可以用来装入新的作业 ，必

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

4、留在高地址端，以利于大作业的装入 。 为此在空闲区表中，按空闲区首地址从低到高进行登记。为了便于快速查找，要不断地对表格进行紧缩，即让 “空表目 ”项留在表的后部 。 其分配框图如图 2所示 。开始申请 XK 主存J=0J=J+1查看第 J个表目的登记项状态为N“未分配”吗？Y等于长度 =XK?小于置状态为“空表目大于长度长度 XK将空表目向后移始址始址 XK登记已分配区表和空闲区表，输出系统中各数据结构的值。返回分配给作业的主存始址NJ为空闲区说明表的最后一个表目 ?Y作业等待返回图 2 首次适应算法分配框图（ 3 ）当一个作业执行完时 ，作业所占用的分区应归还给系统。在归还时要考虑相邻空闲

5、区合并的问题 。 作业的释放区与空闲区的邻接分一下4 种情况考虑 ：A 释放区下邻 （低地址邻接 ）空闲区 ；.专业学习资料.B 释放区上邻 （高地址邻接 ）空闲区 ；C释放区上下都与空闲区邻接；D 释放区与空闲区不邻接。首次适应算法回收框图如图3 所示。开始N有与释放区下邻的空闲区吗 ?N在空闲区说明表中找一空闲表目登记：始址 S长度 L状态未分配按地址顺序调整和紧缩空闲区说明表S=释放区始址L 释放区长度查空闲区说明表有与释放区的高地址邻接（上邻）的空闲区吗 ?YY把上邻空闲区登记栏中的状态置为“空表目”，且将空表目向后调整把下邻空闲区登记栏中的长度改为：长度长度LYL L 上邻空闲区长度

6、有与释放区下邻的空闲区吗 ?N把上邻空闲区登记栏中的始址改为 S，长度为 L有等待装入唤醒等待的作的作业吗？业并返回返回图 3 首次适应算法回收框图若采用最佳适应算法，则空闲区说明表中的空闲区按其大小排序。有关最佳适应算法的分配和回收框图由学生自己给出。.专业学习资料.（4 ）请按首次 （或最佳 ）适应算法设计主存分配和回收程序。以图 1 作为主存当前使用的基础 ，初始化空闲区和已分配区说明表的值。学生自己设计一个作业申请队列以及作业完成后的释放顺序，实现主存的分配与回收。把空闲区说明表的变化情况以及各作业的申请、释放情况显示或打印出来。为了说明哪些分区是空闲的，必须要有一张空闲区说明表，格式

7、如下表所示：起始地址长度状态20K20K180K50K1150K100K1300K30K0（空表目 ）600K100K1空表目四、代码及运行结果分析Main.javapackage Exp4;.专业学习资料.public class Main static Scanner scanner = new Scanner(System.in);static ArrayList blockList = new ArrayList();static int application;static int adr;static int size;public static void main(String

8、args) initalize();public static void initalize() / 将整个存储区作为 freeBlock 初始化并显示信息FreeBlock freeBlock = new FreeBlock(0, 32767); blockList.add(freeBlock); printAll();print(Please input the way (1-best,2-first):); int way = scanner.nextInt();.专业学习资料.if (way = 1) bestClass();/ 最佳适应算法 else if (way = 2) fir

9、stClass();/ 首次适应算法 else print(Error!n);public static void bestClass() int type = getRequest();if (type = 1) assign(1, application); else if (type = 2) accept(adr, size); else print(Error!n);bestClass();.专业学习资料.public static void firstClass() int type = getRequest();if (type = 1) assign(2, applicatio

10、n); else if (type = 2) accept(adr, size); else print(Error!n);firstClass();public static void printAll() print(adrtendtsizen);print(-n);for (FreeBlock block : blockList) block.printME();public static int getRequest() .专业学习资料.print(Assign or Accept (1-Assign,2-Accept):); int type = scanner.nextInt();

11、if (type = 1) print(input Application:);application = scanner.nextInt(); else if (type = 2) print(input adr and size:); adr = scanner.nextInt(); size = scanner.nextInt(); else print(Error!n);return type;public static boolean assign(int p_way, int p_application) / 判断是否有空闲区if (blockList.isEmpty() prin

12、t( 没有任何空闲区域可供分配！n);return false;/ 按各自的原则查找空闲区.专业学习资料.if (p_way = 1) / bestint minSize = 32767;int minIndex = -1;for (FreeBlock block : blockList) if (block.getSize() = p_application) minSize = block.getSize();minIndex = blockList.indexOf(block);if (minIndex = -1) print( 没有符合要求的空闲区域！n);return false;

13、else FreeBlock tempBlock1 = blockList.get(minIndex);if (tempBlock1.getSize() = p_application) blockList.remove(tempBlock1);printAll();return true;.专业学习资料.FreeBlock tempBlock2 = new FreeBlock(tempBlock1.getAdr(),tempBlock1.getSize() - p_application);blockList.set(minIndex, tempBlock2);printAll();retu

14、rn true; else if (p_way = 2) / firstint minAdr = 32766;int minIndex = -1;for (FreeBlock block : blockList) if (block.getAdr() = p_application) minAdr = block.getSize();minIndex = blockList.indexOf(block);if (minIndex = -1) print( 没有符合要求的空闲区域！n);return false; else .专业学习资料.FreeBlock tempBlock1 = block

15、List.get(minIndex);if (tempBlock1.getSize() = p_application) blockList.remove(tempBlock1);printAll();return true;FreeBlock tempBlock2 = new FreeBlock(tempBlock1.getAdr(),tempBlock1.getSize() - p_application); blockList.set(minIndex, tempBlock2); printAll();return true; else print(Error!n);return fal

16、se;.专业学习资料.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() & p_end 0) return adr + size - 1; else return 0;.专业学习资料.public int getAdr() return adr;public void setAdr(int adr) this.adr = adr;public i