JP2003050709A

JP2003050709A - タスクスケジューリング方法および装置

Info

Publication number: JP2003050709A
Application number: JP2001237582A
Authority: JP
Inventors: Akiko Yagyu; 亜紀子柳生
Original assignee: Matsushita Electric Industrial Co Ltd
Current assignee: Panasonic Holdings Corp
Priority date: 2001-08-06
Filing date: 2001-08-06
Publication date: 2003-02-21

Abstract

(57)【要約】【課題】複数のタスクを備えたタスクスケジューリン
グ方法および装置において、固定された順に従って実行
タスクを決定していたため、実行完了限界時間を超えて
実行するタスクが存在していた。【解決手段】複数のタスクを管理するタスク管理部を通
じて、タイマハンドラから定期的に呼び出されるスケジ
ューラ内で、タスクごとのアクセス管理情報に基づき、
各々のタスクに要求される処理時間より求められた余裕
度でタスク実行優先順を決めてタスクを実行する。それ
らの処理を複数回繰り返すうちにそれぞれのタスクの処
理を決められた時間内で確実に完了することができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、複数のタスクを備
えたタスクスケジューリング方法および装置に関し、特
に、タスクごとにあらかじめ設定された実行完了時間内
に各々のタスクが確実に処理を完了することにより、タ
スク実行のリアルタイム性を保証するタスクスケジュー
リング方法および装置に関するものである。

【０００２】

【従来の技術】従来OSのタスクスケジューリング機構で
はタスクが実行可能状態(そのタスクを実行する準備は
整っているが、他のタスクが実行中であるために、その
タスクを実行できない状態)であるとき、固定(優先度順
など)された順に従って実行タスクを決定していた。例
えば、一定時間ごとにタスクの実行を切替えるラウンド
ロビン方式や、最も高い優先度のタスクを実行する優先
度方式がある。

【０００３】ここでは優先度方式のタスクスケジューリ
ングを紹介する。先に実行可能状態になったタスクから
順次、待ち行列に登録するタスクレディキューを優先度
ごとに備えている。次タスクの決定はタスクの優先度を
基準にして行われ、実行可能状態にあるタスクの中で最
も高い優先度を持つタスクが実行される。同一優先度の
タスクの場合には先にレディキューにキューイングされ
たタスクから処理される。そのため、高い優先度のタス
クの実行中はそれより低い優先度のタスクは全く実行さ
れない。また、低い優先度のタスクの実行中に高い優先
度のタスクが実行可能状態になると、実行中のタスクは
中断され、高い優先度のタスクが実行される。

【０００４】

【発明が解決しようとする課題】上記のように優先度の
高いタスクをCPUに割り当てるため、従来のタスクスケ
ジューリング方式では、優先度の低いタスクをCPUに割
り当てるのが容易ではなかった。このため、完了限界時
間を超えて実行するタスクが存在した。

【０００５】また、複数の開発者で設計を行う際、従来
のタスクスケジューリングでは固定(優先度順など)され
た順に従って実行タスクを決定していたため、それぞれ
の開発者が他のタスクの実行遷移を想像して設計しなけ
ればならず、デッドラインを超えないように設計するの
は困難だった。

【０００６】したがって、この発明の目的は、優先度に
依存することなく、タスクの処理を決められた時間内で
確実に完了することができ、また複数の開発者で設計を
行う際、他のタスクの実行遷移を気にすることなく設計
することができるタスクスケジューリング方法および装
置を提供することである。

【０００７】

【課題を解決するための手段】請求項１記載のタスクス
ケジューリング方法は、従来のタスクスケジューリング
方法に従って複数のタスクを一通り実行して各タスクが
有する状態値を求め、前記状態値から得たタスクごとの
実行時間に基づき、各々のタスクに要求される処理時間
より求められた余裕度でタスク実行優先順を決めて、１
〜Nの1回のループを複数回繰り返して全タスクの処理を
終了するものである。

【０００８】請求項１記載のタスクスケジューリング方
法によれば、優先度に依存することなく、過去の遷移を
もとに動的に実行タスクを決定するため、本発明のタス
クスケジューリング方式では、それぞれのタスクの処理
を決められた時間内で確実に完了することができる。

【０００９】また、複数の開発者で設計を行う際、本発
明のタスクスケジューリングでは動的に実行タスクを決
定できるため、それぞれの開発者が他のタスクの実行遷
移を気にすることなく、設計できる。また、過去の実績
をもとに自動的に処理順番を変更することによって、更
にデッドラインに余裕ができる。

