3. 同步与互斥

# 基本概念

# 进程的同步与互斥

# 进程同步

定义：指系统中多个需要相互合作以共同完成一项任务的进程，其执行次序需要通过协调来保证。这种协作进程之间相互等待对方消息或信号的协调关系即为进程同步。
产生原因：进程间的合作关系。
同步问题分类：
1. 保证一组合作进程按照逻辑上要求的顺序执行。
2. 保证合作进程在访问共享缓冲区（或共享数据）时能够协调一致。

# 进程互斥

定义：指若干进程在并发执行中，因竞争同一共享资源而产生的制约关系。任何时刻，最多只允许一个进程使用该资源，其他试图使用该资源的进程必须等待，直到资源被释放。
产生原因：对共享资源的竞争。
与同步的关系：互斥是一种特殊的同步关系。它要求进程逐个使用互斥资源，也是对进程使用资源次序的一种协调。

# 临界资源与临界区

# 临界资源

定义：系统中一次只允许一个进程访问和使用的共享资源。
硬件临界资源：如打印机、光盘刻录机等。
软件临界资源：如只能被互斥访问的共享变量、数据表、队列等。
注意：并非所有共享资源都是临界资源，例如只读类型的数据可以被多个进程同时访问。

# 临界区

定义：进程代码中访问临界资源的那一段程序。
组成部分：
- 进入区 (Entry Section)：在进入临界区之前，用于检查是否可进入临界区的一段代码。若可进入，则通常会设置“正在访问”的标志。
- 临界区 (Critical Section)：访问临界资源的代码。
- 退出区 (Exit Section)：在临界区之后，用于清除“正在访问”标志的代码。
- 剩余区 (Remainder Section)：进程中除上述三部分之外的其他代码。

# 访问临界区的基本原则

为了保证使用临界资源的进程能够正确、高效地协作，避免竞争条件 (Race Condition) 的发生，访问临界区必须遵循以下原则。竞争条件指多个进程访问共享资源时，最终结果取决于进程执行的确切时序，从而导致程序正确性依赖于偶然的执行顺序。

空闲让进：当临界区没有进程时，任何有权使用临界区的进程都可以进入。
忙则等待：不允许两个或以上的进程同时进入临界区。
有限等待：任何进程对临界区的访问请求都应在有限的时间内得到满足，避免“饥饿”。
让权等待：当进程不能进入临界区时，应立即释放处理器（CPU），防止进程陷入“忙等”。

# 互斥的实现方法

# 软件实现方法

# 锁变量

思路：设置一个共享的锁变量 lock。lock=0 表示临界区空闲，lock=1 表示临界区被占用。
实现：

问题：
1. 违反“忙则等待”：在检查 lock 和设置 lock 之间可能发生进程切换，导致两个进程同时进入临界区。
2. 违反“让权等待”：while(lock) 循环会导致忙等待 (Busy Waiting)，即进程持续占用 CPU 循环测试变量，造成 CPU 时间的浪费。用于忙等的锁也称为自旋锁 (Spin Lock)。

# 轮转法

思路：设置一个整型变量 turn，用于记录轮到哪个进程进入临界区。例如，turn=0 表示轮到进程0，turn=1 表示轮到进程1。
实现：

问题：
1. 违反“空闲让进”：要求两个进程必须严格轮流进入临界区。如果一个进程暂时不需要进入，另一个进程也必须等待，即使临界区是空闲的。
2. 忙等待：while(turn != ...) 循环是忙等待。
3. 代码不对称：两个进程的代码逻辑不同。

# Peterson 算法

思路：结合锁变量和轮转法的思想，使用一个布尔数组 interested 表示进程是否有意进入临界区，以及一个整型变量 turn 表示“谦让”轮到哪个进程。
实现：
- 当进程希望进入临界区时，调用 enter_region 函数。
- 当进程退出临界区时，调用 leave_region 函数。

分析：
- 只有当 interested[other] == FALSE (对方不想进入) 或者 turn == other (轮到对方进入，即我方谦让) 这两个条件之一不满足时，当前进程才能跳出 while 循环进入临界区。
- 如果两个进程同时想进入，它们都会设置自己的 interested 为 TRUE，并且都会设置 turn。turn 的最终值取决于后一个执行 turn = ... 语句的进程。这个后执行的进程将会因为 turn == process 不成立而等待，而先执行的进程则可以进入临界区。
优点：在软件层面解决了互斥访问问题，且克服了轮转法的“必须轮流”的缺点。
缺点：仍然存在忙等待问题。

# 优先级反转问题 (Priority Inversion Problem)

忙等待不仅浪费 CPU 时间，还可能导致优先级反转。

场景：假设有一个高优先级进程 H 和一个低优先级进程 L。调度规则规定，只要 H 处于就绪态就可以运行。
问题：若某一时刻 L 正在临界区中，此时 H 变为就绪态并被调度运行。H 试图进入临界区但因 L 占用而开始忙等。由于 H 的优先级高于 L，L 无法被调度执行，也就无法离开临界区。结果是高优先级的 H 反而被低优先级的 L 阻塞。

