经典同步问题

真题练习

同步问题设计 是操作系统解答题的重要题型。本节的经典模型提供了可迁移的设计方法：先找资源计数与前驱关系，再确定互斥范围，最后检查 P/V 顺序是否可能导致死锁或饥饿。

生产者消费者问题

生产者消费者问题是并发编程中的经典问题，涉及到两种线程 —— 生产者 和 消费者，它们共享一个固定大小的缓冲区或存储区。

• 生产者的任务是生成数据并将其 放入缓冲区。
• 消费者的任务是 从缓冲区中取出 并消费这些数据。

关键的挑战在于确保生产者不会在缓冲区满时添加数据，同时确保消费者不会在缓冲区空时尝试消费数据。

semaphore mutex = 1;          // 临界区互斥信号量
semaphore empty = n;          // 空闲缓冲区数量
semaphore full  = 0;          // 忙缓冲区数量

producer() {
    while (1) {
        P(empty);             // 等待一个空位置
        P(mutex);             // 进入临界区前先获取 mutex
        ....                  // 将数据项添加到缓冲区
        V(mutex);             // 离开临界区，释放 mutex
        V(full);              // 增加一个数据项的计数
    }
}

consumer() {
    while (1) {
        P(full);              // 等待一个数据项
        P(mutex);             // 进入临界区前先获取 mutex
        ...                  // 从缓冲区取出数据项并消费
        V(mutex);             // 离开临界区，释放 mutex
        V(empty);             // 增加一个空位置的计数
    }
}

下面的步骤与上方代码逐行对应；可点击步骤观察缓冲区、三个信号量与当前代码行同时变化。

01P(empty);02P(mutex);03put(item);04V(mutex);05V(full);

01P(full);02P(mutex);03take(item);04V(mutex);05V(empty);

读者 - 写者问题

读者写者问题 是另一个经典的并发编程问题，涉及到对 共享数据 或 资源 的访问，这些 资源 可以被 多个读者 同时读取，但只能被 一个写者 写入，而且当 写者 正在写入数据时，没有其他 读者 或 写者 可以访问该 资源。

这个问题的挑战在于两点：

• 允许多个读者同时读取资源。
• 确保当有一个写者访问资源时，没有其他读者或写者可以同时访问。

常见策略包括 读者优先、写者优先 和 公平算法。三者的互斥规则相同，区别在于新到达的读者能否越过已经等待的写者。

int read_count = 0;
semaphore wrt  = 1;
semaphore mutex = 1;

reader() {
    while (1) {
        P(mutex)                     // 获取互斥访问权，以修改 read_count
        read_count += 1
        if (read_count == 1) {       // 如果这是第一个读者，需要锁定资源，防止写者写入
            P(wrt)
        }
        V(mutex)                     // 释放互斥访问权
        ...                          // 读取资源
        P(mutex)                     // 获取互斥访问权，以修改 read_count
        read_count -= 1
        if (read_count == 0) {       // 如果没有读者在读取，释放资源，允许写者写入
            V(wrt)
        }
        V(mutex)                     // 释放互斥访问权
    }
}

writer() {
    while (1) {
        P(wrt)                       // 获取资源的互斥访问权
        ...                          // 写入资源
        V(wrt)                       // 释放资源的互斥访问权
    }
}

int read_count = 0;
int write_count = 0;
semaphore resource = 1;  // 共享数据的访问权
semaphore rmutex = 1;    // 保护 read_count
semaphore wmutex = 1;    // 保护 write_count
semaphore read_try = 1;  // 有写者等待时阻止新读者进入

reader() {
    while (1) {
        P(read_try)                     // 写者到达后，新读者在此等待
        P(rmutex)                       // 修改 read_count
        read_count += 1
        if (read_count == 1) {
            P(resource)                 // 第一个读者锁定共享数据
        }
        V(rmutex)
        V(read_try)

        ...                             // 读取资源

        P(rmutex)
        read_count -= 1
        if (read_count == 0) {
            V(resource)                 // 最后一个读者释放共享数据
        }
        V(rmutex)
    }
}

writer() {
    while (1) {
        P(wmutex)
        write_count += 1
        if (write_count == 1) {
            P(read_try)                 // 第一个等待写者关闭读者入口
        }
        V(wmutex)

        P(resource)
        ...                             // 写入资源
        V(resource)

        P(wmutex)
        write_count -= 1
        if (write_count == 0) {
            V(read_try)                 // 最后一个写者重新开放读者入口
        }
        V(wmutex)
    }
}

int read_count = 0;
int write_count = 0;
semaphore wrt = 1;
semaphore mutex = 1;
semaphore queue = 1; // 新增队列信号量，以确保公平性

reader() {
    while (1) {
        P(queue);                 // 进入队列
        P(mutex);                 // 获取互斥访问权，以修改 read_count
        read_count += 1;
        if (read_count == 1) {
            P(wrt);               // 如果是第一个读者，锁定资源
        }
        V(mutex);
        V(queue);                 // 离开队列
        ...                       // 读取资源
        P(mutex);                 // 获取互斥访问权，以修改 read_count
        read_count -= 1;
        if (read_count == 0) {
            V(wrt);               // 如果是最后一个读者，释放资源
        }
        V(mutex);
    }
}

writer() {
    while (1) {
        P(queue);                 // 进入队列
        P(wrt);                   // 锁定资源
        ...                       // 写入资源
        V(wrt);                   // 释放资源
        V(queue);                 // 离开队列
    }
}

试题中如果考察读者写者问题的话，一般考察的还是读者优先，读者优先的同步实现方案可以通过以下流程图进行理解：

哲学家就餐问题

假设有五位 哲学家 坐在一个 圆桌 周围，每两位哲学家之间有一把 叉子。哲学家的生活由 思考和吃饭 两种活动组成。为了吃饭，一个哲学家需要两把叉子——左边和右边的一把。问题在于，如何设计一个算法使得哲学家们可以正常就餐，而不会因为竞争叉子而导致死锁或饥饿。

哲学家就餐问题有多种解法。这里保留一种直观的 非对称拿叉方案，它通过破坏循环等待条件避免死锁。对于包含 $N$ 位哲学家的问题：

• 前 $N-1$ 位哲学家先拿左叉，再拿右叉；
• 最后一位哲学家先拿右叉，再拿左叉。

const int N = 5;
semaphore fork[N] = {1, 1, 1, 1, 1}; // 五个叉子，初始都可用

void philosopher(int i) {
    if (i < N - 1) {
        // 前 N-1 位哲学家先左后右
        first = i;
        second = (i + 1) % N;
    } else {
        // 最后一位哲学家先右后左
        first = (i + 1) % N;
        second = i;
    }
    while (1) {
        think();
        P(fork[first]);
        P(fork[second]);
        eat();
        V(fork[first]);
        V(fork[second]);
    }
}

下面按上方的非对称顺序演示一次竞争：前四位先拿左叉，最后一位先拿右叉；因此总能留出一个可以继续拿到第二把叉子的进程，循环等待无法闭合。

01think();02P(fork[first]);03P(fork[second]);04eat();05V(fork[first]);06V(fork[second]);