Cut-off Theorems for the PV-model
share
We prove cut-off results for deadlocks and serializability of a PV-thread T run in parallel with itself: For a PV thread T which accesses a set R of resources, each with a maximal capacity κ:R→N, the PV-program T^n, where n copies of T are run in parallel, is deadlock free for all n if and only if T^M is deadlock free where M=Σ_r∈Rκ(r). This is a sharp bound: For all κ:R→N and finite R there is a thread T using these resources such that T^M has a deadlock, but T^n does not for n<M. Moreover, we prove a more general theorem: There are no deadlocks in p=T1|T2|... |Tn if and only if there are no deadlocks in T_i_1|T_i_2|... |T_i_M for any subset {i_1,...,i_M}⊂ [1:n]. For κ(r)≡ 1, T^n is serializable for all n if and only if T^2 is serializable. For general capacities, we define a local obstruction to serializability. There is no local obstruction to serializability in T^n for all n if and only if there is no local obstruction to serializability in T^M for M=Σ_r∈Rκ(r)+1. The obstructions may be found using a deadlock algorithm in T^M+1. These serializability results also have a generalization: If there are no local obstructions to serializability in any of the M-dimensional sub programs, T_i_1|T_i_2|... |T_i_M, then p is serializable.
READ FULL TEXT