计算机原理与嵌入式系统笔记：第十三篇

多进程与多速率系统

任务与进程

任务（task） 是一个密切相连的操作组合的功能描述。
- 任务也可定义为若干进程或线程的组成。
进程（process） 是一个程序的单次执行。
- 两次运行相同的程序，可以创建两个不同进程
- 每个进程拥有自己的状态：
  - 寄存器状态
  - 存储器状态
- 操作系统管理进程

为什么需要多进程？多任务本身即是多进程，多进程有助于在时间复杂系统中应用。

多速率系统

多速率（multirate） 的嵌入式计算系统很常见，程序设计必须满足多种速率对计算的时间要求。

任务之间可以是同步或不同步
同步的任务可以以不同的速率发生
根据任务的实际计算需求，进程运行在不同的速率

进程的时间约束

进程的时间约束会影响可用的调度策略，进程有两个重要的约束：

释放时间（release time）：也叫起始时间（initiation time），进程处于准备执行状态的时刻，此时未取得CPU控制，也没有开始运行。
截止时限（deadline）：指明计算何时必须结束。

非周期性进程由一个事件触发；周期性进程在每个周期都执行，在周期开始时初始化。

进程的速率约束

进程的速率约束指进程多快被启动。周期（period） 指同一进程的两次连续执行之间的时间，速率（rate） 就是周期的倒数。多速率系统中，每个进程都以自己的速率执行。

进程的状态

一个进程有三个基本的调度状态:

执行（executing on the CPU）
就绪（ready to run）
等待（waiting for data）

超周期

超周期（Hyperperiod）是所有进程周期数的最小公倍数（LCM）。如果进程周期选择不当，可能会导致超周期的时间很长。

调度策略

调度策略定义如何从就绪态的进程集合中选择进入执行态的进程。

非常简单的调度策略，假设:

没有资源冲突
进程的执行时间固定

要求：

T ≥ ∑_iT_i
不能超过100%的CPU利用率

TDMA调度

静态循环/时分（TDMA）调度策略是一种基于时间片的调度，进程总在相同的时间片内运行。CPU的利用率受时间片的数量和用于有用工作的每个时间片影响。调度建立在所有进程的超周期，调度开销很小，总是相同的CPU利用率。

轮询调度

轮询（Round-robin）调度只调度就绪的进程，总是按照相同的顺序检测各个进程是否就绪。与静态循环调度不同，当一个进程没有有用的工作要做时，轮询调度会直接依次序执行下一个进程。调度周期为所有进程的最小公倍数（LCM），即超周期。

TDMA不能处理不可预料的负载，必须为非周期的事件分配一个调度的时间片，但是轮询能够处理不可预料的负载。

运行周期性进程

while循环实现方式：没有控制各个进程的执行速率，以相同速率执行

while (TRUE) {
	p1();
	p2();
}

定时器的中断处理程序调用pall()函数：

void pall(){
    p1();
	p2();
}

多个定时器实现多速率系统

用一个函数收集以某一速率运行的所有进程
每个任务都有自己的定时器
可能没有足够的定时器支持要求的所有速率

void pA(){ /* rate A */
	p1();
	p3();
}
void pB(){ /* rate B */
	p2();
	p4();
	p5();
}

定时器+计数器

进程p2以进程p1的1/3速率运行：

int p2count = 0;
void pall(){
	p1();
	if (p2count >= 2) {
		p2();
		p2count = 0;
	}
	else p2count++;
}

练习

[{"url":"https://webp.esing.dev/img/image-20240618154100533_2024-6-18_1541_wdti2s8l9p.png","alt":"image-20240618154100533"},{"url":"https://webp.esing.dev/img/image-20240618154112359_2024-6-18_1541_67agw1r2dh.png","alt":"image-20240618154112359"}]

答案

实时操作系统与基于优先级的调度

操作系统（Operation System，OS）要对CPU、I/O、memory进行控制，最重要的资源是CPU， CPU的访问由调度器控制。

基于优先级的调度

为进程分配优先级的两种著名方法：

单一速率调度（Rate-Monotonic Scheduling，RMS）
- 整个执行过程中优先级始终不变；
- 为实时操作系统开发的调度策略之一，现在仍然被广泛使用。
最早截止时限优先（Earliest Deadline First，EDF）
- 动态优先级调度，在执行期间改变进程优先级。

RMS调度

RMS调度的理论基础是单一速率分析（Rate Monotonic Analysis，RMA），优先级依据周期长短进行分配，周期最短的进程被赋予最高优先级。

下面是一个RMS调度的例子：

首先计算CPU执行时间：1x3+2x2+3x1=10<12，可以正常分配。

对于P1，每4个周期执行一次；对于P2，每6个周期执行一次；对于P3，每12个周期执行一次。

周期最短的进程被赋予最高优先级，因此P1先执行第1次并且完成，随后的2个时间片执行P2的第1次并且完成，第4个时间片执行P3的第1次，未执行完；

进入第4个时间片，P1准备就绪，执行第2次并完成，但此时P2还未准备好，因此先执行P3的第1次，仍位执行完。在第6个时间片P2初始化完毕，因此P2执行第2次并完成。

第8个时间片，P1准备就绪，执行第3次并完成，第9个时间片执行P3的第1次并完成。