【００１０】さらに、所定のソフトウェアを汎用処理装
置に供給することによって、本方法を実施でき、タスク
スケジューリング装置と同様の効果を得ることができ
る。

【００１１】請求項２記載のタスクスケジューリング方
法は、従来のスケジューリングに従って複数のタスクを
一通り実行して、一定時間ごとに各タスクが有する状態
値を管理するコード管理行程と、前記タスクごとに前記
状態値から得た実行時間を予め設定した完了限界時間と
比較して評価値を求める設定値評価行程と、前記評価値
が大きいタスクから順にCPUを割り当てる実行タスク決
定行程と、実行するタスクを選択して切替えを行うタス
ク切替え行程を含み、１〜Nの1回のループを複数回繰り
返すうちに全タスクの処理を終了するものである。

【００１２】請求項２記載のタスクスケジューリング方
法によれば、請求項１と同様な効果がある。

【００１３】請求項３記載のタスクスケジューリング方
法は、請求項２において、設定値評価行程が、評価値を
実行時間／完了限界時間で算出するものである。

【００１４】請求項３記載のタスクスケジューリング方
法によれば、請求項２と同様な効果がある。

【００１５】請求項４記載のタスクスケジューリング装
置は、従来のスケジューリングに従って複数のタスクを
一通り実行して各タスクが有する状態値を求める手段
と、前記状態値から得たタスクごとの実行時間に基づ
き、各々の前記タスクに要求される処理時間より求めら
れた余裕度でタスク実行優先順を決める手段を備えたも
のである。

【００１６】請求項４記載のタスクスケジューリング装
置によれば、請求項１と同様な効果がある。

【００１７】請求項５記載のタスクスケジューリング装
置は、従来のスケジューリングに従って複数のタスクを
一通り実行して、一定時間ごとに各タスクが有する状態
値を管理するコード管理部と、前記タスクごとに前記状
態値から求めた実行時間と予め設定した完了限界時間を
比較して評価値を求める設定値評価部と、前記評価値が
大きいタスクから順にCPUを割り当てる実行タスク決定
部と、実行するタスクを選択して切替えを行うタスク切
替え部を備えたものである。

【００１８】請求項５記載のタスクスケジューリング装
置によれば、請求項１と同様な効果がある。

【００１９】請求項６記載のタスクスケジューリング装
置は、請求項５において、設定値評価部が評価値を実行
時間／完了限界時間で算出するものである。

【００２０】請求項６記載のタスクスケジューリング装
置によれば、請求項５と同様な効果がある。

【００２１】

【発明の実施の形態】（第１の実施の形態）以下、本発
明に関わるタスクスケジューリング装置を第１の実施の
形態に基づいて説明する。

【００２２】図１は全体のブロック図である。１はスケ
ジューラであり、２のタイマハンドラによって定期的に
呼び出される。タイマハンドラ２は、一定時間ごとに発
生し、最初に設定したタイマハンドラ２のタイマ値ごと
にスケジューラ１を定期的に呼び出す。

【００２３】図２はスケジューラ１の詳細ブロック図で
ある。１１はコード管理部であり、一定時間ごとに各タ
スクが有する状態値を管理／コード化する。１２は設定
値評価部であり、タスクごとのアクセス管理情報すなわ
ちタスクごとの実行時間と設定値（完了限界時間）をタ
スクごとに比較する。１３は実行タスク決定部であり、
設定値が大きいタスクから順にＣＰＵを割り当てる。１
４はタスク切替え部であり、実行タスクの選択と切替え
を行う。１１のコード管理部の中にある状態値格納部１
１１は各タスクが有する状態値を保存する。１２の設定
値評価部の中にある設定値格納部１２１は、複数のタス
クについて各々の完了限界時間を設定値として最初に設
定し、格納しておく。

【００２４】前述のように構成された本発明の請求項４
〜６に対応する第１の実施の形態における具体的な動作
について図２を参照しながら説明する。

