计算机操作系统专升本复习题计算题ppt课件.pptx

操作系统专升本复习 计算题 1 计算题类型1 作业调度 进程调度算法 根据先来先服务 短作业优先 优先级 高响应比优先 轮转 RR 等调度算法求作业的执行顺序 作业的周转时间 带权周转时间 平均周转时间和平均带权周转时间 2008年 8分 短作业优先 先来先服务调度算法2014年 7分 短作业优先调度算法2015年 8分 先来先服务 短作业优先调度算法2017年 10分 先来先服务调度算法 抢占式优先级调度算法 例1 在单机系统中 系统中各个进程到达就绪队列的时刻 执行时间和优先级 越小者越高 如下表所示 假设进程的调度时间忽略不计 1 请给出采用FCFS 短作业优先调度算法时各个进程的调度顺序 并计算平均周转时间和平均带权周转时间 2 请计算采用抢占式优先级调度算法时各个进程的平均周转时间和平均带权周转时间 平均周转时间 3 7 9 12 12 5 8 6平均带权周转时间 1 1 17 2 25 2 4 6 5 2 56 3 13 9 1 FCFS调度算法 平均周转时间 3 7 3 11 14 5 7 6平均带权周转时间 1 1 17 2 25 2 4 6 5 1 84 3 11 9 短作业优先调度算法 平均周转时间 3 18 4 7 7 5 7 8平均带权周转时间 1 3 1 1 4 3 5 5 1 98 3 8 20 2 采用抢占式优先级调度算法 例2 在一个单道批处理系统中 采用响应比高者优先的作业调度算法 当一个作业进入系统后就可以开始调度 假定作业都是仅计算 忽略调度花费的时间 现有三个作业 进入系统的时间和需要计算的时间如下表所示 求出每个作业的开始时间 完成时间及周转时间并填入表中 60 响应比 服务时间 等待时间 服务时间 1 等待时间 服务时间10 00计算作业2 3的响应比 如下 作业2响应比 1 50 45 2 11作业3响应比 1 45 25 2 8作业3的响应比高 因此10 00开始执行作业3 10 25完成 最后执行作业2 10 00 10 25 70 10 25 11 10 120 计算题类型2 银行家算法 如果判断某时刻是否为安全状态采用安全性算法 若安全 执行安全性算法结束写明安全序列和系统状态是安全的 如果某进程提出资源请求采用银行家算法 写清1 2 3 4步 2008年 8分 2011年 2012年 2013年 2013年真题例3 已知系统内有三个进程P1 P2 P3共享A B两类资源 A类资源的数量为8 B类资源的数量为5 设在T时刻资源分配情况如下表所示 1 问T时刻A B的可利用资源数分别是多少 2 T时刻系统是否处于安全状态 为什么 计算题类型3 地址变换 1 动态可重定位分区分配的地址变换2 分页存储管理方式的地址变换3 分段存储管理方式的地址变换2012年 选择题1分 2016年 10分 例4 2012年真题 一个32位的虚拟地址分为4个域 每个域的长度分别为a b c d位 其中d为页内地址 则系统最多可有 B 个虚拟页面 A a b cB 2a b cC dD 2d 1 动态可重定位分区分配的地址变换 例5 在分区存储管理中 已知某作业空间如图所示 采用动态重定位进行地址映射 假设分给该作业的主存空间起始地址为4000 1 指出在图中的地址1和地址2中 哪个是逻辑地址 哪个是物理地址 2 在图中填写出执行指令MOVL1 2000 时 所取数据 100 的逻辑地址 物理地址以及动态重定位寄存器的内容 用十进制表示 3 在图中填写出指令 MOVL1 2000 的主存地址 动态重定位寄存器 地址1 地址2 例6 在一分页存储管理系统中 逻辑地址长度为16位 页面大小为4096字节 现有一逻辑地址为2F6AH 且第0 1 2页依次存放在物理块5 10 11中 问相应的物理地址为多少 2 分页存储管理方式的地址变换 解析 方法1 逻辑地址2F6AH的二进制 0010111101101010 由于逻辑地址长度为16位 页面大小为4096字节 即212 所以低12为表示页内地址所以页号为2 对应块号为11 二进制1011 因为块内地址 页内地址 所以物理地址表示如下 其二进制1011111101101010 即BF6AH 例6 在一分页存储管理系统中 逻辑地址长度为16位 页面大小为4096字节 现有一逻辑地址为2F6AH 且第0 1 2页依次存放在物理块5 10 11中 问相应的物理地址为多少 解析 方法2 由于逻辑地址长度为16位 页面大小为4096字节 即212 所以低12为表示页内地址所以页号为2 对应块号为11 十六进制B 因为块内地址 页内地址 所以物理地址表示如下 所以 物理地址为BF6AH 例7 某虚拟存储器的用户空间共有32个页面 每页1KB 内存16KB 假定某时刻系统为用户的第0 1 2 3页分别分配的物理块号为5 10 4 7 给定虚拟地址093CH 请将其变换为物埋地址 逻辑地址093CH的二进制 0000100100111100 有已知得逻辑地址长度为15位 页面大小为1KB 即210 所以低10为表示页内地址所以页号为2 对应块号为4 二进制0100 因为块内地址 页内地址 所以物理地址表示如下 其二进制0001000100111100 即113CH 解析 例8 在一个段式存储管理系统中 其段表为 试求下列逻辑地址对应的物理地址是什么 3 分段存储管理方式的地址变换 1350 400 1750 解析 计算题类型4 分页存储的数据访问时间 例9 假定快表检索时间为20ns 内存访问时间为100ns 1 若能在快表中找到CPU给出的页号 CPU存取一个数据将需要的访问时间是多少 2 若不能在快表中找到CPU给出的页号 则为存取一个数据需要的访问时间是多少 3 若假定快表查找命中率为80 则其有效访问时间为多少 解析 1 则若能在快表中找到CPU给出的页号 CPU存取一个数据将需要 20 100 120ns 2 若不能在快表中找到CPU给出的页号 则为存取一个数据将需要 20 100 100 220ns 3 若假定快表查找命中率为80 则其有效访问时间为120 80 220 1 80 140ns 计算题类型5 页面置换算法 根据最佳 先进先出 最近最久未使用页面置换算法计算缺页次数和缺页率 2012年 2014年 LRU 最近最久未使用 页面置换算法 例10 2012年真题 在请求分页系统中 一个进程初始执行连续访问页面的次序为 0 2 1 3 0 2 4 0 2 1 3 4 利用FIFO页面淘汰算法 进程内存只能保存3个页面 共发生的缺页次数为 B A 8B 9C 7D 10 例11 假定分页虚拟存储系统中 某进程的页面访问踪迹为 4 3 2 1 4 3 5 4 3 2 1 5 分配给它的内存物理块数为3 1 按最佳页面置换算法 计算缺页率 2 按先进先出页面置换算法 计算缺页率 3 按LRU页面置换算法 计算缺页率 计算题类型6 磁盘调度算法 根据先来先服务 最短寻道时间优先 扫描算法 循环扫描算法 给出寻道顺序 并计算寻道总数和平均寻道长度 2008年 8分 最短寻道时间优先 扫描算法 例12 一个可移动磁头的磁盘具有200个磁道 其编号为0 199 当它刚刚结束了125道的存取后 现正在处理143道的请求 假设系统当前I 0请求序列以FIFO顺序排列如下 86 147 91 177 94 150 102 175 130 试问对以下几种磁盘调度算法而言 满足以上请求序列 磁头将如何移动 平均寻道长度是多少 1 先来先服务算法2 最短寻道时间优先算法SSTF3 扫描算法SCAN4 循环扫描算法 先来先服务算法FCFS 最短寻道时间优先算法SSTF 扫描算法SCAN 循环扫描算法CSCAN 计算题类型7 索引分配与文件最大长度 计算索引文件最大长度 计算增量式文件最大长度 2011年例13 2011年真题 简述在UNIX系统中采用混合索引方式 如果每个盘块大小是4KB 每个盘的地址要用4个字节 那么在UNIX系统中文件最大是多少 给出步骤说明 例13 2011年真题 简述在UNIX系统中采用混合索引方式 如果每个盘块大小是4KB 每个盘的地址要用4个字节 那么在UNIX系统中文件最大是多少 给出步骤说明 解析 由已知得每个盘块大小4KB 每个盘块号占4B 因此一个盘块内可以存放4KB 4B 1K个盘块 1 直接地址10项 i add 0 i add 9 可以存放10个盘块号 文件大小为10 4KB 40KB 2 一级索引地址是i add 10 存放1个索引表 1个索引表内含1K个盘块 文件大小为 1K 4KB 4MB3 二级索引地址是i add 11 文件大小为 1K 1K 4KB 4GB4 二级索引地址是i add 12 文件大小为 1K 1K 1K 4KB 4TB所以文件的最大长度为 40KB 4MB 4GB 4TB 例14 多级索引分配方式允许文件最大长度两级索引 盘块大小1KB 盘块号占4B 允许文件最大长度为多少 解析 由已知得一个索引块可含1KB 4B 256个盘块号 于是两级索引最多可含256 256 64K个盘块号 允许文件最大长度为64K 1KB 64MB 例15 已知某系统中磁盘的每个盘块大小为1KB 外存分配方法采用中的混合索引结构 其中索引节点中直接地址6项 一级索引地址2项 二级索引地址1项 每个盘块号占用4个字节 请问该系统中允许的文件最大长度是多少 解析 由已知得每个盘块大小1KB 每个盘块号占4B 因此一个盘块内可以存放1KB 4B 256个盘块 1 直接地址6项 可以存放6个盘块号 文件大小为6 1KB 6KB 2 一级索引地址2项 每个存放1个索引表 1个索引表内含256个盘块 文件大小为 256 1KB 2 512KB3 二级索引地址1项 文件大小为 256 256 1KB 64MB所以文件的最大长度为 6KB 512KB 64MB 计算题类型8 计算FAT的大小 例16 有一个大小为500M的硬盘 盘块的大小为1KB 试计算其FAT的大小 计算步骤 1 求FAT中的表项数 磁盘大小 盘块大小2 求FAT中每个表项所占存储空间 是半个字节的整数倍 3 求FAT的大小 FAT所占存储空间 FAT中的表项数 每个表项所占存储空间 1 求FAT中的表项数 500MB 1KB 500K2 求FAT中每个表项所占存储空间256K 500K 512K所以每个表项所占19位 扩展为20位 即2 5B3 求FAT的大小 500K 2 5B 1250KB 例17 假定盘块的大小为1KB 硬盘的大小为10GB 采用显示链接分配方式时 请问文件分配表只是占用多大空间 计算题类型9 查找与磁盘启动次数 例18 假定每次启动磁盘只装入一个目录盘块盘块大小1KB 文件目录共3200个FCB引入索引结点前FCB占64B 查找一个文件平均需启动磁盘次数为多少 引入索引结点后FCB占16B 文件名和索引结点指针分别占用14B和2B 查找一个文件平均需启动磁盘次数为多少 解析 1 由已知得每盘块中包含1KB 64B 16个FCB 文件目录共需占用3200 16 200个盘块 故查找一个文件平均需启动磁盘100 5次 顺序查找 2 引入索引结点后 每盘块包含1KB 16B 64个目录项 文件目录共需占用3200 64 50个盘块 故查找一个文件平均需启动磁盘25 5次 顺序查找 读索引结点取地址信息只需一次 因为索引结点在外存上是连续存放的 计算题类型10 位示图中盘块的分配和回收 教材276页第14题 例19 有一计算机系统采用如下图所示的位示图 行号 列号都从0开始编号 来管理空闲盘块 如果盘块从0开始编号 每个盘块的大小为1KB 1 现要为文件分配两个盘块 试具体说明分配过程 2 若要释放磁盘的第300块 应如何处理 解析 1 盘块的分配过程根据位示图进行盘块分配时 可分三步进行 1 顺序扫描位示图 从中找出两个值为 0 的二进制位分别为map 2 2 和map