第13章 POSIX和实时操作系统

13.1 可移植操作系统接口简介

POSIX是“可移植操作系统接口”（portable operating system interface）的缩写，是由电气与电子工程师协会（IEEE）开发的一种开放操作系统（OS）接口标准，并由国际标准化组织认可。

美国国家标准协会 (ANSI)。作为一种标准软件接口，POSIX 的主要目标是促进应用程序在不同 Unix 操作系统变体之间的互操作性和可移植性。理想情况下，只要两个操作系统都支持 POSIX，为一个操作系统编写并编译以执行的程序，也可以在无需更改源代码的情况下，为另一个操作系统编译并执行。

1988年，IEEE发布了其首个POSIX标准——IEEE Std1003.1‐1988。后续版本分别于 1990年、1996年和2001年发布。随着新标准的推出，“POSIX”这一术语被扩展为指代一系列相关标准，而POSIX.1则专用于指代IEEE Std 1003.1‐1988及其后续版本。截至本文撰写时，POSIX.1标准的最新版本是IEEE Std1003.1‐2008，也称为POSIX.1‐2008[17]。

POSIX.1‐2008 主要包括 POSIX 基础定义（如并发执行、文件访问权限、内存同步、路径名解析和头文件）、系统接口（如套接字、线程、信号、流和实时服务）以及命令和实用程序（如 exec、cat 和 echo）。表 13.1列出了一些 POSIX.1 核心服务和实时扩展。

13.1.1 POSIX进程和线程

在 POSIX 中，每个正在运行的程序实例被称为进程。每个进程都有其独立的受保护地址空间。进程之间相互隔离，以防止它们无意中侵犯彼此。由于这种强制性隔离，进程之间的通信只能通过使用操作系统内核服务来实现。

POSIX线程是运行在进程内的单一执行流。当一个进程开始运行时，实际上是在运行一个线程，这个线程通常被称为“主线程”，因为C程序的入口点是main()函数。主线程可以根据程序设计创建额外的线程。因此，进程实质上是由一个或多个线程组成的集合。

作为一个单一的执行流，进程内的每个线程都有其自己的栈和寄存器值。然而，进程中运行的线程至少共享以下内容：
- 进程的虚拟地址空间（因此在线程之间切换不涉及更改内存上下文）；
- 不在栈上的变量（因此线程可以通过全局变量共享数据并相互通信）；
- 信号处理程序和进程级信号控制结构。

当实时嵌入式系统基于操作系统构建时，每个任务被实现为一个进程或仅仅是一个线程。

13.1.1.1 进程创建

对于由多个程序组成的大型（嵌入式）系统，通常会有一个主程序，也称为启动程序，用于启动所有其他程序。该启动程序本身通常是shell脚本文件（命令批处理）中的最后一条命令，在系统启动并运行后自动执行。

一个进程（实际上是进程内的线程）可以调用系统调用来创建新进程。新创建的进程称为调用进程的子进程，而调用进程被称为新进程的父进程。子进程与其父进程独立运行，但子进程会从其父进程继承许多属性。

POSIX 提供了以下系统调用用于启动新的进程 :
- fork() 。此调用会创建一个新进程，该进程复制调用进程：（a）两个进程执行相同的应用程序代码；（b）它们在此调用处保持执行同步——都即将从 fork() 调用返回。fork() 调用的返回值可用于区分调用进程和新创建的子进程：在新创建的子进程中，返回值为 0；而在父进程中，返回值是子进程的 ID。当新进程刚被创建时，它只包含一个线程。如果从多线程进程中调用 fork()，则新进程仅包含调用线程的副本。
- exec()函数族 。调用进程的进程映像将被从可执行文件构建的新进程映像覆盖，并且不会从该操作返回。从具有多个线程的进程中成功调用exec.A到任何exec函数，将导致所有线程被终止。
- posix_spawn() 函数族 。fork() 的实现通常依赖于内存管理单元（MMU）服务，例如内存交换或动态地址转换，这对于实时应用来说通常太慢。posix_spawn() 函数（及其变体）是一种简单、快速的实现，无需地址转换或其他内存管理单元服务。成功完成后，posix_spawn() 将子进程的 ID 返回给父进程。
- system() 。该调用接收一个命令，启动一个 shell（命令语言解释器）来执行该命令。此调用在子进程终止之前不会返回。它可以通过 posix_spawn() 调用实现，或者通过 fork() 后跟 exec() 来实现。

13.1.1.2 线程创建

创建后，进程拥有一个单一的主线程或初始线程。活动线程被指示执行程序代码，其中可能包含用于创建额外线程的系统调用。POSIX函数pthread_create()用于在进程中创建新线程。

进程内的线程彼此之间没有父子关系。线程可以自行终止。如果进程中的任一线程调用 exit()，则该进程及其所有线程都将终止。

13.1.2 POSIX实时扩展

许多实时嵌入式系统仅有有限资源，且不需要文件系统或任务的独立地址空间等高级功能。对于此类系统，基于仅支持特定子集POSIX函数的操作系统来实现是较为理想的。实时配置文件标准 IEEE Std 1003.13‐1998 于1998年首次发布，以满足这一需求。它包含四个实时应用程序环境配置文件：
1. 最小配置文件：用于构建没有内存管理单元、文件系统或I/O终端的小型嵌入式系统。只允许一个进程，但允许多个线程。
2. 实时系统的最小配置文件：用于构建具有文件系统和I/O终端的实时控制器。只允许一个进程，但允许多个线程。
3. 嵌入式系统有限配置文件：用于构建没有文件系统的大规模嵌入式系统。允许多个进程和线程。
4. 最大配置文件：用于构建具备所有支持功能的大型实时系统和嵌入式系统。

IEEE Std 1003.1‐2008，即POSIX.1标准的最新版本，还包含了一些与实时系统相关的修订或扩展。
- IEEE Std 1003.1b‐1993 实时扩展；
- IEEE Std 1003.1c‐1995 线程；
- IEEE Std 1003.1d‐1999 附加实时扩展；和
- IEEE Std 1003.1j‐2000 高级实时扩展。