【００２５】１１のコード管理部は、ある時間に各タス
クが有する状態の値を受け取り、各タスクの状態値をコ
ード化した値又はその管理表を出力する。コード管理部
１１の中にある状態値格納部１１１に、ある時間に各タ
スクが有する状態の値を格納する。コード管理部１１か
ら各タスクの状態値をコード化した値又はその管理表を
受け取った設定値評価部１２は、各タスクの実行が一通
り終了していれば、タスクごとに評価をして、その結果
を出力する。設定値評価部１２の中にある設定値格納部
１２１には、最初にタスクごとの完了限界時間を設定値
に設定している。この設定値格納部１２１に格納された
値はその後も変化することはない。評価方法について
は、第２の実施の形態で詳しく述べる。設定値評価部１
２から各タスクの評価値を受け取った実行タスク決定部
１３は、次に実行するタスクのアドレスを出力する。実
行タスク決定部１３から実行タスクのアドレスを受け取
ったタスク切替え部１４は、タスクの切替えが必要であ
れば切替えを行い、次に実行するタスクのアドレスを出
力する。

【００２６】全体の流れとしては、まず従来のタスクス
ケジューリングに従って一通り複数タスクの実行をし、
図２に示す矢印のように、コード管理部１１〜タスク切
替部１４を行った後フィードバックする。次回からは新
規のタスクスケジューリングに従って図２に示す矢印の
ようにコード管理部１１〜タスク切替部１４をフィード
バックして繰り返し、タスクを実行する。「従来のタス
クスケジューリング」とは、本発明のタスクスケジュー
リング装置を実現する前のタスクスケジューリングであ
る。例えば、一定時間ごとにタスクの実行を切替えるラ
ウンドロビン方式や、最も高い優先度のタスクを実行す
る優先度方式がある。「新規のタスクスケジューリン
グ」とは、複数のタスクを一通り実行し、タスクごとの
実行時間に基づき、タスクごとに要求される完了限界時
間に対して余裕のないものから実行するタスクスケジュ
ーリングである。

【００２７】（第２の実施の形態）以下、本発明に関わ
るタスクスケジューリング方法を第２の実施の形態に基
づいて具体例を挙げて説明する。

【００２８】図３は、スケジューラのフロー図である。
ステップＳ１は、スケジュール処理であり、定められた
時間ごとに処理を行う。ステップS１１はコード管理ス
テップで、各タスク状態をコード化して管理する。ステ
ップS１２は設定値評価ステップ（行程）であり、タス
クごとに実行時間や評価値を計算する。ステップS１３
は実行タスク決定ステップ（行程）であり、次に実行す
るタスクの決定をする。ステップS１４はタスク切替え
ステップ（行程）であり、次に実行するタスクに処理の
実行権を割り当てる。ステップS１５はタイマ値設定ス
テップであり、次回のタイマハンドラが発生するように
タイマ値を設定する。タイマハンドラについては後で説
明する。ステップＳ１２０は評価モードチェックステッ
プであり、各タスクが一通り動作を終了しているかの評
価を行う。設定値評価ステップS１２内には、更にステ
ップS１２１とステップS１２２とステップS１２３が存
在する。ステップS１２１は実行時間計算ステップであ
り、タスクごとに実行時間の計算や保存を行う。ステッ
プＳ１２２は評価値計算ステップであり、タスクごとに
評価値の計算を行う。ステップS１２３はキュー挿入ス
テップであり、評価値が大きい順にタスクをキューに設
定する。ステップＳ１４０はタスク切替えチェックステ
ップであり、タスクの切替えが必要かどうかの評価を行
う。

【００２９】図４は、タイマハンドラのフロー図であ
り、タイマハンドラは一定時間ごとに発生し、最初に設
定したタイマハンドラのタイマ値ごとにスケジューラを
定期的に呼び出す。ステップS２０はタイマ値チェック
ステップであり、現在のタイマ値がゼロかどうかの評価
を行う。ステップS２１はタイマ値カウントダウンステ
ップであり、タイマ値がゼロでなければ、現在のタイマ
値をカウントダウンする。ステップS２２はスケジュー
ラ呼び出しステップであり、タイマ値がゼロになってい
れば、スケジューラを呼び出す。

【００３０】前述のようなステップで本発明の請求項１
〜３に対応する第２の実施の形態における具体的な動作
について、図３と以下のサンプルデータを参照しながら
説明する。図５は第２の実施の形態におけるタスクの実
行順を表すレディキュー図、表１は第２の実施の形態に
おけるタスク完了限界時間設定表、表２は第２の実施の
形態の従来のタスクスケジューリングにおけるタスク遷
移データ管理表、表３は第２の実施の形態におけるタス
ク評価値表、表４は第２の実施の形態の新規のタスクス
ケジューリングにおけるタスク完了限界時間設定表であ
る。

【００３１】

【表１】

【００３２】

【表２】

【００３３】

【表３】

【００３４】

【表４】

