JP2014225137A - タスクスケジューラ，マイクロプロセッサ及びタスクスケジューリング方法 - Google Patents

Abstract

【課題】リアルタイム処理性能を低下させることなく、大きな回路面積を必要とせず現実的な処理時間でマルチタスクのスケジューリングを行う。
【解決手段】タスクスケジューラ１は、複数のタスクの実行状態を共通カウンタ２が計時する時刻で管理し、各タスクについて次式により余裕消失時刻Ｓを求めると、
Ｓ＝Ｔ＋Ｄ−Ｗ＋Ｃ
（但し、Ｔ：タスクの起動時刻，Ｄ：デッドライン時間，Ｗ：最悪実行時間，Ｃ：現時刻におけるタスクの実行時間）余裕消失時刻Ｓが最も早いタスクを優先して実行させる。
【選択図】図１

Description

本発明は、実行ユニットの数よりも多い複数のタスクを、前記実行ユニットに実行させるようにスケジューリングするタスクスケジューラ，及びそのタスクスケジューラを備えてなるマイクロプロセッサ，並びにタスクスケジューリング方法に関する。

複数のタスクを処理するシステムでは、それぞれについて定められている時刻の制限であるデッドラインを超えないようにプロセッサコア（実行ユニット）に実行させるため、効率的にスケジューリングを行う必要がある。例えば非特許文献１には、各タスクについての最悪実行時間と、残り実行時間とから計算される余裕時間を用いてスケジューリングを行い、プロセッサコアの使用効率を高めるアルゴリズムが提案されている。

また、特許文献１には、タスク（スレッド）の切り換えを行うための判断手法として余裕時間を用いて同時マルチスレッド（ＳＭＴ）上でプロセッサへのタスク割り当てを決定する方法が開示されている。また、特許文献２には、タスクの起動時間を余裕時間を用いて判断することで、タスクの切り換え回数を低減し、効率を向上させる方法が開示されている。

特開２００５−１５７９５５号公報 特開２００１−２３６２３６号公報

M.Hwang,et.al.,"Least Slack Time Rate First:New Scheduling Algorithm for Multi-Processor Environment",International Conference on Complex,Intelligent and Software Intensive Systems(CISIS)2010,pp.806-811,15-18 Feb.2010

しかしながら、特許文献１の技術では、割り込みによりプロセッサから余裕時間を取得するため、プロセッサの利用効率が低下してリアルタイム処理性能が低下する問題がある。また、特許文献２の技術では、タスク情報テーブルにおける各タスクのカウント値を減算して更新する。そのため、カウンタや余裕時間の計算が扱うタスクの数に比例して必要となり、現実的な回路面積を考慮すると実装が困難である。また、タスク情報テーブルを参照して優先度の指標を比較し、前記指標が最も大きいタスクを選択するため、比較に要する時間がタスク数に比例して増加する。したがって、現実的な処理時間でタスクをスケジューリングすることも困難である。このような問題は、非特許文献１についても同様に存在する。

本発明は上記事情に鑑みてなされたものであり、その目的は、リアルタイム処理性能を低下させることなく、大きな回路面積を必要とせず現実的な処理時間でスケジューリングを行うことができるタスクスケジューラ，マイクロプロセッサ及びタスクスケジューリング方法を提供することにある。

請求項１記載のタスクスケジューラによれば、複数のタスクの実行状態を共通の時刻で管理し、各タスクについて次式により余裕消失時刻Ｓを求め、
Ｓ＝Ｔ＋Ｄ−Ｗ＋Ｃ
余裕消失時刻Ｓが最も早いタスクを優先して実行させる。ここで「余裕消失時刻」とは、全てのタスクが管理される共通の時刻上で、各タスクの余裕時間が無くなる時刻を意味する。そして、余裕消失時刻Ｓが最も早いタスクを優先して実行ユニットに実行させるようにスケジューリングを行うと、その結果は、従来の余裕時間が最も短いタスクを優先して実行させるスケジューリングの結果と同じになる。

しかしながら、上式の右辺各項において、動的に変化するのはタスクの実行時間Ｃのみであるから、実行状態にあるタスクの「余裕消失時刻」だけが変化する。したがって、従来とは異なり、複数のタスクの実行状態を共通の時刻で管理した上で、実行状態にあるタスクについてのみ余裕消失時刻Ｓの更新を行えば良いので、タスクスケジューラを小規模な回路で実現できる。