下面，我们介绍一些POSIX.1服务指定在实时修正案中。

13.1.2.1 基于优先级的调度

线程是可调度的实体（即承载作业的资源）。操作系统调度器在任意时刻最多选择一个线程在每个处理器上执行。

每个POSIX线程在创建时都会关联一个称为调度优先级的数值，操作系统调度器使用该数值来确定何时以及如何调度该线程。我们在基于优先级的调度中考虑三个原则。
1. 优先级原则 。当没有线程在运行，且多个线程准备被调度执行时，具有更高优先级的线程总是优先于较低优先级的线程被调度。
2. 抢占原则 。当一个线程正在运行，而另一个更高优先级的线程变为就绪状态时，该更高优先级的线程将抢占当前线程的执行。
3. 公平性原则 。当多个具有相同或不同优先级的线程竞争使用处理资源时，系统的调度行为由与这些线程相关联的调度策略进行调控。

优先级原则是基于优先级的调度的基础。但是，如果一个线程变为就绪状态时，一个较低优先级的线程正在运行，会发生什么情况？让我们首先考察一种称为非抢占式调度的方法，如图13.1所示。这里每个任务都实现为一个线程。任务 T1（即相应的线程） 具有最低优先级，任务 T3具有最高优先级，而任务 T2的优先级居中。任务 T1的第一个作业 J11在时间0被释放。由于 J11是唯一的作业，因此被调度执行。作业 J21和 J31 分别在时间15和时间20被释放。然而，尽管这两个作业各自的优先级高于 J11,，它们不会抢占 J11的执行。一旦 J11在时间25完成，根据优先级原则，J31将被调度执行。当 J31在时间40完成时，J21被调度执行。请注意，此调度导致 J21的截止时间被打破。

图13.2 显示了另一个场景，其中应用了抢占原则。这三个任务的参数仍与图13.1中给出的相同。当作业J21在时间15被释放时，根据抢占原则它会抢占作业J11。类似地，在时间20，作业J31抢占作业J21,，后者在J31执行完毕后的时间35恢复执行。同样， J11在J21执行完毕后的时间40恢复执行。根据此调度，所有三个任务都能满足它们的截止时间。这种调度称为抢占式调度。

当任务（或线程）与调度策略相关联时，公平性原则适用。POSIX.1‐2008 标准规定了四种调度策略：SCHED_FIFO、SCHED_RR、SCHED_SPORADIC 和 SCHED_OTHER。这些策略及相关结构在表13.2中描述。

每个 POSIX 进程/线程都可以与一个调度策略以及与所选调度策略相关的属性相关联。具体而言：
- 创建进程时，可以通过 posix_spawn 调用指定其调度策略和属性，也可以通过 fork 调用继承父进程的调度策略和优先级设置。
- 通过显式调用函数sched_setscheduler()或sched_setparam()，一个进程可以设置或更改自身或其他进程的调度策略和/或属性。
- 在线程创建（通过 pthread_create 调用）时，可以为其指定调度策略和调度属性。
- 通过显式调用函数 pthread_setschedparam() 或 pthread_setschedprio()，调用线程可以设置或更改同一进程内线程的调度策略和/或属性。

进程的调度策略和属性（如果有的话）仅对各个线程的调度行为产生间接影响。创建进程时，其单个线程将继承该进程的调度策略以及相关的调度属性。新创建的线程也可以选择继承创建线程的调度属性（如果这些属性是期望的）。

POSIX 定义	描述
SCHED_FIFO_ SCHED RR_ SCHED SPORADIC_ SCHED OTHER_	表示FIFO策略的整型常量 一个表示轮转策略的整数常量 一个表示偶发服务器策略的整数常量 一个表示任何其他策略的整数常量
struct sched_param	sched_priority：调度优先级的数值（更高值 表示更高优先级） sched_ss_low_priority：SCHED_SPORADIC 的低优先级 sched_ss_repl_period：SCHED_SPORADIC 的补充周期 sched_ss_init_budget：SCHED_SPORADIC 的初始预算 sched_ss_max_repl：SCHED_SPORADIC 的最大补充次数
sched_setparam sched setscheduler_ pthread_setschedparam pthread_setschedprio	为指定的进程设置调度参数 为指定进程设置调度策略和参数 为指定线程设置调度策略和参数 为指定线程动态设置调度优先级

策略SCHED_FIFO、SCHED_RR和SCHED_SPORADIC将在第13.4节中进一步讨论。

POSIX调度策略SCHED_OTHER依赖于具体实现；它可能是一种实时调度策略，也可能不是。

13.1.2.2 任务同步

POSIX.1‐2008 标准定义了用于通过信号量管理进程同步的函数。信号量是一种操作系统内核对象，可实现对共享资源的互斥访问。POSIX 信号量无法防止一种称为“无界优先级反转”的不良问题，该问题发生在高优先级任务需要等待低优先级任务完成其由信号量保护的操作时。有关信号量的使用，请参见第18.3节。

POSIX.1‐2008 标准还定义了mutexes用于进程内的线程同步。如果配置得当，互斥对象也可用于进程间同步。POSIX 互斥锁具有多个重要属性：
- 所有权 。当对互斥对象调用pthread_mutex_lock()成功时，该互斥锁被调用线程锁定，该线程成为互斥对象的所有者。一个被锁定的互斥锁只能由其所有者通过调用pthread_mutex_unlock()来解锁。
- 优先级上限 。这定义了由互斥锁保护的临界区执行时的最低优先级。为了避免优先级反转，在设计时应将互斥锁的优先级上限设置为等于或高于所有可能锁定该互斥锁的线程中的最高优先级。
- 协议 。可通过调用函数 pthread_mutexattr_setprotocol() 将其设置为以下三种协议之一：PTHREAD_PRIO_NONE、PTHREAD_PRIO_INHERIT 和 PTHREAD_PRIO_PROTECT。默认协议值为 PTHREAD_PRIO_NONE。

