Vidyasankarのグループk-排他アルゴリズムの高速化

概要

論文の詳細を見る
一般化された相互排他問題にk-排他問題やグループ相互排他問題がある。後者はJoungによって提案された問題であり、これまでに様々なグループ相互排他アルゴリズムが提案されてきた。最近、Vidyasankarによって、k-排他問題とグループ相互排他問題を組み合わせた、k-グループ排他問題が提案された。グループ相互排他問題では、会議室は一つしかなく、同じ興味を持った哲学者同士は平行してその会議室で開催されている討論会に参加することができるが、興味が異なる哲学者同士が並行してその会議室に入ることはできないという制限がある。グループk-排他問題では、利用できる会議室の数はkである。Vidyasankarが考案したアルゴリズムは、多重書き込み/多重読み出し共有変数モデルモデル上で動く、Petersonのn-プロセスアルゴリズムの簡単な拡張である。本論文では、このVidyasankarのアルゴリズムの改良を行い、trying regionでの待ち時間の上限を、n(n-k)c+O(n^3(n-k))lから(n-k)c+O(n(n-k)^2)lに減らした。ここでnはプロセスの数(哲学者の数でもある)、lは二つの連続する原子ステップ間の時間の上限、cは哲学者が討論会に参加する時間の上限を表す。
2003-10-20