Speedup of lockout-free mutual exclusion algorithms
Y. Igarashi, Y. Nishitani · 2003
We propose three lockout-free mutual exclusion algorithms for the asynchronous multi-writer/reader shared memory model. The first two algorithms are modifications of the n-process algorithm by G.L. Peterson (1981), and the third algorithm is a modification of the tournament algorithm by G.L. Peterson and M.J. Fischer (1977). The correctness and efficiency of these modified algorithms are shown. By these modifications we can speed up the original algorithms. The running times for the trying regions of the first algorithm and the second algorithm are (2n-3)c+O(n/sup 3/l) and (n-1)c+O(n/sup 3/l), respectively, where n is the number of processes, l is an upper bound on the time between successive two steps, and c is an upper bound on the time that any user spends in the critical region. The running time for the trying region of the third algorithm is (n-1)c+O(nl).