同步和互斥

同步和互斥是操作系统中考察的重中之重，关于各个概念的理解经常在选择题中出现，需要熟练掌握信号量的用法。

实现互斥的方法

软件互斥

Peterson’s Algorithm

Peterson’s Algorithm 基于两个线程之间的竞争条件来实现互斥。它使用两个布尔变量和一个整数变量，分别表示两个线程的意愿和当前正在运行的线程。通过这些变量的协作，可以确保只有一个线程能够进入临界区。

Peterson’s Algorithm 通常用于理论教学和理解互斥原理，但在实际多线程编程中并不常用，因为它只适用于两个线程之间的互斥。

// 初始化
bool flag[2] = {false, false};  // 两个线程的意愿
int turn = 0;                   // 当前运行的线程（0 或 1）

// 线程 1 希望进入临界区
void thread0() {
    flag[0] = true;
    turn = 1; // 通知线程 2 你可以运行了
    while (flag[1] && turn == 1) {
    // 等待线程 2 退出临界区或让出 CPU
    }
    // 进入临界区
    // ...
    // 退出临界区
    flag[0] = false;
}

// 线程 2 希望进入临界区
void thread1() {
    flag[1] = true;
    turn = 0; // 通知线程 1 你可以运行了
    while (flag[0] && turn == 0) {
    // 等待线程 1 退出临界区或让出 CPU
    }
    // 进入临界区
    // ...
    // 退出临界区
    flag[1] = false;
}

硬件互斥

硬件互斥是一种在计算机体系结构层面实现的互斥机制，通常用于保护共享资源，以确保在多核处理器系统中同时只有一个线程或核心能够访问这些资源。硬件互斥的实现通常依赖于底层硬件支持，包括原子指令和特殊的寄存器。

原子指令：原子指令（Atomic Instructions），也称为原子操作或原子操作指令，是计算机体系结构中的一种特殊指令，它们被设计为在单个处理器指令周期内执行完毕，不会被中断或其他线程干扰。

这里主要掌握 TAS 和 CAS 两种原子指令即可：

  • Test-and-Set（TAS）指令：TAS 指令用于原子地设置一个内存位置的值，并返回该位置的先前值。互斥锁可以用一个整数变量表示，0 表示锁是空闲的，1 表示锁已经被占用。锁定操作可以使用 TAS 指令来尝试将锁的值从 0 设置为 1，如果返回的先前值为 0，则表示锁定成功。解锁操作将锁的值设置为 0。
  • Compare-and-Swap（CAS）指令：CAS 指令用于原子地比较内存位置的当前值与一个预期值，并只有在它们匹配时才会更新该位置的值。互斥锁可以用 CAS 指令来实现。例如，锁定操作可以使用 CAS 指令来将锁的值从 0 修改为 1，如果 CAS 操作成功，则表示锁定成功。解锁操作可以使用 CAS 来将锁的值从 1 修改为 0。
// TAS 原子指令相当于以下函数被原子性地执行
bool TestAndSet(bool *lock) {
    bool old = *lock;
    *lock = true;
    return old;
}

// 通过 TAS 实现自旋锁
void acquire_lock(bool *lock) {
    while (!TestAndSet(lock)) {
        // 锁被占用，继续自旋等待
    }
}

void release_lock(bool *lock) {
    *lock = false;
}
// CAS 原子指令相当于以下函数被原子性地执行
bool CompareAndSet(bool *lock, bool expected, bool new_value) {
    if (*lock == expected) {
        *lock = new_value;
        return true;  // 操作成功
    } else {
        return false; // 操作失败
    }
}

// 通过 CAS 实现自旋锁
void acquire_lock(bool *lock) {
    while (!CompareAndSet(lock, false, true)) {
        // 锁被占用，继续自旋等待
    }
}

void release_lock(bool *lock) {
    *lock = false;
}

C 语言通过 TAS 实现自旋锁

互斥锁

互斥锁（Mutex，来源于“mutual exclusion”，即相互排斥）是并发编程中用于确保多个线程不会同时访问共享资源或执行特定代码段的同步原语。互斥锁提供了一种机制，确保在任何时刻只有一个线程能够持有该锁，从而确保共享资源的安全访问。

