互斥与同步机制及其算法

操作系统中的同步互斥机制

进程同步与互斥是为了解决并发进程访问共享资源时可能出现的数据不一致问题。

• 互斥（Mutual Exclusion）：指多个进程在并发执行时，任何时刻**只允许一个进程进入临界区（Critical Section）**访问共享资源。临界区是访问共享资源的代码段。

• 同步（Synchronization）：指多个并发进程在执行过程中，需要按照某种预定的顺序或条件来推进。

实现同步互斥的机制可以分为两大类：软件实现方法和硬件实现方法。

1. 软件实现方法

软件方法完全依赖于程序代码逻辑来解决同步互斥问题。主要包括以下几种尝试性算法：

a. 单标志法（轮换法）

• 原理：设置一个公共的整型变量 turn，表示轮到哪个进程进入临界区。例如，turn = 0 表示 P0 进程可以进入，turn = 1 表示 P1 进程可以进入。

• 伪代码（P0 进程）：

  代码段

  // P0 进程
  while (true) {
      while (turn != 0); // 等待轮到自己
      // 临界区
      // ... 访问共享资源 ...
      turn = 1; // 轮到 P1
      // 剩余区
  }
  

• P1 进程类似：while (turn != 1) 等待，然后设置 turn = 0。

• 缺点：严格交替进入。如果 P0 进程执行完临界区后，P1 进程还没准备好进入临界区，P0 也无法再次进入，必须等待 P1 进来又出去，导致资源利用率低。不满足“空闲让进”原则。

b. 双标志先检查法（尝试法）

• 原理：设置一个布尔型数组 flag[i]，表示进程 i 是否想进入临界区。flag[i] = true 表示想进入。

• 伪代码（P0 进程）：

  代码段

  // P0 进程
  while (true) {
      flag[0] = true;
      while (flag[1]); // 检查 P1 是否想进入
      // 临界区
      // ... 访问共享资源 ...
      flag[0] = false;
      // 剩余区
  }
  

• P1 进程类似：flag[1] = true; while (flag[0]);。

• 缺点：可能出现饥饿（Starvation）和忙等待（Busy Waiting）。

  • 饥饿：如果 P0 和 P1 同时执行 flag[0]=true; 和 flag[1]=true;，然后都进入 while 循环，都检查到对方 flag 为 true，从而都无法进入临界区，形成死锁。这是由于检查-设置操作不是原子的，存在时序问题。

  • 忙等待：进程在等待时，会一直占用CPU进行循环检测，浪费CPU资源。

c. 双标志后检查法（礼让法）

• 原理：在检查对方标志之前，先把自己想进入的标志置为 true，然后“礼让”对方，如果对方也想进入，则自己先退让。

• 伪代码（P0 进程）：

  代码段

  // P0 进程
  while (true) {
      flag[0] = true;
      while (flag[1]) { // 检查 P1 是否想进入
          flag[0] = false; // 礼让 P1
          // P0 可能执行一些其他操作，或者等待一段时间
          flag[0] = true; // 再次尝试
      }
      // 临界区
      // ... 访问共享资源 ...
      flag[0] = false;
      // 剩余区
  }
  

• 缺点：仍然可能出现饥饿。如果 P0 和 P1 不断地同时尝试进入，并反复互相礼让，可能导致两个进程都无法进入临界区，或者某个进程长时间无法进入。

d. Peterson 算法（Peterson's Algorithm）

• 原理：结合了单标志法和双标志法的优点，解决了前述所有软件实现方法的缺陷。它通过两个变量实现互斥：一个布尔型数组 flag[i] 表示进程 i 是否想进入临界区；一个整型变量 turn 表示哪个进程有优先权。

• 伪代码（P0 进程）：

  代码段

  // P0 进程
  while (true) {
      flag[0] = true;   // P0 声明想进入
      turn = 1;         // 礼让 P1 (P1 有优先权)
      while (flag[1] && turn == 1); // 如果 P1 也想进入且 P1 有优先权，则 P0 等待
      // 临界区
      // ... 访问共享资源 ...
      flag[0] = false;  // P0 离开，声明不想进入
      // 剩余区
  }
  

• P1 进程类似：flag[1] = true; turn = 0; while (flag[0] && turn == 0);。

• 优点：

  • 满足互斥访问：同一时间只有一个进程在临界区。

  • 不发生饥饿：进程最终总能进入临界区。

  • 空闲让进：如果临界区空闲，请求进入的进程能立即进入。

  • 有限等待：一个进程进入临界区之前，等待的时间是有限的。

• 缺点：

  • 仍存在忙等待。

  • 只能解决两个进程的互斥问题，扩展性差。

  • 依赖于共享变量，在多处理器系统中可能因内存缓存一致性问题而失效（现代操作系统通常不直接使用此算法）。

2. 硬件实现方法

硬件方法利用特殊的机器指令来提供原子操作，从而实现同步互斥。

a. TestAndSet 指令（TSL指令）

