操作系统第3章(2)(第四版)

3.4实

时

调

度

一、实现实时调度的基本条件提供必要的信息；

就绪时间、截止时间、处理时间、资源要求、优先级；系统处理能力强；

对单处理机：

m个周期性硬实时任务；处理时间：Ci；周期时间：Pi

满足：采用抢占式调度机制；具有快速切换机制：对外部中断的快速响应能力。(具有快速硬件中断机构)

快速的任务分派能力。（快速任务切换，减少任务切换时间）

二、实时调度算法的分类（调度方式的不同）1．非抢占式调度算法----适用：不太严格，小型实时系统1)非抢占式轮转调度算法适用：工业生产的群控系统，不太严格实时系统；响应：数秒~数十秒计算机对象实时任务轮转2)非抢占式优先调度算法适用：较严格实时系统；响应：数百毫秒调用就绪队列新任务插入队首当前任务CPU完成或终止被调用优先级高2．抢占式调度算法-适用：较严格实时系统基于时钟中断的抢占式优先权调度算法适用：大多数实时系统；响应：几十毫秒~几毫秒新任务当前任务CPU产生时钟中断抢占优先级高等待时钟中断2)立即抢占(ImmediatePreemption)的优先权调度算法适用：大多数实时系统；响应：几毫秒~100微秒只要当前任务未处于临界区，便立即剥夺当前任务的执行。三、常用的几种实时调度算法1．最早截止时间优先即EDF(EarliestDeadlineFirst)算法

算法：根据任务的开始截止时间来确定任务的优先级。截止时间愈早，其优先级愈高。要求：系统中保持一个实时任务就绪队列，该队列按各任务截止时间的早晚排序；适用：抢占式调度、非抢占式调度。

该算法用于非抢占式调度方式示例。在该例子中具有四个非周期任务，它们先后到达。

任务1任务执行→任务到达→任务1t图3-9DEF算法用于非抢占式调度方式任务3任务4任务2任务2任务3任务4开始截止时间：任务1的任务3的任务4的任务2的结束下一步下一步2．最低松弛度优先即LLF(LeastLaxityFirst)算法

算法：根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，优先级就愈高。

例如：一个任务在200ms时必须完成，它本身所需的运行时间有100ms，该任务的紧急程度(松弛程度)为100ms。

实现：一个按松弛度排序的实时任务就绪队列；松弛度最低（最紧迫）的任务排在队列最前面；调度程序选择就绪队列中的队首任务执行。适用：可抢占调度

例：一个实时系统中有两个周期性实时任务，A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间25ms。对于A，合适截止时间依次为20、40、60、80、100…;对于B，合适截止时间依次为50、100、150…;

图3-11给出了A和B截止的时间点。

图3-11A和B任务每次必须完成的时间020406080100120140160180200AAAAAAAAAAtBBBB松弛度=必须完成的时间点-本身所需运行时间-当前时间:A1(10)B1(20)0102030405060708090100t1t2

t3

t4

t5t6

t7

t8

t图3-12利用LLF算法对两个周期性实时任务进行调度A2(10)A3(10)A4(10)B1(5)B2(15)B2(10)初始：t=0时刻，计算A，B松弛度：A1=20–10–0=10B1=50–25–0=25t=10时刻，计算A，B松弛度：A2=40–10–10=20B1=50–25–10=15t=30时刻，计算A，B松弛度：A2=40–10–30=0B1=50–5–30=15t=40时刻，计算A，B松弛度：A3=60–10–40=10B1=50–5–40=5t=45时刻，计算A，B松弛度：A3=60–10–45=5B2=100–25–45=30t=55时刻，计算A，B松弛度：A4=80–10–55=35B2=100–25–55=20t=70时刻，计算A，B松弛度：A4=80–10–70=0B2=100–10–70=20t=80时刻，计算A，B松弛度：A5=100–10–80=10B2=100–10–80=10结束●●下一步下一步下一步下一步下一步下一步下一步下一步最低松弛度优先（LLF）3.5产生死锁的原因和必要条件

一、死锁的概念

1.死锁问题P(s1)P(s2)临界区V(s2)V(s1)P(s2)P(s1)临界区V(s1)V(s2)........................进程1进程2就绪就绪执行执行阻塞s1s2阻塞状态：状态：死锁2.死锁概念

指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。

即：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。

3.关于死锁的一些结论

1)参与死锁的进程最少是两个。

2)参与死锁的进程至少有两个已经占有资源。

3)参与死锁的所有进程都在等待资源。

4)参与死锁的进程是当前系统中所有进程的子集。

注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。

4.永久性资源和临时性资源永久性资源：可以被多个进程多次使用（可再用资源）可抢占资源(可剥夺)；如：主存、CPU不可抢占资源（不可剥夺）；如：打印机临时性资源：只可使用一次的资源；如信号量，中断信号，同步信号（可消耗性资源）“申请--分配--使用--释放”模式二、产生死锁的原因

产生的根本原因是系统能够提供的资源数少于需要该资源的进程数(系统资源不足)。

1）竞争系统资源(不可剥夺)。

