C 嵌入式系统设计模式 17：静态优先级模式

本书的原著为：《Design Patterns for Embedded Systems in C ——An Embedded Software Engineering Toolkit 》，讲解的是嵌入式系统设计模式，是一本不可多得的好书。

本系列描述我对书中内容的理解。本文章描述嵌入式并发和资源管理模式之三：静态优先级模式。

静态优先级模式 (Static Priority Pattern) 是一种 调度模式。在计算机系统中，调度模式指的是对任务、进程或线程进行调度时所采用的一种或多种特定的策略或方法。这些模式旨在优化资源利用率、提高系统性能、确保实时响应等。

静态优先级模式对高优先级事件的响应表现良好，并且能够很好地扩展到大量的任务上。大多数实时操作系统都支持静态优先级模式。

静态优先级 是指在创建任务时，赋予任务一个固定的优先级，该优先级在整个任务的生命周期中保持不变。

在确定任务的 优先级 时，可以采用多种不同的方案，但通常这些方案都基于任务的 紧迫性 和 关键性，或是这两者的某种组合。

当采用 速率单调调度（rate monotonic scheduling）进行优先级分配时，静态优先级模式不仅表现出最优性（即无法通过其他调度策略获得更好的性能），还具有稳定性。在过载情况下，可以预测哪些任务会失败——通常是优先级最低的任务。这种可预测性对于实时系统来说至关重要。

速率单调调度：一种为周期性任务分配优先级的策略，其中较短的周期（即较高的频率）被赋予较高的优先级。

在这种情况下，如果我们假设每个任务的截止时间恰好等于一个完整任务执行周期的时长，那么如下所示的公式给出了任务集中可调度的必要条件：
$\sum_{j}\frac{C_{j}}{T_{j}} + max(\frac{B_{1}}{T_{1}},...,\frac{B_{n-1}}{T_{n-1}}) ≤ 利用率(n) = n(2^{\frac{1}{n} }-1)$
其中：

C_j 是任务 j 的最坏执行时间
T_j 是任务 j 的执行周期(也是任务 j 的截止时间)
B_j 是任务 j 的最坏阻塞时间
n 是任务的数目

对于非周期性任务，会使用任务 j 的最小到达间隔时间作为任务的执行周期。请注意，阻塞项仅扩展到第n-1个任务；这是因为根据定义，最低优先级的任务不能被阻塞。

最小到达间隔时间：指的是非周期性任务两次连续启动执行之间的最小时间间隔。

摘要

静态优先级模式 在嵌入式系统中广泛流行，这得益于实时操作系统的强大支持、易用性以及对紧急事件的出色响应能力。然而，对于规模极小、结构简单或由高度可预测且不受紧急异步事件驱动的系统而言，静态优先级模式可能会显得过于复杂。

尽管该模式在可调度性分析方面表现出色，但使用基于阻塞资源共享的原始实现方式可能会引发 不受控制的优先级反转 问题。幸运的是，存在一些资源共享模式，可以有效地避免这一问题，或者至少将优先级反转限制在单个级别内。

在分配优先级时，最常见的方法是基于截止时间的长短，即任务的 紧迫性。通常情况下，截止时间越短的任务被赋予更高的优先级。当截止时间等于任务执行周期时，这种分配方案称为 速率单调调度，此时截止时间越短，执行周期越短，所以执行频率越高，优先级越高。虽然速率单调调度假设所有任务都是周期性的，但对于非周期性任务，也可以采用最小到达间隔时间来进行处理。然而，这种做法往往会导致系统设计的过度冗余(最小达到间隔时间可能很短)，进而对系统的经常性成本产生不良影响。

问题

静态优先级模式为任务调度提供了一种基于优先级的简洁方法。与 循环执行模式 相比，它可以处理更多的任务，而且可以对紧急事件快速的响应。

模式结构

模式结构如下图所示：

在这里插入图片描述

彩色类通常由实时操作系统（RTOS）提供。

模式详情

抽象的静态线程

抽象的静态线程 与 调度器 相 关联 。调度器执行线程的 run() 函数来运行线程。这个 run() 函数由抽象的静态线程声明，在具体的静态线程中实现。

具体的静态线程

表示软件中的具体线程。

互斥量类

互斥量类 用于保护共享资源，它对共享资源提供 序列化 访问。确保在任何时候只有一个线程能够访问被保护的资源，从而防止数据竞争和不一致的状态。

当线程需要访问共享资源的受保护函数时，它首先会调用互斥量类的 lock() 函数来尝试获取锁。一旦受保护的代码执行完毕，线程会调用互斥量类的release() 函数来释放锁。

