Geometric Performance Analysis of Mutual Exclusion: The Model

Abstract

This paper is motivated by the need to better understand parallel program run-time behavior. The paper first formally describes a general model of program execution based on Djkstra's progress graphs. The paper then defines a special case of the model representing two cyclic processes sharing mutually exclusive, reusable resources. Processes synchronize through semaphore operations that are not embedded in conditionally executed code segments. Model parameters are the times at which each semaphore operation completes and the independently derived, constant execution time required by each process between points of completion of semaphore operations.