现代操作系统 - 进程与线程及其调度

进程#

new: 进程刚被创建但还没有完成初始化
ready: 进程可以被调度执行
running: 进程正在 CPU 上执行
blocked: 被阻塞，需要等待外部事件完成
terminated: 执行完成，不会再被调度

进程地址空间
内核代码及数据
内核栈
用户栈
⬇️
共享库，只读 (如 libc)
⬆️
用户堆
数据段 (全局变量)
代码段

Linux 使用 fork 从当前进程中创建一个新的子进程：对于父进程 fork 返回子进程的 PID; 对于子进程 fork 返回 0 执行 fork 时子进程会复制父进程 PCB(Process Control Block) 中的数据，比如打开的文件描述符表，但是两进程 FD 表中指向的文件数据结构是相同的 (相当于只复制了指针) 导致两进程共享一份打开文件的指针，在读取文件时受到共享偏移量的影响，读取的数据并不一致。

子进程复制父进程数据

通过 fork 可以得到一个和父进程几乎相同的子进程在 Linux 下还可以通过 exec 系列接口在当前进程中执行新的程序。使用 execve 后操作系统会执行以下操作:

根据指定的可执行文件路径将数据段和代码段载入地址空间
重新初始化堆和栈并进行 地址空间随机化 改变堆栈起始地址
将 PC 寄存器设置到可执行文件代码段的入口

Linux 的第一个进程是 init 进程，所有进程都是通过 fork 创建的，每个进程都会记录自己的父子进程，由此所有进程形成了一颗进程树。父进程可以通过 wait 监控子进程的退出并检查其状态，比如是否异常退出。如果父进程没有执行或者还没来得及执行 wait 调用子进程就已经退出，此时子进程的资源并不会被完全回收 Linux 下称这种进程为 zombie 进程。

Linux 内核定义了 进程组 process group 的概念，即由多个进程组成的集合，应用进程可以用过 killpg 向一个进程组发送信号，此信号会发送到组内的所有进程。多个进程组的集合构成 会话 session 会话将进程组分为前台进程组和后台进程组，前台进程组一般用于接受 控制终端 controlling terminal 进程的输入 (比如标准输入或者信号等)。会话和进程组主要用于 Shell 环境的进程管理。

线程#

线程是进程内可以独立执行的单元，同一进程内的所有线程共享同一份地址空间，但是拥有不同的运行上下文：比如寄存器状态和栈。多线程应用的地址空间分布如下:

有多个线程的进程地址空间
内核代码及数据
内核栈 1
内核栈 2
内核栈 2
...
用户栈 1
用户栈 2
用户栈 3
...
共享库，只读 (如 libc)
⬆️
用户堆
数据段 (全局变量)
代码段

操作系统内线程分为用户态线程和内核线程，用户态线程如果要进行系统调用需要进入到内核线程中去执行，所以需要为每个用户态线程分配对应的内核线程。分配方式有多种:

多对一：多个用户线程对应一个内核线程，缺点是同时只能有一个用户线程进入内核
一对一：每个用户线程对应一个内核线程，缺点是内核线程的数量会随着用户进程的增多而增多
多对多：将 N 个用户线程对应 M 个内核线程 (N> M) 需要内核对映射关系做管理和调度

每个线程有一个 Thread Control Block TCB 数据结构用于保存线程的上下文信息。

用户态线程可以创建特殊的 Thread Local Storage TLS 线程局部存储变量，多个线程可以使用同一个 TLS 变量，但是每个线程读写的都只是本线程内的数据拷贝。如下伪代码:

__thread int count; // 声明一个 TLS 变量

thread1.set(&count, 1); // 线程1写 count
thread2.set(&count, 2); // 线程2写 count
thread1.get(&count) == 1; // 线程1读 count 的结果是 1
thread1.get(&count) == 2; // 线程2读 count 的结果是 2

在 x86-64 架构中，当一个线程被调度时 libpthread 会将该线程的 TLS 起始地址写入到 FS 段寄存器内，线程访问 TLS 变量时会使用 FS 寄存器中的地址加上变量偏移量进行访问，即实际上多线程读写各自的 TLS 变量时使用的地址是不同的。

