(57)【要約】【課題】  プロセッサグループの各プロセッサに、実行可能なスレッドを連続して実行もしくはプロセッサグループ内で並列に同時実行できるマルチプロセッサシステムを実現する。【解決手段】  スレッドグループ実行手段が利用可能なプロセッサが次に実行するスレッドの次スレッド構造体特定情報を特定し、この次スレッド構造体特定情報と同一スレッドグループで、かつ実行可能なスレッド構造体特定情報を特定し、スレッド実行手段が利用可能なプロセッサに次スレッド構造体特定情報のスレッドを実行させ、利用可能なプロセッサと同じグループ中のプロセッサにスレッドグループ実行手段により特定されたスレッド構造体特定情報のスレッドを実行させる。【選択図】        図１
2009059181.tif 000002
【特許請求の範囲】
【請求項１】
複数のプロセッサとこの複数のプロセッサにより利用される共有データが保存された共有キャッシュメモリとをそれぞれ有する複数のプロセッサグループと、
前記複数のプロセッサによりそれぞれ実行されるスレッドの実行状態が格納された複数のスレッド構造体とこの複数のスレッド構造体を特定する複数の第１のスレッド構造体特定情報を複数のスレッドグループ毎に保持する複数のスレッドグループ管理テーブルとを有するスレッド管理データと、
前記複数のプロセッサによりそれぞれ次に実行されるスレッドのスレッド構造体を特定する複数の第２のスレッド構造体特定情報を前記複数のプロセッサに対応させて前記複数のプロセッサグループ毎に保持する複数のプロセッサグループ管理テーブルと、
利用可能なプロセッサが次に実行するスレッドの次スレッド構造体特定情報を前記複数のプロセッサグループ管理テーブル中から特定し、この次スレッド構造体特定情報と同一スレッドグループで、かつ実行可能な第３のスレッド構造体特定情報を前記スレッド管理データ中から特定し、この第３のスレッド構造体特定情報を前記複数のプロセッサグループ管理テーブル中の前記利用可能なプロセッサ以外のプロセッサの前記第２のスレッド構造体特定情報として格納するスレッドグループ実行手段と、
前記利用可能なプロセッサに前記次スレッド構造体特定情報のスレッドを実行させ、前記利用可能なプロセッサと同じグループ中のプロセッサに前記スレッドグループ実行手段により格納された前記第２のスレッド構造体特定情報のスレッドを実行させるスレッド実行手段と、
を備えたことを特徴とするマルチプロセッサシステム。
【請求項２】
前記スレッド実行手段により実行中のスレッドの実行を中断するスレッド中断手段を備え、
前記スレッド実行手段は、前記スレッド中断手段により実行を中断したスレッドを同時並列に実行させることを特徴とする請求項１記載のマルチプロセッサシステム。
【請求項３】
前記複数のスレッドグループの中から優先的に処理を実行するスレッドグループを選択するスレッドグループ選択手段を備え、
前記スレッドグループ実行手段は、前記スレッドグループ選択手段により選択されたスレッドグループの実行可能なスレッドを特定する第４のスレッド構造体特定情報を前記利用可能なプロセッサ以外のプロセッサの前記第２のスレッド構造体特定情報として格納することを特徴とする請求項１記載のマルチプロセッサシステム。
【請求項４】
同時に使用できない資源にアクセスするスレッドの開始前に中断禁止情報を前記複数のプロセッサグループ管理テーブルに格納するスレッド中断抑止手段を備え、
前記スレッド中断手段は、前記複数のプロセッサグループ管理テーブルに格納された前記中断禁止情報に基づいて前記スレッド実行手段により実行中のスレッドの実行を中断することを特徴とする請求項２記載のマルチプロセッサシステム。
【請求項５】
用途に応じた処理を実行するスレッドグループを選択する複数のスレッドグループ選択手段と、この複数のスレッドグループ選択手段を特定する情報を前記複数のプロセッサグループ管理テーブルに格納するスレッドグループ選択切替え手段とを備え、
前記スレッドグループ実行手段は、前記複数のプロセッサグループ管理テーブル中から利用すべきスレッドグループ選択手段を選択し、このスレッドグループ選択手段により選択されたスレッドグループの実行可能なスレッドを特定する第５のスレッド構造体特定情報を前記利用可能なプロセッサ以外のプロセッサの前記第２のスレッド構造体特定情報として格納することを特徴とする請求項１記載のマルチプロセッサシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数のマルチコアプロセッサを搭載したマルチプロセッサシステムに関するものである。
【背景技術】
【０００２】
同一のキャッシュメモリを使用する複数のプロセッサを搭載したマルチコアCPUがある。複数のマルチコアCPUを搭載したマルチプロセッサシステムがある。そのマルチプロセッサシステムにおけるディスパッチ方式は、キャッシュを共有するプロセッサをグルーピングし、同じ資源を利用するスレッド（プロセス）をグルーピングし、あるスレッドグループに含まれるスレッドを特定のプロセッサグループ内のプロセッサに優先的にディスパッチする方式によって、同じメモリを利用するスレッドが特定のプロセッサグループに集中することにより、プロセッサグループのもつキャッシュメモリを優先的に利用することを行っていた（例えば、特許文献１参照）。
【特許文献１】特開平１１−２５９３１８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかし、前記従来技術では、キャッシュメモリに記録されるメモリデータを同じスレッドグループのスレッドが利用する前に他のスレッドグループのスレッドがディスパッチされることによってキャッシュメモリ上の共有データが消されてしまい、キャッシュメモリを有効に活用できないという問題点がある。
この発明は前記のような問題点を解決するためになされたもので、スレッドグループの実行可能なスレッドを、プロセッサグループの各プロセッサにて、連続して実行もしくはプロセッサグループ内で並列に同時実行できるようにすることで、他のスレッドによってキャッシュメモリ上の共有データが消されることもなく、キャッシュを有効活用することを第一の目的とするものである。
また、プロセッサグループによって異なるスケジューリングアルゴリズムに切替えることで、そのプロセッサグループの中から優先的に処理を実行すべきスレッドグループを選択し、この選択したスレッドグループの処理を優先して実行することが出来ることを第二の目的とするものである。これにより、例えば、プロセッサ数の多いプロセッサグループでは実行可能なスレッド数が多いスレッドグループが優先的に選択し、かつ、他のプロセッサグループより高速なプロセッサを搭載したプロセッサグループでは重要な順にスレッドグループを選択することなどができる。
【課題を解決するための手段】
【０００４】
この発明に係るマルチプロセッサシステムは、複数のプロセッサとこの複数のプロセッサにより利用される共有データが保存された共有キャッシュメモリとをそれぞれ有する複数のプロセッサグループと、
前記複数のプロセッサによりそれぞれ実行されるスレッドの実行状態が格納された複数のスレッド構造体とこの複数のスレッド構造体を特定する複数の第１のスレッド構造体特定情報を複数のスレッドグループ毎に保持する複数のスレッドグループ管理テーブルとを有するスレッド管理データと、
前記複数のプロセッサによりそれぞれ次に実行されるスレッドのスレッド構造体を特定する複数の第２のスレッド構造体特定情報を前記複数のプロセッサに対応させて前記複数のプロセッサグループ毎に保持する複数のプロセッサグループ管理テーブルと、
利用可能なプロセッサが次に実行するスレッドの次スレッド構造体特定情報を前記複数のプロセッサグループ管理テーブル中から特定し、この次スレッド構造体特定情報と同一スレッドグループで、かつ実行可能な第３のスレッド構造体特定情報を前記スレッド管理データ中から特定し、この第３のスレッド構造体特定情報を前記複数のプロセッサグループ管理テーブル中の前記利用可能なプロセッサ以外のプロセッサの前記第２のスレッド構造体特定情報として格納するスレッドグループ実行手段と、
前記利用可能なプロセッサに前記次スレッド構造体特定情報のスレッドを実行させ、前記利用可能なプロセッサと同じグループ中のプロセッサに前記スレッドグループ実行手段により格納された前記第２のスレッド構造体特定情報のスレッドを実行させるスレッド実行手段と、を備えたものである。
【発明の効果】
【０００５】
この発明は、スレッドグループ実行手段が利用可能なプロセッサが次に実行するスレッドの次スレッド構造体特定情報を複数のプロセッサグループ管理テーブル中から特定し、この次スレッド構造体特定情報と同一スレッドグループで、かつ実行可能なスレッド構造体特定情報を前記スレッド管理データ中から特定し、このスレッド構造体特定情報を複数のプロセッサグループ管理テーブル中の前記利用可能なプロセッサ以外のプロセッサのスレッド構造体特定情報として格納し、スレッド実行手段が利用可能なプロセッサに次スレッド構造体特定情報のスレッドを実行させ、利用可能なプロセッサと同じグループ中のプロセッサにスレッドグループ実行手段により格納されたスレッド構造体特定情報のスレッドを実行させることにより、スレッドグループの実行可能なスレッドをプロセッサグループの各プロセッサにて実行できるので、他のスレッドによって共有キャッシュメモリ上の共有データが消されることなく、キャッシュを有効活用することができる。
【発明を実施するための最良の形態】
【０００６】
実施の形態１．
図１は、実施の形態１のマルチプロセッサシステムの構成図である。
本実施の形態１におけるディスパッチ方式を備えたマルチプロセッサシステムは、K個のプロセッサグループ131-1〜131-Kと1つの主記憶メモリ121を備えている。
プロセッサグループは、複数のプロセッサとそれらのプロセッサが利用する1つの共有メモリを備えている。例えば、プロセッサグループ131-1は、N個のプロセッサ101-1-1〜101-1-Nと1個の共有キャッシュメモリ111-1を備えている。プロセッサグループにおけるプロセッサの個数は同一でなくても良い。例えば、プロセッサグループ131-Kは、M個のプロセッサ101-K-1〜101-K-Mと1個の共有キャッシュメモリ111-Kを備えている。
【０００７】
主記憶メモリ121は、カーネルプログラム201とカーネルデータ211を備えている(カーネルプログラム201とカーネルデータ211はオペレーティングシステムの一部である)。
カーネルプログラム201は、プロセッサグループにてスレッドグループを実行する機能を持つスレッドグループ実行手段221と、プロセッサにてスレッドを実行する機能を持つスレッド実行手段231を備えている。
スレッドグループ実行手段221とスレッド実行手段231については後述する。
【０００８】
カーネルデータ211は、K個のプロセッサグループ管理テーブル301-1〜301-Kと1個のスレッド管理データ311を備える。
プロセッサグループ管理テーブルは、1つのプロセッサグループに対して1つ備える。例えば、プロセッサグループ131-1のプロセッサグループ管理テーブルは301-1である。同様にして、プロセッサグループ131-Kのプロセッサグループ管理テーブルは301-Kである。
プロセッサグループ管理テーブル301-1〜301-Kは、管理するプロセッサグループのプロセッサ数のプロセッサ管理テーブル321-1-1〜321-K-Mを備える。
【０００９】
プロセッサ管理テーブルは、1つのプロセッサに対して1つ備える。例えば、プロセッサグループ管理テーブル301-1が備えるプロセッサ管理テーブル数は、プロセッサグループ131-1が備えるプロセッサ数と同じN個で、プロセッサ101-1-1を管理するプロセッサ管理テーブルは321-1-1である。
プロセッサ管理テーブル321-1-1〜321-K-Mは、実行スレッド情報331-1-1〜331-K-Mと実行予約スレッド情報341-1-1〜341-K-Mを1つずつ備える。例えば、プロセッサ管理テーブル321-1-1は実行スレッド情報331-1-1と実行予約スレッド情報341-1-1を備える。
【００１０】
実行スレッド情報331-1-1〜331-K-Mは、そのプロセッサが実行しているスレッドのスレッド構造体(後述)を特定する情報(例えば、スレッド構造体へのポインタ)を保持する。
実行予約スレッド情報341-1-1〜341-K-Mは、そのプロセッサが次に実行するスレッドのスレッド構造体を特定する情報(例えば、スレッド構造体へのポインタ)を保持する。
【００１１】
スレッド管理データ311は、T個のスレッド構造体401-1〜401-TとS個のスレッドグループ管理テーブル411-1〜411-Sを備える。
スレッド構造体401-1〜401-Tは、スレッド毎に生成され、各スレッドのスレッド情報(スレッドの実行状態「実行中、実行可能、停止中」やコンテキストなど)を格納する。
スレッドグループ管理テーブル411-1〜411-Sは、スレッドグループ毎に生成され、スレッドグループ毎にグループに属するスレッドのスレッド構造体を特定する情報(例えば、スレッド構造体へのポインタ)を管理スレッド情報421-1-1〜421-S-Qに保持する。1つの管理スレッド情報は、1つのスレッド構造体を特定する情報を保持する。例えば、スレッドグループ管理テーブル411-1は、P個のスレッドから構成されたスレッドグループを管理し、各々のスレッドのスレッド構造体を特定する情報は管理スレッド情報421-1-1〜421-1-Pに保持している。
【００１２】
次に、スレッド実行手段231の動作について説明する。
スレッド実行手段231は、利用可能となったプロセッサにおいて、そのプロセッサの実行予約スレッド情報からスレッド構造体を特定し、そのプロセッサにて、特定したスレッド構造体のスレッドを実行する。
例えば、実行予約スレッド情報341-K-Mがスレッド構造体401-Tを特定する情報を保持し、プロセッサ101-K-Mが実行可能となった場合を説明する。スレッド実行手段231は、実行予約スレッド情報341-K-Mよりスレッド構造体401-Tを特定し、そのスレッド構造体401-Tの格納する情報を用いてプロセッサ101-K-Mにてスレッドを実行する。実行スレッド情報331-K-Mにそのスレッド構造体401-Tを特定する情報を持たせ、実行予約スレッド情報341-K-Mに、次に実行するスレッド構造体(例えば401-1)を特定する情報を持たせる(次に実行するスレッドのスレッド構造体を選択する手段は、オペレーティングシステムに含まれている)。
【００１３】
次に、カーネルプログラム201の処理動作を図２のフローチャートを用いて説明する。
カーネルプログラム201のスレッドグループ実行手段221は、プロセッサが利用可能となったとき動作する。スレッドグループ実行手段221は、利用可能となったプロセッサの実行予約スレッド情報を用いて、次に実行されるスレッドが属するスレッドグループを特定し、そのスレッドグループ内に実行可能なスレッドが複数存在するか検索する（ステップＳ１）。
具体的には、スレッドグループ実行手段221は、利用可能となったプロセッサの実行予約スレッド情報の中から次に実行するスレッドのスレッド構造体を特定する情報を検索し、この検索したスレッド構造体を特定する情報と同じグループ内のスレッド構造体を特定する情報をスレッドグループ管理テーブル411-1〜411-Sの中から検索し、さらにスレッドグループ管理テーブル411-1〜411-S中から検索したスレッド構造体のスレッド情報の中から実行可能なスレッドが複数存在するか検索する（スレッド情報の中には、実行中、実行可能、停止中のスレッドの実行状態が格納されている）。
【００１４】
複数の実行可能なスレッドが存在する場合(Y)は、そのプロセッサが属するプロセッサグループの他のプロセッサの実行予約スレッド情報に、検索した実行可能なスレッドのスレッド構造体を特定する情報を格納する（ステップＳ２）。その後、もしくは複数の実行可能なスレッドが存在しない場合(N)は、スレッド実行手段231が、利用可能となったプロセッサにてスレッドを実行させる（ステップＳ３）。
【００１５】
例えば、
実行予約スレッド情報341-K-Mがスレッド構造体401-Tを特定する情報を保持しており、
スレッド構造体401-1,401-2,401-Tの各スレッドが実行可能であり、
管理スレッド情報421-S-1はスレッド構造体401-1を特定する情報を保持しており、
管理スレッド情報421-S-2はスレッド構造体401-2を特定する情報を保持しており、
管理スレッド情報421-S-Qはスレッド構造体401-Tを特定する情報を保持しており、
プロセッサ101-K-Mが実行可能となった場合について説明する。
【００１６】
ステップＳ１にてスレッドグループ実行手段221は、実行予約スレッド情報341-K-Mを用いて、スレッド構造体401-Tを特定する。スレッドグループ管理テーブル411-1〜411-Sの各々の管理スレッド情報421-1-1〜421-S-Qを検索し、スレッド構造体401-Tを特定する情報を保持する管理スレッド情報421-S-Qを特定する。この特定した管理スレッド情報421-S-Qを保持するスレッドグループ管理テーブル411-S内に備える管理スレッド情報421-S-1〜421-S-Qを用いて、特定されるスレッド構造体全部から実行可能なスレッドを検索し、スレッド構造体401-1,401-2を特定する。
【００１７】
実行可能なスレッドが複数見つかり(Y)、ステップＳ２にてスレッドグループ実行手段231は、実行予約スレッド情報341-K-1にスレッド構造体401-1を特定する情報を格納し、実行予約スレッド情報341-K-2にスレッド構造体401-2を特定する情報を格納する。
その後、ステップＳ３にてスレッド実行手段221が、スレッド構造体401-Tの格納する情報を用いてプロセッサ101-K-Mにてスレッドを実行させる。
【００１８】
この場合、プロセッサ101-K-1が利用可能となった後、スレッド構造体401-1のスレッドがプロセッサ101-K-1にて次に動作する。つまり、スレッド構造体401-Tのスレッドと同じスレッドグループのスレッド(スレッド構造体401-1)がプロセッサ101-K-1で動作するため、スレッド構造体401-Tのスレッドが共有キャッシュ上に残したデータを、他が共有キャッシュを使うことによって消される前にスレッド構造体401-1のスレッドが利用する可能性が高い。よって、共有キャッシュメモリを有効利用することが出来る。
【００１９】
以上のように本実施の形態によれば、スレッドグループ実行手段221が、同プロセッサグループ内のプロセッサが次に実行するスレッドを特定することにより、スレッドグループの実行可能なスレッドをプロセッサグループの各プロセッサにて実行できるので、他のスレッドによって共有キャッシュメモリ上の共有データが消されることなく、キャッシュを有効活用することができる。
また、スレッドグループがプロセッサグループ上で連続して実行する頻度が上がり、プロセッサグループにて利用する共有キャッシュメモリのデータが削除されないうちにこのデータを利用することができるので、共有キャッシュメモリのデータヒット率を上げることが可能となる。
【００２０】
実施の形態２．
実施の形態１では、スレッドグループの同時並列実行の実現は、プロセッサグループの他プロセッサ上で実行中のスレッドがそのプロセッサを解放するまで行われなかったが、本実施の形態では、意図的にそれらのプロセッサを解放することで、スレッドグループの同時並行実行を実現する場合について説明する。
【００２１】
本実施の形態のマルチプロセッサシステムの構成は、主記憶メモリ121のカーネルプログラム201にスレッド中断手段241を追加した以外は図１と同様である。
図３は、本実施の形態における主記憶メモリ121のカーネルプログラム201の構成図である。図において、主記憶メモリ121のカーネルプログラム201はスレッドグループ実行手段221とスレッド実行手段231とスレッド中断手段241とを備える。
【００２２】
次に、スレッド中断手段241の動作について説明する。
スレッドは、実行内容を全て実行した時、もしくは意図的に動作を停止した時(例えば、他スレッドの処理終了を待機したり、ハードウェアの返答を待機したりする時)、もしくはハードウェアによる割込みを実行しているプロセッサが受けた時、もしくは実行しているプロセッサの電源が遮断された時などに、スレッドの実行を中断する。
スレッド中断手段241は、意図的にハードウェアによる割込みをプロセッサに発行などして、スレッドの実行を中断する。続いて、実行を中断したスレッドの情報をスレッド構造体に格納し、中断したスレッドを実行中から実行可能へ状態推移(スレッド構造体の内容を変更)する。
【００２３】
次に、カーネルプログラム201の処理動作を図４のフローチャートを用いて説明する。
カーネルプログラム201のスレッドグループ実行手段221は、プロセッサが利用可能となった時に動作する。まず、スレッドグループ実行手段221は、利用可能となったプロセッサの実行予約スレッド情報を用いて、次に実行されるスレッドが属するスレッドグループを特定し、そのスレッドグループ内に実行可能なスレッドが複数存在するか検索する（ステップＳ１）。
複数のスレッドが存在しない場合(N)は、スレッド実行手段231が、利用可能となったプロセッサにてスレッドを実行させる（ステップＳ３）。
【００２４】
複数のスレッドが存在する場合(Y)は、ステップＳ２で、そのプロセッサが属するプロセッサグループの他のプロセッサの実行予約スレッド情報に、検索した実行可能なスレッドのスレッド構造体を特定する情報を格納することにより、同じプロセッサグループの実行予約スレッド情報を変更する。その後、スレッド中断手段241が、実行予約スレッド情報を変更したプロセッサにて実行中のスレッドを中断する（ステップＳ４）。その後、スレッド実行手段231が、スレッドの中断により利用可能となったプロセッサにてスレッドを実行させる（ステップＳ５）。
【００２５】
例えば、
実行予約スレッド情報341-K-Mがスレッド構造体401-Tを特定する情報を保持しており、
スレッド構造体401-1, 401-2, 401-Tの各スレッドが実行可能であり、
管理スレッド情報421-S-1がスレッド構造体401-1を特定する情報を保持しており、
管理スレッド情報421-S-2がスレッド構造体401-2を特定する情報を保持しており、
管理スレッド情報421-S-Qがスレッド構造体401-Tを特定する情報を保持しており、
プロセッサ101-K-Mが実行可能となった場合について説明する。
【００２６】
まず、ステップＳ１にて実行予約スレッド情報341-K-Mを用いて、スレッド構造体401-Tを特定する。スレッドグループ管理テーブル411-1〜411-Sの各々の管理スレッド情報421-1-1〜421-S-Qを検索し、スレッド構造体401-Tを特定する情報を保持する管理スレッド情報421-S-Qを特定する。スレッドグループ管理テーブル411-S内に備える管理スレッド情報421-S-1〜421-S-Qを用いて特定されるスレッド構造体全部から実行可能なスレッドを検索し、スレッド構造体401-1,401-2を特定する。
【００２７】
ステップＳ１にて実行可能なスレッドが複数見つかると(Y)、ステップＳ２にてスレッドグループ実行手段221は、実行予約スレッド情報341-K-1にスレッド構造体401-1を特定する情報を格納し、実行予約スレッド情報341-K-2にスレッド構造体401-2を特定する情報を格納する（格納先の実行予約スレッド情報は任意選択）。
その後、ステップＳ４B01にてスレッド中断手段241を用いて、プロセッサ101-K-1, 101-K-2, 101-K-Mにて実行しているスレッドを中断する。
その後、ステップＳ５B02にてスレッド実行手段231は、実行予約スレッド情報341-K-1を用いて特定されるスレッド構造体401-1を用い、プロセッサ101-K-1にてスレッドを実行させる。
【００２８】
同様に、スレッド実行手段231は、実行予約スレッド情報341-K-2, 341-K-Mを用いて特定されるスレッド構造体401-2,401-Tを用い、プロセッサ101-K-2, 101-K-Mにてスレッドを実行させる。
この場合、プロセッサ101-K-1,101-K-2,101-K-Mは同時に実行を開始し、これらのプロセッサでは同じスレッドグループのスレッド(管理スレッド情報421-S-1, 421-S-2, 421-S-Qから特定されるスレッド構造体401-1, 401-2, 401-Tのスレッド)が動作する。つまり、スレッド構造体401-1, 401-2, 401-Tのスレッドが共有するデータが共有キャッシュメモリ上に保持される。よって、共有キャッシュメモリを有効利用することが出来る。
【００２９】
以上のように本実施の形態によれば、同一プロセッサグループ内のプロセッサにて実行中スレッドの実行状態を実行中断から実行可能へ状態推移することにより、プロセッサグループにおけるスレッドグループの実行可能な複数のスレッドを同時並列実行させる。また、これにより、他のスレッドによってキャッシュメモリ上の共有データが消されることもなく、キャッシュを有効活用することが可能となる。
【００３０】
実施の形態３．
実施の形態１では、スレッドグループに属するスレッドが実行される場合にプロセッサグループでスレッドグループを実行していたが、本実施の形態では、並列実行可能なスレッドグループの有無を検索することで、スレッドグループの優先並列実行を実現する場合について説明する。
【００３１】
本実施の形態のマルチプロセッサシステムの構成は、主記憶メモリ121のカーネルプログラム201にスレッドグループ選択手段251を追加した以外は図１と同様である。
図５は、本実施の形態における主記憶メモリ121のカーネルプログラム201の構成図である。図において、主記憶メモリ121のカーネルプログラム201はスレッドグループ実行手段221とスレッド実行手段231とスレッドグループ選択手段251とを備える。
【００３２】
次に、スレッドグループ選択手段251の動作について説明する。
スレッドグループ選択手段251は、全てのスレッドグループの中から複数の実行可能なスレッドを含むスレッドグループを検索する。また、それらのスレッドグループの中から優先的に処理を実行すべきスレッドグループを選択する。もしくは検索した結果見つからなかった場合、何も選択しない。
例えば、
スレッド構造体401-1, 401-2, 401-3, 401-Tの各スレッドが実行可能であり、
管理スレッド情報421-1-1, 421-2-2がスレッド構造体401-1を特定する情報を保持しており、
管理スレッド情報421-1-2がスレッド構造体401-2を特定する情報を保持しており、
管理スレッド情報421-S-2がスレッド構造体401-3を特定する情報を保持しており、
管理スレッド情報421-S-Qがスレッド構造体401-Tを特定する情報を保持している場合、
スレッドグループ選択手段251は複数の実行可能なスレッドを含むスレッドグループを管理するスレッドグループ管理テーブル411-1, 411-Sを特定し、これらのスレッドグループ管理テーブルから任意(ここでは411-1か411-S)のスレッドグループを選択する。
【００３３】
次に、カーネルプログラム201の処理動作を図６のフローチャートを用いて説明する。
カーネルプログラム201のスレッドグループ実行手段221は、プロセッサが利用可能となった時に動作する。まず、スレッドグループ実行手段221は、スレッドグループ選択手段251を用いて実行可能なスレッドを複数含むスレッドグループを検索する（ステップＳ１１）。
実行可能なスレッドを複数含むスレッドグループが存在する場合(Y)は、スレッドグループ選択手段251が複数のプロセッサグループの中から優先的に処理を実行すべきスレッドグループを選択する（ステップＳ１２）。その後、選択したスレッドグループの実行可能なスレッドのスレッド構造体を特定する情報を、利用可能となったプロセッサが属するプロセッサグループの他プロセッサの実行予約スレッド情報に格納する（ステップＳ１３）。その後、もしくは実行可能なスレッドを複数含むスレッドグループが存在しない場合(N)は、スレッド実行手段231が、利用可能となったプロセッサにてスレッドを実行させる（ステップＳ３）。
【００３４】
例えば、
スレッド構造体401-1, 401-2, 401-3, 401-4, 401-Tの各スレッドが実行可能であり、
実行予約スレッド情報341-1-1がスレッド構造体401-4を特定する情報を保持しており、
管理スレッド情報421-1-1がスレッド構造体401-1を特定する情報を保持しており、
管理スレッド情報421-1-2がスレッド構造体401-2を特定する情報を保持しており、
管理スレッド情報421-2-2がスレッド構造体401-1を特定する情報を保持しており、
管理スレッド情報421-3-3がスレッド構造体401-4を特定する情報を保持しており、
管理スレッド情報421-S-2がスレッド構造体401-3を特定する情報を保持しており、
管理スレッド情報421-S-Qがスレッド構造体401-Tを特定する情報を保持しており、
プロセッサ101-1-1が実行可能となった場合について説明する。
【００３５】
まず、ステップＳ１１にてスレッドグループ実行手段221が、スレッドグループ選択手段251を用いて実行可能なスレッドを複数含むスレッドグループを検索する。スレッドグループ選択手段251は、スレッドグループ管理テーブル411-1, 411-Sを特定する。
ステップＳ１１C01にて実行可能なスレッドを複数含むスレッドグループが見つかり(Y)、ステップＳ１２にてスレッドグループ選択手段251を用いて、優先的に処理を実行すべきスレッドグループを選択する。ここでは、スレッドグループ管理テーブル411-Sのスレッドグループを選択したとする。
【００３６】
その後、ステップＳ１３にてスレッドグループ実行手段221は、スレッドグループ管理テーブル411-Sの管理スレッド情報421-S-1〜421-S-Qから、スレッド構造体401-3, 401-Tのスレッドが実行可能であることを特定する。スレッドグループ実行手段221は、実行予約スレッド情報341-1-1にスレッド構造体401-3を特定する情報を格納する。同様に、実行予約スレッド情報341-1-2にスレッド構造体401-Tを特定する情報を格納する。
その後、ステップＳ３にてスレッド実行手段231は、プロセッサ101-1-1にてスレッド構造体401-3のスレッドを実行させる。
同条件下で、実施の形態1のスレッドグループ実行手段221を用いた場合、実行予約スレッド情報341-1-1によって特定されるスレッド構造体401-4のスレッドが属するスレッドグループ411-3は、他に実行可能なスレッドを含んでおらず、プロセッサグループ131-1にてスレッドグループの実行を行うことが出来ない。しかし、本実施の形態のスレッドグループ実行手段221の場合は、別の実行可能なスレッドグループ(ここでは411-S)を検索し、プロセッサグループ131-1にてスレッドグループの実行を行うことが出来る。
【００３７】
以上のように本実施の形態によれば、複数のプロセッサグループの中から優先的に処理を実行すべきスレッドグループを選択し、このスレッドグループのスレッドを実行することにより、実行可能な複数のスレッドを有する複数のスレッドグループの中から優先的に処理を実行すべきスレッドグループのスレッドの処理を実行することができる。
【００３８】
実施の形態４．
実施の形態２では、スレッドの実行状態を実行中の処理内容に関わらず変更しており、実行内容によってはこれを好まない場合(例えば、共有メモリの内容を複数箇所変更中のスレッドが処理の途中で中断されると、内容に一貫性が取れなくなってしまう)がある。本実施の形態では、各プロセッサの利用予約を行い、スレッドの実行中断を許しても良い時に中断することにより、より安全なスレッドグループの同時並列実行を実現する場合について説明する。
【００３９】
本実施の形態のマルチプロセッサシステムの構成は、主記憶メモリ121のカーネルプログラム201の構成とカーネルデータ211との内部構成が他の実施の形態と違う以外は同様である。
図７は、本実施の形態における主記憶メモリ121のカーネルプログラム201の構成図である。図において、主記憶メモリ121のカーネルプログラム201は、スレッドグループ実行手段221とスレッド実行手段231とスレッド中断手段241とスレッドグループ選択手段251とスレッド中断抑止手段261とを備える。
図８は、本実施の形態における主記憶メモリ121のカーネルデータ211の構成図である。図において、主記憶メモリ121のカーネルデータ211のプロセッサグループ管理テーブル301-1〜301-Kは、それぞれ、プロセッサ管理テーブル321-1-1〜321-K-Mとプロセッサグループ予約情報361-1〜361-Kとを備え、プロセッサグループ管理テーブル301-1〜301-Kは、それぞれ、実行スレッド情報331-1-1〜331-K-Mと実行予約スレッド情報341-1-1〜341-K-Mとプロセッサ予約情報351-1-1〜351-K-Mを備える。
【００４０】
ここで、プロセッサ予約情報351-1-1〜351-K-Mは、各プロセッサ管理テーブル321-1-1〜321-K-Mに1つずつ備える。プロセッサ予約情報351-1-1〜351-K-Mは、そのプロセッサにおいて実行中のスレッドを中断可能であるかを示す情報(例えばフラグ)を格納している。
また、プロセッサグループ予約情報361-1〜361-Kは、各プロセッサグループ管理テーブル301-1〜301-Kに1つずつ備える。プロセッサグループ予約情報361-1〜361-Kは、そのプロセッサグループにおいて実行したいスレッドグループが存在し実行を予約しているかを示す情報(例えばフラグ)を格納している。
【００４１】
次に、スレッド中断抑止手段261の動作について説明する。
スレッド中断抑止手段261は、スレッドがクリティカルセクションに入る前(例えば、同時に使用できない資源にアクセスする処理を始める前)に動作する。スレッド中断抑止手段261は、クリティカルセクションに入るスレッドを実行しているプロセッサのプロセッサ管理テーブル内のプロセッサ予約情報に中断禁止である情報を格納する。
例えば、プロセッサ101-1-1にて実行中のスレッド(スレッド構造体401-1)がクリティカルセクションに入る場合、スレッド中断抑止手段261はプロセッサ予約情報351-1-1に中断禁止である情報を格納する。
【００４２】
また、スレッド中断抑止手段261は、スレッドがクリティカルセクションから出た後(例えば、同時に使用できない資源にアクセスする処理を終えた後)に動作する。スレッド中断抑止手段261は、クリティカルセクションから出たスレッドを実行しているプロセッサのプロセッサ管理テーブル内のプロセッサ予約情報に中断可能である情報を格納する。
【００４３】
次に、スレッド中断手段241の動作について説明する。
スレッド中断手段241は、実行を中断させたいスレッドが実行しているプロセッサのプロセッサ予約情報よりスレッドが中断可能であるか判定し、中断可能であれば、スレッドの実行を中断する。中断禁止であれば、何もしない。
【００４４】
次に、カーネルプログラム201の処理動作を図９のフローチャートを用いて説明する。
スレッドグループ実行手段221は、プロセッサが利用可能となった時に動作する。
スレッドグループ実行手段221は、まず、利用可能となったプロセッサのプロセッサグループ予約情報371-1〜371-Kより、このプロセッサグループがスレッドグループによって予約されているか確認する（ステップＳ２１）。
予約されていない場合(N)は、スレッドグループ実行手段221は、利用可能となったプロセッサの実行予約スレッド情報を用いて、次に実行されるスレッドが属するスレッドグループを特定し、そのスレッドグループ内に実行可能なスレッドが複数存在するか検索する（ステップＳ１）。
ステップＳ１で検索の結果、複数のスレッドが存在する場合(Y)は、利用可能となったプロセッサのプロセッサグループ予約情報に、プロセッサグループにおいて実行したいスレッドグループが存在する情報を格納(例えばフラグをセットする)する（ステップＳ２２）。
【００４５】
その後、もしくステップＳ２１でプロセッサグループが予約されている場合(Y)は、プロセッサグループのプロセッサが中断可能か確認する（ステップＳ２３）。
ステップＳ２３で中断禁止のプロセッサが存在した場合(N)、もしくはステップＳ１で複数のスレッドが存在しない場合(N)、スレッド実行手段231が、利用可能となったプロセッサにてスレッドを実行させる（ステップＳ３）。
また、ステップＳ２３で中断禁止のプロセッサが存在しない場合(Y)は、スレッドグループ選択手段251が、実行可能なスレッドを複数含むスレッドグループを選択する（ステップＳ１２）。
【００４６】
次に、選択したスレッドグループの実行可能なスレッドのスレッド構造体を特定する情報を、利用可能となったプロセッサが属するプロセッサグループの他プロセッサの実行予約スレッド情報に格納する（ステップＳ１３）。
その後、スレッド中断手段241がプロセッサグループのプロセッサ上で実行しているスレッドを中断する（ステップＳ４）。
次に、スレッドグループ実行手段221が、プロセッサグループのプロセッサグループ予約情報にスレッドグループを実行した情報を格納し、プロセッサグループの予約を解除する(例えばフラグをクリアする)（ステップＳ２４）。
その後、スレッド実行手段231が、スレッドの実行を中断したことにより利用可能となったプロセッサにて、先ほど実行予約スレッドとして指定したスレッドを実行させる（ステップＳ５）。
【００４７】
例えば、
スレッド構造体401-1, 401-2, 401-3, 401-4, 401-Tの各スレッドが実行可能であり、
実行予約スレッド情報341-1-1がスレッド構造体401-4を特定する情報を保持しており、
管理スレッド情報421-1-1がスレッド構造体401-1を特定する情報を保持しており、
管理スレッド情報421-1-2がスレッド構造体401-2を特定する情報を保持しており、
管理スレッド情報421-2-2がスレッド構造体401-1を特定する情報を保持しており、
管理スレッド情報421-3-3がスレッド構造体401-4を特定する情報を保持しており、
管理スレッド情報421-S-2がスレッド構造体401-3を特定する情報を保持しており、
管理スレッド情報421-S-Qがスレッド構造体401-Tを特定する情報を保持しており、
プロセッサグループ予約情報361-1に実行したいスレッドグループが存在しない情報を保持しており、
各プロセッサ予約情報351-1-1〜351-1-Nに中断可能である情報を保持しており、
プロセッサ101-1-1が実行可能となった場合を説明する。
【００４８】
ステップＳ２１にてスレッドグループ実行手段221は、プロセッサグループ予約情報361-1を参照し、プロセッサグループ131-1がスレッドグループによって予約されているか確認する。プロセッサグループ予約情報361-1には、実行したいスレッド情報が存在しない情報を保持しており、ステップＳ１へ処理を移す。
ステップＳ１にてスレッドグループ実行手段221は、実行予約スレッド情報341-1-1を参照しスレッド構造体401-4を特定し、スレッドグループ管理テーブル411-Sを特定する。
スレッド実行手段231は、実行可能なスレッドのスレッド構造体401-3, 401-Tを参照する管理スレッド情報421-S-2, 421-S-Qをスレッドグループ管理テーブル411-S内から見つける。これによりスレッド実行可能であると判断し、ステップＳ２２に処理を移す。
ステップＳ２２にてスレッド実行手段231は、プロセッサグループ予約情報361-1にグループスレッドを実行したい情報を格納する。
【００４９】
次に、ステップＳ２３にてスレッド実行手段231は、利用可能となったプロセッサ101-1-1が属するプロセッサグループの各プロセッサ予約情報351-1-1〜351-1-Nを検索し、中断可能であるか確認する。この例では中断可能であるので、ステップＳ１２に制御を移を複数含む任意のスレッドグループを選択する。ここではスレッドグループ管理テーブル411-す。
ステップＳ２２にてスレッドグループ選択手段251は、実行可能なスレッドSを選択したとする。
その後、ステップＳ１３にてスレッドグループ実行手段221は、スレッド構造体401-3を特定する情報を実行予約スレッド情報341-1-1に格納し、スレッド構造体401-Tを特定する情報を実行予約スレッド情報341-1-2に格納する。
【００５０】
次に、ステップＳ４にてスレッド実行中断手段242は、プロセッサ101-1-1, 101-1-2にて実行中のスレッドを中断する。ステップＳ２４にてスレッドグループ実行手段221はプロセッサグループ予約情報361-1に、実行したいスレッドグループが存在しない情報を格納する。
その後、ステップＳ５にてスレッド実行手段231は、プロセッサ101-1-1にてスレッド構造体401-3のスレッドを実行させ、プロセッサ101-1-2にてスレッド構造体401-Tのスレッドを実行させる。
【００５１】
以上のように本実施の形態によれば、同一プロセッサグループ内のプロセッサにて実行中スレッドの実行状態を実行中断から実行可能へ状態推移するときに、スレッドの実行中断を許しても良い時にのみ実行中断することにより、より安全なスレッドグループの同時並列実行を実現することができる。
また、プロセッサグループの利用を予約し、スレッドの実行内容を考慮し、中断を抑制することにより、内容の一貫性を保ち、かつ、スレッドグループの実行可能な複数のスレッドの同時並列実行を実現することが出来る。
【００５２】
実施の形態５．
実施の形態４では、各プロセッサグループで同じスレッドグループ選択手段を利用する場合について説明したが、本実施の形態では、スレッドグループ選択手段を複数持たせ、各プロセッサグループによって利用するスレッドグループ選択手段を切替え、プロセッサグループ毎に用途に応じたスレッドグループの同時並列実行を実現する場合について説明する。
【００５３】
本実施の形態のマルチプロセッサシステムの構成は、主記憶メモリ121のカーネルプログラム201とカーネルデータ211との内部構成が他の実施の形態と違う以外は同様である。
図１０は、本実施の形態における主記憶メモリ121のカーネルプログラム201の構成図である。図において、主記憶メモリ121のカーネルプログラム201は、スレッドグループ実行手段221とスレッド実行手段231とスレッド中断手段241とスレッド中断抑止手段261と、X個のスレッドグループ選択手段251-1〜251-Xとスレッドグループ選択切替え手段271とを備える。
図１１は、本実施の形態における主記憶メモリ121のカーネルデータ211の構成図である。図において、主記憶メモリ121のカーネルデータ211のプロセッサグループ管理テーブル301-1〜301-Kは、図８で示すプロセッサグループ管理テーブル301-1〜301-Kにスレッドグループ選択切替え情報371-1〜371-Kを備えた以外は図８と同様である。ここで、スレッドグループ選択切替え情報371-1〜371-Kは、各プロセッサグループ管理テーブル301-1〜301-Kに1つずつ備えられており、そのプロセッサグループで利用されるスレッドグループ選択手段251-1〜251-Xを特定する情報(例えば番号)が格納されている。
【００５４】
次に、スレッドグループ選択切替え手段271の動作について説明する。
スレッドグループ選択切替え手段271は、オペレーティングシステム(例えば起動における設定時など)やユーザなどからの呼び出しによって起動する。プロセッサグループで利用するスレッドグループ選択手段251-1〜251-Xを特定する情報(例えば番号)をスレッドグループ選択切替え情報371-1〜371-Kに格納する。
【００５５】
次に、カーネルプログラム201の処理動作を図１２のフローチャートを用いて説明する。
なお、本実施の形態におけるカーネルプログラム201の処理動作は、実施の形態４で説明した図９のフローチャートにステップＳ３１の処理動作を加えたほかは同様の処理であるため、ここではステップＳ３１の処理を中心に動作の説明を行う。
ステップＳ２３でプロセッサグループのプロセッサが中断可能か確認し、中断可能である、即ち、中断禁止のプロセッサが存在しない場合(Y)は、プロセッサグループのスレッドグループ選択切替え情報371-1〜371-Kを参照し、プロセッサグループで利用するスレッドグループ選択手段251-1〜251-Xを特定する（ステップＳ３１）。
その後、ステップＳ１２でスレッドグループを選択する。ただし、このとき利用するスレッドグループ選択手段はステップＳ３１にて特定したスレッドグループ選択手段を用いる。
以降の処理動作は、図９のステップＳ１３〜ステップＳ５と同様である。
【００５６】
例えば、
スレッド構造体401-1, 401-2, 401-3, 401-4, 401-Tの各スレッドが実行可能であり、
実行予約スレッド情報341-1-1がスレッド構造体401-4を特定する情報を保持しており、
管理スレッド情報421-1-1がスレッド構造体401-1を特定する情報を保持しており、
管理スレッド情報421-1-2がスレッド構造体401-2を特定する情報を保持しており、
管理スレッド情報421-2-2がスレッド構造体401-1を特定する情報を保持しており、
管理スレッド情報421-3-3がスレッド構造体401-4を特定する情報を保持しており、
管理スレッド情報421-S-2がスレッド構造体401-3を特定する情報を保持しており、
管理スレッド情報421-S-Qがスレッド構造体401-Tを特定する情報を保持しており、
プロセッサグループ予約情報361-1に実行したいスレッドグループが存在しない情報を保持しており、
各プロセッサ予約情報351-1-1〜351-1-Nに中断可能である情報を保持しており、
スレッドグループ選択切替え情報371-1にスレッドグループ選択手段251-2を利用する情報を保持しており、
プロセッサ101-1-1が実行可能となった場合を説明する。
【００５７】
ステップＳ２１にてスレッドグループ実行手段221は、プロセッサグループ予約情報361-1を参照し、プロセッサグループ131-1がスレッドグループによって予約されているか確認する。プロセッサグループ予約情報361-1には実行したいスレッド情報が存在しない情報を保持しており、ステップＳ１へ処理を移す。
ステップＳ１にてスレッドグループ実行手段221は、実行予約スレッド情報341-1-1を参照しスレッド構造体401-4を特定し、スレッドグループ管理テーブル411-Sを特定する。スレッド実行手段231はスレッドグループ管理テーブル411-S内に実行可能なスレッドのスレッド構造体401-3, 401-Tを参照する管理スレッド情報421-S-2, 421-S-Qをスレッドグループ管理テーブル411-S内から見つける。これによりスレッド実行可能であると判断し、ステップＳ２２に処理を移す。
ステップＳ２２にてスレッド実行手段231は、プロセッサグループ予約情報361-1にグループスレッドを実行したい情報を格納する。
【００５８】
次に、ステップＳ２３にてスレッド実行手段231は、利用可能となったプロセッサ101-1-1が属するプロセッサグループの各プロセッサ予約情報351-1-1〜351-1-Nを検索し、中断可能であるか確認する。この例では中断可能（Y）であるので、ステップＳ３１に制御を移す。
ステップＳ３１にてスレッドグループ実行手段221は、スレッドグループ選択切替え情報371-1を参照し、スレッドグループ選択手段251-2を特定する。
次に、ステップＳ１２にてスレッドグループ選択手段251-2は、実行可能なスレッドを複数含む任意のスレッドグループを選択する。ここではスレッドグループ管理テーブル411-Sを選択したとする。
【００５９】
その後、ステップＳ１３にてスレッドグループ実行手段221は、スレッド構造体401-3を特定する情報を実行予約スレッド情報341-1-1に格納し、スレッド構造体401-Tを特定する情報を実行予約スレッド情報341-1-2に格納する。
さらに、ステップＳ４にてスレッド実行中断手段242は、プロセッサ101-1-1, 101-1-2にて実行中のスレッドを中断する。
次に、ステップＳ２４にてスレッドグループ実行手段221は、プロセッサグループ予約情報361-1に実行したいスレッドグループが存在しない情報を格納する。
その後、ステップＳ５にてスレッド実行手段231は、プロセッサ101-1-1にてスレッド構造体401-3のスレッドを実行し、プロセッサ101-1-2にてスレッド構造体401-Tのスレッドを実行する。
【００６０】
以上のように本実施の形態によれば、スレッドグループ選択切替え手段によりスレッドグループ選択手段をプロセッサグループ毎に選択することで、特定のプロセッサグループにて用途に応じたスレッドグループの実行可能な複数のスレッドを優先的に動作させることが可能となる。
また、プロセッサグループ毎に用途に応じたスレッドグループの選択を行うことが可能であり、例えば、プロセッサ数の多いプロセッサグループでは実行可能なスレッド数が多いスレッドグループを優先的に選択し、かつ、他のプロセッサグループより高速なプロセッサを搭載したプロセッサグループでは優先度の高い順にスレッドグループを選択することができる。
【図面の簡単な説明】
【００６１】
【図１】実施の形態１のマルチプロセッサシステムの構成図。
【図２】実施の形態１におけるカーネルプログラム201の処理動作を示すフローチャート。
【図３】実施の形態２における主記憶メモリ121のカーネルプログラム201の構成図。
【図４】実施の形態１におけるカーネルプログラム201の処理動作を示すフローチャート。
【図５】実施の形態３における主記憶メモリ121のカーネルプログラム201の構成図。
【図６】実施の形態３におけるカーネルプログラム201の処理動作を示すフローチャート。
【図７】実施の形態４における主記憶メモリ121のカーネルプログラム201の構成図。
【図８】実施の形態４における主記憶メモリ121のカーネルデータ211の構成図。
【図９】実施の形態４におけるカーネルプログラム201の処理動作を示すフローチャート。
【図１０】実施の形態５における主記憶メモリ121のカーネルプログラム201の構成図。
【図１１】実施の形態５における主記憶メモリ121のカーネルデータ211の構成図。
【図１２】実施の形態５におけるカーネルプログラム201の処理動作を示すフローチャート。
【符号の説明】
【００６２】
１０１−１−１〜１０１−Ｋ−Ｎ  プロセッサ、１１１−１〜１１１−Ｋ  共有キャッシュメモリ、１２１  主記憶メモリ、１３１−１〜１３１−Ｋ  プロセッサグループ、２１１  カーネルデータ、２２１  スレッドグループ実行手段、２３１  スレッド実行手段、３０１−１〜３０１−Ｋ  プロセッサグループ管理テーブル、３１１  スレッド管理データ、３２１−１−１〜３２１−Ｋ−Ｍ  プロセッサ管理テーブル、３３１−１−１〜３３１−Ｋ−Ｍ  実行スレッド情報、３４１−１−１〜３４１−Ｋ−Ｍ  実行予約スレッド情報、４０１−１〜４０１−Ｔ  スレッド構造体、４１１−１〜４１１−Ｓ  スレッドグループ管理テーブル、４２１−１−１〜４２１−Ｓ−Ｑ  管理スレッド情報。
【図１】
2009059181.tif 000003
【図２】
2009059181.tif 000004
【図３】
2009059181.tif 000005
【図４】
2009059181.tif 000006
【図５】
2009059181.tif 000007
【図６】
2009059181.tif 000008
【図７】
2009059181.tif 000009
【図８】
2009059181.tif 000010
【図９】
2009059181.tif 000011
【図１０】
2009059181.tif 000012
【図１１】
2009059181.tif 000013
【図１２】
2009059181.tif 000014