操作系统例题PPT课件

《操作系统例题PPT课件》由会员分享，可在线阅读，更多相关《操作系统例题PPT课件（42页珍藏版）》请在金锄头文库上搜索。

1、 存储管理习题 例1 1 某系统采用动态分区管理技术 某时刻在内存有三个空闲区 它们的首地址和大小分别是 空闲区1 100KB 10KB 空闲2 200KB 30KB 空闲区3 300KB 15KB 现有如下作业序列 作业1需要15KB 作业2需求16KB 作业3需求10KB 要求 1 画出该时刻内存分配图 2 用首次适应算法和最佳适应算法画出此时的自由主存队列结构 1 将作业序列装入主存之前 内存的分配图如下所示 2 首次适应算法的自由主存队列结构为 2 最佳适应算法的自由主存队列结构为 例2 2 在分页系统中地址结构长度为16位 页面大小为2K 作业地址空间为6K 该作业的各页依次存放在2

2、 3 6号物理块中 相对地址2500处有一条指令store1 4500 请给出该作业的页表和该指令的物理单元以及数据存放的物理单元 答案 页面大小为2K 即2048字节 作业地址空间6K 则占用页数为3 编号为0 1 2 依次存放在2 3 6号物理块中 作业页表如下 相对地址为2500字节 应在第2500 2048 1号页面 余数452即为页内位移 所以对应的物理块号为3 得到物理地址为2048 3 452 6596 相对地址4500 2048 2号页面 页内位移为404 对应的物理块号为6 得到物理地址为2048 6 404 12692 例3 3 某操作系统的存储管理采用页式管理系统 系统的

3、物理地址空间大小为32K 页的大小是4K 假定某进程的大小为32页 请回答如下问题 1 写出逻辑地址的格式 2 如果不考虑权限位 该进程的页表有多少项 每项至少多少位 答案 页面大小是4K 即212 进程大小是32页 即25 1 逻辑地址应有17位 其中0 11位是页内位移 12 16位是页号 2 该进程页表有32项 每项5位 例4 4 对一个将页表放在内存中的分页系统 1 如果访问内存需要 2 如果增加一个快表 且假定在快表中找到页表项的概率高达90 则有效访问时间表又是多少 假定查找快表需花的时间为0 答案 每次访问数据时 若不使用快表 则需要两次访问内存 即先从内存的页表中读出页对应的块

4、号 然后再根据形成的物理地址去存取数据 使用快表时 若能从快表中直接找到对应的页表项 则可立即形成物理地址去访问相应的数据 否则 仍需两次访问内存 1 有效访问时间为 2 有效访问时间为 例5 5 在分页存储管理系统中 逻辑地址的长度为16位 页面大小为4096字节 现有一逻辑地址为2F6AH 且0 1 2页依次存放在物理块5 10 11中 问相应的物理地址是多少 答案 分析 在分页存储管理系统中进行地址转换时 地址变换机构将自动把逻辑地址转化为页号和页内地址 如果页号不小于页表长度 则产生越界中断 否则便以页号为索引去检索页表 从中得到对应的块号 并把块号和页内位移分别送入物理地址寄存器的块

5、号和块内位移字段中 形成物理地址 答案 由分析所给条件可知 分页存储管理系统的逻辑地址结构如下图 逻辑地址2F6AH的二进制表示如下 0010111101101010页号页内位移由此可知逻辑地址2F6AH的页号为2 小于页表长度3 没有越界 该页存放在第11个物理块中 用十六进制表示块号为B 所以物理地址为BF6AH 例7 7 某虚拟存储器的用户空间共有32个页面 每页1KB 主存16KB 假定某时刻系统为用户的第0 1 2 3页分别分配的物理块号为5 10 4 7 试将虚拟地址0A5C和093C变换为物理地址 答案 虚拟地址为0A5C 对应的二进制数为 0000101001011100 其中

