批处理系统的目标：

平均周转时间短：用户希望自己作业的周转时间最短，希望能使平均周转时间最短。有效地提高系统资源的利用率，而且还可使大多数用户都感到满意。

系统吞吐量高：吞吐量是指在单位时间内系统所完成的作业数，因而它与批处理作业的平均长度有关。短作业优先有利于提高吞吐量。

处理机利用率高：调度方式和算法又对处理机的利用率起着十分重要的作用。选择计算量大的作业运行，可以提高利用率。

分时系统的目标：

响应时间快：响应时间，是从用户通过键盘提交一个请求开始，直到屏幕上显示出处理结果为止的一段时间间隔。

均衡性：系统响应时间的快慢应与用户所请求服务的复杂性相适应。

实时系统的目标：

截止时间的保证

截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。

实时系统中，调度算法的一个主要目标是保证实时任务对截止时间的要求。

可预测性 在实时系统中，可预测性显得非常重要。

（4）处理机调度算法的目标

处理机调度算法的共同目标：

资源利用率：使系统中的处理机和其它所有资源都尽可能地保持忙碌状态

公平性：诸进程都获得合理的CPU 时间，不会发生进程饥饿现象。

平衡性：系统中可能具有多种类型的进程，有的属于计算型作业，有的属于I/O型。为使系统中的CPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的平衡性。

策略强制执行：对所制订的策略其中包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。

（5）评价指标

周转时间

从作业提交给系统开始，到作业完成为止的这段时间间隔。

平均周转时间

带权周转时间：权值为作业周转时间Ti与系统为之服务时间TS之比。

平均带权周转时间

响应时间

从用户通过键盘提交请求开始，直到系统首次显示出处理结果为止的一段时间。

等待时间（进程调度）

进程在就绪队列中等待调度的所有时间之和。

二、作业与作业调度

1.在多道批处理系统中，作业是用户提交给系统的一项相对独立的工作。

2.操作员把用户提交的作业：

        通过相应的输入设备输入到磁盘存储器

        并保存在一个后备作业队列中

        再由作业调度程序将其从外存调入内存

作业调度的主要任务是：

1.根据作业控制块（JCB）中的信息，检查系统中的资源能否满足作业对资源的需求；

2.按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。

3.然后再将新创建的进程排在就绪队列上等待调度。在每次执行作业调度时，都需做出以下两个决定。

>> 接纳多少个作业

>> 接纳哪些作业

（1）作业调度算法

先来先服务调度算法(FCFS)

短作业优先调度算法(SJF)

优先级调度算法(PR)

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

FCFS、SJF、PR既可用于作业调度，也可用于进程调度

先来先服务调度算法(FCFS)

短作业优先调度算法(SJF)

优先权调度算法(PR)

时间片轮转调度算法(RR)

多级队列调度算法

多级反馈队列调度算法

基于公平原则的调度算法

先来先服务（FCFS）调度算法

按照作业到达的先后次序来进行调度

既可用于作业，也可用于进程

>>

假定作业到达顺序如下: J1 , J2 , J3 该调度的甘特图(Gantt)为:

平均等待时间 = (0 + 24 + 27)/3 = 17

平均周转时间 = (24 + 27 + 30)/3 = 27

假定进程到达顺序如下 J2 , J3 , J1 .

该调度的Gantt图为 :

平均等待时间 = (6 + 0 + 3)/3 = 3

平均周转时间 = (30+ 3 + 6)/3 = 13

>> 比前例好得多

>> 此结果产生是由于短进程先于长进程到达

短作业优先（SJF）调度算法

SJF算法：既可用于作业，也可用于进程

对作业：从后备队列中选择若干个估计运行时间最短的作业。

对进程：关联到每个进程下次运行的CPU区间长度，调度最短的进程。

对进程调度，SJF有两种模式：

非抢占式SJF

抢占式SJF–抢占发生在有比当前进程剩余时间片更短的进程到达时，也称为最短剩余时间优先调度

SJF是最优的（对一组指定的进程而言），它给出了最短的平均等待时间。

非抢占式SJF举例

平均等待时间 = (0 + 6 + 3 + 7)/4 = 4

平均周转时间=(7+10+4+11)/4= 8

抢占式SJF举例

平均等待时间 = (9 + 1 + 0 +2)/4 = 3

