著者

高村 政孝 五十嵐 善英

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.101, no.376, pp.61-68, 2001-10-12

被引用文献数

1

---

本論文ではsingle-writer/multi-reader共有変数モデル上で相互排他問題を解く2つのアルゴリズム提案する.これらのアルゴリズムはBakery algorithmの改良である.まず, ある特殊な条件が成り立っている元で, 有限サイズの共有変数で相互排他が実現されるようBakery algorithmを変更する.次に, この特殊な条件を取り除くために, どのユーザーにも属さない追加のプロセスを用いたアルゴリズムを提案する.この追加のプロセスを用いた相互排他アルゴリズムはlock-out-freeを満足する.さらに, このアルゴリズムの共有変数のサイズを減らすよう改良したアルゴリズムも提案する.これらのアルゴリズムの時間計算量は, ユーザーの数をn, atomic stepの時間の上限をl, ユーザーが資源を利用する時間の上限をcとすると, いずれも(n-1)c+Ο(nl)である.共有変数のサイズは, 最初のアルゴリズムが(n+1)(1+⌈log(n+2)⌉bits, 二つ目のアルゴリズムがn(1+⌈log(n+1)⌉)+1bitsである.