JPH07200314A - 並列ジョブの協調スケジューリング方式 - Google Patents

Abstract

(57)【要約】 【目的】 オペレーティングシステムとタスクスケジュ
ーラ間で必要な情報を共有し、指定したプロセッサ数を
常に確保したスケジューリングと、並列ジョブの実行時
間の短縮を実現する。 【構成】 並列オペレーティングシステムとライブラリ
層の二階層で実現されるスケジューリング方式におい
て、生成スレッド数を物理プロセッサ数に限定せず、多
めに生成して待機状態とする手段、待機状態のスレッド
を実行可能状態とする手段、実行可能状態のスレッド数
をライブラリ層で確認する手段、実行可能状態のスレッ
ドを待機状態にする手段、および待機状態のスレッドを
終了させる手段から構成される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、並列ジョブの協調スケ
ジューリング方式に関して、例えば、ＩＯなどを多発す
る並列プログラムの処理において、ＩＯ待ちによるプロ
セッサの遊びをなくしプロセッサ使用効果を高める効果
を持つ並列ジョブの協調スケジューリング方式に関す
る。

【０００２】

【従来の技術】従来のジョブスケジューリング方式につ
いて説明する。ここで、ジョブとは利用者が投入したプ
ログラムやコマンドとする。

【０００３】従来のオペレーティングシステムのスケジ
ューリングの考え方は単一のプロセッサを備えるマシン
上から発展してきた。プロセッサへのジョブの割り当て
のためにプロセスという管理単位が用意される。１つの
物理プロセッサを時間分割で使用し、複数のプロセスを
交互に処理することによって、ジョブを多重処理してい
るように見せる。

【０００４】一方、マルチスレッド機構を採用する並列
オペレーティングシステムにおいても基本的な考え方は
同様で、プロセッサ割り当て単位としてスレッドと呼ば
れる管理単位を設定する。１つのプロセスに複数のスレ
ッドを用意し、独立に物理プロセッサにスケジュールす
ることによって１つのプロセスを並列処理することが出
来る。

【０００５】さらに、利用者が並列処理を利用するイン
ターフェースが並列ライブラリで実現されている。この
並列ライブラリをタスクスケジューラと呼ぶことにす
る。利用者は、プログラム内に並列処理の指示を挿入す
ることにより、プログラムを並列処理の処理単位である
タスクに分割し、個々のタスクの同期や排他などのスケ
ジューリングを指示することが出来る。

【０００６】従来の並列ジョブのスケジューリング方式
を図２を使用して説明する。

【０００７】利用者プログラム２０３の中には、そのプ
ログラムで使用するスレッド数２０５やタスク２０４の
スケジューリングに関する指示が書かれてある。タスク
スケジューラ２０１は利用者の指示したスケジューリン
グにしたがって、タスクを選択し動かす。指示したスレ
ッド数２０５と比較して生成したスレッド２０６の数が
少なければ、オペレーティングシステム２０２に生成を
要求するが、指示したスレッド数２０５に等しくなった
時点でそれ以上の生成要求をしない。物理プロセッサ２
０７へスレッド２０６を割り当てることはオペレーティ
ングシステム２０２が行なうので、オペレーティングシ
ステム２０２とタスクスケジューラ２０１の二階層での
スケジューリングという構成になる。従来の二階層スケ
ジューリングでは、タスクスケジューラ２０１からオペ
レーティングシステム２０２でのスケジューリングは意
識しない構造になっている。

【０００８】

【発明が解決しようとする課題】従来の並列ジョブのス
ケジューリング方式では、利用者が並列処理を利用する
ための機構はタスクスケジューラで実現されてはいるも
のの、物理プロセッサへの仕事の割り当てはすべてオペ
レーティングシステムのスケジューリング次第で決ま
る。利用者は、スレッドを物理プロセッサとみなしてス
タクのスケジューリングを指示するが、実際にはそのス
レッドがどの物理プロセッサ上でいつ処理されているか
タスクスケジューラは認知しない。タスクスケジューラ
とオペレーティングシステムでの二階層のスケジューリ
ングで、情報交換をほとんどせず協調性がないために以
下のような問題がある。

【０００９】１．通常、利用者が指示するスレッド数は
固定的で、利用者はスレッド＝物理プロセッサと考えて
タスクの動作を指示する。この時、動作中のタスクの１
つがＩＯを発行すると、オペレーティングシステム中
で、そのスレッドが休眠状態となってＩＯ完了を待つ。
すると、使用できるスレッド数が１つ減り、実行可能な
タクが他にある場合でも処理することができない。

