嵌入式系统概论-06-嵌入式软件系统

本文主要内容来自 SpriCoder的博客，更换了更清晰的图片并对原文的疏漏做了补充和修正。

嵌入式软件概述

嵌入式软件开发路线图

系统越来越复杂，嵌入式系统的软件开发逐渐变成了软件专家的工作。
对电子硬件很了解，也愿意做一些和硬件密切相关的工作。
最近 10-15 年，伴随着嵌入式软件规模和复杂性的爆炸性增长，专门的软件开发团队进入了视野。软件团队在不断壮大，但这种增长不仅仅是因为完成所需的代码。嵌入式软件团队中有不同领域的专家，包括网络、用户界面设计、硬件设备、传统嵌入式软件设计等方面。

嵌入式软件与桌面软件的对比

内存

有限，影响编程语言的选择以及开发工具的使用（比如编译器优化）。

CPU 处理能力

成本和功耗的考虑，ES 不得不采用保守的设计方案，其中的 CPU 往往只是恰好满足要求。

操作系统

OS（Windows/Linux）、RTOS、专有 OS 或裸机

实时性

实时系统不一定会运行得很快，但一定是可预测的，通常的术语叫做确定性
实时性的要求对于 OS 的选择和程序设计都有影响

开发流程

ES 往往没有足够的资源进行软件开发。交叉开发对于工具的选择有很大影响。
开发过程也不同，编辑/编译/调试的循环是一样的，但执行程序这一步却非常复杂，需要把代码转移到目标机上或者在某种环境下运行。

执行流程

多数嵌入式设备从开机开始就会运行某个程序，该程序会一直运行到系统关机。这个程序可能存储在 ROM，也可能是从非易失性存储器转移到 RAM 中执行。

每一个嵌入式设备都是不同的

可能是技术层面的：不同的 CPU 架构、内存、外设、应用程序和操作系统
也可能是商业运作层面的，比如手机开发、生产的商业模式就和核磁共振扫描仪完全不同。

嵌入式软件工具和组件

与桌面软开发一样，嵌入式软件工程师需要运用工具来构建和测试软件。同时，也很可能会引入可重用的软件组件

开发工具

从表面上看，嵌入式软件的开发过程和桌面软件很像：编译代码模块，然后在调试器的控制下执行。然而，并不这么简单，有着显著的不同。

往往是使用交叉编译器来进行嵌入式软件的开发。
有时候嵌入式应用中会直接包含小部分的汇编代码：出于对性能的考量。
嵌入式链接器除了将多个对象模块和函数库例程整合在一起以外，链接器还负责在内存中正确定位代码和数据。嵌入式系统的内存映射十分复杂，对于精确性的要求也十分严格。链接器必需能够灵活地应对这些要求。
嵌入式调试器并不是一个单一的组件，而是一系列对应不同运行环境的工具。借由在本地或者指令集模拟器中运行代码，代码可以仅在宿主机上运行。调试器也可以和一个目标板相连接（JTAG 或其他方式，如以太网），并执行代码。
其他一些更有针对性的工具，典型的选项包括分析实时性能、代码执行时设备功耗情况的分析器。

软件组件

最简单和显而易见的可重用的软件组件是库。一些库是由编译器提供的，嵌入式编译器提供的库应当是适合嵌入式环境的：可以重入、可以被存储在 ROM 中。（不会使用 printf：会有问题）

其他可用的库，特别是针对 C++ 的库，如标准模板库 STL。这些库可能并不适合嵌入式应用，在使用时要多加小心。

与硬件交互是难点之一。在 OS 内部设备驱动提供了这样的接口

ES 的互联性不断提高，需要不同的网络支持，TCP/IP 或总线 CAN2C，其他网络技术 SNMP、Zigbee、Bluetooth、WiFi 和 USB。最重要的是应该检查有效性，确保符合标准，并能和其他系统互通互联。

嵌入式设备对于有组织的数据存储是有需求的，比如能够应对电源故障和支持多线程。

LCD（往往是触摸式的）成本减低让其能够被应用到嵌入式设计中。软件于是迎来了一项挑战：支持复杂的图像和用户界面。

软件如何影响硬件设计

谁设计硬件？

可能有同时负责软件和硬件的嵌入式工程师
更有可能拥有两个团队：只有少数人同时掌握两项知识
有关硬件的决定可能会对软件产生持久影响

软件/硬件的权衡

微处理器选择：可能会影响软件效率

内存大小和混合：

延迟承诺是可取的
ROM/RAM 互换性很有用

外围设备实现：有时可通过软件替换。例如：计时器

调试硬件

在线仿真器：不广泛使用，
监控调试器：
1. 需要沟通渠道，额外的性能消耗
2. 需要 RAM/ROM 交换
片上调试：
1. 需要板载连接器，相当于协议转换器
2. 需要 RAM/ROM 交换

自检支持

