JPH07302246A - スケジューリング方式 - Google Patents

Abstract

(57)【要約】 【目的】スレッドをディスパッチする場合に、スレッド
が属しているプロセスと実行するプロセッサを考慮する
ことによってキャッシュを有効利用する。 【構成】プロセス中に複数スレッドを定義可能なＯＳに
より動作する、各プロセッサがキャッシュを有するマル
チプロセッサコンピュータシステムにおいて、実行可能
スレッドのキューに繋がれた実行可能スレッドの数を認
識する実行可能スレッド認識手段６２と、実行可能スレ
ッド認識手段６２によって認識された実行可能スレッド
のうち、ディスパッチ対象のスレッドと同じプロセスに
属しているプロセスを認識する所属プロセス認識手段６
３と、所属プロセス認識手段６３によって認識されたス
レッドが複数で、かつ実行可能スレッドのキューに繋が
れたスレッドの数が特定の値（Ｎ個）より多い場合に、
複数のスレッドをまとめて（Ｍ個）プロセッサにディス
パッチするディスパッチ手段６６とを具備して構成す
る。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、マルチスレッド構造の
オペレーティングシステムにおけるスケジューリング方
式に関する。

【０００２】

【従来の技術】現在、多くのマルチプロセッサコンピュ
ータシステムでは、各プロセッサがキャッシュを持つこ
とでメモリへのアクセス回数を減らし処理速度を向上さ
せている。

【０００３】ところで、最近では１つのプロセス中に複
数のスレッドを定義することが可能なマルチスレッド構
造のオペレーティングシステムが一般的になってきてい
る。このオペレーティングシステムの長所は、同一プロ
セス中のスレッドが同じアドレス空間を共有することが
できるため、プロセッサで実行するスレッドをスイッチ
する際にアドレス空間をスイッチする必要がなくなり、
キャッシュやＴＬＢ（table look-up buffer：アドレス
変換バッファ）を有効に利用できる点にある。

【０００４】ところで、あるプロセッサにより処理され
ているスレッドが、プリエンプトやブロックなどによっ
て切替えられる時、オペレーティングシステムのプロセ
ス管理機能であるスケジューラは、実行可能スレッドの
キューの中から一番プライオリティの高いスレッドをプ
ロセッサにディスパッチする。

【０００５】ここでもし、実行可能スレッドのキューの
中に、同一プロセスに属する複数のスレッドがある場
合、それらのスレッドが同じプロセッサに割り当てられ
る確率はプロセッサの数が増えるのに伴い低くなる。

【０００６】プロセッサにスレッドが割り当てられた
際、先に同一プロセス中のスレッドが同一プロセッサに
割り当てられていると、そのプロセッサのキャッシュの
中に共有データが残っている可能性が高い。この場合、
スレッドを実行する際に、共有データを他のプロセッサ
のキャッシュや共有メモリからキャッシュに持ってくる
必要がない。こうした場合には、処理時間が短縮され、
またバスのトランザクションが低減される等、効率的で
ある。

【０００７】一方、同一プロセス中のスレッドが別々の
プロセッサに割り当てられた場合には、共有データをそ
れぞれのプロセッサでキャッシュに取り込まなければな
らないため、同一プロセッサに割り当てられる場合と比
べると非効率的である。

【０００８】現在のマルチスレッド構造のオペレーティ
ングシステムでは、プロセッサにスレッドを割り当てる
場合に、スレッドがどのプロセスに属しているかという
ようなことを考慮していない。すなわち、同一プロセス
中のスレッドが同一プロセッサで実行される確率が低い
ため、キャッシュが有効利用されていないということに
なる。

【０００９】

【発明が解決しようとする課題】このように従来のマル
チプロセッサコンピュータシステム上で動作する現在の
マルチスレッド構造のオペレーテイングシステムでは、
プロセッサにスレッドを割り当てる場合に、そのスレッ
ドがどのプロセスに属しているかというようなことを考
慮していなかった。このため、同一プロセス中のスレッ
ドが同一プロセッサで実行される確率が低くなってしま
い、各プロセッサでキャッシュへの共有データ読み込み
が発生し、プロセッサに装備されたキャッシュが十分に
有効利用されていないという問題があった。

【００１０】本発明は前記のような事情を考慮してなさ
れたもので、スレッドをディスパッチする場合には、そ
のスレッドが属しているプロセスと実行するプロセッサ
を考慮することによってキャッシュを有効利用すること
が可能なスケジューリング方式を提供することを目的と
する。

