操作系统 - 信号量

在操作系统中，信号量用于确保正确的进程同步，并在多个进程并发访问共享资源时避免竞争条件。阅读本章以了解信号量的概念、类型、操作以及它们在操作系统中的实现方式。

• 用于进程同步的信号量
• 信号量的类型
• 信号量的工作原理
• 信号量的实现
• 信号量的优点
• 信号量的缺点

用于进程同步的信号量

信号量是一种变量（通常为整数类型），用于在并发系统中控制多个进程对公共资源的访问。通过控制对共享资源的访问，信号量可以防止临界区问题，并在多处理系统中确保进程同步。

信号量定义了两种原子操作：wait(S)，如果 S 为正则递减信号量 S；signal(S)，递增 S，从而实现进程同步。下面部分将详细解释这些操作。

Wait 操作

wait 操作在其参数 S 为正时递减 S。如果 S 为负或零，则不执行任何操作。该操作检查信号量的值。如果值为大于 0，则进程继续执行并将 S 递减 1。如果值为 0，则进程被阻塞（等待），直到 S 变为正。

wait(S) {
   while (S <= 0);
   S--;
}

Signal 操作

signal 操作递增其参数 S。进程使用完共享资源后，执行 signal 操作，将信号量的值增加 1，从而可能解除其他等待进程的阻塞，允许它们访问资源。

signal(S) { 
   S++; 
}

信号量的类型

信号量主要有两种类型：计数信号量和二进制信号量。详情如下 −

• 二进制信号量
• 计数信号量

1. 二进制信号量

二进制信号量的值为限制在 0 和 1之间。wait 操作仅在信号量为 0 时生效。有时实现二进制信号量比计数信号量更容易。

二进制信号量用于系统中仅有一个资源实例的场景。例如，如果系统中只有一个打印机，可以使用二进制信号量来控制对打印机的访问。

2. 计数信号量

计数信号量是具有无限制值域的整数值信号量。它们用于协调资源访问，信号量的计数值表示可用资源的数量。如果添加资源，信号量计数值自动递增；如果移除资源，则计数值递减。

当有多个资源实例可用时使用计数信号量。例如，如果有 5 个相同的资源，则将信号量 S 初始化为 5。每次进程获取一个资源时，S 递减 1；释放时，S 递增 1。当 S=0 时，表示没有可用资源，请求资源的进程将被阻塞，直到有资源被释放。

信号量的工作原理

为了理解信号量的工作原理，考虑两个进程 P1 和 P2 之间的情况，它们需要访问一个共享资源。最初，信号量 S 被设置为 1，这表示资源可用。

状态 1 − P1 和 P2 都处于它们的非关键区。

状态 2 − P1 想要进入其关键区，因此它执行 wait(S)。于是 S 被递减为 0。

状态 3 − P1 处于关键区，现在 P2 也想要进入其关键区，因此它执行 wait(S)。由于 S 为 0，P2 被阻塞并等待。

状态 4 − P1 完成其关键区并执行 signal(S)。于是 S 被递增为 1。

状态 5 − P2 被解除阻塞并执行 wait(S)。于是 S 被递减为 0，P2 进入其关键区。

状态 6 − P2 完成其关键区并执行 signal(S)。于是 S 被递增为 1。

下图展示了上述步骤 −

信号量实现

以下是如何使用 POSIX threads 在 C++ / Python / Java 中实现二进制信号量的示例。

import threading
import time

semaphore = threading.Semaphore(1)
def process(id):
    print(f"Process {id} is trying to enter critical section")
    semaphore.acquire()  # 等待操作
    print(f"Process {id} has entered critical section")
    time.sleep(1)  # 模拟临界区
    print(f"Process {id} is leaving critical section")
    semaphore.release()  # 信号操作
threads = []
for i in range(5):
    t = threading.Thread(target=process, args=(i,))
    threads.append(t)
    t.start()
for t in threads:
    t.join()

Process 0 is trying to enter critical section
Process 0 has entered critical section
Process 1 is trying to enter critical section
Process 2 is trying to enter critical section
Process 3 is trying to enter critical section
Process 4 is trying to enter critical section
...

#include <iostream>
#include <semaphore.h>
#include <thread>
#include <vector>
using namespace std;

sem_t semaphore;
void process(int id) {
    cout << "Process " << id << " is trying to enter critical section" << endl;
    sem_wait(&semaphore); // 等待操作
    cout << "Process " << id << " has entered critical section" << endl;
    this_thread::sleep_for(chrono::seconds(1)); // 模拟临界区
    cout << "Process " << id << " is leaving critical section" << endl;
    sem_post(&semaphore); // 信号操作
}

int main() {
    sem_init(&semaphore, 0, 1); // 初始化二进制信号量
    vector<thread> threads;
    for (int i = 0; i < 5; i++) {
        threads.push_back(thread(process, i));
    }
    for (auto& t : threads) {
        t.join();
    }
    sem_destroy(&semaphore);
    return 0;
}

Process 0 is trying to enter critical section
Process 0 has entered critical section
Process 1 is trying to enter critical section
Process 2 is trying to enter critical section
Process 3 is trying to enter critical section
Process 4 is trying to enter critical section
...

import java.util.concurrent.Semaphore;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class SemaphoreExample {
    static Semaphore semaphore = new Semaphore(1);
    public static void process(int id) {
        try {
            System.out.println("Process " + id + " is trying to enter critical section");
            semaphore.acquire(); // 等待操作
            System.out.println("Process " + id + " has entered critical section");
            Thread.sleep(1000); // 模拟临界区
            System.out.println("Process " + id + " is leaving critical section");
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            semaphore.release(); // 信号操作
        }
    }
    public static void main(String[] args) {
        ExecutorService executor = Executors.newFixedThreadPool(5);
        for (int i = 0; i < 5; i++) {
            final int id = i;
            executor.submit(() -> process(id));
        }
        executor.shutdown();
    }
}

Process 0 is trying to enter critical section   
Process 0 has entered critical section
Process 1 is trying to enter critical section
Process 2 is trying to enter critical section
Process 3 is trying to enter critical section
Process 4 is trying to enter critical section
...