在 Linux 下线程的创建，退出等操作都是通过调用 libpthread 接口实现:

pthread_create: 在当前进程内创建一个线程，运行指定的函数，底层通过 clone 调用实现
pthread_exit: 结束当前线程，函数执行结束时会隐式调用，可以通过主动调用设置返回值
pthread_yield: 主动暂停当前线程，让出资源，等待下一次调度，但是线程仍处于 ready 状态
pthread_join: 等待指定的线程结束并获取其返回值
pthread_cond_wait: 等待一个指定的条件变量，用于多线程同步

调度概念#

调度的指标#

吞吐量：单位时间内处理的任务数量
周转时间：任务从开始执行到结束执行的耗时
响应时间：交互式任务的请求响应耗时
实时性：实时任务的完成度 (某些任务需要在指定 deadline 前完成)
能耗
资源利用率
公平性
调度器本身的开销

长期，中期与短期调度#

长期调度#

长期调度主要控制系统中可以被调度的任务总量，比如短时间内大量的进程被创建，长期调度不会立即将所有进程都转移到 ready 状态 (对于实时性要求较高的交互式任务例外), 否则会造成任务数量剧增调度开销增大。另外长期调度会根据当前系统的 CPU 和 I/O 使用情况适当平衡可以被调度的进程，避免同时有大量的 I/O 任务或 CPU 任务造成剧烈的资源竞争和利用率不足。总的来说长期调度通过决定是否将一个任务纳入调度来控制总量，降低短期调度的压力。

短期调度#

短期调度执行具体的调度决策，将任务的状态在 blocked/ready/running 之间转换。比如:

处于 running 状态的进程如果执行时间超过预估的时间片会被调度抢占，转换为 ready 状态等待下一次调度
任务执行或等待 I/O 时会被转换为 blocked 状态等到 I/O 事件就绪时转换为 ready 状态
软 / 硬件 (比如时钟) 中断，系统调用等会中断任务的执行

中期调度#

中期调度是换页机制的一部分，主要是控制系统中可运行和正在运行任务的内存使用，避免使用量超出内存资源总量。实际运行过程中，如果系统中的任务已经占用了大量的内存，中期调度会选取某些任务 (比如频繁触发缺页异常的任务) 将其挂起 suspend 而后换页机制会倾向于将被挂起的进程内存换出到磁盘以缓解系统的内存压力。被挂起的任务也无法被短期调度使用，进一步降低短期调度的压力。

总体调度示意图:

操作系统进程调度

调度机制#

优先级调度#

时间片轮转：每个任务执行指定时间片的时间，然后切换到下一个任务。这种调度策略会导致平均的周转时间变长 (比如系统中一共就两个任务，时间片轮转会耗费大量的时间在两个任务的切换上)。而且需要平衡时间片的大小：如果太小，调度和状态转换的开销会很大；如果太大会造成某些任务延迟过高。

考虑到交互式任务的实时性需求，可以为每个进程指定一个优先级，高优先级的任务 (比如交互式任务或者实时任务) 会先被调度器执行。

实际运行时一般会有多个具有高优先级的任务，因此可以使用 多级队列 的方式将所有任务分配到不同的优先级，依旧是高优先级任务先执行，但是同一优先级内的多个任务会放在一个队列中通过时间片轮转或者其他策略进行调度。此种策略可能会造成低优先级的任务长时间无法执行。

在多级队列的基础上，还可以根据任务的运行情况，动态调整优先级，称为 多级反馈队列 Multi-Level Feedback Queue 此种方式倾向于将将短任务 (比如 I/O 密集型和交互式这种在 CPU 上运行时间较短的任务) 设置更高的优先级，以获取更好的平均周转时间。

动态调整优先级策略：在任务运行之初 MLFQ 会将新任务设置较高的优先级 (便于交互和实时任务), 在每个优先级上 MLFQ 会设置一个最长运行时间 (任务多次运行的总时间) 如果任务在此队列上的运行时间超过此时间则 MLFQ 会认为此任务是一个较长的任务，将其调整至下一级队列，多次运行后该任务会根据执行时间情况被调整到一个合适的优先级。

