进程与线程

进程

进程 (Process) 是操作系统中的核心概念，是对正在运行的程序的抽象。即使只有一个可用的 CPU，也可以启动多个进程，让操作系统具有并发能力。

进程模型

一个进程就是一个正在执行的程序实例，每个进程都拥有一个自己的虚拟 CPU、程序计数器、寄存器、内存地址空间等，这些是一个进程私有的，不可被其他进程所访问、修改，真正的 CPU 在各个进程之间来回切换。

假设现在有 4 个程序，它们在运行时装入自己虚拟的程序计数器、寄存器，并有物理 CPU 运行程序。当程序被切换时，物理程序计数器等数据被保存到内存中。在观察足够长的时间时，所有的进程都运行了，但每个瞬间仅有一个程序在执行。需要注意的是，如果一个程序运行了两遍，那将被算作两个进程。

进程的核心思想即：一个进程是某种类型的一个活动，它有程序、输入、输出以及状态。单个处理器可以被若干进程共享，它使用调度算法决定何时停止一个进程的工作，并转而为另一个进程提供服务。

当进程创建了一个新进程后，其被称为父进程，新进程被称为子进程，这些进程组成了层次结构。在 UNIX 中一个称为 init 的特殊进程出现在启动映像中，init 运行时读入终端数量的文件，并为每一个终端创建一个新进程。这些终端等待用户登陆，登陆成功时便会执行 shell 进程来接收用户命令。整个系统中，所有进程都属于以 init 为根的进程树。 Windows 中没有层次结构概念，所有进程地位相同。创建进程时父进程得到 句柄 用于控制子进程，但也可以将句柄传送给其他进程。

进程的创建与终止

操作系统往往需要一种方式来创建进程，一般由 4 种主要事件来创建进程：

1. 系统初始化
2. 正在运行的程序执行了创建进程的系统调用 (syscall)
3. 用户请求创建新进程
4. 批处理作业的初始化

新进程都是由于一个已存在的进程执行了一个用于创建进程的 syscall 用而创建的。这个系统调用通知操作系统创建一个新进程，并且直接或间接地指定在该进程中运行的程序。

在 UNIX 系统，往往采用 syscall fork 来创建一个与调用进程相同的副本。调用成功后，两个进程拥有相同的内存映像、相同的环境字符串与打开文件。通常子进程执行 exec 系列 syscall 来修改其内存映像，并运行一个新程序。在执行 exec 之前，允许子进程处理其文件描述符等操作。

UNIX 中子进程的初始地址空间是父进程的一个副本，但是两个不同的地址空间，不可写的部分则是共享的。而某些 UNIX 实现中，子进程共享父进程的所有内存，内存通过 写时复制 (Copy-On-Write, COW) 技术实现共享，即当两者之一修改内存时，这块内存被明确的复制，以保证修改发生在进程的私有区域。

进程在创建之后开始运行，完成其工作，进程可能在未来的某个时刻完成任务并被终止。通常终止进程由以下条件引起：

1. 正常退出 (自愿)
2. 错误退出 (自愿)
3. 严重错误 (非自愿)
4. 被其他进程杀死 (非自愿)

前两种即进程自己所处理的终止，完成工作或者在运行时遇到了一些可处理的错误，这时进程通过 exit 调用终止，并向父进程返回状态值。

严重错误往往会导致进程直接崩溃，终止进程，比如发生 零除错误 或 引用错误内存 等。不过在 UNIX 中，进程可以通知操作系统自行处理一部分严重错误，当发生错误时收到信号 (被中断) 而非终止。

进程可以被其他进程杀死，需要采用 syscall kill 来完成这个操作。kill 采用发送信号的方式告知进程执行操作，进程可以捕获一部分信号自行处理，但是「杀死」信号 SIGKILL 无法被捕获，进程接收到 KILL 信号后将直接被杀死。

进程的状态

进程虽然是独立的实体，但有时需要在进程之间相互作用。比如进程等待其他进程的输入时，则会被阻塞，进程的状态也变为阻塞态。正在运行的进程则是运行态进程，当一个进程被剥夺 CPU 的使用权而等待 CPU 的调度时，被称为就绪态。

阻塞态与运行态相似，都是进程不在使用 CPU，但其完全不同。前者是需要一定条件才能继续运行，比如等待输入就绪或等待硬盘读取数据，这时进程阻塞并主动让出 CPU 以供其他进程使用。而后者则是可以继续运行，但操作系统将 CPU 调度给了其他进程，因此进入等待 CPU 的状态。因此阻塞态进程必须满足一定条件才能继续进行，而就绪态进程只需要等待操作系统的调度，CPU 暂时没有分配给它。

这三种状态可以互相转换，如下图所示。当操作系统发现进程需要等待某些任务而不能继续执行时，将运行态转换为阻塞态；运行态与就绪态的转换，是由操作系统针对进程的调度引起的，对于进程来说无法察觉调度的存在；如果进程阻塞时，其等待的任务已完成，进程可以继续运行，则会转换为就绪态等待操作系统调度。

进程的实现

操作系统使用进程表 (process table) 来维护进程模型，每个进程占用一个进程控制块。该控制块包含了进程状态的重要信息，包括程序计数器、堆栈指针、内存分配情况、打开的文件状态、调度信息等，从而保证该进程可以在之后调度中能再次启动，就像没有被中断过一样。下表展示了程序控制块中的关键字段。

