Lazy loaded imageOS05 并发与同步

type
status
date
slug
summary
tags
category
icon
password

并发与同步

并发是现代操作系统的核心能力之一，它允许多个任务“同时”执行（逻辑上或物理上），从而提升系统吞吐量和响应性。然而，并发也带来了同步问题——当多个执行流（进程或线程）共享资源时，若不加以协调，将导致数据不一致、竞态条件甚至系统崩溃。本章系统梳理并发模型、上下文切换机制、同步原语及其在不同层次的实现。

并发与多进程

操作系统通过进程（Process）抽象来隔离运行中的程序。每个进程拥有独立的地址空间，由进程控制块（Process Control Block, PCB）维护其全部状态信息：
  • 进程状态：RUNNING（运行中）、READY（就绪）、BLOCKED（阻塞）；
  • 标识与权限：进程 ID（PID）、用户 ID、权限位；
  • 执行上下文：程序计数器（PC）、通用寄存器、栈指针；
  • 内存管理：页表、内存限制、内存映射区域；
  • 资源表：打开的文件描述符表（fd table）；
  • 统计信息：CPU 使用时间、调度优先级等。
内核的调度器（Scheduler）维护一个 PCB 队列（如就绪队列、I/O 等待队列），依据特定策略（如时间片轮转、优先级调度）决定哪个进程获得 CPU。此外，内核还需分配内存、磁盘、网络等硬件资源。

上下文切换（Context Switch）

当调度器决定切换进程时，会执行上下文切换，步骤如下：
  1. 通过中断（如时钟中断）或系统调用陷入内核态；
  1. 内核将当前进程的 CPU 状态（寄存器、PC 等）保存到其 PCB；
  1. 从目标进程的 PCB 中恢复其上下文；
  1. 切换回用户态，将控制权交给新进程。
上下文切换是昂贵的操作（典型开销：3–4 微秒），应尽量减少其频率。

进程生命周期

进程在其生命周期中经历以下状态转换：
  • NEW → READY：进程被创建并加入就绪队列；
  • READY ↔ RUNNING：由调度器根据策略切换；
  • RUNNING → BLOCKED：主动发起 I/O 或等待事件（如 read()、sleep()）；
  • BLOCKED → READY：等待的事件完成（如 I/O 结束）；
  • RUNNING → TERMINATED：调用 exit() 或被强制终止。
PCB 会根据状态被移入不同队列（如就绪队列、I/O 等待队列），调度器只需检查这些队列即可决策。

进程调度

调度的目标是在多个竞争者之间公平、高效地分配 CPU。理想调度策略应满足：
  1. 公平性（Fairness）：避免某些进程长期饥饿；
  1. 实时性（Real-time Guarantee）：关键任务必须在截止时间内完成；
  1. 低延迟（Low Latency）：减少任务响应时间，提升交互体验。

多线程

线程是比进程更轻量的执行单元。同一进程内的多个线程共享以下资源：
  • 堆内存（heap）
  • 全局变量
  • 代码段（text segment）
  • 文件描述符
但每个线程拥有独立的状态：
  • 线程控制块（TCB）
  • 私有栈（stack）
  • 寄存器上下文（包括 PC、栈指针）
  • 线程局部存储（TLS）
操作系统调度的基本单位通常是线程。调度器（或称为 dispatcher）负责在线程间切换：加载其寄存器、栈指针，并激活其虚拟内存环境。

线程切换的触发方式

线程切换可由两类事件引发：
  1. 内部事件（协作式）：
      • 主动调用 yield() 放弃 CPU；
      • 因 I/O 阻塞或等待条件变量而休眠。
  1. 外部事件（抢占式）：
      • 时钟中断：实现时间片轮转；
      • 硬件中断：如网络包到达；
      • 软件中断：如信号（signal）。
切换时，硬件将当前线程的上下文保存到内核栈，内核再将其存入 TCB。线程切换的 bug 极难复现和调试，因其依赖于非确定性的调度时机。