【００１１】

【課題を解決するための手段】本発明は、１つのプロセ
ス中に複数のスレッドを定義することが可能なマルチス
レッド構造のオペレーティングシステムにより動作す
る、プロセッサ毎にキャッシュが設けられたマルチプロ
セッサコンピュータシステムにおいて、実行可能スレッ
ドのキューに繋がれた実行可能スレッドの数を認識する
実行可能スレッド認識手段と、前記実行可能スレッド認
識手段によって認識された実行可能スレッドのうち、最
優先にディスパッチ対象とされるスレッドと同じプロセ
スに属しているスレッドを認識する所属プロセス認識手
段と、前記所属プロセス認識手段によって認識されたス
レッドが複数で、かつ前記実行可能スレッドのキューに
繋がれたスレッドの数が、ある特定の値より多い場合
に、前記所属プロセス認識手段によって認識された複数
のスレッドをまとめて、所定のプロセッサにディスパッ
チするディスパッチ手段とを具備したことを特徴とす
る。

【００１２】また、前記ディスパッチ手段によりディス
パッチされる各スレッドが、前回どのプロセッサ上で実
行されたかを認識する前回実行プロセッサ認識手段をさ
らに具備し、前記ディスパッチ手段が前回と同じプロセ
ッサ上にスレッドをディスパッチするように、ディスパ
ッチ時期を調整することを特徴とする。

【００１３】

【作用】このような構成によれば、マルチプロセッサコ
ンピュータシステム上で動作する、マルチスレッド構造
のオペレーティングシステムにおいて、スレッドをディ
スパッチする場合には、そのスレッドが属しているプロ
セスを考慮し、複数のスレッドをまとめてディスパッチ
することによって、プロセッサに設けられたキャッシュ
が有効に利用される。

【００１４】

【実施例】以下、図面を参照して本発明の一実施例を説
明する。図１は本実施例に係わるマルチプロセッサコン
ピュータシステムの概略構成を示すシステム構成図であ
る。図１に示すように、マルチプロセッサコンピュータ
システムは、複数のＣＰＵ３１，３２，３３が設けられ
ている。各ＣＰＵ３１，３２，３３は、それぞれキャッ
シュ３４，３５，３６を装備している。ＣＰＵ３１，３
２，３３は、バス３７を介して共有メモリ３８と接続さ
れる。

【００１５】共有メモリ３８は、各ＣＰＵ３１，３２，
３３が、本発明によるスケジューリング方式を実行する
ためのスケジューラの機能を含むオペレーティングシス
テムを格納している。また、共有メモリ３８には、実行
可能なスレッドのキュー（実行可能スレッドキュー３
９）が繋がれて格納され、またスリープキュー４０が格
納される。

【００１６】図２は本発明によるスケジューリング方式
の機能を実現する構成を示す機能ブロック図である。図
２に示すように、本発明のスケジューラ５６は、プロセ
ッサ数認識手段６１、実行可能スレッド認識手段６２、
スレッド所属プロセス認識手段６３、プロセス中スレッ
ド数認識手段６４、前回実行プロセッサ認識手段６５、
及びディスパッチ手段６６の機能が設けられている。

【００１７】プロセッサ数認識手段６１は、スケジュー
ラ５６がスケジューリングを行なう際に、マルチプロセ
ッサコンピュータシステム中に存在するプロセッサの数
（Ｐ）を認識するものである。

【００１８】実行可能スレッド認識手段６２は、現在、
マルチプロセッサコンピュータシステムで同時に実行可
能なスレッドの数（Ｔ）を認識するものである。スレッ
ド所属プロセス認識手段６３は、実行可能スレッド認識
手段６２によって認識された実行可能スレッドキューに
繋がれたスレッドの数（Ｔ）が特定の値（Ｎ）を越える
ときに、後述するプロセス中スレッド数認識手段６４で
認識されたスレッドの数が複数であれば、実行可能スレ
ッドキューの中からプライオリティの最も高いスレッド
と同じプロセスに属するスレッドを認識して実行可能ス
レッドキューからまとめて取り外すものである。

【００１９】プロセス中スレッド数認識手段６４は、実
行可能スレッド認識手段６２によって認識されたスレッ
ド数を認識するものである。前回実行プロセッサ認識手
段６５は、実行可能スレッド認識手段６２によって認識
されたスレッドが、ディスパッチ手段６６により複数の
ＣＰＵ３１，３２，３３の何れかにディスパッチされる
際に、スレッドを前回実行したプロセッサに再びディス
パッチするようにディスパッチ時期を調整するものであ
る。

