A Concurrency Measure

With the new advents of technology and the availability of microprocessors and minicomputers, parallel and distributed processing is gaining widespread acceptability. In such systems resources are shared among a number of processes. Accesses to the resources must be synchronized in order to guarantee proper operation of a system. In this research work, a measure, called maximal compatibility, is developed to measure the degree of concurrency (parallelism) a synchronization policy achieves. A set of accesses is considered compatible if it only contains accesses that are permitted to occur simultaneously. A policy is maximally compatible if it allows every compatible set of accesses to occur simultaneously and if the maximum number of requests is always satisfied without allowing incompatible accesses to occur simultaneously.