R. Baldoni et B. Ciciani, A CLASS OF HIGH-PERFORMANCE MAEKAWA-TYPE ALGORITHMS FOR DISTRIBUTED SYSTEMS UNDER HEAVY DEMAND, Distributed computing, 8(4), 1995, pp. 171-180
Citations number
18
Categorie Soggetti
Controlo Theory & Cybernetics","Computer Science Theory & Methods
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.