简而言之，拥有互斥锁的线程的优先级和调度可能会受到以下影响：
- 线程的优先级和调度不受具有PTHREAD_PRIO_NONE协议属性的互斥锁所有权的影响。
- 当一个线程由于拥有一个或多个具有PTHREAD_PRIO_INHERIT协议属性的互斥锁而阻塞较高优先级的线程时，该线程应以其自身的优先级和等待其拥有的任何互斥锁的线程中的最高优先级两者中较高的优先级执行。
- 当一个线程持有一个或多个使用 PTHREAD_PRIO_PROTECT 协议初始化的互斥锁时，无论是否有其他线程阻塞在这些互斥锁上，该线程都将以其自身优先级和其所持有并使用此协议初始化的所有互斥锁的优先级上限中的较高者来执行。

如果一个线程同时拥有以不同协议初始化的多个互斥锁，则该线程应以其通过这些协议获得的最高优先级执行。

通过使用具有PTHREAD_PRIO_INHERIT或PTHREAD_PRIO_PROTECT协议的互斥锁，可以避免无界优先级反转。有关这些协议的详细信息，请参见第14.5节。有关互斥锁的使用，请参见第18.3节。

13.1.2.3 其他服务

图13.3 给出了操作系统内核中通常实现的一些对象。

POSIX 定义了一种用于异步进程间通信的信号机制：尽管任务可以指定在信号到达时执行的特定操作，但无法预测信号何时到达。POSIX 信号可以在接收进程中排队，从而避免事件或请求丢失。每个信号都关联一个优先级；实时信号按优先级顺序出队，使得紧急事件能够更早被处理并更快响应。信号处理的详细信息参见第21章。

POSIX.1‐2008 标准要求操作系统实现至少支持一个由常量 CLOCK_REALTIME 标识的实时时钟，默认情况下，该时钟表示自纪元以来经过的时间（以秒或纳秒为单位）。

实时时钟可以以有限的速率跳动，例如 1000 赫兹。时钟的分辨率（也称为其粒度）是其跳动速率的倒数。例如，跳动速率为 1000 赫兹的时钟分辨率为 1 毫秒。有关时间分辨率的更多信息，请参见第22章。

表13.3 给出了一些用于实时时钟的POSIX函数。对于特定的实时时钟，用户可以获取其分辨率、获取当前时间或为时钟设置新时间。用户还可以通过调用睡眠函数来暂停线程的执行，这些函数可以接受相对或绝对时间值，且时间值可以以秒（低分辨率）或纳秒（高分辨率）为单位。如果相对睡眠函数被信号中断，则会返回剩余时间。在这种情况下，如有必要，可利用剩余时间重新发出。

POSIX 定义	描述
结构体 timespec	long tv_sec: 秒 long tv_nsec：纳秒
结构体itimerspec	timespec it_interval：定时器周期 timespec it_value：定时器首次超时时间
创建定时器_ 定时器_gettime 定时器 settime_	为调用进程创建一个定时器 获取定时器的当前时间间隔 设置/重置现有定时器的时间间隔
clock_getres clock_gettime clock settime_ sleep 纳秒睡眠 clock_纳秒睡眠	返回实时时钟的分辨率 返回指定时钟的当前值（结构体 timespec） 为指定时钟设置一个新值 一个相对低分辨率的 sleep 函数，导致调用线程被暂停执行，直到请求的时间间隔（以秒为单位）结束 经过的时间，或线程被信号中断 一个相对高分辨率的sleep函数，它使调用线程被暂停执行，直到请求的时间间隔（以纳秒为单位）结束 时间已过，或线程被信号中断。在后一种情况下，剩余的时间也会被返回（请求的时间减去实际睡眠的时间） 这种高分辨率的睡眠函数可以有两种模式 如果设置了“absolute”标志，则为绝对睡眠函数。它会使当前线程暂停执行，直到引用的时钟达到请求的时间 绝对时间，或线程被信号中断 如果“absolute”标志未设置，则为相对睡眠函数。它会使当前线程暂停执行，直到请求的时间间隔已过，或者线程被信号中断。在后一种情况下，剩余时间也会被返回（请求的时间减去实际睡眠的时间）

a最终会进行一次内核调用，启动一个相对定时器。

POSIX实时时钟可用于控制实时任务的执行，以满足其时序要求。特别是，在实时系统中存在一些需要被挂起并以周期性方式多次激活的任务（线程）。例如，显示设备可能需要周期性刷新，或非中断设备的状态可能需要周期性轮询。此类周期性行为可通过使用实时时钟来实现。例如，假设一个周期性任务T1=(p1,e1)在时间t0（这是一个绝对时间点）开始执行，并在时间t1= t0+e1运行完成。该任务需要将自身挂起，直到下一个周期的开始，即时间t0+p1。这一操作可以通过调用clock_nanosleep()函数并传入绝对时间点t0+p1作为请求的时间参数“精确”地实现。

需要注意的是，通过调用相对睡眠函数（如 sleep()、nanosleep() 或 clock_nanosecondsleep() 的相对版本）可能无法实现“精确的周期性激活”。例如，如果任务 T1 改为使用 nanosleep()，则在调用 nanosleep() 函数之前，必须先调用 clock_gettime() 获取当前时间，然后计算当前时间与 t0+p1, 之间的差值，最后使用计算的时间间隔调用 nanosleep()。然而，这两个函数调用之间任务可能会被其他任务抢占。在这种情况下，计算的时间间隔将不准确，任务 T1 将比预期更晚唤醒。使用绝对版本的 clock_nanosecondsleep() 函数则不会出现此问题，因为只需一次函数调用即可将任务挂起至期望的时间。