• 原理：TestAndSet 指令（或称 TSL，Test and Set Lock）是一条原子操作指令，它将某个内存地址的值读取出来，并立即将其设置为 true（或 1），整个过程不可中断。

• 指令定义：boolean TestAndSet(boolean *lock)

  • 返回 *lock 的旧值。

  • 将 *lock 的新值设置为 true。

• 伪代码（使用 TSL 实现互斥）：

  代码段

  boolean lock = false; // 全局共享互斥变量，初始为 false
  
  while (true) {
      while (TestAndSet(&lock)); // 如果 lock 为 true，则循环等待；为 false 则进入并将 lock 置为 true
      // 临界区
      // ... 访问共享资源 ...
      lock = false; // 释放锁
      // 剩余区
  }
  

• 优点：

  • 实现简单，满足互斥性要求。

  • 适用于任意数量的进程。

• 缺点：

  • 存在忙等待：进程在等待时会循环检测 TestAndSet，浪费 CPU 周期。

  • 可能导致饥饿：由于没有优先级概念，当临界区释放时，多个等待进程中的哪一个能再次进入是不确定的，可能导致某些进程长时间无法进入。

b. Swap 指令（XCHG指令）

• 原理：Swap 指令（或称 XCHG，Exchange）也是一条原子操作指令，它将两个内存地址的内容进行交换。

• 指令定义：void Swap(boolean *a, boolean *b)

  • 将 *a 和 *b 的值进行交换。

• 伪代码（使用 Swap 实现互斥）：

  代码段

  boolean lock = false; // 全局共享互斥变量，初始为 false
  boolean key; // 进程私有变量
  
  while (true) {
      key = true; // 进程先将自己的 key 置为 true
      while (key == true) { // 如果 key 为 true，则循环等待
          Swap(&lock, &key); // 原子交换 lock 和 key 的值
          // 首次交换：key变为false (lock的旧值)，lock变为true (key的旧值)
          // 之后循环：key为true (lock的旧值)，lock仍为true (key的旧值)
      }
      // 临界区
      // ... 访问共享资源 ...
      lock = false; // 释放锁
      // 剩余区
  }
  

• 优点：与 TSL 类似，实现简单，满足互斥性，适用于任意数量进程。

• 缺点：同样存在忙等待和可能导致饥饿的问题。

3. 高级抽象机制

为了克服上述低级机制的缺点（如忙等待、易用性差等），操作系统提供了更高级的同步互斥机制。

a. 信号量机制（Semaphore）

• 原理：由 Dijkstra 提出，是一个整数变量，除初始化外，只能通过两个标准的原子操作 wait()（又称 P 操作）和 signal()（又称 V 操作）来访问。

  • wait(S) / P(S)：

    1. S = S - 1

    2. 如果 S < 0，则执行此操作的进程进入阻塞状态，并被加入到信号量 S 的等待队列中。

    3. 如果 S >= 0，则进程继续执行。

  • signal(S) / V(S)：

    1. S = S + 1

    2. 如果 S <= 0，则从信号量 S 的等待队列中唤醒一个进程。

• 分类：

  • 二值信号量（Binary Semaphore）：信号量的值只能为 0 或 1。常用于实现互斥锁（S 初始化为 1）。

  • 计数信号量（Counting Semaphore）：信号量的值可以为任意非负整数。常用于资源计数（S 初始化为可用资源数）。

• 优点：

  • 可以实现互斥和同步。

  • 可以避免忙等待（当资源不满足时，进程会阻塞，不占用 CPU）。

  • 适用于多进程并发。

  • 比硬件指令更易于使用。

• 缺点：

  • P/V 操作是分散在各个进程中的，这使得程序的正确性难以验证。

  • 程序员可能忘记执行 P 或 V 操作，导致死锁或互斥被破坏。

  • 容易出现死锁、饥饿等问题。

• 图示（概念性）：

  +-------------------+
  |    Semaphore S    |
  |      Value: X     |  <-- 信号量的值
  |                   |
  |  Waiting Queue:   |  <-- 阻塞进程的队列
  |   [Process A]     |
  |   [Process B]     |
  +-------------------+
          ^      ^
          |      |
        P()    V()
       (请求) (释放)
  

• 例题：使用信号量解决生产者-消费者问题

  代码段

  semaphore mutex = 1;     // 互斥信号量，用于对缓冲区的互斥访问
  semaphore empty = N;     // 空闲缓冲区数量，初始为 N
  semaphore full = 0;      // 已填充缓冲区数量，初始为 0
  
  // 生产者进程
  producer() {
      while (true) {
          item newItem = produce_item();
          wait(empty);     // 等待有空闲缓冲区
          wait(mutex);     // 进入临界区，互斥访问缓冲区
          // 临界区：将 newItem 放入缓冲区
          insert_item(newItem);
          signal(mutex);   // 离开临界区
          signal(full);    // 增加已填充缓冲区数量
      }
  }
  
  // 消费者进程
  consumer() {
      while (true) {
          wait(full);      // 等待有已填充缓冲区
          wait(mutex);     // 进入临界区，互斥访问缓冲区
          // 临界区：从缓冲区取出 item
          item consumedItem = remove_item();
          signal(mutex);   // 离开临界区
          signal(empty);   // 增加空闲缓冲区数量
          consume_item(consumedItem);
      }
  }
  

