Some Modifications of the Tournament Algorithm for the Mutual Exclusion Problem

概要

論文の詳細を見る
We propose two lockout-free (starvation-free) mutual exclusion algorithms for the asynchronous multi-writer/reader shared memory model. The first algorithm is a modification of the well-known tournament algorithm for the mutual exclusion problem. By the modification we can speed up the original algorithm. The running time of the modified algorithm from the entrance of the trying region to the entrance of the critical region is at most (n-1)c+O(nl), where n is the number of processes, l is an upper bound on the time between successive two steps of each process, and c is is an upper bound on the time that any user spends in the critical region. The second algorithm that some processes have an advantage of access to the resource over other processes.
社団法人電子情報通信学会の論文
1999-02-25