平均周转时间 = (16+ 5 +1+ 6)/4 = 7

SJF比FCFS算法有明显改进

缺点：

只能估算进程的运行时间（估值不准确），所以通常用于作业调度

对长作业不利

采用SJF算法时，人-机无法实现交互

完全未考虑作业的紧迫程度

优先级调度算法PR

既可用于作业调度，也可用于进程调度。

基于作业/进程的紧迫程度，由外部赋予作业相应的优先级，调度算法根据优先级进行调度。

每个进程都有一个优先数，优先数为整数。

默认：小的优先数具有高优先级。

目前主流的操作系统调度算法。

高响应比优先调度算法是一种优先级调度算法，用于作业调度。

优先级调度算法的类型：非抢占式、抢占式

优先级类型

静态优先级

创建进程时确定优先数(整数)，在进程的整个运行期间保持不变

简单易行，系统开销小

不够精确，可能会出现优先级低的进程长期没有被调度的情况

动态优先级

创建进程时先赋予其一个优先级，然后其值随进程的推进或等待时间的增加而改变

非抢占式优先级调度算法举例

平均等待时间 = (0 + 5 + 16+18+1)/5 =8

平均周转时间 = (16 + 1 + 18+19+6)/5 = 12

优点：

实现简单，考虑了进程的紧迫程度灵活，可模拟其它算法

存在问题：

饥饿 ——低优先级的进程可能永远得不到运行

解决方法：

老化 —— 视进程等待时间的延长提高其优先数

高响应比优先调度算法（PR的特例）

1.HRRN：既考虑作业的等到时间，又考虑作业的运行时间

2.优先级：

3.响应比：

4.如等待时间相同，运行时间越短，类似于SJF

5.如运行时间相同，取决于等待时间，类似于FCFS

6.长作业可随其等待时间的增加而提高，也可得到服务

7.缺点：每次调度之前，都需要计算响应比，增加系统开销

高响应比优先调度算法（HRRN）

例题：根据HRRN算法，计算作业平均周转时间和带权平均周转时间

JOB1运行结束后，其他作业的响应比Rp为

JOB2：(70+50)/50=2.4 J

OB3：(60+10)/10=7

JOB4：(10+20)/20=1.5

作业名

进入时间

运行时间

JOB1

8:00

120分钟

JOB2

8:50

50分钟

JOB3

9:00

10分钟

JOB4

9:50

20分钟

JOB1、JOB3运行结束后，其他作业的响应比Rp为:

JOB2：(80+50)/50=2.6

JOB4：(20+20)/20=2

三、进程调度

进程调度的任务：

保存处理机的现场信息、按某种算法选取进程、把处理器分配给进程

进程调度机制（调度程序分为三部分）：

排队器：用于将就绪进程插入相应的就绪队列

分派器：用于将选定的进程移出就绪队列

上下文切换器：进行新旧进程之间的上下文切换

（1）进程调度的方式

非抢占方式： 一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才再把处理机分配给其他进程，决不允许某进程抢占已经分配出去的处理机。

抢占方式：允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。(现代OS广泛采用)

优先权原则：允许优先权高的新到进程抢占当前进程的处理机

短作业优先原则：短作业可以抢占当前较长作业的处理机

时间片原则：各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新进行调度

抢占方式对于：

批处理机系统，可以防止一个长进程长时间地占用处理机，以确保处理机能为所有进程提供更为公平的服务。

在分时系统中，只有采用抢占方式才有可能实现人—机交互。

在实时系统中，抢占方式能满足实时任务的需求。但抢占方式比较复杂，所需付出的系统开销也较大。

（2）进程调度的方式

轮转法的基本原理：

在轮转(RR)法中，系统将所有的就绪进程按FCFS策略排成一个就绪队列。

时间片：系统可设置每隔一定时间(通常为10~100毫秒)便产生一次中断，去激活进程调度程序进行调度，把CPU分配给队首进程，并令其执行一个时间片。

当它运行完毕后，该进程将被抢占并插入就绪队列末尾

把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片。

这样循环执行，就可以保证就绪队列中的所有进程在确定的时间段内，都能获得一个时间片的处理机时间。

进程切换时机：

在RR调度算法中，应在何时进行进程的切换，可分为两种情况：

① 若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片。

② 在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。

（3）时间片大小的确定

特性：

