======第三章处理机调度与死锁======（2）：https://developer.aliyun.com/article/1415803
3.4.3 常用的集中实时调度算法
最早截止时间优先即 **EDF ** 算法
该算法是根据任务的开始截止时间来确定任务的优先级。截止时间愈早，其优先级愈高。该算法要求在系统中保持一个实时任务就绪队列，该队列按各任务截止时间的早晚排 序；当然，具有最早截止时间的任务排在队列的最前面。调度程序在选择任务时，总是选择就绪队列中的第一个任务，为之分配处理机，使之投入运行。最早截止时间优先算法既可用于抢占式调度，也可用于非抢占式调度方式中。
1) 非抢占式调度方式用于非周期实时任务
图 3-9 示出了将该算法用于非抢占调度方式之例。
该例中具有四个非周期任务，它们先后到达。系统首先调度任务 1 执行，在任务 1 执行期间，任务 2、3 又先后到达。由于任务 3 的开始截止时间早于任务 2，故系统在任务 1 后将调度任务 3 执行。在此期间又到达作业 4，其开始截止时间仍是早于任务 2 的，故在任务 3 执行完后，系统又调度任务 4 执行，最后才调度任务 2 执行。
2) 抢占式调度方式用于周期实时任务 图 3-10 示出了将最早截止时间优先算法用于抢占调度方式之例。在该例中有两个周期性任务，任务 A 的周期时间为 20 ms，每个周期的处理时间为 10 ms；任务 B 的周期时间为 50 ms，每个周期的处理时间为 25 ms。
图中的第一行示出了两个任务的到达时间、最后期限和执行时间图。其中任务 A 的到达时间为 0、20、40、…；任务 A 的最后期限为 20、40、 60、…；任务 B 的到达时间为 0、50、100、…；任务 B 的最后期限为 50、100、150、…(注： 单位皆为 ms)。
为了说明通常的优先级调度不能适用于实时系统，该图特增加了第二和第三行。在第 二行中假定任务 A 具有较高的优先级，所以在 t = 0 ms 时，先调度 A1 执行，在 A1 完成后 (t = 10 ms)才调度 B1 执行；在 t = 20 ms 时，调度 A2 执行；在 t = 30 ms 时，A2 完成，又调 度 B1 执行；在 t = 40 ms 时，调度 A3 执行；在 t = 50 ms 时，虽然 A3 已完成，但 B1 已错过了它的最后期限，这说明了利用通常的优先级调度已经失败。第三行与第二行类似，只 是假定任务 B 具有较高的优先级。
第四行是采用最早截止时间优先算法的时间图。在 t = 0 时，A1 和 B1 同时到达，由于 A1 的截止时间比 B1 早，故调度 A1 执行；在 t = 10 时，A1 完成，又调度 B1 执行；在 t = 20 时，A2 到达，由于 A2 的截止时间比 B2 早，B1 被中断而调度 A2 执行；在 t = 30 时，A2 完成，又重新调度 B1 执行；在 t = 40 时，A3 又到达，但 B1 的截止时间要比 A3 早，仍应 让 B1 继续执行直到完成(t = 45)，然后再调度 A3 执行；在 t = 55 时，A3 完成，又调度 B2 执行。在该例中利用最早截止时间优先算法可以满足系统的要求。
最低松弛度优先即LLF算法
该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高， 为该任务所赋予的优先级就愈高，以使之优先执行。例如，一个任务在 200 ms 时必须完成， 而它本身所需的运行时间就有 100 ms，因此，调度程序必须在 100 ms 之前调度执行，该任 务的紧急程度(松弛程度)为 100 ms。又如，另一任务在 400 ms 时必须完成，它本身需要运 行 150 ms，则其松弛程度为 250 ms。在实现该算法时要求系统中有一个按松弛度排序的实 时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队 首任务执行。
该算法主要用于可抢占调度方式中。假如在一个实时系统中，有两个周期性实时任务 A 和 B，任务 A 要求每 20 ms 执行一次，执行时间为 10 ms；任务 B 只要求每 50 ms 执行一 次，执行时间为 25 ms。由此可得知任务 A 和 B 每次必须完成的时间分别为：A1 、A2 、A3 、… 和 B1 、B2 、B3 、…，见图 3-11。为保证不遗漏任何一次截止时间，应采用最低松弛度优先 的抢占调度策略。
在刚开始时(t 1 = 0)，A 1 必须在 20 ms 时完成，而它本身运行又需 10 ms，可算出 A 1 的 松弛度为 10 ms；B 1 必须在 50 ms 时完成，而它本身运行就需 25 ms，可算出 B 1 的松弛度 为 25 ms，故调度程序应先调度 A 1 执行。在 t 2 = 10 ms 时，A 2 的松弛度可按下式算出：
A 2 的松弛度 = 必须完成时间 - 其本身的运行时间 - 当前时间 = 40 ms-10 ms-10 ms = 20 ms
类似地，可算出 B 1 的松弛度为 15 ms，故调度程序应选择 B 2 运行。在 t 3 = 30 ms 时， A 2 的松弛度已减为 0(即 40 - 10 - 30)，而 B 1 的松弛度为 15 ms(即 50 - 5 - 30)，于是调度程 序应抢占 B 1 的处理机而调度 A 2 运行。在 t 4 = 40 ms 时，A 3 的松弛度为 10 ms(即 60 - 10 - 40)， 而 B 1 的松弛度仅为 5 ms(即 50 - 5 - 40)，故又应重新调度 B 1 执行。在 t 5 = 45 ms 时，B1 执行完成，而此时 A 3 的松弛度已减为 5 ms(即 60 - 10 - 45)，而 B 2 的松弛度为 30 ms (即 100 - 25 - 45)，于是又应调度 A 3 执行。在 t 6 = 55 ms 时，任务 A 尚未进入第 4 周期，而任务 B 已进入第 2 周期，故再调度 B 2 执行。在 t 7 = 70 ms 时，A 4 的松弛度已减至 0 ms (即 80 - 10 - 70)，而 B 2 的松弛度为 20 ms(即 100 - 10 - 70)，故此时调度又应抢占 B 2 的处 理机而调度 A4 执行。图 3-12 示出了具有两个周期性实时任务的调度情况。
3.5 产生死锁的原因和必要条件
3.5.1 产生死锁的原因
(1) 竞争资源。当系统中供多个进程共享的资源如打印机、公用队列等，其数目不足以 满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。
(2) 进程间推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，也同样会 导致产生进程死锁。
竞争资源引起进程死锁
1) 可剥夺和非剥夺性资源
可把系统中的资源分成两类，一类是可剥夺性资源，是指某进程在获得这类资源后， 该资源可以再被其他进程或系统剥夺。甚至可将一个进程从内存调出到外存上。可见，CPU 和主存均属于可剥夺性资源。另一类资源是不可剥夺性资源，当系统把这类资源分配给某 进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等。
2) 竞争非剥夺性资源
在系统中所配置的非剥夺性资源，由于它们的数量不能满足诸进程运行的需要，会使进程在运行过程中，因争夺这些资源而陷入僵局。
例如，系统中只有一台打印机 R 1 和一台 磁带机 R2 ，可供进程 P 1 和 P 2 共享。假定 P 1 已占用了打印机 R1 ，P 2 已占用了磁带机 R2 。此 时，若 P 2 继续要求打印机，P 2 将阻塞；P 1 若又要求磁带机，P 1 也将阻塞。于是，在 P 1 与P 2 之间便形成了僵局，两个进程都在等待对方释 放出自己所需的资源。但它们又都因不能继续获 得自己所需的资源而不能继续推进，从而也不能 释放出自己已占有的资源，以致进入死锁状态。
为便于说明，我们用方块代表资源，用圆圈代表进程，见图 3-13 所示。当箭头从进程指向资源 时，表示进程请求资源；当箭头从资源指向进程 时，表示该资源已被分配给该进程。从中可以看出，这时在 P1 、P 2 及 R 1 和 R 2 之间已经形成了一 个环路，说明已进入死锁状态。
3) 竞争临时性资源
上述的打印机资源属于可顺序重复使用型资源，称为永久性资源。还有一种是所谓的临时性资源，这是指由一个进程产生，被另一进程使用一短暂时间后便无用的资源，故也 称之为消耗性资源，它也可能引起死锁。
图 3-14 示出了在进程之间通信时形成死锁的情况。 图中 S1 、S 2 和 S 3 是临时性资源。进程 P 1 产生消息 S1 ，又要求从 P 3 接收消息 S3 ；进程 P3 产生消息 S3 ，又要求从进程 P 2 接收其所产生的消 息 S2 ；进程 P 2 产生消息 S2 ，又需要接收进程 P 1 P1 所产生的消息 S1 。如果消息通信按下述顺序进行：
P1 ： …Release(S1 )； Reqaest(S3 )； … P2 ： …Release(S2 )； Request(S1 )； … P3 ： …Release(S3 )； Request(S2 )； … 并不可能发生死锁，但若改成下述的运行顺序： P1 ： …Request(S3 )； Release(S1 )； … P2 ： …Request(S1 )； Release(S2 )； … P3 ： …Request(S2 )； Release(S3 )； … 则可能发生死锁。
- 进程推进顺序不当引起死锁
1) 进程推进顺序合法
在进程 P 1 和 P 2 并发执行时，如果按下述顺序推进： P1 ：Request(R1 )；Request(R2 )； P1 ：Releast(R1 )；Release(R2 )； P2 ：Request(R2 )；Request(R1 )； P2 ：Release(R2 )；Release(R1 )； 两个进程便可顺利完成。
图 3-15 中的曲线①示出了这一情况。类似地，若按曲线②和 ③所示的顺序推进，两进程也可顺利完成。我们称这种不会引起进程死锁的推进顺序是合 法的。
2) 进程推进顺序非法若并发进程 P 1 和 P 2 按曲线④所示的顺序推进，它们将进入不安全区 D 内。此时 P 1 保 持了资源 R1 ，P 2 保持了资源 R2 ，系统处于不安全状态。因为这时两进程再向前推进，便可 能发生死锁。例如，当 P 1 运行到 P1 ：Request(R2 )时，将因 R 2 已被 P 2 占用而阻塞；当 P 2 运 行到 P2 ：Request(R1 )时，也将因 R 1 已被 P 1 占用而阻塞，于是发生了进程死锁。
======第三章处理机调度与死锁======（4）https://developer.aliyun.com/article/1415846?spm=a2c6h.13148508.setting.30.188b4f0evtcvhF