与每一 I/O 类关联的是一个称作 中断向量 (interrupt vector) 的位置，这是靠近内存底部的固定区域，这些内存包含中断服务程序的入口地址。在中断发生时，操作系统会做一系列操作，保存当前进程的上下文，并执行中断程序服务。以下是中断的执行步骤：

1. 将程序计数器、程序状态字压入堆栈 (硬件)
2. 从中断向量装入新的程序计数器 (硬件)
3. 保存寄存器的值 (汇编语言)
4. 设置新的堆栈 (汇编语言)
5. 中断服务程序 (通常为 C 语言)
6. 调度下一个运行的进程
7. 中断返回
8. 开始运行新的当前进程

一个进程在执行过程中可能被中断数千次，但关键是每次中断后，被中断的进程都返回到与中断发生前完全相同的状态。

线程

在传统操作系统中，每个进程有一个地址空间和一个控制线程。经常存在在同一个地址空间中，并行运行多个控制线程的情形，这些线程就像分离的进程，但彼此共享地址空间。

我们引入线程往往有以下理由：

1. 并行实例拥有共享同一个地址空间和所有数据的能力，这对于多进程模型是难以表达的
2. 线程相对于进程更加轻量，创建更加容易、更加快速，也更容易撤销，有利于大量线程的动态、快速修改
3. 若多个线程都是 CPU 密集型的，那么并不能获得性能上的增强，但是如果存在大量计算和大量 I/O 处理，拥有多个线程允许这些活动彼此重叠进行，从而会加快应用程序执行的速度
4. 在多 CPU 系统中，多线程是有益的，真正的并行有了实现的可能

线程模型

进程用某种方法将相关的资源集中在一起，包含程序正文、数据以及地址空间、打开的文件、定时器等。进程拥有一个执行线程 (thread)，thread 中存在一个程序计数器、寄存器和堆栈，用于记录指令、变量等信息。线程与传统进程一样，拥有若干个状态用于 CPU 的调度，线程的状态转换与进程是一致的。进程用于把资源集中到一起，线程则是 CPU 上被调度执行的实体。

同一个进程环境中，允许彼此之间有较大独立性的多个线程同时执行，这是对多进程模型的一种模拟。由于多线程模型中，所有线程都具有完全相同的地址空间，意味着他们也共享同样的全局变量。线程之间是没有保护的，一个线程可以读、写、清除另一个线程的堆栈。这样便于线程为完成某一任务而共同工作。

为实现可移植的线程程序，IEEE 1003.1c 中定义线程的标准，其被成为 pthread，大部分 UNIX 都支持该标准。所有 pthread 线程都有一些特性，包含一个 标识符 、一组 * 寄存器* (包含程序计数器) 和一组存储于结构中的属性，包括堆栈大小、调度参数等。

创建一个新线程时使用 pthread_create 调用，线程的标识符会作为函数返回值返回。这么做看起来像 fork 调用，方便其他线程引用该线程。当线程完成它的工作时，可以通过调用 pthread_exit 来终止，这个调用类似于 exit 调用，这会终止线程并释放线程的栈。线程可以使用 pthread_yield 调用，主动地为其他线程让出 CPU。

内核态线程

由内核实现线程以及调度、管理操作，当需要创建或操作一个线程时，会使用 syscall 完成相关的操作。内核使用线程表对系统中的所有线程进行记录，其中保存了每个线程的寄存器、状态与其他信息。

由于内核中创建或撤销线程的代价较大，某些系统会采用 回收线程 的方式，减小开销。当某个线程被撤销时，将其标记为不可运行，但其内核数据结构完全不受影响，在需要创建新线程时就重新启用某个旧线程即可。

用户态线程

用户态线程可以将整个线程包放在用户空间中，内核对线程包一无所知，内核仅需要管理单线程进程即可。可以在不支持线程的操作系统上以这种方式实现线程。在用户空间管理线程时，每个进程都需要专用的线程表，用以跟踪进程中的线程，该进程表及调度方法由运行时系统进行管理。

用户态线程模型进行调度时，保存线程状态的过程与调度程序都是在本地进行，不需要陷入内核、上下文切换等操作，相较于内核态线程要快很多 (一个数量级或更多)。并且针对不同的进程，允许用户制定不同的调度算法。

用户态线程有一个明显的问题，即如何实现 阻塞系统调用。当线程进行一个阻塞的系统调用时，将会阻塞整个进程直到等待就绪，导致其他线程也被迫停止运行。解决方法即：在运行时系统中使用 IO 多路复用进行阻塞系统调用，当阻塞时不进行调用并运行另一个线程，直到当前线程可以安全运行。这种方法需要改写一部分系统调用，对其进行包装，以保证用户态线程的正确运行。

用户态线程的另一个问题，如果一个线程开始运行，那么在该进程中的其他线程就不能运行，除非第一个线程自动放弃 CPU。在一个单独的进程内部，没有时钟中断，所以不能使用轮转调度的方式调用线程。除非某个线程能够按照自己的意志进入运行时系统，否则调度程序就没有任何机会。可以考虑让运行时系统请求每秒一次的时钟信号 (中断)，但高频率的发生周期性的时钟中断开销客观，如果线程使用时钟中断时可能扰乱运行时系统的时钟。