>> q 大 => FCFS

>> q 小 => 增加上下文切换的时间

时间片设置应考虑：

>>系统对响应时间的要求、就绪队列中进程的数目、系统的处理能力

一般准则：时间片/10>进程上下文切换时间

RR例子：q = 1和q = 4时进程的周转时间



             作业情况



    时间片

进程名

A

B

C

D

E

平均

到达时间

0

1

2

3

4

服务时间

4

3

4

2

4

RR

q=1

完成时间

15

12

16

9

17

周转时间

15

11

14

6

13

11.8

带权周转时间

3.75

3.67

3.5

3

3.25

3.43

RR

q=4

完成时间

4

7

11

13

17

周转时间

4

6

9

10

13

8.4

带权周转时间

1

2

2.25

5

3.25

2.7

（4）综合调度算法：多级队列调度算法

如前所述的各种单一调度算法，尤其在应用于进程调度时，由于系统中仅设置一个进程的就绪队列，即低级调度算法是固定的、单一的，无法满足系统中不同用户对进程调度策略的不同要求

在多处理机系统中，这种单一调度策略实现机制的缺点更显突出

由此，多级队列调度算法能够在一定程度上弥补这一缺点。

（5）多级队列调度算法调度机制

多级反馈队列调度算法的调度机制可描述如下：

设置多个就绪队列。

每个就绪队列优先级不同

第一队优先级最高，依次降级

优先级越高，时间片越小

每个队列都采用FCFS算法。

先进入第一队列，完成一个时间片

一个时间片内未完成，则进入第二个队列，完成一个时间片，还未完成则进入第三个队列，以此类推。

按队列优先级调度。首先调度最高优先级队列中的个进程运行。

多级反馈队列例子

如果规定第一队列的时间片略大于大多数人际交互所需的处理时间，则能较好地满足各类用户的需要。

（6）多级反馈队列调度算法

进程能在不同的队列间移动

其他调度算法的局限性

短进程优先的调度算法，仅照顾了短进程而忽略了长进程

如果并未指明进程的长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用。

多级反馈队列调度算法优点：

不必事先知道各种进程所需的执行时间；

可以满足各种类型进程的需要。

（7）基于公平原则的调度算法

主要考虑调度的公平性。

保证调度算法：

性能保证，而非优先运行；

如保证处理机分配的公平性（处理机时间为1/n）。

公平分享调度算法：

调度的公平性主要针对用户而言；

使所有用户能获得相同的处理机时间或时间比例。

四、实时调度

（1）基于公平原则的调度算法

实时调度是针对实时任务的调度

实时任务，都联系着一个截止时间

硬实时HRT任务

软实时SRT任务

实时调度应具备一定的条件

（2）实现实时调度的基本条件

1. 提供必要的信息

就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级

2. 系统处理能力强

单处理机系统，满足

多处理机系统，满足

3. 采用抢占式调度机制

4. 采用快速切换机制

对中断具有快速响应能力

快速的任务分派能力

（3）实时调度算法分类

根据实时任务性质

HRT调度算法

SRT调度算法

根据调度方式

非抢占式调度算法

抢占式调度算法

非抢占式调度算法

非抢占式轮转调度算法

响应时间：数秒至数十秒

可用于要求不太严格的实时控制系统

非抢占式优先调度算法

响应时间：数秒至数百毫秒

可用于有一定要求的实时控制系统

抢占式调度算法

基于时钟中断的抢占式优先级调度

响应时间：几十毫秒至几毫秒

可用于大多数实时系统

立即抢占的优先级调度

响应时间：几毫秒至几百微秒

可用于有严格时间要求的实时系统

（4）最早截止时间优先(EDF)调度算法

EDF根据任务的截止时间确定优先级，截止时间越早，优先级越高

既可用于抢占式调度，也可用于非抢占式调度

非抢占式调度用于非周期实时任务

抢占式调度用户周期实时任务

--->非抢占式调度

任务1最先到达最先开始执行

任务1执行过程中任务2、任务3到达，由于任务3截止时间更早，其优先级愈高，所以执行完任务1后执行任务3

任务3执行过程中任务4到达，由于任务4截止时间更早优先级愈高，任务3执行完后执行任务4,

最后执行任务2

抢占式EDF例子

周期任务A，周期时间20ms，处理时间10ms

