可变分区存储管理(2012)

1、操作系统上机实验存储管理操作系统上机实验一、实验题目 可变分区存储管理采用首次适应算法二、目的与要求 通过消化理解模拟管理程序，了解存储器的分配与回收过程，体会相关数据结构在实现管理算法中的重要性。 输入一到两组实验数据，观察分配与回收的处理结果，特别是回收时邻接空闲分区的合并处理，检测其算法的正确性。三、数据结构v空闲分区链表 结点结构：分区首地址 分区大小 链接指针 addr size next struct linkk int size; int addr; struct linkk * next; struct linkk *PL;v作业表（记录作业情况）静态数组实现静态数组实现 jn

2、o addr size flag 作业号 内存地址 作业长度 标志 struct jobtab int jno； int size；struct jobtab tab20； int addr； int flag； 例：内存分配情况（假定总容量为640k）0 0 1 0 2 0 3 80k 30k 1 4 450k 50k 1 5 160k 140k 1 6 0 7 500k 80k 1 8 350k 90k 1 9 300k 50k 1 空闲分区链表情况作业表情况四、算法思想v算法实现分配：查空闲分区链表回收：考虑邻接合并v实验过程：输入操作命令代码1.分配：输入作业号及作业长度（已建立作业不

3、重复建立）2.回收：输入作业号（不存在作业不释放空间）3.可查看空闲链表情况（检测分配、回收正确性）4.可查看作业表情况（检测分配、回收正确性）五、算法流程v主程序（main（）函数）v分配程序（allocm（）函数）v回收程序（freem（）函数）v显示空闲分区链表及作业表程序（printlink（）及printtab（）函数）v 主程序（main（）函数）v 分配程序（allocm（）函数）例：新建作业8，长度为90k，（输入8 = n，90 = l） 查空闲分区链表，分区3够分配，一分为二。 空闲链表修改情况如下：内存及作业表情况见前图（红线所示）v回收程序（freem（）函数）有四种情

4、形（假定回收区首地址 = addr，长度 = length）1.空闲分区链表空，或不与任何空闲区邻接= 分配新结点空间，存入回收作业首地址及长度 插入空闲分区链（链首，链中，链尾）2.回收分区与后一空闲分区相邻接= 进行后邻接合并例：回收作业7空间（addr+length = 分区4首地址） 修改分区4首地址及分区大小（qaddr = addr； qsize = qsize+length；）合并后空闲分区链表情况如下：3.回首分区与前一空闲分区相邻接例：作业4释放空间，与分区3合并 合并后空闲分区链情况如下：4.回收分区与前同时又与后空闲分区相邻接= 需进行三个分区合并，并删除一个空闲分区结点

5、例：回收作业7后再回收作业4空间 注：除了修改空闲分区链表，还要修改作业表（清除注：除了修改空闲分区链表，还要修改作业表（清除flagflag标志）标志）v显示空闲分区链表及作业表程序（printlink（）及printtab（）函数）=上述三函数由学员自己画出流程图。六、实验步骤v消化实验算法程序v组织上机实验数据第一组：指定（见下页）第二组：自定（要求能测试各种情形）v输入上机程序，编译，运行，记录各操作步骤的运行结果（通过显示空闲分区链表及作业表）。指定操作数据 （设内存总空闲容量为640K）1.分配作业1（80k），作业3（30k），作业8（50k），作业5（140k），作业9（50k），作业6（100k），作业4（50k）2.观察（记录）空闲表及作业表情况3.回收作业8，观察结果4.分配作业7（80k），观察结果5.回收作业6, 回收作业1, 观察结果6.分配作业10（120k），观察运行