(57)【特許請求の範囲】
【請求項１】
実行可能な複数のタスクが実行のために利用可能であるようなコンピュータシステムでタスクを選択する方法において、
それら実行可能な複数のタスクを含むデータ構造を維持する過程と；
実行可能なタスクのそれぞれに１つの優先順位を関連づけ、タスク優先順位のセットを与える過程と；
前記の実行可能な複数のタスクを含むデータ構造からランダムにタスクの選択をするタスク選択過程であって、タスクが選択をされる確率が、前記タスク優先順位のセットのうちから当該タスクに関連づけられているタスク優先順位に比例するように、タスクの選択をするタスク選択過程と
を備えるタスクを選択する方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明はデジタルコンピュータ、特に、１つ以上のプロセッサによる実行に備えて複数のタスクをスケジューリングするようなデジタルコンピュータのオペレーティングシステムの分野に関する。
【０００２】
【従来の技術】
デジタルコンピュータにおいては、２つ以上のタスクが同時に実行可能な状態になることは一般的である。本体コンピュータ及びミニコンピュータでは、それらのタスクはバッチ処理ジョブと、時分割システムのユーザーと、プリンタへ出力を送信するために使用されるシステムタスクとから構成されると考えることができる。現在、マイクロコンピュータ利用システム、さらにはハンドヘルドコンピュータ利用システムでも、多重タスク処理は適用範囲に入っている。マイクロコンピュータシステム又はハンドヘルドコンピュータシステムのユーザーは、ユーザーのアクションにより指定されている一次タスクのみを承知しているが、他のタスクには電子メール、カレンダサービス、手書き文字認識などの処理機能がある。
【０００３】
多重タスク処理環境においては実行可能であるタスクが２つ以上あるとき、オペレーティングシステムはタスクが１つ以上のプロセッサにより実行される順序をスケジューリングしなければならない。
公知のスケジューリング方法はそれぞれのタスクと優先順位を関連づける。スケジューリング間隔ごとに、最も高い優先順位をもつタスクが実行のために選択される。この優先順位ベースのスケジューリングに関わる問題は、より高い優先順位のタスクが実行のために利用可能である間は、低い優先順位のタスクは実行されないということである。この問題はロックアウトとして知られている。優先順位スケジューリングには変形（強制排除スケジューリング及び短期間のうちに事象に基づいて優先順位に小さな増分を加える方式など、共に以下に説明する）もあるが、それらの方法はロックアウトの問題を解決せず、スケジューリングプロセスを一層複雑にしてしまう。
【０００４】
【発明が解決しようとする課題】
本発明は、ロックアウトの発生を許さない新たな優先順位ベーススケジューリングプロセスを提供することである。
【０００５】
【課題を解決するための手段】
タスクは、タスクの優先順位により重み付けされた乱数に基づいて確率によって実行のために選択される。どのタスクも選択される有限の零でない確率を有しており、その確率はタスクの優先順位に比例するので、本発明は、たとえ優先順位の低いタスクであっても、全てのタスクが選択される機会をもち、それにより、ロックアウトの問題を排除するという利点を有する。
本発明のその他の目的、特徴及び利点は、以下の好ましい実施例の詳細な説明、特許請求の範囲及び添付の図面からさらに十分に明らかになるであろう。
【０００６】
【実施例】
図１は、典型的なコンピュータ利用装置又はシステムのブロック線図である。このシステムは入力装置１２、メモリ階層１４、出力装置１６及びクロックタイマ１８と相互に接続する中央処理装置（ＣＰＵ）１０を含む。ＣＰＵ１０はメモリ１４から取り出した命令を実行する必要があるシステムに含まれるＣＰＵは１つであっても良く、複数であっても良い。典型的な使用状況においては、メモリ１４は階層を成して配列されている。より大形のシステムは、通常、読取り専用メモリ（ＲＯＭ）と、読出し書込み用メモリ（ＲＡＭ）と、普通はディスクドライブの形態をとる補助記憶装置とを有する。小形のコンピュータはＲＯＭ及びＲＡＭのみを含んでいれば良く、拡張に備えて追加のＲＯＭ又はＲＡＭを含むプラグインカードを使用しても良い。クロックタイマ１８はＣＰＵに対する割込みの発生源を構成している。
【０００７】
動作中、ＣＰＵ１０はメモリ１４から命令を取り出す。メモリから取り出した命令によって、ＣＰＵ１０は入力装置１２と出力装置１６を制御し、メモリ１４のデータを操作する。オペレーティングシステムは、コンピュータシステムの動作を制御する１組の命令とデータ構造である。オペレーティングシステムは選択されたユーザータスクを実行することを目的としている。オペレーティングシステムのうち、実行すべきタスクを選択する部分はスケジューラとして知られている。
【０００８】
多重タスク処理オペレーティングシステムでは、１つのタスクは複数の命令とデータの集合体である。スケジューリングプロセスはタスクの操作と選択を扱う。簡略化したモデルにおいては、タスクは２つの状態の一方、すなわち、活動状態又はブロック化状態のいずれかをとると考えられる。１つの状態から他方の状態へのタスクの遷移は事象により駆動される。活動状態のタスクはＣＰＵにより実行可能な状態にある。ブロック化状態のタスクは実行可能ではなく、タスクを活動状態に戻すための何らかの事象が起こるのを待機している。１例として、第１のタスクがデータを実行し、処理しているものと仮定する。タスクは処理を継続するために必要な情報を求めてオペレーティングシステムに対して入力要求を発生する。オペレーティングシステムは入力動作を開始させ、タスクの状態を活動からブロック化へ変化させるためにスケジューラを呼び出す。スケジューラは実行すべき第２のタスクを選択する。第１のタスクに関わる入力動作が完了したとき、スケジューラは第１のタスクの状態をブロック化から活動へ再び変化させる。
【０００９】
公知の単純なスケジューラはラウンドロビンスケジューラである。この種のスケジューラは単純にそれぞれ活動状態にあるタスクを順に選択し、各タスクに等しい重みを与える。ラウンドロビンスケジューリングの場合にはロックアウトは起こらない。スケジューリングは、オペレーティングシステムに対して実行中のタスクが要求を発生した結果として始まるか、あるいは、タイマの割込みに基づいて定期的にスケジューリングが開始されるかのいずれかであろう。
【００１０】
優先順位に基づくスケジューリングは、いくつかのタスクが他のタスクより重要であることを認識する方法として知られている。たとえば、銀行業務システムにおいては、銀行用端末装置にいたるデータ通信回線を処理するタスクはチェックを処理するバッチジョブと比べてより重要であり、より高い優先順位を有する。すなわち、銀行用端末装置での顧客は迅速な応答を要求するが、バックグラウンドチェック処理はそれと同様の時間の制約を受けていない。複数の時間を共用するユーザーを表すタスクと、バックグラウンドバッチジョブとを有し、プリンタへデータを転送している従来の時分割システムでは、それぞれが入力した要求に対する迅速な応答を要望する時間共用ユーザーに高い優先順位を割当て、ほとんど時間をとらないプリンタタスクにより低い優先順位を割当て、まだ利用可能な残ったＣＰＵの時間を使用できるバックグラウンドバッチタスクに低い優先順位を割当てることになるであろう。語処理などの主ユーザーアクティビティを表わすタスクと、プリンタ制御、遠隔データ転送及び電子メールなどのバックグラウンドタスクとを有するパーソナルコンピュータシステムにおいては、語処理アクティビティに最高の優先順位を与え、バックグラウンドタスクには低い優先順位を与えることになるであろう。スケジューラソフトウェアはタスクを追跡し、次に実行すべきタスクを選択する。
【００１１】
通常、スケジューラは活動タスクの待ち行列と、ブロック化タスクの待ち行列とを保持する。図２は、優先順位ベーススケジューラに関わる活動タスク待ち行列を表わす図である。概略的に示したデータ構造は当該技術では良く知られている。使用するプロセッサのアーキテクチャに応じて、それらのデータ構造を制御ブロック（図示したもの）として編成するか、又はテーブルとして編成することが可能であろう。図２の活動タスク待ち行列は二重連係リストを使用して示されている。活動待ち行列見出し２０は待ち行列の最終要素に向かう逆方向リンク２１と、第１のタスク待ち行列ブロック２４に向かう順方向リンク２２とを含む。各タスク待ち行列ブロック２４も先行要素に向かう逆方向リンク２１と、待ち行列の次の要素に向かう順方向リンク２２とを含む。明瞭を期するために、順方向リンク２２を図示し、逆方向リンクを省略してある。各タスク待ち行列ブロック２４は、オペレーティングシステムに対するタスクを識別するために使用される一意のタスクｉｄ２５をさらに含む。各タスク待ち行列ブロック２４はタスク優先順位２６をさらに含む。タスク待ち行列ブロック２４は、タスクの実行を延期し、異なるタスクへ切り替え、後に、オペレーティングシステム及びＣＰＵによる要求に応じてタスクの実行を再開するための追加タスク文脈データ２７をさらに含む。二重連係リストにより、待ち行列へのエントリの挿入、待ち行列からの除去及びエントリの再位置決めに際して周知の技法を効率良く使用することができる。
【００１２】
優先順位ベーススケジューリングを採用し、活動タスク待ち行列を優先順位の順に保持した状態で、スケジューラは単純に実行すべき活動タスク待ち行列中の第１のタスクを選択する。動作中、図２に提示した情報を使用する優先順位ベーススケジューラはｉｄ＝１且つ優先順位＝１４であるタスク２４ａを実行させると考えられる。このタスクは、別のタスクの優先順位をそのタスクのレベルを越えるまで上げ、そのタスクの優先順位を別のタスクの優先順位より低くなるまで下げるか、あるいは、タスクを活動状態からブロック化状態へ変化させる何らかの事象が起こるまで、実行を継続するであろう。タスク２４ｂ、２４ｃ及び２４ｄはロックアウトされ、そのような何らかの事象が起こるまで実行されない。
【００１３】
スケジューリングプロセスには２つの段階がある。一方の段階は事象の報告を含み、他方の段階は実行すべきのタスクの選択を含む。事象の報告の結果、タスクの優先順位と状態は変化する。それらの事象はタスクの優先順位の変化をもたらすかもしれないので、通常は実行すべきタスクの選択は事象報告に続いている。従って、スケジューリングプロセスは事象によって開始されるとみなして良い。スケジューリングプロセスを引き起こす事象の１つの種類は、オペレーティングシステムに対する呼び出しである。
【００１４】
例えば、タスクが入力要求の完了までそのタスクの実行を延期すべきであることを指定する入力要求を発生する場合、そのタスクの状態を活動からブロック化へ変化させ、次に、実行すべき活動タスクを選択するために、スケジューリングを呼び出す。
スケジューリングプロセスを呼び出す別の種類の事象は、入出力動作の完了や、バッファが空又は一杯になるなどの入出力事象である。たとえば、タスクが非常に急速にデータを生成しており、そのデータを出力バッファを介して相対的に低速の出力装置へ送信している場合、出力バッファが一杯になったならば、出力バッファに空きができるまで、そのタスクをブロック化する。空きが利用可能になった時点で、タスクを再び活動状態にすることができる。
【００１５】
スケジューリングを呼び出すために使用されるもう１つの事象はタイマ割込みである。オペレーティングシステムは、タイマスライスとして知られるある長さの時間（たとえば、１／６０秒）の中で１回の割込みを発生させるために、ＣＰＵに接続するタイマをイネーブルする。割込みが起こると、ＣＰＵはその現在タスクを実行するのを停止し、割込みをサービスする。この割込みサービスの一部として、オペレーティングシステムはスケジューリングプロセスを呼び出し、その結果、実行すべき別のタスクが選択されるであろう。この種のスケジューリングでは、現在タスクの実行を強制排除し、また、ＣＰＵ時間をスライスとして割当てるので、この方式をタイムスライス形強制排除スケジューリングと呼ぶ。逆に、現在実行中のタスクが別のタスクのスケジューリングを招く何らかの事象を発生させるまで、そのタスクに実行を継続させるスケジューラは非強制排除スケジューラとして知られている。
【００１６】
ロックアウトの問題に対処するために、基本的な優先順位スケジューリング方法に対していくつかの変更が行われている。タイムスライス形強制排除スケジューリングはその１つである。
同じ優先順位をもつ一群のタスクの中でのロックアウトを防止するために、ラウンドロビンスケジューリングも採用されている。この方法の原則は非常に単純である。すなわち、１）タスクを追加するときは、そのタスクをその優先順位グループの先頭に追加し、２）タスクが１つのタイムスライスを完了すると、タスクをその優先順位グループの終わりへ移動するというものである。たとえば、図２に示すケースでは、ｉｄ＝１のタスク２４ａが最初に実行されるタスクになるであろう。所定のタイムスライスが終了したとき、ラウンドロビン方法はタスク２４ａを待ち行列の優先順位グループ１４の終わりへ移動する。図２においては、タスク２４ａはリスト中のタスク２４ｂの後に再び連なり、タスク２４ｂが実行に備えて待ち行列の先頭に出ることになるであろう。次のタイムスライスの終了時には、それらの位置は逆転し、タスク２４ａの実行が再開されるであろう。次々に続くタイムスライスを経て、タスク２４ａとタスク２４ｂは順番に実行される。この方式はロックアウトの問題を解決しない。タスク２４ｃ及び２４ｄは優先順位が低く、実行されないため、それらのタスクは依然として事実上ロックアウトされている。
【００１７】
ロックアウトの問題に対処するもう１つの方式は、事象に基づいて短い間隔でタスクの優先順位に小さな増分を加えるというものである。これを図３に示す。そのようなシステムにおいては、各タスクブロック２４は現在優先順位３２と、基底優先順位３４とを含む。図３に示すように、先に説明したようなラウンドロビン強制排除スケジューラがタスク２４ａと、タスク２４ｂとを交互に実行させると考えられる。増分方式はスケジューリングプロセスに次の規則を追加する。１）タイムスライスの終了時に、現在タスクの優先順位３２を減分するが、優先順位は現在タスクの基底順位３４より低くなるほど落とされることがない。現在優先順位を減分した後、タスクを適切な優先順位群の末尾に配置する。そして、２）スケジューラに報告されるそれぞれの事象はそれと関連する優先順位増分を有するが、その増分は０であっても良い。１つの事象が報告されると、この増分をタスクの現在優先順位に追加し、そのタスクを待ち行列中の、適切な優先順位群の先頭に再び配置する。
【００１８】
ｉｄ＝３のタスク２４ｃについて事象が報告され、この事象が優先順位増分３を伴うものと仮定する。これにより、タスク２４ｃの現在優先順位３２は１２から１５へ上がるので、タスク２４ｃは最も高い優先順位をもつことになるであろう。活動タスク待ち行列２０は、タスク２４ｃを先頭とし、その後にタスク２４ａ及び２４ｂが続く連なりとなるので、実行のためにタスク２４ｃがスケジューリングされることになる。１つのタイムスライスの終了時に、タスク２４ｃの現在優先順位３２は１５から１４に減分し、待ち行列中の、同様に現在優先順位１４を有するタスク２４ａ及び２４ｂの後に再び連なるであろう。そこで、タスク２４ａは１つのタイムスライスで実行されるであろう。そのタイムスライスの終了時には、タスク２４ａの優先順位を減分することができない。それは、減分すると基底優先順位３４より低くなってしまうからである。そこで、タスク２４ａはタスク２４ｂ及び２４ｃの後に再び連なり、タスク２４ｂが実行される。次のタイムスライスの終了時には、タスク２４ｂはタスク２４ｃ及び２４ａの後に再び連なり、タスク２４ｃが実行されることになる。次のタイムスライスの終了時に、タスク２４ｃの現在優先順位３２は１４から１３に減分し、タスク２４ａ及び２４ｂの後に再び連なる。（強制排除タイマ事象以外の）他の事象が報告されないと仮定すれば、タスク２４ａ及び２４ｂは実行を継続し、タスク２４ｃ及び２４ｄは現在優先順位が低いために再びロックアウトされる。
【００１９】
優先順位増分プロセスはスケジューリングプロセスを一層複雑にする。事象ごとに優先順位増分を割当てなければならず、それらの増分がわずかに変化しても、システムの動作や性能に著しく影響を及ぼす可能性がある。さらに、ロックアウトの問題は優先順位増分プロセスによっては解決されない。
【００２０】
図４は、本発明の第１の実施例により使用されるデータ構造を概略的に示す。本発明は、タスクの優先順位に基づき確率方式によりタスクを選択することにより、優先順位ベース方式を維持しつつロックアウトの問題を解決する。活動待ち行列見出し２０はタスク待ち行列ブロック２４から成る二重連係リストの先頭である。各タスク待ち行列ブロック２４はタスクｉｄ２５と、タスク優先順位２６と、タスクデータ２７とを含む。変数Σprio４０は活動タスク待ち行列の中の全てのタスクのタスク優先順位２５の和を保持する。タスクの挿入又は除去によって活動タスク待ち行列が変更されると、活動タスク待ち行列中の全てのタスクのタスク優先順位２５の和を表わすために、変数Σprio４０を更新する。図４に示す構造の場合、この値は４３である。本発明のスケジューリングプロセスは１からΣprioを含めた値までの範囲で、従って、１から４３までの範囲の中で１つの任意の整数を生成し、この整数を使用して、実行すべき次のタスクを選択する。
【００２１】
従来、線形合同擬似乱数列発生器などの周知の方法や装置を使用して、ランダム整数を効率良く発生させることができる。数列の現在整数値がｒｎ  であるとすれば、数列中の次の整数値ｒｎ＋１  はｒｎ＋１  ＝（ａ＊ｒｎ）ｍｏｄ  ｋとして計算される。当該技術で良く知られているように、定数ａと、数列の初期シード値とを慎重に選択しなければならない。乗算は基底をＫとしてモジュール方式で実行されるが、この基底は計算を容易にするために２の累乗に関連づけられている。たとえば、ｒｎ＋１  ＝（１６８０７＊ｒｎ  ）  ｍｏｄ２３１−１は一様数列を生成する。
【００２２】
適正な範囲内でランダム整数を与えて、優先順位の和が生成した値以上になるまで、タスクの優先順位を加算しつつ活動タスク待ち行列をたどってゆく。そのたどりプロセスの間にこの条件を満たすタスクが実行すべきタスクである。タスク待ち行列にタスクを追加し、また、待ち行列からタスクを除去するときに、値Σｐｒｉｏを維持することができるが、あるいは、スケジューリングプロセスの間に待ち行列をさらに通過してゆき、タスク優先順位を加算することにより、値Σｐｒｉｏを再生成することも可能である。
【００２３】
図４に示す例では、タスク選択のために生成されるランダム整数は３３であると仮定する。タスク待ち行列をたどるときは、タスク２４ａから始まる。タスク優先順位の和はこの時点では１４であり、１４は３３より小さいので、タスク２４ａは選択されない。次のタスク２４ｂに移ると、優先順位の和は２８（１４＋１４）になり、これも３３より小さいので、タスク２４ｂは選択されない。次のタスク２４ｃへ移ると、優先順位の和は４０（１４＋１４＋１２）になり、これは３３より大きいので、タスク２４ｃが実行すべきタスクとして選択される。
【００２４】
あるいは、タスク待ち行列をたどり、タスク優先順位を加算する代わりに、タスク待ち行列をたどりながらランダム整数を現在タスク優先順位だけ減分し、０に対して試験することも可能である。多くのコンピュータにおいて、値が０以下であるかどうかをみるために試験することはより効果的である。図４を利用して説明すると、この待ち行列たどり方法において、タスク選択のために生成されるランダム整数は３３であると仮定する。タスク待ち行列をたどるときには、タスク２４ａから始まる。タスク選択値３３からタスクの優先順位１４を減算する。その剰余は１９であり、これをタスク選択値として戻し、記憶する。この値は０より大きいので、タスク２４ｂから待ち行列をたどり続ける。タスク２４ｂの優先順位は１４であり、この値を１９から減算すると、その剰余は５となる。５は０より大きいので、タスク２４ｃへとたどり続ける。タスク２４ｃの優先順位は１２であり、これを５から減算すると、剰余は−７になる。−７は０より小さいので、タスク２４ｃは実行すべきタスクとして選択される。
【００２５】
図５は、本発明の動作をグラフの形態で示す。適切に設計された擬似乱数列発生器の出力は統計的に見て均一であるので、時間の経過に伴って１から４３までの全ての整数値が同様の頻度をもって現れ、従って、与えられたタスクの全てが実行のために選択される。与えられるどのタスクについても、そのタスクが選択される確率はそのタスクの優先順位に比例する。図５において、数直線５０は０からΣｐｒｉｏ（活動タスク優先順位の和）、ここでは０から４３の範囲の整数を示す。さらに、各タスクのスパンも示されており、各スパンはタスクの優先順位と等しい。優先順位１４のタスク２４ａに関連するスパン５２ａは１から１４までの範囲である。優先順位１４のタスク２４ｂは、１５から２８までのスパン５２ｂを有する。優先順位１２のタスク２４ｃは、２９から４０までのスパン５２ｃを有する。優先順位３のタスク２４ｄは４１から４３までのスパン５２ｄを有する。１から１４までの範囲にある生成ランダム整数はタスク２４ａを選択し、２５から２８の範囲にあるときはタスク２４ｂを選択し、２９から４０の範囲にあるときはタスク２４ｃを選択し、４１から４３の範囲にあるときはタスク２４ｄを選択する。時間の経過につれて、１つのタスクが実行されるＣＰＵ時間の量はその優先順位に比例し、ロックアウトされるタスクは全くない。限界に至ると、時間が増すにつれて、タスクが実行するＣＰＵ時間の量はタスク優先順位をΣｐｒｉｏで除算した値に近づく。図５では、Σｐｒｉｏは値４３を有する。優先順位１４をもつタスク２４ａが実行されるＣＰＵ時間の量は１４／４３、約３２．６％に近づく。優先順位１４のタスク２４ｂが実行されるＣＰＵ時間の量は１４／４３、約３２．６％にほぼ等しい。優先順位１２のタスク２４ｃが実行されるＣＰＵ時間の量は１２／４３、約２７．９％に近づく。優先順位３のタスク２４ｄが実行されるＣＰＵ時間の量は３／４３、約７％に近づく。
【００２６】
図６は、図５のパラメータを使用した本発明のモデルを示す。このモデルは、Ａｐｐｌｅ  Ｍａｃｉｎｔｏｓｈを含む数多くのコンピュータシステムで利用可能である。Ｗｏｌｆｒａｍ  Ｒｅｓｅａｒｃｈ，Ｉｎｃ．が刊行した言語Ｍａｔｈｅｍａｔｉｃａで書かれている。図７は、このモデルをＡｐｐｌｅ  Ｍａｃｉｎｔｏｓｈ  ＩＩ    でランさせた場合の出力を示し、その性能を論証している。
まず、図６について説明すると、縦棒の左側の行番号は単に参照を助けるためのであり、モデルの一部ではない。行１から５はグラフ作成機能ｌｐｌｏｔを規定している。この機能は引数として作図すべき点のリストと、グラフの名称と、作図すべき漸近線の値とを取り出す。行６は累算すべきサンプル点の数として変数ｎを規定しており、この場合、ｎは１０００である。行７は変数ｔ１，ｔ２，ｔ３及びｔ４を規定し、それらを０に初期設定する。変数ｔ１はタスク１が選択される回数を含む。変数ｔ２はタスク２が選択される回数を含む。変数ｔ３はタスク３が選択される回数を含む。変数ｔ４はタスク４が選択される回数を含む。行８は、作図データを保持するために使用される４つのリストｐ１，ｐ２，ｐ３及びｐ４を初期設定する。行９は、サンプル点ごとに繰り返されるループを開始する。行１０は変数ｊに１から４３まで（４３を含む）の範囲のランダム整数を割当てる。行１１から１４は、変数ｊのランダム整数に基づいて、各タスクが選択される回数をカウントする。図５も参照して説明すると、ランダム整数ｊが１から１４の範囲にあるとき、図５では２４ａと記されているタスク１を選択し、この選択を表わすために変数ｔ１を増分する。行１５及び１６は、図７のグラフで使用するための、各タスクが実行された時間のパーセンテージを計算する。データ点ごとに時間のパーセンテージは、タスクが選択された回数（変数ｔ１，ｔ２，ｔ３及びｔ４に保持されている）をサンプル数ｉで除算した値に等しい。行１８から２１は図７に示すグラフを生成する。
【００２７】
図７は、図６によりモデル化した本発明の性能をグラフで表わし、各タスクが時間の経過につれて使用するＣＰＵ時間のパーセンテージを示している。優先順位１４をもつタスク１についてグラフに示すように、ＣＰＵ時間はグラフには水平の実線として示されている３２．７％の計算値に急速に近づく。同様に、同じ優先順位１４をもつタスク２は３２．７％に急速に近づき、優先順位１２のタスク３は２７．９％に急速に近づき、優先順位３のタスク４は７％のＣＰＵ経時使用量に急速に近づく。これらのグラフは、本発明が優先順位に基づいてタスクをスケジューリングし、優先順位の低いタスクをロックアウトしないことを示している。
【００２８】
図５の実施例は、選択を実行するために活動タスク待ち行列の直線的探索を要求する。待ち行列の中に多数のタスクが入っている場合には、この直線的探索は長い時間を要するようになる。図８は、待ち行列の中に数多くのタスクがあるときに待ち行列をたどるのに要する時間を短縮する本発明の第２の実施例を示す。１つの直線的リストの中で活動待ち行列見出し２０に全ての活動タスクを連ならせるのではなく、タスクをそれぞれが副待ち行列見出し６２を有する副待ち行列にグループ分けする。それぞれの副待ち行列見出し６２はセルΣｌｉｓｔ６４を含み、これはその副待ち行列に入っている全てのタスクに関わる優先順位の和である。副待ち行列見出し６２は、それぞれのタスク待ち行列ブロック６６に至る順方向リンクと、逆方向リンクとを含むタスク待ち行列見出し６５をさらに含む。図表を明瞭にするために、順方向リンクのみを示してある。全てのΣｌｉｓｔ６４セルの和は、全タスクの優先順位の和であるΣｐｒｉｏ６０として保持されている。副待ち行列の中ではタスクは何らかの特定の順序である必要がない。
【００２９】
図８の実施例では、まず、スケジューリング基準に適合する１つの副待ち行列を選択するために副待ち行列見出し６２をたどり、次に、その副待ち行列をたどって特定のタスク待ち行列ブロック６６を選択し、図５の実施例のように選択されるタスク到達するために全てのタスク待ち行列２４をたどらないので、図８の待ち行列たどりプロセスは図５の実施例の場合より速い。
【００３０】
たとえば、図８において、タスク選択のために生成されるランダム整数は８１であると仮定する。たどるときには、副待ち行列見出し６２ａから始める。この時点での優先順位の和は４０であり、４０は８１より小さいので、選択すべきタスクは副待ち行列６２ａの中にはない。次の副待ち行列見出し６２ｂに移ると、優先順位の和は５４（４０＋１４）であり、これは８１より小さいので、選択すべきタスクは副待ち行列６２ｂの中にはない。次の副待ち行列見出し６２ｃに移ると、優先順位の和は６６（４０＋１４＋１２）であり、これは８１より小さいので、選択すべきタスクは副待ち行列６２ｃの中にはない。次の副待ち行列見出し６２ｄへ移ると、優先順位の和は９２（４０＋１４＋１２＋２６）であり、これは８１より大きいので、選択すべきタスクは副待ち行列６２ｄの中にある。副待ち行列見出しブロック６２ｄの中のタスク待ち行列見出し６５をたどると、タスク待ち行列ブロック６６ｄに至る。この時点での優先順位の和は７５（４０＋１４＋１２＋９）であり、これは８１より小さいので、実行すべきタスクとしてタスク６６ｄは選択されない。タスク待ち行列ブロック６６ｅへ移ると、優先順位の和は８２（４０＋１４＋１２＋９＋８）であり、これは８１より大きいので、実行すべきタスクとしてタスク６６ｅが選択される。
【００３１】
図８の変形は、副待ち行列見出し６２に連係するタスクの数のカウントをその副待ち行列見出し６２の中に保持しておくものであると考えられる。これにより、タスク待ち行列ブロック６６ｃ及び待ち行列見出しブロック６２ｃにより示すように、副待ち行列見出し６２に連係するタスク待ち行列ブロック６６が唯一つしかないケースを処理するために、特定の符号化が可能になる。これは最も短い副待ち行列に新たなタスクを追加するプロセスをも簡略化するであろう。
【００３２】
開示したように、本発明はロックアウトの問題を排除する優先順位ベーススケジューラを提供する。本発明の付加的な利点としては待ち行列の管理が簡単になるということがある。タスクを優先順位の順に追加したり、優先順位の順に保持しておく必要はない。タスクの優先順位はかわらないので、タスクを待ち行列の中の新たな優先順位位置に再び連ならせる必要はない。
【００３３】
本発明をコンピュータシステムに関連して説明したが、本発明は、実行のために複数のタスクをスケジューリングしなければならないどのようなコンピュータ作動装置に適用されても良い。本発明を特定の実施例に関連して説明したが、本発明の真の趣旨から逸脱せずに様々な変更を実施して良く、要素を等価の物と置き換えても良いことは当業者には理解されるであろう。加えて、本発明の本質的な技法から逸脱せずに数多くの変形を実施しうるであろう。
【図面の簡単な説明】
【図１】典型的なコンピュータシステムのブロック線図。
【図２】優先順位ベーススケジューリングシステム（従来の技術）に関わるデータ構造を示す図。
【図３】変形した優先順位ベーススケジューリングシステム（従来の技術）に関わるデータ構造を示す図。
【図４】本発明に従ったデータ構造を示す図。
【図５】本発明の異なる表示を示す図。
【図６】本発明の１つのモデルを示す図。
【図７】図６のモデルの性能を示す図。
【図８】本発明の第２の実施例を示す図。
【符号の説明】
２０  活動待ち行列見出し
２１  逆方向リンク
２２  順方向リンク
２４  タスク待ち行列ブロック
２４ａ〜２４ｄ  タスク
２５  タスクｉｄ
２６  タスク優先順位
２７  追加タスク文脈データ
４０  可変Σｐｒｉｏ
６０  Σｐｒｉｏ
６２ａ〜６２ｄ  副待ち行列見出し
６４  セルΣｌｉｓｔ
６５  タスク待ち行列見出し
６６ａ〜６６ｆ  タスク待ち行列ブロック
【図１】
0003578780.tif 000002
【図２】
0003578780.tif 000003
【図３】
0003578780.tif 000004
【図４】
0003578780.tif 000005
【図５】
0003578780.tif 000006
【図６】
0003578780.tif 000007
【図７】
0003578780.tif 000008
【図８】
0003578780.tif 000009