4.3 最早截止时间优先EDF算法
该算法是根据任务的截止时间确定任务的优先级，任务的截止时间愈早，其优先级愈高，具有最早截止时间的任务排在队列的队首。调度程序在选择任务时，总是选择就绪队列中的第一个任务，为之分配处理机。最早截止时间优先算法既可用于抢占式调度方式中，也可用于非抢占式调度方式中。
1非抢占式调度方式用于非周期实时任务
2抢占式调度方式用于周期实时任务
4.4 最低松弛度优先LLF(Least Laxity First)算法
该算法在确定任务的优先级时，根据的是任务的紧急（或松弛）程度。任务紧急程度愈高，赋予该任务的优先级就愈高，以使之优先执行。如一任务在400ms时必须完成，它本身需要运行150ms，则其松弛程度为250ms。在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在最前面，调度程序选择队列中的队首任务执行。
该算法主要用于可抢占调度方式中。假如在一个实时系统中有两个周期性实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms，任务B要求每50ms执行一次，执行时间为25ms。由此可见，任务A和B每次必须完成的时间分别为A1、A2、A3、···和B1、B2、B3、···，如下图。为保证不遗漏任何一次截止时间，应采用最低松弛度优先的抢占调度策略。
在刚开始是(t1=0)，A1必须在20ms时完成，而它本身运行又需10ms，可算出A1的松弛度为10ms。B1必须在50ms时完成，而它本身运行就需25ms，可算出B1的松弛度为25ms，故调度程序应先调度A1执行。在t2=10ms时，A2的松弛度可按下式算出：
A2的松弛度=必须完成时间-其本身的运行时间-当前时间
= 40ms - 10ms - 10ms = 20ms
类似地，可算出B1的松弛度为15ms，故调度程序应选择B1运行。在t3=30ms时，A2的松弛度已减为0(即40-10-30)，而B1的松弛度为15ms(即50-5-30)，于是调度程序应抢占B1的处理机而调度A2运行。在t4=40ms时，A3的松弛度为10ms，而B1的松弛度为5ms，故又重新调度B1执行。在t5=45ms时，B1执行完成，而此时A3的松弛度为5ms，而B2的松弛度为30ms，于是又调度A3执行。在t6=55ms时，任务A尚未进入第4周期，而任务B已进入第2周期，故再调度B2执行。在t7=70ms时，A4的松弛度为0ms，而B2的松弛度为20ms，故此时调度程序又应抢占B2的处理机而调度A4执行。下图示出了具有两个周期性实时任务的调度情况。
4.5 优先级倒置(priority inversion problem)
1优先级倒置的形成
当前OS广泛采用优先级调度算法和抢占方式，然而在系统中存在着影响进程运行的资源而可能产生“优先级倒置”的现象，即高优先级进程（或线程）被低优先级进程（或线程）延迟或阻塞。举个例子，假如有三个完全独立的进程P1、P2和P3，P1的优先级最高，P2次之，P3最低。P1和P3通过共享的一个临界资源进行交互。
假如P3最先执行，在执行了P(mutex)操作后，进入到临界区CS-3。在时刻a，P2就绪，因为它比P3的优先级高，P2抢占了P3的处理机而运行。在时刻b，P1就绪，因为它又比P2的优先级高，P1抢占了P2的处理机而运行。在时刻c，P1执行P(mutex)操作，视图进入临界区CS-1，但因为相应的临界资源已被P3占用，故P1将被阻塞。有P2继续运行，直到时刻d运行结束。然后由P3接着运行，到时刻e时P3退出临界区，并唤醒P1。因为它比P3的优先级高，故它抢占了P3的处理机而运行。
根据优先级原则，高优先级进程应当能优先执行，但在此例中，P1和P3共享着“临界资源”，而出现了不合常理的现象，高优先级进程P1因P3进程被阻塞了，又因为P2进程的存在而延长了P1被阻塞的时间，而且被延长的时间是不可预知和无法限定的。由此所产生的“优先级倒置”的现象是非常有害的，它不应该出现在实时系统中。
2优先级倒置的解决方法
一种简单的解决方法是规定：假如进程P3在进入临界区后P3所占用的处理机就不允许被抢占。由上图可以看出，P2即使优先级高于P3也不能执行。于是P3就有可能会较快地退出临界区，不会出现上述情况。如果系统中的临界资源都较短且不多，该方法是可行的。反之，如果P3临界区非常长，则高优先级进程P1仍会等待很长时间，其效果是无法令人满意的。
一个比较实用的方法是建立在动态优先级继承基础上的。该方法规定，当高优先级进程P1要进入临界区，去使用临界资源R，如果已有一个低优先级进程P3正在使用该资源，此时一方面P1被阻塞，另一方面由P3继承P1的优先级，并一直保持到P3退出临界区。这样做的目的在于不让比P3优先级稍高，但比P1优先级低的进程如P2进程插进来。导致延缓P3退出临界区。如下图示出了采用动态优先级继承方法后，P1、P2、P3三个进程的运行情况。
5.死锁概述
5.1 资源问题
在系统中有许多不同类型的资源，其中可以引起死锁的主要是需要采用互斥访问方法的、不可以被抢占的资源，即在前面介绍的临界资源。系统中这类资源有很多，如打印机、数据文件、队列、信号量等。
1可重用性资源和消耗性资源
(1) 可重用性资源
(2) 可消耗性资源
2可抢占性资源和不可抢占性资源
(1) 可抢占性资源
(2) 不可抢占性资源
5.2 计算机系统中的死锁
死锁的起因，通常是源于多个进程对资源的争夺，不仅对不可抢占资源进行争夺时会引起死锁，而且对可消耗资源进行争夺时，也会引起死锁。
1竞争不可抢占性资源引起死锁
通常系统中所拥有的不可抢占性资源其数量不足以满足多个进程运行的需要，使得进程在运行过程中，会因争夺资源而陷入僵局。例如，系统中有两个进程P1和P2，它们都准备写两个文件F1和F2，而这两者都属于可重用和不可抢占性资源。此时如果在P1打开F1的同时，P2去打开F2，每个进程都占有一个打开的文件，此时就出现死锁问题。
2竞争可消耗资源引起死锁
如下图，P1一方面产生消息m1发给P2，另一方面接收P3发的m3；P2一方面产生消息发给P3，另一方面接收P1发的m1；P3一方面产生消息发给P1，另一方面接收P2发的m2。
如果三个进程按下列顺序进行：
则可以正常运行下去，但如果按下面这种顺序执行：
则这三个进程就永远阻塞在它们的receive操作上，等待一条永远不会发出的消息，于是发生了死锁。
3进程推进顺序不当引起死锁
(1) 进程推进顺序合法
(2) 进程推进顺序非法
5.3 死锁的定义、必要条件和处理方法
1死锁的定义
如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程就是死锁的(Deadlock)。
2产生死锁的必要条件
(1) 互斥条件
(2) 请求和保持条件
(3) 不可抢占条件
(4) 循环等待条件
3处理死锁的方法
(1) 预防死锁
(2) 避免死锁
(3) 检测死锁
(4) 解除死锁
6.预防死锁
6.1 破坏“请求和保持”条件
为了能破坏“请求和保持”条件，系统必须保证做到：当一个进程在请求资源时，它不能持有不可抢占资源。该保证可通过如下两个不同的协议实现：
1第一种协议
该协议规定，所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。
2第二种协议
该协议是对第一种协议的改进，它运行一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的、且已用毕的全部资源，然后再请求新的所需资源。
6.2 破坏“不可抢占”条件
为了能破坏“不可抢占”条件，协议中规定，当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。
6.3 破坏“循环等待”条件
一个能保证“循环等待”条件不成立的方法是，对系统所有资源类型进行线性排序，并赋予不同的序号。在对系统所有资源类型进行线性排序后，便可采用这样的预防协议：规定每个进程必须按序号递增的顺序请求资源。
7.避免死锁
7.1 系统安全状态
在死锁避免方法中，把系统的状态分为安全状态和不安全状态。当系统处于安全状态时，可避免发生死锁。反之，当系统处于不安全状态时，则可能进入到死锁状态。
1安全状态
在该方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，才可将资源分配给进程，否则，令进程等待。
2由安全状态向不安全状态的转换
如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。
在建立了系统安全状态的概念后便可知道避免死锁的基本思想，就是确保系统始终处于安全状态。一个系统开始是处于安全状态的，当有进程请求一个可用资源时，系统需对该进程的请求进行计算，若将资源分配给进程后系统仍处于安全状态，才将该资源分配给进程。
7.2 利用银行家算法避免死锁
1银行家算法中的数据结构
为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。
(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]
2银行家算法
设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：
(1) 如果Requesti[j]≤Need[i,j]，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
(2) 如果Requesti[j]≤Available[j]，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。
(3) 系统试探着把资源分配给进程Pi，并修改数据结构中的数值。
(4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
3安全性算法
系统所执行的安全性算法可描述如下：
(1) 设置两个向量：①工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available；②Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=false；当有足够资源分配给进程时，再令Finish[i]=true。
(2) 从进程集合中找到一个能满足下述条件的进程：
①Finish[i]=false;
②Need[i,j]≤Work[j];
若找到，执行步骤(3)，否则，执行步骤(4)。
(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
Work[j] = Work[j] + Allocation[i,j];
Finish[i] = true;
go to step 2;
(4) 如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。
8.1 死锁的检测
为了能对系统中是否已发生了死锁进行检测，在系统中必须：①保存有关资源的请求和分配信息；②提供一种算法，它利用这些信息来检测系统是否已进入死锁状态。
1资源分配图(Resource Allocation Gragh)
系统死锁，可利用资源分配图来描述。该图是由一组结点和一组边E所组成的一个对偶G=(N, E)。
图中，P1进程已经分得了两个R1资源，并又请求一个R2资源；P2进程分得一个R1和一个R2资源，并又请求R1资源。
2死锁定理
我们可以利用把资源分配图加以简化的方法，来检测当系统处于S状态时，是否为死锁状态。简化方法如下：
(1) 在资源分配图中，找出一个既不阻塞又非独立的进程结点Pi。在顺利的情况下，Pi可获得所需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去Pi的请求边和分配边，使之成为孤立的结点。如下图(a)中，将P1的两个分配边和一个请求边消去，边形成图(b)所示的情况。
(2) P1释放资源后，便可使P2获得资源而继续运行，直至p2完成后又释放出它所占有的全部资源，形成图©所示的情况，即将P2的两条分配和一条请求边消去。
(3) 在进行一系列的简化后，若能消去图中所有的边，使所有的进程结点都称为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。
S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。
3死锁检测中的数据结构
死锁检测中的数据结构类似于银行家算法中的数据结构：
(1) 可利用资源向量Available，它表示了m类资源中每一类资源的可用数目。
(2) 把不占用资源的进程(向量Allocation=0)记入L表中。
(3) 从进程集合中找到一个Requesti≤Work的进程做如下处理：①将其资源分配图简化，释放出资源，增加工作向量Work=Work+Allocationi。②将它记入L表中。
(4) 若不能把所有进程都记入L表中，便表明系统状态S的资源分配图是不可完全简化的。因此，该系统状态将发生死锁。
Work=Available;
L={Li|Allocationi=0⋂Requesti=0}
for(all Li∉ L) {
for (all Requesti≤Work) {
Work=Work+Allocationi;
Li⋃L;
}
}
deadlock=(L={P1, P2，···，Pn});
8.2 死锁的解除
常用的解除死锁的两种方法是：
(1) 抢占资源。从一个或多个进程中抢占足够数量的资源，分配给死锁进程，以接触死锁。
(2) 终止(或撤销)进程。终止(或撤销)系统中的一个或多个死锁进程，直至打破循环环路，使系统从死锁状态解脱出来。
1终止进程的方法
(1) 终止所有死锁进程
(2) 逐个终止进程
2付出代价最小的死锁解除算法
一个比较有效的方法是对死锁状态S做如下处理：从死锁状态S中先终止一个死锁进程P1，使系统状态由S演变成U1，将P1记入被终止进程的集合d(T)中，并把所付出的代价C1加入到Rc(T)中；对死锁进程P2、P3等重复上述过程，得到状态U1，U2，···，Ui，Un后，再按终止进程时所花费代价的大小，把它插入到由S状态所演变的新状态的队列L中。显然，队列L中的第一个状态U1是由S状态花最小代价终止一个进程所演变成的状态。在终止一个进程后，若系统仍处于死锁状态，则再从U1状态按照上述处理方式再依次地终止一个进程。这样，为把系统从死锁状态中解脱出来，所花费的代价可表示为：R(S)min = min{Cui} + min{Cuj} + min{Cuk} + ··· 。
————————————————