I/O 电路：“回送”可能有用
板载开关：适用于配置或模式选择
状态显示：提供对用户额外的信息
可能是字符或只是 LED
LED 至少可以具有 3 种状态：开，关，闪烁

嵌入式系统软件架构

软件分层

为何要为实时系统建立模型

辅助测试和完善最终系统
更重要的是，模型利用它所知的系统属性来描述整个系统，并能够被用于对系统特性的进一步研究
实时工程师使用程序模型来开发软件和硬件，以便能将整个实时系统全盘考虑
模型使得工程师能够预测程序的运行，从而满足系统的性能需求和功能需求

模型间的差异

一些模型易于编写，但调试不易
另一些难于编写，但调试容易
一些模型使得程序运行得更快，但需要付出更多内存资源消耗的代价
一些鲁棒性更好，但维护很简单的模型

嵌入式系统的可视化程序模型

实时系统有两种基本的程序模型：

将实时应用视为单个执行线程
将实时应用视为多个执行线程

取决于需要构建什么类型的系统

单线程程序模型优缺点

优点：

编程和再编程非常快速简单
改变系统响应的特性的同时，往模型上添加新功能插件也相当容易

缺点：

在于应用领域的限制
难以做到安全地再编程
很难应用到不同行为或不同环境的运行系统中去。

多线程程序模型的优缺点

优点：

允许将系统工作划分为几个逻辑阶段，然后编写相互独立的程序来处理各自的工作。
所有处理过程并行。
如果有更高吞吐量的需求，工程师可以在任务中引入新的通信和协作模型

缺点：可能引入资源竞争，也就是不得不付出代价

嵌入式软件体系结构概述

轮询
有限状态机
带中断的轮询
仅有中断
功能队列调度
实时操作系统（RTOS）

轮询

//Round Robin / Control Loop
//Everything is a function call from the main loop
void main(void) {
   while(TRUE) {
      if (device_A requires service)
         service device_A
      if (device_B requires service)
         service device_B
      if (device_A requires service)
         service device_A
      if (device_C requires service)
         service device_C
      if (device_A requires service)
         service device_A
      // ... and so on, making sure high-priority device_A always serviced on time
   }
}

可确定性：如果有任务不能确定时间，会导致其他所有的任务都被影响到。而这不符合嵌入式的实时性要求。

轮询的特点：

优先级：无，一切按顺序进行。
响应时间：所有任务的总和。
变更的影响：重大。改变执行任务时间或添加任务会影响所有其他任务。
简单，没有共享数据问题：线性并行执行

Arduino - 按下按钮时打开 LED

const int LED = 13; // the pin for the LED
const int BUTTON = 7; // the input pin where the
// pushbutton is connected
int val = 0; // val will be used to store the state
// of the input pin
void setup() {
   pinMode(LED, OUTPUT); // tell Arduino LED is an output
   pinMode(BUTTON, INPUT); // and BUTTON is an input
}
void loop(){
   val = digitalRead(BUTTON); // read input value and store
   it
   // check whether the input is HIGH (button pressed)
   if (val == HIGH) {
      digitalWrite(LED, HIGH); // turn LED ON
   }else{
      digitalWrite(LED, LOW);
   }
}

Arduino - Watchdog

#include <avr/wdt.h>
#define TIMEOUT WDTO_8S // predefine time, refer avr/wdt.h
const int ledPin = 13; // the number of the LED pin

void setup(){
   // disable the watchdog
   //wdt_disable();
   pinMode(ledPin, OUTPUT);
   // LED light once after start or if timeout
   digitalWrite(ledPin, HIGH);
   delay(1000);
   // enable the watchdog
   wdt_enable(TIMEOUT);
}
void loop(){
   // process runing
   digitalWrite(ledPin,LOW);
   delay(9000); //if timeout trig the reset
   //feed dog
   wdt_reset();
}

有限状态机

while(1) {
   switch(state) {
      case IDLE:
         check_buttons();
         LEDisplay_hex(NUM1);
         if (BUTTON1 | BUTTON2 | BUTTON3)
            state = SHOW;
         break;
      case SHOW:
         NUM1 = 0;
         if (BUTTON1) NUM1 += 0x0001;
         if (BUTTON2) NUM1 += 0x0010;
         if (BUTTON3) NUM1 += 0x0100;
         state = IDLE;
         break;
   }
}

与轮询类似，但只有当前状态被执行。
每个状态决定下一个状态（非顺序执行）。
优先级：每个状态确定下一个状态的优先级。
响应时间：所有任务的总和。
变更的影响：重大。更改任务的执行时间或添加任务会影响所有其他任务。
简单性：没有共享数据问题。

带有中断的轮询

BOOL flag_A = FALSE; /* Flag for device_A follow-up processing */
/* Interrupt Service Routine for high priority device_A */
ISR_A(void) {
   ... handle urgent requirements for device_A in the ISR,
   then set flag for follow-up processing in the main loop ...
   flag_A = TRUE;
}
void main(void) {
   while(TRUE) {
      if (flag_A)
         //中断任务优先
         flag_A = FALSE
         //... do follow-up processing with data from device_A
      if (device_B requires service)
         service device_B
      if (device_C requires service)
         service device_C
      //... and so on until all high and low priority devices have been serviced
   }
}