【００３５】ここで挙げる例では、３つのタスクを有
し、０．１秒（タイマ値）ごとにステップS１が呼び出
されるものとする。また表１に示すように、各タスクの
完了限界時間は、タスク１が０．５、タスク２が０．
４、タスク３が０．３とする。

【００３６】ステップS１１では各タスクが有する状態
値を記録する。ここで挙げる例では０．１秒ごとにステ
ップS１が呼び出されているので０．１秒ごとに記録し
ている。その記録の結果を表２に示す。「１」タスク実
行中、「０」はタスク未実行中であることを示してい
る。タスク１は最初の０．２秒間は実行中であり、０．
３秒後には実行権がタスク２に移され、０．４秒後に再
度実行して処理を完了している。同様にタスク２は０．
３秒後に、タスク３は０．５秒後に一通りの動作を完了
している。

【００３７】全てのタスクが一通り動作を終了していれ
ば、ステップS１２に移る。ステップS１２では、ステッ
プS１１で記録したコードを参照して、タスクごとの実
行時間と評価値を計算する。その結果を表３に示す。ス
テップS１２１にて、タスクごとに実行時間を計算す
る。実行時間は（スケジューラが呼び出されるタイミン
グ×タスク実行回数）で求める。ここで挙げる例では、
スケジューラが呼び出されるタイミングは０．１であ
る。また、タスク実行回数とは表２におけるタスクごと
の「１：タスク実行中」の数である。タスク１は０．１
秒後、０．２秒後、０．４秒後の3回実行中であったの
で、タスク１のタスク実行回数は３となる。よって、タ
スク１の実行時間は（０．１×３）で０．３となる。同
様に、タスク２とタスク３は０．１となる。次にS１２
２にて、タスクごとに評価値を計算する。評価値は（実
行時間／設定値（完了限界時間））で求める。タスク１
はS１２１で求めた実行時間が０．３で、最初に設定し
た設定値（完了限界時間）は表１より０．５なので、
（０．３／０．５）で０．６０となる。同様に、タスク
２は０．２５、タスク３は０．３３となる。次にS１２
３にて、S１２２で求めた評価値の大きいタスクから順
にキューに設定する。その結果を図４に示す。ここで挙
げた例では、評価値が一番大きいタスク１から順に設定
される。

【００３８】次にステップS１３にて、キューの先頭の
タスクを次に実行するタスクと決定する。ここで挙げた
例ではタスク１が次に実行される。

【００３９】現在実行中のタスクとこれから実行するタ
スクが違えば、ステップS１４に移り、タスクの切替え
を行う。

【００４０】最後にステップS１５にて、タイマ値の設
定を行い、次回のタイマハンドラが発生するようにす
る。ここで挙げた例ではタイマ値が０．１なので、その
値を０．１にしておく。

【００４１】以上のステップでS１を何度も繰り返し、
タスクを実行する。このタスクスケジューリング方法を
もう一度フィードバックすることによって、表２は表４
のように変化する。表４において、タスク１が０．１秒
から０．２秒間で連続して実行しているのは、タスク１
が実行できる状態であったからであり、０．２秒が経過
したときにタスク１は実行できる状態でなくなり、図５
よりタスク１の次に設定されているタスク３が実行でき
る状態になったことを示している。表１よりタスク３の
完了限界時間が０．３秒なのに対して、表２より実際の
実行時間は０．５秒で完了限界時間を超えていた。表４
では、タスク３の実際の実行時間は０．３秒で完了して
いる。よって、従来のタスクスケジューリングではタス
ク３が完了限界時間を超えて実行を終了していたのに対
して、S１を繰り返すことによって、新規タスクスケジ
ューリングでは完了限界時間内に処理を終了できた。

【００４２】こうして、１〜Nの1回のループを複数回繰
り返して全タスクの処理を終了するようにする。あるタ
スクの実際の実行時間がそのタスクの完了限界時間以内
で処理を終了できればよいので、上記の条件が全てのタ
スクについて満たされた時（それまでにスケジューリン
グを繰り返した回数がＮ）、繰り返し（スケジューリン
グのループ）は終わる。

【００４３】なお、この発明の実施の形態では、評価値
の計算式を掲示したり、実行タスクの決定を評価値の大
きい順番と固定したが、状態値から得たタスクごとの実
行時間に基づき、各々のタスクに要求される処理時間よ
り求められた余裕度でタスク実行優先順を決めるため、
処理の一部または全体を、他の計算式や他の実行タスク
決定方法で実現することは可能である。