人们已经研究了各种试图将用户级线程的优点和内核级线程的优点结合起来的方法，其中一种方法即将用户态线程与一些/全部内核态线程多路复用起来，由编程人员决定使用多少内核线程与多少用户线程。内核只识别内核线程，并对内核线程进行调度；内核线程被用户线程多路复用，每个内核线程有一个可以轮流使用的用户线程。

进程间通信

进程间有时需要通信，被称为 进程间通信 (Inter Process Communication, IPC)。同时我们需要考虑三个问题：

1. 进程如何将信息传递给另一个进程
2. 确保两个或更多进程在关键活动中不会出现交叉
3. 如果进程间顺序关联的话，确保顺序正确

除了第一问题在线程中很好解决，因为它们共享内存地址，但后两个问题对线程同样适用。

竞争条件与临界区

协作的线程可能通过共享公共的存储区来完成通信，两个或多个的进程 (或线程) 读写某些共享数据，而最后的结果取决于进程 (或线程) 运行的精确时序，被称为 竞争条件 (race condition)。

以最简单的循环加一程序举例，两个线程同时对一个内存变量进行加一操作，各自循环 10000000 次，最终的结果可能不为 20000000。其中加一条件即是该段程序的竞争条件，它们竞争同一内存地址。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int sum = 0; // 可能的结果 13049876
void* add(void* atgs) {
  for (int i = 0; i < 10000000; i++) ++sum;
}
int main(void) {
  pthread_t t1;
  pthread_t t2;
  pthread_create(&t1, NULL, add, NULL); // 创建线程 1
  pthread_create(&t2, NULL, add, NULL); // 创建线程 2
  pthread_join(t1, NULL); // 等待线程 1 结束
  pthread_join(t2, NULL); // 等待线程 2 结束
  printf("%d\n", sum);
}

实际上，凡是涉及共享内存、共享文件或共享任何资源时，都会由竞争条件引发错误，要避免这种错误，必须阻止多个进程同时读写共享数据。换言之即 互斥 (mutual exclusion)，即以某种手段确保当一个进程使用共享资源时，其他进程无法进行同样的操作。实现互斥而选择的原语是操作系统的主要设计内容之一。

避免竞争条件的问题也可以用一种抽象的方式进行描述。一个进程的一部分时间做内部计算或另外一些不会引发竞争条件的操作。在某些时候进程可能需要访问共享数据或执行另外一些导致竞争的操作。我们把对共享内存进行访问的程序片段称为 临界区域 (critical region) 或 临界区 (critical section)。如果我们能够适当地安排，使得两个进程不可能同时处于 临界区中，就能够避免竞争条件。

尽管这样的要求避免了竞争条件，但它还不能保证使用共享数据的并发进程能够正确和高效地进行协作。对于一个好的解决方案，需要满足以下 4 个条件：

1. 任何两个进程不能同时处于临界区
2. 不应对 CPU 的速度和数量做任何假设
3. 临界区外运行的进程不得阻塞其他进程
4. 不得使进程无限期等待进入临界区

忙等待的互斥

屏蔽中断

在单处理器系统中，最简单的方法为每个进程进入临界区时立即屏蔽所有中断，并在离开前再次打开中断。但是屏蔽中断也会导致时钟中断被屏蔽。CPU 只有发生时钟中断或其他中断时才会进行进程切换，屏蔽之后 CPU 将不会切换到其他进程。

对于内核来说，当更新变量或列表的几条指令期间，将中断屏蔽是方便的。但是用户可以自由屏蔽中断对系统来说是不安全的，如果用户屏蔽中断并不再打开中断，那么整个系统将会因此终止。而系统如果有多个处理器，屏蔽中断仅对当前关闭中断的 CPU 有效，其他 CPU 依然会继续运行。因此这是一种在用户进程中不合适的互斥机制。

锁变量

设想有一个共享 (锁) 变量，其初始值为0，当进程想进入临界区时，如果锁的值为 0 则设置为 1 并进入临界区，反之则等待。这可能在设置时，被 CPU 调度而导致有多个进程同时位于临界区内。

严格轮换法

设置一个共享内存记录当前可以进入临界区的进程 ID，当即将进入临界区时，检查该变量是否与自己的进程 ID 相等，不相等时则一直循环空转检测，直到可以进入临界区为止。当即将离开临界区时，将共享内存设置为下一个进程 ID，轮询每个竞争进程。连续测试一个变量，直到某个值出现为止，被称为 忙等待 (busy waiting)。由于这种方式浪费 CPU 时间，所以通常应该避免，只有在有理由认为等待时间非常短的情况下进行忙等待。用于忙等待的锁被称为 自旋锁 (spin lock)。

Peterson 解法

这是一种简单的不需要严格轮换的软件互斥算法。当前进程准备进入临界区时，标志数组对应的元素为 TRUE，并将共享变量设置为当前进程。循环判断共享变量是否为当前进程，是否有其他进程在标志数组中被设置为 TRUE。如果检查成功，则会继续循环，直到条件不成立，代码将进入临界区。在离开临界区时，将当前进程所对应的标志元素设置为 FALSE 即可。

