ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo
Deadlocks
System Model
• System consists of resources
• Resource types R1, R2, . . ., Rm
CPU cycles, memory space, I/O devices
• Each resource type Ri has Wi instances.
• Each process utilizes a resource as follows:
• request
• use
• release
Deadlock Characterization
• Deadlock can arise if these four conditions hold
simultaneously.
• Mutual exclusion: only one process at a time can use a resource
• Hold and wait: a process holding at least one resource is waiting
to acquire additional resources held by other processes
• No preemption: a resource can be released only voluntarily by
the process holding it, after that process has completed its task
• Circular wait: there exists a set {P0, P1, …, Pn} of waiting
processes such that P0 is waiting for a resource that is held by P1,
P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for
a resource that is held by Pn, and Pn is waiting for a resource that
is held by P0.
Resource-Allocation Graph
• A set of vertices V and a set of edges E.
• V is partitioned into two types:
• P = {P1, P2, …, Pn}, the set consisting of all the processes in the system
• R = {R1, R2, …, Rm}, the set consisting of all resource types in the
system
• request edge – directed edge Pi  Rj
• assignment edge – directed edge Rj  Pi
Resource-Allocation
Graph(Cont.)
• Process
• Resource Type with 4 instances
• Pi requests instance of Rj
• Pi is holding an instance of Rj
Pi
Pi
Rj
Rj
Example of a Resource
Allocation Graph
Resource Allocation Graph
With A Deadlock
Graph With A Cycle But No
Deadlock
Basic Facts
• If graph contains no cycles  no deadlock
• If graph contains a cycle 
• if only one instance per resource type, then deadlock
• if several instances per resource type, possibility of deadlock
Methods for Handling
Deadlocks
• Ensure that the system will never enter a deadlock state:
• Deadlock prevention
• Deadlock avoidence
• Allow the system to enter a deadlock state and then recover
• Ignore the problem and pretend that deadlocks never occur in
the system; used by most operating systems, including UNIX

More Related Content

Similar to Deadlock.pptx (20)

