操作系统课后习题答案

5 1 为什么对调度程序而言 区分为什么对调度程序而言 区分 CPU 约束程序和约束程序和 I O 约束程序很重要 约束程序很重要 答 在运行 I O 操作前 I 0 限制的程序只运行很少数量的计算机操作 而 CPU 约束程 序一般来说不会使用很多的 CPU 另一方面 CPU 约束程序会利用整个时间片 且不做任 何阻碍 I O 操作的工作 因此 通过给 I O 约束程序优先权和允许在 CPU 约束程序之前运 行 可以很好的利用计算机资源 5 3 考虑用于预测下一个考虑用于预测下一个 CPU 区间长度的指数平均公式 将下面的值赋给算法中的参数的区间长度的指数平均公式 将下面的值赋给算法中的参数的 含义是什么 含义是什么 A a 0 且且 t0 100 ms B a 0 99 且且 t0 10 ms 答 当 a 0 且 t0 100 ms 时 公式总是会预测下一次的 CPU 区间为 100 毫秒 当 a 0 99 且 t0 10 毫秒时 进程将给予更高的重量以便能和过去相比 因此 调度算法几乎 是无记忆的 且简单预测未来区间的长度为下一次的 CPU 执行的时间片 5 4 考虑下面一组进程 进程占用的考虑下面一组进程 进程占用的 CPU 区间长度以毫秒来计算 区间长度以毫秒来计算 进程区间时间优先级 P1103 P211 P323 P414 P552 假设在假设在 0 时刻进程以时刻进程以 P1 P2 P3 P4 P5 的顺序到达 的顺序到达 a 画出画出 4 个个 Gantt 图分别演示用图分别演示用 FCFS SJF 非抢占优先级 数字小代表优先级高 和 非抢占优先级 数字小代表优先级高 和 RR 时间片 时间片 1 算法调度时进程的执行过程 算法调度时进程的执行过程 b 每个进程在每种调度算法下的周转时间是多少 每个进程在每种调度算法下的周转时间是多少 c 每个进程在每种调度算法下的等待时间是多少 每个进程在每种调度算法下的等待时间是多少 d 哪一种调度算法的平均等待时间最小 哪一种调度算法的平均等待时间最小 答 a FCFS P1P2P3P4P5 SJF P2P4P3P5P1 非抢占优先级 P2P5P1P3P4 RR P1P2P3P4P5P1P3P5P1P5P1P5P1P5P1 b 周转时间 FCFSSJF 非抢占优先级 RR P110191619 P211112 P3134187 P4142194 P5199614 c 等待时间 FCFSSJF 非抢占优先级 RR P10969 P210001 P3112165 P4131183 P514429 d 从上表中可以看出 SJF 的等待时间最小 01011131419 0124919 016 161819 0 101112141912345678913 5 5 下面哪种调度算法能导致饥饿下面哪种调度算法能导致饥饿 a 先到先服务先到先服务 b 最短作业优先最短作业优先 c 轮转法轮转法 d 优先级优先级 答 最短作业优先和优先级调度算法能导致饥饿 因为对于优先级较低的作业来说 最短 作业优先和优先级调度算法会使其无穷等待 CPU 长期得不到调用 这就导致了饥饿问题 也叫无穷阻塞 5 9 考虑下面的动态改变优先级的抢占式优先级调度算法 大的优先级数代表高优先级 当考虑下面的动态改变优先级的抢占式优先级调度算法 大的优先级数代表高优先级 当 一个进程在等待一个进程在等待 CPU 时 在就绪队列中 但未执行 时 在就绪队列中 但未执行 优先级以 优先级以 速率改变 当它运行速率改变 当它运行 时 优先级以时 优先级以 速率改变 所有的进程在进入等待队列时被给定优先级为速率改变 所有的进程在进入等待队列时被给定优先级为 0 参数 参数 和和 可以进行设定得到许多不同的调度算法 可以进行设定得到许多不同的调度算法 a 0 是什么算法 是什么算法 b 0 时是什么算法 时是什么算法 答 a FCFS 先到先服务调度算法 当进程进入到就绪队列时 其 PCB 链接到队列的尾部 优先级以 速率改变 当 CPU 空闲时 CPU 分配给位于队列头的进程 优先级加快 以 速率改变 接着该运行进程从队列中删除 b LIFO 后进先服务调度算法 同上 当进程进入到就绪队列时 优先级以 速率改变 等待后进的进程先调度 之后轮到该进程时 优先级加快 以 速率改变 完成调度 6 1 第一个著名的正确解决两个进程的临界区问题的软件方法是第一个著名的正确解决两个进程的临界区问题的软件方法是 Dekker 设计的 两个进程设计的 两个进程 P0 和和 P1 共享以下变量 共享以下变量 booleanboolean flag 2 flag 2 initially initially false false intint turn turn 进程进程 Pi i 0 或或 1 的结构见的结构见 6 25 另一个进程为另一个进程为 Pj j 0 或或 1 证明这个算法满足临界区问 证明这个算法满足临界区问 题的所有三个要求 题的所有三个要求 do do flag i TRUE flag i TRUE while flag j while flag j if turn j if turn j flag i false flag i false while turn j while turn j do do nothingnothing flag i flag i TRUE TRUE critical critical sectionsection turn jturn j flag i FALSE flag i FALSE remainder remainder sectionsection while TRUE while TRUE 答 这个算法满足临界区问题的三个要求 1 在标记和返回变量的使用中 互斥条件是保证的 如果两个进程将它们的标识设 为真 那么只有一个进程会成功进行 即轮到的那个进程 当另一个进程更新它的返回变 量时 等待的那个进程只能进入它的临界区域 2 就绪的进程 通过标志 返回变量 这个算法没有提供严格的交替 如果一个进 程想要进入它们的临界区域 它可以将它的标识设为真 然后进入它们的临界区域 当退 出它的临界区域 它可以设置转向其他进程的值 如果这个进程想要在其他进程之前再次 进入它的临界区域 它会重复这样的进程 进入它的临界区域 在退出时转向另一个进程 3 在双 T 返回变量的使用过程中 临界等待受阻 假设两个进程想要进入它们的责 任所在的临界区域 它们都将它们的标志的值设为真 而只有轮到的那个线程可以执行 其他的线程处于等待状态 如果临界等待没有受阻 当第一个进程重复 进入 退出 它的 临界区域这一过程 Dekker 算法在一个进程中设置一个转向另一个进程的值 从而保证另 一个进程接下来进入它的临界区域 6 2 第一个将等待次数降低到第一个将等待次数降低到 n 1 范围内的正确解决范围内的正确解决 n 个进程临界区问题的软件解决方法是个进程临界区问题的软件解决方法是 由由 Eisenberg 和和 Mcguire 设计的 这些进程共享以下变量 设计的 这些进程共享以下变量 enum pstate idle pstate idle wantwant in in inin cs cs pstatepstate flag n flag n 图图 6 25 Dekker 算法中的进程算法中的进程 pi 结构结构 intint turn turn flag 的所有成员被初始化为的所有成员被初始化为 idle turn 的初始值无关紧要 在的初始值无关紧要 在 0 和和 n 1 之间 之间 进程 进程 pi 的结的结 构见图构见图 6 26 试证明这个算法满足临界区问题的所有三个要求 试证明这个算法满足临界区问题的所有三个要求 do do while TRUE while TRUE flag i flag i wantwant in in j j turn turn while jwhile j i i if flag j if flag j idle idle j j turn turn elseelse j j j 1 n j 1 n flag i flag i inin cs cs j j 0 0 while j n while j n n break critical critical sectionsection j j turn turn 1 n 1 n while flag j while flag j idle idle j j j j 1 n 1 n turnturn j j flag i flag i idle idle remainder remainder sectionsection while TRUE while TRUE 答 1 互斥 注意到一个进程只有在下列条件满足时才能进入临界区域 没有其他进程 在 CS 中有设置的标识变量 保证没有两个进程同时进入临界区域 2 有空让进 当多进程同时在 CS 中设置它们的标识变量时 检查是否有其他进程在 cs 中设置标识变量 这种情况发生时 所有的进程意识到这里存在进程竞争 在外层 while 1 的 图图 6 26 Eisenberg 和和 McGuire 算法中的进程算法中的进程 pi 结构结构 循环下进入下一次迭代 重置它们的标识变量到 want 中 这个进程仅能进入临界区域 3 有限等待 当进程 k 在打算进入临界区域时 它的标识不再置为空闲 任何序号不 在轮次和 k 之间的进程不能进入临界区域 与此同时 所有序号落在轮次和 k 之间且又 想要进入临界区域的进程能够进入临界区域 这是基于系统一直在进步的事实 这个轮次 值变得越来越接近 k 最后 要么轮次变为 k 要么没有哪些序号在轮次和 k 之间的进程 这样进程 k 就进入临界区域了 6 9 试说明如果试说明如果 wait 和和 signal 操作不再是原子化操作 那么互斥可能是不稳定的 操作不再是原子化操作 那么互斥可能是不稳定的 答 买卖操作自动递减和信号量有关的值 如果两个买卖操作在信号量的值为 1 的信号量 上执行 而且这两种操作不是自动执行的 那么这两个操作在进展中会递减信号量的值 从而干扰互斥 6 11 理发店问题 一家理发店有一间有理发店问题 一家理发店有一间有 n 把椅子的等待室和一间有一把理发椅的理发室 把椅子的等待室和一间有一把理发椅的理发室 如果没有顾客 理发师就去睡觉 如果顾客来时所有的椅子都有人 那么顾客就会离去 如果没有顾客 理发师就去睡觉 如果顾客来时所有的椅子都有人 那么顾客就会离去 如果理发师在忙 而又有空闲的椅子 那么顾客会坐在其中一个空闲的椅子上 如果理发如果理发师在忙 而又有空闲的椅子 那么顾客会坐在其中一个空闲的椅子上 如果理发 师在睡觉 顾客会摇醒他 编写一个程序来协调理发师和顾客 师在睡觉 顾客会摇醒他 编写一个程序来协调理发师和顾客 答 当系统中某一进程使用某一资源时 可以看作是消耗 且该进程称为消费者 而当某 个进程释放资源时 则它就相当一个生产者 因此此题可看作是 n 个生产者和 1 个消费者 问题 顾客作为生产者 每到来一个就使计数器 count 增加 1 以便让理发师理发 相当 于消费 至最后一个顾客 相当于产品 并且 第 1 个到来的顾客应负责唤醒理发师 如 果不是第 1 个到达的顾客 则在有空椅子的情况下坐下等待 否则离开理发店 该消息可 由计数器 count 获得 所以可以通过一个有界缓冲区把理发师和顾客联系起来通过对信号 进行 P V 操作来实现有关问题和相关描述 控制变量控制变量 waiting 用来用来记录正在等候顾客的理发师数 信号量信号量 customers 用来记录等候理发的顾客数 并用作阻塞理发师进程 信号量信号量 barbers 用来记录正在等候顾客的理发师数 并用作阻塞顾客进程 信号量信号量 mutex 用于互斥 初始化 初始化 int long waiting 0 正在等待的顾客的数目 customers barbers mutex semaphore customers 0 barbers 1 waiting 0 mutex NULL 理发师进程 理发师进程 barber begin do P customers 若无顾客 理发师睡眠 p mutex 进程互斥 waiting 等候顾客减 1 V barbes 理发师为下一个顾客理发 V mutex 开放临界区 cut hair 正在理发 while TURE 是否还有顾客 顾客进程 顾客进程 customer begin do P mutex 进程互斥 if waiting waiting 等待顾客数加 1 V customers 唤醒理发师 V mutex 开放临界区 P barbers 理发师没空 顾客等候 get haircut 顾客准备理发 else V utex 无