操作系统学习笔记-2.3哲学家和管程问题

哲学家问题

问题描述

假设有五位哲学家围坐在一张圆桌旁，每位哲学家面前放有一盘意大利面，他们各自间隔放置一根叉子。哲学家的行为分为“思考”和“进餐”两种状态。为了进餐，哲学家需要同时拿起左手边和右手边的两根叉子。用餐结束后，他会放下叉子并继续思考。

问题的挑战

在此问题中，哲学家会面临以下资源竞争和同步问题：

1. 死锁：如果每个哲学家都拿起了左边的叉子并等待右边的叉子（同理右边情况），将会导致死锁，因为每个人都在等待别人释放叉子。

2. 饥饿：即使没有死锁，某些哲学家可能长时间无法获得两把叉子，从而导致饥饿问题。

3. 并发控制：我们希望尽可能让哲学家同时进餐，最大化资源利用率，避免资源被长时间锁住。
   

解决方案

哲学家问题的解决方案通常围绕以下思路展开，以确保哲学家不会陷入死锁或饥饿：

1. 奇偶编号的解决方法

让奇数编号的哲学家先拿左边的叉子，再拿右边的叉子；偶数编号的哲学家则相反。这样可以避免所有哲学家都同时拿起左边的叉子，从而减小死锁风险。

2. 服务员（或“门童”）机制（同时拿两只筷子）

引入一个“服务员”进程，只有在两个相邻的叉子都空闲时才允许哲学家进餐。服务员控制哲学家的进餐顺序，保证不会导致所有哲学家都拿到一只叉子后陷入等待。

3. 限制进餐人数

限制同时进餐的哲学家人数，比如限制为4人。这样一定有一名哲学家不会持有叉子，从而打破等待环，防止死锁的发生。

4. 信号量控制

使用信号量 semaphore 控制哲学家行为，可以设置一个信号量数组 forks，每个叉子与信号量相关联。当哲学家需要用餐时，尝试获取两侧的信号量，成功则用餐，否则等待。

管程

管程（Monitor）是一种高级的同步机制，提供了一种结构化的方式来管理并发环境下的共享资源。它是一种进程同步的抽象，可以看作是一种对象，封装了资源、共享数据以及对这些数据进行操作的过程，同时也提供了一个互斥访问的环境。

1. 管程的概念

管程是一种面向对象的同步原语，用于协调多个线程或进程对共享资源的访问。它包含以下关键部分：

• 共享资源：资源是所有线程需要访问的共享数据，如缓冲区、文件、变量等。

• 互斥访问：管程通过内置的互斥机制，确保在任何时刻只有一个线程能访问其内的数据，从而避免数据竞争和不一致性。

• 条件变量：管程使用条件变量来管理线程的等待和通知机制，允许线程在某种条件未满足时释放资源并进入等待状态。当条件满足时，被通知的线程可以重新获取资源继续执行。

2. 管程的结构

管程通常包含以下内容：

• 锁：管程内部有一个隐含的锁来保证互斥访问。线程在进入管程时需要获取锁，退出时会释放锁。

• 共享变量：管程中定义的共享变量在多个线程间共享，这些变量只能通过管程内部的方法来访问。

• 条件变量（Condition Variables）：用于管理线程等待的条件。条件变量通常提供了 wait() 和 signal() 方法：

  • wait()：如果条件未满足，调用线程会释放锁并进入等待状态。
  • signal()：当条件满足时，唤醒一个等待的线程，让它重新尝试进入临界区。

3. 管程的工作原理

管程的典型工作流程如下：

1. 互斥进入：当线程进入管程时，获得管程的锁，确保只有一个线程可以访问管程的共享数据。

2. 条件等待：如果条件不满足，线程会通过条件变量的 wait() 操作进入等待状态，同时释放锁。其他线程可以获得锁并尝试进入管程。

3. 条件通知：当某个条件满足时，线程可以通过条件变量的 signal() 操作来通知等待的线程。

4. 互斥退出：线程执行完操作后，释放锁，让其他线程可以进入管程。

4. 管程的典型应用

引入管程的目的无非就是要更方便地实现进程互斥和同步。

1. 需要在管程中定义共享数据(如生产者消费者问题的缓冲区)
2. 需要在管程中定义用于访问这些共享数据的“入口”—其实就是一些函数(如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品)
3. 只有通过这些特定的“入口”才能访问共享数据
4. 管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入(如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证个时间段内最多只会有一个进程在访问缓冲区。注意:这种互斥特性是由编译器负责实现的程序员不用关心)
5. 可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量万上等待(此时，该进程应先释放管程的使用权，也就是让出“入口”)；可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。
6. 程序员可以用某种特殊的语法定义一个管程(比如: monitor ProducerConsumer …end monitor;)之后其他程序员就可以使用这个管程提供的特定“入口”很方便地使用实现进程同步/互斥了。采用了封装思想

5. 管程的优缺点

• 优点：

  • 简化同步代码的设计：管程将同步逻辑封装在对象内部，提高了代码的模块化和可读性。
  • 保证了互斥访问，避免了死锁、资源竞争等问题。

• 缺点：

  • 实现相对复杂：尤其在需要处理多个条件变量的场景下，代码复杂度增加。
  • 扩展性有限：管程一般用于单机多线程的同步，分布式系统中应用有限。

2.3 其它杂七杂八知识点

临界区（Critical Section）指的是程序中多个线程可能同时访问的共享资源或共享代码片段。临界资源是多个线程或进程共享并且需要互斥访问的资源。
互斥信号量通常在未被占用时为1，被占用时为0。当信号量值为0时，其他线程将会被阻塞，直到该信号量重新释放（恢复到1）

可重入编码（Reentrant Code）是一种可以安全地在多个线程或多个进程中并发执行而不出现冲突的编码方式。可重入代码在执行时不会依赖全局或静态变量，也不保留静态状态，因此避免了多线程环境中的数据竞争。

mutex 的初值为1，表示允许一个进程进入临界区，当有一个进程进入临界区且没有进程等待进入时，mutex 减1，变为0。|mutex|为等待进入的进程数。