6、 页内偏移量占10位地址码 为25C 因第 页存储在 号块中 其基地址为 0001000000000000 这样 虚拟地址为十六进制的125C 虚拟地址为093C 对应的二进制数为 0000100100111100 其中 页内偏移量占10位地址码 为13C 因第2号页存储在4号块中 其基地址为 0001000000000000 01000100111100 这样 虚拟地址为十六进制的113C 例8 8 在采用页式存储管理的系统中 某作业J的逻辑地址空间为4页 每页2048字节 且已知该作业的页面映像表 即页表 如下 试借助地址变换 要求画出地址变换图 求出有效逻辑地址4865所对应的物理地址

7、分析与解答 逻辑地址4865指的是2号页中偏移地址为769的存储单元 4865 4096 769 而内存6号块的起始地址是12288 2048 6 因此对应的物理地址为13057 12288 769 地址变换图如下 例9 9 设一段表如图所示那么 逻辑地址 2 88 对应的物理地址是多少 逻辑地址 4 100 所对应的物理地址是多少 分析与解答 1 2号段所占的内存空间基地址是90 段内地址是88 因此访存的物理地址应当是二者相加 90 88 178 2 在分段存储管理系统中 段的长度是不固定的 因此段表内需要登记各段的实际长度 用以检查CPU产生的访存地址是否超界 题中第2部分给出的段内地址

8、是100 而段的长度是96 因此将产生越界中断 无任何物理地址产生 例10 10 某页式存储管理系统中 地址寄存器长度为24位 其中页号占14位 则主存的分块大小应该是多少字节 程序最多占有多少页 分析与解答 主存的分块大小占10位 应为1K个字节 即210 程序最多可以占有16K个页 即214 0 9 10 23 逻辑地址 在分页机制中 需要将用户的线性地址空间划分成二维地址空间 让地址的高位部分作为页号 低位部分作为分块的大小 也称位移量 例11 11 某虚拟存储器的用户空间共有32个页面 每页1K 主存16K 假定某时刻系统为用户的第0 1 2 3页分配的物理块号为5 10 4 7 而该

9、用户作业的长度为6页 试将十六进制的虚拟地址0A5C转换成物理地址 分析与解题 逻辑地址有15位 其中高5位为页号 低10位为页内地址 物理地址有14位 其中高4位为块号 低10位为块内地址 逻辑地址 0A5C 16的页号为 00010 2 即2 故页号合法 从页表中找到对应的内存块号为4 即 0100 2 与页内地址 1001011100 2拼接形成物理地址 01001001011100 2 即 125C 16 逻辑地址 0 5 A 1 C C 5 2 物理地址125C 页号2 块号4 页内地址25C 块内地址25C 例12 在一个使用交换技术 Swapping 的系统中 按地址从低到高排列

10、的内存空间长度是 10KB 4KB 20KB 18KB 7KB 9KB 12KB 15KB 对于下列顺序段的请求 1 12KB 2 10KB 3 15KB 4 18KB 5 12KB分别使用首次适配 最佳适配 最差适配和下次适配算法说明空间的使用情况 并说明对暂时不能分配情况的处理方法 分析与解题 首次适配 1 12KB 2 区 2 10KB 0 区 3 15KB 3 区 4 18KB 失败 5 12KB 6 区最佳适配 1 12KB 6 区 2 10KB 0 区 3 15KB 7 区 4 18KB 3 区 5 12KB 2 区最差适配 1 12KB 2 区 2 10KB 3 区 3 15KB

11、 7 区 4 18KB 失败 5 12KB 6 区下次适配 1 12KB 2 区 2 10KB 3 区 3 15KB 7 区 4 18KB 失败 5 12KB 6 区上述算法中 只有最佳适配算法是分配成功的 其他3种算法都在第4段请求 18KB 出现时分配失败 当出现暂时不能分配的情况时 系统可以采用拼接技术 将内存中的进程移动到存储器的一端 使夹杂于其间的空闲小空间移动到另一端 形成一个较大的可用空间 以满足用户的需求 例13 13 某页式存储管理系统中 地址寄存器长度24位 其中页号占14位 则主存的分块大小应该是 字节 程序最多占有 页 A 210B 10C 14D 214E 24F 2

