操作系统--进程调度习题课件.ppt

1、第3章 进程调度习题【例】在三种基本类型的操作系统中，都设置了进程调度，在批处理系统中还应设置()调度A 作业B 进程C 中级D 多处理机【答案】A【例】下列算法中，（）只能采用非抢占调度方式A 高优先权法B 时间片轮转法C FCFS调度算法D 短作业优先算法【解答】C【例】最适合分时系统的进程调度算法是（）A FCFSB SSJFC 优先数法D 轮转法【解答】D【例】进程调度是从（）选择一个进程投入运行。A 就绪队列B 等待队列C 作业后备队列D 提交队列【解答】A【例】进程调度主要负责（）A 选作业进入内存B 选一进程占有CPUC 建立一进程D 撤销一进程【解答】B【例】“可抢占”和“不可

2、抢占”的优先级调度算法相比（）A 前者开销小B 前者开销大C 两者开销大致相同D 两者开销不能相比【解答】B【解析】因为“可抢占”优先级调度时钟保证在处理机上运行的是优先级最高的进程，这样，当处理机正在运行某个进程时，很可能会被其他优先级更高的进程抢占引起处理机调度，和不可抢占算法相比，前者的调度次数会更频繁，而每调度一次都会引起保护现场，恢复现场的工作，所以可抢占的优先级调度算法开销更大。【例】（）优先权是在创建进程时确定的，确定之后在整个进程运行期间不再改变A 先来先服务B 静态C 动态D 短作业【答案】B【例】若进程P一旦被唤醒就能够投入运行，系统可能为()A 分时系统，进程P的优先级最

3、高B 抢占调度方式，就绪队列上的所有进程的优先级皆比P的低C 就绪队列为空队列D 抢占调度方式，P的优先级高于当前运行的进程【分析】1 在分析系统中，进程调度是按照轮转方式进行的。系统并不登记进程的优先级2 在抢占调度方式中，P的优先级高于就绪队列上的所有进程，但不一定高于当前的运行进程，所以也不一定能立即运行3 无论哪种调度方式，若就绪队列为空队列，P被唤醒并插入后都会成为该队列的唯一进程，但这并不是说P可以立即获得处理机。只有当前运行的进程释放了CPU，且就绪队列无其他进程时，P才可以立即使用CPU4 在抢占调用调度中，一个新的进程P到来，若P的优先级高于当前进程时，可以抢占CPU,立即投

4、入运行【答案】D【例】一个进程被P被唤醒后，（）A P就占有了CPUB P 的PCB被移到就绪队列的对首C P的优先级肯定最高D P的状态变为就绪【分析】1 进程P被唤醒后，由于当前运行的进程正在使用CPU，是否立即放弃CPU还要由其他因素决定，所以P不一定能立即占有CPU2进程P被唤醒后插入到队列的那个位置，要取决于管理程序和调度算法的实现方案。如果系统采用的是最高优先级算法，则可以按照优先级顺序将P插入到队列中；如果采用FIFO，则按到达就绪队列的时间顺序被插入队列尾部。此外，其他调度方案也有不同处理3 P被唤醒是因为它所等待的事件已经到来，并不是因为P的优先级最高4 进程P被唤醒后，说明

5、P已具备在CPU上运行的先决条件【答案D】【例】当系统中（）时，系统将不会执行进程调度原语。A 一个新进程被创建B 当前进程执行了P操作C 在非抢占调度中，进程A正在运行而进程B恰好被唤醒D 分时系统中的时间片用完【答案】C【例】下列进度调度算法中，（）可能出现进程得不到调度的情况A 静态优先权发B 抢占式调度中采用动态优先权算法C 分时处理中的时间片轮转调度算法D 非抢占式调度中采用FIFO算法【答案】A【例】在采用动态优先权的调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和（）相同A 先来先服务调度算法B 短作业优先调度算法C 时间片轮转调度算法D 长作业优先调

6、度算法【答案】A【例】下列进程调度算法中，（）可能会出现进程长期得不到调度的情况。A 非抢占式静态优先权法B 抢占式静态优先权法C 时间片轮转调度算法D 非抢占式动态优先权法【解答】B【例】为了照顾紧迫型作业，应采用（）A 先来先服务调度算法B 短作业优先调度算法C 时间片轮转调度算法D 优先权调度算法【解答】D【例】以优先级为基础的进程调度算法可以保证在任何时候正在运行的进程总是非等待状态下进程中优先级最高的进程，上述描述是_A 正确的B 错误的【答案】B【例】进程调度方式有两种，一种是_的，另一种是-_【答案】剥夺方式；非剥夺方式【例】进程调度算法采用时间片轮转法时，时间片过大，就会使轮转

