## Deadlocks and dihomotopy in mutual exclusion models

Martin Raussen

Department of mathematical sciences Aalborg Universitet

MSRI-seminar, 9.10.2006

## Mutual exclusion

*Mutual exclusion occurs, when n processes P*_{i}*compete for m*
*resources S** _{j}*.

P P

1 2

R 1

P3

R2

*Only k processes can be served at any given time.*

Semaphores!

Semantics: A processor has to lock a resource and relinquish the lock later on!

**Description/abstraction P*** _{i}* :

*. . .PR*

_{j}*. . .VR*

_{j}*. . .*(Dijkstra)

## Schedules in ”progress graphs”

The Swiss flag example

Unsafe

Un- reachable

(0,0)

Pa Pb Vb Va Pb

Pa Va Vb T2

T1 (1,1)

**-**
**6**

*P*_{1}:*P*_{a}*P*_{b}*V*_{b}*V*_{a}*P*_{2}:*P*_{b}*P*_{a}*V*_{a}*V*_{b}

Executions aredirectedpathsavoiding a*forbidden region F*.
Deadlocks: no directed path with that source.

Unsafe regions: Every inextendible dipath ends in a deadlock.

## Deadlocks in higher dimensions

A B

C a

b c

A=Pa.Pb.Va.Vb B=Pb.Pc.Vb.Vc C=Pc.Pa.Vc.Va

Higher di- mensional complex with a forbidden region consist- ing of isothetic hypercubes and an unsafe region.

## Geometric deadlock detection 1

Deadlocks may occur at the

lower cornersofintersectionsof*n*hypercubes –
unless contained in the interior of the forbidden region.

Unsafe

Un- reachable

(0,0)

Pa Pb Vb Va Pb

Pa Va Vb T2

T1 (1,1)

**-**
**6**

Dimension 3: The front right upper corner of a room is the intersection of 3 (forbidden) walls.

## Geometric deadlock detection 2

published in CONCUR’98 proceedings

Theorem

* A (non-final) point x∈X* =

*I*

^{n}*\int*(

*F*)

*is adeadlockif and only if*

*•* *there is ann-elementindex set J* =*{i*_{1}*, . . . ,i**n**}with*
*R** ^{J}* =

*R*

^{i}^{1}

*∩ · · · ∩R*

^{i}

^{n}*=∅*

*•* **x**=**a*** ^{J}* = (

*a*

^{J}_{1}

*, . . . ,a*

^{J}*) =*

_{n}*min R*

^{J}*∈int*(

*F*)

*.*

Remark*The coordinate a*^{J}* _{j}* is thenmaximum

*of the j-th*

coordinates of the lower corners of the participating hypercubes
*R** ^{i}* – easy to find algorithmically.

(Mininal)unreachablepoints can be found analogously.

Unsafe regions?

## An algorithm detecting unsafe regions

published in CONCUR’98 proceedings, illustrations courtesy Eric Goubault

From the PV-program

*Compute the forbidden region F* *⊂I** ^{n}*,

*The intersections R** ^{J}* of

*n forbidden hyperrectangles*

*R*

*= [*

^{i}*a*

^{i}_{1}

*,b*

^{i}_{1}]

*× · · ·*[

*a*

^{i}

_{n}*,b*

_{n}*]create deadlocks.*

^{i} Forbidsuccessively the hyperrectangles[˜*x,x*], where
*x* =*minJ*= (max_{i}*a*^{i}_{1}*,· · ·*max_{i}*a*^{i}* _{n}*)and

˜

*x* = (2nd max_{i}*a*_{1}^{i}*,· · ·* *,*2nd max_{i}*a*^{i}* _{n}*)
secondary deadlocks, unsafe regions.

## Dipaths and dihomotopy

combinatorial and geometric

Definition *Two dipaths f*_{0}*,f*_{1}:*I→ X from a to b are*

dihomotopic*if there is a one-parameter family H* :*I×I→X*
*such that H** _{t}* =

*H*(

*t,−)*is adipath

*for every t, H*

_{0}=

*f*

_{0}

*,H*

_{1}=

*f*

_{1},

*H*(0

*,s*) =

*(1*

**a, and H***,s*) =

**b.**

DefinitionCombinatorial dipath: Concatenation of dipaths in
*X* *⊂I** ^{n}*parallel to one of the axes.