周期任务B，周期时间50ms，处理时间25ms

为了说明通常的优先级调度不能适用于实时系统，该图增加了固定优先级调度的第二行和第三行

第二行中

固定A，B优先级，且优先级A>B；

先执行A1，A1执行完后执行B1；

B1执行了10ms后被A2抢占；

A2执行完后继续执行B2；

B2执行10ms后被A3抢占；

A3执行完后已经到达B2的截止时间了，但B2总共执行了20ms，很明显低于所需处理时间25ms。

第三行中

固定A，B优先级，且优先级B>A；

先执行B1，B1执行完后已经过了A1的截止时间，可知A1根本就没能执行到。

第四行中

A1截止时间早于B1截止时间，先执行A1；

A1执行完执行B1，B1执行10ms后A2到达；

A2截止时间早于B1截止时间，先执行A2；

A2执行完执行B1，B1执行10ms后A3到达；

B1截止时间早于A3截止时间，继续执行B3；

以此类推，每个任务有序无错过进行，能满足系统的要求。

（5）最低松弛度优先LLF算法

根据任务的紧急程度（松弛度）确定任务优先级

紧急程度越高（松弛度越低），优先级越高

松弛度=必须完成时间－其本身的运行时间－当前时间

主要用在抢占式调度方式中

例子：

两个周期性实时任务A和B，任务A要求每20 ms执行一次，执行时间为10 ms，任务B要求每50 ms执行一次，执行时间为25 ms

（6）优先级倒置现象

采用优先级调度和抢占方式，可能产生优先级倒置。

现象：高优先级进程被低优先级进程延迟或阻塞。

解决方法：

制定一些规定，如规定低优先级进程执行后，其所占用的处理机不允许被抢占；

建立动态优先级继承。

（7）Linux进程调度

默认调度算法：完全公平调度CFS算法。

基于调度器类：允许不同的可动态添加的调度算法并存，每个类都有一个特定的优先级。

总调度器：根据调度器类的优先顺序，依次对调度器类中的进程进行调度。

调度器类：使用所选的调度器类算法（调度策略）进行内部的调度。

调度器类的默认优先级顺序为：Stop_Task＞Real_Time＞Fair＞Idle_Task

普通进程调度：

采用SCHED_NORMAL调度策略。

分配优先级、挑选进程并允许、计算使其运行多久。

CPU运行时间与友好值（-20~+19）有关，数值越低优先级越高。

实时进程调度：

实时调度的进程比普通进程具有更高的优先级。

SCHED_FIFO：进程若处于可执行的状态，就会一直执行，直到它自己被阻塞或者主动放弃CPU。

SCHED_RR：与SCHED_FIFO大致相同，只是进程在耗尽其时间片后，不能再执行，而是需要接受CPU的调度。

五、死锁概述

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

在系统中有许多不同类型的资源，其中可以引起死锁的主要是，需要采用互斥访问方法的、不可以被抢占的资源，即在前面介绍的临界资源。系统中这类资源有很多，如打印机、数据文件、队列、信号量等。

（1）资源问题

可重用性资源和可消耗性资源

可重用性资源：可供用户重复使用多次的资源

一次只能分配给一个进程，不允许多个进程共享，

遵循：请求资源→使用资源→释放资源。

系统中每一类可重用性资源中的单元数目是相对固定的，进程在运行期间既不能创建也不能删除它。

可消耗性资源：临时性资源，由进程动态创建和消耗 （进程间通信的消息）。

数目在进程运行期间是可以不断变化

进程在运行过程中，可以不断地创造可消耗性资源的单元

进程在运行过程中，可以请求若干个可消耗性资源单元，用于进程自己的消耗，不再将它们返回给该资源类中。

可抢占性和不可抢占性资源

可抢占性资源：某进程在获得这类资源后，该资源可以再被其他进程或系统抢占，CPU（处理机）和主存区。

不可抢占资源：当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，打印机、磁带机。

（2）死锁原因

竞争不可抢占性资源引起死锁

系统中的不可抢占性资源，由于它们的数量不能满足诸进程运行的需要，会使进程在运行过程中，因争夺这些资源而陷入僵局。

例如：系统中有两个进程P1和P2，它们都准备写两个文件 F1和 F2，而这两者都属于可重用和不可抢占性资源。进程P1先打开F1，然后再打开文件F2，进程P2，先打开文件F2，后打开F1，下面示出了这段代码。

