【Java并发编程】操作系统基础（四）：进程调度时机、模式、算法

雨点打透心脏的1/2处 2022-12-07 01:50 177阅读 0赞

## 1.调度时机 ##

*  在创建一个新进程之后，需要决定是运行父进程还是运行子进程。由于这两种进程都处于就绪状态，所以这是一种正常的调度决策，可以任意决定。
 *  在一个进程退出时必须做出调度决策。一个进程不再运行，所以必须从就绪进程集中选择另外某个进程。如果没有就绪的进程，通常会运行一个系统提供的空闲进程。
 *  当一个进程在阻塞I/O和信号量上或由于其他原因阻塞时，必须选择另一个进程运行。
 *  在一个I/O中断发生时，必须做出调度决策。如果中断来自I/O设备，而该设备现在完成了工作，某些阻塞的等待该I/O进程就成为可运行的就绪进程了。是否让新就绪的进程运行，这取决于调度程序的决定 ，或者让中断发生时运行的进程继续运行，或者应该让某个其他进程运行。

注：区分一个多任务分时系统是抢占式的还是非抢占式的，则要看进程能否在发生中断时产生调度（抢占）。

## 2.调度模型 ##

### 2.1 抢占式 ###

抢占式调度指的是每条**线程执行的时间、线程的切换都由系统控制**，即当到达调度时机时，调度机会决定是让当前进程继续运行，或者将CPU抢占给别的进程。在这种机制下，一个线程的堵塞不会导致整个进程堵塞。

> PS：会引起的进程调度的时机主要是，一个进程运行完毕/(时间片结束)/被阻塞/被唤醒，或者一个新进程被创建。

举个例子，比如调度机采用的是抢占式短作业优先算法，此刻作业A（PS：A剩余执行时间为10s）正在执行，现在有另一个作业B（PS：B的执行时间为3s）来了，那么调度机就会将作业A中断并挂起，然后让作业B执行，待B执行完了再执行A的剩余10s。相当于作业B抢占了作业A的CPU。

我们最常用的是就是基于抢占式调度的时间片轮转算法。如果在一个时间片结束时，该进程仍在运行，它就被挂起，而调度程序挑选另一个进程运行（如果存在一个就绪进程）。

### 2.2 非抢占式 ###

非抢占式调度算法挑选一个进程，然后让该进程运行直至阻塞（阻塞在I/O上或等待另一个进程），或者直到该进程自动释放CPU。即使该进程运行了若干个小时，它也不会被强迫挂起。这样做的结果是，在时钟中断发生时不会进行调度。在处理完时钟中断后，如果没有更高优先级的进程等待到来，则被中断的进程会继续执行。

**线程的执行时间由线程本身控制，线程切换可以预知，不存在多线程同步问题**，但它有一个致命弱点：如果一个线程编写有问题，运行到一半就一直堵塞，那么可能导致整个系统崩溃。

> 注：Windows3.x是使用的非抢占式，Windows95以后及UNIX,Linux最新内核都是使用的抢占式。

## 3.调度策略 ##

### 3.1 先来先服务（FCFS、非抢占式） ###

*  使用该算法，进程按照它们请求CPU的顺序使用CPU。
    
     *  基本上，有一个就绪进程的单一队列。当第一个作业从外部进入系统，就立即开始并允许运行它所期望的时间。不会中断该作业，因为它需要很长的时间运行。
     *  当其也作业进入时，它们就被安排到队列的尾部。当正在运行的进程被阻塞时，队列中的第一个进程就接着运行。
     *  在被阻塞的进程变为就绪时，就像一个新来到的作业一样，排到队列未尾。
 *  优点
    
     *  易于理解并且便于在程序中运用。
     *  在这个算法中，一个单链表记录了所有就绪进程。要选取一个进程运行，只要从该队列的头部移走一个进程即可;要添加一个新的作业或阻塞一个进程，只要把该作业或进程附加在相应队列的末尾即可
 *  缺点
    
     *  CPU和I/O设备得不到充分利用。
     *  假如，有一个一次运行1秒钟的CPU密集型进程和每个都要进行1000次磁盘读操作的I/O密集型进程存在。CPU密集型进程运行1秒钟，接着I/O密集型进程开始读一个磁盘块，此时它将会被阻塞，加入到队列未尾。CPU密集型进程接着运行，依次循环，这样I/O密集型进程就要要等1000秒钟才能完成操作。如果有一个调度算法每10ms抢占计算密集型进程，那么I/O进程将在10秒钟内完成而不是1000秒钟，而且还不会对计算密集型进程产生多少延迟。

### 3.2 最短作业优先（SJF、非抢占式） ###