基本特点：

  • 互斥性：任何时候，只有一个线程可以持有互斥锁。其它试图获取该互斥锁的线程将被阻塞，直到持有锁的线程释放该锁。
  • 所有权：只有锁的持有者才能释放它。这确保了非持有者不能误释放锁。

基本操作：

  • 锁定（Lock 或 Acquire）：当线程试图获取互斥锁时，如果锁已被其他线程持有，则该线程将被阻塞，直到锁被释放。
  • 解锁（Unlock 或 Release）：持有互斥锁的线程在完成其对共享资源的访问后，应该释放锁以使其他线程可以获取锁。

线程是如何在互斥锁操作中被阻塞或唤醒的？

当线程尝试获取一个已经被持有的锁时，它会被挂起，并且不会消耗 CPU 资源。只有当锁被释放并且该线程被选择为下一个获取锁的线程时，它才会恢复执行。这样的机制确保了临界区的互斥访问，同时也尽量减少了不必要的 CPU 浪费。

  • 阻塞：
    • 当线程尝试获取一个已经被其他线程持有的互斥锁时，该线程会进入一个等待状态，也称为阻塞状态。
    • 操作系统维护了一个与该互斥锁关联的等待队列。尝试获取锁但未成功的线程会被放入这个队列中。
    • 被阻塞的线程会从“运行”状态转为“等待”或“睡眠”状态。这意味着该线程将不再获得 CPU 时间，直到它被唤醒。
  • 唤醒：
    • 当持有互斥锁的线程释放该锁时，操作系统会检查与该锁关联的等待队列。
    • 通常，队列中的下一个线程（取决于调度策略，可能是队列的第一个线程或其他）会被选中并被唤醒，允许它获取锁。
    • 被唤醒的线程转换为“就绪”状态，并在适当的时候由调度器重新分配 CPU 时间，从而继续执行。
thread A
Pending Queue for Lock L
Thread A is holding
the lock currently
thread B
thread C
thread D
Thread D is trying to acquire the lock,
and it's appended to the pending queue 
LOCK L
thread B
Pending Queue for Lock L
Thread A release lock and
execute the following code
thread C
thread D
LOCK L
thread A
acquire(l)
critical section
release(l)
following code
Thread B is holding
the lock currently
acquire(l)
critical section
release(l)
following code
acquire(l)
critical section
release(l)
following code
acquire(l)
critical section
release(l)
following code
Thread A release the lock
and operating system pick a thread from pending queue
and grant the lock to it

需要注意的是，上述描述是一个高级和简化的过程。实际的操作系统实现可能会有更多的优化和特性，如优先级反转控制、超时机制、自旋锁等。

条件变量

条件变量（Condition Variable） 是一种同步原语，用于线程之间的有条件同步。它允许线程等待某个条件成立，同时释放已获取的锁，这样其他线程可以获取锁并可能更改共享数据的状态，使得条件成立。

用途

  • 实现同步操作：有时，线程需要等待某个条件才能继续执行。条件变量使线程可以等待，直到其他线程更改了共享数据的状态并满足了该条件。
  • 避免忙等（busy-waiting）：而不是使线程不停地轮询共享数据以检查条件是否满足（这会浪费 CPU 资源），条件变量使线程可以休眠直到条件满足。

操作

  • wait()：这个操作做两件事。首先，它会释放与条件变量关联的锁，从而使其他线程可以获取锁并更改共享数据的状态。其次，它会使调用它的线程休眠，直到另一个线程来唤醒它。
  • signal()：这个操作用于唤醒等待在条件变量上的某个线程。如果多个线程在等待，通常只有一个线程被唤醒（但这取决于具体实现）。唤醒的线程将重新获取锁并从其调用 wait() 的地方继续执行。
  • broadcast() 或 notify_all()：这个操作唤醒所有等待在条件变量上的线程。当共享数据的状态变化可能影响多个等待的线程时，这很有用。

信号量

信号量（Semephore）是一个同步原语，相比锁，信号量可以解决一些更加复杂的同步问题。

在逻辑上我们将信号量理解为一个整数值，信号量提供两个原子操作：

  • P （proberen，荷兰语的“尝试”之意）
  • V （verhogen，荷兰语的“增加”之意）。

P 操作