【００２０】ディスパッチ手段６６は、実行可能スレッ
ド認識手段６２によって認識され、スレッド所属プロセ
ス認識手段６３によって取り外された複数のスレッド
を、前回実行プロセッサ認識手段６５の調整に従って、
ＣＰＵ３１，３２，３３の何れか（前回実行したＣＰ
Ｕ）にまとめてディスパッチするものである。

【００２１】次に、本実施例のスケジューラ５６の動作
について、図３に示すフローチャートを参照しながら説
明する。まず、スケジューラ５６は、スケジュール要求
があると、プロセッサ数認識手段１１により、マルチプ
ロセッサコンピュータシステム中に存在するプロセッサ
の数（Ｐ）を認識する（ステップＳ１，Ｓ２）。

【００２２】また同時に、スケジューラ５６は、実行可
能スレッド認識手段６２により、共有メモリ３８の中の
実行可能スレッドキューに繋がれた、現在、実行可能な
スレッドの数（Ｔ）を認識する（ステップＳ３）。

【００２３】例えば、ここでは、図４に示すように、シ
ステム中には２つのプロセスＰ１とＰ２があり、それぞ
れのプロセスＰ１，Ｐ２に属している複数のスレッド
（プロセスＰ１にはＴ11，Ｔ12，Ｔ13、プロセスＰ２に
はＴ21，Ｔ22）があるものとして説明する。

【００２４】共有メモリ３８の中には実行可能状態のス
レッドを繋いでおく実行可能スレッドキュー、スリープ
状態のスレッドを繋いでおくスリープキューがおかれて
いる。各キューには、図１に示すように、異なるプロセ
スに属するスレッドが混在している。

【００２５】システムで実行可能なスレッドの数（Ｔ）
を認識した結果、マルチプロセッサコンピュータシステ
ムで実行可能なスレッドの数（Ｔ）が、ある特定の値
（Ｎ）を越えるようならば、スケジューラ５６は、実行
可能なスレッドを、複数（Ｍ）まとめて実行可能スレッ
ドキューから取り外す。

【００２６】すなわち、スケジューラ５６は、スレッド
の数（Ｔ）がある特定の値（Ｎ）より大きければ、最初
にプライオリティ制御に基づき、一番プライオリティの
高いスレッド、すなわち実行可能スレッドキュー１７の
先頭に位置するスレッド（Ｔ11）を取り外す。

【００２７】なお、ある特定の値（Ｎ）は、本発明によ
るスケジューリング方式を適用することによって十分に
効果が得られるスレッド数であるかを判別するための基
準値である。すなわち、特定の値（Ｎ）よりスレッド数
が少ない場合には、大きな問題とならないため本方式を
用いないこともできるが、特定の値（Ｎ）よりスレッド
数が多い場合には、本方式を用いたスケジューリングを
行なうことにより、大きな効果が得られる。

【００２８】スケジューラ５６は、スレッド所属プロセ
ス認識手段１３により、実行可能スレッドキューの中か
らスレッドＴ11と同じプロセスに所属するスレッド、図
１に示す例ではスレッドＴ12，Ｔ13を認識し、これら同
じプロセスに属するスレッドＴ11，Ｔ12，Ｔ13をまとめ
て実行可能スレッドキューからまとめて取り外す（ステ
ップＳ５，Ｓ６）。

【００２９】次に、スケジューラ５６は、実行可能スレ
ッドキューから取り外したＭ個（例では３個）のスレッ
ドを、例えばＣＰＵ３１にディスパッチ（図１中４１）
する（ステップＳ８）。

【００３０】この際、スケジューラ５６は、スレッドの
前回実行プロセッサ認識手段１８によって、できる限り
スレッドが前回実行したプロセッサに再びディスパッチ
されるようにディスパッチ時期を調整する。

【００３１】ＣＰＵ３１は、まとめてディスパッチされ
たＭ個のスレッドを順番に実行していく。この際、ディ
スパッチされたＭ個のスレッドは、全ての実行が終わる
までキューには戻らず、ＣＰＵ３１に割り当てられたま
まとなる（ステップＳ９）。この時、キャッシュ３４に
は、割り当てられた複数のスレッドで扱われる共有デー
タが１度格納されていれば、各スレッドを実行する毎
に、共有メモリ３８や他のＣＰＵ３２，３３のキャッシ
ュ３５，３６に格納されたデータを読み込む必要がな
い。