当关联的互斥量被锁定时，调用服务的其他客户端线程将被阻塞，直到互斥量解锁。mutexID 标识哪个互斥量正在阻塞任务。这个元素通常由 RTOS 提供。

序列化 (serializes ) ：在编程中，当多个进程或线程尝试同时访问和修改共享资源（如内存中的数据、文件等）时，如果不加以控制，就可能导致数据的不一致或其他未定义的行为。为了解决这个问题，我们需要引入某种机制来确保在任何时候只有一个进程或线程可以访问共享资源，或者至少确保访问是以一种可预测和可控的顺序进行的。
“序列化”访问共享资源就是这样一种机制。通过序列化，我们可以确保对资源的访问请求是按照某种顺序（如先进先出FIFO）排队和处理的。这通常是通过使用锁、信号量、互斥量等同步原语来实现的。当一个进程或线程获得对资源的访问权时，其他进程或线程必须等待直到该资源被释放。

优先级队列

优先级队列 是一个按优先级组织的 StaticTaskControlBlock 指针队列。该模式使用两个独立的优先级队列实例。第一个是 就绪队列 。当任务准备运行时，按其优先级的顺序将其 StaticTaskControlBlock 的指针插入队列中。如果任务的优先级高于当前正在运行的任务（或在当前任务终止时变得更高），那么任务将从就绪队列中移除并运行。另一个优先级队列是 阻塞队列 ；这个队列保存了当前被阻塞的任务集合，因为它们试图访问由锁定的 互斥量类 保护的共享资源。优先级队列通常由RTOS提供。

共享资源

共享资源 由一个或多个 具体的静态线程 共享。为了在所有情况下都能使系统正常运行，共享资源要么是 可重入 的，要么通过访问序列化进行保护。

栈

每个抽象线程都有一个栈，用于存储返回地址和传递的参数。这通常在应用程序线程的汇编语言级别中才是明确的，但它是调度基础设施的重要组成部分。这个元素通常由 RTOS 提供。

静态优先级调度器

静态优先级调度器 基于线程的优先级协调多个线程的执行，它遵循一个简单规则：始终运行优先级最高的就绪线程。当创建任务时，它（或其创建者）会调用 createThread() 函数创建一个线程。每当静态优先级调度器执行此线程时，它都会调用 StartAddr 地址函数（除非线程被阻塞或抢占，在这种情况下，它会调用 EntryPoint 地址函数）。这个元素通常由RTOS提供。

静态任务控制块

静态任务控制块包含其对应的抽象线程对象的 调度信息。这包括线程的优先级、默认起始地址和当前入口地址。静态优先级调度器 为每个现有的抽象线程维护一个静态任务控制块对象。这个元素通常由RTOS提供。

效果

如前所述，静态优先级模式可以很好地运行大量任务，并对传入的事件做出响应。通常情况下，任务大部分时间都在等待启动，只有当触发事件发生时才会激活。当有多个任务时，将优先运行优先级最高的任务。

实现策略

通常情况下我们无需自己实现这个模式，而是使用商业 RTOS 来提供调度基础设施。如今有数十种流行的 RTOS 可以满足大多数嵌入式系统的约束条件。

无论你是购买商业 RTOS 还是自己开发，都必须解决分配优先级的问题。速率单调调度 是分配优先级的最常用方法。它是最优且稳定的。它能获得最好的性能，而且在过载情况下，还可以预测哪些任务会失败(优先级在最低的任务)速率单调调度只是将优先级作为周期的函数——周期越短，优先级越高。

速率单调调度任务做了一些假设：

任务是周期性的
任务的截止时间和执行周期相同
任务可无线抢占

但在违反这些假设的情况下，速率单调调度仍然是相当稳健的。

关于第一个假设，如果任务不是周期性的，那么它们可以使用任务调用之间的最小时间间隔来确定优先级。

关于第二个假设，有时截止时间可能小于周期。在这种情况下，可以简单地使用截止时间（Dj）而不是周期（Tj）来分配优先级。

最后一个假设是，一旦有更高优先级的任务准备就绪，当前正在运行的任务就可以立即被抢占。然而，如果当前正在运行的任务处于 临界区（即禁止任务切换的时间段），这一假设则不成立。但是，如果临界区的时间很短，这通常不会成为问题。在这种情况下，可以将所有其他任务的最长临界区持续时间视为正在分析的任务的最坏情况阻塞时间来进行分析。