1 2 3 4 5 6 7 8 9 10 11

int turn; int intersted[N]; // N = 2 void enter_region(int process) { int other = 1 - process; intersted[process] = TRUE; turn = process; while (turn == process && interested[other] == TRUE); } void leave_region(int process) { intersted[process] = FALSE; }

TSL 指令

TSL 是一种硬件支持的解决方案，指令为 TSL RX, LOCK，称为 测试并加锁 (test and set lock)，它将内存字 lock 读入寄存器 RX 中，然后在该内存地址上存一个非零值。读字与写字操作是不可分割的，即该指令结束之前其他处理器均不允许访问该内存字。执行 TSL 指令的 CPU 将锁住内存总线，以禁止其他 CPU 在本指令结束之前访问内存。

在进入临界区时，将 LOCK 变量通过 TSL 指令设置为 1，并进入临界区。如果已经被设置为 1，则表示已经有进程进入临界区，则循环检测条件是否达成。当离开临界区时，将 0 写入 LOCK 即可。所以在请求进入临界区时将导致忙等待，直到锁空闲为止。

XCHG 是 TSL 的一种可替代指令，原子性地交换两个位置的内容。所有的 Intel x86 CPU 在底层同步中使用 XCHG 指令。

睡眠与唤醒

Peterson 与 TSL 都是正确的，但都有着忙等待的缺点，即进程准备进入临界区时，先检查是否允许进入，如果不被允许进程将原地等待，直到允许为止。原地等待将造成 CPU 空转，浪费 CPU 资源。

忙等待的另一个问题为 优先级反转问题 (priority inversion problem)：在两个进程 H (高优先级进程) 与 L (低优先级进程)，调度时当高优先级人物就绪时就可以运行。此时 L 处于临界区中，此时 H 就绪准备运行。当 H 开始忙等待，但由于调度关系导致 L 不会被调度，因此 L 无法离开临界区而 H 也会永远地等待下去。

我们讨论以下进程间通信原语，这些原语在无法进入临界区时将阻塞进程，而非忙等待。 sleep 是一个引起调用进程阻塞的系统调用，直到其他进程将其唤醒，wakeup 将参数指定的进程唤醒。

以下讨论 生产者-消费者问题 (又称 有界缓冲区 (bounded-buffer) 问题) 问题的实际应用。生产-消费模型即两个进程共享一个公共的固定大小的缓冲区，这两个进程一个是生产者，将消息放入公共缓冲区中；一个是消费者，从缓冲区中读取消息。在缓冲区满的情况下，生产者如果再次生产消息，则通过 sleep 对进程进行阻塞，直到消费者消费消息时再次唤醒，产生消息。同样地，消费者消费没有消息的缓冲区时，也被阻塞，直到生产者为缓冲区填入消息时被唤醒。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

int size;
const int capcity = 100;
void producer(void) {
  while (true) {
    int item = product_item();
    if (size == capcity) sleep();
    insert_item(item);
    ++size;
    if (1 == size) wakeup(consumer);
  }
}
void consumer(void) {
  while (true) {
    if (size == 0) sleep();
    int item = remove_item();
    --size;
    if (size == capcity - 1) wakeup(producer);
    consume_item(item);
  }
}

以上代码虽然展示了生产-消费模型，但其中存在数据竞争，即对缓冲区大小 size 的访问没有加以限制。有可能出现：缓冲区为空时消费者读取 size 等于 0 时的值，但此时调度程序启用生产者而暂停消费者。生产者产生数据并将 size + 1，此时生产者使用 wakeup 唤醒一个消费者，由于消费者还未被阻塞，因此 wakeup 丢失。当消费者下次被调度时，由于上次读取到 0 值，因此被阻塞。当缓冲区被生产者填满时，生产者与消费者都会被阻塞。

问题的实质是向一个未被阻塞的进程发送的 wakeup 信号丢失，如果信号不丢失那么将不会产生任何问题。我们可以为进程加上一个 唤醒等待位，当发送一个 wakeup 信号给清醒的进程时，将唤醒等待位设置为 1，之后如果进程要被阻塞时，检查唤醒等待位，如果为 1 则清除掉继续运行。

信号量

信号量 (Semaphore) 由 E.W.Dijkstra 于 1965 年提出，使用整型变量来累计唤醒次数，供以后使用。一个 semaphore 的取值可以为 0 (没有保存下来的唤醒操作) 与正整数 (表示多次唤醒操作)。当 Semaphore 取值仅有 0 和 1 时，被称为 二元信号量 (binary semaphore)。信号量支持两种操作： down (消费一次唤醒直到 0 阻塞) 与 up (增加一次唤醒操作)。但是在 Dijkstra 的论文中，分别使用 P (荷兰语 Proberen，尝试，表示 down 操作) 与 V (荷兰语 Verhogen，增加，表示 up 操作) 来表示 Semaphore 的两种操作。Semaphore 另一个重要的用途是实现 同步 (synchronization)，保证某种事件的顺序发生或不发生，在程序设计语言 Algol 68 中首次引入。