【００１０】２．指示するスレッド数を大きくした場
合、スレッドの１つがＩＯで休眠状態に入っても、オペ
レーティングシステムが余ったスレッドを動かすことが
できる。このため、１．の問題はある程度回避できる。
しかし、スレッドのスケジューリングはオペレーティン
グシステムが行なうため、タスクの動作するタイミング
が利用者の意図したタイミングと異なる場合が生じ、利
用者の意図したスケジューリングができないことがある
という問題がある。

【００１１】本発明の目的は、従来の並列ジョブのスケ
ジューリング方式において、オペレーティングシステム
で管理されるスレッドの情報をタスクスケジューラに認
識させる協調スケジューリング方式を提案することによ
って、協調性を持った二階層スケジューリングを可能と
し、利用者の意図したスケジューリングを可能とし、さ
らに実行時間の短縮を実現することにある。

【００１２】

【課題を解決するための手段】上述の問題点を解決する
ために、本発明の並列ジョブの協調スケジューリング方
式は、マルチスレッド機構を整えるオペレーティングシ
ステム、および並列ジョブの各タスクをスレッド上にス
ケジューリングするタスクスケジューラの二階層で実現
されるスケジューリング方式において、以下の手段から
構成される。

【００１３】１．オペレーティングシステム中で、スレ
ッドをスケジューリング対象とならない待機状態で生成
する手段、２．待機状態のスレッドをスケジューリング
対象となる実行可能状態とする手段、３．実行可能状態
のスレッドを待機状態にする手段、４．オペレーティン
グシステム中で管理される実行可能状態スレッド数をラ
イブラリ層で確認する手段、５．待機状態のスレッドを
終了させる手段。

【００１４】

【作用】図１に示す本発明の全体構成を使って説明す
る。

【００１５】タスクスケジューラ１０１中では、タスク
分割に応じてオペレーティングシステム１０２にスレッ
ド生成を要求し、最適スレッド数１０６を越えた時点で
スレッドを待機状態で生成要求する手段１１０に切替え
る。さらに、スレッドがＩＯ待ちなどの休眠状態に入る
時に、待機状態のスレッド１０３を実行可能状態１０４
とする手段１１２を使うことにより、実行可能なスレッ
ド１０４の数を最適スレッド数１０６を下回らないよう
にできる。

【００１６】ＩＯ待ちなどのスレッドが休眠状態から実
行可能状態１０４に復帰することで、実行可能状態のス
レッド数１０５が最適スレッド数１０６よりも多くなる
ことがある。この場合、タスクのスイッチ時に、タスク
スケジューラ１０１で実行可能スレッド数１０５と最適
スレッド数１０６を比較し、スレッド待機化手段１１１
を使うことによって、実行可能スレッド数１０５をでき
る限り最適スレッド数１０６を上回らないようにする。
これにより実行可能なスレッド１０４の数が増え過ぎな
いよう制御でき、オペレーティングシステム１０２の余
計なスケジューリングを最小限にとどめ、利用者が意図
したスケジューリングをタスクスケジューラ１０１が行
なうことが可能となる。

【００１７】プロセスの終了時に、待機状態のスレッド
１０３を実行状態として終了処理を行なわせることによ
り、プロセスの完全な終了処理を保証する。

【００１８】

【実施例】図３のようなフローで動く簡単なプログラム
を例として考え、本発明の動作および効果について順を
追って説明する。図３のプログラムでは、ルートタスク
３０１からＩＯを含むタスク１（３０２）、計算処理の
みを含むタスク２（３０３）を分割し、最後に同期をと
って終了する。

【００１９】本発明を構成するそれぞれの手段につい
て、図４〜８の例を使って動きを説明する。

【００２０】図４に、タスク分割に応じてスレッドを待
機状態で生成した状態の一例を示す。タスク４０１は３
つに分割しているが、プロセッサ４０３の数は２つなの
で、従来の方法ならスレッドは２つしか生成できなかっ
た。本発明では３つ目のスレッドを生成する代わりにオ
ペレーティングシステムのスケジューリング対象となら
ない待機状態４０４として生成する。

【００２１】図５に、待機状態のスレッドを実行可能状
態とする場合の一例を示す。実行中だったタスク５０１
の１つがＩＯ待ちなどで休眠状態５０５に入ると、スレ
ッドはタスクと対になったまま停止する。この時、待機
状態５０４のスレッドを実行可能状態５０２とすること
により、プロセッサ５０３の個数分の実行可能スレッド
５０２の数を確保でき、タスク５０１を処理できる。

