第四章 处理机调度【操作系统】

1.什么是分级调度

多道程序设计的关键是调度，处理机调度的目标是以满足系统目标的方式，把进程分配到一个或多个处理机中执行。根本上，调度属于队列管理方面的问题

一般处理机调度分为三级：

处理机调度分为三级：

作业调度：又称宏观调度或高级调度、长程调度:按一定的原则对外存上的大量后备作业进行选择，给选出的作业分配内存等必要的资源，并建立相应的进程。另外当作业执行完毕时，还负责回收系统资源

交换调度(中级调度):按给定的原则和策略，将处于外存交换区中的就绪状态的进程调入内存，或把处于内存阻塞状态的进程交换到外存交换区。主要涉及到内存管理与扩充，也归入内存管理部分

进程调度（微观调度或低级调度、短程调度）：按某种策略和方法选取一个处于就绪状态的进程占用处理机。

线程调度：对于支持多线程的系统，按某种策略和方法选取一个处于就绪状态的线程占用处理机

2.试述作业调度的主要功能

(1)记录系统中各个作业的情况;(2)按照某种调度算法从后备作业队列中挑选作业;(3)为选中的作业分配内存和外设等资源;(4)为选中的作业建立相应的进程;(5)作业结束后进行善后处理工作。

3.试述进程调度的主要功能

（1）记录系统中所有进程的执行情况

进程调度

进程调度的具体功能可总结为如下几点：作为进程调度的准备，进程管理模块必须将系统中各进程的执行情况和状态特征记录在各进程的PCB表中。并且，根据各进程的状态特征和资源需求等、进程管理模块还将各进程的PCB表排成相应的队列并进行动态队列转接。进程调度模块通过PCB变化来掌握系统中存在的所有进程的执行情况和状态特征，并在适当的时机从就绪队列中选择出一个进程占据处理机。

（2）选择占有处理机的进程

进程调度的主要功能是按照一定的策略选择—个处于就绪状态的进程，使其获得处理机执行。根据不同的系统设计目的，有各种各样的选择策略，例如系统开销较少的静态优先数调度法，适合于分时系统的轮转法(Round RoLin)和多级互馈轮转法(Round Robin with Multip1e feedback)等。这些选择策略决定了调度算法的性能。

（3）进行进程上下文切换

—个进程的上下文(context)包括进程的状态、有关变量和数据结构的值、机器寄存器的值和PCB以及有关程序、数据等。一个进程的执行是在进程的上下文中执行。当正在执行的进程由于某种原因要让出处理机时，系统要做进程上下文切换，以使另一个进程得以执行。当进行上下文切换时点统要首先检查是否允许做上下文切换(在有些情况下，上下文切换是不允许的，例如系统正在执行某个不允许中断的原语时)。然后，系统要保留有关被切换进程的足够信息，以便以后切换回该进程时，顺利恢复该进程的执行。在系统保留了CPU现场之后，调度程序选择一个新的处于就绪状态的进程、并装配该进程的上下文，使CPU的控制权掌握在被选中进程手中。

4.进程调度的时机有哪些

（1）正在执行的进程执行完毕

（2）执行中进程自己调用阻塞原语将自己阻塞起来进入等待状态

（3）执行中进程调用了P原语操作，因为资源不足而被阻塞；或用V原语激活了等待资源的进程队列

（4）执行中进程提出了I/O请求后被阻塞

（5）正在执行的进程的CPU时间片已经用完

（6）在执行完系统调用，返回用户进程时，可以认为系统进程执行完毕，从而可调度选择一个新的用户进程执行

以上是对于CPU执行方式不可剥夺，对于CPU执行方式可剥夺（抢占）还有：

（7）就绪队列中的某进程的优先级高于当前执行进程的优先级

5.假设一个系统中有5个进程，它们处于就绪状态的时刻和估计运行时间如下表所示忽略I/O以及其它开销时间若分别按先来先服务，最短进程优先，最短剩余时间优先.响应比优先、时间片轮转(时间片=1)、非抢占多级反馈队列(第i级队列的时间片=2的i次方-1)以及抢占的多级反馈队列调度算法进行CPU调度请给出各进程的调度顺序、完成时间、周转时间

参考答案：

6.在单CPU和两台I/O设备(1，12) 的多6道程序设计环境下，同时投入3个作Job1Job2、Job3运行。这3个作业对CPU和I/O设备的使用顺序和时间如下所示:? Job1:12(30ms);CPU(10ms);11(30ms);CPU(10ms);12(20ms)Job2:11(20ms);CPU(20ms);12(40ms)Job3:CPU(30ms);11(20ms);CPU(10ms);1(10ms)假定CPU、11、12都能并行工作，Job1优先级最高，Job2次之，Job3最低，优先级高的作业可以抢占优先级低的作业的CPU但不可抢占11，12。求:

(1)3个作业从投入到完成分别需要的时间

(2)从投入到完成的CPU利用率

(3)I/0设备利用率

参考答案：

7。某进程调度程序采用基于优先数(priority)的调度策略，即选择优先数最小的进程运行，进程创建时由用户指定一个nice作为静态优先数。为了动态调整优先数，引入运行时间cpuTime和等待时间waitTime初值均为0。进程处于执行态时，cpuTime定时加1,且waitTime置0;进程处于就绪态时cpuTime置0waitTime定时加1。请回答下列问题1)若调度程序只将nice的值作为进程的优先数，即priority = nice,则可能会出现饥饿现象。为什么?2)使用nice,cpuTime和waitTime设计一种动态优先数计算方法，以避免产生饥饿现象并说明waitTime的作用

参考答案：

1）由于采用了静态优先数，当就绪队列中总有优先数较小的进程时，优先数较大的进程一直没有机会运行，因而会出现饥饿现象。

2）优先数 priority 的计算公式为 priority=nice+k1×cpuTime-k2×waiTime，其中k1>0，k2>0，用于分别调整cpuTime 和 waitTime 在 priority 中所占的比例。waitTime 可使长时间等待的进程优先数减少，从而避免出现饥饿现象。