在 Semaphore 进行操作时，所有动作是 原子性 的。原子 (Atom) 是从希腊语 ἄτομος (atomos，不可切分的) 转化而来，一个原子操作表示一组相关联的操作要么都不间断的执行，要么都不执行，整个过程是不可分割的。原子操作在计算机科学领域与解决同步、竞争问题是非常重要的。为了完成原子操作，引号量采用 TSL 或 XCHG 指令保证只有一个 CPU 对信号量进行操作。这与忙等待不同，忙等待可能在一个任意长的时间内进行，而 Semaphore 只需要几毫秒。

互斥量

当不需要信号量的计数能力时，可以简化为二元版本，称为 互斥量 (mutex)。互斥量仅适用于管理共享资源或一小段代码，但由于其实现容易、有效，在用户空间线程包的实现时非常有用。

随着并行的增加，有效的同步和锁机制对性能而言十分重要。如果等待时间很短，自旋锁将会很快，但随着等待时间的增长，将会有大量 CPU 周期被浪费。如果存在很多竞争时，那么阻塞此进程，并仅当锁释放的时候让内核解除阻塞会很有效果，但只有很小的竞争时，频繁的陷入内核与切换线程的开销将变得十分巨大，并且锁竞争的数量不是很容易预测的。

Linux 实现了 快速用户空间互斥 (futex)，它实现了基础的锁，但避免陷入内核。futex 包含两个部分，一个内核服务和一个用户库。内核服务提供一个等待队列，它允许多个进程在一个锁上等待。它们将不会运行，除非内核明确地对它们解除阻塞。将一个进程放到等待队列需要系统调用，因此我们尽可能地避免这么做。在没有竞争时，futex 完全工作在用户空间。

pthread 提供了锁设施用于数据竞争，同时提供了同步机制：条件变量。在允许或阻塞对临界区的访问时互斥量是很有用的，而条件变量则是允许线程由于一些未达成的条件而阻塞。绝大多数情况下，这两种方法是合作使用的。

需要注意的是，条件变量与信号量不同的是，不会存在与内存中。因此一个将一个信号传递给一个没有线程在等待的条件变量，那么这个信号就会消失。

管程

由于在编写多进程、多线程代码时，极易出现问题，并且这些错误都是竞争条件、死锁以及一些不可预测、不可复现的行为。为了更易于编写正确的程序，出现了一种高级同步原语 管程 (monitor)。一个 monitor 是由一个过程、变量以及数据结构等组成的集合，它们组成了一个特殊的模块或者说软件包。进程可以在任何需要的时候调用 monitor 中的过程，但它们不能在 monitor 之外直接访问内部的数据结构。

管程有一种很重要的特性，即任一时刻管程中只能有一个活跃的进程，这是一种有效的互斥原语。管程是编程语言的一部分，编译器可以对其进行特殊处理，来保证其互斥特性。

消息传递和屏障

信号量是一种低级的进程间通信方式，而管程存在于少数语言当中，因此它们无法用于跨计算机的进程通信。操作系统提供了一种跨机器的进程通信原语，即消息传递 (message passing)，它包含两个调用 send (将消息发送给特定目标) 和 receive (从给定源中接收消息)。如果当前没有消息可用，接收者可能会被阻塞 (直到消息达到) 或返回错误代码。

由于在网络上传输数据，因此消息传递必须考虑在网络不佳时，导致的消息丢失。并且还需要解决进程命名问题，在消息传递中的进程必须是没有二义性的。其次身份认证也是一个问题。

在消息传递中，可以为每个进程分配一个唯一地址，让消息按照进程的地址进行编址，或者引入全新的数据结构 信箱 (mailbox)，对一定数量的消息进行缓存。使用有缓存的信箱时，当信箱被填满时发送者将被阻塞，当信箱为空时，接收者会被阻塞。而没有缓存的信箱，发送者会被阻塞直到接收者调用 receive 接收消息，反之也会被阻塞，这种情况被称为 会合 (rendezvous)。

屏障 (barrier) 是用于进程组的一种同步机制。在一些应用中划分了若干阶段，并规定除非所有进程都准备就绪，否则任何进程都不会进入下一阶段，此时可以在每阶段的结尾安置 barrier。

调度

通常有多个进程或线程同时竞争 CPU，只要有两个或更多的进程处于就绪状态，调度就会发生。如果只有一个 CPU 可用，那么必须选择下一个要运行的进程。在操作系统中，完成选择工作的这一部分称为 调度程序 (scheduler)，该程序使用的算法被称为 调度算法 (scheduling algorithm)。

在早期以磁带上的卡片作为输入的批处理系统时代，调度算法很简单，依次运行磁带上的每个作业。对于多道程序设计系统，调度算法要复杂一些，因为经常有多个用户等待服务。有些大型机系统仍将批处理和分时服务结合使用，需要调度程序决定下一个运行的是一个批处理任务还是终端上的一个交互用户。CPU 是稀缺资源，所以好的调度程序可以在提高性能与用户满意度方面取得很大的成果。对于个人计算机多数时间内只有一个活动进程，且主要限制的是用户当前的输入速率而不是 CPU 处理速率，因此调度程序在个人计算机中并不是很重要。目前个人计算机主要在绘制高精度视频时需要大量且高强度的计算。在网络服务器上，多个进程经常竞争 CPU，因此调度功能变得十分重要。在移动设备上资源并不充足，CPU 薄弱并且电量也是重要限制，因此调度算法主要在于优化电量损耗。