【００２２】図６に、実行可能スレッド数をタスクスケ
ジューラから確認する手段を示す。プログラムの開始時
に実行可能スレッド数が収まる領域６０４のアドレスを
オペレーティングシステム６０２に要求する。システム
空間中には利用者空間から見える領域６０３があり、オ
ペレーティングシステムはこの領域に実行可能スレッド
数を収める領域６０４を作り、そのアドレスをタスクス
ケジューラに返す。タスクスケジューラ６０１からこの
アドレスをたどることにより、自由に実行可能スレッド
数を確認することができる。

【００２３】図７に、実行可能状態のスレッドを待機状
態とする場合の一例を示す。ＩＯ待ちで休眠状態となっ
ていたスレッド７０５が、ＩＯ完了により実行可能状態
に復帰すると、実行可能スレッド７０２が１ツ余分にな
るという状態が一時的に発生する。この状態で、タスク
７０１の１つが利用者空間中でスイッチを行なった場
合、実行可能スレッド数を見て余分になっていることを
確認したら、そのタスクのスレッドを待機状態７０４に
するようオペレーティングシステムに要求する。

【００２４】図８に、待機状態のスレッドを終了させる
一例を示す。プロセス終了時に待機状態のスレッド８０
４をそのまま残さず、一旦、実行可能状態８０２にして
おいてからＫＩＬＬシグナル８０５を送ってスレッドを
終了させる。

【００２５】

【発明の効果】以上説明したように、本発明によれば、
最適スレッド数のスレッドを常に確保してタスクをスケ
ジューリングできる。これによって、利用者の意図した
スケジューリングが可能となり、実行時間の短縮を実現
できる。

【図面の簡単な説明】

【図１】本発明の全体構成

【図２】従来のスケジューリング手法

【図３】本発明の実施例プログラムフロー

【図４】タスク分割に応じてスレッドを待機状態で生成
した状態の一例

【図５】待機状態のスレッドを実行可能状態とする場合
の一例

【図６】実行可能スレッド数を利用者空間で確認する手
法

【図７】実行可能状態のスレッドを待機状態とする場合
の一例

【図８】待機状態のスレッドを終了させる場合の一例

【符号の説明】

１０１ タスクスケジューラ １０２ オペレーティングシステム １０３ 待機状態スレッド １０４ 実行可能状態スレッド １０５ 実行可能状態スレッド数 １０６ プロセッサ数 １０７ プロセッサ ２０１ タスクスケジューラ ２０２ オペレーティングシステム ２０３ 利用者プログラム ２０４ タスク ２０５ プロセッサ数 ２０６ スレッド ２０７ プロセッサ ３０１ ルートタスク ３０２ ＩＯを含む子タスク ３０３ 計算処理のみを含む子タスク ４０１ 実行可能スレッド ４０２ タスク ４０３ プロセッサ ４０４ 待機状態スレッド ５０１ タスク ５０２ 実行可能スレッド ５０３ プロセッサ ５０４ 待機状態スレッド ５０５ 休眠状態スレッド ６０１ タスクスケジューラ ６０２ オペレーティングシステム ６０３ 利用者空間から見えるシステム空間中の領域 ６０４ 実行可能スレッド数を収める領域 ７０１ タスク ７０２ 実行可能スレッド ７０３ プロセッサ ７０４ 待機状態スレッド ７０５ 休眠状態スレッド ８０１ タスク ８０２ 実行可能スレッド ８０３ プロセッサ ８０４ 待機状態スレッド ８０５ ＫＩＬＬシグナル

Claims (1)

【特許請求の範囲】
1. 【請求項１】 マルチスレッド機構を備えるオペレーテ
   ィングシステム、および並列ジョブをスレッド上にスケ
   ジューリングする並列ライブラリの二階層で実現される
   スケジューリング方式において、 オペレーティングシステム中で、スレッドをスケジュー
   リング対象とならない待機状態で生成する手段と、 待機状態のスレッドをスケジューリング対象となる実行
   可能状態とする手段と、 実行可能状態のスレッドを待機状態にする手段と、 オペレーティングシステム中で管理される実行可能状態
   スレッド数をライブラリ層で確認する手段と、 待機状態のスレッドを終了させる手段とから構成される
   ことを特徴とする並列ジョブ協調スケジューリング方
   式。