优先级：中断优先于主循环，中断的优先级也是如此
响应时间：所有任务的总和以及中断执行时间
更改的影响：对于中断服务程序而言意义不大。与轮询作为主循环相同
共享数据-必须处理与中断服务程序共享的数据
MCU 中使用最多的

仅有中断

1
2
3

SET_VECTOR(P3AD, button_isr);
SET_VECTOR(TIMER1, display_isr);
while(1) {}

如果 ISR 过多，可能会有问题
如果高优先级的中断执行所需的时间比低优先级的中断所需的时间长，那么某些中断将被错过，或者您需要处理嵌套中断。
优先级：中断优先
响应时间：中断执行时间
变化的影响：对于中断服务程序而言意义不大。
共享数据：必须处理与中断服务程序共享的数据

函数队列调度

函数指针被添加到队列中。
主循环在队列中循环并执行任务。
任务或中断将新任务添加到函数队列中。
最坏情况时机 The worst case timing

#define MAX_TASKS 20
typedef int (*FuncPtr)();
FuncPtr tasks[MAX_TASKS] int current_task = 0;
void add_task(FuncPtr func) {
	int n;
	for (n = current_task + 1; n < MAX_TASKS - 1; n++) {
		if (tasks[n] == NULL) {
			tasks[n] = func;
			return;
		}
	}
	for (n = 0; n < current_task; n++) {
		if (tasks[n] == NULL) {
			tasks[n] = func;
			return;
		}
	}

	id display_task() {
		LEDisplay_hex(NUM1);
		add_task(button_task);
	}
	void button_task() {
		check_buttons();
		NUM1 = 0;
		if (BUTTON1)
			NUM1 += 0x0001;
		if (BUTTON2)
			NUM1 += 0x0010;
		if (BUTTON3)
			NUM1 += 0x0100;
		add_task(display_task);
	}

	main() {
		LEDisplay_init();
		LEDisplay_clear();
		init_buttons();

		add_task(button_task);

		while (1) {
			if (tasks[current_task] == NULL) {
				;
			} else {
				(*tasks[current_task])();
				tasks[current_task] = NULL;
			}
			current_task++;
			if (current_task >= MAX_TASKS)
				current_task = 0;
		}
	}

优先级：中断优先。任务按顺序执行
响应时间：最长任务的执行时间
变更的影响：低。中断管理优先级功能。队列管理较低的优先级。
共享数据：必须处理与中断服务程序共享的数据

函数队列优化

// 添加时间队列
typedef int(*FuncPtr);

typedef struct {
	long timer;
	int status;
	FuncPtr;
} Task;

Task task_list[MAX_TASKS];

// 添加任务优先级
typedef int(*FuncPtr);

typedef struct {
	int priority;
	FuncPtr;
} Task;

Task task_list[MAX_TASKS];

抢占式多任务或多线程

在这种类型的系统中，一段低级代码基于定时器（连接到中断）在任务或线程之间切换。这是系统通常被认为具有“操作系统”内核的级别。根据需要多少功能，它或多或少地引入了管理概念上并行运行的多个任务的复杂性。

要访问共享数据，必须通过某种同步策略来控制，例如消息队列，信号量或非阻塞同步方案。

由于这些复杂性，组织通常使用实时操作系统（RTOS），从而使应用程序程序员可以专注于设备功能而不是操作系统服务。

内核分类

实时内核

微内核

微内核是实时操作系统的逻辑升级。通常的安排是操作系统内核分配内存并将 CPU 切换到不同的执行线程。用户态进程实现文件系统、网络接口等主要功能。

一般来说，微内核在任务切换和任务间通信快速时成功，而在它们缓慢时失败。

单内核

具有复杂功能的相对较大的内核适用于嵌入式环境。

示例：嵌入式 Linux 和 Windows CE

尽管硬件成本增加，但这种嵌入式系统却越来越受欢迎，尤其是在功能更强大的嵌入式设备（例如无线路由器和 GPS 导航系统）上。原因如下：

提供了通用嵌入式芯片组的端口。
它们允许将公共可用代码重复用于设备驱动程序，Web 服务器，防火墙和其他代码。
开发系统可以从广泛的功能集开始，然后可以将该发行版配置为排除不需要的功能，并节省其消耗的内存开销。
许多工程师认为，在用户模式下运行应用程序代码更可靠且更容易调试，从而使开发过程更容易且代码更可移植。
需要可以保证更快响应的功能通常可以放在硬件中。

实时操作系统 RTOS

通用操作系统模型（和 Linux 相似）

操作系统

操作系统控制资源：

谁获得 CPU；
I/O 何时发生；
分配了多少内存；
流程如何通信。

最重要的资源是 CPU 本身：由调度程序控制的 CPU 访问。

RTOS 和通用操作系统（GPOS）

相似的功能：

多任务级别
软件和硬件资源管理
为应用提供基本的 OS 服务
从软件应用抽象硬件

RTOS 从 GPOS 中分离出来的不同功能

嵌入式应用上下文中具有的更好的可靠性
满足应用需要的裁剪能力
更快的特性
减少内存需求
为实时嵌入式系统提供可裁剪的调度策略
支持无盘化嵌入式系统，允许从 ROM 或 RAM 上引导并运行
对不同硬件平台具有更好的可移植性。

RTOS 的特性

可靠性
可预测性、确定性
表现
紧凑
可扩展性

实时操作系统

为什么要实现 RTOS？

灵活性
响应时间

一个个实时系统（RTS）是指计算的正确性不仅取决于程序的逻辑正确性，也取决于结果产生的时间，如果系统的时间约束条件得不到满足，将会发生系统出错。

术语

TODO：调整字体

确定性（Determinism）：如果一个系统始终会为某个已知输入产生相同的输出，则该系统是确定性的。非确定性系统的输出具有随机变化特征。
截止时限（Deadline）：截止时限就是必须完成某项任务的有限时间窗口。指明计算何时必须结束。
服务质量（QoS，Quality of Service）：指一个网络的整体性能，包括带宽、吞吐量、可用性、抖动（jitter）、延迟和错误率等因素。
到达时刻：任务实例所属任务的起始时刻称为该任务实例的到达时刻。
释放时刻：任务实例被置为就绪态的时刻称为该任务实例的释放时刻。
硬实时（Hard real-time）软件系统有一组严格的截止时间，且错过一个截止时间就会认为系统失败。硬实时系统的示例包括：飞机传感器和自动驾驶系统、航天器和行星探测器。
软实时（Soft real-time）系统会试图满足截止时间要求，但如果错过了某个截止时间也不会认为系统失败。但是，在这样一个事件中，软实时系统可能会降低其服务质量以改进其响应能力。软实时系统的示例包括：用于娱乐的音频和视频传输软件（延迟是不可取的，但不是灾难性的）。
准实时（Firm real-time）系统会将截止时间之后交付的信息/计算视为无效。与软实时系统一样，准实时系统在错过某个截止时间后不会认为系统失败，并且如果错过了某个截止时间，准实时系统可能会降低服务质量（QoS）。准实时系统的示例包括：财务预测系统、机器人装配线。

任务的周期

周期任务：周期任务是指按一定周期达到并请求运行，每次请求称为任务的一个任务实例，任务实例所属任务的起始时刻称为该任务实例的到达时刻，任务实例被置为就绪态的时刻称为该任务实例的释放时刻。
偶发任务：在偶发任务中，虽然其任务实例的到达时刻不是严格周期的，但相邻任务实例到达时刻的时间间隔一定大于等于某个最小值，即偶发任务的各任务实例按照不高于某个值的速率到达。因此在实际应用中，偶发任务经常被当作周期任务进行处理，其周期为相邻任务实例到达时刻的最小时间时隔。
非周期任务：非周期任务是指随机到达系统的任务。

基本单位

实时操作系统的基本组成部分是进程。
由于没有主循环，因此可以轻松添加新进程或删除过时的进程。
RTOS 根据进程的优先级安排运行时间。

调度程序

RTOS 的调度程序用来跟踪每个进程的状态，并确定应该运行的进程。
调度基本单位是进程，调度是通过有限状态机完成的

时序约束

执行计算以符合外部时序约束。

截止时间频率：

周期性
非周期性的

截止时间类型：

硬性：未能按时完成会导致系统故障
软性：未按时完成进程会导致响应降低

偶发进程：具有一定时钟周期的进程

进程时序的规范

释放时间：进程处于就绪态的时间
截止时间：进程必须结束的时间

释放时间和截止时间

非周期性的进程
紫色表示占用 CPU 的时间，紫色右侧是结束时间

周期性进程
截止时间默认和周期时间相同

周期性进程
比较复杂，时序的截止时间小于其周期性

进程速率要求

周期：进程激活之间的间隔。
速率：周期的倒数。
启动速率可能高于周期：一次运行多个副本。

时间冲突

如果流程没有在截止时间之前完成，会发生什么？

硬截止时间：如果错过了系统就会失败。
软截止时间：用户可能会注意到，但系统不一定会出现故障。

我们希望通过自己的调度算法来尽可能避免这种问题

示例：航天飞机软件错误

航天飞机的首次发射由于软件计时错误而延迟：

主控制系统 PASS 和备用系统 BFS。
BFS 无法与 PASS 同步。
更改为一个例行增加的延迟，这会延迟开始时间的计算。
\(\frac{1}{61}\) 的概率发生计时问题

进程执行特征

进程执行时间 T_i：

没有抢占的执行时间。
可能的时间单位：秒、时钟周期
在某些情况下，最坏、最好情况的执行时间可能会有用。

变化来源：

数据依赖性。
内存系统。
CPU 管道。

主备冗余、多机热备

利用率

CPU 利用率：CPU 执行有用的工作的比率

通常在没有调度开销的情况下进行计算

\[ U = \frac{\text{CPU time for userful work}}{\text{total available CPU time}} = \frac{\sum\limits_{t_1\leq t \leq t_2}T(t)}{t_2 - t_2} = \frac{T}{t} \]

进程状态

进程可以处于以下三种状态之一：

在 CPU 上执行；
准备执行；
等待数据。

调度问题

我们可以在所有截止日期之前完成吗？在所有情况下都必须能够按时完成进程。
我们需要多少个 CPU 才能按时完成进程？

嵌入式与通用调度

调度工作尝试避免使 CPU 访问过程变得空闲：公平=访问 CPU。
嵌入式系统必须符合所有截止时间：低优先级进程可能长时间不会运行。

OS 进程管理

操作系统需要跟踪：进程优先级、时序状态、进程激活记录
进程可以被创建：系统启动前静态、在执行期间动态：比如电话来电

多道程序操作系统

进程 = 程序的唯一执行

代码 + 数据
多进程可能会共享代码
每一个进程都会有唯一的数据（CPU 寄存器，栈空间、内存空间）
进程会被他们的激活记录定义

线程有他们自己 CPU 寄存器值，但是共享相同的内存空间，所以他们可以通过其他线程来影响数据

一个进程可能有不同的线程
线程可能会运行在划分出来的 CPU 核心栈上

典型的进程/任务激活记录（任务控制块）

任务 ID
任务状态（运行，就绪，已阻止）
任务优先级
任务起始地址
任务堆栈
任务 CPU 寄存器
任务数据指针
任务时间

什么时候可以分派新线程？

在非抢占式调度中：当前线程完成时可以分派新线程

在抢占式调度下：

在计时器中断时
在 I/O 中断时可能会分派新线程
创建新线程或完成一个新线程时
当前线程阻塞或释放互斥锁时
当前线程阻塞信号量时
更改信号量状态时
当前线程进行任何 OS 调用时
1. 文件系统访问
2. 网络访问

当前的焦点：如何决定要安排哪个线程？

需要关注的内容有：

抢占式与非抢占式调度
定期与非定期任务
固定优先级与动态优先级
优先反转异常
其他计划异常

指标

我们如何评估调度策略？

能够满足所有截止时间
CPU 利用率-有效工作的时间百分比
计划开销：制定计划所需的时间
延迟
总完成时间

抢占式调度

假设所有线程都有优先级：

静态分配的（在线程持续时间内恒定）
动态分配的（可能有所不同）

进一步假设内核跟踪“启用”了哪些线程（能够执行，例如在等待信号量或互斥量或时间到期之前不会被阻塞）。

抢占式调度：

在任何时候，具有最高优先级的已启用线程正在执行。
每当任何线程更改优先级或启用状态时，内核都可以分派新线程。

速率单调调度 RMS

假设使用以下命令定期调用 n 个任务：

周期 T₁，...，T_n（施加实时约束）
所有任务都是独立的。
最坏情况执行时间（WCET）C₁，...，C_n：假定没有互斥请锁、信号量或阻塞的 I/O
没有优先级限制
固定优先级
上下文切换所需的时间可以忽略不计
抢占式调度

定理：如果任何优先级分配产生一个可行的调度，那么按周期排序的优先级（最小的周期具有最高优先级）也产生一个可行的调度。

就可行性而言，RMS 是最佳的。

RMS 的可行性 Feasibility

为 RMS 定义的可行性是指每个任务在其指定时间内执行一次完成。

显示 RMS 的优越性：考虑两个不同周期的任务

非抢占式时序是否可行？

非抢占式的时间表是不可行的。红色任务的某些实例（2）如果我们进行非抢占式调度，则不会在其期限内完成。

如果我们对红色任务有优先级更高的抢占式调度该怎么办？

具有较高优先级的红色任务的抢占式调度是可行的。请注意，抢占蓝色任务会延长其完成时间。

显示 RMS 的优越性：任务调整

当低优先级任务的开始阶段与高优先级任务的开始阶段匹配时，其完成时间最差。
因此，在检查计划的可行性时，仅考虑最坏的情况就足够了：所有任务都同时开始其周期，如下就是最差情况

显示 RMS 的优越：用于两个任务

足以表明，如果非 RMS 调度是可行的，则 RMS 调度是可行的。

考虑以下两个任务：

非 RMS 固定优先级时间表如下所示：我们可以观察到对于非 RMS 时序如果可行当且仅当 \(C_1 + C_2 \leq T_2\)

RMS 时间表如下所示：周期较短的任务会提前移动，而对于 RMS 是可行的

总结

该证明可以扩展到任意数量的任务（尽管它变得更加乏味）。

该证明仅具有最优性、可行性。它没有说其他最优标准。

实际实施：

定时器中断在周期的最大公约数
多个计时器

RMS 的可行性调度分析

可调度性分析：如果需要，可以使用 RM 调度一组定期任务：

\[ \sum\limits^n\limits_{i=1} \leq n(2^{\frac{1}{n}} - 1) \]

此条件足够，但不是必需的。

\[ U = \sum\limits_{i=1}^{n}\frac{C_i}{T_i} \]

上式表示处理器利用率因子 U，它是执行任务集所花费的处理器时间的一部分。

DDL 驱动调度

Jackson's Algorithm：EDD，Earliest Due Date（1955）

给定 n 个具有期限 d₁，...，d_n 的独立一次性任务，对它们进行调度以最大程度地减少最大延迟，定义为：

\[ L_{max} = \max\limits_{1 \leq i \leq n}\{f_i - d_i\} \]

其中 f_i 是任务 i 的完成时间。请注意，如果所有截止日期都得到满足，则这是负的。
EDD 算法：按不递减的截止日期顺序执行它们。
请注意，这不需要抢占。

定理：从最大延迟的意义上讲，EDD 是最佳的

为了证明这一点，请使用互换参数。如果给定的时间表 S 不是 EDD，则必须存在任务 a 和 b，其中时间表中 a 紧接在 b 之前，但 \(d_a > d_b\)。为什么？
我们可以证明通过交换 a 和 b 可以改善此调度。因此，没有任何一个非 EDD 时间表可以达到比 EDD 更小的最大延迟，因此 EDD 时间表必须是最佳的。

考虑一个非 EDD 调度 S

在调度中必须存在任务 a 和 b，其中 a 紧接在 b 之前，但 \(d_a > d_b\)

所以 S' 绝对不会比 S 的情况更差

Horn 的算法：EDF，Earliest deadline first（1974）

通过允许任务随时“到达”（准备就绪）来扩展 EDD。
最早截止时间优先（EDF）：给定 n 个独立任务的集合，它们具有任意的到达时间，任何算法在任何到达的任务中以绝对绝对最早的时间最早执行任务的任何算法都是最优的。最大程度地减少延迟。
证明使用类似的互换参数。

使用 EDF 执行定期任务

EDF 算法可以被同等地应用于周期性任务和非周期性任务。

最简单的用法：截止时间是该期限的结束。
替代用途：分别指定时间（相对于期间开始时间）和期限。

RMS 和 EDF 哪个好

RMS 优点：调度决策更简单（固定优先级与 EDF 所需的动态优先级。EDF 调度程序必须维护按优先级排序的就绪任务列表。）

EDF 优点：

由于 EDF 是关于最大延迟的最优，也是关于可行性的最优选择。RMS 仅是关于可行性的最优选择。对于不可行的调度，RMS 会完全阻止优先级较低的任务，从而导致无限的最大延迟。
如果 RMS 无法做到这一点，那么 EDF 可以充分利用
EDF 实际上减少了抢占，因此减少了上下文切换的开销。
截止时间可能与周期不同。

优先级约束

有向无环图（DAG）显示优先级，这些优先级指示哪些任务必须在其他任务开始之前完成。

DAG，表明任务 1 必须在任务 2 和 3 开始之前完成，依此类推。

它不需要抢占。我们会看到 EDF 确实如此。

EDF*

如果任务是可抢占的，则可以用多项式时间复杂度解决调度具有优先级约束的 n 个任务的集合（并发激活）的问题。

对于存在优先约束的任务，EDF *算法确定可行的时间表。

通过修改可以保证，如果根本存在有效的时间表，则

任务的开始执行不得早于其释放时间且不得早于其前继的完成时间（任务不能抢占任何前任的任务）
所有任务均在期限内完成执行

修改截止日期：

任务必须在其最后期限内完成执行时间 s
任务的执行不得晚于其后继任务的最大开始时间
解决方案：任务 j 取决于任务 i

\[ d'_i = \min(d_i, d'_j - C_j) \]

