(57)【要約】【課題】一つのタスクに同時に割り当てることが必要なプロセッサ数が複数である場合にも利用可能なスケジューリング可能性判定方法を実現する。【解決手段】Σi=1...N Mi * Uk,i ≦ Lk  の条件によってタスク k のデッドラインミスが発生する可能性を判定する。プロセッサの数をM、タスクの数をN、タスクi( 1 ≦ i ≦ N )の周期、利用プロセッサ数、処理時間、相対デッドラインをそれぞれTi， Mi, Ci, Diとすると、Mk ≦ (M + 1)/2 の場合はLk = (M - Mk + 1) - (M - 2Mk + 1)Ck/Dk； (M + 1)/2 < Mk の場合はLk = M - Mk + 1; Mk ≦ (M + 1) / 2，Mi < (M + 1) / 2，且つXk,i ≦ 0 の場合はUk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk; Mk ≦ (M + 1) / 2，Mi < (M + 1) / 2，且つ 0 < Xk,i < Ci/Ti の場合はUk,i = Ci/Ti{1+(Ti-Di)/Dk}+(Ci-Xk,i*Ti)/Dk; Mk ≦ (M + 1) / 2，Mi < (M + 1) / 2，且つ Ci/Ti ≦ Xk,i の場合はUk,i = Ci/Ti{1+(Ti-Di)/Dk}である。【選択図】      図１
2005284351.tif 000002
【特許請求の範囲】
【請求項１】
同時に１以上のプロセッサをそれぞれ使用する複数のタスクを複数のプロセッサ上でリアルタイムスケジューリングすることが可能であるかどうかを判定するリアルタイムスケジューリング可能性判定方法において、
前記複数のタスクの各々について Lk および Σi=1...N Mi * Uk,i を算出するステップと、
前記複数のタスクの全てが
Σi=1...N Mi * Uk,i  ≦  Lk  
の条件を満たす場合に前記複数のタスクを前記複数のプロセッサ上でリアルタイムスケジューリングすることが可能であると判定するステップとを具備し、
前記複数のプロセッサの数をM、前記複数のタスクの数をN、タスクi( 1 ≦ i ≦ N )の周期をTi、タスクiによって同時に使用されるプロセッサ数をMi、タスクiの処理時間をCi、タスクiの相対デッドラインをDiとすると、
前記条件を満たす可能性を検証すべきタスクk ( 1 ≦ k ≦ N )に対応する前記Lkの値は、
(1) Mk ≦ (M + 1)/2 の場合
Lk = (M - Mk + 1) - (M - 2Mk + 1)Ck/Dk
であり、
前記タスクk( 1 ≦ k ≦ N )に対応する前記Uk,iの値は、
(1) Mk ≦ (M + 1) / 2の場合, Mi < (M + 1) / 2の場合, 且つ Xk,i ≦ 0 の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
(2) Mk ≦ (M + 1) / 2の場合, Mi < (M + 1) / 2の場合, 且つ0 < Xk,i < Ci/Ti の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+(Ci-Xk,i*Ti)/Dk
(3) Mk ≦ (M + 1) / 2の場合, Mi < (M + 1) / 2の場合, 且つ Ci/Ti ≦ Xk,i の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}
であり、ただしXk,i = {Mk - Mi + (M - 2Mk + 1)Ck/Dk}/(M - 2Mi + 1)であることを特徴とするリアルタイムスケジューリング可能性判定方法。
【請求項２】
前記リアルタイムスケジューリングはEDF(earliest deadline first)アルゴリズムを用いて実行されることを特徴とする請求項１記載のリアルタイムスケジューリング可能性判定方法。
【請求項３】
同時に１以上のプロセッサをそれぞれ使用する複数のタスクを複数のプロセッサ上でリアルタイムスケジューリングすることが可能であるかどうかを判定するリアルタイムスケジューリング可能性判定方法において、
前記複数のタスクの各々について Lk および Σi=1...N Mi * Uk,i を算出するステップと、
前記複数のタスクの全てが
Σi=1...N Mi * Uk,i  ≦  Lk  
の条件を満たす場合に前記複数のタスクを前記複数のプロセッサ上でリアルタイムスケジューリングすることが可能であると判定するステップとを具備し、
前記複数のプロセッサの数をM、前記複数のタスクの数をN、タスクi( 1 ≦ i ≦ N )の周期をTi、タスクiによって同時に使用されるプロセッサ数をMi、タスクiの処理時間をCi、タスクiの相対デッドラインをDiとすると、
前記条件を満たす可能性を検証すべきタスククk ( 1 ≦ k ≦ N )に対応する前記Lkの値は、
(1) Mk ≦ (M + 1)/2 の場合
Lk = (M - Mk + 1) - (M - 2Mk + 1)Ck/Dk
(2) (M + 1)/2 < Mk の場合
Lk = M - Mk + 1
前記タスクk( 1 ≦ k ≦ N )に対応する前記Uk,iの値は、
(1) Mk ≦ (M + 1) / 2 の場合
(1-1) Mi < (M + 1) / 2 の場合
(1-1-1) Xk,i ≦ 0 の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
(1-1-2) 0 < Xk,i < Ci/Ti の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+(Ci-Xk,i*Ti)/Dk
(1-1-3) Ci/Ti ≦ Xk,i の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}
(1-2) Mi = (M + 1) / 2 の場合
(1-2-1) Mk ≠ (M + 1) / 2の場合
(1-2-1-1) Ck / Dk < 1 / 2 の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
(1-2-2) Mk = (M + 1) / 2 の場合 
Uk,i = Ci/Ti{1+(Ti-Di)/Dk} 
(1-3) (M + 1) / 2 < Mi の場合
(1-3-1) Xk,i ≦ 0 の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk} 
(1-3-2) 0 < Xk,i の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk  
(2) (M + 1) / 2 < Mk の場合
(2-1) Mi < (M + 1) / 2 の場合
(2-1-1) Yk,i < Ci/Ti の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+(Ci-Yk,i*Ti)/Dk
(2-1-2) Ci/Ti ≦ Yk,i の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}
(2-2) (M + 1) / 2 ≦ Mi の場合
(2-2-1) Mi ≦ Mk の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}
(2-2-2) Mk < Mi の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
であり、ただしXk,i = {Mk - Mi + (M - 2Mk + 1)Ck/Dk}/(M - 2Mi + 1)であり、Yk,i = (Mk - Mi)/(M - 2Mi + 1)であることを特徴とするリアルタイムスケジューリング可能性判定方法。
【請求項４】
前記リアルタイムスケジューリングはEDF(earliest deadline first)アルゴリズムを用いて実行されることを特徴とする請求項３記載のスケジューリング可能性判定方法。
【請求項５】
同時に１以上のプロセッサをそれぞれ使用する複数のタスクを複数のプロセッサ上でリアルタイムスケジューリングすることが可能であるかどうかを判定するリアルタイムスケジューリング可能性判定方法において、
（１）前記各タスクの周期、前記各タスクによって同時に使用されるプロセッサ数、前記各タスクの処理時間、および前記各タスクの相対デッドラインを示すタスクパラメタ情報を入力し、
（２）デッドラインミスが発生する可能性を検証すべきタスクのタスクパラメタ情報と前記複数のプロセッサの総数とに基づいて、前記検証すべきタスクのデッドラインミスを引き起こす可能性がある、最小の平均負荷値を算出し
（３）前記複数のタスクそれぞれに対応する前記タスクパラメタ情報に基づいて、平均負荷が前記算出された最小の平均負荷値以上となる最も早い時点から前記検証すべきタスクのデッドラインミスが発生する可能性がある時点までの期間において発生する可能性がある、前記複数のタスクそれぞれの最大平均負荷の合計値を算出し、
（４）前記検証すべきタスクを変更しながら前記（２）〜（３）を繰り返し実行し、
（５）前記複数のタスクのすべてについて前記算出された最小の平均負荷値よりも前記算出された最大平均負荷の合計値が大きい場合に前記複数のタスクを前記複数のプロセッサ上でリアルタイムスケジューリングすることが可能であると判定することを特徴とするリアルタイムスケジューリング可能性判定方法。
【請求項６】
前記リアルタイムスケジューリングはEDF(earliest deadline first)アルゴリズムを用いて実行されることを特徴とする請求項５記載の（リアルタイム）スケジューリングが可能性判定方法。
【請求項７】
複数のプロセッサと、
同時に１以上のプロセッサをそれぞれ使用する、リアルタイムスケジューリング対象のの複数のタスクの各々について Lk および Σi=1...N Mi * Uk,i を算出する手段と、
前記複数のタスクの全てが
Σi=1...N Mi * Uk,i  ≦  Lk  
の条件を満たす場合に前記複数のタスクを前記複数のプロセッサ上でリアルタイムスケジューリングすることが可能であると判定する手段と、
前記複数のタスクを前記複数のプロセッサ上でリアルタイムスケジューリングすることが可能であると判定された場合に、前記複数のタスクを前記複数のプロセッサ上でリアルタイムスケジューリングするスケジューリング手段とを具備し、
前記複数のプロセッサの数をM、前記複数のタスクの数をN、タスクi( 1 ≦ i ≦ N )の周期をTi、タスクiによって同時に使用されるプロセッサ数をMi、タスクiの処理時間をCi、タスクiの相対デッドラインをDiとすると、
前記条件を満たす可能性を検証すべきタスクk( 1 ≦ k ≦ N )に対応する前記Lkの値は、
(1) Mk ≦ (M + 1)/2 の場合
Lk = (M - Mk + 1) - (M - 2Mk + 1)Ck/Dk
であり、
前記タスクk( 1 ≦ k ≦ N )に対応する前記Uk,iの値は、
(1) Mk ≦ (M + 1) / 2の場合, Mi < (M + 1) / 2の場合, 且つ Xk,i ≦ 0 の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
(2) Mk ≦ (M + 1) / 2の場合, Mi < (M + 1) / 2の場合, 且つ0 < Xk,i < Ci/Ti の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+(Ci-Xk,i*Ti)/Dk
(3) Mk ≦ (M + 1) / 2の場合, Mi < (M + 1) / 2の場合, 且つ Ci/Ti ≦ Xk,i の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}
であり、ただしXk,i = {Mk - Mi + (M - 2Mk + 1)Ck/Dk}/(M - 2Mi + 1)であることを特徴とするリアルタイムシステム。
【請求項８】
前記リアルタイムスケジューリングはEDF(earliest deadline first)アルゴリズムを用いて実行されることを特徴とする請求項７記載のリアルタイムシステム。
【請求項９】
複数のプロセッサと、
同時に１以上のプロセッサをそれぞれ使用する、リアルタイムスケジューリング対象のの複数のタスクの各々について Lk および Σi=1...N Mi * Uk,i を算出する手段と、
前記複数のタスクの全てが
Σi=1...N Mi * Uk,i  ≦  Lk  
の条件を満たす場合に前記複数のタスクを前記複数のプロセッサ上でリアルタイムスケジューリングすることが可能であると判定する手段と、
前記複数のタスクを前記複数のプロセッサ上でリアルタイムスケジューリングすることが可能であると判定された場合に、前記複数のタスクを前記複数のプロセッサ上でリアルタイムスケジューリングするスケジューリング手段とを具備し、
前記複数のプロセッサの数をM、前記複数のタスクの数をN、タスクi( 1 ≦ i ≦ N )の周期をTi、タスクiによって同時に使用されるプロセッサ数をMi、タスクiの処理時間をCi、タスクiの相対デッドラインをDiとすると、
前記条件を満たす可能性を検証すべきタスクk( 1 ≦ k ≦ N )に対応する前記Lkの値は、
(1) Mk ≦ (M + 1)/2 の場合
Lk = (M - Mk + 1) - (M - 2Mk + 1)Ck/Dk
(2) (M + 1)/2 < Mk の場合
Lk = M - Mk + 1
前記タスクk( 1 ≦ k ≦ N )に対応する前記Uk,iの値は、
(1) Mk ≦ (M + 1) / 2 の場合
(1-1) Mi < (M + 1) / 2 の場合
(1-1-1) Xk,i ≦ 0 の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
(1-1-2) 0 < Xk,i < Ci/Ti の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+(Ci-Xk,i*Ti)/Dk
(1-1-3) Ci/Ti ≦ Xk,i の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}
(1-2) Mi = (M + 1) / 2 の場合
(1-2-1) Mk ≠ (M + 1) / 2の場合
(1-2-1-1) Ck / Dk < 1 / 2 の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
(1-2-2) Mk = (M + 1) / 2 の場合 
Uk,i = Ci/Ti{1+(Ti-Di)/Dk} 
(1-3) (M + 1) / 2 < Mi の場合
(1-3-1) Xk,i ≦ 0 の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk} 
(1-3-2) 0 < Xk,i の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk 
(2) (M + 1) / 2 < Mk の場合
(2-1) Mi < (M + 1) / 2 の場合
(2-1-1) Yk,i < Ci/Ti の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+(Ci-Yk,i*Ti)/Dk
(2-1-2) Ci/Ti ≦ Yk,i の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}
(2-2) (M + 1) / 2 ≦ Mi の場合
(2-2-1) Mi ≦ Mk の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}
(2-2-2) Mk < Mi の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
であり、ただしXk,i = {Mk - Mi + (M - 2Mk + 1)Ck/Dk}/(M - 2Mi + 1)であり、Yk,i = (Mk - Mi)/(M - 2Mi + 1)であることを特徴とするリアルタイムシステム。
【請求項１０】
前記リアルタイムスケジューリングはEDF(earliest deadline first)アルゴリズムを用いて実行されることを特徴とする請求項９記載のリアルタイムシステム。
【請求項１１】
複数のプロセッサと、
同時に１以上のプロセッサをそれぞれ使用する、リアルタイムスケジューリング対象のの複数のタスクの各々の周期、前記各タスクによって同時に使用されるプロセッサ数、前記各タスクの処理時間、および前記各タスクの相対デッドラインを示すタスクパラメタ情報を入力する手段と、
デッドラインミスが発生する可能性を検証すべきタスクのタスクパラメタ情報と前記複数のプロセッサの総数とに基づいて、前記検証すべきタスクのデッドラインミスを引き起こす可能性がある、最小の平均負荷値を算出する手段と、
前記複数のタスクそれぞれに対応する前記タスクパラメタ情報に基づいて、平均負荷が前記算出された最小の平均負荷値以上となる最も早い時点から前記検証すべきタスクのデッドラインミスが発生する可能性がある時点までの期間において発生する可能性がある、前記複数のタスクそれぞれの最大平均負荷の合計値を算出する手段と、
前記複数のタスクのすべてについて前記算出された最小の平均負荷値よりも前記算出された最大平均負荷の合計値が大きい場合に、前記複数のタスクを前記複数のプロセッサ上でリアルタイムスケジューリングするスケジューリング手段とを具備することを特徴とするリアルタイムシステム。
【請求項１２】
前記リアルタイムスケジューリングはEDF(earliest deadline first)アルゴリズムを用いて実行されることを特徴とする請求項１１記載のリアルタイムシステム。
【請求項１３】
同時に１以上のプロセッサをそれぞれ使用する複数のタスクを複数のプロセッサ上でリアルタイムスケジューリングすることが可能であるかどうかを判定するリアルタイムスケジューリング可能性判定処理をコンピュータに実行させるプログラムであって、
前記複数のタスクの各々について Lk および Σi=1...N Mi * Uk,i を算出する処理を、前記コンピュータに実行させる手順と、
前記複数のタスクの全てが
Σi=1...N Mi * Uk,i  ≦  Lk  
の条件を満たす場合に前記複数のタスクを前記複数のプロセッサ上でリアルタイムスケジューリングすることが可能であると判定する処理を、前記コンピュータに実行させる手順とを具備し、
前記複数のプロセッサの数をM、前記複数のタスクの数をN、タスクi( 1 ≦ i ≦ N )の周期をTi、タスクiによって同時に使用されるプロセッサ数をMi、タスクiの処理時間をCi、タスクiの相対デッドラインをDiとすると、
前記条件を満たす可能性を検証すべきタスクk( 1 ≦ k ≦ N )に対応する前記Lkの値は、
(1) Mk ≦ (M + 1)/2 の場合
Lk = (M - Mk + 1) - (M - 2Mk + 1)Ck/Dk
であり、
前記タスクk( 1 ≦ k ≦ N )に対応する前記Uk,iの値は、
(1) Mk ≦ (M + 1) / 2の場合, Mi < (M + 1) / 2の場合, 且つ Xk,i ≦ 0 の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
(2) Mk ≦ (M + 1) / 2の場合, Mi < (M + 1) / 2の場合, 且つ0 < Xk,i < Ci/Ti の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+(Ci-Xk,i*Ti)/Dk
(3) Mk ≦ (M + 1) / 2の場合, Mi < (M + 1) / 2の場合, 且つ Ci/Ti ≦ Xk,i の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}
であり、ただしXk,i = {Mk - Mi + (M - 2Mk + 1)Ck/Dk}/(M - 2Mi + 1)であることを特徴とするプログラム。
【請求項１４】
前記リアルタイムスケジューリングはEDF(earliest deadline first)アルゴリズムを用いて実行されることを特徴とする請求項１３記載のプログラム。
【請求項１５】
同時に１以上のプロセッサをそれぞれ使用する複数のタスクを複数のプロセッサ上でリアルタイムスケジューリングすることが可能であるかどうかを判定するリアルタイムスケジューリング可能性判定処理をコンピュータに実行させるプログラムであって、
前記複数のタスクの各々について Lk および Σi=1...N Mi * Uk,i を算出する処理を、前記コンピュータに実行させる手順と、
前記複数のタスクの全てが
Σi=1...N Mi * Uk,i  ≦  Lk  
の条件を満たす場合に前記複数のタスクを前記複数のプロセッサ上でリアルタイムスケジューリングすることが可能であると判定する処理を、前記コンピュータに実行させる手順とを具備し、
前記複数のプロセッサの数をM、前記複数のタスクの数をN、タスクi( 1 ≦ i ≦ N )の周期をTi、タスクiによって同時に使用されるプロセッサ数をMi、タスクiの処理時間をCi、タスクiの相対デッドラインをDiとすると、
前記条件を満たす可能性を検証すべきタスクk( 1 ≦ k ≦ N )に対応する前記Lkの値は、
(1) Mk ≦ (M + 1)/2 の場合
Lk = (M - Mk + 1) - (M - 2Mk + 1)Ck/Dk
(2) (M + 1)/2 < Mk の場合
Lk = M - Mk + 1
前記タスクk( 1 ≦ k ≦ N )に対応する前記Uk,iの値は、
(1) Mk ≦ (M + 1) / 2 の場合
(1-1) Mi < (M + 1) / 2 の場合
(1-1-1) Xk,i ≦ 0 の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
(1-1-2) 0 < Xk,i < Ci/Ti の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+(Ci-Xk,i*Ti)/Dk
(1-1-3) Ci/Ti ≦ Xk,i の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}
(1-2) Mi = (M + 1) / 2 の場合
(1-2-1) Mk ≠ (M + 1) / 2の場合
(1-2-1-1) Ck / Dk < 1 / 2 の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
(1-2-2) Mk = (M + 1) / 2 の場合 
Uk,i = Ci/Ti{1+(Ti-Di)/Dk} 
(1-3) (M + 1) / 2 < Mi の場合
(1-3-1) Xk,i ≦ 0 の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk} 
(1-3-2) 0 < Xk,i の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk 
(2) (M + 1) / 2 < Mk の場合
(2-1) Mi < (M + 1) / 2 の場合
(2-1-1) Yk,i < Ci/Ti の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+(Ci-Yk,i*Ti)/Dk
(2-1-2) Ci/Ti ≦ Yk,i の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}
(2-2) (M + 1) / 2 ≦ Mi の場合
(2-2-1) Mi ≦ Mk の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}
(2-2-2) Mk < Mi の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
であり、ただしXk,i = {Mk - Mi + (M - 2Mk + 1)Ck/Dk}/(M - 2Mi + 1)であり、Yk,i = (Mk - Mi)/(M - 2Mi + 1)であることを特徴とするプログラム。
【請求項１６】
前記リアルタイムスケジューリングはEDF(earliest deadline first)アルゴリズムを用いて実行されることを特徴とする請求項１５記載のプログラム。
【請求項１７】
同時に１以上のプロセッサをそれぞれ使用する複数のタスクを複数のプロセッサ上でスケジューリングすることが可能であるかどうかを判定する処理を、コンピュータに実行させるプログラムであって、
（１）前記各タスクの周期、前記各タスクによって同時に使用されるプロセッサ数、前記各タスクの処理時間、および前記各タスクの相対デッドラインを示すタスクパラメタ情報を入力する処理を、前記コンピュータに実行させる手順と、
（２）デッドラインミスが発生する可能性を検証すべきタスクのタスクパラメタ情報と前記複数のプロセッサの総数とに基づいて、前記検証すべきタスクのデッドラインミスを引き起こす可能性がある、最小の平均負荷値を算出する処理を、前記コンピュータに実行させる手順と、
（３）前記複数のタスクそれぞれに対応する前記タスクパラメタ情報に基づいて、平均負荷が前記算出された最小の平均負荷値以上となる最も早い時点から前記検証すべきタスクのデッドラインミスが発生する可能性がある時点までの期間において発生する可能性がある、前記複数のタスクそれぞれの最大平均負荷の合計値を算出する処理を、前記コンピュータに実行させる手順と、
（４）前記検証すべきタスクを変更しながら前記（２）〜（３）を繰り返し実行する処理を、前記コンピュータに実行させる手順と、
（５）前記複数のタスクのすべてについて前記算出された最小の平均負荷値よりも前記算出された最大平均負荷の合計値が大きい場合に前記複数のタスクを前記複数のプロセッサ上でリアルタイムスケジューリングすることが可能であると判定する処理を、前記コンピュータに実行させる手順とを具備することを特徴とするプログラム。
【請求項１８】
前記リアルタイムスケジューリングはEDF(earliest deadline first)アルゴリズムを用いて実行されることを特徴とする請求項１７記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は複数のプロセッサ上で複数のタスクをリアルタイムスケジューリングすることが可能であるかどうかを判定するリアルタイムスケジューリング可能性判定方法および同方法が適用されるリアルタイムシステムに関する。
【背景技術】
【０００２】
リアルタイムシステムは、“タスクごとに決められた制限時間内に必ずこのタスクの処理を完了させなければならない”という時間的制約を受けたコンピュータシステムである。
【０００３】
一般に、各タスクごとに決められた制限時間のことを“デッドライン”、デッドライン内にタスクの処理が完了しないことを“デッドラインミス”と呼ぶ。デッドラインミスはリアルタイムシステムにおいては絶対に起こってはいけないことである。
【０００４】
代表的なリアルタイムシステムの応用例としては、航空管制システム、プラント制御監視システム、医療システムなどがある。例えば、航空管制システムは、航空機の衝突事故防止のため、航空機間や航空機と他の障害物との間の安全間隔を設定する。この際、飛行機同士が一秒以内に衝突するかどうか判定するという処理を二秒かかって行ったのでは意味がないので、航空管制システムは厳格な時間制約の上で動作しなければならない。
【０００５】
デッドラインミスを一切許さないという厳格な時間制約のもとで機器を動かすことを“リアルタイムスケジューリング”と呼ぶ。リアルタイムスケジューリングを実現する方法に関しては、様々な検討が進められている。
【０００６】
リアルタイムスケジューリングを実現する方法としては、EDF(earliest deadline first)アルゴリズムを用いてスケジューリングを行う技術が知られている（例えば、非特許文献１参照。）。
【０００７】
リアルタイムスケジューリングにおいては、各タスクがデッドラインミスを起こさないで実行できるように、適切なプロセッサを適切な期間だけ適切なタスクに割り当てることが重要である。
【０００８】
複数のタスクを複数のプロセッサ上でリアルタイムスケジューリングする際には、第一に、これらのタスクが複数のプロセッサ上でリアルタイムスケジューリング可能であるかどうかをリアルタイムスケジューリング可能性判定方法を用いて判定し、可能であると判定された場合に限り、第二に、適切なスケジューリング方法を用いて、実際にどのプロセッサをどの期間にどのタスクに割り当てるか決定する。
【０００９】
代表的なスケジューリング方法であるEDFアルゴリズムは、デッドラインが早いタスクに対して優先的に早い時刻にプロセッサを割り当てるアルゴリズムである。
【００１０】
また、リアルタイムスケジューリング可能性判定方法としては、EDFアルゴリズムによるリアルタイムスケジューリングが可能であるかどうかを判定する方法が知られている（例えば、非特許文献２参照。）。
【００１１】
さらに、リアルタイムスケジューリング可能性判定方法としては、仮想的にスケジューリングを実行してデッドライミスが発生するかどうかを検査する方法も知られている（例えば、非特許文献３参照。）。
【００１２】
本明細書の以下においては、特に特記しない限りにおいて“リアルタイムスケジューリング可能（不可能）”であることを単に“スケジューリング可能（不可能）”と呼ぶことにする。
【非特許文献１】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
【発明の開示】
【発明が解決しようとする課題】
【００１３】
しかし、非特許文献２の判定方法は一つのタスクに同時に割り当てることが可能なプロセッサが一つである場合を前提とした方法であり、同時に複数のプロセッサを必要とするタスクについては考慮されていない。タスクによっては、その処理効率を高めるために同時に複数のプロセッサを必要とするものがある。従って、一つのタスクに同時に割り当てることが必要なプロセッサ数が複数である場合にも利用可能なスケジューリング可能性判定方法を提供することが必要である。
【００１４】
また仮想的にスケジューリングを行う非特許文献３の方法は計算時間が長いため現実的ではない。
【００１５】
本発明は上述の事情を考慮してなされたものであり、一つのタスクに同時に割り当てることが必要なプロセッサ数が複数である場合にも利用可能であり、かつ計算時間が短いスケジューリング可能性判定方法およびリアルタイムシステムを提供することを目的とする。
【課題を解決するための手段】
【００１６】
上述の課題を解決するため、請求項１に係る本発明は、同時に１以上のプロセッサをそれぞれ使用する複数のタスクを複数のプロセッサ上でリアルタイムスケジューリングすることが可能であるかどうかを判定するリアルタイムスケジューリング可能性判定方法において、前記複数のタスクの各々について Lk および Σi=1...N Mi * Uk,i を算出するステップと、前記複数のタスクの全てがΣi=1...N Mi * Uk,i  ≦  Lk  の条件を満たす場合に前記複数のタスクを前記複数のプロセッサ上でリアルタイムスケジューリングすることが可能であると判定するステップとを具備し、前記複数のプロセッサの数をM、前記複数のタスクの数をN、タスクi( 1 ≦ i ≦ N )の周期をTi、タスクiによって同時に使用されるプロセッサ数をMi、タスクiの処理時間をCi、タスクiの相対デッドラインをDiとすると、前記条件を満たす可能性を検証すべきタスクk ( 1 ≦ k ≦ N )に対応する前記Lkの値は、(1) Mk ≦ (M + 1)/2 の場合
Lk = (M - Mk + 1) - (M - 2Mk + 1)Ck/Dk
であり、
前記タスクk( 1 ≦ k ≦ N )に対応する前記Uk,iの値は、
(1) Mk ≦ (M + 1) / 2の場合, Mi < (M + 1) / 2の場合, 且つ Xk,i ≦ 0 の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
(2) Mk ≦ (M + 1) / 2の場合, Mi < (M + 1) / 2の場合, 且つ0 < Xk,i < Ci/Ti の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+(Ci-Xk,i*Ti)/Dk
(3) Mk ≦ (M + 1) / 2の場合, Mi < (M + 1) / 2の場合, 且つ Ci/Ti ≦ Xk,i の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}
であり、ただしXk,i = {Mk - Mi + (M - 2Mk + 1)Ck/Dk}/(M - 2Mi + 1)であることを特徴とする。
【発明の効果】
【００１７】
本発明によれば、一つのタスクに同時に割り当てることが必要なプロセッサ数が複数である場合にもリアルタイムスケジューリング可能性を判定することができ、また仮想的なスケジューリングを行う場合に比べ計算時間を短くすることができる。
【発明を実施するための最良の形態】
【００１８】
以下、図面を参照して、本発明の実施形態を説明する。  
図１には、本発明の一実施形態に係るリアルタイムシステムの構成例が示されている。このリアルタイムシステムは、例えば組み込みシステムとして使用されるコンピュータシステムであり、複数のタスクをその時間制約の範囲内でリアルタイムに実行する。
【００１９】
このリアルタイムシステムは、マスタープロセッサユニット（ＭＰＵ１１：Master Processing Unit）１１と、複数のバーサタイルプロセッサユニット（ＶＰＵ：Versatile Processing Unit）１２と、バス１３と、共有メモリ１４と、Ｉ／Ｏ（input/output）コントローラ１５、およびＩ／Ｏデバイス１６を含んでいる。ＭＰＵ１１、複数のＶＰＵ１２、メインメモリ１４、Ｉ／Ｏコントローラ１５は、バス１３によって相互に接続されている。
【００２０】
ＭＰＵ１１は本リアルタイムシステムの動作を制御するメインプロセッサであり、共有メモリ１４内に格納されたオペレーティングシステム(ＯＳ：Operating System)を実行する。各ＶＰＵ１２は、ＭＰＵ１１の管理の下で各種の処理を実行するプロセッサである。リアルタイム性が要求される複数のタスクは、複数のＶＰＵ１２上で実行される。複数のタスクの各々は、同時に１以上のプロセッサを必要とする。オペレーティングシステムは、各タスクに１以上のＶＰＵ１２をリアルタイムに割り当てる。このオペレーティングシステムは、スケジュール可能性判定部１０１およびスケジューラ１０２を含む。
【００２１】
スケジュール可能性判定部１０１は、リアルタイム性が要求される複数のタスクを複数のＶＰＵ１２上で、例えばEDFアルゴリズムを用いてリアルタイムスケジューリングすることが可能であるかどうかを判定するスケジューリング可能性判定処理を実行する。リアルタイムスケジューリングすることが可能であることが判定された場合、スケジューラ１０２は、実際に複数のタスクを複数のＶＰＵ１２上で、例えばEDFアルゴリズムを用いてリアルタイムスケジューリングする。EDFアルゴリズムは、上述したように、デッドラインが早いタスクに対して優先的に早い時刻にプロセッサを割り当てるアルゴリズムである。
【００２２】
スケジューリング可能性判定処理は、例えば、あるアプリケーションプログラムの実行が要求された時に実行される。この場合、スケジュール可能性判定部１０１は、そのアプリケーションプログラム内の複数のタスクと既に実行されているアプリケーションプログラム内の複数のタスクとを含む全てのタスクの各々についてデッドラインミスを発生する可能性があるかどうかを判定する。全てのタスクについてデッドラインミスを発生する可能性が無いことが判定されたならば、スケジューラ１０２は、全てのタスクのケジューリングを開始する。一方、もし全てのタスクの中の一つでもデッドラインミスを発生する可能性があると判定されたならば、実行が要求されたアプリケーションプログラム内の複数のタスクのスケジューリングは実行されない。既に実行されているアプリケーションプログラムは継続して実行される。これにより、デッドラインミスが発生することを事前に防止することができる。
【００２３】
図２には、スケジューリング可能性判定処理が実行される場合のデータの流れが示されている。
【００２４】
スケジュール可能性判定部１０１は、スケジューリングに利用可能な総プロセッサ数と、スケジューリングすべき全てのタスクそれぞれに対応するタスクパラメタ情報を入力する。各タスクのタスクパラメタ情報は、そのタスクを含むアプリケーションプログラムからスケジュール可能性判定部１０１に渡される。本実施形態においては、総プロセッサ数は、本リアルタイムシステムに設けられたＶＰＵ１２の数を示す。
【００２５】
各タスクに対応するタスクパラメタ情報は、そのタスクの周期、そのタスクによって同時に使用されるプロセッサ数（利用プロセッサ数）、そのタスクの処理時間（実行期間）、およびそのタスクの相対デッドライン、等を示す。周期は、タスクが繰り返し実行されるべき時間間隔を示す。利用プロセッサ数は、タスクに同時に割り当てるべきプロセッサの数を示す。タスク毎に利用プロセッサ数は予め決められている。処理時間（実行期間）は、タスクの実行に要する時間を示す。
【００２６】
スケジュール可能性判定部１０１は、総プロセッサ数と、スケジューリングすべき全てのタスクそれぞれに対応するタスクパラメタ情報とを利用して、スケジューリング可能性判定処理を実行する。そして、スケジュール可能性判定部１０１は、判定結果(スケジューリング可能である、またはスケジューリング不可能である)をスケジューラ１０２に出力する。
【００２７】
ここで、タスクについて説明する。  
各タスクは“ジョブ”と呼ばれるタスク実行単位の繰り返しであり、“周期”に等しい時間ごとにジョブが開始する。また、各ジョブはジョブ開始時刻から“相対デッドライン”に等しい時間内に、“利用プロセッサ数”に等しい数のプロセッサを同時に用いて、“処理時間”に等しい時間だけ実行される。また、ジョブ開始時刻に相対デッドラインを加えた時刻（つまりジョブの実行が完了しなければならない時刻）を“絶対デッドライン”と呼ぶことにする。
【００２８】
図３はタスクの具体例を示している。
【００２９】
この図３の横軸は時間軸, 縦軸はプロセッサを表している。また、この図３は、スケジューリングに利用可能な総プロセッサ数（ＶＰＵの総数）が 3 であるリアルタイムシステムにおいて、周期が 100ms, 利用プロセッサ数が 2, 処理時間が 50ms, 相対デッドラインが 80ms である、あるタスクを実行した例を示している。
【００３０】
図３においては、タスクの実行の様子が 3 周期分だけ示されている。各周期において、 2 つのプロセッサを同時に用いる、処理時間50ms のジョブが実行される。図３では、各ジョブの処理はジョブ開始時刻から絶対デッドラインまでの期間内に収まっている（デッドラインミスは発生していない）。
【００３１】
本明細書の以下において、特に明記しない限りにおいて、タスク実行に利用可能な総プロセッサ数を M, スケジューリング対象の総タスク数を N とし, N 個のタスクには 1 から N のタスク番号を付与することにする。また、タスクi ( 1 ≦ i ≦ N ) の周期, タスクi の利用プロセッサ数, タスクi の処理時間, タスクi の相対デッドラインをそれぞれ Ti, Mi, Ci, Di と置くことにする。
【００３２】
次に、スケジューリング可能性判定処理の手続きの概要を説明する。
【００３３】
図４は、複数のタスクを複数のプロセッサ上でEDF アルゴリズムを用いてスケジューリングすることが可能であるかどうか判定する手続きを示すフローチャートである。
【００３４】
スケジューリング可能性判定部１０１は、あるタスク (フローチャートではタスク k ( 1 ≦ k ≦ N )) に注目し、このタスクがデッドラインミスを起こす可能性があるかどうか判定する（ステップＳ１０１〜Ｓ１０３）。そして、スケジューリング可能性判定部１０１は、注目するタスク k を順番に変えながら（ステップＳ１０４、Ｓ１０５）、上記判定を繰り返し実行する。
【００３５】
もしすべてのタスクがデッドラインミスを起こす可能性がないと判定された場合には（ステップＳ１０５のＹＥＳ）、スケジューリング可能性判定部１０１は、スケジューリング可能であると判定する（ステップＳ１０６）。タスクの中に 1 つでもデッドラインミスを起こす可能性があると判断されるタスクが含まれている場合には（ステップＳ１０３のＹＥＳ）、スケジューリング可能性判定部１０１は、その時点でスケジューリング不可能であると判定する（ステップＳ１０７）。
【００３６】
スケジューリング可能性判定部１０１によってスケジューリング可能であると判定された場合には、デッドラインミスの発生を招くことなく、EDF アルゴリズムを用いたリアルタイムスケジューリングを実際に実行することが可能である。
【００３７】
本実施形態では、タスクがデッドラインミスを起こす場合に必ず成り立つ事象を用い、その事象が成り立つ場合にはタスクがデッドラインミスを起こす可能性があると判定を行う。
【００３８】
図５に、上記事象を用い図４に示したフローチャートを書き直したものを示した。
【００３９】
図５のフローチャートにおいては、タスク k がデッドラインミスを起こす場合に必ず成り立つ事象を Ak で表している。そのような事象はタスクごとに異なることから添字 k を付けてある。図５のフローチャートにおいては、スケジューリング可能性判定部１０１は、Ak が成り立つか否かを判定し（ステップＳ２０１）、これによって、EDF アルゴリズムを用いてスケジューリングした場合に、タスク k のデッドラインミスが発生する可能性があるかどうかを判定する。
【００４０】
より具体的には、タスク k がデッドラインミスを起こす場合に必ず成り立つ事象は以下に説明を行う Lk, Uk を用いた不等式 Lk < Uk で表される。この不等式の左辺, 右辺はタスクごとに異なることから添字 k を付けてある。
【００４１】
図７に、上記不等式 Lk < Ukを用い図５に示したフローチャートを書き直したものを示した。図７のフローチャートにおいては、スケジューリング可能性判定部１０１は、Lk < Uk が成り立つか否かを判定し（ステップＳ３０１）、これによってタスク k のデッドラインミスが発生する可能性があるかどうかを判定する。
【００４２】
次に、本実施形態で用いる、タスク k がデッドラインミスを起こす場合に必ず成り立つ事象 Lk < Uk ついて、第一に概要説明、第二に詳細説明を行う。
【００４３】
第一に上記事象について概要説明を行う。
【００４４】
デッドラインミスは、スケジューリングされた全てのタスクの負荷がリアルタイムシステムの処理能力を越える場合に発生する。そこでまず、負荷に関して定義を行う。負荷の定義は、 Lk, Uk を説明する際に重要な役割を果たす。
【００４５】
以下、負荷に関して厳密な定義を行う。
【００４６】
いま、複数のタスクを複数のプロセッサ上で実行する場合を想定する。そして、ある任意の期間Ｔに注目する。あるタスク i のジョブ群のうち、期間Ｔ内に絶対デッドラインを持つジョブ群のみに注目し、これらのジョブそれぞれが期間Ｔ内に実行される時間を合計したものをタスク i の“単一負荷時間”と定義する。
【００４７】
タスク i の利用プロセッサ数とタスク i の単一負荷時間とを掛け合わせたものをタスク i の“単一負荷”と定義する。タスク i の“単一負荷”は、そのタスク i 自体の実行によって生じる負荷である。
【００４８】
以上の“単一負荷時間”と“単一負荷”の定義により、たとえタスク i のあるジョブが期間Ｔ内に実行されていても、このジョブの絶対デッドラインが期間Ｔ内に入っていなければ、このジョブの実行時間はタスク i の“単一負荷時間”には加味されない。
【００４９】
また、すべてのタスクそれぞれの“単一負荷”を足し合わせたものを“合計負荷”と定義する。
【００５０】
上記の“単一負荷時間”、“単一負荷”、“合計負荷”の値を期間の長さで割ると様々な時間平均を求めることができる。
【００５１】
本明細書では、
“単一負荷時間”を期間Ｔの長さで割った値を“平均単一負荷時間”,
“単一負荷”を期間Ｔの長さで割った値を“平均単一負荷”,
“合計負荷”を期間Ｔの長さで割った値を“平均負荷”
とそれぞれ定義する。
【００５２】
いま、例えば期間 [T, T + Δ) に注目する。ここで、記号“[”は以上、記号“)”は未満を意味する。つまり、期間 [T, T + Δ) は、時刻Tから、時刻T + Δの直前までの期間である。
【００５３】
タスク数を N, タスク i の利用プロセッサ数を Mi, タスク i の単一負荷時間を Ei とすると、
期間 [T, T + Δ) におけるタスク i の単一負荷時間 = Ei,
期間 [T, T + Δ) におけるタスク i の単一負荷 = Mi * Ei,
期間 [T, T + Δ) における全てのタスクの合計負荷 = Σi=1...N ( Mi * Ei ),
期間 [T, T + Δ) におけるタスク i の平均単一負荷時間 = Ei / Δ,
期間 [T, T + Δ) におけるタスク i の平均単一負荷 = Mi * Ei / Δ,
期間 [T, T + Δ) における全てのタスクの平均負荷 = { Σi=1...N ( Mi * Ei )} / Δ,
とそれぞれ計算することができる。
【００５４】
図６に負荷の具体例を示す。
【００５５】
この図６の横軸は時間軸, 縦軸はプロセッサを表している。また図６は、スケジューリングに利用可能な総プロセッサ数 （ＶＰＵの総数）が 3 であるリアルタイムシステムにおいて、タスク 1 とタスク 2 が実行される様子を、 期間 [T, T + Δ) に関して示している。タスク 1 の絶対デッドライン T3 は期間[T, T + Δ)内に含まれている。このタスク 1 は、時刻 T1 から時刻 T2 の間プロセッサ 1 上で実行される。タスク 2 の絶対デッドライン T6 は期間[T, T + Δ)内に含まれている。このタスク 2 は、時刻 T4 から時刻 T5 の間 2 つのプロセッサ 2, 3 上で実行される。この 2 つのタスク 1 , 2 以外にこの期間[T, T + Δ)内に絶対デッドラインを持つタスクは存在しないとする。
【００５６】
この図６において、
タスク 1 の単一負荷時間 = T2 - T1 
タスク 1 の単一負荷 = 1 * (T2 - T1) 
タスク 2 の単一負荷時間 = T5 - T4 
タスク 2 の単一負荷 = 2 * (T5 - T4) 
合計負荷 = 1 * (T2 - T1) + 2 * (T5 - T4) 
タスク 1 の平均単一負荷時間 = (T2 - T1) / Δ 
タスク 1 の平均単一負荷 = 1 * (T2 - T1) / Δ 
タスク 2 の平均単一負荷時間 = (T5 - T4) / Δ 
タスク 2 の平均単一負荷 = 2 * (T5 - T4) / Δ 
平均負荷 = {1 * (T2 - T1) + 2 * (T5 - T4)} / Δ 
でそれぞれ計算される。
【００５７】
以下で詳しく説明する通り、あるタスク k がデッドラインミスを起こす場合においては、Lk は ある期間における全てのタスクの平均負荷以下の値に必ずなっており、Uk は同じ期間の平均負荷よりも必ず大きな値になっている。つまり、タスク k がデッドラインミスを起こす際には、必ず Lk < Uk という事象が成立する。スケジュール可能性判定部１０１は、Lk < Uk という事象が成立するかどうかを判定して、タスク k がデッドラインミスを起こす可能性があるかどうかを判断する。
【００５８】
以下において Lk, Uk を定義する。
【００５９】
まず、 Lk は、
“タスク k ごとに一意に定まる値であり、
タスク k がデッドラインミスを起こす場合に、 
この値以上の平均負荷を持つ期間が存在することが保証されている値” 
と定義する。
【００６０】
Lk は、タスク k がデッドラインミスを起こす場合には、“ある期間の実際の平均負荷が必ずこの値以上となる”という値であり、
Lk ≦ 実際の負荷
の関係が成立する。尚、Lk は、タスク k がデッドラインミスを起こす／起こさないに関係なく、タスク kのパラメタ情報と総プロセッサ数 M から求められる値である。
【００６１】
タスク k がデッドラインミスを起こす場合における Lk の値のことを、タスク k の “基準平均負荷”と呼ぶことにする。タスク k の“基準平均負荷”は、タスク k がデッドラインミスを起こす場合にのみ定義される値であり、ある一意に決められる期間の負荷はこの値以上になる。
【００６２】
また、“基準平均負荷期間”は
“あるタスクがデッドラインミスを起こす場合に一意に定まる期間であり, 
基準平均負荷以上の平均負荷を持つ期間”
と定義する。
【００６３】
あるタスクがデッドラインミスを起こす場合、全てのタスクの平均負荷は期間ごとに様々な値を取り得る。このため、基準平均負荷 Lk としてどの値を選択するかにはいくつかの選択肢がある。
上記基準平均負荷の定義は、選択肢のうちどの値を基準平均負荷として選択するかに関しては規定していない。また、あるタスクがデッドラインミスを起こす場合、基準平均負荷以上の平均負荷を持つ期間は一期間または複数期間存在する。
【００６４】
上記基準平均負荷期間の定義は、それらの期間のうちどの期間を基準平均負荷期間として選択するかに関しては規定していない。 
図８に基準平均負荷と基準平均負荷期間の具体例を示す。 
この図８の横軸が概念的な期間, 縦軸が平均負荷を表している。期間は開始時間 S と終了時間 E の二次元で表されるものであるため、本来であればグラフの一次元の軸 (横軸) で表すことができない。そこで、この図８では横軸があくまで “概念的”な期間であると考えて説明を行う。
【００６５】
図８のグラフには、複数のタスクを複数のプロセッサ上で EDF アルゴリズムを用いて
スケジューリングした際に、期間ごとに平均負荷がどのように変化するかが波線で表されており、ある時刻においてタスク k がデッドラインミスを起こしているとする。この場合、平均負荷がタスク k の基準平均負荷Lk 以上となる期間が必ず存在する。
【００６６】
図８のグラフにおいては、
期間 I1 と期間 I2 の間の期間, 
期間 I3 と期間 I4 の間の期間, 
期間 I5 と期間 I6 の間の期間が
Lk 以上の平均負荷を持つ期間であるとする。 
これらの期間の中から、タスク k の基準平均負荷期間が一意に定義される。図８では、例えば I3 をタスク k の基準平均負荷期間であるとしている。
【００６７】
次に、 Uk,i は
“タスク k, タスク i の二つのタスクの組ごとに一意に定まる値であり, 
タスク k がデッドラインミスを起こす場合に, 
タスク k の基準平均負荷期間におけるタスク i の平均単一負荷時間以上の値に
( i が k に等しい場合には, 平均単一負荷時間より大きく ) なっていることが
保証されている値“ 
と定義する。
【００６８】
Uk は 
Uk = Σi=1...N ( Mi * Uk,i ) と定義する。
【００６９】
Uk は、タスク k がデッドラインミスを起こす場合には、“基準平均負荷期間の実際の平均負荷が必ずこの値未満となる”という値であり、
実際の負荷  < Uk 
の関係が成立する。
【００７０】
タスク k がデッドラインミスを起こす場合においては、タスク k の基準平均負荷期間におけるタスク i の平均単一負荷時間の値以上となる値 ( i が k に等しい場合には, 平均単一負荷時間よりも大きい値) は無限に存在する。
【００７１】
上記 Uk,i の定義は、それらの値のうちどの値を Uk,i として選択するかに関しては規定していない。
【００７２】
あるタスクの平均単一負荷時間の値はどんなタスクに対しても 1 以下であるので、一例として、 i が k と等しいならば Uk,i = 1.1、それ以外の場合には Uk,i = 1 と定義することが可能である。これはほんの一例であり、複数存在する Uk,i の候補の中から、本実施形態例において具体的にどのような方法を用いて Uk,i を決めているかに関しては、タスクがデッドラインミスを起こす場合に必ず成り立つ事象 Lk < Uk の詳細説明を行う際に述べる。
【００７３】
Lk, Uk の定義を行ったので、次にタスク k がデッドラインミスを起こす場合に
Lk < Uk という事象が必ず成り立つことを説明する。
【００７４】
タスク k がデッドラインミスを起こす場合において、例えば、
タスク k の基準平均負荷期間を [Tk, Tk + Δk),
タスクの数を N, 
タスク i の利用プロセッサ数を Mi,
基準平均負荷期間 [Tk, Tk + Δk) におけるタスク i の単一負荷時間を Ei
とすると、基準平均負荷と単一平均負荷の関係から、以下の式が成り立つ。
【００７５】
タスク k の基準平均負荷期間 [Tk, Tk + Δk) における全てのタスクの平均負荷 
= { Σi=1...N ( Mi * Ei )} / Δk 
= Σi=1...N ( Mi * 基準平均負荷期間 [Tk, Tk + Δk) におけるタスク i の平均単一負荷時間) 
タスク k の基準平均負荷 Lk は、タスク k の基準平均負荷期間 [Tk, Tk + Δk) における全てのタスクの平均負荷以下であるこのことから、Lk に関する以下の式が成り立つ。
【００７６】
Lk ≦ タスク k の基準平均負荷期間 [Tk, Tk + Δk) における全てのタスクの平均負荷
また Uk,i は、 “タスク k がデッドラインミスを起こす場合に, 
タスク k の基準平均負荷期間におけるタスク i の平均単一負荷時間以上に 
( i が k に等しい場合には, 平均単一負荷時間より大きく ) なっていることが
保証されている値”であることから、 Uk,i に関する以下の式が成り立つ。 
i = k の場合, 
Uk,i > (基準平均負荷期間 [Tk, Tk + Δk) におけるタスク i の平均単一負荷時間)                                                                    …（１） 
それ以外の場合（つまり i ≠ k の場合）, 
Uk,i ≧ (基準平均負荷期間 [Tk, Tk + Δk) におけるタスク i の平均単一負荷時間)                                                                …（２） 
また、
Uk = Σi=1...N Mi * Uk,i                                        …（３）
である。
【００７７】
これらの式（１）〜（３）と先に示した Lk に関する不等式を用いると、以下の式を導くことができる。
【００７８】
Lk < Uk                                                            …（４） 
以上のことから、タスク k がデッドラインミスを起こす場合には、Lk < Uk という事象が必ず成り立つことが示された。
【００７９】
次に、本実施形態で用いる、あるタスクがデッドラインミスを起こす場合に必ず成り立つ事象について詳細説明を行う。
【００８０】
タスク k がデッドラインミスを起こす場合に必ず成り立つ事象 Lk < Uk の
概要説明においては、
１）複数存在する Lk の値の候補から, 本実施形態において, 具体的にどのような方法を用いて Lk を選択しているか
２）複数存在する基準平均負荷期間の候補の中から, 本実施形態において, 具体的にどのような方法を用いて基準平均負荷期間を選択しているか
３）複数存在する Uk,i の値の候補から, 本実施形態において, 具体的にどのような方法を用いて Uk,i を選択しているか
に関しては特に規定しておらず、
これらに関しては事象 Lk < Uk の詳細説明を行う際に述べると言うに留めている。
【００８１】
そこで以下において、これら三つの選択方法に関して詳細説明を行う。
【００８２】
本実施例では、 Lk を以下に示す値にする。
【００８３】
(1) Mk ≦ (M + 1)/2 の場合
Lk = (M - Mk + 1) - (M - 2Mk + 1)Ck/Dk 
(2) (M + 1)/2 < Mk の場合
Lk = M - Mk + 1
既に概要説明において述べた通り、タスク k がデッドラインミスを起こす場合において、全てのタスクの平均負荷が Lk 以上である期間が必ず存在するように Lk を選択しなければならない。
【００８４】
以下において、タスク k がデッドラインミスを起こす場合においては、全てのタスクの平均負荷が上記 Lk 以上となる期間が必ず存在することを示す。
【００８５】
そのためには、タスク k がデッドラインミスを起こす場合にこの時刻を Tk' とし、期間 [Tk' - Dk, Tk') における全てのタスクの平均負荷が上記 Lk 以上であることが示せれば十分である。
【００８６】
図９にタスク k がデッドラインミスを起こす直前の期間 [Tk' - DK, Tk') におけるタスク群の実行例を示す。図９の横軸は時間軸, 縦軸は各タスクが利用中のプロセッサ数を表している。また、この図９のグラフにおいて、ダブルハッチが施されている部分がタスク k の実行を示し、シングルハッチが施されている部分がタスク k 以外の他のタスク群の実行を示している。Tk' はタスク k がデッドラインミスを起こす可能性がある時点であり、期間 [Tk' - DK, Tk') は、タスク k の相対デッドラインの期間である。
【００８７】
またこのグラフでは、期間 [Tk' - DK, Tk') にタスク k のジョブが２回に分けて実行され、その合計の実行時間の長さを x で示している。
【００８８】
x = x1 + x2
タスク k が時刻Tk' でデッドラインミスを起こした場合、x はタスク k の処理時間 Ck よりも小さい。したがって、Dk から x を引いた残りの時間はタスク k を実行するために必要な Mk 個のプロセッサの空きがなかった、つまり少なくともM - Mk + 1 個のプロセッサがタスク k 以外のタスクを実行するために利用されていたことになる。
【００８９】
この事実を用いて、期間 [Tk' - DK, Tk') における全てのタスクの平均負荷を計算すると、その値は、
{Mk * x + (M - Mk + 1)(Dk - x)} / Dk                         …（５）
以上の値であることが分かる。
【００９０】
タスク k の実行時間 x は 0 以上 Ck 以下であるので、この式（５）の最小値は、
Mk ≦ (M + 1)/2 の場合は 
(M - Mk + 1) - (M - 2Mk + 1)Ck/Dk,
(M + 1)/2 < Mk の場合は 
M - Mk + 1
であり、これらは上記 Lk の値に等しい。
【００９１】
以上のことから、タスク k がデッドラインミスを起こす場合には、平均負荷が上記 Lk 以上の期間が必ず存在することが示された。
【００９２】
また、以上のことから、Lk の値は、タスク k のデッドラインミスを引き起こす可能性がある、最小の平均負荷値に相当するものであると言える。タスク k がデッドラインミスを起こす場合には、そのデッドラインミスを起こす直前のある期間（例えば、タスク k の相対デッドラインの期間）における平均負荷は Lk の値以上となる。
【００９３】
次に、基準平均負荷期間の定め方について説明する。
【００９４】
本実施形態では、 タスク k がデッドラインミスを起こす場合に, この時刻を Tk' とし, 平均負荷が Lk 以上である期間 [Tk' - Δk', Tk') の中で一番長い期間を基準平均負荷期間とする。 タスク k がデッドラインミスを起こす場合においては、平均負荷が Lk 以上である期間が必ず存在するので、基準平均負荷期間は必ず存在する。
【００９５】
図１０に基準平均負荷期間の具体例を示す。
【００９６】
この図１０の横軸が時間軸、縦軸が平均負荷を表している。期間 [T, Tk') における平均負荷と時刻 T との関係が波線で表されている。期間 [T, Tk') における平均負荷の値が、時刻 T 上に示されている。たとえば、時刻 Tk' - Dk 上に示された平均負荷の値は期間 [Tk' - Dk, Tk') における平均負荷の値であり、時刻 Tk 上に示された平均負荷の値は期間 [Tk , Tk') における平均負荷の値である。図１０においては、平均負荷が Lk 以上になっている幾つかの期間の中でもっとも長い期間[Tk, Tk') がこの具体例における基準平均負荷期間である。
【００９７】
本実施形態では、Uk,i を以下に示す値にする。
【００９８】
(1) Mk ≦ (M + 1) / 2 の場合
(1-1) Mi < (M + 1) / 2 の場合
(1-1-1) Xk,i ≦ 0 の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
(1-1-2) 0 < Xk,i < Ci/Ti の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+(Ci-Xk,i*Ti)/Dk
(1-1-3) Ci/Ti ≦ Xk,i の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}
(1-2) Mi = (M + 1) / 2 の場合
(1-2-1) Mk ≠ (M + 1) / 2 の場合
(1-2-1-1) Ck / Dk < 1 / 2 の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
(1-2-1-2) 1 / 2 ≦ Ck / Dk の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}
(1-2-2) Mk = (M + 1) / 2 の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}
(1-3) (M + 1) / 2 < Mi の場合
(1-3-1) Xk,i ≦ 0 の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}
(1-3-2) 0 < Xk,i の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
(2) (M + 1) / 2 < Mk の場合
(2-1) Mi < (M + 1) / 2 の場合
(2-1-1) Yk,i < Ci/Ti の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+(Ci-Yk,i*Ti)/Dk
(2-1-2) Ci/Ti ≦ Yk,i の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}
(2-2) (M + 1) / 2 ≦ Mi の場合
(2-2-1) Mi ≦ Mk の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}
(2-2-2) Mk < Mi の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
ただし、
Xk,i = {Mk - Mi + (M - 2Mk + 1)Ck/Dk}/(M - 2Mi + 1)
Yk,i = (Mk - Mi)/(M - 2Mi + 1)
である。
【００９９】
また、上記 Uk,i の値を示す式においては、複数の条件のアンド条件を階層構造で示している。例えば、
“(1) Mk ≦ (M + 1) / 2 の場合
(1-1) Mi < (M + 1) / 2 の場合
(1-1-1) Xk,i ≦ 0 の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
(1-1-2) 0 < Xk,i < Ci/Ti の場合
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+(Ci-Xk,i*Ti)/Dk ”
という表記は、
(1) Mk ≦ (M + 1) / 2 の場合，(1-1) Mi < (M + 1) / 2 の場合，且つ
(1-1-1) Xk,i ≦ 0 の場合に
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
(1) Mk ≦ (M + 1) / 2 の場合，(1-1) Mi < (M + 1) / 2 の場合，且つ
(1-1-2) 0 < Xk,i < Ci/Ti の場合に
Uk,i = Ci/Ti{1+(Ti-Di)/Dk}+(Ci-Xk,i*Ti)/Dk 
であることを示している。以下においても、同様の表記を利用する。
【０１００】
既に事象 Lk < Uk の概要説明において述べた通り、
タスク k がデッドラインミスを起こす場合に, 
基準平均負荷期間におけるタスク i の平均単一負荷時間が Uk,i 以下に 
( i が k に等しい場合には, タスク i の平均単一負荷時間が Uk,i 未満に ) 
必ずなるように Uk,i を選択しなければならない。
【０１０１】
以下において、
タスク k がデッドラインミスを起こす場合に, 
上記 Uk,i が基準平均負荷期間におけるタスク i の平均単一負荷時間以上に
( i が k に等しい場合には, タスク i の平均単一負荷時間がより大きく ) 
なっていることを示す。
【０１０２】
図１１にタスク k の基準平均負荷期間におけるタスク i の実行の具体例を示す。
【０１０３】
この図１１の横軸は時間軸、縦軸はプロセッサを表している。総プロセッサ数は 3 であり、期間 [Tk, Tk + Δk) がタスク k の基準平均負荷期間であるとする。
【０１０４】
またこの具体例では、基準平均負荷期間 [Tk, Tk + Δk) にデッドラインが入っているタスク i のジョブが n + 1 個存在するとする。
【０１０５】
さらに、 n + 1 個のジョブのうち最初に開始するジョブは、時刻 Tk - φに開始し、基準平均負荷期間 [Tk, Tk + Δk) 内に εi ( ≦ Ci ) の長さの時間だけ実行されるとする。また、n + 1 個のジョブのうち最後に開始するジョブは時刻 Tk + Δk - ψに開始し、基準平均負荷期間 [Tk, Tk + Δk) 内に δi ( i = k の場合には δi < Ci, それ以外の場合には δi ≦ Ci ) の長さの時間だけ実行されるとする。
【０１０６】
基準平均負荷期間 [Tk, Tk + Δk) におけるタスク i の単一負荷時間は、
{εi + ( n - 1) * Ci + δi} / Δk 
で計算でき、
i = k の場合には 
{εi + ( n - 1) * Ci + δi} / Δk < (εi + n * Ci) / Δk 
それ以外の場合には
{εi + ( n - 1) * Ci + δi} / Δk ≦ (εi + n * Ci) / Δk 
の関係が成り立つ。
【０１０７】
このため、(εi + n * Ci) / Δk の値が上記 Uk,i 以下であることが示せれば十分である。
【０１０８】
以下、
(1) (εi + n * Ci) / Δk が最大になる条件を求める, 
(2) “εi がこの値よりは絶対に大きくなることはないという値”を計算する, 
(3) “(εi + n * Ci ) / Δk がこの値よりは絶対に大きくなることはないという値”を計算する, 
という三つの手続きを経て、(εi + n * Ci) / Δk がこの値よりは絶対に大きくなることはないという値を計算する。
【０１０９】
＜＜(εi + n * Ci) / Δk が最大になる条件＞＞
始めに, (εi + n * Ci) / Δk が最大になる条件を求める。
【０１１０】
n + 1 個のジョブのうち最後に開始するジョブの絶対デッドラインが限りなく Tk + Δk に近くなる場合、図１０に示した具体例で言うと、 ψ が限りなく Di に近くなる場合に (εi + n * Ci) / Δk が最大になる。
【０１１１】
このことは、 ψ = Di + d ( d > 0 ) である期間 [Tk, Tk + Δk) において
(εi + n * Ci) / Δk が最大になると仮定すると、
期間 [Tk, Tk + Δk) 
期間 [Tk - d / 2, Tk + Δk - d / 2) とでは、
期間 [Tk - d / 2, Tk + Δk - d / 2) の方が (εi + n * Ci) / Δk の値が大きくなり不合理を生じることから証明される。
【０１１２】
また, ψ を Di に限りなく近くすると、n は (Δk - Di + φ) / Ti に限りなく近くなる。
【０１１３】
＜＜εi がこの値よりは絶対に大きくなることはないという値の計算＞＞
次に, εi がこの値よりは絶対に大きくなることはないという値を計算する。
【０１１４】
0 < εi であると仮定する。
【０１１５】
図１２に期間 [Tk - φ, Tk) におけるタスク群の実行の具体例を示す。
【０１１６】
この図１２の横軸が時間軸, 縦軸がタスク群によって使用されているプロセッサ数を表している。また、この図１２のグラフにおいて、ダブルハッチが施されている部分がタスク i の実行を表しており、シングルハッチが施されている部分がタスク i 以外の他のタスク群の実行を表している。またこの具体例では、 期間 [Tk - φ, Tk) にタスク i が長さ Ci - εi の時間だけ実行されている。
【０１１７】
φ から Ci - εi を引いた残り φ - Ci + εi の時間は、タスク i を実行するために必要な Mi 個のプロセッサの空きがなかった, つまり少なくとも M - Mi + 1 個のプロセッサがタスク i 以外のタスクを実行するために利用されていたことになる。
【０１１８】
この事実を用いると、
期間 [Tk - φ, Tk + Δk) の全体負荷のうち
期間 [Tk - φ, Tk) に含まれるものは、
Mi * (Ci - εi) + (M - Mi + 1)(φ - Ci + εi) 
よりも小さくなることはないことが計算される。
【０１１９】
平均負荷が Lk 以上である期間 [Tk' - Δk', Tk') の候補の中で一番長い期間が基準平均負荷期間の定義であったので、
{Mi * (Ci - εi) + (M - Mi + 1)(φ - Ci + εi) } / φ は
基準平均負荷より小さい。
【０１２０】
つまり、
{Mi * (Ci - εi) + (M - Mi + 1)(φ - Ci + εi) } / φ < Lk       …（６）
の関係が成り立つ. 
上記不等式（６）を適切な場合分けを行って整理すると、以下の通りになる。
【０１２１】
ただし、
Xk,i = {Mk - Mi + (M - 2Mk + 1)Ck/Dk}/(M - 2Mi + 1)
Yk,i = (Mk - Mi)/(M - 2Mi + 1)
と置いている。
【０１２２】
(1) Mk ≦ (M + 1) / 2 の場合
(1-1) Mi < (M + 1) / 2 の場合
εi < Ci - Xk,i * φ
(1-2) Mi = (M + 1) / 2 の場合
(1-2-1) Mk ≠ (M + 1) / 2 の場合
Ck / Dk < 1 / 2 
(1-2-2) Mk = (M + 1) / 2 の場合
0 < 0 
(1-3) (M + 1) / 2 < Mi の場合
Ci - Xk,i * φ < εi 
(2) (M + 1) / 2 < Mk の場合
(2-1) Mi < (M + 1) / 2 の場合
εi < Ci - Yk,i * φ . 
(2-2) Mi = (M + 1) / 2 の場合
Mk < Mi = (M + 1) / 2 
(2-3) (M + 1) / 2 < Mi の場合
Ci - Yk,i * φ < εi . 
上記の結果には、 0 < 0 など恒等的に偽になる不等式が含まれているが、この場合は 0 < εi という仮定自体が誤っていたことを意味している。この結果に, さらに 0 ≦ εi ≦ Ci の関係を適用すると、εi は以下の通り整理できる。
【０１２３】
(1) Mk ≦ (M + 1) / 2 の場合
(1-1) Mi < (M + 1) / 2 の場合
(1-1-1) Xk,i ≦ 0 の場合
εi ≦ Ci 
(1-1-2) 0 < Xk,i * φ < Ci の場合 
εi < Ci - Xk,i * φ 
(1-1-3) Ci ≦ Xk,i * φ の場合
εi = 0 
(1-2) Mi = (M + 1) / 2 の場合
(1-2-1) Mk ≠ (M + 1) / 2 の場合
(1-2-1-1) Ck / Dk < 1 / 2 の場合
εi ≦ Ci 
(1-2-1-2) 1 / 2 ≦ Ck / Dk の場合
εi = 0 
(1-2-2) Mk = (M + 1) / 2 の場合
εi = 0 
(1-3) (M + 1) / 2 < Mi の場合
(1-3-1) Xk,i ≦ 0 の場合
εi = 0 
(1-3-2) 0 < Xk,i の場合
εi ≦ Ci 
(2) (M + 1) / 2 < Mk の場合
(2-1) Mi < (M + 1) / 2 の場合
(2-1-1) Yk,i ≦ 0 の場合
εi ≦ Ci 
(2-1-2)  0 < Yk,i * φ < Ci の場合
εi < Ci - Yk,i * φ 
(2-1-3) Ci ≦ Yk,i * φ の場合 
εi = 0 
(2-2) Mi = (M + 1) / 2 の場合 
εi = 0 
(2-3) (M + 1) / 2 < Mi の場合 
(2-3-1) Yk,i ≦ 0 の場合 
εi = 0 
(2-3-2) 0 < Yk,i の場合 
εi ≦ Ci 
以上、“εi がこの値よりは絶対に大きくなることはないという値”を計算した。
【０１２４】
＜＜ (εi + n * Ci ) / Δk がこの値よりは絶対に
大きくなることはないという値の計算＞＞
最後に、 (εi + n * Ci ) / Δk がこの値よりは絶対に大きくなることはないという値を計算する。
【０１２５】
εi がこの値よりは絶対に大きくなることはないという値が求められたので、この結果に加えて、
n = (Δk - Di + φ) / Ti,   Dk ≦ Δk,   0 < φ ≦ Ti 
の関係を用いると、
以下の不等式が成り立つ。
【０１２６】
(1) Mk ≦ (M + 1) / 2 の場合
(1-1) Mi < (M + 1) / 2 の場合
(1-1-1) Xk,i ≦ 0 の場合
(εi+n*Ci)/Δk≦Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk 
(1-1-2) 0 < Xk,i < Ci/Ti の場合
(εi+n*Ci)/Δk≦Ci/Ti{1+(Ti-Di)/Dk}+(Ci-Xk,i*Ti)/Dk 
(1-1-3) Ci/Ti ≦ Xk,i の場合
(εi+n*Ci)/Δk≦Ci/Ti{1+(Ti-Di)/Dk} 
(1-2) Mi = (M + 1) / 2 の場合
(1-2-1) Mk ≠ (M + 1) / 2 の場合
(1-2-1-1) Ck / Dk < 1 / 2 の場合
(εi+n*Ci)/Δk≦Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk 
(1-2-1-2) 1 / 2 ≦ Ck / Dk の場合
(εi+n*Ci)/Δk≦Ci/Ti{1+(Ti-Di)/Dk}
(1-2-2) Mk = (M + 1) / 2 の場合
(εi+n*Ci)/Δk≦Ci/Ti{1+(Ti-Di)/Dk} 
(1-3) (M + 1) / 2 < Mi の場合
(1-3-1) Xk,i ≦ 0 の場合
(εi+n*Ci)/Δk≦Ci/Ti{1+(Ti-Di)/Dk}
(1-3-2) 0 < Xk,i の場合
(εi+n*Ci)/Δk≦Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
(2) (M + 1) / 2 < Mk の場合
(2-1) Mi < (M + 1) / 2 の場合
(2-1-1) Yk,i < Ci/Ti の場合
(εi+n*Ci)/Δk≦Ci/Ti{1+(Ti-Di)/Dk}+(Ci-Yk,i*Ti)/Dk
(2-1-2)  Ci/Ti ≦ Yk,i の場合
(εi+n*Ci)/Δk≦Ci/Ti{1+(Ti-Di)/Dk}
(2-2)  (M + 1) / 2  ≦ Mi の場合
(2-2-1) Mi ≦ Mk の場合
(εi+n*Ci)/Δk≦Ci/Ti{1+(Ti-Di)/Dk} 
(2-2-2) Mk < Mi の場合
(εi+n*Ci)/Δk≦Ci/Ti{1+(Ti-Di)/Dk}+Ci/Dk
以上のことから、 (εi + n * Ci) / Δk の値が Uk,i 以下であることが示された。 
以上、本実施形態で用いる、 タスクがデッドラインミスを起こす場合に必ず成り立つ
事象 Lk < Uk について詳細説明を行った。
【０１２７】
次に、図１３のフローチャートを参照して、スケジュール可能性判定部１０１によって実行されるスケジューリング可能性判定処理全体の流れについて説明する。
【０１２８】
スケジュール可能性判定部１０１は、スケジューリング対象となる全てのタスクそれぞれに対応するタスクパラメタ情報、および総プロセッサ数を、オペレーティングシステムを通じて入力する（ステップＳ５０１）。次いで、スケジュール可能性判定部１０１は、タスク k のタスクパラメタ情報と、総プロセッサ数とに基づいて、タスク k のデッドラインミスを引き起こす可能性がある、最小の平均負荷値を求める（ステップＳ５０２）。最小の平均負荷値は上記 Lk である。
【０１２９】
次に、スケジュール可能性判定部１０１は、全てのタスクそれぞれのタスクパラメタ情報に基づいて、平均負荷が Lk 以上となる最も早い時点からタスク k のデッドラインミスが発生する可能性がある時点までの期間(基準平均負荷期間)において発生する可能性がある、全てのタスクそれぞれの最大平均負荷の合計値を算出する（ステップＳ５０３）。この合計値は、上記 Uk である。
【０１３０】
スケジュール可能性判定部１０１は、Lk と Uk を比較してタスク k のデッドラインミスが発生する可能性があるかどうかを判定する（ステップＳ５０４）。そして、スケジュール可能性判定部１０１は、タスク k を変更しながら（ステップＳ５０４）、ステップＳ５０２〜Ｓ５０４を繰り返し実行し、全てのタスクについてデッドラインミスを発生する可能性がないと判定された場合にスケジューリング可能であると判定する。
【０１３１】
以上のように、本実施形態では、プロセッサ総数と各タスクの利用プロセッサ数とを考慮してLk と Uk の値を定義し、タスク毎に Lk , Uk を求めて Lk < Uk の事象が成立するかどうかを判定しているので、一つのタスクに同時に割り当てることが必要なプロセッサ数が複数である場合にも利用可能であり、かつ計算時間が短いスケジューリング可能性判定方法を実現できる。
【０１３２】
また、複数の基準平均負荷期間の候補の中で一番長い期間を基準平均負荷期間として使用しているので、スケジューリング可能性判定の判定結果の厳密性を高めることが出来る。
【０１３３】
また、実際には、一つのタスクが同時に使用するプロセッサの数には上限を設けることが現実的であるので、Uk,iの値としては、例えば、(1) Mk ≦ (M + 1) / 2, 且つMi < (M + 1) / 2の条件に対応する値のみを定義しても、十分な効果を得ることが出来る。
【０１３４】
また、以上の例では、いずれか一つのタスクがLk < Ukの条件を満たすならば、EDFアルゴリズムを用いてリアルタイムスケジューリングすることが不可能であると判定したが、全てのタスクが Uk ≦  Lk  の条件を満たすならばリアルタイムスケジューリング可能であると判定することも出来る。
【０１３５】
この場合のスケジューリング可能性判定処理全体の流れを図１４に示す。
【０１３６】
スケジュール可能性判定部１０１は、スケジューリング対象となる全てのタスクそれぞれに対応するタスクパラメタ情報、および総プロセッサ数を、オペレーティングシステムを通じて入力する（ステップＳ６０１）。次いで、スケジュール可能性判定部１０１は、デッドラインミスを発生する可能性を検証するための２つの値、つまりLk , Uk 、をタスク k 毎に求める（ステップＳ６０２）。このステップＳ６０２では、スケジュール可能性判定部１０１は、まず、検証対象のタスク k のデッドラインミスを引き起こす可能性がある、最小の平均負荷値（ Lk ）を求める。次いで、スケジュール可能性判定部１０１は、全てのタスクそれぞれのタスクパラメタ情報に基づいて、平均負荷が Lk 以上となる最も早い時点から検証対象のタスク k のデッドラインミスが発生する可能性がある時点までの期間(基準平均負荷期間)において発生する可能性がある、全てのタスクそれぞれの最大平均負荷の合計値（ Uk ）を算出する。
【０１３７】
スケジュール可能性判定部１０１は、検証対象のタスクを変更しながらステップＳ６０２の処理を繰り返し実行し（ステップＳ６０３，Ｓ６０４）、これによって全てのタスクそれぞれについて、Lk と Ukを求める。
【０１３８】
次に、スケジュール可能性判定部１０１は、全てのタスクが、Uk ≦  Lk  の条件を満たすか否かを判定する（ステップＳ６０５）。満たすならば、スケジューリング可能と判定し（ステップＳ６０６）、満たさないならば、スケジューリング不可能と判定する（ステップＳ６０７）。
【０１３９】
次に、図１５のフローチャートを参照して、スケジューリング可能性判定処理のさらなる他の例について説明する。
【０１４０】
ここでは、タスク k がEDF アルゴリズムを用いてスケジューリングされた場合にデッドラインミスを起こす可能性を示す値 Xk を用いる。 Xk は、
Xk = Uk - Lk
で定義される。
【０１４１】
スケジュール可能性判定部１０１は、スケジューリング対象となる全てのタスクそれぞれに対応するタスクパラメタ情報、および総プロセッサ数を、オペレーティングシステムを通じて入力する（ステップＳ７０１）。次いで、スケジュール可能性判定部１０１は、タスク k がデッドラインミスを起こす可能性を示す値 Xk を求める（ステップＳ７０２）。このステップＳ７０２では、スケジュール可能性判定部１０１は、まず、検証対象のタスク k のデッドラインミスを引き起こす可能性がある、最小の平均負荷値（ Lk ）を求める。次いで、スケジュール可能性判定部１０１は、全てのタスクそれぞれのタスクパラメタ情報に基づいて、平均負荷が Lk 以上となる最も早い時点から検証対象のタスク k のデッドラインミスが発生する可能性がある時点までの期間(基準平均負荷期間)において発生する可能性がある、全てのタスクそれぞれの最大平均負荷の合計値（ Uk ）を算出する。そして、これらUk , Lk を用いて、タスク k がデッドラインミスを起こす可能性を示す値 Xk を求める。
【０１４２】
スケジュール可能性判定部１０１は、検証対象のタスクを変更しながらステップＳ７０２の処理を繰り返し実行し（ステップＳ７０３，Ｓ７０４）、これによって全てのタスクそれぞれについて、Xk を求める。
【０１４３】
次に、スケジュール可能性判定部１０１は、全てのタスクそれぞれに対応する全てのXk の値が正であるかか否かを判定する（ステップＳ７０５）。満たすならば、スケジューリング可能と判定し（ステップＳ７０６）、満たさないならば、スケジューリング不可能と判定する（ステップＳ７０７）。
【０１４４】
なお、本実施形態のスケジューリング可能性判定方法は全てコンピュータプログラムによって実現されているので、そのコンピュータプログラムが格納されたコンピュータ読み取り可能な記録媒体を通じてそのコンピュータプログラムをコンピュータに導入して実行するすることにより、容易に本実施形態と同様の効果を実現することが出来る。
【０１４５】
また、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１４６】
【図１】本発明の一実施形態に係るリアルタイムシステムの構成の例を示すブロック図。
【図２】同実施形態のリアルタイムシステムで利用されるスケジューリング可能性判定部の動作を説明するための図。
【図３】同実施形態のリアルタイムシステムによって実行されるタスクを説明するための図。
【図４】同実施形態のリアルタイムシステムによって実行されるスケジューリング可能性判定処理の手順を示す第１のフローチャート。
【図５】同実施形態のリアルタイムシステムによって実行されるスケジューリング可能性判定処理の手順を示す第２のフローチャート。
【図６】同実施形態のリアルタイムシステムにおける負荷の具体例を説明するための図。
【図７】同実施形態のリアルタイムシステムによって実行されるスケジューリング可能性判定処理の手順を示す第３のフローチャート。
【図８】同実施形態のリアルタイムシステムにおける平均負荷と基準平均負荷期間を説明するための図。
【図９】同実施形態のリアルタイムシステムにおいてデッドラインミスが発生する直前の期間におけるタスク群の実行例を示す図。
【図１０】同実施形態のリアルタイムシステムにおける基準平均負荷期間の定め方を説明するための図。
【図１１】同実施形態のリアルタイムシステムにおける基準平均負荷期間におけるタスク i の実行例を示す図。
【図１２】図１１における期間 [Tk - φ, Tk) のタスク群の実行の具体例を示す図。
【図１３】同実施形態のリアルタイムシステムによって実行されるスケジューリング可能性判定処理の手順を示す第４のフローチャート。
【図１４】同実施形態のリアルタイムシステムによって実行されるスケジューリング可能性判定処理の手順を示す第５のフローチャート。
【図１５】同実施形態のリアルタイムシステムによって実行されるスケジューリング可能性判定処理の手順を示す第６のフローチャート。
【符号の説明】
【０１４７】
１１…ＭＰＵ、１２…ＶＰＵ、１４…共有メモリ、１０１…スケジュール可能性判定部、１０２…スケジューラ
【図１】
2005284351.tif 000003
【図２】
2005284351.tif 000004
【図３】
2005284351.tif 000005
【図４】
2005284351.tif 000006
【図５】
2005284351.tif 000007
【図６】
2005284351.tif 000008
【図７】
2005284351.tif 000009
【図８】
2005284351.tif 000010
【図９】
2005284351.tif 000011
【図１０】
2005284351.tif 000012
【図１１】
2005284351.tif 000013
【図１２】
2005284351.tif 000014
【図１３】
2005284351.tif 000015
【図１４】
2005284351.tif 000016
【図１５】
2005284351.tif 000017