软考高级架构师: AI 通俗讲解 嵌入式操作系统调度算法

1 通俗讲解

四种调度算法，可以通过一个生活中的例子来理解：假设你是一家餐厅的经理，需要决定哪些订单先做哪些后做。你的目标是确保顾客满意并且高效地使用厨房资源。

A. 优先级调度算法

这种算法就像在餐厅中，每个订单都有一个优先级标记。比如，VIP客人的订单优先级高，普通客人的次之。你按照订单的优先级来决定做菜的顺序，高优先级的订单先做。但是，一旦开始做一个订单，即使来了更高优先级的订单，也不会停下当前正在做的订单。

B. 抢占式优先级调度算法

这种方法与优先级调度类似，也是按订单的优先级来排序，但有一点不同：如果正在做的是普通客人的订单，这时来了一个VIP客人的订单，厨师会暂停当前订单，先去做VIP的订单。也就是说，这种方法允许新的高优先级任务打断正在进行的低优先级任务。

C. 最晚截止期调度算法

想象每个订单都有一个必须完成的截止时间。在这种调度算法中，你总是选择离截止时间最近的订单来做，以确保每个订单都能在截止时间前完成。这种方式关注的是“谁最急需”，而不是“谁最重要”。

D. 最早截止期调度算法

与最晚截止期相反，最早截止期调度算法会优先处理那些截止时间最早的订单。这样做的目的是尽量减少因订单延误而影响客户满意度的风险。即使有的订单可能更简单或更复杂，只要它的截止时间最早，就先做。

总结来说，这四种调度算法各有侧重，优先级调度算法和抢占式优先级调度算法侧重于“重要性”，而最晚截止期和最早截止期调度算法则侧重于“紧急性”。在实际应用中，选择哪种算法取决于任务的性质和具体需求。

2 最晚截止期调度算法 VS 最早截止期调度算法

当然可以，让我们用一个图书馆还书的例子来进一步阐明“最晚截止期调度算法”和“最早截止期调度算法”之间的区别。

最晚截止期调度算法

假设你是图书馆的管理员，负责收回借出的图书。图书的还书日期是不同的，有些是今天到期，有些是几天后。在使用最晚截止期调度算法时，你会优先处理那些离到期时间最近的图书。例如，如果今天有5本书到期，而明天有3本，你会先联系今天到期的那些借书者，确保这些书能及时回收。这种方式的关键是“避免逾期”，尽量在最后期限之前完成任务。

最早截止期调度算法

现在，如果你改用最早截止期调度算法，情况就反过来了。在这种情况下，你会优先处理那些截止时间最早的图书，无论它们的到期日是今天、明天还是后天。比如，如果昨天有2本书未还（假设已逾期但还未处理），今天有5本到期，你会先处理那2本昨天就应该归还的书。这种方式的目标是“最大程度减少逾期时间”，即使它们已经逾期，也要尽快处理。

通过这个图书馆还书的例子，可以更清楚地看出两种调度算法的差异：

• 最晚截止期调度算法专注于处理接近当前日期的紧急任务，以防任务逾期。
• 最早截止期调度算法则优先解决已经逾期或最早需要处理的任务，以最快解决潜在的延误问题。

这两种算法都试图以不同的方式优化任务的完成时间和资源的利用，选择哪一种取决于你希望优化的目标是什么。

3 例题

某嵌入式实时操作系统采用了某种调度算法，当某任务执行接近自己的截止期（deadline）时，调度算法将把该任务的优先级调整到系统最高优先级，让该任务获取CPU资源运行。请问此类调度算法是（ ）。

A. 优先级调度算法 B. 抢占式优先级调度算法 C. 最晚截止期调度算法 D. 最早截止期调度算法

试题信息:通过率：67% 所属知识点：嵌入式系统>嵌入式操作系统；

答案 C

试题分析 本题考查的是嵌入式操作系统调度算法。 实时系统存在多种调度算法。 A选项优先级调度算法：系统为每个任务分配一个相对固定的优先顺序，然后调度程序根据优先级的高低排序，按时间顺序进行高优先级任务优先调度。 B选项抢占式优先级调度算法：是在优先级调度算法基础上，允许高优先级任务抢占低优先级任务而运行。 C选项最晚截止期调度算法：指调度程序按每个任务最接近其截止期末端的时间进行调度，本题描述的就是最晚截止期调度算法。 D选项最早截止期调度算法：指调度程序按每个任务的截止期时间，选择最早到截止期的头端时间的任务进行调度。