计算机操作系统第4章案例分析.ppt

习 题1 3个进程共享4个同类资源，他们一次只能保持和释放1个资源。每个进程最多需要2个资源。问：系统可能死锁吗？ 答案：系统不可能死锁。 根据：抽屉原理/鸽巢原理 ——把多于kn个东西任意分放进n个空抽屉（k是正整数），那么一定有一个抽屉中放进了至少k+1个东西。 进程→鸽巢；资源→鸽子 习 题2 N个进程共享M个资源，保持和释放这些资源每次仅一个。每个进程对资源的需求量最大不超过M,并且这N个进程对资源的最大需求量的总和小于M+N。这时，不会产生死锁。 证明：假设已经产生死锁，且死锁的进程是P1,P2,…,PI。则根据产生死锁的4个必要条件，有： 所有资源(M个)已经被这些进程占用； 这些进程至少需要多于I个单位的资源； 其他N-I个进程至少需要N-I个单位的资源。 因此，这N个进程至少需要M+I+N-I=M+N个资源。矛盾，此矛盾说明死锁不会产生。 * 4.3.1 资源 资源可以分成如下两类： 可剥夺性资源，是指某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺。如：处理机和内存。优先权高的进程可以剥夺优先权低的进程的处理机。内存区可由存储器管理程序把一个进程从一个存储区移到另一个存储区，此即剥夺了该进程原来占有的存储区。甚至可将一个进程从内存调出到外存上。 不可剥夺性资源，当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等。 * 4.3.2 死锁产生原因和必要条件 死锁的定义 所谓死锁 (Deadlock)，是指多个进程因竞争资源而造成的一种僵局(Deadly-Embrace)，若无外力作用，这些进程将永远不能再向前推进。 在一组进程发生死锁的情况下，这组死锁进程中的每一个进程，都在等待另一个死锁进程所占有的资源。 * 4.3.2 死锁产生原因和必要条件 1. 死锁产生的原因 死锁产生的原因和临界资源的访问及进程的并发执行有关。 资源竞争：当系统中供多个进程共享的资源如打印机，其数目不足以满足诸进程的需要时，会引起诸多进程对资源的竞争而产生死锁； 进程推进顺序不当：进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。 * 进程推进顺序不当引起死锁 P1req(R1) P1req(R2) P1rel(R1) P1rel(R2) P2rel(R1) P2rel(R2) P2req(R1) P2req(R2) a b c d e f g 1、推进顺序 P1req(R1) P1req(R2) P1rel(R1) P1rel(R2) P2req(R2) P2req(R1) P2rel(R2) P2rel(R1) 3、推进顺序 P1req(R1) P1req(R2) P2req(R2) P1rel(R1) P1rel(R2) P2req(R1) P2rel(R2) P2rel(R1) 4、推进顺序：P1req(R1) ； P2req(R2) , P1和P2再 继续推进将发生死锁 四种颜色的线段 为四种推进顺序 2、类似情形1 * 4.3.2 死锁产生原因和必要条件 2. 死锁产生的必要条件 互斥: 进程对所分配到的资源必须独立使用，即在一段时间内某资源只由一个进程占用，不能共享。如果此时还有其它进程请求该资源，则请求者只能等待，直至占有该资源的进程使用完毕，对资源进行释放。 请求和保持：进程已经持有了至少一个资源，但又提出了新的资源请求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对已获得的其它资源保持继续持有。 不可剥夺: 在未使用完之前，不能剥夺进程已获得的资源，只能在使用完时由自己释放。 循环等待：在发生死锁时，必然存在一个进程和进程之间等待相互资源的环形链。使得链中每个进程的资源需求都得不到满足。 * 4.3.3 死锁的表示方法 系统资源分配图来表示死锁 一个系统资源分配图（System Resource Allocation Graph, SRAG）可以定义为一个二元组 ，其中 是顶点的集合， 是有向边的集合。 是由系统内的所有进程组成的集合，每一个 代表一个进程； 是由系统内所有资源组成的集合，每一个 代表一类资源。 如果 ，则存在一条从 指向 的有向边，它表示进程 提出了一个要求分配 类资源中的一个资源的请求。 * 4.3.3 死锁的表示方法 系统资源分配图来表示死锁 图 4.7 SRAG示例 * 4.3.4 死锁的