文献

J-GLOBAL ID：200902239491251535   整理番号：09A0887278

EDFスケジューリングを有するリアルタイムシステムに対するスケジュール可能性解析

Schedulability Analysis for Real-Time Systems with EDF Scheduling

著者 (2件)： ZHANG Fengxiang (Univ. York, York, GBR) ,  BURNS Alan (Univ. York, York, GBR)
資料名： IEEE Transactions on Computers  (IEEE Transactions on Computers)
巻： 58  号： 9  ページ： 1250-1258  発行年： 2009年09月 
JST資料番号： C0233A  ISSN： 0018-9340  CODEN： ICTOB4  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： スケジューリング理論では,リアルタイムシステムはリアルタイムタスクの集合で構成され,各タスクはジョブの無限あるいは有限のストリームで構成される。タスクの集合は固定優先権あるいは動的優先権アルゴリズムを含む多くのポリシーによりスケジュールされうる。リアルタイムシステムの成功はすべてのタスクのすべてのジョブがそれぞれのデッドライン前に実行を完了するがことが保証されることが可能かどうかに依存する。もしこれが可能ならばタスク集合はスケジュール可能であると言う。リアルタイムシステムのための最も一般的な動的優先権スケジューリングアルゴリズムはEarliest Deadline First(EDF)であり,EDFは単一プロセッサ・リアルタイムシステムにとって最適なスケジューリングアルゴリズムであることが証明されている。しかし,任意の相対的デッドラインをもつEDFスケジューリングに対する必要かつ十分なスケジュール可能性テストについての既存の結果は,規定された時間間隔においてオーバフローがあるかどうかをチェックするためにすべての絶対的デッドラインでタスク集合のプロセッサ要求を計算することを必要とする。そのためEDFの実用が厳しく制限される。本稿では,EDFスケジューリングに対する必要かつ十分なスケジュール可能性解析を提供するという問題を検討し解決した。本稿での結果は,あらゆる状況においてスケジュール可能なタスク集合に対して,また,ほとんどの状況においてスケジュール不可能なタスク集合に対して,計算時間を指数的に削減する。たとえば,従来の解析において858,331点(デッドライン)をチェックしなければならなかった16タスクのシステムは新しい解析によるとたった12点でチェックされるのでよい。

シソーラス用語： *実時間処理 ,  システム ,  *スケジューリング ,  時間制限 ,  マルチプロセッサシステム ,  多重プログラミング ,  組込みシステム

分類 (2件)： オペレーティングシステム  (JD03020J) ,  ディジタル計算機方式一般  (JC02010O)

タイトルに関連する用語 (6件)： EDF ,  スケジューリング ,  リアルタイム ,  スケジュール ,  可能性 ,  解析