12、24 分析与解答 本题的考核要点是内存分页管理机制 主要涉及页面长度的划分方法 我们知道 在分页机制中 需要将用户的线性地址空间划分成二维地址空间 让地址的高位部分作为页号 低位部分作为分块的大小 也称位移量 见下图所示 主存的分块大小占10位 应为1K个字节 即210 因此 第1个选项是A 程序最多可以占有16K个页 即214 第2个选项是D 例14 14 假设一个分页存储管理系统具有快表 多数活动页表项都可以存在其中 如果页表放在内存中 内存访问时间是1 s 若快表的命中率是85 则有效存取时间为多少 若快表的命中率为50 那么有效存取时间为多少 分析与解答 本题的考核要点是内存分页存储管

13、理中 具有快表机制的访问过程 涉及的内容有 1 当快表的命中率是85 时 有效存取时间为 0 85 1 1 0 85 1 1 1 15 m2 当快表的命中率是50 时 有效存取时间为 0 5 1 1 0 5 1 1 1 5 m 例15 15 在可变式分区分配方案中 某一作业完成后系统收回其主存空间 并与相邻空闲区合并 为此需修改空闲区表 造成空闲数减1的情况是 A 无上邻空闲区 也无下邻空闲区B 有上邻空闲区 但无下邻空闲区C 有下邻空闲区 但无上邻空闲区D 有上邻空闲区 也有下邻空闲区 分析与解答 本题的考核要点是可变分区管理系统的空闲分区回收问题 当用户归还一个空闲分区后 系统在挂入空闲分

14、区链表时需要将相邻空闲分区合并 形成一个大的空闲分区 因此涉及的内容有 1 无上邻空闲区 也无下邻空闲区的情况下 系统将回收的空闲分区挂入空闲链表 使空闲分区总数增加1 2 有上邻空闲区 但无下邻空闲区的情况下 系统将回收的空闲分区并入上邻分区中 使空闲分区总数不增不减 3 有下邻空闲区 但无上邻空闲区的情况下 系统将回收的空闲分区并入下邻分区中 使空闲分区总数不增不减 4 有上邻空闲区 也有下邻空闲区的情况下 系统将回收的空闲分区与上 下邻分区合并为一个大分区 使空闲分区总数减1 例16 16 在一个请求分页存储管理系统中 一个作业的页面走向为4 3 2 1 4 3 5 4 3 2 1 5

15、当分配给该作业的物理块数分别为3 4时 试计算采用下述页面淘汰算法时的缺页率 假设开始执行时主存中没有页面 并比较所得结果 1 最佳置换淘汰算法 2 先进先出淘汰算法 3 最近最久未使用淘汰算法 题解 1 根据所给页面走向 使用最佳页面淘汰算法时 页面置换情况如下所示 缺页率 7 12 A 题解 缺页率 6 12 B 题解 2 根据所给页面走向 使用先进先出页面淘汰算法时 页面置换情况如下所示 缺页率 9 12 A 题解 缺页率 10 12 B 由上述结果可以看出 对先进先出算法而言 增加分配给作业的内存块数反而使缺页率上升 这种异常现象称为Belady现象 题解 3 根据所给页面走向 使用最

16、近最久未使用页面淘汰算法时 页面置换情况如下所示 缺页率 10 12 A 题解 缺页率 8 12 B 由上述结果可以看出 增加分配给作业的内存块数可以降低缺页率 例17 17 有一页式系统 其页表存放在主存中 1 如果对主存的一次存取需要1 5 m 试问实现一次页面访问的存取时间是多少 2 如果系统加有快表 平均命中率为85 当页表项在快表中时 其查找时间忽略为0 试问此时的存取时间为多少 解答 若页表存入在内存中 则要实现二次页面访问需要两次访问主存 一次是访问页表 确定所存取页面的物理地址 第二次才根据该地址存取页面数据 1 由于页表存在主存 因此 CPU必须两次访问主存才能获得所需数据 所以实现一次页面访问的存取时间为 1 5 2 3 m 2 在系统增加了快表后 在快表中找到页表项的概率为85 所以实现一次页面访问的存取时间为 0 85 1 5 1 0 85 2 1 5 1 725 m 例18 某请求分页存储管理系统使用一级页表 假设页表总在主存中 1 如果一次存储器访问需要200ns 那么访问一个数据需要多长时间 2 现在增加一个快表 在命中或失误时均有20ns的开销 假设快表