(57)【要約】【課題】複数のプロセッサ上で複数の周期タスクをリアルタイムスケジューリングすることが可能か否かを、正確且つ高速に判定できるリアルタイムシステムを提供する。【解決手段】複数のプロセッサで複数のタスクを各タスクに予め定められた周期時間毎に実行するために、各タスクに予め定められた周期時間毎の各ジョブを上記複数のプロセッサに割り当てるスケジューリング手段が割り当てるジョブの周期時間内における上記複数のプロセッサ上での実行時間の分布を計算し、当該ジョブの実行時間の分布を基に、当該ジョブが予め定められた許容時刻までに終了するか否かを判定し、許容時刻までに終了しないと判定されたジョブが得られたとき、スケジューリング不可能と決定し、許容時刻までに終了すると判定された各ジョブの上記複数のプロセッサ上での実行時間の分布が収束したとき、スケジューリング可能と決定する。【選択図】      図７
2006268754.tif 000002
【特許請求の範囲】
【請求項１】
複数のプロセッサと、
前記複数のプロセッサで複数のタスクを各タスクに予め定められた周期時間毎に実行するために、各タスクに予め定められた周期時間毎の各ジョブを前記複数のプロセッサに割り当てるスケジューリング手段と、
を備え、前記スケジューリング手段が割り当てた各ジョブを前記複数のプロセッサで実行するリアルタイムシステムにおけるスケジューリング可能性判定方法であって、
前記スケジューリング手段が割り当てる前記ジョブの前記周期時間内における前記複数のプロセッサ上での実行時間の分布を計算する第１のステップと、
前記ジョブの実行時間の分布を基に、当該ジョブが予め定められた許容時刻までに終了するか否かを判定する第２のステップと、
前記第２のステップで、前記許容時刻までに終了しないと判定されたジョブが得られたとき、スケジューリング不可能と決定する第３のステップと、
前記第２のステップで前記許容時刻までに終了すると判定された各ジョブの前記実行時間の分布が収束したか否かを判定する第４のステップと、
前記実行時間の分布が収束したとき、スケジューリング可能と決定する第５のステップと、
を有することを特徴とするスケジューリング可能性判定方法。
【請求項２】
前記第４のステップは、前記複数のタスクの全ての周期時間の最小公倍数の時間差のある第１及び第２の時刻のそれぞれにおいて既に前記周期時間が開始されている各タスクの当該周期時間内の未実行のジョブを基に前記実行時間の分布が収束したか否かを判定し、
前記各タスクの当該周期時間内の未実行のジョブが前記第１及び第２の時刻で同一であるとき、収束と判定することを特徴とする請求項１記載のスケジューリング可能性判定方法。
【請求項３】
前記第４のステップは、各タスクの実行開始時刻のうち最も遅い実行開始時刻以降の前記複数のタスクの全ての前記周期時間の最小公倍数で区切られた連続する２つの時間区間で、前記実行時間の分布が同一となるとき、収束と判定することを特徴とする請求項１記載のスケジューリング可能性判定方法。
【請求項４】
前記スケジューリング手段は、各タスクの前記周期時間毎の各ジョブを、その優先順位に従って前記複数のプロセッサに割り当てることを特徴とする請求項１記載のスケジューリング可能性判定方法。
【請求項５】
前記スケジューリング手段は、前記ジョブの前記許容時刻を基に、各ジョブを前記複数のプロセッサに割り当てることを特徴とする請求項１記載のスケジューリング可能性判定方法。
【請求項６】
前記スケジューリング手段は、
前記複数のタスクのうちの任意の第１のタスクと任意の第２のタスクについて、前記第１のタスクの２つのジョブの実行開始時刻の時間差及び前記第２のタスクの２つのジョブの実行開始時刻の時間差が、前記複数のタスクのそれぞれの周期時間の最小公倍数の整数倍である場合、前記第１のタスクの２つのジョブのうちの先に実行されるジョブが前記第２のタスクの２つのジョブのうち先に実行されるジョブよりも優先的に実行されるときには、前記第１のタスクの２つのジョブのうちの後に実行されるジョブを前記第２のタスクの２つのジョブのうち後に実行されるジョブよりも優先的に実行するスケジューリングアルゴリズムを用いて、各タスクの前記周期時間毎の各ジョブを前記複数のプロセッサに割り当てることを特徴とする請求項５記載のスケジューリング可能性判定方法。
【請求項７】
複数のプロセッサと、
前記複数のプロセッサで複数のタスクを各タスクに予め定められた周期時間毎に実行するために、各タスクに予め定められた周期時間毎の各ジョブを前記複数のプロセッサに割り当てるスケジューリング手段と、
を備え、前記スケジューリング手段が割り当てた各ジョブを前記複数のプロセッサで実行するリアルタイムシステムにおけるスケジューリング可能性判定方法であって、
前記複数のタスクのそれぞれの実行開始時刻のうち最も遅い実行開始時刻以降に、前記複数のタスクの全ての周期時間の開始時が一致するグリッド時刻を計算する第１のステップと、
前記スケジューリング手段が割り当てる前記ジョブの前記周期時間内における前記複数のプロセッサ上での実行時間の分布を計算する第２のステップと、
前記ジョブの実行時間の分布を基に、当該ジョブが予め定められた許容時刻までに終了するか否かを判定する第３のステップと、
２番目の前記グリッド時刻までに前記スケジューリング手段が割り当てる各ジョブが前記許容時刻までに終了するときには、スケジューリング可能と決定する第４のステップと、
２番目の前記グリッド時刻までに、前記許容時刻までに終了しないと判定されたジョブが得られたとき、スケジューリング不可能と決定する第５のステップと、
を有することを特徴とするスケジューリング可能性判定方法。
【請求項８】
複数のプロセッサと、
前記複数のプロセッサで複数のタスクを各タスクに予め定められた周期時間毎に実行するために、各タスクに予め定められた周期時間毎の各ジョブを前記複数のプロセッサに割り当てるスケジューリング手段と、
を備え、前記スケジューリング手段が割り当てた各ジョブを前記複数のプロセッサで実行するリアルシステムにおいて、
前記スケジューリング手段が割り当てる各ジョブの前記周期時間内における前記複数のプロセッサ上での実行時間の分布を計算する計算手段と、
前記ジョブの実行時間の分布を基に、当該ジョブが予め定められた許容時刻までに終了するか否かを判定する第１の判定手段と、
前記第１の判定手段で、前記許容時刻までに終了しないと判定されたジョブが得られたとき、スケジューリング不可能と決定する第１の決定手段と、
前記第１の判定手段で前記許容時刻までに終了すると判定された各ジョブの前記実行時間の分布が収束したか否かを判定する第２の判定手段と、
前記実行時間の分布が収束したとき、スケジューリング可能と決定する第２の決定手段と、
を具備したことを特徴とするリアルタイムシステム。
【請求項９】
前記第２の判定手段は、前記複数のタスクの全ての周期時間の最小公倍数の時間差のある第１及び第２の時刻のそれぞれにおいて既に前記周期時間が開始されている各タスクの当該周期時間内の未実行のジョブを基に前記実行時間の分布が収束したか否かを判定し、前記各タスクの当該周期時間内の未実行のジョブが前記第１及び第２の時刻で同一であるとき、収束と判定することを特徴とする請求項８記載のリアルタイムシステム。
【請求項１０】
前記複数のタスクのそれぞれの実行開始時刻のうち最も遅い実行開始時刻以降に、周期的に前記複数のタスクのそれぞれの周期時間の開始時が一致するグリッド時刻があるか否かを判定する第３の判定手段をさらに備え、
前記第１の決定手段は、前記複数のタスクに周期的に前記グリッド時刻がある場合には、２番目の前記グリッド時刻までに前記スケジューリング手段が割り当てる各ジョブが前記許容時刻までに終了するときに、スケジューリング可能と決定することを特徴とする請求項８載のリアルタイムシステム。
【請求項１１】
前記スケジューリング手段は、ＥＤＦ（Ｅａｒｌｉｅｓｔ  Ｄｅａｄｌｉｎｅ  Ｆｉｒｓｔ）アルゴリズムを用いて、各ジョブを前記複数のプロセッサに割り当てることを特徴とする請求項６記載のリアルタイムシステム。
【請求項１２】
複数のプロセッサと、
前記複数のプロセッサで複数のタスクを各タスクに予め定められた周期時間毎に実行するために、各タスクに予め定められた周期時間毎の各ジョブを前記複数のプロセッサに割り当てるスケジューリング手段と、
を備えたコンピュータに、
前記スケジューリング手段が割り当てる前記ジョブの前記周期時間内における前記複数のプロセッサ上での実行時間の分布を計算する第１のステップと、
前記ジョブの実行時間の分布を基に、当該ジョブが予め定められた許容時刻までに終了するか否かを判定する第２のステップと、
前記第２のステップで、前記許容時刻までに終了しないと判定されたジョブが得られたとき、スケジューリング不可能と決定する第３のステップと、
前記第２のステップで前記許容時刻までに終了すると判定された各ジョブの前記実行時間の分布が収束したか否かを判定する第４のステップと、
前記実行時間の分布が収束したとき、スケジューリング可能と決定する第５のステップと、
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のプロセッサ上で複数の周期タスクをリアルタイムスケジューリングにより実行するリアルタイムシステムに関する。
【背景技術】
【０００２】
リアルタイムシステムは、「タスクごとに決められた制限時間内に必ずこのタスクの処理を完了させなければならない」という時間的制約を受けたコンピュータシステムである。一般に、タスクごとに決められた制限時間のことを「デッドライン」、デッドライン内にタスクの処理が完了しないことを「デッドラインミス」と呼び、デッドラインミスはリアルタイムシステムにおいては絶対に起こってはいけないことである。
【０００３】
代表的なリアルタイムシステムの例としては、航空管制システム、プラント制御監視システム、医療システムなどがある。例えば、航空管制システムは、航空機の衝突事故防止のため、航空機間や航空機と他の障害物との間の安全間隔を設定する。この際、例えば飛行機同士が１秒以内に衝突するかどうか判定するというタスクに注目すると、このタスクの処理を２秒かかって行ったのではまったく意味がなく、航空管制システムは厳格な時間制約の上で動作しなければならない。
【０００４】
デッドラインミスを一切許さないという厳格な時間制約のもとで機器を動かすことを「リアルタイムスケジューリング」と呼び、これは以下に説明を行う２つの方法から構成される。
【０００５】
１．スケジューリング方法
２．リアルタイムスケジューリング可能性判定方法
第一に、スケジューリング方法に関して説明を行う。「飛行機の衝突を検知する処理」に代表されるタスクは、リアルタイムシステムに搭載されている有限個のプロセッサ上で実行される。１つのプロセッサが一度に処理できるタスクは１つのみであるので、リアルタイムシステムで処理するべきタスクが複数存在する場合には、有限個のプロセッサを時分割で複数個のタスクでシェアし、どのタイミングで、どのプロセッサ上で、どのタスクを実行するかをスケジューリングする。この方法のことを、ここでは、スケジューリング方法と呼ぶことにする。
【０００６】
第二に、リアルタイムスケジューリング可能性判定方法に関して説明を行う。デッドラインミスを一切許さないという厳格な時間制約のもとでリアルタイムシステムを動かすためには、システムの処理能力を超えたタスクを受け付けないことが必須である。このため、リアルタイムシステムは、タスク集合とスケジューリング方法が与えられ、与えられたタスク集合を与えられたスケジューリング方法によってスケジューリングした際に、すべてのタスクの時間制約が守られるかどうか（デッドラインミスを起こすか否か）を判定し、この結果を用いてシステムで受け入れるタスクを決定する。この判定方法のことを、ここでは、リアルタイムスケジューリング可能性判定方法と呼ぶことにする。
【０００７】
タスクの時間制約が守られるかどうかは、タスクに依存することは言うまでもないが、同時にスケジューリング方法にも依存する。タスク群の実行に必要な処理能力の合計が、リアルタイムシステムの処理能力よりはるかに小さい場合には、どのようなスケジューリング方法であっても大抵の場合デッドラインミスのないタスク実行を実現可能である。また逆に、タスク群の実行に必要な処理能力の合計が、リアルタイムシステムの処理能力を超えてしまっている場合には、どのようなスケジューリング方法であってもデッドラインミスを防ぐことは不可能である。しかしながら、タスク群の実行に必要な処理能力の合計が、リアルタイムシステムの処理能力とちょうど同じである場合や、処理能力よりも少しだけ小さい場合には、スケジューリング方法によって、デッドラインミスのないタスク実行を実現可能である場合、デッドラインミスが起こってしまう場合の両方のケースがあり得る。これに対応し、リアルタイムスケジューリング可能性判定方法は、タスク集合とスケジューリング方法の２つを入力とし、リアルタイムタイムスケジューリング可能であるかまたは不可能であるかの判定結果を返す。
【０００８】
実際に、リアルタイムシステムに新規タスクの投入要求が到着したら、以下の手続きを行う。第一に、リアルタイムスケジューリング可能性判定方法を用いて、新規タスクを受け入れた場合に、新規タスクとリアルタイムシステム上で実行中のすべてのタスクの時間制約が、スケジューリング方法によって守られるかどうか（デッドラインミスを起こさないかどうか）を判定し、守られると判定された場合に、新規タスクの投入を受け入れる。
【０００９】
第二に、スケジューリング方法を用いて、新規タスクとリアルタイムシステム上で実行中のすべてのタスクのスケジューリングを行い、スケジューリング結果に従ってタスクを実行する。
【００１０】
スケジューリング方法においては、各タスクがデッドラインミスを起こさないで実行できるように、適切なプロセッサを適切な期間だけ適切なタスクに割り当てることが重要である。各タスクの処理が制限時間以内に終了するように、各タスクが利用するプロセッサをスケジューリングすることで、デッドラインミスのないタスク実行を実現する。
【００１１】
周期タスクのスケジューリング方法の具体例としては、ＥＤＦ(Earliest Deadline First )アルゴリズムが知られている（例えば、非特許文献１参照）。ＥＤＦアルゴリズムは、デッドラインが早いタスクに対して優先的に早い時刻にプロセッサを割り当てるアルゴリズムである。
【００１２】
また、リアルタイムスケジューリング可能性判定方法としては、ＥＤＦアルゴリズムによるリアルタイムスケジューリングが可能であるかどうかを判定する方法が知られている（例えば、非特許文献２参照）。
【００１３】
さらに、リアルタイムスケジューリング可能性判定方法としては、スケジューリング方法を実際に用いて仮想的にタスクのスケジューリングを実行することにより、タスクのすべての周期においてデッドライミスが発生していないことを検査する方法も知られている（例えば、非特許文献３参照）。
【００１４】
非特許文献２の判定方法は１つのタスクに同時に割り当てることが可能なプロセッサが１つである場合を前提とした方法であり、同時に複数のプロセッサを必要とするタスクについては考慮されていない。タスクによっては、その処理効率を高めるために同時に複数のプロセッサを必要とするものがある。従って、１つのタスクに同時に割り当てることが必要なプロセッサ数が複数である場合にも利用可能なスケジューリング可能性判定方法を提供することが必要である。またこの判定方法は、実際にはリアルタイムスケジューリング可能であるにもかかわらず、リアルタイムスケジューリング不可能と判定される場合があり、判定精度の面でも不十分である。
【００１５】
また、スケジューリング方法を実際に用いて仮想的にタスクのスケジューリングを実行することにより、タスクのすべての周期においてデッドライミスが発生していないことを検査する方法は、判定にかかる計算時間が長いため現実的ではない。
【非特許文献１】J. W. S. Liu著, “Real-Time Systems”, Prentice Hall, 2000
【非特許文献２】T. P. Baker著, “An Analysis of EDF Schedulability on a Multiprocessor”, FSU Computer Science Technical Report TR-030202, 2003
【非特許文献３】J. F. Hermant et all著, “Real-Time Fixed and Dynamic Priority Driven Scheduling Algorithms: Theory and Experience”, Inria Technical Report, 1996
【発明の開示】
【発明が解決しようとする課題】
【００１６】
従来は、複数の周期タスクを複数のプロセッサ数で実行する場合に、リアルタイムスケジューリングすることが可能であるか否かを正確且つ高速に判定することができないという問題点があった。
【００１７】
そこで、本発明は、上記問題点に鑑み、複数のプロセッサ上で複数の周期タスクをリアルタイムスケジューリングするこが可能であるか否かを正確且つ高速に判定することができるスケジューリング可能性判定方法、及びそれを用いたリアルタイムシステムを提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明は、複数のプロセッサで複数のタスクを各タスクに予め定められた周期時間毎に実行するために、各タスクに予め定められた周期時間毎の各ジョブを上記複数のプロセッサに割り当てるスケジューリング手段が割り当てるジョブの周期時間内における上記複数のプロセッサ上での実行時間の分布を計算し、当該ジョブの実行時間の分布を基に、当該ジョブが予め定められた許容時刻までに終了するか否かを判定し、許容時刻までに終了しないと判定されたジョブが得られたとき、スケジューリング不可能と決定する。また、許容時刻までに終了すると判定された各ジョブの上記実行時間の分布が収束したとき、スケジューリング可能と決定する。
【発明の効果】
【００１９】
本発明によれば、複数のプロセッサ上で複数の周期タスクをリアルタイムスケジューリングすることが可能か否かを、正確且つ高速に判定することができる。
【発明を実施するための最良の形態】
【００２０】
以下、本発明の実施形態について図面を参照して説明する。
【００２１】
なお、以下の第１及び第２の実施形態では、複数のプロセッサ上で複数の周期タスクスをリアルタイムスケジューリングするリアルタイムシステムについて説明する。
【００２２】
図１は、本発明の第１の実施形態に係るリアルタイムシステムの構成例を示したものである。このリアルタイムシステムは、例えば組み込みシステムとして使用されるコンピュータシステムであり、複数のタスクをその時間制約の範囲内でリアルタイムに実行する。
【００２３】
このリアルタイムシステムは、マスタープロセッサユニット(ＭＰＵ:Master Processing Unit)１と、複数の（ここでは、例えば３つの）バーサタイルプロセッサユニット(ＶＰＵ:Versatile Processing Unit)２ａ〜２ｃ（なお、これらを区別する必要がない場合には、ＶＰＵ２と呼ぶ）と、バス３と、共有メモリ４と、Ｉ／Ｏ(input/output）コントローラ５、およびＩ／Ｏデバイス６を含んでいる。
【００２４】
ＭＰＵ１、複数のＶＰＵ２、共有メモリ４、Ｉ／Ｏコントローラ５は、バス３によって相互に接続されている。
【００２５】
ＭＰＵ１は、リアルタイムシステムの動作を制御するメインプロセッサであり、共有メモリ４内に格納されたオペレーティングシステム（ＯＳ:Operating System)１０を実行する。各ＶＰＵ２は、ＭＰＵ１の管理の下で各種の処理を実行するプロセッサである。リアルタイム性が要求される複数のタスクは、複数のＶＰＵ２上で実行される。複数のタスクのそれぞれは、同時に１個以上のプロセッサを必要とする。オペレーティングシステム１０は、各タスクに１個以上のＶＰＵをリアルタイムに割り当てる。
【００２６】
オペレーティングシステム１０は、リアルタイムスケジューリング可能性判定プログラム１０ａ及びスケジューリングプログラム１０ｂを含み、各プログラム１０ａ、１０ｂがＭＰＵ１により実行されて、当該コンピュータシステムにリアルタイムスケジューリング可能性判定機能（以下、簡単にスケジューリング可能性判定機能と呼ぶこともある）及びスケジューラ機能を実現させる。
【００２７】
リアルタイムスケジューリング可能性判定機能は、リアルタイム性が要求される複数の周期タスクを複数のＶＰＵ２上で、例えばＥＤＦアルゴリズムを用いてリアルタイムスケジューリングすることが可能であるかどうかを判定するスケジューリング可能性判定処理を実行する。スケジューリング可能性判定処理の各ステップは、スケジューリング可能性判定プログラム１０ａに記述されている。スケジューリング可能性判定処理は、与えられたタスクの集合に対し、スケジューリングプログラム１０ｂによりスケジューリングしながら共有メモリ４上に、ジョブ実行のタイムテーブルを生成する。そして、このタイムテーブルを基に、上記リアルタイムスケジューリングすることが可能か否かを判定する。
【００２８】
リアルタイムスケジューリングすることが可能であることが判定された場合、スケジューラ機能は、実際に複数の周期タスクを複数のＶＰＵ２上で、例えばＥＤＦアルゴリズムを用いてリアルタイムスケジューリングする。ＥＤＦアルゴリズムは、上述したように、デッドラインが早いタスクに対して優先的に早い時刻にプロセッサを割り当てるアルゴリズムである。上記スケジューラの機能を実現するためのアルゴリズム（例えば、ＥＤＦアルゴリズムのような複数のタスクを各タスクの優先度に基づきスケジューリングするアルゴリズム）が、上記スケジューリングプログラム１０ｂに記述されている。
【００２９】
スケジューリング可能性判定処理は、例えば、あるアプリケーションプログラムの実行要求が発生したときに実行される。例えば、コンピュータシステムの（例えばバス３に接続された）入出力装置（Ｉ／Ｏデバイス６）からのリクエストや、アプリケーションプログラムの実行などにより、オペレーティングシステム（ＯＳ）１０が、新たなアプリケーションプログラム（新たなタスク）の実行を要求するための例えば「割り込み」を検知したときに、リアルタイムスケジューリング可能性判定プログラム１０ａがＭＰＵ１により実行される。
【００３０】
図１４は、図１のコンピュータシステムにおいて、例えば、あるアプリケーションプログラム（新たなタスク）の実行要求が検知されたときの処理動作について説明するためのフローチャートである。
【００３１】
新たなアプリケーションプログラム（新たなタスク）の実行要求が検知されると（ステップＳ１０１）、当該新たなタスクの実行開始時刻であるタスクのリリース時刻、当該タスクを周期的に実行するための周期時間、当該タスクの実行に利用されるプロセッサの数（利用プロセッサ数）、上記周期時間毎に処理すべきジョブの処理時間及び上記周期時間毎のジョブの処理開始時から上記処理時間が終了するまでの許容時間（デッドライン時間）を含む当該新たなタスクのパラメタ情報が共有メモリ４のＯＳ１０の実行のために予め定められた作業領域にロードされる。その結果、新たなアプリケーションプログラム内の複数のタスク（新たなタスク）と既に実行されているアプリケーションプログラム内の複数のタスクを含むタスク集合の各タスクについて、図４に示すようなパラメタ情報が当該作業領域に記憶されている。
【００３２】
そして、ＭＰＵ１は、図４に示すようなパラメタ情報を読込ながら、リアルタイムスケジューリング可能性判定プログラム１０ａを実行する（ステップＳ１０２）。
【００３３】
タスク集合の各タスクに対し、スケジューリング可能と判定されたならば（ステップＳ１０３）、次に、スケジューリングプログラム１０ｂが実行されて、新たなタスクと既存のタスクを含むタスク集合について、ケジューリングを行いながら、各タスクがＶＰＵ２ａ〜２ｃで実行される（ステップＳ１０４）。
【００３４】
一方、新たなタスクと既存のタスクを含むタスク集合の中に、デッドラインミスを発生する可能性があると判定されたタスクが１つでもあれば、新たなタスクの実行を拒否し（ステップＳ１０５）、スケジューラ機能は、新たなアプリケーションプログラム内の複数のタスク（新たなタスク）のスケジューリングは実行しない。スケジューリングプログラム１０ｂを実行して、スケジューリングしながら、既に実行されているアプリケーションプログラムの各タスクをＶＰＵ２ａ〜２ｃで継続して実行する（ステップＳ１０６）。これにより、デッドラインミスが発生することを事前に防止することができる。
【００３５】
図２は、スケジューリング可能性判定処理の概略を説明するための図である。
【００３６】
リアルタイムスケジュール可能性判定機能には、スケジューリングすべきタスク集合とスケジューリングアルゴリズムとが入力される。各タスクのタスクパラメタ情報は、そのタスクに対応するアプリケーションプログラムから共有メモリ４内の所定の領域にロードされ、ＯＳ、すなわちリアルタイムスケジューリング可能性判定プログラムを実行しているＭＰＵ１に渡される。リアルタイムスケジューリング可能性判定機能は、これら入力された情報を利用して、リアルタイムスケジューリング可能性判定処理を実行する。そして、リアルタイムスケジュール可能性判定機能は、判定結果(リアルタイムスケジューリング可能である／リアルタイムスケジューリング不可能である)をＯＳに返す。この判定結果を基に、スケジューラ機能は、スケジューリングを行う。
【００３７】
ここで、第１及び第２の実施形態で対象とするタスクについて詳しく説明する。ここで対象とするタスクは、周期タスクと呼ばれるものであり、各タスクは、リリース時刻、周期時間、利用プロセッサ数、上記周期時間毎に処理すべきジョブの処理時間及び上記周期時間の開始時からジョブが終了するまでの許容時間（デッドライン時間）を含むパラメタ情報を有する。各タスクは周期時間毎の複数の「ジョブ」と呼ばれるタスク実行単位の繰り返しから構成される。「リリース時刻」にリアルタイムシステムに投入されたタスクでは、「周期時間」に等しい時間ごとにこのタスクの新しいジョブがリリースされ、ジョブリリース時に「利用プロセッサ数」個以上の空きプロセッサが存在する場合には、ジョブの実行を開始し、存在しない場合にはジョブは実行待ち状態に入る。または、既に実行中の優先順位の低いジョブを一時中断させて、実行を開始する。リリースされた各ジョブは、ジョブリリース時刻（周期時間の開始時刻）から「デッドライン時間」に等しい時間内に、「利用プロセッサ数」に等しい数のプロセッサを同時に用いて、「処理時間」に等しい時間だけ実行されなければならない。ここで、ジョブリリース時刻にデッドライン時間を加えた時刻（つまりジョブの実行が完了しなければならない時刻）を「絶対デッドライン時刻」と呼ぶことにする。複数のタスクが存在する場合に、タスクごとにリリース時刻、周期時間、利用プロセッサ数、処理時間、デッドライン時間が異なっていて構わない。
【００３８】
図３は、周期タスクの具体例を示したもので、横軸は時間軸、縦軸は各プロセッサを表している。また、図３では、スケジューリングに利用可能な総プロセッサ数が「３」であるリアルタイムシステムにおいて、リリース時刻が「０」、周期時間が「１００ｍｓ」、利用プロセッサ数が「２」、処理時間が「５０ｍｓ」、デッドライン時間が「８０ｍｓ」であるタスクを実行した例を示している。
【００３９】
タスクの実行の様子が、タスクリリース時刻から３周期分だけ示されている。各周期時間において、処理時間「５０ｍｓ」のジョブが２個のプロセッサを同時に用いて実行される。図３では、各ジョブの実行が終了する時刻（実行終了時刻）はジョブリリース時刻から絶対デッドライン時刻までの期間内に収まっている（デッドラインミスは発生していない）。
【００４０】
次に、スケジューラ機能におけるスケジューリング方法について説明する。一般に、スケジューリング方法は、現在プロセッサ上で実行中のジョブや、実行待ちのジョブを管理し、実行中のジョブが終了した際や、実行待ちのジョブが増加した際に、空きプロセッサを探して、または実行中のジョブの中で優先度が低いジョブを一時中断して、実行待ちジョブの中で最も優先度が高いジョブの実行を開始するという手続きを繰り返して、どのジョブを、どのタイミングで、どのプロセッサを用いて実行するかスケジューリングする。
【００４１】
特に、第１及び第２の実施形態では、以下の条件を満たすスケジューリング方法を用いている。周期タスク集合中の全てのタスクの周期時間の最小公倍数をＬとし、タスクｉ１の２つのジョブｊ１及びｊ２、タスクｉ２の２つのジョブｊ３及びｊ４について、
ジョブｊ２のリリース時刻−ジョブｊ１のリリース時刻
＝ジョブｊ４のリリース時刻−ジョブｊ３のリリース時刻
＝Ｌの整数倍
を満たすタスクｉ１の２つのジョブｊ１及びｊ２、タスクｉ２の２つのジョブｊ３及びｊ４をどのように選んでも、
１．スケジューリング方法は、ジョブｊ１をジョブｊ３よりも優先的に実行する場合には、ジョブｊ２をジョブｊ４よりも優先的に実行する。
【００４２】
２．スケジューリング方法は、ジョブｊ３をジョブｊ１よりも優先的に実行する場合には、ジョブｊ４をジョブｊ２よりも優先的に実行する。
【００４３】
上記条件のことを、ここでは、「タスクの優先度に関する条件」と呼ぶことにし、第１及び第２の実施形態では「タスクの優先度に関する条件」を満たすスケジューリング方法のみを対象とする。
【００４４】
ＥＤＦアルゴリズムは、デッドライン（絶対デッドライン時刻）が早いジョブを優先して実行するアルゴリズムである。同一の絶対デッドライン時刻を持つジョブが複数存在する場合に常に特定のタスクのジョブを優先的に実行するという制約付きのＥＤＦアルゴリズムは上記条件を満たすスケジューリング方式の１つである。以下、特に混乱のない限り、制約付きＥＤＦアルゴリズムのことを単にＥＤＦアルゴリズムと呼ぶことにする。ＥＤＦアルゴリズムは「タスクの優先度に関する条件」を満たすスケジューリング方式の１つである。
【００４５】
以下において、スケジューリング方法がＥＤＦアルゴリズムである場合を例にとり、タスク集合がリアルタイムスケジューリング可能であるかどうか判定する方法を示す。
【００４６】
ＥＤＦアルゴリズムを実際に用いて仮想的にタスクのスケジューリングを行い、各タスクの実行に係る「全て」の周期時間においてデッドライミスが発生していないことを検査する(すべてのジョブに関してデッドラインミスが発生していないことを検査する)方法は、判定にかかる計算時間が長いため現実的ではない。
【００４７】
そこで、本実施形態では、ＥＤＦアルゴリズムを実際に用いて仮想的にタスクのスケジューリングを行い、タスクのすべての周期時間ではなく、「一部」の早い時刻の周期時間のみにおいてデッドライミスが発生しているか否かを検査し、その結果を用いてリアルタイムスケジューリングが可能であるか否か判定する。ここでは、ＭＰＵ１でスケジューリング可能性判定プログラム１０ａを実行し、与えられたタスクの集合に対し仮想的にスケジューリングしながら各ジョブをＶＰＵ２ａ〜２ｃで実行する場合の各ジョブの各周期時間毎の実行開始時刻や実行終了時刻などを含む実行時間の分布を計算し、図５に示すようなタイムテーブルを共有メモリ４上に生成することを、シミュレーションと呼ぶことがある。スケジューリング可能性判定処理は、このシミュレーションを行うことにより、リアルタイムスケジューリングが可能であるか否かを判定する。
【００４８】
生成されるタイムテーブルは、仮想的にスケジューリングされた各ジョブを各ＶＰＵ２ａ〜２ｃ（複数のプロセッサ）で実行した場合に、各ジョブの周期時間毎の実行時間の分布を示している。なお、図５に示すような、各ジョブが複数のプロセッサ上で実行されたときの実行時間の分布をジョブ実行パターンと呼ぶ（後述）。
【００４９】
より具体的には、以下の方法でリアルタイムスケジューリング可能性判定を行う。タスクの集合に対するシミュレーションでは、ＥＤＦアルゴリズムが、現在プロセッサ上で実行中のジョブや、実行待ちのジョブを管理し、実行中のジョブが終了した際や、新たなジョブがリリースされ実行待ちジョブが増加した際に、空きプロセッサを探して、または実行中のジョブの中で優先度が低いジョブを一時中断して、最も優先度が高い実行待ちジョブの実行を開始するという手続きを繰り返す。この際、リアルタイムスケジューリング判定方法も、現在プロセッサ上で実行中のジョブや、実行待ちのジョブを管理し、
１．全てのタスクの周期の最小公倍数をＬとしたとき、タスクの実行パターンが時間間隔Ｌを基準として収束したかどうか、
２．実行中のジョブがデッドラインミスを起こしていないかどうか、
の２つのチェックを行なう。より厳密には、タスクのジョブ実行パターンが時刻Ｔにおいて収束しているとは、
１．時刻ｔ(Ｔ≦ｔ)においてタスクｉのジョブが実行している場合には、時刻ｔ−Ｌにおいてもタスクｉのジョブが実行している。
【００５０】
２．時刻ｔにおいてタスクｉのジョブが実行していない場合には、時刻ｔ−Ｌにおいてもタスクｉのジョブが実行していない。
【００５１】
という関係が、すべてのタスクｉに関して満たされている状態であると定義する。
【００５２】
なお、ここで、ジョブ実行パターンとは、図５に示すように、複数のプロセッサにおける各タスクの各ジョブの実行時間の分布である。なお、図５では、１つのプロセッサについてのジョブ実行パターンを示している。
【００５３】
ここでのリアルタイムスケジューリング可能性判定方法は、複数のプロセッサで実行された各ジョブがデッドラインミスを起こさず、ジョブ実行パターンが収束している場合には、収束以降のタスクをスケジューリングすることなくリアルタイムスケジューリング可能であると判定する。また、もしジョブがデッドラインミスを起こしている場合にはリアルタイムスケジューリング不可能であると判定する。
【００５４】
図４に示すように、リリース時刻「９．５」、周期時間「２」、利用プロセッサ数「２」、処理時間「０．４」、デッドライン時間「０．４」のタスクＡと、リリース時刻「０」、周期時間「５」、利用プロセッサ数「１」、処理時間「３．８」、デッドライン時間「５」のタスクＢについて、ＥＤＦアルゴリズムを用いてスケジューリングする場合を例にとり説明する。
【００５５】
図５は、図４に示した２つのタスク、すなわち、タスクＡ及びタスクＢについて、ＥＤＦアルゴリズムを用いてスケジューリングしたときのジョブ実行パターンを示している。なお、図５では、１つのプロセッサ上での、各タスクの実行期間を示している。また、横軸は時刻を表し、タスクの実行期間をタスクごとに横線で表してあり、１段目はタスクＢのリリース時刻「０」から時刻「２０」まで、２段目が時刻「２０」から時刻「４０」までである。
【００５６】
タスクＢは、時刻「０」にリリースされ、タスクＢの周期時間「５」内に、当該周期時間のジョブｂ１を処理時間「３．８」の間実行される。また、時刻「１０」からの周期時間では、当該周期時間のジョブｂ３が３つに分割されて、実行されている。ジョブｂ３は、実行開始時刻「１０」に実行が開始され、「１．５」の間実行された後、「０．４」間をおいて、再び「１．６」の間実行される。そして、「０．４」間をいて再び「０．７」の間実行されてる。ジョブｂ３の実行終了時刻は「４．６」である。  またタスクＡは、時刻「９．５」にリリースされ、タスクＡの周期時間「２」内に、当該周期時間のジョブａ１を処理時間「０．４」の間実行されている。以降、周期時間「２」毎に当該周期時間のジョブａ２〜ａ１６ｇがそれぞれ処理時間「０．４」の間実行されている。
【００５７】
タスクＡ及びタスクＢの周期時間の最小公倍数Ｌの値は「１０」であり、時刻「２０」においてタスクのジョブ実行パターンが収束している。また、時刻「２０」以前にはタスクのジョブ実行パターンは収束していない。
【００５８】
例えば、タスクＢのリリース時刻「９．５」からタスクＡの周期「２」とタスクＢの周期「５」の最小公倍数である時間「１０」だけ経過した時刻「１９．５」にはタスクのジョブ実行パターンは収束していない。
【００５９】
このように、ジョブ実行パターンが収束するとは、複数のタスク（ここでは、例えばタスクＡ及びタスクＢ）のそれぞれのリリース時刻のうち、最も遅いリリース時刻（例えば、タスクＡのリリース時刻「９．５」）以降に、複数のタスクの全ての周期時間の最小公倍数に対応する時間（例えばタスクＡとタスクＢの周期時間の最小公倍数「１０」）で区切られた連続する２つの時間区間（例えば、時刻「１０」から時刻「２０」までの第１の時間区間と、時刻「２０」から時刻「３０」までの第２の時間区間）でジョブ実行パターンが同一であるということである。図５では、上記第１の時間区間と第２の時間区間とでジョブ実行パターンが同一であるため、第１及び第２の時間区間の境界の時刻「２０」でタスクＡとタスクＢのジョブ実行パターンが収束していると云う。
【００６０】
スケジューリング可能性判定処理では、ＥＤＦアルゴリズムのような各タスクの優先度に基づき複数のプロセッサに各タスクのジョブを割り当てるスケジューリングアルゴリズムを用いて、シミュレーションを行っている。従って、上記ジョブ実行パターンは、各タスクに予め定められた、当該タスクを実行する際に用いるプロセッサの数、リリース時刻、周期時間、周期時間毎のデッドライン時間、当該タスクの周期時間毎のジョブを実行するために要する時間（処理時間）、及び各タスクの優先度を基に、スケジューリングアルゴリズムを用いたスケジューリングにより、各プロセッサで各タスクの周期時間毎のジョブを実行した場合の各プロセッサ上でのジョブ実行パターンを示している。
【００６１】
ジョブにデッドラインミスが発生していないとは、当該ジョブが実行される周期時間の開始時刻（ジョブリリース時刻）から絶対デッドライン時刻までの時間内（デッドライン時間内）に、当該ジョブが終了しているということである。言い換えると、ジョブの実行終了時刻が絶対デッドライン時刻までの時間内であるということである。
【００６２】
タスクのジョブ実行パターンが収束しているかどうかは、以下に導入するキャリーインを計算することにより求めることが可能である。
【００６３】
キャリーインとは、ある時刻におけるタスクの未実行の仕事量（ジョブ）のことである。タスクｉのジョブのうち、時刻Ｔにおいてすでにリリースされているものの集合をＪとする。Ｊに属するジョブの中には、
種別１）時刻Ｔにおいて実行が終了しているもの
種別２）時刻Ｔにおいて実行途中であるもの
種別３）時刻Ｔにおいて実行が開始されていないもの
の３種類が存在するが、種別２及び種別３においてまだ実行されていない仕事量の合計をＷとした場合、時刻ＴにおけるタスクｉのキャリーインをＷと定義する。
【００６４】
図６は、タスクＡとタスクＢのキャリーインを説明するための図で、タスクＡの２つのジョブであるジョブａｘ１、ジョブａｘ２、タスク２の２つのジョブｂｘ１、ジョブｂｘ２うち、時刻Ｔにおいてすでに周期時間が開始されている（リリースされている）ジョブの集合Ｊは｛ジョブａｘ１、ジョブａｘ２、ジョブｂｘ１｝であり、Ｊのジョブは、
１．時刻Ｔにおいて実行が終了しているもの：ジョブａｘ１
２．時刻Ｔにおいて実行途中であるもの：ジョブｂｘ１
３．時刻Ｔにおいて実行が開始されていないもの：ジョブａｘ２
と分類される。時刻Ｔにおけるジョブａｘ２の未実行の仕事量はＷＡ、時刻Ｔにおけるジョブｂｘ１の未実行の仕事量はＷＢであるので、
１．時刻ＴにおけるタスクＡのキャリーインはＷＡ
２．時刻ＴにおけるタスクＢのキャリーインはＷＢ
である。
【００６５】
全てのタスクのリリース時刻のうち最も遅いリリース時刻をＲ、すべてのタスクの周期の最小公倍数をＬとしたとき、すべてのタスクｉについて、時刻Ｔ（Ｒ＋Ｌ≦Ｔ）におけるキャリーインの値が、時刻Ｔ−Ｌにおけるキャリーインの値と同じである場合、時刻Ｔにおいてキャリーインが収束していると定義する。時刻Ｔにおいてキャリーインが収束しているとき、時刻Ｔでジョブ実行パターンが収束している。
【００６６】
図５において、時刻「９．５」のおけるタスクＡのキャリーインは「０」、タスクＢのキャリーインは「０」であるのに対して、時刻「１９．５」におけるタスクＡのキャリーインは「０」、タスクＢのキャリーインは「０．１」である。従って、キャリーインの値が異なっており、時刻「１９．５」ではまだタスクのジョブ実行パターンは収束していない。
【００６７】
一方、時刻「１０」のおけるタスクＡのキャリーインは「０」、タスクＢのキャリーインは「０」であり、時刻「２０」におけるタスクＡのキャリーインは「０」、タスクＢのキャリーインは「０」である。従って、キャリーインの値は同じであり、時刻「２０」ではタスクのジョブ実行パターンが収束している。
【００６８】
このように、複数のタスクのそれぞれのリリース時刻のうち最も遅いリリース時刻（例えば、図５においてタスクＡのリリース時刻「９．５」）以降において、複数のタスクの全ての周期時間の最小公倍数の時間差（例えば、図５では、「１０」）のある第１の時刻（例えば、図５において、時刻「１０」）及び第２の時刻（例えば、図５において、時刻「２０」）において、既に周期時間が開始されている各タスクの当該周期時間内の未実行のジョブが同一であるとき、ジョブ実行パターンが収束していると判定することができるのである。
【００６９】
スケジューリング方法がＥＤＦアルゴリズムである場合に、タスク集合がリアルタイムスケジューリング可能であるかどうか判定する方法、すなわち、図１４のステップＳ１０２におけるリアルタイムスケジューリング可能性判定処理について、図７のフローチャートを参照して説明する。
【００７０】
スケジューリング可能性判定処理は、例えば、あるアプリケーションプログラムの実行の要求（新たなタスクの実行要求）を検知したときに実行される。この場合、スケジュール可能性判定機能は、そのアプリケーションプログラム内の複数のタスクと既に実行されているアプリケーションプログラム内の複数のタスクとを含む全てのタスクのそれぞれについて、デッドラインミスを発生する可能性があるかどうかを判定する。
【００７１】
新たなアプリケーション（新たなタスク）の実行要求が検知されたとき、スケジュール可能性判定処理の実行が開始され、まず、そのアプリケーションプログラム内の複数のタスクと既に実行されているアプリケーションプログラム内の複数のタスクとを含む全てのタスクについて、スケジューリングプログラム１０ｂを用いてスケジューリングして、最も優先順位の高いジョブから順に実行するシミュレーションを行う（ステップＳ２０１）。前述したように、スケジューリングアルゴリズムは、現在プロセッサ上で実行中のジョブや、実行待ちのジョブを管理し、実行中のジョブが終了したとき、実行待ちのジョブが増加したとき（新たなジョブがリリースされたとき）に、空きプロセッサを探して、または実行中のジョブの中で優先度が低いジョブを一時中断して、実行待ちジョブの中で最も優先度が高いジョブをプロセッサ上で実行開始するという手続きを繰り返して、どのジョブを、どのタイミングで、どのプロセッサを用いて実行するかスケジューリングする。そこで、ここでは、スケジューリングに従い、新たなジョブがリリースされる度に、当該ジョブリリース時刻において、キャリーインが収束しているか否かを判定し、実行中のジョブが終了する度に当該ジョブがデッドラインミスを起こしているか否かを判定する。
【００７２】
すなわち、上記シミュレーションにおいて、新たなジョブがリリースされたときには（ステップＳ２０２）、ステップＳ２０５へ進み、当該ジョブリリース時刻において、キャリーインが収束しているか否かを判定し、収束していないと判定された場合には、ステップＳ２０１へ戻り、スケジューリングに従い、優先順位の高いジョブから実行を開始する。すなわち、当該ジョブを複数のプロセッサで実行した場合の当該ジョブの周期時間内における実行時間の分布を計算する。そして、実行中のジョブが終了したときには（ステップＳ２０２）、ステップＳ２０３へ進み、当該ジョブの実行時間の分布を基に、がデッドラインミスを起こしているか否かを判定し、デッドラインミスを起こしていない場合には、ステップＳ２０１へ戻る。
【００７３】
ステップＳ２０３において、終了したジョブがデッドラインミスを起こしている場合には、この時点で、リアルタイムスケジューリング不可能と判定し（ステップＳ２０４）、スケジューリング可能性判定処理を終了する。
【００７４】
ステップＳ２０５において、新たなジョブがリリースされた時刻（リリース時刻）においてキャリーインが収束している場合には、この時点で、リアルタイムスケジューリング可能と判定し（ステップＳ２０６）、スケジューリング可能性判定処理を終了する。
【００７５】
なお、ステップＳ２０５においてキャリーインが収束している場合、キャリーインが収束している時刻までに実行された各ジョブは、ステップＳ２０３においてデッドラインミスは発生していないと判定されている。
【００７６】
上記ステップＳ２０３では、当該ジョブの実行終了時刻が絶対デッドライン時刻までの時間内である場合、すなわち、当該ジョブのリリース時刻（周期時間の開始時刻）から当該ジョブ（タスク）に予め定められているデッドライン時間までに、（絶対デッドライン時刻までの時間内）に、当該ジョブが終了している場合には、デッドラインミスは発生していないと判定し、そうでない場合にはデッドラインミスが発生していると判定する。
【００７７】
また、上記ステップＳ２０５では、新たなジョブがリリースされた時刻（ジョブリリース時刻）と、当該時刻より、判定対象の全タスクのそれぞれの周期時間の最小公倍数の時間だけ前の時刻とでタスク毎のキャリーインを求め、両時刻でタスク毎のキャリーインが同一の場合には収束したと判定し、異なる場合には収束していないと判定する。
【００７８】
図８は、図７に示したスケジューリング可能性判定処理動作をより具体的に示したフローチャートである。
【００７９】
新たなタスクの実行要求が検知されたとき、スケジュール可能性判定処理の実行が開始され、まず、そのアプリケーションプログラム内の複数のタスクと既に実行されているアプリケーションプログラム内の複数のタスクとを含む全てのタスクのリリース時刻のうち、最も早いリリース時刻（最小リリース時刻）、最も遅いリリース時刻（最大リリース時刻）、及び全てのタスクの周期の最小公倍数を求め、それぞれ、Ｒｍｉｎ、Ｒｍａｘ、Ｌとする（ステップＳ１）。
【００８０】
時刻ＴをＲｍｉｎとし、空の実行待ちジョブリストＬｉｓｔを作成する（ステップＳ２）。
【００８１】
そして、時刻Ｔ以降で最初にリリースされるジョブｉを求め、そのリリース時刻をＴｉとする。また、時刻Ｔ以降で最初に実行終了するジョブｊを求め、その実行終了時刻をＴｊとし（ステップＳ３）、ステップＳ４へ進む。
【００８２】
ステップＳ４において、Ｔｉ≦Ｔｊの場合（時刻Ｔの直後に、ジョブｉがリリースされる時刻が到来する場合）には、ステップＳ５へ進み、Ｔｉ＞Ｔｊの場合（時刻Ｔの直後に、ジョブｊが終了する時刻が到来する場合）にはステップＳ１１へ進む。
【００８３】
ステップＳ５では、（ａ）ジョブｉを実行待ちジョブリストＬｉｓｔに追加し、（ｂ）現在実行中のジョブの中にジョブｉよりも絶対デッドライン時刻が早いジョブが存在する場合には、それらのジョブを時刻Ｔｉにおいて一時実行中断し、実行待ちジョブリトＬｉｓｔに追加し、ステップＳ６へ進む。
【００８４】
ステップＳ６では、実行待ちジョブリストＬｉｓｔ中で最も絶対デッドライン時刻が早いジョブをｋとおき、ステップＳ７へ進む。
【００８５】
ステップＳ７では、時刻Ｔｉにおいてジョブｋを実行可能な空きプロセッサが存在する場合には、ステップＳ８へ進み、ジョブｋを実行待ちジョブリストＬｉｓｔから削除し、ジョブｋの実行を開始し（ステップＳ８）、ステップＳ６へ戻る。
【００８６】
一方、ステップＳ７において、時刻Ｔｉにジョブｋを実行可能な空きプロセッサが存在しない場合には、ステップＳ９へ進み、時刻Ｔ後に最初にリリースされるジョブのリリース時刻Ｔｉにおいてキャリーインが収束しているかどうかチェックする（ステップＳ９）。すなわち、ジョブｉがリリースされる時刻と、当該時刻より、判定対象の全タスクのそれぞれの周期時間の最小公倍数の時間だけ前の時刻とでタスク毎のキャリーインを求め、両時刻でタスク毎のキャリーインが同一の場合には収束したと判定し、異なる場合には収束していないと判定する。
【００８７】
キャリーインが収束している場合には（ステップＳ９）、ステップＳ１０へ進み、リアルタイムスケジューリング可能と判定して終了する（ステップＳ１０）。キャリーインが収束していない場合には（ステップＳ９）、ステップＳ９´へ進み、ＴをＴｉに更新して（ステップＳ９´）、ステップＳ３へ戻る。
【００８８】
上記ステップＳ４において、Ｔｉ＞Ｔｊの場合にはステップＳ１１へ進み、ステップＳ１１では、ジョブｊがデッドラインミスを起こしているかどうかチェックする。
【００８９】
すなわち、ジョブｊの実行終了時刻が、ジョブｊのリリース時刻から、当該ジョブに予め定められている絶対デッドライン時刻までの時間内である場合には、デッドラインミスを起こしていないと判定し、ジョブｊが絶対デッドライン時刻までに終了していない場合には、デッドラインミスを起こしていると判定する。
【００９０】
ジョブｊがデッドラインミスを起こしている場合には（ステップＳ１１）、ステップＳ１２へ進み、リアルタイムスケジューリング不可能と判定して終了する（ステップＳ１２）。ジョブｊがデッドラインミスを起こさない場合には（ステップＳ１１）、ステップＳ１１´へ進み、Ｔ＝Ｔｊとして（ステップＳ１１´）、さらにステップＳ３へ戻る。
【００９１】
次に、図１４のステップＳ１０２における他のリアルタイムスケジューリング可能性判定処理について、図９に示すフローチャートを参照して説明する。
【００９２】
図７及び図８に示したリアルタイムスケジューリング可能性判定処理は、スケジューリングに従い、新たなジョブがリリースされる度に、当該ジョブリリース時刻において、キャリーインが収束しているか否かを判定し、実行中のジョブが終了する度に当該ジョブがデッドラインミスを起こしているか否かを判定する場合を示している。
【００９３】
図９では、実行中のジョブが終了する度に当該ジョブがデッドラインミスを起こしているか否かを判定するとともに、キャリーインが収束しているか否かを判定する場合を示している。なお、図９において、図７と同一部分には同一符号を付し、異なる部分について説明する。
【００９４】
すなわち、図９では、ステップＳ２０１で、スケジュール可能性判定対象の全てのタスクについて、スケジューリングプログラム１０ｂを用いてスケジューリングして、最も優先順位の高いジョブから順に実行するシミュレーションを行う（ステップＳ２０１）。このシミュレーションにおいて、新たなジョブがリリースされたときには（ステップＳ２０２）、ステップＳ２０１へ戻る。
【００９５】
上記シミュレーションにおいて、実行中のジョブが終了したときには（ステップＳ２０２）、ステップＳ２０３へ進み、当該ジョブがデッドラインミスを起こしているか否かを判定する。デッドラインミスを起こしていない場合には、さらにステップＳ２０５´へ進み、当該ジョブの実行終了時刻において、キャリーインが収束しているか否かを判定する。
【００９６】
ステップＳ２０３において、終了したジョブがデッドラインミスを起こしている場合には、この時点で、リアルタイムスケジューリング不可能と判定し（ステップＳ２０４）、スケジューリング可能性判定処理を終了する。
【００９７】
ステップＳ２０５´において、ジョブの実行終了時刻においてキャリーインが収束している場合には、この時点で、リアルタイムスケジューリング可能と判定し（ステップＳ２０６）、スケジューリング可能性判定処理を終了する。
【００９８】
なお、ステップＳ２０５´においてキャリーインが収束している場合、キャリーインが収束している時刻までに実行された各ジョブは、ステップＳ２０３においてデッドラインミスは発生していないと判定されている。
【００９９】
上記ステップＳ２０３では、処理の終了したジョブのリリース時刻（周期時間の開始時刻）から当該ジョブ（タスク）に予め定められているデッドライン時間内（絶対デッドライン時刻までの時間内）に、当該ジョブが終了している場合には、デッドラインミスは発生していないと判定し、そうでない場合にはデッドラインミスが発生していると判定する。
【０１００】
また、上記ステップＳ２０５´では、当該ジョブの実行終了時刻と、当該実行終了時刻より、判定対象の全タスクのそれぞれの周期時間の最小公倍数の時間だけ前の時刻とでタスク毎にキャリーインを求め、両時刻でタスク毎のキャリーインが同一である場合には、キャリーインが収束したと判定し、異なる場合には収束していないと判定する。
【０１０１】
ここで、図７及び図９に示したスケジューリング可能性判定処理では、常に正しい判定結果を返すこと（タスク集合が実際にリアルタイムスケジューリング可能である場合には「リアルタイムスケジューリング可能」という判定結果を返し、実際にリアルタイムスケジューリング不可能である場合には「リアルタイムスケジューリング不可能」という判定結果を返すこと）を証明し、図７及び図９のスケジューリング可能性判定処理の妥当性について述べる。
【０１０２】
証明すべき命題は、次の２点である。
【０１０３】
第１の命題）タスク集合について、スケジューリングアルゴリズムを用いてリアルタイムスケジューリング可能な場合には、キャリーインが収束する。
【０１０４】
第２の命題）タスク集合がスケジューリングアルゴリズムを用いてリアルタイムスケジューリング不可能な場合には、デッドラインミスが発生する。また、デッドラインミスが発生するのは、タスク集合がスケジューリングアルゴリズムを用いてリアルタイムスケジューリング不可能な可能な場合に限る。
【０１０５】
これら２つの命題のうち、第２の命題に関しては自明であるので証明は省略し、第１の命題に関してのみ証明する。
【０１０６】
まず始めに、タスクｉの時刻ＴにおけるキャリーインをＣＩ（ｉ，Ｔ）とすると、ＣＩ（ｉ，Ｔ）≦ＣＩ（ｉ，Ｔ＋Ｌ）の関係が成り立つ（キャリーインの単調性が成り立つ）ことを証明する。
【０１０７】
証明は背理法で行なう。キャリーインの単調性が成り立たないと仮定し、ＣＩ（ｉ，Ｔ＋Ｌ）＜ＣＩ（ｉ，Ｔ）を満たす最も小さなＴをＴ１、このときのｉをｉ１と置く。また、タスクｉ１のジョブのうち周期内に時刻Ｔを含むジョブをｊ１、タスクｉ１のジョブのうち周期内に時刻Ｔ＋Ｌを含むジョブをｊ２、ジョブｊ１の周期開始時刻（リリース時刻）をＲ１と置く。この時、ジョブｊ２のリリース時刻はＲ１＋Ｌである。
【０１０８】
ＣＩ（ｉ１，Ｔ１＋Ｌ）＜ＣＩ（ｉ１，Ｔ）が成り立つということは、ジョブｊ１が時刻Ｒ１からＴ１の間に実行される時間より、ジョブｊ２が時刻Ｒ１＋Ｌから時刻Ｔ１＋Ｌの間に実行される時間の方が短いことを意味する。つまり、時刻Ｒ１から時刻Ｔ１までの期間内の時刻Ｔ３において、ジョブｊ１は実行していないが、時刻Ｔ３＋Ｌにおいてジョブｊ２が実行している、という条件を満たす時刻Ｔ３（Ｒ１≦Ｔ３≦Ｔ１）が存在する（時刻Ｔ３はそのような条件を満たす時刻の中で最も小さいものであるとする）。このことから、タスクｉ３を適切に選ぶと、図１０に示すように、タスクｉ３のジョブｊ３が時刻Ｔ３において実行しているが、タスクｉ３のジョブｊ４が時刻Ｔ３＋Ｌにおいて実行していないという状況が必ず成り立つ。
【０１０９】
ジョブｊ３が時刻Ｔ３において実行しているということは、ジョブｊ３はジョブｊ１よりも優先度が高く、時刻Ｔ３＋Ｌにおいてｊ４が実行していないということは、
１．ジョブｊ４はジョブｊ２よりも優先度が低い
２．ジョブｊ４は時刻Ｔ３＋Ｌにおいて実行を終了している
のいずれかである。
【０１１０】
ジョブｊ４がジョブｊ２より優先度が低いとすると、前述の「タスクの優先度に関する条件」に反する。また、ジョブｊ４は時刻Ｔ３＋Ｌにおいて実行を終了しているとすると、ＣＩ（ｉ３，Ｔ３＋Ｌ）＜ＣＩ（ｉ３，Ｔ３）となり、Ｔの極小性に反する。
【０１１１】
以上のことから、キャリーインの単調性が成り立つことが証明された。
【０１１２】
次に、タスク集合がスケジューリングアルゴリズムを用いてリアルタイムスケジューリング可能な場合には、キャリーインが収束することを証明する。
【０１１３】
証明は背理法で行なう。タスク集合がスケジューリングアルゴリズムを用いてリアルタイムスケジューリング可能であり、キャリーインが収束しない場合があると仮定する。キャリーインが収束しないことと、先に証明を行なったキャリーインの単調性を組み合わせると、あるタスクのキャリーインは増加し続けることが言える。キャリーインが増加し続けるということは、いつかはデッドラインミスが発生する、つまりリアルタイムスケジューリング不可能であることを意味し、不合理を生じる。これは仮定が誤っていたことを意味し、以上のことから、タスク集合がスケジューリングアルゴリズムを用いてリアルタイムスケジューリング可能な場合には、キャリーインが収束することが証明できた。
【０１１４】
以上より、図７及び図９のスケジューリング可能性判定方法の妥当性が示された。
【０１１５】
以上説明したように、上記第１の実施形態によれば、実際のスケジューリングに用いるスケジューリングアルゴリズム（スケジューリングプログラム１０ｂ）を用いてシミュレーションを行うことにより、複数のプロセッサ（ＶＰＵ２ａ〜２ｃ）に割り当てられたジョブが上記複数のプロセッサで実行したときの周期時間内の実行時間の分布を計算し、当該ジョブが当該ジョブに予め定められた許容時刻（絶対デッドライン時刻）までに終了している否かを判定し、許容時刻までに終了していると判定された各ジョブの上記複数のプロセッサ上での実行時間の分布（ジョブ実行パターン）が収束したときに、スケジューリング可能と決定し、上記許容時刻までに終了していないジョブ（デッドラインミスを起こすジョブ）が得られたときには、スケジューリング不可能と決定する。
【０１１６】
このような構成により、判定対象の複数のタスクに対し、ジョブ実行パターンが収束するまでシミュレーションを行うことによりスケジューリング可能と判定し、デッドラインミスを起こすジョブを１つでも検知したときには、その時点でスケジューリング不可能と判定するので、リアルタイムスケジューリングの可否を高速にしかも正確に判定することができる。
【０１１７】
各タスクの実行開始時刻（リリース時刻）のうち最も遅い実行開始時刻後のできるだけ早い時期に、スケジューリングが可能か否かを正確に判定することができる。
【０１１８】
なお、スケジューリング可能性判定処理を予め定められた時間行ったが、ジョブ実行パターンが収束せず、しかもデッドラインミスを起こすジョブも検知されない場合には、予め定められた時間が経過した時点でスケジューリング不可能と判定するのが望ましい。
【０１１９】
（第２の実施形態）
上記第１の実施形態では、スケジューリング可能性判定処理は、判定対象の各タスク（周期タスク）については何ら制限をすることなく適用することが可能である。しかし、判定対象の全タスクが、当該タスクのデッドライン時間が当該タスクの周期時間以内であり、かつ、全てのタスクの周期時間の開始時が一致する時刻があり、このような時刻が周期的に到来する場合には、図７のステップＳ２０５のキャリーインの収束の判定を省略し、デッドラインミスが発生するか否かを判定することによりスケジューリングの可否を判定することができる。
【０１２０】
図１１は、第２の実施形態に係るリアルタイムシステムの構成例を示したものである。このリアルタイムシステムは、例えば組み込みシステムとして使用されるコンピュータシステムである。なお、図１１において、図１と同一部分には同一符号を付し、異なる部分についてのみ説明する。すなわち、図１１のＯＳ１０には、図１のリアルタイムスケジューリング可能性判定プログラム１０ａに対応する第１のスケジューリング可能性判定プログラム１０ａ及びスケジューリングプログラム１０ｂの他に、第１のスケジューリング可能性判定プログラム１０ａを簡略化した第２のスケジューリング可能性判定プログラム１０ｄと、第１及び第２のスケジューリング可能性判定プログラム１０ａ、１０ｄのうちのどちらを選択すべきかを決定するための判定プログラム１０ｃが含まれている。
【０１２１】
第１のスケジューリング可能性判定プログラム１０ａを用いてＭＰＵ１により実行される第１のスケジューリング可能性判定処理は、図７あるいは図９と同様である。また、第２のスケジューリング可能性判定プログラム１０ｄを用いてＭＰＵ１により実行される第２のスケジューリング可能性判定処理は、判定対象の全タスクが、当該タスクのデッドライン時間が当該タスクの周期時間以内であり、かつ、全タスクの周期時間の開始時が周期的に一致する場合に実行される。
【０１２２】
判定プログラム１０ｃを用いてＭＰＵ１により実行される判定処理は、例えば、あるアプリケーションプログラムの実行要求が発生したときに実行される。
【０１２３】
図１５は、図１１のコンピュータシステムにおいて、例えば、あるアプリケーションプログラム（新たなタスク）の実行要求が検知されたときの他の処理動作について説明するためのフローチャートである。なお、図１５において、図１４と同一部分には同一符号を付し、異なる部分についてのみ説明する。
【０１２４】
すなわち、図１５では、図１４のステップＳ１０２が、ステップＳ１１１ａ〜Ｓ１１１ｃに置き換わっている。
【０１２５】
新たなタスクの実行要求が検知されると（ステップＳ１０１）、まず、上記判定処理が実行され、新たなタスク及び既存のタスクを含む全タスクの図４に示すようなパラメタ情報を基に、以下の２つの条件を満たすか否かチェックする（ステップＳ１１１ａ）。
【０１２６】
第１の条件）各タスクのデッドライン時間が当該タスクの周期時間以内である。
【０１２７】
第２の条件）全タスクの周期時間の開始時が一致する時刻が存在し、このような時刻が周期的に到来する。
【０１２８】
新たなタスク及び既存のタスクを含む全タスクについて、上記第１及び第２の条件をいずれも満たす場合には（ステップＳ１１１ａ）、ステップＳ１１１ｂへ進み、第２のスケジューリング可能性判定処理を行い（ステップＳ１１１ｂ）、そうでない場合には、ステップＳ１１１ｃへ進み、第１のスケジューリング可能性判定処理を行う（ステップＳ１１１ｃ）。
【０１２９】
ＭＰＵ１は、共有メモリ４に記憶されている各タスクのパラメタ情報を読込ながら、上記判定処理、上記第１、第２のスケジュール可能性判定処理を行う。
【０１３０】
ステップＳ１０３以降の処理は、図１４と同様である。
【０１３１】
第１のスケジューリング可能性判定処理は、図７あるいは図８と同様であるので、説明は省略し、第２のスケジューリング可能性判処理について説明する。
【０１３２】
第２のスケジューリング可能性判定処理の判定対象となるタスク集合は、前述の通り、上記第１及び第２の条件を満たしている。スケジューリングアルゴリズム（スケジューリングプログラム１０ｂ）を実際に用いて上記シミュレーションを行い、（各タスクのすべての周期ではなく）一部の早い時刻の周期のみにおいてデッドライミスが発生しているか否かを検査し、その結果を用いてリアルタイムスケジューリング可能であるか否かを判定を行うという点では、第１のスケジューリング可能性判定処理と同一である。しかしながら、条件が限定されたタスク集合のみの判定を行えばよいため、より単純で高速な方法により判定可能である。
【０１３３】
上記第２の条件が示すように、全てのタスクの周期時間の開始時が周期的に一致する場合、この全てのタスクの周期時間の開始時が一致する時刻を「グリッド時刻」と呼ぶ。  この第２の条件について、図１２を参照して説明する。図１２（ａ）は、グリッド時刻がない３つのタスク集合（タスクＡ、タスクＢ、タスクＣ）が各タスクの周期時間毎に実行される様子を時間軸（横軸）に沿って示し、図１２（ｂ）は、グリッド時刻を有する３つのタスク集合（タスクＤ、タスクＥ、タスクＦ）が各タスクの周期時間毎に実行される様子を時間軸（横軸）に沿って示している。
【０１３４】
タスクＡ、タスクＢ、タスクＣの３つのタスクの集合では、これら３つのタスクのリリース時刻のうち、最も遅いリリース時刻以降に、各タスクの各周期時間の開始時が一致する時刻はない。例えば、タスクＢとタスクＣは時刻Ｔ１において周期時間が同時に開始するが、時刻Ｔ１には、タスクＡの周期時間は開始しない。また、タスクＡとタスクＢは時刻Ｔ２において周期時間が同時に開始するが、時刻Ｔ２にタスク３の周期時間は開始しない。
【０１３５】
これに対して、図１２（ｂ）に示すように、タスクＤ、タスクＥ、タスクＦの３つのタスクの集合では、これら３つのタスクのリリース時刻のうち最も遅いリリース時刻以降に、各タスクの周期時間の開始時が一致する時刻（グリッド時刻）が存在する。例えば、これら３つのタスクの周期時間は時刻Ｔ３、Ｔ４、Ｔ５において、同時に開始している。図１２（ｂ）では、１番目のグリッド時刻は時刻Ｔ３であり、２番目のグリッド時刻は時刻Ｔ４であり、３番目のグリッド時刻は時刻Ｔ５である。
【０１３６】
これらを踏まえて、第２のスケジューリング可能性判定処理について、図１３に示すフローチャートを参照して説明する。判定対象の全てのタスクについて、当該タスクのデッドライン時間が、当該タスクの周期以内であり、且つ全てのタスクの周期時間の開始時が一致する時刻（グリッド時刻）が周期的に到来する場合には、「２番目のグリッド時刻までデッドラインミスを起こさなければ、以降デッドラインミスを起こすことはない」という性質を満たす。第２のスケジューリング判定処理は、この性質を利用し、図１３に示すような処理を行う。
【０１３７】
図１３に示す第２のスケジューリング判定処理では、スケジューリングプログラム１０ｂを用いてスケジューリングしながらシミュレーションを行い、このシミュレーションにおいて、実行中のジョブが終了する度に、当該ジョブがデッドラインミスを起こすか否かをチェックしている。そして、判定対象の全タスクのうち最初にリリースされるタスクのリリース時刻「０」から計測された時刻が、２番目のグリッド時刻になるまで、デッドラインミスを起こすジョブが検知されなかったときに、スケジューリング可能と判定する。
【０１３８】
まず、判定対象の各タスクのパラメタ情報に含まれるリリース時刻、周期を基に、新たなタスクと既存のタスクを含む全てのタスクの周期時間が一致する時刻（グリッド時刻）を求める（ステップＳ５１）。
【０１３９】
そして、スケジューリングプログラム１０ｂを用いてスケジューリングしながら、シミュレーションを行う。シミュレーションは、判定対象の全タスクのうち最初にリリースされるタスクのリリース時刻「０」から計測される時刻が、２番目のグリッド時刻まで行われる（ステップＳ５２、ステップＳ５３）。
【０１４０】
２番目のグリッド時刻までに、上記シミュレーションにおいて、新たなジョブがリリースされたときには（ステップＳ５４）、ステップＳ５２へ戻り、２番目のグリッド時刻でなければ（ステップＳ５２）、再びシミュレーションを継続する（ステップＳ５３）。また、上記シミュレーションにおいて、実行中のジョブが終了したときには（ステップＳ５４）、ステップＳ５５へ進む。
【０１４１】
ステップＳ５５では、当該ジョブにデッドラインミスが発生しているか否かを検査し、デッドラインミスが発生していない場合には、ステップＳ５２へ戻る。
【０１４２】
ステップＳ５５で、デッドラインミスが発生するジョブが検知された場合には、ステップＳ５６へ進み、リアルタイムスケジューリング不可能と判定する（ステップＳ５６）。そして、以降のシミュレーションは行わず、ここでスケジューリング判定処理を終了する。
【０１４３】
一方、上記シミュレーションにおいて、新たなジョブがリリースされたとき（ステップＳ５４）、そのときの時刻が２番目のグリッド時刻であるときは、この２番目のグリッド時刻まで、デッドラインミスを起こすジョブは検知さなかったので、ステップＳ５７へ進み、スケジューリング可能と判定する（ステップＳ５７）。
【０１４４】
以上説明したように、上記第２の実施形態によれば、複数のタスクのそれぞれの周期時間の開始時が一致するグリッド時刻が周期的に到来する場合、２番目のグリッド時刻までに複数のプロセッサで実行される各ジョブが、当該ジョブの許容時刻（絶対デッドライン時刻）までに終了するとき（デッドラインミスの発生するジョブがないとき）、スケジューリング可能と判定し、２番目のグリッド時刻までに、許容時刻までに終了しないジョブ（デッドラインミスの発生するジョブ）を検知したときには、スケジューリング不可能と判定する。
【０１４５】
このような構成により、各タスクに予め定められたデッドライン時間が各タスクに予め定められた周期時間以内であり、しかも、周期的に複数のタスクのそれぞれの周期時間の開始時が一致する場合には、各タスクの周期時間の開始時が一致するグリッド時刻のうち、２番目のグリッド時刻までシミュレーションを行えば、リアルタイムスケジューリングが可能か否かを正確に判定することができる。
【０１４６】
また、判定対象のタスクの集合が、各タスクに予め定められたデッドライン時間が各タスクに予め定められた周期時間以内であり、しかも、周期的なグリッド（各タスクの周期時間の開始時が一致する状態）を有するという条件を満たす場合には、上記第２の実施形態に係る簡略化された第２のスケジューリング可能性判定処理を行い、判定対象のタスクの集合が、上記条件を満たさない場合には、上記第１の実施形態に係るスケジューリング可能性判定処理を行うことにより、判定対象のタスクの集合の特性に応じて、スケジューリングの可否を正確にしかも高速に判定することができる。特に、上記条件を満たすようなタスクの集合の場合には、より高速にスケジューリングの可否を判定することができる。
【０１４７】
従来のように、スケジューリングアルゴリズムを実際に用いてシミュレーションを行うことにより、タスクのすべての周期においてデッドライミスが発生していないことを検査する方法は、判定にかかる計算時間が長いため現実的ではない。上記第１及び第２の実施形態では、スケジューリングアルゴリズムを実際に用いてシミュレーションを行い、タスクのすべての周期ではなく、一部の早い時刻の周期のみにおいてデッドライミスが発生しているか否かを検査し、その結果を用いてリアルタイムスケジューリングが可能であるか否かを判定する。
【０１４８】
より具体的には、以下の方法でリアルタイムスケジューリング可能性判定を行う。タスク集合のシミュレーションでは、スケジューリング方法が、現在プロセッサ上で実行中のタスクや、実行待ちのタスクを管理し、実行中のタスクが終了した際や、実行待ちのタスクが増加した際に、空きプロセッサを探して、あるいは既に実行中の優先順位の低いジョブを一時中断させて、最も優先度が高い実行待ちタスクの実行を開始という手続きを繰り返す。この際、リアルタイムスケジューリング判定方法も、現在プロセッサ上で実行中のタスクや、実行待ちのタスクを管理し、
１．すべてのタスクの周期の最小公倍数をＬとしたとき、タスクの実行パターンが時間間隔Ｌを基準として収束したかどうか、
２．実行中のタスクがデッドラインミスを起こしたかどうか、
の２つのチェックを行なう。もしタスクの実行パターンが収束した場合には、収束以降のタスクをスケジューリングすることなくリアルタイムスケジューリング可能であると判定し、もしタスクがデッドラインミスを起こした場合には、デッドラインミス発生以降タスクをスケジューリングすることなくリアルタイムスケジューリング不可能であると判定する。
【０１４９】
上記第１及び第２の実施形態に係るアルタイムスケジューリング可能性判定方法によれば、周期タスクの集合とスケジューリング方法が与えられた場合に、このスケジューリング方法を用いて周期タスクの集合をリアルタイムスケジューリング可能であるかどうか正確、かつ高速に判定することが可能である。
【０１５０】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【０１５１】
本発明の実施の形態に記載した本発明の手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フレキシブルディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、半導体メモリなどの記録媒体に格納して頒布することもできる。
【図面の簡単な説明】
【０１５２】
【図１】第１の実施形態に係るリアルタイムシステムの構成例を示した図。
【図２】スケジューリング可能性判定処理の概略を説明するための図。
【図３】周期タスクの具体例を示した図。
【図４】周期タスクのパラメータ情報の一例を示した図。
【図５】２つのタスク（タスクＡ及びタスクＢ）を、ＥＤＦアルゴリズムを用いてスケジューリングしたときの、ジョブ実行パターンを示した図。
【図６】キャリーインを説明するための図。
【図７】第１の実施形態に係るリアルタイムスケジューリング可能性判定処理（第１のスケジューリング可能性判定処理）を説明するためのフローチャート。
【図８】図７のリアルタイムスケジューリング可能性判定処理をより具体的に示したフローチャート。
【図９】第１の実施形態に係る他のリアルタイムスケジューリング可能性判定処理（第１のスケジューリング可能性判定処理）を説明するためのフローチャート。
【図１０】キャリーインの単調性を説明するための図。
【図１１】第２の実施形態に係るリアルタイムシステムの構成例を示した図。
【図１２】グリッド及びグリッド時刻を説明するための図。
【図１３】第２の実施形態に係るリアルタイムスケジューリング可能性判定処理（第２のスケジューリング可能性判定処理）を説明するためのフローチャート。
【図１４】第１の実施形態に係るリアルタイムシステムの処理動作の概略を説明するためのフローチャート。
【図１５】第２の実施形態に係るリアルタイムシステムの処理動作の概略を説明するためのフローチャート。
【符号の説明】
【０１５３】
１…ＭＰＵ（Master Processing Unit）、２ａ〜２ｃ…ＶＰＵ（Versatile Processing Unit）、３…バス、４…共有メモリ、５…Ｉ／Ｏコントローラ、６…Ｉ／Ｏデバイス、１０…オペレーティングシステム（ＯＳ）、１０ａ…リアルタイムスケジューリング可能性判定プログラム（第１のスケジューリング可能性判定プログラム）、１０ｂ…スケジューリングプログラム、１０ｃ…判定プログラム、１０ｄ…第２のスケジューリング可能性判定プログラム。
【図１】
2006268754.tif 000003
【図２】
2006268754.tif 000004
【図３】
2006268754.tif 000005
【図４】
2006268754.tif 000006
【図５】
2006268754.tif 000007
【図６】
2006268754.tif 000008
【図７】
2006268754.tif 000009
【図８】
2006268754.tif 000010
【図９】
2006268754.tif 000011
【図１０】
2006268754.tif 000012
【図１１】
2006268754.tif 000013
【図１２】
2006268754.tif 000014
【図１３】
2006268754.tif 000015
【図１４】
2006268754.tif 000016
【図１５】
2006268754.tif 000017