(57)【特許請求の範囲】
【請求項１】
各実行が少なくとも一つのコード・モジュールの実行を含むタスク群を実行し、1つのオペレーティング・システムを実行する少なくとも一つのプロセッサを有するデータ処理システムにおいて、前記オペレーティング・システムによって実行される方法であって、
２つのタスクが共通のコード・モジュールを呼び出すかどうかに基づいた相互に従属する関係にあるタスク群からなるグループ群に、タスク群を論理的に分割するステップと、
相互に従属する関係にあるタスク群からなる前記グループそれぞれが、そのグループのタスク群が前記プロセッサ上で実行する一サイクル内の一つのタイム・スロットに割り当てられるように、実行されるべき、相互に従属する関係にあるタスク群からなる前記各グループを横取り型にスケジューリングするステップと、
各グループごとに、前記グループに割り当てられた前記タイム・スロット内で実行されるべきそれぞれの前記グループ内の前記タスク群を、非横取り型にスケジューリングするステップと、
前記グループ内の前記タスク群の相互に従属する関係における変化を反映するために、相互に従属するタスク群のグループに、タスク群の前記分割を動的に更新するステップと、
グループ群の前記横取り型のスケジューリングを更新するステップと、
各グループ内のタスク群の協調的なスケジューリングを更新するステップと
を備えることを特徴とする方法。
【請求項２】
前記データ処理システムは少なくとも一つの記憶装置を含み、前記方法は、各グループのグループ・リストを前記記憶装置に記憶するステップをさらに備え、各グループ・リストは、当該グループ・リストに関連付けられたグループにおけるタスクの識別情報を含むことを特徴とする請求項１に記載の方法。
【請求項３】
各グループごとのステータス情報で、実行中のタスクをそのグループが有しているかどうかを示し、かつ、実行中の任意のタスクについての識別情報を保持するステータス情報を格納するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項４】
タスク群を前記相互に従属する関係にあるタスク群からなるグループに論理的に分割する前記ステップは、
最初に、各タスクをそれ自身のグループに配置するステップと、
その後、前記最初に配置されたタスクが他のグループ内の一つのタスクによって呼び出されたモジュールを呼び出す場合には、前記最初に配置されたタスクを、タスク群からなる前記他のグループに移動するステップと
を備えることを特徴とする請求項１に記載の方法。
【請求項５】
コード・モジュール群を格納する少なくとも一つの記憶装置、および各実行が少なくとも一つのコード・モジュールの実行を含むタスク群を実行する少なくとも一つのプロセッサを備えたデータ処理システムにおいて、
タスクが前記プロセッサ上の実行されるときに呼び出されるモジュールを列挙したタスク従属リストを各タスクごとに提供するステップと、
前記タスク従属リストに関連付けられたタスクによってモジュールが呼び出された際における変化に基づいて前記タスク従属性リストを動的に更新するステップと、
前記タスク群の実行中、各タスクの前記タスク従属性リストに基づいて、前記タスク群を、相互に従属する関係にあるタスク群からなるグループ群に動的に、１つのタスクによって呼び出された１つのコード・モジュールと、他のタスクによって呼び出された他のコード・モジュールとの間の従属に基づいて、分割するステップと、
そのグループのタスク群が前記プロセッサ上で実行することが可能な一サイクル内の一つのタイム・スロットを、タスク群からなる各グループに与えられるように、実行されるべきタスク群からなる前記グループ群を横取り型にスケジューリングするステップと、
タスク群からなる各グループごとに、当該グループに割り当てられた前記タイム・スロットの期間に、各グループ内で実行されるタスク群を非横取り型にスケジューリングするステップと
を備えることを特徴とする方法。
【請求項６】
前記グループに含まれるタスク群の識別情報を保持するグループ・リストを各グループごとに格納するステップをさらに備えることを特徴とする請求項５に記載の方法。
【請求項７】
各グループごとのステータス情報で、実行中のタスクを前記グループが有しているということを示し、かつ、実行中の任意のタスクについての識別情報を保持するステータス情報を格納するステップをさらに備えることを特徴とする請求項５に記載の方法。
【請求項８】
コード・モジュールを格納する少なくとも一つの記憶装置、および各実行が少なくとも一つのコード・モジュールの実行を含むタスク群を実行する少なくとも一つのプロセッサを備えたデータ処理システムにおいて、
関連付けられたコード・モジュールからなる相互に従属する関係にあるコード・モジュールを列挙したモジュール従属リストを、前記各関連したコード・モジュールごとに提供するステップと、
タスクが前記プロセッサ上で実行されるときにロードされ、あるいはエクスポートされる、モジュール群からなる前記モジュール従属リスト群に列挙されたモジュール群について論理的な結合を行うことにより、各タスクごとにタスク従属リストを生成するステップと、
前記タスク従属リスト群を調べて、前記タスク群を、相互に従属する関係にあるタスク群からなるグループ群に論理的に分割するステップと、
そのグループのタスク群が前記プロセッサ上で実行することが可能な一サイクル内の一つのタイム・スロットを、タスク群からなる各グループに与えられるように、実行されるべきタスク群からなる前記グループ群を横取り型にスケジューリングするステップと、
タスク群からなる各グループごとに、当該グループに割り当てられた前記タイム・スロットの期間に、各グループ内で実行されるタスク群を非横取り型にスケジューリングするステップと、
を備えることを特徴とする方法。
【請求項９】
前記各グループに含まれるタスクの識別情報を保持するグループ・リストを各グループごとに格納するするステップをさらに備えることを特徴とする請求項８に記載の方法。
【請求項１０】
各グループごとのステータス情報で、実行中のタスクを前記グループが有しているということを示し、かつ、実行中の任意のタスクについての識別情報を保持する、ステータス情報を格納するステップをさらに備えることを特徴とする請求項８に記載の方法。
【請求項１１】
各実行が少なくとも一つのコード・モジュールの実行を含むタスク群を実行し、1つのオペレーティング・システムを実行する少なくとも１つのプロセッサを有するデータ処理システムにおいて、前記オペレーティング・システムによって実行される方法であって、
相互に従属する関係にあるタスク群からなるグループ群に、タスク群を、前記タスク群によって呼び出されるコード・モジュール群に基づいて、論理的に分割するステップと、
相互に従属する関係にあるタスク群からなるグループそれぞれが、そのグループのタスク群が前記プロセッサ上で実行する一サイクル内の一つのタイム・スロットに与えられるように、実行されるべき、相互に従属する関係にあるタスク群からなる前記グループを横取り型にスケジューリングするステップと、
各グループごとに、前記グループに割り当てられた前記タイム・スロット期間、各グループ内で実行されるタスク群を非横取り型にスケジューリングするステップと、
前記コード・モジュールが前記タスクによって呼び出された際の変化を反映するために、相互に従属する関係にあるタスク群からなるグループ群に、タスク群の前記分割を動的に更新するステップと、
グループ群の前記横取り型のスケジューリングを更新するステップと、
各グループ内のタスク群の前記非横取り型なスケジューリングを更新するステップと
を備えることを特徴とする方法。
【請求項１２】
前記オペレーティング・システムは、さらに、
最初に、各タスクをそれ自身のグループに配置するステップと、
その後、前記最初に配置されたタスクが他のグループ内の１つ以上のタスクによって呼び出されたモジュールを呼び出す場合には、前記最初に配置されたタスクをタスク群からなる他のグループに移動するステップと
をさらに実行することを特徴とする請求項１１に記載の方法。
【請求項１３】
コード・モジュールを格納する少なくとも１つの記憶装置と、各実行が少なくとも一つのコード・モジュールの実行を含むタスク群を実行する少なくとも一つのプロセッサとを備えたデータ処理システムにおける方法であって、
前記タスクが前記プロセッサ上で実行される際にロードされ、あるいはエクスポートされるモジュール群を列挙する、各タスクごとのタスク従属リストを提供するステップと、
前記タスク従属リストを動的に更新し、かつ検査するステップと、
前記タスクの実行中、前記タスク従属性リストの検査に基づいて、相互に従属する関係にあるタスク群からなるグループ群に動的に分割するステップと、
タスク群からなる各グループが、そのグループのタスク群が前記プロセッサ上で実行することが可能な一サイクル内の一つのタイム・スロットに与えられるように、実行されるべきタスク群からなる前記グループを横取り型にスケジューリングするステップと、
タスク群からなる各グループごとに、前記グループに割り当てられた前記タイム・スロット期間、各グループ内で実行されるべきタスク群を非横取り型にスケジューリングするステップと
を備えることを特徴とする方法。
【請求項１４】
コード・モジュールを格納する少なくとも一つの記憶装置と、および各実行が少なくとも一つのコード・モジュールの実行を含むタスク群を実行する少なくとも一つのプロセッサを備えたデータ処理システムにおける方法であって、
関連付けられたコード・モジュールからなる相互に従属する関係にあるコード・モジュールを列挙したモジュール従属リストを、前記各関連したコード・モジュールごとに提供するステップと、
タスクが前記プロセッサ上で実行されるときにロードされ、あるいはエクスポートされる、モジュール群からなる前記モジュール従属リスト群に列挙されたモジュール群についての論理的な結合を行うことにより、各タスクごとにタスク従属リストを生成するステップと、
前記タスク従属リスト群を検査するステップと、
前記タスク従属リストの前記検査に基づいて、前記タスクを相互に従属する関係にあるタスク群からなるグループ群に論理的に分割するステップと、
そのグループのタスク群が、前記プロセッサ上で実行することが可能な一サイクル内の一つのタイム・スロットを、タスク群からなる各グループに与えられるように、実行されるべき、タスク群からなる前記グループ群を横取り型にスケジューリングすること、
タスク群からなる前記グループごとに、当該グループに割り当てられた前記タイム・スロットの期間に、各グループ内で実行されるタスク群を非横取り型にスケジューリングするステップと
を備えることを特徴とする方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
この発明は、一般に、データ処理システムに関し、より詳細には、データ処理システムにおけるタスクのスケジューリングに関する。
【０００２】
【従来の技術】
ワシントンのレドモンドにあるマイクロソフト社により販売されているマイクロソフトWINDOWS バージョン3.1 オペレーティング・システムは、メッセージ駆動型のオペレーティング・システムである。オペレーティング・システム上を実行される各プログラムは、そのプログラムのある部分に向けられた入力メッセージを保持するメッセージ・キューを備えている。メッセージは、プログラムによって生成されたウィンドウへ向けられていることがよくある。プログラムによって生成された各ウィンドウは、関連するプロシジャを備えている。つまり、メッセージは、ウィンドウそれ自体には送られず、むしろ関連するプロシジャに送られる。
【０００３】
メッセージは、「メッセージ・ループ」として知られているコードのブロックの実行により、関連するプログラムによってメッセージ・キューから取り出され、処理される。図１は、メッセージ・ループによって実行される処理の流れを示すフローチャートである。これらの処理は、プログラムがアクティブである間、ループ処理により繰り返し実行される。
【０００４】
まず、GetMessage関数が呼び出され、キューからメッセージが一つ取り出される（ステップ10）。GetMessage関数は、キューからメッセージを一つ（一つ存在するならば）取り出す機能をもつ。
【０００５】
メッセージが、キューから一度取り出されると、（必要ならば）TranslateMessage関数が呼び出され、このメッセージは使用可能なフォーマットに変換される（ステップ12）。この関数は、あるキーボード変換を行う。
【０００６】
メッセージが一度変換されると、DispatchMessage 関数が呼び出され、このメッセージは適切なプロシジャにディスパッチされる（ステップ14）。このメッセージは、行き先のウィンドウを識別する情報を含んでいる。この情報は、メッセージを適切にディスパッチするために使用される。
【０００７】
また、上述したGetMessage関数は、マイクロソフトWINDOWS バージョン3.1 オペレーティング・システムにおけるタスクのスケジューリングにおいても役割を担う。このオペレーティング・システムは、非横取り型（非プリエンプティブ）、すなわち協調型のマルチタスキングのアプローチを採用する。タスクは、サブルーチンまたはプログラムのように、独立に実行することができる一つのコードの集まりである。
【０００８】
協調型マルチタスキングとは、タスク相互間でプロセッサ上の制御を自発的に渡す（譲渡する（“yielding”））ことにより、タスクが互いに協調することをいう。これとは対照的に、横取り型のマルチタスキングでは、スケジューラがどのタスクにプロセッサの使用を認めるべきかを決定し、典型的には、実行のために与えられたタイム・スロットを各タスクに提供する。GetMessage関数は、オペレーティング・システムにおける協調型マルチタスキングを実行するための媒体の一例である。オペレーティング・システムが提供する他の関数であって、協調型マルチタスキングを実行するのに役立つ関数には、PeekMessage 、Yield およびWaitMessage 関数が含まれる。GetMessage関数およびこれらの他の名前をもつ関数群が協調型マルチタスキングにおいてどのように機能するかを理解するために、GetMessage関数の処理をより詳しく見ることが有効である。
【０００９】
図２は、複数のアクティブなタスクを有する状況において、GetMessage関数が第１のタスク（例えば、プログラム）から呼び出されたときに、GetMessage関数によって実行される処理の流れを示すフローチャートである。
【００１０】
まず、GetMessage関数は、呼出し側タスクのメッセージ・キューが空かどうかを判定する（ステップ16）。呼出し側タスクのメッセージ・キューが空の場合には、このタスクは、空でないメッセージ・キューをもつ第２のタスクにプロセッサを譲る（すなわち、この第１のタスクはプロセッサの制御を放棄する）（ステップ18）。時間が少し経過した時点において、メッセージが第１のタスクのメッセージ・キューで利用可能になる（ステップ20）。第２のタスクがもう一つのタスクに制御を譲るまで、第２のタスクはプロセッサの制御を維持する。最終的に、あるタスクが制御を第１のタスクに戻すことになる（ステップ22）。一般的には、他のタスクの一つのメッセージ・キューが空であり、かつ、第１のタスクのメッセージ・キューが空でないときに、この他のタスクが第１のタスクに制御を戻す。続いて、第１のタスクのメッセージ・キューのメッセージが、メッセージ・キューから取り出される（ステップ24）。一方、ステップ16において、第１のタスクのメッセージ・キューが空でないと判定された場合には、メッセージ・キューからのメッセージの取出し処理（ステップ24）が、ステップ18、20および22の実行後ではなく、直接実行される。
【００１１】
【発明が解決しようとする課題】
マイクロソフトWINDOWS バージョン3.1 オペレーティング・システムの協調型マルチタスキングのアプローチの難点の一つは、あるタスクが、他のタスクに制御を譲ることを拒否することにより、プロセッサを占有することである。タスクがそのメッセージ・キューにメッセージを持っている限り、タスクは、制御を譲る必要がない。
【００１２】
【課題を解決するための手段】
この発明の第１の特徴によると、タスク群を実行する少なくとも一つのプロセッサを備えたデータ処理システムにおいて、一方法が実行される。これらのタスク群は、独立したタスク・グループに論理的に分割される。各タスク・グループにプロセッサ上で実行されるためのタイム・スロットが割り当てられるように、タスク・グループは横取り型（プリエンプティブ）にスケジューリングされ、実行される。各グループ内で実行されるタスク群は、非横取り型（非プリエンプティブ）にスケジューリングされ、これらのタスク群は、グループに割り当てられたタイム・スロットの時間中に実行される。
【００１３】
この発明の第２の特徴によると、コード・モジュールを記憶する少なくとも一つの記憶装置と、タスク群を実行する少なくとも一つのプロセッサとを備えたデータ処理システムにおいて、一方法が実行される。各タスクの実行中に、少なくとも一つのコード・モジュールが実行される。この方法では、タスク従属リストが各タスク用に設けられる。このタスク従属リストは、タスクがプロセッサ上で実行されるときに呼び出される候補のモジュールを列挙したものである。
【００１４】
この方法は、各コード・モジュール用のモジュール従属リストを設けるための付加的な処理（ステップ）を含んでいる。各モジュール従属リストは、そのリストに関連したコード・モジュールに相互に従属するコード・モジュール群を列挙したものである。このような場合に、各タスクのタスク従属リストは、タスクがプロセッサ上で実行されるときに呼び出される候補のモジュール従属リストに列挙されたモジュール群の論理的な結合を行うことにより生成される。タスク従属リストは、タスクを、相互に従属するグループ内に論理的に分割するように調べられる。タスク・グループは、横取り型（プリエンプティブ）にスケジューリングされ、実行される。このスケジューリングは、各タスク・グループに、そのグループのタスク群がプロセッサ上で実行される一サイクル中の一つのタイム・スロットが与えられるように行われる。各タスク・グループごとに、グループ内のタスク群は、非横取り型にスケジューリングされ、そのグループに割り当てられたタイム・スロットの時間中に実行される。
【００１５】
この発明の第３の特徴によると、データ処理システムは、相互に従属するタスク群からなるグループにタスク群を分割するための分割メカニズムを含んでいる。また、このデータ処理システムは、タスクを実行するための実行メカニズムも含んでいる。横取り型スケジューラは、タスク・グループを横取り型にスケジューリングする。このスケジューリングは、各グループのタスク群の一つを実行するための一つのタイム・スロットが、各グループに与えられるように行われる。また、非横取り型スケジューラは、各グループのタスク群を非横取り型にスケジューリングするためにデータ処理システムに設けられる。
【００１６】
【実施例】
この発明の好ましい実施例は、横取り型マルチタスキングと協調型マルチタスキングを組み合わせ、オペレーティング・システムにおけるタスク群のスケジューリングを最適化する。特に、タスク群は、論理的には、相互に従属するタスク・グループに分けられる。
【００１７】
以下に詳細に説明されるように、相互に従属するタスク（相互従属タスク）が非同期にスケジューリングされると、コード・シェアリング（コードの共有）およびデータ・シェアリング（データの共有）の問題が発生するように、相互従属タスクは関連している。
【００１８】
プロセッサ時間のタイム・スロットは、各グループに与えられる。しかし、そのグループ内におけるスケジューリングは、ワシントンのレドモンドにあるマイクロソフト社によって販売されているマイクロソフトWINDOWS バージョン3.1 オペレーティング・システムによって実行されるように、協調型の方法で行われる。グループが、横取り型でスケジュールされているので、一つのタスクが、プロセッサを占有することはなく、すべてのタスクの実行を遅くすることはない。一般に、タスク完了の応答時間は、この発明により改善される。また、一つのタスクが停止（ハング）しても、スケジューラは、全てのタスクが停止しないように、もう一つのグループに切り換える。
【００１９】
さらに、互換性のために、この発明は、タスク間の従属性が無視されないことを確実にする。
【００２０】
マイクロソフトWINDOWS オペレーティング・システムの早期のバージョンは、協調型のマルチタスキングを使用していた。したがって、このオペレーティング・システムの早期バージョン用に記述されたアプリケーションは、横取り型スケジューリングには向いていない。また、そのようなアプリケーションが、横取り型でスケジュールされた環境において実行されるときに、従属性の問題が生じる。これらの従属性を認識することに失敗すると、純粋に横取り型でスケジューリングされた環境において種々の問題が発生する。
【００２１】
この発明の好ましい実施例は、図３に示すように、データ処理システム26において実現される。図３に示すデータ処理システム26は、単一のプロセッサ・システムであるが、この技術分野の専門家ならば、この発明が分散システムのようなマルチ・プロセッサ・システムにおいても実現されることを理解するであろう。図３のデータ処理システム26は、システムの処理を制御する中央処理装置（ＣＰＵ）27を備えている。データ処理システム26は、ファイルおよびデータを記憶するためのメモリ28およびディスク記憶装置30も備えている。メモリ28は、ＲＡＭ、ＲＯＭまたは他のよく知られたタイプのメモリ・デバイスを含む複数のタイプのメモリ・デバイスのいずれであってもよい。データ処理システム26は、さらに、キーボード32、マウス34およびビデオ・ディスプレイ36も備えている。追加の、または他のタイプの入出力装置をデータ処理システム26に備えることができるのはいうまでもない。
【００２２】
メモリ28は、オペレーティング・システム40とコード・モジュール38とのコピーを保持する。オペレーティング・システムは、ここに示される好ましい実施例をサポートするための、マイクロソフトWINDOWS バージョン3.1 オペレーティング・システムの改良バージョンであってもよい。オペレーティング・システム40は、ＣＰＵ28上でのタスクの実行をスケジューリングする機能をもつスケジューラ42を含んでいる。この発明の好ましい実施例の大部分は、このスケジューラ42によって実行される。
【００２３】
図４は、この発明の好ましい実施例におけるタスクのスケジューリングで実行される処理の流れを示す高レベルのフローチャートである。
【００２４】
まず、タスク群は、相互従属関係にあるタスク群の論理的なグループに組織される（ステップ44）。これらのタスク群は、別々のタイム・スロットで実行できないように相互従属性を有している。例えば、これらのタスク群は、共通の動的リンク・ライブラリ（ＤＬＬ）・モジュールまたは他の共通のモジュールを呼び出すかもしれない。このようなタスク群が別々のタイム・スロットで実行されると、データ共有問題が発生する。これらのタスク群の一つが、ＤＤＬのデータを不注意に変化させると、他のタスクに有害な影響を与える。タスク群を論理的なグループに組織する処理は、オペレーティング・システム40によって実行される。この組織する処理については、後に詳述する。
【００２５】
以下では、まず、この発明の横取り型スケジューリングの点に焦点を合わせ、後に、この発明の協調型スケジューリングの点に焦点を合わせて説明する。
【００２６】
オペレーティング・システム40上を実行される様々なタスク・グループは、横取り型でスケジューリングされ、各グループに、ＣＰＵ28上での実行のために、プロセッサ時間のある特定のタイム・スロットが与えられる（図４のステップ46）。図５は、４つのタイム・スロット（グループ１、グループ２、グループ３およびグループ４）が存在する場合に、タイム・スロットがどのように割り当てられるかを示している。図５に示す例では、グループ１は、サイクル１のタスク１に割り当てられ、次のサイクル２ではタイム・スロット５に割り当てられている。また、図５に示す例では、グループ２はサイクル１のタイム・スロット２に、グループ３はサイクル１のタイム・スロット３に、グループ４はサイクル１のタイム・スロット４にそれぞれ割り当てられている。各グループは、次のサイクルにおいて対応するタイム・スロットにそれぞれ割り当てられている。すなわち、グループ１はサイクル２のタイム・スロット５に、グループ２はサイクル２のタイム・スロット６に、グループ３はサイクル２のタイム・スロット７に、グループ４はサイクル２のタイム・スロット８にそれぞれ割り当てられている。
【００２７】
スケジューリングが動的であり、時間の経過とともにグループの追加および削除の双方またはいずれか一方が行われるかもしれないので、タイム・スロットのシーケンスは、固定されている必要はない。むしろスケジューリングは、時間の経過とともに変化する。しかしながら、スケジューラ42は、アクティブな各グループが、各サイクルでタイム・スロットを得られることを確実にする。
【００２８】
各グループ内におけるタスク群のスケジューリングは、横取り型で行われず、むしろ協調型で行われる（図４のステップ48）。上述したように、協調型のマルチ・タスキングでは、あるタスクが別のタスクに自発的に制御を譲ることが必要とされる。GetMessage関数に焦点を置いた従来技術の項で説明した例では、GetMessage関数がタスク間で制御を譲る媒体として機能する。一般に、グループ内で行われる協調型マルチ・タスキングは、マイクロソフトWINDOWS バージョン3.1 オペレーティング・システムで行われるスケジューリングと同様にして行われる。以下に詳述するように、この発明は、タスクを非ブロック化する前に、従属性のチェックを付加的に行う。GetMessage、PeekMessage 、Yield およびWaitMessage のようなＡＰＩは、アプリケーションに同じグループ内の他のタスクに従属することを許容する。
【００２９】
まとめると、各グループには、各サイクルにおいて、プロセッサ時間の一つのタイム・スロットが与えられる。グループに割り当てられたタイム・スロットにおいて、どのタスクを実行するかは、そのグループ内のタスクの協調型スケジューリングに依存する。したがって、あるグループにおいて現在実行されているタスクは、そのタスクがGetMessage関数のような媒体によってそのグループ内の他のタスクに制御を渡すまで、そのグループに割り当てられたタイム・スロットの期間中、連続的に実行され続けるであろう。
【００３０】
オペレーティング・システム40は、どのタスクが各グループにあるかを監視するためのデータ構造を有する。このための最初のデータ構造は、グループ・リスト50（図６）である。グループ・リスト50は、メモリ28におけるオペレーティング・システム40のデータ領域に記憶することができる。グループ・リスト50は、そのグループに含まれる各タスク用に、それぞれのエントリ52A 、52B 、52C および52D を含んでいる。各エントリ52A 、52B 、52C および52D は、そのグループの一部であるタスク用のハンドルを保持する。ハンドルとは、システム26のタスク群において一つのタスクをユニークに識別するための番号である。図６に示す例では、グループ・リスト50には、タスク１、タスク２、タスク７およびタスク８の４つのタスクのエントリ52A 、52B 、52C および52D が含まれている。
【００３１】
グループ・リストに含まれるタスクは、時間の経過とともに変化する。図７は、グループを併合するために実行される処理の流れを示すフローチャートである。
【００３２】
まず、一つのタスクが、それ自身のグループ内で起動する（ステップ54）。このタスクの実行中に、このタスクは、ＤＤＬにリンクを行うために、ＡＰＩコール（例えば、LoadLibrary 、LoadModule、WinExec 、またはSendMessage のある形態）を行う（ステップ56）。オペレーティング・システム40は、データ共有問題を回避するために、同じＤＤＬを用いる他のアプリケーション（タスク）を有するグループに、このタスクを移動させる（ステップ58）。
【００３３】
図８は、図７のステップ58の処理を詳細に示すフローチャートである。このフローチャートでは、あるタスクを、他のタスクを有するグループに移動する処理がどのようにして行われるかが示されている。
【００３４】
第１のグループから第２のグループに移動されるべきタスク（アプリケーション）は、LoadLibrary またはLoadModuleのＡＰＩから直接返される（リターンされる）のではなく、停止状態に置かれる（ステップ60）。第１のグループは、この時点で、「同期状態」（シンキング・アップ状態）にある。オペレーティング・システム40は、第２のグループのアプリケーション・コードのいずれもが実行されなくなるまで待つ（ステップ62）。すなわち、オペレーティング・システム40は、第２のグループのタスクのそれぞれが、GetMessage、WaitMessage またはYield のようなＡＰＩを呼び出すまで待つ。その後、第１のグループからのタスクは、第２のグループに加えられ（ステップ64）、続いて、そのタスクは実行のためにスケジューリングされる（ステップ66）。
【００３５】
スケジューラ42がグループにタイム・スロットを適切に割り当てるために、スケジューラ42は、各グループの現在の状態と、たとえあるとしても、どのタスクが、そのグループに与えられた次のタイム・スロットで実行されるようにスケジューリングされているかを知らなければならない。図９に示すように、グループ・ステータス・テーブル68が、オペレーティング・システム40によってメモリ28に記憶され、スケジューラ42が様々なグループからのタスクを横取り型でスケジューリングするのを助ける。
【００３６】
図９に示す例では、システム26は、現在、４つのアクティブなタスク・グループを有している。個別のエントリ70A 、70B 、70C および70D が、各グループに提供される。これらのエントリ70A 、70B 、70C および70D のそれぞれには、ステータス・フィールド72A 、72B 、72C および72D がそれぞれ含まれている。ステータス・フィールド72A 、72B 、72C および72D は、各グループのタスクのいずれが次のタイム・スロットで実行されるようにスケジューリングされているか、またはそのグループが「同期状態」（以下に詳述する）にあるかを詳細に示すステータス情報を保持する。ステータス情報は、ステータス・フィールド72A 、72B 、72C および72D 内のビットの集合として符号化されているであろう。また、各エントリ70A 、70B 、70C および70D には、タスク・ネーム・フィールド74A 、74B 、74C および74D がそれぞれ含まれている。このタスク・ネーム・フィールド74A 、74B 、74C および74D は、そのグループの次の利用可能なタイム・スロットで実行されるタスクのタスク・ネーム（タスク名）を保持する。したがって、エントリト70A がグループ１のステータス情報を保持するならば、このタスク・ネーム・フィールド74A は、実行されるグループ１のタスクのタスク名（またはハンドル）を保持する。
【００３７】
オペレーティング・システム40は、モジュール群38のそれぞれについてのモジュール従属リストも有している。このモジュール従属リストは、新しいタスクまたはモジュールがグループに追加されたとき、およびタスクがどのグループに追加されるかを決定するときに、タスク／モジュールをグループに割り当てる役割をもつ。モジュール従属リストは、タスクが割り当てられるべきグループを決定するために調べられる。横取り型にスケジューリングされたグループ群は、常に、共通の要素を持たないモジュール従属リストを有する。タスク／モジュールは、それ自身のグループまたは相互に従属するタスク／モジュールを有するグループ内に置かれる。
【００３８】
図10には、モジュール従属リスト76の一例が示されている。各タスクは、一つのモジュールまたは複数のモジュールを含んでいてもよい。モジュール従属リスト76は、関連するモジュールから呼び出され、またはロードされる候補モジュール群を列挙したものである。列挙されたモジュール群および関連するモジュールは、相互に従属する関係を有している。エントリ64A 、64B および64C は、各モジュール用のハンドルを保持する。このモジュール従属リスト76は、このリストに関連したモジュールから呼び出されまたはロードされるモジュールのそれぞれのエントリ78A 、78B および78C を備えている。図10では、このモジュールは、モジュール１、ＤＤＬ１およびＤＤＬ２を呼び出しまたはロードする。
【００３９】
モジュール従属リストは静的ではなく、むしろこのリストは時間の経過とともに変化する。図11は、関連したモジュールが実行されているときに、モジュール従属リスト76を更新するために行われる処理の流れを示すフローチャートである。
【００４０】
まず、モジュール従属リストは、各モジュール用に保持される（ステップ80）。続いて、そのリストに関連したモジュールに関係する従属関係を追加する処理が実行される（ステップ82）。この処理には、例えば、ライブラリ・モジュールのロード、ＤＤＬモジュールのロード、アプリケーション・モジュールの実行、またはエクスポートされるＤＤＬモジュールのアドレスの獲得処理が含まれる。マイクロソフトWINDOWS（登録商標） バージョン3.1 オペレーティング・システムでは、LoadLibrary、LoadModule、GetProcAddressおよびWinExec のようなＡＰＩコールは、モジュールに関係する従属関係を追加する。続いて、このようなＡＰＩコールによってロードされ、実行され、またはエクスポートされる新しいモジュールは、モジュール従属リストに追加される（ステップ84）。このようにして、モジュール従属リストは、関連したモジュールの実行中に、動的に変化（成長）する。
【００４１】
いずれのタスクも複数のモジュールを含むので、タスクのモジュール従属リストをどのようにして生成するかという問題がある。図12は、タスクの従属リストを生成するために実行される処理の流れを示すフローチャートである。まず、タスクが生成される（ステップ86）。続いて、このタスクのタスク従属リストが、このタスクのモジュール群からなるモジュール従属リストを結合することにより生成される（ステップ88）。このようにして、この発明の好ましい実施例は、タスクをグループに割り当てるときに、タスクの全ての従属関係が考慮されることを確実にする。
【００４２】
スケジューラ42によって実行されるスケジューリングの内容を、ここでまとめておくことはおそらく有益であろう。このスケジューラ42は、アクティブなグループのそれぞれにタイム・スロットを割り当てる。また、スケジューラ42は、グループ内のどのタスクが実行されるべきか、またはそのグループが同期状態にあるかどうかを判定しなければならない。現在実行されているタスクは、グループ・ステータス・テーブル68のエントリ70A 、70B 、70C および70D のタスク・ネーム・フィールド74A 、74B 、74C および74D （図９）内に示される。ＡＰＩのGetMessage、PeekMessage 、Yield およびWaitMessage が、この発明の好ましい実施例においては改良され、制御を渡すときおよびブロック化するときに、グループ・ステータス・テーブルを更新する。このようにして、グループ・ステータス・テーブル68は現在の情報を備え、各グループの適切なタスクがスケジューリングされる。
【００４３】
この発明について、好ましい実施例を参照しながら説明したが、この技術分野における専門家ならば、特許請求の範囲に記載された発明の範囲内で、様々な変更ないし修正を加えることが可能なことを理解するであろう。例えば、この発明は分散システムにおける使用によく適している。また、この発明は、マイクロソフトWINDOWS バージョン3.1 オペレーティング・システム以外の環境下でも実行することができる。さらに、この発明においては、単一のスケジューラだけでなく、むしろ複数のスケジューラを共同で使用することもできる。
【図面の簡単な説明】
【図１】マイクロソフトWINDOWS バージョン3.1 オペレーティング・システムのメッセージ・ループにより実行される処理の流れを示すフローチャートである。
【図２】図１のメッセージ・ループのGetMessage関数によって実行される処理の流れを示すフローチャートである。
【図３】この発明の好ましい実施例を実行するのに適したデータ処理システムを示すブロック図である。
【図４】タスク実行のスケジューリングにおいて、この発明の好ましい実施例によって実行される処理の高レベルの流れを示すフローチャートである。
【図５】この発明の好ましい実施例におけるグループの横取り型スケジューリングの一例を示すブロック図である。
【図６】この発明の好ましい実施例において使用されるグループ・リストの一例を示す。
【図７】この発明の好ましい実施例において、タスク群を、一つの併合されたグループに併合するために実行される処理の流れを示すフローチャートである。
【図８】この発明の好ましい実施例において、同じＤＤＬを用いる他のタスクを有するグループに、あるタスクを移動させるために実行される詳細な処理の流れを示すフローチャートである。
【図９】この発明の好ましい実施例において使用されるグループ・ステータス・テーブルの一例を示す。
【図１０】この発明の好ましい実施例において使用されるモジュール従属リストの一例を示す。
【図１１】この発明の好ましい実施例におけるモジュール従属リストを変化（成長）させるために実行される処理の流れを示すフローチャートである。
【図１２】この発明の好ましい実施例におけるタスク従属リストを生成するために実行される処理の流れを示すフローチャートである。
【符号の説明】
26  データ処理システム
27  ＣＰＵ
28  メモリ
30  ディスク記憶装置
32  キーボード
34  マウス
36  ビデオ・ディスプレイ
38  モジュール群
40  オペレーティング・システム
42  スケジューラ
50  グループ・リスト
52A 、52B 、52C 、52D エントリ
68  グループ・ステータス・テーブル
70A 、70B 、70C 、70D エントリ
72A 、72B 、72C 、72D ステータス・フィールド
74A 、74B 、74C 、74D タスク・ネーム・フィールド
76  モジュール従属リスト
78A 、78B 、78C エントリ
【図１】
0003746798.tif 000002
【図２】
0003746798.tif 000003
【図３】
0003746798.tif 000004
【図４】
0003746798.tif 000005
【図５】
0003746798.tif 000006
【図６】
0003746798.tif 000007
【図７】
0003746798.tif 000008
【図８】
0003746798.tif 000009
【図９】
0003746798.tif 000010
【図１０】
0003746798.tif 000011
【図１１】
0003746798.tif 000012
【図１２】
0003746798.tif 000013