操作系统算法题.pdf

《操作系统算法题.pdf》由会员分享，可在线阅读，更多相关《操作系统算法题.pdf（22页珍藏版）》请在金锄头文库上搜索。

1、 1 1 在信号量机制中 若在信号量机制中 若 P P S S 操作是可中断的 则会有什么问题 操作是可中断的 则会有什么问题 答 P S 的操作如下 Begin S Value S Value 1 If S Value0 S 的值表示可继续进入售票厅的人数 S 0 表示售票厅中已有 20 名购票者 S 0 S 的值为等待进入售票厅中的人数 2 上框为 P S 下框为 V S 3 S 的最大值为 20 S 的最小值为 20 N N 为某一时刻需要进入售票厅的最多人数 5 已经系统中有四个缓冲池已经系统中有四个缓冲池 M0 M1 M2 M3 其容量分别为 其容量分别为 3 2 3 2 现各缓冲区

2、分别存在 现各缓冲区分别存在 0 1 0 2 个数据 个数据 现同时有四个进程现同时有四个进程 P0 P1 P2 P3 分别在各缓冲区间不断地移动数据 见图分别在各缓冲区间不断地移动数据 见图 3 5 例如 例如 P0 进程从进程从 M0 向向 M1 移动数据 试用信号量及其移动数据 试用信号量及其 P V 或 或 signal wait 操作及类 操作及类 Pasic C 语言描述各进程之间的同步关系 并给出各信号量的含义和初值 语言描述各进程之间的同步关系 并给出各信号量的含义和初值 答 1 互斥信号量和初值 M 0 1 M 1 1 M 2 1 M 3 1 2 同步信号量 Full i 表

3、示 buffer i 是否有数据 初值为 full 0 0 full 1 1 full 2 0 full 3 2 Empty i 表示 buffer i 是否有空间 初值为 empty 0 3 empty 1 1 empty 2 3 empty 3 0 3 进程 i 的程序 Process Proc i p full i p empty i 1 mod 5 p m i move v m i v m full i 1 mod 5 v empty i 6 设有两个优先级相同的进程设有两个优先级相同的进程 P1 和和 P2 如下 信号量如下 信号量 S1 和和 S2 的初值均为的初值均为 0 试问

4、试问 P1 P2 并发执并发执 行结束后 行结束后 x y z Y 1 Y y 2 V S1 Z y 1 P S2 Y z y 进程 进程 P2 X 1 X x 1 P S1 X x y V S2 Z x z 答 因为 P1 和 P2 是两个并发进程 所以进程调度程序调度 P1 和 P2 的顺序是不确定的 这里不妨假设 P1 先执行 进程 P1 执行到语句 P S2 时 S2 1 进程 P1 阻塞 此时 y 3 z 4 当进程调度程序调度到进程 P2 时 由于进程 P1 已执行了 V S1 进程 P2 在执行 P S1 时并未阻塞 而继续执行 当执行到 V S2 时 将 P1 唤醒 然后执行最

5、后一个语句 z x z 此时 x 5 z 9 当进 程 P1 再次被调度时 继续执行 P1 的最后一个语句 此时 y 12 最终结果是 x 5 y 12 z 9 如果当 P2 进程执行到 V S2 时 将 P1 唤醒 然后 P2 进程被中断 此时 x 5 y 3 z 4 P1 进程 开始执行然后执行最后一个语句 y z y 此时 x 5 y 3 z 7 然后 P2 进程被调度 执行 z x z 此 时 x 5 y 3 z 12 如果 P2 先执行 则执行结果与上面相同 7 在批处理系统 分时系统和实时系统中 各采用哪几个进程 作业 调度算法 在批处理系统 分时系统和实时系统中 各采用哪几个进程

6、 作业 调度算法 答 1 批处理系统中的作业调度算法有 先来先服务算法 FCFS 短作业优先算法 SJF 优 先级调度算法 HPF 和高响应比优先算法 RF 批处理系统的进程调度算法有 先进先出算法 FIFO 短进程优先算法 SPF 优先级调度算法 HPF 和高响应比优先算法 RF 2 分时系统中只设有进程调度 不设作业调度 其进程调度算法只有轮转法 RR 一种 3 实时系统中只设有进程 不设作业调度 其进程调度算法调度有 轮转法 优先级调度算法 前者适用于时间要求不严格的实时系统 后者用于时间要求严格的实时系统 后者又可细分为 非 抢占式优先级调度 抢占式优先级调度 基于时钟中断的抢占式优先

