精华内容
下载资源
问答
  • 2019-09-06 16:48:38

    一、管程

    1.采用封装的思想

    2.解决信号量机制或者PV操作编程麻烦的、易出错等问题

    3.可看做一个软件模块,将共享的变量和对于这些共享变量的操作封装起来,形成一个具有一定接口的功能模块,进程可以调用管程来实现进程级别的并发

    4.管程的组成(封装):共享数据结构、对数据结构初始化的语句、一组用来访问数据的过程即是函数

        例如:enter过程、leave过程、条件型变量c、wait(c) 、signal(c)

    5.基本特征:各外部进程/线程只能通过管程提供特定“入口”(接口)才能访问共享数据每次仅允许一个进程/线程在管程内执行某个内部过程

    补充:各进程必须互斥访问管程由编译器实现的;可在管程中设置条件变量及等待wait/唤醒signal操作以解决同步问题

    二、死锁和饥饿

    1.死锁现象:某计算机系统中只有一台打印机和一台输出设备,进程P1正在占用输入设备,同时又提出使用打印机的请求,但此时打印机正被进程P2占用,而P2在未释放打印机之前,又提出请求使用正被P1占用着的输入设备。

    2.死锁(各进程):并发环境下,互相等待,各进程都阻塞,无法继续向前推进

       饥饿(某进程):某进程无法继续向前推进

    3.产生死锁必须同时满足4个条件:

                    互斥条件;不剥夺条件(只能主动释放,不能由其他进程强行夺走);请求和保持条件;循环等待条件 

    举例:如果你手上拿着一个苹果不吃,别人也无法抢走,这就是不可剥夺条件;如果你左手拿一个苹果,允许右手再去拿一个,这就是请求和保持条件。

    4.产生死锁的时机:对不可剥夺资源的不合理分配

    5.死锁的处理----不允许死锁发生----静态策略:预防(破坏4个必要条件)

    破坏互斥条件:SPOOLing(假脱机)技术,允许设备共享使用;

    破坏不剥夺条件:常用于状态易于保存和回复的资源,如CPU的寄存器及内存资源;

    破坏请求和保护条件:采用预先静态分配,进程在运行前一次申请完它所需的全部资源,可能会导致系统资源浪费和饥饿现象;

    破坏循环等待条件:采用顺序资源分配法,并对系统中的资源进行编号,必须按编号顺序申请。

    6.死锁的处理----不允许死锁发生----动态策略:避免

    银行家算法:n种进程,m种资源

    检查此次申请是否超过之前声明的最大需求数------>检查此时系统剩余的可用资源是否还能满足这次请求(满足为安全,不满足为不安全)----> 试探分配,更改各数据结构---->用安全性算法检查此次分配是否会导致系统进入不安全状态

    安全性算法

    检查当前的剩余可用资源是否能满足某个进程的最大需求(满足为安全,不满足为不安全)---->如果满足,把该进程加入安全序列,并把该进程持有资源回收----->所有进程全部能加入安全序列即是安全状态,否则系统处于不安全状态

    7.死锁的处理----允许死锁发生----死锁的检测和解除

    检测

    补充:数据结构(有向图):两结点:资源和进程;两边 (请求:进程--->资源,分配:资源----->进程)

    死锁定理: 资源分配图中找出一条有向边与即不阻塞又不是孤点的进程Pi相连,且该邮箱变对应资源申请数小于等于系统空闲资源数,并简化,当且仅当资源分配图不可完全简化时会发生死锁。

    解除

    资源剥夺法(挂起某些死锁进程并抢夺它的资源)、终止进程法(强制撤销,剥夺资源)、进程回退法(让进程回退到足以避免死锁的地步)

    更多相关内容
  • 死锁和饥饿有什么区别?如何解决?

    1、分述

    1. 饥饿是指系统不能保证某个进程的等待时间上界,从而使该进程长时间等待,当等待时间给进程推进和响应 带来明显影响时,称发生了进程饥饿。当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义 时称该进程被饿死。
    2. 死锁是指在多道程序系统中,一组进程中的每一个进程都无限期等待被该组进程中的另一个进程所占有且永远不会释放的资源。

    2、区别

     

    相同点:二者都是因为竞争资源引起的。
    不同点:我觉得可以这么理解死锁和饥饿的区别,首先死锁是同步的,饥饿时异步的。也就是说,死锁可以认为是两个及以上线程或进程同时在请求对方占有的资源。饥饿可以认为是一个或以上线程或是进程在无限 的等待另外两个或多个线程或进程占有的但是不会往外释放的资源。就是死锁里资源的占有方和资源的拥有 方互相请求对方的资源,但是饥饿时一方请求不知道哪一方的资源,就是饿了需要进食,但是谁给都行。
    1. 从进程状态考虑,死锁进程都处于等待状态,忙等待 ( 处于运行或就绪状态 ) 的进程并非处于等待状态,但却可能被饿死;
    2. 死锁进程等待永远不会被释放的资源,饿死进程等待会被释放但却不会分配给自己的资源,表现为等待时限没有上界(界限) ( 排队等待或忙式等待 )
    3. 死锁一定发生了循环等待,而饿死则不然。这也表明通过资源分配图可以检测死锁存在与否,但却不能检测是否有进程饿死;
    4. 死锁一定涉及多个进程,而饥饿或被饿死的进程可能只有一个。
    5. 在饥饿的情形下,系统中有至少一个进程能正常运行,只是饥饿进程得不到执行机会。而死锁则可能会最终使整个系统陷入死锁并崩溃。

    3、案例

     

    死锁案例

    例子 1 :如果线程 A 锁住了记录 R1 并等待记录 R2 ,而线程 B 锁住了记录 R2 并等待记录 R1 ,这样两个线程 A B 就发生了死锁现象。
    例子 2 :两个山羊过一个独木桥,两只羊同时走到桥中间,一个山羊等另一个山羊过去了然后再过桥,另一个山羊等这一个山羊过去,结果两只山羊都堵在中间动弹不得。

    饥饿案例

    资源在其中两个或以上线程或进程相互使用,第三方线程或进程始终得不到。想像一下三 个人传球,其中两个人传来传去,第三个人始终得不到。

    4、解决问题

     

    饥饿

    多创建一个线程池解决问题,做菜线程池就是做菜线程池,服务员线程池就是服务员线程池。各个线程池各司其职。

    死锁

    打破互斥条件;
    改造独占性资源为虚拟资源
    展开全文
  • 操作系统-并发:死锁和饥饿

    千次阅读 2019-05-26 13:32:22
    本章介绍并发处理中需要解决的两个问题:死锁和饥饿。本章首先讨论死锁的基本原理和饥饿的相关问题;接着分析处理死锁的三种常用方法:预防、检测避免;然后考虑用于说明同步和死锁的一个经典问题;哲学家就餐问题...

    在这里插入图片描述

    知识架构

    本章介绍并发处理中需要解决的两个问题:死锁和饥饿。本章首先讨论死锁的基本原理和饥饿的相关问题;接着分析处理死锁的三种常用方法:预防、检测和避免;然后考虑用于说明同步和死锁的一个经典问题;哲学家就餐问题。

    作为对全局知识的把控,这里给出学习目标,作为参考:

    • 列举并解释死锁产生的条件
    • 定义死锁预防,针对死锁产生的条件给出死锁预防的策略
    • 理解死锁预防与死锁避免的区别
    • 掌握死锁避免的两种方法
    • 理解死锁检测与死锁预防、死锁检测与死锁避免的本质区别
    • 掌握设计综合死锁解决策略的方法
    • 分析哲学家就餐问题

    6.1 死锁原理

    死锁定义为一组相互竞争系统资源或进行通信的进程间的“永久”阻塞。当一组进程中的每个进程都在等待某个事件(典型情况下是等待释放所请求的资源),而仅有这组进程中被阻塞的其他进程才可触发该事件时,就称这组进程发生了死锁。因为没有事件能够被触发,故死锁是永久性的。与并发进程管理中的其他问题不同,死锁问题并无有效的通用解决方案。

    6.1.1 可重用资源

    资源通常分为两类:可重用资源和可消耗资源。可重用资源是指一次仅供一个进程安全使用且不因使用而耗尽的资源。进程得到资源单元并使用后,会释放这些单元供其他进程再次使用。可重用资源的例子包括处理器、I/O通道、内存和外存、设备,以及诸如文件、数据库和信号量之类的数据结构。

    下面给出一个涉及可重用资源死锁的例子。考虑相互竞争的两个进程都要独占访问磁盘文件D和磁带设备T的情形。程序执行如图6.4所示的操作。每个进程都占用一个资源并请求另一个资源时,就会发生死锁;例如,多道程序设计系统交替地执行两个进程时会发生死锁,如下所示:
    在这里插入图片描述

    这看起来更像程序设计错误而非操作系统设计人员的问题。由于并发程序设计非常具有挑战性,因此这类死锁的确会发生,而发生的原因通常隐藏在复杂的程序逻辑中,因此检测非常困难。处理这类死锁的一个策略是,给系统设计施加关于资源请求顺序的约束

    可重用资源死锁的另一个例子是内存请求。假设可用的分配空间为200KB,且发生的请求序列如下所示:
    在这里插入图片描述
    两个进程都行进到它们的第二个请求时,就会发生死锁。因为对方都不释放内存,那么另外一个进程就无法申请到新的内存,如果不申请到新的内存,就不会继续执行以释放内存,这就是产生死锁的根本原因所在。 若事先并不知道请求的存储空间总量,则很难通过系统设计约束来处理这类死锁。解决这类特殊问题的最好办法是,使用虚存有效地消除这种可能性。

    在可重用资源上发生死锁是非常典型的现象。有的人可能对死锁的影响也只停留于于此,但是还有一种可消耗资源上的死锁,也很常见。

    6.1.2 可消耗资源

    可消耗资源是指可被创建(生产)和销毁(消耗)的资源。某种类型可消耗资源的数量通常没有限制,无阻塞生产进程可以创建任意数量的这类资源。消费进程得到一个资源时,该资源就不再存在。可消耗资源的例子有中断、信号、消息和I/O缓冲区中的信息。

    作为一个涉及可消耗资源死锁的例子,考虑下面的进程对,其中的每个进程都试图从另一个进程接收消息,然后再给那个进程发送一条消息:
    在这里插入图片描述
    Receive阻塞(即接收进程被阻塞直到收到消息)时,发生死锁。同样,引发死锁的原因是一个设计错误。这类错误比较微妙,因而难以发现。此外,罕见的事件组合也会导致死锁,因此只有当程序使用了相当长的一段时间甚至几年后,才可能出现这类问题(即发生死锁)。

    不存在解决所有类型死锁的有效策略。表6.1概括了已有方法中最重要的那些方法的要素:检测、预防和避免。首先详细阐述死锁的条件,然后依次分析每种方法(现在看来这张表可能有些抽象,实际上这是下面关于解决死锁问题讨论的总结,可以先看下面的讨论,而不用纠结于这张表)。
    在这里插入图片描述

    6.1.3 资源分配图

    表征进程资源分配的有效工具是Holt引入的资源分配图(resource allocation graph)。资源分配图是有向图,它说明了系统资源和进程的状态,其中每个资源和进程用节点表示。图中从进程指向资源的边表示进程请求资源但还未得到授权,如图6.5(a)所示。资源节点中,圆点表示资源的一个实例。I/O设备是有多个资源实例的资源类型,它由操作系统中的资源管理模块分配。图中从可重用资源节点中的点到一个进程的边表示请求已被授权,如图6.5(b)所示;也就是说,该进程已被安排了一个单位的资源。图中从可消耗资源节点中的点到一个进程的边表示进程是资源生产者。
    在这里插入图片描述
    图6.5(c)是一个死锁的例子。资源Ra和Rb都仅拥有一个单元的资源。进程P1持有Rb同时请求Ra;进程P2持有Ra同时请求Rb。图6.5(d)和图6.5(c)的拓扑结构相同,但图6.5(d)不会发生死锁,因为每个资源有多个实例。

    图6.6所示资源分配图的死锁情况与图6.1(b)类似。与6.5(c)不同的是,图6.6不是两个进程彼此拥有对方所需资源的简单情况,而是存在进程和资源的环,因此导致了死锁(但本质和图6.5(c)还是一样的)。
    在这里插入图片描述

    6.1.4 死锁条件

    死锁有三个必要条件:

    1. 互斥(独占性)。一次只有一个进程可以使用一个资源。其他进程不能访问已分配给其他进程的资源。
    2. 占有且等待。当一个进程等待其他进程时,继续占有已分配的资源。
    3. 不可抢占。不能强行抢占进程已占有的资源。

    在很多情况下,这些条件很容易满足。例如,要确保结果的一致性和数据库的完整性,互斥是非常有必要的。同理,不能随意地进行资源抢占。比如,在涉及数据资源时,必须提供回滚恢复机制(rollback recovery mechanism)来支持资源抢占,只有这样才能把进程及其资源恢复到以前的适当状态,使得进程最终可以重复其动作。前三个条件都只是死锁存在的必要条件而非充分条件。要产生死锁,还需要第四个条件:

    1. 循环等待。存在一个闭合的进程链,每个进程至少占有此链中下一个进程所需的一个资源,如图6.5(c)和图6.6所示。

    第四个条件实际上是前三个条件的潜在结果,即假设前三个条件存在,那么可能发生的一系列事件会导致不可解的循环等待。这个不可解的循环等待实际上就是死锁的定义。条件4中列出的循环等待之所以不可解,是因为有前面三个条件的存在。因此,这四个条件一起构成了死锁的充分必要条件。
    在这里插入图片描述

    6.2 死锁的预防

    简单地讲,死锁预防(deadlock prevention)策略是试图设计一种系统来排除发生死锁的可能性。死锁预防方法分为两类。一类是间接死锁预防方法,即防止前面列出的三个必要条件中的任何一个条件的发生(见6.4.1节到6.4.3节);另一类是直接死锁预防方法,即防止循环等待的发生(见6.4.4节)。下面具体分析与这4个条件相关的技术问题。

    6.2.1 互斥

    一般来说,在所列出的4个条件中,第一个条件不可能禁止。如果需要对资源进行互斥访问,那么操作系统就必须支持互斥。某些资源,如文件,可能允许多个读访问,但只能允许互斥的写访问,此时若有多个进程请求写权限,则也可能发生死锁。

    6.2.2 占有且等待

    为预防占有且等待的条件,可以要求进程一次性地请求所有需要的资源,并阻塞这个进程直到所有请求都同时满足(即:要不就不请求资源,请求就一下子全部请求,并一次全部得到,或者不得到)。这种方法有两个方面的低效性。首先,一个进程可能被阻塞很长时间,以等待满足其所有的资源请求。而实际上,只要有一部分资源,它就可以继续执行。其次,分配给一个进程的资源可能会在相当长的一段时间不会被该进程使用,且不能被其他进程使用。另一个问题是一个进程可能事先并不知道它所需要的所有资源。

    这也是应用程序在使用模块化程序设计或多线程结构时产生的实际问题。要同时请求所需的资源,应用程序需要知道其以后将在所有级别或所有模块中请求的所有资源。

    6.2.3 不可抢占

    预防不可抢战的方法有几种。首先,占有某些资源的一个进程进一步申请资源时若被拒绝,则该进程必须释放其最初占有的资源,必要时可再次申请这些资源和其他资源。其次,一个进程请求当前被另一个进程占有的一个资源时,操作系统可以抢占另一个进程,要求它释放资源。只有在任意两个进程的优先级都不同的条件下,后一种方案才能预防死锁。

    此外,只有在资源状态可以很容易地保存和恢复的情况下(就像处理器一样),这种方法才是实用的。

    6.3.4 循环等待

    循环等待条件可通过定义资源类型的线性顺序来预防。若一个进程已分配了R类型的资源,则其接下来请求的资源只能是那些排在R类型之后的资源。

    为证明这种策略的正确性,我们给每种资源类型指定一个下标。当i</时,资源R,排在资源R
    前面。现在假设两个进程A和B死锁,原因是A获得R并请求R,而B获得R,并请求R,那么这个条件不可能,因为这意味着i<j且j<i。

    类似于占有且等待的预防方法,循环等待的预防方法可能是低效的,因此它会使进程执行速度变慢,且可能在没有必要的情况下拒绝资源访问。

    6.3 死锁避免

    解决死锁问题的另一种方法是死锁避免(deadlock avoidance),它和死锁预防的差别很小。在死锁预防(deadlock prevention)中,约束资源请求至少可破坏四个死锁条件中的一个条件。这可通过防止发生三个必要条件中的一个(互斥、占有且等待、非抢占)间接完成,也可通过防止循环等待直接完成,但都会导致低效的资源使用和低效的进程执行。死锁避免则相反,它允许三个必要条件,但通过明智地选择,可确保永远不会到达死锁点,因此死锁避免与死锁预防相比,可允许更多的并发。在死锁避免中,是否允许当前的资源分配请求是通过判断该请求是否可能导致死锁来决定的。因此,死锁避免需要知道未来进程资源请求的情况。

    本节给出了两种死锁避免方法:

    • 若一个进程的请求会导致死锁,则不启动该进程
    • 若一个进程增加的资源请求会导致死锁,则不允许这一资源分配

    关于这两点的进一步讨论显得有些无聊,如果感兴趣的话,可以直接去查看原书中的描述,如果做了解的话,到这一步已经足够了。下面的6.4.1死锁检测算法也是一样的。

    6.4 死锁检测

    死锁预防策略非常保守,它们通过限制访问资源和在进程上强加约束来解决死锁问题。死锁检测策略则完全相反,它不限制资源访问或约束进程行为。对于死锁检测(deadlock detection)来说,只要有可能,就会给进程分配其所请求的资源。操作系统周期性地执行一个算法来检测前面的条件(4),即图6.6中描述的循环等待条件。

    6.4.1 死锁检测算法

    死锁检测可以频繁地在每个资源请求发生时进行,也可进行得少一些,具体取决于发生死锁的可能性。在每次请求资源时检查死锁有两个优点:可以尽早地检测死锁情况;算法相对比较简单,因为这种方法基于系统状态的逐渐变化情况。然而,这种频繁的检测会耗费相当多的处理器时间。

    具体的检测算法不做说明,只要知道这种算法可以检测出来发生死锁即可。

    6.4.2 恢复

    检测到死锁后,就需要某种策略来恢复死锁。下面按复杂度递增的顺序列出可能的方法:

    1. 取消所有的死锁进程。这是操作系统中最常采用的方法。
    2. 把每个死锁进程回滚到前面定义的某些检查点,并重新启动所有进程。此时,要求在系统中构建回滚和重启机制。这种方法的风险是原来的死锁可能再次发生。但是,并发进程的不确定性通常能保证不会发生这种情况。
    3. 连续取消死锁进程直到不再存在死锁。所选取消进程的顺序应基于某种最小代价原则。在每次取消后,必须重新调用检测算法,以测试是否仍存在死锁。
    4. 连续抢占资源直到不再存在死锁。和(3)一样,需要使用一种基于代价的选择方法,且需要在每次抢占后重新调用检测算法。一个资源被抢占的进程必须回滚到获得这个资源之前的某一状态。

    对于(3)和(4),选择原则如采用如下之一:

    • 目前为止消耗的处理器时间最少。
    • 目前为止产生的输出最少。
    • 预计剩下的时间最长。
    • 目前为止分配的资源总量最少。
    • 优先级最低。

    在这些原则中,有些原则更易于测度。预计剩下的时间最值得怀疑。此外,除优先级测度外,相对于整个系统的代价而言,其他原则对用户而言没有任何代价。

    6.5 一种综合的死锁策略

    如表6.1所示,解决死锁的所有策略都各有优缺点。与其将操作系统机制设计为只采用其中的一种策略,不如在不同情况下使用不同的策略。[HOWA73]提出了一种方法:

    • 把资源分成几组不同的资源类。
    • 为预防在资源类之间由于循环等待产生死锁,可使用前面定义的线性排序策略。
    • 在一个资源类中,使用该类资源最适合的算法。

    作为这种技术的一个例子,我们考虑如下资源类:

    • 可交换空间:进程交换所用外存中的存储块。
    • 进程资源:可分配的设备,如磁带设备和文件。
    • 内存:可按页或按段分配给进程。
    • 内部资源:诸如I/O通道。

    前面给出的次序表明了资源分配的次序。考虑到一个进程在其生命周期中可能会遵循这样的顺序,因此这个次序是最合理的。在每一类中,可采用以下策略:

    • 可交换空间:要求一次性分配所有请求的资源来预防死锁,就像古有等待预防策略一样。若知道最大存储需求(通常情况下都知道),则这个策略是合理的,死锁避免也是可能的。
    • 进程资源:对于这类资源,死锁避免策略通常是很有效的,因为进程可以事先声明它们需要的这类资源。采用资源排序的预防策略也是可能的。
    • 内存:对于内存,基于抢占的预防是最适合的策略。当一个进程被抢占后,它仅被换到外存,释放空间以解决死锁。
    • 内部资源:可以使用基于资源排序的预防策略。

    6.6 哲学家就餐问题

    6.6.1 基于信号量的解决方案

    图6.12给出了基于信号量的解决方案。每位哲学家首先拿起左边的叉子,然后拿起右边的叉子。
    在哲学家吃完面后,这两把叉子又被放回到餐桌上。这个解决方案会导致死锁:如果所有哲学家在同一时刻都感到饥饿,那么他们都会坐下来,都拿起左边的叉子,都伸手拿右边的叉子,但都没有拿到。在这种有损尊严的状态下,所有哲学家都会处于饥饿状态。
    在这里插入图片描述

    为避免死锁的危险,可再买5把叉子(一种更卫生的解决方案)或教会哲学家仅用一把叉子吃面。另一种方法是,考虑增加一位服务员,他/她只允许4位哲学家同时进入餐厅,由于最多有4位哲学家就座,因而至少有一位哲学家可以拿到两把叉子。图6.13显示了这种方案,这里再次使用了信号量。这个方案不会发生死锁和饥饿。
    在这里插入图片描述

    6.6.2 基于管程的解决方案

    图6.14给出了基于管程的哲学家就餐问题的解决方案。这种方案定义了一个含有5个条件变量的向量,每把又子对应一个条件变量。这些条件变量用来标示哲学家等待的叉子可用情况。另外,用一个布尔向量记录每把叉子的可用情况(true表示叉子可用)。管程包含了两个过程。get_forks函数表示哲学家取他/她左边和右边的叉子。如果至少有一把叉子不可用,那么哲学家进程就会在条件变量的队列中等待。这可让其他哲学家进程进入管程。release-forks函数用来标示两把叉子可用。注意,这种解决方案的结构和图6.12中的信号量解决方案相似。在这两种方案中,哲学家都是先取左边的叉子,然后取右边的叉子。与信号量不同的是,管程不会发生死锁,因为在同一时刻只有一个进程进入管程。比如,第一位哲学家进程进入管程保证了只要他拿起左边的叉子,其右边的哲学家可以拿到其左边的叉子之前(即这位哲学家右边的叉子),就一定可以拿到右边的叉子。
    在这里插入图片描述

    6.7 小结

    死锁是指一组争用系统资源的进程或互相通信的进程被阻塞的现象。这种阻塞是永久性的,除非操作系统采取某些非常规行动,如杀死一个或多个进程,或强迫一个或多个进程进行回滚。死锁可能涉及可重用资源或可消耗资源。可重用资源是指不会因使用而被耗尽或销毁的资源,如I/O通道或一块内存区域。可消耗资源是指当被一个进程获得时就销毁的资源,这类资源的例子有消息和I/O缓冲区中的信息。

    处理死锁通常有三种方法:预防、检测和避免。死锁预防通过确保不满足死锁的一个必要条件来避免发生死锁。操作系统总是同意资源请求时,需要进行死锁检测。操作系统必须周期性地检查死锁,并采取行动打破死锁。死锁避免涉及分析新的资源请求,以确定它是否会导致死锁,且仅当不可能发生死锁时才同意该请求。

    在程序编写过程中也会经常会遇到死锁的情况,这就需要使用语言提供的相应的机制来打破,打破的方法,也就是从上面提到的方法中入手。作为参考,可以来看看java中是如何解决死锁问题的。
    https://www.cnblogs.com/xiaoxi/p/8311034.html

    展开全文
  • 并发性死锁和饥饿PPT教案学习.pptx
  • 死锁和饥饿-哲学家就餐问题

    千次阅读 2019-11-05 14:38:59
    哲学家就餐问题 背景: 假设5位哲学家住在一起(可以推广到n),...问题: 设计算法 保证互斥(2位哲学家不能使用相邻的叉子),同时还要避免死锁(每个哲学家都在等待叉子,且占用了叉子)和饥饿 信号量解决方案 规定:...

    哲学家就餐问题

    • 背景:
    1. 假设5位哲学家住在一起(可以推广到n),每天生活就是思考和吃饭,每位哲学家需要2把叉子来吃意大利面.
    2. 就餐安排: 一张圆桌,5个板凳,5个盘子,5把叉子,每个想吃饭的哲学家做到椅子上,使用盘子2侧的叉子来吃面条,
    3. 问题: 设计算法 保证互斥(2位哲学家不能使用相邻的叉子),同时还要避免死锁(每个哲学家都在等待叉子,且占用了叉子)和饥饿

    问题图片

    信号量解决方案

    • 规定: 每位哲学家首先拿起左边的叉子,然后拿起右边的叉子
    semaphore fork[5] = {1};
    int i;
    void philosopher (int i) {
        while (true) {
            think();
            wait(fork[i]); //等待左边的叉子
            wait(fork[(i+1) % 5]; // 等待右边的叉子
            eat();
            signal(fork[(i+1) % 5]); // 放回右边的叉子
            signal(fork[i]; //放回左边的叉子 (增加信号量)
        }
    }
    void mian() {
    	parbegin(philosopher(0),philosopher(1).....philosopher(4));   
    }
    
    • 此方案会导致死锁: 所有哲学家同时坐下来,都拿起左边的叉子,都去伸手拿右边的叉子,却都没有拿到

    对上面死锁危险的解决方案:
    1. 再增加5把叉子,
    2. 哲学家学会只使用一把叉子吃面
    3. 增加服务员: 限制每次最多只能4个哲学家坐下来,那么至少有一个哲学家能够拿到2把叉子

    增加服务员方案

    • 一个信号量room表示 : 限制每次哲学家同时坐下的数量
    semaphore fork[5] = {1};
    semaphore room = 4;
    int i;
    void philosopher (int i) {
    	while (true) {
            think();
            wait(room);
            wait(fork[i]);
            wait(fork[(i+1) % 5]);
            eat();
            signal(fork[(i+1) % 5]);
            signal(fork[i]);
            signal(room);
        }
    }
    void main() {
        parbegin(philosopher(0),philosopher(1).....philosopher(4));
    }
    

    基于管程的解决方案

    1. 定义 5个管程的条件变量, 每把叉子对应一个条件变量,用来标识哲学家 等待 的叉子可用情况,

    2. 开一个bool数组记录每把叉子是否可用(true/false)

    3. 管程包含2个过程

      1. get_forks : 表示取哲学家左右的叉子, 如果至少有1把不可以用,那么在条件变量队列中等待,使得其他哲学家进程进入管程
      2. release_forks : 标识2把叉子可用
    4. 信号量方案类似,都是首先拿起左边的叉子,然后拿起右边的叉子

    monitor dining_controller; // 声明管程
    cron ForkReady[5];  //  管程的条件变量
    bool fork[5] = {true}; // 标记叉子是否可用
    
    void get_forks(int pid) { // pid既代表哲学家又代表叉子
        int left = pid;
        int right = (pid + 1) % 5;
        if (!fork[left]) // 左边叉子被使用,则等待条件变量
            cwait(ForkReady[left]);
        fork[left] = false;//左边叉子现在可以归我们用了,再次标记为不能用
        if (!fork[right])
            cwait(ForkReady[right]);
        fork[right] = false;
    }
    
    void release_forks(int pid) {
        int left = pid;
        int right= (pid + 1) % 5;
        if (empty(ForkReady[left])) // 没有哲学家在该队列上等待,则该叉子可以使用
            fork[left] = true;
        else //如果还有等待,增加信号量
            csignal(ForkReady[left]);
        /* 释放右边的叉子 */
        if (empty(ForkReady[right]))
            fork[right] = true;
        else
            csignal(ForkReady[right]);
    }
    
    void philosopher(int i) {
        while (true) {
            think();
            get_forks(i);
            eat();
            release_forks(i);
        }
    }
    void main() {
    	parbegin(philosopher(0),philosopher(1).....philosopher(4));
    }
    
    展开全文
  • 第五章 死锁饥饿;[学习目标] 1.掌握死锁的定义,死锁的条件死锁的处理以及处理死锁的算法银行家算法 2.理解资源分配图 [学习要点] 本章的重点在于掌握死锁的处理方法会用银行家算法计算是否发生死锁;第五章 死锁与...
  • 哲学 哲学家问题的实现以显示死锁和饥饿
  • 1.死锁 1.1死锁原理
  • 死锁和饥饿

    2017-12-25 11:23:00
    转载于:https://www.cnblogs.com/lnlin/p/8108581.html
  • 设计一个程序,能够显示当前各哲学家的状态桌上餐具的使用情况,并能无死锁的推算出下一状态各哲学家的状态桌上餐具的使用情况。即设计一个能安排哲学家正常生活的程序。 3.2 问题描述 可能出现死锁问题,因为...
  • 6.4.2 破坏占有等待条件 另一种破坏占有等待条件的略有不同的方案是要求当一个进程请求资源时先暂时释放其当前占用的所有资源然后再尝试一次获得所需的全部资源 6.4.3 破坏不可抢占条件 破坏关于死锁的第三个...
  • 操作系统:死锁和饥饿

    千次阅读 多人点赞 2019-11-13 18:17:47
    饥饿:指系统不能保证某个进程的等待时间上界,从而使该进程长时间等待,当等待时间给进程推进响应带来明显影响时,称发生了进程饥饿。当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被...
  • 并发处理中需要解决两个问题,死锁和饥饿。处理死锁问题又三种常用方法:预防、检测、避免。
  • 一张图说死锁和饥饿

    2021-07-24 11:04:39
    死锁和饥饿
  • (四)死锁和饥饿

    2020-07-24 21:13:11
    本章介绍并发处理中需要解决的两个问题:死锁和...本章首先讨论死锁的基本原理和饥饿的相关问题:接着分析处理死锁的三种常用方法:**预防、检测避免**:然后考虑用于说明同步和死锁的一个经典问题:哲学家就餐问题。
  • 死锁和饥饿的异同

    千次阅读 2011-09-24 18:28:52
    但是,若对资源的管理、分配使用不当,则会产生死锁或是饥饿。   所谓死锁是指在多道程序系统中,一组进程中的每一个进程都无限期等待被该组进程中的另一个进程所占有且永远不会释放的资源。 饥饿是指系统不能...
  • 死锁与活锁的区别,死锁饥饿的区别 死锁 是指两个或者两个以上的进程(或线程)在执行过程中, 因争夺资源而造成的一种互相等待的现象, 若无外力作用,他们将无法推进下去。 产生死锁的原因 互相争夺共享资源...
  • 并发:死锁饥饿

    2019-07-24 19:27:11
    并发处理中通常需要解决两个问题:死锁饥饿 死锁的原理 可以把死锁定义为一组相互竞争系统资源或进行通信的进程之间的“永久性”阻塞。当一组进程中的每个进程都在等待某个事件,而只有在这组进程中的其他被阻塞...
  • 并发:死锁和饥饿

    2017-08-03 16:47:06
    死锁原理一组相互竞争系统资源或进行通信的进程间的“永久”阻塞。当一组进程中的每个进程都在等待某个事件,...可重用资源的例子包括处理器、I/O、内存外存、设备,以及诸如文件、数据库信号量之类的数据结构。如
  • 死锁饥饿

    千次阅读 2018-05-12 19:52:39
    死锁类型:1.竞争资源2.进程通信3.其他原因死锁的条件:资源独占(mutual exclusion):一个资源在同一个时刻只能被分配给一个进程。不可剥夺(non preemption):资源申请者不能强行地从资源占有者手中夺取资源,即资源...
  • OS-并发:死锁和饥饿

    2020-12-22 15:11:48
    操作系统作业-并发:死锁和饥饿 1. 分别举例说明什么是可重用资源和可消耗资源? 可重用资源包括处理器、I/O通道、内存外设、设备,以及诸如文件,数据库信号量之类的数据结构。诸如此类资源,一次仅供一个...
  • 本章讲述在并发处理中通常需要解决的两个问题:死锁和饥饿 处理死锁的三种常用方法:预防、检测避免 经典问题:哲学家就餐问题 一、死锁原理 可以把死锁定义为一组互相竞争系统资源或进行...
  • 操作系统-4——并发:死锁和饥饿

    千次阅读 2018-06-12 12:49:13
    一、死锁1、死锁原理当一组进程中的每个进程都在等待某个事件(所请求的资源被释放),而只有在这组进程中的其他阻塞进程才能触发该事件,而只有这组进程中的其他阻塞进程才能触发该事件,称这组进程发生死锁死锁...
  • 死锁发生在一个线程需要获取多个资源的时候,这时由于两个线程互相等待对方的资源而被阻塞,死锁是最常见的活跃性问题。这里先分析死锁的情形:假设当前情况是线程A已经获取资源R1,线程B已经获取资源R2,之后线程A...
  • 1、什么是死锁 死锁,是指两个或两个以上的进程(或线程)执行过程中,因争夺资源而造成的一种互相等待的现象,若无外力作用干预,他们都死等下去,也都将无法往下推进。 产生死锁的必要条件: 1、互斥条件:所谓...
  • 1. 死锁原理 死锁是一组进程,在互相竞争资源或者互相通信时,发生的永久性阻塞。每个进程都占用某个资源,并且在等待另一个资源。 死锁的条件: 互斥:一次只有一个进程能够占有一个资源。 占有且等待:在等待...
  • 多线程饥饿现象,饥饿死锁区别

    千次阅读 多人点赞 2020-07-04 17:41:17
    定义 让有限多的工作线程来轮流异步处理无限多的工作任务,也可以将其归类为...注意:不同的类型应该使用不同的线程池,这样能避免饥饿,提升效率。 例如:饭店切菜就是切菜的员工,服务员就是服务员。 饥饿现象 ...
  • 操作系统实验源代码(创建进程、信号量、死锁和饥饿
  • 一、定义:1、死锁:是指两个或两个以上的进程(或线程)在执行过程中,因争夺资源而造成的一种互相等待的现象,若无外力作用,它们都将无法推进下去。...(2)请求保持条件:线程T1至少已经保持了...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,942
精华内容 6,776
关键字:

死锁和饥饿