第3章 处理机调度与死锁2

第 9 次 课 教 案

操作系统 课程 计本081-4 班级 年 月 日 章节名称 教学目的 与 要 求 第3章 处理机调度与死锁 了解死锁产生的原因和必要条件，掌握处理死锁的方法。 3.5 产生死锁的原因与必要条件 教学内容 3.6 死锁的预防与避免 3.7 死锁的检测与解除 重 点 难 点 作 业 教具与挂图 银行家算法 死锁处理的方法 自编3.3、3.4、3.4 教学过程 讲解与举例 (组织与方法) 3.5 产生死锁的原因和必要条件

假设系统中有P1、P2两个并发执行的进程，P1和P2在执行中同时需要R1和R2两类资源，其中R1是输入机，R2是打印机，P1和P2的执行过程如下：

P1 () {

…… 申请R1; }

…… 申请R2;

使用R1和R2; 释放R1和R2；

P2 () {

…… 申请R2; }

…… 申请R1;

使用R1和R2; 释放R1和R2；

死锁是指系统中并发执行的进程彼此互相等待对方已经拥有的资源，这些并发执行的进程在

得到对方的资源之前又不释放自己拥有的资源，从而使得所有的进程都陷入阻塞的状态，而不能再向前推进的一种僵局的状态。

一、死锁的形成原因 ⒈ 资源分配图

资源分配图是由一组结点和一组边E所组成的点对集合，即G=(N，E)，具有下述定义和限制： ⑴N是两个互斥的子集，一组是进程结点P={P1，P2，P3，……}，一组是资源结点R={R1，R2，R3，……}，N=P∪R。

⑵E中的每条边连接P中的一个结点和R中的一个结点。 如果E中的一条边e={Pi，Rj}，表示进程Pi请求资源Rj；

如果E中的一条边e={Rj，Pi}，表示资源Rj已经分配给了进程Pi。

P1R1R2 P2 资源分配图

⒉ 形成原因 ⑴竞争资源

系统中并发执行的进程共享着系统中的资源，系统中的资源数不足以满足所有进程的最大需求，所以进程间将会竞争资源，从而才有可能出现进程间相互等待对方资源的情况。

⑵进程推进顺序不当 ●进程推进顺序合理

P2Relase(R1)2Relase(R2)Request(R1)13Request(R2)4Request(R1)Request(R2)Relase(R1)Relase(R2)P1

进程推进顺序对死锁的影响

二、产生死锁的必要条件 ⒈ 互斥条件 ⒉ 不可剥夺条件 ⒊ 请求与保持条件 ⒋ 环路等待条件

环路等待条件是死锁产生的必要条件而不是充分条件，即进程和资源之间形成环路却不一定会产生死锁。

三、处理死锁的基本方法 ⒈ 预防死锁 ⒉ 避免死锁 ⒊ 检测死锁

⒋ 解除死锁

3.6 死锁的预防和避免

一、死锁的预防

死锁的预防是解决死锁的一种静态策略，破环死锁的4个必要条件，从而达到防止死锁的目的。

⒈ 破坏互斥条件 ⒉ 破坏不可剥夺条件 ⒊ 破坏请求与保持条件 ⒋ 破坏环路等待条件 二、 系统的安全状态 ⒈ 安全状态

所谓安全状态，是指系统能按照某种顺序如{P1，P2，P3，……，Pn}，其中P1，P2等为系统中的进程，为每个进程分配其所需要的资源，并达到最大的需求，使得每个进程可以顺利完成。

⒉ 安全序列

系统中所有的进程能够执行完毕的一种执行次序，如{P1，P2，P3，……，Pn}。从定义中可以得知安全序列不唯一。

下面通过一个例子来说明什么是安全状态和安全序列。

【例】假设系统中有3个进程P1、P2、P3，共有12台磁带机。进程P1需要10台磁带机，P2

需要4台，P3需要9台。设某一时刻T0，进程占有资源的情况如表所示。请判断系统在T0时刻是否安全，如果安全，请给出安全序列。

T0时刻的资源分配情况

进程 P1 P2 P3 需求 10 4 9 已分配 5 2 2

三、银行家算法

死锁的避免是一种动态策略，保证系统不进入死锁状态，对进程发出的资源请求进行动态检查，并根据检查结果决定是否分配资源。

银行家算法是最具有代表性的死锁避免的方法，银行家算法需要如下几个重要的数据结构。

⒈ 数据结构 ⑴Max矩阵

Max是一个n×m的矩阵，表示系统中每个进程对各类资源的最大需求。 ⑵Allocation矩阵

Allocation是一个n×m的矩阵，表示系统中每一个进程已经占有的各类资源的数量。 ⑶Need矩阵

Need是一个n×m的矩阵，表示系统中每个进程完成还需要的各类资源的数量。从定义中可以得知Need矩阵=Max矩阵-Allocation矩阵。 ⑷Available矩阵

系统剩余的可用资源数。Available矩阵是含有m个元素的数组。 ⒉ 算法执行过程

进程在执行过程中可能要请求资源，设Requesti是进程Pi对资源的请求向量，如果Request[j]=k，表示进程Pi需要k个Rj资源。当进程Pi提出资源请求时，系统将按照如下过程进行动态检查：

⑴如果Requesti≤Needi，则转向步骤⑵；否则出错，因为进程Pi请求的资源数超出进程运行完成还需要的资源数。

⑵如果Requesti≤Available，则转向步骤⑶，否则该进程必须等待，因为系统剩余的资源数不能满足进程的需要。

⑶进行资源预分配，假设系统满足进程的需要，将资源分配给进程Pi，并且修改相应的数据结构：

Available=Available-Requesti；

Allocation=Allocation+Requesti； Needi = Needi -Requesti；

⑷系统执行安全性算法，检查此次预分配后，系统是否处于安全状态。如果处于安全状态，正式将资源分配给进程Pi；否则，此次预分配失败，恢复预分配前的系统的资源分配状态，让进程Pi处于等待状态。

⒊ 安全性算法

安全性算法就是用来检查系统是否是安全状态的一种常用算法。 安全性算法需要定义如下几个重要的数据结构： ⑴工作向量Work

Work表示系统可提供给进程继续运行所需要的各类资源的数目，即Work= Available。 ⑵Finish向量

Finish向量表示系统是否有足够的资源分配给进程，使其能运行完成，初始情况Finish值均为False，当有足够的资源分配给进程使其能运行完成时，该进程对应的Finish的值变为True。

安全性算法执行过程如下：

⑴从n个进程中找到一个满足下述条件的进程：

①Finish[i]=False

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第3章 处理机调度与死锁2在线全文阅读。