操作系统中的哲学家进餐问题与读者写者问题详解

操作系统中的哲学家进餐问题与读者写者问题详解

引用

CSDN

1.

https://blog.csdn.net/qq_44886731/article/details/146173523

哲学家进餐问题（Dining Philosophers Problem）

问题描述+解决方案

1. 问题描述

5个哲学家围坐在圆桌旁，每个哲学家面前有一盘面，左右各有一支筷子。哲学家需同时拿到左右两支筷子才能进餐，否则进入思考状态。

核心挑战：避免死锁（如所有哲学家同时拿起左边筷子导致无限等待）和饥饿。

2. 解决方案

信号量实现：

semaphore chopstick[5] = {1}; // 每支筷子初始为可用
semaphore mutex = 4; // 最多允许4人同时拿筷子

void philosopher(int i) {
    while (true) {
        think();
        wait(mutex);
        wait(chopstick[i]);
        wait(chopstick[(i+1)%5]);
        eat();
        signal(chopstick[i]);
        signal(chopstick[(i+1)%5]);
        signal(mutex);
    }
}

常见考点

简答：哲学家进餐问题的场景及死锁产生原因

问题场景：
5 位哲学家围坐在圆桌前，每人面前有一盘面，左右两侧各有一支筷子（共 5 支）。哲学家交替进行两种行为：

• 思考：不需要筷子。
• 进餐：必须同时拿起左右两支筷子。
  若无法同时获得两支筷子，则等待。

死锁产生原因
当所有哲学家同时执行以下动作时，发生死锁：

• 每位哲学家先拿起左侧筷子（wait(chopstick[i])）。
• 尝试拿右侧筷子时，发现右侧筷子已被邻居拿走，进入阻塞等待。
• 此时，死锁的四个必要条件均被满足：
• 互斥：筷子是临界资源，一次只能被一个哲学家使用。
• 持有并等待：哲学家持有一支筷子，等待另一支。
• 不可剥夺：哲学家不会主动释放已持有的筷子。
• 循环等待：每个哲学家都在等待右侧邻居持有的筷子，形成环形依赖。

算法：信号量实现无死锁的哲学家进餐问题
破坏死锁的必要条件之一（通常通过限制同时拿筷子的哲学家数量）。

代码实现（信号量 + 限制并发数）

semaphore chopstick[5] = {1}; // 每支筷子初始为可用
semaphore mutex = 4; // 最多允许4个哲学家同时拿筷子

void philosopher(int i) {
    while (true) {
        think();
        wait(mutex); // 限制最多4人进入拿筷子阶段
        wait(chopstick[i]); // 拿左筷子
        wait(chopstick[(i+1)%5]); // 拿右筷子
        eat();
        signal(chopstick[i]);
        signal(chopstick[(i+1)%5]);
        signal(mutex);
    }
}

mutex 初始值为 4：确保最多 4 人同时尝试拿筷子，至少剩 1 人无法拿筷子，打破循环等待。
按顺序申请资源：先申请左筷子，再申请右筷子，避免随机竞争。

变形：筷子数量变为 6 支，如何调整算法？
筷子总数由 5 支变为 6 支（例如：每位哲学家右侧额外增加一支筷子）。

资源分配策略：
原问题中资源数为 5，设置 mutex = 4；
现资源数为 6，可设置 mutex = 5（允许 5 人同时拿筷子）。

允许更多哲学家同时进餐：原本最多允许 4 人拿筷子，现因资源增加，可适当放宽限制。
调整 mutex 初始值：若保持“最多允许 N 人拿筷子”，需满足 N ≤ 资源总数 - 1（避免循环等待）。
注：允许的并发进程数 ≤ 资源数 - 1 或等价表述为：资源数 ≥ 允许的并发进程数 + 1

代码如下:

semaphore chopstick[6] = {1}; // 6支筷子
semaphore mutex = 5; // 最多允许5人同时拿筷子

void philosopher(int i) {
    while (true) {
        think();
        wait(mutex);
        wait(chopstick[i]);
        wait(chopstick[(i+1)%6]); // 右侧筷子编号为 (i+1)%6
        eat();
        signal(chopstick[i]);
        signal(chopstick[(i+1)%6]);
        signal(mutex);
    }
}

