东莞网站建设设计公司哪家好,杭州建设网站官网,网站建设网站目的模板,wordpress扫码下载目录
哲学家进餐问题描述
解决方案 1#xff1a;
解决方案 2#xff1a;信号量实现
解决方案 3#xff1a;使用 Monitor 的实现
1. 监视器的组成部分
2. 监视器的优点
3. 使用监视器解决哲学家进餐问题
4. 使用监视器的优势 5. 监视器的局限性
6. Mesa风格和Hoare风…目录
哲学家进餐问题描述
解决方案 1
解决方案 2信号量实现
解决方案 3使用 Monitor 的实现
1. 监视器的组成部分
2. 监视器的优点
3. 使用监视器解决哲学家进餐问题
4. 使用监视器的优势 5. 监视器的局限性
6. Mesa风格和Hoare风格监视器的区别
1. 调用 notify() 时的行为
2. Mesa风格的监视器
3. Hoare风格的监视器
总结
总结 并发控制是操作系统和多线程编程中的一个核心问题。哲学家进餐问题Dining Philosophers Problem 是一个经典案例展示了在共享资源上进行协调的挑战及其解决方案。本篇博客将详细讲解哲学家进餐问题并展示三种主要解决方案特别是通过 Monitor 来实现高效的并发控制。
哲学家进餐问题描述
假设有五位哲学家围坐在圆桌旁每位哲学家之间有一只叉子。哲学家有两种行为思考和进餐。要进餐哲学家需要同时拿起左边和右边的两只叉子。一旦进餐完毕哲学家会放下叉子并开始思考。这个问题的核心挑战是如何设计一种机制避免死锁和饥饿并最大限度地提高并行度。
解决方案 1
在这种方法中每个哲学家都尝试同时拿起两只叉子
void pickup(int i) {wait(fork[i]); // 拿起左边的叉子wait(fork[(i 1) % 5]); // 拿起右边的叉子
}void putdown(int i) {signal(fork[i]); // 放下左边的叉子signal(fork[(i 1) % 5]); // 放下右边的叉子
}缺点这种实现容易导致死锁。例如如果所有哲学家同时拿起左边的叉子并等待右边的叉子整个系统将陷入僵局。
解决方案 2信号量实现
使用信号量控制叉子的可用性和哲学家的同步。
sem_t forks[5]; // 初始化为1表示每个叉子都可用void pickup(int i) {sem_wait(forks[i]); // 拿起左边的叉子sem_wait(forks[(i 1) % 5]); // 拿起右边的叉子
}void putdown(int i) {sem_post(forks[i]); // 放下左边的叉子sem_post(forks[(i 1) % 5]); // 放下右边的叉子
}缺点这种方法通过信号量避免了死锁但无法实现最大并行度因为哲学家无法同时进餐。
解决方案 3使用 Monitor 的实现 1. 监视器的组成部分
监视器是一种高级同步机制通过封装共享资源和相关操作确保只有一个线程能在任一时刻访问和操作共享资源。其主要组成部分包括
共享私有数据Shared Private Data管理监视器所保护的资源外部线程无法直接访问确保数据封装性和安全性。操作数据的程序Monitor Procedures访问和操作共享数据的唯一途径保证线程在同步环境下安全地进行数据操作。同步原语Synchronization Primitives使用条件变量和锁来管理线程的等待和唤醒避免繁忙等待提高系统资源利用率。 2. 监视器的优点
避免信号量的复杂性监视器自动封装了同步逻辑简化了代码的实现减少了使用信号量引发的死锁风险。自动管理互斥监视器保证在任意时刻只有一个线程可以进入和执行监视器中的方法。避免繁忙等待当线程无法获取资源时进入等待队列而不占用 CPU 资源。 3. 使用监视器解决哲学家进餐问题
在哲学家进餐问题中使用监视器可提供一种简洁而有效的资源竞争与同步管理方法。
核心思路
状态管理每个哲学家有三种状态——THINKING思考、HUNGRY饥饿、EATING用餐并通过一个共享的 state 数组记录状态。条件变量每个哲学家都有自己的条件变量 self[i]用于在不能用餐时进入等待状态。互斥和同步使用锁和条件变量确保同时只有一个线程能操作监视器避免竞争条件。
实现逻辑 pickup(i) 哲学家 i 调用 pickup() 将其状态设置为 HUNGRY。调用 test(i) 检查左右邻居状态决定是否进入用餐状态。如果不能用餐进入 self[i] 等待队列等待唤醒。 putdown(i) 用餐结束后调用 putdown() 将状态设置为 THINKING。调用 test() 检查左右邻居是否可以用餐并唤醒满足条件的哲学家。 test(i) 检查哲学家 i 是否可以用餐即 state[i] HUNGRY 且左右邻居都不在 EATING 状态。条件满足时将状态设为 EATING 并唤醒 self[i]。
代码示例
monitor DiningPhilosophers {enum { THINKING, HUNGRY, EATING } state[5];condition self[5];void pickup(int i) {state[i] HUNGRY;test(i);if (state[i] ! EATING)self[i].wait();}void putdown(int i) {state[i] THINKING;test((i 4) % 5);test((i 1) % 5);}void test(int i) {if (state[i] HUNGRY state[(i 4) % 5] ! EATING state[(i 1) % 5] ! EATING) {state[i] EATING;self[i].signal();}}initialization_code() {for (int i 0; i 5; i)state[i] THINKING;}
}4. 使用监视器的优势
无死锁通过 self[i] 条件变量控制每个哲学家在无法用餐时主动等待避免了相互持有资源而导致的死锁。高并发性允许不相邻的哲学家同时用餐实现最大化并行。代码简洁使用监视器封装同步逻辑简化了实现和维护。 5. 监视器的局限性
嵌套监视器在一个监视器内调用另一个监视器方法可能导致死锁。这是因为嵌套结构会增加持有锁的复杂度导致不同的线程之间出现相互等待最终无法继续执行。优先级反转监视器无法解决优先级反转问题。当一个低优先级线程持有监视器时高优先级线程可能会被阻塞直到低优先级线程释放监视器。灵活性受限相比信号量监视器在某些复杂同步需求中不够灵活。 6. Mesa风格和Hoare风格监视器的区别
1. 调用 notify() 时的行为
没有等待线程 通知线程继续执行信号会被丢失不会唤醒任何线程。有等待线程 唤醒一个线程执行其他线程继续等待。
2. Mesa风格的监视器
通知线程保持锁并继续执行等待线程需等待锁释放后才能继续。优点实现简单适合多任务调度。缺点等待线程可能需延迟较长时间。
3. Hoare风格的监视器
通知线程立即释放锁唤醒等待线程并将锁交给它。等待线程完成后将锁归还给通知线程。优点更快响应信号提供更精确的同步控制。缺点实现复杂锁的频繁切换增加了系统开销。
总结
Mesa风格灵活、易于实现适合多任务调度的操作系统。Hoare风格同步更强但实现复杂常用于理论讨论。 总结
哲学家进餐问题展示了并发编程中的同步挑战。简单的实现容易导致死锁而使用信号量可以避免死锁但并行度有限。通过 Monitor 实现解决了死锁问题并最大化了并行度是一种高级而高效的并发控制方法。
Monitor 作为一种抽象数据类型封装了共享数据和同步操作在解决并发问题时提供了极大的便利。
