JPH08190489A - タスク処理実行可能性判定方法 - Google Patents
タスク処理実行可能性判定方法Info
- Publication number
- JPH08190489A JPH08190489A JP241695A JP241695A JPH08190489A JP H08190489 A JPH08190489 A JP H08190489A JP 241695 A JP241695 A JP 241695A JP 241695 A JP241695 A JP 241695A JP H08190489 A JPH08190489 A JP H08190489A
- Authority
- JP
- Japan
- Prior art keywords
- task
- tasks
- time set
- test time
- time
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Abstract
(57)【要約】
【目的】 縮小スケジュール試験時刻集合を用いること
により、複数のタスクのすべての仕事の処理実行がその
期限以内に終了するか否かの判定を高速に行うことがで
きるタスク処理実行可能性判定方法を提供する。 【構成】 各タスクの必要処理量情報を基にスケジュー
ル試験時刻集合の各要素を比較し、スケジュール試験時
刻集合に属する他の時刻における必要処理量情報の合計
結果からその時刻における必要処理量情報合計結果が誘
導される時刻を取り除いて、縮小スケジュール試験時刻
集合を求め（ステップＳ１３）、該縮小スケジュール試
験時刻集合の各時刻ｔについてのみ、その時刻までに発
生した各タスクの仕事の必要処理量情報の合計がｔ以下
であるか否かを調べて、すべてのタスクのすべての仕事
がその期限以内に終了することができるか否かを判定す
る（ステップＳ１４〜Ｓ１９）。
により、複数のタスクのすべての仕事の処理実行がその
期限以内に終了するか否かの判定を高速に行うことがで
きるタスク処理実行可能性判定方法を提供する。 【構成】 各タスクの必要処理量情報を基にスケジュー
ル試験時刻集合の各要素を比較し、スケジュール試験時
刻集合に属する他の時刻における必要処理量情報の合計
結果からその時刻における必要処理量情報合計結果が誘
導される時刻を取り除いて、縮小スケジュール試験時刻
集合を求め（ステップＳ１３）、該縮小スケジュール試
験時刻集合の各時刻ｔについてのみ、その時刻までに発
生した各タスクの仕事の必要処理量情報の合計がｔ以下
であるか否かを調べて、すべてのタスクのすべての仕事
がその期限以内に終了することができるか否かを判定す
る（ステップＳ１４〜Ｓ１９）。
Description
【０００１】
【産業上の利用分野】本発明は、計算機などにおいて複
数のタスクのスケジュールを行う場合の該スケジュール
による実行可能性を判定するタスク処理実行可能性判定
方法に関する。
数のタスクのスケジュールを行う場合の該スケジュール
による実行可能性を判定するタスク処理実行可能性判定
方法に関する。
【０００２】
【従来の技術】従来、複数のタスクが与えられた時に、
Rate Monotonic法あるいはInverse Deadline法でスケジ
ュール（どの時刻にどのタスクを実行するかの決定）を
行った場合に、すべてのタスクのすべての仕事がその期
限以内に終了することができるか否かを判定する方式と
しては、以下に示す判定法が存在する。なお、この判定
法に関しては、真鍋、青柳：『周期的リアルタイムタス
クのRate Monotonic法によるスケジュール可能性判定問
題について』、信学会コンピュテーション研究会（July
1994)などにおいて論じられている。
Rate Monotonic法あるいはInverse Deadline法でスケジ
ュール（どの時刻にどのタスクを実行するかの決定）を
行った場合に、すべてのタスクのすべての仕事がその期
限以内に終了することができるか否かを判定する方式と
しては、以下に示す判定法が存在する。なお、この判定
法に関しては、真鍋、青柳：『周期的リアルタイムタス
クのRate Monotonic法によるスケジュール可能性判定問
題について』、信学会コンピュテーション研究会（July
1994)などにおいて論じられている。
【０００３】すなわち、この判定法においては、まずタ
スクの集合をＸ＝｛τ1 ，τ2 ，…，τn ｝とする。各
タスクτi は発生周期情報ｐi 、必要処理量情報ｃi お
よび処理期限情報ｄi を持つ。これは、各タスクτi の
仕事が時刻ｋ・ｐi （ｋ＝０，１，２，…）に発生し、
各仕事の処理にはｃi 時間かかり、時刻ｋ・ｐi （ｋ＝
０，１，２，…）に発生した仕事は時刻ｋ・ｐi ＋ｄi
（ｋ＝０，１，２，…）までに終了しなければいけない
ことを表している。
スクの集合をＸ＝｛τ1 ，τ2 ，…，τn ｝とする。各
タスクτi は発生周期情報ｐi 、必要処理量情報ｃi お
よび処理期限情報ｄi を持つ。これは、各タスクτi の
仕事が時刻ｋ・ｐi （ｋ＝０，１，２，…）に発生し、
各仕事の処理にはｃi 時間かかり、時刻ｋ・ｐi （ｋ＝
０，１，２，…）に発生した仕事は時刻ｋ・ｐi ＋ｄi
（ｋ＝０，１，２，…）までに終了しなければいけない
ことを表している。
【０００４】Rate Monotonic法はすべてのタスクがｄi
＝ｐi を満足する場合に用いられるスケジュール法であ
り、『発生周期情報ｐi が小さいタスクを優先的に実行
する』という規則である。このスケジュール方法に基づ
く判定アルゴリズムの流れ図を図２に示す。この図２に
示す手順に従いスケジュールした場合、すべてのタスク
のすべての仕事がその期限以内に終了することができる
のは、ステップＳ３３およびステップＳ１６に示す、ｐ
1 ≦ｐ2 ≦…≦ｐn としたとき、１からｎまでのすべて
のｉの値について、以下の性質が成立することである。
＝ｐi を満足する場合に用いられるスケジュール法であ
り、『発生周期情報ｐi が小さいタスクを優先的に実行
する』という規則である。このスケジュール方法に基づ
く判定アルゴリズムの流れ図を図２に示す。この図２に
示す手順に従いスケジュールした場合、すべてのタスク
のすべての仕事がその期限以内に終了することができる
のは、ステップＳ３３およびステップＳ１６に示す、ｐ
1 ≦ｐ2 ≦…≦ｐn としたとき、１からｎまでのすべて
のｉの値について、以下の性質が成立することである。
【０００５】『スケジュール試験時刻集合Ｓi に含まれ
るある時刻ｔにおいて、その時刻までに発生したタスク
τ1 ，τ2 ，…，τi の仕事の必要処理量情報の総合計
がｔ以下であること。』 なお、ここでスケジュール試験時刻集合Ｓi は各タスク
の発生周期情報ｐi より、以下の式で求められる時刻の
集合である。
るある時刻ｔにおいて、その時刻までに発生したタスク
τ1 ，τ2 ，…，τi の仕事の必要処理量情報の総合計
がｔ以下であること。』 なお、ここでスケジュール試験時刻集合Ｓi は各タスク
の発生周期情報ｐi より、以下の式で求められる時刻の
集合である。
【０００６】
【数１】 一方、Inverse Deadline法はすべてのタスクがｄi ≦ｐ
i を満足する場合に用いられるスケジュール法であり、
『処理期限情報ｄi が小さいタスクを優先的に実行す
る』という規則である。この方法でスケジュールした場
合、すべてのタスクのすべての仕事がその期限以内に終
了することができるのは、ｄ1 ≦ｄ2 ≦…≦ｄn とした
とき、１からｎまでのすべてのｉの値について、以下の
性質が成立することである。
i を満足する場合に用いられるスケジュール法であり、
『処理期限情報ｄi が小さいタスクを優先的に実行す
る』という規則である。この方法でスケジュールした場
合、すべてのタスクのすべての仕事がその期限以内に終
了することができるのは、ｄ1 ≦ｄ2 ≦…≦ｄn とした
とき、１からｎまでのすべてのｉの値について、以下の
性質が成立することである。
【０００７】『スケジュール試験時刻集合Ｓi に含まれ
るある時刻ｔにおいて、その時刻までに発生したタスク
τ1 ，τ2 ，…，τi の仕事の必要処理量情報の総合計
がｔ以下であること。』 なお、ここでスケジュール試験時刻集合Ｓi は各タスク
の処理期限情報ｄi および発生周期情報ｐi より、以下
の式で求められる時刻の集合である。
るある時刻ｔにおいて、その時刻までに発生したタスク
τ1 ，τ2 ，…，τi の仕事の必要処理量情報の総合計
がｔ以下であること。』 なお、ここでスケジュール試験時刻集合Ｓi は各タスク
の処理期限情報ｄi および発生周期情報ｐi より、以下
の式で求められる時刻の集合である。
【０００８】
【数２】
【０００９】
【発明が解決しようとする課題】上述したように、従来
の判定法では、スケジュール試験時刻集合を発生周期情
報あるいは発生周期情報および処理期限情報のみを使っ
て決定しており、この集合に含まれるすべての時刻につ
いて、その時点での各タスクの必要処理量情報の合計を
求める必要があり、多大な計算を必要とする場合が多い
という問題がある。
の判定法では、スケジュール試験時刻集合を発生周期情
報あるいは発生周期情報および処理期限情報のみを使っ
て決定しており、この集合に含まれるすべての時刻につ
いて、その時点での各タスクの必要処理量情報の合計を
求める必要があり、多大な計算を必要とする場合が多い
という問題がある。
【００１０】本発明は、上記に鑑みてなされたもので、
その目的とするところは、縮小スケジュール試験時刻集
合を用いることにより、複数のタスクのすべての仕事の
処理実行がその期限以内に終了するか否かの判定を高速
に行うことができるタスク処理実行可能性判定方法を提
供することにある。
その目的とするところは、縮小スケジュール試験時刻集
合を用いることにより、複数のタスクのすべての仕事の
処理実行がその期限以内に終了するか否かの判定を高速
に行うことができるタスク処理実行可能性判定方法を提
供することにある。
【００１１】
【課題を解決するための手段】上記目的を達成するた
め、本発明のタスク処理実行可能性判定方法は、ある周
期で処理すべき仕事が発生し、それらの処理に期限が存
在するという性質を有するタスクが複数存在し、該複数
のタスクに対してRate Monotonic法またはInverse Dead
line法と呼ばれる手法でどの時刻にどのタスクを実行す
るかを決定するというスケジュールを行った場合にすべ
てのタスクのすべての仕事の処理実行がその期限以内に
終了することができるか否かを各時刻における各タスク
の仕事の所要時間を表す必要処理量情報を基に判定する
タスク処理実行可能性判定方法であって、各タスクの発
生周期情報または発生周期情報と処理期限情報を使用し
て、スケジュール試験時刻集合を求め、各タスクの必要
処理量情報を基に前記スケジュール試験時刻集合の各要
素を比較し、該スケジュール試験時刻集合に属する他の
時刻における必要処理量情報の合計結果からその時刻に
おける必要処理量情報合計結果が誘導される場合、その
時刻を前記スケジュール試験時刻集合から取り除いて、
縮小スケジュール試験時刻集合を求め、このようにして
求めた前記縮小スケジュール試験時刻集合の各時刻ｔに
ついてのみ、その時刻までに発生した各タスクの仕事の
必要処理量情報の合計がｔ以下であるか否かを調べ、こ
の結果に基づいてすべてのタスクのすべての仕事がその
期限以内に終了することができるか否かを判定すること
を要旨とする。
め、本発明のタスク処理実行可能性判定方法は、ある周
期で処理すべき仕事が発生し、それらの処理に期限が存
在するという性質を有するタスクが複数存在し、該複数
のタスクに対してRate Monotonic法またはInverse Dead
line法と呼ばれる手法でどの時刻にどのタスクを実行す
るかを決定するというスケジュールを行った場合にすべ
てのタスクのすべての仕事の処理実行がその期限以内に
終了することができるか否かを各時刻における各タスク
の仕事の所要時間を表す必要処理量情報を基に判定する
タスク処理実行可能性判定方法であって、各タスクの発
生周期情報または発生周期情報と処理期限情報を使用し
て、スケジュール試験時刻集合を求め、各タスクの必要
処理量情報を基に前記スケジュール試験時刻集合の各要
素を比較し、該スケジュール試験時刻集合に属する他の
時刻における必要処理量情報の合計結果からその時刻に
おける必要処理量情報合計結果が誘導される場合、その
時刻を前記スケジュール試験時刻集合から取り除いて、
縮小スケジュール試験時刻集合を求め、このようにして
求めた前記縮小スケジュール試験時刻集合の各時刻ｔに
ついてのみ、その時刻までに発生した各タスクの仕事の
必要処理量情報の合計がｔ以下であるか否かを調べ、こ
の結果に基づいてすべてのタスクのすべての仕事がその
期限以内に終了することができるか否かを判定すること
を要旨とする。
【００１２】
【作用】本発明のタスク処理実行可能性判定方法では、
各タスクの必要処理量情報を基にスケジュール試験時刻
集合の各要素を比較し、スケジュール試験時刻集合に属
する他の時刻における必要処理量情報の合計結果からそ
の時刻における必要処理量情報合計結果が誘導される時
刻を取り除いて、縮小スケジュール試験時刻集合を求
め、該縮小スケジュール試験時刻集合の各時刻ｔについ
てのみ、その時刻までに発生した各タスクの仕事の必要
処理量情報の合計がｔ以下であるか否かを調べて、すべ
てのタスクのすべての仕事がその期限以内に終了するこ
とができるか否かを判定する。
各タスクの必要処理量情報を基にスケジュール試験時刻
集合の各要素を比較し、スケジュール試験時刻集合に属
する他の時刻における必要処理量情報の合計結果からそ
の時刻における必要処理量情報合計結果が誘導される時
刻を取り除いて、縮小スケジュール試験時刻集合を求
め、該縮小スケジュール試験時刻集合の各時刻ｔについ
てのみ、その時刻までに発生した各タスクの仕事の必要
処理量情報の合計がｔ以下であるか否かを調べて、すべ
てのタスクのすべての仕事がその期限以内に終了するこ
とができるか否かを判定する。
【００１３】
【実施例】以下、図面を用いて本発明の実施例を説明す
る。
る。
【００１４】図１は、本発明の一実施例に係るタスク処
理実行可能性判定方法の判定アルゴリズムの流れを示す
フローチャートである。同図においては、まず変数ｉを
１に設定し（ステップＳ１１）、それから上述した従来
の技術において説明したように、複数のタスクτ1 ，τ
2 ，…，τn において、各タスクτi の発生周期情報ｐ
i または発生周期情報ｐi と処理期限情報ｄi を使用し
て、スケジュール試験時刻集合Ｓi を求める（ステップ
Ｓ１２）。
理実行可能性判定方法の判定アルゴリズムの流れを示す
フローチャートである。同図においては、まず変数ｉを
１に設定し（ステップＳ１１）、それから上述した従来
の技術において説明したように、複数のタスクτ1 ，τ
2 ，…，τn において、各タスクτi の発生周期情報ｐ
i または発生周期情報ｐi と処理期限情報ｄi を使用し
て、スケジュール試験時刻集合Ｓi を求める（ステップ
Ｓ１２）。
【００１５】それから、このようにして求めたスケジュ
ール試験時刻集合Ｓi の各要素を比較試験することによ
り、スケジュール試験時刻集合Ｓi に属する他の時刻に
おける必要処理量情報ｃi の合計結果からその時刻にお
ける必要処理量情報ｃi の合計結果が誘導されるか否か
をチェックし、誘導される場合には、その時刻をスケジ
ュール試験時刻集合Ｓi から取り除くことにより試験す
る必要のある時刻を減らした縮小スケジュール試験時刻
集合Ｒi を求める（ステップＳ１３）。
ール試験時刻集合Ｓi の各要素を比較試験することによ
り、スケジュール試験時刻集合Ｓi に属する他の時刻に
おける必要処理量情報ｃi の合計結果からその時刻にお
ける必要処理量情報ｃi の合計結果が誘導されるか否か
をチェックし、誘導される場合には、その時刻をスケジ
ュール試験時刻集合Ｓi から取り除くことにより試験す
る必要のある時刻を減らした縮小スケジュール試験時刻
集合Ｒi を求める（ステップＳ１３）。
【００１６】更に詳しくは、前記縮小スケジュール試験
時刻集合Ｒi は、次のようにして求められる。まず、ス
ケジュール試験時刻集合Ｓi の要素を昇順にソートす
る。そして、隣接した要素ｔ，ｔ′（ｔ＜ｔ′）におい
て、以下の試験を行う。ここで、ｔにおいてタスク
τi1，τi2，…，τikの仕事が同時に新たに発生し、ｔ
とｔ′の間では新たな仕事が発生することがないものと
する。
時刻集合Ｒi は、次のようにして求められる。まず、ス
ケジュール試験時刻集合Ｓi の要素を昇順にソートす
る。そして、隣接した要素ｔ，ｔ′（ｔ＜ｔ′）におい
て、以下の試験を行う。ここで、ｔにおいてタスク
τi1，τi2，…，τikの仕事が同時に新たに発生し、ｔ
とｔ′の間では新たな仕事が発生することがないものと
する。
【００１７】このとき、以下の２つの規則を用いてＳi
から要素を取り除く。 （１）ｔ′−ｔ≦ｃi1＋ｃi2＋…＋ｃikが成立する場合
には、ｔ′をＳi から取り除く。 （２）ｔ′−ｔ＞ｃi1＋ｃi2＋…＋ｃikが成立する場合
には、ｔをＳi から取り除く。 前者（１）のルールについては、もし時刻ｔ′におい
て、ｔ′までに発生した、タスクτ1 ，τ2 ，…，τi
の仕事の必要処理量情報の総合計がｔ′以下である場合
には、必ずｔにおいても、タスクτ1 ，τ2 ，…，τi
の仕事の必要処理量情報の総合計がｔ以下となるためで
ある。
から要素を取り除く。 （１）ｔ′−ｔ≦ｃi1＋ｃi2＋…＋ｃikが成立する場合
には、ｔ′をＳi から取り除く。 （２）ｔ′−ｔ＞ｃi1＋ｃi2＋…＋ｃikが成立する場合
には、ｔをＳi から取り除く。 前者（１）のルールについては、もし時刻ｔ′におい
て、ｔ′までに発生した、タスクτ1 ，τ2 ，…，τi
の仕事の必要処理量情報の総合計がｔ′以下である場合
には、必ずｔにおいても、タスクτ1 ，τ2 ，…，τi
の仕事の必要処理量情報の総合計がｔ以下となるためで
ある。
【００１８】後者（２）のルールについては、もし時刻
ｔにおいて、ｔまでに発生した、タスクτ1 ，τ2 ，
…，τi の仕事の必要処理量情報の総合計がｔ以下であ
る場合には、必ずｔ′においても、タスクτ1 ，τ2 ，
…，τi の仕事の必要処理量情報の総合計がｔ′以下と
なるためである。
ｔにおいて、ｔまでに発生した、タスクτ1 ，τ2 ，
…，τi の仕事の必要処理量情報の総合計がｔ以下であ
る場合には、必ずｔ′においても、タスクτ1 ，τ2 ，
…，τi の仕事の必要処理量情報の総合計がｔ′以下と
なるためである。
【００１９】上述したルールを用いることにより、スケ
ジュール試験時刻集合Ｓi からいくつかの時刻、すなわ
ち試験する必要のあるいくつかの時刻を取り除いた縮小
スケジュール試験時刻集合Ｒi を求めることができる
（ステップＳ１３）。
ジュール試験時刻集合Ｓi からいくつかの時刻、すなわ
ち試験する必要のあるいくつかの時刻を取り除いた縮小
スケジュール試験時刻集合Ｒi を求めることができる
（ステップＳ１３）。
【００２０】そして、このようにして求めた縮小スケジ
ュール試験時刻集合Ｒi の中から１つの要素ｔを取り除
く（ステップＳ１４）。それから、時刻ｔにおけるタス
クτ1 ，τ2 ，…，τi の仕事の必要処理量情報ｃi の
合計をＬとして算出する（ステップＳ１５）。この合計
値Ｌが時刻ｔより小さいか否かを比較する（ステップＳ
１６）。
ュール試験時刻集合Ｒi の中から１つの要素ｔを取り除
く（ステップＳ１４）。それから、時刻ｔにおけるタス
クτ1 ，τ2 ，…，τi の仕事の必要処理量情報ｃi の
合計をＬとして算出する（ステップＳ１５）。この合計
値Ｌが時刻ｔより小さいか否かを比較する（ステップＳ
１６）。
【００２１】ステップＳ１６における比較の結果、Ｌが
ｔより小さい場合には、前記変数ｉを＋１インクリメン
トし（ステップＳ１７）、該変数ｉがｎより大きくなる
までステップＳ１２〜Ｓ１７の処理を繰り返し（ステッ
プＳ１８）、変数ｉがｎより大きくなると、すべてのタ
スクのすべての仕事の処理実行がその期限以内に終了す
ることができると判定し（ステップＳ１９）、処理を終
了する。
ｔより小さい場合には、前記変数ｉを＋１インクリメン
トし（ステップＳ１７）、該変数ｉがｎより大きくなる
までステップＳ１２〜Ｓ１７の処理を繰り返し（ステッ
プＳ１８）、変数ｉがｎより大きくなると、すべてのタ
スクのすべての仕事の処理実行がその期限以内に終了す
ることができると判定し（ステップＳ１９）、処理を終
了する。
【００２２】また、前記ステップＳ１６において、Ｌが
ｔよりも小さくない場合には、ステップＳ２０に進ん
で、縮小スケジュール試験時刻集合Ｒi が空であるか否
かをチェックする。そして、空でない場合には、ステッ
プＳ１４に戻って、同じ処理を繰り返すが、空である場
合には、すべてのタスクのすべての仕事の処理実行がそ
の期限以内に終了することができないと判定し（ステッ
プＳ２１）、処理を終了する。
ｔよりも小さくない場合には、ステップＳ２０に進ん
で、縮小スケジュール試験時刻集合Ｒi が空であるか否
かをチェックする。そして、空でない場合には、ステッ
プＳ１４に戻って、同じ処理を繰り返すが、空である場
合には、すべてのタスクのすべての仕事の処理実行がそ
の期限以内に終了することができないと判定し（ステッ
プＳ２１）、処理を終了する。
【００２３】上述したように、スケジュール試験時刻集
合Ｓi からいくつかの時刻を取り除いた縮小スケジュー
ル試験時刻集合Ｒi を求め、この縮小スケジュール試験
時刻集合Ｒi においてのみ、その時点での必要処理量情
報に基づく判定を行うことにより、判定を行う時刻集合
が小さくなり、すべてのタスクのすべての仕事の処理実
行がその期限以内に終了することができるか否かの判定
を高速に行うことができる。
合Ｓi からいくつかの時刻を取り除いた縮小スケジュー
ル試験時刻集合Ｒi を求め、この縮小スケジュール試験
時刻集合Ｒi においてのみ、その時点での必要処理量情
報に基づく判定を行うことにより、判定を行う時刻集合
が小さくなり、すべてのタスクのすべての仕事の処理実
行がその期限以内に終了することができるか否かの判定
を高速に行うことができる。
【００２４】
【発明の効果】以上説明したように、本発明によれば、
各タスクの必要処理量情報を基にスケジュール試験時刻
集合の各要素を比較し、スケジュール試験時刻集合に属
する他の時刻における必要処理量情報の合計結果からそ
の時刻における必要処理量情報合計結果が誘導される時
刻を取り除いて、縮小スケジュール試験時刻集合を求
め、該縮小スケジュール試験時刻集合の各時刻ｔについ
てのみ、その時刻までに発生した各タスクの仕事の必要
処理量情報の合計がｔ以下であるか否かを調べて、すべ
てのタスクのすべての仕事がその期限以内に終了するこ
とができるか否かを判定するので、スケジュール試験時
刻集合における試験の必要のある時刻を低減することが
でき、計算量が少なくなり、判定処理を高速化すること
ができる。
各タスクの必要処理量情報を基にスケジュール試験時刻
集合の各要素を比較し、スケジュール試験時刻集合に属
する他の時刻における必要処理量情報の合計結果からそ
の時刻における必要処理量情報合計結果が誘導される時
刻を取り除いて、縮小スケジュール試験時刻集合を求
め、該縮小スケジュール試験時刻集合の各時刻ｔについ
てのみ、その時刻までに発生した各タスクの仕事の必要
処理量情報の合計がｔ以下であるか否かを調べて、すべ
てのタスクのすべての仕事がその期限以内に終了するこ
とができるか否かを判定するので、スケジュール試験時
刻集合における試験の必要のある時刻を低減することが
でき、計算量が少なくなり、判定処理を高速化すること
ができる。
【図１】本発明の一実施例に係るタスク処理実行可能性
判定方法の判定アルゴリズムの流れを示すフローチャー
トである。
判定方法の判定アルゴリズムの流れを示すフローチャー
トである。
【図２】従来のタスク処理実行可能性判定方法の判定ア
ルゴリズムの流れを示すフローチャートである。
ルゴリズムの流れを示すフローチャートである。
Claims (1)
- 【請求項１】 ある周期で処理すべき仕事が発生し、そ
れらの処理に期限が存在するという性質を有するタスク
が複数存在し、該複数のタスクに対してRateMonotonic
法またはInverse Deadline法と呼ばれる手法でどの時刻
にどのタスクを実行するかを決定するというスケジュー
ルを行った場合にすべてのタスクのすべての仕事の処理
実行がその期限以内に終了することができるか否かを各
時刻における各タスクの仕事の所要時間を表す必要処理
量情報を基に判定するタスク処理実行可能性判定方法で
あって、 各タスクの発生周期情報または発生周期情報と処理期限
情報を使用して、スケジュール試験時刻集合を求め、 各タスクの必要処理量情報を基に前記スケジュール試験
時刻集合の各要素を比較し、該スケジュール試験時刻集
合に属する他の時刻における必要処理量情報の合計結果
からその時刻における必要処理量情報合計結果が誘導さ
れる場合、その時刻を前記スケジュール試験時刻集合か
ら取り除いて、縮小スケジュール試験時刻集合を求め、 このようにして求めた前記縮小スケジュール試験時刻集
合の各時刻ｔについてのみ、その時刻までに発生した各
タスクの仕事の必要処理量情報の合計がｔ以下であるか
否かを調べ、この結果に基づいてすべてのタスクのすべ
ての仕事がその期限以内に終了することができるか否か
を判定することを特徴とするタスク処理実行可能性判定
方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP241695A JPH08190489A (ja) | 1995-01-11 | 1995-01-11 | タスク処理実行可能性判定方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP241695A JPH08190489A (ja) | 1995-01-11 | 1995-01-11 | タスク処理実行可能性判定方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH08190489A true JPH08190489A (ja) | 1996-07-23 |
Family
ID=11528653
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP241695A Pending JPH08190489A (ja) | 1995-01-11 | 1995-01-11 | タスク処理実行可能性判定方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH08190489A (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7711613B2 (en) | 2001-12-25 | 2010-05-04 | Ricoh Company, Ltd. | System and method, and computer program for managing product reserve |
| US7788318B2 (en) | 2002-10-15 | 2010-08-31 | Ricoh Company, Ltd. | Printing management system and electronic file printing method |
| US8027049B2 (en) | 2001-12-04 | 2011-09-27 | Ricoh Company, Ltd. | Remote e-mail printing |
-
1995
- 1995-01-11 JP JP241695A patent/JPH08190489A/ja active Pending
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8027049B2 (en) | 2001-12-04 | 2011-09-27 | Ricoh Company, Ltd. | Remote e-mail printing |
| US7711613B2 (en) | 2001-12-25 | 2010-05-04 | Ricoh Company, Ltd. | System and method, and computer program for managing product reserve |
| US7788318B2 (en) | 2002-10-15 | 2010-08-31 | Ricoh Company, Ltd. | Printing management system and electronic file printing method |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Lawrence et al. | Heuristic, optimal, static, and dynamic schedules when processing times are uncertain | |
| Potts et al. | An algorithm for single machine sequencing with deadlines to minimize total weighted completion time | |
| JP2002342097A (ja) | タスク割当可能時間決定装置及びタスク割当可能時間決定方法 | |
| Yang | Single machine rescheduling with new jobs arrivals and processing time compression | |
| CN112508398A (zh) | 基于深度强化学习的动态生产调度方法、装置及电子设备 | |
| CN107193655B (zh) | 一种基于效用函数的面向大数据处理的公平资源调度方法 | |
| JPH08190489A (ja) | タスク処理実行可能性判定方法 | |
| JPH1196222A (ja) | 工程進捗管理方法および工程管理装置 | |
| US20050050541A1 (en) | Method of and apparatus for task control, and computer product | |
| EP1672578A1 (en) | Method and system for analyzing the risk of a project | |
| CN119784045A (zh) | 一种基于建筑工程模型进行施工调度的方法 | |
| JPH05324358A (ja) | 性能予測装置 | |
| Madureira et al. | A genetic approach for dynamic job-shop scheduling problems | |
| JP3772713B2 (ja) | プライオリティ動的制御方式、プライオリティ動的制御方法およびプライオリティ動的制御用プログラム | |
| JP4385263B2 (ja) | ジョブスケジューリング装置およびジョブスケジューリング方法 | |
| CN108445856A (zh) | 梁片生产工序监控方法、装置、管理系统及储存介质 | |
| CN110308988A (zh) | 一种应用于异构计算平台的动态调度方法及系统 | |
| JPH06119205A (ja) | ソフトウェアの品質分析装置およびその高品質化支援装置 | |
| Aida et al. | Performance enhancement of scheduling algorithm in heterogeneous distributed computing systems | |
| CN115904705B (zh) | 一种多处理器限制性抢占最优调度方法 | |
| JP2000132535A (ja) | 最適パラメータ組合せ予測方法、およびそのプログラムを記録した記録媒体と装置 | |
| Van den Akker et al. | Minimizing the number of late jobs in case of stochastic processing times with minimum succes probabilities | |
| CN118863385B (zh) | 一种车间生产进度控制方法及系统 | |
| Müller | Scheduling flexible job shops under workforce constraints | |
| Ouchene et al. | Permutation in shop scheduling problems with FIFO considerations |