1. Review and Overview 2. Deadlocks 3. Distributed Systems Architecture 4. Theoretical Foundations 5. Distributed Mutual Exclusions

6. Agreement Protocols 7. Distributed Resource Management 8. Distributed Scheduling 9. Secutiry and Protection 10. Recovery and Fault Tolerance

I know of no more encouraging fact,
than the unquestionable ability of man
to elevate his life by conscious endeavor.

                        Henry David Thoreau

1. Introduction

   processes are blocked, waiting on events that could never happen

   different from starvation ( the associated resource is in continuous use )

   Four necessary conditions for deadlock:

   • mutual exclusion
   • hold and wait
   • no preemption
   • circular wait
   e.g. Resources are two books: Java Programming, OS Principles,
          need the two books to finish project

2. Deadlock handling strategies
   deadlock prevention, avoidance, detection, recovery

3. Resource graph for single-unit resource type

   cycle => deadlock
   deadlock => cycle
   

   

4. Graph-theoretic model
   reusable resource -- can be used again and again ( e.g. CPU, main-memory, I/O devices )
   consumable resource -- vanish as a result of its use ( e.g. messages, signals )
   Created (produced) by a process
   Destroyed (consumed) by a process
   Operations: request/receive (implies consume), produce/send
   Deadlock may occur if the receive operation can block
   Potential deadlock situations are more difficult to detect, and reproduce, by testing
   
   resource access -- can be exclusive or shared

   General resource system

   nonempty set of processes P = { P₁, P₂, P₃, ..., P_n}
   nonempty set of resources G = { R₁, R₂, R₃, ..., R_m}

   G = G_r    ∪    G_c
      reusable    consumable

   G_r    ∩    G_c = Ø    ( disjoint )

   for every reusable R_i
   t_i = |R_i| = # of units of resource of type i
       ≥ 0
   for every consumable R_i
   there exists subset R C P
   producers of R_i

   consumable resource -- concentric rectangle  
   process -- circle    O

   

   General resource graph

   a bi-partite directed graph with set of nodes:
   P = { P₁, P₂, P₃, ..., P_n}
   G = { R₁, R₂, R₃, ..., R_m}

   available units vector ( a₁, a₂, a₃, ..., a_m)
   A bi-partite graph is a graph whose nodes can be divided into two disjoint sets such that two adjacent nodes cannot come from the same set.

   diagrams

   for every reusable resource R_i:

   • # of assignment edges #( R_i, * ) ≤ t_i

   • a_i = t_i - #(R_i, * )

   • a process cannot request more than the total number of units of a resusable resource
     #(P_j, R_i ) ≤ t_i - #(R_i, P_j )

   for every consumable resource R_i

   • ( R_i, P_j ) exists iff P_j is a producer of R_i

   • a_i ≥ 0
   if #( P_i, R_j ) > a_j => p_i blocked ( more requests than available resources )

5. Reduction of Resource Graph
   If a process's resource requests can be granted, then we say that the graph can be reduced by that process
   ( i.e. the process is allowed to complete its execution and return all its resources )
   consider reusable resources only If a graph can be reduced by all the processes, then there is no deadlock.
   If a graph cannot be reduced by all the processes, the irreducible processes constitute the set of deadlock processes in the graph An example of reduction of an RAG ( Resource Allocation Graph )
   
   Example of RAG with loop but no deadlock
   

   Now if we consider both reusable and consumable resources:

   graph completely reducible => state deadlock free
   but deadlock free may not => graph completely reducible

   necessary and sufficient conditions for deadlock

   A state is an expedient state if all processes having outstanding requests cannot be granted
   

   if node only has incoming edges => sink

   
   Definition
   A knot K in a graph is a nonempty set of nodes such that for every node x in K, all nodes in K and only the nodes in K are reachable from x.
   ( all x, all y ∈ K => x → y ) AND ( all x ∈ K, some z, such that x → z => z ∈ K )

   Example

   

   Question: Any knot in the above figure?

   Theorem

   A cycle is a necessary condition for a deadlock.
   If the graph is expedient, then a knot is a sufficient condition for deadlock.

   System with only consumable resources
   claim-limited graph

   each resource has 0 available units
   it has a request edge ( p_i, R_j ) iff P_i is a consumer of R_j
   
   This claim-limited graph cannot be reduced Theorem: A consumable resource only system is deadlock free if its claim-limited graph is completely reducible.

   But a system may fail the claim-limited graph reducibility test, and still be free from deadlock. Example: Both P1 and P2 are producers and consumers.

   Process P1		Process P2
   . down ( mutex ); critical_section(); up ( mutex ); . loop		. down ( mutex ); critical_section(); up ( mutex ); . loop