将上面的问题利用资源分配图进行描述，用方块代表可重用的资源（文件），用圆圈代表进程，见图所示。这时在P1、P2及R;和R2之间，已经形成了一个环路，说明已进入死锁状态。

竞争可消耗性资源引起死锁

现在进一步介绍竞争可消耗资源所引起的死锁。图示出了在三个进程之间，在利用消息通信机制进行通信时所形成的死锁情况。

进程推进顺序不当引起死锁

进程推进顺序合法

进程推进顺序非法

除了系统中多个进程对资源的竞争会引发死锁外，进程在运行过程中，对资源进行申请和释放的顺序是否合法，也是在系统中是否会产生死锁的一个重要因素。

例如：系统中只有一台打印机R1，和一台磁带机R2 R1和R2可供进程P1和P2共享进程在运行时具有异步特性，所以推进顺序可能有多种情况。

（3）死锁定义

死锁：一组等待的进程，其中每一个进程都持有资源，并且等待着由这个组中其他进程所持有的资源。

（4）产生死锁的必要条件

互斥

一段时间内某资源只能被一个进程占用。

请求和保持

一个至少持有一个资源的进程等待获得额外的由其他进程所持有的资源。

不可抢占

一个资源只有当持有它的进程完成任务后，自由的释放。

循环等待

等待资源的进程之间存在环 {P0, P1, …, Pn} 。

P0 等待P1占有的资源, P1等待P2占有的资源, …, Pn–1等待Pn占有的资源, P0等待Pn占有的资源

（5）处理死锁的方法

确保系统永远不会进入死锁状态

死锁预防：破坏死锁的四个必要条件中一个或几个。

死锁避免：在资源动态分配时，防止系统进入不安全状态。

允许系统进入死锁状态，然后恢复系统

死锁检测：事先不采取任何措施，允许死锁发生，但及时检测死锁发发生。

死锁恢复：检测到死锁发生时，采取相应措施，将进程从死锁状态中解脱出来。

忽略这个问题，假装系统中从未出现过死锁。这个方法被大部分的操作系统采用，包括UNIX

六、预防死锁

破坏死锁的四个必要条件中的一个或几个

互斥： 互斥条件是共享资源必须的，不仅不能改变，还应加以保证

（1）破坏请求和保持

当一个进程在请求资源时，它不能持有不可抢占资源

第一种协议

该协议规定，所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。

优点：简单、易行且安全。

缺点：

如果申请到了：资源被严重浪费，严重地恶化了资源的利用率。

如果申请不到：进程经常会发生饥饿现象。

第二种协议

允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的、且已用毕的全部资源，然后再请求新的所需资源。

举例：有一个进程，要将数据从磁带复制到磁盘文件上，然后对磁盘文件进行排序。最后把结果打印出来。

（2）破坏非抢占

如果一个进程的申请没有实现，它要释放所有占有的资源；

先占的资源放入进程等待资源列表中；

进程在重新得到旧的资源的时候可以重新开始。

缺点：该方法实现起来比较复杂，且需付出很大的代价。

不可抢占资源（如打印机、刻录机等）使用一段时间后被抢占，将造成前一阶段工作失效，造成前后两次运行的信息不连续。

增加周转时间、系统开销，降低系统吞吐量。

（3）破坏循环等待

对所有的资源类型排序进行线性排序，并赋予不同的序号，要求进程按照递增顺序申请资源。

如何规定每种资源的序号是十分重要的；

限制新类型设备的增加；

作业使用资源的顺序与系统规定的顺序不同；

限制用户简单、自主的编程。

七、避免死锁

避免死锁同样是属于事先预防的策略。

并不是事先采取某种限制措施，破坏产生死锁的必要条件，

而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。

这种方法所施加的限制条件较弱，可能获得较好的系统性能。

目前常用此方法来避免发生死锁。

设一个简单而有效的模型，要求每一个进程声明它所需要的资源的最大数。

死锁避免算法动态检查资源分配状态以确保不会出现循环等待的情况。

资源分配状态定义为可用的与已分配的资源数，和进程所需的最大资源量。

（1）安全状态

当进程申请一个有效的资源的时候，系统必须确定分配后是安全的。否则，令进程等待。

如果存在一个安全序列，则系统处于安全态。

