Deadlocks Flashcards
A deadlock is a set of __________ each holding a resource and waiting to acquire a resource held by another _______
processes, process
What are 2 reasons why deadlocks occur?
- Complex dependencies
- Encapsulation
Complex dependencies can cause deadlocks because it’s easy to create _________ _____________
circular dependencies
____________ can cause deadlocks because each module hides its implementation details without coordinating with other modules
Encapsulation
What four conditions if held simultaneously MAY cause a deadlock?
- Mutual exclusion
- Hold and wait
- No preemption
- Circular Wait
What is mutual exclusion?
Threads requiring exclusive control of resources
What is hold and wait?
hreads are already holding resources but also are waiting for additional resources being held by other threads
What does no preemption mean?
resource released only voluntarily by the thread holding it
What is circular wait?
here exists a set {P0, P1, …, Pn} of processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for P2, …, Pn–1 is waiting Pn, and Pn is waiting for P0
What are 3 methods to avoid or recover from deadlocks?
- Prevention (ensure one condition does not hold)
- Avoidance
- Detection and recovery
To prevent circular wait, we enforce that each thread requests resources in a ________ _______. We impose a _______ ________ on all resource types
consistent order, total ordering
To prevent hold and wait, we acquire ____ locks ___________
all, atomically
A disadvantage in preventing hold and wait is that we must know which locks to acquire in ________ and it decreases _________
advance, concurrency
To prevent no preemption, we make processes that fail to get a lock _____ __ all already-holding lock and _______
give up, retry
To prevent no preemption, we can specify a _______ for a thread if it does not get all its locks
timeout
Preventing no preemption can cause a __________, where all threads are __________ steps
livelock, repeating
To solve a livelock, we can add random ______ between retries
delays
To prevent mutual exclusion, we can use ________ algorithms using ______ instructions
lock-free, atomic
Lock-free algorithms may achieve high ________ and prevent creation of ________, but are very ____________, as threads must handle data races explicitly
performance, deadlocks, error-prone
Avoiding deadlocks by scheduling works in 2 steps. What are they?
- Know which locks might be requested by which threads
2. Schedule threads in a way that guarantees no deadlocks can occur
A disadvantage of avoiding deadlock by scheduling is that it requires _______ _______ about all participating threads and resources
global knowledge
Review deadlock avoidance slides
Review deadlock avoidance slides
A disadvantage of avoiding deadlock by scheduling is that it can possibly _______ the time needed to complete jobs
increase
A _______ and ________ solution allows deadlocks to occur, then take actions to resolve it
detect, recover
In detect and recover, a deadlock _______ runs periodically
detector
In detect and recover, a possible deadlock detector maintains a _____ that summarizes _________ and check for _______
graph, dependencies, cycles
In detect and recover, once a deadlock is detected, the system can _____ system or ______ some threads/victims
restart, preempt
Detect and recover is common in _______ _______
database systems