读者写者问题（Readers-Writers Problem）

问题描述+解决方案

1. 问题描述

多个读者和写者访问共享数据：

• 读者：可并发读取数据，但不可与写者同时访问。
• 写者：需独占访问，与其他读者/写者互斥。
  核心挑战：保证数据一致性，避免写者饥饿。

2. 解决方案（读者优先）

信号量实现：

semaphore rw_mutex = 1; // 读写互斥锁
semaphore count_mutex = 1; // 读者计数器互斥锁
int read_count = 0; // 当前读者数量

void writer() {
    wait(rw_mutex); // 写者独占访问
    write_data();
    signal(rw_mutex);
}

void reader() {
    wait(count_mutex); // 保护读者计数器
    if (read_count == 0) {
        wait(rw_mutex); // 第一个读者申请读写锁
    }
    read_count++;
    signal(count_mutex);
    read_data();
    wait(count_mutex);
    read_count--;
    if (read_count == 0) {
        signal(rw_mutex); // 最后一个读者释放读写锁
    }
    signal(count_mutex);
}

算法：读者优先或写者优先，分析性能差异

1.读者优先策略
核心逻辑：只要有一个读者正在读，后续读者可直接加入，写者必须等待所有读者完成。（代码同上）
性能分析：

• 优点：读者并发性高，吞吐量大。
• 缺点：写者可能饥饿（长期无法执行）。

2. 写者优先策略
核心逻辑：一旦有写者等待，后续读者需等待写者完成。

代码实现（需新增信号量）：

semaphore rw_mutex = 1; // 读写互斥锁
semaphore count_mutex = 1; // 读者计数器互斥锁
semaphore write_queue = 1; // 写者优先队列锁（新增）
int read_count = 0, write_wait = 0;

void writer() {
    wait(write_queue); // 进入写者队列
    wait(rw_mutex); // 申请写锁
    signal(write_queue);
    write_data();
    signal(rw_mutex);
}

void reader() {
    wait(write_queue); // 检查是否有写者等待
    wait(count_mutex);
    if (read_count == 0) {
        wait(rw_mutex);
    }
    read_count++;
    signal(count_mutex);
    signal(write_queue); // 释放队列锁
    read_data();
    wait(count_mutex);
    read_count--;
    if (read_count == 0) {
        signal(rw_mutex);
    }
    signal(count_mutex);
}

性能分析：

• 优点：避免写者饥饿，保证写操作及时执行。
• 缺点：读者并发性降低，吞吐量下降。

代码：补全代码，解释计数器作用

补全读者优先策略中的信号量操作代码，并说明 read_count 的作用。

void reader() {
    wait(count_mutex);
    if (read_count == 0) {
        wait(rw_mutex); // 第一个读者申请读写锁
    }
    read_count++;
    signal(count_mutex);
    read_data();
    wait(count_mutex);
    read_count--;
    if (read_count == 0) {
        signal(rw_mutex); // 最后一个读者释放读写锁
    }
    signal(count_mutex);
}

计数器 read_count 的作用：

• 跟踪并发读者数：记录当前正在读取共享数据的读者数量。
• 控制读写锁：当第一个读者进入时申请 rw_mutex，最后一个读者退出时释放 rw_mutex。
• 保证互斥：通过 count_mutex 保护 read_count 的原子操作。

对比分析：读者写者 vs. 生产者消费者

1. 相同点

• 同步与互斥：均需保证对共享资源的互斥访问。
• 信号量使用：均通过信号量（如 mutex）实现临界区保护。
  但信号量设计也有区别：读者写者使用计数器 + 读写锁，生产者消费者使用空/满信号量。

2. 不同点

生产者消费者问题如图演示

3. 读写锁的应用场景

• 高并发读取场景：如数据库查询，允许多线程并发读，提升吞吐量。
• 低频写入场景：如配置文件更新，写操作独占访问保证一致性。
• 实时性要求：写者优先策略用于日志写入等需及时持久化的操作。