中国科学技术大学：《嵌入式操作系统 Embedded Operating Systems》课程教学资源（PPT课件讲稿）第六讲 死锁及其处理

第六讲死锁及其处理 2 GALVIN 中国科学技术大学计算机系 计算机操作系统 陈香兰 operating System xlanchen ustc. edu.cn Concepts 2013Fall ◆大 嵌入式系统实验室 EMBEDDED SYSTEM LAE口RAT口RY SUZHOU INSTITUTE FOR ADVANCED STUDY OF USTC

第六讲 死锁及其处理 中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn 2013Fall

内容提要 ◆死锁的定义和产生死锁的原因 令产生死锁的必要条件 令处理死锁的基本方法 死锁的预防 死锁的避免958 死锁的检测与解除 ☆ Reading ≯计算机操作系统,汤子瀛,46、47、48节 >Operating System Concepts, 7Th edition, ch7 嵌入式系统实验室 EMBEDDED SYSTEM LAB口RAT口RY SU:MDU INTHUTE OR AOVANCLD STUOY D USTt

内容提要 ❖死锁的定义和产生死锁的原因 ❖产生死锁的必要条件 ❖处理死锁的基本方法 ➢死锁的预防 ➢死锁的避免 ➢死锁的检测与解除 ❖Reading ➢计算机操作系统，汤子瀛，4.6、4.7、4.8节 ➢Operating System Concepts，7Th edition，ch7

内容提要 ◆死锁的定义和产生死锁的原因 令产生死锁的必要条件 令处理死锁的基本方法 死锁的预防 死锁的避免958 死锁的检测与解除 嵌入式系统实验室 EMBEDDED SYSTEM LAB口RAT口RY SU:MDU INTHUTE OR AOVANCLD STUOY D USTt

内容提要 ❖死锁的定义和产生死锁的原因 ❖产生死锁的必要条件 ❖处理死锁的基本方法 ➢死锁的预防 ➢死锁的避免 ➢死锁的检测与解除

死锁的定义 令 Deadlock死锁 ◇所谓死锁,是指多个进程因竞争资源而造成的一 种僵局( Deadly- Embrace),若无外力作用, 这些进程将永远不能再向前推进。 嵌入式系统实验室 EM日 EDDED SYSTEM LA日口 RATORY

死锁的定义 ❖Deadlock 死锁 ❖所谓死锁，是指多个进程因竞争资源而造成的一 种僵局（Deadly－Embrace），若无外力作用， 这些进程将永远不能再向前推进

产生死锁的原因 令归结为两点 竞争资源 进程推进顺序非法 令为便于讨论,首先给出资源分配图的概念 嵌入式系统实验室 EMBEDDED SYSTEM LAB口RAT口RY SU:MDU INTHUTE OR AOVANCLD STUOY D USTt

产生死锁的原因 ❖归结为两点 ➢竞争资源 ➢进程推进顺序非法 ❖为便于讨论，首先给出资源分配图的概念

资源分配图( Resource allocation graph) ◆死锁可用资源分配图来描述 令资源分配图是由一组结点N和一组边E所组成的 个有向图G=(N,E) >N=P∪R P是一组进程结点,P={P1,P2,P3} R是一组资源结点,R={R1,R2,,R3 ≯e={PiRj},或Pi→Rj,资源请求边 e={RjPi},或Rj→Pi,资源分配边 嵌入式系统实验室 EMBEDDED SYSTEM LAB口RAT口RY SU:MDU INTHUTE OR AOVANCLD STUOY D USTt

资源分配图（Resource allocation Graph） ❖死锁可用资源分配图来描述 ❖资源分配图是由一组结点N和一组边E所组成的 一个有向图G=(N, E) ➢N=P∪R P是一组进程结点，P={P1,P2,…,P3} R是一组资源结点，R={R1,R2,…,R3} ➢e={Pi,Rj}，或Pi→Rj，资源请求边 ➢e={Rj,Pi}，或Rj→Pi，资源分配边

令资源分配图的图形表示 >使用小圆卷表示一个进程 >使用方框表示一个资源类型 口日 >使用一个点表示个资源实例 请求边由进程指向方框; P)→日 R >分配边必须始于方框中的某个点 R 嵌入式系统实验室 EMBEDDED SYSTEM LAB口RAT口RY SU:MDU INTHUTE OR AOVANCLD STUOY D USTt

❖资源分配图的图形表示 ➢使用小圆卷表示一个进程 ➢使用方框表示一个资源类型 ➢使用一个点表示一个资源实例 ➢请求边由进程指向方框； ➢分配边必须始于方框中的某个点 Pi Rj Pi Rj

资源分配图举例 RI R3 1958 R2 R4 Resource-allocation graph 嵌入式系统实验室 EMBEDDED SYSTEM LAB口RAT口RY SU:MDU INTHUTE OR AOVANCLD STUOY D USTt

资源分配图举例 R4 R3 R2 R1 P1 P2 Resource-allocation graph P3

发生死锁的资源分配图 RI R3 PI P3 958 R2 R4 Resource-allocation graph ith a deadlock k 嵌入式系统实验室 EMBEDDED SYSTEM LAB口RAT口RY SU:MDU INTHUTE OR AOVANCLD STUOY D USTt

发生死锁的资源分配图 R4 R3 R2 R1 P1 P2 Resource-allocation graph with a deadlock P3

、竟争资源引起死锁 令可剥夺和非剥夺性资源 可剥夺资源,如CPU,内存 不可剥夺资源,如磁带机,打印机 ◆竞争非剥夺资源 Example 1958 System has 2 tape drives >PI and P2 each hold one and each needs another one P1 tape1 tape2 P2 嵌入式系统实验室 EMBEDDED SYSTEM LAB口RAT口RY SU:MDU INTHUTE OR AOVANCLD STUOY D USTt

一、竞争资源引起死锁 ❖可剥夺和非剥夺性资源 ➢可剥夺资源，如CPU，内存 ➢不可剥夺资源，如磁带机，打印机 ❖竞争非剥夺资源 Example： ➢System has 2 tape drives ➢P1 and P2 each hold one and each needs another one P1 P2 tape1 tape2