目录

一、处理机调度

1.1 处理机调度的层次

1.1.1 高级调度 

1.1.2 低级调度

1.1.3 中级调度

1.2 调度频率的比较

1.3 调度算法的评价指标

1.3.1 CPU利用率

1.3.2 系统吞吐量

1.3.3 周转时间

1.3.4 等待时间

1.3.5 响应时间

二、作业调度

2.1 先来先服务（FCFS）

2.2 短作业(进程)优先  (SJ(P)F) 

2.3 高响应比优先调度算法 (HRRN)

2.4 总结 

三、进程调度 

3.1 短进程优先（SPF）

3.2 时间片轮换法

3.3 优先级调度算法

3.4 多级反馈队列调度算法

3.5 总结

四、实时调度

4.1 最早截止时间优先EDF（Earliest Deadline First）算法

4.2 最低松弛度优先LLF（Least Laxity First）算法 

五、死锁

5.1 预防死锁

5.1.1 破坏请求和保持条件

5.1.2 破环不剥夺条件

5.1.3 破坏循环等待条件

5.2 避免死锁

5.2.1 安全状态 和 不安全状态

5.2.2 银行家算法

5.3 死锁的检测和解除 

5.3.1 死锁的检测 

5.3.2 死锁的解除 

六、结尾

Reference

在多道程序环境下，进程数目往往多于处理机数目。这就要求系统能够按某种算法，动态的把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。

一个批处理型作业，从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历下述三级调度。

又称为作业调度或长程调度（Long-Term Scheduling），用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后将新创建的进程排在就绪队列上，准备执行。因此有时也称作业调度为接纳调度。

在批处理系统中，因作业进入系统后先驻留在外存，故需要有作业调度。在分时系统中为做到及时响应，作业被直接送入内存，故不需作业调度。在实时系统中，通常也不需作业调度。

每次执行作业调度时，都须作出两个决定：

对进程状态的影响：无 -> 创建态 -> 就绪态 

通常也称为进程调度或短程调度（Short-Term Scheduling），用来决定就绪队列中的哪个进程应获得处理机，然后再由分派程序把处理机分配给该进程。为最基本的一种调度，三种OS中都有。

进程调度可采用下述两种调度方式：

● 非抢占方式（Non-preemptive Mode）： 一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才把处理机分配给其他进程，决不允许进程抢占已分配出去的处理机。评价：实现简单、系统开销小；适用于大多数的批处理OS，但在要求比较严格的实时系统中，不宜采用这种调度方式

● 抢占方式（Preemptive Mode）：允许调度程序根据某种原则，去暂停某个正在执行的进程，将处理机重新分配给另一进程。

对进程状态的影响：就绪态 -> 运行态 

又称中程调度（Medium-Term Scheduling）。引入目的是为了提高内存利用率和系统吞吐量。为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调之外存去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。

中级调度实际上就是存储器管理中的对换功能，第四章会讲解。

对进程状态的影响：挂起态 -> 就绪态 

1、进程调度的运行频率最高，在分时系统中通常是10~100ms便进行一次进程调度，因而进程调度算法不能太复杂，以免占用太多的CPU时间。

2、作业调度是发生在一个作业运行完毕，退出系统，而需要重新调度一个作业进入内存时，故作业调度的周期较长，大约几分钟一次。因而也允许作业调度算法花费较多的时间。 

3、中级调度的运行频率，基本上介于进程调度和作业调度之间。

CPU利用率：指CPU“忙碌”的时间占总时间的比例。

利用率 = CPU忙碌的时间 / 总时间

系统吞吐量：单位时间内完成作业的数量。

系统吞吐量 = 总共完成了多少道作业 / 总共花了多少时间

周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。 它包括四个部分： 作业在外存后备队列上等待作业调度(高级调度) 的时间、进程在就绪队列上等待进程调度(低级调度)的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间。后三项在一个作业的整个处理过程中，可能发生多次。