修改释放时间：

任务必须在释放时间之前开始执行。
任务的执行时间不得早于其前任的最短完成时间。
解决方案：任务 j 取决于任务 i

\[ r'_j = \max(r_i, r_i + C_i) \]

具有优先级的 EDF

使用抢占式调度程序，可以修改 EDF 以考虑优先级并允许任务在任意时间到达。只需根据优先级调整截止日期和到达时间。

（修正释放时间）给定 n 个具有优先级和释放时间 ri 的任务，如果任务 i 紧接任务 j，则修改释放时间，如下所示：

（修正截止时间）给定 n 个具有优先级和最后期限 di 的任务，如果任务 i 紧接在任务 j 之前，则按以下方式修改最后期限：

在最大程度地减少最大延迟方面，具有优先级的 EDF 是最佳的。

How

如果进程组不可调度，又需要保证在截至时限前完成

使用更快的 cpu。不改变周期就可以减少执行时间。但 cpu 利用率更低。
新设计进程以减少执行时间。需要了解代码。
写规格说明以改变截至时限。

调度异常

互斥：

优先级倒置
优先继承
优先上限

多处理器调度：理查德（Richard）的异常情况在最大程度地减少最大延迟方面是最佳的。

互斥访问

线程访问共享资源时，它们需要使用互斥对象以确保数据完整性。
互斥体也可能使调度复杂化。

多个进程中的锁机制

#include <pthread.h> pthreads
// ...
pthread_mutex_t lock;
void* addListener(notify listener) {
	pthread_mutex_lock(&lock);
	// ...
	pthread_mutex_unlock(&lock);
}
void* update(int newValue) {
	pthread_mutex_lock(&lock);
	value = newValue;
	elementType* element = head;
	while (element != 0) {
		(*(element->listener))(newValue);
		element = element->next;
	}
	pthread_mutex_unlock(&lock);
}
int main(void) {
	pthread_mutex_init(&lock, NULL);
	// ...
}

每当跨线程共享数据结构时，对数据结构的访问通常必须是原子的。这是使用互斥锁或互斥锁强制执行的。持有锁时执行的代码称为临界区。

优先级反转：互斥的危害

任务 1 的优先级最高，任务 3 的优先级最低。任务 3 获取一个共享对象上的锁，进入关键部分。它被任务 1 抢占，然后任务 1 尝试获取锁和块，失败后被阻塞。任务 2 在时间 4 抢占了任务 3（不需要锁和块），使较高优先级的任务 1 被阻止了无限制的时间。实际上，任务 1 和 2 的优先级颠倒了，因为任务 2 可以使任务 1 任意等待较长时间。

不是正常的：任务二先于任务一执行完了

示例：火星探路者问题

但是在执行任务的几天后，即“探路者”开始收集气象数据后不久，该航天器就开始经历整个系统的重置，每次重置都会导致数据丢失。

优先级反转导致的结果
VxWorks 提供了抢占式线程优先级调度。“探路者”飞船上的任务是作为线程执行的，其优先级以通常的方式分配，反映了这些任务的相对紧迫性。
- VxWorks：比较贵
- VxWorks：最好的实时操作系统
探路者包含“信息总线”，您可以将其视为用于在航天器不同组件之间传递信息的共享存储区域。

火星探路者的任务安排

总线管理任务经常以高优先级运行，以将某些类型的数据移入和移出信息总线。对总线的访问已与互斥锁（互斥锁）同步。
气象数据收集任务作为不经常发生的低优先级线程运行...发布其数据时，它将获取一个互斥锁，对总线进行写操作并释放该互斥锁。
该航天器还包含以中等优先级运行的通信任务。

火星探路者的优先级安排

高优先级：从共享内存中检索数据
中优先级：沟通任务
低优先级：线程收集气象数据

问题产生

在大多数情况下，这种组合效果很好。但是，很少会发生中断，导致（中优先级）通信任务在较短的时间间隔内被调度，而（高优先级）信息却线程被阻塞，等待（低优先级）气象数据线程。在这种情况下，优先级高于气象任务的长期运行的通信任务将阻止其运行，从而阻止阻塞的信息总线任务运行。经过一段时间后，看门狗定时器将关闭，注意到数据总线任务已经有一段时间没有执行了，得出的结论是发生了严重错误，并启动了系统总体复位。这种情况是优先级反转的典型案例。

火星探路者的优先反转

优先级继承还解决了火星探路者问题：路径查找器中使用的 VxWorks 操作系统为调用互斥体基元实现了一个标志。该标志允许将优先级继承设置为 on。软件出厂时，将其设置为关闭

火星上的问题已通过使用 VxWorks 的调试工具将标志更改为 on 而得到纠正，而探路者已经在火星上[Jones，1997]。

Priority Inheritance Protocol（PIP）优先级继承协议

假设：通过 m 个共享资源进行合作的 n 个任务；固定优先级后，资源上的所有关键部分都以\(wait(S_i)\)开始，并以\(signal(S_i)\)操作结束。
基本思想：当任务\(J_i\)阻止一个或多个优先级更高的任务时，它会临时（继承）被阻止任务的最高优先级。
协议：我们区分固定的名义优先级 Pi 和活动的优先级\(p_i\)

大于或等于\(P_i\)。相对于名义优先级对作业\(J_1\)，... \(J_n\)进行排序，其中 J1 具有最高优先级。乔布斯不会暂停工作。

PIP 算法

作业是根据其活动优先级安排的。具有相同优先级的作业在 FCFS 执行线中执行。
当作业\(J_i\)试图进入关键部分并且资源被优先级较低的作业阻塞时，作业\(J_i\)就会被阻塞。否则，它将进入关键部分。
当作业\(J_i\)被阻止时，它将其活动优先级发送给持有信号量的作业\(J_k\)。\(J_k\)以优先级\(p_k\) = \(p_i\)恢复并执行其关键部分的其余部分（它继承了被其阻止作业的最高优先级的优先级）。
\(J_k\)退出关键部分时，它将解锁信号量，并且唤醒该信号量上阻塞的最高优先级作业。如果没有其他作业被\(J_k\)阻止，则将\(p_k\)设置为\(P_k\)，否则将其设置为被\(J_k\)阻止的作业的最高优先级。
优先级继承是可传递的，即，如果 1 被 2 阻止，而 2 被 3 阻止，则 3 通过 2 继承优先级 1。

PIP 算法示例

任务 1 的优先级最高，任务 3 的优先级最低。任务 3 获取一个共享对象上的锁，进入关键部分。它被任务 1 抢占，然后任务 1 尝试获取锁和块。任务 3 继承了任务 1 的优先级，从而防止了任务 2 的抢占。

死锁

较低优先级的任务首先启动并获取锁 a，然后被较高优先级的任务抢占，后者获取锁 b，然后阻止尝试获取锁 a 的任务。然后，较低优先级的任务将阻止尝试获取锁 b，并且无法进一步进行。

#include <pthread.h>
...
pthread_mutex_t lock_a, lock_b;
void* thread_1_function(void* arg) {
   pthread_mutex_lock(&lock_b);
   ...
   pthread_mutex_lock(&lock_a);
   ...
   pthread_mutex_unlock(&lock_a);
   ...
   pthread_mutex_unlock(&lock_b);
   ...
}
void* thread_2_function(void* arg) {
   pthread_mutex_lock(&lock_a);
   ...
   pthread_mutex_lock(&lock_b);
   ...
   pthread_mutex_unlock(&lock_b);
   ...
   pthread_mutex_unlock(&lock_a);
   ...
}

Priority Ceiling Protocol（PCP）（Sha， Rajkumar，Lehoczky， 1990）优先天花板协议

每个锁定或信号量都被分配一个优先级上限，该上限等于可以锁定它的最高优先级任务的优先级：是否可以自动计算优先级上限？
仅当任务的优先级严格高于其他任务当前持有的所有锁的优先级上限时，任务 T 才能获得锁：任何任务都不持有的锁不会影响任务
这样可以防止死锁
有一些扩展支持动态优先级和动态创建锁（堆栈资源策略）

OCPP and ICPP

在 OCPP 中

当更高优先级的任务 Y 尝试获取 X 锁定的资源时，任务 X 的优先级会提高。
将任务的优先级提高到资源的优先级上限，以确保任务 X 快速完成其关键部分，从而解锁资源。
仅当任务的动态优先级高于其他任务锁定的所有资源的优先级上限时，才允许该任务锁定资源。否则，任务将被阻塞，等待资源。

在 ICPP 中

任务锁定资源时会立即提高其优先级
任务的优先级设置为资源的优先级上限，因此，可能锁定资源的任务无法调度。
这样可以确保 OCPP 属性“任务只有在其动态优先级高于其他任务锁定的所有资源的优先级上限时才能锁定资源”。

ICPP 与 OCPP

从调度角度来看，两个最高限额方案的最坏情况行为是相同的。但是，有一些区别：
- ICPP 比 OCPP 更易于实施，因为不需要监视阻塞关系
- ICPP 导致较少的上下文切换，因为阻塞是在第一次执行之前
- ICPP 需要更多的优先级移动，因为这会随着所有资源的使用而发生
- 仅当发生实际阻止时，OCPP 才更改优先级

优先天花板协议

在这种情况下，锁 a 和锁 b 的优先级和任务 1 的优先级相同。在时间 3，任务 1 尝试获取锁 b，但是由于任务 2 当前持有当前优先级上限等于任务 1 的锁 a，导致任务 1 无法获取锁 b

#include <pthread.h>
...
pthread_mutex_t lock_a, lock_b;
void* thread_1_function(void* arg) {
   pthread_mutex_lock(&lock_b);
   ...
   pthread_mutex_lock(&lock_a);
   ...
   pthread_mutex_unlock(&lock_a);
   ...
   pthread_mutex_unlock(&lock_b);
   ...
}
void* thread_2_function(void* arg) {
   pthread_mutex_lock(&lock_a);
   ...
   pthread_mutex_lock(&lock_b);
   ...
   pthread_mutex_unlock(&lock_b);
   ...
   pthread_mutex_unlock(&lock_a);
   ...
}

脆性

通常，所有线程调度算法都很脆弱：小的更改可能会带来巨大的意外后果。
我将用多处理器（或多核）时间表进行说明。
定理（Richard Graham，1976 年）：如果根据固定数量的处理器上的优先级安排了具有固定优先级，执行时间和优先级约束的任务集，则增加处理器数量，减少执行时间或削弱优先级约束可以增加时间表的长度。