进程与线程

1. 进程（Process）

1.1 定义

进程是程序的一次执行实例，是操作系统进行资源分配的基本单位。

每个进程拥有独立的：

虚拟地址空间（代码段、数据段、堆、栈）
文件描述符表
信号处理表
进程 ID（PID）

1.2 进程控制块（PCB）

操作系统用 PCB（Process Control Block） 维护每个进程的元数据：

字段	内容
PID	进程标识符
进程状态	Running / Ready / Waiting / ...
PC（程序计数器）	下一条待执行指令地址
CPU 寄存器	通用寄存器、栈指针等快照
调度信息	优先级、调度队列指针
内存管理信息	页表基址、段表
I/O 状态	打开的文件列表、I/O 请求

1.3 进程状态转换

stateDiagram-v2
    [*] --> New: 创建
    New --> Ready: 允许进入就绪队列
    Ready --> Running: 调度器选中
    Running --> Ready: 时间片用完 / 被抢占
    Running --> Waiting: 等待 I/O 或事件
    Waiting --> Ready: I/O 完成 / 事件发生
    Running --> Terminated: 执行结束 / 异常退出
    Terminated --> [*]

1.4 进程创建与终止

UNIX/Linux 模型：

fork()：创建子进程（复制父进程地址空间，COW 优化）
exec()：替换进程映像为新程序
wait() / waitpid()：父进程等待子进程终止
exit()：进程终止

进程树：所有进程形成以 init/systemd（PID 1）为根的树。

2. 线程（Thread）

2.1 定义

线程是 CPU 调度的基本单位，同一进程的线程共享地址空间和资源。

属性	进程	线程
地址空间	独立	共享（同进程）
创建开销	大（需复制地址空间）	小（仅需栈和寄存器）
上下文切换	慢（需切换页表、TLB flush）	快（共享地址空间）
通信方式	IPC（管道、消息、共享内存）	直接读写共享变量
隔离性	强	弱（一个线程崩溃影响全进程）

2.2 线程实现

类型	实现位置	优势	劣势
用户级线程	用户空间线程库	切换快、无需内核参与	一个线程阻塞→整个进程阻塞
内核级线程	操作系统内核	真正并行、可利用多核	切换需陷入内核，开销大
混合模型	M:N 映射	兼顾两者优势	实现复杂

现代实践：

Linux：1:1 模型（NPTL），每个用户线程对应一个内核线程
Go：M:N 模型（goroutine → OS thread），运行时调度器管理

2.3 上下文切换

上下文切换的开销：

操作	开销来源
保存/恢复寄存器	直接 CPU 时间
TLB 刷新（进程切换）	切换后 TLB miss 增加
Cache 污染	新进程/线程的数据挤出旧数据
流水线刷新	分支预测器状态失效

典型开销：进程切换 ~1-10 μs，线程切换 ~0.1-1 μs。

3. CPU 调度

3.1 调度准则

指标	含义	优化目标
CPU 利用率	CPU 忙碌时间占比	最大化
吞吐量	单位时间完成的进程数	最大化
周转时间	提交到完成的总时间	最小化
等待时间	在就绪队列中等待的总时间	最小化
响应时间	提交到首次响应的时间	最小化（交互式系统）

3.2 调度算法

FCFS（First Come First Served）

先到先服务，非抢占式
护航效应（Convoy Effect）：长进程阻塞后面的短进程

SJF / SRTF

SJF（Shortest Job First）：选择预计运行时间最短的进程（非抢占）
SRTF（Shortest Remaining Time First）：SJF 的抢占版本
理论最优（最小化平均等待时间），但需要预知运行时间

\[ \text{平均等待时间}_{\text{SJF}} \leq \text{平均等待时间}_{\text{其他算法}} \]

实际中使用指数加权移动平均预测下次 CPU burst：

\[ \tau_{n+1} = \alpha \cdot t_n + (1 - \alpha) \cdot \tau_n \]

Round Robin（时间片轮转）

每个进程获得固定时间片（quantum） \(q\)
时间片耗尽 → 回到就绪队列尾部
\(q\) 太大 → 退化为 FCFS；\(q\) 太小 → 上下文切换开销过大
典型值：10-100 ms

MLFQ（Multi-Level Feedback Queue）

现代操作系统的基础调度框架：

规则：

高优先级队列的进程优先执行
同优先级队列内使用 Round Robin
新进程进入最高优先级队列
用完时间片 → 降级到下一级队列
定期将所有进程提升到最高优先级（Boost，防饥饿）

优先级 高  [Q0] ── RR, quantum = 8ms
          [Q1] ── RR, quantum = 16ms
          [Q2] ── RR, quantum = 32ms
优先级 低  [Q3] ── FCFS

I/O 密集型进程：频繁让出 CPU → 保持在高优先级 → 响应快
CPU 密集型进程：用尽时间片 → 逐渐降级 → 不影响交互性

CFS（Completely Fair Scheduler）

Linux 默认调度器（自 2.6.23 起）：

