四川大学：《操作系统 Operating System》课程教学资源（PPT课件讲稿）Chapter 6 Concurrency - Deadlock（死锁）and Starvation（饥饿）

Review Concurency 互斥/ Mutua| Exclusion 同步/ Synchronization . Implementation 软件方法: Dekker算法(两个进程(线程)实现互斥) 硬件方法:关中断、特殊指令 ·OS/开发语言所提供的机制 Semaphore · Monitor MessagePassing

Review • Concurerncy: • 互斥/Mutual Exclusion • 同步/Synchronization • Implementation • 软件方法：Dekker算法(两个进程(线程)实现互斥) • 硬件方法：关中断、特殊指令 • OS/开发语言所提供的机制 • Semaphore • Monitor • MessagePassing • ... 2

Chap6 Concurrency: Deadlock&Starvation .6.1 Principles of deadlock 6.2 Deadlock prevention 6 3 Deadlock avoidance 6.4 Deadlock detection 6.5 An Integrated Deadlock Strategy 6.6 Dining Philosophers Problem .6.7 Summary

Chap6 Concurrency: Deadlock&Starvation • 6.1 Principles of Deadlock • 6.2 Deadlock Prevention • 6.3 Deadlock Avoidance • 6.4 Deadlock Detection • 6.5 An Integrated Deadlock Strategy • 6.6 Dining Philosophers Problem • 6.7 Summary 3

6.1 Principles of Deadlock ·6.1.0 Intro 6.1.1 Reusable resources 6.1.2 Consumable resources 6. 1.3 Resource Allocation Graphs 6.1. 4 The Conditions for deadlock

6.1 Principles of Deadlock • 6.1.0 Intro • 6.1.1 Reusable Resources • 6.1.2 Consumable Resources • 6.1.3 Resource Allocation Graphs • 6.1.4 The Conditions for Deadlock 4

6.1.0 Intro(1/6) Deadlock Permanent blocking of a set of processes that either compete for system resources or communicate with each other No efficient solution Involve conflicting (冲突) needs for resources by two or more processes

6.1.0 Intro(1/6) • Deadlock • Permanent blocking of a set of processes that either compete for system resources or communicate with each other • No efficient solution • Involve conflicting(冲突) needs for resources by two or more processes 5

61.0 Intro(2/6) cb曰曰 后曰图 EA o E s4d (a) Deadlock possible (b) Deadlock Figure 6.1 Illustration of Deadlock

6.1.0 Intro(2/6) 6

61.0 Intro(3/6) rogress Release 绕 and Release Required et⊥ 3 B deadlock inevitable Required Get B 4 Fatal Region P has a, Q has B Deadlock!! Progress Get A Get B Release A Release B of p both Pand Q want resource A S=both Pand Q want resource B Required deadlock-inevitable region B Required possible progress path of P and Q Horizontal portion of path indicates Pis executing and Q is waiting Vertical portion of path indicates Pis executing and Q is waiting Figure 6.2 Example of Deadlock

6.1.0 Intro(3/6) 7 Fatal Region P has A, Q has B Deadlock!!

61.0 Intro(4/6) Progress f Q Release Release Required Get A and Required Get B Progress Geta Release A Get B Release B =both P Q want resource A A Required B Required both P and Q want resource B possible progress path of P and Q Horizontal portion of path indicates P is executing and Q is waiting Vertical portion of path indicates P is executing and Q is waiting Figure 6.3 Example of No Deadlock [BACO03]

6.1.0 Intro(4/6) 8

6.1.0 Intro(5/6) Resources categories(资源的分类) Reusable resources(可重用资源) Consumable resources(可消费资源)

6.1.0 Intro(5/6) • Resources Categories(资源的分类) • Reusable Resources(可重用资源) • Consumable Resources(可消费资源) 9

6.1.0 Intro(6/6) System Model Process must request a resource before using Process must release the resource when done Deadlock A set of processes is in a deadlock state when every process in the set is waiting for an event that can only be caused by another process in the set

6.1.0 Intro(6/6) • System Model • Process must request a resource before using • Process must release the resource when done • Deadlock • A set of processes is in a deadlock state when every process in the set is waiting for an event that can only be caused by another process in the set. 10

6.1 Principles of Deadlock ·6.1.0 Intro 6.1.1 Reusable resources 6.1.2 Consumable resources 6. 1.3 Resource Allocation Graphs 6.1. 4 The Conditions for deadlock

6.1 Principles of Deadlock • 6.1.0 Intro • 6.1.1 Reusable Resources • 6.1.2 Consumable Resources • 6.1.3 Resource Allocation Graphs • 6.1.4 The Conditions for Deadlock 11