2）进程的推进顺序不当。死锁起因是并发进程的资源竞争，但资源竞争并不一定产生死锁。1.竞争系统资源（非可剥夺）

若系统中只有一台打印机R1和一台磁带机R2，可供进程P1和P2共享。若形成环路，这样会产生死锁。

实质：可共享资源不足。2.进程的推进顺序不当

在进程P1和P2并发执行时，按照左图曲线①②③所示顺序推进时，两进程会顺利完成，我们称这种推进顺序是合法的。若按曲线④的顺序推进时，进入不安全区D内，两进程再推进会产生死锁。三、产生死锁的必要条件

1）互斥条件。进程对其所要求的资源进行排它性控制，即一次只有一个进程可以使用一个资源。

2）请求和保持条件。进程已经保持了至少一个资源，但又提出了新的资源请求。

3）不剥夺条件。进程所获得的资源在未被释放之前，不能被其它进程强行剥夺。

4）环路条件。在发生死锁时，必然存在一个进程资源的循环等待链，P1P2R1R2被占有

被占有

请求请求四、处理死锁的基本方法

1.预防死锁

原理：设置某些限制条件，破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。

优点：较简单、直观的。

缺点：导致系统资源利用率和系统吞吐量降低。

1)弃“互斥条件”。为了破坏资源使用的互斥条件，就要允许多个进程同时访问共享资源。但是这种方法受到资源本身固有特性的限制，对某些资源是行不通的。例如打印机，就不允许多个进程在其运行期间交替打印数据，打印机只能互斥使用。而文件，可能允许多个进程对其进行读访问，但只允许互斥地写访问。总之：由于受限于资源本身，互斥条件难以破坏。

2)弃“请求和保持”条件第一种协议：

策略：资源一次性分配。(资源的静态分配策略)优点：简单、易于实现，且很安全。缺点：（1）资源严重浪费。一个进程一次获得其所需的全部资源且独占，其中可能有些资源很少使用，甚至在整个运行期间都未使用，这就严重地恶化了系统资源利用率。（2）进程延迟运行。仅当进程获得其所需全部资源后，方能开始运行，但可能有许多资源长期被其它进程占用，致使进程推迟运行，这往往要经过很长的时延。（饥饿现象）第二种协议：

策略：一个进程只获得初期所需资源后，开始运行。运行过程逐步释放已分配、已用完的全部资源，再请求新的所需资源。

如进程任务:（1）数据从磁带机复制到磁盘文件；（2）对磁盘文件进行排序；（3）打印机打印结果；

分析：

按第一协议必须开始请求获得磁带机、磁盘文件、打印机；打印机最后用，即影响效率又影响其他进程运行，还有可能打印机得不到，推迟运行。

按第二协议开始只需请求磁带机和磁盘文件，便可运行。等任务前（1）、（2）完成后释放磁带机和磁盘文件，再请求磁盘文件和打印机。可以提高设备利用率和减少进程饥饿现象。3）弃“不剥夺”条件

策略：申请未果，则放弃。

问题：

1）实现比较复杂，代价很大。

2）一个资源在使用一段时间后被释放，可能会造成前阶段工作的失效，即使采取某些防范措施，也还会使前后两次运行的信息不连续。

3）还可能由于反复地申请和释放资源，使进程的执行无限推迟。这不仅延长了进程的周转时间，还增加了系统开销，又降低了系统吞吐量。4）弃“环路等待”条件

策略：资源有序分配策略。

做法：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反。

编号的原则：较为紧缺的资源给以一个较大的序号。

优点：较前两种策略，资源利用率和系统吞吐量，都有显著的改善。

问题：

a.限制了新设备类型的增加；

b.发生作业使用资源的顺序与系统规定顺序不同的情况，造成资源的浪费，如：某进程先用磁带机，后用打印机，但按系统规定，它应先申请打印机，后申请磁带机，致使打印机长期闲置。

c.限制了用户简单、自由的编程。2.避免死锁(允许动态申请资源)

预防死锁的几种策略问题：严重地损害了系统性能。

死锁避免定义：在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。P进程R资源动态申请系统是否满足申请资源要求？否不予分配检查是试分配新状态系统进入新状态是否安全？检查不分配等待不安全允许最终分配安全系统可用资源>=申请资源思考：1、什么是安全状态？1）安全状态与不安全状态

安全状态指系统能按某种进程顺序来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。若系统不存在这样一个序列，则称系统处于不安全状态。

关键：寻找一个进程推进安全序列。结论：

a.安全状态一定是没有死锁发生的。

b.并非所有的不安全状态都必然会转为死锁状态。

c.避免死锁的实质：系统在进行资源分配时，如何使系统不进入不安全状态。2)安全状态之例假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配。T0：共有12台，可用3台寻找到安全序列：<P2，P1，P3>结论：系统在T0时刻是安全的。由安全状态向不安全状态的转换例如：在T0时刻以后，P3又请求1台磁带机；T0：转变新状态：结论：无法找到安全序列；系统在新状态下是不安全的。

