操作系统 习题及答案 第四章 进程线程调度

第四章进程线程调度习题1．试述进程调度的主要任务。为什么说它把一台物理机变成多台逻辑上的处理机？进程调度的主要任务是使CPU运行能够在多个进程之间高效切换，以实现并发执行和有效使用处理器。进程调度把一台物理机变成多台逻辑上的处理机，因为调度程序能使计算机同时处理多个进程，让每个进程都认为自己独占了处理器。2．抢占式进程调度是指系统能够强制性地使执行进程放弃处理机。试问分时系统采用的是抢占式还是非抢占式进程调度？实时系统呢？分时系统采用的是抢占式进程调度。因为在分时系统中，所有用户共享计算机，系统要保证各个用户能公平地使用到计算资源，因此需要事先设定一个时间片，时间片结束后强行抢占资源。实时系统如硬实时系统或软实时系统，一般也采用抢占式调度，以保证高优先级的任务能及时响应。3．在CPU按优先级调度的系统中：（1）没有运行进程是否一定就没有就绪进程？没有运行进程并不意味着就没有就绪进程，因为有可能所有就绪进程正处于等待状态。（死锁不存在就绪进程处于等待状态，等待状态就不是就绪状态）不存在就绪进程处于等待状态，等待状态就不是就绪状态（2）没有运行进程，没有就绪进程或两者都没有是否可能？各是什么情况？没有运行进程：等待外设或其他资源的响应；没有就绪进程：恰好满负载，均在运行；都没有：参见（1）（3）运行进程是否一定是自由进程中优先数最高的？不一定，在动态优先级调度中可能存在调度后其他进程优先级提升的情况。4．对某系统进行监测后表明平均每个进程在I/O阻塞之前的运行时间为T。一次进程切换需要的时间为S，这里S实际上就是开销。对于采用时间片长度为Q的时间片轮转法，请给出以下各种情况的CPU利用率的计算公式。（1）Q=∞100%T/（T+S）（2）Q>T100%T/（T+S）（3）S<Q<TQ/(Q+S)（4）Q=S50%（5）Q趋近于00%5．大多数时间片轮转调度程序使用一个固定大小的时间片，请给出选择小时间片的理由。然后，再给出选择大时间片的理由。选择小的时间片可以减少响应时间并提高交互性；而选择大的时间片可以减少调度开销。6．有5个批处理作业A到E几乎同时到达一计算中心。它们的估计运行时间分别为10，6，2，4和8分钟。其优先数(由外部设定)分别为3，5，2，1和4，其中5级为最高优先级。对于下列每种调度算法，计算其平均进程周转时间，可忽略进程切换的开销。（1）时间片轮转法假设q=2：进程到达时间运行时间开始时间完成时间周转时间A0100101824283030B06212202222C02466D046141616E0881622262828avg=20.4102/5（2）优先级调度进程到达时间运行时间开始时间完成时间周转时间A010142424B06066C02242626D04263030E0861414avg=20100/5（3）先来先服务（按照次序10，6，2，4，8运行）进程到达时间运行时间开始时间完成时间周转时间A01001010B06101616C02161818D04182222E08223030avg=19.296/5（4）最短作业优先进程到达时间运行时间开始时间完成时间周转时间A010203030B0661212C02022D04266E08122020avg=1470/5对（1），假设系统具有多道处理能力，每个作业均获得公平的CPU时间，对（2）到（4）假设任一时刻只有一个作业运行，直到结束。所有的作业都是CPU密集型作业。7．有5个待运行作业，它们的估计运行时间分别是9，6，3，5和X。采用哪种次序运行各作业将得到最短的平均响应如果是响应时间的话，假设作业一旦得到调度就有响应，那么，适用时间片轮转，且时间片越小越好。本题的解法是适用平均周转时间。时间？（答案依赖于X）如果是响应时间的话，假设作业一旦得到调度就有响应，那么，适用时间片轮转，且时间片越小越好。本题的解法是适用平均周转时间。采用SJF（短作业优先）的方式：如果X>9，则运行顺序为3→5→6→9→X。如果6<X<=9，运行顺序为3→5→6→X→9。如果5<X<=6，运行顺序为3→5→X→6→9。如果3<X<=5，运行顺序为3→X→5→6→9。如果X<=3，运行顺序为X→3→5→6→9。8．列出并简单定义线程调度的四种技术。负载分配：系统维护一个就绪进程的全局队列，每个处理器只要空闲就从队列中选择一个线程。组调度：一组相关的线程基于一对一的原则，同时调度到一组处理器上运行。专用处理器分配：通过把线程指定到处理器来定义隐式的调度。在程序执行过程中，每个程序被分配给一组处理器，处理器的数目与程序中线程的数目相等。当程序终止时，处理器返回到总的处理器池中，可供分配给另一个程序。动态调度：在执行期间，进程中线程的数目可以改变。9．列出并简单定义四类实时调度算法。静态表驱动调度算法：执行关于可行调度的静态分析。分析的结果是一个调度，它用于确定在运行时一个任务何时必须开始执行。静态优先级驱动抢占调度算法：同样，执行一个静态分析，但是没有指定调度，而且用于给任务指定优先级，使得可以使用传统的优先级驱动的抢占式调度器。基于动态规划调度调度算法：在运行时动态地确定可行性，而不是在开始运行前离线地确定。一个到达的任务，只有当能够满足它的时间约束时，才可以被接受执行。可行性分析的结果是一个调度或规划，可用于确定何时分派这个任务。动态尽力调度调度算法：不执行可行性分析。系统试图满足所有