【００４４】

【発明の効果】請求項１記載のタスクスケジューリング
方法によれば、優先度に依存することなく、過去の遷移
をもとに動的に実行タスクを決定するため、本発明のタ
スクスケジューリング方式では、それぞれのタスクの処
理を決められた時間内で確実に完了することができる。

【００４５】また、複数の開発者で設計を行う際、本発
明のタスクスケジューリングでは動的に実行タスクを決
定できるため、それぞれの開発者が他のタスクの実行遷
移を気にすることなく、設計できる。また、過去の実績
をもとに自動的に処理順番を変更することによって、更
にデッドラインに余裕ができる。

【００４６】さらに、所定のソフトウェアを汎用処理装
置に供給することによって、本方法を実施でき、タスク
スケジューリング装置と同様の効果を得ることができ
る。

【００４７】請求項２記載のタスクスケジューリング方
法によれば、請求項１と同様な効果がある。

【００４８】請求項３記載のタスクスケジューリング方
法によれば、請求項２と同様な効果がある。

【００４９】請求項４および請求項５記載のタスクスケ
ジューリング装置によれば、請求項１と同様な効果があ
る。

【００５０】請求項６記載のタスクスケジューリング装
置によれば、請求項５と同様な効果がある。

【図面の簡単な説明】

【図１】本発明の第１の実施の形態の全体のブロック図
である。

【図２】スケジューラの詳細ブロック図である。

【図３】第２の実施の形態のスケジューラのフロー図で
ある。

【図４】タイマハンドラのフロー図である。

【図５】第２の実施の形態におけるタスクの実行順を表
すレディキュー図である。

【符号の説明】

１スケジューラ１１コード管理部１２設定値評価部１３実行タスク決定部１４タスク切替え部１１１状態値格納部１２１設定値格納部２タイマハンドラＳ１スケジュール処理Ｓ１１コード管理Ｓ１２設定値評価Ｓ１３実行タスク決定Ｓ１４タスク切替えＳ１５タイマ値設定Ｓ１２０評価モードチェックＳ１２１実行時間計算Ｓ１２２評価値計算Ｓ１２３キュー挿入Ｓ１４０タスク切替えチェックＳ２０タイマ値チェックＳ２１タイマ値カウントダウンＳ２２スケジューラ呼び出し

Claims

【特許請求の範囲】

【請求項１】従来のタスクスケジューリング方法に従
って複数のタスクを一通り実行して各タスクが有する状
態値を求め、前記状態値から得たタスクごとの実行時間
に基づき、各々のタスクに要求される処理時間より求め
られた余裕度でタスク実行優先順を決めて、１〜Nの1回
のループを複数回繰り返して全タスクの処理を終了する
タスクスケジューリング方法。
【請求項２】従来のスケジューリングに従って複数の
タスクを一通り実行して、一定時間ごとに各タスクが有
する状態値を管理するコード管理行程と、前記タスクご
とに前記状態値から得た実行時間を予め設定した完了限
界時間と比較して評価値を求める設定値評価行程と、前
記評価値が大きいタスクから順にCPUを割り当てる実行
タスク決定行程と、実行するタスクを選択して切替えを
行うタスク切替え行程を含み、１〜Nの1回のループを複
数回繰り返すうちに全タスクの処理を終了するタスクス
ケジューリング方法。
【請求項３】設定値評価行程は、評価値を実行時間／
完了限界時間で算出する請求項２記載のタスクスケジュ
ーリング方法。
【請求項４】従来のスケジューリングに従って複数の
タスクを一通り実行して各タスクが有する状態値を求め
る手段と、前記状態値から得たタスクごとの実行時間に
基づき、各々の前記タスクに要求される処理時間より求
められた余裕度でタスク実行優先順を決める手段を備え
たタスクスケジューリング装置。
【請求項５】従来のスケジューリングに従って複数の
タスクを一通り実行して、一定時間ごとに各タスクが有
する状態値を管理するコード管理部と、前記タスクごと
に前記状態値から求めた実行時間と予め設定した完了限
界時間を比較して評価値を求める設定値評価部と、前記
評価値が大きいタスクから順にCPUを割り当てる実行タ
スク決定部と、実行するタスクを選択して切替えを行う
タスク切替え部を備えたタスクスケジューリング装置。
【請求項６】設定値評価部は評価値を実行時間／完了
限界時間で算出する請求項５記載のタスクスケジューリ
ング装置。