2018年5月中项计算题真题解题思路.pdf

试题二（17 分）阅读下列说明，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。【说明】某项目由 P1、P2、P3、P4、P5 五个活动组成，五个活动全部完成之后项目才能够完成，每个活动都需要用到 R1、R2、R3 三种互斥资源，三种资源都必须达到活动的资源需求量，活动才能开始。已分配资源只有在完成本活动后才能被其他活动所用。目前项目经理能够调配的资源有限，R1、R2、R3 的可用资源数分别为 9、8、5 活动对资源的需求量、已分配资源数和各活动历时如下表所示（假设各活动之间没有依赖关系）:资源 活动 资源需求量 已分配资源数 历时（周）R1 R2 R3 R1 R2 R3 P1 6 4 1 1 2 1 1 P2 2 3 1 2 1 1 3 P3 8 0 1 2 0 0 3 P4 3 2 0 1 2 0 2 P5 1 4 4 1 1 3 4【问题 1】（6 分）基于以上案例，简要叙述最优的活动步骤安排。【问题 2】（7 分）基于以上案例，请计算项目的完工时间（详细写出每个活动开始时间、占用资源和完成时间以及项目经理分配资源的过程）。在学习操作系统中进程的时候，会接触到进程死锁这个名称。那么什么是进程死锁？进程死锁指的是：如果多个进程同时占有对方需要的资源而同时请求对方的资源，而它们在得到请求之前不会释放所占有的资源，那么就会导致死锁的发生，也就是进程不能实现同步。那么死锁是怎样产生的？那么死锁是怎样产生的？死锁的产生有四个必要条件：死锁的产生有四个必要条件：互斥条件：即一个资源每次只能被一个进程使用（在操作系统中这是真实存在的情况）保持和等待条件：有一个进程已获得了一些资源，但因请求其他资源被阻塞时，对已获得的资源保持不放 不剥夺条件：有些系统资源是不可剥夺的，当某个进程已获得这种资源后，系统不能强行收回，只能由进程使用完成时自己释放 环路等待条件：若干个进程形成环形链，每个都占用对方要申请的下一个资源 而避免死锁最具有代表性的就是银行家算法 至于什么是银行家算法，这里就不再赘述了，说实话，单凭概念很难理解它的含义，还是通过讲解例子，来理解到底什么是银行家算法。 QQ：915446173例题：假设系统中有三类互斥资源 R1、R2、R3，可用资源数分别是 9、8、5。在 T0 时刻，系统中有 P1、P2、P3、P4 和 P5 五个进程，这些进程对资源的最大需求量和已分配的资源数如下所示，如果进程按照_序列执行，那么系统状态是安全的。解答过程：从题目给出的进程资源表可以看出，对于资源 R1、R2、R3，它们已经提前各自分配了一部分，现在我们看一下，是否还有剩余。R1=9-（1+2+2+1）=2 R2=8-（2+1+1+2+1）=1 R3=5-（1+1+3）=0 同时，对于五个进程，系统分配给了他们各自一部分资源，这一部分资源是否能够满足他们，根据还需资源还需资源=最大需求量最大需求量已分配资源数来已分配资源数来求，结果如下：很明显，“剩余资源”只能满足进程 P2 的要求 那么就先开始运行进程 P2。当 P2 运行之后，已“分配的资源”要释放出来，此时剩余资源剩余资源=上一个进程的剩余资源上一个进程的剩余资源+“已分配资源已分配资源”（下图中 P2 已经执行完毕了）根据比较可以看出“剩余资源”完全满足进程完全满足进程 P4，以此类推，可以得到最后的结果表，以此类推，可以得到最后的结果表 QQ：915446173银行家是计算并不难，主要就是有些繁琐，在计算的时候需要耐心。银行家是计算并不难，主要就是有些繁琐，在计算的时候需要耐心。著名的银行家算法，最早是由 Dijkstra 提出来的。它是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。银行家算法最重要的就是判断是可用资源和仍需资源之间的关系，如果可用资源数大于人需资源数，那么我们认为这个进程就是可以执行的，也是安全的，反之，便是不安全的。所以重中之重的是找到各种资源数。对进程的判断遵循以下步骤:1.计算系统开始时所有的资源数,即开始的可用资源数;2.在仍需资源数和可用资源数中作比较,找到符合条件的进程,最后修改进程执行完毕时系统的可用资源数;3.继续比较剩余进程和可用资源数,找到下边可以执行的进程;4.依次类推;下面那一个例子来解释这些晦涩的文字，一定要认真去看哦 O(_)O 【例】假设系统中有 3 类互斥资源 R1、R2、R3，可用资源分别是 9、8、5,。在 T0 时刻系统中有 P1、P2、P3、P4 和 P5 五个进程，这些进程对资源的最大需求量和已分配资源数如下表所示，则进程如何执行是安全的。 QQ：915446173 这里需要强调的是，无论题目中给出何种条件，我们只要找到以下信息便可从容应对各种变化：【注】：可用资源：表示相应的进程执行完毕（即释放该进程占用的资源）以后可用的资源，满足公式可用资源=可用资源+已分配资源，（因为已分配的资源将会在进程执行完毕以后释放，所以可用资源会不断增多，进程执行完毕便会全部释放）同时它也是下一个进程执行时可用的资源。*需要说明的是根据进程执行情况的不同，每次填入表格中的可用资源也不会相同（因为每个进程分配的资源是有差异的），那么执行顺序也会有所差异，合理即可。仍需资源：仍需资源数=最大需求量-已分配资源数，据此公式可以求得 R1、R2、R3 在不同的进程时仍需的资源数，如上表中所示。按照之前所讲的步骤，实现如下：R1 已分配的总资源数为 1+2+2+1+1=7 R2 已分配的总资源数为 2+1+1+2+1=7 R3 已分配的总资源数为 1+1+0+0+3=5 则 R1 R2 R3 可用资源数分别为 9-7=2,8-7=1,5-5=0，1.开始有的资源数 R1 R2R3 分别为 2、1、0,所以从仍需资源中查找(需要说明的是查找的时候以最少资源数作为限定条件能够较快地找出结果),只有 P2 进程符合条件,此时可用资源变为 4、2、1；2.接下来在在其余的进程中查找符合条件的进程,只能执行 P4,此时可用资源变为 5、4、1,以此类推,按照以上的步骤即可找到所有进程执行的顺序 P2-P4-P5-P1-P3；以上便是有关银行家算法的计算过程，总体看来，银行家算法更多的是对概念的考察，弄清楚各个条件之间的制约关系便可迎刃而解了，希望能对大家有所帮助！ QQ：915446173