On the Synchronizing Tools for Parallel Programs

Article type: Research Article

Authors: Müldner, Tomasz

Affiliations: Institute of Computing Machines – Warszawa

Abstract: The paper contains precise and structured definitions of the following synchronizing tools: Mutually Excluding Regions, Elementary Critical Regions and Critical Regions. Some applications of these tools are shown on the following examples: the Kung algorithm of finding a zero of a function, ticket booking system, and synchronous and asynchronous Jacobi algorithms of solving a system of linear equations. Next, the implementations of the above synchronizing tools in the formal languages of parallel programming are given. The semantics of these languages are defined on the ground of the present author’s earlier paper “On the Semantics of Parallel Programs”. The implementations are proved to be correct. The implementation of a critical region is actually an implementation of Dijkstra P and V operations on binary semaphores.

Keywords: Synchronizing tool, critical region, mutual exclusion, accessibility, passive waiting, monotonicity

DOI: 10.3233/FI-1981-4106

Journal: Fundamenta Informaticae, vol. 4, no. 1, pp. 95-133, 1981