FIT2070 Lecture Notes - Lecture 6: Mutual Exclusion, Resource Allocation, Message Queue
13 Jun 2018
School
Department
Course
Professor
L6 - Concurrency: Deadlock & Starvation
Deadlock
● Permanent blocking of processes that either compete for system resources or
communicate with each other
● No efficient solution
● Conditions:
○Mutual Exclusion
: only one process may use a resource at a time
○Hold-and-wait
: a process may hold allocated resources while awaiting
assignment of others
○No Pre-emption
: no resource can be forcible removed from a process holding
it
○Circular Wait
: a closed chain of processes exists, such that each process
holds at least one resource needed by the next process in the chain
● Dealing with it:
○Prevent
: adopt a policy that eliminates one of the conditions
○Avoid
: make the appropriate dynamic choices based on the current state of
resource allocation
○Detect
: attempt to detect the presence of deadlock and take action to recover
Resource Categories
● Reuseable: not exhausted once it's been used
○ Eg: processors, I/O channels
● Consumable: Produce it, use it, then destroyed
○ Eg: interrupts, signals, messages
Conditions for Deadlock
● Mutual Exclusion
○ Only one process may use a resource at a time
● Hold-and-Wait
○ A process may hold allocated resources while awaiting assignment of others
● No pre-emption
○ No resource forcible removed from a process holding it
○ Only practical when states of resource can be easily saved and restored later
● Circular wait
○ A closed chain of processes exists, such that each process holds at least one
resource needed by the next process in the chain
Dealing with Deadlock
● Prevent: adopt a policy that eliminates one of the conditions
○ Conservative: limit access to resources by imposing restrictions on processes
○ Indirect : prevent the occurrence of one of the three necessary conditions
○ Direct: prevent the occurrence of a circular wait
● Avoid: make the appropriate dynamic choices based on the current state of resource
allocation
Document Summary
Permanent blocking of processes that either compete for system resources or communicate with each other. Mutual exclusion : only one process may use a resource at a time. Hold-and-wait : a process may hold allocated resources while awaiting. No pre-emption : no resource can be forcible removed from a process holding. Circular wait : a closed chain of processes exists, such that each process holds at least one resource needed by the next process in the chain it. Prevent : adopt a policy that eliminates one of the conditions. Avoid : make the appropriate dynamic choices based on the current state of. Detect : attempt to detect the presence of deadlock and take action to recover resource allocation. Reuseable: not exhausted once it"s been used. Consumable: produce it, use it, then destroyed. Only one process may use a resource at a time. A process may hold allocated resources while awaiting assignment of others.
