(57)【特許請求の範囲】
【請求項１】
連続メディアをストリームデータとして扱うストリーム処理タスクと非連続メディアを扱うイベント駆動タスクとをスケジューリングするタスクスケジューリング方法であって、
(a) 少なくとも１つの前記イベント駆動タスクをスポラディックサーバに取り込み、
(b) 前記スポラディックサーバを１つの前記ストリーム処理タスクとみなし、そして
(c) 少なくとも１つの前記ストリーム処理タスクと前記スポラディックサーバとの間で適応デッドラインを設定するようにした、タスクスケジューリング方法。
【請求項２】
前記ステップ(c) は、(c-1) メッセージが到着したときに前記メッセージを処理すべき前記ストリーム処理タスクを起動するステップ、(c-2) 前記ストリーム処理タスクで前記メッセージの処理が終了した後前記ストリーム処理タスクの実効未処理メッセージ数を出力するステップ、および(c-3) 前記実効未処理メッセージ数に応じて前記適応デッドラインを設定するステップを含む、請求項１記載のタスクスケジューリング方法。
【請求項３】
前記ステップ(c-3) は、(c-4) 少なくとも前記タスクの重要度に従って適応デッドラインを設定するステップを含む、請求項２記載のタスクスケジューリング方法。
【請求項４】
前記ステップ(c-4) は、(c-5) 隣接する２つの前記ストリーム処理タスクの重要度を同じにするステップ、および(c-6) 前記２つのストリーム処理タスクにおける先行する前記ストリーム処理タスクにおける前記実効未処理メッセージ数が後続の前記ストリーム処理タスクの前記実効未処理メッセージ数よりも多い場合に前記重要度を高くし、少ない場合に前記重要度を低くするステップを含む、請求項３記載のタスクスケジューリング方法。
【請求項５】
前記ステップ(c-6) は、(c-7) メッセージ処理完了後に実測された処理遅延時間が推定デッドライン時刻を満たさない場合に前記重要度を高めるステップを含む、請求項４記載のタスクスケジューリング方法。
【請求項６】
前記ステップ(c-6) は、(c-8) メッセージ処理完了後に実測された処理遅延時間が前記メッセージ処理に要したＣＰＵ使用時間に対する予約したＣＰＵ使用率の比より小さい場合に前記重要度を低めるステップをさらに含む、請求項４または５記載のタスクスケジューリング方法。
【請求項７】
前記スポラディックサーバは、前記イベント駆動タスクのランキューに応じて決定される容量補充ポリシと前記ストリーム処理タスクの重要度で決定される優先度ポリシを含み、
前記ステップ(c-4) では、前記容量補充ポリシと前記優先度とに基づいて前記スポラディックサーバの前記重要度を更新する、請求項３ないし６のいずれかに記載のタスクスケジューリング方法。
【請求項８】
前記ステップ(c-4) は、(c-9) 前記ランキューが長くなると前記スポラディックサーバの重要度を高くし、短くなると前記スポラディックサーバの重要度を低くするステップを含む、請求項３ないし７のいずれかに記載のタスクスケジューリング方法。
【請求項９】
前記ステップ(c-4) は、(c-10)前記ストリーム処理タスクの重要度が高くなると前記スポラディックサーバの重要度を低くし、前記ストリーム処理タスクの重要度が低くなるとスポラディックサーバの重要度を高くするステップを含む、請求項３ないし８のいずれかに記載のタスクスケジューリング方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
この発明はタスクスケジューリング方法に関し、特にたとえば連続メディアをストリームデータとして扱うストリーム処理タスクと非連続メディアを扱うイベント駆動タスクとをスケジューリングする、タスクスケジューリング方法に関する。
【０００２】
【従来の技術】
この種の従来技術では、動画や音声に代表される連続メディアを扱うストリーム処理タスクと非連続メディアを扱うイベント駆動タスクが混在するマルチメディア環境においては、図１１に示すように、ＣＰＵ使用率（１００％）をストリーム処理タスク用とイベント駆動タスク用との間で固定的に決定して、ＣＰＵはこれらのタスクを処理していた。
【０００３】
【発明が解決しようとする課題】
しかし、この従来技術では、ストリーム処理タスクとイベント駆動タスクとの間でＣＰＵ使用率を固定的に決定しているため、実際にＣＰＵの負担がほとんどない場合であっても、その使用率が確保されるため、たとえばストリーム処理タスクの処理が過渡になった場合には、ストリーム処理タスクの時間制約を満たさないという問題が発生していた。一方、イベント駆動タスクの処理が過渡になった場合には、各イベント駆動タスクを実行するまでに長時間かかってしまうという問題があった。つまり、ＣＰＵの使用効率を低下させてしまっていた。
【０００４】
それゆえに、この発明の主たる目的は、ストリーム処理タスクの時間制約を満たし、かつイベント駆動タスクに高い応答性を発揮できる、タスクスケジューリング方法を提供することである。
【０００５】
【課題を解決するための手段】
この発明は、連続メディアをストリームデータとして扱うストリーム処理タスクと非連続メディアを扱うイベント駆動タスクとをスケジューリングするタスクスケジューリング方法であって、 (a)少なくとも１つのイベント駆動タスクをスポラディックサーバに取り込み、 (b)スポラディックサーバを１つのストリーム処理タスクとみなし、そして (c)少なくとも１つのストリーム処理タスクとスポラディックサーバとの間で適応デッドラインを設定するようにした、タスクスケジューリング方法である。
【０００６】
【作用】
連続メディアをストリームデータとして扱うストリーム処理タスクと非連続メディアを扱うイベント駆動タスクとをスケジューリングするタスクスケジューリング方法では、まず、少なくとも１つのイベント駆動タスクがスポラディックサーバに取り込まれる。このスポラディックサーバを１つのストリーム処理タスクとみなし、そして、すべてのストリーム処理タスク、すなわち少なくとも１つのストリーム処理タスクとスポラディックサーバとの間で適応デッドラインが設定される。
【０００７】
たとえば、ストリーム処理タスクが処理すべきデータ（メッセージ）が到着すると、そのストリーム処理タスクが起動される。したがって、タスクによってメッセージが処理され、メッセージが処理されると、タスクが処理すべきメッセージであり、たとえばバッファメモリに保持されている処理されていない（処理待ち）のメッセージの数（実効未処理メッセージ数）が取得される。この実効未処理メッセージ数からストリーム処理タスクの処理速度を他のストリーム処理タスクとの関係において知ることができ、したがって、実効未処理メッセージ数に応じて適応デッドラインが設定（再設定）される。これにより、処理遅延時間が調整される。このような処理を各ストリーム処理タスクについて実行することにより、各タスクの処理遅延時間が調整され、全ストリーム処理タスクの処理遅延を均一にすることができる。このため、処理の遅いストリーム処理タスクによって、システム全体の処理が遅延することがなくなり、結果的に、ＣＰＵを有効に使用することができる。
【０００８】
また、適応デッドラインは、少なくともストリーム処理タスクの重要度に従って設定或いは再設定されるので、たとえば、マルチメディア情報を扱う動的な環境に適応することができる。
【０００９】
したがって、ストリーム処理タスクを実行する毎に重要度を更新すれば、適応デッドラインも更新（再設定）される。
【００１０】
具体的には、重要度は隣接する２つのストリーム処理タスクの重要度が同じにされ、他のストリーム処理タスクにおいても同様の処理が実行され、他のストリーム処理タスクにおける実効未処理メッセージ数が取得される。そして、隣接する２つのストリーム処理タスクにおいて、先行するストリーム処理タスク（先行タスク）の実効未処理メッセージ数が後続するストリーム処理タスク（後続タスク）の実効未処理メッセージ数よりも多い場合には、先行タスクの処理が後続タスクよりも遅いと判断し、先行タスクの重要度が高くされる。逆に、先行タスクの実効未処理メッセージ数が後続タスクの実効未処理メッセージ数より少ない場合には、先行タスクの処理が後続タスクよりも速い、すなわち後続タスクの処理が遅いと判断し、先行タスクの重要度が低くされる。このように、隣接するストリーム処理タスク間で処理遅延を均一化することにより、システム全体の処理遅延を均等にすることができる。
【００１１】
また、メッセージ処理完了後に実測された処理遅延時間が推定デッドライン時刻を満たさない場合には、大きく処理遅延が発生していると判断し、処理を速めるため、重要度が高くされる。
【００１２】
さらに、メッセージ処理完了後に実測された処理遅延時間がメッセージ処理に要したＣＰＵ使用時間に対する予約したＣＰＵ利用率の比より小さい場合には、処理が速いと判断して、重要度が低くされる。
【００１３】
一方、スポラディックサーバは、上述したように、ストリーム処理タスクとみなされるが、その内部にイベント駆動タスクのランキューに応じて決定される容量補充ポリシと他のストリーム処理タスクの重要度で決定される優先度ポリシを含む。したがって、スポラディックサーバの優先度（重要度）は、容量補充ポリシと優先度ポリシとに基づいて設定（再設定）される。
【００１４】
たとえば、ランキューが長くなると、処理待ちのイベント駆動タスクが多いと判断し、イベント駆動タスクをできる限り速く実行すべく、スポラディックサーバの重要度を高くする。一方、ランキューが短くなると、処理待ちのイベント駆動タスクが少ないと判断し、他のストリーム処理タスクの時間制約を満たすべく、スポラディックサーバの重要度を低くする。
【００１５】
また、他のストリーム処理タスクの重要度が高くなるとスポラディックサーバの重要度が低くされ、他のストリーム処理タスクの重要度が低くなるとスポラディックサーバの重要度が高くされる。
【００１６】
【発明の効果】
この発明によれば、イベント駆動タスクを取り込んだスポラディックサーバをストリーム処理タスクとして適応デッドラインを設定するようにしたので、ストリーム処理タスク用とイベント駆動タスク用のＣＰＵ使用率を処理環境に適応して変化させることができる。このため、ストリーム処理タスクの時間制約を満たすことができ、かつイベント駆動タスクに高い応答性を発揮させることができる。
【００１７】
この発明の上述の目的，その他の目的，特徴および利点は、図面を参照して行う以下の実施例の詳細な説明から一層明らかとなろう。
【００１８】
【実施例】
図１を参照して、この実施例のパーソナルコンピュータ（以下、単に「ＰＣ」という。）１０は、ＣＰＵ１２を含む。ＣＰＵ１２は、バス１４を介してハードディスクドライブ（ＨＤＤ）１６、ＲＡＭ１８およびインターフェイス２０に接続される。なお、ＰＣ１０は、インターフェイス２０を介して、他のＰＣなどのマルチメディア（図示せず）に接続される。
【００１９】
ＨＤＤ１６には、周期タスク（ソフト実時間タスク）および非周期タスク（非実時間タスク）をスケジューリングするため、すなわち連続メディアと不連続メディアとを処理するためのソフトおよび他の複数のアプリケーションソフトがプログラミング（またはインストール）されており、ＣＰＵ１２の指示に従って処理が実行される。また、ＲＡＭ１８は、ＣＰＵ１２のワーキングメモリとして使用され、さらに他のマルチメディアからのデータ等を一時記録するためのバッファメモリとしても使用される。
【００２０】
なお、この実施例において、「周期タスク」を単に「タスク」という場合もある。
【００２１】
この実施例では、ストリーム処理の適応的スケジューリングポリシＡＤＭ（Ａｄａｐｔｉｖｅ  Ｄｅａｄｌｉｎｅ  Ｍｏｄｉｆｉｃａｔｉｏｎ）をストリーム処理タスクだけではなく、同一処理環境のスポラディックサーバに拡張適用する。つまり、図１で示す構成で処理される連続メディアをストリームデータとして扱うストリーム処理タスク（ソフト実時間タスク）と非連続メディアを扱うイベント駆動タスク（非実時間タスク）とをスケジューリングする。ただし、以下に列挙することを前提とする。
【００２２】
第１に、連像メディア処理はストリーム処理により行われる。第２に、連像メディアデータはその入出力装置からＶＢＲ（Ｖａｒｉａｂｌｅ  Ｂｉｔ  Ｒａｔｅ）／固定周期で生成／消費される。第３に、ストリーム処理タスクの実行時間は、ランダムに変動する。第４に、非連続メディアデータの到着はポアソン到着とする。第５に、非連続メディアを扱う非実時間タスクの実行時間は指数分布とする。第６に、複数のストリーム処理と複数の非実時間処理が混在する。
【００２３】
ここで、連続メディアデータは、動画データ或いは音声データなどの圧縮／伸長および差分処理に見られるように可変量であるため、ＶＢＲデータであると言える。
【００２４】
また、入出力装置は、図２に示す連続メディアデータのストリーム処理（パイプラインモデル）における連続メディア入力装置および連続メディア出力装置を意味する。
【００２５】
この実施例は、ストリーム処理モデルとしての連続メディア資源モデル（Linear Bounded Arrival Process: ＬＢＡＰ) に連続メディアデータすなわちＶＢＲデータ（以下、単に「データ」という。）を処理するための変更を加えたモデルに基づいている。したがって、ＬＢＡＰとこれに基づいて従来のストリーム処理モデルを説明して、従来モデルに変更を加えたＶＢＲストリーム処理モデルを説明する。その上で、ＡＤＭの適応ポリシを概説する。
【００２６】
従来の方式では、ストリームデータを一定のメッセージの到着レートと最悪実行時間とにより特徴付け、ＣＰＵ利用率を予約している。すなわち、各周期タスクの時間制約を満たすために、すべてのメッセージ処理時間が最悪実行時間である場合でも、十分に処理できるＣＰＵ利用率を予約している。したがって、従来の方式は、最悪実行時間に基づいたＣｏｎｓｔａｎｔ  Ｂｉｔ  Ｒａｔｅ（以下、「ＣＢＲ」という。）ストリーム処理として考えられる。このようなＣＢＲストリーム処理を、ＬＢＡＰのパラメータを用いて表すと、次のようになる。
＜パラメータ（１）＞
Ｒc   :constant message rate(messages/second)
Ｗmax :maximum workahead messages(messages)
Ｃmax :maximum processing time for a message(seconds/message)
ＬＢＰでは、パラメーターＷmax により示されるバースト的なデータ到着により、データ到着レートは短期間Ｒmax を超えることを許容している。このバースト的なデータ到着に伴う処理されていない (処理待ち）メッセージ数（以下、「未処理メッセージ数」という。）は、数１のように定義される。
【００２７】
【数１】
ｗn（ｍ0）＝０
ｗn（ｍi）＝ｍａｘ（０，ｗn（ｍi-1）
−（ａn（ｍi）−ａn（ｍi-1））Ｒc＋１）
なお、括弧内の“，”は“または”という意味である。以下、この実施例において同じである。
【００２８】
ただし、ｗn （ｍi ）はタスクｎにおけるｉ番目のメッセージ到着時の未処理メッセージ数、ａn （ｍi ）はタスクｎにおけるｉ番目のメッセージ到着時刻である。したがって、タスクｎにおけるＷmax は数２のように定義できる。
【００２９】
【数２】
0003957055.tif 000002
【００３０】
到着したメッセージは、未処理メッセージをすべて処理完了した後に、初めて処理対象となる。ＬＢＡＰでは、メッセージが処理対象となる論理的な時刻（論理的時刻）は、タスクｎにおけるｉ番目のメッセージが到着する論理的時刻（メッセージ論理到着時刻）ｌn （ｍi ）として、数３のように定義する（図３参照）。
【００３１】
【数３】
ｌn（ｍi）＝ａn（ｍi）＋ｗn（ｍi）／Ｒc
同じく図３を参照して、ＬＢＡＰでは、タスクｎにおけるｉ番目のメッセージにおける処理遅延時間Ｄa （ｍi）、論理処理遅延時間Ｄl（ｍi）およびデッドライン時刻ｄn（ｍi）を数４、数５および数６のように定義する。
【００３２】
【数４】
0003957055.tif 000003
【００３３】
【数５】
0003957055.tif 000004
【００３４】
【数６】
0003957055.tif 000005
【００３５】
【数７】
0003957055.tif 000006
【００３６】
ＬＢＡＰでは、このように特徴付けられたメッセージストリームの処理において、以下に列挙するように周期タスクが定義される。第１に、周期タスクの実行順は、周期タスクのデッドライン時刻に基づき、Ｅａｒｌｉｅｓｔ  Ｄｅａｄｌｉｎｅ  Ｆｉｒｓｔ（ＥＤＦ）により決定される。第２に、第１のように定義された周期タスクがパイプラインモデル（図２参照）により複数接続される。第３に、周期タスクはメッセージの到着時刻に起動される。すなわち、メッセージ到着時に周期タスクがスケジューリング対象となる。第４に、周期タスクは、メッセージ処理完了時刻に未処理メッセージが有る場合、処理完了したメッセージのデッドライン時刻を待たずに直ちに起動する（実行可能となる）。
【００３７】
上述したように、定義された時間属性において、連続メディアデータ出力装置（以下、単に「出力装置」という。）の時間制約を保証するには、連続メディアデータ入力装置（以下、単に「入力装置」という。）と出力装置との間に十分な初期位相が必要である。その初期位相は、数８のように示される。
【００３８】
【数８】
0003957055.tif 000007
【００３９】
ただし、ａout （ｍi ）は出力装置におけるｉ番目のメッセージ到着時刻、ａin（ｍ0 ）は入力装置における最初のメッセージ発生時刻、ｎは入出力装置間のパイプライン上のタスク数である。
【００４０】
したがって、出力装置の時間制約を保証する場合、最悪実行時間に基づくＣＢＲストリーム処理モデルは、大きなエンド−エンドの遅延時間が必要となる。また、最悪実行時間に基づくＣＰＵ使用量の予約は、過渡なＣＰＵ予約量となり、システム全体でのＣＰＵ利用率が低下する。
【００４１】
これを回避するため、この実施例では、メッセージ処理時間は最悪実行時間Ｃmax より短い任意の時間Ｃreq とし、また、最大未処理メッセージ数Ｗmax の代わりに実測の未処理メッセージ数ｂを用いる。そのパラメータを以下に示す。
＜パラメータ（２）＞
Ｒc   :constant message rate(messages/second)
ｂ    :actual workahead messages(messages)
Ｃreq :request processing time for a message(seconds/message)
タスクｎにおいて、レートＲc で最悪実行時間より短い時間Ｃreq を用いてＣＰＵ利用率を予約する場合、すべてのメッセージの処理時間が１／Ｒc 以下であることは保証されない。したがって、数１および数３で定義したように、未処理メッセージ数およびメッセージ論理到着時刻を予測することは困難である。
【００４２】
そこで、ＶＢＲデータ処理モデルおける時間属性は、変動する処理時間を考慮して定義することにする。具体的には、未処理メッセージ数は、ｗn （ｍi ）に代えて、任意の時刻に実測された未処理メッセージ数を用いる。つまり、タスクｎにおいて、時刻ｔに実測された未処理メッセージ数をｂn （ｔ）と表記し、実効未処理メッセージ数と呼ぶことにする。
【００４３】
また、メッセージ論理到着時刻ｌn （ｍi ）に代えて、メッセージ実効到着時刻ｅn （ｍi ）を定義する。つまり、メッセージ論理到着時刻ｌn （ｍi ）は、メッセージが初めて処理対象になると予測される論理時刻である。このことから、メッセージ実効到着時刻ｅn （ｍi ）は、タスクｎにおいて、ｉ番目のメッセージが初めて処理対象になった実際の時刻とし、数９のように定義する。
【００４４】
【数９】
ｅn （ｍ0 ）＝ａn （ｍ0 ）
ｅn （ｍi ）＝ｍａｘ（ａn （ｍi ），ｆn （ｍi-1 ））
ただし、ｆn （ｍi-1 ）は、タスクｎにおけるｉ−１番目のメッセージの処理完了時刻である。
【００４５】
続いて、デッドライン時刻について検討する。デッドライン時刻を算出するために、諭理処理遅延時間を知る必要がある。しかし、時刻ｅn （ｍi ）において、ｉ番目のメッセージは処理を完了していないため、論理処理遅延時間を知ることができない。
【００４６】
そこで、パイプラインモデルにおいて隣接するタスクｎとタスクｎ＋１とについて考える。タスクｎ＋１におけるｉ番目のメッセージが処理対象となる時刻は、タスクｎ＋１におけるｉ−１番目のメッセージの処理完了時刻ｆn+1 （ｍi-1 ）である。すなわち、タスクｎは、ｉ番目のメッセージ処理を、タスクｎ＋１におけるｉ−１番目のメッセージの処理完了時刻ｆn+1 （ｍi-1 ）までに完了すればよいと考えられる。したがって、タスクｎにおけるｉ番目のメッセージのデッドライン時刻は、数１０のように考えられる。
【００４７】
【数１０】
ｄn （ｍi ）＝ｆn+1 （ｍi-1 ）
しかし、時刻ｅn （ｍi ）において、ｆn+1 （ｍi-1 ）は、上述の論理処理遅延時間と同様に不明である。このため、時刻ｅn （ｍi ）におけるタスクｎ＋１の実効未処理メッセージ数からｆn+1 （ｍi-1 ）を数１１で示すように想定（推測）する。なお、数１１おけるｆn+1 上のバー（横棒）は、推測値であることを意味する。
【００４８】
【数１１】
0003957055.tif 000008
【００４９】
この推定値を用いると、デッドライン時刻ｄn （ｍi ）は、数１２に示すように定義される。
【００５０】
【数１２】
ｄn （ｍi ）＝ｅn （ｍi ）＋ｂn+1 （ｅn （ｍi ））／Ｒc 
ただし、その他の定義は上述したＬＢＡＰの場合と同じである。
【００５１】
次に、ＶＢＲストリーム処理モデルにおいて、最悪実行時間より短い処理時間に基づき、ＣＰＵ利用率を予約する場合におけるＶＢＲストリーム処理モデルの特性に関して検討する。具体的には、定理１〜３を定義し、それぞれについて証明する。
【００５２】
［定理１］ＶＢＲストリーム処理モデルにおいて、最悪実行時間より短い時間すなわちパラメータＣreq とＲc とによりＣＰＵ利用率を予約する場合、メッセージの処理完了時刻は、数１３で示される条件で、デッドライン時刻を満たす。
【００５３】
【数１３】
0003957055.tif 000009
【００５４】
［証明］メッセージの処理完了時刻が、デッドライン時刻を満たすためには、数１４で示すような条件となる。
【００５５】
【数１４】
ｆn ≦ｄn （ｍi ）
数１４を数９で示したメッセージ実効到着時刻の定義に従い、ａn （ｍi ）がｆn （ｍi-1 ）より大きい場合と、そうでない場合とに分けて考える。
【００５６】
まず、ａn （ｍi ）≧ｆn （ｍi-1 ）の場合には、ｅn （ｍi ）はａn （ｍi ）となるので、数９により、数１４は数１５のようになる。
【００５７】
【数１５】
ｆn （ｍi ）≦ａn （ｍi ）＋ｂn+1 （ｅn （ｍi ））／Ｒc 
また、メッセージ処理完了時刻ｆn （ｍi ）は、メッセージ到着時刻ａn （ｍi ）に処理遅延時間を加えた時刻である。したがって、数１５は数１６のようになる。
【００５８】
【数１６】
0003957055.tif 000010
【００５９】
したがって、ａn （ｍi ）≧ｆn （ｍi-1 ）の条件下で、数１６を満たす場合には、処理モデルはデッドライン時刻を満たす。
【００６０】
次に、ａn （ｍi ）＜ｆn （ｍi-1 ）の場合について考える。この場合、ｅn （ｍi ）はｆn （ｍi-1 ）となるので、数９により、数１４は数１７のようにる。
【００６１】
【数１７】
ｆn （ｍi ）≦ｆn （ｍi-1 ）＋ｂn+1 （ｅn （ｍi ））／Ｒc 
パイプラインモデルにおいて、タスクｎのメッセージ処理完了時刻ｆn （ｍi ）は、タスクｎ＋１のメッセージ処理完了時刻ａn+1 （ｍi ）と一致する。したがって、数１７は数１８のようになる。
【００６２】
【数１８】
ａn+1 （ｍi ）≦ａn+1 （ｍi-1 ）＋ｂn+1 （ｅn （ｍi ））／Ｒc 
すなわち、
ｂn+1 （ｅn （ｍi ））／Ｒc ≧ａn+1 （ｍi ）−ａn+1 （ｍi-1 ）
また、場合分けの条件（ｆn （ｍi ）＜ｆn （ｍi-1 ））も同様に、数１９ののようになる。
【００６３】
【数１９】
ａn （ｍi ）＜ａn+1 （ｍi-1 ）
ここで、数１８の右辺の式、ａn+1 （ｍi ）−ａn+1 （ｍi-1 ）について考える。この式を、処理遅延時間を用いて表すと、数２０のようになる。
【００６４】
【数２０】
0003957055.tif 000011
【００６５】
数２０は、数１９によって、数２１のようになる。
【００６６】
【数２１】
0003957055.tif 000012
【００６７】
ただし、ｘは正の数である。
【００６８】
このことから、数１９は数２２のようになる。
【００６９】
【数２２】
0003957055.tif 000013
【００７０】
したがって、ａn （ｍi ）＜ｆn （ｍi-1 ）の条件下で、数２２を満たす場合には、処理モデルはデッドライン時刻を満たす。
【００７１】
以上のように説明した２つの条件（場合分けの条件）下で、デッドラインを満たすためには、数１６および数２２の両方を満たす必要がある。つまり、数２３に示すようになる。
【００７２】
【数２３】
0003957055.tif 000014
【００７３】
したがって、定理１は成り立つ。
【００７４】
［定理２］定理１を満たすＶＢＲストリーム処理モデルにおいて、数２４を満たすならば、メッセージ処理に必要なＣＰＵ利用率は、予約したＣＰＵ利用率を超えない。
【００７５】
【数２４】
0003957055.tif 000015
【００７６】
ただし、Ｃn （ｍi ）は、タスクｎにおけるｉ番目のメッセージ処理に使用するＣＰＵ時間（ＣＰＵ使用時間）である。
【００７７】
［証明］タスクｎにおいて、１メッセージ処理当たりに予約したＣＰＵ使用時間をＹとすると、ＣＰＵ予約量はＹＲc である。したがって、タスクｎにおけるｉ番目のメッセージを処理するために使用（利用）したＣＰＵ利用率Ｕn （ｍi ）は、数２５のようになる。
【００７８】
【数２５】
0003957055.tif 000016
【００７９】
上述したように、処理モデルは定理１を満たすことから、メッセージ処理完了時刻はデッドライン時刻より小さい。したがって、数２５に示すａn （ｍi ）とｄn （ｍi ）との時間間隔は、数２６のようになる。
【００８０】
【数２６】
0003957055.tif 000017
【００８１】
この数２６を数２５に適用すると、ＣＰＵ利用率Ｕn （ｍi ）は数２７のようになる。
【００８２】
【数２７】
0003957055.tif 000018
【００８３】
タスクｎにおいて、処理に必要なＣＰＵ利用率Ｕn （ｍi ）が、予約したＣＰＵ利用率ＹＲc を越えないためには、数２８を満たす必要がある。
【００８４】
【数２８】
0003957055.tif 000019
【００８５】
この数２８から数２９が成立する。
【００８６】
【数２９】
0003957055.tif 000020
【００８７】
この数２９は、処理遅延時間は、ｉ番目のメッセージ処理に要したＣＰＵ使用時間に対するＣＰＵ利用率の比で表される時間以上であることを意味する。さらに、定理１から数２９は、数３０のようになる。
【００８８】
【数３０】
0003957055.tif 000021
【００８９】
したがって、定理２が成り立つ。
【００９０】
［定理３］ＶＢＲストリーム処理モデルにおいて、パラメータＣreq とＲc とによりＣＰＵ利用率を予約する場合、タスクｎの初期位相が数３１を満たすならば、出力装置の時間制約が満たされることが保証される。
【００９１】
【数３１】
0003957055.tif 000022
【００９２】
［証明］出力装置の時間制約を満たすためには、出力装置は１／Ｒc 時間毎にメッセージを必要とすることから、数３２を成立させる必要がある。
【００９３】
【数３２】
ａout （ｍi ）≦ａout （ｍ0 ）＋ｉ／Ｒc 
ただし、ａout （ｍi ）は、出力装置におけるｉ番目のメッセージ到着時刻である。
【００９４】
出力装置をパイプライン上における終端タスクｎの次のタスク、すなわちタスクｎ＋１として考えると、数３２は数３３のようになる。
【００９５】
【数３３】
ａn+1 （ｍi ）−ａn+1 （ｍ0 ）≦ｉ／Ｒc 
パイプラインモデルの隣接する２つのタスクにおいて、メッセージ到着時刻ａn+1 （ｍi ）とメッセージ処理完了時刻ｆn （ｍi ）とが一致することから、ａn+1 （ｍi ）は数３４のようになる。
【００９６】
【数３４】
0003957055.tif 000023
【００９７】
この数３４をｎに関して展開すると、数３５が得られる。
【００９８】
【数３５】
0003957055.tif 000024
【００９９】
この数３５のａ0 （ｍi ）は、タスク０におけるメッセージ到着時刻であるが、タスク０はパイプラインの先頭のタスクである。したがって、タスク０のメッセージは連続メディアデータ入力装置（以下、単に「入力装置」という。）から得られる。入力装置におけるメッセージの到着時刻は周期的であることから、ａ0 （ｍi ）は数３６のようになる。
【０１００】
【数３６】
ａ0 （ｍi ）＝ａ0 （ｍ0 ）＋ｉ／Ｒc 
以上より、ａn+1 （ｍi ）は、数３７のようになる。
【０１０１】
【数３７】
0003957055.tif 000025
【０１０２】
この数３７からａn+1 （ｍi ）−ａn+1 （ｍ0 ）を求めると、数３８のようになる。
【０１０３】
【数３８】
0003957055.tif 000026
【０１０４】
数３８を数３１に適用すると、数３９が得られる。
【０１０５】
【数３９】
0003957055.tif 000027
【０１０６】
したがって、定理３が成り立つ。
【０１０７】
このように定理１〜定理３で定義されるＶＢＲストリーム処理を前提として、出力装置の時間制約を満たすタスク制御について考え、この実施例のスケジューリング方法について説明する。
【０１０８】
上述した定理３により、タスクの初期位相が数２９を満たすなら、最悪実行時間より短い時間を用いてＣＰＵ利用率を予約する場合においても、出力装置の時間制約が満たされる。しかし、出力装置の時間制約を満たすためには、上述したように、各タスクに十分な初期位相が必要であるため、エンド−エンドの処理遅延時間が大きくなる。
【０１０９】
しかし、たとえば、テレビ会議システムのようなライブによるシステムでは、エンド−エンドの処理遅延時間が少ないことが要求される。したがって、十分な初期位相がない場合において、出力装置の時間制約を満たす可能性を高める制御について考える。
【０１１０】
ここで、定理３で示した数２９を見直すことにする。数２９に示したａn （ｍi ）に、パイプラインモデル（ＶＢＲストリーム処理モデル）におけるメッセージ到着時刻と処理完了時刻との関係を適用すると、数４０が得られる。
【０１１１】
【数４０】
0003957055.tif 000028
【０１１２】
ここで、（ａ0 （ｍ0 ）−ａ0 （ｍi ））は、タスク０のメッセージ到着時刻の差である。タスク０はパイプラインの最初のタスクであるため、メッセージの到着時刻は、入力装置からのメッセージ出力時刻である。したがって、メッセ一ジの到着時刻は周期的であり、（ａ0 （ｍ0 ）−ａ0 （ｍi ））は−ｉ／Ｒc である。このことから、数４０は数４１のようになる。
【０１１３】
【数４１】
0003957055.tif 000029
【０１１４】
さらに、０番目のメッセージ到着時刻からｉ番目のメッセージ到着時刻までの時間間隔をメッセージの到着間隔ごとに分割すると、数４１の括弧内は数４２で示すようになる。
【０１１５】
【数４２】
0003957055.tif 000030
【０１１６】
したがって、数４１は、数４３に示すようになる。
【０１１７】
【数４３】
0003957055.tif 000031
【０１１８】
この数４３から分かるように、各タスクにおいて、メッセージ間での処理遅延時間を均等にすると（数４３の括弧内の演算結果を０にすると）、時間制約が満たされる。しかし、各メッセージの処理遅延時間は、そのメッセージ毎に変動するため、単一のタスク内でメッセージ間の処理遅延時間を均等にすることは困難である。そこで、各タスクのメッセージ間の処理遅延時間の差異を、隣接する２つのタスク間で吸収することを考える。まず、数４３をタスクｊに関して展開すると、数４４のようになる。
【０１１９】
【数４４】
0003957055.tif 000032
【０１２０】
ここで、タスクｎにおけるｋ＋１番目のメッセージ処理遅延時間は、タスクｎ＋１におけるｋ番目のメッセージ処理遅延時間と比較されるべきであるが、タスクｎ＋１は存在しない。しかし、タスクｎ＋１は出力装置として考えられるので、メッセージ処理遅延時間の比較対象は出力装置におけるｋ番目のメッセージ処理遅延時間とする。同様に、タスク０におけるｋ番目のメッセージ処理遅延時間は、入力装置におけるｋ＋１番目のメッセージ処理遅延時間と比較する。したがって、数４４は数４５のようになる。
【０１２１】
【数４５】
0003957055.tif 000033
【０１２２】
このように、隣接する２つのタスク間のメッセージ処理遅延時間を均等にすることにより、出力装置の時間制約を満たすことが可能となる。これを実現させるため、次のような制御を行う。第１に、パイプライン上のタスクの実行機会が同じになるように各タスクの優先度（重要度）を連動させる。第２に、メッセージ処理遅延時間は実効未処理メッセージ数ｂn （ｔ）に依存することから、タスクｎのｉ番目のメッセージの処理時における実効未処理メッセージ数ｂn （ｅn （ｍi ））と後続のタスクｎ＋１のｉ番目のメッセージの処理時における実効未処理メッセージ数ｂn+1 （ｅn （ｍi ））とを比較し、前者の値が大きい場合には、タスクｎに大きな遅延が発生することが予想されるので、タスクｎの優先度を高め、処理を速める。一方、後者の値が大きい場合には、タスクｎの処理遅延は小さいことが予想されるので、タスクｎの優先度を低め、処理を遅らせる。
【０１２３】
図４に示すように、タスク１〜タスク４がパイプラインモデルに従って接続されているストリーム処理を用いて具体的に説明する。このパイプラインモデルでは、隣接するタスク１とタスク２とでは、バッファ１に溜まっているメッセージすなわちデータの量（データ量）がバッファ２に溜まっているデータ量よりも多いため、タスク１はタスク２より処理が速いと言える。また、隣接するタスク２とタスク３とでは、バッファ２に溜まっているデータ量がバッファ３に溜まっているデータ量よりも少ないため、タスク２はタスク３より処理が遅いといえる。さらに、隣接するタスク３とタスク４とでは、バッファ３に溜まっているデータ量がバッファ４に溜まっているデータ量よりも多いため、タスク３はタスク４より処理が速いといえる。
【０１２４】
したがって、隣接する２つのタスクにおいて、実効未処理データ数すなわちバッファに溜まっているデータ量を比較し、処理すべきデータのデータ量が多いタスクについては処理を速めるように、重要度を高める。一方、処理すべきデータのデータ量が少ないタスクについては処理を遅くするように、重要度を低める。したがって、全てのタスクの処理遅延時間が均一化され、処理が遅いタスクに依存して全体の処理が遅くなるのを回避している。
【０１２５】
さらに、第３に、メッセージ処理完了後に、実測された処理遅延時間が定理１すなわち数２３（数１３）を満たさないならば、処理遅延時間を小さくするため、優先度を高める。第４にメッセージ処理完了後に、実測された処理遅延時間が定理２すなわち数２９（数２４）を満たさないならば、処理遅延時間を大きくするため、優先度を低める。
【０１２６】
以上のように制御することにより、予約したＣＰＵ利用率に基づいて、出力装置の時間制約を満たし、かつエンド−エンドの処理遅延時間を小さくすることが可能となる。
【０１２７】
このようなＶＢＲストリーム処理するタスクは、横取り可能なタスクである。横取り可能なタスクとは、その実行中に、より高い優先度を持つタスクが到着した場合、実行権をより高い優先度を持つタスクに引き渡すことが可能なタスクをいう。
【０１２８】
また、ＶＢＲストリーム処理するタスクは、航空システムや原子力システムに見られる処理完了時刻に厳密なハードリアルタイムタスクと異なり、その処理完了時刻には許容される遅延幅があるソフトリアルタイムタスクとして考えられる。したがって、デッドラインに許容遅延幅を持たせることによって、タスクの優先度として用いるデッドライン時刻は、数１２で求められる時刻に許容遅延幅内で、スケジュール可能性を高める制御による優先度の修正を行った時刻とする。この時刻を適応デッドライン時刻と呼ぶことにする。
【０１２９】
以上のように、スケジュール可能性を高める制御について説明したが、このような制御は、単一のストリーム処理における制御である。しかし、マルチメディア環境においては、多地点のテレビ会議システムに見られるように、複数のストリーム処理が混在する場合が多い。すなわち、マルチメディア環境におけるストリーム処理は、パイプラインモデルにより接続されたタスク群が複数混在するタスクセットとして考えられる。
【０１３０】
このようなタスクセットでは、上述したような制御におけるスケジュールの問題は、複数のパイプラインのタスク群で上述したような時間制約を同時に満たすような状態を探し出す多重制約の問題（多重制約問題）である。
【０１３１】
この問題を回避するため、この実施例では、上述したように、ＰＤＰモデルを応用する。このＰＤＰモデルでは、多くの単純な情報処理ユニットが相互に結合し、それぞれが他のユニットから信号を受け取る。その入力信号が正の値である場合には、ユニットの状態値を高める。一方、入力信号が負の値である場合には、ユニットの状態値を低める。さらに、ユニットの状態値に応じた信号を他のユニットに送る。この相互作用をユニット毎に非同期に繰り返すことにより情報処理を行う。
【０１３２】
各ユニットの相互結合により構成されるネットワークは、多重制約の構造を表している。このネットワークに、何らかの外部条件を与え、各ユニットで非同期に相互作用の繰り返し処理を行う。すると、各ユニットは或る状態に落ち着く。その状態が或る条件での制約を最大に充足した状態を表している。
【０１３３】
以上のことから、複数のパイプラインのタスク群における制約を充足する状態を算出するために、タスク間の依存関係をＰＤＰモデルの相互結合ネットワーク（以下、単に「ネットワーク」という。）に次のように対応づける。
【０１３４】
▲１▼各ユニットの状態値（０から１までの連続値）は、各タスクの重要度とする。タスクの重要度は、最高値（１）を適応デッドライン時刻の最短時刻に対応づけ、最低値（０）を適応デッドライン時刻の最長時刻に対応づける。これにより、重要度から適応デッドライン時刻を算出する。
【０１３５】
▲２▼ユニット間の結合は、通信するタスク間では、正の重みを持たせ、通信しないタスク間では、負の重みを持たせる。したがって、正の重みを持つタスク間の結合では、ユニットの状態値に比例した正の入力が他のタスクに作用し、相互に近い状態値になる。一方、負の重みを持つタスク間の結合では、ユニットの状態値に比例した負の入力が他のタスクに作用し、互いに遠い状態値になる。これにより、同一パイプライン上のタスク群の重要度が連動し、各タスクの実行機会を同じにすることができる。
【０１３６】
▲３▼各ユニットに与えられる外部条件は、変動するタスク実行状況に対応してネットワークの動作を修正する力とする。すなわち、外部条件は、各タスクの変動する処理遅延時間に応じて、上述したような制御を次のようにネットワークに作用させる。
【０１３７】
（I)タスクｎのｉ番目のメッセージの処理時における実効未処理メッセージ数ｂn （ｅn （ｍi ））と後続するタスクｎ＋１のｉ番目のメッセージの処理時における実効未処理メッセージ数ｂn+1 （ｅn （ｍi ））とを比較し、前者の値が大きい場合には、正の入力とする。また、後者の値が大きい場合には、負の入力とする。
【０１３８】
（II）実測された処理遅延時間が定理１を満たすならば、正の入力とする。
【０１３９】
（III)実測された処理遅延時間が定理２を満たすならば、負の入力とする。
【０１４０】
以上により、複数のパイプラインのタスク群における制約を、ネットワークを動作させて処理する。
【０１４１】
しかし、ＰＤＰモデルは、ネットワークを動作させると、その状態は初期値に依存して或る制約充足度の高い状態に至り、動作は静止する。一方、ストリーム処理環境において、各タスクの処理遅延時間は、処理するメッセージによって常に変化する。ネットワークは、この変化に応じて、１つの状態に静止することなく、いくつかの制約充足度の高い状態間を移動する必要がある。
【０１４２】
このため、ＰＤＰモデルに熱力学的モデルを加える。熱力学的モデルは、温度による物質の熱揺動（高温では分子間の結合が弱まり不安定であり、低温では分子間の結合が強まり安定する性質）をＰＤＰモデルの処理において擬似する。具体的には、焼き鈍し法が加えられる。しかし、焼き鈍し法は、収束するのに時間がかかるため、制約充足度の高い状態（安定状態）との距離に応じて焼き鈍しの温度を制御する。すなわち、制約充足度の高い状態から距離が離れている場合には温度を高くし、制約充足度の高い状態に近い場合には温度を低くする。すると、ネットワークワークは、制約充足度の高い状態に素早く近づき、また外部条件の変化に敏感に対応する。この温度による熱揺動制御により、ＰＤＰモデルを各タスクの変動する処理遅延時間に連続的に動作するようにし、定理１と定理２とを満たし、かつタスク間の処理遅延時間を均一にする適応デッドライン時刻を探し続けることを可能とする。
【０１４３】
以上のような考え方に基づいたアルゴリズムで或るタスクの重要度の更新則（重要度更新則）について説明する。タスクの重要度は、ＰＤＰモデルにしたがって、他のタスクからの入力および外部条件としての入力（外部入力）により決定する。しかし、その決め方が焼き鈍し法により制御されるため、確率的に決定させる。この確率的な決定をＰＤＰモデルの状態更新則に加え、タスクの重要度更新則とする。具体的には、タスクの重要度は、数４６に従って決定される。
【０１４４】
なお、これ以降では、ユニットをタスクに対応づけるとともに、状態値を重要度に対応づけて説明する。
【０１４５】
【数４６】
0003957055.tif 000034
【０１４６】
この数４６において、タスクの重要度を高める方向へ更新する場合には、右辺の第２項の上式が採用される。一方、タスクの重要度を低める方向経更新する場合には、右辺の第２項の下式が採用される。上下どちらの式を採用するかは、後で詳細に説明する確率関数（ボルツマン関数）によって決定される。すなわち、数４６の右方に示した不当式によって決定される。
【０１４７】
また、タスクへの総入力は、図５のように示され、他のタスクからの入力（他のタスクの出力）の総和と外部入力とにより構成される。このタスクへの総入力は、数４７で示される。
【０１４８】
【数４７】
0003957055.tif 000035
【０１４９】
数４７から分かるように、他のタスクからの入力は他のタスクの重要度とそのタスク間の結合重みとの積である。このため、正の結合重みを持つ、すなわち通信するタスク（他のタスク）からはそのタスクの重要度の高さに比例した正の入力が、入力を受けるタスクに作用する。一方、負の結合重みを持つ、すなわち通信しないタスク（他のタスク）からはそのタスクの重要度の高さに比例した負の入力が、入力を受けるタスクに作用する。
【０１５０】
したがって、タスクへの総入力が大きな正の値となると、重要度更新則は高い確率でタスクの重要度を高める。逆の状態では、タスクへの総入力は大きな負の値となり、重要度更新則は高い確率で重要度を低める。すなわち、相互通信するタスクの重要度は連動して更新される可能性が高い。
【０１５１】
この実施例では、接続要求を行うタスクとその接続先のタスクとの間の結合を、正の重みを持つ結合とする。また、接続関係のないタスク間の結合は負の重みを持つ結合とする。これにより、タスク間の通信依存関係を、相互結合ネットワークとして構築する。
【０１５２】
また、上述したように、時刻ｅn （ｍi ）におけるタスクｎの実効未処理メッセージ数とタスクｎ＋１の実効未処理メッセージ数との比較結果、に基づいてネットワークの動作を修正する必要がある。その修正を外部入力として対応づけることができる。具体的には、数４８、数４９および数５０のように示される。
【０１５３】
【数４８】
0003957055.tif 000036
【０１５４】
【数４９】
0003957055.tif 000037
【０１５５】
【数５０】
0003957055.tif 000038
【０１５６】
数４８から分かるように、時刻ｅn （ｍi ）おけるタスクｎの実効未処理メッセージ数がタスクｎ＋１の実効未処理メッセージ数以上である場合には、タスクｎにおいて処理遅延が発生し始めていると判断する。このため、外部入力は、処理速度を速くするように適応デッドラインを算出するため、タスクｎの重要度を高める正の入力とする。一方、時刻ｅn （ｍi ）おけるタスクｎの実効未処理メッセージ数がタスクｎ＋１の実効未処理メッセージ数より少ない場合には、タスクｎにおける処理遅延が小さいと判断する。逆に、タスクｎ＋１における処理遅延が発生し始めていると判断する。このため、外部入力は、処理速度を遅くするように適応デッドラインを算出するため、タスクｎの重要度を低める負の入力とする。
【０１５７】
また、数４９から分かるように、処理遅延時間が定理１を満たさない場合には、処理遅延時間を小さくするように適応デッドラインを算出するため、タスクｎの重要度を高める正の入力とする。
【０１５８】
さらに、数５０から分かるように、処理遅延時間が定理２を満たさない場合には、処理遅延時間を大きくするように適応デッドラインを算出するため、タスクｎの重要度を低める負の入力とする。
【０１５９】
数４７で示したように、数４８〜数５０の総和が外部入力としてタスクに入力される。ただし、数４９および数５０においては、処理遅延時間が定理１および定理２をそれぞれ満たす場合には、適応デッドラインを調整する必要がない。したがって、重要度を更新する必要がないので、０が入力されることになる。
【０１６０】
なお、最初の周期では、タスクの実効未処理メッセージ数は０であるため、数４９において外部入力を０とすると、タスクの重要度は数４８の右辺の第１項のみによって決定される。つまり、通信依存関係があるつまり協調関係にある他のタスクの重要度によってタスクの重要度が決定される。その結果として、通信するタスクの実行開始時刻に近づけるように、タスクの適応デッドラインを設定することができる。
【０１６１】
さらに、上述したように、ＰＤＰモデルネットワークは、初期値に依存して、或る制約充足度の高い状態に至り、静止する。したがって、この実施例では、焼き鈍し法を加えることにより、これを回避している。つまり、重要度を高めるかまたは低めるかを、数５１で示すような確率関数で決定する。
【０１６２】
【数５１】
0003957055.tif 000039
【０１６３】
なお、通常の焼き鈍し法では、熱力学的モデルを応用し、或る固定の外部条件で温度を高い状態（様々な状態を激しく移動する）からゆっくりと温度を下げ、最も安定する状態を探す。しかし、この実施例で想定する動的な環境では、外部条件（外部入力）である実行未処理メッセージ数が短時間に変動するため、この方法をそのまま用いることができない。そこで、短時間に変動する外部条件に対応するため、適度な充足度とすることで収束を途中までとし、また外部変化に敏感に反応するようにしている。これを実現するため、この実施例では、制約充足度の高い状態（安定状態）からの距離により焼き鈍しの温度を制御している。
【０１６４】
たとえば、ＰＤＰモデルにおける制約充足度は、数５２のように示される。
【０１６５】
【数５２】
0003957055.tif 000040
【０１６６】
ここで、制約充足度Ｇ(t) は、次のようにすると、最大となる。つまり、外部入力が０の場合には、相互に通信するタスク集合におけるすべてのタスクの重要度を１にし、通信しないタスク集合におけるすべてのタスクの重要度を０にする。これは、相互に通信するタスクは重要度を同時に高くして処理速度を早め、その他の（通信しない）タスクは処理速度を遅らすことを意味している。このような状態が制約充足度を高くする。また、制約充足度の高い状態は、相互に通信するタスクの集合毎に存在する。
【０１６７】
この実施例では、外部入力である実行未処理メッセージ数があるため、上述した制約充足度の高い状態とは一致しない可能性が高い。しかし、相互に通信するタスクを近い時刻で実行すると、通信待ち時間が減少することから、この近傍に制約充足度の高い状態が存在していると考えられる。
【０１６８】
また、この実施例では、制約充足度の高い状態を、接続要求を行うタスク毎に設定する。その状態は、接続要求を行うタスクおよびその接続先のタスクの重要度が１となり、その他のタスクの重要度が０となるようにする。これにより、制約充足度の高い状態が比較的多く設定される。したがって、制約充足度の高い状態間の距離が短くなり、状態間の移動が容易になる。
【０１６９】
したがって、焼き鈍し温度は、数５３に従って制御される。
【０１７０】
【数５３】
0003957055.tif 000041
【０１７１】
数５３から分かるように、タスク間の相互結合ネットワークの状態が制約充足度の高い状態に近い場合には温度を低くする。その結果、確率関数は１に近い値を出力し、タスクの重要度が制約充足度の高い状態へ近づきすぎると、温度が小さな値となり、確率関数はほぼ１を出力し、タスクの重要度は制約充足度の高い特定の状態に固定化する。
【０１７２】
ただし、この実施例では、動的な環境であるため、制約充足度の高い状態は時間とともに変化する。そこで、焼き鈍し下限温度ＣＯＯＬにより、温度を下げ止まりさせ、その近傍で小さく振動させる。したがって、適度な制約充足と外部変化に敏感に反応する動作を実現することができる。一方、距離が遠い場合には、温度を高くし、大きく振動させ充足度の高い状態を発見する可能性を高める。このように制御することにより、タスクの重要度の初期値に依存することなく、外部環境の変化に応じて複数の制約充足度の高い状態を移動することができる。言い換えると、準安定状態と準安定状態を探している状態（不安定状態）との２つの状態を移動することができる。
【０１７３】
このようなタスクの重要度更新則は、タスクにおけるメッセージの実効到着時刻ｅn （ｍi ）にタスク毎に単独に適用する。これにより求められたタスクの重要度αn （ｔ）から数５４で示すように、デッドラインを修正する時刻を算出する。
【０１７４】
【数５４】
ｖn （ｍi ）＝ｈn −２ｈn αn （ｅn （ｍi ））
ただし、ｈn はタスクｎにおける処理遅延許容幅、ｖn （ｍi ）はタスクｎにおけるｉ番目のメッセージ処理におけるデッドライン時刻を修正する時間（−ｈn ≦ｖn （ｍi ）≦ｈn ）である。
【０１７５】
このｖn から、タスクエヌにおけるｉ番目のメッセージ処理の適応デッドライン時刻を数５５により求めることができる。
【０１７６】
【数５５】
0003957055.tif 000042
【０１７７】
この数５５によって算出された適応デッドライン時刻に基づいて、タスクの実効順をＥＤＦにより求める。
【０１７８】
具体的には、図１で示したＣＰＵ１２は、タスク毎に、図６に示すデッドライン設定処理を実行し、数５５に示した適応デッドラインを設定（更新）する。ただし、簡単のため、タスクｎについて処理した場合を説明し、他のタスクについての説明は省略する。
【０１７９】
ＰＣ１０でタスクをスケジューリングするためのソフトが起動されると、ＣＰＵ１２はデッドライン設定処理を開始し、ステップＳ１でタスクｎが処理すべきデータが到着したかどうかを判断する。ステップＳ１で“ＮＯ”であれば、つまりタスクｎが処理すべきデータが到着しなければ、そのままステップＳ１に戻って、データが到着するのを待つ。一方、ステップＳ１で“ＹＥＳ”であれば、つまりタスクｎが処理すべきデータが到着すれば、ステップＳ３でスケジューリング対象のタスクｎを起動する。したがって、到着したデータが処理される。
【０１８０】
続くステップＳ５では、タスクｎの実効未処理メッセージ数を取得し、ステップＳ７では、後で詳細に説明する重要度更新処理を実行する。そして、ステップＳ９では、ステップＳ７で更新された重要度に基づいて適応デッドラインを設定或いは再設定（更新）してからステップＳ１に戻る。
【０１８１】
図７を参照して、図６のステップＳ７の重要度更新処理が開始されると、ＣＰＵ１２は、ステップＳ１１で、タスクｎとタスクｎ＋１との優先度を同じ（均一）にする。続くステップＳ１３では、ｂn （ｅn （ｍi ））がｂn+1 （ｅn （ｍi ））以上かどうかを判断する。つまり、同じ時間ｅn （ｍi ）におけるタスクｎの実効未処理タスク数とタスクｎ＋１の実効未処理タスク数とを比較して、タスクｎに大きな遅延が発生するかどうかを予想している。
【０１８２】
なお、タスクｎ＋１における未実効処理タスク数は、タスクｎ＋１についての図６で示したデッドライン設定処理において取得される。
【０１８３】
ステップＳ１３で“ＹＥＳ”であれば、つまりｂn （ｅn （ｍi ））がｂn+1 （ｅn （ｍi ））以上であれば、タスクｎに大きな遅延が発生すると判断し、ステップＳ１５でタスクｎの重要度を高めてからステップＳ１９に進む。一方、ステップＳ１３で“ＮＯ”であれば、つまりｂn （ｅn （ｍi ））がｂn+1 （ｅn （ｍi ））より小さければ、タスクｎの処理遅延が小さいと判断し、ステップＳ１７でタスクｎの重要度を低めてからステップＳ１９に進む。
【０１８４】
ステップＳ１９では、処理遅延時間が数１３を満たすかどうか、すなわち定理１を満たすかどうかを判断する。ステップＳ１９で“ＹＥＳ”であれば、つまり定理１を満たす場合には、タスクｎにおけるメッセージの処理完了時刻はデッドライン時刻を満たすと判断し、そのままステップＳ２３に進む。
【０１８５】
一方、ステップＳ１９で“ＮＯ”であれば、つまり定理１を満たさない場合には、タスクｎにおけるメッセージの処理完了時刻がデッドライン時刻を越えてしまうと判断し、ステップＳ２１でタスクｎの重要度を高めてからステップＳ２３に進む。
【０１８６】
ステップＳ２３では、処理遅延時間が数２９を満たすかどうか、すなわち定理２を満たすかどうかを判断する。ステップＳ２３で“ＹＥＳ”であれば、つまり定理２を満たす場合には、タスクｎにおけるメッセージ処理に必要なＣＰＵ利用率が最悪実効時間より短い時間を用いて予約したＣＰＵ利用率を越えないと判断し、そのままリターンする。
【０１８７】
一方、ステップＳ２３で“ＮＯ”であれば、つまり定理２を満たさない場合には、タスクｎにおけるメッセージ処理に必要なＣＰＵ利用率が予約したＣＰＵ利用率を越えてしまうと判断し、ステップＳ２５でタスクｎの重要度を低めてから処理を終了する。
【０１８８】
このように、タスクｎの重要度を修正（高めたり低めたり）することによって、適応デッドラインを速くしたり、遅くらせたりすることができる。したがって、タスクｎでの処理を速めたり遅らせたりすることができる。
【０１８９】
さらに、この実施例では、スポラディックサーバを用いて、非実時間タスクであるイベント駆動タスクを上述したようなＡＤＭのソフト実時間タスクスケジュール環境に取り込む。イベント駆動タスクは、スポラディックサーバ内の任意のスケジューリング方式によって実行順が決定される。さらに、スポラディックサーバは、ストリーム処理タスクと同様に１つのソフト実時間タスクとして、ＡＤＭによってスケジューリングされる。また、スポラディックサーバは、容量補充ポリシと優先度ポリシとから構成される。
【０１９０】
まず、容量補充ポリシについて説明することにする。非連続メディアデータの到着によって実行可能状態となったイベント駆動タスクは、スポラディックサーバのランキューに接続される。スポラディックサーバは、ランキューに接続された非実時間タスクをスケジューリング処理する。このキューの待ち行列の平均長Ｌは、非連続メディアデータの到着がポアソン分布で処理時間が指数分布であると仮定すると、待ち行列理論のＭ／Ｍ／１により数５６のようになる。
【０１９１】
【数５６】
0003957055.tif 000043
【０１９２】
ただし、ρはトラフィック強度であるが、ここではＣＰＵ利用率であり、数５７のように定義される。
【０１９３】
【数５７】
0003957055.tif 000044
【０１９４】
ただし、λは平均到着率であり、μは平均サービス率である。
【０１９５】
ここで、スポラディックサーバにおけるイベント駆動タスクの平均サービス率μについて考えることにする。スポラディックサーバの最大補充量をイベント駆動タスクの平均ＣＰＵ使用時間とし、またデッドライン時間Ｔdss 、容量補充時間をＲdss とすると、イベント駆動タスクの平均サービス時間は、Ｔdss ≦Ｒdss の条件下でＲdss となる。したがって、平均サービス率μは、数５８のようになる。
【０１９６】
【数５８】
0003957055.tif 000045
【０１９７】
また、非連続メディアデータの平均到着間隔をＩとすると、平均到着率λは数５９のようになる。
【０１９８】
【数５９】
0003957055.tif 000046
【０１９９】
したがって、スポラディックサーバにおけるイベント駆動タスクのランキュー（実行可能タスクの待ち行列）の平均長Ｌは数６０のようになる。
【０２００】
【数６０】
0003957055.tif 000047
【０２０１】
イベント駆動タスクの平均応答時間は、スポラディックサーバの任意のスケジューリング方式において、スポラディックサーバにおけるイベント駆動タスクのランキューの平均長Ｌに依存して変動する。すなわち、ランキューが長くなると平均応答時間が大きくなり、またランキューが短くなると平均応答時間が減少する。したがって、数６０および図８からイベント駆動タスクの平均応答時間を小さくするために、次のようなポリシで容量補充時間Ｒdss を制御する。
【０２０２】
ランキューの長さが大きくなる場合、Ｔdss ≦Ｒdss の条件下では、スポラディックサーバの容量補充時間Ｒdss を小さくする。
【０２０３】
次に、優先度ポリシについて説明する。スポラディックサーバは、ストリーム処理タスクとＣＰＵとにおいて競合関係にある。そのため、優先度において、次のようなポリシで制御する。
【０２０４】
（１）ＣＰＵ利用率が高く過負荷の場合、ストリーム処理タスクのスケジューリング可能性を維持するためスポラディックサーバの優先度を下げる。すなわち、スポラディックサーバのデッドライン時間Ｔdss を大きくする。
【０２０５】
（２）ＣＰＵ利用率が低い場合、ストリーム処理タスクのスケジューリング可能性は十分に高いのでスポラディックサーバの優先度を上げる。すなわち、スポラディックサーバのデッドライン時間をＴdss を小さくする。
【０２０６】
スポラディックサーバにおける２つのポリシは、スポラディックサーバの容量補充時間Ｒdss とデッドライン時間Ｔdss の関係から協調関係と考える。この協調関係をＡＤＭのネットワークメカニズムにより処理するため、図９を参照して、次のようにネットワークを構成する。
【０２０７】
（１）ネットワークは容量補充ポリシのユニット（容量補充ユニット）と優先度ポリシのユニット（優先度ユニット）から構成する。
【０２０８】
（２）容量補充ユニットと優先度ユニットとの間の結合は正の重み付けとする。
【０２０９】
（３）容量補充ユニットの外部制約として、ランキューの長さが大きくなる場合、正の入力を与える。
【０２１０】
（４）優先度ユニットの外部制約として、各ストリーム処理タスクの重要度に応じて負の入力を与える。
【０２１１】
このネットワークメカニズムにより求められた２つのユニットの状態値を、ＡＤＭと同様に、それぞれの許容時間幅に重ねて適応容量補充時間と適応デッドライン時間を算出する。すなわち、スポラディックサーバの２つの時間は固定とせず、時間幅を持たせて実行状況に応じて変動させる。
【０２１２】
任意のスケジューリングポイントｔにおける適応デッドライン時間は、当該ユニットの状態値の最高値（１）を最小デッドライン時間に、最低値（０）を最大デッドライン時間に対応付けて数６１のように求める。
【０２１３】
【数６１】
0003957055.tif 000048
【０２１４】
また、任意のスケジュールポイントｔにおける適応容量補充時間は、当該ユニットの状態値の最高値を適応デッドライン時間に、最小値に適応デッドライン時間に許容時間ｈdss を加えた時間に対応付けて数６２のように求める。
【０２１５】
【数６２】
0003957055.tif 000049
【０２１６】
この実施例のポリシは、スポラディックサーバのポリシと各ストリーム処理タスクのポリシから構成される。この複数のポリシを同時に満たすために、上述
したような多重制約を処理するメカニズムをスポラディックサーバに取り込む。すなわち、ストリーム処理タスク間の相互接続ネットワークにスポラディックサーバを図９に示したように接続する。
【０２１７】
ここで、スポラディックサーバの当該ユニットと各ストリーム処理タスクのユニットとの結合は負の重み付けとする。すなわち、ストリーム処理タスクの重要度が高くなると、スポラディックサーバの重要度が低くなる。逆に、ストリーム処理タスクの重要度が低くなると、スポラディックサーバの重要度が高くなる。
【０２１８】
また、各ストリーム処理タスクのユニットからのスポラディックサーバのユニットへの入力は、スポラディックサーバのポリシ内部における優先度ポリシの当該ユニットの外部制約とする。
【０２１９】
さらに、スポラディックサーバにおいて、内部ポリシである優先度ユニットの状態値をスポラディックサーバの当該ユニットの状態値とする。
【０２２０】
以上のように、この実施例のポリシは、スポラディックサーバポリシを含む複数のポリシを処理するため、ＡＤＭのメカニズムを動作させる。また、スポラディックサーバのポリシは２つのポリシを処理するため、その内部でＡＤＭを動作させる。すなわち、この実施例のポリシは、図１０に示すように、スポラディックサーバにおいて、ＡＤＭのメカニズムのメタレベル構造を形成する。
【０２２１】
このようなＡＤＭのメカニズムをスケジューリングポイント毎に非同期に動作させて、ストリーム処理タスクの適応デッドライン時間、スポラディックサーバの適応容量補充時間と適応デッドライン時間を求める。
【０２２２】
この実施例によれば、非実時間タスクをスポラディックサーバに取り込んで、ストリーム処理タスクと同様に扱うことにより、ＡＤＭによる適応デッドラインを求めるので、実時間タスクと非実時間タスクが混在する環境下において、効率よくタスクをスケジューリングすることができる。すなわち、ＣＰＵを有効に利用することができる。
【０２２３】
また、最悪実行時間よりも短いＣＰＵ使用時間を用いてＣＰＵ利用率を予約するので、予約量が過負荷になることがなく、スケジューリング可能性を高めることができる。
【図面の簡単な説明】
【図１】この発明方法を実施する際の構成の一実施例を示す図解図である。
【図２】この発明方法が適用されるパイプラインモデルの一例を示す図解図である。
【図３】ＬＢＡＰにおけるタスクの時間属性を示すタイミングチャートである。
【図４】パイプラインモデルの各タスクにおけるメッセージ処理の一例を示す概念図である。
【図５】タスクへの総入力の構成を示す模式図である。
【図６】図１に示すＣＰＵのデッドライン設定処理を示すフロー図である。
【図７】図６に示すＣＰＵの重要度更新処理を示すフロー図である。
【図８】スポラディックサーバにおける容量補充時間によるランキューの長さの特性を示すグラフである。
【図９】この実施例のスケジューリング方法におけるネットワーク構造を示す図解図である。
【図１０】この実施例のスケジューリング方法のメタレベル構造を示す図解図である。
【図１１】従来のタスクスケジューリング方法でのストリーム処理タスクの処理とスポラディックサーバの処理とにおけるＣＰＵの使用率を説明するための図解図である。
【符号の説明】
１０  …ＰＣ
１２  …ＣＰＵ
１４  …バス
１６  …ＨＤＤ
１８  …ＲＡＭ
２０  …インターフェイス
【図１】
0003957055.tif 000050
【図２】
0003957055.tif 000051
【図３】
0003957055.tif 000052
【図４】
0003957055.tif 000053
【図５】
0003957055.tif 000054
【図６】
0003957055.tif 000055
【図７】
0003957055.tif 000056
【図８】
0003957055.tif 000057
【図９】
0003957055.tif 000058
【図１０】
0003957055.tif 000059
【図１１】
0003957055.tif 000060