处理机调度.doc

1. 在批处理系统中，一个作业从提交给系统到运行结束退出系统，通常有哪些作业状态？你能说出这些状态转换的原因吗？由哪些程序负责这些状态之间的转换？ 2. 简述作业调度程序、中级调度程序和进程调度程序的功能，并指出这些调度程序通常配置于什么操作系统中？ 3. 下列问题应由哪一级调度程序负责？(1) 发生时间片中断后，决定将处理机分给哪一个就绪进程？(2) 在短期繁重负荷情况下，应将哪个进程挂起？(3) 一个作业运行结束后，从后备作业队列中选具备能够装入内存的作业？4. 在分时系统内部有必要设立作业调度程序吗？为什么？ 5. 有三道程序其构成如下所示，它们在一个系统中运行，该系统有输入设备、输出设备各一台。A进程：输入32秒，计算8秒，输出5秒。B进程：输入21秒，计算14秒，输出35秒。C进程：输入12秒，计算32秒，输出15秒。试问：(1) 三道程序顺序执行时需要最短时间多少？(2) 为了充分发挥各设备效能，三道程序并发执行，最短需要多少时间？（不计系统开销时间）6. 进程调度方式有哪两种？各适用于什么场合？ 7 试述抢占调度方式中的三种抢占原则。8. 调度队列模型主要有哪三种？各适用于什么场合？ 9. 什么是作业周转时间？请写出作业平均周转时间和作业带权周转时间的计算公式，并指出公式中参数的含义。10. 什么是响应时间？分别写出分时系统和实时系统对响应时间的要求。11. 举例说明，为什么FCFS算法对交互式用户而言，并不是一种恰当的进程调度模式。12. 什么是短作业（短进程）优先调度？为什么SJF(SPF) 调度算法对长作业（长进程）不利？ 13. 作业调度算法选择作业的原则，可以是保证系统吞吐量大，可以是对用户公平合理，可以是充分发挥系统资源的利用率。请分别指出先来先服务、最短作业优先体现了哪种选择作业的原则。14. 优先级调度算法有什么优点？它适用于什么系统？ 15. 假定在一个多道批处理系统中，道数不受限制。当第1个作业进入输入井后或内存中有一道程序完成后立即进行作业调度。现在有四道都是仅作计算而没有请求设备输入输出的作业，它们进入输入井的时间、需要计算的时间及优先级如下所示：作业名进入输入井时间需要计算时间（分钟）优先级（数大级高）A8：00601B8：10402C8：20304D8：30103(1) 作业调度和进程调度均采用FCFS算法时，计算这批作业的T和W。(2) 作业调度采用SJF和进程调度采用SPF算法时，计算这批作业的T和 W。(3) 作业调度和进程调度均采用优先级高者优先算法时，计算这批作业的T和W。约定，作业优先级与进程优先级相一致。16. 试比较下列作业调度算法，对短作业的优待程度，对长作业的虐待程度，哪些算法有可能发生长作业挨饿（总得不到调度）现象？(1) 先来先服务FCFS(2) 短作业优先SJF17. 什么是时间片轮转调度算法？它适用于什么场合？ 18. 假设某系统的调度如下图所示，其中时间片q=50ms，假定系统中只有A、B两个合作进程，它们的同步信号量S的初值为0。进程A的循环体是：执行计算20ms后，调用P(S)操作，然后计算30ms后返回起点循环。进程B的循环体是：开始执行计算30ms后，调用V（S）操作，再计算20ms后返回起点循环。假定t=0时刻，A，B都在就绪队列中，A在B之前，且忽略进程切换和PV操作本身所花的时间。试按下列表格写出A、B两进程，从t=0时刻开始，到t=170ms为止的状态变化。时刻执行态进程就序态进程阻塞态进程发生何种事件T=019. 指出下述各说法，为什么是不正确的？(1) 短作业优先是公平的。(2) 越短的作业应该享受越好的服务。(3) 由于最短作业优先调度是优先选择短作业，故可用于分时系统。20. 为什么说多级反馈队列能较好地满足各种用户的需要？ 1. 参考答案作业通常有四种状态。提交状态，是程序员把存储有作业实体信息的介质交给机房或用户通过终端键盘向计算机键入其作业实体信息时所处状态。后备状态，是作业实体信息已被输入到硬盘的输入井中，建立了相应的JCB等，等待作业调度时所处状态。运行状态，是作业已被调度到装入内存，创建了相应的进程、投入运行时的状态。完成状态，是作业运行结束或因错误而终止时，释放所占全部资源，准备离开系统时的状态。提交状态后备状态，是系统操作员启动作业注册过程的结果。这过程中涉及脱机输入程序或联机spooling系统的输入进程，将作业实体信息转储到硬盘的输入井中。另外，主要涉及到作业注册程序，创建作业控制块JCB。后备状态运行状态，是由作业调度程序调度选中，装入内存创建相应进程及有关表格投入运行。这过程中涉及作业调度程序，装入作业到内存时涉及内存管理程序和设备管理程序中的某些功能程序。运行状态完成状态，是由进程调度、进程控制原语、及OS中各种资源管理程序的帮助下，使作业的进程正常运行结束，或出错无法运行下去时，由作业终止程序处理，做作业结束的善后处理工作。2. 参考答案：作业调度程序的功能是按照某种调度算法从后备作业队列中选择作业，为它们分配内存和其他资源，创建相应就绪进程，挂入就绪进程队列。作业调度程序配置于具有批处理作业功能的OS中。进程调度程序是按照某种调度算法从就绪状态的进程中选择一个进程，将CPU分配给它，让其执行。进程调度程序在任何一种操作系统中均有配置，它是一种处理机调度程序。中级调度程序的功能是根据系统负荷太重，将有些暂不具备运行的进程挂起，并将它们从内存调至外存上等待；当这些进程又具备执行条件，且内存有空闲时，将它们激活从外存重新装入内存，等待进程调度。中级调度通常配置于具有挂起、激活功能原语的OS中。3. 参考答案： (1) 应由进程调度程序负责。(2) 应由中级调度程序负责。(3) 应由作业调度程序负责。4. 参考答案：在分时系统中不必设立作业调度程序，因为分时的作业是用户从终端设备上输入的命令和数据都直接进入主存，而不是进入磁盘输入并等待。5. 参考答案：(1) 三道程序顺序执行时没有并行操作，所以总需要的最短执行时间是各道程序执行时间之和为174秒，即T=32+8+5+21+14+35+12+32+15=174（秒）。(2) 三道程序并发执行，可使输入、输出和计算尽量并行操作，缩短了三道作业的总周转时间，调度最理想时只需90秒。其并行操作如下所示：从示意图可知进程A,B,C需要的最短时间T=21+14+35+15+5=90（秒）。6. 参照答案：进程调度方式主要有抢占方式和非抢占方式两种。非抢占方式适用于大多数的批处理系统，而抢占方式适用于分时系统和大多数实时系统。7. 参考答案：时间片原则：当前进程用完一个时间片时，系统立刻停止当前进程的执行，而将cpu分给下一个就绪进程。优先级原则：当新到达作业的进程的运行时间小于当前进程的运行时间时，立即将cpu分配给新进程。8. 参考答案：调度队列模型主要有三种：第1种是只具有进程调度的调度队列模型1，主要适用于分时操作系统中；第2种是具有作业调度和进程调度的调度队列模型2，主要适用具有批处理作业功能的批处理OS中；第3种是具有作业调度、进程调度和中级调度的调度队列模型3，它主要适用于同时具有批处理作业功能和分时功能，并且具有挂起功能的OS中。9. 参考答案：周转时间有作业周转时间和进程周转时间之分。作业周转时间是从用户提交的作业实体信息全部进入输入井时刻开始，到作业完成时刻这段时间间隔。它包括作业在后备队列中等待时间、进程在就绪队列、阻塞队列等待时间和在CPU上执行的时间之和。进程周转时间是相应作业周转时间中去掉作业在后备队列中的等待时间。作业平均周转时间公式为： 其中，n为作业数，Tci是第i个作业完成时刻，Tsi是第i个作业提交作业完成时刻，i是1，2n中之一。10. 参考答案：响应时间是用户从提交一个请求开始，直到系统在屏幕上显示出结果或提示信息这一段时间。分时系统的响应时间通常是，而实时系统对响应时间的要求差别很大，一般为秒级、毫秒级甚至要求时间更小。11. 参考答案：交互式的用户通常是在分时系统和实时信息处理系统中。用户通过联机的终端设备发命令，系统以分时的形式及时为他们服务，通常响应时间为35秒。但FCFS调度算法，为先来的进程分配处理机后让它一直运行，直到运行完毕或因等待某事件发生不能继续运行时，才调度另一交互式进程运行。如某交互型用户从键盘上发命令运行他的一分钟算题程序后，由于它前面的十个其他用户程序约需运行1个小时，他要等1个小时才能得到响应处理，这是不能容忍的。所以FCFS算法对交互式用户而言是不恰当的进程调度模式。12. 参考答案：所谓短作业优先调度是指作业运行时间、进程运行的时间最短的先调度。因此往往主存在长作业、长进程被推迟调度的情况，所以这种调度算法对长作业、长进程不利。13. 参考答案：吞吐量大的是最短作业优先算法，因为SJF使作业的平均周转时间有明显的改善，从而使系统在单位时间内处理的作业数增多。 公平合理的是先来先服务算法。因为对用户而言按照作业进入输入井时间的先后调度，先来的先服务，后来的自然后服务，对每个用户都是公平的。14. 参考答案：优先级调度算法的主要优点是能使最紧迫的作业、进程尽快调度到执行。可适应于批处理系统、分时系统、实时系统。一定要拥有优先级调度算法。15. 参考答案：(1) FCFS算法调度的次序是A，B，C，D。作业名输入时间运行时间（分）开始执行时间结束执行时间周转时间（分）带权周转时间A8：00608：009：006060/60B8：10409：009：409090/40C8：20309：4010：10110110/30D8：301010：1010：20110110/10作业平均周转时间T=(60+90=110=110)/4=92.5（分）作业平均带权周转时间W=(1+9/4+11/3+11)/4=4.25（2）短作业（短进程）优先算法调度的次序是A，D，C，B。作业名输入时间运行时间（分）开始执行时间结束执行时间周转时间（分）带权周转时间A8：00608：009：006060/60D8：30109：009：104040/10C8：20309：109：408080/30B8：10409：4010：20130130/40T=(60+40+80+130)/4=77.5（分）W=(1+4+8/3+13/4)/42.73（3）优先级高者优先算法调度的次序是A，C，D，B。作业名输入时间运行时间（分）开始执行时间结束执行时间周转时间（分）带权周转时间A8：00608：009：006060/60C8：20309：009：307070/30D8：30109：309：407070/10B8：10409：4010：20130130/40T=(60+70+70+130)/4=82.5（分）W=(1+7/3+7+13/4)/4=167/483.4816 参考答案：(1) FCFS算法不考虑作业运行时间的长短，仅按作业进入输入井时间的先后进行调度，因此对所有的作业是公平合理的。(2) 短作业优先SJF算法对短作业非常有利，而对长作业非常不利。因为，即使很迟进入输入井的短作业能先被调度，而很早进入输入井的长作业，可能因为进入一大批短作业后得不到调度而挨饿。17 参考答案：时间片轮转算法主要用于进程调度，此调度算法将进程就绪队列按进程进入队列的先后排列，调度时只要将分给队列首进程一个时间片，当用完时间片后当前进程从队列首移到队列尾，并将分配队列新队列首进程。18. 参考答案：时刻执行态进程就绪态进程阻塞态进程发生的事件T=0AA，BA被调度选中T=20BAA执行P（S）后， S= -1而阻塞T=50BAB执行V（S），S=0 唤醒AT=70ABB时间片到时，B为就绪 T=120BAA时间片到时，A执行P（S），S= -1转为 阻塞T=150BAB执行V（S），S=0，唤醒AT=170ABB时间片到时19. 参考答案：(1) 短作业优先算法是优先照顾运行时间短的作业，虽然它有利减少作业平均周转时间和作业平均带权周转时间，但对长作业用户而言感到很不公平。长作业常常因连续不断进入输入井的短作业而长时间得不到调度。(2) 越短的作业不一定应该享受越好的服务，要看该短作