7、法转化为（）法【解答】FCFS（先来先服务）【例】在操作系统中引起进程调度的因素有：现运行进程任务完成或出现异常情况；现运行进程在运行中又提出了新的资源申请，现运行进程由于之行某些原语，使进程由运行态变为阻塞态；在分时系统中，如果现运行进程给定的（）用完了；在采用可剥夺式的调度方式时，当有更高（）的进程进入就绪队列时，要引起重新调度。【解答】时间片优先级【例】若使当前运行进程总是优先级最高的进程，则应选择（）进程调度算法【解答】剥夺式优先级【例】进程调度负责（）的分配工作【解答】处理机【例】一种最常用的进程调度算法是把处理机分配给具有最高优先权的进程。而确定优先权的方法概括起来不外乎是基于_-

8、特性和_特性两种方法。前者所得到的是_优先权，后者所得到的是_优先权【答案】静态；动态；静态；动态【例】当进程调度未能选中一个进程运行时，就绪队列和阻塞队列一定为空。【解答】错当进程调度未能选中一个进程运行时，就绪队列为空，但阻塞队列不一定为空。因为调度时，阻塞状态的进程不受到影响。【例】在分时系统中，是否应设置作业调度？为什么？【解答】在分时系统中不需要设置作业调度。因为分时系统中的所有作业都由用户终端（键盘）输入到内存，然后系统立即为它建立进程，并将该进程插入到就绪队列。调度程序按时间片轮转法，对各终端作业进行调度，保证了在一较短时间内，各终端作业都能被处理，从而实现人机交互。反之，若将终

9、端作业先送到外存输入井上，再等待作业调度后，方可将作业调入内存（创建相应进程），这样就难以保证人际交互的要求，且也是多此一举。【例】某进程被唤醒时后立即投入运行，我们就说这个系统采用的是剥夺式调度方式，对么？【解答】不对当进程在唤醒前，CPU处于空闲状态时，某进程被唤醒后，系统会使它立即投入运行，但这不是剥夺调度方式。仅当它被唤醒后，立即抢占当前正在运行进程的CPU才可说系统采用的是剥夺式调度方式。【例】在采用优先级进程调度时，运行进程是否一定是系统中优先级最高的进程？【解答】不一定。因为高优先级的进程有可能正处于等待队列等待，进程调度就从就绪队列中选一个进程占用CPU，这个被选中的进程可能优

10、先级较低【例】在CPU按优先级调度的系统中1 没有运行进程是否一定没有就绪进程？为什么？2 没有运行进程或者没有就绪进程或者两者都没有，是否可能？都是什么情况？3 运行进程是否一定是进程中优先级最高的？【解答】1 是。因为当正在运行的进程由于某种原因放弃CPU，这时要调用调度程序，从就绪队列中挑选一进程投入运行。若就绪队列没有进程，则就无法挑选出进程。因此，无运行进程。2 可能。即在某一段时间内，可能系统中有几个进程都暂时处于阻塞状态，正在运行I/O或I/O等待，这时没有运行进程或者没有就绪进程或者两者都没有3 不一定。因为阻塞队列中的进程，其优先级可能比正在运行队列中的进程优先级高。【例】什

11、么叫抢占（剥夺）式处理调度和非抢占（非剥夺）式处理调度？先来先服务发（FCFS），优先法（HPF）各属于哪种调度方式【解答】剥夺方式是指当一进程正在处理机上运行时，当有更重要，更紧急或特殊要求的进程，即优先权更高的进程进入就绪队列时，就要终止现运行进程的运行，将CPU分配给更高优先权的进程。非剥夺方式是指当一进程正在处理机上运行时，若有优先权更高的进程要求使用时，现行进程不予理睬，继续运行，知道它运行完或出现某种情况时才给其他进程使用先来先服务（FCFS）属于非剥夺方式优先法（HPF）属于剥夺方式【例】假设一个系统中有5个进程，它们的到达时间和服务时间如下。忽略I/O以及其他开销，若分别按先来

12、先服务，非抢占及抢占的短进程优先，高响应比优先，时间片轮转调度算法进行CPU调度，请给出各进程的完成时间，周转时间，带权周转时间，平均周转时间和平均带权周转时间。6、考虑、考虑5个进程个进程P1,P2,P3,P4,P5，规定进程的优先数越小，优，规定进程的优先数越小，优先级越高，试描述在采用下述调度算法时各个进程运行过程，先级越高，试描述在采用下述调度算法时各个进程运行过程，并计算采用每种算法时进程平均周转时间。假设忽略进程的并计算采用每种算法时进程平均周转时间。假设忽略进程的调度时间。调度时间。1)先来先服务调度算法；先来先服务调度算法；2）时间片轮转调度算）时间片轮转调度算法（时间片法（时

