写在前面：

笔者用来复习时的大提纲，建议搭配书一起复习

调度的分类：

1. 高级调度(长程调度)：调度的对象是作业。
2. 中级调度：调度的对象是内存。[存储器的对换]
3. 低级调度(短程调度)：调度的对象是进程。

调度的目标：

1. 资源利用率高
2. 公平
3. 平衡：平衡多种类型的进程(比如计算型、输出型)
4. 策略强制执行

批处理调度(作业调度)#

TIP

作业包括要运行的程序以及对应的数据，还有一份作业说明书。

作业步是该作业每一步要加工的动作。

作业也有对应的$JCB$.

作业有后备，运行，完成三个阶段。

批处理调度算法的独特目标：

1. 平均周转时间短

   TIP

   周转时间$T_i$ = 作业完成时刻 - 作业到达时刻，即从作业到达系统，直到被完成所花的时间。

   带权周转时间$T_i'$ = $\frac{T_i}{T_s}$，其中$T_s$是作业服务时间。

2. 吞吐量大

先来先服务(FCFS)#

短作业优先(SJF)#

优先级调度算法(PSA $priority-scheduling \ algorithm$)#

高响应比优先调度算法(HRRN $high \ response \ ration \ next$)#

定义：

每次调度前需要计算优先级，比较耗时。

进程调度#

进程调度的任务：

1. 保存现场信息
2. 选取该调度的进程
3. 分配处理机

进程调度分为非抢占方式和抢占方式。

轮转调度算法#

分时系统的独特目标：

1. 响应速度快。

   TIP

   响应时间 = 首次服务时刻 - 作业到达时刻

2. 均衡性：系统响应时间的快慢和作业的复杂程度相关。

优先级调度算法#

静态优先级#

动态优先级#

多队列调度#

有多个优先队列。

多级反馈队列调度#

多个优先队列，优先级$1 > 2 > 3 > \cdots > n$

每一个队列$FCFS$，若未运行完则插入下一个队列末尾，时间片*2。

公平原则调度算法#

保证调度算法: 每一个进程公平#

计算:

公平分享调度算法: 每一个用户公平#

实时调度#

实时系统的独特目标：

1. 截止时间的保证，最晚不能超过某时刻完成/最晚不能超过某时刻开始执行
2. 可预测性： 不卡顿？

对于服务时间为$C_i$，周期时间为$P_i$的周期性实时任务，若要在单处理机上可调度，要保证：

非抢占式轮转调度算法#

非抢占式优先级调度算法#

基于时钟中断的抢占式调度算法#

最早截止时间优先EDA($Earliest \ Deadline \ First$)#

选取最早截止的进程进行调度

最低松弛度优先LLF($Least \ Laxity \ First$)#

定义可松弛时间：

选取可以拖延时间最少的那一个进行调度。

CAUTION

最低松弛度调度只会在进程完成和有进程的可松弛时间转变为0时调度！！

优先级倒置#

TIP

假设进程$P_3$和$P_1$都要使用同一种临界资源，而$P_2$不需要。优先级$P_1 > P_2 > P_3$

当$P_3$正在临界区时，$P_2$抢占处理机，再过了一会$P_1$试图进入临界区，但阻塞。

$P_1$阻塞，先让$P_2$运行，再让$P_3$退出临界区。

$P_1$必须要等$P_2$运行，这就是优先级倒置。

解决方案是： 当$P_1$试图进入临界区后，可以把优先级共享给正在临界区的$P_3$，就可以先让$P_3$运行，而不等待$P_2$

死锁#

产生死锁有$4$个必要条件：

1. 互斥条件：所请求的资源是互斥的，只能被一个进程占用
2. 请求和保持条件： 进程必须都占用一些资源，而又请求其他的资源
3. 不可抢占条件：进程所占用的资源是不可抢占的
4. 循环等待条件：在发生死锁时，一定存在一个循环等待环。

预防死锁：破坏条件，使永远不产生死锁#

破坏“请求与保持”#

1. 一次性申请所有的资源
2. 申请初期资源，使用后释放，继续申请其他资源

破坏”不可抢占”#

当一个进程因为请求不到资源而被阻塞时，释放它所有占有的资源，下次重新申请

破坏”循环等待”#

为每一个资源确定一个”序号”

规定：一个进程只能申请比占有资源序号更大的资源。

避免死锁：分配资源时利用算法检测是否容易产生死锁#

安全状态是指，存在一个推进序列$\{P_1,P_2,\cdots,P_n\}$能够被顺利完成。

安全状态下，不会产生死锁，而不安全状态下，有可能产生死锁。

检测死锁#

破坏死锁#

1. 抢占资源
2. 终止进程