C++ Concurrency in Action | Processes and Threads

2023-11-19 2023-12-11 约 11907 字预计阅读 24 分钟 - 次阅读

警告

本文最后更新于 2023-12-11，文中内容可能已过时。

进程

在进程模型中，计算机上所有可运行的软件，通常也包括操作系统，被组织成若干顺序进程(sequential process)，简称进程(process)，一个进程就是就是一个正在执行程序的实例，包括程序计数器、寄存器和变量的当前值
概念上来说，每个进程有自己的虚拟 CPU，但实际上真正的 CPU(假设只有一个 CPU)在各进程之间来回切换，同一时刻实际只有一个进程在运行
实际只有一个物理程序计数器。每个进程运行时，它的逻辑程序计数器被装入实际的程序计数器。当进程结束时，物理程序计数器保存到内存中该进程的逻辑程序计数器中
进程创建主要有四种形式
- 系统初始化：启动系统时会创建若干进程，包括和用户交互的前台进程和停在后台的守护进程，守护进程可以通过 UNIX 的 ps 指令或 Window 的任务管理器查看
- 运行中的程序执行创建进程的系统调用：比如启动一个程序，该程序要启动更多进程来分配任务
- 用户请求创建一个新进程：比如用户双击图标启动程序
- 大型机批处理作业的初始化
创建进程的系统调用在 UNIX 中是 fork，在 Windows 中是 CreateProcess，进程创建后，父子进程有不同的地址空间
进程终止通常也有四种形式
- 正常退出(自愿的)：比如点击浏览器的关闭图标。进程退出的系统调用在 UNIX 中是 exit，在 Windows 中是 ExitProcess
- 出错退出(自愿的)：比如执行 cc foo.c 编译 foo.c 而该文件不存在
- 严重错误(非自愿)：比如执行非法指令、引用不存在的内存、除数是零，UNIX中会希望自行处理这些错误以通知操作系统，进程会收到信号被中断而非终止
- 被其他进程杀死(非自愿)：UNIX 中是 kill，Windows 中是 TerminateProcess
UNIX中，进程和其所有子进程(包括其后裔)组成一个进程组，当用户发出一个键盘信号，该信号会发送给进程组所有成员
Windows中没有进程层次的概念，所有进程地位相同
进程阻塞有两种情况，一是正常情况，比如操作系统调度另一个进程占用 CPU，二是异常情况，比如没有足够的 CPU 可调用

进程有三种状态：运行、就绪、阻塞

1
2
3
4
5
6
7
运行 <-> 就绪
  ↘    ↗
    阻塞

运行：该时刻实际占用 CPU
就绪：操作系统调度了其他进程运行而暂时停止
阻塞：逻辑上不能继续运行，比如等待用户输入

操作系统通过维护一张进程表(一个结构数组)来实现进程模型，每个进程占一个表项(即进程控制块，Processing Control Block)。PCB 包含了进程状态的主要信息，如程序计数器、堆栈指针、内存分配状态、所打开的文件状态、账号和调度信息、进程状态切换时必须保存的信息
所有中断都从保存寄存器开始，通常会保存到当前进程的 PCB 中。一个进程在执行过程中可能中断几千次，但恢复时，被中断的进程都将返回到与中断发生前完全相同的状态
发生中断后，操作系统最底层的工作过程
- 中断硬件将程序计数器、程序状态字、寄存器压入堆栈
- 硬件从中断向量装入新的程序计数器
- 通过汇编保存寄存器值(因为这类操作无法用高级语言完成)
- 通过汇编设置新的堆栈
- 运行C语言(假设操作系统用C编写)中断服务例程
- 调用调度程序，决定接下来要运行的进程
- C返回到汇编
- 通过汇编运行新进程

假设一个进程等待 I/O 操作与其在内存中停留的时间比为 p，则 n 个进程都在等待(此时 CPU 空转)的概率为 p ^ n，CPU 利用率为 1 - p ^ n，因此一般(该模型只是粗略情况)I/O 时间越短、运行进程越多，CPU 利用率越高

1
2
3
4
5
6
7
假如内存为 8G，操作系统和相关表格占 2G，用户程序也占 2G，内存最多容纳 3 个用户程序
假设 80% 时间用于等待 I/O 操作
CPU 利用率 = 1 - 0.8 ^ 3 = 49%
如果增加 8G 内存，则最多容纳 7 个用户程序
CPU 利用率 = 1 - 0.8 ^ 7 = 79%，吞吐量提高为 79% - 49% = 30%
如果再增加 8G 内存，则最多容纳 11 个用户程序
CPU 利用率 = 1 - 0.8 ^ 11 = 91%，吞吐量只提高了 12%，可见第一次增加内存比较划算

