Quiz 4 Flashcards
What are the three resource types in the system model?
CPU cycles, memory space, I/O devices
In which way does each process utilizes a resource?
Request
Use
Release
What are the four conditions required to have a Deadlock?
Mutual exclusion
Hold and wait
No preemption
Circular wait
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
Each waiting process is waiting for a resource held by another process, where each of said processes are reliant on the other to give up their resource
What is a resource allocation graph?
A resource allocation graph is a graph that shows the relationship between requests and resources held between processes
If a graph contains no cycles this means what in reference to a deadlock?
No deadlock
If a graph contains a cycle this means what in reference to a deadlock?
If only one instance per resource type then deadlock
else its only a possibility
What are the two methods for preventing a deadlock state?
Deadlock prevention and Deadlock avoidance
How does Deadlock Prevention prevent deadlocks?
It invalidates on of the four necessary conditions for deadlocks
How does deadlock prevention invalidate mutual exclusion?
It makes it not required for sharable resources, this means non sharable resources can still result in a deadlock
How does deadlock prevention invalidate Hold and Wait?
It must guarantee that whenever a process requests a resource it does not hold any other resource.
How does deadlock prevention invalidate no Preemption?
If a process that is holding some resources requests another resource that cannot be immediately allocated to it then all resources currently being held are released
How does deadlock prevention invalidate circular wait?
Impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration
What is the most common type of deadlock prevention?
Invalidating circular wait
How does deadlock avoidance avoid deadlocks?
By requesting additional a priori information to be available
What is the a priori info that is typically requested for deadlock avoidance?
Each process declares the maximum number of resources of each type that it may need
What must the system be in for a process request to be verified when the system is using deadlock avoidance?
A safe state
When you have a single instance of a resource type which algorithm should you use?
A resource allocation graph
When you have multiple instances of a resource type which algorithm should you use?
The bankers algorithm
When can a request be granted for a request edge to an assignment edge?
As long as it does not result in the formation of a cycle
What are the attributes of the Banker’s Algorithm?
You have multiple instances of resources
Each process must a priori claim maximum use
When a process requests a resource it may have to wait
When a process gets all its resources it must return them in a finite amount of time
What is the overview for Deadlock detection?
Allow the system to enter the deadlock state, use a detection algorithm and then use a recovery scheme
How do deadlock detection systems recover from a deadlock?
Abort all deadlocked processes
Abort one process at a time until the deadlock cycle is eliminated
