Studies on Mutual Exclusion Algorithm with Skipping Arbitration Tree for Shared Memory System
鈴木 健司 (0751065)
We propose an efficient mutual exclusion algorithm
with respect to remote memory reference (RMR) complexity
that measures remote accesses to shared memory.
The worst-case RMR complexity for one access to a critical section
with N processes has been proven to be Θ(log N).
Though our algorithm has the same worst case RMR complexity,
the algorithm becomes efficient with increasing the number of processes executing concurrently.
We show the efficiency using queueing theory and simulation.
Furthermore, we improve the algorithm so that the elapsed time
from some process exits its critical section
to the next waiting process enters its critical section is reduced.