Geometric Performance Analysis of Mutual Exclusion: The Model Solution

This paper presents an analytic solution to progress graphs used for performance analysis. It derives the exact sequence of blocking and running times experienced by two processes sharing mutually exclusive, reusable resources. A novel application of Dijkstra's progress graphs yields the complex relationship between the waiting times at each synchronization point. The problem of solving progress graphs is formulated in terms of finding the minimum solution of each of a set of Diophantine equations. An algorithm is presented to find all steady state behaviors involving blocking that emerge from any initial condition.