线程

正如进程提供的抽象使得避免了对中断、定时器、上下文切换的考虑，多线程提供了一种新抽象，即并行实例共享同一地址空间和所有可用数据，这正是多进程模型(地址空间不同)无法表达的
第二个需要多线程的理由是，线程更轻量，创建和撤销都更快(通常创建一个线程比创建一个进程快 10 - 100 倍)
第三个理由是多核 CPU 系统中，多线程为真正的并行提供了可能
线程包含一个程序计数器(记录接下来要执行哪一条指令)、寄存器(保存线程当前的工作变量)、堆栈指针(记录执行历史，每个线程的堆栈有一帧，每一帧保存一个已调用但还未返回的过程，如局部变量、返回地址)
各线程可以访问进程地址空间的每一个内存地址，因此一个线程可以读写甚至清除另一个线程的堆栈。线程之间没有保护，因为不可能，也没必要
除了共享地址空间，线程还共享同一个打开文件集、子进程、定时器及相关信号量
线程可以处在运行、就绪、阻塞、终止等状态中的任何一个
thread_yield 允许线程自动放弃 CPU 转让给另一个线程运行，提供这个调用是因为，不同于进程，线程库不能利用时钟中断强制线程让出 CPU
实现线程包主要有两种方式，一是用户级线程(User-Level Thread)，二是内核级线程(Kernel-Level Thread)，另外也有混合实现
用户级线程把整个线程包放在用户空间中，内核对其一无所知，不需要内核支持，可以在不支持线程的操作系统上实现。在用户空间管理线程时，每个进程需要有其专用的线程表(thread table)，这些表和内核中的进程表类似，只不过记录的是各个线程的属性，如程序计数器、寄存器、堆栈指针和状态等。该线程表由运行时系统管理，当线程转换到就绪或阻塞状态时，在线程表中存放重启该线程所需的信息，与内核在进程表中存放进程的信息完全一样
用户级线程允许进程有自己定制的调度算法，具有更好的可扩展性(因为内核级线程需要一些固定表格空间和堆栈空间)，性能更好。用户级线程的切换需要少量机器指令，而内核级线程需要完整的上下文切换，修改内存映像，使高速缓存失效，这导致了若干数量级的延迟
用户级线程的问题是如何实现阻塞系统调用，比如线程读取键盘，在没有按下任何按键之前不能让该线程实际进行该系统调用，因为这会停止所有线程。另一个问题是，如果一个线程开始运行，则其所在进程的其他线程就不能运行，除非运行线程自动放弃 CPU。而使用内核级线程时，线程阻塞在 I/O 上时，不需要将整个进程挂起
内核级线程的线程表(和用户级线程的线程表一样，记录寄存器、状态和其他信息)存在于内核中，当一个线程希望创建一个新线程或撤销一个已有线程时，将进行一个系统调用，这个系统调用通过对线程表的更新完成创建或撤销工作
当内核级线程阻塞时，内核可以运行同一进程中的另一线程，或者运行另一个进程的线程。而对于用户级线程，运行时系统始终运行其所在进程的线程，直到内核剥夺 CPU(或没有可运行的线程存在)为止
在内核中创建或撤销线程的代价较大，因此内核级线程被撤销时，系统会将其标记为不可运行的，但其内核数据结构未受影响，之后必须创建新线程时就重新启动一个旧线程。用户级线程也可以这样回收，但因为管理代价很小，所以没必要

进程间通信(Inter Process Communication)

对共享内存进行访问的程序片段称为临界区(critical region、critical section)，如果同一时刻临界区只有一个进程，就能避免 race condition
单处理器系统中实现这点的简单做法是，在每个进程刚进入临界区后立即屏蔽所有中断，在即将离开时再打开中断。屏蔽中断后，时钟中断也被屏蔽。CPU 只有发生时钟中断或其他中断才会进行进程切换，这样 CPU 就不会切换到其他进程
但这个方案并不好，因为把屏蔽中断的权力交给用户进程是不明智的，如果一个进程屏蔽中断后不打开，就可能导致整个系统终止。此外如果系统是多处理器，则屏蔽中断只对执行了 disable 指令的 CPU 有效，其他 CPU 仍将运行
对于内核来说，更新变量或列表的几条指令期间屏蔽中断很方便，因此屏蔽中断对操作系统本身是一项很有用的技术，但对用户进程则不是一种合适的互斥机制
第二种方式是一种软件方案，假设有一个共享锁变量，其初始值为 0，当进程要进入临界区时，首先测试锁，如果值为 0 则将锁设为1并进入临界区，如果锁的值已经为 1，则进程等待其值为 0
这种方式的问题在于，如果在一个进程检查到锁为 0，并要将锁设为 1 之前，恰好另一个线程被调度运行将锁设为 1，而第一个进程恢复运行时也将把锁设为 1 并进入临界区，此时临界区就有了两个进程