# 硬件辅助方法

硬件方法通过提供原子操作（不可中断的操作）来解决互斥问题。

# 禁止中断

思路：在进入临界区前执行“关中断”指令，在离开临界区后执行“开中断”指令。
原理：进程切换依赖于时钟中断或其他中断，禁止中断可以确保当前进程在临界区内不会被切换出去。
优点：简单有效。
缺点：
- 滥用风险：将禁止中断的权利交给用户进程，可能会因长时间关中断而影响系统稳定性。
- 不适用多处理器：关中断只对执行该指令的 CPU 有效，无法阻止其他 CPU 上的进程访问临界区。

# 硬件原子指令

利用处理器提供的、能在一个指令周期内完成的“测试并修改”的特殊指令。

# Test and Set 指令

例如：x86 的 BTS (Bit Test and Set) 和 BTR (Bit Test and Reset) 指令。LOCK 前缀可用于锁定内存总线，保证在多处理器环境下的原子性。
- BTS OP1, OP2：将操作数 OP1 中第 OP2 位的值存入进位标志 CF，然后将该位置为 1。
- BTR OP1, OP2：将操作数 OP1 中第 OP2 位的值存入进位标志 CF，然后将该位清 0。

# Swap (Exchange) 指令

例如：x86 的 XCHG 指令。
- XCHG OP1, OP2：原子地交换 OP1 和 OP2 的内容。

硬件指令方法的优缺点：
- 优点：
  - 适用于任意数目的进程。
  - 简单，易于验证其正确性。
  - 可支持多个临界区（为每个临界区设置一个独立的布尔变量）。
- 缺点：仍然存在忙等待问题。

# 高级同步机制

为了克服忙等待的缺点，操作系统提供了更高级的同步原语。

# 信号量

# 信号量的定义

结构：每个信号量 s 是一个数据结构，包含一个整数值 s.count 和一个进程等待队列 s.queue。
访问方式：信号量只能通过初始化和两个标准的原子原语（P 操作和 V 操作）来访问。这些原语作为操作系统核心代码执行，不会被中断。
计数值的含义 (资源信号量)：
- s.count > 0：表示有 count 个可用资源。
- s.count = 0：表示无可用资源。
- s.count < 0：其绝对值 |count| 表示在等待队列 s.queue 中阻塞的进程个数。
互斥信号量：若不需计数能力，仅用于实现互斥，初值为1的信号量也称为互斥信号量或二进制信号量。

# P、V 原语

P、V 操作来自荷兰语 proberen (测试/降低) 和 verhogen (增加/升起)。

P 操作 (wait / down)：申请一个资源。

P(s) {
    s.count--;  // 申请一个资源
    if (s.count < 0) {  // 若无可用资源
        // 将调用进程加入等待队列 s.queue
        // 阻塞该进程
    }
}

V 操作 (signal / up)：释放一个资源。

V(s) {
    s.count++;  // 释放一个资源
    if (s.count <= 0) {  // 若有进程在等待该资源
        // 从等待队列 s.queue 中取出一个进程 P
        // 将进程 P 移入就绪队列
    }
}

# 利用信号量实现互斥与同步

实现互斥：
1. 为临界资源设置一个互斥信号量 mutex，初值为 1。
2. 在每个进程中，将临界区代码置于 P(mutex) 和 V(mutex) 之间。
实现同步：
1. 考虑并发进程 P1 和 P2，要求 P1 中的代码 C1 必须在 P2 中的代码 C2 开始前完成（前趋关系）。
2. 设置一个同步信号量 S12，初值为 0。
3. 在 C1 执行后调用 V(S12)，在 C2 执行前调用 P(S12)。

# P、V 原语使用要点

P 和 V 原语必须成对使用，不能重复或遗漏。
- 遗漏 P 操作不能保证互斥。
- 遗漏 V 操作会导致资源无法释放，使其他进程永久等待。
用于互斥时，P 和 V 操作通常在同一进程中。
用于同步时，P 和 V 操作通常在不同进程中。
P、V 原语的次序不能错误。
- 当一个同步 P 操作和一个互斥 P 操作在一起时，同步 P 操作必须在互斥 P 操作之前，否则可能导致死锁。
- 两个 V 操作的顺序通常无关紧要。

# 管程

# 引入管程：信号量的局限性

信号量机制虽然有效，但其控制逻辑分布在各个进程中，给程序设计和验证带来了困难。

同步操作分散：P、V 操作分散在各进程中，使用不当易导致死锁。
可读性差：难以通过局部代码理解整个系统的同步行为。
不利于修改和维护：模块独立性差，局部修改可能影响全局。
正确性难以保证：在复杂系统中，难以确保所有 P、V 操作都正确使用。

