A CLASS OF HIGH-PERFORMANCE MAEKAWA-TYPE ALGORITHMS FOR DISTRIBUTED SYSTEMS UNDER HEAVY DEMAND

Distributed Mutual Exclusion algorithms have been mainly compared usin g the number of messages exchanged per critical section execution. In such algorithms, no attention has been paid to the serialization order of the requests. Indeed, they adopt FCFS discipline. Conversely, the insertion of priority serialization disciplines, such as Short-Job-Fir st, Head-Of-Line, Shortest-Remaining-Job-First etc., can be useful in many applications to optimize some performance indices. However, such priority disciplines are prone to starvation. The goal of this paper i s to investigate and evaluate the impact of the insertion of a priorit y discipline in Maekawa-type algorithms. Priority serialization discip lines will be inserted by means of a gated batch mechanism which avoid s starvation. In a distributed algorithm, such a mechanism needs synch ronizations among the processes. In order to highlight the usefulness of the priority based serialization discipline, we show how it can be used to improve the average response time compared to the FCFS discipl ine. The gated batch approach exhibits other advantages: algorithms ar e inherently deadlock-free and messages do not need to piggyback times tamps. We also show that, under heavy demand, algorithms using gated b atch exchange less messages than Maekawa-type algorithms per critical section excution.