請求項２の記載タスクスケジューラによれば、新規タスクの余裕消失時刻が、実行タスクの余裕消失時刻うち最も遅いものよりも早ければ、新規タスクを実行タスクにすると共に余裕消失時刻が最も遅い実行タスクを待機タスクとし、前記最も遅いものよりも遅ければ新規タスクを待機タスクとする。したがって、余裕消失時刻の遅早関係に基づいて、実行させるタスクと待機させるタスクとを入れ替えることができる。そして、入れ替えを行うための比較は１回のみ行えば良いので、スケジューリングを迅速に行うことができる。

請求項３記載のタスクスケジューラによれば、実行タスクと待機タスクとを分別して管理するので、上記の入れ替えを行うための時刻の比較をより簡単に行うことができる。
請求項４記載のタスクスケジューラによれば、実行タスクのうち余裕消失時刻が最も遅いタスクと、待機タスクのうち余裕消失時刻が最も早いタスクとについて両者の余裕消失時刻の早遅関係を比較する。そして、後者の時刻が前者の時刻よりも早ければ対応する実行タスクを待機タスクとし、対応する待機タスクを実行タスクとするように状態の入れ替えを行う。すなわちこの場合も、入れ替えを行うための比較は１回のみ行えば良いので、スケジューリングを迅速に行うことができる。

第１実施形態であり、タスクスケジューラの構成を概念的に示す機能ブロック図 タスクスケジューラの処理を示すフローチャート 本実施形態のスケジューラをマイクロプロセッサに適用した例を示す図 余裕消失時刻を説明する図 実行タスクについての図４相当図 タスクスケジューリングの一例を示す図 従来の図６相当図 図７に対応した従来構成図 第２実施形態を示す図１相当図 余裕消失時刻をソートするイメージを示す図

（第１実施形態）
先ず、本実施形態では、従来のタスクスケジューリングに使用していた余裕時間に替えて新たな概念である「余裕消失時刻」を導入し、この「余裕消失時刻」を用いてスケジューリングを行う。ここで余裕消失時刻Ｓとは（１）式により定義される時刻である。
Ｓ＝Ｔ＋Ｄ−Ｗ＋Ｃ …（１）
Ｔ：タスクの起動時刻
Ｄ：デッドライン時間（タスクの実行を完了させなればならない時間）
Ｗ：最悪実行時間（タスクの実行完了に要すると予測される時間）
Ｃ：現時刻におけるタスクの実行時間
すなわち、「余裕消失時刻」とは、タスクの実行に関する（従来使用されていた）余裕時間が無くなる時刻である。

図４に示すように、余裕消失時刻Ｓはタスクが実行されると遅延するが、タスクが実行されず待機中となる期間は変化しない。したがって、余裕消失時刻Ｓは実行タスクについてのみ更新すれば良く、未だ実行されていない新規タスクの余裕消失時刻Ｓｉは、Ｃ＝０であるから
Ｓｉ＝Ｔ＋Ｄ−Ｗ …（２）
で求められる。また、実行中のタスクについての余裕消失時刻Ｓｎは、前回に更新した余裕消失時刻をＳｐとして保存しておき、実行時間Ｃａを、前回の更新時を起点とする更新時間とすれば、
Ｓｎ＝Ｓｐ＋Ｃａ …（３）
により求めることができる（図５参照）。本実施形態では、全てのタスクについて余裕消失時刻Ｓを求め、各時点において余裕消失時刻Ｓが最も早いタスクを優先して実行するようにスケジューリングを行う。以下、そのための構成について説明する。

図１に示すように、タスクスケジューラ１は、スケジューリングを行うために使用する１個の共通カウンタ２を備えており、全てのタスク実行に関する時刻を共通カウンタ２によって管理する。新規（新たな）タスクが発生すると（図２；ステップＳ１：ＹＥＳ）、初期余裕消失時刻計算部３により新規タスクについての余裕消失時刻Ｓｎが計算される（Ｓ２）。計算された余裕消失時刻Ｓｎは、余裕消失時刻比較部４及び新規タスク登録部５に入力される。

また、タスクスケジューラ１は、実行タスクテーブル６及び待機タスクテーブル７を備えている。実行タスクテーブル６では、実行中のタスクＲ１〜Ｒｎについて計算された余裕消失時刻Ｓｒが管理され、待機タスクテーブル７では、待機中のタスクＷ１〜Ｗｍについての余裕消失時刻Ｓｗが管理される。実行タスク選択部８は、実行タスクテーブル６より余裕消失時刻Ｓｒが最も遅いタスクを選択し、対応する余裕消失時刻Ｓｒｌを余裕消失時刻比較部４及び９に入力する。待機タスク選択部１０は、待機タスクテーブル７より余裕消失時刻Ｓｗが最も早いタスクを選択し、対応する余裕消失時刻Ｓｗｆを余裕消失時刻比較部９に入力する。

