操作系统原理学习笔记（十四）-实时调度(202/1/3更新)

操作系统原理学习笔记目录

这部分好多是前面内容的重复赘述，因此省略，
如非抢占式轮转调度算法，就是非抢占式调度算法与轮转调度算法的并集。

2021/1/3：更新了硬实时任务的概念，以及对松弛度添加了一点介绍。

实现实时调度的基本条件

• 提供必要信息：
  就绪时间。
  开始截止时间与完成截止时间。
  处理时间。
  资源要求。
  优先级。
• 系统处理能力强：提高单处理机系统的处理能力，或使用多处理机系统。
• 采用抢占式调度机制。
• 具有快速切换机制：对中断的快速处理能力，快速的任务分派能力。

实时调度算法的分类

各类调度算法的区别于P107有图示。

• 根据实时任务性质，分成硬实时调度算法与软实时调度算法。
  • 即对实时性要求高不高，高的是硬实时调度算法。
• 根据调度方式，分成非抢占调度算法与抢占调度算法。

非抢占式调度算法

• 轮转调度算法。
• 优先调度算法。

抢占式调度算法

• 基于时钟中断的抢占式优先调度算法，出现时间中断时进行抢占。
• 立即抢占（Immediate Preemption）的优先级调度算法，立即抢占。

最早截止时间优先算法(Earliest Deadline First, EDF)

本部分于书108页中有图示讲解。

非抢占调度方式用于非周期实时任务

先执行开始截止时间早的任务。

抢占式调度算法用于周期实时任务

固定优先级调度不适用于实时系统，因为容易使得任务错过最后期限。
而使用了最早截止时间优先算法，先将截止时间早的任务先执行，若出现比当前进程截止时间更早的，则中断该进程。

最低松弛度优先算法(Least Laxity First, LLF)

本算法于109页有图解。
松弛度实际上就是任务是否紧张，如果任务不紧张，就先运行其他的，而判别是否紧张，是根据从现在开始，到其最迟完成时间这段时间，是否有足够的完成时间。
如果能完成，并且还能剩余很多时间，那其松弛度就比较高，就不用那么急着安排。

松弛度=最迟完成时间-运行时间-当前时间

每次中断时（书上没写，但根据上篇轮转算法所述，这里指的应是自动中断机制），为最低松弛度的进程分配处理机。

优先级倒置（Priority Inversion Problem）

本现象于P111有图解。

在本部分中，要注意运行在临界区时，一般是使用原子操作的，因此不会被中断。
低优先级的进程阻塞了高优先级的进程。

产生原因

设三个进程ABC，优先级依次提高，进入就绪队列的次序为ABC。
A获得临界资源s后，B出现，A被B中断，但没有释放资源s，而后B被C中断，C需要临界资源s，但s被A使用，导致C被A阻塞，且B又延长了A被阻塞的时间。

解决办法

最简单的办法，获得临界资源的进程不允许被中断，但若临界区很长，那么优先级更高的进程将被推迟很久。

一个实用的方法，是让获得临界资源的进程，获得新进入的更高优先级进程的优先级，
例如上面的例子中，A在临界区中，先获得B的优先级，再获得C的优先级，在临界区结束后，会先执行C，再执行B，避免了C被长时间推迟。