POSIX定时器 也可用于控制实时任务的执行，以满足其时序要求。一个进程可以创建多个定时器3来计数特定的时间间隔。由一个进程创建的定时器不能被其子进程继承。

定时器依赖于信号的使用，4并且必须引用实时时钟作为其时序基准。如图13.3所示，定时器可以指定两个时间间隔：定时器周期和到期值，前者用于定义周期性定时器，后者用于指定一次性定时器的超时间隔或周期性定时器的第一次到期值。当指定的超时间隔结束时，定时器可以向创建该定时器的进程发送一个“超时”信号。对于给定的定时器，在任何时刻只能有一个超时信号被排队到该进程。

周期性定时器可以生成未指定数量的超时信号。有关定时器使用的更多信息，请参见第15 章和第22章。

POSIX.1‐2008 标准将消息队列 定义为一种异步进程间通信机制。连接到消息队列的进程可以向其发送结构化消息或从中读取消息。传输和接收不是同步的，即发送方不会等待接收方实际从队列中取回消息。消息的传输和接收可以是阻塞的或非阻塞的。

第19章描述了消息队列的POSIX函数及其用途。

POSIX.1标准还规定了内存映射文件和共享内存对象作为进程共享物理内存部分的方法。当实时应用需要以极小的开销共享大量数据时，这非常有用。内存映射文件提供了一种机制，允许进程将其地址空间直接映射文件内容；由于采用直接内存操作，文件数据访问速度非常快。如果多个进程映射同一个文件，则它们共享该文件的内容。

特别地，通过一个进程的地址空间写入内存对象的数据，也会出现在所有映射同一内存对象区域的进程的地址空间中。有关共享内存对象的使用，请参见第18章。

13.1.3 POSIX兼容性和一致性

POSIX 实现合规性 指的是操作系统实现部分支持POSIX.1标准，并且有文档说明哪些POSIX功能被支持，哪些未被支持。

POSIX 实现一致性 意味着一个操作系统实现完全支持 POSIX.1 标准中定义的所有强制性系统接口（函数和头文件）、工具和设施，以及一些标准扩展。

根据符合POSIX.1标准的程度，可以将操作系统分为部分POSIX.1兼容或完全（100 %）POSIX.1兼容（一致性）。一些操作系统，如Solaris和QNX [8],是完全兼容的，而其他一些，如GNU/Linux和VxWorks，则不是完全兼容。

POSIX 应用程序一致性 意味着应用程序严格符合POSIX.1标准，即仅依赖于标准中描述的功能。应用程序一致性对于支持软件互操作性和可移植性至关重要。为一个符合POSIX的操作系统编写的代码通常可以移植到另一个符合POSIX的操作系统上，甚至可以以较低的成本移植到部分兼容的操作系统上。此外，熟悉一个符合POSIX的操作系统的程序员可以直接将其技能集应用于涉及其他符合POSIX的操作系统的项目中。

13.2 任务静态与动态

13.2.1 一般任务结构

图13.4 展示了一个UML类图，说明了“任务”概念的静态结构：
- 任务是一种可调度实体。为了实现SchedulableEntity接口，任务具有调度策略和指定优先级等属性。任务可能以不同的优先级（即实际优先级）临时运行。任务还可以根据所选的调度策略指定其他相关参数。
- 任务可以具有任务参数，例如周期、释放时间、执行时间和截止时间。任务可能是周期性任务、非周期性任务或偶发性任务。在任意时刻，任务可能处于四种状态之一：就绪、运行、阻塞或睡眠。
- 任务是一个抽象概念。线程是（实现）一个任务。线程的线程ID是一个唯一标识该线程的整数。
- 线程包含在进程内。每个线程都关联一个任务例程，其中程序计数器指向该例程的当前指令。
- 线程具有一个执行栈，用于表示线程的当前执行状态。该栈由函数调用期间形成的多个栈帧组成。每个栈帧包含多个对象，每个对象保存某个寄存器的值。执行栈对于上下文切换至关重要，在上下文切换过程中，当前运行任务被暂停，并与另一个任务进行交换（该替换任务成为新的运行任务）。在上下文切换期间，处理器所使用的所有寄存器的值将被保存到当前运行任务的执行栈中；而替换任务的执行栈（如果非空）则用于恢复其最新的执行状态。
- 线程还具有一个控制块对象，用于保存与调度、资源访问和性能监控相关的线程级信息，例如累计运行时间、阻塞时间、阻塞信号掩码、待处理信号队列以及持有的互斥锁列表。线程控制块还可能包含指向其他线程控制块的指针，以便实现调度和阻塞等动态特性。

• 进程是多个线程的容器。特别地，每个进程都有一个主线程，该线程是一个具有执行入口点的特殊线程。
• 一个进程具有属性PID——一个唯一标识该进程的整数。一个进程可以有多个子进程，并且可能有一个父进程。
• 进程映像由可执行文件对象创建。一旦形成进程映像，它便拥有自己独立于其他进程的虚拟地址空间。
• 进程的虚拟地址空间包含其内每个线程的执行栈以及每个线程的任务例程。
• 进程还具有一个控制块对象，其中包含用于高效进程管理的进程级信息，例如被忽略信号的掩码、待处理信号队列、指向信号处理程序的指针，以及进程所使用的进程级资源（如I/O设备、定时器和消息队列）。

13.2.2 任务状态转换

在任何时刻，一个任务（线程）都处于四种状态之一：就绪、运行、睡眠或阻塞。在讨论状态转换之前，我们首先介绍操作系统用于线程（任务）调度的一些数据结构：
- 一个有序列表是一种数据结构，其中包含零个、一个或多个以特定方式排序的节点。
- 有序列表一端的节点称为头节点，另一端的节点称为尾节点。可以从列表中移除现有节点，也可以向列表中添加新节点。
- 时间有序列表是一种节点按其在列表中的存在时间排序的列表结构。通常，列表的头部是存在于列表中最长时间的节点，而尾部是存在于列表中最短时间的节点。
- 阻塞线程列表 是一个有序列表，其中每个节点代表一个处于阻塞状态的线程。
- 睡眠线程列表 是一个有序列表，其中每个节点表示处于睡眠状态的线程。
- 就绪线程列表 是一个时间有序列表，其中每个节点表示一个处于就绪状态（即准备执行）的线程。