*  进程开始获取CPU**一直运行直到完成或者由于某事件被阻塞放弃CPU，运行结束后从当前就绪队列选择“最短”的进程运行**。该调度算法适用于运行时间可以预知的任务。
 *  优点：可以有效减少周转时间  
    假如有A、B、C、D四个进程，分别要执行A（8），B（4），C（4)，D(4）分钟，按照原有次序运行作业：  
    ![img][]  
    则A的周转时间为8分钟，B为12分钟，C为16分钟，D为20分钟，平均（8+12+16+20）/4=14分钟。如果按照最短作业优先次序运行：  
    ![img][img 1]  
    则B的周转时间为4分钟，C为8分钟，D为12分钟，A为20分钟，平均（4+8+12+20）/4=11分钟
 *  缺点：利用短进程，长进程可能由于得不到CPU，而“饿死”。

有必要指出，只有在所有作业都可同时运行的情形下，最短作业优先算法才是最优化的。作为一个反例，考虑5个作业，从A到E，运行时间分别是2、4、1、1和1。它们的到达时间是0、0、3、3和3。 开始只能选择A或B，因为其他三个作业还没有到达。使用最短作业优先，将按照A、B、C、D、E的顺序运行作业，其平均等待时间是4.6。但是，按照B、C、D、E、A的顺序运行作业，其平均等待时间则是4.4。

### 3.3 最高响应比优先（HRP、非抢占式） ###

*  进程开始获取CPU一直运行直到完成或由于某事件被阻塞放弃CPU，运行结束从当前就绪队列**选择最高响应比的进程**投入运行。
    
     *  响应比 =（等待时间+运行时间）/运行时间 = 1 + 等待时间 / 运行时间（PS：等待时间是指，进程到达时可能需要等待前一进程先执行完）
     *  在响应时间固定的情况下，利于短进程。长进程随着等待时间变长，响应比会提高，因此长进程也能在足够长的时间被调度。
 *  优缺点：利用于短进程、长进程不会被饿死。

### 3.4 最短剩余时间（SRT、抢占式） ###

*  使用这个算法，调度程序总是**选择剩余运行时间最短**的那个进程运行。
    
     *  有关的运行时间必须提前掌握。当一个新的作业到达时，其整个时间同当前进程剩余时间做比较。
     *  如果新的进程比当前运行进程需要更少的时间，当前进程就被挂起，而运行新的进程。
 *  优缺点：利于短进程，开销大，不利于长进程。

### 3.5 时间片轮转调度（RR、抢占式） ###

*  每个进程被分配一个时间段，称为**时间片**，即允许该进程在该时间段中运行。
    
     *  如果在时间片结束时该进程还在运行，则将剥夺CPU并分配给另一个进程。
     *  如果该进程在时间片结束前阻塞或结束，则CPU立即进行切换。
     *  时间片轮转调度很容易实现，调度程序所要做的就是维护一张可运行进程列表，如下图  
        ![img][img 2]  
        当一个进程用完它的时间片后，就被移到队列的末尾，如下图。  
        ![img][img 3]

在时间片轮转算法下，可能每个进程都分同样的执行时间片，也可能是某些线程执行的时间片较长，甚至某些线程得不到执行的时间片

*  时间片小：假如进程切换需要5毫秒，最大值为20毫秒，那么在做完20毫秒有用的工作之后，CPU将花费5毫秒来进行进程切换，在100毫秒内CPU时间就有20%被浪费在了进程切换上。
 *  时间片大：为了提高CPU效率，我们将最大值设为500毫秒，这时浪费的时间只有1%。但考虑在一个分时系统中，如果有十个交互用户几乎同时按下回车键，将发生什么情况？假设所有其他进程都用足它们的时间，最后一个不幸的进程不得不等待5秒钟才获取运行机会，这通常是用户无法忍受的。

> 所以这里得出一个结论：**时间设得太短会导致过多的进程切换，降低CPU效率;而设得太长又可能引起对短的交互请求的响应变差。将时间片设为20ms-50ms通常是一个比较合理的折中**。

**此算法是最古老、最简单、最公平且使用最广的算法**

### 3.6 优先级调度（Java） ###

*  **轮转调度做了一个隐含的假设，即所有的进程同等重要**，而拥有和操作多用户计算机系统的人对此有不同的看法。这种将外部因素考虑在内的需要就导致了优先级调度。其基本思想很清楚：**每个进程被赋予一个优先级，允许优先级最高的可运行进程先运行**。
    
     *  为了防止高优先级进程一直获取CPU，调度程序可以在每个时钟滴答（即每个时钟中断）**降低当前进程的优先级**。如果这个动作导致该进程的优先级低于次高优先级的进程，则进行进程切换。
     *  每个进程可以被赋予一个允许运行的最大时间片，当这个时间片用完，下一个次高优先级的进程获得机会运行。  
        在有些操作系统内中，优先级越高的进（线）程会分到更大的时间片

可以很方便地将一组进程按优先级分成若干类，并且在各类之间采用优先级调度，而在各类进程的内部采用轮转调度。如图：  
![img][img 4]

> 注意，执行进程不一定是可运行进程中优先级最高的的。因为如果采用非抢占式调度，某个进程正在执行的过程中，来了一个优先权更高的进程进入就绪队列，由于不进行CPU抢占，则执行进程便不再是进程中优先级最高的。

*  其调度算法如下
    
     *  只要存在优先级为第4类的可运行进程，就按照轮转法为每个进程运行一个时间片，此时不理会较低先级的进程
     *  若第4类进程为空，则按照轮转法运行第3类进程。
     *  若第4类和第3类均为空，则按轮转法运行第2类进程。
     *  如果不偶尔对优先级进行调整，则低优先级进程很可能会产生饥饿现象。

除了上面介绍的几种算法以外，还有多级队列，多级反馈队列，保证调度，彩票调度等算法，此处不再一一的进行介绍。

[img]: /images/20221123/3687884c80ee4747baa917b25299d0e2.png
[img 1]: /images/20221123/edf46df882c4403fb0c1924276513bf6.png
[img 2]: /images/20221123/129d02c2bbf34d5c86c1547ba5845de9.png
[img 3]: /images/20221123/427515abf9fd425a931f1c49c4947617.png
[img 4]: /images/20221123/4046c80c47f0463686de8b3294bd9e82.png