改良ベーカリーアルゴリズムのチケット範囲

概要

論文の詳細を見る
相互排他問題を解くベーカリーアルゴリズムで使用するチケットの大きさを有界にするため、チケット番号をmを法とする数にする。この簡単な修正版において、少なくとも1人のユーザが資源の使用を試みているか、資源を使用中であるかが常に観察できるという条件のもとで、最後に発行されたチケットを見分けるためには、mは少なくとも4n-5であればよいことを示した。ここで、nはユーザの数である。この条件を除去するために、各ユーザに対応するプロセスの他に、余分のプロセス1個を使用する。このようにして、使用チケットの大きさが有界な相互排他アルゴリズムを設計する。このアルゴリズムはベーカリーアルゴリズムと同様に、単一書き込み/多重読みだしの非同期共有メモリーモデルの上で動作し、ロックアウトフリー、ファーストインファーストサーヴドの性質を持つ。このアルゴリズムによる資源使用の待時間の上限は(n-1)c+O(nl)で、共有メモリーの大きさは(n+1)(1+⌈log(4n)⌈)ビットである。ここで、cは1人のユーザが資源を使用する時間の上限、lは2つの連続するアトミックステップの間の時間の上限である。
社団法人電子情報通信学会の論文
2002-09-23