所谓安全状态，是指系统能按某种进程推进顺序（P1，P2，Pn）为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。

此时称（P，P2，….Pn）为安全序列。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。

安全状态举例

假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：

经分析发现，在T0时刻系统是安全的，因为这时存在一个安全序列（P2，P1，P3），即只要系统按此进程序列分配资源，就能使每个进程都顺利完成。

（2）安全状态向不安全状态的转换

如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。

在T0时刻，P3又申请了1台磁带机

此时系统把剩余的3台磁带机中的1台分配给了P3

此时系统进入不安全状态，此时已无法找到一个安全序列

（3）基本事实

如果一个系统在安全状态，就没有死锁

如果一个系统不是处于安全状态，就有可能死锁

死锁避免 => 确保系统永远不会进入不安全状态

（4）利用银行家算法避免死锁

最有代表性的避免死锁的算法是Dijkstra的银行家算法。

起这样的名字是由于该算法原本是为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。

在OS中也可用它来实现避免死锁。

银行家可以把一定数量的资金供多个用户周转使用，为保证资金安全，规定∶

（1）当一个用户对资金的最大需求量不超过银行家现有的资金时就可接纳该用户;

（2）用户可以分期贷款，但贷款的总数不能超过最大需求量;

（3）当银行家现有的资金不能满足用户的尚需贷款数时，对用户的贷款可推迟支付，但总能使用户在有限的时间里得到贷款;

（4）当用户得到所需的全部资金后，一定能在有限的时间里归还所有的资金。

我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款，操作系统按照银行家制定的规则为进程分配资源。

该算法原本是为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。

针对资源有多个实例

每一个进程必须事先声明使用的最大量

当一个进程请求资源，它可能要等待

当一个进程得到所有的资源，它必须在有限的时间释放它们

银行家算法例子

现在通过一个例子来说明银行家算法是怎样进行资源分配的。假定某系统有三类资源A、B、C，资源类A共有10个资源，资源类B 共有5个资源，资源类C共有7个资源，现有5个进程，它们对各类资源的最大申请量和第一次请求分配的资源量如表所示。

如果进程P1、P2、P3、P4、P5依次向系统提出申请资源的要求：系统为进程P1和进程P2分配资源后剩余的资源为A类8个，B类4个，C类7个。

紧接着进程P3申请资源时将被拒绝，因为A类资源只剩8个，不能满足进程P3对A类资源的最大需求量，故对进程P3的资源分配需推迟。

但是，对后继的进程P4和进程P5的请求可以接受并为它们分配资源。

如果申请资源的进程次序为P3，P1，P2，P5，P4，则系统都能为这5个进程第一次分配，此时系统是安全的。分配后的情况如下表所示。

现在系统剩余A类资源3个，B类资源3个和C类资源2个，用（3，3，2）表示。

当5个进程都希望系统为它们分配尚需的资源时，为保持系统的安全，此时只能接受进程P2或进程P4的请求。因为剩余的资源不能满足进程P1或进程P3或进程P5的尚需资源，这些进程只能等其他进程归还资源后才可能得到尚需的资源。

如果系统先把现存的（3，3，2）资源中的一部分分配给了进程P2。当进程P2执行结束归还资源后系统就有（5，3，2）个资源，可满足进程P4或进程P5的需求。

若先满足进程P4的要求，则进程P4执行结束后系统可分配的资源就增加到（6，4，3），能满足进程P3或进程P5的需求，可把资源先分配给它们中的一个进程，但仍不能为进程P1分配。

按银行家算法继续为进程分配资源，直到所有进程都执行结束，系统收回全部资源。

银行家算法的数据结构

n为进程的数目，m为资源类型的数目

Available: 长度为 m的向量。如果available[j]=k,那么资源Rj有k个实例有效

Max: n x m 矩阵。如果Max[i,j]=k,那么进程Pi可以最多请求资源Rj的k个实例

Allocation: n x m 矩阵。如果Allocation[i,j]=k,那么进程Pj当前分配了k个资源Rj的实例 Need: n x m 矩阵。如果Need[i,j]=k,那么进程Pj还需要k个资源Rj的实例

Need [i,j] = Max[i,j] – Allocation [i,j].

安全性算法

让Work和Finish作为长度为m和n的向量初始化

Work := Available

