一、处理机调度的层次
低级调度(Low Level Scheduling)，低级调度的对象 是就绪队列中的进程。因此低级调度就是进程调度。
处理机调度：
- 非抢占方式（Non-Preemptive Mode）
- 抢占方式（Preemptive Mode）
非抢占方式（Non-Preemptive Mode）
- 一旦获得CPU，一直运行到进程结束为止，不会中断。
- 在采用非抢占调度方式时，可能引起进程调度的因素可归结为这样几个：
① 正在执行的进程执行完毕， 或因发生某事件而不能再继续执行；
② 执行中的进程因提出I/O请求而暂停执行；
③ 在进程通信或同步过程中执行了某种原语操作，如P操 作 (wait操作)、block原语、wakeup原语等。 - 这种调度方式的优点是实现简单、系统开销小，但它难以满足紧急任务的要求——不适合实时系统中。
抢占方式（Preemptive Mode）
抢占原则：
- 优先权原则
- 短进程优先原则
- 时间片原则
二、调度模型和准则
三、调度算法
- 作业调度算法
- 进程调度算法
作业调度算法
- 先来先服务算法（FCFS）
- 短作业优先算法（SJF）
- 优先级调度算法 (PSA)
- 高相应比优先调度算法 (HRRN)
1.先来先服务（FCFS）
2. 短作业优先（SJF）
短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。
缺点：
- 需要预估作业时间
- 对长作业不利
- 无法实现人机交互
- 完全未考虑作业紧迫程度
3. 优先级调度（priority-scheduling algorithm, PSA）
- 非抢占式优先权算法
- 抢占式优先权算法
非抢占式优先权算法
在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法可用于某些对实时性要求不严的实时系统中。
抢占式优先权算法
在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。
显然，这种抢占式的优先权调度算法，能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中， 以及对性能要求较高的批处理和分时系统中。
优先权类型
静态优先权：
动态优先权
静态优先权
静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，例如，07或0255中的某一整数， 又把该整数称为优先数。
只是具体用法各异：有的系统用“0”表示最高优先权，当数值愈大时，其优先权愈低；而有的系统恰恰相反。
确定进程优先权：
- 进程类型
- 进程对资源的需求
- 用户要求
动态优先权
动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。
4. 高响应比优先调度算法（Hi格荷斯坦R撒泼尿色R奥体哦N而心痛， HRRN）
优先权的变化率
由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：
1.如果作业的等待时间相同，该算法有利于短作业。
2.当要求服务的时间相同时，作业的优先权决定于其等待时间，因而它实现的是先来先服务。
3.对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高， 从而也可获得处理机。
进程调度算法
- 时间片轮转算法
- 高级优先权优先调度算法
- 多级反馈队列调度算法
1. 时间片轮转算法
在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；
2. 高级优先权优先调度算法
- 静态优先
- 动态优先
3. 多级反馈队列调度算法（基于时间片的先来先服务动态高优先抢占调度）
应设置多个就绪队列，并为各个队列赋予不同的优先级。 第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。
新进程进入内存后, 放入第一队列的末尾(FCFS原则)
当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果未完成，该进程转入第二队列的末尾，按FCFS原则等待调度执行；
仅当第一队列空闲时，调度程序才调度第二队列中的进程运行； 仅当第1~(i-1) 队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机。
四、实时调度
实现实时调度的基本条件
- 提供必要的信息
- 就绪时间
- 开始截止时间和完成截止时间
- 处理时间
- 资源要求
- 优先级
-
系统处理能力强
在实时系统中，通常都有着多个实时任务。若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理， 从而导致发生难以预料的后果。假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件：
假如系统中有6个硬实时任务，它们的周期时间都是 50 ms，而每次的处理时间为 10 ms，系统可调度不？
解决的方法是提高系统的处理能力，其途径有二：其一仍是采用单处理机系统， 但须增强其处理能力， 以显著地减少对每一个任务的处理时间；其二是采用多处理机系统。假定系统中的处理机数为N，则应将上述的限制条件改为：
- 采用抢占式调度机制
当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。但这种调度机制比较复杂。
- 具有快速切换机制
该机制应具有如下两方面的能力：
- 对外部中断的快速响应能力。要求系统具有快速硬件中断机构 。
- 快速的任务分派能力。在完成任务调度后，便应进行任务切换, 以减少任务切换的时间开销。
实时调度算法分类
1.非抢占式调度算法
- 非抢占式轮转调度算法
- 非抢占式优先调度算法
- 抢占式调度算法
- 基于时钟中断的抢占式优先权调度算法
-
立即抢占的优先权调度算法
实时进程调度
常用的实时调度算法
1. 最早截止优先时间算法（Earliest Deadline First, EDF）
EDF用于非抢占调度方式
2. 最低松弛优先算法（Least Laxity First, LLF）
一个实时系统中，有两个周期性实时任务A和B：任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每50 ms执行一次，执行时间为 25 ms。
在刚开始时(t1=0)，A1必须在20ms时完成，而它本身运行又需 10 ms，可算出A1的松弛度为10ms；B1必须在50ms时完成， 而它本身运行就需25 ms，可算出B1的松弛度为25 ms，故调度程序应先调度A1执行。在t2=10 ms时，A2的松弛度可按下式算出：
A2的松弛度=必须完成时间-其本身的运行时间-当前时间 =40 ms-10 ms-10 ms=20 ms
类似地，可算出B1的松弛度为15ms，故调度程序应选择B2运行。在t3=30 ms时，A2的松弛度已减为0(即40-10-30)，而B1的松弛度为15 ms(即50-5-30)，于是调度程序应抢占B1的处理机而调度A2运行。在t4=40 ms时，A3的松弛度为10 ms(即60-10-40)，而B1的松弛度仅为5 ms(即50-5-40)，故又应重新调度B1执行。在t5=45 ms时，B1执行完成，而此时A3的松弛度已减为5 ms(即60-10-45)，而B2的松弛度为30 ms(即100-25-45)，于是又应调度A3执行。在t6=55ms时，任务A尚未进入第4周期，而任务B已进入第2周期，故再调度B2执行。在t7=70 ms时，A4的松弛度已减至0 ms(即80-10-70)，而B2的松弛度为20 ms(即100-10-70)，故此时调度又应抢占B2的处理机而调度A4执行。
五、产生死锁的原因和必要条件
产生死锁的原因
- 竞争资源
- 进程间推进顺序非法
竞争资源
可剥夺性资源（如:CPU.内存）
非可剥夺性资源（如：打印机）
-
竞争非剥夺性资源
竞争非剥夺性资源 竞争临时性资源
进程间推进顺序非法
若并发进程P1和P2按曲线④所示的顺序推进，它们将进入不安全区D内。此时P1保持了资源R1, P2保持了资源R2, 系统处于不安全状态。因为，这时两进程再向前推进，便可能发生死锁。例如，当P1运行到P1:Request(R2)时，将因R2已被P2占用而阻塞；当P2运行到P2: Request(R1)时，也将因R1已被P1占用而阻塞，于是发生了进程死锁。
死锁发生的必要条件
- 互斥条件
- 请求和保持条件
- 不剥夺条件
- 环路等待条件
处理死锁的方法
- 预防死锁。
- 摒弃“请求和保持”条件
- 摒弃“不剥夺”条件
- 摒弃“环路等待”条件
- 避免死锁。
- 检测死锁。
- 解除死锁。
避免死锁
系统安全状态
安全状态
在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程； 否则，令进程等待。
所谓安全状态，是指系统能按某种进程顺序(P1, P2, …，Pn)(称〈P1, P2, …, Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
由安全状态转向不安全状态
我们通过一个例子来说明安全性。假定系统中有三个进程P1、 P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：
如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。
例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。
因为，此时也无法再找到一个安全序列， 例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。
利用银行家算法避免死锁
参考 https://blog.csdn.net/qq_33414271/article/details/80245715
