著者

三浦 真 疋田 輝雄

雑誌

全国大会講演論文集

巻号頁・発行日

vol.44, pp.83-84, 1992-02-24

---

並行プログラムにおいては,複数のプロセス(タスク)が,共有変数を通して,あるいはメッセージの交換によって,互いの間の通信と同期を行なう.さらに,各プロセスには優先度(prior-ity)が付与されているとする.(プロセスの優先度は現実的なシステムにおいて重要で,実時間処理の周期的なプログラムにおいては,短い周期のプロセスに高い優先度を与えるという方式を用いることが多い.)この状況のもとで,優先度の高いプロセスが低いプロセスに待たされるという優先度逆転(priority inversion)の現象が起ることが知られている.一例は,優先度の高いプロセスAが,低いプロセスCからのメッセージを待って停止(suspend)し,Cの優先度が低いため,Aが中間の優先度のプロセスBに追い越されてしまう状況である.これに対処するための方策がいくつか提案されている.ここでは,優先度逆転がどのような状況において起こるかを解析する.さらに,新しい対策法を提案する.(なお,優先度を整数で表わすものとし,値の大きいほど優先度が高いとする.)一般に,メッセージ交換方式のうちでも,いくつか種類がある.第一に,同期(synchronous)と非同期(asynchronous)の区別があり,受付けプロセスのキューには,同期方式の場合は呼出しプロセスが,非同期方式の場合はメッセージがはいる.さらに細かい区別として,キューが,あるかないか,その長さが1か限定長か不定長かがある.現在のAda(1983年規格)は同期方式で,キューは不定長である.優先度逆転の起る状況はこれらの通信・同期の方式によって異なる.ここでは単一プロセッサ・システムの下で考える.なお,プロセスの優先度と,プロセスのスケジューリングという二つの概念は,互いに独立したものである.ここではスケジューリングはもっとも単純なもので,その時点で実行可能な,待ち状熊(blocked)のプロセスの中の,最も優先度の高いものから一つ選んで実行するというものとする.プロセスの優先度に関する議論は並行処理一般に関わり,言語からは独立である.しかしこの話はこれまで主として,現在進行中のAdaの言語改定にからんで議論されている.我々は種々のインプリメントや実験をCおよびAdaの上で行なっている.現在のAdaでは,プロセスの優先度は,静的にプラグマによって与える.Ada 9xでは,スケジューリングの方針をユーザが選択できるエうにすること,優先度を実行時に変えられるようにすることなどが検討されている.