第三种方式是忙等待(busy waiting)，用一个循环不断测试变量值，直到变量值改变才进入临界区，用于忙等待的锁称为自旋锁(spin lock)。这种方式的问题是，在循环中浪费了大量 CPU 时间，应该避免，除非等待时间非常短才有使用的理由

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// 进程 A
while (true) {
  while (x) {
  }
  critical_region();
  x = true;  // 允许进程 B 进入临界区
  noncritical_region();
}

// 进程 B
while (true) {
  while (!x) {
  }
  critical_region();
  x = false;  // 允许进程 A 进入临界区
  noncritical_region();
}

第四种方式是 1981 年由 G. L. Peterson 提出的 Peterson 算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
constexpr int N = 2;  // 进程数量为2
int turn = 0;         // 轮到的进程
vector<bool> interested(N);

void enter_region(int process) {
  int other = 1 - process;  // 另一进程(进程号为 0 或 1)
  interested[process] = true;
  turn = process;  // turn 只有一个，即使两个进程调用也只有后一个赋值会保留
  while (turn == process && interested[other]) {
  }
}

void leave_region(int process) {  // 调用上述函数完成后调用此函数
  interested[process] = false;
}

// 若进程 A 调用 enter_region 则很快返回，
// 此时进程 B 调用将在 while 循环挂起，
// 直到进程 A 调用 leave_region
// 若进程 AB 同时调用 enter_region，
// turn 为后赋值者，
// 则先赋值者退出循环并调用 leave_region，后赋值者再退出循环

第五种方式是一种硬件方式，需要借助 TSL 指令，即测试并加锁(test and set lock)，该指令是一个原子操作，执行 TSL 指令的 CPU 将锁住内存总线以禁止其他 CPU 在指令结束前访问该内存
1
TSL RX, LOCK // 将内存字 LOCK 读到寄存器 RX 中，然后在该内存地址写一个非零值，读写是原子操作

为了使用 TSL 指令实现互斥，用一个共享变量 LOCK 来协调对内存的访问，其值为 0 时任何进程都能用 TSL 指令将值设为 1 并读写共享内存，操作结束时再用 move 指令将值重置为 0

1
2
3
4
5
6
7
8
9
enter_region:
    TSL REGISTER, LOCK  ;复制锁到寄存器并设置值为 1
    CMP REGISTER, #0    ;值是否为 0
    JNE enter_region    ;不是 0 则循环
    RET                 ;返回，进入临界区

leave_region:
    MOVE LOCK, #0
    RET

可以用 XCHG 指令替代 TSL 指令，它原子交换两个位置的内容

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
enter_region:
    MOVE REGISTER, #1    ;在寄存器放一个 1
    XCHG REGISTER, LOCK  ;原子交换寄存器和锁变量的内容
    CMP REGISTER, #0     ;值是否为 0
    JNE enter_region     ;不是 0 则循环
    RET                  ;返回，进入临界区

leave_region:
    MOVE LOCK, #0
    RET

Peterson 算法和 TSL 或 XCHG 解法同样都有忙等待的问题，它们的本质都是在进程进入临界区时检查是否允许进入，不允许则原地等待直到允许为止

生产者-消费者问题

两个进程共享一个固定大小的缓冲区，生产者进程将消息放入缓冲区，消费者进程从缓冲区取出消息

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
constexpr int N = 100;  // 缓冲区的槽数
int cnt = 0;            // 缓冲区数据数

void producer() {
  while (true) {
    int item = produce_item();  // 生成新数据
    if (cnt == N) {
      sleep();
    }
    insert_item(item);  // 将消息放入缓冲区
    ++cnt;              // 1
    if (cnt == 1) {
      wakeup(consumer);  // 2
    }
  }
}

void consumer() {
  while (true) {
    if (!cnt) {
      sleep();  // 3
    }
    int item = remove_item();  // 从缓冲区取一个数据
    --cnt;
    if (cnt == N - 1) {
      wakeup(producer);
    }
    consume_item(item);  // 打印数据
  }
}

