(57)【要約】【課題】  一つのタスクに割り当てられた優先順位が時間の経過によって変化しないようにして、優先順位の再割当によって発生する実行時間のオーバーヘッドを除去することで、実行時間のオーバーヘッドを最小化し得るＥＤＦスケジューリング方法を提供しようとする。【解決手段】  スケジューリングするタスクの数をチェックして、各タスクに優先順位を割り当てて、現在時間を最も低い優先順位に更新して、該更新された最も低い優先順位から、時間軸上、締切時間に最も近いタスクを最初に処理することで、ＥＤＦスケジューリングを行う。【選択図】  図１
2005044326.tif 000002
【特許請求の範囲】
【請求項１】
スケジューリングすべきタスクの数をチェックして、
各タスクに優先順位を割り当てて、
現在時間を最も低い優先順位に更新して、
該更新された最も低い優先順位から、時間軸上、締切時間に最も近いタスクを最初に処理することを特徴とするＥＤＦスケジューリング方法。
【請求項２】
スケジューリングするタスクの数が優先順位水準の数より少ないか否かを更に判断することを特徴とする請求項１記載のＥＤＦスケジューリング方法。
【請求項３】
優先順位水準の数は、２ｋ個であることを特徴とする請求項２記載のＥＤＦスケジューリング方法。
【請求項４】
タスクの数が優先順位水準の数より少ないとき、各タスクの優先順位は、該当のタスクの締切時限（ｄｉ）を最大締切時限（Ｔｍａｘ）で割った後、残りの数を特定時間単位（ｑ）で割った値により決定されることを特徴とする請求項２〜３記載のＥＤＦスケジューリング方法。
【請求項５】
前記最大締切時限は、各タスク中、最も長い周期を有するタスクの相対締切時限であることを特徴とする請求項４記載のＥＤＦスケジューリング方法。
【請求項６】
前記特定時間単位（ｑ）は、前記最大締切時限を優先順位水準の数で割って得られた値であることを特徴とする請求項４記載のＥＤＦスケジューリング方法。
【請求項７】
現在時間は、現在時間指示針により指示されることを特徴とする請求項１〜４中何れか一つに記載のＥＤＦスケジューリング方法。
【請求項８】
前記現在時間指示針は、システムの現在時間を前記最大締切時限で割った後、残りの数を前記特定時間単位（ｑ）で割って得られた値であること特徴とする請求項１〜７中何れか一つに記載のＥＤＦスケジューリング方法。
【請求項９】
タスクの数が優先順位水準の数より少ないとき、各タスクの優先順位（Ｐｉ）は、式
【数１】
2005044326.tif 000022
により決定され、このとき、ｄｉは該当タスクの締切時限、Ｔｍａｘは最大締切時限、ｑは特定時間単位をそれぞれ示すことを特徴とする請求項２〜３記載のＥＤＦスケジューリング方法。
【請求項１０】
前記Ｔｍａｘは、各タスク中、最も長い周期を有するタスクの相対締切時限であることを特徴とする請求項９記載のＥＤＦスケジューリング方法。
【請求項１１】
前記特定時間単位（ｑ）は、式
【数２】
2005044326.tif 000023
により計算されることを特徴とする請求項９〜１０記載のＥＤＦスケジューリング方法。
【請求項１２】
現在時間は、式
【数３】
2005044326.tif 000024
により更新され、ｃｕｒｒｅｎｔ＿ｔｉｍｅは、システムの現在時間であることを特徴とする請求項１１記載のＥＤＦスケジューリング方法。
【請求項１３】
タスクの数が優先順位水準の数より多いとき、各タスクをいくつかのタスクセットにグループ化することを特徴とする請求項２〜３記載のＥＤＦスケジューリング方法。
【請求項１４】
各タスクセットに一つの現在時間指示針を設定することを特徴とする請求項１３記載のＥＤＦスケジューリング方法。
【請求項１５】
締切時限が２ｍ−１Ｔｍｉｎより大きく、２ｍＴｍｉｎより小さいタスクの優先順位（Ｐｉ）は、式
【数４】
2005044326.tif 000025
により求められ、このとき、ｑ（ｍ）はｍ番目の現在時間指示針と関連された時間単位で、ｘは各現在時間指示針と関連された優先順位水準の数、ｄｉは該当タスクの締切時限をそれぞれ示すことを特徴とする請求項１４記載のＥＤＦスケジューリング方法。
【請求項１６】
現在時間指示針の数は、
【数５】
2005044326.tif 000026
個であることを特徴とする請求項１５記載のＥＤＦスケジューリング方法。
【請求項１７】
ｍ番目の現在時間指示針の値Ｃ（ｍ）は、式
【数６】
2005044326.tif 000027
により更新されることを特徴とする請求項１６記載のＥＤＦスケジューリング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、実時間スケジューリングに係るもので、詳しくは、優先順位（ｐｒｉｏｒｉｔｙ）の割当を常数時間複雑度により行うＥＤＦスケジューリング方法に関するものである。
【背景技術】
【０００２】
最近、コンピュータ及びコンピュータネットワークシステム技術の急成長に伴い、多様な実時間マルチメディアアプリケーションが登場しているが、このような実時間アプリケーションが益々精巧且つ複雑になることによって、システムの性能及び信頼性を増進するための実時間スケジューリングに対する研究が大いに進行されている。
【０００３】
且つ、このような各実時間スケジューリング技法中、ＲＥ（Ｒａｔｅ  Ｍｏｎｏｔｏｎｉｃ）及びＥＤＦ（Ｅａｒｌｉｅｓｔ  Ｄｅａｄｌｉｎｅ  Ｆｉｒｓｔ）アルゴリズムがマルチメディアスケジューリングに適合したものと評価されている。
【０００４】
特に、ＥＤＦアルゴリズムは、システムの活用度が１００％という点で最適のスケジューリングアルゴリズムとして認定されているが、具現の煩雑性及び一時的な過負荷時の不安定性があるため、ＲＭのような固定優先順位アルゴリズムがより頻繁に使用されている。
【０００５】
図３及び図４は、従来のＲＭ及びＥＤＦスケジューリングの説明図で、図示されたように、従来の相互異なる周期（ｐｅｒｉｏｄ）及び遂行時間を有する三つのタスクＴ１、Ｔ２、Ｔ３がＲＭ及びＥＤＦアルゴリズムにより夫々スケジューリングされる過程が示されている。
【０００６】
即ち、ＲＭスケジューリングの場合、各タスクには、周期が短いほど高い優先順位が割り当てられるが、図３の周期が５のタスクＴ１には最も高い優先順位Ｈ、周期が７のタスクＴ２には中間優先順位Ｍ、且つ、周期が１５のタスクＴ３には最も低い優先順位Ｌがそれぞれ割り当てられ、一旦各タスクに優先順位が割り当てられると、時間が経過しても変更されない。
【０００７】
その反面、ＥＤＦスケジューリングの場合、各タスクの優先順位は各タスクのデッドライン（ｄｅａｄｌｉｎｅ）により決定され、現在時間でデッドラインに最も近いタスクに最も高い優先順位が割り当てられる。よって、図４に示したように、時間０のとき、デッドラインまでの時間が５のタスクＴ１には最も高い優先順位Ｈ、デッドラインまでの時間が７のタスクＴ２には中間優先順位Ｍ、且つ、デッドラインまでの時間が１５のタスクＴ３には最も低い優先順位Ｌがそれぞれ割り当てられる。然し、時間９に至ると、タスクＴ１及びタスクＴ３のデッドラインまで残った時間が６になり、タスクＴ２のデッドラインまで残った時間が５になって優先順位が変更される。
【０００８】
このようなＥＤＦスケジューリングを支援する運営体制は、一般的にリスト構造又はヒープ（Ｈｅａｐ）形態のデータ構造が使用され、この場合、システムのタスク数又はメッセージ数がＮであると、スケジューラが次にスケジューリングされるタスク又はメッセージを選択するために線形時間Ｏ（Ｎ）を要求する。
【０００９】
然し、予測可能な遂行時間が要求され、余裕時間があまりない実時間ネットワークや実時間内蔵型システムでは、線形時間複雑度のスケジューラを好まず、常数時間にスケジューリングされることが要求される。
【００１０】
従って、これを改善したＥＤＦにおける優先順位割当方法が非特許文献１に開示され、その優先順位割当方法は、現在時間を基準にして現在のタスク又はメッセージの締切時間をそれぞれログスケール（ｌｏｇａｒｉｔｈｍｉｃ  ｓｃａｌｅ）に変換し、これを利用して優先順位を割り当てるようになっている。且つ、このようなメッシュの優先順位割当方法では、新しいタスク又はメッセージが追加されないと、新しい優先順位割当が必要でないため、スケジュールは常数時間に行われる。
【非特許文献１】Ａ．Ｍｅｓｈ  ｅｔ．ａｌ、”Ｅａｒｌｉｅｓｔ  Ｄｅａｄｌｉｎｅ  Ｍｅｓｓａｇｅ  Ｓｃｈｅｄｕｌｉｎｇ  ｗｉｔｈ  Ｌｉｍｉｔｅｄ  Ｐｒｉｏｒｉｔｙ  Ｉｎｖｅｒｓｉｏｎ”
【発明の開示】
【発明が解決しようとする課題】
【００１１】
然るに、このような従来のメッシュの優先順位割当方法においては、マルチメディア等の動的システムのように、使用者の要求による動的タスクの生成／消滅が頻繁な環境では、依然として線形時間複雑度を有するという不都合な点があった。
【００１２】
本発明は、このような従来の課題に鑑みてなされたもので、一つのタスクに割り当てられた優先順位が時間の経過によって変化しないようにして、優先順位の再割当によって発生する実行時間のオーバーヘッドを除去することで、実行時間のオーバーヘッドを最小化し得るＥＤＦスケジューリング方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
このような目的を達成するため、本発明に係るＥＤＦスケジューリング方法の第１実施形態においては、スケジューリングするタスクの数をチェックして、各タスクに優先順位を割り当てて、現在時間を最も低い優先順位に更新して、該更新された最も低い優先順位から、時間軸（ｔｅｍｐｏｒａｌ  ａｘｉｓ）上、締切時間に最も近いタスクを最初に処理する。
【００１４】
次いで、スケジューリングするタスクの数が優先順位水準（ｐｒｉｏｒｉｔｙ  ｌｅｖｅｌ）の数（２ｋ）より少ないか否かを判断して、タスクの数が優先順位水準の数より少ないとき、各タスクの優先順位は、該当タスクの締切時限（ｄｉ）を最大締切時限（Ｔｍａｘ）で割った後、残りの数を特定時間単位（ｑ）で割った値により決定される。このとき、前記最大締切時限は、各タスク中、最も長い周期を有するタスクの相対締切時限で、前記特定時間単位は、前記最大締切時限を優先順位水準の数で割って得られた値である。
【００１５】
且つ、前記現在時間は、システムの現在時間を前記最大締切時限で割った後、残りの数を前記特定時間単位で割って得られた値であって、現在時間指示針により指示される。
【００１６】
又、本発明に係るＥＤＦスケジューリング方法の第２実施形態においては、前記タスクの数が優先順位水準の数より多いとき、各タスクが複数のタスクセットにグループ化され、それらタスクセットに一つの現在時間指示針が設定される。
【００１７】
即ち、締切時限が２ｍ−１Ｔｍｉｎより大きく、２ｍＴｍｉｎより小さいタスクの優先順位（Ｐｉ）は、式
【００１８】
【数７】
2005044326.tif 000003
により求められ、このとき、ｑ（ｍ）はｍ番目の現在時間指示針と関連された時間単位、ｘは各現在時間指示針と関連された優先順位水準の数、ｄｉは、該当タスクの締切時限をそれぞれ示したものである。又、現在時間指示針の数は
【００１９】
【数８】
2005044326.tif 000004
個である。
【００２０】
又、ｍ番目の現在時間指示針の値Ｃ（ｍ）は、式
【００２１】
【数９】
2005044326.tif 000005
により更新される。
【００２２】
尚、本発明に係るＥＤＦスケジューリング方法は、優先順位水準が充分な場合及び優先順位水準が充分でなく有限である場合の優先順位割当方法と、このようなＥＤＦスケジューリング方法を適用した場合のスケジュール可能性（ｓｃａｄｕｌａｂｉｌｉｔｙ）検査方法と、を含んだものである。
【００２３】
本発明によるＥＤＦスケジューリング方法は、スケジューリングすべきタスクの数をチェックして、各タスクに優先順位を割り当てて、現在時間を最も低い優先順位に更新して、該更新された最も低い優先順位から、時間軸上、締切時間に最も近いタスクを最初に処理することを特徴とし、それにより上記目的を達成する。
【００２４】
スケジューリングするタスクの数が優先順位水準の数より少ないか否かを更に判断することを特徴としてもよい。
【００２５】
優先順位水準の数は、２ｋ個であることを特徴としてもよい。
【００２６】
タスクの数が優先順位水準の数より少ないとき、各タスクの優先順位は、該当のタスクの締切時限（ｄｉ）を最大締切時限（Ｔｍａｘ）で割った後、残りの数を特定時間単位（ｑ）で割った値により決定されることを特徴としてもよい。
【００２７】
前記最大締切時限は、各タスク中、最も長い周期を有するタスクの相対締切時限であることを特徴としてもよい。
【００２８】
前記特定時間単位（ｑ）は、前記最大締切時限を優先順位水準の数で割って得られた値であることを特徴としてもよい。
【００２９】
現在時間は、現在時間指示針により指示されることを特徴としてもよい。
【００３０】
前記現在時間指示針は、システムの現在時間を前記最大締切時限で割った後、残りの数を前記特定時間単位（ｑ）で割って得られた値であること特徴としてもよい。
【００３１】
タスクの数が優先順位水準の数より少ないとき、各タスクの優先順位（Ｐｉ）は、式
【００３２】
【数１０】
2005044326.tif 000006
により決定され、このとき、ｄｉは該当タスクの締切時限、Ｔｍａｘは最大締切時限、ｑは特定時間単位をそれぞれ示すことを特徴としてもよい。
【００３３】
前記Ｔｍａｘは、各タスク中、最も長い周期を有するタスクの相対締切時限であることを特徴としてもよい。
【００３４】
前記特定時間単位（ｑ）は、式
【００３５】
【数１１】
2005044326.tif 000007
により計算されることを特徴としてもよい。
【００３６】
現在時間は、式
【００３７】
【数１２】
2005044326.tif 000008
により更新され、ｃｕｒｒｅｎｔ＿ｔｉｍｅは、システムの現在時間であることを特徴としてもよい。
【００３８】
タスクの数が優先順位水準の数より多いとき、各タスクをいくつかのタスクセットにグループ化することを特徴としてもよい。
【００３９】
各タスクセットに一つの現在時間指示針を設定することを特徴としてもよい。
【００４０】
締切時限が２ｍ−１Ｔｍｉｎより大きく、２ｍＴｍｉｎより小さいタスクの優先順位（Ｐｉ）は、式
【００４１】
【数１３】
2005044326.tif 000009
により求められ、このとき、ｑ（ｍ）はｍ番目の現在時間指示針と関連された時間単位で、ｘは各現在時間指示針と関連された優先順位水準の数、ｄｉは該当タスクの締切時限をそれぞれ示すことを特徴としてもよい。
【００４２】
現在時間指示針の数は、
【００４３】
【数１４】
2005044326.tif 000010
個であることを特徴としてもよい。
【００４４】
ｍ番目の現在時間指示針の値Ｃ（ｍ）は、式
【００４５】
【数１５】
2005044326.tif 000011
により更新されることを特徴としてもよい。
【発明の効果】
【００４６】
本発明に係るＥＤＦスケジューリング方法においては、現在時間に最も低い優先順位水準を指示する現在時間指示針を設定し、時計方向に該当のタスクをそれぞれ検索して、最も先に検索されるタスクを一番最初に処理することで、各タスクに割り当てられた優先順位を変更することなく、常数時間複雑度によりスケジューリングし得るという効果がある。
【００４７】
又、優先順位水準が充分でない場合、複数の現在時間指示針を設定して締切時限の範囲を拡張することで、システムの使用率を最大化し得るという効果がある。
【００４８】
又、一度割り当てられた優先順位が変更されないため、優先順位の再割当によって発生する実行時間のオーバーヘッドを最小化し得るという効果がある。
【００４９】
尚、本発明に係る”改善されたＥＤＦスケジューリング方法”は、前記実施形態に限定されることなく、本発明の技術思想が許容する範囲内で多様に変形して実施することができる。
【発明を実施するための最良の形態】
【００５０】
以下、本発明の実施の形態に対し、図面に基づいて説明する。
【００５１】
本発明では、時間軸（ｔｅｍｐｏｒａｌ  ａｘｉｓ）をクワンタム（ｑｕａｎｔｕｍ）単位に分割して、各タスクの優先順位及び現在時間指示針を計算してビットマップにマッピングし、前記現在時間指示針を周期的に更新して、各タスクの優先順位を再び割り当てる過程を省いて、現在時間指示針に対する相対的な優先順位により前記各タスクをスケジューリングする。
【００５２】
このとき、前記クワンタム（ｑ）は、スケジューリングされる各タスクの締切時間中、最も長い締切時限を優先順位水準の数（２ｋ）で割って計算することで、次式１により表現される。
【００５３】
【数１６】
2005044326.tif 000012
−−−−−−−−−−−−−−−−−−−−−−−−−−−＜式１＞
上式１中、Ｔｍａｘは最大締切時限、ｋは優先順位のために割り当てられたビット数をそれぞれ示したものである。
【００５４】
又、各タスクの優先順位（Ｐｉ）は、次式２により算出される。
【００５５】
【数１７】
2005044326.tif 000013
−−−−−−−−−−−−−−−−−−−−−−−−−−−＜式２＞
上式２中、ｄｉは該当のタスクの締切時限を示したものである。
【００５６】
又、前記現在時間指示針（Ｃ）は、システムの現在時間が更新される時毎に次式３により更新される。
【００５７】
【数１８】
2005044326.tif 000014
−−−−−−−−−−−−−−−−−−−−−−−−−−−＜式３＞
上式３中、ｃｕｒｒｅｎｔ＿ｔｉｍｅはシステムの現在時間を示したものである。
【００５８】
図１は本発明に係るＥＤＦスケジューリング方法に適用されるビットマップ構造を示した概念図で、前記式１及び式２によりスケジューリングされる各タスクの優先順位が決定されると、前記ビットマップに該当の優先順位ビットが設定され、前記現在時間指示針は前記式３により周期的に更新される。
【００５９】
以下、本発明に係るスケジューリング方法で３つのタスクＴ１、Ｔ２、Ｔ３がスケジューリングされる場合を、図２（Ａ）〜（Ｃ）に基づいて説明する。
【００６０】
図２（Ａ）〜（Ｃ）は、本発明のＥＤＦスケジューリング方法における時間の経過によって各タスクの優先順位が決定される過程の説明図で、図示されたように、本発明に係るＥＤＦスケジューリング方法においては、まず、図２（Ａ）に示したように、時間０で、周期が２のＴ１、周期が５のＴ２、周期が１５のＴ３がそれぞれスケジューラに到着すると、前記スケジューラは、式１及び式２により前記各タスクの優先順位を決定するが、時間０で、前記三つのタスク中、最大締切時限（Ｔｍａｘ）はＴ３の周期と同様な１３であるため、１３個の優先順位水準が存在し、Ｔ１、Ｔ２、Ｔ３の締切時限ｄ１、ｄ２、ｄ３は、式２によりそれぞれ２、５、０になり（ｄ１＝２、ｄ２＝５、ｄ３＝０）、現在時間指示針は式３により０になり、このとき、現在時間指示針が指示する時間の優先順位が最も低く、時計方向に行くほど優先順位は低くなる。
【００６１】
その後、時間が経過して時間１１に至ると、図２（Ｂ）に示したように、現在時間指示針は時間１１を指し、Ｔ１、Ｔ２、Ｔ３の相対締切時限は、前記式２によりそれぞれｄ１＝１、ｄ２＝４、ｄ３＝２になる。よって、各タスクは、時間１１でＴ１、Ｔ３、Ｔ２の順に処理される。
【００６２】
又、時間１２では、図２（Ｃ）に示したように、現在時間指示針は時間１２を指し、Ｔ１、Ｔ２、Ｔ３の相対締切時限は、前記式２によりそれぞれｄ１＝２、ｄ２＝３、ｄ３＝１になる。よって、前記各タスクは、時間１２でＴ３、Ｔ１、Ｔ２の順に処理される。
【００６３】
以上説明したように、本発明に係るＥＤＦスケジューリング方法は、正確にＥＤＦスケジューリングにおける優先順位設定方法に従うが、従来のＥＤＦスケジューリングのように、現在時間から各タスクの相対締切時限を算出して優先順位を再び割り当てることなく、現在時間に最も低い優先順位水準を指示する現在時間指示針を設定し、時計方向に該当タスクをそれぞれ検索して、最も先に検索されるタスクを一番最初に処理するため、優先順位の再割当による実行時間のオーバーヘッドを最小化することができる。
【００６４】
実際の状況では、優先順位水準の数は有限であるため、タスクの数が割り当てられる優先順位の数より多い場合もあるが、このとき、複数の現在時間指示針を適用して効率的にＥＤＦスケジューリングを行うことができる。
【００６５】
以下、本発明の第２実施形態として、スケジューリングされる各タスク中、最も短い締切時限をＴｍｉｎ、最も長い締切時限をＴｍａｘとしたとき、ｍ番目の現在時間指示針と関連されたクワンタムｑ（ｍ）を、次式４により求めることもできる。
【００６６】
【数１９】
2005044326.tif 000015
−−−−−−−−−−−−−−−−−−−−−−−−−−−＜式４＞
上式４中、ｘは各現在時間指示針と関連された優先順位水準の数を示したもので、次式５により求められる。
【００６７】
【数２０】
2005044326.tif 000016
−−−−−−−−−−−−−−−−−−−−−−−−−−−＜式５＞
上式５中、ｋは優先順位ビット数を示したものである。
【００６８】
又、締切時限が２ｍ−１Ｔｍｉｎより大きく、２ｍＴｍｉｎより小さいタスクの優先順位（Ｐｉ）は、次式６により求められる。
【００６９】
【数２１】
2005044326.tif 000017
−−−−−−−−−−−−−−−−−−−−−−−−−−−＜式６＞
このとき、現在時間指示針は
【００７０】
【数２２】
2005044326.tif 000018
個に維持され、システムの現在時間が更新される時、ｍ番目の現在時間指示針Ｃ（ｍ）は、次式７により更新される。
【００７１】
【数２３】
2005044326.tif 000019
−−−−−−−−−−−−−−−−−−−−−−−−−−−＜式７＞
本発明では、前記優先順位水準が充分な場合及び優先順位水準が充分でない場合のシステム使用率を算出して、スケジュール可能性をそれぞれ検査する。このとき、システム使用率とは、タスク又はメッセージの処理時間をその締切時限で割った値の総合をいう。
【００７２】
従って、優先順位ビット数がｋの場合は、システム使用率が
【００７３】
【数２４】
2005044326.tif 000020
より小さいか同様であるとスケジューリングが可能になり、ｋが充分でない場合は、システム使用率が
【００７４】
【数２５】
2005044326.tif 000021
より小さいか同様であるとスケジューリングが可能になる。
【００７５】
以上説明したように、本発明に係るＥＤＦスケジューリング方法においては、現在時間に最も低い優先順位水準を指示する現在時間指示針を設定し、時計方向に該当のタスクをそれぞれ検索して、最も先に検索されるタスクを一番最初に処理することで、各タスクに割り当てられた優先順位を変更することなく、常数時間複雑度によりスケジューリングし得るという効果がある。
【００７６】
又、優先順位水準が充分でない場合、複数の現在時間指示針を設定して締切時限の範囲を拡張することで、システムの使用率を最大化し得るという効果がある。
【００７７】
又、一度割り当てられた優先順位が変更されないため、優先順位の再割当によって発生する実行時間のオーバーヘッドを最小化し得るという効果がある。
【００７８】
尚、本発明に係る”改善されたＥＤＦスケジューリング方法”は、前記実施形態に限定されることなく、本発明の技術思想が許容する範囲内で多様に変形して実施することができる。
【００７９】
一つのタスクに割り当てられた優先順位が時間の経過によって変化しないようにして、優先順位の再割当によって発生する実行時間のオーバーヘッドを除去することで、実行時間のオーバーヘッドを最小化し得るＥＤＦスケジューリング方法を提供しようとする。
【００８０】
スケジューリングするタスクの数をチェックして、各タスクに優先順位を割り当てて、現在時間を最も低い優先順位に更新して、該更新された最も低い優先順位から、時間軸上、締切時間に最も近いタスクを最初に処理することで、ＥＤＦスケジューリングを行う。
【図面の簡単な説明】
【００８１】
【図１】本発明に係るＥＤＦスケジューリング方法に適用されるビットマップを示した構成図である。
【図２】（Ａ）〜（Ｃ）本発明に係るＥＤＦスケジューリング方法で三つのタスクがスケジューリングされる場合を示した説明図で、（Ａ）は時間０における各タスクの優先順位の説明図、（Ｂ）は時間１１における各タスクの優先順位の説明図、（Ｃ）は時間１２における各タスクの優先順位の説明図である。
【図３】従来のＲＭスケジューリングの説明図である。
【図４】従来のＥＤＦスケジューリングの説明図である。
【図１】
2005044326.tif 000028
【図２】
2005044326.tif 000029
【図３】
2005044326.tif 000030
【図４】
2005044326.tif 000031