Week 8 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. The conditions for deadlocks are as follows:
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 aprocess 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.
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
Req[i, j]
matrix representing the number of resources Rj requested by process Pi
Checkpointing
save the state (of a process) in case of a required rollback of operations to the process
C[i, j]
matrix representing the amount of resource Rj currently held by process Pi
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
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