余裕消失時刻比較部４は、新規タスクの余裕消失時刻Ｓｎと、実行タスクの最遅余裕消失時刻Ｓｒｌとを比較し（Ｓ２）、その比較結果に基づく登録先情報を新規タスク登録部５に出力する。すなわち、（Ｓｎ＜Ｓｒｌ；余裕消失時刻Ｓｎの方が早い）であれば（ＹＥＳ）新規タスクは実行タスクテーブル６に登録されて管理され、その代わりに実行タスクは、待機タスクテーブル７に登録されて管理される（Ｓ３）。一方、（Ｓｎ＞Ｓｒｌ；余裕消失時刻Ｓｎの方が遅い）であれば新規タスクは待機タスクテーブル７に登録されて管理される（Ｓ４）。

余裕消失時刻比較部９は、実行タスクの最遅余裕消失時刻Ｓｒｌと、待機タスクの最早余裕消失時刻Ｓｗｆとを比較し、その比較結果に基づく切替えタスク切替え部１１に出力する。すなわち、（Ｓｒｌ＞Ｓｗｆ）であれば、対応する実行タスクを待機タスクテーブル７で管理する待機タスクにすると共に、対応する待機タスクを実行タスクテーブル６で管理する実行タスクとするように入れ替え（スワップ）を行う。

図３に示すように、タスクスケジューラ１を、３つのプロセッサコア（実行ユニット）１２（１）〜１２（３）が搭載されたシステムに適用する際に、（ａ）に示すマイクロプロセッサ１３ではタスク切替え部１１を分離して適用しており、（ｂ）に示すマイクロプロセッサ１４では、タスクスケジューラ１を一体としたまま適用している。尚、このようなマイクロプロセッサにタスクスケジューラ１を適用する場合は、余裕消失時刻が最も早いものから上位３つのタスクを選択してプロセッサコア１２（１）〜１２（３）に実行させれば良い。

図６は、３つのタスク（１〜３）が起動された場合のスケジューリング例である。これら３つのタスクの実行情報は、以下のようになっている。
起動時刻Ｔ デッドライン時間Ｄ 最悪実行時間Ｗ
タスク（１） １ １３ ７
タスク（２） ６ ７ ４
タスク（３） １ ２０ ４
時刻「１」において、タスク（１）の余裕消失時刻は「７」，タスク（３）の余裕消失時刻Ｓは「１７」であるから、タスク（１）が実行されてタスク（３）は待機タスクとなる。タスク（１）は実行されることで実行時間Ｃが増加し、その増加分だけ余裕消失時刻は遅くなる。一方、タスク（３）の余裕消失時刻は「１７」のまま変化しない。時刻「６」において、タスク（２）が新規タスクとして起動され、余裕消失時刻は「９」であるからタスク（１）は待機タスクとなり、タスク（２）が実行タスクとなるように切り替わる。

タスク（２）の実行が終了した時刻「１０」においてタスク（１）の余裕消失時刻は「１２」であり、タスク（３）の余裕消失時刻「１７」よりも早いので、タスク（１）の実行が再開される。タスク（１）の実行が終了した時刻「１２」においてタスク（３）の実行が開始される。

一方図７は、図６に示すものと同じタスク（１〜３）について、従来の余裕時間を用いたタスクスケジューリングの一例である。余裕時間は、起動時から実行されるタスク（１）では変化せず初期値「６」を維持するが、起動時から実行されない状態が継続するタスク（３）については時刻の経過に伴い減少するように随時変化する。このように、余裕時間が最も少ないタスクを優先して実行させた場合も、タスクの実行優先順序は図６に示す本実施形態と同様になる。

しかし、図８に対応する構成を示すように、従来のスケジューリングでは、全てのタスクについてカウンタ（デッドラインカウンタ）及び余裕時間計算手段が必要になる。これに対して、本実施形態のタスクスケジューラ１では、カウンタは１つの共通カウンタ２のみで良い。また、従来構成では、新規タスクが発生した際に、新規タスクの余裕時間と、全てのタスクの余裕時間とを比較する必要があるが、タスクスケジューラ１では、余裕消失時刻比較部４，９のみで比較を行えば良い。

