多进程与多速率系统

任务与进程

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

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

多速率系统

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

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

进程的时间约束

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

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

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

进程的速率约束

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

进程的状态

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

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

超周期

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

一组进程的CPU利用率

调度策略

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

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

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

要求：

  • T ≥ ∑iTi
  • 不能超过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://bp.esing.dev/https://raw.githubusercontent.com/Zxis233/images/main/img/image-20240618154100533_2024-6-18_1541_wdti2s8l9p.png","alt":"image-20240618154100533"},{"url":"https://bp.esing.dev/https://raw.githubusercontent.com/Zxis233/images/main/img/image-20240618154112359_2024-6-18_1541_67agw1r2dh.png","alt":"image-20240618154112359"}]
答案
  1. C
  2. C

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

操作系统（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利用率，注意无法达到100%

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

RMS调度的例子 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次并完成。

EDF调度

EDF是一种动态优先级调度方案。在进程执行时，根据进程的截止时限排序来改变进程的优先级，对截止时限最近者优先调度。

在每个时间片开始重新计算所有进程的优先级：

  • 优先级最高的进程是距离截止时限最近的进程；
  • 优先级最低的进程是距离截止时限最远的进程；
  • 一旦重新计算完优先级，其调度过程同RMS一样。

RMS调度不能100%利用CPU，即使在上下文切换为0开销情况下，但是EDF可以，代价是实际中实现的代价大。

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

EDF调度的例子

在前五个时间片中，按照每个的截止时限最近-最远进行运行，因此0-2依次运行P1P2P3。第3个时间片，P1距离截止还有3个时间片，但是P3仅有1个，因此优先运行P3并结束它的第一次运行。第4个时间片同理。

RMS与EDF调度的对比，注意RMS在按照策略运行时会优先执行P2，导致P3被挤占

多进程共享高速缓存

多进程共享缓存，注意第二种策略为P1准备了缓存，使得后续时间减少

进程间通信机制与功耗优化策略

上课没讲，不做要求 ^_^ 最喜欢的一集

进程间通信

（Interprocess communication，IPC）：由操作系统提供的进程间数据传输的机制。

进程发起通信的2种方式：

  • 阻塞式（blocking）：在发送了信息之后，进程进入等待状态，直到接收到响应才执行其他操作；
  • 非阻塞式（nonblocking）：允许进程在发送信息之后继续执行。

临界区与信号量

使用共享内存进行通信，可能会存在临界时间竞争（critical timing race） 问题：

  • 如果一个标志用于CPU和I/O设备之间的双向信号
  • CPU读标志单元，看到其值为0
  • I/O设备读标志单元，看到其值为0
  • CPU设置标志单元为1，并向共享单元写入数据
  • I/O设备错误的将标志单元设置为1，写入数据，将覆盖CPU写入的数据

为了防止发生临界时间竞争，需要控制操作发生的顺序。通过临界区（critical section） 实现操作控制：

  • 不能被其他进程中断的一段连续执行的代码；
  • 确保一个任务完成了读写操作，才能允许其他任务进行操作。

使用**信号量（Semaphore）**来创建临界区，实现对一块受保护的资源（比如共享内存块）进行访问控制。

  • 进入临界区之前，调用一个信号量函数P()，这个函数直到资源可用时才会返回，获得临界区的信号量。
  • 执行临界区的操作（受保护的工作）。
  • 资源使用执行完后，调用另一个信号量函数V()，实现信号量的释放。

原子操作

为了实现信号量函数P()和V()，CPU总线必须支持原子读写（atomic read/write）操作，该操作不能被中断。