线程初始化示例

创建新线程时，需初始化其 TCB 和栈：
线程启动后执行 ThreadRoot：
初始化细节高度依赖体系结构（如寄存器命名、调用约定）。

并发效率总结

  • 上下文切换频率：通常每 10–100ms 一次；
  • 切换开销：
    • 进程间切换：约 3–4 微秒；
    • 线程间切换：约 100 纳秒（因共享地址空间，无需切换页表）。
  • 多核优化：
    • 超标量（Superscalar）：单周期执行多条独立指令；
    • 超线程（Hyper-Threading）：单物理核心模拟多个逻辑核心，提升资源利用率。
若两个进程同时运行在不同核心上，通信开销较低；若一个进程不在运行，则需通过内核中转，开销显著增加。

同步的必要性

调度器的非确定性（Non-determinism）意味着线程可在任意时刻被切换。这使得：
  • 测试极其困难：同一程序多次运行可能产生不同结果；
  • 合作线程（共享状态）必须通过同步机制协调访问，否则将出现竞态条件（Race Condition）。

原子操作

原子操作（Atomic Operation）是同步的基础：它要么完全执行，要么完全不执行，中间不可被中断。
  • 在大多数架构上，简单的 load/store（内存读写）是原子的；
  • 但读-改-写（Read-Modify-Write, RMW）操作（如 i++）不是原子的，需特殊指令支持。
通过声明原子变量，可确保对其的读写操作不可分割，常用于实现无锁计数器、标志位等。

生产者-消费者问题

经典同步问题：生产者生成数据放入缓冲区，消费者从中取出。需协调两者节奏，避免：
  • 缓冲区溢出（生产过快）；
  • 读取空缓冲区（消费过快）。
解决方案：
  • 使用互斥锁保护缓冲区；
  • 使用两个信号量：
    • emptySlots：初始值 = 缓冲区大小，表示可用空槽；
    • fullSlots：初始值 = 0，表示已填充槽。
生产者先 P(emptySlots)，消费者先 P(fullSlots)，操作完成后分别 V(fullSlots) 和 V(emptySlots)。

同步术语

术语
说明
临界区（Critical Section）
访问共享资源的代码段
竞态条件（Race Condition）
多个线程并发进入临界区，导致结果依赖执行顺序
不确定性程序
包含竞态条件，行为不可预测
互斥（Mutual Exclusion）
确保同一时刻仅一个线程进入临界区

POSIX 同步原语

POSIX 线程（pthread）提供标准同步接口：
pthread_cond_wait 会在被唤醒后自动重新获取锁，再返回。

锁的实现

朴素实现：关闭中断

  • 思路：加锁时禁用中断，防止被抢占。
  • 问题：
    • 用户代码若长时间持有锁，将阻塞整个系统；
    • 多核无效：其他核心仍可访问共享资源；
    • 可能丢失中断；
    • 频繁开关中断开销大。

改进实现：休眠等待

仅在修改锁状态时短暂关闭中断，其余时间允许中断：
关键：休眠操作由调度器完成，新线程会开启中断，避免系统死锁。

硬件原子指令

为支持多核同步，现代 CPU 提供原子 RMW 指令：
指令
功能
test_and_set(addr)
返回原值，并将内存设为 1
swap(addr, reg)
交换内存与寄存器的值
compare_and_swap(addr, expected, new)
若内存 == expected，则设为 new，返回成功/失败
这些指令在单/多核上均有效，无需关闭中断。

自旋锁（Spinlock）

使用 test_and_set 实现忙等待锁：
优缺点：
  • ✅ 适用于短临界区、多核场景；
  • ❌ 单核下无效（忙等线程无法让出 CPU）；
  • ❌ 可能导致优先级反转（高优先级线程等待低优先级线程释放锁）。

公平自旋锁：Ticket Lock

通过“取号-叫号”机制保证公平性：
所有线程按请求顺序获得锁，避免饥饿。