Elementary dihomotopy: *·* ^{//}*·*

*·*

OO //*·*

OO

Combinatorial dihomotopy: Congruence relation generated by elementary dihomotopies.

Theorem

*(L. Fajstrup, 05): In a cubical complex, combinatorial*
*dipaths/combinatorial dihomotopydipaths/dihomotopy.*

## Dihomotopy is finer than homotopy with fixed endpoints

Example: Two wedges in the forbidden region

All dipaths from minimum to maximum are homotopic.

A dipath through the “hole” isnot dihomotopic to a dipath on the boundary.

## Why bother? Database management as an example

Serial and serializable executions

An execution is

serial if only one proces is accessing databases at a given time;

*P*_{i}_{1}*.P*_{i}_{2}*.· · ·.P*_{i}_{n}

serializable if the result of a schedule is always equivalent to a serial exedution (safe).

Correctness is

often easy to check for serial executions

difficult or impossible to check for general executions Serializable executions have advantages:

Check correctness for serial executions only!

Can be muchfasterthan a serial execution!

## 2-phase locking protocols

Which schedules (protocols) are known to be serializable?

Data engineers often use2-phase locked protocols.

*For those, every proces P** _{i}* should

first do all the lock operations

then the computations

finally all the unlock operations

*PPP. . .PVVV. . .V*

## 2-phase locking is safe

Theorem

*Every diapth in a 2-phase locking protocol is serializable (thus*

*“safe” and correct).*

Proofsusing

graph theory came first, but were quite complicated topological methods more transparent

J. Gunawardena (1994)

L. Fajstrup, E. Goubault, M.R. (1999, finally published in TCS, 2006)

IdeaFor a2-phase locked protocol, the forbidden region F has aparticular geometric structure(“blockwise starshaped”).

This property can be used to prove geometrically, that every
*dipath in X is dihomotopic to a dipath*on the edges*of I** ^{n}* –
modelling a serial execution.

ConclusionEvery execution is equivalent to a serial execution!

## A single hypercube gives rise to nontrivial dihomotopy

but only between points in specified regions

*In dim. n: n−*2 coordinates “forbidden”, 2 coordinates ”free”.

The two dipaths pass through forbidden intervals in reverse orders.

Nontrivial dihomotopy only “persists” if source and target live in the dotted boxes.

Conditions for persistent nontrivial dihomotopy?

## Projections and forbidden regions

A tool linking to the deadlock situation

Projections to the first(*n−*1), resp. last coordinate:

*π** ^{n}* :

**R**

^{n}*→*

**R**

^{n}

^{−}^{1}

*, π*

*n*:

**R**

^{n}*→*

**R**

*,A →A*

*=*

^{n}*π*

*(*

^{n}*A*),

*A*

*n*=

*π*

*n*(

*A*)

*A*= (

*a*1

*,b*1)

*× · · · ×*(

*a*

*n*

*−*1

*,b*

*n*

*−*1)× (

*a*

*n*

*,b*

*n*)

*A** ^{n}*= (

*a*

_{1}

*,b*

_{1})

*× · · · ×*(

*a*

_{n}

_{−}_{1}

*,b*

_{n}

_{−}_{1})

*A** _{n}*= (

*a*

_{n}*,b*

*)*

_{n}What happens to the forbidden region under projection?

*New forbidden region F*^{n}*⊂I*^{n}^{−}^{1}, new state space
*X*¯ *⊂I*^{n}^{−}^{1}*,* *X*¯ *=X** ^{n}*!

*X* =*I*^{n}*\F* *⊂I*^{n}*X*¯ =*I*^{n}^{−}^{1}*\F*^{n}*⊂I*^{n}^{−}^{1}

**x***∈I*^{n}^{−}^{1}forbidden*⇔***x***∈F*^{n}*⇔∃x*_{n}*∈I with*(**x***,x** _{n}*)

*∈F .*

*X can have deadlocks even if X is deadlockfree.*¯

## Forbidden region and projection

*from n**−*1 intersecting hyperrectangles

*J* = (*i*_{1}*, . . . ,i*_{n}_{−}_{1}),*R** _{J}* =

_{n}

_{−}_{1}

1 *R** ^{i}* = (

*a*

_{1}

*,b*

_{1})

*× · · · × ×(a*

_{n}*,b*

*)the*

_{n}*intersection of n−*1 forbidden hyperrectangles.

*R** _{J}* = (

*a*

_{1}

*,b*

_{1})

*× · · · ×*(

*a*

_{n}

_{−}_{1}

*,b*

_{n}

_{−}_{1})× (

*a*

_{n}*,b*

*)*

_{n}*R*

_{J}*= (*

^{n}*a*

_{1}

*,b*

_{1})

*× · · · ×*(

*a*

_{n}

_{−}_{1}

*,b*

_{n}

_{−}_{1})

*R*_{J}_{,}* _{n}*= (

*a*

*n*

*,b*

*n*)

*R*_{J}^{n}*⊂I n−*1 gives rise to thedeadlock(*a*_{1}*, . . . ,a*_{n}_{−}_{1})*∈X and*¯
(*b*_{1}*, . . . ,b*_{n}_{−}_{1})isunreachable.

## Nontrivial dihomotopy

*from n**−*1 intersecting hyperrectangles

**x***Us*(π*R** ^{J}*)

*πR*

^{J}*a*

*n*

*b*_{n}**R** **y**

**R**^{n}^{−}^{1}
*R*^{J}

*D*_{1}
*D*_{2}

For a dipath*α*= (α^{n}*, α**n*)**from x***∈Us*(*R*_{J}* ^{n}*)either

*α*^{n}*waits in Us*(*R*_{n}* ^{J}*)until

*α*

*n*(

*t*)

*>b*

*n*

*(through D*

_{2}) or

*α*^{n}*passes R** ^{J}* before

*α*

*n*(

*t*)

*>a*

_{n}*(through D*

_{1})

A dihomotopyrespects this choice: D_{1}*,D*_{2}disconnected!

## Nontrivial dihomotopy from source to target

The double wedge example

Ur Us

C

0

**1**

The dipath through the hole isnot dihomotopic to a dipath on the boundary:

*The projection to I*^{n}^{−}^{1}exhibits intersection of an unsafe and
unreachable region that is disconnected from source and
target.

**Nontrivial dihomotopy from source 0 to target 1**

fortwoarrangements of*n−*1pairwise intersecting
hyperrectangles:

*I* = (*i*_{1}*, . . . ,i*_{n}_{−}_{1}) *R** ^{I}* = (

*a*

_{1}

*,b*

_{1})

*× · · · ×*(

*a*

_{n}*,b*

*)*

_{n}*J* = (*j*_{1}*, . . . ,j*_{n}_{−}_{1}) *R** ^{J}* = (

*c*

_{1}

*,d*

_{1})

*× · · · ×*(

*c*

_{n}*,d*

*);*

_{n}*a*

_{n}*<d*

*(*

_{n}*c*

_{1}

*, . . . ,c*

_{n}

_{−}_{1})deadlock in

*X ,*¯ (

*b*

_{1}

*, . . . ,b*

_{n}

_{−}_{1})unreachable in

*X .*¯ Theorem

*Let C* =*Us*(*R*_{I}* ^{n}*)

*∩Us*(

*R*

^{n}*)*

_{J}

**be disconnected from 0 and 1.***Ifα∈P*_{1}(*X*)(**0***,***1**)*has property*

(P) *a*_{n}*≤α**n*(*t*)*≤d*_{n}*⇒α** ^{n}*(

*t*)

*∈C*

*then so has everyβ∈P*_{1}(*X*)(**0***,***1**)*dihomotopic toα.*

Proofuses directed van Kampen theorem (M. Grandis, ’03)
Corollary 1A dipath*α∈P*_{1}(*X*)(**0***,***1**)satisfying (P) is not
serializable (dihomotopic to a dipath on the 1-skeleton).

Corollary 2*π*1(*X*)(**0***,***1**)isnottrivial.

## Trivial dihomotopy for other intersection patterns 1

Theorem

*Assume that the forbidden region F* =

*R*^{i}*satisfies:*

*R** ^{J}* =

*i**∈**J**R** ^{i}* =

*∅for all index sets J with|J| ≥n−1.*

*Then any two dipaths in the model space X* =*I*^{n}*\F* *⊂I*^{n}*from*
**0 to 1 are dihomotopic:***π*1(*X*)(**0***,***1**)*is trivial.*

Tool: *σ**i**: one edge step along x** _{i}*-axis. Everycombinatorial
dipathcan be written in the form

*σ*

*i*

*L*

*∗ · · · ∗σ*

*i*2

*∗σ*

*i*1.

*For a vertex x* *∈X , let Out*(*x*) =*{σ**i*_{1}*,· · ·* *, σ**i*_{k}*} ⊆ {σ*1*,· · ·* *, σ**n**}*
*denote the set of edges with source x .*

Proposition. *Assume that X has no deadlocks and that for*
*every vertex x* *∈X and all directed edgesσ**i*1*, σ**i*2 *∈Out*(*x*):

1. *σ**i*1*, σ**i*2 homotopy commute^{1}or

2. *∃j* *=i*_{1}*,i*_{2}:*σ**j* homotopy commutes with both*σ**i*1 and*σ**i*2.
Then*π*1(*X*)(**0***,***1**)is trivial.

1Exists a 2-cube filling*σ**i*_{1}*∗**σ**i*_{2}*, σ**i*_{2}*∗**σ**i*_{1}

## Trivial dihomotopy for other intersection patterns 2

Proofby induction on the “length” of dipaths.

Why is the condition on homotopy commutativity satisfied for
*forbidden regions in which at most n−*2 hyperrectangles
intersect nontrivially?

**Look at the “local future” of a vertex x. It is always of the form**

*∂*_{−}*I*^{j}^{1}*× · · · ×∂*_{−}*I*^{j}^{k}*×I*^{n}^{−}^{j}*,* *j*:=*j*_{1}+*· · ·*+*j** _{k}*.

*In our case k*

*≤n−*2. Hence either

*j* *<n (factorI) or*

*at least one j*_{i}*≥*3 (lower boundary of a 3 cube) or

*there exist i*_{1}*=i*_{2}*with j*_{i}_{1} =*j*_{i}_{2} =*2 (product of two Ls*
containing enough rectangles).