6. Deadlock Avoidance requires that the maximum resource requirement of a process be known at every state during its execution ( claim of the process )
   resource is granted only if the resulting state is safe
   a state is safe if there exists at least one sequence of execution for all processes such that all of them can run to completion

   Trajectory Diagram

   A deadlock path

   
   • P2 requests R2
   • The OS grants the request of P2
   • P1 requests R1
   • The OS grants the request of P1
   • P2 requests R1
   • The OS cannot grant the request of P2, because R1 is locked.
   • P1 requests R2
   • The OS cannot grant the request of P1, because R2 is locked.
   • No further progress is possible, i.e. we have a deadlock.

   An avoidance path

   
   • P2 requests R2
   • The OS grants the request of P2
   • P1 requests R1
   • The OS postpones granting the request of P1, because it would lead to an unsafe state.
   • P2 requests R1
   • The OS grants the request of P2
   • P2 releases R1
   • The OS grants the request of P1 for R1
   • P1 requests R2
   • The OS cannot grant the request of P1, because it R2 is still locked by P2.
   • P2 releases R2
   • The OS grants the request of P1 for R2
   • P1 releases R2
   • P1 releases R1

   Question: What is the difference between a safe state and a deadlock-free state?

   How do we know a state is safe?

   • Start in the given state
   • Simulate running each process to completion, by allocating its maximum resource requirements, and then releasing all resources
   • If all processes can complete, the state is safe

   Habermann's Algorithm ( generalization of Dijkstra's Algorithm )

   Max-Avail matrix A = ( a₁ a₂ ... a_m ) where a_i = t_i = |R_i|

   Max-Claim matrix B =

   b 11 b 12 ... b 1m b 21 b 22 ... b 2m . .   .    . b n1 b n2 ... b nm

   =

   B1 B2 . Bn

   where b_ij = max number of units of Resource R_j that will ever be held by process P_i

   Allocation matrix C =

   c 11 c 12 ... c 1m c 21 c 22 ... c 2m . .   .    . c n1 c n2 ... c nm

   =

   C1 C2 . Cn

   where c_ij = number of units of Resource R_j that are currently held by process P_i
   all k, B_k ≤ A ( no process can claim more units of Resources than are available )
   C ≤ B ( no process attempts to request more resources than its maximum claim )
   
   

   n k=1

   Ck ≤ A ( never allocate more resources than are available )

   Available matrix D:
   

   D =

   ( d1

   d2

   ...

   dm )

   =

   A -

   n k=1

   Ck

   d_i = number of units of Resourc R_i available in current state
   Need matrix E:
   

   Need matrix E =

   e 11 e 12 ... e 1m e 21 e 22 ... e 2m . .   .    . e n1 e n2 ... e nm

   = B - C =

   E1 E2 . En

   Request matrix F:

   Request matrix F =

   f 11 f 12 ... f 1m f 21 f 22 ... f 2m . .   .    . f n1 f n2 ... f nm

   =

   F1 F2 . Fn

   tentative state:
   Suppose we grant all requests and see what would happen.

   D ← D - Fi	( avialable - requests )
   Ci ← Ci + Fi	( allocated + requests )
   Ei ← Ei - Fi	( need - requests )

   
   The request is granted only if the tentative state is a safe state

   Safe-State Check Algorithm

   1. Pick an unfinished process P_i such that E_i ≤ D (i.e more resources available than needed by P_i ). If no such process exists, go to Step 3.
   2. D ← D + C_i. Tag P_i as finished. Go to step 1.
   3. If all processes are tagged finished, the system state is safe; otherwise it is not safe.

   If the system is not safe, the request is blocked and the system state is reset by

   D ← D + Fi Ci ← Ci - Fi Ei ← Ei + Fi

   In addition, a process tagged with finished in step 2 is reset by:
   D ← D - C_i
   and retag P_i as unfinished.

   Example

   max-Avail A = ( 2 4 3 )

   Max-Claim B =

   1 2 2 1 2 1 1 1 1

   Allocation C =

   1 2 0 0 1 1 1 0 1

   Available D = ( 0 1 1 )
   

   Need E =

   0 0 2 1 1 0 0 1 0

   
   Suppose process P₁ makes a request F₁ = ( 0 0 1 )

   The tentative state would be:

   Available D = ( 0 1 0 )
   

   Allication C =

   1 2 1 0 1 1 1 0 1

   Need E =

   0 0 1 1 1 0 0 1 0

   In this state, P₃ can complete because E₃ ≤ D returning ( 1 0 1 ) to the available pool of resources,

   D = ( 1 1 1 )

   Thus, the outstanding needs of both P₁ and P₂ can be satisfied and consequently the tentative state resulting from the request P₁ is safe and the request F₁ of P₁ can be granted.