避免自旋：休眠替代忙等

自旋浪费 CPU 资源。改进方案：休眠等待。
使用小锁（guard）仅保护元数据操作，临界区极短，几乎不会竞争。

同步方法总结

层次
机制
程序级
共享内存、消息传递
高级抽象
锁、信号量、管程（Monitor）、Send/Receive
硬件支持
原子 load/store、关闭中断、Test&Set、CAS
推荐实践：使用锁实现互斥，条件变量实现调度，比直接使用信号量更安全、易读。

基于锁的并发数据结构

懒惰计数器（Lazy Counter）

  • 每个线程维护局部计数器；
  • 增量达到阈值 S 时，才加到全局计数器；
  • 读取时返回全局值（可能有偏差 ≤ N×S，N 为线程数）；
  • 优点：大幅减少锁竞争。

带锁链表

  • 插入时：先在无锁状态分配节点、设置数据；
  • 再加锁修改链表指针；
  • 优点：将耗时操作移出临界区。

管程（Monitor）

管程是一种高级同步抽象，封装了：
  • 一把互斥锁；
  • 零个或多个条件变量。

条件变量操作

  • wait(mutex)：原子地释放锁 + 休眠；唤醒后重新获取锁；
  • signal()：唤醒一个等待线程；
  • broadcast()：唤醒所有等待线程。
必须在持有锁时调用条件变量操作。

两种语义风格

风格
行为
特点
Hoare-style
signal() 后立即切换到被唤醒线程
条件一定成立，但上下文切换开销大
Mesa-style（主流）
signal() 后继续执行，被唤醒者进入就绪队列
条件可能不成立，需循环检查
Mesa 风格示例（生产者-消费者）：
必须用 while 而非 if，防止虚假唤醒或条件失效。

读者-写者问题

允许多个读者并发读，但写者必须独占访问。

第一类（读者优先）

  • 读者不会被写者阻塞；
  • 但可能导致写者饥饿。
实现要点：
  • 维护活跃/等待读者/写者计数；
  • 写者离开时，广播唤醒所有读者（因读者只能被写者唤醒）。
若合并条件变量，需全部使用 broadcast，但会降低效率且破坏读者优先特性。

编程语言中的同步支持

不同语言提供不同级别的同步抽象，但核心原则一致：确保异常安全下的锁释放。

C++

推荐使用 lock_guard 或 unique_lock 实现RAII，避免手动管理。

Java

synchronized 块在异常时自动释放锁，但 ReentrantLock 需手动释放。

Python

with 语句确保异常安全。

总结

  • 并发提升性能，但引入同步挑战；
  • 原子操作和硬件指令是底层基础；
  • 锁 + 条件变量（管程）是推荐的高级同步模式；
  • 避免自旋，优先使用休眠等待；
  • 语言特性（RAII、with、finally）可简化异常安全的同步代码。
正确使用同步机制，是编写高效、可靠并发程序的关键。
Prev
OS04 抽象-进程间通信
Next
OS06 调度
Loading...
Article List
SunVapor的小站
计算机系统导论
Lazy loaded image ICS01 概述
Lazy loaded image ICS02 数据
Lazy loaded image ICS03 汇编语言
Lazy loaded image ICS04 处理器体系结构
Lazy loaded image ICS05 存储器层次结构
Lazy loaded image ICS06 优化程序性能
Lazy loaded image ICS07 链接
Lazy loaded image ICS08 异常控制流
Lazy loaded image ICS09 虚拟内存
Lazy loaded image ICS10 系统级I/O
Lazy loaded image ICS11 网络编程
Lazy loaded image ICS12 并发编程
操作系统
Lazy loaded image OS01 绪论
Lazy loaded image OS02 抽象-线程与进程
Lazy loaded image OS03 抽象-文件与I/O
Lazy loaded image OS04 抽象-进程间通信
Lazy loaded image OS05 并发与同步
Lazy loaded image OS06 调度
文档
📖 关于建站