目标：每个进程获得公平的 CPU 时间份额
使用虚拟运行时间（vruntime）追踪每个进程已获得的CPU时间
用红黑树维护就绪队列，vruntime 最小的进程优先运行
nice 值影响 vruntime 增长速率

4. 进程同步

4.1 竞态条件（Race Condition）

多个线程并发访问共享数据，最终结果取决于执行顺序。

临界区（Critical Section）：访问共享资源的代码段，需要互斥保护。

临界区解决方案需满足：

互斥（Mutual Exclusion）：同时只有一个线程在临界区
进展（Progress）：不在临界区的线程不能阻止他人进入
有界等待（Bounded Waiting）：等待进入临界区的时间有上界

4.2 同步原语

互斥锁（Mutex）

pthread_mutex_lock(&mutex);    // 获取锁（阻塞）
// 临界区
pthread_mutex_unlock(&mutex);  // 释放锁

实现基础：原子指令（CAS、test-and-set、LL/SC）

自旋锁（Spinlock）

while (test_and_set(&lock) == 1)
    ; // 忙等待（spin）
// 临界区
lock = 0;

等待时间短时高效（无上下文切换）
等待时间长时浪费 CPU
适合多核环境下的短临界区

信号量（Semaphore）

Dijkstra 提出，是更通用的同步机制：

P（wait/down）：\(S \leftarrow S - 1\)，若 \(S < 0\) 则阻塞
V（signal/up）：\(S \leftarrow S + 1\)，若有等待者则唤醒一个

类型	初始值	用途
二元信号量	1	等价于互斥锁
计数信号量	\(N\)	控制资源并发访问数

条件变量（Condition Variable）

与 mutex 配合，允许线程在条件不满足时等待：

pthread_mutex_lock(&mutex);
while (!condition)
    pthread_cond_wait(&cond, &mutex);  // 原子释放锁+睡眠
// 条件满足，执行操作
pthread_mutex_unlock(&mutex);

必须用 while 而非 if

cond_wait 返回后条件可能已被其他线程改变（虚假唤醒 spurious wakeup），必须重新检查。

4.3 经典同步问题

生产者-消费者（Bounded Buffer）

信号量:
  mutex = 1          // 互斥访问缓冲区
  empty = N          // 空槽位数
  full = 0           // 满槽位数

生产者:                         消费者:
  P(empty)                       P(full)
  P(mutex)                       P(mutex)
  放入数据                        取出数据
  V(mutex)                       V(mutex)
  V(full)                        V(empty)

读者-写者问题

读者优先：多个读者可同时读，写者需等所有读者完成
写者优先：写者到来后，新读者等待
公平版：按到达顺序处理

哲学家就餐问题

5 个哲学家围坐圆桌，每人之间一根筷子，需同时拿起左右两根才能吃饭。

解决方案：

最多允许 4 人同时尝试拿筷子
奇数号先拿左再拿右，偶数号相反（破坏循环等待）
使用一把全局锁（降低并发度）

5. 死锁（Deadlock）

5.1 必要条件（Coffman 条件）

同时满足以下四个条件才可能发生死锁：

互斥（Mutual Exclusion）：资源不可共享
持有并等待（Hold and Wait）：持有资源的进程可以请求新资源
不可剥夺（No Preemption）：资源不能被强制回收
循环等待（Circular Wait）：存在进程的循环等待链

5.2 处理策略

策略	方法	实际应用
预防	破坏四个条件之一	资源排序（破坏循环等待）
避免	动态检查是否安全	银行家算法
检测+恢复	允许发生，检测后处理	数据库（超时+回滚）
鸵鸟策略	忽略问题	大多数通用 OS

5.3 银行家算法（Banker's Algorithm）

Dijkstra 提出的死锁避免算法。系统在分配资源前检查是否存在安全序列。

数据结构（\(n\) 个进程，\(m\) 类资源）：

\(\text{Available}[m]\)：当前可用资源向量
\(\text{Max}[n][m]\)：每个进程的最大需求
\(\text{Allocation}[n][m]\)：当前已分配
\(\text{Need}[n][m] = \text{Max} - \text{Allocation}\)

安全性检查：

初始化 \(\text{Work} = \text{Available}\)，\(\text{Finish}[i] = \text{false}\)
找到进程 \(i\) 使得 \(\text{Finish}[i] = \text{false}\) 且 \(\text{Need}[i] \leq \text{Work}\)
\(\text{Work} = \text{Work} + \text{Allocation}[i]\)，\(\text{Finish}[i] = \text{true}\)
重复直到所有进程 Finish 或找不到可执行的进程
若所有 \(\text{Finish}[i] = \text{true}\)，则系统处于安全状态

\[ \text{时间复杂度} = O(n^2 \times m) \]

6. 进程间通信（IPC）

机制	特点	适用场景
管道（Pipe）	单向、字节流、父子进程	Shell 管道 `\|`
命名管道（FIFO）	有文件名、无亲缘关系	进程间简单通信
消息队列	结构化消息	异步通信
共享内存	最快（无需拷贝）	大数据量传输
信号（Signal）	异步通知	进程控制（SIGKILL等）
Socket	跨网络	网络通信

导航

下一节：内存管理
相关：存储层次设计