======第三章处理机调度与死锁======（1）https://developer.aliyun.com/article/1415761
3.3.2 高优先权优先调度算法
- 优先权调度算法的类型
为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权优先(FPF) 调度算法。此算法常被用于批处理系统中，作为作业调度算法，也作为多种操作系统中的 进程调度算法，还可用于实时系统中。当把该算法用于作业调度时，系统将从后备队列中 选择若干个优先权最高的作业装入内存。当用于进程调度时，该算法是把处理机分配给就 绪队列中优先权最高的进程，这时，又可进一步把该算法分成如下两种。
1)非抢占式优先权算法
在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便 一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机 重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些 对实时性要求不严的实时系统中。
2)抢占式优先权调度算法
在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原 优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。这种抢占式的优先权调度算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求 较高的批处理和分时系统中。
优先权类型
1)静态优先权
静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，有的系统用“0”表示最高优先权，当数值愈大时， 其优先权愈低；而有的系统恰恰相反。
确定进程优先权的依据有如下三个方面：
(1) 进程类型。通常，系统进程(如接收进程、对换进程、磁盘 I/O 进程)的优先权高于 一般用户进程的优先权。
(2) 进程对资源的需求。如进程的估计执行时间及内存需要量的多少，对这些要求少的进程应赋予较高的优先权。
(3) 用户要求。这是由用户进程的紧迫程度及用户所付费用的多少来确定优先权的。 静态优先权法简单易行，系统开销小，但不够精确，很可能出现优先权低的作业(进程) 长期没有被调度的情况。因此，仅在要求不高的系统中才使用静态优先权。
2)动态优先权
动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间 的增加而改变的，以便获得更好的调度性能。若所有的就绪进程具有各不相同的优先权初值，那么，对于优先权初值低的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获得处理机。当采用抢 占式优先权调度算法时，如果再规定当前进程的优先权以速率 b 下降，则可防止一个长作 业长期地垄断处理机。
高响应比优先调度算法
在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先 级随着等待时间的增加而以速率 a 提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先权的变化规律可描述为：
由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先权又相当于响 应比 RP 。据此，又可表示为：
由上式可以看出：
(1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。
(2) 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。
(3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时， 其优先级便可升到很高，从而也可获得处理机。 简言之，该算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期 得不到服务。因此，该算法实现了一种较好的折衷。当然，在利用该算法时，每要进行调度之前，都须先做响应比的计算，这会增加系统开销
3.3.3 基于时间片的轮转调度算法
- 时间片轮转法
1)基本原理
在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则排成一个队列， 每次调度时，把 CPU 分配给队首进程，并令其执行一个时间片。时间片的大小从几 ms 到几百 ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号 来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一 给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应 所有用户的请求。
2)时间片大小的确定
在时间片轮转算法中，时间片的大小对系统性能有很大的影响，如选择很小的时间片将有利于短作业，因为它能较快地完成，但会频繁地发生中断、进程上下文的切换，从而 增加系统的开销；反之，如选择太长的时间片，使得每个进程都能在一个时间片内完成， 时间片轮转算法便退化为 FCFS 算法，无法满足交互式用户的需求。
一个较为可取的大小是， 时间片略大于一次典型的交互所需要的时间。这样可使大多数进程在一个时间片内完成。
图 3-5 示出了时间片分别为 q=1 和 q=4 时，A、B、C、D、E 五个进程的运行情况，而 图 3-6为 q=1和 q=4时各进程的平均周转时间和带权平均周转时间。图中的 RR(Round Robin) 表示轮转调度算法。
多级反馈队列调度算法
前面介绍的各种用作进程调度的算法都有一定的局限性。如短进程优先的调度算法， 仅照顾了短进程而忽略了长进程，而且如果并未指明进程的长度，则短进程优先和基于进程 长度的抢占式调度算法都将无法使用。而多级反馈队列调度算法则不必事先知道各种进程所 需的执行时间，而且还可以满足各种类型进程的需要，因而它是目前被公认的一种较好的进 程调度算法。在采用多级反馈队列调度算法的系统中，调度算法的实施过程如下所述。
(1) 应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高， 第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片 的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例 如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第 i+1 个队列的时间片要 比第 i 个队列的时间片长一倍。图 3-7 是多级反馈队列算法的示意。
(2) 当一个新进程进入内存后，首先将它放入第一队列的末尾，按 FCFS 原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一 个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按 FCFS 原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第 三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第 n 队列后，在第 n 队列中便采取按时间片轮转的方式运行。
(3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第 1～(i-1)队列均空时，才会调度第 i 队列中的进程运行。如果处理机正在第 i 队列中为某进程服务时， 又有新进程进入优先权较高的队列(第 1～(i-1)中的任何一个队列)，则此时新进程将抢占正 在运行进程的处理机，即由调度程序把正在运行的进程放回到第 i 队列的末尾，把处理机分配给新到的高优先权进程。
多级反馈队列调度算法的性能
多级反馈队列调度算法具有较好的性能，能很好地满足各种类型用户的需要。
(1) 终端型作业用户。由于终端型作业用户所提交的作业大多属于交互型作业，作业通常较小，系统只要能使这些作业(进程)在第一队列所规定的时间片内完成，便可使终端型作 业用户都感到满意。
(2) 短批处理作业用户。对于很短的批处理型作业，开始时像终端型作业一样，如果仅在第一队列中执行一个时间片即可完成，便可获得与终端型作业一样的响应时间。对于稍长的作业，通常也只需在第二队列和第三队列各执行一个时间片即可完成，其周转时间仍然较短。
(3) 长批处理作业用户。对于长作业，它将依次在第 1，2，…，n 个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理。
3.4 实时调度
由于在实时系统中都存在着若干个实时进程或任务，它们用来反应或控制某个(些)外部 事件，往往带有某种程度的紧迫性，因而对实时系统中的调度提出了某些特殊要求。前面所介绍的多种调度算法并不能很好地满足实时系统对调度的要求，为此，需要引入一种新的调度，即实时调度。
3.4.1 实现实时调度的基本条件
- 提供必要的信息
为了实现实时调度，系统应向调度程序提供有关任务的下述一些信息：
(1) 就绪时间。这是该任务成为就绪状态的起始时间，在周期任务的情况下，它就是事 先预知的一串时间序列；而在非周期任务的情况下，它也可能是预知的。
(2) 开始截止时间和完成截止时间。对于典型的实时应用，只须知道开始截止时间，或 者知道完成截止时间。
(3) 处理时间。这是指一个任务从开始执行直至完成所需的时间。在某些情况下，该时间也是系统提供的。
(4) 资源要求。这是指任务执行时所需的一组资源。
(5) 优先级。如果某任务的开始截止时间已经错过，就会引起故障，则应为该任务赋予 “绝对”优先级；如果开始截止时间的推迟对任务的继续运行无重大影响，则可为该任务 赋予“相对”优先级，供调度程序参考。
系统处理能力强
在实时系统中，通常都有着多个实时任务。若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。假 定系统中有 m 个周期性的硬实时任务，它们的处理时间可表示为 Ci ，周期时间表示为 Pi ， 则在单处理机情况下，必须满足下面的限制条件：
系统才是可调度的。假如系统中有 6 个硬实时任务，它们的周期时间都是 50 ms，而每次的处理时间为 10 ms，则不难算出，此时是不能满足上式的，因而系统是不可调度的。 解决的方法是提高系统的处理能力，其途径有二：其一仍是采用单处理机系统，但须 增强其处理能力，以显著地减少对每一个任务的处理时间；其二是采用多处理机系统。假 定系统中的处理机数为 N，则应将上述的限制条件改为：
上述的限制条件并未考虑到任务的切换时间，包括执行调度算法和进行任务切换，以及消息的传递时间等开销，因此，当利用上述限制条件来确定系统是否可调度时，还应适当地留有余地。
- 采用抢占式调度机制
在含有硬实时任务的实时系统中，广泛采用抢占机制。当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时 任务对截止时间的要求。但这种调度机制比较复杂。
对于一些小型实时系统，如果能预知任务的开始截止时间，则对实时任务的调度可采用非抢占调度机制，以简化调度程序和对任务调度时所花费的系统开销。但在设计这种调 度机制时，应使所有的实时任务都比较小，并在执行完关键性程序和临界区后，能及时地将自己阻塞起来， 以便释放出处理机， 供调度程序去调度那种开始截止时间即将到达的任务。
具有快速切换机制
为保证要求较高的硬实时任务能及时运行，在实时系统中还应具有快速切换机制，以 保证能进行任务的快速切换。该机制应具有如下两方面的能力：
(1) 对外部中断的快速响应能力。为使在紧迫的外部事件请求中断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机(其它 紧迫任务)。
(2) 快速的任务分派能力。在完成任务调度后，便应进行任务切换。为了提高分派程序 进行任务切换时的速度，应使系统中的每个运行功能单位适当地小，以减少任务切换的时 间开销。
3.4.2 实时调度算法的分类
- 非抢占式调度算法
1) 非抢占式轮转调度算法
该算法常用于工业生产的群控系统中，由一台计算机控制若干个相同的(或类似的)对象，为每一个被控对象建立一个实时任务，并将它们排成一个轮转队列。调度程序每次选择队列中的第一个任务投入运行。当该任务完成后，便把它挂在轮转队列的末尾，等待下次调度运行，而调度程序再选择下一个(队首)任务运行。这种调度算法可获得数秒至数十秒的响应时间，可用于要求不太严格的实时控制系统中。
2) 非抢占式优先调度算法
如果在实时系统中存在着要求较为严格(响应时间为数百毫秒)的任务，则可采用非抢占式优先调度算法为这些任务赋予较高的优先级。当这些实时任务到达时，把它们安排在就 绪队列的队首，等待当前任务自我终止或运行完成后才能被调度执行。这种调度算法在做了精心的处理后，有可能获得仅为数秒至数百毫秒级的响应时间，因而可用于有一定要求的实时控制系统中。
抢占式调度算法
1) 基于时钟中断的抢占式优先权调度算法
在某实时任务到达后，如果该任务的优先级高于当前任务的优先级，这时并不立即抢 占当前任务的处理机，而是等到时钟中断到来时，调度程序才剥夺当前任务的执行，将处 理机分配给新到的高优先权任务。这种调度算法能获得较好的响应效果，其调度延迟可降 为几十毫秒至几毫秒。因此，此算法可用于大多数的实时系统中。
2) 立即抢占的优先权调度算法
在这种调度策略中，要求操作系统具有快速响应外部事件中断的能力。一旦出现外部中断，只要当前任务未处于临界区，便立即剥夺当前任务的执行，把处理机分配给请求中 断的紧迫任务。这种算法能获得非常快的响应，可把调度延迟降低到几毫秒至 100 微秒， 甚至更低。
图 3-8 中的(a)、(b)、©、(d)分别示出了采用非抢占式轮转调度算法、非抢占式优先权 调度算法、基于时钟中断抢占的优先权调度算法和立即抢占的优先权调度算法四种情况的 调度时间。
======第三章处理机调度与死锁======（3）https://developer.aliyun.com/article/1415810?spm=a2c6h.13148508.setting.31.188b4f0evtcvhF