b. 管程机制（Monitor）

• 原理：管程是更高层次的同步机制，它将共享数据、**操作这些数据的一组过程（函数）以及同步机制（条件变量）**封装在一起。管程在内部保证了对共享数据的互斥访问，一次只允许一个进程在管程中执行。

• 组成：

  • 共享数据：管程内部的变量。

  • 一组过程：操作共享数据的函数。

  • 初始化代码。

  • 条件变量（Condition Variables）：用于进程同步。

    • wait(condition)：进程阻塞，释放管程互斥权，加入条件变量的等待队列。

    • signal(condition)：唤醒条件变量队列中的一个进程（如果有）。

• 优点：

  • 结构化：将共享数据和操作封装在一起，模块化程度高，易于理解和验证正确性。

  • 自动互斥：管程内部提供了隐含的互斥机制，程序员无需显式编写 P/V 操作来保护临界区，减少了出错的可能性。

  • 避免 P/V 操作的误用：程序员只需调用管程的过程，无需直接操作信号量。

• 缺点：

  • 语言支持要求：管程需要编程语言或编译器提供支持（如 Java 的 synchronized 关键字和 wait()/notify()）。

  • 相对信号量更抽象：理解条件变量的语义（特别是 Hoare 和 Mesa 管程的区别）需要一定门槛。

• 例题：使用管程解决生产者-消费者问题

  （此部分伪代码已在之前详细阐述，此处不再重复，请参考上次回答中的管程示例。）

各种同步互斥机制的异同点

异同点总结：

相同点：

• 所有这些机制的最终目标都是为了实现进程的互斥和/或同步，从而保证共享数据的一致性和正确性。

• 它们都涉及到对共享资源的访问控制。

不同点：

1. 抽象层次：

   • 软件方法和硬件方法属于低级原语，它们直接操作共享变量或利用原子指令，但实现复杂同步逻辑较为困难，且容易出错。

   • 信号量是中级原语，通过 P/V 操作实现阻塞与唤醒，大大简化了同步互斥的实现，但其操作分散，仍需程序员谨慎使用。

   • 管程是高级抽象机制，它将共享数据、操作以及同步机制封装在一个模块中，由编译器或运行时环境保证互斥，极大地提高了易用性和安全性。

2. 是否避免忙等待：

   • 软件方法和硬件方法通常会导致忙等待，即等待进程会持续占用 CPU 循环检测条件。

   • 信号量和管程则可以使等待进程进入阻塞状态，释放 CPU，避免忙等待，提高了 CPU 利用率。

3. 安全性与易用性：

   • 软件方法和硬件方法需要程序员非常小心地处理共享变量，容易因编程错误导致死锁、饥饿或破坏互斥。

   • 信号量虽然比低级方法好用，但 P/V 操作的顺序和配对仍然需要程序员严格控制，否则极易引发问题。

   • 管程通过其内部的自动互斥和条件变量机制，大大降低了程序员犯错的可能性，提高了程序的健壮性和易用性。可以说，管程是目前公认的更优的同步互斥解决方案。

考点分析与命题方式

• 选择题：

  • 各种机制的优缺点（特别是忙等待、饥饿、死锁等问题）。

  • 概念辨析（如同步与互斥的区别，信号量与管程的定义）。

  • Peterson 算法的特点及其能解决的问题。

  • TestAndSet 和 Swap 指令的功能。

• 简答题/分析题：

  • 要求详细阐述某种同步互斥机制的原理和工作过程。

  • 比较不同机制的异同点。

  • 分析一段伪代码（可能是错误的）并指出问题所在。

• 应用题/算法设计题：

  • 重中之重：使用信号量或管程解决经典的同步问题（生产者-消费者、读者-写者、哲学家进餐等）。这要求你不仅理解原理，还能熟练运用伪代码进行实现。

  • 可能会给出一些新颖的同步问题，要求你灵活运用所学知识。

历年命题方式与陷阱：

• 混淆概念：例如，将同步和互斥的定义混淆。

• P/V 操作的顺序错误：在信号量题目中，P/V 操作的顺序非常关键，放错位置可能导致死锁或互斥被破坏。

• 信号量初值错误：互斥信号量一般初始化为 1，资源信号量初始化为资源数量，如果初始化错误，会导致问题。

• 管程中 wait 之后没有 while 循环检查条件：这是 Mesa 管程语义下的一个常见陷阱。

• 对低级同步机制的缺点理解不透彻：例如，TSL 和 Swap 为什么会存在饥饿问题。

• 死锁、饥饿、忙等待的区分：这些概念常常一同出现，需要清晰辨别。