为了选择正确的进程运行，调度程序还要考虑 CPU 的利用率，因为进程切换的代价是比较高的。首先用户态必须切换到内核态，然后要保存当前进程的状态，包括在进程表中存储的寄存器，在很多系统中内存映像 (页表内的内存访问位) 也会保存，接着将心进程的内存映像装入 MMU，最后新进程开始运行。进程切换还会使整个 Cache 失败，强迫缓存从内存中动态装入两次。

在进程具有较长时间的 CPU 集中使用和较小的频度的 I/O 等待，这种进程被称为 CPU 密集型 进程。反之具有较短时间的 CPU 集中使用和频繁的 I/O 等待的进程，被称为 I/O 密集型 进程，这些进程并不是拥有特别长的 I/O 时间，而是它们的 I/O 请求频繁。在 I/O 开始后无论处理数据多还是少，它们都花费同样的时间提出硬件请求。随着 CPU 的速度越来越快，更多的进程开始偏向于 I/O 密集型，为此未来对 I/O 密集型进程的调度变得尤为重要。

有关调度处理的一个关键问题，在于何时进行调度决策。

1. 在创建新进程后需要决定是运行父进程还是子进程。由于两个进程都是就绪状态，因此调度程序可以任意决定运行的进程。
2. 在一个进程退出时必须做调度决策。进程退出后，调度程序必须从就绪进程集中选择一个进程运行，如果没有可运行的进程，通常会运行一个系统提供的空闲进程。
3. 当一个进程阻塞在 I/O 或 Semaphore 等原因的阻塞时，必须选择一个进程运行。有时阻塞的原因会成为选择的因素。
4. 在一个 I/O 中断发生时，必须做出调度决策。如果中断来自 I/O 设备，而该设备现在完成了工作，某些被阻塞的等待该 I/O 的进程就成为可运行的进程了。是否让新就绪的进程来运行，或中断发生时正在运行的进程运行，这取决于调度程序。

如果硬件时钟提供 50 、 60 Hz 或其他频率的周期性中断，可以在每个或每 k 个时钟中断时做出调度决策。根据如何处理时钟中断，可以把调度算法分为两类。

1. 非抢占式 调度算法会挑选一个进程，并让该进程运行直至被阻塞，或直到进程主动放弃 CPU 时。因此非抢占式调度不会强迫进程挂起，即使该进程已运行了几个小时。这种调度方式是没有时钟时的唯一选择。
2. 抢占式 调度算法会挑选一个进程，并让该进程运行某个固定时段的最大值。如果该进程在时段结束后仍在运行，则会被挂起并调度其他进程。这种调度方式需要在时间间隔末端发生时钟中断，以便 CPU 的使用权可以分配给调度程序。

由于不同的应用领域与操作系统有不同的目标，不同的环境中需要不同的调度算法，调度程序的优化也是不同的。主要将环境分为三种：

1. 批处理
2. 交互式
3. 实时

调度算法的目标也会根据环境的不同而有所不同。

1. 所有系统
   1. 公平。每个进程公平的 CPU 份额
   2. 策略强制执行。保证规定的策略被执行
   3. 平衡。保持系统的所有部分都忙碌
2. 批处理系统
   1. 吞吐量。每小时最大作业数
   2. 周转时间。从提交到终止的最小时间
   3. CPU 利用率。保持 CPU 始终忙碌
3. 交互式系统
   1. 响应时间。快速响应请求
   2. 均衡性。满足用户的期望
4. 实时系统
   1. 满足截止时间。避免丢失数据
   2. 可预测性。在多媒体系统中避免品质降低

批处理系统中的调度

先来先服务

在所有的调度算法中，最简单的非抢占式的即是 先来先服务 (First-Come First-Served, FCFS) 算法。使用该算法，即采用队列数据结构，将最先请求使用 CPU 的进程最先调度。

FCFS 最主要的优点即 易于理解 且 便于运行。这个算法中，单链表记录了所有就绪进程，当需要选取进程时只需要从表头选择即可；当添加一个新的作业或阻塞一个进程时，只需要将进程添加到链表的尾部。但是其缺点很明显，即 平均等待时间过长。当前面的进程有着相当大的 CPU 执行时间时，排在后面的进程就会显著增加其等待时间，最终导致平均等待时间的增长。

比如 3 个进程，\(P_1\) 进程执行 24 ms，\(P_2\) 和 \(P_3\) 进程各执行 3 ms，按 FCFS 执行时平均等待时间为 \((0 + 24 + 27) / 3 = 17 ms\)。

最短作业优先

当运行时间可以预知时，可以采用非抢占式算法 最短作业优先 (Shortest Job First， SJF)。即使用优先队列以进程运行时间对将要调度的进程进行排序，运行时间最短的进程最先被调度，运行时间最长的进程最后被调度。当一组给定且已知时间的进程，可以求得 SJF 算法是最优的，其平均等待时间最短。

以 FCFS 中的例子计算，使用 SJF 算法的平均等待时间为 \((0 + 3 + 6) / 3 = 3 ms\)。

SJF 的抢占式版本即最短剩余时间优先 (Shortest Remaining Time Next，SRTN) 算法，调度程序总是选择剩余运行时间最短的那个进程运行。这种方式可以使新的短作业获得良好的服务。

