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.