以上のように本実施形態によれば、タスクスケジューラ１は、複数のタスクの実行状態を共通カウンタ２が計時する時刻で管理し、各タスクについて（１）式により余裕消失時刻Ｓを求め、余裕消失時刻Ｓが最も早いタスクを優先して実行させる。したがって、従来とは異なり、実行タスクについてのみ余裕消失時刻Ｓの更新を行えば良いので、リアルタイム処理性能を低下させることなく、タスクスケジューラ１を小規模な回路で実現できる。また、新規タスクの余裕消失時刻Ｓｉを（２）式で求め、実行タスクについての余裕消失時刻Ｓｎを（３）式で求めるので、余裕消失時刻Ｓの計算をより迅速に行うことができる。

そして、新規タスクの余裕消失時刻が、実行タスクの余裕消失時刻うち最も遅いものよりも早ければ、新規タスクを実行タスクにすると共に余裕消失時刻が最も遅い実行タスクを待機タスクとし、前記最も遅いものよりも遅ければ新規タスクを待機タスクとする。したがって、余裕消失時刻の遅早関係に基づいて、実行タスクと待機タスクとを入れ替えることができる。そして、入れ替えを行うための比較は１回のみ行えば良いので、スケジューリングを迅速に行うことができる。
また、実行タスクと待機タスクとを、実行タスクテーブル６と待機タスクテーブル７とで分別して管理するので、上記の入れ替えを行うための時刻の比較をより簡単に行うことができる。

加えて、タスクスケジューラ１は、実行タスクのうち余裕消失時刻が最も遅いタスクと、待機タスクのうち余裕消失時刻が最も早いタスクとについて両者の余裕消失時刻の早遅関係を比較する。そして、後者の時刻が前者の時刻よりも早ければ対応する実行タスクを待機タスクとし、対応する待機タスクを実行タスクとするように状態の入れ替えを行う。この場合も、入れ替えを行うための比較は１回のみ行えば良いので、スケジューリングを迅速に行うことができる。そして、タスクスケジューラ１を備えてマイクロプロセッサ１２，１３を構成すれば、マイクロプロセッサ１２，１３を小型化することができる。

（第２実施形態）
以下、第１実施形態と同一部分には同一符号を付して説明を省略し、以下異なる部分について説明する。図９に示すように、第２実施形態のタスクスケジューラ２１では、実行タスク選択部８及び待機タスク選択部１０が削除されている。それに替えて、実行タスクテーブル２２，待機タスクテーブル２３が、それぞれ実行タスク，待機タスクについての余裕消失時刻の遅早順位を常時ソートして管理している。

そして、実行タスクテーブル２２は、余裕消失時刻比較部４，９に対して余裕消失時刻が最も遅いものを出力しており、待機タスクテーブル２３は、余裕消失時刻比較部９に対して余裕消失時刻が最も早いものを出力している（図１０参照）。したがって、実行タスク，待機タスクの相互入れ替えをより迅速に行うことができる。

本発明は上記した、又は図面に記載した実施形態にのみ限定されるものではなく、以下のような変形又は拡張が可能である。
実行タスクと待機タスクとを、分別することなく一括して管理しても良い。
プロセッサコアが４つ以上搭載されているマイクロプロセッサに適用しても良い。また、プロセッサコアが２つやシングルコアのマイクロプロセッサに適用しても良い。

図面中、１はタスクスケジューラ、２は共通カウンタ、６は実行タスクテーブル、７は待機タスクテーブル、１２はプロセッサコア（実行ユニット）、１３及び１４はマイクロプロセッサを示す。

Claims (15)

1. 実行ユニット（１２）の数よりも多い複数のタスクを、前記実行ユニットに実行させるようにスケジューリングするタスクスケジューラ（１，１’）において、
   前記複数のタスクの実行状態を共通の時刻で管理し、
   Ｔ：タスクの起動時刻
   Ｄ：タスクの実行を完了させなればならない時間
   Ｗ：タスクの実行完了に要すると予測される時間
   Ｃ：現時刻におけるタスクの実行時間
   とすると、各タスクについて次式により余裕消失時刻Ｓを求め、
   Ｓ＝Ｔ＋Ｄ−Ｗ＋Ｃ
   前記余裕消失時刻Ｓが最も早いタスクを優先して実行させることを特徴とするタスクスケジューラ。