由于多个任务可能以相同的优先级运行，因此在概念上每个优先级级别都有一个就绪线程列表。级别 i 的就绪线程列表仅包含优先级为i的线程。

一个级别为i的就绪线程列表如果至少包含一个节点，并且对于任意j>i，级别j的就绪线程列表均为空，则该列表被称为最高优先级非空就绪线程列表（HNERT）。

图13.5 展示了一个UML状态图，显示了任务（线程）的动态状态转换。它具有以下转换规则：
1. 线程在创建后即进入就绪状态，等待执行。它将被放置在其优先级对应的就绪线程列表的尾部。
2. 在任意时刻，单处理器系统上只有一个运行线程。当当前没有线程正在运行时，符合POSIX.1标准的操作系统将选择HNERT队列头部的线程，将其从HNERT中移除，并主动将执行控制权转移给该线程。
3. 当运行线程的优先级i不再最高——例如，一个优先级高于i的任务变为就绪状态时——该线程会被抢占，并成为第i级就绪线程列表的

头部。随后选择另一个线程作为新的运行线程。（此规则符合SCHED_FIFO调度策略）
4. 当优先级为i的运行线程已用尽其调度策略规定的时间片时，它将变为第i级就绪线程列表的 尾部成员。（此规则符合 SCHED_RR调度策略）随后选择另一个线程作为新的运行线程。
5. 当运行线程调用阻塞函数且相应的阻塞条件为真时，该线程将被阻塞。示例包括获取不可用的信号量或互斥锁、从空管道读取数据、向可用空间小于请求大小的管道写入数据、向已满的消息队列发送消息以及从空的消息队列接收消息。被阻塞的线程将被放入阻塞线程列表中，并选择另一个就绪线程作为新的运行线程。
6. 当一个阻塞线程解除阻塞时，要么阻塞条件已消除，要么被信号中断，该线程将从阻塞线程列表中移除，并成为其优先级对应的就绪线程列表的尾部成员。
7. 当运行线程通过调用睡眠函数主动暂停其执行时，它开始进入睡眠状态并被放入睡眠线程列表中。另一个线程被选为新的运行线程。
8. 当一个睡眠线程唤醒时，可能是请求的睡眠时间已到，也可能是被信号中断，该线程将从睡眠线程列表中移除，并成为其优先级对应的就绪线程列表的尾部成员。
9. 当运行线程调用sched_yield()函数时，它将成为其优先级对应的就绪线程列表的尾部成员，并选择另一个线程作为新的运行线程。
10. 当通过调用 pthread_setschedprio() 修改了运行或就绪线程的优先级时，
- 如果其优先级被提升，该线程将成为对应其新优先级的就绪线程列表的 尾部；
- 如果其优先级被降低，该线程将成为对应其新优先级的就绪线程列表的头部。
11. 当运行或就绪线程的优先级或策略被 pthread_setschedprio() 以外的函数修改时，它将变为对应其新优先级的就绪线程列表的尾部。

13.3 实时操作系统

通用操作系统是管理用户应用程序和计算机硬件资源的系统软件，它定义了规则和编程接口，使程序能够请求操作系统服务并与系统其余部分交互 [47, 69]。具备某些实时特性的通用操作系统可用于软实时应用程序。

然而，对于硬实时系统而言，必须使用实时操作系统（RTOS），以便以有界响应时间响应通常与硬性时间约束（截止时间）相关的外部事件。例如，计算机数控（CNC）机床在底层是逐步运行的：该步进操作是一个周期性任务（例如，周期为1 ms）。在每个步骤中，数控机床必须监控切削头的当前位置，实时计算轨迹，然后驱动切削头到达下一个位置。为了精确地遵循预设的切割模式，数控机床显然需要一个实时操作系统（RTOS）来生成精确计时的脉冲序列以控制切削头的运动。

那么，什么是实时操作系统呢？毫无疑问，实时操作系统首先是一个操作系统，由多个软件子系统组成，其中以内核为核心。根据具体实现的不同，实时操作系统可能提供许多在通用操作系统中常见的服务，例如多任务、优先级、任务抢占、资源共享和任务间通信。

当然，实时操作系统（RTOS）不仅仅是通用操作系统。RTOS 具有专门的调度算法，旨在运行具有软截止时间和/或硬截止时间的实时应用。因此，RTOS 的关键特性是其对事件的响应时间应该是确定性的（或可预测的）。换句话说，RTOS 应提供可靠的机制，例如实时信号、抢占式调度和非阻塞进程间通信，以实现确定性响应 [43, 57]。

图13.6 illustrates a potential execution path in response to an event. Let us use 图13.6 to examine those factors that may affect the response time of a system to an external event:

• 硬件设备X的事件响应时间 是指从中断请求被提出到设备X的服务器任务完全处理该请求之间的时间间隔。它包括中断延迟、设备X的中断服务程序(ISR)的执行时间、调度延迟以及设备X的服务器任务的执行时间。
• 中断延迟 指的是从中断请求发出到相应ISR的第一条指令开始执行之间的时间间隔。部分中断延迟可能是由于软件禁用了中断，如图13.6所示，或正在执行更高优先级设备的ISR所致。这部分完全由系统设计者控制，任何实时操作系统都无法弥补不良的设计。良好的做法是尽量缩短禁用中断的代码段。此外，硬件设备的优先级应合理设计，以使关键设备的中断延迟得到合理的优化。
• 中断延迟的最后一部分是由上下文切换引起的，在此过程中，当前执行上下文需要被保存并切换到另一个任务（在本例中为中断服务例程）。上下文切换时间是实时操作系统的一个重要性能指标。
• 实时操作系统为中断服务例程（和信号处理程序）提供默认实现。用户可以修补现有的中断服务例程或安装新的中断服务例程（或信号处理程序）。对于默认中断服务例程（信号处理程序）的执行时间，由实时操作系统负责；对于用户自己的部分，由用户负责。
• 调度延迟 是指服务器任务已就绪但尚未开始执行的时间间隔。它可能由高优先级任务的执行、上下文切换以及调度开销引起。调度开销指的是内核调度器的执行时间。虽然任务抢占主要在设计时（通过任务优先级分配）确定，但实时操作系统有责任减少调度开销。
• 服务器任务的执行时间取决于任务例程的长度。任务的代码（包括中断服务例程）可能会调用系统调用来请求各种操作系统服务。系统调用的响应时间是实时操作系统的另一个重要性能指标。此外，任务可能与其他任务进行通信；每次任务间通信都会引入通信延迟。

总之，实时操作系统通常通过确定性的响应来实现
- 支持抢占式优先级调度：高优先级任务总是抢占低优先级任务，无论用户任务或系统任务。
- 在上下文切换时间、调度开销和系统调用方面提供有界延迟。有界延迟意味着对延迟具有可测量的保证，即响应时间应为
- 短且可预测：上下文切换时间、调度开销以及系统调用的完成应在已知延迟范围内且较短。
- 具有低抖动：在所有可能情况下，响应时间（针对上下文切换、调度开销以及每种系统调用）的方差应非常小。例如，一个系统调用平均可在10毫秒内响应，但可能会有高达20毫秒的峰值。最坏情况值通常用于可调度性分析。
- 提供高效的中断服务例程：默认中断服务例程（信号处理程序）的执行时间应较短且有界。
- 支持确定性同步：多个任务可以在可预测的时间内进行通信。

最广泛采用的实时操作系统包括RTLinux、Windows CE、LynxOS、VxWorks和 QNX等[24]。例如，VxWorks是一种商业实时操作系统，支持具有256个优先级级别的抢占式优先级调度，以及信号量、消息队列和高速任务间通信。VxWorks适用于多种处理器平台，包括x86、PowerPC、ARM、MIPS、Pentium和SPARC。QNX Neutrino [8]被广泛用作许多嵌入式实时应用的基础，如汽车机电部件、医疗仪器、国防系统和核电站。QNX基于微内核架构，如图13.7所示，这种架构使系统能够缩小到非常小的尺寸，同时仍提供多任务、抢占式调度和快速上下文切换。QNX Neutrino可在多种现代处理器平台上运行，包括PowerPC、x86、MIPS、ARM和 XScale。

我们已经知道，实时操作系统仅代表嵌入式软件的一种架构类型。对于规模小、功能有限或仅有软定时约束的实时嵌入式系统，不一定需要使用实时操作系统。如果在任务关键系统中使用实时操作系统是最佳选择，那么为了在市场上可用的实时操作系统中做出“明智”的选择，您可能需要考虑诸如实时特性（有界延迟）、可移植性（处理器支持）、可扩展性（操作系统内存使用）、支持（开发工具、设备驱动程序和板级支持包）以及预算限制等因素。

13.4 POSIX实时调度策略

在第13.1.2.1节中，我们讨论了优先级原则和抢占原则，这些原则适用于就绪任务具有不同优先级的情况。调度策略的目的是为具有相同优先级的任务定义公平规则（例如，SCHED_FIFO 和 SCHED_RR）或具有有界执行预算的任务（例如，SCHED_SPORADIC）。

13.4.1 先进先出调度策略

由于SCHED_FIFO（“先进先出”）调度策略仅适用于具有相同优先级的任务调度，我们在此重点关注优先级为k的就绪线程列表——即具有优先级k的任务。

假设第 k 级就绪线程列表包含以下线程：[T1, T2, …, Tn]。我们用 T0 表示具有相同优先级 k 的运行线程。根据就绪线程列表的定义，如果 1 ≤i<j ≤ n，则 Ti 在列表中的时间必须比 Tj 更长。

对于位于级别 k 就绪线程列表中的任务，SCHED_FIFO 策略规定，任何任务 Ti 都不能被 Tj（j>i）抢占。换句话说，任务 Ti+1 只有在其运行至完成之后，才能被调度执行。

图13.8 给出了一个示例，其中系统由三个具有相同优先级的周期性任务组成。

作业 J11 在时间0 就绪（被释放）。由于 T1 是就绪列表中唯一的任务，它成为运行线程。在时间1，作业 J21 被释放并添加到就绪列表中。在时间2，J11 完成，J21 成为新的正在运行的作业。

同时，作业 J31 在时间2 被释放并添加到就绪列表中。在时间4，J21 完成，J31 成为新的正在运行的作业。在时间6，作业 J12 被释放并添加到就绪列表中。作为练习，您可以继续此分析。有一点是明确的：任何稍后被释放的作业从未抢占过较早被释放的作业。

注意，作业 J14的截止时间在时间24处被打破。

13.4.2 时间片轮转调度策略

与SCHED_FIFO类似，SCHED_RR（轮转）调度策略仅适用于调度具有相同优先级的任务。对于实现SCHED_RR策略的操作系统，时间片的长度（也称为时间片）由POSIX函数sched_rr_get_interval()返回。

SCHED_RR 策略规定：（1）每个就绪线程列表中的所有任务按照其顺序依次被调度；（2）当需要选择一个新的运行线程时，如果级别 k 的就绪线程列表为 HNERT，则将头部线程从列表中移除并成为运行线程；（3）一个运行线程一旦用完其时间片，即成为其优先级对应就绪线程列表的尾部线程。

图13.9 给出了一个示例，其中系统由三个具有相同优先级的周期性任务组成。