Finish [i] = false for i - 1,3, …, n.

查找i

(a) Finish [i] = false

(b) Needi => Work

If no such i exists, go to step ④.

Work := Work + Allocationi

Finish[i] := true

go to step ②.

如果对所有i的 Finish [i] = true, 则系统处在安全状态

银行家算法：是否满足某进程的资源请求

Requesti =进程 Pi 的资源请求向量，如果Requesti [m] = k 则进程 Pi 想要资源类型为Rjm的k个实例

如果 Requesti <=（小于等于） Needi 转 step 2. 否则报错, 因为进程请求超出了其声明的最大值

如果 Requesti <= Available, 转 step 3. 否则 Pi 必须等待, 因为资源不可用

假设通过修改下列状态来试着分配请求的资源给进程Pi :

Available := Available - Requesti;

Needi := Needi – Requesti;

Allocationi := Allocationi + Requesti;

系统执行安全性算法

如果系统安全 => 将资源分配给 Pi.

如果系统不安全 => Pi 必须等待，恢复原有的资源分配状态

八、死锁的检测与解除

（1）死锁的检测与解除

如果在系统中，既不采取死锁预防措施，也未配有死锁避免算法，系统很可能会发生死锁。

在这种情况下，系统应当提供两个算法：

① 死锁检测算法。该方法用于检测系统状态，以确定系统中是否发生了死锁

② 死锁解除算法。当认定系统中已发生了死锁，利用该算法可将系统从死锁状态中解脱出来。

为了能对系统中是否已发生了死锁进行检测，在系统中必须：

保存有关资源的请求和分配信息；

提供一种算法，它利用这些信息来检测系统是否已进入死锁状态

资源分配图(Resource Allocation Graph) 系统死锁，可利用资源分配图来描述。

（2）资源分配图

系统模型

资源类型 R1, R2, . . ., Rm

CPU周期，内存空间，I/O设备

每一种资源Ri 有Wi 种实例

每一个进程通过如下方法来使用资源

申请

使用

释放

（3）资源分配图组成

一个顶点的集合V和边的集合E

V被分为两个部分

P = {P1, P2, …, Pn}, 含有系统中全部的进程

R = {R1, R2, …, Rm}, 含有系统中全部的资源

请求边：有向边Pi -> Rj

分配边：有向边 Rj Pi

无死锁的资源分配图

有死锁的资源分配图

（4）基本事实

如果图没有环，那么不会有死锁！

如果图有环，那么：

如果每一种资源类型只有一个实例，那么死锁发生；

如果一种资源类型有多个实例，那么可能死锁。

（5）资源分配图的简化

在资源分配图中，找出一个既不阻塞又非独立的进程结点pi。在顺利的情况下，pi可获得所需资源而继续运行，直至运行完毕，再释放其所占有得全部资源，这相当于消去pi所有的请求边和分配边，使之成为孤立的结点；

p1释放资源后，便可使p2获得资源而继续运行，直到p2完成后又释放出它所占有的全部资源；

在进行一系列的简化后，若能消去图中所有的边，使所有进程都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。

（6）死锁定理

对于较复杂的资源分配图，可能有多个既未阻塞、又非孤立的进程结点，不同的简化顺序，是否会得到不同的简化图？有关文献已经证明，所有的简化顺序，都将得到相同的不可简化图。

S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。该充分条件称为死锁定理。

（7）死锁检测算法

数据结构类似于银行家算法（基于资源分配图简化）

Work：=Available；
        L：={Li│Allocationi=0∩Requesti=0}
        for all Li  L do
          begin
           for all Requesti≤Work do
             begin
               Work：= Work + Allocationi；
               Li∩L；
             end
           end
           deadlock：= ┐（L={P1，P2，…，Pn}）；

让Work和Finish作为长度为m和n的向量初始化

(a) Work := Available

(b)   For i = 1,2, …, n, if Allocationi 不等于 0, then Finish[i] := false;otherwise, Finish[i] := true.

找到满足下列条件的下标i

(a)   Finish[i] = false

(b)   Requesti 小于等于 Work 如果没有这样的i存在，转4

Work := Work + Allocationi Finish[i] := true 转 2.

如果有一些i, 1 小于等于 i 小于等于 n , Finish[i] = false, 则系统处在死锁状态。而且，如果 Finish[i] = false, 则进程 Pi 是死锁的。

