周期的リアルタイムタスクのRate Monotonic法によるスケジュール可能性判定問題について

• 真鍋 義文

  NTT基礎研究所

• 青柳 滋己

  NTT基礎研究所

書誌事項

タイトル別名

• A Feasibility Decision Algorithm for Rate Monotonic Scheduling of Periodic Real-Time Tasks

抄録

リアルタイムシステムでは各タスクに期限が存在し、タスク処理は期限までに終了しなければいけないため、タスクのスケジュールは重要な問題である。Rate Monotonic法は周期的リアルタイムタスクの最も一般的なスケジュール法である。タスクの組が与えられた時に、Rate Monotonic法ですべてのタスクが期限までに実行できるか否かを判定する問題を考察する。本稿では実行可能であるための新たな必要十分条件を示し、その条件に基づく判定アルゴリズムを与える。このアルゴリズムの時間計算量はタスク数のみに依存する。このアルゴリズムは、Rate Monotonic法を拡張したInverse Deadline法に対しても適用可能である。
The rate monotonic scheduling algorithm is the most commonly used task scheduling algorithm for periodic real-time task systems, in which each task has a deadline by which execution must be complete.This paper discusses feasibility decision for a given real-time task system by the rate monotonic scheduling algorithm. It presents a new necessary and sufficient condition for a given task system to be feasible,and a new feasibility decision algorithm based on that condition.The time complexity of this algorithm depends solely on the number of tasks.This algorithm can be applied to the inverse-deadline scheduling algorithm,which is an extension of the rate monotonic scheduling algorithm.

収録刊行物

• 電子情報通信学会技術研究報告. COMP, コンピュテーション

  電子情報通信学会技術研究報告. COMP, コンピュテーション 94 (181), 63-72, 1994-07-25

  一般社団法人電子情報通信学会

キーワード

• リアルタイムシステム
• 周期的タスク
• スケジューリング
• Rate Monotonic法
• 実行可 能性
• 判定アルゴリズム

詳細情報

• CRID: 1570291227422832896
• NII論文ID: 110003191703
• NII書誌ID: AN10013152
• 本文言語コード: en
• データソース種別:
  • CiNii Articles