作业J11在时间0被释放并成为正在运行的作业。在时间1，作业J21被释放并加入就绪列表。从该时刻开始，两个作业J11和J21,将轮流执行。在时间2，作业J31被释放并同样加入轮转调度。一旦某个作业运行完成，即退出轮转调度。

SCHED_RR 策略实际上提供了一种分时机制，确保当存在其他相同优先级的线程时，某个任务不会独占处理器。这种机制可以通过使用时钟（定时器）中断来实现。

还请注意，如果一个系统具有不同优先级的任务，则就绪线程列表上的任务轮转调度可能会被更高优先级任务的执行所抢占（“中断”）。

13.4.3 偶发服务器调度策略

调度策略 SCHED_SPORADIC （偶发服务器）允许任务在运行时更改其优先级。

我们关注使用 SCHED_SPORADIC 调度策略的特定线程Ti。Ti的调度参数如下所示：
- 一个正常优先级，表示为 μ；
- 一个低优先级，表示为 ω，其中 ω< μ；
- 一个补充周期，用p表示；
- 一个初始执行预算，表示为e。

线程 Ti 在其创建时获得初始执行预算 e。当 Ti 处于运行状态时，预算值 e 将被消耗。

当 e> 0 时，线程 Ti 的有效优先级为 μ，否则为 ω。根据其有效优先级，当 Ti 处于就绪状态时，它应位于第 μ 级就绪列表或第 ω 级就绪列表中。

Ti的执行预算可以通过补充动作进行补充。每次补充动作由 〈t， v〉定义，其中t是执行此补充动作的时间， v是待补充的数量。

Ti的调度行为受以下规则约束：
1. 每次将Ti放置到级别μ就绪列表的尾部时，该时间点由 τ记录。τ称为Ti的最新激活时间。在Ti创建时，其具有 τ= 0。 τ随时间变化。
2. 当Ti以优先级μ运行时，其预算以每单位执行时间消耗1的速度被消耗。
3. 当以优先级μ运行的Ti的预算变为0时，它将变为级别ω就绪列表的尾部。操作系统调度一个补充动作 〈t, v〉，其中t = τ+ p，且v等于自最新激活时间 τ以来已消耗的预算。如果t早于当前时间，则立即执行该补充动作。
4. 当以优先级μ运行的Ti变为阻塞线程时，操作系统调度一个补充动作 〈t, v〉，其中t = τ+ p，且v等于自最新激活时间 τ以来已消耗的预算。如果t早于当前时间，则立即执行该补充动作。
5. 当以优先级μ运行的Ti被抢占时，它将变为级别μ就绪列表的头部。在这种情况下， τ不发生变化。
6. 当Ti位于级别ω就绪列表的头部且该列表为HNERT时，它将成为运行线程。当Ti以优先级ω运行时，其预算保持不变。
7. 当到达执行补充动作〈t, v〉的时间（即当前时间不早于t）时，Ti的预算将被更改： e = e + v。如果Ti的有效优先级为ω，则将其更改为μ，并且Ti变为级别μ就绪列表的尾部。

例如，考虑一个由两个任务（线程）T1和T2组成的系统（假设使用实时操作系统时，系统任务的执行开销可以忽略不计）。这两个任务共享一个由信号量保护的互斥资源。

如图13.10所示，任务T1的释放时间、周期、执行时间需求和截止时间分别为 5、120、35 和 80；任务T2的任务参数分别为 0、60、20 和 60。任务T2具有固定的优先级 50；任务T1采用 SCHED_SPORADIC 策略，其参数如下：
- μ= 60;
- ω= 40;
- p= 30; 和
- e= 10.

下面解释 图13.10 中给出的调度场景：
1. 在时间0系统启动时，线程 T2处于就绪状态，并成为运行线程。在时间2.5，T2请求并成功获取了资源。我们还有 τ= 0。
2. 在时间5，线程 T1变为就绪状态。它抢占了T2的执行，并成为新的运行线程。
3. 从时间5到10，T1以优先级60执行。其执行预算在时间10减少至5。
4. 在时间10，T1请求当前被T2锁定的资源。T1被阻塞并放入阻塞线程列表。操作系统调度一个补充动作 〈t, v〉，其中t= τ+ p= 0+ 30= 30，以及 v= 5（即从时间0以来已消耗的预算）。此时，T2是唯一处于就绪状态等待执行的线程，因此它成为运行线程。
5. 从时间10到15，T2执行。
6. 在时间15，T2释放资源，导致T1从阻塞列表中被移除，并成为60级就绪列表的尾部。此时，我们有 τ= 15。此外，T1立即抢占T2并成为运行线程。
7. 从时间15到20，T1以优先级60执行。其执行预算在时间20变为0。
8. 在时间20，由于已消耗全部预算，T1成为40级就绪列表的尾部。操作系统调度一个补充动作 〈t, v〉，其中t = τ+p = 15+ 30= 45，且 v= 5为自时间15以来已消耗的预算。此时，T2是 HNERT的头部，并成为运行线程。
9. 从时间20到25，T2执行。
10. 在时间25，T2请求当前被T1锁定的资源。T2被阻塞并放入阻塞线程列表。此时，T1是唯一处于就绪状态的线程，因此成为运行线程。
11. 从时间25到30，T1以优先级40执行。其执行预算保持为0。
12. 在时间30，操作系统执行补充动作 〈30, 5〉，T1的预算变为5，其优先级恢复为60。同时，我们有 τ= 30。
13. 从时间30到35，T1以优先级60执行。其执行预算在时间35变为0。在时间32.5，T1释放资源，导致T2从阻塞列表中被移除，并成为50级就绪列表的尾部。
14. 在时间35，由于已消耗全部预算，T1成为40级就绪列表的尾部。操作系统调度一个补充动作 〈t, v〉，其中t = τ+p = 30+ 30= 60，且 v= 5为自时间30以来已消耗的预算。此时，T2是HNERT的头部，并成为运行线程。
15. 从时间35到40，T2执行。
16. 在时间40，T2释放资源并运行完成。此时，T1是唯一处于就绪状态的线程，因此成为运行线程。
17. 从时间40到45，T1以优先级40执行。其执行预算保持为0。
18. 在时间45，操作系统执行补充动作 〈45, 5〉，T1的预算变为5，其优先级恢复为60。同时，我们有 τ= 45。
19. 从时间45到50，T1以优先级60执行。其执行预算在时间50变为0。
20. 在时间50，由于已消耗全部预算，T1成为40级就绪列表的尾部。操作系统调度一个补充动作 〈t, v〉，其中t = τ+p = 45+ 30= 75，且 v= 5为自时间45以来已消耗的预算。此时，T1是唯一的就绪线程，并成为运行线程。
21. 从时间50到55，T1以优先级40执行。其执行预算保持为0。
22. 在时间55，T1运行完成。
23. 在时间60，T2的第二个作业被释放并开始运行。

