进程调度

进程调度（Process Scheduling）

　　进程调度是指操作系统按某种策略或规则选择进程占用CPU进行运行的过程。

　　无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。进程调度虽然是在系统内部的低级调度，但进程调度的优劣直接影响作业调度的性能。评价进程调度的优劣如反映作业调度优劣的周转时间和平均周转时间只在某种程度上反映了进程调度的性能，例如，其执行时间部分中实际上包含有进程等待(包括就绪状态时的等待)时间，而进程等待时间的多少是要依靠进程调度策略和等待事件何时发生等来决定的。因此，进程调度性能的商量是操作系统设计的一个重要指标。

　　进程调度性能的衡量方法可分为定形和定量两种。在定形衡量方面，首先是调度的可靠性。包括一次进程调度是否可能引起数据结构的破坏等。这要求我们对调度时机的选择和保存CPU现场十分谨慎。另外，简洁性也是衡量进程调度的一个重要指标，由于调度程序的执行涉及到多个进程和必须进行上下文切换，如果调度程序过于繁琐和复杂，将会耗去较大的系统开销。这在用户进程调用系统调用较多的情况下，将会造成响应时间大幅度增加。

　　进程调度的定量评价包括CPU的利用率评价、进程在就绪队列中的等待时间与执行时间之比等。实际上由于进程进入就绪队列的随机模型很难确定，而且进程上下文切换等也将影响进程的执行效率，LL而对进程调度进行解析是很困难的。一般情况下，大多利用模拟或测试系统响应时间的方法来评价进程调度的性能。

　　其基本属性有多态性 从诞生、运行，直至消灭；多个不同的进程可以包括相同的程序；三种基本状态 它们之间可进行转换；并发性并发执行的进程轮流占用处理器。

　　进程对将系统中各进程的执行情况和状态特征记录在各进程的PCB表中。并且，根据各进程的状态特征和资源需求等、进程管理模块还将各进程的PCB表排成相应的队列并进行动态队列转接。进程调度模块通过PCB变化来掌握系统中存在的所有进程的执行情况和状态特征，并在适当的时机从就绪队列中选择出一个进程占据处理机。

• 选择占有处理机的进程

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

• 进行进程上下文切换

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

　　进程上下文由正文段、数据段、硬件寄存器的内容以及有关数据结构等组成。硬件寄存器主要包括存放CPU将要执行的下条指令虚拟地址的程序计数器PC，指出机器与进程相关联的硬件状态的处理机状态寄存器PS，存放过程调用(或系统调用)时所传递参数的通用寄存器R以及堆栈指针寄存器S等。数据结构则包括PCB等在内的所有与执行该进程有关的管理和控制用表格、数组、链等。在发生进程调度时系统要做进程上下文切换。

• 先进先出算法

　　算法总是把处理机分配给最先进入就绪队列的进程，一个进程一旦分得处理机，便一直执行下去，直到该进程完成或阻塞时，才释放处理机。 例如，有三个进程P1、P2和P3先后进入就绪队列，它们的执行期分别是21、6和3个单位时间，对于P1、P2、P3的周转时间为21、27、30，平均周转时间为26。可见，FIFO算法服务质量不佳，容易引起作业用户不满，常作为一种辅助调度算法。

• 短进程优先

　　最短CPU运行期优先调度算法(SCBF--Shortest CPU Burst First)，该算法从就绪队列中选出下一个“CPU执行期最短”的进程，为之分配处理机。例如，在就绪队列中有四个进程P1、P2、P3和P4，它们的下一个执行期分别是16、12、4和3个单位时间，执行情况如下：P1、P2、P3和P4的周转时间分别为35、19、7、3，平均周转时间为16。该算法虽可获得较好的调度性能，但难以准确地知道下一个CPU执行期，而只能根据每一个进程的执行历史来预测。

• 轮转法

　　前几种算法主要用于批处理系统中，不能作为分时系统中的主调度算法，在分时系统中，都采用时间片轮转法。

　　简单轮转法：系统将所有就绪进程按FIFO规则排队，按一定的时间间隔把处理机分配给队列中的进程。这样，就绪队列中所有进程均可获得一个时间片的处理机而运行。

• 多级队列方法：将系统中所有进程分成若干类，每类为一级。
• 多级反馈队列：多级反馈队列方式是在系统中设置多个就绪队列，并赋予各队列以不同的优先权。

　　进程调度发生的时机与引起进程调度的原因以及进程调度的方式有关。

1. 正在执行的进程执行完毕。这时，如果不选择新的就绪进程执行，将浪费处理机资源。
2. 执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等状态。
3. 执行中进程调用了P原语操作，从而因资源不足而被阻塞；或调用了v原语操作激活了等待资源的进程队列。
4. 执行中进程提出I/O请求后被阻塞。
5. 在分时系统中时间片已经用完。
6. 在执行完系统调用等系统程序后返回用户进程时，这时可看作系统进程执行完毕，从而可调度选择一新的用户进程执行。
7. 就绪队列中的某进程的优先级变得高于当前执行进程的优先级，从而也将引发进程调度。

　　以上都是在可剥夺方式下的引起进程调度的原因。在CPU执行方式是可剥夺时，还有进程调度的调度方法包括非剥夺式的调度和可剥夺式的调度，在可剥夺式调度中有时间片轮转方法、优先级调度方法、彩票调度、多级队列调度方法。如两种占用CPU的方式：

1. 非剥夺方式，分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生。不可剥夺式即不可抢占式non_preemptive，即使在就绪队列存在有优先级高于当前执行进程时，当前进程仍将占用处理机直到该进程自己因调用原语操作或等待I/O而进入阻塞、睡眠状态，或时间片用完时才重新发生调度让出处理机。
2. 剥夺方式，当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。剥夺原则有：优先权原则、短进程优先原则、时间片原则。可剥夺式即可抢占式preemptive，就绪队列中一旦有优先级高于当前执行进程优先级的进程存在时，便立即发生进程调度，转让处理机。

　　（1）作业调度是从作业后备队列选择一个或多个作业，为其分配必要的资源，并为之创建进程，做好运行前的准备。按照一定的作业调度算法，从后备作业队列中选择一个或几个作业调入内存。

　　（2）进程调度是指从已经进入内存的进程的就绪队列中选择一个进程真正占有CPU，并为其运行进行上下文转换，让其立即运行。按照一定的进程调度算法，从内存的进程中选择一个进程，将处理机分配给它，使其执行。

　　（3）作业调度是主要解决进程真正在CPU上运行的问题。进程调度是主要解决作业有无资格占有CPU的问题。

• 地址寄存器
• 码头调度