Deadlock in Real Time operating Systempptx
Deadlock in Real Time operating SystempptxDeadlock in Real Time operating Systempptx
Deadlock in Real Time operating Systempptx
ssuserca5764
Ìý
7 Deadlocks
7 Deadlocks7 Deadlocks
7 Deadlocks
Dr. Loganathan R
Ìý
6. Deadlock_1640227623705.pptx
6. Deadlock_1640227623705.pptx6. Deadlock_1640227623705.pptx
6. Deadlock_1640227623705.pptx
shrijanasharma3
Ìý
14th November - Deadlock Prevention, Avoidance.ppt
14th November - Deadlock Prevention, Avoidance.ppt14th November - Deadlock Prevention, Avoidance.ppt
14th November - Deadlock Prevention, Avoidance.ppt
Unknown664473
Ìý
Module 3 Deadlocks.pptx
Module 3 Deadlocks.pptxModule 3 Deadlocks.pptx
Module 3 Deadlocks.pptx
shreesha16
Ìý
deadlocks for Engenerring for he purpose
deadlocks for Engenerring for he purposedeadlocks for Engenerring for he purpose
deadlocks for Engenerring for he purpose
adityaarya357060
Ìý
OS deadlock.pptx
OS deadlock.pptxOS deadlock.pptx
OS deadlock.pptx
rpbbhalerao2000
Ìý
protection and security in operating systems
protection and security in operating systemsprotection and security in operating systems
protection and security in operating systems
MadhaviB6
Ìý
Lecture 8 - Memory Management. It deals with memory management
Lecture 8 - Memory Management. It deals with memory managementLecture 8 - Memory Management. It deals with memory management
Lecture 8 - Memory Management. It deals with memory management
tumaassignment
Ìý
Chapter 4
Chapter 4Chapter 4
Chapter 4
ushabarad142
Ìý
Chapter5_Deadlock.pptx
Chapter5_Deadlock.pptxChapter5_Deadlock.pptx
Chapter5_Deadlock.pptx
DenisPriscus
Ìý
Deadlock
DeadlockDeadlock
Deadlock
Rajapriya82
Ìý
Deadlock
DeadlockDeadlock
Deadlock
Rajapriya82
Ìý
Deadlock in Operating System
Deadlock in Operating SystemDeadlock in Operating System
Deadlock in Operating System
AUST
Ìý
Deadlocks Part- I.pdf
Deadlocks Part- I.pdfDeadlocks Part- I.pdf
Deadlocks Part- I.pdf
Harika Pudugosula
Ìý
Mch7 deadlock
Mch7 deadlockMch7 deadlock
Mch7 deadlock
wahab13
Ìý
Deadlock.ppt
Deadlock.pptDeadlock.ppt
Deadlock.ppt
JeelBhanderi4
Ìý
deadlock in OS.pptx
deadlock in OS.pptxdeadlock in OS.pptx
deadlock in OS.pptx
Monirul Islam
Ìý
Deadlock
DeadlockDeadlock
Deadlock
sangrampatil81
Ìý
Module-2Deadlock.ppt
Module-2Deadlock.pptModule-2Deadlock.ppt
Module-2Deadlock.ppt
KAnurag2
Ìý
Deadlock in Real Time operating Systempptx
Deadlock in Real Time operating SystempptxDeadlock in Real Time operating Systempptx
Deadlock in Real Time operating Systempptx
ssuserca5764
Ìý
6. Deadlock_1640227623705.pptx
6. Deadlock_1640227623705.pptx6. Deadlock_1640227623705.pptx
6. Deadlock_1640227623705.pptx
shrijanasharma3
Ìý
14th November - Deadlock Prevention, Avoidance.ppt
14th November - Deadlock Prevention, Avoidance.ppt14th November - Deadlock Prevention, Avoidance.ppt
14th November - Deadlock Prevention, Avoidance.ppt
Unknown664473
Ìý
Module 3 Deadlocks.pptx
Module 3 Deadlocks.pptxModule 3 Deadlocks.pptx
Module 3 Deadlocks.pptx
shreesha16
Ìý
deadlocks for Engenerring for he purpose
deadlocks for Engenerring for he purposedeadlocks for Engenerring for he purpose
deadlocks for Engenerring for he purpose
adityaarya357060
Ìý
protection and security in operating systems
protection and security in operating systemsprotection and security in operating systems
protection and security in operating systems
MadhaviB6
Ìý
Lecture 8 - Memory Management. It deals with memory management
Lecture 8 - Memory Management. It deals with memory managementLecture 8 - Memory Management. It deals with memory management
Lecture 8 - Memory Management. It deals with memory management
tumaassignment
Ìý
Chapter5_Deadlock.pptx
Chapter5_Deadlock.pptxChapter5_Deadlock.pptx
Chapter5_Deadlock.pptx
DenisPriscus
Ìý
Deadlock in Operating System
Deadlock in Operating SystemDeadlock in Operating System
Deadlock in Operating System
AUST
Ìý
Mch7 deadlock
Mch7 deadlockMch7 deadlock
Mch7 deadlock
wahab13
Ìý
deadlock in OS.pptx
deadlock in OS.pptxdeadlock in OS.pptx
deadlock in OS.pptx
Monirul Islam
Ìý
Module-2Deadlock.ppt
Module-2Deadlock.pptModule-2Deadlock.ppt
Module-2Deadlock.ppt
KAnurag2
Ìý

Recently uploaded (20)