（8）死锁的解除

常用解除死锁的两种方法：

抢占资源。从一个或多个进程中抢占足够数量的资源给死锁进程，以解除死锁状态

终止或撤消进程。终止系统中一个或多个死锁进程，直到打破循环环路，使死锁状态消除为止。

终止所有死锁进程（最简单方法）

这是一种最简单的方法，即是终止所有的死锁进程，死锁自然也就解除了，但所付出的代价可能会很大。

因为其中有些进程可能已经运行了很长时间，已接近结束，一旦被终止真可谓“功亏一篑”，以后还得从头再来。

还可能会有其它方面的代价，在此不再一一列举。

逐个终止进程（稍温和方法）

稍微温和的方法是，按照某种顺序，逐个地终止进程，直至有足够的资源，以打破循环等待，把系统从死锁状态解脱出来为止。

但该方法所付出的代价也可能很大。因为每终止一个进程，都需要用死锁检测算法确定系统死锁是否已经被解除，若未解除还需再终止另一个进程。

另外，在采取逐个终止进程策略时，还涉及到应采用什么策略选择一个要终止的进程。选择策略最主要的依据是，为死锁解除所付出的“代价最小”。但怎么样才算是“代价最小”，很难有一个精确的度量。

应该选择怎样的中断顺序，使“代价最小”？

进程的优先级；

进程需要计算多长时间，以及需要多长时间结束；

进程使用的资源，进程完成还需要多少资源；

进程是交互的还是批处理的。

作业名	进入时间	运行时间
JOB1	8:00	120分钟
JOB2	8:50	50分钟
JOB3	9:00	10分钟
JOB4	9:50	20分钟

作业情况时间片	进程名	A	B	C	D	E	平均
	到达时间	0	1	2	3	4
	服务时间	4	3	4	2	4
RR q=1	完成时间	15	12	16	9	17
	周转时间	15	11	14	6	13	11.8
	带权周转时间	3.75	3.67	3.5	3	3.25	3.43
RR q=4	完成时间	4	7	11	13	17
	周转时间	4	6	9	10	13	8.4
	带权周转时间	1	2	2.25	5	3.25	2.7

处理机调度与死锁

一、处理机调度的层次和调度算法的目标

（1）处理机调度层次

（2）处理机调度层次

高级调度

中级调度

低级调度

（3）处理机调度算法的目标

（4）处理机调度算法的目标

（5）评价指标

周转时间

响应时间

等待时间（进程调度）

二、作业与作业调度

（1）作业调度算法

先来先服务（FCFS）调度算法

短作业优先（SJF）调度算法

优先级调度算法PR

高响应比优先调度算法（PR的特例）

高响应比优先调度算法（HRRN）

三、进程调度

（1）进程调度的方式

（2）进程调度的方式

（3）时间片大小的确定

（4） 综合调度算法：多级队列调度算法

（5）多级队列调度算法调度机制

多级反馈队列例子

（6）多级反馈队列调度算法

（7）基于公平原则的调度算法

四、实时调度

（1）基于公平原则的调度算法

（2）实现实时调度的基本条件

（3）实时调度算法分类

非抢占式调度算法

抢占式调度算法

（4）最早截止时间优先(EDF)调度算法

抢占式EDF例子

（5）最低松弛度优先LLF算法

（6）优先级倒置现象

（7）Linux进程调度

五、死锁概述

（1）资源问题

（2）死锁原因

（3）死锁定义

（4）产生死锁的必要条件

（5）处理死锁的方法

六、预防死锁

（1）破坏请求和保持

第一种协议

第二种协议

（2）破坏非抢占

（3）破坏循环等待

七、避免死锁

（1）安全状态

安全状态举例

（2）安全状态向不安全状态的转换

（3）基本事实

（4）利用银行家算法避免死锁

银行家算法例子

银行家算法的数据结构

安全性算法

银行家算法：是否满足某进程的资源请求

八、死锁的检测与解除

（1）死锁的检测与解除

（2）资源分配图

（3）资源分配图组成

无死锁的资源分配图

有死锁的资源分配图

（4）基本事实

（5）资源分配图的简化

（6）死锁定理

（7）死锁检测算法

（8）死锁的解除

网站公告

今日签到

热门文章

最新发布

（4）综合调度算法：多级队列调度算法