P 操作也被称为 wait 操作， P 操作的具体流程如下：

  • 如果信号量值大于 0，则减少信号量的值，并继续执行后续代码。
  • 如果信号量值为 0，则执行 P 操作的线程将被阻塞，直到信号量变为正值。

简而言之，就是尝试（正如荷兰语的原义）将信号量的值减一，若不至于将信号量的值减为负数。 则尝试成功，线程可继续执行后续代码。若尝试失败，则线程被阻塞。

V 操作

V 操作也被称为 signal 操作， V 操作的具体流程如下：

增加信号量的值。如果有任何线程因为 P 操作被阻塞，则选取一个被阻塞的线程（选择机制可能依赖于具体的实现）并唤醒它。 接着继续执行后续代码。

信号量是如何实现的

只需要在逻辑上理解信号量的机制即可，信号量中有维护有一个整数值，并且与一个阻塞队列和运行队列相关联。

  • 当线程的 P 操作执行成功后，线程被加入信号量的运行队列。
  • 当线程的 P 操作执行失败后，线程被加入信号量的阻塞队列。
  • 当线程的 V 操作执行成果后，线程被从运行队列中移除，并尝试从阻塞队列中选取线程继续执行 P 操作。

线程是如何在 PV 操作中被阻塞或唤醒的？

当一个线程尝试执行 P 操作并发现信号量的值为 0 或负数时，该操作会导致该线程阻塞。具体地说，线程会被移出运行队列并放入一个特定的阻塞队列。这个阻塞队列是与信号量关联的，其中保存了因该信号量被阻塞的所有线程。

当其他线程对该信号量执行 V 操作并增加其值时，一个被阻塞的线程（或多个，具体取决于实现和信号量的增量）会从等待队列中被选出并被唤醒，随后它可以继续执行。

信号量应用

用信号量实现同步操作

先执行 P1 中的 code1，再执行 P2 中的 code2：

semphore S = 0;

P1() {
    code1;       // 先执行 code1
    V(S);        // 告诉线程 P2，code1 已经完成
    ...
}

P2() {
    ...
    P(S);        // 检查 code1 是否完成
    code2;       // 检查无误，运行 code2
}

用信号量实现互斥操作

当信号量的初始值为 1 时，可以把信号量当作锁使用：

semaphore S = 1;

P1() {
    P(S);
    // critical section
    V(S);
}

P2() {
    P(S);
    // critical section
    V(S);
}

用信号量实现前驱关系

S4
S2
S6
S5
S1
c
d
b1
b2
a1
S3
a2
e
semphore a1 = a2 = b1 = b2 = c = d = e = 0;

S1() {
    ...;
    V(a1); V(a2);
}

S2() {
    P(a1);
    ...
    V(b1); V(b2);
}

S3() {
    P(a2);
    V(e);
}

S4() {
    P(b1);
    V(c);
}

S5() {
    P(b2);
    V(d);
}

S6() {
    P(c); P(d); P(e);
}

管程

管程（Monitor）是一个并发编程中的同步原语，用于封装共享数据及其操作以确保对共享数据的并发访问是安全的。它提供了一种结构化的方式来封装共享数据、对数据的操作方法以及同步机制（如条件变量）。

管程的核心思想是仅在给定的时间允许一个线程进入并执行管程中的代码，从而实现对共享资源的互斥访问。当其他线程试图进入同一管程时，它们将被阻塞，直到当前执行的线程退出管程。

管程基本组成：

  • 共享数据：管程封装了需要被多个线程共享和访问的数据。
  • 方法：定义了如何操作共享数据的函数或方法。这些方法是唯一可以访问和修改共享数据的方式。
  • 条件变量：用于控制线程的执行顺序，让线程在某些条件下等待，或通知等待的线程继续执行。

管程和锁、信号量的区别？

锁和信号量是更低级的同步原语。尽管它们非常有用并且广泛应用，但在某些情况下直接使用它们可能导致代码复杂且难以理解。另外，使用这些低级原语可能会增加死锁、饥饿或其他同步问题的风险。

管程的设计是为了将这些低级的细节隐藏起来，并提供一个更高级、更抽象的接口，使得程序员可以更容易地编写正确、安全的并发代码。

管程的实际例子

用管程封装生产者消费者问题。