操作系统原理学习笔记(十四)-实时调度(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被长时间推迟。

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注