Module 8: Deadlocks

Question 1

Deadlocks

Answer 1

suppose there is a finite set of resource 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 will be able to proceed.

Question 2

conditions for deadlock (4)

Answer 2

1. mutual exclusion
2. resource preemption
3. hold and wait
4. circular waiting

Question 3

mutual exclusion

Answer 3

resources held by one process cannot be simultaneously used by another process

Question 4

resource preemption

Answer 4

when a process or thread acquires a particular resource, it holds onto the resource until it releases it; other processes cannot steal the resource

Question 5

hold and wait

Answer 5

a process can accumulate resources and does not have to grab all the resources that it needs at the same time

Question 6

circular waiting

Answer 6

circular chain of processes that are requesting resources from each other

Question 7

hierarchical allocation (deadlock prevention)

Answer 7

create a policy that determines which processes can receive which resources by creating a hierarchy between the resources or between the processes

Question 8

resource allocation graph (deadlock detection)

Answer 8

a RAG is a tool for deadlock detection because deadlock only occurs if the RAG has a cycle (IFF). to form a 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, the we form a directed edge from P to R.

Question 9

wait-for graph (deadlock detection)

Answer 9

shows dependencies of processes or threads that are waiting on others.
to form this graph, there is a node for each process/thread, and there is a directed edge Pi to Pj if Pi is waiting on a resource from Pj.

Question 10

checkpointing

Answer 10

save the state (of a process) in case of a required rollback of operations to the process

Question 11

safe-allocations (deadlock avoidance)

Answer 11

an allocation state is safe if there is a sequential ordering of processes such that all the processes will be able to finish executing

Question 12

banker’s algorithm (deadlock avoidance)

Answer 12

given n processes and m resources, the algorithm only grants resources to a process if it will result in a safe allocation state

Re[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 amount of resource Rj that a process Pi will ever request

A[j]: vector representing the number of resources Rj that are currently free