由于低优先级的任务一般是长任务，所以低优先级队列的时间片也会比较长，高优先级队列同理时间片会比较短。

公平共享调度#

除了提升调度指标以外，某些情况下还需要实现对资源的公平调度。比如用户 A 和用户 B 花费同样的价格共享一台机器但是用户 A 运行了三个进程而用户 B 只运行了一个进程，此时系统需要保证用户 A 和用户 B 各自都能占用 50% 的资源，即 CPU 的时间片。

彩票调度#

彩票调度为每个任务分配一定份额的彩票，每次调度时抽取一个中奖号码，根据此中奖号码选取需要执行的任务，类似于带权重的随机，伪代码如下:

loop:
    R = random(0, total_tickets)
    for sum = 0; task in task_list; {
        sum += task->tickets
        if sum > R {
            schedule(task)
            goto loop
        }
    }

通过此种方式为每个用户分配相同的彩票额即可保证 CPU 时间的公平分配。但实际的分配情况依赖随机，在调度次数较少的情况下由于随机数据不平均可能会导致短期的分配不平均。

步幅调度#

步幅调度通过设置步幅确定性的为任务分配公平的时间，消除彩票调度的随机性影响。

假设两个任务 A 和 B 应分配的资源比例是 6:5 则步幅调度使用其反比作为其步幅，即 A 和 B 的步幅为 5 和 6 步幅调度会设置一个固定的时间片，每次选取当前已走距离最小的任务执行一次，并将其走过的距离加上对应的步幅。由于步幅不同，两任务最终执行的时间片数量比会是 6:5 即达到稳定公平分配的目的。伪码如下:

loop:
    task = queue.pop_min()
    schedule(task)
    task.pass += task.stride
    queue.push(task)
    goto loop

多核调度#

在多核场景下由于系统可以同时运行多个任务，调度器需要决定同一时间有有哪些任务可以进行，这些任务分别在哪个核心上运行。还需要考虑在同一核心上，如果调度不同任务，频繁切换造成的性能损耗 (页表切换，寄存器存取等)

协同调度#

对于某些任务间有关联的场景，比如有请求 - 响应关系的两个任务，如果不能同时运行即 A 发送消息时 B 并没有在运行那这个消息要等到下次 B 被调度时才能收到，且 B 在被调度运行时 A 可能又会被调度出去返回的消息没办法立即接收，这样每次发送请求和返回响应都会由于调度产生至少一个时间片的延迟，降低程序的运行效率。对于此类场景，需要使用协同调度：每次调度一组任务并行执行，这样可以将具有关联关系 (需要同时运行) 的任务可以分配到同一组内并行执行，而具有依赖关系的任务 (某个任务必须等待另外一个任务执行完) 需要分配到不同的组，避免空等造成 CPU 资源浪费。

协同调度一般用于并行计算，即将一个大的任务切分成多个子任务在多核心上并行执行加快计算。但是在更为普遍的场景下，使用协同调度可能会由于组内任务的相互等待 (注意：协同调度是以组为单位而非任务) 造成 CPU 资源的浪费。

协同调度的一个经典策略是群组调度，基本思想是将所有任务分成不同的组，将关联任务分配至同一组，并且以组为单位，调度任务在多个核心上运行。比如现在有 4 个 CPU 核心和三组任务 A/B/C 每个组内分别有 4/3/2 个任务，则调度情况如下:

Core 0	Core 1	Core 2	Core 3
A0	A1	A2	A3
B0	B1	B2	C1
C2	A0	A1	A2

两级调度#

多核心场景下，考虑任务在不同核心间的切换开销，可以将某个任务固定到一个核心上进行调度和执行。即新任务首先通过一个全局调度器分配到某个核心上，每个核心再通过单核调度策略执行分配给自己的任务，在系统运行过程中，全局调度器也会根据每个核心的负载情况，平衡任务在不同核心间的分配。这种调度方式称为两级调度。

处理器亲和性#

某些操作系统在自己运行的调度器之上，为用户进程提供了处理器亲和性相关的调用接口，可以让应用进程自己控制 CPU 核心使用情况，比如 Linux 提供了 sched_setaffinity 接口可以让用户进程控制自己只能在某些核心上执行。