マルチプロセッサにおけるスケジュール可能性を向上するための動的優先度スケジューリングアルゴリズム(スケジューリング,組込技術とネットワークに関するワークショップETNET2007)

概要

論文の詳細を見る
近年,組込み実時間システムにおいてもマルチプロセッサの利用が主流になりつつある.しかしながら,マルチプロセッサにおける実時間スケジューリングは複雑であることが知られている.一般的に,高いスケジュール可能性を実現できる洗練されたスケジューリングアルゴリズムでは多くのコンテキストスイッチやタスクマイグレーションが発生し,それらのオーバーヘッドによる実用性の低下が問題となる.一方で,単純なアルゴリズムでは高いスケジュール可能性を実現することはできない.そこで,本論文では,高いスケジュール可能性を実現できる実用的な動的優先度スケジューリングアルゴリズムを提案する.提案アルゴリズムは新しいスケジューリング方式に基づいており,従来のスケジューリング方式に基づくあらゆるアルゴリズムのスケジュール可能なシステム利用率の上限が高々50%であるのに対して,その上限を73% に向上できる.評価では,実際のスケジュールにおいても,提案アルゴリズムが既存のアルゴリズムよりも多くのタスクをスケジュール可能であることを示す.
2007-03-09