交互式系统中的调度

轮转调度

轮转调度 (round robin) 是一种 最古老、最简单、最公平 且 使用最广 的调度算法，每个进程被分配一个时间段，称为 时间片 (quantum)，即允许该进程在该时间段中运行。如果在 quantum 结束时该进程依然在运行，则剥夺 CPU 并分配给其他进程。如果该进程在 quantum 结束前阻塞或结束，则立即切换进程。

轮转调度中最有趣的即是时间片的大小。从一个进程切换到另一个进程是需要一定时间进行事务处理的，即我们之前说的保存、装入寄存器值与内存映像等。假设 进程切换 (process switch) 或称 上下文切换 (context switch) 需要 1 ms，时间片大小为 4 ms，那么 CPU 将会有 \(20\%\) 的时间被浪费在进程切换中。如果将时间片调整为 100 ms，那么 CPU 仅浪费 \(1\%\) 的时间，但是如果有 50 个可运行进程且每个进程都会使用完整的时间片，那么最后一个进程需要等待 5 秒才可以使用到 CPU。如果时间片的大小长于平均的 CPU 突发时间，那么不会经常发生抢占。相反，在时间片耗费完之前多数进程会完成一个阻塞操作引起进程切换。抢占的消失改善了性能，因为进程切换只会发生在确实逻辑上有需要的时候，即进程被阻塞不能继续运行。

简单来说，太短的 quantum 会导致频繁的进程切换，降低 CPU 效率；太长的 quantum 可能引起对短交互请求的响应时间变长。因此 quantum 一般设置为 20 ~ 50 ms 一个比较折中的长度。

优先级调度

轮转调度做了一个隐含的假设，即所有的进程同等重要，而拥有和操作多用户计算机系统的人对此常有不同的看法，将外部因素考虑在内的需要就导致了 优先级调度 。其基本思想很清楚，每个进程被赋予一个优先级，允许优先级最高的可运行进程先运行。为了防止高优先级进程无休止的运行，低优先级进程可能出现饥饿现象，调度程序可能在每个时钟中断降低当前进程的优先级，如果当前进程的优先级低于次高级优先级的进程，则进行进程切换。另一种方法是，每个进程拥有一个运行的最大时间片，当时间片耗尽时，调度次高优先级的进程。

优先级可以是静态赋予或动态赋予的，也可以由系统动态确定。例如有些 I/O 密集型进程，多数时间用来等待 I/O 结束，当这样的进程需要 CPU 时，应立即分配 CPU 以便启动下一个 I/O 请求，这样就可以在另一个进程执行计算时执行 I/O 操作。使这类 I/O 密集型进程长时间等待 CPU 只会造成其无谓地长时间占用内存。使 I/O 密集型进程获得较好服务的一种简单方法是，将其优先级设置为 \(1/f\)，其中 \(f\) 为该进程在上一时间片中所占用的部分。另一种方式是让用户进程主动的调整进程的优先级，如此可以使调度机制采用适用于当前环境的调度策略。

相容分时系统

相容分时系统 (Compatible Time Sharing System，CTSS) 是 MIT 在 IBM 7094 上开发的最早使用优先级调度的系统之一。CTSS 中存在进程切换速度太慢的问题，这与 IBM 7094 内存中只能存在一个进程有关。CTSS 的设计者很快便认识到，为 CPU 密集型进程设置较长的时间片比频繁分给它们时间片更加高效，但长时间片又会影响到响应时间。其解决方法即建立优先级类，最高优先级的进程运行 1 个 quantum，次高优先级进程运行 2 个 quantum，再次一级运行 4 个 quantum，以此类推。

当一个进程用完分配的 quantum 后，被移动到下一级。如此，以前可能需要 100 次调度的进程，可以减少到 7 次调度，并且随着优先级的不断降低，它的运行频率会不断放慢，从而为短的交互进程让出 CPU。对于刚刚运行过长时间但又需要交互的进程，为防止其永远处于惩罚状态，可以将其调整到高优先级队伍，提高其响应速度。

最短进程优先

SJF 算法往往有着最短响应时间，所以如果能够把其用于交互式进程是最好的。当前的问题是如何找出当前可运行进程中最短的那个进程。

可以根据进程过去的行为进行推测，并执行估计运行时间最短的那个。假设某终端上每条命令的估计运行时间为 \(T_0\) ，现在假设测量到其下一次运行时间为 \(T_1\) 。可以用这两个值的加权和 \(\alpha T_0 + (1-\alpha) T_1\) 来改进估计时间。通过选择 \(\alpha\) 的值，可以决定是尽快忘掉老的运行时间，还是在一段长时间内始终记住他们。当 \(\alpha = 1 / 2\) 时，可以得到如下序列：

\[T_0, \quad \frac{T_0}{2}+\frac{T_1}{2}, \quad \frac{T_0}{4}+\frac{T_1}{4}+\frac{T_2}{2}, \quad \frac{T_0}{8}+\frac{T_1}{8}+\frac{T_2}{4}+\frac{T_3}{2}, \quad \dots\]

可以看到，三轮过后，\(T_0\) 在新的估计值中所占的比重下降到了 \(1 / 8\)。将这种通过当前测量值与先前估计值进行加权平均而得到下一个估计值的技术，称为 老化 (aging)，它适用于许多测量值必须基于先前值的情况。