// 问题在于 cnt 的访问存在 race condition，
// 如果消费者执行到 3 处，cnt 为 0，在即将 sleep 之前，
// 生产者在此之后才执行到 1 处，此时 cnt 为 1，执行到 2 处，调用 wakeup，
// 但此时消费者还未 sleep，因此 wakeup 的信号丢失，没有实际作用，
// 接着消费者 sleep，生产者开始下一轮循环，
// 生产者下一轮循环到 1 处，cnt 为 2，到 2 处，不再调用 wakeup，消费者保持 sleep，
// 生产者继续之后的循环，并且每一轮都不会唤醒消费者，
// 最终生产者执行到 cnt 为 N 时 sleep，两个进程都将永久 sleep

信号量(semaphore)

信号量是由 E. W. Dijkstra 于 1965 年提出的一种方法，它使用一个整型变量作为信号量，值为 0 表示没有保存下来的唤醒操作，值为正数表示唤醒操作的次数
信号量有 down 和 up 两种操作，Dijkstra 在论文中称其为 P 和 V 操作(荷兰语中的 Proberen 意为尝试，Verhogen 意为增加或升高)
down 操作检查值是否大于 0，若大于 0 则减 1 并继续，若为 0 则进程睡眠，并且此时 down 操作未结束
up 操作对值加 1。如果有进程在信号量上睡眠，无法完成一个先前的 down 操作，则由系统选择其中一个以允许完成其 down 操作。于是，对一个有睡眠进程的信号量执行一次 up 操作，信号量值仍为 0，但睡眠进程少了一个
down 操作和 up 操作中的所有操作都是原子的，一般作为系统调用实现。操作系统只要在执行测试信号量、更新信号量、使进程睡眠等操作时暂时屏蔽全部中断，这些动作只需要几条指令，所以屏蔽中断不会带来什么副作用。如果使用多个 CPU，则每个信号量应由一个一个锁保护，使用 TSL 或 XCHG 指令来确保同一时刻只有一个 CPU 对信号量进行操作
注意，这里使用 TSL 或 XCHG 指令来防止多 CPU 同时访问一个信号量，与生产者或消费者用忙等待来等待对方腾出或填充缓冲区是完全不同的。信号量操作只需要几毫秒，而生产者或消费者则可能需要任意长时间
使用三个信号量解决生产者-消费者问题：full 记录已充满的缓冲槽数，初值为 0；empty 记录空的缓冲槽数，初值为缓冲区中槽的数目；mutex 确保生产者和消费者不会同时访问缓冲区，初值为 1

供多个进程使用的信号量初值为 1，保证同时只有一个进程可以进入临界区，这种信号量称为二元信号量(binary semaphore)。如果每个进程进入临界区前执行一个 down 操作，并在刚退出时执行一个 up 操作，就能实现互斥

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
constexpr int N = 100;  // 缓冲区的槽数
using semaphore = int;
semaphore mutex = 1;
semaphore empty = N;  // 缓冲区空槽数
semaphore full = 0;   // 缓冲区满槽数

void producer() {
  while (true) {
    int item = produce_item();
    down(&empty);
    down(&mutex);
    insert_item(item);
    up(&mutex);
    up(&full);
  }
}

void consumer() {
  while (true) {
    down(&full);
    down(&mutex);
    int item = remove_item();
    up(&mutex);
    up(&empty);
    consume_item(item);
  }
}

信号量的另一个作用是实现同步(synchronization)，这里 full 和 empty 保证缓冲区满时生产者停止运行，缓冲区空时消费者停止运行

互斥量(mutex)

如果不需要信号量的计数功能，可以使用其称为互斥量的简化版本。互斥量仅适用于管理共享资源或一小段代码。互斥量实现简单且有效，在实现用户空间线程包时十分有用
互斥量只有加锁和解锁两种状态，只需要一个二进制位表示，不过实际上一般用整型量，0 表示解锁，其他值表示加锁
线程需要访问临界区时调用 mutex_lock，如果互斥量是解锁的则临界区可用，调用成功，线程可以进入临界区，否则线程被阻塞，直到临界区中的线程完成并调用 mutex_unlock。如果多个线程阻塞在该互斥量上，则随机选择一个线程并允许它获得锁

用 TSL 或 XCHG 指令就可以很容易地在用户空间实现互斥量

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
mutex_lock:
    TSL REGISTER, MUTEX  ;将互斥量复制到寄存器，并将互斥量置为 1
    CMP REGISTER, #0
    JZE ok               ;如果互斥量为 0，它被解锁，所以返回
    CALL thread_yield    ;互斥量忙，调度另一个线程
    JMP mutex_lock       ;稍后再试
ok: RET

mutex_unlock:
    MOVE MUTEX, #0       ;将互斥量置0
    RET

