发布时间 : 星期六 文章操作系统总复习更新完毕开始阅读
死锁避免的基本思想是:对进程所发出的每一个申请资源命令加以动态地检查,并根据检查结果决定是否进行资源分配.就是说,在资源分配过程中若预测有发生死锁的可能性,则加以避免.这种方法的关键是确定资源分配的安全性. 5什么是死锁的安全序列?何谓系统是安全的？
答：进程的安全序列{P1,P2,?,PN}是这样组成的：若对于每个进程Pi（1<=I<=n），它需要的附加资源可以被系统中当前可用资源加上所有进程Pj（j “系统是安全的”是指系统中的所有进程能够按照某种次序分配资源，并且依次运行完毕。即系统中的进程处于安全序列中。 6资源按序分配法为什么能够预防死锁？ 证明：采用反证法来证明。 若存在循环等待，设在环路上的一组进程为{P0,P1,P2,?,Pn}，这里Pi等待进程Pi+1占有资源Ri（下角标取模运算，从而，Pn等待p0占有的资源）。由于Pi+1占有资源Ri,又申请资源Ri+1,从而一定存在F(i) F(R0) 显然，这是不可能的，因而，上述假设不成立，表明不会出现循环等待条件。 7死锁和“饥饿”之间的主要差别是什么? 答：死锁：多个并发进程相互等待对方占用的资源而产生的错误现象。 饿死：在系统中，由于系统采用的资源分配算法不当，虽然每个资源占有者都在有限时间内释放它所占的资源，但仍然使一些进程永远得不到资源的一种错误现象。 综合题 1设系统中有三种类型的资源（A,B,C）和五个进程（P1,P2,P3,P4,P5）,A资源的数量为17， B资源的数量为5，C资源的数量为20。在T0时刻系统状态如表3-9所试。系统采用银行家算法来避免死锁。 ①T0时刻是否为安全状态？若试，请给出安全序列。 ②在T0时刻，若进程P2请求资源（0，3，4），能否实现资源分配？为什么？ ③在②的基础上，若进程P4请求资源（2，0，1），能否实现资源分配？为什么? ④在③的基础上，若进程P1请求资源（0，2，0），能否实现资源分配？为什么? 表3-9 T0时刻系统状态 进程 最大资源需求量 已分配资源数量 系统剩余资源数量 A B C A B C A B C P1 5 5 9 2 1 2 2 3 3 P2 5 3 6 4 0 2 P3 4 0 11 4 0 5 P4 4 2 5 2 0 4 P5 4 2 4 3 1 4 解： ①T0时刻是安全状态，因为存在一个安全序列{P4,P5,P1,P2,P3} (2’) ②不能实现资源分配，因为所剩余的资源数量不够。 (2’) ③可以分配。当分配完成后，系统剩余的资源向量为（0，3，2），这时，仍可找到一个安全序列{P4,P5,P1,P2,P3} (3’) ④不能分配。如果分配的话，则系统剩余的资源向量为（0，1，2），这时无法找到一个安全序列。(3’) 2在银行家算法中，系统有5个进程和3个资源。若出现以下资源分配情况： 进程 资源最大请求 已分配资源 p0 7, 5, 3 0, 1, 0 p1 3, 2, 2 2, 1, 0 p2 9, 0, 2 3, 0, 2 p3 2, 2, 2 2, 1, 1 p4 4, 3, 3 0, 0, 2 系统剩余资源数量为(3,2,2)。 1） 该状态是否安全(给出详细的检查过程)? 2） 如果进程依次有如下资源请求 p1:资源请求Request(1,0,2)? p4:资源请求Request(3,3,0)? p0:资源请求Request(0,1,0)? 则系统如何进行资源分配，才能避免死锁？ 解: 1)该系统状态是否安全,主要看能否找到一个进程完成序列.若能找到,系统只要按照这个序列为进程分配资源,所有进程就都可顺利完成;若找不到,系统状态就是不安全的.为此,可先求出进程的剩余请求矩阵. 进程 资源最大需求 已分配资源 剩余资源请求 P0 7, 5, 3 0, 1, 0 7, 4, 3 P1 3, 2, 2 2, 1, 0 1, 1, 2 P2 9, 0, 2 3, 0, 2 6, 0, 0 P3 2, 2, 2 2, 1, 1 0, 1, 1 P4 4, 3, 3 0, 0, 2 4, 3, 1 系统剩余资源向量A=(3,2,2)，在进程剩余资源请求矩阵中找，是否有一行，其值都小于或等于A.若有，选进程P1，满足它的全部资源请求，它在有限时间内能释放全部资源，并标记它为完成使系统剩余资源向量A=(5,3,2).之后再重复上述过程，从而找到了一个进城完成序列为：P1,P3,P4,P2,P0 (2’)。由此可见，系统状态是安全的(2’)。 2）p1:资源请求Request(1,0,2)时，由1）可知，可以立即满足它，使得A=(2,2,0),P1的分配向量为(3,1,2)，其剩余向量变为(0,1,0). (2’) p4:资源请求Request(3,3,0)时，由于系统剩余资源向量A=(2,2,0)，显然不能满足它的请求，因为系统剩余资源向量A小于P4的请求 (2’) p0:资源请求Request(0,1,0)时，由于系统剩余资源向量A=(2,2,0)，若满足它的请求，使得系统剩余资源向量A=(2,1,0)。之后，系统仍可以找到一个进程完成序列P1,P4,P0,P4,P2。故可以满足它的请求。 (2’) 3系统有同类资源10个，进程p1、p2和p3需要该类资源的最大数量分别为8，6，7。它们使用资源的次序和数量如下图所示。 1） 试给出采用银行家算法分配资源时，进行第5次分配后各进程的状态及各进程占用资源 情况。 2） 在以后的申请中，那次的申请可以得到最先满足?给出一个进程完成序列。 次序 进程 申请量 次序 进程 申请量 1 P1 3 5 P2 2 2 P2 2 6 P1 3 3 P3 4 7 P3 3 4 P1 2 8 P2 2 解：1）计算第5次分配后进程的状态和占用资源情况：(`5’=1’*5) ① p1申请3个，满足，系统还剩7个 ②p2申请2个，满足（因为系统的7个可以使p2运行完），系统还剩5个 ③p3申请4个，因为若满足它的请求，可能使以后的任何进程都不能运行完，故p3等待 ④p1申请2个，满足（系统还剩5个可以满足p1的最大请求），系统还剩3个 ⑤ p2申请2个，不能满足，等待。此时系统的分配情况如下： p1分配5个后正在运行，p2分配2个后等待分配2个，p3等待分配4个，系统还剩3个。 2）p1接着运行，p1申请3个可满足(2’)。P1运行完成后，释放资源，使系统的资源数量变为8个。首先将p3唤醒，满足它的4个资源，系统还剩4个，可以唤醒p2，满足它的2个请求。系统还剩2个。 P3申请3个，不能满足，等待。 P2申请2个，系统满足它，p2接着运行；p2完成，释放资源，使系统资源变为6个。系统唤醒p3，满足它的资源请求，最终p3完成，释放资源，使资源数量恢复为10个。 找到的进程完成序列为p1,p2,p3。 (3’) 4设系统中有150个可用的同类资源。在某时刻系统中的进程已获得的资源和最大请求资源如下所示，请用银行家算法分别判断完成下列请求时，系统是否安全？若安全，请给出进程的完成序列。如不安全，请说明原因。 进程 最大需求量 当前已分配量 p1 70 25 p2 60 40 p3 60 45 p4 60 0 (1) 进程p4当前请求25个资源； (2) 之后p4又提出35个资源的请求。 解答：系统当前剩余资源量为：150 – 25 – 40 – 45 = 40 (2’) (1) 可以满足(2’)，假定先分配p4的25个资源，系统还剩15个。将这15个资源可先分配 给p3，p3达到最大请求，释放60个；之后可以分配给其他任何进程，系统中的进程都能顺利完成。由此可见，p2请求的25个资源可以满足，且能找到完成序列：p3，p1，p2，p4，…(4’) (2) 当p4再提出35个资源请求时，系统还剩15，显然不能满足它的请求，让其阻塞等待。 (2’) 5系统中有五个进程，分别为p1\\p2\\p3\\p4\\p5，四类资源分别为r1\\r2\\r3\\r4。某一时刻，系统剩余资源向量A=(1，2，3，0)。 （1） 用银行家算法试判断系统当前状态是否安全？ （2） 当进程p3提出对资源r3的剩余请求时，能否满足她？ （3） 系统初始配置的各类资源分别为多少？ ?1?1? MAX??2??0??0?1?0???1 NEED??0??0212?750??356? ， ?852?636???0?1??1??0??0012?000??144? . ?632?014??解答：系统剩余资源向量 A=(1, 2, 3, 0) 。现在需求出各进程的剩余资源请求矩阵: 200?750??212? (2’) ?220?622??(1) 详细步骤省略。由于系统存在一个进程完成的安全序列P1\\P3\\P4\\P2\\P5(2’)，故系统状态 是安全的(2’)。 (2) 进程P3提出对资源R3的剩余请求为1，由于系统剩余资源向量A=(1,2, 3, 0)，故可以 假定分配给它。如果能找到一个安全序列，就可以真正进行分配。当分配给P3一个资源时，系统剩余资源向量A=(1 ,2 ,2 , 0)。由此可见，仍然可以找到一个与(1)相同的安全序列。故可以满足P3的请求。(3’) (3) 系统初始配置的各类资源分别为(3 ,9 , 12 , 12 )。(1’) 第四章 调度 名词解释 1作业 用户在一次上机过程中要求计算机系统所做工作的集合。 2周转时间 是指从作业进入系统开始，到作业退出系统所经历的时间。 3响应时间 是分时系统的一个技术指标，指从用户输入命令到系统对命令开始执行和显示所需要的时间。 4作业调度 作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转换。 5进程调度 也称低级调度程序，它完成进程从就绪状态到运行状态的转化。实际上，进程调度完成一台物理的cpu转变成多台虚拟（或逻辑）的cpu的工作。 6交换调度 是基于系统确定的某个策略，将主存中处于等待状态或就绪状态的某个或某些进程交换到外存交换区中，以便将外存交换区上具备运行条件的进程换入主存，准备执行。引入交换调度的目的是为了解决主存紧张和提高主存的利用效率。 7剥夺式调度 当一个进程正在执行时，系统基于某种策略强行将处理机从占有者进程剥夺而分配给另一个进程的调度。这种调度方式系统开销大，但系统能及时响应请求。 8非剥夺式调度 系统一旦把处理机分配给某个进程之后，该进程一直运行下去，直到该进程完成或因等待某个事件发生时，才将处理机分配给其他进程。这种调度方式实现简单，系统开销小，但系统性能不够好。 简答题 1作业由哪几部分组成？各有什么功能？ 答：作业由三部分组成：程序、数据和作业说明书。 程序和数据完成用户所要求的业务处理工作，作业说明书则体现用户的控制意图。 2试比较作业和进程的区别 答：一个进程是一个程序对某个数据集的执行过程，是分配资源的单位。作业是用户需要计算机完成某项任务，而要求计算机所做工作的集合。一个作业的完成要经过作业提交、作业收容、作业执行和作业完成4个阶段。而进程是已提交完毕的程序所执行过程的描述，是资源分配的基本单位。 其主要区别关系如下： （1）作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业之后，系统将它放入外存中的作业等待队列中等待执行。而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。任一进程，只要它被创建，总有相应的部分存在内存中。 （2）一个作业可由多个进程组成。且必须至少由一个进城组成，但反过来不成立。 （3）作业的概念主要用在批处理系统中。像UNIX这样的分时系统中，则没有作业概念。则进程的概念则用在几乎所有的多道程序系统中。 3高级调度与低级调度的主要功能是什么？为什么要引入中级调度？ 答:高级调度的主要功能是根据一定的算法,从输入的一批作业中选出若干作业,分配必要的资源,如内存、外设等，为它建立相应的用户作业进程和为其服务的系统进程（如输入/输出进程），最后把它们的程序和数据调入内存，等待进程调度程序对其执行调度，并在作业完成后做善后处理工作。 低级调度的主要功能是根据一定的算法将cpu分派给就绪队列中的一个进程。 为了使内存中同时存放的进程数目不至于太多，有时需要把某些进程从内存移到外存上，以减少多道程序的数目，为此设立了中级调度. 4处理机调度一般分为哪三级？其中哪一级调度必不可少？为什么？ 答：处理机调度一般可分为高级调度（作业调度）、中级调度和低级调度（进程调度） 。其中进程调度必不可少 。 进程只有在得到CPU之后才能真正活动起来，所有就绪进程经由进程调度才能获得CPU