7、级调度 注意 一个纯粹的实时系统是针对特定应用领域设计的专用系统 作业提交的数量不会超过系统规 定的多道程序的道数 因而可全部进入内存 若将实时系统与批处理系统结合的话 就可以让作业 量超过多道程序道数 使优先级低的作业呆在外存的后备队列上 8 8 假设系统中有假设系统中有 5 5 个进程 它们的到达时间和服务时间个进程 它们的到达时间和服务时间见下表见下表 1 1 忽略 忽略 I OI O 以及其他开销时间 若以及其他开销时间 若 按先来先服务 按先来先服务 FCFSFCFS 非抢占的短作业优先和抢占的短作业优先三种调度算法进行 非抢占的短作业优先和抢占的短作业优先三种调度算法进行 CPUC

8、PU 调度 请给调度 请给 出各个进程的完成时间 周转时间 带权周转时间 平均周转时间和平均带权周转时间 完成表出各个进程的完成时间 周转时间 带权周转时间 平均周转时间和平均带权周转时间 完成表 2 2 表表 1 1 进程到达和需要服务时间进程到达和需要服务时间 进程进程 到达时间到达时间 服务时间服务时间 A A 0 0 3 3 B B 2 2 6 6 C C 4 4 4 4 D D 6 6 5 5 E E 8 8 2 2 表表 2 2 进程的完成时间和周转时间进程的完成时间和周转时间 进程进程 A A B B C C D D E E 平均平均 FCFSFCFS 完成时间完成时间 周转时间

9、周转时间 带权周转时间带权周转时间 SPF SPF 非抢占非抢占 完成时间完成时间 周转时间周转时间 带权周转时间带权周转时间 SPF SPF 抢占抢占 完成时间完成时间 周转时间周转时间 带权周转时间带权周转时间 答 进程 A B C D E 平均 FCFS 完成时间 3 9 13 18 20 周转时间 3 7 9 12 12 8 6 带权周转时间 1 00 1 17 2 25 2 40 6 00 2 56 SPF 非抢占 完成时间 3 9 15 20 11 周转时间 3 7 11 14 3 7 6 带权周转时间 1 00 1 17 1 75 2 80 1 50 1 84 SPF 抢占 完成

10、时间 3 15 8 20 10 周转时间 3 13 4 14 2 7 2 带权周转时间 1 00 2 16 1 00 2 80 1 00 1 59 9 一个逻辑空间最多可有一个逻辑空间最多可有 64 个页 每页个页 每页 1KB 字节 若把它映射到由字节 若把它映射到由 32 个物理块组成的存储器 个物理块组成的存储器 问 问 1 有效的逻辑地址由多少位 有效的逻辑地址由多少位 2 有效的物理 有效的物理地址由多少位 地址由多少位 答 一个逻辑空间有 64 个页 每页 1KB 字节 若把它映射到由 32 个物理块组成的存储嚣 64 26 则 1 逻辑地址有 16 位 2 物理地址有 15 位

11、说明 解此题的关键是要知道在分页管理中 页 和 块 是一样大小的 这样才知道物理存储器是 32KB 10 在某分页系统中 测得在某分页系统中 测得 CPU 和磁盘的利用率如下 试指出每种情况下的问题和措施 和磁盘的利用率如下 试指出每种情况下的问题和措施 1 CPU 的利用率为的利用率为 15 磁盘利用率为 磁盘利用率为 95 2 CPU 的利用率为的利用率为 88 磁盘利用率为 磁盘利用率为 3 3 CPU 的利用率为的利用率为 13 磁盘利用率为 磁盘利用率为 5 答 在某分页虚存系统中 在题中的 CPU 和磁盘的利用率的情况下 出现的问题和应采取的措施如 下 1 可能已出现了抖动现象 应

