(57)【特許請求の範囲】
【請求項１】
複数のプロセッサ装置に、実行させるスレッドを割り当てる処理をコンピュータに機能させるスケジュール制御プログラムにおいて、
コンピュータを、
スレッドの実行時に実行開始時刻及び実行するプロセッサ装置の識別情報を記憶するスレッド情報記憶手段、
中断中の前記スレッドを次に実行させるプロセッサ装置へ割り当てる際に、前記実行開始時刻からの経過時間を算出する経過時間算出手段、
前記プロセッサ装置で使用するキャッシュメモリに対して次数が高いほど大きな時間パラメータを設定し、前記経過時間を、１次のキャッシュメモリの時間パラメータから、次数が高いキャッシュメモリの時間パラメータへと順に比較していき、前記経過時間がｎ次（ｎは２以上の自然数）のキャッシュメモリに設定された前記時間パラメータ未満であり、（ｎ−１）次のキャッシュメモリに設定された前記時間パラメータ以上の場合には、前回実行したプロセッサ装置及び、前記前回実行したプロセッサ装置と共に前記ｎ次のキャッシュメモリを共有するプロセッサ装置の中の１つのプロセッサ装置に前記スレッドを割り当てるスレッド割り当て手段、
として機能させることを特徴とするスケジュール制御プログラム。
【請求項２】
前記スレッド割り当て手段は、前記経過時間が前記ｎ次のキャッシュメモリに設定された前記時間パラメータ以上の場合には、前記ｎ次のキャッシュメモリを共有するプロセッサ装置以外のプロセッサ装置を含めた複数のプロセッサ装置の中で、負荷の最も少ないプロセッサ装置に前記スレッドを割り当てることを特徴とする請求項１記載のスケジュール制御プログラム。
【請求項３】
前記スレッド割り当て手段は、前記経過時間が前記１次のキャッシュメモリに設定された前記時間パラメータ以上であり、２次のキャッシュメモリに設定された前記時間パラメータ未満の場合には、複数の２次のキャッシュメモリのうち、前記スレッドを前回実行したプロセッサ装置が使用した２次のキャッシュメモリを共有するプロセッサ装置の中で、負荷の最も少ないプロセッサ装置に前記スレッドを割り当てることを特徴とする請求項１又は２のいずれか一項に記載のスケジュール制御プログラム。
【請求項４】
前記スレッド割り当て手段は、前記経過時間が前記２次のキャッシュメモリに設定された前記時間パラメータ以上であり、３次のキャッシュメモリに設定された前記時間パラメータ未満の場合には、複数の３次のキャッシュメモリのうち、前記スレッドを前回実行したプロセッサ装置が使用した３次のキャッシュメモリを共有するプロセッサ装置の中で、負荷の最も少ないプロセッサ装置に前記スレッドを割り当てることを特徴とする請求項３記載のスケジュール制御プログラム。
【請求項５】
複数のプロセッサ装置に、実行させるスレッドを割り当てるスケジュール制御方法において、
スレッドを次に実行させるプロセッサ装置へ割り当てる際に、経過時間を算出し、
前記プロセッサ装置で使用するキャッシュメモリに対して次数が高いほど大きな時間パラメータを設定し、前記経過時間を、１次のキャッシュメモリの時間パラメータから、次数が高いキャッシュメモリの時間パラメータへと順に比較していき、前記経過時間がｎ次（ｎは２以上の自然数）のキャッシュメモリに設定された前記時間パラメータ未満であり、（ｎ−１）次のキャッシュメモリに設定された前記時間パラメータ以上の場合には、前回実行したプロセッサ装置及び、前記前回実行したプロセッサ装置と共に前記ｎ次のキャッシュメモリを共有するプロセッサ装置の中の１つのプロセッサ装置に前記スレッドを割り当てることを特徴とするスケジュール制御方法。
【請求項６】
前記スレッドの割り当ては、前記経過時間が前記ｎ次のキャッシュメモリに設定された前記時間パラメータ以上の場合には、前記ｎ次のキャッシュメモリを共有するプロセッサ装置以外のプロセッサ装置を含めた複数のプロセッサ装置の中で、負荷の最も少ないプロセッサ装置に前記スレッドを割り当てることを特徴とする請求項５記載のスケジュール制御方法。
【請求項７】
前記スレッドの割り当ては、前記経過時間が前記１次のキャッシュメモリに設定された前記時間パラメータ以上であり、２次のキャッシュメモリに設定された前記時間パラメータ未満の場合には、複数の２次のキャッシュメモリのうち、前記スレッドを前回実行したプロセッサ装置が使用した２次のキャッシュメモリを共有するプロセッサ装置の中で、負荷の最も少ないプロセッサ装置に前記スレッドを割り当てることを特徴とする請求項５又は６のいずれか一項に記載のスケジュール制御方法。
【請求項８】
前記スレッドの割り当ては、前記経過時間が前記２次のキャッシュメモリに設定された前記時間パラメータ以上であり、３次のキャッシュメモリに設定された前記時間パラメータ未満の場合には、複数の３次のキャッシュメモリのうち、前記スレッドを前回実行したプロセッサ装置が使用した３次のキャッシュメモリを共有するプロセッサ装置の中で、負荷の最も少ないプロセッサ装置に前記スレッドを割り当てることを特徴とする請求項７記載のスケジュール制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はスケジュール制御プログラム及びスケジュール制御方法に関し、特に、複数のプロセッサ装置に、実行させるスレッドを割り当てる処理をコンピュータに機能させるスケジュール制御プログラム及び複数のプロセッサ装置に、実行させるスレッドを割り当てるスケジュール制御方法に関する。
【背景技術】
【０００２】
複数のＣＰＵ（Central Processing Unit）を用いてプログラムを実行するマルチプロセッサシステム対応のＯＳ（Operating System）では、実行するプログラムを複数の実行単位（以下スレッドという。）に分割し、スレッドをＯＳのスケジューラにより各ＣＰＵに割り当てることによってプログラムを実行している。このように、１つのプログラムを複数のＣＰＵにより並列処理することで、プログラムの処理時間の節約と、ＣＰＵにかかる負荷の分散を実現している。【０００３】
スケジューラは、ＣＰＵごとに、これから実行させるスレッドが繋がった待ち行列（以下ランキューと呼ぶ。）から最も優先度の高いスレッドを選び出し、そのスレッドを選び出したランキューに対応するＣＰＵで実行させる。また、実行開始時刻をスレッドごとに記録していた。【０００４】
図７は、従来のスケジューラによるスレッドの割り当ての様子を模式的に示した図であり、（Ａ）はあるスレッドの実行時のキャッシュメモリのデータを示し、（Ｂ）は一定時間経過後にそのスレッドを再び割り当てる際のキャッシュメモリのデータの様子を示す図である。【０００５】
ここでは、ＣＰＵ５００ａ、５００ｂ、５００ｃ、５００ｄのそれぞれに対し１次のキャッシュメモリ（以下１次キャッシュという。）５０１ａ、５０１ｂ、５０１ｃ、５０１ｄが接続されており、ＣＰＵ５００ａ、５００ｂとで２次のキャッシュメモリ（以下２次キャッシュという。）５０２ａを共有し、ＣＰＵ５００ｃ、５００ｄとで２次キャッシュ５０２ｂを共有しているコンピュータの一部の構成を示している。なお、斜線部はデータを示している。【０００６】
図７（Ａ）において、ＣＰＵ５００ａはスレッド５１０を実行している。このとき、１次キャッシュ５０１ａ及び２次キャッシュ５０２ａでは、スレッド５１０で用いるデータが、例えば図示しないメインメモリから読み出されて記憶される。なお、スレッド５１１、５１２、５１３はランキューに接続されており、実行待ちの状態となっている。【０００７】
ところで、シングルプロセッサシステムの場合と異なり、マルチプロセッサシステムでは、スレッドは常に同一のＣＰＵで実行されるのではなく、例えば一定時間で中断され、そのＣＰＵに別のスレッドを実行させることでマルチタスクを実現している。そして、例えば、中断したスレッド５１０を再開するときには、図７（Ｂ）のようにスケジューラはそのスレッド５１０を繋げるランキューを有するＣＰＵを以下のように選択していた。【０００８】
（１）スレッド５１０が前回に実行権を得た時刻（実行開始時刻）から今回ランキューに繋げる時刻までの経過時間が、ある一定時間以内であれば、前回、スレッド５１０を実行したＣＰＵ５００ａを選択する。【０００９】
（２）ある一定時間外であれば、全てのＣＰＵ５００ａ〜５００ｄの中から最も負荷が少ないＣＰＵを選択する。
これは、ある一定時間内であれば、前回スレッド５１０を実行したＣＰＵ５００ａが使用したキャッシュに、図７（Ｂ）に示すように、スレッド５１０が前回使用したデータがまだ残っていることが期待できるためである。この制御により、キャッシュヒット率を向上させ、性能向上を実現していた。なお、各ＣＰＵの負荷は、ランキューに繋がっているスレッド５１４、５１５、５１６の数やその優先度から決定する。【００１０】
また、マルチプロセッサシステムにおけるキャッシュのミスヒットを少なくするための技術として、各スレッド（タスク）が各プロセッサのキャッシュ中に確保しているブロック数を計数して、この計数結果を複数のプロセッサで共有しているメモリに記憶しておき、スレッドの再開時、この計数結果を元に、キャッシュに、より多くのブロック数を有するプロセッサに、そのスレッドを実行させる手法が知られている（例えば、特許文献１参照。）。【００１１】
また、２次キャッシュのミスヒットを少なくするための技術として、２次キャッシュを共有しているＣＰＵのグループが複数接続されたマルチプロセッサシステムにおいて、プロセスが、常に特定のＣＰＵのグループで実行されるようにした技術もあった（例えば、特許文献２参照。）。
【特許文献１】特開平８−３０５６２号公報（段落番号〔００２０〕〜〔００３９〕，第１〜第５図）
【特許文献２】特開平１０−１４３３８２号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかし、中断していたスレッドのＣＰＵへの割り当てを、前回の実行開始時刻からの一定の経過時間を基準として行う従来のスケジュール制御方法では、以下のような問題があった。【００１３】
図７（Ｂ）のように、経過時間によっては１次キャッシュ５０１ａにはスレッド５１０の前回実行時に記憶したデータは残っていないが、２次キャッシュ５０２ａにそのデータが残っている場合がある。また、２次キャッシュ５０２ａにはデータが残っていないが、図示しない３次キャッシュにデータが残っている場合もある。すなわち次数の大きいキャッシュほど、経過時間が長くてもデータが残っている可能性が高い。しかし、従来のスケジュール制御では、このことを考慮せず、経過時間がある一定時間外の場合には、全てのＣＰＵの中から最も負荷の少ないＣＰＵを選ぶので、キャッシュに残っているデータを無駄にすることがあり、効率的なキャッシュの使用が行われていないという問題があった。【００１４】
本発明はこのような点に鑑みてなされたものであり、効率的にキャッシュを使用可能なようにスレッドをＣＰＵに割り当てるスケジュール制御プログラムを提供することを目的とする。【００１５】
また、本発明の他の目的は、効率的にキャッシュを使用可能なようにスレッドをＣＰＵに割り当てるスケジュール制御方法を提供することである。
【課題を解決するための手段】
【００１６】
発明の一観点によれば、複数のプロセッサ装置に、実行させるスレッドを割り当てる処理をコンピュータに機能させる、以下のようなスケジュール制御プログラムが提供される。このスケジュール制御プログラムは、コンピュータを、スレッドの実行時に実行開始時刻及び実行するプロセッサ装置の識別情報を記憶するスレッド情報記憶手段、中断中の前記スレッドを次に実行させるプロセッサ装置へ割り当てる際に、前記実行開始時刻からの経過時間を算出する経過時間算出手段、前記プロセッサ装置で使用するキャッシュメモリに対して次数が高いほど大きな時間パラメータを設定し、前記経過時間を、１次のキャッシュメモリの時間パラメータから、次数が高いキャッシュメモリの時間パラメータへと順に比較していき、前記経過時間がｎ次（ｎは２以上の自然数）のキャッシュメモリに設定された前記時間パラメータ未満であり、（ｎ−１）次のキャッシュメモリに設定された前記時間パラメータ以上の場合には、前回実行したプロセッサ装置及び、前記前回実行したプロセッサ装置と共に前記ｎ次のキャッシュメモリを共有するプロセッサ装置の中の１つのプロセッサ装置に前記スレッドを割り当てるスレッド割り当て手段、として機能させる。
【発明の効果】
【００１８】
開示のスケジュール制御プログラム及びスケジュール制御方法によれば、キャッシュのヒット率が上がり、キャッシュを効率的に使用することができる。
【００２０】
本発明の上記および他の目的、特徴および利点は本発明の例として好ましい実施の形態を表す添付の図面と関連した以下の説明により明らかになるであろう。
【図面の簡単な説明】
【００２１】
【図１】複数のＣＰＵに実行させるスレッドを割り当てるためのスケジュール制御の概略を説明する図である。
【図２】本実施の形態のスケジュール制御を実行するコンピュータの一例のハードウェア構成図である。
【図３】ハードウェアの構成情報を示す図である。
【図４】本実施の形態のスケジュール制御に係るＯＳの機能を模式的に示す図である。
【図５】スレッド実行時の処理の流れを説明するフローチャートである。
【図６】中断中のスレッドをいずれかのＣＰＵのランキューに繋げる処理の流れを説明する図である。
【図７】従来のスケジューラによるスレッドの割り当ての様子を模式的に示した図であり、（Ａ）はあるスレッドの実行時のキャッシュメモリのデータを示し、（Ｂ）は一定時間経過後にそのスレッドを再び割り当てる際のキャッシュメモリのデータの様子を示す図である。
【発明を実施するための最良の形態】
【００２２】
以下、本発明の実施の形態を図面を参照して詳細に説明する。
まず、本発明の実施の形態の概略を説明する。
図１は、複数のＣＰＵに実行させるスレッドを割り当てるためのスケジュール制御の概略を説明する図である。【００２３】
なお、ここでは複数のＣＰＵ１０ａ、１０ｂ、１０ｃ、１０ｄのそれぞれに対し１次キャッシュ１１ａ、１１ｂ、１１ｃ、１１ｄが接続されており、ＣＰＵ１０ａ、１０ｂとで２次キャッシュ１２ａを共有し、ＣＰＵ１０ｃ、１０ｄとで２次キャッシュ１２ｂを共有しており、ＣＰＵ１０ａ〜１０ｄとで３次キャッシュ１３を共有しているコンピュータにおけるスケジュール制御を例にして説明する。また、各ＣＰＵ１０ａ〜１０ｄで実行されるスレッド２０、２１、２２、２３、２４、２５、２６を模式的に示している。【００２４】
複数のＣＰＵ１０ａ〜１０ｄに実行させるスレッドを割り当てるスケジュール制御は、スレッド情報記憶手段１、経過時間算出手段２、スレッド割り当て手段３にて行われる。
以下、各処理手段の機能を説明する。【００２５】
スレッド情報記憶手段１は、スレッド２０〜２６のそれぞれの実行時に実行開始時刻及び、実行するＣＰＵ１０ａ〜１０ｄの識別情報（以下ＣＰＵ番号）を記憶する。
経過時間算出手段２は、中断中のスレッド（例えばスレッド２０）を、次に実行させるＣＰＵ１０ａ〜１０ｄに割り当てる際に、スレッド情報記憶手段１に記憶した実行開始時刻からの経過時間ｔを算出する。【００２６】
スレッド割り当て手段３は、ＣＰＵ１０ａ〜１０ｄへのスレッド２０〜２６の割り当てを行う。このとき、ＣＰＵ１０ａ〜１０ｄが使用するキャッシュメモリ（１次キャッシュ１１ａ、１１ｂ、１１ｃ、１１ｄ、２次キャッシュ１２ａ、１２ｂ、３次キャッシュ１３）に対して次数が高いほど大きな時間パラメータＴ１、Ｔ２、Ｔ３（Ｔ１＜Ｔ２＜Ｔ３）を設定する。この時間パラメータは、それぞれの次数のキャッシュに、中断中のスレッドが前回実行時に使用したデータが残っている可能性がある時間を目安に設定される。次数の高いキャッシュほど容量が大きいため、経過時間ｔが長くてもデータが残っている可能性が高い。そのため、次数が高いほど大きな時間パラメータが設定される。具体的には、時間パラメータは、キャッシュの容量や、ベンチマークなどによって決定する。そして、スレッド割り当て手段３は、中断中のスレッドの経過時間ｔがｎ次（ｎは２以上の自然数）のキャッシュに設定された時間パラメータ未満であり、（ｎ−１）次のキャッシュに設定された時間パラメータ以上の場合には、前回実行したＣＰＵ及び、前回実行したＣＰＵと共にｎ次のキャッシュを共有するＣＰＵの中で、負荷の最も少ないものに中断中のスレッドを割り当てることを特徴としている。【００２７】
以下、中断中のスレッド２０を、再びＣＰＵ１０ａ〜１０ｄのいずれかに割り当てる場合を例にして、本実施の形態のスケジュール制御方法の概略を説明する。
中断中のスレッド２０を、ＣＰＵ１０ａ〜１０ｄのいずれかに割り当てる際、経過時間算出手段２は、スレッド情報記憶手段１で記憶された、スレッド２０の前回の実行時の実行開始時刻を参照して、現時刻までの経過時間ｔを算出する。スレッド割り当て手段３は、算出された経過時間ｔを基に、以下のようなスレッド２０の割り当てを行う。【００２８】
まず、経過時間ｔがｔ＜Ｔ１の場合には、スレッド情報記憶手段１で記憶したＣＰＵ番号を参照して、スレッド２０を前回実行したＣＰＵ１０ａを選択して、再度スレッド２０を割り当てる（ＣＰＵ１０ａのランキューに繋げる）。【００２９】
Ｔ１≦ｔ＜Ｔ２の場合には、前回実行したＣＰＵ１０ａ及び、ＣＰＵ１０ａと共に２次キャッシュ１２ａを共有するＣＰＵ１０ｂの中で、負荷の少ないほうにスレッド２０を割り当てる。図１の場合、ＣＰＵ１０ａのランキューには、３つのスレッド２１、２２、２３が存在する。一方、ＣＰＵ１０ｂのランキューには、２つのスレッド２４、２５がある。そのため、スレッド割り当て手段３は、負荷の少ないＣＰＵ１０ｂのランキューにスレッド２０を繋げる。【００３０】
Ｔ２≦ｔ＜Ｔ３の場合には、前回実行したＣＰＵ１０ａ及び、ＣＰＵ１０ａと共に３次キャッシュ１３を共有するＣＰＵ１０ｂ、１０ｃ、１０ｄの中で、負荷の最も少ないものにスレッド２０を割り当てる。図１の場合、ＣＰＵ１０ｃにはスレッドは存在せず、ＣＰＵ１０ｄには１つのスレッド２６が存在するため、スレッド２０は、ＣＰＵ１０ｃに割り当てられる。【００３１】
なお、ｔ≧Ｔ３の場合には、従来と同様に、全てのＣＰＵ１０ａ、１０ｂ、１０ｃ、１０ｄの中で最も負荷の少ないものに、スレッド２０が割り当てられる。図１の場合では、ＣＰＵ１０ｃが選択され、スレッド２０が割り当てられる。【００３２】
このようにすることで、経過時間に応じて前回実行時に記憶したデータが残っている可能性が高いキャッシュを使用するＣＰＵ１０ａ〜１０ｄが、中断中のスレッド２０の割り当て対象として選択されるので、キャッシュのヒット率が上がり、キャッシュを効率的に使用することができる。【００３３】
また、キャッシュを共有するＣＰＵ１０ａ〜１０ｄの中で最も少ない負荷のＣＰＵに割り当てる処理を行うので、スレッド２０の割り当てと同時に負荷分散処理が行えることになる。これにより、スレッド割り当て後に負荷分散処理を行うことに起因して、キャッシュに記憶されていたスレッドのデータが追い出されてキャッシュヒット率が下がることを防止できる。【００３４】
次に、実施の形態の詳細を説明する。
図２は、本実施の形態のスケジュール制御を実行するコンピュータの一例のハードウェア構成図である。【００３５】
ここで示すコンピュータ３０は、例えば、ＵＮＩＸ（登録商標）のサーバコンピュータである。
コンピュータ３０は、それぞれ１次キャッシュを内蔵している８つのＣＰＵ３１ａ、３１ｂ、３１ｃ、３１ｄ、３１ｅ、３１ｆ、３１ｇ、３１ｈと、２次キャッシュ３２ａ、３２ｂ、３２ｃ、３２ｄ、３次キャッシュ３３ａ、３３ｂ、３次キャッシュ３３ａ、３３ｂとシステムバス３４を介して接続されるメモリ３５、Ｉ／Ｏ３６などから構成されている。【００３６】
また、２次キャッシュ３２ａはＣＰＵ３１ａ、３１ｂで共有され、２次キャッシュ３２ｂは、ＣＰＵ３１ｃ、３１ｄで共有され、２次キャッシュ３２ｃはＣＰＵ３１ｅ、３１ｆで共有され、２次キャッシュ３２ｄはＣＰＵ３１ｇ、３１ｈで共有されている。さらに、３次キャッシュ３３ａは、ＣＰＵ３１ａ、３１ｂ、３１ｃ、３１ｄで共有され、３次キャッシュ３３ｂは、ＣＰＵ３１ｅ、３１ｆ、３１ｇ、３１ｈで共有されている。【００３７】
このような、ハードウェアの構成情報は以下のようなファームウェアで記述されている。
図３は、ハードウェアの構成情報を示す図である。【００３８】
例えば、ＣＰＵ（ｃｐｕ  ｎｏｄｅ）については、それぞれの識別情報“ｉｄ：〜”が記述され、さらに、そのＣＰＵが用いるキャッシュの識別情報がキャッシュの次数ごとに記述されている。例えば、図２のＣＰＵ３１ａは、識別情報が“ｉｄ＝０”で記述され、ＣＰＵ３１ａに内蔵された１次キャッシュは“ｌｅｖｅｌ  １  ｃａｃｈｅ  ｉｄ：０”で、ＣＰＵ３１ａで用いる２次キャッシュ３２ａは“ｌｅｖｅｌ  ２  ｃａｃｈｅ  ｉｄ：０”で、３次キャッシュ３３ａは“ｌｅｖｅｌ  ３  ｃａｃｈｅ  ｉｄ：０”でそれぞれ記述されている。また、例えば、ＣＰＵ３１ｈは、識別情報が“ｉｄ＝７”で記述され、ＣＰＵ３１ｈに内蔵された１次キャッシュの識別情報は“ｌｅｖｅｌ  １  ｃａｃｈｅ  ｉｄ：７”で、ＣＰＵ３１ｈで用いる２次キャッシュ３２ｄの識別情報は“ｌｅｖｅｌ  ２  ｃａｃｈｅ  ｉｄ：３”で、３次キャッシュ３３ｂの識別情報は“ｌｅｖｅｌ  ３  ｃａｃｈｅ  ｉｄ：１”でそれぞれ記述されている。また、ハードウェアの構成情報には、図示を省略したがメモリ３５や、Ｉ／Ｏ３６などの構成を示す記述も含まれる。このようなハードウェアの構成情報は、ＯＳに渡される。【００３９】
図４は、本実施の形態のスケジュール制御に係るＯＳの機能を模式的に示す図である。
ファームウェアからのハードウェア構成情報により、図２のＣＰＵ３１ａ〜３１ｈの情報を示すＣＰＵ管理構造体４０−１、４０−２、４０−３、…、４０−８が生成される。スレッド４１はスレッド管理構造体で表され、そのスレッド４１の実行開始時刻“ｄｉｓｐ＿ｔｉｍｅ”と、そのスレッド４１を実行したＣＰＵ番号“ｃｐｕ”が記憶される。スレッド４１は、スケジューラ４２によって、ＣＰＵ３１ａ〜３１ｈのいずれかに割り当てられる。【００４０】
ＯＳのスケジューラ４２は、スレッド管理構造体を参照して、経過時間に応じて中断中のスレッドを割り当てるＣＰＵを選択する。また、前述したようにキャッシュの次数に応じて時間パラメータＴ１、Ｔ２、Ｔ３を設定する。【００４１】
このような機能を有するＯＳにより、図１で示した各手段が、図２で示すようなハードウェアのコンピュータ３０上で実現される。
以下、図２、図３、図４を用いて本実施の形態のスケジュール制御方法を説明する。【００４２】
まず、スレッド実行時の処理を説明する。
図５は、スレッド実行時の処理の流れを説明するフローチャートである。
スレッド実行処理が開始すると、スケジューラ４２は、各ＣＰＵ３１ａ〜３１ｈのランキューを確認し、待機中のスレッド４１の存在を確認する。スレッド４１がある場合にはステップＳ２の処理に進み、スレッド４１がない場合には、スレッド４１がランキューに出現するまでステップＳ１の処理を繰り返す（ステップＳ１）。【００４３】
スケジューラ４２は、スレッド４１がランキューに存在した場合には、ランキューからスレッド４１を抜き、実行状態とする。以下、図４で示すように、ＣＰＵ管理構造体４０−２で表されるＣＰＵ３１ｂのランキューに繋がったスレッド４１ａを例にして説明する。図４の矢印Ａで示しているように、ＣＰＵ管理構造体４０−２で示されるＣＰＵ３１ｂのランキューからスレッド４１ａが抜かれ、スレッド４１ａはＣＰＵ３１ｂによる実行権を得る（ステップＳ２）。【００４４】
さらに、実行権を得たスレッド４１ａのスレッド管理構造体に、実行開始時刻“ｄｉｓｐ＿ｔｉｍｅ”となる現時刻と、実行するＣＰＵ３１ｂのＣＰＵ番号（例えば、ＣＰＵ３１ｂの識別情報である“ｉｄ＝１”）を記憶する（ステップＳ３）。【００４５】
その後、ＣＰＵ３１ｂにより、実行権を得たスレッド４１ａが実行される（ステップＳ４）。
このようなスレッド４１ａは、処理が終われば消滅するが、Ｉ／Ｏ３６を介した外部機器からの応答待ちや、別スレッドが獲得中の排他資源待ちの場合や、スレッド４１ａの処理が一定時間を越えたときなど、処理を終える前に中断されることがある（図４の矢印Ｂ）。その場合、スケジューラ４２は、スレッド４１ａを一旦中断状態にし、ＣＰＵ３１ｂのランキューにある別のスレッドに実行権を与える。Ｉ／Ｏ３６を介した外部機器からの応答があったときや、別スレッドが獲得中だった排他資源が解放されたとき、その他スレッド４１ａの処理が一定時間を越えて一旦別スレッドに実行権を譲渡した後など、スレッド４１ａの実行を再開させる場合、スレッド４１ａを再びいずれかのＣＰＵ３１ａ〜３１ｈに割り当てる処理を行う。【００４６】
図６は、中断中のスレッドをいずれかのＣＰＵのランキューに繋げる処理の流れを説明する図である。
なお、以下でも図４で示したスレッド４１ａを用いて説明する。【００４７】
まず、スケジューラ４２は、中断中のスレッド４１ａのスレッド管理構造体に記録されている、実行開始時刻“ｄｉｓｐ＿ｔｉｍｅ”と現時刻との差より経過時間ｔを算出する（ステップＳ５）。【００４８】
そして経過時間ｔが、ｔ＜Ｔ１の場合、前回と同じＣＰＵ３１ｂを選択する（ステップＳ６）。
Ｔ１≦ｔ＜Ｔ２の場合には、前回動作したＣＰＵ３１ｂと２次キャッシュ３２ａを共有するＣＰＵ３１ａ、３１ｂの中から最も負荷の少ないＣＰＵを選択する。図４の例では、ＣＰＵ管理構造体４０−１で表されるＣＰＵ３１ａのランキューに繋がっているスレッド４１の数が、ＣＰＵ管理構造体４０−２で表されるＣＰＵ３１ｂのランキューに繋がっているスレッド４１の数よりも多く、負荷が大きいのでＣＰＵ３１ｂが選択される（ステップＳ７）。【００４９】
Ｔ２≦ｔ＜Ｔ３の場合には、前回動作したＣＰＵ３１ｂと３次キャッシュ３３ａを共有するＣＰＵ３１ａ、３１ｂ、３１ｃ、３１ｄの中から最も負荷の少ないＣＰＵを選択する。図４の例では、ＣＰＵ管理構造体４０−３で表されるＣＰＵ３１ｃが選択された場合を示している（ステップＳ８）。【００５０】
ｔ≧Ｔ３の場合には、全ＣＰＵ３１ａ〜３１ｈの中から最も負荷の少ないＣＰＵを選択する。図４の例は、ＣＰＵ管理構造体４０−８で表されるＣＰＵ３１ｈが選択された場合を示している（ステップＳ９）。【００５１】
そして最後に、スケジューラ４２は、選択されたＣＰＵのランキューにスレッド４１ａを繋げる（ステップＳ１０）。
以上のように、本実施の形態のスケジュール制御方法によれば、経過時間に応じて、前回実行時に記憶したデータが残っている可能性が高いキャッシュを使用するＣＰＵが、中断中のスレッドの割り当て対象として選択されるので、キャッシュのヒット率が上がり、キャッシュを効率的に使用することができる。【００５２】
また、キャッシュを共有するＣＰＵの中で最も少ない負荷のＣＰＵに割り当てる処理を行うので、中断中のスレッドの割り当てと同時に負荷分散処理が行えることになる。これにより、スレッド割り当て後に負荷分散処理を行うことに起因して、キャッシュに記憶されていたスレッドのデータが追い出されてキャッシュヒット率が下がることを防止できる。【００５３】
なお、前述したように、上記の処理内容は、コンピュータによって実現することができる。その場合、コンピュータが有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記録装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。光磁気記録媒体には、ＭＯ（Magneto-Optical disk）などがある。【００５４】
プログラムを流通させる場合には、たとえば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。【００５５】
プログラムを実行するコンピュータは、たとえば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送される毎に、逐次、受け取ったプログラムに従った処理を実行することもできる。【００５６】
以上、本発明を実施例に基づいて説明したが、本発明は上記に限定されるものではなく、特許請求の範囲に記載の範囲内で様々な変形が可能である。例えば、上記では３次キャッシュまでのコンピュータを例にして説明したが、３次以上のキャッシュがあるコンピュータについても同様に適用できる。【００５７】
上記については単に本発明の原理を示すものである。さらに、多数の変形、変更が当業者にとって可能であり、本発明は上記に示し、説明した正確な構成および応用例に限定されるものではなく、対応するすべての変形例および均等物は、添付の請求項およびその均等物による本発明の範囲とみなされる。
【符号の説明】
【００５８】
１  スレッド情報記憶手段
２  経過時間算出手段
３  スレッド割り当て手段
１０ａ、１０ｂ、１０ｃ、１０ｄ  ＣＰＵ
１１ａ、１１ｂ、１１ｃ、１１ｄ  １次キャッシュ
１２ａ、１２ｂ  ２次キャッシュ
１３  ３次キャッシュ
２０、２１、２２、２３、２４、２５、２６  スレッド
Ｔ１、Ｔ２、Ｔ３  時間パラメータ
ｔ  経過時間
【図１】
0004651671.tif 000002
【図２】
0004651671.tif 000003
【図３】
0004651671.tif 000004
【図４】
0004651671.tif 000005
【図５】
0004651671.tif 000006
【図６】
0004651671.tif 000007
【図７】
0004651671.tif 000008