thread_yield 只是调用用户空间线程调度程序，运行十分快捷，这样 mutex_lock 和 mutex_unlock 都不需要任何内核调用。用户级线程通过互斥量的这个过程即可实现同步，而同步过程仅需要少量指令

管程(monitor)

如果把生产者代码中的两个 down 操作交换顺序，使得 mutex 在 empty 之前减 1，就会导致死锁，因此使用信号量要十分小心。为了更易于编写正确的程序，Brinch Hansen 和 Hoare 提出了一种称为管程的高级同步原语
一个管程是由过程、变量、数据结构等组成的一个集合，它们组成一个特殊的模块或软件包，进程可以在任何需要的时候调用管程中的过程，但不能在管程之外声明的过程中直接访问管程内的数据结构
任一时刻管程中只能有一个活跃进程，这一特性使得管程能有效地完成互斥。管程是编程语言的组成部分，编译器知道其特殊性，进入管程时的互斥由编译器负责，通常做法是使用互斥量或二元信号量。这样就不需要程序员安排互斥，出错的可能性就小很多
管程提供了互斥的简便途径，但此外还需要一种方法使得进程在无法继续运行时被阻塞，这个方法就是引入条件变量(condition variable)
当一个管程过程发现它无法继续运行时(如生产者发现缓冲区满)，则会在某个条件变量(如 full)上执行 wait 操作，该操作将阻塞当前进程，并将另一个在管程外的进程调入管程。另一个进程可以通过对同一条件变量执行 signal 操作唤醒阻塞进程
为了避免管程中有两个活跃进程，执行 signal 操作之后有两种规则。Hoare 建议让新唤醒的进程运行，挂起另一个进程。Brinch Hansen 建议执行 signal 的进程必须立即退出管程，即 signal 语句只能作为一个管程过程的最后一条语句。后者在概念上更简单，并且更容易实现。第三种方法是，让发信号者继续运行，直到其退出管程，才允许等待的进程开始运行
如果一个条件变量上有若干进程正在等待，则对其执行 signal 操作之后，系统调度程序只能选择其中一个恢复运行
如果一个条件变量没有等待进程，则对其执行 signal 会丢失信号，因此 wait 操作必须在 signal 之前。这与之前提到的 sleep 和 wakeup 的关键区别是，管程的自动互斥保证了在 wait 完成之前不会先 signal

消息传递(message passing)

管程和信号量通过共享内存解决 CPU 互斥问题，但没有提供不同机器间(比如局域网中的机器)的信息交换方法
消息传递使用 send 和 receive 原语来实现进程间通信，它们像信号量而不像管程，是系统调用而非语言成分

1
2
send(destination, &message);
receive(source, &message);

send 向一个给定目标发送一条消息，receive 从一个给定源(或者任意源)接收一条消息，如果没有消息可用则接收者可能被阻塞直至有一条消息到达，或者带着一个错误码立即返回
消息传递系统面临许多设计难点：比如消息可能被网络丢失，需要三次握手来确认信息到达情况；比如发送方未收到确认，因此重发消息导致接收方收到两条相同消息，接收方需要区分新老消息；比如身份认证(authentication)问题，客户端如何确认通信的是一个文件服务器还是冒充者

消息传递方式可以有许多变体，一种对消息进行编址的方式是，为每个进程分配一个唯一地址，让消息按进程的地址编址。另一种方式是引入一种称为信箱(mailbox)的数据结构，用来对一定数量的消息进行缓冲。使用信箱时，send 和 receive 调用的地址参数就是信箱而非进程的地址

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
constexpr int N = 100;

void producer() {
  message m;  // 消息缓冲区

  while (true) {
    int item = produce_item();
    receive(consumer, &m);    // 等待消费者发送空缓冲区
    build_message(&m, item);  // 建立一个待发送的消息
    send(consumer, &m);       // 发送数据项给消费者
  }
}

void consumer() {
  message m;

  for (int i = 0; i < N; ++i) {
    send(producer, &m);  // 发送 N 个空缓冲区
  }

  while (true) {
    receive(producer, &m);        // 接收包含数据项的消息
    int item = extract_item(&m);  // 将数据项从消息中提取出来
    send(producer, &m);           // 将空缓冲区发送回生产者
    consume_item(item);
  }
}

使用信箱的另一种极端方法是彻底取消缓冲。采取这种方法时，如果 send 在 receive 之前执行则发送进程被阻塞，直到 receive 发生，反之亦然。执行 receive 时，消息可以直接从发送者复制到接收者，不用任何中间缓冲。这种方案常被称为会和(rendezvous)，实现起来更容易，但降低了灵活性，因为发送者和接收者一定要以步步紧接的方式运行
通常在并行程序设计系统中使用消息传递，一个著名的消息传递系统是消息传递接口(Message-Passing Interface，MPI)，它广泛应用于科学计算

