M8: Deadlocks Flashcards
Deadlocks :
suppose there is a finite set of resources and there are multiple threads or processes requesting these resources.
There is a deadlock if the threads are waiting on resources held by other threads in a cycle such that none of the threads in this cycle of dependencies will be able to proceed.
Conditions for Deadlocks
○ Mutual exclusion: resources held by one process cannot be simultaneously used by another process
○ Resource preemption: when a process or thread acquires a particular resource, it holds onto the
resource until it releases it; other processes or threads cannot steal the resource
○ Hold and wait: a process can accumulate resources and does not have to grab all the resources that it needs at the same time
○ Circular waiting: circular chain of processes that are requesting resources from each other
Hierarchical allocation (deadlock prevention) :
create a policy that determines which processes can receive which resources by creating a hierarchy between the resources or between the processes
Resource allocation graph (deadlock detection)
a RAG is a tool for deadlock detection, because deadlock only occurs if the RAG has a cycle. To form the RAG, there is a node for every process and a node for every resource. If a process P currently has resource R, then we form a directed edge from R to P. If process P is requiring process R, then we form a directed edge from P to R
Wait-for-graph (deadlock detection)
shows dependencies of processes or threads that waiting on others. To form this graph, there is a node for each process or thread, and there is a directed edge from Pi to Pj, if Pi is waiting on a resource from Pj.
Checkpointing
save the state (of a process) in case of a required rollback of operations to the process
Safe-allocations (deadlock avoidance) :
an allocation state is safe if there is a sequential ordering of processes such that all the processes will be able to finish executing
Banker’s Algorithm (deadlock avoidance)
given n processes and m resources, the algorithm only grants resources to a process if it will result in a
safe allocation state
○ Req[i, j]: matrix representing the number of resources Rj requested by process Pi
○ C[i, j]: matrix representing the amount of resource Rj currently held by process Pi
○ M[i, j]: matrix representing the maximum number of resource Rj that a process Pi will ever request
○ A[j] : vector representing the number of resource Rj that are currently free
Are Semaphores and Conditional Variables functionally equivalent
They are not functionally equivalent, e.g. semaphores maintain counters, while conditional variables are mostly used with monitors.
Summarize 4 Deadlock mitigation approaches
Ignore - this sounds crazy, but actually done in practice. For example, sometimes, two append only writes can be reconciled later on, and no critical section is needed. Putting to a shopping card is an example. You can put into two carts and later merge them.
Prevent - try to write code or design locking protocol so deadlocks cannot happen.
Avoid - At runtime, try to grant/deny locks to stay away from potential deadlocks.
Recover - Allow deadlocks to happen, and when it does, deal with it (e.g. kill processes involved).
Deadlock mitigation approach when to use which
Ignore - when you know a critical section is not needed, you can use that. Many cloud systems today uses loose consistency models so that they can scale up without having to do expensive locking. The tradeoff is temporary inconsistency but it is tolerable.
Prevent - use this when the problem at hand lends itself easily to ordering of processes or resources. Not every application has a nice ordering in place.
Avoid - it is quite specific to bankers algorithm, but in general, any runtime avoidance strategy need OS monitoring support.
Recover - it is best done under two scenarios: (1) applications where rollback is easy, e.g. database transactions, (2) nuclear option to force kill processes in a deadlock cycle when all else fails (e.g. deadlock in a production system). If the software written is deadlock prone, the nuclear option only buys you some time to fix the code before the problem happens again.
If an allocation is considered safe, then we use sequential execution to finish the processes
Wrong, a safe allocation does not mean it has to be sequentially executed to avoid deadlock. But it also does not mean that it does not matter how resources are allocated to avoid Deadlock
