メッセージ交換における優先度逆転とその対策
スポンサーリンク
概要
- 論文の詳細を見る
並行プログラムにおいては,複数のプロセス(タスク)が,共有変数を通して,あるいはメッセージの交換によって,互いの間の通信と同期を行なう.さらに,各プロセスには優先度(prior-ity)が付与されているとする.(プロセスの優先度は現実的なシステムにおいて重要で,実時間処理の周期的なプログラムにおいては,短い周期のプロセスに高い優先度を与えるという方式を用いることが多い.)この状況のもとで,優先度の高いプロセスが低いプロセスに待たされるという優先度逆転(priority inversion)の現象が起ることが知られている.一例は,優先度の高いプロセスAが,低いプロセスCからのメッセージを待って停止(suspend)し,Cの優先度が低いため,Aが中間の優先度のプロセスBに追い越されてしまう状況である.これに対処するための方策がいくつか提案されている.ここでは,優先度逆転がどのような状況において起こるかを解析する.さらに,新しい対策法を提案する.(なお,優先度を整数で表わすものとし,値の大きいほど優先度が高いとする.)一般に,メッセージ交換方式のうちでも,いくつか種類がある.第一に,同期(synchronous)と非同期(asynchronous)の区別があり,受付けプロセスのキューには,同期方式の場合は呼出しプロセスが,非同期方式の場合はメッセージがはいる.さらに細かい区別として,キューが,あるかないか,その長さが1か限定長か不定長かがある.現在のAda(1983年規格)は同期方式で,キューは不定長である.優先度逆転の起る状況はこれらの通信・同期の方式によって異なる.ここでは単一プロセッサ・システムの下で考える.なお,プロセスの優先度と,プロセスのスケジューリングという二つの概念は,互いに独立したものである.ここではスケジューリングはもっとも単純なもので,その時点で実行可能な,待ち状熊(blocked)のプロセスの中の,最も優先度の高いものから一つ選んで実行するというものとする.プロセスの優先度に関する議論は並行処理一般に関わり,言語からは独立である.しかしこの話はこれまで主として,現在進行中のAdaの言語改定にからんで議論されている.我々は種々のインプリメントや実験をCおよびAdaの上で行なっている.現在のAdaでは,プロセスの優先度は,静的にプラグマによって与える.Ada 9xでは,スケジューリングの方針をユーザが選択できるエうにすること,優先度を実行時に変えられるようにすることなどが検討されている.
- 一般社団法人情報処理学会の論文
- 1992-02-24
著者
関連論文
- 2. コンピュータ科学領域(J07-CS)(情報専門学科カリキュラム標準J07)
- IIOSSにおけるUMLモデルの振舞い解析
- A Mapping System from Object-Z to C++
- メッセージ交換における優先度逆転とその対策
- M-096 実際的なページ操作の共有を実現したウェブブラウジング協調システム(ユビキタス・モバイルコンピューティング,一般論文)
- 3C-5 Webアプリケーションの汎用化のための中間表現の提案と実装(Web検索支援,一般セッション,データベースとメディア,情報処理学会創立50周年記念)
- 1C-2 OpenLaszloによるXHTMLからの柔軟なFlash生成システム(コンテンツ作成支援,一般セッション,データベースとメディア)
- デジタルデータ放送コンテンツのHTMLへの変換
- IIOSSにおけるUMLモデルのインタラクティブな動的検証
- Smalltalkにおけるリソースプログラミング
- 中間表現とフレームワークを用いたWebアプリケーションのメンテナンス法の提案と評価
- あいまい性が強い文脈自由文法の枝刈りに基づく効率的な構文解析
- 4G-10 CORBA環境におけるミーティングスケジューリングシステムFlexMeet
- CORBA分散処理による会合日決定アルゴリズムと評価
- カテゴリー理論とプログラミング : カルテシアン閉カテゴリー (関数型プログラミングと計算の基礎)
- 中間表現とフレームワークを用いたWebアプリケーションのメンテナンス法の提案と評価
- 一様遅れ演算の完全性 (クローン理論と離散数学・計算機科学をめぐる代数と論理)
- M-048 FlexアプリケーションのiOS環境でのHTML5変換による実行(作業支援ほか,M分野:ビキタス・モバイルコンピューティング)