P3请求1台磁带机后系统进入不安全状态，不可对其分配。4）利用银行家算法避免死锁a．银行家算法中的数据结构

(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]b．安全性算法—判断状态是否安全。

关键：寻找一个进程安全的推进序列。

描述如下：

(1)设置两个向量：

①工作向量Work，表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work:=Available。

②Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]:=false；当有足够资源分配给进程时，再令Finish[i]:=true。

(2)算法从进程集合中找到一个能满足下述条件的进程：①Finish[i]=false；未推进的进程②Need[i,j]≤Work[j]；若找到，执行步骤(3)，否则，执行步骤(4)。

③当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work[j]:=Work[j]+Allocation[i,j]；Finish[i]:=true；gotostep2；

④如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。例：判断当前状态是否是否安全的。假定系统中有五个进程{P0，P1，P2，P3，P4}和三类资源{A，B，C}，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图所示。

图3-16T0时刻的资源分配表

T0时刻的安全性：安全的。安全的进程推进序列：P1->P3->P4->P2->P0图3-17

T0时刻的安全序列

c．银行家算法

当Pi发出资源请求后,如:Requesti[j]=K，表示进程Pi需要K个Rj类型的资源，系统按下述步骤进行：

(1)检查两前提

①如果Requesti[j]≤Need[i,j]

申请≤需要

②如果Requesti[j]≤Available[j]

申请≤可用

(2)系统试探分配资源给进程Pi，修改下面数据结构中的数值：Available[j]:=Available[j]-Requesti[j]；Allocation[i,j]:=Allocation[i,j]+Requesti[j]；Need[i,j]:=Need[i,j]-Requesti[j]；

(3)系统执行安全性算法。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。5）银行家算法之例假定系统中有五个进程{P0，P1，P2，P3，P4}和三类资源{A，B，C}，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图所示。

图3-16T0时刻的资源分配表(1)T0时刻的安全性：安全的图3-17

T0时刻的安全序列

(2) P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查：①Request1(1，0，2)≤Need1(1，2，2)②Request1(1，0，2)≤Available1(3，3，2)③

系统先试为P1分配资源，并修改Available，Allocation1和Need1向量，形成新状态。

两前提修改后④再利用安全性算法检查此时系统是否安全。图3-17P1申请资源时的安全性检查结论：找到了一个安全序列，系统是安全的，可以为P1分配资源(3) P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查：①Request4(3，3，0)≤Need4(4，3，1)；②Request4(3，3，0)≤Available(2，3，0)，让P4等待。图：已分配了P1的资源分配表优点：能时刻保证系统处于安全状态。缺点：需要不断进行测试，需花费较多时间。借助银行家算法预测系统的安全性：例如，某系统有同类资源m个，可并发执行且共享该类资源的进程最多n个，而每个进程申请该类资源的最大量为x（1≤x≤m），只要不等式n（x-1）+1≤m成立，则系统一定不会发生死锁。

例题:某系统中有11台打印机，N个进程共享打印机资源，每个进程要求3台。但N的取值不超过(

)时，系统不会发生死锁。A．4B．5C．6 D．73.死锁的检测和解除

当系统为进程分配资源时，若未采取任何限制性措施来保证不进入死锁状态，则系统必须提供检测和解除死锁的手段。

系统做到：

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

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

发现死锁是根据死锁状态的定义，利用死锁描述中介绍的资源分配图来考察某一时刻系统状态是否合理，即是否能使所有进程都得到它们所申请的资源而运行结束。

解除死锁：与检测死锁相配套的一种措施。

方法：剥夺资源、撤消进程；死锁的检测和解除措施有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。一、调度的类型和层次1.调度层次

1）作业调度（高级调度）：批处理系统、运行频率低。

2）中级调度（交换调度）：解决内存紧张。

3）进程调度（低级调度）：OS中必须配置、运行频率高。2、作业控制块—JCB：控制和管理作业运行。作业的5个状态：“提交”、“后备”、“活动”、“完成”、“退出”。3、进程调度功能：

1)保存处理机的现场信息。

2)按某种算法选取进程。

3)把处理器分配给进程。由分派程序(Dispatcher)把处理器分配给进程。从选中的进程PCB中恢复处理机现场。时机：

1）进程运行结束；

2）执行中的进程发生某个等待事件；

3）分时系统时间片到；

4）在采用可抢占调度方式的系统中，当具有更高优先级的进程要求使用处理机。总结：

进程调度方式：

1）非抢先调度方式

2）可抢先调度方式4、调度队列模型

1、2、3种。5、调度总则面向用户：

1）周转时间短。评价批处理系统。

2）响应时间快。评价分时系统。

3）截止时间的保证。评价实时系统。

4）优先权准则。都可遵循。面向系统：

1）系统吞吐量高。

2）处理机利用率好。

3）各类资源的平衡利用。二、调度算法（重点）1.先来先服务调度算法(FCFS)：

适用：进程调度、作业调度，有利于长作业。2.短作业(进程)优先调度算法（SJ(P)F）适用：短作业，但会有“饿死”现象。3.高优先权优先调度算法（HPF）

适用：作业调度、进程调