# 管程的定义与主要特性

定义：管程是一种将共享资源的数据结构以及所有针对该资源的操作过程封装在一起的软件模块。
主要特性：
- 模块化：管程是一个可以单独编译的基本程序单位。
- 抽象数据类型：管程封装了数据和对数据的操作代码。
- 信息封装：管程内的共享变量对外部不可见，外部进程只能通过调用管程提供的过程来间接访问这些变量。

# 管程的内部机制：互斥、条件变量与等待队列

互斥进入：管程本身保证了在任何时刻只有一个进程可以在管程内部执行。试图进入一个已被占用的管程的进程，会在入口等待队列中阻塞。
条件变量 (Condition Variables)：
- 当进程在管程内因资源不满足而无法继续执行时，它可以通过在某个条件变量上执行 wait 操作来阻塞自己，并释放管程的互斥访问权。
- wait(c)：调用进程被阻塞，并被放入与条件变量 c 相关的资源等待队列，同时释放管程。
- signal(c)：唤醒在条件变量 c 的等待队列中的第一个进程。如果队列为空，则 signal 操作无效。
紧急等待队列：
- 当进程 P 执行 signal 唤醒进程 Q 时，管程中出现了两个活动进程。
- Hoare 管程：P 等待，Q 先执行。P 被放入紧急等待队列，其优先级高于入口等待队列。
- Hansen 管程：signal 必须是管程过程中的最后一个操作，执行 signal 的进程立即退出管程。

# 管程的缺点

管程是一种编程语言特性，需要编译器支持。Java、Pascal、Modula-2 等语言支持管程。
C、C++ 等多数常用语言不直接支持管程。而信号量作为操作系统机制，只需提供系统调用即可实现，对编译器无特殊要求。

# 进程间通信 (IPC)

# 进程间通信概述

定义 (IPC, Inter-Process Communication)：指在不同进程之间传递或交换信息的过程。
通信分类：
- 低级通信：交换控制信息，如信号量，用于实现进程的同步与互斥。数据量小。
- 高级通信：利用操作系统提供的命令，在进程间高效地传送大量数据。
高级通信的必要性：信号量作为通信工具效率低，且通信过程对用户不透明。

# 分布式系统中的消息传递

信号量和管程主要解决共享内存环境下的同步问题。对于不共享内存的分布式系统，必须采用消息传递等机制。

消息传递 (Message Passing)：
- 基本原语：send(destination, &message) 和 receive(source, &message)。这些通常是系统调用。
- 设计问题：需要考虑消息丢失、进程命名、身份认证和性能等问题。

# 主要的 IPC 机制

# 共享内存

原理：在物理内存中划出一块共享区域，多个进程将此区域映射到各自的地址空间，通过直接读写这块内存来实现通信。
特点：
- 操作系统只负责提供共享内存空间。
- 进程间的读写互斥问题需要程序员自行通过同步机制（如信号量）来解决。
优点：效率极高，因为无需数据拷贝。
缺点：
- 仅限于在同一台物理机器上的进程。
- 安全性较差。
注意：同一进程内的线程通过全局变量通信不属于共享内存 IPC。

# 消息传递

原理：进程间以格式化的消息 (Message) 为单位进行数据交换。
实现方式：
- 直接通信方式 (消息队列)
  - 发送进程直接将消息发送给接收进程，挂载到接收进程的消息缓冲队列上。
  - 通信原语：send(receiver, message) 和 receive(sender, message)。
  - 操作系统负责管理消息缓冲区。
- 间接通信方式 (信箱)
  - 进程通过一个共享的中间实体——信箱 (Mailbox) ——来收发消息。
  - 通信原语：send(mailbox, message) 和 receive(mailbox, message)。
  - 发送方和接收方解耦，可用于非实时通信。

# 管道

原理：在进程间以字节流方式传送信息的通信通道。管道是 UNIX 系统首创的一种基于文件系统的通信方式。
特点：管道有两端，一端用于写，一端用于读。一个进程的输出可以作为另一个进程的输入。
```
# 示例：sort命令的输出作为grep命令的输入
sort < namefile | grep ma
```
管道类型：
- 无名管道 (Anonymous Pipe)：用于具有亲缘关系（如父子）的进程间通信。
- 有名管道 (Named Pipe / FIFO)：允许无亲缘关系的进程间通信，因为它在文件系统中有一个路径名。

# 套接字

套接字是一种更为通用的 IPC 机制，它不仅可以用于同一台机器上的进程通信，还可以用于网络上不同机器之间的进程通信。

# 经典同步问题

这些是用于检验和展示同步机制能力的经典问题模型。

生产者-消费者问题 (The Producer-Consumer Problem)
读者-写者问题 (The Readers-Writers Problem)
哲学家进餐问题 (The Dining Philosophers Problem)
睡眠理发师问题 (The Sleeping Barber Problem)