(57)【特許請求の範囲】
【請求項１】
コンピュータ・システムにおいてプロセッサで実行されるべきタスクを容認するための方法であって、
（ａ）プロセッサの実行要求を少なくとも３つのタスクから受ける工程であって、該各タスクの第１の品質のパフォーマンスを提供する少なくとも第１のレベルのプロセッサ使用時間をそれぞれが有し、少なくとも２つのタスクが該各タスクの第２の品質のパフォーマンスを提供する第２のレベルのプロセッサ使用時間を要求する第２の使用レベルを有し、前記各タスクの前記第１のレベルは、前記各タスクの前記第２のレベルよりも前記プロセッサ使用時間が少なく、前記各タスクの前記第１の品質のパフォーマンスは、前記各タスクの前記第２の品質のパフォーマンスよりも優れる工程と、
（ｂ）第２の使用レベルの少なくとも１つのタスクを含む少なくとも２つのタスクであるが全てのタスクではないタスクを処理するために容認する工程であって、前記プロセッサの未使用時間が、第２の使用レベルでの容認を未だ受けなかったタスクの１つを容認するに不十分であり、かつそれぞれの第２の使用レベルの和が前記プロセッサに得ることができるトータル時間を超えないように、容認タスクを選択する工程と、
（ｃ）前記容認を未だ受けていないタスクを処理するための容認から排除する工程とを含む、方法。
【請求項２】
前記プロセッサの時間が許可された全てのタスクを第１の使用レベルで実行させるのに不十分であるとき、さらに、
（ｄ）第２の使用レベルで実行する容認タスクの少なくとも１つで前記容認タスクの実行を開始する工程と、
（ｅ）１以上の容認タスクが実行の要求を一時的に中止しかつ前記プロセッサが第２の使用レベルで実行しているタスクを第１の使用レベルで実行させるに十分な未使用時間を得ることができるとき、前記タスクを第１の使用レベルに切り換える工程とを含む、請求項１に記載の方法。
【請求項３】
さらに、
（ｄ）前記容認タスクの実行を開始する工程と、
（ｅ）以前に排除されたタスクが容認を再度要求しているとき、前記容認タスクの各第２の使用レベルの和が前記プロセッサに得ることができる時間を超えることなく以前の排除タスクを容認するのに十分に小さくならないかぎり、前記容認タスクを再度排除する工程とを含む、請求項１に記載の方法。
【請求項４】
前記少なくとも１つの容認タスクは、前記プロセッサ使用時間についての少なくとも３つのレベルを有する、請求項１に記載の方法。
【請求項５】
コンピュータ・システムにおいてプロセッサ時間をタスクに割り当てるべくプロセッサ資源分配機のための方法であって、
（ａ）プロセッサ時間の要求を２以上のタスクから受ける工程であって、少なくとも１つの要求は前記要求と関連するバイレベル・タスク(bi-level task)のために２以上のプロセッサ使用レベルを特定し、該２以上の各レベルはリアル・タイムの分配のためのサイクル持続期間により特定され、各サイクル期間のために各サイクルの一部を前記バイレベル・タスクに配分する工程と、
（ｂ）前記要求に基づいて前記２以上のタスクのそれぞれにプロセッサ時間を配分する工程であって、各サイクルの一部及び前記特定されたサイクル持続期間の１つを選択することにより前記バイレベル・タスクのためのプロセッサ時間を配分する工程とを含む、方法。
【請求項６】
前記２以上のレベルのそれぞれは前記バイレベル・タスクのためのコールバック機能と関連し、前記タスクは選択されかつ特定されたサイクル持続期間及び各サイクルの一部と関連するコールバック機能を使用することにより呼び出される、請求項５に記載の方法。
【請求項７】
前記選択は得られるプロセッサ時間量を基に行われ、選択されたレベルは得られるプロセッサ時間量内に調和し得る各サイクルの最大部分と関連するレベルである、請求項５に記載の方法。
【請求項８】
コンピュータ・システムにおいて少なくとも２つのタスク間でプロセッサの時間配分を調整するための方法であって、
（ａ）前記プロセッサの時間を一連の第１の期間に分割し、第１のタスクの前記プロセッサでの実行を開始し、各第１の期間の一部を前記第１のタスクに配分する工程と、
（ｂ）前記プロセッサ時間を前記一連の第１の期間と同じであるか又は異なる一連の第２の期間に分割し、前記各第２の期間中、前記プロセッサ使用時間についての第１のレベルで第２のタスクの前記プロセッサでの実行を開始し、各第２の期間の一部を第２のタスクに配分する工程であって、前記第２のタスクは、前記第２の期間中、前記第１のレベルに比べ少ないプロセッサ時間を使用するレベルであって前記第１のレベルに比べ低品質のパフォーマンスを提供する、前記プロセッサ使用時間についての前記第２のレベルでも実行することができる、工程と、
（ｃ）第１のタスクが配分されたプロセッサ時間に比べ期間において大きいプロセッサ時間を供給しているとき、第２のタスクを第２のレベルに切り換え、第１のタスクで利用可能にすべくプロセッサの時間の少なくとも一部を再配分する工程とを含む、方法。
【請求項９】
第２のタスクの第２のレベル使用への切り換えは、一連の第２の期間のそのときの各期間の終わりに発生し、引き続く期間のために効果を与える、請求項８に記載の方法。
【請求項１０】
第１のタスクが配分時間よりも期間において大きいプロセッサ時間を要求しているか否かの決定はタスクが前記期間に要求している時間の推定を基にした予測により行われ、切り換え及び再配分は第１のタスクが前記期間の配分時間を消費する前に行われる、請求項８に記載の方法。
【請求項１１】
第２のタスクの第２のレベル使用への切り換えは、前記一連の第２の期間のそのときの期間の終わりに発生し、引き続く期間のために効果をもたらす、請求項１０に記載の方法。
【請求項１２】
さらに、
（ｄ）工程（ｂ）及び（ｃ）間において、第１の品質のパフォーマンスを提供するレベルを有しかつ第１のレベルのプロセッサ使用時間を実行する第３のタスクのプロセッサでの実行を開始する工程であって、第３のタスクは前記第１のレベルより低いプロセッサ時間を使用するレベルであって前記第１のレベルより低品質のパフォーマンスを提供する第２のレベルのプロセッサ使用時間でも実行することができる、工程と、
（ｅ）工程（ｃ）において、第１のタスクが配分されたプロセッサ時間より大きい時間を要求している場合に、第３のタスクを第２のレベルの使用に切り換えるよりもむしろ第２のタスクを第２のレベルの使用に切り換える工程とを含む、請求項８に記載の方法。
【請求項１３】
コンピュータ・システムにおいてプロセッサの使用時間をタスクにより調整する方法であって、
（ａ）プロセッサの時間を一連の期間に分割する工程と、
（ｂ）第１の品質のパフォーマンスを提供する第１のレベルのプロセッサ使用時間で実行するタスクのプロセッサでの実行を開始する工程であって、前記タスクは前記第１のレベルより少ないプロセッサ時間を使用するレベルであって前記第１のレベルより低い品質のパフォーマンスを提供する第２のレベルのプロセッサ使用時間でも実行することができる、工程と、
（ｃ）前記各期間の一部を前記タスクに配分する工程と、
（ｄ）前記タスクが配分されたプロセッサ時間より期間内で大きいプロセッサ時間を要求しているとき、そのタスクを第２の使用レベルに切り換える工程とを含む、方法。
【請求項１４】
前記タスクは次の期間のために第２の使用レベルに切り替えられる、請求項１３に記載の方法。
【請求項１５】
前記タスクが配分されたプロセッサ時間より期間内で大きいプロセッサ時間を要求していることの決定は前記タスクが前記期間において要求している時間の推定に基づく予測により行われ、前記切り換えは前記タスクが前記期間において配分された時間を消費する前に行われる、請求項１３に記載の方法。
【請求項１６】
コンピュータ・システムにおいてプロセッサの使用時間をタスクにより調整する方法であって、
（ａ）プロセッサの時間を一連の期間に分割する工程と、
（ｂ）第１のレベルのプロセッサ使用時間で実行する第１のタスクのプロセッサでの実行を開始する工程であって、前記第１のタスクは前記第１のレベルより少ないプロセッサ時間を使用するレベルであって前記第１のレベルより低品質のパフォーマンスを提供する第２のレベルのプロセッサ使用時間でも実行することができる、工程と、
（ｃ）前記各期間の一部を前記第１のタスクに配分する工程と、
（ｄ）第１のレベルのプロセッサ使用時間で実行する第２のタスクのプロセッサでの実行を開始する工程であって、前記第２のタスクは前記第１のレベルより少ないプロセッサ時間を使用するレベルであって前記第１のレベルより低品質のパフォーマンスを提供する第２のレベルのプロセッサ使用時間でも実行することができる工程と、
（ｅ）第１のタスクが配分されたプロセッサ時間より期間において大きいプロセッサ時間を要求しているとき、第１のタスクを第２のレベル使用に切り換えるよりもむしろ第２のタスクを第２のレベルの使用に切り換える工程とを含む、方法。
【請求項１７】
コンピュータ・システムにおいて作動されたとき、プロセッサで実行されるべき容認タスクのための以下の方法をシステムに実行させるコンピュータ・プログラムを含む、コンピュータ読み取り可能の媒体であって、
（ａ）プロセッサの実行要求を少なくとも３つのタスクから受ける工程であって、該各タスクの第１の品質のパフォーマンスを提供する少なくとも第１のレベルのプロセッサ使用時間をそれぞれが有し、少なくとも２つのタスクが該各タスクの第２の品質のパフォーマンスを提供する第２のレベルのプロセッサ使用時間を要求する第２の使用レベルを有し、前記各タスクの前記第１のレベルは、前記各タスクの前記第２のレベルよりも前記プロセッサ使用時間が少なく、前記各タスクの前記第１の品質のパフォーマンスは、前記各タスクの前記第２の品質のパフォーマンスよりも優れる工程と、
（ｂ）第２の使用レベルの少なくとも１つのタスクを含む少なくとも２つのタスクであるが全てのタスクではないタスクを処理するために容認する工程であって、プロセッサの未使用時間が、第２の使用レベルでの容認を未だ受けていないタスクの１つを容認するに不十分であり、かつそれぞれの第２の使用レベルの和が前記プロセッサに得られるトータル時間を超えないように、容認するタスクを選択する工程と、
（ｃ）前記容認を未だ受けていないタスクを処理するために容認から排除する工程とを含む、コンピュータ読み取り可能の媒体。
【請求項１８】
前記プロセッサの時間が許可された全てのタスクを第１の使用レベルで実行させるのに不十分であるときに、前記方法は、さらに、
（ｄ）第２の使用レベルで実行する容認タスクの少なくとも１つで前記容認タスクの実行を開始する工程と、
（ｅ）１以上の容認タスクが実行の要求を一時的に中止しかつ前記プロセッサが第２の使用レベルで実行しているタスクを第１の使用レベルで実行させるに十分な未使用時間を得ることができるとき、前記タスクを第１の使用レベルに切り換える工程とを含む、請求項１７に記載のコンピュータ読み取り可能の媒体。
【請求項１９】
前記方法は、さらに、
（ｄ）前記容認タスクの実行を開始する工程と、
（ｅ）以前に排除されたタスクが容認を再度要求しているとき、前記容認タスクの各第２の使用レベルの和が前記プロセッサに得ることができる時間を超えることなく以前の排除タスクを容認するのに十分に小さくならないかぎり、前記容認タスクを再度排除する工程とを含む、請求項１７に記載のコンピュータ読み取り可能の媒体。
【請求項２０】
前記少なくとも１つの容認タスクは前記プロセッサ使用時間についての少なくとも３つのレベルを有する、請求項１７に記載のコンピュータ読み取り可能の媒体。
【請求項２１】
コンピュータ・システムにおいて作動されたとき、プロセッサ時間をタスクに割り当てるべくプロセッサ資源分配機のための以下の方法をシステムに実行させるコンピュータプログラムを含む、コンピュータ読み取り可能の媒体であって、
（ａ）プロセッサ時間の要求を２以上のタスクの各々から受ける工程であって、少なくとも１つの要求は前記要求と関係するバイレベル・タスクのために２以上のプロセッサ使用レベルを特定し、該２以上の各レベルはリアル・タイムの分配のためのサイクル持続期間により特定され、各サイクル期間のために各サイクルの一部を前記バイレベル・タスクに配分する工程と、
（ｂ）前記要求を基に２以上のタスクのそれぞれにプロセッサ時間を配分し、各サイクルの一部及び特定されたサイクル持続期間の１つを選択することにより前記バイレベル・タスクのためのプロセッサ時間を配分する工程とを含む、コンピュータ読み取り可能の媒体。
【請求項２２】
前記２以上のレベルのそれぞれは前記バイレベル・タスクのためのコールバック機能と関連し、前記タスクは選択されかつ特定されたサイクル持続期間及び各サイクルの一部と関連するコールバック機能を使用することにより呼び出される、請求項２１に記載のコンピュータ読み取り可能の媒体。
【請求項２３】
前記選択は得られるプロセッサ時間量を基に行われ、選択されたレベルは得られるプロセッサ時間量内に調和し得る各サイクルの最大部分と関連するレベルである、請求項２１に記載のコンピュータ読み取り可能の媒体。
【請求項２４】
コンピュータ・システムにおいて作動されたとき、少なくとも２つのタスクの間でプロセッサの時間配分を調整するための以下の方法をシステムに実行させるコンピュータプログラムを含む、コンピュータ読み取り可能の媒体であって、
（ａ）前記プロセッサの時間を一連の第１の期間に分割し、第１のタスクの前記プロセッサでの実行を開始し、各第１の期間の一部を第１のタスクに配分する工程と、
（ｂ）前記プロセッサ時間を前記一連の第１の期間と同じであるか又は異なる一連の第２の期間に分割し、該各第２の期間中、前記プロセッサ使用時間についての第１のレベルで第２のタスクの前記プロセッサでの実行を開始し、各第２の期間の一部を第２のタスクに分配する行程であって、前記第２のタスクは、前記第２の期間中、前記第１のレベルに比べ少ないプロセッサ時間を使用するレベルであって前記第１のレベルに比べ低品質のパフォーマンスを提供する、前記プロセッサ使用時間についての前記第２のレベルでも実行することができる、工程と、
（ｃ）第１のタスクが配分されたプロセッサ時間に比べ期間において大きいプロセッサ時間を供給しているとき、第２のタスクを第２のレベル使用に切り換え、第１のタスクで利用可能にすべくプロセッサの時間の少なくとも一部を再配分する工程とを含む、コンピュータ読み取り可能の媒体。
【請求項２５】
第２のタスクの第２のレベル使用への切り換えは、一連の第２の期間のそのときの各期間の終わりに発生し、引き続く期間のために効果を与える、請求項２４に記載のコンピュータ読み取り可能の媒体。
【請求項２６】
第１のタスクが配分時間よりも期間において多いプロセッサ時間を要求しているか否かの決定はタスクが前記期間に要求している時間の推定を基にした予測により行われ、切り換え及び再配分は第１のタスクが前記期間の配分時間を消費する前に行われる、請求項２４に記載のコンピュータ読み取り可能の媒体。
【請求項２７】
第２のタスクの第２のレベル使用への切り換えは、前記一連の第２の期間のそのときの期間の終わりに発生し、引き続く期間のために効果をもたらす、請求項２６に記載のコンピュータ読み取り可能の媒体。
【請求項２８】
前記方法は、さらに、
（ｄ）工程（ｂ）及び（ｃ）間において、第１の品質のパフォーマンスを提供するレベルを有しかつ第１のレベルのプロセッサ使用時間を実行する第３のタスクのプロセッサでの実行を開始する工程であって、第３のタスクは前記第１のレベルより少ないプロセッサ時間を使用するレベルであって前記第１のレベルより低品質のパフォーマンスを提供する第２のレベルのプロセッサ使用時間でも実行することができる、工程と、
（ｅ）工程（ｃ）において、第１のタスクが配分されたプロセッサ時間より大きい時間を要求している場合に、第３のタスクを第２のレベルの使用に切り換えるよりもむしろ第２のタスクを第２のレベルの使用に切り換える工程とを含む、請求項２４に記載のコンピュータ読み取り可能の媒体。
【請求項２９】
コンピュータ・システムにおいて作動されたとき、プロセッサの使用時間をタスクにより調整するための以下の方法をシステムに実行させるコンピュータプログラムを含む、コンピュータ読み取り可能の媒体であって、
（ａ）プロセッサの時間を一連の期間に分割する工程と、
（ｂ）第１の品質のパフォーマンスを提供する第１のレベルのプロセッサ使用時間で実行するタスクのプロセッサでの実行を開始する工程であって、前記タスクは前記第１のレベルより少ないプロセッサ時間を使用するレベルであって前記第１のレベルより低品質のパフォーマンスを提供する第２のレベルのプロセッサ使用時間でも実行することができる、工程と、
（ｃ）前記各期間の一部を前記タスクに配分する工程と、
（ｄ）前記タスクが配分されたプロセッサ時間より期間内で大きいプロセッサ時間を要求しているとき、そのタスクを第２の使用レベルに切り換える工程とを含む、コンピュータ読み取り可能の媒体。
【請求項３０】
前記タスクは次の期間のために第２の使用レベルに切り替えられる、請求項２９に記載のコンピュータ読み取り可能の媒体。
【請求項３１】
前記タスクが配分されたプロセッサ時間より期間内で大きいプロセッサ時間を要求していることの決定は前記タスクが前記期間において要求している時間の推定に基づく予測により行われ、前記切り換えは前記タスクが前記期間において配分された時間を消費する前に行われる、請求項２９に記載のコンピュータ読み取り可能の媒体。
【請求項３２】
コンピュータシステムにおいて作動されたとき、プロセッサの使用時間をタスクにより調整するための以下の方法をシステムに実行させるコンピュータプログラムを含む、コンピュータ読み取り可能の媒体であって、
（ａ）プロセッサの時間を一連の期間に分割する工程と、
（ｂ）第１のレベルのプロセッサ使用時間で実行する第１のタスクのプロセッサでの実行を開始する行程であって、前記第１のタスクは前記第１のレベルより少ないプロセッサ時間を使用するレベルであって前記第１のレベルより低品質のパフォーマンスを提供する第２のレベルのプロセッサ使用時間でも実行することができる、工程と、
（ｃ）前記各期間の一部を前記第１のタスクに配分する工程と、
（ｄ）第１の品質のパフォーマンスを提供する第１のレベルのプロセッサ使用時間で実行する第２のタスクのプロセッサでの実行を開始する工程であって、前記第２のタスクは前記第１のレベルより低いプロセッサ時間を使用するレベルであって前記第１のレベルより低い品質のパフォーマンスを提供する第２のレベルのプロセッサ使用時間でも実行することができる、工程と、
（ｅ）第１のタスクが配分されたプロセッサ時間より期間内で大きいプロセッサ時間を要求しているとき、第１のタスクを第２のレベル使用に切り換えるよりもむしろ第２のタスクを第２のレベルの使用に切り換える工程とを含む、コンピュータ読み取り可能の媒体。
【請求項３３】
プロセッサで実行されるべきタスクを許可するコンピュータ装置であって、
（ａ）プロセッサの実行要求を少なくとも３つのタスクから受ける手段であって、該各タスクの第１の品質のパフォーマンスを提供する少なくとも第１のレベルのプロセッサ使用時間をそれぞれが有し、少なくとも２つのタスクが該各タスクの第２の品質のパフォーマンスを提供する第２のレベルのプロセッサ使用時間を要求する第２の使用レベルを有し、前記各タスクの前記第１のレベルは、前記各タスクの前記第２のレベルよりも前記プロセッサ使用時間が少なく、前記各タスクの前記第１の品質のパフォーマンスは、前記各タスクの前記第２の品質のパフォーマンスよりも優れる手段と、
（ｂ）第２の使用レベルの少なくとも１つのタスクを含む少なくとも２つのタスクであるが全てのタスクではないタスクを処理するために容認する工程であって、前記プロセッサの未使用時間が、第２の使用レベルでの容認を未だ受けていないタスクの１つを容認するに不十分であり、かつそれぞれの第２の使用レベルの和が前記プロセッサに得ることができるトータル時間を超えないように、容認タスクを選択する手段と、
（ｃ）前記容認を未だ受けていないタスクを処理するための容認から排除する手段とを含む、コンピュータ装置。
【請求項３４】
さらに、
（ｄ）第２の使用レベルで実行する容認タスクの少なくとも１つで容認タスクの実行を開始する手段と、
（ｅ）１以上の容認タスクが実行の要求を一時的に中止しかつ前記プロセッサが第２の使用レベルで実行しているタスクを第１の使用レベルで実行させるに十分な未使用時間を得ることができるとき、前記タスクを第１の使用レベルに切り換える手段とを含む、請求項３３に記載の装置。
【請求項３５】
さらに、
（ｄ）前記容認タスクの実行を開始する手段と、
（ｅ）以前に排除されたタスクが容認を再度要求しているとき、前記容認タスクの各第２の使用レベルの和が前記プロセッサに得ることができる時間を超えることなく以前の排除タスクを容認するのに十分に小さくならないかぎり、前記容認タスクを再度排除する手段とを含む、請求項３３に記載の装置。
【請求項３６】
前記少なくとも１つの容認タスクは、前記プロセッサ使用時間についての少なくとも３つのレベルを有する、請求項３３に記載のコンピュータ装置。
【請求項３７】
コンピュータ・システムにおいてプロセッサ時間をタスクに割り当てるプロセッサ資源分配機であって、
（ａ）プロセッサ時間の要求を２以上のタスクから受ける手段であって、少なくとも１つの要求は前記要求と関連するバイレベル・タスク(bi-level task)のために２以上のプロセッサ使用レベルを特定し、該２以上の各レベルはリアル・タイムの分配のためのサイクル持続期間により特定され、各サイクル期間のために各サイクルの一部を前記バイレベル・タスクに配分する手段と、
（ｂ）前記要求に基づいて前記２以上のタスクのそれぞれにプロセッサ時間を配分する手段であって、各サイクルの一部及び前記特定されたサイクル持続期間の１つを選択することにより前記バイレベル・タスクのためのプロセッサ時間を配分する手段とを含む、プロセッサ資源分配機。
【請求項３８】
前記２以上のレベルのそれぞれは前記バイレベル・タスクのためのコールバック機能と関連し、前記タスクは選択されかつ特定されたサイクル持続期間及び各サイクルの一部と関連するコールバック機能を使用することにより呼び出される、請求項３７に記載の分配機。
【請求項３９】
前記選択は得られるプロセッサ時間量を基に行われ、選択されたレベルは得られるプロセッサ時間量内に調和し得る各サイクルの最大部分と関連するレベルである、請求項３７に記載の分配機。
【請求項４０】
コンピュータ・システムにおいて少なくとも２つのタスク間でプロセッサの時間配分を調整するための装置であって、
（ａ）前記プロセッサの時間を一連の第１の期間に分割し、第１のタスクの前記プロセッサでの実行を開始し、各第１の期間の一部を前記第１のタスクに配分する手段と、
（ｂ）前記プロセッサ時間を前記一連の第１の期間と同じであるか又は異なる一連の第２の期間に分割し、前記各第２の期間中、前記プロセッサ使用時間についての第１のレベルで第２のタスクの前記プロセッサでの実行を開始し、各第２の期間の一部を第２のタスクに配分する手段であって、前記第２のタスクは、前記第２の期間中、前記第１のレベルに比べ少ないプロセッサ時間を使用するレベルであって前記第１のレベルに比べ低品質のパフォーマンスを提供する前記プロセッサ使用時間についての前記第２のレベルでも実行することができる手段と、
（ｃ）第１のタスクが配分されたプロセッサ時間に比べ期間において大きいプロセッサ時間を供給しているとき、第２のタスクを第２のレベル使用に切り換え、第１のタスクで利用可能にすべくプロセッサの時間の少なくとも一部を再配分する工程とを含む、調整装置。
【請求項４１】
第２のタスクの第２のレベル使用への切り換えは、一連の第２の期間のそのときの各期間の終わりに発生し、引き続く期間のために効果を与える、請求項４０に記載の装置。
【請求項４２】
第１のタスクが配分時間よりも期間において大きいプロセッサ時間を要求しているか否かの決定はタスクが前記期間に要求している時間の推定を基にした予測により行われ、切り換え及び再配分は第１のタスクが前記期間の配分時間を消費する前に行われる、請求項４０に記載の装置。
【請求項４３】
第２のタスクの第２のレベル使用への切り換えは、前記一連の第２の期間のそのときの期間の終わりに発生し、引き続く期間のために効果をもたらす、請求項４２に記載の装置。
【請求項４４】
さらに、
（ｄ）第１の品質のパフォーマンスを提供するレベルを有しかつ第１のレベルのプロセッサ使用時間を実行する第３のタスクのプロセッサでの実行を開始する手段であって、第３のタスクは前記第１のレベルより少ないプロセッサ時間を使用するレベルであって前記第１のレベルより低品質のパフォーマンスを提供する第２のレベルのプロセッサ使用時間でも実行することができる手段と、
（ｅ）第１のタスクが配分されたプロセッサ時間より大きい時間を要求している場合に、第３のタスクを第２のレベルの使用に切り換えるよりもむしろ第２のタスクを第２のレベルの使用に切り換える手段とを含む、請求項４０に記載の装置。
【請求項４５】
コンピュータ・システムにおいてプロセッサの使用時間をタスクにより調整する装置であって、
（ａ）プロセッサの時間を一連の期間に分割する手段と、
（ｂ）第１の品質のパフォーマンスを提供する第１のレベルのプロセッサ使用時間で実行するタスクのプロセッサでの実行を開始する手段であって、前記タスクは前記第１のレベルより少ないプロセッサ時間を使用するレベルであって前記第１のレベルより低い品質のパフォーマンスを提供する第２のレベルのプロセッサ使用時間でも実行することができる手段と、
（ｃ）前記各期間の一部を前記タスクに配分する手段と、
（ｄ）前記タスクが配分されたプロセッサ時間より期間内で大きいプロセッサ時間を要求しているとき、そのタスクを第２の使用レベルに切り換える手段とを含む、調整装置。
【請求項４６】
前記タスクは次の期間のために第２の使用レベルに切り替えられる、請求項４５に記載の装置。
【請求項４７】
前記タスクが配分されたプロセッサ時間より期間内で大きいプロセッサ時間を要求していることの決定は前記タスクが前記期間において要求している時間の推定に基づく予測により行われ、前記切り換えは前記タスクが前記期間において配分された時間を消費する前に行われる、請求項４５に記載の装置。
【請求項４８】
コンピュータ・システムにおいてプロセッサの使用時間をタスクにより調整する装置であって、
（ａ）プロセッサの時間を一連の期間に分割する手段と、
（ｂ）第１の品質のパフォーマンスを提供する第１のレベルのプロセッサ使用時間で実行する第１のタスクのプロセッサでの実行を開始する手段であって、前記第１のタスクは前記第１のレベルより少ないプロセッサ時間を使用するレベルであって前記第１のレベルより低品質のパフォーマンスを提供する第２のレベルのプロセッサ使用時間でも実行することができる手段と、
（ｃ）前記各期間の一部を前記第１のタスクに配分する手段と、
（ｄ）第１のレベルのプロセッサ使用時間で実行する第２のタスクのプロセッサでの実行を開始する手段であって、前記第２のタスクは前記第１のレベルより少ないプロセッサ時間を使用するレベルであって前記第１のレベルより低品質のパフォーマンスを提供する第２のレベルのプロセッサ使用時間でも実行することができる手段と、
（ｅ）第１のタスクが配分されたプロセッサ時間より期間内で大きいプロセッサ時間を要求しているとき、第１のタスクを第２のレベル使用に切り換えるよりもむしろ第２のタスクを第２のレベル使用に切り換える手段とを含む、調整装置。
【発明の詳細な説明】
【０００１】
【技術分野】
本発明は、１つのデジタル・プロセッサに利用可能な時間を２以上の選択的タスク又はスレッド分配し、それらの実行のスケジュールを作成する装置と方法に関する。
【０００２】
【背景技術】
ソフト・リアルタイム要件を備えるプロセッサのスケジュール作成の必要性は、スマート(SMART)、リアルト(Rialto)、及びプロセッサ・キャパシティ・リザーヴズ（プロセス容量予約装置）を含むいくつかの先行技術システムによって取り扱われてきた。
【０００３】
スタンフォード大学設計のＳＭＡＲＴスケジューラは、従来及びソフト・リアルタイムのアプリケーションの同時実行を支援する。対話式アプリケーションは、よい応答を得る。それは、改良されたベスト・エフォート・スケジューラを使用し、軽負荷ではすべての最終期限が満たされ、過負荷では、低順位のタスクへのサービスを否定することにより、ゆるやかにパフォーマンスを下げるようにタスクの優先順位が使用される。それは、実行するタスクに向かって前進される規約時間の観念を利用している。
【０００４】
マイクロソフト・リサーチで設計されたリアルト・スケジューラは、割り振られた環境で従来及びソフト・リアルタイムのアプリケーションの双方の同時実行を支援する。リアルトのアプリケーションは、独立して発案されているので、タスクがそのスケジュール作成の必要性を判断できるように、タイミングとスケジュール作成のモジュール性が必要とされる。リアルトは、割り振られたアプリケーションにとってEarliest Deadline First（ＥＤＦ）(最早期限最優先)よりも優れた最小弛緩スケジューラを使用しており、中間パイプラインでアクセスされた構成部分のための最終期限の概念はない。リアルトは、始期拘束／終期拘束機構と、利用、スケジュール作成を制限し、過負荷状態を処理するための予約装置の組み合わせを使用している。それらは「大抵の負荷除去状況を積極的に避ける」。
【０００５】
ＣＭＵ(Processor Capacity Reserves)で開発されたプロセッサ・キャパシティ・リザーヴズ装置もまた、従来及びリアルタイム作業の双方の同時実行を支援する。アプリケーションは、必要な時間を前もって予約し、装置は、タスクが予約を超えないこと、また予約が装置の容量を超えないことを確実にする。予約は各期間に使用される時間量に関して与えられ、スケジュール作成はＥＤＦ（最早期限最優先）である。予約は、処理境界から境界まで通されることでタスクの割り振りを支援する。プロセッサ・キャパシティ・リザーブでは、スケジュール作成とＱＯＳマネジャーが明確に分かれている。
【０００６】
【発明の概要】
本発明に係るプロセッサ資源分配装置は、１つのプロセッサで多数のタスクに時間を配分する。それは３つの構成要素から成る。第１の構成要素は資源管理機(資源マネージャ)と呼ばれ、どのタスクにどれだけの時間量が与えられるかを決定する。第２の構成要素はスケジューラと呼ばれ、各タスクが配分された時間を得るように、タスクに時間を与える。第３の構成要素はポリシー・ボックスと呼ばれ、全てのタスクの要求を満たす時間が不十分な場合に、ユーザーと資源マネージャとに連絡する。
【０００７】
プロセッサは、１組の装置に見えるタスク・セット等のタスクのセットをホスト機かあるいは直接ユーザーに対して稼働するよう求められる。ホスト機はＤＯＳボックスでもよく、コンピュータ稼働ウィンドウズか、他のものでもよい。あるいは、プロセッサは、ホスト機が入っていないセットの最上ボックス内に入れられていてもよい。ＡＰＣユーザーは、オーディオ・ビデオ、モデム及びグラッフィク装置のための支援を提供されてもよい。
【０００８】
何らかの装置に支持された１組のタスクは、（ＤＯＳボックスの場合のように）静的であってもよいし、（ウィンドウズ、又はジャワのアプレットのある場合はセットの最上ボックスの場合のように）動的であってもよい。これらのタスクは、同時稼動の装置の外観を呈するように、リアルタイムにプロセッサを共有しなければならない。
【０００９】
プロセッサ資源分配装置は、タスクを許容しスケジュールする役割を有する。それは、タスクが稼働できるか否か、いつ稼働できるか、またどの位の利用可能な時間を消費するか（各セッションにおいてどの位の稼働時間が可能か）を決定する。それは、１組の実際の物理装置が支援されていることをユーザーが信じ続けられるように、プロセス時間の使用を管理する。多数の装置がシミュレートされている事実は目に見えない。
【００１０】
この環境では、ソフト、リアルタイム要件を有する。タスクには最終期限があるが、最終期限に間に合わない場合、結果は不運ではあるものの、破滅的ではない。この限られた環境では、従来のような作業場又は時分割タスクを持っていないかもしれない。もっとも、セットの最上環境ではある程度それらがあるかもしれないが。非周期的タスクは通常、頻繁に実行されないコマンドに関連する。
【００１１】
従来技術装置との対比
許容制御が保証されている。本発明の装置では、タスクが許容を許可されると、それが終了されるまで少なくともそれ自体の規定最小回数を得るまで保証される。
【００１２】
資源の配分は、ステップ関数である。他の装置は資源配分を平滑関数として行う。他の装置においては、優先順位は過負荷の場合稼働タスクのパフォーマンスを「ゆるやかに下げる」ために使用される。この取り組みの問題点は、本発明のタスクはいずれも、その利用がわずかに変更される場合は「ゆるやかに下がらない」ことである。むしろ、資源配分における対応する段階を必要とするサービスの質には、はっきりと段がある。配分がこれらの段の１つに行われない場合は、より低いレベルの質の方に資源を浪費するか、あるいはより高いレベルのための最終期限を逸するかのどちらかの結果となる。
【００１３】
許容制御と許可セットのための最小再計算。本発明の実施例においては、スケジュールに悪影響を及ぼすような事象が発生したときに、またそのときにのみ、スケジュール作成情報を再計算する。始期拘束／終期拘束対を使用するリアルトのような装置は、各周期に関する各タスクに対するスケジュール作成の可能性を再計算する。
【００１４】
本発明の実施例においては、装置が過負荷の状態の場合、又は最終期限が見逃されそうな場合、スケジュール作成を再計算しないし、アドミタンスについての取り組みを決定しようとしない。これはリアルトのような装置の取り組みである。それは、スケジュール作成の決定が行われつつある時期までには、最終期限が既に見逃されているかも知れないという欠点を有する。本発明の実施例においては、最終期限は決して見逃されない。
【００１５】
本発明の実施例においては、休止タスクを支援する。これらのタスクは、容認制御を再計算するコストをかけず、休止状態をやめるまで資源を消費しないで、稼働したいときに容認を保証される。ある装置は、容量の予約のためにこの種のタスクを、使用されていないものに至るまで全量を必要とするものもあるであろう。その結果、リソースが浪費される。他の装置は、実際に実行を望むときにタスクが判断することを要求するものもあるが、その結果、既に容認されている他のタスクが終了されてしまう。
【００１６】
どのタスクが負荷を除去するか、あるいは最終期限を逸するかに関する全体的な取り組みの決定。他の装置は、過渡的な過負荷が検知されたときに全体的な決定をするが、その時点で何らかのタスクがすでに最終期限を逸している。事実上、負荷を除去することが求められてきた。そして、過負荷が発生したら次にどのタスクが偶然稼働するか、このタスクの「選択プロセス」はほとんどでたらめである。
【００１７】
本発明の一実施例は、プロセッサで行われるタスクの容認を制限する方法である。各タスクは、高品質の実行を与える高レベルと低品質の実行を与える低レベルとを含む２以上の時間使用のレベルを有する。タスクの最低使用レベルの合計がプロセッサで利用可能な全時間を超えない限り、タスクは処理のため容認される。１つのタスクが処理を必要とするがプロセッサで時間が利用不能であれば（既に容認されたタスクの最低使用レベルの合計が大き過ぎて新しいタスクを容認できない場合）、新しいタスクは除外される。しかし、さらに低い最低使用レベルなら、その使用レベルが利用可能時間内に適合できる範囲であれば容認されるであろう。
【００１８】
タスクが一旦容認されると、実行が開始される。タスクの１つが一時的に実行を必要としなくなり、それによってプロセッサにおいて利用可能な時間が増える場合、最高使用レベルより低いレベルで実行されてきた他のタスクは、解放された時間を使用するため、より高い使用レベルにその実行を切り替えるであろう。また、あるタスクが一時的に実行を必要としなくなり、プロセッサで未使用の時間が利用可能になった場合、本発明の方法の重要な面は、一時的に実行を必要としなくなったそのタスクも含めてすべてのタスクの最低使用レベルの合計が新しく容認されたタスクに時間を許さない限り、追加的なタスクにその利用可能時間を許さないことである。すなわち、１以上のタスクが実行を必要としなくなった場合に充分な時間がプロセッサで利用可能であるという事実だけでは、未使用の時間の使用を別のタスクに許すには不十分である。その代わり、残りの容認されたタスクの最低使用レベルの合計が、プロセッサで利用可能の時間を超えることなく新しいタスクが容認されるに充分小さくなるように、先に容認されたタスクの１つが終了されなくてはならない。
【００１９】
本発明の別の面において、本発明の方法は、アプリケーション・プログラム作成インターフェイスを複数のアプリケーションに提供する。各アプリケーションは、プロセッサ資源分配装置に対してそのアプリケーションを呼び出す２以上の機能を指定する。この方法においては、プロセッサ資源分配装置は、プロセッサで利用可能な時間に基づくタスクの呼び出しに使用される機能を選択して、各タスクをその機能の１つと共に呼び出す。アプリケーションがその呼び出し機能をプロセッサに提供する際に、各アプリケーションは呼び戻し機能のリストと、各呼び戻し機能に関連して、リアルタイムの分割のための周期持続性（サイクル持続期間）、及び各周期持続性に対して、タスクがその機能と共に呼び出された場合、そのタスクによって使用される各周期（サイクル）の一部の仕様を提示する。その情報は、周期持続性と、使用される各周期の部分とから成る。この情報は、処理時間を各アプリケーションに配分するスケジュールを決定するために、プロセッサ資源分配装置によって使用される。
【００２０】
本発明の別の面は、１つのタスクから別のタスクへと時間を移行させる方法を含む。時間使用の少なくとも２つのレベルを有する第１のタスクが、仕様のより高度なレベルで操作しており、特定の期間のために第２のタスクがタスクに割り振られてきた時間よりも多くの時間を要求するならば、本発明は第１のタスクを、第２のタスクによって時間を利用可能にする、より低い使用レベルに移行させる方法を含む。さらに、１つのタスクから別のタスクへ利用可能な時間を移行させる代わりに、第２のタスクは、特定の期間又は周期に処理を終了するには充分な時間がなかったことをプロセッサに報告することができる。そうすれば、他のタスクが先に終了するときに利用可能になる時間を与えられるであろう。もし次の周期又は期間の開始前に完了するには不十分な時間が利用可能になる場合、この事実がリソース・マネジャーに報告されれば、リソース・マネジャーは、より低い使用レベルを指定する呼び戻し機能を有する次の周期のタスクを呼び出すことができる。
【００２１】
【発明を実施するための最良の形態】
第１原則：図１に示すように、プロセッサ資源分配装置１は、以下の３つの第１原則に従う。
【００２２】
１．一旦タスク２がユーザーによって首尾よく開始されると、ユーザーの見通しから、そのタスクは自然に終了するまで、あるいはユーザーがそれを終了するまで継続する。
【００２３】
ユーザーは、何らかのコマンド回線、対話、ボタン又はその他何でもを介して（例えば、ＣＤ再生装置の演奏ボタンをたたいて）、タスクを開始する。一旦タスクが開始されると（例えば、サウンド・トラックがスピーカーから出始めると）、それが終了する（ＣＤの最後に来る）まで、あるいはユーザーが（ＣＤ再生装置の「停止」ボタンを押して）それを終了させるまで継続する。プロセッサ３のこの機能性に関わるタスクは、ＣＤの演奏中連続して稼働しないかも知れない（実際、理想的には、それらタスクは連続して稼働しないであろう）が、ユーザーはこれをスピーカーの音からは検知することはできないであろう。
【００２４】
この原則は、過渡的過負荷があるときに稼働中のタスクを終了させる可能性のある装置では満たされない。
【００２５】
これは、タスクが強制排除なしに稼働することを保証するのではなく、連続的な機能性の出現を維持するに充分頻繁に充分な時間を許可されることを保証する。プロセッサ分散装置１は、タスク２が時間使用の態勢にある限り、プロセッサ３に利用可能な時間を（ほとんど）１００％配分する。
【００２６】
２．タスク２が稼働態勢にあり、再現時間周期（図２における「期間」）の幾分かが未使用であれば、その時間量が稼働態勢タスクに利用可能にされる。すなわち、プロセッサが部分的にアイドルであり、タスクがさらにプロセッサ時間を要求するならば、それはさらに時間を許可される。これは、１つのタスクがそれ自体に超過プロセッサ時間を蓄える必要がないことを意味する。先のタスクが蓄えておいたが使用していないいくらかの時間を別のタスクが要求するなら、後のタスクはその時間を与えられる。
【００２７】
３．サービスの質の修正は、ユーザーの要求事項を参照して行われ、そのような手段決定は、全装置の了解でなされる。
【００２８】
プロセッサの時間があまりに多くタスク・セットによって要求されるために装置が過負荷になると、あるタスクは終了されるか、より低い質のサービスを提供することによって負荷を下げるように要求されねばならない。どのタスクに負荷を下げるように要求すべきか、またそのサービスをどの程度下げるよう要求すべきかの決定は、ユーザーの選択に基づいてなされるべきである。タスク・セットが如何にユーザーの必要事項を満たすかについて、包括的な（装置全体の）了解がなければならない。また、サービスの質の決定は、単独のタスクの必要事項を了解するだけで行われてはならない。
【００２９】
プロセッサ資源分配装置の設計原則
プロセッサ資源分配装置１の設計にとって重要な設計選択事項がいくつかある。
【００３０】
スケジュール作成と許容制御の分離
この実施例においては、どのタスクを稼働するか（資源管理装置５）、及びどのタスクを現在稼働中であるか（スケジューラ４）の決定を別々に行う。
【００３１】
どのタスクを稼働するか（またそれらを如何によく稼働するか）の決定プロセスは、資源管理装置５によって行われるが、さらに２つの構成要素に分けられる。第１の許容制御６は、タスクが装置に許容され得るか否かを我々が決定するためのプロセスである。許容されたタスクは、プロセッサ時間の最小量を保証される。アプリケーション書き出しプログラムは、ゼロを最小と指定するオプションを有する。第２の許可制御７は、各タスクにどの程度のプロセッサ時間が与えられるかを決定する。その許可は、消費できる期間とその量とからなる。例えば、１つの許可は、３０ｍｓ期間に１０ｍｓを配分することができる。許可は、これだけの時間が各指定期間にタスク２に配分されるという、タスク２への保証である。
【００３２】
実際にタスクに稼働せよと命令するプロセス、及び許可された時間の配分が引き渡されたと保証するプロセスは、スケジューラ４によって行われる。スケジューラは手段決定をしない。それは、許可制御プロセス７によって設定されたタスクのセットを介して単に循環するのみである。
【００３３】
ユーザー制御のスケジュール作成手段
当社は、どのタスクが実行されるべきかを決定する手段と、その選択を行うのに使用する手段とを分離している。同様に、当社は、特定のタスクがどの程度の質のサービスを提供するべきかを決定する手段と、その質のサービス・レベルを選択するのに使用する手段とを分離している。
【００３４】
ユーザー（又はホスト機）８は、スケジュール作成にどのタスクが選択されるか、及びどのレベルの質のサービスを各タスクが提供を要求されるを制御する。資源管理装置５は、スケジュール作成手段の決定が行われなければならない場合に、ユーザーに操作されたスケジュール作成手段情報をポリシー・ボックス９にアクセスするためのフックを有する。
【００３５】
プロセッサ資源分配装置１は、どのタスクのセットが稼働するか、又はどの程度に稼働するかを決定することに運と時間調節が関与しないように設計されている。配分手段の決定は、常に明白になされる。これは周期タスクの寿命における各期間に対する新スケジュール作成決定を効果的に行う装置と対照をなす。当社は、新しいタスクがスタートしたか停止した、あるいはタスクがその利用パターンを修正する必要があるといった、資源割振に重要な事象が発生したときに、手段配分決定を行うだけである。
【００３６】
プロセッサ資源分配装置１の機能は、３つの主要構成要素であるスケジューラ４、資源管理装置５，ポリシー・ボクス９に分かれる。ポリシー・ボックスは、装置設計者によって予め設定されているが、ユーザー８が個人的な選択事項に合うように修正してもよい。例えば、デフォルトにより、ビデオ処理は、オーディオ処理より質が低下するが、聴覚障害ユーザーは、その逆にしたいかも知れない。
【００３７】
プロセッサでの時間の割り振りの概要
資源分配機１の機能は、スケジューラ４、資源マネージャー５及びポリシー・ボックス９の３つの主要素に分割される。
【００３８】
資源マネージャー５は、容認制御６、許可設定７、及びユーザーのために多重タスク間における利用時間協定のために応答することができる。
【００３９】
スケジューラ４は、資源マネージャー５により作られた容認を受け取るスケジュールを実行し、時間の配分を実行し、実際の利用を資源マネージャー５に知らせるために応答する。
【００４０】
タスク２がプロセッサ３を開始させることを必要としているとき、プロセッサの時間の要求が資源マネージャー５に対して行われる。プロセッサ・サイクル（プロセッサ周期）のための要望は、要求されたプロセッサ時間にわたる（繰り返し）期間とプロセッサ時間が各期間において必要とする時間量とにおいて与えられる。例えば、ＭＰＥＧデコーダ・タスクは、各３０ミリ秒のプロセッサ時間のうち１０ミリ秒を必要としてもよい（図２参照）。
【００４１】
もし要求された時間のために十分な超過容量であると、資源マネージャー５はタスク２により作られた要望を容認する。そのタスクは、スケジュールを作成されたされたセットに加えられ、タスクがユーザー又は他の外部事象により終了されるまでそれらをとどめる。
【００４２】
もし過負荷状態が発生すると、ある特別なアクションがなされなければならない。この場合、資源マネージャー５は、タスクがある負荷の切り離しを要求されねばならないことを決定するようにポリシー・ボックス９を呼び出し、低品質のサービスを提供する。これには、連絡することができないという要求を作られたタスクが負荷を排除する（捨てる）ように質問される１つである、という含みはない。むしろタスクの独立した秩序転移及びそれらのサービスの質は、この決定を援助すようにポリシー・ボックスにより提供される。
【００４３】
本実施例においては、厳格な容認制御を行うという事実の含みは、スケジューラ４がスケジュール可能のタスクセットだけのスケジュールを作成するように問い合わされることを保証するということである。これは、Earliest Deadline First (ＥＤＦ)のようなサンプル・スケジューリング・ポリシーを使用することができる、ということを意味する。ＥＤＦは、確実な制約で、理論的にスケジュールを作ることができる適宜なタスクセットのスケジュールを効果的に作成するために提供される。そのような制約は、優先使用の可能性と、タスク間での同調の欠落とを含む。より小期間のタスクは、長い稼動タスクのために単一期間の間、ある程度の時間で稼動される。これは、長いタスクが優先使用可能であることを必要とする。スケジューリングは、タスクが期間のある時点でそれらの使用を許すことができるならば、保証され得ない。これは、周期的なタスクがそれらの期間内で同期することができない、ということを意味する。プロセッサ資源分配機、制御ビデオ、オーディオ、及び通信のための典型的なタスクセットの周期的タスクは、それらの要求に遭遇する。
【００４４】
この作業の手法
タスクの稼動を終了させない目的のために、その時間を使用するか否かのタスクのために十分な時間を予約しなければならない。システムが過負荷になっていると、タスクがその利用時間を低減することを要求する手法を必要とするが、要求を否定してもよい。
【００４５】
これら潜在的な矛盾する目標に遭遇するために、表１に示すような資源リストを導入することができる。このデータ構成は、支援可能の各サービス・レベルでタスクのために要求される時間利用の明細すなわち仕様を示す。各エントリーは、期間、利用性、率（レート）及びファンクション（機能）を含む。期間は、ミリ秒（ｍ秒）又はシステムの時間単位において、タスクが遂行しなければならないサイクル期間の明細を示す。利用性は、各期間において消費される時間量（ミリ秒又はシステム時間単位）の明細を示す。レートは、期間により分割された利用性として計算され、またこのタスクにより使用される時間の百分率の値である。機能パラメータは、特定の期間／利用性の結合がタスクに容認されているとき呼び出される機能の明細を示す。タスクは、期間及び利用性が呼び出される機能を基に容認されるものを決定する。
【００４６】
タスクが単一の低サービスの支援だけをすることができるならば、それはその資源シストにおける１つのエントリーだけを有する。その表内にいくつかのエントリーがあるならば、それらの表はレートにより規則正しくされる。最大レートのエントリーはタスクのための最良のパフォーマンス(performance)を表し、最小レートのエントリーはタスクが最小レートにより合理的に得ることができる最小処理量を表す。アプリケーションは、資源マネージャー５を呼び出すことによって資源リストのエントリーを変更することができる。
【００４７】
タスクに容認された実際のレートは、テーブル内のエントリーの１つである。資源マネージャーは、結合がその資源リスト内に存在している限りタスクに対し期間／利用性の結合を許容しない。
【００４８】
【表１】
0004174178.tif 000002
表１：資源リストのフォーマット
【００４９】
各タスクは、少なくとも１つのエントリーを持つ資源リストを資源マネージャー５に提供する。アプリケーションは、スケジューラ４がこのタスクを遂行しているとき、実行すべきコールバック機能を提供する。キャリブレーション期間の間、利用性はユーザーにより省略することができ、資源マネージャー５はそれを充填する。
【００５０】
資源マネージャーの実行内容
資源マネージャー５は、容認制御及び確立された容認セットのために応答可能である。
【００５１】
資源マネージャー５は、各タスクに与えられる時間配分を決定する。各タスクに与えられる時間配分は、「容認」を呼び出される。容認は、タスクの資源リストにおけるエントリーの１つに応答される。
【００５２】
タスク用の容認は、３つのイベントの１つが発生するとき、変更することができる。最初は、タスクがシステムに入るとき又はシステムから離れるときである。第２は、タスクがその資源リストを変更するときである。第３は、あるタスクが「静止」状態に入るとき又は「静止」状態にあるときである。静止状態は、今後稼動を希望し、それ自身のためにプロセッサ時間の配分を希望するタスクのために予約され、その結果容認層(admission later)を否定しないことがある。しかし、これらのタスクは、それが静止しているとき、その間多くの時間を使用しないから、他のタスクへの使用のためにそれらの時間配分が自由になる。
【００５３】
図３に示すように、新たなタスクが立ち上がると（ステップ２１）、そのタスクはその資源リストで資源マネージャーに接触する（ステップ２２）。資源マネージャーは、次に容認制御を行う。新たなタスクは、システムにおける全てのタスク（現在実行可能のものと静止しているものとの両者）の最小容認の和が１００％以下であるときだけシステムに入ることを許される（ステップ２３）。
【００５４】
タスクが、システムに入るか（ステップ２２）又はシステムから離れるとき、若しくは、潜在的に静止しているタスクが状態を変えるとき（ステップ２５）、資源マネージャーは全ての容認されたタスクの許可の新たなセットを発生しなければならない。この時点で、タスク用の許可を増減させてもよい。このプロセスの最初のステップとして、全てのタスクがそれらの最大許可を得ることができるか否かを決定する（ステップ２６）。それができないと、ポリシー・ボックスがユーザーの性能優先(performance preference)を得るようにアクセスされ（ステップ２７）、妥協した許可時間が計算される（ステップ２７）。達成された新たな許可セットで、次のステップは資源量を自由にすべくスケジューラで現在の許可を除く又は低減させ（ステップ２９）、最終ステップは新たな及び増大された許可をスケジューラに通知する（ステップ３０）。タスクは、次の期間の利用が新たな許可と関連する機能に対する呼び出しでもって開始されるので、間接的に通知される。許可の和が１００％を越えないことを資源マネージャーが保証しているので、スケジューラ４は全てのタスクの引き続くスケジュールを作成すべく単純なＥＤＦ構成を使用することができるように許可を実施するだけである。
【００５５】
【数１】
容認制御:
0004174178.tif 000003
【００５６】
【数２】
許可セット:
0004174178.tif 000004
【００５７】
スケジューラの実行内容
スケジューラ４は、図４に示すように、どのタスクを次に稼動させるかを決定し、許可を実行し、資源マネージャーにアカウントをする資源を提供するために、応答することができる。
【００５８】
スケジューラへの入力は、許可セットである。これは、許可された稼動可能のタスクの資源リストにおける入力セットである。スケジューラは、「次の期間が始期、次の期間の終期」のための一定の時間で「期間、利用性」のセットを増大させている。
【００５９】
タスクの次の稼動を決定するために、スケジューラはＥＤＦアルゴリズムを使用する。使用される最終期限は許可のための期間端すなわち終期である。この期間のための全許可を既に受けていない近くの次の終期を有するタスクは、いつでも選択される。
【００６０】
次のコンテキスト(context)スイッチは次の３つの理由の１つのために発生する。第１に、タスクはプロセッサに（その許可を仕上げるまたは仕上げることなしに）ゆだねてもよい。第２に、タスクはその許可を越えてもよい。第３に、他の終期は現在の期間に先立って発生してもよい。
【００６１】
タスクが一度選択され、タスクに対するスイッチングの前に、スケジューラはタイマーの割り込みを設定することにより再度制御を得るために整える（ステップ４８）。スケジューラは以下より早期にタイマー割り込みを設定する。
【００６２】
選択されたタスクのための許可終期、又は、まもなく到来する次の期間終了時を有するタスク（現在のタスク以外の）用の次の期間開始時。
【００６３】
タイマーが第１のイベントにおいて行われると、タスクはその許可を超過される。タイマーが第２のイベントにおいて行われると、現在稼動している１つが新たな期間を開始するより短い期間を持つタスクは、新たな期間を開始し、稼動中のタスクよりはむしろ最終期限を有する。
【００６４】
許可の終わりに、又はタスクがプロセッサを譲渡し、この期間で実行していることを表しているとき、次の期間が開始され、次の終期が更新される。更新は、タスクが先取りしてもよいので、タスクがプロセッサに承諾されるときは行われない。
【００６５】
図４に示すように、プロセッサは、割り込みでもって開始し（ステップ４１）、傑出した許可であるか否かのチェックをする（ステップ４２）。優れた許可であると、時間がタスクに与えられる（ステップ４７）、次の中断が設定され（ステップ４８）、タスクが稼動される。優れた許可でないと、多くの資源量が最近要求されているならば、許可セットが更新される。これが優れた許可をもたらすならば、処理はステップ４７に移行する。傑出した許可でないならば、システムは、その許可内で完了せずかつ超過時間を供給するタスクであるか否かのチェックをする（ステップ４５）。そのようなタスクであると、タイマーはそのタスクに提供され（ステップ４６）、ステップ４８に続く。超過時間が要求されていないと、タイマーは散発的なサーバーに与えられる（ステップ５０）。
【００６６】
図２に示すように、以下は、モデム、３Ｄグラフィックス表示装置及びＭＰＥＧ３デコーダの３つのタスク用のサンプル・スケジュールを示す。時間０では、複数のタスク用の許可セットは以下のようになる。
【００６７】
【表２】
0004174178.tif 000005
表２：３つのタスク用の初期許可
モデム，ＭＰＥＧデコンプレッション(decompression)、３Ｄグラフィック
【００６８】
【表３】
0004174178.tif 000006
表３：３つのタスク用の引き続く始期及び終期
モデム，ＭＰＥＧデコンプレッション、３Ｄグラフィックス
【００６９】
表３は、３つのタスクを稼動させるために、最初の７０ミリ秒用のスケジュールを示す。６６ミリ秒を超えるこのスケジュールは、図２に図表として示される。
【００７０】
ここに、スケジューラの稼動のための疑似コードを示す。
【００７１】
while (1) {
task_to_run = find_task ( min "period_end" AND "period_begin" <=
time_now);
if (preempting_task = find_task ("period_end" < task_to_run ("period_end")
AND min ("period_begin"))){
alarm_time = preempting_task ("period_begin");
} else {
alarm_time = time_now + task_to_run ("utilization");
}
set_timer (alarm_time);
run (task_to_run);
/* if the user returns here, they have finished their grant for this period*/
task_to_run (period_begin)+= task_to_run (period);
task_to_run (period_end)+= task_to_run (period);
{
【００７２】
３Ｄグラフィックス・タスクは図示の５つの期間中の３つの期間に先取り権なしに稼動するが、ＭＰＥＧデコーディング・タスクは少なくとも一回で常に先取する。
【００７３】
ポリシー・ボックスの実行内容
ポリシー・ボックス９は、最高レベルのプロセッサ時間を与えるべき全てのタスクに与えるには不十分な資源であるとき、他に対して交換しなければならないタスク２に関する情報源である。
【００７４】
支援されたタスク２のセット毎に、ポリシー・ボックス９は、ユーザーに対する各タスクの相対的な重要性を理解している。それらには、プロダクトで初期に移す格付けのデフォルト・セット(default set)がある。このセットは、システムのユーザー又はシステム管理者により無効にすることができる。
【００７５】
それらには、実行され得るポリシー・ボックスのような各種の手法がある。実施例においては、セットの各タスクのためのプロセッサ時間の相対的配分に応答する百分率のセットを維持している。それら百分率は、資源リスト２１に開示されている、タスクにより支援することができる現実のレートに関連しない。百分率セットは、システムが過負荷のとき、ポリシー・ボックス９により資源マネージャー５に戻される。
【００７６】
容認された格タスクのために、資源マネージャー５は、ポリシー・ボックス９により与えられた百分率より高い又は低い２つの資源リスト・エントリー(Resource List Entrie)を選択する。そのように選択された高エントリーの総和がプロセッサ時間の１００％より小ささいと、全てのタスクはこの高エントリーを得ることができる。しかし、そのような和が大きすぎると、リシー・ボックス９によりそれに与えられた百分率とそのより高レベルとの間に大きな隔たりを有するタスクは、低レベルを与えられることになる。このプロセスは、保証の和が入手可能のプロセッサ時間の１００％より小さくなるまで繰り返される。
【００７７】
最終的な付加的なパス(pass)は、許可の和が１００％未満であるときに、形成される。可能であるならば、１００％の近くで使用されるように、タスクの許可が増大される。さらに、現在選択されたレベルに近い次の高いレベルを有するタスクは、最初に付加的なプロセッサ時間を与えられる。
【００７８】
タスクの展望
ここで、スケジューラ４と資源マネージャー５がタスク２の外観から行うことを説明する。それには、正常タスクと静止タスクとの２種類のタスクがある。正常タスクは、稼動する準備ができているものである。静止タスクは、それらのスケジュールを正常に行うことを一時的に放棄されており、次の期間開始時を有していない。
【００７９】
正常タスク
タスクは、これが最初に立ち上げられるとき、資源リスト２１で資源マネージャーを呼び出す（ステップ２２）。この時点で校正ループを稼動させてもよいし、レート用を除いて資源リストのエントリーをファイルしてもよい。多くの場合、少なくとも機能が満たされていなければならず、やがては、期間、利用性及びレートが同様に満たされる。
【００８０】
タスクが制御を得る次の時間は図１に示すように、資源リストに与えられた機能の１つが呼び出されるときである。タスクは、３つの機能の１つを解することを除いて各種の手法で制御を得られない。その機能は、１フレームの計算、フレームセットの計算等、完了すべき作業の微少セットに相当する。フレームが慣性すると、その機能の復帰はプロセッサに効果的に与えられ、タスクはこの期間を計算する。
【００８１】
タスクは、同じ機能を通すか又は資源リストに与えられた他の機能を通して、そのタスクのために次の期間の時間を再度コールされる。各時間毎に、タスクは、３つの機能のうちの１つを通してコールされ、最後の期間における実際の利用性のリポートを与えられる。これは、資源リストを調整すべく選択的に使用される（期間を使用する持続時間はある２つの期間の差であってもよい。）。
【００８２】
タスクは、任意の時間でその資源リストを調整することができ、特定の最小レートが先の最小レートより大きくない単一のケビエート(caveat)で、システムに容認を許可される。エントリーは加えられ、除かれ、又は変更され、さらには新たな機能を自由に特定される。
【００８３】
タスクがその許可を越えると（例えば、許可が超過する前に譲渡されないならば）、タスクは直ちに先取りされ、そのタスクはそれが稼動する次の時間に超過して稼動することを通知される。次の稼動期間において、タスクが稼動する次の期間において、そのタスクは、同じ処理を継続すること、負荷を切り離すこと、又は適切なエルスを選ぶことができる。図４のステップ４５及び４６に示すように、資源が過剰であると、その許可が期限切れになる前に計算されない多くのタスクは、稼動することを許可される。そのようなタスクが２以上であると、最初に早期に期限切れになるタスクがその最終期限に達するまで稼動することを許される。しかし、アプリケーション・ライターは、許可を越える特別な資源を立案しない。
【００８４】
静止タスク
システムは、直ちに稼動する必要のないタスクであって稼動する必要があるとき容認を否定されないタスクのための時間を予約することができる。そのようなタスクが資源の要求を資源マネージャー５に登録されるまで待つと、タスクセット用の最小時間の和は既に１００％になる（ステップ２３）。次いで、そのタスクを否定するか（ステップ２０）、既に稼働中のタスク（第１の原理の１つに違反するタスク）を切り離す。これの代わりに、静止させることを実際に希望しているときにタスクを適宜なアイドル・ループに回してもよい。しかし、これは他の第１の原理に違反し、それらを使用することができるタスクがあると、機械時間の１００％を使用することになる。
【００８５】
この課題は、静止タスクの観念を導入することにより解決することができる。開始時、このタスクは、通常のように資源マネージャーに登録する（ステップ２２）。その資源リスト２１は、それが実際に稼動しているとき必要な時間に匹敵し、静止状態のために特別にはエントリーしない。その最小必要条件は、容認のために使用してもよい。資源マネージャーへの呼び出しのアーギュメント(argument)は静止タスクを確認し、そのタスクはシステムに一回容認されると一時停止される。
【００８６】
休止は、静止と本質的に異なる。休眠（ブロック）が周期的タスクとして実際にスケジュールをされないタスク、以下に記載するスポラディック・サーバ(Sporadic Server)は、休眠タスクのスケジュールをすることができるが、プロセッサ資源分配機はブロッキングをされている多くの期間においてタスク用の保証スケジュールを作成することができない。静止タスクは、資源マネージャーを介して配分される１つであるが、静止の間スケジュールをされない。
【００８７】
タスクが外部事象により静止から目覚めさせられると、保証は再計算されるが、容認制御作業は既に行われている。静止タスクが立ち上がると、他のタスクは、次の期間に新たに目覚めさせられたタスクを稼動させるべく不十分な時間であるより小さい許可を与えられる（ステップ２９）。しかし、容認制御式のために利用可能の時間にふさわしい許可セットが保証される。
【００８８】
許可セットを再構成しかつタスクを浮遊させる資源マネージャーに対する呼び出しにより（あるタスクが稼動できるように）静止タスクを静止状態に戻してもよい。
【００８９】
正常タスクの例：ＭＰＥＧ２ビデオ・デコーダィング
ＭＰＥＧ２ビデオ・デコーディングは、正常タスクの一例である。これは、ＭＰＥＧ標準により規定されたフレーム・リフレッシュ・レートである３０ミリ秒の期間を有する。本実施例で使用されるプロセッサにおいては、プロセッサ時間のほぼ３３％がこのタスクに使用される。
【００９０】
ＭＰＥＧにおけるコーディングには、非常に異なる利用性を有する改良された３種のフレームが用いられる。最初のフレーム(I)は、最小の圧縮を有しており、最小のプロセッサ時間を必要とする。Ｐフレームは、Ｉフレームから計算され、中間のフレーム時間を必要とする。Ｂフレームは、前の一対のＩ又はＰフレームから計算され、多くのプロセッサ時間を必要とする。ＢフレームとＩフレームとの相対的なプロセッサ時間は、ほぼ２対１である。Ｉフレームが計算されないときは、次のＩフレームを受けるまで１／２秒であるが、最新化をすることができない。Ｂ及びＩフレームが下げられると、多くの負荷が排除され、ユーザーは１／２秒の異常を経験する。
【００９１】
異種のビデオ標準はＭＰＥＧフレームの異なる組み合わせを必要とするが、表示装置はフレームの種類のランダムな選択を含むことができる。例えば、(IPBBPBBPBBPBBPB)(繰り返し)の次数におけるＭＰＥＧフレームを減らすことが必要な標準を考慮する。ＭＰＥＧタスク用の時間リストの一例を表４に示す。
【００９２】
【表４】
0004174178.tif 000007
表４：ＭＰＥＧビデオ・デコーディングで可能な資源リスト
フレームの負荷切り離し：１／４，１／３又は１／５
【００９３】
過負荷にならないシステムにおいては、最良の資源リスト・エントリーが使用され、満杯の圧縮を与える。過負荷状態においては、ユーザーは毎秒数フレームを見る選択を有する。負荷制限選択の存在は、真の感覚において受け入れられるような視界状態を提供しないが、有意義な選択肢ある。
【００９４】
この資源リストは全フレームが同じ方法で圧縮解除されるＭＰＥＧタスクの要求を含み、単一フレーム内の利用性を変更する必要はない。より短い期間を有する他のタスクがあるならば、そのタスクがある機能で呼び出されるとき、最も短い期間でさえ先取りされるように確かめられる。それらは異種の直交法であり、最適な先行取得が発生するとき調整するように使用することができる。このことは後により詳細に言及される。
【００９５】
ＭＰＥＧタスクがある理由のめにその許可を超過すると、それは許可され、次の期間の通知を受ける。フレームの種類に応じて制御を回復しているとき行われるアクションは、圧縮されている。そのタスクがＢフレームであると、それを下げるように選択され、次のフレームに継続する。タスクがＩフレームであると、それを終了し、次のＢフレームを下げるように特筆されるであろう。正しいものはどれでも、ＭＰＥＧタスクはその決定をする。タスクが一貫してその許可を超過していると、その資源リスト内の機能と関連する利用性の要求を変更することが必要になる。
【００９６】
休止タスクの例：電話への応答
ユーザーは、電話に応答し電話をかけた人とのモデム接続を確立するタスクを有することができる。電話が鳴るまで、そのタスクにはすることがない。電話が鳴ると、タスクは接続をしてそれを維持するに充分なプロセッサ時間を配分されなければならない。
【００９７】
配分の見込みがあるので、このタスクは稼働したいときに容認制御が容認を拒否することができないタスクである。実際、そのためには時間を取っておく必要がある。休止タスクでのみこれを行うことができる。
【００９８】
電話が鳴る前のいつでも、電話応答タスクは資源マネージャーに、稼働中の最小要件を確立して登録する。電話がかかって操作系がタスクを起動させるまでそれは中断している。資源マネージャーは、許可セットを再計算するが、容認制御アルゴリズムのため運転可能なスケジュールを見つけることを保証されている。電話応答タスクが稼働していない場合、その時間は、装置内の他のタスクにより高いレベルのサービスを提供するために利用率することができる。
【００９９】
処理超過時間：負荷移行
許可配分方法及びスケジュール作成は、期間毎に必要な時間が比較的一定である場合に行われるのが理想的である。ＭＰＥＧやオーディオ等いくつかの周期的なタスクは、このモデルに非常によく適合する。処理要件が、画面上の画素数のように、決まった数値によらず、１シーンにおけるポリゴンの数のように非常に変化しやすい数値による、３Ｄのような他のタスクもある。大抵の３Ｄタスクは、この課題を制限しようとするポリゴン・バジェットを有するが、フレーム毎に５，０００から１０，０００ポリゴンを有する現行のバジェットは、いまだに２：１の処理能力の偏差を残している。
【０１００】
３Ｄアプリケーション設計者が１０，０００ポリゴンを処理するに充分な配分を要求しても、この数を超えるフレームがまだあり得る。また、もちろん、フレームの大部分は、５０００ポリゴンしか使用しないならば、３Ｄに残しておいた処理容量の約半分が浪費される。
【０１０１】
この課題にアドレスするために、負荷移行の観念が発明された。多数の装置は、タスクが負荷を下げること、多分、１フレームのための計算の途中で部分的に処理されたポリゴンを下げること、を予期している。そのような脱負荷に加えて、限られた持続時間に１つのタスクから別のタスクへ時間の変換を制御されている負荷移行をも許されている。このため、別のタスクの処理能力を損なわずに、必要に応じて余分の時間を利用率できるようにする一方、正規の条件で３Ｄのようなタスクに時間量をより少なく配分することが可能になる。
【０１０２】
負荷移行の可能性は、先ずポリシー・ボックス９に指示される。タスクのセットがつながれ、１つのタスクがその許可を超えるかも知れないことを表示する。超過の事象においては（既に過ぎたか予期されるか、いずれか一方）、スケジューラ４はこの１つの期間にセットのうちの他のタスクから超過したタスクへと時間を移行することができる。この期間に、時間を寄付したタスクは、それらが与えられようとしていた時間量よりも少ない時間、すなわちそれらの現行の許可より少ない時間に関連するコールバックを受ける。寄付するタスクに与えられる時間は、なおもその資源リストに挙げられた時間であり、もしそのタスクがこの期間に既に稼働を開始して強制排除されてされていれば、寄付行為をしているタスクへの配分を変えることはできない。このため、図４のステップ６１及び６２に示すように、３Ｄのようなタスクにとって、もしそれが超過する期間での利用率における非常に早い時期に報告することができれば、非常に効果がある。利用率はこの期間の始期に知られていた処理されるポリゴン数の直接のファンクションであるから、これは３Ｄにとってかなり些細なことである。
【０１０３】
負荷移行が実行されるか否かは、ポリシー・ボックスによって管理される。負荷の移行は、ユーザーによって無効にされてもよく、あるいは、負荷を移行する新しいタスクのセットを追加してもよい。
【０１０４】
非周期的タスク(Non-Periodic Tasks)
最も単純な形式のプロセッサ資源分散装置によって期待される周期的な高度な呼出時間モデルに、完全には適合しないタスクもある。これには非周期的タスクや、呼出時間の必要性が非常に低いタスクが含まれる。このいずれかの特徴を持つタスクは、異なる方法で取り扱われる。
【０１０５】
非周期的タスク(Aperiodic Tasks)
非周期的のタスクは、本来の周期を持たない。休止タスクは、この一例と考えてよい。但し、実施例においては休止タスクを休止状態のときでなく稼働しているときの動態によって特徴づけられている。非周期的の休止タスクもあり得るが、ほとんどの休止タスクは周期的である。非周期的モデルは、タスク作成及び他の予告できない家政タスクの支援に使用することができる。
【０１０６】
非周期的タスクは、散発的なサーバーによって取り扱われる。散発的なサーバーは、作業に待ち行列をチェックしながら非常に少ない利用率で周期的に稼働する。作業が可能な場合、サーバーは許可をさらに増やすよう資源マネージャー５に連絡して要求する。周期的なサーバーのための資源リストへの最小エントリーは、図４のステップ５０に示すように、散発的なサーバーがアイドル状態であるが、なすべき作業のチェックをしているモードに使用される。作業が到来すると、同じ最小のエントリーを有するが利用率の増大を要求するエントリーも有する新しい資源リストが、資源マネージャーに提示される。装置が過負荷になると、散発的なサーバーに許可が与えられ、サーバーはその許可を非同期的な作業をするために使用する。作業が完了し、待ち行列が空になると、散発的なサーバーは、資源リストに最小なエントリーだけをして資源マネージャーを再度呼び出す。
【０１０７】
散発的なサーバーのもとで稼働中のタスクのために実現される最良の呼出時間は、新しい許可を実施するのに要する時間量のファンクションである。最悪の成功例においては、これはすべての未使用の許可期間の合計である。唯一の非同期タスクが装置内にある場合でも、最悪の例は、許容制御が新しい資源リストへのエントリーを拒否することである。これは、装置が過負荷になり、かつすべての稼働中のタスクが散発的なサーバーより優位にされることをポリシー・ボックスが表示した場合にのみ生じる。そのようなポリシーは、ユーザーにより修正されることができる。
【０１０８】
低呼出時間及び高周波タスク
プロセッサ資源分散装置が支援できる最小呼出時間の一部は、文脈切り換えに要する時間で決定される。それはまた、過剰データ通信量を避けるべく、強制排除と強制排除の間で稼働している通常のタスクの最小単位時間によって、間接的に制限される。（例えば、データはタスクの１つの位相でしばしばアクセスされるが別の位相ではアクセスされないようなキャッシュの中にあってもよい。理想的な文脈切り換え時間は、この２つの位相の間にある。）。
【０１０９】
プロセッサ資源分散装置は、およそ５００マイクロ秒の粒度を提供する。しかし、毎秒１０００回（または２０００回より多い場合さえある）より多い回数で稼働する必要のあるタスクもあり、それにはこの機構は作動しない。明らかに、毎秒１０００回より多く稼働するタスクは、反復毎に１ミリ秒より少なく使用している。これらは低呼出時間、高周波タスクである。一例は、オーディオ・コマンド・ストリームの代わりに発生するＤＭＡ割込みであり、毎秒２８００回又は８０００回も割り込むことがあるが、各反復に対して少しの命令しか実行されない。さらに、これらの事象に応答する呼出時間要求は、ほんの１マイクロ秒程度である。
【０１１０】
これらのタスクは、文脈切り換えの時間自体が装置を過負荷にすることが度々あるので、中断ハンドラとして稼働される。中断ハンドラは、完全な文脈切り換えを行わず、中断レベルで使用できる記録器セットも同様に制限される。スケジュール作成のために、プロセッサの幾分かの量が中断処理に保留されている。この量を、どのタスク・セットが稼働されるかによって増加したり減少したりする。これは、プロセッサの１００％使用という当社の目標を僅かに損なうが、これらのタスクはそれ自体の待ち時間の必要性より少ない利用率を持たなければならないので、全利用率はあまり大きくない。
【０１１１】
静的及び動的タスク・セット：  レガシー・アプリケーション
プロセッサ資源分散装置は、タスクが起動するとき容認制御を行う能力に依存する。これがなければ、稼働が継続できるように、又はどのタスクが首尾良く稼働するかに関するポリシーをユーザーが安心して損なうことができるように保証をすることができない。
【０１１２】
如何なるタスクも最後にはドライバを介する要求を開始しなければならないので、ウィンドウズの環境において、またセット最上ボックスの環境においてこれが行われている。
【０１１３】
ＤＯＳ環境においては、これらの保証をしていない。ＤＯＳ環境には、ハードウエアの端子対に直接アドレスすることができると期待するレガシー・アプリケーションがある。ドライバ又は他のＯＳ・ＡＰＩを介して行われるセットアップはない。プロセッサは、ＤＯＳボックスにおいてプロセッサ・ドライバに予めロードすることにより、これらのアプリケーションを支援する。また、可能な各タスクのために資源リストを予めロードすることができる。容認制御は、操作系ロード時間に静的に効果的に行われる。初期許可セットは、すべての予めロードされたデバイスが稼働していると推測することを予め設定されている。ウィンドウズがＤＯＳのトップにロードされていれば、この配分とスケジュールは、動的に作成され且つその作成とタスク削除を調整できるものと差し替えられることに注目してほしい。
【０１１４】
許可条件
タスクに許可が与えられるとき、装置は特別な保証を与えられている。プロセッサ利用率の許可のため、装置は許可された量のプロセッサ時間が各指定期間にタスク配分されることを約束する。一例として、３Ｄグラフィックスは、各１４ミリ秒のうち７ミリ秒を配分されてきた。１４ミリ秒毎に３Ｄグラフィックスは７ミリ秒を与えられるであろう。この７ミリ秒は、期間の始まりに来てもよいし、期間の終わりに来てもよい。あるいは、数個の部分に分割されタスクがそれらの間に強制排除されていてもよい。タスクに時間が配分されずに過ぎることのできる最長時間は（２＊期間−２＊利用率）である。このタスクに関しては、２８−１４＝１４ミリ秒である。このタスクは、この例を処理するに充分なバッファリングを有することが必要である。
【０１１５】
降伏(Yielding)
この装置の周期的なタスクについての推測の１つは、排除要求に応じる以外に、この期間に作業を終了するまでプロセッサに降伏しない（ブロック）ということである。それらタスクは、外部の事象を待つことをブロック（妨害）しない。散発的サーバーの文脈で稼働する非周期的タスクは、いつでもブロックする可能性がある。タスクは、起動されると、散発的サーバーの作業待ち行列に配置され、その待ち行列上に配置されたものとして実行される。
【０１１６】
非周期的タスクが閉塞すると、この期間に対するその許可の残部を受けることが期待できない。問題は、容認制御の保証が、プロセッサ時間のすべてのミリ秒を装置が使用できると当てにしていることである。１つは３毎に１ミリ秒（３３％の率）を、他は１０語とに５ミリ秒（５０％の率）を許可されてきた。利用率全体で僅かに８３％である。
【０１１７】
ここで、１つの事象を待つ１ミリ秒の後、１０ミリ秒のタスクがプロセッサを明け渡し、その事象が７ミリ秒で戻るときに稼働を続けることができるとしよう。３ミリ秒のタスクは、ミリ秒１で、また再びミリ秒４で稼働する。理論的には、一旦事象が戻ると、１０ミリ秒のタスクは次の４ミリ秒を７から１０まで使用して、その最終期限を満たすことができる。しかし、３ミリ秒の期間を有する第２のタスクも、それらのミリ秒、７か８か９の１つを使用しなければならない。このスケジュール作成は適合できない。
【０１１８】
ただ１つのタスクで証明される、閉塞に関するより単純な問題がある。そのタスクは、既に過ぎたか、又は残る利用率時間が最終期限までの時間より大きいかのいずれかであるため、最終期限がもはや満たされない場合に起動することができる。
【０１１９】
用語集
容認制御：新しいタスクが稼働を許されるか否かを決定するプロセス。
【０１２０】
非周期タスク：自然の期間を持たないタスク。例えば、短期のユーザー・コマンド要求を実行するタスク。
【０１２１】
較正ループ：どの程度のプロセッサ利用率が必要とされるかを決定するために稼働される資源リストに指定されたファンクションの反復のセット。較正ループの結果は、資源リストの記入に使用できる。
【０１２２】
コンテクスト・スイッチ：プロセッサで稼働しているタスクが、１つから別のものへ切り替えられる時。
【０１２３】
EDF：最早最終期限優先：最も早い最終期限を有する稼働待ち行列上のタスクを次に稼働するよう選択するスケジュール作成手段。単純な状況において、このアルゴリズムは、どの方法ででもスケジュールされる如何なるタスクのセットをもスケジュールすることが可能であると証明されている。
【０１２４】
例外：帯域外通知。例外を受けると、タスクＰＣがその例外ハンドラーに設定される。
【０１２５】
許可：ある（反復）期間についての時間の割り振り。例えば、３０ミリ秒毎に１０ミリ秒のプロセッサ。
【０１２６】
許可セット：装置に許容されたすべてのタスクに対する許可のセット。
【０１２７】
最小記入：最小の利用率率を有するタスクの資源リストへの記入。
【０１２８】
最良記入：最大の利用率率を有し、ユーザーに最高質のサービスを提供するタスク資源リストへの記入。
【０１２９】
始期：周期的なタスクのための次の期間の始まり。
【０１３０】
終期：現行の許可が満了した時点。
【０１３１】
ポリシー・ボックス：ユーザーの望むタスクとサービスの命令を報告するファンクション。どのタスクを稼働させるべきか、またでのレベルの質のサービスかを決定するために装置が過負荷になったとき使用される。
【０１３２】
強制排除：プロセッサが現在稼働中のタスクから取られて別のタスクへ与えられるとき、稼働中であったタスクは強制排除されると言われ、プロセッサからそれを除去する行為を強制排除すると言う。
【０１３３】
サービスの質（ＱＯＳ）：アプリケーションによって提供される質のレベル。アプリケーションは、負荷を下げるとき、より低い質のサービスを提供する。
【０１３４】
休止タスク：装置に容認されたがスケジュール作成にはまだ適格でないタスク。休止タスクは、その期間を放棄している。休止を解かれると、新しい許可セットが計算されるが、容認制御は発生する必要がない。
【０１３５】
資源リスト：所定のタスクにとって意味のある有用な期間と利用率の組み合わせを規定する仕様のセット。過負荷状態のとき、容認制御を行ったり負荷を下げるのに使用される。
【０１３６】
資源マネージャー（資源管理機）：装置においてタスクに時間を配分するためのコード。手段に関し、ポリシー・ボックスが参照される。資源管理装置は、容認制御にも、許可セット決定にも関与する。
【０１３７】
スケジューラ：予め規定されたタスクのセットのうちいずれが次に稼働すべきかを選択すること及びプロセッサ利用率許可を実施することに関与する機能。
【０１３８】
セット最上ボックス：ＰＣではなく、おそらくユーザー・インターフェイスを有し、かつ利用率可能な媒体デバイスを作る非分散型装置。「セット・トップ」とは、テレビジョン・セットの上にあることを指す。
【０１３９】
散発的サーバー：自ら周期的に稼働するタスクであるが、本来は非周期的であるタスクに実行時間を提供するタスク。
【０１４０】
タスク：ユーザーに変わってジョブを行う実行の単一な流れ。例えばＭＰＥＧ復号に関わるタスクは多数あり得る。それらタスク間の同期化はその周期性によって処理される。
【０１４１】
降伏：タスクがプロセッサを断念して休止状態に入るとき。
【０１４２】
上記の実施例は本発明を例示するに過ぎない。これらに代わる多数の実施例が可能である。本発明は、特許請求の範囲によって定義される。
【図面の簡単な説明】
【図１】  プロセッサ資源分配機のスケジューリング構成要素を示すブロック図
【図２】  ３つのタスク用プロセッサ資源分配機のスケジューラにより実行されるサンプル・スケジュールを示す図
【図３】  資源マネージャの操作を示すフローチャート
【図４】  スケジューラの操作を示すフローチャート
【図１】
0004174178.tif 000008
【図２】
0004174178.tif 000009
【図３】
0004174178.tif 000010
【図４】
0004174178.tif 000011