屏障(barrier)

屏障是一种用于进程组的同步机制，只有所有进程就绪时才能进入下一阶段。每个阶段的结尾设置一个屏障，当一个进程到达屏障时将被阻拦，直到所有进程到达屏障为止

调度

几乎所有进程的 I/O 请求和计算都是交替突发的，如果进程花费大量时间在计算上，则称为计算密集型(compute-bound)，如果大量时间花费在等待 I/O 上，则称为 I/O 密集型(I/O-bound)
随着 CPU 变得越来越快，更多的进程倾向为 I/O 密集型。这种现象的原因是 CPU 的改进比磁盘的改进快得多，所以未来对 I/O 密集型进程的调度处理更为重要
调度的基本思想是，如果需要运行 I/O 密集型进程，就应该让它尽快得到机会，以便发出磁盘请求并保持磁盘始终忙碌
根据如何处理时钟中断，可以把调度算法分为非抢占式和抢占式两类
非抢占式调度算法挑选一个进程，然后让该进程运行直至阻塞，或直到该进程自动释放 CPU。即使该进程运行了几个小时也不会被强迫挂起，这样导致时钟中断发生时不会进行调度。在处理完时钟中断后，如果没有更高优先级的进程，则被中断的进程将继续运行
抢占式调度算法挑选一个进程，让该进程运行某个固定时段的最大值，时段结束时将挂起该进程，并挑选另一个进程运行。抢占式调度需要在时间间隔的末端发生时钟中断，以便把 CPU 控制返回给调度程序，如果没有可用的时钟，就只能选择非抢占式调度
不同的应用领域有不同的目标，也就需要不同的调度算法。环境可以划分为三种
- 批处理：广泛用于商业领域，比如处理薪水清单、账目收入、账目支出、利息计算，批处理系统不会有用户在旁边急切等待响应，因此通常使用非抢占式算法，或对每个进程都有长时间周期的抢占式算法，这样减少了进程切换从而改进了性能
- 交互式：必须使用抢占式算法，以避免 CPU 被一个进程霸占而拒绝为其他进程服务。服务器也归于此类，因为通常要服务多个突发的远程用户
- 实时：有时不需要抢占，因为进程了解它们可能会长时间得不到运行，所以通常很快地完成各自工作并阻塞

调度算法的评价指标

对于批处理系统，调度算法的评价指标主要有三个
- 吞吐量(throughout)：系统单位时间内完成的作业数量，比如 10 道作业花费 100 秒，则吞吐量为 0.1 道/秒
- 周转时间(turnaround time)：一个批处理作业从提交开始到完成的统计平均时间
- CPU 利用率：CPU 忙碌时间相对总时间的占比
对于交互式系统，评价指标最重要的是最小响应时间，即从发出命令到得到响应之间的时间
实时系统的特点是或多或少必须满足截止时间，多数实时系统中，可预测性十分重要，比如如果多媒体实时系统的音频进程运行错误太多，音质就会明显下降，为此实时系统的调度算法必须是高度可预测和有规律的

批处理系统中的调度

先来先服务(First-Come First-Served，FCFS)

非抢占式。进程按照请求 CPU 的先后顺序调度，优点是公平，算法实现简单，不会导致进程饥饿(Starvation，等待时间对进程响应带来明显影响)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
进程 到达时间 运行时间
P1   0        7
P2   2        4
P3   4        1
P4   5        4

先到先服务，因此调度顺序为 P1 -> P2 -> P3 -> P4
P1      P2   P3 P4
------- ---- -  ----

周转时间 = 完成时间 - 到达时间
P1 = 7 - 0 = 7
P2 = 11 - 2 = 9
P3 = 12 - 4 = 8  // 只运行 1，却需要等待 8，可见 FCFS 算法对短作业不利
P4 = 16 - 5 = 11
平均周转时间 = 8.75

带权周转时间 = 周转时间 / 运行时间
P1 = 7 / 7 = 1
P2 = 9 / 4 = 2.25
P3 = 8 / 1 = 8
P4 = 11 / 4 = 2.75
平均带权周转时间 = 3.5

等待时间 = 周转时间 - 运行时间(不考虑等待 I/O 操作的时间)
P1 = 7 - 7 = 0
P2 = 9 - 4 = 5
P3 = 8 - 1 = 7
P4 = 11 - 4 = 7
平均等待时间 = 4.75

最短作业优先(Shortest Job First，SJF)

非抢占式。选择已到达的且运行时间最短的进程，运行时间相同则先到达的先运行。目标是追求最短的平均周转时间、平均带权周转时间、平均等待时间，缺点是不公平，对短作业有利，对长作业不利，如果一直有短作业到达可能导致长作业饥饿

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
进程 到达时间 运行时间
P1   0        7
P2   2        4
P3   4        1
P4   5        4

P1 先到达，P1 运行结束时 P2、P3、P4 均到达，P3 运行时间最短先运行
P2、P4 运行时间相同，P2 先到达，因此 P2 先于 P4 运行

最终调度顺序为 P1 -> P3 -> P2 -> P4
P1      P3 P2    P4
------- -  ----  ----

周转时间 = 完成时间 - 到达时间
P1 = 7 - 0 = 7
P2 = 12 - 2 = 10
P3 = 8 - 4 = 4
P4 = 16 - 5 = 11
平均周转时间 = 8

带权周转时间 = 周转时间 / 运行时间
P1 = 7 / 7 = 1
P2 = 10 / 4 = 2.5
P3 = 4 / 1 = 4
P4 = 11 / 4 = 2.75
平均带权周转时间 = 2.56

等待时间 = 周转时间 - 运行时间(不考虑等待 I/O 操作的时间)
P1 = 7 - 7 = 0
P2 = 10 - 4 = 6
P3 = 4 - 1 = 3
P4 = 11 - 4 = 7
平均等待时间 = 4

最短剩余时间优先(Shortest Remaining Time Next，SRTN)

SRTN 是 SJF 的抢占式版本，每当新进程加入时，调度程序总是选择剩余运行时间最短的进程运行，如果当前进程剩余运行时间比新进程长，则挂起当前进程而运行新进程

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
进程 到达时间 运行时间
P1   0        7
P2   2        4
P3   4        1
P4   5        4

P2 到达时，P1 剩余 5，P2 为 4，运行 P2
P3 到达时，P1 剩余 5，P2 剩余 2，P3 为 1，运行 P3
P4 到达时，P3 运行结束，P1 剩余 5，P2 剩余 2，P4 为 4，运行 P2
最后依次运行 P4 和 P1

最终调度顺序为 P1 -> P2 -> P3 -> P2 -> P4 -> P1
P1 P2 P3 P2 P4    P1
-- -- -  -- ----  -----

周转时间 = 完成时间 - 到达时间
P1 = 16 - 0 = 16
P2 = 7 - 2 = 5
P3 = 5 - 4 = 1
P4 = 11 - 5 = 6
平均周转时间 = 7

带权周转时间 = 周转时间 / 运行时间
P1 = 16 / 7 = 2.29
P2 = 5 / 4 = 1.25
P3 = 1 / 1 = 1
P4 = 6 / 4 = 1.5
平均带权周转时间 = 1.51

等待时间 = 周转时间 - 运行时间(不考虑等待 I/O 操作的时间)
P1 = 16 - 7 = 9
P2 = 5 - 4 = 1
P3 = 1 - 1 = 0
P4 = 6 - 4 = 2
平均等待时间 = 3

高响应比优先(Highest Response Ratio Next，HRRN)

非抢占式。在所有已到达进程中选择响应比(等待时间 / 运行时间 + 1)最高的运行，综合 FCFS 和 SJF 的优点，等待时间长、运行时间短的优先，避免长作业饥饿的问题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
进程 到达时间 运行时间
P1   0        7
P2   2        4
P3   4        1
P4   5        4

响应比 = (等待时间 + 运行时间) / 运行时间
P1 运行至结束，P2、P3、P4 均到达，响应比分别为
P2 = (5 + 4) / 4 = 2.25
P3 = (3 + 1) / 1 = 4
P4 = (2 + 4) / 4 = 1.5
运行 P3，P3 结束时，响应比分别为
P2 = (6 + 4) / 4 = 2.5
P4 = (3 + 4) / 4 = 1.75
运行 P2，最后运行 P4

最终调度顺序为 P1 -> P3 -> P2 -> P4
P1      P3 P2    P4
------- -  ----  ----

交互式系统中的调度

时间片轮转调度(Round-Robin Scheduling，RR)

RR 是一种简单公平的抢占式调度算法，并且可以避免饥饿。每个进程被分配一个时间片(quantum)。时间片结束时，如果进程还在运行，则剥夺 CPU 并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则 CPU 立即切换。RR 算法实现很容易，只需要维护一张进程队列表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
A -> B -> C -> D

若 A 用完时间片，但仍在运行，则插入到队列尾
B -> C -> D -> A