2. 新たに実行要求が発生したタスク（以下、新規タスクと称す）の余裕消失時刻が、現在実行されているタスク（以下、実行タスクと称す）の余裕消失時刻のうち最も遅いものよりも早ければ、新規タスクを実行タスクにすると共に、余裕消失時刻が最も遅い実行タスクを待機状態とし（以下、待機タスクと称す）、
   前記最も遅いものよりも遅ければ、新規タスクを待機タスクとすることを特徴とする請求項１記載のタスクスケジューラ。
3. 前記実行タスクと前記待機タスクとを分別して管理することを特徴とする請求項２記載のタスクスケジューラ。
4. 前記実行タスクのうち余裕消失時刻が最も遅いタスクと、前記待機タスクのうち余裕消失時刻が最も早いタスクとについて両者の余裕消失時刻の早遅関係を比較し、後者の時刻が前者の時刻よりも早ければ、対応する実行タスクを待機タスクとし、対応する待機タスクを実行タスクとするように状態の入れ替えを行うことを特徴とする請求項３記載のタスクスケジューラ。
5. 現在実行されているタスクの現在の余裕消失時刻Ｓｎを、次式
   Ｓｎ＝Ｓｐ＋Ｃａ
   （ただし、Ｓｐ：前回に更新された余裕消失時刻，Ｃａ：前回に更新された時刻からのタスクの実行時間）により求めることを特徴とする請求項１から４の何れか一項に記載のタスクスケジューラ。
6. 新たに実行要求が発生したタスクの余裕消失時刻Ｓｉを、次式
   Ｓｉ＝Ｔ＋Ｄ−Ｗ
   により求めることを特徴とする請求項１から５の何れか一項に記載のタスクスケジューラ。
7. 前記余裕消失時刻の値に基づいて、各タスクを予めソートして管理することを特徴とする請求項１から６の何れか一項に記載のタスクスケジューラ。
8. １つ以上の実行ユニットと、請求項１から７の何れか一項に記載のタスクスケジューラとを備えることを特徴とするマイクロプロセッサ（１３，１４）。
9. 実行ユニットの数よりも多い複数のタスクを、前記実行ユニットに実行させるようにスケジューリングする方法において、
   前記複数のタスクの実行状態を共通の時刻で管理し、
   Ｔ：タスクの起動時刻
   Ｄ：タスクの実行を完了させなればならない時間
   Ｗ：タスクの実行完了に要すると予測される時間
   Ｃ：現時刻におけるタスクの実行時間
   とすると、各タスクについて次式により余裕消失時刻Ｓを求め、
   Ｓ＝Ｔ＋Ｄ−Ｗ＋Ｃ
   前記余裕消失時刻Ｓが最も早いタスクを優先して実行させることを特徴とするタスクスケジューリング方法。
10. 新たに実行要求が発生したタスク（以下、新規タスクと称す）の余裕消失時刻が、
    現在実行されているタスク（以下、実行タスクと称す）の余裕消失時刻のうち最も遅いものよりも早ければ、新規タスクを実行タスクにすると共に、余裕消失時刻が最も遅い実行タスクを待機状態とし（以下、待機タスクと称す）、前記最も遅いものよりも遅ければ、新規タスクを待機タスクとすることを特徴とする請求項９記載のタスクスケジューリング方法。
11. 前記実行タスクと前記待機タスクとを分別して管理することを特徴とする請求項１０記載のタスクスケジューリング方法。
12. 前記実行タスクのうち余裕消失時刻が最も遅いタスクと、前記待機タスクのうち余裕消失時刻が最も早いタスクとについて両者の余裕消失時刻の早遅関係を比較し、
    後者の時刻が前者の時刻よりも早ければ、対応する実行タスクを待機タスクとし、対応する待機タスクを実行タスクとするように状態の入れ替えを行うことを特徴とする請求項１１記載のタスクスケジューリング方法。
13. 現在実行されているタスクの現在の余裕消失時刻Ｓｎを、次式
    Ｓｎ＝Ｓｐ＋Ｃａ
    （ただし、Ｓｐ：前回に更新された余裕消失時刻，Ｃａ：前回に更新された時刻からのタスクの実行時間）により求めることを特徴とする請求項９から１２の何れか一項に記載のタスクスケジューリング方法。
14. 新たに実行要求が発生したタスクの余裕消失時刻Ｓｉを、次式
    Ｓｉ＝Ｄ−Ｗ＋Ｔ
    により求めることを特徴とする請求項９から１３の何れか一項に記載のタスクスケジューリング方法。
15. 前記余裕消失時刻の値に基づいて、各タスクを予めソートして管理することを特徴とする請求項９から１４の何れか一項に記載のタスクスケジューリング方法。

Images