13、间片1ms）；）；3）非剥夺式优先级调度算法；）非剥夺式优先级调度算法；4）剥夺）剥夺式优先级调度算法。式优先级调度算法。进程进程创建时刻创建时刻ms运行时间运行时间ms优先数优先数P1033P2265P3441P4652P5824解：解：进程进程创建时刻创建时刻ms运行时间运行时间ms优先数优先数P1033P2265P3441P4652P5824A 先来先服务调度算法先来先服务调度算法时间段时间段 0-3-9-13-18-20时间段对应进程顺序时间段对应进程顺序 p1 p2 p3 p4 p5 平均周转时间平均周转时间(3-0)+(9-2)+(13-4)+(18-6)+(20-8)/5=8.6

14、周转时间周转时间=作业的完成时间作业的完成时间-提交时间提交时间 带权周转时间带权周转时间=周转时间周转时间/系统服务时间系统服务时间最好用尺子画出带刻度的甘特图最好用尺子画出带刻度的甘特图解：解：进程进程创建时刻创建时刻ms运行时间运行时间ms优先数优先数P1033P2265P3441P4652P5824B 时间片轮转调度算法时间片轮转调度算法对应每对应每1ms（时间片）的执行顺序（时间片）的执行顺序p1 p1 p2 p1 p2 p3 p2 p4 p3 p2 p5 p4 p3 p2 p5 p4 p3 p2 p4 p4平均周转时间平均周转时间(4-0)+(18-2)+(17-4)+(20-6)

15、+(15-8)/5=10.80-1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19p2-p3p2-p4-p3p4-p3-p2p3-p2-p5-p4p3-p2解：解：进程进程创建时刻创建时刻ms运行时间运行时间ms优先数优先数P1033P2265P3441P4652P5824C 非剥夺式优先级调度算法非剥夺式优先级调度算法时间段时间段 0-3-9-13-18-20时间段对应进程顺序时间段对应进程顺序 p1 p2 p3 p4 p5 平均周转时间平均周转时间(3-0)+(9-2)+(13-4)+(18-6)+(20-8)/5=8.6优先数越小，优先级越高优

16、先数越小，优先级越高解：解：进程进程创建时刻创建时刻ms运行时间运行时间ms优先数优先数P1033P2265P3441P4652P5824D 剥夺式优先级调度算法剥夺式优先级调度算法时间段时间段 0-3-4-8-13-15-20时间段对应进程顺序时间段对应进程顺序 p1 p2p3 p4 p5 p2平均周转时间平均周转时间 (3-0)+(20-2)+(8-4)+(13-6)+(15-8)/5=7.8优先数越小，优先级越高优先数越小，优先级越高【解答】先来先服务选择最早进入就绪队列的进程投入运行ABCDE 到达时间 结束时间 周转时间 带权周转时间A 0 3 3-0=3 3/3=1B 2 3+6=

17、9 9-2=7 7/6C 4 9+4=13 13-4=9 9/4D 6 13+5=18 18-6=12 12/5E 8 18+2=20 20-8=12 12/2=6非抢占短进程优先选择最早进入就绪队列的进程投入运行ABECD 到达时间 结束时间 周转时间 带权周转时间A 0 3 3-0=3 3/3=1B 2 3+6=9 9-2=7 7/6C 4 11+4=15 15-4=11 11/4D 6 15+5=20 20-6=14 14/6E 8 9+2=11 11-8=3 3/2抢占短进程优先0时，A运行2时，B达到，但不运行3时，A运行结束，队列里面B,B开始运行4时，C到达，B运行1小时,选择C

18、运行，队列里面有B56时，D到达，队列里有B5,D58时，E到达，C运行完毕，队列里有B5,D5,E2,E开始运行10时，E运行完毕，队列里由B5,D5,B运行15时，B运行完毕，队列里有D5,D运行20时，D运行完毕 到达时间 结束时间 周转时间 带权周转时间A 0 3 3-0=3 3/3=1B 2 15 15-2=13 13/6C 4 8 8-4=4 4/4D 6 20 20-6=14 14/6E 8 10 10-8=2 2/2时间片轮转RR(时间片=1)0时,A执行1时,A执行2时,B到达,B执行,队列A13时,A运行,队列B54时,A运行完毕,C到达,B运行,队列C45时,C运行,队列

19、B46时,D到达,B运行,队列C3,D57时,C运行,队列D5,B38时,E2到达,D运行,队列B3,C2,E29时,B运行,队列C2,E2,D410时,C运行，队列E2,D4,B211时，E2运行，队列D4，B2，C112时，D4运行，队列B2，C1，E113时，B2运行，队列C1，E1，D314时，C1运行，队列E1，D3，B115时，C运行完毕，E运行，队列D3，B116时，E运行完毕，D3运行，队列B117时，B1运行，队列D218时，B运行完毕，D运行20时，D运行完毕【例】在OS中引入进程调度的主要因素有哪些？【解答】引入进程调度的主要因素有：1 一个进程运行完毕2 一个正在运行的进程被阻塞3 在抢占式调度中，一个高优先级的进程被创建4 在抢占调度中，一个高优先级进程由阻塞唤醒5 在轮转式调度中，正在运行的进程运行完一个时间片。