CS3451-OPERATING-SYSTEM NOTES ALL123.pdf
CS3451-OPERATING-SYSTEM NOTES ALL123.pdfCS3451-OPERATING-SYSTEM NOTES ALL123.pdf
CS3451-OPERATING-SYSTEM NOTES ALL123.pdf
PonniS7
Ìý
Multi objective genetic approach with Ranking
Multi objective genetic approach with RankingMulti objective genetic approach with Ranking
Multi objective genetic approach with Ranking
namisha18
Ìý
Env and Water Supply Engg._Dr. Hasan.pdf
Env and Water Supply Engg._Dr. Hasan.pdfEnv and Water Supply Engg._Dr. Hasan.pdf
Env and Water Supply Engg._Dr. Hasan.pdf
MahmudHasan747870
Ìý
decarbonization steel industry rev1.pptx
decarbonization steel industry rev1.pptxdecarbonization steel industry rev1.pptx
decarbonization steel industry rev1.pptx
gonzalezolabarriaped
Ìý
Integration of Additive Manufacturing (AM) with IoT : A Smart Manufacturing A...
Integration of Additive Manufacturing (AM) with IoT : A Smart Manufacturing A...Integration of Additive Manufacturing (AM) with IoT : A Smart Manufacturing A...
Integration of Additive Manufacturing (AM) with IoT : A Smart Manufacturing A...
ASHISHDESAI85
Ìý
CS3451 INTRODUCTIONN TO OS unit ONE .pdf
CS3451 INTRODUCTIONN TO OS unit ONE .pdfCS3451 INTRODUCTIONN TO OS unit ONE .pdf
CS3451 INTRODUCTIONN TO OS unit ONE .pdf
PonniS7
Ìý
autonomous vehicle project for engineering.pdf
autonomous vehicle project for engineering.pdfautonomous vehicle project for engineering.pdf
autonomous vehicle project for engineering.pdf
JyotiLohar6
Ìý
Turbocor Product and Technology Review.pdf
Turbocor Product and Technology Review.pdfTurbocor Product and Technology Review.pdf
Turbocor Product and Technology Review.pdf
Totok Sulistiyanto
Ìý
US Patented ReGenX Generator, ReGen-X Quatum Motor EV Regenerative Accelerati...
US Patented ReGenX Generator, ReGen-X Quatum Motor EV Regenerative Accelerati...US Patented ReGenX Generator, ReGen-X Quatum Motor EV Regenerative Accelerati...
US Patented ReGenX Generator, ReGen-X Quatum Motor EV Regenerative Accelerati...
Thane Heins NOBEL PRIZE WINNING ENERGY RESEARCHER
Ìý
04 MAINTENANCE OF CONCRETE PAVEMENTS.ppt
04  MAINTENANCE OF CONCRETE PAVEMENTS.ppt04  MAINTENANCE OF CONCRETE PAVEMENTS.ppt
04 MAINTENANCE OF CONCRETE PAVEMENTS.ppt
sreenath seenu
Ìý
Lecture -3 Cold water supply system.pptx
Lecture -3 Cold water supply system.pptxLecture -3 Cold water supply system.pptx
Lecture -3 Cold water supply system.pptx
rabiaatif2
Ìý
15. Smart Cities Big Data, Civic Hackers, and the Quest for a New Utopia.pdf
15. Smart Cities Big Data, Civic Hackers, and the Quest for a New Utopia.pdf15. Smart Cities Big Data, Civic Hackers, and the Quest for a New Utopia.pdf
15. Smart Cities Big Data, Civic Hackers, and the Quest for a New Utopia.pdf
NgocThang9
Ìý
Mathematics_behind_machine_learning_INT255.pptx
Mathematics_behind_machine_learning_INT255.pptxMathematics_behind_machine_learning_INT255.pptx
Mathematics_behind_machine_learning_INT255.pptx
ppkmurthy2006
Ìý
Syntax Directed Definitions Synthesized Attributes and Inherited Attributes
Syntax Directed Definitions  Synthesized Attributes  and  Inherited AttributesSyntax Directed Definitions  Synthesized Attributes  and  Inherited Attributes
Syntax Directed Definitions Synthesized Attributes and Inherited Attributes
GunjalSanjay
Ìý
Air pollution is contamination of the indoor or outdoor environment by any ch...
Air pollution is contamination of the indoor or outdoor environment by any ch...Air pollution is contamination of the indoor or outdoor environment by any ch...
Air pollution is contamination of the indoor or outdoor environment by any ch...
dhanashree78
Ìý
How to Make an RFID Door Lock System using Arduino
How to Make an RFID Door Lock System using ArduinoHow to Make an RFID Door Lock System using Arduino
How to Make an RFID Door Lock System using Arduino
CircuitDigest
Ìý
Mathematics behind machine learning INT255 INT255__Unit 3__PPT-1.pptx
Mathematics behind machine learning INT255 INT255__Unit 3__PPT-1.pptxMathematics behind machine learning INT255 INT255__Unit 3__PPT-1.pptx
Mathematics behind machine learning INT255 INT255__Unit 3__PPT-1.pptx
ppkmurthy2006
Ìý
How Engineering Model Making Brings Designs to Life.pdf
How Engineering Model Making Brings Designs to Life.pdfHow Engineering Model Making Brings Designs to Life.pdf
How Engineering Model Making Brings Designs to Life.pdf
Maadhu Creatives-Model Making Company
Ìý
Best KNow Hydrogen Fuel Production in the World The cost in USD kwh for H2
Best KNow  Hydrogen Fuel Production in the World The cost in USD kwh for H2Best KNow  Hydrogen Fuel Production in the World The cost in USD kwh for H2
Best KNow Hydrogen Fuel Production in the World The cost in USD kwh for H2
Daniel Donatelli
Ìý
How to Build a Maze Solving Robot Using Arduino
How to Build a Maze Solving Robot Using ArduinoHow to Build a Maze Solving Robot Using Arduino
How to Build a Maze Solving Robot Using Arduino
CircuitDigest
Ìý
CS3451-OPERATING-SYSTEM NOTES ALL123.pdf
CS3451-OPERATING-SYSTEM NOTES ALL123.pdfCS3451-OPERATING-SYSTEM NOTES ALL123.pdf
CS3451-OPERATING-SYSTEM NOTES ALL123.pdf
PonniS7
Ìý
Multi objective genetic approach with Ranking
Multi objective genetic approach with RankingMulti objective genetic approach with Ranking
Multi objective genetic approach with Ranking
namisha18
Ìý
Env and Water Supply Engg._Dr. Hasan.pdf
Env and Water Supply Engg._Dr. Hasan.pdfEnv and Water Supply Engg._Dr. Hasan.pdf
Env and Water Supply Engg._Dr. Hasan.pdf
MahmudHasan747870
Ìý
decarbonization steel industry rev1.pptx
decarbonization steel industry rev1.pptxdecarbonization steel industry rev1.pptx
decarbonization steel industry rev1.pptx
gonzalezolabarriaped
Ìý
Integration of Additive Manufacturing (AM) with IoT : A Smart Manufacturing A...
Integration of Additive Manufacturing (AM) with IoT : A Smart Manufacturing A...Integration of Additive Manufacturing (AM) with IoT : A Smart Manufacturing A...
Integration of Additive Manufacturing (AM) with IoT : A Smart Manufacturing A...
ASHISHDESAI85
Ìý
CS3451 INTRODUCTIONN TO OS unit ONE .pdf
CS3451 INTRODUCTIONN TO OS unit ONE .pdfCS3451 INTRODUCTIONN TO OS unit ONE .pdf
CS3451 INTRODUCTIONN TO OS unit ONE .pdf
PonniS7
Ìý
autonomous vehicle project for engineering.pdf
autonomous vehicle project for engineering.pdfautonomous vehicle project for engineering.pdf
autonomous vehicle project for engineering.pdf
JyotiLohar6
Ìý
Turbocor Product and Technology Review.pdf
Turbocor Product and Technology Review.pdfTurbocor Product and Technology Review.pdf
Turbocor Product and Technology Review.pdf
Totok Sulistiyanto
Ìý
04 MAINTENANCE OF CONCRETE PAVEMENTS.ppt
04  MAINTENANCE OF CONCRETE PAVEMENTS.ppt04  MAINTENANCE OF CONCRETE PAVEMENTS.ppt
04 MAINTENANCE OF CONCRETE PAVEMENTS.ppt
sreenath seenu
Ìý
Lecture -3 Cold water supply system.pptx
Lecture -3 Cold water supply system.pptxLecture -3 Cold water supply system.pptx
Lecture -3 Cold water supply system.pptx
rabiaatif2
Ìý
15. Smart Cities Big Data, Civic Hackers, and the Quest for a New Utopia.pdf
15. Smart Cities Big Data, Civic Hackers, and the Quest for a New Utopia.pdf15. Smart Cities Big Data, Civic Hackers, and the Quest for a New Utopia.pdf
15. Smart Cities Big Data, Civic Hackers, and the Quest for a New Utopia.pdf
NgocThang9
Ìý
Mathematics_behind_machine_learning_INT255.pptx
Mathematics_behind_machine_learning_INT255.pptxMathematics_behind_machine_learning_INT255.pptx
Mathematics_behind_machine_learning_INT255.pptx
ppkmurthy2006
Ìý
Syntax Directed Definitions Synthesized Attributes and Inherited Attributes
Syntax Directed Definitions  Synthesized Attributes  and  Inherited AttributesSyntax Directed Definitions  Synthesized Attributes  and  Inherited Attributes
Syntax Directed Definitions Synthesized Attributes and Inherited Attributes
GunjalSanjay
Ìý
Air pollution is contamination of the indoor or outdoor environment by any ch...
Air pollution is contamination of the indoor or outdoor environment by any ch...Air pollution is contamination of the indoor or outdoor environment by any ch...
Air pollution is contamination of the indoor or outdoor environment by any ch...
dhanashree78
Ìý
How to Make an RFID Door Lock System using Arduino
How to Make an RFID Door Lock System using ArduinoHow to Make an RFID Door Lock System using Arduino
How to Make an RFID Door Lock System using Arduino
CircuitDigest
Ìý
Mathematics behind machine learning INT255 INT255__Unit 3__PPT-1.pptx
Mathematics behind machine learning INT255 INT255__Unit 3__PPT-1.pptxMathematics behind machine learning INT255 INT255__Unit 3__PPT-1.pptx
Mathematics behind machine learning INT255 INT255__Unit 3__PPT-1.pptx
ppkmurthy2006
Ìý
Best KNow Hydrogen Fuel Production in the World The cost in USD kwh for H2
Best KNow  Hydrogen Fuel Production in the World The cost in USD kwh for H2Best KNow  Hydrogen Fuel Production in the World The cost in USD kwh for H2
Best KNow Hydrogen Fuel Production in the World The cost in USD kwh for H2
Daniel Donatelli
Ìý
How to Build a Maze Solving Robot Using Arduino
How to Build a Maze Solving Robot Using ArduinoHow to Build a Maze Solving Robot Using Arduino
How to Build a Maze Solving Robot Using Arduino
CircuitDigest
Ìý