若 B 用完时间片，但仍在运行，并到达一个新进程 E，则先插入新进程
C -> D -> A -> E -> B

若 C 用完时间片之前就结束了，则直接切换到下一个进程
D -> A -> E -> B

需要考虑的是时间片的长度，假设时间片为 4 ms，上下文切换为 1 ms，则 CPU 完成 4 ms 工作后将浪费 1 ms 进行上下文切换(context switch)，即浪费了 20% 的时间。但如果时间片太大，就会退化为 FCFS，导致增大响应时间。通常为了提高 CPU 效率，设置时间片时，切换开销占比应不超过 1%

优先级调度

为每个进程设置优先级，在已到达进程中，选择优先级最高的运行，可以为抢占式或非抢占式
比如对于操作系统来说，I/O 密集型进程的优先级应该更高。I/O 密集型继承多数时间用于等待 I/O 结束，因此需要 CPU 时应立即分配给它以便启动下一个 I/O 请求，这样就可以在另一个进程计算的同时执行 I/O 操作
一种简单做法是将优先级设置为 1 / f，f 为该进程在上一时间片中的运行时间占比。比如在 50 ms 时间片中，使用 1 ms 的进程优先级为 50，使用 25 ms 的进程优先级为 2。将进程按优先级分组，再使用 RR 算法调度高优先级组中的进程

多级反馈队列调度

CTSS(Compatible Time Sharing System)是最早使用优先级调度的系统之一，但存在进程切换速度太慢的问题，其设计者意识到设置较长的时间片可以减少切换次数，但长时间片又会影响到响应时间。最终的解决方法是多级反馈队列调度，它是对 FCFS、SJF、RR、优先级调度的折中权衡
设置多个优先级队列，每个级别对应不同长度的时间片，比如第一级(最高级)时间片为 1，第二级为 2，第三级为 4，以此类推
如果一个进程用完当前级别时间片后仍未运行完，则加入下一级队列队尾，如果已经位于最后一级则放回该级队尾
高优先级队列为空时，才会调度低优先级队列，因此可能导致低优先级进程饥饿
比如一个进程需要 100 个时间片，第一次分配 1 个时间片，第二次分配 2 个，接下来是 4、8、16、32、64，最后一次使用 64 中的 37 个即可结束工作，一共进行 7 次切换。如果使用 RR 算法，则需要 100 次切换

最短进程优先

关键在于如何从可运行进程中找出最短的一个
一种方法是根据过去的行为进行预测。假设某终端每条命令的估计运行时间为 T0，测量到下一次运行时间为 T1，则估计时间可以修正为 a * T0 + (1 - a) * T1，比如设 a 为 1 / 2 可以得到序列如下
1 2 3 4
T0 T0/2 + T1/2 T0/4 + T1/4 + T2/2 T0/8 + T1/8 + T2/4 + T3/2 // T0 在此时估计时间中的占比下降到 1/8

保证调度

向用户作出明确的性能保证，然后实现它。比如有 n 个进程运行的单用户系统中，如果所有进程等价，则每个进程获得 1 / n 的CPU时间，为了实现所作的保证，系统跟踪每个进程已使用的 CPU 时间，并计算应获得的时间，然后转向已用时间最少的进程，直到超过最接近的竞争者

彩票调度(Lottery Scheduling)

保证调度的想法不错，但很难实现。彩票调度既可以给出类似预测结果，并且实现非常简单。其基本思想是为进程提供各种系统资源(如 CPU 时间)的彩票，一旦需要做出调度决策时，就随机抽出一张彩票，拥有该彩票的进程获取该资源
比如系统掌握每秒 50 次的一种彩票，作为奖励每个获奖者可以获得 20 ms 的 CPU 时间
可以给更重要的进程额外的彩票，以增加其获胜的机会，比如出售 100 张彩票，一个进程持有其中 20 张，则每次抽奖该进程就有 20% 的取胜机会，在较长运行时间中该进程就会得到 20% 的 CPU
彩票调度可以解决其他方法很难解决的问题，比如一个视频服务器上有若干提供视频流的进程，每个流的帧率不同，假设帧率分别为 10、20、25，那么给这些进程分别分配 10、20、25 张彩票，它们就会自动按照接近 10:20:25 的比例划分 CPU 的使用

公平分享调度

之前的调度关注的都是进程本身，而没有关注进程所有者。假设两个用户分别启动 9 个进程和 1 个进程，使用 RR 算法，则两者分别得到 90% 和 10% 的 CPU 时间。为了避免这种情况，在调度处理之前应该考虑进程拥有者

Buy me a coffee~

赞赏

支付宝

微信