マルチプロセッサオンラインスケジューリングによるハードリアルタイムタスク

マルチプロセッサ環境におけるハードリアルタイムタスクスケジューリングの問題を、問題のスケジューリングゲームの表現に基づいて論じる。先行知識なしでの最適スケジューリングは、先行関係や相互排除制約によるプレエンプションの制約がなくても、マルチプロセッサの場合には不可能であることが示される。実行時にタスクのセットを最適にスケジューリングするための十分条件が導出される。