Deadlock.pptx

  • 2. System Model • System consists of resources • Resource types R1, R2, . . ., Rm CPU cycles, memory space, I/O devices • Each resource type Ri has Wi instances. • Each process utilizes a resource as follows: • request • use • release
  • 3. Deadlock Characterization • Deadlock can arise if these four conditions hold simultaneously. • Mutual exclusion: only one process at a time can use a resource • Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes • No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task • Circular wait: there exists a set {P0, P1, …, Pn} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P0.
  • 4. Resource-Allocation Graph • A set of vertices V and a set of edges E. • V is partitioned into two types: • P = {P1, P2, …, Pn}, the set consisting of all the processes in the system • R = {R1, R2, …, Rm}, the set consisting of all resource types in the system • request edge – directed edge Pi ï‚® Rj • assignment edge – directed edge Rj ï‚® Pi
  • 5. Resource-Allocation Graph(Cont.) • Process • Resource Type with 4 instances • Pi requests instance of Rj • Pi is holding an instance of Rj Pi Pi Rj Rj
  • 6. Example of a Resource Allocation Graph
  • 8. Graph With A Cycle But No Deadlock
  • 9. Basic Facts • If graph contains no cycles  no deadlock • If graph contains a cycle  • if only one instance per resource type, then deadlock • if several instances per resource type, possibility of deadlock
  • 10. Methods for Handling Deadlocks • Ensure that the system will never enter a deadlock state: • Deadlock prevention • Deadlock avoidence • Allow the system to enter a deadlock state and then recover • Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX