共有メモリシステムにおける調停木スキップ相互排除アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2009-01-23
• タイトル: 共有メモリシステムにおける調停木スキップ相互排除アルゴリズム
• タイトル / 言語: en
• タイトル: Mutual Exclusion Algorithm with Skipping Arbitration Tree
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 奈良先端科学技術大学院大学情報科学研究科
• 著者所属: 奈良先端科学技術大学院大学情報科学研究科
• 著者所属: 奈良先端科学技術大学院大学情報科学研究科
• 著者所属(英): en
• 著者所属(英): Nara Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Nara Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Nara Institute of Science and Technology
• 著者名: 鈴木, 健司; 井上, 美智子; 藤原, 秀雄
• 著者名(英): Tsuyoshi, Suzuki; Michiko, Inoue; Hideo, Fujiwara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 共有メモリへの遠隔操作の回数を評価尺度とする RMR (Remote Memory Reference) 計算量に関して効率の良い相互排除アルゴリズムを提案する．相互排除の最悪 RMR 計算量は 1 回の共有資源の獲得のためにプロセスが行う RMR の回数である． N プロセス相互排除アルゴリズムの最悪 RMR 計算量は O (log N) であることが知られている．我々は最悪時計算量が O (logN)であるが，多くのプロセスが同時に資源獲得を行う場合に効率の良いアルゴリズムを提案し，その効率性を待ち行列理論とシミュレーションの二つの手法を用いて示す．さらにアルゴリズムを計算処理時間に関して改善を行う．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2009, 号 9(2009-AL-122), p. 9-16, 発行日 2009-01-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会