12、减少系统的进程数 2 系统比较正常 可考虑适当增加进程数以提高资源利用率 3 CPU 和磁盘的利用率都较低 必须增加并发进程数 11 对访问串 对访问串 1 2 3 4 1 2 5 1 2 3 4 5 指出在驻留集大小分别为 指出在驻留集大小分别为 3 4 时 使用时 使用 FIFO 和和 LRU 替换算法的缺页次数 结果说明了什么 替换算法的缺页次数 结果说明了什么 答 首先采用 FIFO 当 m 3 时 缺页次数 9 当 m 4 时 缺页次数 10 采用 LRU 算法 当 m 3 时 缺页次数 10 当 m 4 时 缺页次数 8 结果说明 FIFO 有 Belady 奇异现象 即不满足驻留

13、集增大 缺页次数一定减小的规律 另外在 m 3 时 LRU 的缺页次数比 FIFO 要多 所以 LRU 算法并不总优于 FIFO 还要看当前访问串的特点 12 一个分页存储器的页表存放在内存 一个分页存储器的页表存放在内存 1 若内存的存取周期为 若内存的存取周期为 0 6ms 则 则 CPU 从内存取一条指令 或一个操作数 需多少时间 从内存取一条指令 或一个操作数 需多少时间 2 若使用快表且快表的命中率为 若使用快表且快表的命中率为 75 则内存的平均存取周期为多少 则内存的平均存取周期为多少 答 一个分页存储器的页表存放在内存 1 因为页表放在内存 故取一条指令 或一个操作数 须访问两

14、次内存 所以需 0 6ms 2 1 2ms 的时间 2 这里家假设访问快表的时间忽略不计 命中快表时 取数只要一次访问 故此时的平均存取 周期为 0 6ms 0 75 1 2ms 1 0 75 0 75ms 13 在一个请求分页系统中 采用在一个请求分页系统中 采用 LRU 页面置换算法时 假如一个作业的页面走向为页面置换算法时 假如一个作业的页面走向为 4 3 2 1 4 3 5 4 3 2 1 5 当分配给该作业的物理内存块数 当分配给该作业的物理内存块数 M 分别为分别为 3 和和 4 时 分别计算在访问过时 分别计算在访问过 程中所发生的缺页次数和缺页率 并画出页面置换图 程中所发生的

15、缺页次数和缺页率 并画出页面置换图 解 解 访问过程中缺页情况 M 3 页面走向 4 3 2 1 4 3 5 4 3 2 1 5 最近最长时间未使用的页面 4 3 3 2 4 3 5 4 3 2 4 3 2 1 4 3 5 4 3 2 1 最近刚使用过的页面 4 3 2 1 4 3 5 4 3 2 1 5 缺页 当 M 3 时 缺页次数为 10 次 缺页率为 10 12 0 83 83 访问过程中缺页情况 M 4 页面走向 4 3 2 1 4 3 5 4 3 2 1 5 最近最长时间未使用的页面 4 3 2 1 1 1 5 4 3 4 3 2 1 4 3 5 4 3 2 4 3 2 1 4 3

16、 5 4 3 2 1 最近刚使用过的页面 4 3 2 1 4 3 5 4 3 2 1 5 缺页 当 M 4 时 缺页次数为 8 次 缺页率为 8 12 0 66 66 可见 增加分配给作业的内存块数可以减少缺页次数 从而降低缺页率 14 对于一个使用快表的页式虚存 设快表的命中率为对于一个使用快表的页式虚存 设快表的命中率为 70 内存的存取周期为 内存的存取周期为 1ns 缺页处理时 缺页处理时 若内存有可用空间或被置换的页面在内存未被若内存有可用空间或被置换的页面在内存未被修改过 则处理一个缺页中断需修改过 则处理一个缺页中断需 8000ns 否则需 否则需 20000ns 假定被置换的页面 假定被置换的页面 60 是属于后一种情况 为了保证有效存取时间不超过是属于后一种情况 为了保证有效存取时间不超过 2ns 问可接受 问可接受 的最大缺页率是多少 的最大缺页率是多少 答 设可接受的最大缺页率位 p 则有 1ns 0 7 2ns 1 0 7 p 0 4p 8000ns 0 6p 20000ns 2ns 即 0 7 0 6 2p 3200p 12000p 2 15198p 0 7