Synchronization Efficiency

Candidate: Borg,Anita

Abstract

A generally applicable methodology for the analysis of synchronization efficiency is introduced. It is based upon the assumption that synchronization is required because of the need to control the use of resources by concurrent processes. Two aspects of synchronization efficiency are identified: Time efficiency, and accuracy efficiency. Time efficiency provides a measure of the use of resources during synchronization. Accuracy efficiency specifies how well a solution to a synchronization problem supports the rules of a problem. The methodology involves the simulation of solutions to synchronization problems as greater and greater implementation detail is specified. The assumptions made concerning the execution times of operations, especially synchronization operations, is seen to be crucial to the correct analysis of synchronization efficiency. It is argued that the only reasonable assumption for the execution times of synchronization operations, when their implementation is left unspecified, is that they execute instantaneously. However, it is also shown that this assumption must be used with care in order to avoid erroneous conclusions. The methodology is applied to PV, Monitor, and ADA solutions to the mutual exclusion, reader-writer, and consumer-producer problems. The PV solutions were usually the most efficient, while the ADA solutions were found to be the least efficient. It is also shown that no single characteristic of a solution determines its efficiency. However, the primary characteristics affecting efficiency are shown to be: (1) The execution time required for synchronization. (2) The rules for execution of the synchronizating computations. (3) The amount of competition among processes. (4) The amount and cost of process switching required during synchronization. It is the interaction of these factors which determine synchronization efficiency.