13.5 其他实时调度策略

13.5.1 最小松弛度优先

任务的松弛度定义为剩余时间（截止时间之前的时间）与完成该任务仍需时间之间的差值。更正式地，给定一个任务Ti=(pi,ri,ei,di)，其松弛时间定义为
(di − t)− e′i,
其中t是自当前周期开始以来经过的时间，e′i ≤ ei是其剩余的执行时间需求。

松弛度是衡量任务调度灵活性的指标。若一个任务的松弛度为t，则意味着即使该任务延迟t个时间单位，仍可满足其截止时间。松弛度为零表示该任务必须立即开始执行，否则将有无法满足截止时间的风险。

最小松弛度优先调度策略，也称为最少松弛度优先或最少松弛时间调度，是一种动态优先级方法，其中松弛度较小的任务具有更高优先级。显然，松弛度最小的任务具有最高优先级。

为了实现这一策略，操作系统调度器需要持续监控所有就绪作业的松弛度，并将其与正在运行的作业的松弛度进行比较。每当作业之间松弛度的相对顺序发生变化时，调度器就会重新分配作业的优先级，允许具有相同松弛度的作业以轮转方式执行。

显然，由于持续计算带来的运行时开销较大，而过多的循环调度会引发不必要的上下文切换开销。在实际中，操作系统可能采用一种非严格方法，即仅在作业被释放或完成时才检查就绪作业的松弛度。

图13.11 给出了一个符合非严格最小松弛度优先策略的调度示例。在 图13.11底部的表格给出了对应“关键”时间点的作业松弛度。

系统启动之初，三个任务的第一个作业被释放，它们各自的松弛度分别为2.5、7和9。
由于J11的松弛度最小，因此获得最高优先级，并在1.5时刻运行完成。在1.5时刻检查就绪作业的松弛度，J21的松弛度最小。因此，J21获得最高优先级并运行至时间4，此时作业J12被释放。这提供了一个重新检查就绪作业松弛度的机会。新释放的作业J12具有最小的松弛度，因此获得最高优先级，并在5.5时刻运行完成。作为练习，请跟踪该场景，观察作业松弛度如何变化，以及这些变化如何影响三个任务的调度。

13.5.2 最早截止时间优先

另一种常见的实现方法称为最早截止时间优先（EDF），这也是一种动态优先级调度策略。EDF策略要求截止时间更早的任务（作业）具有更高优先级。显然，截止时间最早的任务具有最高优先级。

图13.12 给出了一个基于EDF的调度示例。在图13.12底部的表格给出了相应“关键”时间点的作业截止时间。

系统启动初期，两个任务的首个作业被释放，其各自的截止时间为2和5。由于J11的截止时间更早，因此获得更高优先级，并在时间1运行完成。在时间1，J21是唯一的就绪作业；它运行至时间2，此时作业J12被释放。由于J12的截止时间更早，被调度执行，并在时间3完成。J21在时间3恢复执行，并持续运行至时间5，此时作业J21完成，同时作业J22被释放。与此同时，作业J13在时间4被释放，截止时间为6。在时间5，J13开始执行，因为它比作业J22具有更早的截止时间。

在时间8发生了一个有趣的情况，此时作业J15和J22具有相同的截止时间。由于它们具有相同的优先级，操作系统以轮转方式调度它们。作业J15在时间10完成；然而，作业J22,未能满足其截止时间。

13.5.3 截止时间单调分配调度

截止时间单调分配方法是一种静态优先级调度策略，其中任务的优先级根据设计时已知的截止时间分配：截止时间更早的任务被赋予更高优先级。与EDF方法不同，截止时间单调分配中的任务优先级是固定的。

图13.13 给出了基于截止时间单调分配的调度示例。根据它们的截止时间，任务 T2 具有最高优先级，任务 T3具有最低优先级，而任务 T1的优先级在中间。

系统启动初期，作业J11被释放并开始运行。在时间15，J21被释放，并抢占了J11。作业J 31 在时间20被释放，并成为其优先级就绪列表的尾部。当J21在时间25完成时，由于J11具有比J31更高的优先级，因此它成为正在运行的作业。在时间35，J11完成，J31开始运行。

13.5.4 速率单调分配调度

速率单调分配方法也是一种静态优先级调度策略[49, 65],，其中任务的优先级根据设计时已知的周期分配：为具有更短周期（即更高频率）的任务分配更高优先级。与截止时间单调分配类似，速率单调分配中的任务优先级是固定的。

图13.14 给出了基于速率单调分配的调度的一个示例。根据它们的周期，任务 T1具有最高优先级，任务 T3具有最低优先级，任务 T2的优先级居中。

系统启动之初，三个作业J11, J21,和J 31同时被释放。J11开始运行，因为它具有更高优先级。
在时间7 J11完成之后，J21开始运行，因为它比J31具有更高优先级。在时间19，J21完成， J31开始运行。在时间24，J12,（任务T1,的第二个作业）变为就绪并开始运行。

第16章中介绍了更多基于速率单调分配的可调度性分析原理。