@techreport{oai:ipsj.ixsq.nii.ac.jp:00061009, author = {鈴木, 健司 and 井上, 美智子 and 藤原, 秀雄 and Tsuyoshi, Suzuki and Michiko, Inoue and Hideo, Fujiwara}, issue = {9(2009-AL-122)}, month = {Jan}, note = {共有メモリへの遠隔操作の回数を評価尺度とする RMR (Remote Memory Reference) 計算量に関して効率の良い相互排除アルゴリズムを提案する.相互排除の最悪 RMR 計算量は 1 回の共有資源の獲得のためにプロセスが行う RMR の回数である. N プロセス相互排除アルゴリズムの最悪 RMR 計算量は O (log N) であることが知られている.我々は最悪時計算量が O (logN)であるが,多くのプロセスが同時に資源獲得を行う場合に効率の良いアルゴリズムを提案し,その効率性を待ち行列理論とシミュレーションの二つの手法を用いて示す.さらにアルゴリズムを計算処理時間に関して改善を行う., 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 O (logN). 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 wanting process enters its critical section is reduced.}, title = {共有メモリシステムにおける調停木スキップ相互排除アルゴリズム}, year = {2009} }