对于用户来说，更关心自己单个作业的周转时间。  

【1】周转时间 = 作业完成时间 - 作业提交时间

对于操作系统来说，更关心系统的整体表现，即所有作业的平均周转时间。

【2】平均周转时间 = 各作业周转时间之和 / 作业数

对于单个作业的执行满意度而言，带权周转时间更小，用户才会更加满意。

理由如下：

【3】带权周转时间 = 作业周转时间 / 作业实际运行的时间

同理，还有平均带权周转时间。

【4】平均带权周转时间 =各作业带权周转时间之和 / 作业数

注意：带权周转时间必定大于1。

计算机的用户希望自己的作业/进程尽可能少的等待处理机。

等待时间指：作业/进程处于等待处理机状态的时间之和。

一个作业总共需要被CPU服务多久，被I/O设备服务多久一般是确定不变的，因此调度算法其实只能影响作业或者进程的等待时间。当然，与前面指标类似，也有“平均等待时间”来评价整体性能。

从用户提交请求到首次产生响应所用的时间。即 等待时间+要求服务时间 

对于不同的系统和系统目标，通常采用不同的调度算法：例如，在批处理系统中为照顾为数众多的短作业，应采用短作业优先的调度算法；又如在分时系统中，为了保证系统具有合理的响应时间，应采用轮转法进行调度。 

目前存在的多种调度算法中，有的算法适用于作业调度，有的算法适用于进程调度；但有些算法作业调度和进程调度都可以采用。 

是一种最简单的调度算法，既可用于作业调度，也可用于进程调度。

例题： 答案：

从表上可以看出，其中短作业P3的带权周转时间竟高达8，这是不能容忍的；而长作业P1的带权周转时间仅为1。因此FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。

对于抢占式的短进程优先调度算法在下面的进程调度讲解。

对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。 

 例题：

答案：

采用SJF算法后，不论是平均周转时间还是平均带权周转时间，都较FCFS调度算法有较明显的改善，尤其是对短作业P3。而平均带权周转时间从3.5降到了2.56。这说明SJF调度算法能有效的降低作业的平均等待事件，提高系统吞吐量。 

优点：有效降低作业的平均等待时间，提高系统吞吐量。

缺点：

我们为每个作业引入动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则可解决问题。见下式：

优先权 = (等待时间+要求服务时间) / 要求服务时间

由于等待时间与服务时间之和就是系统的响应时间，故上式又表示为：

Rp = 响应时间 / 要求服务时间 

兼顾前面两种调度算法的优点（即考虑等待时间，又考虑了要求服务时间）。

由上式可以看出：

例题：

答案：

为最基本的一种调度，三种OS中都有。

短作业（进程）可以抢占长作业（进程）的处理机。

例题：

答案：

注意： 如果题目中，没有明确说明是抢占还是非抢占，默认是非抢占式的。

系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给首进程，并令其执行一个时间片。 

时间片的大小从几ms到几百ms。当执行的时间片用完时，停止该进程的执行并将其送往就绪队列的末尾。这样就可以保证就绪队列中所有进程在一定时间内均能获得一时间片的处理机执行时间，也就是说系统能在给定的时间内响应所有用户的请求。

例题： （时间片大小为2）

答案： 

【1】首先分析：0时刻 ~ 5时刻

【2】 分析：6时刻 ~ 11时刻

【3】分析：12时刻 ~ 16时刻

 注意：

根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种。 静态优先级： 创建进程时确定，之后一直不变。 动态优先级： 创建进程时有一个初始值， 之后会根据情况动态地调整优先级。

做题肯定是静态优先级的！ 

 【1】首先先来分析非抢占的：

例题 ： 

答案：

【2】 分析 抢占的：

例题：

答案： 

注意：优先数越大，优先级越高是根据题目而定的，也可以反着来。

