的需求向量,由矩阵Need的第i行构成。 上述三个矩阵间存在关系 Need (i, j)=Max(i, j)-Allocation (i, j) 银行家算法如下 Request是进程Pi的请求向量。 Request(j)表示进程Pi请求分配R类资源k个。 当Pi发出资源请求后,系统按下述步骤进行检查z 1)如果 Request<=Need,则转向步骤(2);否则,认为出错,因为它所需要的资源数已超过 它所宣布的最大值。 (2)如果 Request<= Available,则转向步骤(3);否则,表示系统中尚无足够的资源满足Pi 的申请,Pi必须等待。 (3)系统试探把资源分配给进程Pi,并修改下面数据结构中的数值: Available =Available-Requesti Allocation=Allocationi+Request Needi=Needi-Requesti: (4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将 资源分配给进程Pi,以完成本次分配:否则,将试探分配作废,恢复原来的资源分配状态,让进 程Pi等待 系统所执行的安全性算法描述如下 (1)设置两个向量 Work它表示系统可提供给进程继续运行的各类资源数目,它含有m个元素,开始执行安 全性算法时,Work= Availabh Finish它表示系统是否有足够的资源分配给进程,使之运行完成,开始时, Finish(i)= false:当有足够资源分配给进程Pi时,令 Finish(i)=true. (2)从进程集合中找到一个能满足下述条件的进程 Finish (i)=false Needi<=Work 如找到则执行步骤(3):否则,执行步骤(4) (3)当进程Pi获得资源后,可顺利执行直到完成,并释放出分配给它的资源,故应执行 Work =work+Allocation Finish (i)=true (4)若所有进程的 Finish(i)都为true,则表示系统处于安全状态:否则,系统处于不安全 状态 5.死锁的检测和解除 (1)死锁的检测 前面介绍的死锁预防和避免算法都是在系统为进程分配资源时施加限制条件或进行检测 若系统为进程分配资源时不采取任何措施,则应该提供检测和解除死锁的手段 发现死锁的原理是考察某一时刻系统状态是否合理,即是否存在一组可以实现的系统状 态,能使所有进程都得到它们所申请的资源而运行结束。检测死锁算法的基本思想是: 获得某时刻t系统中各类可利用资源的数目向量w(t〉,对于系统中的一组进程P1 P2、…、pn},找出那些对各类资源请求数目均小于系统现在所拥有的各类资源数目的进程 我们可以认为这样的进程可以获得它们所需要的全部资源并运行结束,当它们运行结束后释 放所占有的全部资源,从而使可用资源数目增加,这样的进程加入到可运行结束的进程序列L 中,然后对剩下的进程再作上述考察。如果一组进程{P1、P2、…、Pn}中有几个进程不在序列
的需求向量,由矩阵 Need 的第 i 行构成。 上述三个矩阵间存在关系: Need (i,j)=Max(i,j)-Allocation (i,j) 银行家算法如下: Requesti 是进程 Pi 的请求向量。Requesti(j)=k 表示进程 Pi 请求分配 Rj 类资源 k 个。 当 Pi 发出资源请求后,系统按下述步骤进行检查 z （1）如果 Requesti<=Need,则转向步骤(2);否则,认为出错,因为它所需要的资源数已超过 它所宣布的最大值。 (2)如果 Requesti<=Available,则转向步骤(3〉;否则,表示系统中尚无足够的资源满足 Pi 的申请,Pi 必须等待。 (3)系统试探把资源分配给进程 Pi,并修改下面数据结构中的数值: Available =Available-Requesti; Allocationi=Allocationi+Requesti; Needi=Needi-Requesti; (4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将 资源分配给进程 Pi,以完成本次分配:否则,将试探分配作废,恢复原来的资源分配状态,让进 程 Pi 等待。 系统所执行的安全性算法描述如下: (1)设置两个向量。 Work它表示系统可提供给进程继续运行的各类资源数目,它含有m个元素,开始执行安 全性算法时,Work =Availabh。 Finish 它表示系统是否有足够的资源分配给进程,使之运行完成,开始时, Finish (i)=false:当有足够资源分配给进程 Pi 时,令 Finish (i)=true. (2)从进程集合中找到一个能满足下述条件的进程。 Finish (i〉==false: Needi<=Work: 如找到则执行步骤(3〉:否则,执行步骤(4)。 (3)当进程 Pi 获得资源后,可顺利执行直到完成,并释放出分配给它的资源,故应执行 Work =work+Allocationi: Finish (i〉=true: Goto step2: (4)若所有进程的 Finish(i)都为 true,则表示系统处于安全状态:否则,系统处于不安全 状态。 5．死锁的检测和解除 （1）死锁的检测 前面介绍的死锁预防和避免算法都是在系统为进程分配资源时施加限制条件或进行检测， 若系统为进程分配资源时不采取任何措施，则应该提供检测和解除死锁的手段。 发现死锁的原理是考察某一时刻系统状态是否合理,即是否存在一组可以实现的系统状 态,能使所有进程都得到它们所申请的资源而运行结束。检测死锁算法的基本思想是: 获得某时刻 t 系统中各类可利用资源的数目向量 w(t〉,对于系统中的一组进程{Pl、 P2、…、pn},找出那些对各类资源请求数目均小于系统现在所拥有的各类资源数目的进程。 我们可以认为这样的进程可以获得它们所需要的全部资源并运行结束,当它们运行结束后释 放所占有的全部资源,从而使可用资源数目增加,这样的进程加入到可运行结束的进程序列 L 中,然后对剩下的进程再作上述考察。如果一组进程{P1、P2、…、Pn}中有几个进程不在序列
L中,那么它们会发生死锁。 检测死锁可以在每次分配后进行。但是,用于检测死锁的算法比较复杂,所花的检测时间 长,系统开销大,因此,也可以选取比较长的时间间隔来执行。 (2)死锁的解除 旦系统成为死锁状态,就应将系统从死锁状态解脱出来,即解除死锁,使系统恢复到正常 状态。解除死锁的常用方法有两种 ①资源剥夺法:当发现死锁后,从其他进程剥夺足够数量的资源给死锁进程,以解除死锁 状态 ②撤消进程法:此方法是采用强制手段从系统中撤消一个或一部分死锁进程,并剥夺这 些进程的资源供其他死锁进程使用 最简单的撤消进程方法是撤消全部死锁进程,使系统恢复到正常状态。但这种做法付出的 代价太大。另一方法是按照某种顺序逐个撤消死锁进程,直到有足够的资源供其他未被撤消的 进程使用,消除死锁状态为止 4.2重点难点学习提示 本章的学习目的主要是使学生理解和掌握处理机调度和死锁的基本概念,为此应对以下 几个重点、难点问题作认真而深入的学习 1.高优先权优先调度和基于时间片的轮转调度算法 高优先权优先调度和基于时间片的轮转调度算法是目前被广泛使用的两种进程调度算法, 读者应对它们有较深入的理解和掌握 (1)什么是高优先权优先调度算法:这是指将处理机分配给就绪队列中优先权最高的进程 的调度算法。在学习时应了解系统是根据哪些因素来确定一个进程的优先权的,在采用动态优 先权的系统中又将根据哪些因素来调整运行进程的优先权 (2)什么是高响应比优先调度算法:这是指以响应比作为进程的优先权的进程调度算法 在学习时应了解高响应比优先调度算法是为了解决什么问题而引入的,它有何优缺点 (3)什么是时间片轮转算法:这是指让就绪进程以FCFS的方式按时间片轮流使用CPU的 调度方式。在学习时应了解时间片的概念是为了解决什么问题而引入的,它是如何解决上述问 题的。 (4)什么是多级反馈队列调度算法:该算法设置了多个就绪队列,并给每个队列赋予不同 的优先权和时间片。在学习时应了解该算法是如何对各个就绪队列中的进程进行进程调度的, 为什么它能较好地满足各种类型用户的需要。 2.常用的几种实时调度算法 根据确定实时任务优先权方法的不同,可形成以下两种常用的实时调度算法 (1)最早截止时间优先(EDF)算法:在学习时应了解EDF算法是根据什么来确定任务的优 先权的,或者说它是如何保证满足各任务对截止时间的要求的 (2)最低松弛度优先(LLF)算法:在学习时应了解LLF算法是根据什么来确定任务的优先 级的,在什么情况下,一个进程应抢占被另一进程占用的CPU 3.多处理机环境下的进程(线程)调度方式 多处理机系统己广为流行多年,目前,己出现了多种多处理机环境下的进程(线程)调度方 式,故读者应对下述几种比较有代表性的调度方式有较好的了解 (1)自调度方式:自调度方式是多处理机环境下最简单的一种调度方式,在学习时应了解 它是如何为就绪进程(线程)分配处理机的,该方式主要有什么优点,以及它存在哪些缺点 (2)成组调度方式:它将一组相互合作的进程或隶属于同一个进程的一组线程分配到一组 处理器上去同时执行,读者应了解为什么成组调度方式的性能会优于自调度方式
L 中,那么它们会发生死锁。 检测死锁可以在每次分配后进行。但是,用于检测死锁的算法比较复杂,所花的检测时间 长,系统开销大,因此,也可以选取比较长的时间间隔来执行。 （2）死锁的解除 一旦系统成为死锁状态,就应将系统从死锁状态解脱出来,即解除死锁,使系统恢复到正常 状态。解除死锁的常用方法有两种: ①资源剥夺法：当发现死锁后,从其他进程剥夺足够数量的资源给死锁进程,以解除死锁 状态。 ② 撤消进程法：此方法是采用强制手段从系统中撤消一个或一部分死锁进程，并剥夺这 些进程的资源供其他死锁进程使用。 最简单的撤消进程方法是撤消全部死锁进程,使系统恢复到正常状态。但这种做法付出的 代价太大。另一方法是按照某种顺序逐个撤消死锁进程,直到有足够的资源供其他未被撤消的 进程使用,消除死锁状态为止。 4.2 重点难点学习提示 本章的学习目的主要是使学生理解和掌握处理机调度和死锁的基本概念,为此应对以下 几个重点、难点问题作认真而深入的学习。 1.高优先权优先调度和基于时间片的轮转调度算法 高优先权优先调度和基于时间片的轮转调度算法是目前被广泛使用的两种进程调度算法, 读者应对它们有较深入的理解和掌握。 (1)什么是高优先权优先调度算法：这是指将处理机分配给就绪队列中优先权最高的进程 的调度算法。在学习时应了解系统是根据哪些因素来确定一个进程的优先权的,在采用动态优 先权的系统中又将根据哪些因素来调整运行进程的优先权。 (2)什么是高响应比优先调度算法：这是指以响应比作为进程的优先权的进程调度算法。 在学习时应了解高响应比优先调度算法是为了解决什么问题而引入的,它有何优缺点。 (3)什么是时间片轮转算法：这是指让就绪进程以 FCFS 的方式按时间片轮流使用 CPU 的 调度方式。在学习时应了解时间片的概念是为了解决什么问题而引入的,它是如何解决上述问 题的。 (4)什么是多级反馈队列调度算法：该算法设置了多个就绪队列,并给每个队列赋予不同 的优先权和时间片。在学习时应了解该算法是如何对各个就绪队列中的进程进行进程调度的, 为什么它能较好地满足各种类型用户的需要。 2.常用的几种实时调度算法 根据确定实时任务优先权方法的不同,可形成以下两种常用的实时调度算法: (1)最早截止时间优先(EDF)算法：在学习时应了解 EDF 算法是根据什么来确定任务的优 先权的,或者说它是如何保证满足各任务对截止时间的要求的。 (2)最低松弛度优先(LLF)算法：在学习时应了解 LLF 算法是根据什么来确定任务的优先 级的,在什么情况下,一个进程应抢占被另一进程占用的 CPU。 3.多处理机环境下的进程(线程)调度方式 多处理机系统己广为流行多年,目前,己出现了多种多处理机环境下的进程(线程)调度方 式,故读者应对下述几种比较有代表性的调度方式有较好的了解： (1)自调度方式：自调度方式是多处理机环境下最简单的一种调度方式,在学习时应了解 它是如何为就绪进程(线程)分配处理机的,该方式主要有什么优点,以及它存在哪些缺点 (2)成组调度方式：它将一组相互合作的进程或隶属于同一个进程的一组线程分配到一组 处理器上去同时执行,读者应了解为什么成组调度方式的性能会优于自调度方式
(3)专用处理器分配方式:这种方式有可能造成部分处理机的严重浪费,读者必须了解在 并行程度相当高的多处理器环境下,为什么这种浪费是值得的,它换来了什么好处 4.死锁的基本概念 死锁是指多个进程竞争资源而形成的一种僵局,若无外力的作用,这些进程将无法再向前 推进。可见,死锁状态不同于一般的阻塞状态。在学习时,读者应对下述两个问题有较深刻的 理解和掌握 (1)产生死锁的原因是什么:产生死锁的根本原因是竞争资源和进程推进顺序非法,在学 习时应了解这两个根本原因与0S的两个基本特征并发和其事之间存在着什么样的联系。 (2)产生死锁的必要条件有哪些。产生死锁的必要条件奋互斥条件、请求与保持条件、不 剥夺条件和环路等待条件,在学习时请思考如果其中的一个条件不满足,为什么不会产生死 5.预防死锁的方法 预防死锁是通过摒弃死锁产生的必要条件来达到防止死锁产生的目的的在学习时应了 解下述几个方面的内容 (1)摒弃″互斥″条件:应了解"互斥"条件为什么很难被摒弃,对某些(极少数的)互斥共享 的设备(如打印机)又可通过什么技术来摒弃互斥条件 2)摒弃″请求和保持″条件:读者应了解可通过哪些方法来摒弃″请求和保持”条件它们 对进程的运行和系统资源的利用率造成了什么样的影响。 (3)摒弃″不剥夺″条件:读者应了解可通过哪些方法来摒弃”不剥夺”条件,这些法有什么 缺点 (4)摒弃″环路等待″条件:读者应了解可通过哪些方法来摒弃″环路等待”条件,它对系统 和用户带来了哪些不便,对资源的利用率又有什么影响 (5)各种方法的比较:读者应从实现的简单性和资源的利用率等方面比较上述几种预防 死锁的方法,以了解哪种方法实现最简便,哪种方法可使资源利用率受损最少 6.利用银行家算法避免死锁 银行家算法是一种最有代表性的避免死锁的算法。在学习时应对下述几个方面的内容国 有较好的理解: (1)避免死锁的实质在于如何防止系统进入不安全状态二在学习时,读者必须清晰地认识 到,为什么系统处于安全状态便可避免进入死锁状态,而处于不安全状态则极有可能导致死锁 状态的产生。 (2)在银行家算法中用到了可利用资源向量 Available、最大需求矩阵Max、分配矩阵 Allocation、需求矩阵Ned等数据结构,而在安全性检査算法中则还要用到工作向量Work 和完成向量 Finish等数据结构,读者应对它们的物理意义和相互关系有较好的理解。 (3)安全性检査算法的目的是寻找一个安全序列。在学习时应了解满足什么条件的进程 Pi,其对资源的最大需求可以得到满足,故可顺利完成:当Pi完成后,应如何修改工作向量 Work和完成向量 Finish (4)在利用银行家算法避免死锁时应了解,系统什么时候可以为提出资源请求的进程试行 分配资源,什么时候才可以正式将资源分配给进程。 4.3典型问题分析和解答 1.为什么说多级反馈队列调度算法能较好地满足各方面用户的需要? 答:对终端型作业用户而言,他们提交的作业大多属于交互型作业,作业通常较小,系统只 要能使这些作业在一个队列所规定的时间片内完成,便可使他们都感到满意。对短批处理作业 用户而言,开始时他们的作业像终端型作业一样,如果仅在第一个队列中执行一个时间片即可
(3)专用处理器分配方式：这种方式有可能造成部分处理机的严重浪费,读者必须了解在 并行程度相当高的多处理器环境下,为什么这种浪费是值得的,它换来了什么好处。 4.死锁的基本概念 死锁是指多个进程竞争资源而形成的一种僵局,若无外力的作用,这些进程将无法再向前 推进。可见,死锁状态不同于一般的阻塞状态。在学习时,读者应对下述两个问题有较深刻的 理解和掌握: (1)产生死锁的原因是什么：产生死锁的根本原因是竞争资源和进程推进顺序非法,在学 习时应了解这两个根本原因与 OS 的两个基本特征并发和其事之间存在着什么样的联系。 (2)产生死锁的必要条件有哪些。产生死锁的必要条件奋互斥条件、请求与保持条件、不 剥夺条件和环路等待条件,在学习时请思考如果其中的一个条件不满足,为什么不会产生死 锁。 5.预防死锁的方法 预防死锁是通过摒弃死锁产生的必要条件来达到防止死锁产生的目的的在学习时应了 解下述几个方面的内容: (1)摒弃"互斥"条件：应了解"互斥"条件为什么很难被摒弃,对某些(极少数的)互斥共享 的设备(如打印机)又可通过什么技术来摒弃互斥条件。 （2）摒弃"请求和保持"条件：读者应了解可通过哪些方法来摒弃"请求和保持"条件它们 对进程的运行和系统资源的利用率造成了什么样的影响。 (3)摒弃"不剥夺"条件：读者应了解可通过哪些方法来摒弃"不剥夺"条件,这些法有什么 缺点。 (4)摒弃"环路等待"条件：读者应了解可通过哪些方法来摒弃"环路等待"条件,它对系统 和用户带来了哪些不便,对资源的利用率又有什么影响。 （5）各种方法的比较：读者应从实现的简单性和资源的利用率等方面比较上述几种预防 死锁的方法,以了解哪种方法实现最简便,哪种方法可使资源利用率受损最少。 6.利用银行家算法避免死锁 银行家算法是一种最有代表性的避免死锁的算法。在学习时应对下述几个方面的内容国 有较好的理解： (1)避免死锁的实质在于如何防止系统进入不安全状态二在学习时,读者必须清晰地认识 到,为什么系统处于安全状态便可避免进入死锁状态,而处于不安全状态则极有可能导致死锁 状态的产生。 (2)在银行家算法中用到了可利用资源向量 Available、最大需求矩阵 Max、分配矩阵 Allocation、需求矩阵 Need 等数据结构，而在安全性检查算法中则还要用到工作向量 Work 和完成向量 Finish 等数据结构,读者应对它们的物理意义和相互关系有较好的理解。 (3)安全性检查算法的目的是寻找一个安全序列。在学习时应了解满足什么条件的进程 Pi,其对资源的最大需求可以得到满足,故可顺利完成:当 Pi 完成后,应如何修改工作向量 Work 和完成向量 Finish。 (4)在利用银行家算法避免死锁时应了解,系统什么时候可以为提出资源请求的进程试行 分配资源,什么时候才可以正式将资源分配给进程。 4.3 典型问题分析和解答 1.为什么说多级反馈队列调度算法能较好地满足各方面用户的需要? 答:对终端型作业用户而言,他们提交的作业大多属于交互型作业,作业通常较小,系统只 要能使这些作业在一个队列所规定的时间片内完成,便可使他们都感到满意。对短批处理作业 用户而言,开始时他们的作业像终端型作业一样,如果仅在第一个队列中执行一个时间片即可
完成,便可获得与终端型作业一样的响应时间:对于稍长的作业,通常也只需在第二队列和第 三队列各执行一个时间片即可完成,其周转时间仍然很短。对长批处理作业用户而言,他们的 作业将依次在第1,2,…,n个队列中运行,然后再按轮转方式邑行,用户不必担心其作业长期 得不到处理;而且每往下降一个队列,其得到的时间片将随着增加,故可进一步缩短长作业 的等待时间。 2.假设一个系统中有5个进程,它们的到达 表4.1进程到达和需服务时间 时间和服务时间如表4.1所示,忽略I/0以及 其他开销时间,若分别按先来先服务(FCFS)、非抢 匚进程『到达时间服务时间 占及抢占的短进程优先(SPF)、高响应比优先 HRN)、时间片轮转(RR,时间片=1)、多级反馈 队列(FB,第i级队列的时间片=2^i-1)以及立即 枪占的多级反馈队列(FB,第i级队列的时间片=2^i-1) BCDE 2468 3645 调度算法进行CPU调度,请给出各进程的完成时间、 周转时间、带权周转时间、平均周转时间和平均带 权周转时间。 分析:进程调度的关键是理解和掌握调度所采用的算法。FCFS算法选择最早进入就绪队 列的进程投入执行;SPF算法选择估计运行时间最短的进程投入执行,采用抢占方式时,若新 就绪的进程运行时间比正在执行的进程的剩余运行时间短,则运行时间+等待时间新进程将抢 占CPU;HRRN算法选择响应比(响应比=最高的运行时间+等待时间/运行时间)最高的进程投入 执行;R算法中,就绪进程按FIFO方式排队,CPU总是分配给队首的进程,并只能执行一个时间 片;FB算法将就绪进程排成多个不同优先权及时间片的队列,新就绪进程总是按FIFO方式先 进入优先权最高的队列,CPU也总是分配给较高优先权队列上的队首进程,若执行一个时间片 仍未完成,则转入下一级队列的末尾,最后一级队列则采用时间片轮转方式进行调度 答:各进程的完成时间、周转时间和带权周转时间(如表4.2所示) 表4.2进程的完成时间和周转时间 进程 完成时间 131820 周转时间 B97 FCFS 带权周转时间1.001.172.256.006.002.56 完成时间 15|11|11 SPF(非抢占)周转时间 7.6 带权周转时间.001.172.7511.51.511.84 完成时间31581010 SPF(抢占)周转时间3134227.2 带权周转时间1.002.161.001.001.001.59 完成时间 131515 HRRN 周转时间 带权周转时间1.001.172.253.53.52.14 完成时间 17 17 15 RR(g=1) 周转时间 4 1313|14|710.8 带权周转时间1.333.253.252.83.52.71 完成时间 10.4 FB(q=2-1)周转时间 2.56 带权周转时间12.503.502.83.00
完成,便可获得与终端型作业一样的响应时间:对于稍长的作业,通常也只需在第二队列和第 三队列各执行一个时间片即可完成,其周转时间仍然很短。对长批处理作业用户而言,他们的 作业将依次在第 1,2,…,n 个队列中运行,然后再按轮转方式邑行,用户不必担心其作业长期 得不到处理； 而且每往下降一个队列，其得到的时间片将随着增加,故可进一步缩短长作业 的等待时间。 2.假设一个系统中有 5 个进程,它们的到达 表 4.1 进程到达和需服务时间 时间和服务时间如表 4.1 所示,忽略 I/0 以及 其他开销时间,若分别按先来先服务(FCFS)、非抢 占及抢占的短进程优先（SPF）、高响应比优先 (HRRN)、时间片轮转(RR,时间片=1)、多级反馈 队列(FB,第 i 级队列的时间片=2^i-1)以及立即 枪占的多级反馈队列(FB,第 i 级队列的时间片=2^i-1) 调度算法进行 CPU 调度,请给出各进程的完成时间、 周转时间、带权周转时间、平均周转时间和平均带 权周转时间。 分析：进程调度的关键是理解和掌握调度所采用的算法。FCFS 算法选择最早进入就绪队 列的进程投入执行;SPF 算法选择估计运行时间最短的进程投入执行,采用抢占方式时,若新 就绪的进程运行时间比正在执行的进程的剩余运行时间短,则运行时间+等待时间新进程将抢 占 CPU;HRRN 算法选择响应比(响应比=最高的运行时间+等待时间/运行时间)最高的进程投入 执行;RR算法中,就绪进程按FIFO方式排队,CPU总是分配给队首的进程,并只能执行一个时间 片;FB 算法将就绪进程排成多个不同优先权及时间片的队列,新就绪进程总是按 FIFO 方式先 进入优先权最高的队列,CPU 也总是分配给较高优先权队列上的队首进程,若执行一个时间片 仍未完成,则转入下一级队列的末尾,最后一级队列则采用时间片轮转方式进行调度。 答：各进程的完成时间、周转时间和带权周转时间(如表 4.2 所示) 表 4.2 进程的完成时间和周转时间 进程 A B C D E 平 均 FCFS 完成时间 周转时间 带权周转时间 3 3 1.00 9 7 1.17 13 9 2.25 18 12 6.00 20 12 6.00 8.6 2.56 SPF(非抢占) 完成时间 周转时间 带权周转时间 3 3 1.00 9 7 1.17 15 11 2.75 11 3 1.5 11 3 1.5 7.6 1.84 SPF(抢占) 完成时间 周转时间 带权周转时间 3 3 1.00 15 13 2.16 8 4 1.00 10 2 1.00 10 2 1.00 7.2 1.59 HRRN 完成时间 周转时间 带权周转时间 3 3 1.00 9 7 1.17 13 9 2.25 15 7 3.5 15 7 3.5 8 2.14 RR(q=1) 完成时间 周转时间 带权周转时间 4 4 1.33 17 13 3．25 17 13 3.25 20 14 2.8 15 7 3.5 10.8 2.71 FB(q=2^i-1) 完成时间 周转时间 带权周转时间 3 3 1 17 15 2.50 18 14 3.50 20 14 2.8 14 6 3.00 10.4 2.56 进程 到达时间 服务时间 A 0 3 B 2 6 C 4 4 D 6 5 E 8 2
F(q=i-1)完成时间 16 (立即抢占周转时间 14810.6 带权周转时 2.84.002.87 3.何谓自调度方式?其主要优缺点是什么? 答:自调度方式是多处理器系统中的一种处理机调度方式,它在系统中设置一个公用的进 程(或线程)队列,所有的处理器在空闲时,都可自己到该队列中取一进程(或线程)来执行。在 自调度方式中,可采用单处理机环境下的进程调度算法(如先来先服务、最高优先权优先、抢 占式最高优先权优先调度算法等)来进行进程调度 自调度算法的主要优点是:①系统中公用就绪队列的组织方式以及具体的进程(或线程) 调度算法都可沿用单处理机中的方式,因而容易实现:②不会发生处理器忙闲不均的现象,因 而有利于提高处理器的利用率 而它的缺点主要是:①公用就绪队列很容易成为整个系统的瓶颈:②一个线程在整个生命 期中,可能要多次更换处理器,从而使处理器上的高速缓存使用率降低,并进一步降低整个系 统的性能:③相互合作型的线程很难冋时获得处理器而同时运行,这将会增加合作线程之间的 阻塞频率,从而提髙线程切换的频率,增加系统的开销并降低进程的运行速度 4.何谓成组调度方式?其主要优点是什么? 答:成组调度方式是多处理器系统中的一种处理机调度方式,它将一组相互合作的进程或 个进程的一组线程分配到一组处理器上去同时执行 成组调度的主要优点是:如果一组相互合作的进程或线程能并行执行,则可有效地减少同步阻 塞的现象,从而可以减少进程和线程的切换次数,使系统性能得到改善:另外,由于每次调度都 可以解决一组进程或线程的处理器分配问题,因而可显著地减少调度频率,降低调度开销。 5.产生死锁的四个必要条件是什么?试以过河问题中产生的死锁为例加以说明 答:产生死锁的必要条件如下: (1)互斥:系统中至少有一个(类)资源必须用非共享方式使用。过河问题中,每一块垫脚石 任一时刻仅能为一个人占用 (2)占用并等待∷一个进程至少占有一个资源并正等待得到其他资源,而这些资源已被其他 进程所占用.过河问题中,相遇的两个人各自踏在一块垫脚石上,并同时等待踏上对方占用的 那一块 (3)非抢占:资源不可能被抢占.在过河问题中,由于垫脚石不能强行移动,"非抢占"条件满 足。 (4)循环等待:存在循环等待情况。从东岸来的人等着从西岸来的人,而从西岸来的人则等 着从东岸来的人 于是,大家都不能过河,每人都等待对方从其占用的垫脚石上移开脚,具备以上四个条件 死锁发生 6.在哲学家就餐问题中,如果将先拿起左边的筷子的哲学家称为左撇子,而将先拿起右边 的筷子的哲学家称为右撇子,请说明在同时存在左撇子和右撤子的情况下,任何就座安排都不 会产空死锁。 分析:这类题目的关键是必须证明产生死锁的4个必要条件的其中一个不可能望成立。在 本题中,互斥条件、请求与保持条件、不剥夺条件是肯定成立的,因此必须证明"循环等待"条 件不成立 答:对本题,死锁产生的必要条件-一"循环等待"不可能成立。如果存在所有左边的哲学家 等待右边的哲学家放下筷子的循环等待链,则每个哲学家肯定已获得左边的筷子,但还没得到 右边的筷子,这与存在右撇子的情况不符:同样,也不可能存在相反的循环等待链。而且,系统
FB(q=^i-1) (立即抢占 完成时间 周转时间 带权周转时间 4 4 1.33 18 16 2.67 15 11 2.75 20 14 2.8 16 8 4.00 10.6 2.87 3.何谓自调度方式?其主要优缺点是什么? 答:自调度方式是多处理器系统中的一种处理机调度方式,它在系统中设置一个公用的进 程(或线程)队列,所有的处理器在空闲时,都可自己到该队列中取一进程(或线程)来执行。在 自调度方式中,可采用单处理机环境下的进程调度算法(如先来先服务、最高优先权优先、抢 占式最高优先权优先调度算法等)来进行进程调度。 自调度算法的主要优点是:①系统中公用就绪队列的组织方式以及具体的进程(或线程) 调度算法都可沿用单处理机中的方式,因而容易实现:②不会发生处理器忙闲不均的现象,因 而有利于提高处理器的利用率。 而它的缺点主要是:①公用就绪队列很容易成为整个系统的瓶颈:②一个线程在整个生命 期中,可能要多次更换处理器,从而使处理器上的高速缓存使用率降低,并进一步降低整个系 统的性能:③相互合作型的线程很难同时获得处理器而同时运行,这将会增加合作线程之间的 阻塞频率,从而提高线程切换的频率,增加系统的开销并降低进程的运行速度。 4.何谓成组调度方式?其主要优点是什么? 答:成组调度方式是多处理器系统中的一种处理机调度方式,它将一组相互合作的进程或 一个进程的一组线程分配到一组处理器上去同时执行。 成组调度的主要优点是:如果一组相互合作的进程或线程能并行执行,则可有效地减少同步阻 塞的现象,从而可以减少进程和线程的切换次数,使系统性能得到改善；另外,由于每次调度都 可以解决一组进程或线程的处理器分配问题,因而可显著地减少调度频率,降低调度开销。 5. 产生死锁的四个必要条件是什么?试以过河问题中产生的死锁为例加以说明。 答：产生死锁的必要条件如下： (1)互斥:系统中至少有一个(类)资源必须用非共享方式使用。过河问题中,每一块垫脚石 任一时刻仅能为一个人占用。 (2)占用并等待:一个进程至少占有一个资源并正等待得到其他资源,而这些资源已被其他 进程所占用.过河问题中,相遇的两个人各自踏在一块垫脚石上,并同时等待踏上对方占用的 那一块。 (3)非抢占:资源不可能被抢占.在过河问题中,由于垫脚石不能强行移动,"非抢占"条件满 足。 (4)循环等待:存在循环等待情况。从东岸来的人等着从西岸来的人，而从西岸来的人则等 着从东岸来的人。 于是,大家都不能过河,每人都等待对方从其占用的垫脚石上移开脚,具备以上四个条件, 死锁发生. 6.在哲学家就餐问题中,如果将先拿起左边的筷子的哲学家称为左撇子,而将先拿起右边 的筷子的哲学家称为右撇子,请说明在同时存在左撇子和右撇子的情况下,任何就座安排都不 会产空死锁。 分析：这类题目的关键是必须证明产生死锁的 4 个必要条件的其中一个不可能望成立。在 本题中,互斥条件、请求与保持条件、不剥夺条件是肯定成立的,因此必须证明"循环等待"条 件不成立。 答:对本题,死锁产生的必要条件-一"循环等待"不可能成立。如果存在所有左边的哲学家 等待右边的哲学家放下筷子的循环等待链,则每个哲学家肯定已获得左边的筷子,但还没得到 右边的筷子,这与存在右撇子的情况不符:同样,也不可能存在相反的循环等待链。而且,系统