Chapter 5 : Deadlock In ICS Flashcards
How are System Resource Structured in a multi-thread system?
- Systems consists of finite resources distributed among competing threads
What are resources partitioned into?
- Partitioned into types ( CPU , Network Interface )
- Each type has multiple identical instances ( 4 CPU , 2 Network Interface )
What is the typical sequence for a thread when ultilizing system resources?
- Request → Use → Release
- Thread first request for a resource, then uses it, then release the resource when it was finished
How are resource requests typically implemented in operating systems?
- Request / Release Device
- Open/ Close File
When does deadlock occurs?
- Occurs when threads wait for resources held by each other
- Situation in concurrent systems ( OS with multiple threads or processes ) where 2 or more threads are permanently blocked, waiting each other to release resources
- Example
- Two people trying to cross a narrow bridge from opposite sides and they wait at the middle, which is also a deadlock
List out 2 synchronization tools for Deadlock
- Mutex Locks
- Semaphores
What does Synchronization Tools do to avoid deadlocks?
- Properly managing resource acquistion and release is crucial to avoid deadlocks
List out 4 conditions that is necessary for deadlock to occur
- Mutual Exclusion
- Hold and Wait
- No Pre-emption
- Circular Wait
- All 4 condition must be present sumultaneously for a deadlock to occur
What is the condition for Mutual Exclusion?
- At least one resource must be non-sharable ( Only one thread can use it at a time )
What is the condition for Hold and Wait?
- A thread holding at least one resource is waiting to acquire additional resources held by other threads
What is the condition for No Pre-emption?
- Resources cannot be forcibly taken away from a thread; they must be released voluntarily
What is the condition for Circular Wait?
- A st of waiting threads exists where each thread is waiting for a resource held by the next thread in the set, forming a cycle
What is a resource allocation graph?
- A system resource-allocation graph is a directed graph used to represent the allocation of resources to threads
List out 2 components of Resource-Allocation Graph
- Vertices ( Graph Components )
- Edges ( Graph Directions )
List out 2 types of Vertices
- T
- Set of all active Threads
- R
- Set of all Resource types
List out 2 types of Edges
- Request Edge ( T → R )
- Thread Ti requests an instance of resource type Rj
- Assignment Edge ( R → T )
- Resource type Rj is allocaed to thread Ti
What are thread represented as in Resource Allocation Graph? ( Shape )
- Circles
What are Resource represented in Resource Allocation Graph ? ( Shape )
- Rectangle
How to see if there is no deadlock in the graph?
- If there is no cycle in the graph, no threads are deadlocked
How to view if there is a deadlock in the Resource Allocation Graph?
- With exactly one instance per resource type, deadlock occured
- With multiple instanced per resource type, deadlock may or may not occur
List out 3 main approached for handling deadlocks
- Ignore the Problem
- Prevent or Avoid Deadlocks
- Detect and Recover
What methods for handling deadlocks is common in most OS?
- Ignore the Problem ( Linux, Windows )
What methods for handling deadlocks relies on developers to handle deadlocks?
- Ignore the Problem