前面介绍的各种进程调度的算法都有一定的局限性。这里介绍一种目前被公认为较好的进程调度算法——多级反馈队列调度算法。实施过程如下：

当一个新进程进入内存后，首先将它放入第一个队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，在同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……如此下去，当一个长作业（进程）从第一队列依次降到第n队列后，在第n队列（最后一个队列）中便采取按时间片轮转的方式运行。

仅当第一队列空闲时，调度程序才调度第二队列中的进程运行，换言之，仅当第1~(i-1)队列均空时，才会调度第i队列中的进程

例题：

答案：

图解：

要点：

实时系统中包含两种任务：

在实时系统中，硬实时任务和软实时任务都联系着一个截止时间。为保证系统能正常工作，实时调度必须满足实时任务对截止时间的要求，为此，实现实时调度应具备下列4个条件：

1、提供必要的信息

2、系统处理能力强

3、采用抢占式调度机制。但是对于一些小的实时系统，如能预知任务的开始截止时间，则对实时任务的调度可采用非抢占调度机制。

4、具有快速切换机制  

可按照不同方式对实时调度算法加以分类：

1、根据实时任务性质的不同，分为硬实时调度算法和软实时调度算法；

2、按调度方式的不同，分为非抢占调度算法和抢占调度算法；

3、根据调度程序调度时间的不同，分为静态调度算法和动态调度算法。

4、多处理机环境下，可分为集中式调度和分布式调度两种算法。

目前有许多实时调度算法，在常用的算法中简单介绍两种实时调度算法： 

我们学校应该期末不会考察，重点在作业调度和进程调度，所以有需要的朋友，可以查询其他博客或B站上优质的视频学习了解。

概念：根据任务的截止时间来确定任务的优先级。截止时间越早，其优先级越高。该算法要求在系统中保持一个实时任务就绪队列，该队列按各任务截止时间的早晚排序，调度程序在选择任务时总是选择就绪队列中的第一个任务，为之分配处理机，使之投入运行。

EDF算法既可以用于抢占式调度，也可用于非抢占式调度。

概念：该算法是根据任务紧急（或松弛）的程度，来确定任务的先级。任务的紧急程度越高，为之赋予的优先级就越高。

例如，任务A在200ms时必须完成，本身运行时间100ms，则必须在100ms之前调度执行，A任务的紧急（松弛）程度为100ms，又如任务B在400ms是必须完成，需运行150ms，其松弛程度为250ms.

 该算法主要用于抢占调度方式中。 

在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险——死锁。

死锁（Deadlock）：是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种状态时，若无外力作用，它们都将无法再向前推进。

产生死锁的原因可归结为如下两点：

1、竞争资源。当系统中供多个进程共享的资源如打印机、公用队列等，其数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。

2、进程间推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生死锁。例如进程P1和P2分别申请了资源R1和R2，但是紧接着P1又申请P2拥有的R2资源，P2申请P1拥有的R1资源。

产生死锁的必要条件：

【1】互斥条件：指进程对所分配到的资源进行排他性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其他进程请求该资源，则请求者只能等待，直至占有该资源的进程用毕释放。

【2】请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求（该资源又被其他进程占有，此时请求进程阻塞，但又对自己已获得的其他资源保持不放）。

【3】不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

【4】循环等待条件：指在发生死锁时，必然存在一个 进程—资源 的环形链。即进程集合{P0,P1,P2,…,Pn}中的P0正在等待一个P1占用的资源；P1正在等待一个P2占用的资源，……，Pn正在等待一个已被P0占用的资源。 

注意：

注意区别 死锁、饥饿、死循环 ：

处理死锁的基本方法

1、预防死锁：这是一种较简单和直观的事先预防方法。该方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件的一个或几个，来预防发生死锁。预防死锁是一种较易实现的方法，已被广泛使用。但由于所施加的限制条件往往太严格。可能会导致系统资源利用率和系统吞吐量降低。

2、避免死锁：该方法同样是属于事先预防的策略，但它并不须事先采取各种限制措施去破坏产生死锁的四个必要条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。这种方法只须事先加以较弱的限制条件，便可获得较高的资源利用率及系统吞吐量，但在实现上有一定的难度。目前在较完善的系统中，常用银行家算法来避免发生死锁。

3、死锁的检测和解除：允许死锁发生，系统负责检测出死锁并解除。这种有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。

预防死锁的方法是使四个必要条件中的第2、3、4条件之一不能成立，来避免发生死锁。至于必要条件1，因为它是由设备的固有条件所决定的，不仅不能改变，还应加以保证（有少数的互斥资源可以改造成共享的，但是大部分都不行，所以这里不做过多探讨）。下面分别对三种情况加以说明：

解决办法：系统规定所有进程在开始运行之前，都必须一次性的申请其在整个运行过程所需的全部资源。此时若系统有足够资源就分配给该进程，该进程在运行期间不会提出资源要求，从而摒弃了“请求”条件。若系统没有足够资源分配给它，就让该进程等待。因而也摒弃了“保持”条件，从而可避免发生死锁。

该策略实现起来简单，但也有明显的缺点：

有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。

不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。

破坏不剥夺条件：

该策略的缺点：

循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

解决方法：首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源(即编号相同的资源)一次申请完。

原理分析：一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。

假设系统中共有10个资源, 编号为1,2, ……10。P1、P2、P3进程拥有资源如下：

那么在任何一个时刻，总有一个进程拥有的资源编号是最大的（比如此时的进程P3），那这个进程申请之后的资源必然畅通无阻。因此，不可能出现所有进程都阻塞的死锁现象。

该策略的缺点：

在该方法中把系统的状态分为 安全状态 和 不安全状态，只要能使系统始终都处于安全状态，便可避免发生死锁。 

安全状态，是指系统能按某种进程顺序（ P0, P1, P2, …, Pn ）来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。

虽然并不是所有的不安全状态都是死锁状态，但是死锁状态一定处于不安全状态，但当系统进入不安全状态后，便可能进入死锁状态；反之只要处于安全状态就不会死锁。

避免死锁的实质是：系统在进行资源分配时，设法使系统不进入不安全状态。

这句话为什么不改成《设法使系统进入安全状态呢》，你要知道，避免死锁是属于事先预防的，是在事先检测：如果分配了这份资源，是否会找不到一个安全序列，如果找不到，即系统处于不安全状态，那么不予分配，反之可以分配。因此设法让系统进入安全状态是其不能主导的，而只能事先检测，尽量避免使系统不进入不安全状态，如果不安全，就不予分配这份资源。

银行家算法是荷兰学者 Dijkstra为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中，用于避免死锁。

核心思想：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。

接下来就开始讲怎么个预判法！！！

在介绍之前，先了解银行家算法中涉及的数据结构 (设系统中有m类资源，n个进程)：

【1】可利用资源向量Available。含有m个元素的一维数组，每个元素代表一类可利用的资源数目，初值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配与回收而动态的改变。Available[j]=K, 表示系统中现有Rj类资源K个。

【2】最大需求矩阵Max。为n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求数。Max[i,j]=K, 表示进程i需要Rj类资源的最大数目为K。

【3】分配矩阵Allocation。为n*m的矩阵，它定义了系统中每类资源当前已分配给每一进程的资源数。Allocation[i,j]=K,表示进程i当前已分得Rj类资源的数目为K。 

【4】需求矩阵Need。为n*m的矩阵，表示每个进程尚需的各类资源数。Need[i,j]=K, 表示进程i还需要Rj类资源K个，方能完成其任务。

三个矩阵间的关系：Need[ i , j] = Max[ i , j] - Allocation[ i , j] 

基于银行家算法，系统按下述步骤进行检查： 

设是进程Pi的请求向量。 ，表示Pi需K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：