网站怎样排版,中企建网站,网站seo关键词优化技巧,做pc网站排哲学家问题
问题描述
假设有五位哲学家围坐在一张圆桌旁#xff0c;每位哲学家面前放有一盘意大利面#xff0c;他们各自间隔放置一根叉子。哲学家的行为分为“思考”和“进餐”两种状态。为了进餐#xff0c;哲学家需要同时拿起左手边和右手边的两根叉子。用餐结束后每位哲学家面前放有一盘意大利面他们各自间隔放置一根叉子。哲学家的行为分为“思考”和“进餐”两种状态。为了进餐哲学家需要同时拿起左手边和右手边的两根叉子。用餐结束后他会放下叉子并继续思考。
问题的挑战
在此问题中哲学家会面临以下资源竞争和同步问题 死锁如果每个哲学家都拿起了左边的叉子并等待右边的叉子同理右边情况将会导致死锁因为每个人都在等待别人释放叉子。 饥饿即使没有死锁某些哲学家可能长时间无法获得两把叉子从而导致饥饿问题。 并发控制我们希望尽可能让哲学家同时进餐最大化资源利用率避免资源被长时间锁住。
解决方案
哲学家问题的解决方案通常围绕以下思路展开以确保哲学家不会陷入死锁或饥饿
1. 奇偶编号的解决方法
让奇数编号的哲学家先拿左边的叉子再拿右边的叉子偶数编号的哲学家则相反。这样可以避免所有哲学家都同时拿起左边的叉子从而减小死锁风险。
2. 服务员或“门童”机制同时拿两只筷子
引入一个“服务员”进程只有在两个相邻的叉子都空闲时才允许哲学家进餐。服务员控制哲学家的进餐顺序保证不会导致所有哲学家都拿到一只叉子后陷入等待。
3. 限制进餐人数
限制同时进餐的哲学家人数比如限制为4人。这样一定有一名哲学家不会持有叉子从而打破等待环防止死锁的发生。
4. 信号量控制
使用信号量 semaphore 控制哲学家行为可以设置一个信号量数组 forks每个叉子与信号量相关联。当哲学家需要用餐时尝试获取两侧的信号量成功则用餐否则等待。
管程
管程Monitor是一种高级的同步机制提供了一种结构化的方式来管理并发环境下的共享资源。它是一种进程同步的抽象可以看作是一种对象封装了资源、共享数据以及对这些数据进行操作的过程同时也提供了一个互斥访问的环境。
1. 管程的概念
管程是一种面向对象的同步原语用于协调多个线程或进程对共享资源的访问。它包含以下关键部分 共享资源资源是所有线程需要访问的共享数据如缓冲区、文件、变量等。 互斥访问管程通过内置的互斥机制确保在任何时刻只有一个线程能访问其内的数据从而避免数据竞争和不一致性。 条件变量管程使用条件变量来管理线程的等待和通知机制允许线程在某种条件未满足时释放资源并进入等待状态。当条件满足时被通知的线程可以重新获取资源继续执行。
2. 管程的结构 管程通常包含以下内容 锁管程内部有一个隐含的锁来保证互斥访问。线程在进入管程时需要获取锁退出时会释放锁。 共享变量管程中定义的共享变量在多个线程间共享这些变量只能通过管程内部的方法来访问。 条件变量Condition Variables用于管理线程等待的条件。条件变量通常提供了 wait() 和 signal() 方法 wait()如果条件未满足调用线程会释放锁并进入等待状态。signal()当条件满足时唤醒一个等待的线程让它重新尝试进入临界区。
3. 管程的工作原理
管程的典型工作流程如下 互斥进入当线程进入管程时获得管程的锁确保只有一个线程可以访问管程的共享数据。 条件等待如果条件不满足线程会通过条件变量的 wait() 操作进入等待状态同时释放锁。其他线程可以获得锁并尝试进入管程。 条件通知当某个条件满足时线程可以通过条件变量的 signal() 操作来通知等待的线程。 互斥退出线程执行完操作后释放锁让其他线程可以进入管程。
4. 管程的典型应用
引入管程的目的无非就是要更方便地实现进程互斥和同步。
需要在管程中定义共享数据(如生产者消费者问题的缓冲区)需要在管程中定义用于访问这些共享数据的“入口”—其实就是一些函数(如生产者消费者问题中可以定义一个函数用于将产品放入缓冲区再定义一个函数用于从缓冲区取出产品)只有通过这些特定的“入口”才能访问共享数据管程中有很多“入口”但是每次只能开放其中一个“入口”并且只能让一个进程或线程进入(如生产者消费者问题中各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证个时间段内最多只会有一个进程在访问缓冲区。注意:这种互斥特性是由编译器负责实现的程序员不用关心)可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量万上等待(此时该进程应先释放管程的使用权也就是让出“入口”)可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。程序员可以用某种特殊的语法定义一个管程(比如: monitor ProducerConsumer …end monitor;)之后其他程序员就可以使用这个管程提供的特定“入口”很方便地使用实现进程同步/互斥了。采用了封装思想
5. 管程的优缺点 优点 简化同步代码的设计管程将同步逻辑封装在对象内部提高了代码的模块化和可读性。保证了互斥访问避免了死锁、资源竞争等问题。 缺点 实现相对复杂尤其在需要处理多个条件变量的场景下代码复杂度增加。扩展性有限管程一般用于单机多线程的同步分布式系统中应用有限。
2.3 其它杂七杂八知识点
临界区Critical Section指的是程序中多个线程可能同时访问的共享资源或共享代码片段。临界资源是多个线程或进程共享并且需要互斥访问的资源。 互斥信号量通常在未被占用时为1被占用时为0。当信号量值为0时其他线程将会被阻塞直到该信号量重新释放恢复到1
可重入编码Reentrant Code是一种可以安全地在多个线程或多个进程中并发执行而不出现冲突的编码方式。可重入代码在执行时不会依赖全局或静态变量也不保留静态状态因此避免了多线程环境中的数据竞争。
mutex 的初值为1表示允许一个进程进入临界区当有一个进程进入临界区且没有进程等待进入时mutex 减1变为0。|mutex|为等待进入的进程数。
