(57)【要約】【課題】  過負荷状態を避けながらＱｏＳレベルの偏りをなくすために、指定された総ＣＰＵ利用率の下で全てのタスクのＱｏＳレベルを公平化するようなＣＰＵ利用率の制御を行うことが可能なＱｏＳ適応制御装置を提供する。【解決手段】  タスク表１１はコンピュータ１の中で実行されるタスクの制御ブロックの表であり、実行待ちキュー１２はタスク表１１の中でリリースされたジョブを蓄えるキューである。スケジューラ１３は実行待ちキュー１２の中からあるスケジューリングポリシにしたがって実行すべきジョブを選択する。ジョブ実行部１４はスケジューラ１３から選択されたジョブを実行し、モニタ１５はタスクのＱｏＳレベルを測定する。ＱｏＳ適応制御器１６は入力となる時刻ｔl でのタスクのＱｏＳレベルＱi （ｔl ）から次の時刻時刻ｔl+1 でのタスクのＣＰＵ利用率ｒi （ｔl+1 ）を計算する。【選択図】      図１                                                  
2005236456.tif 000002
【特許請求の範囲】
【請求項１】
ＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）レベルを調停するＱｏＳ適応制御装置を含むリアルタイムシステムであって、現在の平均ＱｏＳレベルに基づいて前記ＱｏＳレベルを制御するＱｏＳ適応制御器を前記ＱｏＳ適応制御装置に有し、制御理論を用いて前記ＱｏＳ適応制御器で配分されるＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）利用率がすべてのＱｏＳレベルを等しくする値に収束する条件を利用することを特徴とするリアルタイムシステム。
【請求項２】
タスクの前記ＱｏＳレベルをモニタする手段を前記ＱｏＳ適応制御装置に含み、前記ＱｏＳ適応制御器はそのモニタの結果に基づいて次のタスクの前記ＣＰＵ利用率を計算することを特徴とする請求項１記載のリアルタイムシステム。
【請求項３】
前記タスクが時間サービスを取り合う場合の協調動作をＱｏＳ制御することを特徴とする請求項２記載のリアルタイムシステム。
【請求項４】
前記タスクが空間サービスを行う場合の協調動作をＱｏＳ制御することを特徴とする請求項２記載のリアルタイムシステム。
【請求項５】
ＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）レベルを調停するＱｏＳ適応制御装置であって、現在の平均ＱｏＳレベルに基づいて前記ＱｏＳレベルを制御するＱｏＳ適応制御器を有し、制御理論を用いて前記ＱｏＳ適応制御器で配分されるＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）利用率がすべてのＱｏＳレベルを等しくする値に収束する条件を利用することを特徴とするＱｏＳ適応制御装置。
【請求項６】
タスクの前記ＱｏＳレベルをモニタする手段を含み、前記ＱｏＳ適応制御器はそのモニタの結果に基づいて次のタスクの前記ＣＰＵ利用率を計算することを特徴とする請求項５記載のＱｏＳ適応制御装置。
【請求項７】
前記タスクが時間サービスを取り合う場合の協調動作をＱｏＳ制御することを特徴とする請求項６記載のＱｏＳ適応制御装置。
【請求項８】
前記タスクが空間サービスを行う場合の協調動作をＱｏＳ制御することを特徴とする請求項６記載のＱｏＳ適応制御装置。
【請求項９】
ＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）レベルを調停するＱｏＳ適応制御装置を含むリアルタイムシステムのＱｏＳ適応制御方法であって、前記ＱｏＳ適応制御装置側に、現在の平均ＱｏＳレベルに基づいて前記ＱｏＳレベルを制御するステップを有し、制御理論を用いて前記ステップで配分されるＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）利用率がすべてのＱｏＳレベルを等しくする値に収束する条件を利用することを特徴とするＱｏＳ適応制御方法。
【請求項１０】
前記ＱｏＳ適応制御装置側に、タスクの前記ＱｏＳレベルをモニタするステップを含み、前記ＱｏＳ適応制御器がそのモニタの結果に基づいて次のタスクの前記ＣＰＵ利用率を計算することを特徴とする請求項９記載のＱｏＳ適応制御方法。
【請求項１１】
前記タスクが時間サービスを取り合う場合の協調動作をＱｏＳ制御することを特徴とする請求項６記載のＱｏＳ適応制御方法。
【請求項１２】
前記タスクが空間サービスを行う場合の協調動作をＱｏＳ制御することを特徴とする請求項６記載のＱｏＳ適応制御方法。
【請求項１３】
ＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）レベルを調停するＱｏＳ適応制御装置を含むリアルタイムシステムのＱｏＳ適応制御方法のプログラムであって、コンピュータに、現在の平均ＱｏＳレベルに基づいて前記ＱｏＳレベルを制御する処理を実行させ、制御理論を用いて前記処理で配分されるＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）利用率がすべてのＱｏＳレベルを等しくする値に収束する条件を利用させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はリアルタイムシステム、ＱｏＳ適応制御装置及びそれらに用いるＱｏＳ適応制御方法並びにそのプログラムに関し、特にＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）レベル公平化に基づくリアルタイムシステムのＱｏＳ適応制御方法に関する。
【背景技術】
【０００２】
ＱｏＳレベルを調停する研究については、これまでいくつかの研究がなされてきている。例えば、システム過負荷時のタスクに対して、受容可能なＱｏＳレベルを予め記述し、システム過負荷時には、この記述を基に各タスクとネゴシエーションを行うことによって、タスクのＱｏＳレベルを低下させ、過負荷状態に対処する研究がされている（例えば、非特許文献１参照）。
【０００３】
また、Ｂｕｔｔａｚｚｏらは、リアルタイムシステムにおいて、タスクの処理がバネのように伸縮するものと見なすエラスティックモデルを導入し、過負荷時には各タスクの実行時間を短縮して過負荷状況に適応するアルゴリズムを提案している（例えば、非特許文献２参照）。この場合、プログラム設計者はアプリケーションプログラムをエラスティックモデルに基づき設計しなければならない。これは容易なことでないと考えられる。
【０００４】
さらに、Ｒａｊｋｕｍｍｅｒらは、複数の資源に同時にアクセスする場合にＱｏＳに基づく資源確保モデルを提案している（例えば、非特許文献３参照）。この提案では、各アプリケーションプログラムの持つ最低限のＱｏＳレベルの要求を満たすという制限下に、ＱｏＳレベルを最大化するアルゴリズムが提案されている。
【０００５】
さらにまた、追川らは、リアルタイムプログラムの時間上のＱｏＳレベルを保証するために、ソフトウェアアーキテクチャと資源予約を行うＡＰＩとを提案し、ポータブルなカーネルモジュールを開発している（例えば、非特許文献４参照）。このカーネルモジュールでは、アドミッション制御を行っている。
【０００６】
一方、リアルタイムシステムに制御理論を適用する研究が、近年注目されている。例えば、リアルタイムシステムにおけるタスクのＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）使用率を管理する手法に制御理論を利用する研究が提案されている（例えば、非特許文献５参照）。この研究では、ＣＰＵの使用時間を制御するために、ＰＩＤ（Ｐｒｏｐｏｒｔｉｏｎａｌ−ｉｎｔｅｇｒａｌ−ｄｅｒｉｖａｔｉｖｅ）が応用されている。ＰＩＤ制御は動的な制御なので、過去のＣＰＵ利用率を記憶しておく必要がある。
【０００７】
また、タスクのＣＰＵ利用率やデッドラインミス率を指定された値に維持するために、フィードバック制御理論を用いる研究がなされている。例えば、デッドラインミス率をある範囲内に抑えるべく、ＣＰＵ時間の予約にＰＩ制御器を利用する研究が提案されている（例えば、非特許文献６参照）。
【０００８】
さらに、ＣＰＵ利用率またはデッドラインミス率に対して目標値を与え、ゲインフィードバックによる制御法が提案している（例えば、非特許文献７参照）。
【０００９】
【特許文献１】特開２００３−０６９６３１
【特許文献２】特開平１０−２３３８０２
【特許文献３】特表２００１−５１６９８８
【特許文献４】特開２００２−３６８７９７
【特許文献５】特開平１０−２９３６９４
【特許文献６】特開平１０−２４０６９８
【非特許文献１】“ＱｏＳ  Ｎｅｇｏｔｉａｔｉｏｎ  ｉｎ  Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ  ａｎｄ  Ｉｔｓ  Ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  Ａｕｔｏｍａｔｅｄ  Ｆｌｉｇｈｔ  Ｃｏｎｔｒｏｌ”（Ｔ．Ａｂｄｅｌｚａｈｅｒ，Ｅ．Ａｔｋｉｎｓ，ａｎｄ  Ｋ．Ｓｈｉｎ，Ｐｒｏｃ．ＩＥＥＥ  Ｒｅａｌ−Ｔｉｍｅ  Ｔｅｃｈｎｏｌｏｇｙ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎ  Ｓｙｍｐｏｓｉｕｍ，１９９７．）
【非特許文献２】“Ａｄａｐｔｉｖｅ  Ｗｏｒｋｌｏａｄ  Ｍａｎａｇｅｍｅｎｔ  ｔｈｒｏｕｇｈ  Ｅｌａｓｔｉｃ  Ｓｃｈｅｄｕｌｉｎｇ”（Ｇ．Ｂｕｔｔａｚｚｏ  ａｎｄ  Ｌ．Ａｂｅｎｉ，Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ，Ｖｏｌ．２３，Ｎｏ．１，ｐｐ．７−２４，２００２．）
【非特許文献３】“Ａ  Ｒｅｓｏｕｒｃｅ  Ａｌｌｏｃａｔｉｏｎ  Ｍｏｄｅｌ  ｆｏｒ  ＱｏＳ  Ｍａｎａｇｅｍｅｎｔ”（Ｒ．Ｒａｊｋｕｍａｒ，Ｃ．Ｌｅｅ，Ｊ．Ｌｅｏｃｚｋｙ，ａｎｄ  Ｄ．Ｓｉｅｗｉｏｒｅｋ，Ｐｒｏｃ．１８ｔｈ  ＩＥＥＥ  Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍ  Ｓｙｍｐｏｓｉｕｍ，ｐｐ．２９８−３０７，Ｄｅｃ．１９９７．）
【非特許文献４】“Ｐｏｒｔａｂｌｅ  ＲＫ：  Ａ  Ｐｏｒｔａｂｌｅ  Ｒｅｓｏｕｒｃｅ  Ｋｅｒｎｅｌ  ｆｏｒ  Ｇｕａｒａｎｔｅｅｄ  ａｎｄ  Ｅｎｆｏｒｃｅｄ  Ｔｉｍｉｎｇ  Ｂｅｈａｖｉｏｒ”（Ｓ．Ｏｉｋａｗａ  ａｎｄ  Ｒ．Ｒａｊｋｕｍａｒ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＩＥＥＥ  Ｒｅａｌ−Ｔｉｍｅ  Ｔｅｃｈｎｏｌｏｇｙ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ  Ｓｙｍｐｏｓｉｕｍ，Ｊｕｎｅ  １９９９．）
【非特許文献５】“Ａ  ｆｅｅｄｂａｃｋ−ｄｒｉｖｅｎ  Ｐｒｏｐｏｒｔｉｏｎａｌ  Ａｌｌｏｃａｔｏｒ  ｆｏｒ  Ｒｅａｌ−Ｒａｔｅ  Ｓｃｈｅｄｕｌｉｎｇ”（Ｄ．Ｓｔｅｅｒｅ，Ａ．Ｇｏｅｌ，Ｊ．Ｇｒｅｕｎｂｅｒｇ，Ｄ．ＭｃＮａｍｅｅ，Ｃ．Ｐｕ  ａｎｄ  Ｊ．Ｗａｌｐｏｌｅ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ３ｒｄ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍｓ  Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ，１９９９．）
【非特許文献６】“Ａｎａｌｙｓｉｓ  ｏｆ  ａ  Ｒｅｓｅｒｖａｔｉｏｎ−Ｂａｓｅｄ  Ｆｅｅｄｂａｃｋ  Ｓｃｈｅｄｕｌｅｒ”（Ｌ．Ａｂｅｎｉ，Ｌ．Ｐａｌｏｐｏｌｉ，Ｇ．Ｌｉｐａｒｉ  ａｎｄ  Ｊ．Ｗａｌｐｏｌｅ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２３ｒｄ  Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ  Ｓｙｍｐｏｓｉｕｍ，ｐｐ．７１−８０，２００２．）
【非特許文献７】“Ｆｅｅｄｂａｃｋ  Ｃｏｎｔｒｏｌ  Ｒｅａｌ−Ｔｉｍｅ  Ｓｃｈｅｄｕｌｉｎｇ：Ｆｒａｍｅｗｏｒｋ，Ｍｏｄｅｌｉｎｇ，ａｎｄ  Ａｌｇｏｒｉｔｈｍｓ”（Ｃ．Ｌｕ，Ｊ．Ｓｔａｎｋｏｖｉｃ，Ｓ．Ｓｏｎ，ａｎｄ  Ｇ．Ｔａｏ，Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ，Ｖｏｌ．２３，Ｎｏ．１，ｐｐ．８５−１２６，２００２．）
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上述した従来のＱｏＳレベルの調停方法では、上述した方法や研究のいずれの場合も、目標値を前もって与える必要がある。しかしながら、目標値は処理されるべきタスクの集合に依存しており、時間とともにタスクの集合が変動すると、目標値の再計算が必要になる。この計算には非線形方程式の数値計算が含まれており、ｎをタスクの数とした時、Ｏ（ｎ2 ）の計算量になる。
【００１１】
リアルタイムシステムにおける過負荷状態時には、各タスクのＣＰＵ利用率を下げることでデッドラインミスを回避する必要がある。一般に、各タスクのＱｏＳレベルはそれぞれ異なったＣＰＵ利用率の非線形関数で表されるため、同じ割合でＣＰＵの利用率を変化させた時、ＱｏＳレベルの変化がタスクによって異なる。
【００１２】
そこで、本発明の目的は上記の問題点を解消し、過負荷状態を避けながらＱｏＳレベルの偏りをなくすために、指定された総ＣＰＵ利用率の下で全てのタスクのＱｏＳレベルを公平化するようなＣＰＵ利用率の制御を行うことができるリアルタイムシステム、ＱｏＳ適応制御装置及びそれらに用いるＱｏＳ適応制御方法並びにそのプログラムを提供することにある。
【課題を解決するための手段】
【００１３】
本発明によるリアルタイムシステムは、ＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）レベルを調停するＱｏＳ適応制御装置を含むリアルタイムシステムであって、現在の平均ＱｏＳレベルに基づいて前記ＱｏＳレベルを制御するＱｏＳ適応制御器を前記ＱｏＳ適応制御装置に備え、制御理論を用いて前記ＱｏＳ適応制御器で配分されるＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）利用率がすべてのＱｏＳレベルを等しくする値に収束する条件を利用している。
【００１４】
本発明によるＱｏＳ適応制御装置は、ＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）レベルを調停するＱｏＳ適応制御装置であって、現在の平均ＱｏＳレベルに基づいて前記ＱｏＳレベルを制御するＱｏＳ適応制御器を備え、制御理論を用いて前記ＱｏＳ適応制御器で配分されるＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）利用率がすべてのＱｏＳレベルを等しくする値に収束する条件を利用している。
【００１５】
本発明によるＱｏＳ適応制御方法は、ＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）レベルを調停するＱｏＳ適応制御装置を含むリアルタイムシステムのＱｏＳ適応制御方法であって、前記ＱｏＳ適応制御装置側に、現在の平均ＱｏＳレベルに基づいて前記ＱｏＳレベルを制御するステップを備え、制御理論を用いて前記ステップで配分されるＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）利用率がすべてのＱｏＳレベルを等しくする値に収束する条件を利用している。
【００１６】
本発明によるＱｏＳ適応制御方法のプログラムは、ＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）レベルを調停するＱｏＳ適応制御装置を含むリアルタイムシステムのＱｏＳ適応制御方法のプログラムであって、コンピュータに、現在の平均ＱｏＳレベルに基づいて前記ＱｏＳレベルを制御する処理を実行させ、制御理論を用いて前記処理で配分されるＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）利用率がすべてのＱｏＳレベルを等しくする値に収束する条件を利用させている。
【００１７】
すなわち、本発明のＱｏＳ適応制御方法は、過負荷状態を避けながら、ＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）レベルの偏りをなくすために、指定された総ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）利用率の下ですべてのタスクのＱｏＳレベルを公平化するようなＣＰＵ利用率の制御を行う方法である。
【００１８】
ＱｏＳレベルを公平化するようなＣＰＵ利用率を求め、これに基づいて制御するのは困難であるが、本発明のＱｏＳ適応制御方法では、現在の平均ＱｏＳレベルに基づいてＱｏＳレベルを制御するＱｏＳ適応制御器を導入することで、ＱｏＳ公平化を達成している。この場合には、ＣＰＵ利用率が未知であっても、ＱｏＳ公平化が可能である。
【００１９】
本発明では、この目的を達成するために制御理論を用いて、ＱｏＳ適応制御器で配分されるＣＰＵ利用率が、すべてのＱｏＳレベルを等しくする値に収束する条件を利用している。
【００２０】
これによって、本発明のＱｏＳ適応制御方法では、タスクのＱｏＳレベルをモニタし、そのモニタの結果に基づいて次のタスクの利用率を計算する制御器を設けているので、過負荷状態を避けながらＱｏＳレベルの偏りをなくすために、指定された総ＣＰＵ利用率の下ですべてのタスクのＱｏＳレベルを公平化するようなＣＰＵ利用率の制御を行うことが可能となる。
【００２１】
また、本発明のＱｏＳ適応制御方法では、制御理論を用いて、ＱｏＳ適応制御器で配分されるＣＰＵ利用率がすべてのＱｏＳレベルを等しくする値に収束する条件を利用しているため、ＣＰＵ利用率が未知であっても、ＱｏＳ公平化が可能になる。
【発明の効果】
【００２２】
本発明は、以下に述べるような構成及び動作とすることで、過負荷状態を避けながらＱｏＳレベルの偏りをなくすために、指定された総ＣＰＵ利用率の下ですべてのタスクのＱｏＳレベルを公平化するようなＣＰＵ利用率の制御を行うことができるという効果が得られる。
【発明を実施するための最良の形態】
【００２３】
次に、本発明の実施例について図面を参照して説明する。図１は本発明の一実施例によるリアルタイムシステムのＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）適応制御装置の構成を示すブロック図である。図１において、本発明の一実施例によるＱｏＳ適応制御装置はＱｏＳレベルを調停するものであり、コンピュータ１によって構成されている。
【００２４】
コンピュータ１はタスクＴ1 〜ＴN を含むタスク表１１と、実行待ちキュー１２と、スケジューラ１３と、ジョブ実行部１４と、モニタ１５と、ＱｏＳ適応制御器１６から構成されている。
【００２５】
タスク表１１はコンピュータ１の中で実行されるタスクの制御ブロックの表（データ）である。実行待ちキュー１２はタスク表１１の中でリリースされた（実行可能状態になった）ジョブを蓄えるキュー（データ）である。
【００２６】
スケジューラ１３は実行待ちキュー１２の中からあるスケジューリングポリシにしたがって実行すべきジョブを選択するプログラムである。リアルタイムシステムでは、スケジューリングポリシとして、周期的に実行される周期タスクの場合にタスクの周期の短い順に実行するＲａｔｅ  Ｍｏｎｏｔｏｎｉｃスケジューリング、デッドラインの早い順に実行されるＥａｒｌｉｅｓｔ  Ｄｅａｄｌｉｎｅ  Ｆｉｒｓｔスケジューラ等が代表的であるが、本実施例ではスケジューラの種類を特に固定しない。
【００２７】
ジョブ実行部１４はスケジューラ１３から選択されたジョブを実行するプログラムである。モニタ１５はタスクのＱｏＳレベルを測定するプログラムである。ＱｏＳ適応制御器１６は入力となる時刻ｔl でのタスクのＱｏＳレベルＱi （ｔl ）（ｉ＝１，…，Ｎ）から次の時刻時刻ｔl+1 でのタスクのＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）利用率ｒi （ｔl+1 ）（ｉ＝１，…，Ｎ）を計算するプログラムである。
【００２８】
図２は図１のＱｏＳ適応制御器１６の構成を示すブロック図である。図２において、ＱｏＳ適応制御器１６はＱｏＳレベル計算部１６１と、タスクＴ1 の制御器１６２−１と、タスクＴ2 の制御器１６２−２と、・・・、タスクＴN の制御器１６２−Ｎとから構成されている。
【００２９】
ＱｏＳレベル計算部１６１はＱｏＳレベルの平均＜Ｑ＞を計算するプログラムである。タスクＴ1 の制御器１６２−１、タスクＴ2 の制御器１６２−２、・・・、タスクＴN の制御器１６２−Ｎはそれぞれ、ＱｏＳレベルの平均＜Ｑ＞と時刻ｔl でのＱｏＳレベルＱi （ｔl ）（ｉ＝１，…，Ｎ）から、＜Ｑ＞（ｔ）とＱi （ｔl ）との誤差をなくすように、次の時刻時刻ｔl+1 でのタスクのＣＰＵ利用率ｒi （ｔl+1 ）（ｉ＝１，…，Ｎ）を計算するプログラムである。
【００３０】
まず、本発明の背景となる理論について説明する。本発明では、独立な周期タスク集合｛Ｔ1 ，Ｔ2 ，…，ＴN ｝、スケジューラ、及びプロセッサからなるリアルタイムシステムを対象とする。
【００３１】
スケジューラで用いられるスケジューリング則は既に与えられており、総ＣＰＵ利用率がＲ以下ならば、周期タスク集合｛Ｔ1 ，Ｔ2 ，…，ＴN ｝はスケジュール可能であるとする。以下、ＣＰＵ利用率を単に利用率とする。
【００３２】
各タスクＴi は周期的にサービスを要求する。各サービスは要求される時に、Ｔi に与えられた利用率ｒi （０＜ｒi ≦１）に応じてサービスに利用時間が与えられる。
【００３３】
本発明では、サービスの実行が終了すると、その処理結果をＱｏＳとして評価する。以下、タスクＴi が要求するサービスが利用率ｒi で実行された時のＱｏＳレベルをＱｏＳi （ｒi ）とする。
【００３４】
本発明では、各タスクＴi のＱｏＳレベルＱｏＳi （ｒi ）が下限ＱｏＳi - から上限ＱｏＳi + までの値を持つ場合について考える。下限ＱｏＳi - 、上限ＱｏＳi + はそれぞれ利用率の最小要求量ｒi - 、最大要求量ｒi + によって得られるＱｏＳレベルに対応している。ここで、関数ｐi （ｒi ）を、
ｐi （ｒi ）＝（ＱｏＳi （ｒi ）−ＱｏＳi - ）
／（ＱｏＳi + −ＱｏＳi - ）          ・・・（１）
と定義すると、０≦ｐi （ｒi ）≦１であり、ｐi （ｒi ）＝１の時にはタスクＴi が最大ＱｏＳレベルとなる利用率が、ｐi （ｒi ）＝０の時にはタスクＴi が最小ＱｏＳレベルとなる利用率が、それぞれに割り当てられることを意味している。
【００３５】
各タスクＴi のＱｏＳレベルがＱｏＳi - からＱｏＳi + までの値をとるので、関数ｐi （ｒi ）はＱｏＳレベルの達成度を意味していると考えることができ、全てのタスクで関数ｐi （ｒi ）が等しくなる。すなわち、
ｐ1 （ｒ1 ）＝ｐ2 （ｒ2 ）＝…＝ｐN （ｒN ）          ・・・（２）
となるように、各タスクＴi の利用率ｒ1 ，ｒ2 ，…，ｒN と定められる時、利用率が公平に割り当てられていると考える。
【００３６】
ｐi は、
（１）ｐi はｒi ∈［ｒi - ，ｒi + ］で微分可能な単調増加関数である
（２）ｐi （０）＝０、０＜ｄｐi ／ｄｒi ≦Ｄi （Ｄi はｐi の最大変化率）という条件を満たすものと仮定する。
【００３７】
時刻ｔにおいて、各タスクＴi が利用率ｒi + でジョブをリリースした時、
（ａ）総利用率ａがＲ以下であれば、リリースされたジョブはすべてデッドラインまでに処理を終了することができるので、特に制御する必要はない。ここで、総利用率ａは、
【数１】
2005236456.tif 000003
と表される。
（ｂ）総利用率ｂがＲより大きい場合には各タスクＴi に最小限必要な利用率を割り当てることができない。ここで、総利用率ｂは、
【数２】
2005236456.tif 000004
と表される。
（ｃ）総利用率ａ＞Ｒ＞総利用率ｂ
の場合を本実施例で扱い、その動作を以下に述べる。以下、説明を簡単化するために、ｐi （ｒi （ｔ））＝Ｑi （ｔ）とする。
【００３８】
図３は本発明の一実施例によるＱｏＳ適応制御装置の動作を示すフローチャートである。これら図１〜図３を参照して本発明の一実施例によるＱｏＳ適応制御装置の動作について説明する。
【００３９】
ＱｏＳ適応制御器１６は指定された時刻になると起動される。以下、ＱｏＳ制御適応制御器１６のｌ回目の起動時刻をｔl とする。時刻ｔl でＱｏＳ適応制御器１６によって配分された各タスクＴi の利用率は、次にＱｏＳ適応制御器１６が起動する時刻ｔl+1 まで保持される。
コンピュータ１は時刻ｔ∈［ｔl ，ｔl+1 ）の間にタスクＴi のｋ番目のジョブＪj-k をリリースする（図３ステップＳ１）。すると、ジョブＪj-k は利用率がｒi （ｔl ）になるような処理を行う（図３ステップＳ２）。ジョブＪj-k の実行終了後、利用率ｒi （ｔl ）によって決まるタスクＴi のＱｏＳレベルＱi （ｔl ）がモニタ１５で測定され（図３ステップＳ３）、その測定結果がＱｏＳ適応制御器１６に送られる。それに基づいて、ＱｏＳ適応制御器１６は時刻ｔl+1 までにｒi （ｔl+1 ）を計算する（図３ステップＳ４）。
【００４０】
ＱｏＳ適応制御器１６は、
【数３】
2005236456.tif 000005
・・・（３）
ｐ1 （ｒ1 e ）＝ｐ2 （ｒ2 e ）＝…＝ｐN （ｒN e ）＝Ｑe
・・・（４）
を満足するｒi e 、Ｑe を求め、ｒi 、Ｑi がｒi e 、Ｑe に収束するように制御する。
【００４１】
そこで、Ｑi （ｔ）を未知のＱe に近づける制御手法として、各時刻でのＱｏＳレベルの平均値＜Ｑ＞（ｔ）を仮想的な目標値として、＜Ｑ＞（ｔ）とＱj （ｔ）との偏差に基づいた制御を考える。ここで、平均値＜Ｑ＞（ｔ）は、
【数４】
2005236456.tif 000006
と表される。
【００４２】
モニタ１５によって測定された各タスクＴi のＱｏＳレベルＱi （ｔl ）に対して、すべてのＱｏＳレベルの平均値＜Ｑ＞（ｔ）を計算し、各タスクＴi の制御器（タスクＴ1 の制御器１６２−１と、タスクＴ2 の制御器１６２−２と、・・・、タスクＴN の制御器１６２−Ｎ）ではＱｏＳレベルの平均値＜Ｑ＞（ｔ）とＱｏＳレベルＱi （ｔl ）との誤差をなくすように利用率を設定する。ここでは、
ｒi （ｔl ）＝ｒi （ｔl-1 ）＋α（＜Ｑ＞（ｔl-1 ）−Ｑi （ｔl-1 ）
・・・（５）
という式によって求める。但し、αはフィードバックゲインで、全ての制御器（タスクＴ1 の制御器１６２−１と、タスクＴ2 の制御器１６２−２と、・・・、タスクＴN の制御器１６２−Ｎ）で同じ値を用いる。
【００４３】
この場合、ＱｏＳ適応制御器１６のパラメータαをどのように設定すればよいかが重要な問題である。すなわち、
（１）ＱｏＳ適応制御器１６で生成されるｒi （ｔ）が、実行可能スケジュールを生成できることを保証する点である。
（２）各ｒi （ｔ）がｒi e に収束する、つまりシステムがｒi e ，Ｑe で漸近安定となる点である。これはある回数以上、ＱｏＳ適応制御器１６を起動すれば、Ｑi （ｔ）が必ず公平化された値＄Ｑe に近づき、ＱｏＳレベル公平化が達成されることを意味する。
【００４４】
α≦１／ｍａｘj Ｄj ならば、上記の（１）式で与えられるＱｏＳレベルを持つ独立な周期タスクの集合｛Ｔ1 ，Ｔ2 ，…，ＴN ｝のＱｏＳレベル公平化が可能であることを証明することができる。そこで、αはできるだけ大きくとる方がいいので、α＝１／ｍａｘj Ｄj とすればよい。
【００４５】
時刻ｔl でのタスクのＱｏＳレベルＱj （ｔl ）（ｊ＝１，…，Ｎ）と、直前の時刻ｔl-1 のタスクのＱｏＳレベルＱj （ｔl ）（ｊ＝１，…，Ｎ）とを比較し、比較結果がある小さな値εより小さければ（図３ステップＳ５）、漸近収束しているので、処理を終了する。
【００４６】
比較結果がεより小さくなければ（図３ステップＳ５）、漸近収束していないので、ｌを１増して（ｌ＝ｌ＋１）（図３ステップＳ６）、ステップＳ１に戻って次の時間スロットで再度ＱｏＳ制御を行う。
【００４７】
このように、本実施例では、タスクのＱｏＳレベルをモニタし、そのモニタの結果に基づいて次のタスクの利用率を計算する制御器を設けることによって、過負荷状態を避けながら、ＱｏＳレベルの偏りをなくすために、指定された総ＣＰＵ利用率の下で全てのタスクのＱｏＳレベルを公平化するようなＣＰＵ利用率の制御を行うことができる。
【００４８】
また、本実施例では、制御理論を用いて、ＱｏＳ適応制御器で配分されるＣＰＵ利用率が全てのＱｏＳレベルを等しくする値に収束する条件を利用することによって、ＣＰＵ利用率が未知であってもＱｏＳ公平化が可能になる。
【００４９】
図４は本発明の他の実施例によるリアルタイムシステムのＱｏＳ適応制御装置の構成を示すブロック図である。図４において、本発明の他の実施例によるＱｏＳ適応制御装置は、実行待ちキュー１２及びジョブ実行部１４の代わりに、サービス待ちキュー２１及びサービス実行部２２を設けた以外は図１に示す本発明の一実施例によるＱｏＳ適応制御装置と同様の構成となっており、同一構成要素には同一符号を付してある。
【００５０】
本発明の一実施例はタスクが時間サービスを取り合う場合の協調動作をＱｏＳ制御するものであるが、本発明の他の実施例はタスクが空間サービスを行う（タスクが必要なメモリを獲得する）場合の協調動作をＱｏＳ制御するものである。動作の概要は上述した本発明の一実施例と同様であり、適用対象が異なるのみである。
【００５１】
本発明の他の実施例では、空間サービスをサービスと呼ぶことにする。サービスには以下のものが含まれる。タスクの実行に必要なメモリ、バッファ、チャネル等の獲得、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）資源（セマフォ、共有メモリ等）の獲得である。
【００５２】
図４において、本発明の他の実施例によるＱｏＳ適応制御装置はＱｏＳレベルを調停するものであり、コンピュータ２によって構成されている。コンピュータ２はタスクＴ1 〜ＴN を含むタスク表１１と、サービス待ちキュー２１と、スケジューラ１３と、サービス実行部２２と、モニタ１５と、ＱｏＳ適応制御器１６とから構成されている。
【００５３】
タスク表１１はコンピュータ２の中で実行されるタスクの制御ブロックの表（データ）である。サービス待ちキュー２１はタスク表１１の中で要求されたサービス（メモリ要求等）を蓄えるキュー（データ）である。
【００５４】
スケジューラ１３はサービス待ちキュー２１の中からあるサービス処理ポリシにしたがって実行すべきジョブを選択するプログラムである。サービス処理ポリシとして、早く到着したサービスから処理を行うＦｉｒｓｔ  Ｃｏｍｅ  Ｆｉｒｓｔ  Ｓｅｒｖｉｃｅ、優先順位をサービスが持つ場合に優先度の高いサービスから処理を行うＰｒｉｏｒｉｔｙ  Ｓｅｒｖｉｃｅが代表的であるが、本実施例ではスケジューラの種類を特に固定しない。
【００５５】
サービス実行部２２はスケジューラ１３で選択されたサービスを実行するプログラムである。モニタ１５はタスクのＱｏＳレベルを測定するプログラムである。ＱｏＳ適応制御器１６は入力となる時刻ｔl でのタスクのＱｏＳレベルＱi （ｔl ）（ｉ＝１，…，Ｎ）から、次の時刻時刻ｔl+1 でのタスクのＣＰＵ利用率ｒi （ｔl+1 ）（ｉ＝１，…，Ｎ）を計算するプログラムである。
【００５６】
図５は図４のＱｏＳ適応制御器１６の構成を示すブロック図である。図５において、ＱｏＳ適応制御器１６はＱｏＳレベル計算部１６１と、タスクＴ1 の制御器１６２−１と、タスクＴ2 の制御器１６２−２と、・・・、タスクＴN の制御器１６２−Ｎとから構成されている。
【００５７】
ＱｏＳレベル計算部１６１はＱｏＳレベルの平均＜Ｑ＞を計算するプログラムである。タスクＴ1 の制御器１６２−１、タスクＴ2 の制御器１６２−２、・・・、タスクＴN の制御器１６２−Ｎはそれぞれ、ＱｏＳレベルの平均＜Ｑ＞と時刻ｔl でのＱｏＳレベルＱi （ｔl ）（ｉ＝１，…，Ｎ）から、＜Ｑ＞（ｔ）とＱi （ｔl ）との誤差をなくすように、次の時刻時刻ｔl+1 でのタスクのＣＰＵ利用率ｒi （ｔl+1 ）（ｉ＝１，…，Ｎ）を計算するプログラムである。
【００５８】
図６は本発明の他の実施例によるＱｏＳ適応制御装置の動作を示すフローチャートである。これら図４〜図６を参照して本発明の他の実施例によるＱｏＳ適応制御装置の動作について説明する。
【００５９】
ＱｏＳ適応制御器１６は指定された時刻になると起動される。以下、ＱｏＳ制御適応制御器１６のｌ回目の起動時刻をｔl とする。時刻ｔl でＱｏＳ適応制御器１６によって配分された各タスクＴi の利用率は、次にＱｏＳ適応制御器１６が起動する時刻ｔl+1 まで保持される。
【００６０】
コンピュータ１は時刻ｔ∈［ｔl ，ｔl+1 ）の間にタスクＴi のｋ番目のサービスＳj-k をリリースする（図６ステップＳ１１）。すると、サービスＳj-k は利用率がｒi （ｔl ）になるような処理を行う（図６ステップＳ１２）。サービスＳj-k の実行終了後、利用率ｒi （ｔl ）によって決まるタスクＴi のＱｏＳレベルＱi （ｔl ）がモニタ１５で測定され（図６ステップＳ１３）、その測定結果がＱｏＳ適応制御器１６に送られる。それに基づいて、ＱｏＳ適応制御器１６は時刻ｔl+1 までにｒi （ｔl+1 ）を計算する（図６ステップＳ１４）。
【００６１】
ＱｏＳ適応制御器１６は上記の（３）式及び（４）式を満足するｒi e 、Ｑe を求め、ｒi 、Ｑi がｒi e 、Ｑe に収束するように制御する。本実施例では、ｒi e 、Ｑe を計算せずに、ｒi 、Ｑi がｒi e 、Ｑe に収束させる手法を特徴とする。Ｑe が未知であるため、システムではＱe とＱi （ｔ）との偏差に基づいて制御することは困難である。
【００６２】
そこで、Ｑi （ｔ）を未知のＱe に近づける制御手法として、各時刻でのＱｏＳレベルの平均値＜Ｑ＞（ｔ）を仮想的な目標値として、＜Ｑ＞（ｔ）とＱj （ｔ）との偏差に基づいた制御を考える。ここで、平均値＜Ｑ＞（ｔ）は、
【数５】
2005236456.tif 000007
と表される。
【００６３】
モニタ１５によって測定された各タスクＴi のＱｏＳレベルＱi （ｔl ）に対して、すべてのＱｏＳレベルの平均値＜Ｑ＞（ｔ）を計算し、各タスクＴi の制御器（タスクＴ1 の制御器１６２−１と、タスクＴ2 の制御器１６２−２と、・・・、タスクＴN の制御器１６２−Ｎ）ではＱｏＳレベルの平均値＜Ｑ＞（ｔ）とＱｏＳレベルＱi （ｔl ）との誤差をなくすように利用率を設定する。ここでは、上記の（５）式によって求める。但し、αはフィードバックゲインで、全ての制御器（タスクＴ1 の制御器１６２−１と、タスクＴ2 の制御器１６２−２と、・・・、タスクＴN の制御器１６２−Ｎ）で同じ値を用いる。
【００６４】
この場合、ＱｏＳ適応制御器１６のパラメータαをどのように設定すればよいかが重要な問題である。すなわち、
（１）ＱｏＳ適応制御器１６で生成されるｒi （ｔ）が、実行可能スケジュールを生成できることを保証する点である。
（２）各ｒi （ｔ）がｒi e に収束する、つまりシステムがｒi e ，Ｑe で漸近安定となる点である。これはある回数以上、ＱｏＳ適応制御器１６を起動すれば、Ｑi （ｔ）が必ず公平化された値＄Ｑe に近づき、ＱｏＳレベル公平化が達成されることを意味する。
【００６５】
α≦１／ｍａｘj Ｄj ならば、上記の（１）式で与えられるＱｏＳレベルを持つ独立な周期タスクの集合｛Ｔ1 ，Ｔ2 ，…，ＴN ｝のＱｏＳレベル公平化が可能であることを証明することができる。そこで、αはできるだけ大きくとる方がいいので、α＝１／ｍａｘj Ｄj とすればよい。
【００６６】
時刻ｔl でのタスクのＱｏＳレベルＱj （ｔl ）（ｊ＝１，…，Ｎ）と、直前の時刻ｔl-1 のタスクのＱｏＳレベルＱj （ｔl ）（ｊ＝１，…，Ｎ）とを比較し、比較結果がある小さな値εより小さければ（図６ステップＳ１５）、漸近収束しているので、処理を終了する。
【００６７】
比較結果がεより小さくなければ（図６ステップＳ１５）、漸近収束していないので、ｌを１増して（ｌ＝ｌ＋１）（図６ステップＳ１６）、ステップＳ１１に戻って次の時間スロットで再度ＱｏＳ制御を行う。
【００６８】
このように、本実施例でも、タスクのＱｏＳレベルをモニタし、そのモニタの結果に基づいて次のタスクの利用率を計算する制御器を設けることによって、過負荷状態を避けながら、ＱｏＳレベルの偏りをなくすために、指定された総ＣＰＵ利用率の下で全てのタスクのＱｏＳレベルを公平化するようなＣＰＵ利用率の制御を行うことができる。
【００６９】
また、本実施例では、制御理論を用いて、ＱｏＳ適応制御器で配分されるＣＰＵ利用率が全てのＱｏＳレベルを等しくする値に収束する条件を利用することによって、ＣＰＵ利用率が未知であってもＱｏＳ公平化が可能になる。
【産業上の利用可能性】
【００７０】
本発明は、一般に、複数のプログラムが一つの時間的、空間的資源を競合して利用する場面に調停する用途に利用することができる。例えば、本発明は、ＣＰＵスケジューラ、メモリ量が小さい組み込みシステムにおいて、各プログラムが利用するメモリ量を調停する場面、通信やディスク等のＩＯチャネルを各プログラムが利用するチャネル利用に必要なメモリ量を調停する場面でそれぞれ利用することができる。
【図面の簡単な説明】
【００７１】
【図１】本発明の一実施例によるリアルタイムシステムのＱｏＳ適応制御装置の構成を示すブロック図である。
【図２】図１のＱｏＳ適応制御器の構成を示すブロック図である。
【図３】本発明の一実施例によるＱｏＳ適応制御装置の動作を示すフローチャートである。
【図４】本発明の他の実施例によるリアルタイムシステムのＱｏＳ適応制御装置の構成を示すブロック図である。
【図５】図４のＱｏＳ適応制御器の構成を示すブロック図である。
【図６】本発明の他の実施例によるＱｏＳ適応制御装置の動作を示すフローチャートである。
【符号の説明】
【００７２】
１，２  コンピュータ
１１  タスク表
１２  実行待ちキュー
１３  スケジューラ
１４  ジョブ実行部
１５  モニタ
１６  ＱｏＳ適応制御器
２１  サービス待ちキュー
２２  サービス実行部
１６１  ＱｏＳレベル計算部
１６２−１  タスクＴ1 の制御器
１６２−２  タスクＴ2 の制御器
１６２−Ｎ  タスクＴN の制御器
【図１】
2005236456.tif 000008
【図２】
2005236456.tif 000009
【図３】
2005236456.tif 000010
【図４】
2005236456.tif 000011
【図５】
2005236456.tif 000012
【図６】
2005236456.tif 000013