其他调度算法

保证调度

向用户作出明确的性能保证并实现它，是一种独特的调度算法。如现在有 n 个用户登陆终端，可以保证每个用户将会获得 CPU 处理能力的 \(\frac{1}{n}\)。或者说，在单用户系统中，帮证运行的 n 个进程，每个都可以获得 \(\frac{1}{n}\) 的 CPU 时间。为了实现所做的保证，系统必须跟踪各个进程自创建以来，已使用的 CPU 时间，然后计算各个进程应获得的时间。

彩票调度

为用户做出承诺并兑现，是一个好方法，但难以实现。有一个既可以给出类似预测结果又可以简单实现的算法，即 彩票调度 (lottery scheduling)。其基本思想是：为进程提供各个系统资源的彩票，一旦需要做出一项调度决策时，就随机抽出一张彩票，拥有该彩票的进程获得资源。比如系统可以掌握每秒 50 次的彩票，作为奖励每个获奖者可以获得 20 ms 的 CPU 时间。所有进程是平等的，但某些进程更平等一些，对于重要的进程可以分配额外的彩票，以便增加它们的获胜机会。比如一共 100 张彩票，一个进程持有其中的 20 张，那么该进程在较长的运行中会得到 \(20\%\) 的系统资源。即拥有彩票 f 份额的进程大约得到系统资源的 f 份额。

公平分享调度

我们假设被调度的都是进程自身，并不关注其所有者是谁。这样的结果就是，如果用户 A 拥有 9 个进程，而用户 2 拥有 1 个进程，那么轮转调度或同优先级调度算法中，用户 2 仅能使用 CPU 的 \(90\%\) 。为避免这样的情况，可以在调度处理前考虑谁拥有该进程，让每个用户可以公平的分配 CPU 时间，而调度程序以强制的方式选择进程。

实时系统中的调度

实时系统是一种时间起主导作用的系统。典型地，一种或多种外部物理设备发给计算机一个服务请求，计算机必须在一个确定的时间范围内恰当地做出反应。比如音乐播放器必须在非常短的时间间隔内将 bit 流转为音乐，否则听起来就会十分的诡异。因此在这类系统中 正确但迟到的应答往往比没有更加糟糕。

实时系统通常可以分为 硬实时 (hard real time) 与 软实时 (soft real time)，前者是必须满足绝对的截止时间，后者是虽然不希望偶尔错失截止时间但可以容忍。实时性能都是通过把程序分为一组进程而实现的，每个进程的行为是可预测和提前掌握的。这些进程一般寿命较短，且极快完成。在检测到一个外部信号时，调度程序的任务就是按照满足所有截止时间的要求调度程序。

实时系统中的时间可以按照效应方式进一步分为 周期性 与 非周期性 事件，一个系统可能要响应多个周期事件流。根据每个事件要处理时间的长短，系统甚至有可能无法处理完所有事件。如果有 m 个周期事件，事件 i 以周期 \(P_i\) 发生，并需要 \(C_i\) 秒 CPU 时间处理，那么可以处理负载的条件是 \[\sum_{i=1}^{m} \frac{C_i}{P_i} \leq 1\]

满足这个条件的实时系统称为是 可调度的，这意味着它实际能够被实现的。一个不满足此检测标准的进程不能被调度，因为这些进程共同需要的 CPU 时间总和大于 CPU 能够提供的时间。这里假设进程切换的开销极小，可以忽略不计。

实时系统的调度算法可以是静态或动态的，前者在系统开始运行之前做出调度决策，后者在运行过程中进行调度决策。只有在可以提前掌握所完成的工作以及必须满足的截止时间等全部信息时，静态调度才能工作，而动态算法并不需要这些限制。

经典的 IPC 问题

哲学家就餐问题

Dijkstra 于 1965 年提出并解决了 哲学家就餐 的同步问题，该问题属于互斥访问有限资源的竞争问题，自那时起每个发明新的同步原语的人都希望通过解决哲学家就餐问题来展示其原语的精妙之处。

最直观的解决方法，即指定哲学家可用的叉子，并在指定的叉子可用时取用。但是有一个明显的问题，即所有哲学家同时拿起左面的叉子，就没有人可以拿到他们右面的叉子。如此情况就会发生 死锁 (deadlock)。稍加修改，可以在拿起左叉后检查另一把叉子是否可用，不可用则放下叉子。这也有一个显著的问题，即所有哲学家同时拿到左叉，发现右面的叉子不可用，又都放下手中的叉子，一段时间之后如此重复下去。对于这种情况，所有程序都在不停的运行，但又无法取得进展，如此被称为 饥饿 (starvation)。

当使用 binary semaphore 时既不会 deadlock 也不会 starvation，在拿起叉子之前对 semaphore 进行 P 操作，并在结束用餐时进行 V 操作。此方法可行，但只能有一位哲学家进餐。对其进行扩展，采用一个 binary semaphore 数组表示哲学家的进餐状态，即可最大程度的并行。

读者-写者问题

读写者问题为数据库访问建立了一个模型，多个读进程可以同时进行，但读进程与写进程互斥，当写进程进入临界区后将与任何进程互斥。