【００３２】スケジューラ５６は、Ｍ個のスレッド全て
の実行が終わった所で、Ｍ個のスレッドをまとめて実行
可能スレッドキュー、あるいはスリープキューに戻す
（図１中４２、ステップＳ１０）。

【００３３】このようにして、共有メモリ３８中に格納
された実行可能スレッドキューに繋がれた複数のスレッ
ドから、同じプロセスに所属するスレッドをまとめてＣ
ＰＵ３１にディスパッチすることにより、各スレッドを
実行する際、キャッシュ３４に格納された、複数のスレ
ッドで共有される共有データを利用することができる。
すなわち、キャッシュ３４へのデータ読み込みが必要と
なる可能性が低く、処理時間が短縮され、またバス３７
のトランザクション量を低減させることができる。

【００３４】また、ＣＰＵ３１で実行されたスレッドを
１つづつ戻すのではなく、まとめて戻すことで、同じプ
ロセスに属するスレッドがまとまっているのを再び分散
するのを防ぐことができる。これにより、同じプロセス
に属するスレッドが、１つづつ異なるＣＰＵにスケジュ
ーリングされないようにでき、またコストも低減させる
ことができる。

【００３５】また、スレッドをまとめてディスパッチす
る際に、前回と同じＣＰＵにディスパッチするように調
整することで、キャッシュに前回ディスパッチされた際
に格納されたデータが残っている可能性が、不特定のＣ
ＰＵにディスパッチする場合よりも高いため、各ＣＰＵ
３１，３２，３３に設けられたキャッシュ３４，３５，
３６を有効に利用することができる。

【００３６】

【発明の効果】以上のように本発明によれば、マルチス
レッド構造のオペレーティングシステムにおいて、スレ
ッドをディスパッチする場合には、そのスレッドが属し
ているプロセスと実行するプロセッサを考慮することに
よって、キャッシュを有効利用できるものである。

【図面の簡単な説明】

【図１】本発明の一実施例に係わるマルチプロセッサコ
ンピュータシステムの概略構成を示すシステム構成図。

【図２】本発明によるスケジューリング方式の機能を実
現する構成を示す機能ブロック図。

【図３】本実施例によるスケジューリング方式の動作手
順を説明するためのフローチャート。

【図４】本実施例におけるプロセスの一例を示す図。

【符号の説明】

３１，３２，３３…ＣＰＵ、３４，３５，３６…キャッ
シュ、３７…バス、３８…共有メモリ、３６…スケジュ
ーラ、６１…プロセッサ数認識手段、６２…実行可能ス
レッド認識手段、６３…スレッド所属プロセス認識手
段、６４…プロセス中スレッド数認識手段、６５…前回
実行プロセッサ認識手段、６６…ディスパッチ手段

Claims (3)

【特許請求の範囲】
1. 【請求項１】 １つのプロセス中に複数のスレッドを定
   義することが可能なマルチスレッド構造のオペレーティ
   ングシステムにより動作する、プロセッサ毎にキャッシ
   ュが設けられたマルチプロセッサコンピュータシステム
   において、 実行可能スレッドのキューに繋がれた実行可能スレッド
   の数を認識する実行可能スレッド認識手段と、 前記実行可能スレッド認識手段によって認識された実行
   可能スレッドのうち、最優先にディスパッチ対象とされ
   るスレッドと同じプロセスに属しているスレッドを認識
   する所属プロセス認識手段と、 前記所属プロセス認識手段によって認識されたスレッド
   が複数で、かつ前記実行可能スレッドのキューに繋がれ
   たスレッドの数が、ある特定の値より多い場合に、前記
   所属プロセス認識手段によって認識された複数のスレッ
   ドをまとめて、所定のプロセッサにディスパッチするデ
   ィスパッチ手段と、 を具備したことを特徴とするスケジューリング方式。
2. 【請求項２】 前記ディスパッチ手段によってディスパ
   ッチされた複数のスレッドは、プロセッサでまとめて実
   行された後、まとめて実行可能スレッドのキューに戻さ
   れることを特徴とする請求項１記載のスケジューリング
   方式。
3. 【請求項３】 前記ディスパッチ手段によりディスパッ
   チされる各スレッドが、前回どのプロセッサ上で実行さ
   れたかを認識する前回実行プロセッサ認識手段をさらに
   具備し、 前記ディスパッチ手段が前回と同じプロセッサ上にスレ
   ッドをディスパッチするように、ディスパッチ時期を調
   整することを特徴とする請求項１記載のスケジューリン
   グ方式。