(57)【要約】      （修正有）【課題】セマフォまたはスピン・ロックなしに、マルチスレッド・コンピュータにおけるデータ構造の割振り解除をする。【解決手段】データ構造へのアクセスは共用ポインタによって管理され、この共用ポインタは初めに、データ構造を割振り解除するための要求を受け取ると、スレッドに対してデータ構造が使用できないことを示す値に設定される。共用ポインタのコピーをすでに保持してデータ構造にアクセスすることのできる任意のスレッドはすべてが監視され、いずれかのスレッドがデータ構造にアクセスするために共用ポインタを使用することのできるプログラム・コードを実行中であるかどうかを判別する。条件に合致すると、共用ポインタを介してデータ構造に潜在的にアクセスできるスレッドはないことが保証され、したがってデータ構造を割振り解除することができる。【選択図】図１
2004295882.tif 000002
【特許請求の範囲】
【請求項１】
区画マネージャによって管理される複数の論理区画を含むタイプの論理的に区分されたコンピュータから区画を削除する方法であり、前記論理的に区分されたコンピュータはその上で実行中の複数のスレッドをさらに含み、前記区画マネージャは削除される区画に関連付けられた区画制御ブロックへのアクセス権を有するものであって、前記方法は、
第１のスレッドが前記区画マネージャのプログラム・コードを入力すると必ず、複数スレッドのうちの第１のスレッドに関連付けられたシーケンス番号を、奇数値および偶数値のうちの１つに増分すること、
前記第１のスレッドがプログラム・コードを終了すると必ず、奇数値および偶数値のうちの他方からのシーケンス番号を増分すること、および
前記区画制御ブロックを、
前記区画制御ブロックを指す共用ポインタを、前記区画制御ブロックが使用可能でないことを示すｎｕｌｌ値に設定すること、
前記シーケンス番号の値を獲得すること、
第１のスレッドが非活動状態である第１の条件と、第１のスレッドが区画マネージャ内のアイドル・ループ内で実行中である第２の条件と、シーケンス番号が奇数値および偶数値のうちの１つに設定されている第３の条件と、シーケンス番号が獲得された値から変更された第４の条件とを含む、複数の条件のうちの少なくとも１つに合致することに応答して、第１のスレッドが共用ポインタをもはや使用していないことを判別することを含み、各スレッドが前記共用ポインタを使用するプログラム・コードを実行中であるかどうかを判別するために各スレッドを監視することによって、前記複数スレッドのそれぞれがもはや共用ポインタを使用しなくなるまで待機すること、および
前記複数スレッドそれぞれがもはや前記共用ポインタを使用中でなくなるまで待機した後に、前記区画制御ブロックを割振り解除することによって、割振り解除することを含む方法。
【請求項２】
コンピュータ内で実行中の複数のスレッドによってアクセス可能なデータ構造を割振り解除する方法であって、前記方法は、前記データ構造を割振り解除する要求に応答して、
前記データ構造を指す共用ポインタを、その後前記ポインタにアクセスするスレッドに対して前記データ構造が使用可能でないことを示す所定の値に設定すること、
前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラム・コードを各スレッドが実行中であるかどうかを判別するために各スレッドを監視することによって、前記複数のスレッドがもはや前記共用ポインタを使用しなくなるまで待機すること、および
前記複数のスレッドそれぞれがもはや前記共用ポインタを使用しなくなるまで待機した後に、前記データ構造を割振り解除することを含む方法。
【請求項３】
各スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラム・コードを実行中であるかどうかを判別することは、前記複数のスレッドのうちの第１のスレッドが非活動状態であるかどうかを判別することを含む、請求項２に記載の方法。
【請求項４】
各スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラム・コードを実行中であるかどうかを判別することは、前記複数のスレッドのうちの第１のスレッドがアイドル・ループを実行中であるかどうかを判別することを含む、請求項２に記載の方法。
【請求項５】
前記アイドル・ループは区画マネージャのアイドル・ループである、請求項４に記載の方法。
【請求項６】
スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラム・コードを実行中であるかどうかを判別することは、前記複数のスレッドのうちの第１のスレッドに関連付けられたインジケータが、前記第１のスレッドが現在他のプログラム・コードを実行中であることを示すかどうかを判別することを含む、請求項２に記載の方法。
【請求項７】
スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラム・コードを実行中であるかどうかを判別することは、前記複数のスレッドのうちの第１のスレッドに関連付けられたインジケータが、前記第１のスレッドが前記プログラム・コードを励起したことを示すかどうかを判別することをさらに含む、請求項２に記載の方法。
【請求項８】
スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラム・コードを実行中であるかどうかを判別することは、前記複数のスレッドのうちの第１のスレッドに関連付けられたインジケータが、前記第１のスレッドが現在前記プログラム・コードを実行中であること、または前記第１のスレッドが前記プログラム・コードを励起したことを示すかどうかを判別することを含み、前記インジケータは、前記第１のスレッドが前記プログラム・コードを入力すると必ず第１の値から第２の値に更新される、および前記第１のスレッドが前記プログラム・コードを終了すると必ず第２の値から第３の値に更新されるシーケンス番号を含み、さらに前記第１のスレッドに関連付けられた前記インジケータが前記第１のスレッドが前記プログラム・コードを励起したことを示すかどうかを判別することは、前記インジケータをその以前の値と比較することを含む、請求項２に記載の方法。
【請求項９】
第１のスレッドが前記プログラム・コードを入力すると必ず、複数スレッドのうちの第１のスレッドに関連付けられたシーケンス番号を、第１の値セットから選択された第１の値から、第２の値セットから選択された第２の値に増分すること、および
前記第１のスレッドが前記プログラム・コードを終了すると必ず、前記シーケンス番号を、前記第１の値セットから選択された第２の値から第３の値に増分することをさらに含む方法であって、
前記複数のスレッドそれぞれがもはや前記共用ポインタを使用しなくなるまで待機することは、各スレッドを監視する前に前記シーケンス番号の値を獲得することを含み、さらに各スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラム・コードを実行中であるかどうかを判別することは、前記第１のスレッドに関連付けられた前記シーケンス番号が前記第２の値セットから選択された値を有するかどうかを判別すること、および前記シーケンス番号が前記獲得された値とは異なる値を有するかどうかを判別することを含む、請求項２に記載の方法。
【請求項１０】
前記第１の値セットは奇数からなり、前記第２の値セットは偶数からなる、請求項９に記載の方法。
【請求項１１】
前記コンピュータは論理的に区分されたコンピュータであり、前記プログラム・コードは前記コンピュータ内の複数の論理区画にアクセス可能な区画マネージャを含む、請求項２に記載の方法。
【請求項１２】
前記プログラム・コードは前記区画マネージャのディスパッチ不能部分を含む、請求項１１に記載の方法。
【請求項１３】
前記データ構造は前記区画マネージャによって使用される区画制御ブロックを含む、請求項１１に記載の方法。
【請求項１４】
前記共用ポインタを所定の値に設定することは前記共用ポインタをｎｕｌｌ値に設定することを含む、請求項２に記載の方法。
【請求項１５】
前記複数のスレッドは単一スレッド・プロセッサ上で実行する第１のスレッドを含む、請求項２に記載の方法。
【請求項１６】
前記複数のスレッドはマルチスレッド・プロセッサ上で実行する第１および第２のスレッドを含む、請求項２に記載の方法。
【請求項１７】
データ構造が常駐するメモリと、
複数のスレッドを実行するように構成された少なくとも１つのプロセッサと、
前記データ構造を割振り解除する要求に応答して、前記データ構造を指す共用ポインタを、その後前記ポインタにアクセスするスレッドに対して前記データ構造が使用可能でないことを示す所定の値に設定すること、前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラムを各スレッドが実行中であるかどうかを判別するために各スレッドを監視することによって前記複数のスレッドがもはや前記共用ポインタを使用しなくなるまで待機すること、および、前記複数のスレッドそれぞれがもはや前記共用ポインタを使用しなくなるまで待機した後に前記データ構造を割振り解除することにより、前記データ構造を割振り解除するために前記少なくとも１つのプロセッサによって実行されるように構成されたプログラムとを含む装置。
【請求項１８】
前記プログラムは、前記複数のスレッドのうちの第１のスレッドが非活動状態であるかどうかを判別することによって、各スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラム手段を実行中であるかどうかを判別するように構成される、請求項１７に記載の装置。
【請求項１９】
前記プログラムは、前記複数のスレッドのうちの第１のスレッドがアイドル・ループを実行中であるかどうかを判別することによって、各スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラムを実行中であるかどうかを判別するように構成される、請求項１７に記載の装置。
【請求項２０】
前記アイドル・ループは区画マネージャのアイドル・ループである、請求項１９に記載の装置。
【請求項２１】
前記プログラムは、前記複数のスレッドのうちの第１のスレッドに関連付けられたインジケータが、前記第１のスレッドが現在他のプログラムを実行中であることを示すかどうかを判別することによって、スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラムを実行中であるかどうかを判別するように構成される、請求項１７に記載の装置。
【請求項２２】
前記プログラムは、前記複数のスレッドのうちの第１のスレッドに関連付けられたインジケータが、前記第１のスレッドが前記プログラムを励起したことを示すかどうかをさらに判別することによって、スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラムを実行中であるかどうかを判別するように構成される、請求項１７に記載の装置。
【請求項２３】
前記プログラムは、前記複数のスレッドのうちの第１のスレッドに関連付けられたインジケータが、前記第１のスレッドが現在前記プログラムを実行中であること、または前記第１のスレッドが前記プログラムを励起したことを示すかどうかを判別することによって、スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラムを実行中であるかどうかを判別するように構成され、前記インジケータは、前記第１のスレッドが前記プログラムを入力すると必ず第１の値から第２の値に更新される、および前記第１のスレッドが前記プログラムを終了すると必ず第２の値から第３の値に更新されるシーケンス番号を含み、さらに前記プログラムは、前記インジケータをその以前の値と比較することによって、前記第１のスレッドに関連付けられた前記インジケータが前記第１のスレッドが前記プログラムを励起したことを示すかどうかを判別するように構成される、請求項１７に記載の装置。
【請求項２４】
さらに前記プログラムは、第１のスレッドが前記プログラムを入力すると必ず、複数スレッドのうちの第１のスレッドに関連付けられたシーケンス番号を、第１の値セットから選択された第１の値から、第２の値セットから選択された第２の値に増分し、および前記第１のスレッドが前記プログラムを終了すると必ず、前記シーケンス番号を、前記第１の値セットから選択された第２の値から第３の値に増分するように構成されるものであって、前記プログラムは、各スレッドを監視する前に前記シーケンス番号の値を獲得することによって、前記複数のスレッドそれぞれがもはや前記共用ポインタを使用しなくなるまで待機するように構成され、前記プログラムは、前記第１のスレッドに関連付けられた前記シーケンス番号が前記第２の値セットから選択された値を有するかどうか、および前記シーケンス番号が前記獲得された値とは異なる値を有するかどうかを判別することによって、各スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラムを実行中であるかどうかを判別するように構成される、請求項１７に記載の装置。
【請求項２５】
前記第１の値セットは奇数からなり、前記第２の値セットは偶数からなる、請求項２４に記載の装置。
【請求項２６】
前記装置は論理的に区分されたコンピュータとして構成され、前記プログラムは前記少なくとも１つのプロセッサ上で実行中の複数の論理区画にアクセス可能な区画マネージャを含む、請求項１７に記載の装置。
【請求項２７】
前記プログラムは前記区画マネージャのディスパッチ不能部分を含む、請求項２６に記載の装置。
【請求項２８】
前記データ構造は前記区画マネージャによって使用される区画制御ブロックを含む、請求項２６に記載の装置。
【請求項２９】
前記プログラムは、前記共用ポインタをｎｕｌｌ値に設定することによって、前記共用ポインタを所定の値に設定するように構成される、請求項１７に記載の装置。
【請求項３０】
前記少なくとも１つのプロセッサは単一スレッド・プロセッサを含む、請求項１７に記載の装置。
【請求項３１】
前記少なくとも１つのプロセッサはマルチスレッド・プロセッサを含む、請求項１７に記載の装置。
【請求項３２】
前記データ構造を割振り解除する要求に応答して、前記データ構造を指す共用ポインタを、その後前記ポインタにアクセスするスレッドに対して前記データ構造が使用可能でないことを示す所定の値に設定すること、前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラム・コードを各スレッドが実行中であるかどうかを判別するために各スレッドを監視することによって前記複数のスレッドがもはや前記共用ポインタを使用しなくなるまで待機すること、および、前記複数のスレッドそれぞれがもはや前記共用ポインタを使用しなくなるまで待機した後に前記データ構造を割振り解除することにより、コンピュータ内で複数のスレッドを実行することによってアクセス可能なデータ構造を割振り解除するように構成されたプログラム・コードを含む、コンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータおよびコンピュータ・ソフトウェアに関し、具体的に言えば、たとえば論理的に区分されたコンピュータの区画を削除することに関連した、マルチスレッド・コンピュータにおける共用コンピュータ・データの割振り解除に関する。
【背景技術】
【０００２】
現代社会においてコンピュータへの依存度がますます高くなることを考えると、コンピュータ技術は需要の増加に遅れることなく多くの局面で進歩していかなければならない。重要な研究開発活動の特定課題の１つが並行処理、すなわち複数タスクの並行した実行である。
【０００３】
多くの並行処理を容易にするために、いくつかのコンピュータ・ソフトウェアおよびハードウェア技術がこれまでに開発されてきた。ソフトウェアの見地から、マルチスレッド化されたオペレーティング・システムおよびカーネルが開発されており、これはコンピュータ・プログラムを複数の「スレッド」内で同時に実行できるようにするものであり、その結果、基本的に複数のタスクを同時に実行することができる。スレッドとは一般に、プログラムの独立した実行経路を表すものである。たとえば、電子商取引のコンピュータ・アプリケーションの場合、様々な顧客に様々なスレッドを割り当てることができるため、別々のスレッドでそれぞれの顧客に特有の電子商取引トランザクションが処理される。
【０００４】
ハードウェアの見地からすると、コンピュータは作業負荷容量を上げるために複数のマイクロプロセッサへの依存がますます高まってきている。さらに、複数のスレッドを並行して実行する機能をサポートする何らかのマイクロプロセッサも開発され、複数のマイクロプロセッサを使用することで達成可能なものと同じ性能利得の多くを効果的に提供している。
【０００５】
ソフトウェアの見地からすると、コンピュータの中には論理区分の概念を実施するものもあり、ここでは単一の物理コンピュータが、本質的に同じ複数の独立した「仮想」コンピュータ（論理区画と呼ばれる）を動作させることが可能であり、物理コンピュータ内の様々なリソース（プロセッサ、メモリ、入力／出力デバイス）は様々な論理区画間で割り振られている。各論理区画は別々のオペレーティング・システムを実行し、ユーザおよび論理区画上で実行中のソフトウェアアプリケーションの観点からすれば、完全に独立したコンピュータとして動作する。
【０００６】
論理区分を使用すると、「ハイパーバイザ」または区画マネージャと呼ばれることの多い共用リソースが論理区画を管理し、様々な論理区画へのリソースの割振りが容易になる。たとえば区画マネージャは、プロセッサ、ワークステーション・アダプタ、記憶デバイス、メモリ・スペース、ネットワーク・アダプタなどのリソースを、様々な区画に割り振ることで、各論理区画の相対的に独立したオペレーションを別の物理コンピュータとほぼ同じ方法でサポートすることができる。
【０００７】
論理区画の管理に関連して、コンピュータ全体をシャットダウンおよび再起動する必要なしに個々の区画が作成および削除され、したがってコンピュータ内の他の区画が引き続き使用可能であると保証されることが望ましい。新しい区画の作成は、衝突の危険なしに新しい区画をサポートするために新しいデータ構造を作成することができるため、通常は特に問題ではない。他方で区画の削除は、区画の既存のデータ構造がコンピュータから割振り解除または除去されたときに、もはや使用されないことを保証する必要があるため、より問題となることが多い。
【０００８】
具体的に言えば、マルチスレッドのコンピュータ環境で複数のスレッドがアクセスできる任意のデータ構造を削除するには、そのデータ構造を依然として使用しているスレッドがないことを確認した後に削除するように注意する必要がある。そうしなければ、データ構造が削除された後にスレッドがアクセスしようと試みる場合があり、その結果、不確定な結果および潜在的なシステム障害が発生することになる。
【０００９】
従来から、多くの共用データ構造へのアクセスは、セマフォまたはスピン・ロックを使用して管理される。セマフォは通常、データ構造を指す共用ポインタに関連付けられ、スレッドのうちの１つが現在そのポインタを使用しているかどうかを判別するために複数のスレッドによって読み取られる、変数またはトークンとして実施される。現在そのポインタを使用しているスレッドが他にないことを示すセマフォをあるスレッドが読み取ると必ず、そのスレッドはそのセマフォを、そのポインタが現在使用中であることを他のすべてのスレッドに示す値に設定することができる（セマフォ「獲得」と呼ばれるプロセス）。したがって、別のスレッドがそのデータ構造にアクセスしようとしたときに、セマフォが他のスレッドによって保持されていることを検出した場合、そのスレッドは、他方のスレッドがセマフォを解放し、その他のスレッドがポインタ（およびデータ構造）に再度アクセスできるようになったことを示すまで待機する必要がある。したがって、任意の所与の時間に１つのセマフォを保持できるスレッドは１つだけである。
【００１０】
セマフォまたはスピン・ロックの主要な欠点は、関連付けられたデータ構造にアクセスする必要がある場合には必ず、セマフォのチェックおよび獲得に関連するかなりの処理オーバヘッドがあることである。たとえば、論理的に区分されたコンピュータの場合、通常のオペレーション中に頻繁にアクセスされるデータ構造がいくつかある。たとえば、重要な区画構成情報を格納するために使用される区画制御ブロックは、典型的には実際のあらゆる区画管理オペレーション中にアクセスされる。区画制御ブロックにアクセスする必要があるたびにスレッドにセマフォを獲得するように要求することは、性能の点から見て法外な費用がかかることがわかってきた。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
したがって、マルチスレッド・コンピュータにおいて、処理オーバヘッドを削減しながらデータ構造の割振り解除をサポートする方法が、強く求められている。
【課題を解決するための手段】
【００１２】
本発明では、計算上高価なセマフォまたはスピン・ロックを使用する必要なしに、マルチスレッド・コンピュータにおけるデータ構造の割振り解除をサポートする装置、プログラム記録媒体、および方法を提供することによって、従来技術に関連付けられたこれらおよび他の問題に対処する。具体的に言えば、データ構造へのアクセスは共用ポインタによって管理され、この共用ポインタは初めに、データ構造を割振り解除するための要求を受け取ると、後でポインタにアクセスする任意のスレッドに対してデータ構造が使用できないことを示す値に設定される。そのように実行することによって、データ構造の割振りを解除する要求を開始した時点でデータ構造へのアクセス権を持たないスレッドは、その後データ構造へのアクセスを取得できないことが保証される。
【００１３】
さらに、共用ポインタのコピーをすでに保持しており、したがって、要求開始後、共用ポインタを介してデータ構造にアクセスすることのできる任意のスレッドに対処するために、こうしたスレッドはすべてが監視され、いずれかのスレッドがデータ構造にアクセスするために共用ポインタを使用することのできるプログラム・コードを実行中であるかどうかを判別することによって、いずれかのスレッドが依然として共用ポインタを使用しているかどうかが判別される。そうでない場合、プロセスは、依然として共用ポインタを使用しているスレッドがないと判定されるまで待機する。この条件に合致すると、共用ポインタを介してデータ構造に潜在的にアクセスできるスレッドはないことが保証され、したがってデータ構造を割振り解除することができる。
【００１４】
関連付けられた共用ポインタが一意の値を指すように設定することにより、データ構造が割振り解除保留中であるという信号を発信することで、データ構造へのアクセスを試行する前に共用ポインタを試験することに関連付けられたオーバヘッドは、セマフォの取得に必要なオーバヘッドより著しく少なくなる。したがって、データ構造へのアクセスは大幅に速くなる。さらに、スレッドを監視して、スレッドがデータ構造にアクセスするために共用ポインタを使用することのできるプログラム・コードを実行中であるかどうかを判別することによって、スレッドが実際に依然として共用ポインタを使用しているかどうかを判別する必要がなくなる。
【００１５】
前述のプロセスの特定の実施の１つは、具体的には削除される区画に関連付けられた区画制御ブロックを割振り解除するために、論理的に区分されたコンピュータ内の区画を削除することに関連している。区画制御ブロックの割振り解除を容易にするために、区画制御ブロックへのアクセスを禁止し、区画制御ブロックがもはやどんなスレッドにもアクセスできないことを示すように、区画制御ブロックを指す共用ポインタをｎｕｌｌ値に設定することができる。したがって、どんなスレッドが後で区画制御ブロックにアクセスしようとしても、そのように実行することはできなくなる。
【００１６】
さらにこうした実施では、共用ポインタにアクセスできるのは区画マネージャを介した場合のみであり、どんな区画によってもアクセスできないことが知られている。したがって、依然として共用ポインタを使用している（すなわち、ｎｕｌｌ値に設定される前に共用ポインタのコピーを取得していた）任意のスレッドに対処するために、この実施では、共用ポインタを依然として使用しているスレッドがないことが判別できるまで待機する。
【００１７】
この実施では、スレッドが共用ポインタを使用していないと判別することが可能であるのは、スレッドが非活動状態である、スレッドがアイドル・ループにある、スレッドが区画マネージャに関するプログラム・コードを実行していない、または共用ポインタがｎｕｌｌ値に設定されていないためにスレッドが区画マネージャに関するプログラム・コードを励起した、と判別されたときである。こうした条件のいずれかが存在する場合、スレッドがその後データ構造にアクセスしようとすると必ず、共用ポインタのｎｕｌｌ値が取り出される結果となり、したがって、スレッドが後にどのプログラム・コードを実行するかに関わらず、プログラム・コードは共用ポインタを使用してデータ構造にアクセスすることはできなくなることが知られている。したがって、その点で、活動状態のどんなスレッドにも悪影響を与えることなく、区画制御ブロックを削除することができる。
【００１８】
論理的に区分されたコンピュータに関連した本発明の実施は単なる例示的な性質のものであり、したがって本発明は、以下で述べる特定の実施に限定されるものでないことを理解されよう。
【００１９】
本発明を特徴付けるこれらおよび他の利点および機能については、本明細書に添付され、本明細書の他の部分を形成する、特許請求の範囲に記載される。ただし、本発明ならびに本発明の使用によって達成される利点および目的をよりよく理解するために、本発明の例示的な実施形態が記載された図面および添付の記述を参照されたい。
【発明を実施するための最良の形態】
【００２０】
以下で論じる実施形態は、計算上高価なセマフォまたはスピン・ロックが、割振り解除された後にデータ構造にアクセスしようとするスレッドがないことを保証する必要のない方法で、マルチスレッド・コンピュータにおけるデータ構造の順序立てた割振り解除を容易にするものである。
【００２１】
具体的に言えば、データ構造へのアクセスは、データ構造を割振り解除する要求が受け取られたときに、後でポインタにアクセスするどんなスレッドに対してもデータ構造が使用できないことを示す値に初めに設定される、共用ポインタによって管理される。他の一意の値を使用してデータ構造が使用不能であることを示すこともできるが、好適な値の１つはｎｕｌｌ値である。したがって、ポインタがｎｕｌｌ値に設定された後に、スレッドがデータ構造にアクセスするためにそのポインタを取得しようとすると必ず、そのスレッドはデータ構造へのアクセスから除外される。さらにこのスレッドは、たとえデータ構造がメモリから割振り解除された後であっても、データ構造へのアクセスを試行できなくなることは確実であろう。
【００２２】
データ構造の割振り解除は、データ構造が割振り解除された後にデータ構造にアクセスしようとするスレッドがないことを保証できる場合にのみ、実行可能である。本発明に適合して、こうした保証は、データ構造にアクセスするために共用ポインタを使用することが可能なプログラム・コードをいずれかのスレッドが実行中であるかどうかを判別することによって、いずれかのスレッドが依然として共用ポインタを使用中であるかどうかを判別するために、システム内のすべてのスレッドを監視することによって得られる。データ構造にアクセスするために共用ポインタを使用することが可能なプログラム・コードは、たとえ共用ポインタが、データ構造が使用可能でないことを示すｎｕｌｌ値などの一意の値に設定された後でも、依然としてデータ構造を参照する共用ポインタの以前のコピーを保持している可能性のあるプログラム・コードであるとみなすことができる。スレッドがこうしたプログラム・コードを実行している限り、共用ポインタの以前のコピーを使用してデータ構造にアクセスする試みが実行される危険性が存在し、その結果、不確定な結果ならびに潜在的なデータ破損および／またはシステム障害が生じることになる。
【００２３】
以下で論じる特定の実施形態では、たとえば、割振り解除されるデータ構造は、論理的に区分されたコンピュータ内で区画マネージャのみがアクセス可能な区画制御ブロックであり、具体的に言えば、そのうちのディスパッチ不能な部分である。これらの実施形態では、スレッドが区画マネージャに関するプログラム・コードを入力すると必ず、スレッドは、スレッドがアクセスを希望する任意の区画制御ブロックについて共用ポインタの新しいコピーを取得する必要があると想定される。したがって、関連付けられたデータ構造を割振り解除する試みに関連して、特定の共用ポインタがｎｕｌｌ値（または他の適切な一意の値）に設定された後に、スレッドが区画マネージャのプログラム・コードを入力すると必ず、こうしたスレッドはデータ構造を指す有効なポインタを取得しないことが想定できる。したがって当該のスレッドは、関連付けられたデータ構造を割振り解除する要求に関連して共用ポインタが設定された時点で、区画マネージャのプログラム・コード内で実行されており、共用ポインタの（今や古くなった）コピーが依然として存在する可能性があるため、こうしたプログラム・コードをまだ終了していない任意のスレッドである。
【００２４】
様々な組合せで調べることが可能ないくつかの要素を使用して、データ構造にアクセスするために共用ポインタを使用することができるプログラム・コードをスレッドが実行していないという保証を提供することができる。たとえば、１つの要素は、スレッドが休眠状態であるかどうかであり、これは、共用ポインタが一意の値に設定されている時点での休眠スレッド（どんな命令も実行していないスレッド）は、共用ポインタの古くなったコピーを保持することができないためである。他の要素は、スレッドがアイドル・ループ（たとえば区分マネージャ内のアイドル・ループ）を実行中であるかどうかであり、これは、こうしたスレッドも同様に共用ポインタの古くなったコピーを保持することができないためである。
【００２５】
さらに他の要素は、共用ポインタが一意の値に設定されたときに共用ポインタを使用することができるプログラム・コード以外のプログラム・コードを現在実行中であるスレッドが検出されるかどうかであり、このような場合には、共用ポインタを使用することができるプログラム・コードが後で実行されるときに、スレッドがその後共用ポインタの新しいコピーを取得しなければならなくなることが知られている。
【００２６】
さらに他の要素は、共用ポインタが一意の値に設定されたときに共用ポインタを使用することができるプログラム・コードを励起したスレッドが検出されるかどうかである。このような場合には、プログラム・コードを励起した後、共用ポインタを使用することができるプログラム・コードが後で実行されるときに、スレッドが共用ポインタの新しいコピーを取得しなければならなくなることが知られている。
【００２７】
下記でより明らかになるように、データ構造にアクセスするために共用ポインタを使用することができるプログラム・コード以外のプログラム・コードをスレッドが現在実行中であるかどうか、ならびに、共用ポインタを使用することができるプログラム・コードをスレッドが励起したかどうかの両方を試験する際に使用可能な一メカニズムは、そのスレッドがプログラム・コードの特定セクションを入力および終了するときに必ず修正される、各スレッドに関連付けられたインジケータを使用することである。多種多彩な代替実施が使用可能であるが、１つの好適なインジケータは、スレッドが共用ポインタにアクセスすることができるプログラム・コードを入力すると必ず、ならびにスレッドが同じプログラム・コードを終了すると必ず、１つずつ増分されるシーケンス番号である。こうしたシーケンス番号を使用すると、共用ポインタを使用することができるプログラム・コード以外のプログラム・コードをスレッドが実行中であると必ず、偶数および奇数の値のうちの１つを使用して指定することができる。さらに、共用ポインタを一意の値に設定することに関連してシーケンス番号の値を獲得すること、およびその後シーケンス番号の現在の値を監視することにより、シーケンス番号の値における任意の差を使用して、スレッドが当該プログラム・コードを励起したこと、およびしたがってデータ構造にアクセスするために共用ポインタを使用できることを示すことができる。
【００２８】
データ構造にアクセスするために共用ポインタを使用することができるプログラム・コードをスレッドが実行中であるかどうかを判定することに関連して、他の要素および要素の組合せを考慮することができることを理解されよう。さらに、論理的に区分されたコンピュータ以外のコンピュータに関連して、本発明に適合した実施形態を使用することができる。したがって、本発明は本明細書で論じる特定の実施に限定されるものではない。
【００２９】
次に図面を見ると、同じ番号はいくつかの図にわたって同じ部分を表すものであり、図１は、本発明に適合する論理的に区分されたコンピュータ１０における主要なハードウェア構成要素を示す図である。コンピュータ１０は、たとえばネットワーク・サーバ、中級機コンピュータ、メインフレーム・コンピュータなどのいくつかのマルチユーザ・コンピュータのうちのいずれか、たとえばＩＢＭのｅＳｅｒｖｅｒ中級機コンピュータを、総称的に表すものである。ただし本発明は、他のコンピュータおよびデータ処理システム、たとえばワークステーション、デスクトップ・コンピュータ、ポータブル・コンピュータなどの単一ユーザ・コンピュータで、または（埋込み型コントローラなどを組み込んだ）他のプログラム可能電子デバイスで、実施することができることを理解されたい。さらに本発明は、論理的に区分されていないマルチスレッド・コンピュータに関連して使用することもできる。
【００３０】
コンピュータは一般に、バス１６を介してメモリ１４に結合された１つまたは複数のプロセッサ１２を含む。各プロセッサ１２は、単一スレッド・プロセッサとして、または複数のハードウェア・スレッドを組み込むように示されたプロセッサ１２ａなどのマルチスレッド・プロセッサとして実施することができる。たいていの場合、マルチスレッド・プロセッサ１２ａ内の各ハードウェア・スレッド１８は、コンピュータ内に常駐するソフトウェアによって独立したプロセッサのように扱われる。この点に関して本開示では、単一スレッド・プロセッサが単一ハードウェア・スレッド、すなわち単一の独立した実行ユニットを組み込むように考慮されることになる。ただし、ソフトウェアベースのマルチスレッド化およびマルチタスク化は、コンピュータ内での複数タスクの並列パフォーマンスをさらにサポートするために、単一スレッドおよびマルチスレッドの両方のプロセッサに関連して使用することが可能であることを理解されよう。
【００３１】
さらに、図１にも示されるように、１つまたは複数のプロセッサ１２（たとえばプロセッサ１２ｂ）を、システム初期プログラム・ロード（ＩＰＬ）の管理、ならびにシステム・ハードウェアの監視、診断、および構成のために、特殊なファームウェア・コードを実行する際に使用されるサービス・プロセッサとして実施することができる。一般にコンピュータ１０は、コンピュータ内に常駐するオペレーティング・システムおよびアプリケーションを実行するために使用される、１つのサービス・プロセッサおよび複数のシステム・プロセッサを含むことになるが、本発明はこの特定の実施に限定されるものではない。いくつかの実施では、サービス・プロセッサは、バス１６を介する以外の方法でコンピュータ内の様々な他のハードウェア構成要素に結合することができる。
【００３２】
メモリ１４は、１つまたは複数レベルのメモリ・デバイス、たとえばＤＲＡＭベースの主記憶装置、ならびに、当分野で周知の個々のプロセッサまたは複数のプロセッサのいずれかを処理する一定のキャッシュを備えた、１つまたは複数レベルのデータ、命令、および／または、組合せキャッシュを含むことができる。さらにメモリ１４は、バス２０を介していくつかのタイプの外部デバイス、たとえば（コンピュータとネットワーク２４をインターフェースさせるための）１つまたは複数のネットワーク・アダプタ２２、（コンピュータと１つまたは複数の記憶デバイス２８とをインターフェースさせるための）１つまたは複数の記憶域コントローラ２６、および（複数のワークステーション・アダプタを介して１つまたは複数の端末またはワークステーション３２とインターフェースさせるための）１つまたは複数のワークステーション・コントローラ３０に結合される。
【００３３】
図１は、区画マネージャまたはハイパーバイザ３６によって管理される複数の論理区画３４を含む、コンピュータ１０上で論理的に区分されたコンピューティング環境を実施する際に使用される主ソフトウェア構成要素およびリソースもさらに詳細に示している。当分野で周知のように、任意数の論理区画がサポート可能であり、コンピュータ内にいつでも常駐する論理区画の数は、コンピュータへのまたはコンピュータからの区画の追加または除去に応じて動的に変更することができる。
【００３４】
例示されたＩＢＭ  ｅＳｅｒｖｅｒベースの実施では、区画マネージャ３６は２層のプログラム・コードからなる。本明細書ではディスパッチ不能部分３８と呼ばれる第１の層は、ファームウェアまたはコンピュータ１０のライセンス内部コード（ＬＩＣ）内で実施され、これが高位層、たとえばオペレーティング・システムをハードウェア・アクセスの細部から分離させる一方で、様々なハードウェア構成要素への低レベル・インターフェースを提供するために使用される。ファームウェアは、サービス・プロセッサ１２ｂなどのサービス・プロセッサとも通信することができる。ディスパッチ不能部分３８は、コンピュータ１０に対して、たとえばページ・テーブル管理などの多くの低レベル区画管理機能を提供する。ディスパッチ不能部分３８はタスクの概念も持たず、主に高位層のソフトウェアからの機能呼出しを介してアクセスすることができる。
【００３５】
区画マネージャ３６内のプログラム・コードの第２の層は、本明細書ではディスパッチ可能部分４０と呼ばれる。タスクの概念を持たず、再配置オフの状態で実行され、および高位層のソフトウェアからの機能呼出しを介してアクセス可能な、ディスパッチ不能部分３８とは対照的に、ディスパッチ可能部分４０は（任意のオペレーティング・システムと同様に）タスクの概念を持ち、再配置オンの状態で実行される。ディスパッチ可能部分は、ユーザに見えないという点を除き、典型的には区画とほぼ同じ方法で実行される。ディスパッチ可能部分は、一般に、区画の作成および削除、同時Ｉ／Ｏ保守、様々な区画３４へのプロセッサ、メモリ、および他のハードウェア・リソースの割振りなどの、高位レベル区画管理オペレーションを管理する。
【００３６】
各論理区画３４には、典型的にはコンピュータ１０内の使用可能なリソースの一部が統計的および／または動的に割り振りされる。たとえば、各論理区画には１つまたは複数のプロセッサ１２および／または１つまたは複数のハードウェア・スレッド１８、ならびに使用可能なメモリ・スペースの一部を割り振ることができる。論理区画は、プロセッサなどの特定のハードウェア・リソースを共用することが可能であり、その結果、所与のプロセッサが複数の論理区画によって使用される。これに代わる方法では、ハードウェア・リソースを一度に１つの論理区画のみに割り振ることができる。
【００３７】
追加のリソース、たとえば大容量記憶装置、バックアップ記憶装置、ユーザ入力、ネットワーク接続、およびそのためのＩ／Ｏアダプタは、典型的には当分野で周知の方法で１つまたは複数の論理区画に割り振られる。リソースは、複数の論理区画が同じバス上でリソースを共用しながら、いくつかの方法で、たとえばバスごとに、またはリソースごとに、割り振ることができる。リソースによっては、一度に複数の論理区画に割り振ることさえも可能である。
【００３８】
各論理区画３４は、区分されていないコンピュータのオペレーティング・システムと同じ方法で論理区画の主オペレーションを制御するオペレーティング・システム４２を使用する。たとえば、各オペレーティング・システム４２は、Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｂｕｓｉｎｅｓｓ  Ｍａｃｈｉｎｅｓ  Ｃｏｒｐｏｒａｔｉｏｎから入手可能なＯＳ／４００オペレーティング・システムを使用して実施可能である。
【００３９】
各論理区画３４は、別々の、または独立したメモリ・スペース内で実行されるため、各論理区画は、こうした各論理区画内で実行される各ユーザ・アプリケーション（ｕｓｅｒ  ａｐｐ）４４の観点からすれば、独立した区分されていないコンピュータとほぼ同じように動作する。したがって、通常ユーザ・アプリケーションは、区分された環境で使用するためのどんな特別な構成も必要としない。
【００４０】
論理区画３４の性質を別々の仮想コンピュータであるとすれば、あたかも論理区画が別々の物理マシン上にあるかのように、論理区画が相互に通信できるようにするための区画間通信をサポートすることが望ましい。したがって、一部の実施では、イーサネット（登録商標）・プロトコルなどのネットワーキング・プロトコルを介して論理区画３４が相互に通信できるようにするために、ディスパッチ不能部分３８内で仮想ローカル・エリア・ネットワーク（ＬＡＮ）４６をサポートすることが望ましい。本発明に適合して、区画間での通信をサポートする他の方法もサポートすることができる。
【００４１】
本発明に適合した他の論理的に区分された環境が使用可能であることを理解されよう。たとえば、任意の区画３４から分離したディスパッチ可能部分４０を使用するのではなく、代替の方法として、ディスパッチ可能部分の機能を１つまたは複数の論理区画に組み込むことができる。
【００４２】
一般に、本発明の実施形態を実施するために実行されるルーチンは、オペレーティング・システムの一部または特定のアプリケーション、構成要素、プログラム、オブジェクト、モジュール、または命令のシーケンス、あるいはたとえそのサブセットとして実施される場合であっても、本明細書では「コンピュータ・プログラム・コード」または単に「プログラム・コード」と呼ぶ。プログラム・コードは、通常、様々なときに、コンピュータ内の様々なメモリおよび記憶デバイス内に常駐し、コンピュータ内の１つまたは複数のプロセッサによって読み取られて実行されると、本発明の様々な態様を実施するステップまたは要素を実行するのに必要なステップをそのコンピュータに実行させる、１つまたは複数の命令を含む。さらに、本発明については、完全に機能しているコンピュータおよびコンピュータ・システムのコンテキストでこれまで述べてきており、さらに以下でも述べるが、当分野の技術者であれば、本発明の様々な実施形態が様々な形のプログラム記録媒体として配布可能であり、本発明は、実際に配布を実行するために使用される特定タイプの信号搬送媒体に関係なく、等しく適用されることを理解されよう。信号搬送媒体の例には、揮発性および不揮発性のメモリ・デバイス、フロッピィおよび他の取外し可能ディスク、ハード・ディスク・ドライブ、磁気テープ、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）などの記録可能タイプの媒体、ならびにデジタルおよびアナログの通信リンクなどの伝送タイプの媒体が含まれるが、これらに限定されるものではない。
【００４３】
さらに、以下で述べる様々なプログラム・コードは、プログラム・コードが本発明の特定の実施形態で実施されるアプリケーションまたはソフトウェア構成要素に基づいて識別することができる。ただし、それが従ういずれの特定プログラムの命名法も、単に便宜上使用されるものであり、本発明は、こうした命名法によって識別および／または示唆される任意の特定アプリケーションにおいてのみ使用されるように限定されるものでないことを理解されたい。さらに、コンピュータ・プログラムがルーチン、手順、方法、モジュール、オブジェクトなどに編成可能な典型的に無数の方法、ならびに、プログラム機能を典型的なコンピュータ内に常駐する様々なソフトウェア層（たとえば、オペレーティング・システム、ライブラリ、ＡＰＩ、アプリケーション、アプレットなど）の間で割り振ることが可能な様々な方法を考えると、本発明は、本明細書に記載されたプログラム機能の特定の編成および割振りに限定されるものでないことを理解されたい。
【００４４】
当分野の技術者であれば、図１に示された例示的環境が本発明を制限することを意図するものでないことを理解されよう。実際に、当分野の技術者であれば、本発明の範囲を逸脱することなく他の代替のハードウェアおよび／またはソフトウェア環境が使用可能であることを理解されよう。
【００４５】
前述のように、本明細書に記載された実施形態では、データ構造の割振り解除は、論理的に区分されたコンピュータ内での区画の削除に関連して実行される。初期プログラム・ローディング（ＩＰＬ）またはコンピュータのリブートの必要なしに、論理的に区分されたコンピュータ内で区画を動的に作成および削除するための機能をサポートすることが望ましい。こうしたオペレーションに関連して、区画制御ブロックとして知られるデータ構造は、アクティブな区画について、関連付けられた区画に必要な構成を格納するために維持される。論理区画の作成は、部分的に、関連付けられた区画制御ブロックの作成を伴う。同様に論理区画の削除は、部分的に、関連付けられた区画制御ブロックの割振り解除を伴う。
【００４６】
実際には、区画マネージャ内で、および具体的に言えば、通常システム・ファームウェアに常駐するそのディスパッチ不能部分内で実行される、あらゆるオペレーションは、区画制御ブロックへのアクセスを必要とする。こうしたアクセスは、典型的には区画制御ブロックを指す共用ポインタを使用して実行されるものであり、ポインタは、ポインタのコピーがシステム内の複数のスレッドによって取得可能であるという観点から共用される。通常、区画制御ブロックへのアクセスを希望するスレッドは、第１に、それを指すポインタのコピーを取得しなければならず、いったんコピーを取得すると、ポインタの同じコピーを使用してさらにアクセスすることができる。
【００４７】
たとえば、図２に示されるように、区画マネージャ３６（図１）用のメモリ・スペース５０は、共用ポインタ５４のセットのうちの１つがそれぞれを指す区画制御ブロック５２のセットを含むことができる。
【００４８】
区画制御ブロックは、実際に区画マネージャ内で実行されるあらゆるオペレーションに関連してアクセスされるため、スレッドが区画マネージャ内でプログラム・コードを実行するといつでも、関連付けられた区画制御ブロックがスレッドによってアクセスされる確率、およびスレッドがこうしたブロックを指す共用ポインタのコピーを取得する確率が高くなる。こうしたオペレーションが頻繁であるとすれば、セマフォまたはスピン・ロックなどの共用リソースへのアクセスを同期化するための従来のメカニズムは計算上かなり高価であり、これにより、システム性能が大幅に低下する可能性がある。
【００４９】
この問題に対処するために、以下で述べる実施形態では、区画削除オペレーションが本来非同期であり、したがって高レベルの同期化プロトコルに好適である、という事実を利用する。さらに、区画マネージャでプログラム・コードを実行しているスレッドは通常優先使用可能でないため、以下で述べる実施形態では、この事実も同様に利用することができる。
【００５０】
具体的に言えば、以下で述べる実施形態では、始めに、区画制御ブロックを指す共用ポインタを、ブロックがもはや使用可能でないことを示す一意の値、たとえばｎｕｌｌ値に設定することによって、そのブロックを割振り解除するための要求を処理する。さらに、以下で述べる実施形態では、各ハードウェア・スレッドまたはプロセッサについて、本明細書ではシーケンス番号と呼ばれるインジケータを維持し、これは、（たとえば、機能呼出し、中断、マシン・チェック、またはシステム・リセットの結果として）関連付けられたスレッドまたはプロセッサが区画マネージャのプログラム・コードを入力すると必ず増分される。シーケンス番号は、スレッドまたはプロセッサが区画マネージャのプログラム・コードを離れたときも増分される。この実施形態では、シーケンス番号は、奇数値と偶数値の間で（たとえば、各増分についてシーケンス番号に１を追加することによって）増分され、その結果、区画マネージャのプログラム・コードにおけるスレッドの有無は、適宜、奇数または偶数のいずれかの値で示されることになる。たとえば、区画マネージャのプログラム・コードを入力する前にシーケンス番号が奇数であり、その後、入力時に増分された場合、偶数値であれば、区画マネージャのプログラム・コードがスレッドによって実行されたことを示すことになる。その反対に、奇数値であれば、スレッドが区画マネージャのプログラム・コードを実行しておらず、したがってスレッドは、割振り解除される予定の区画制御ブロックを依然として指す共用ポインタの以前のコピーを持たないことを示すことになる。
【００５１】
さらに、シーケンス番号は、スレッドまたはプロセッサが区画マネージャのプログラム・コードを離れた後、再度入力したことを検出する働きをする。具体的に言えば、以下でより明らかになるように、シーケンス番号の値は、２つの時点で獲得可能であり、その結果、区画制御ブロックを割振り解除する要求が受け取られたときにスレッドが区画マネージャのプログラム・コードを実行中であることが最初に発見された場合であっても、その後、シーケンス番号の値にいずれかの変更があれば、スレッドが何らかの時点で区画マネージャのプログラム・コードを離れたこと、したがって、割振り解除される予定の区画制御ブロックを依然として指す共用ポインタの以前のコピーはもはや持たないことを示すことになる。
【００５２】
さらに、以下で述べる実施形態では、各ハードウェア・スレッドまたはプロセッサについて、スレッドまたはプロセッサが、（１）休眠状態（すなわち命令を実行していない）、または（２）アイドル・スレッド内で作業待機中（たとえば区画マネージャのアイドル・スレッドで命令を実行している）の、いずれであるかを示すステータス・フィールドも維持し、どちらの場合も、スレッドまたはプロセッサが、割振り解除される予定の区画制御ブロックを依然として指す共用ポインタの以前のコピーを持たないと判断することができる。
【００５３】
たとえば図２に示されるように、スレッドまたはプロセッサが、共用ポインタを使用することのできるプログラム・コードを実行中であるかどうかの判別に使用される適切なスレッドごとまたはプロセッサごとのインジケータを格納する方法の１つが、複数のスレッド・ステータス・ブロック５６を介するものである。各ブロックに、ブロック５６を特定のハードウェア・スレッドまたはプロセッサに結び付けるスレッド識別子フィールド５８が格納される（単一スレッドのプロセッサの場合）。さらに各ブロック５６は、上記の目的を処理するシーケンス番号フィールド６０およびステータス・フィールド６２も含む。
【００５４】
多種多彩な代替のインジケータおよびそのためのデータ構造が、スレッドまたはプロセッサが共用ポインタを使用することのできるプログラム・コードを実行中であるかどうかの判別に関連して、使用可能であることを理解されよう。したがって本発明は、本明細書で論じられる特定の実施に限定されるものではない。たとえばシーケンス番号は、スレッドが区画マネージャのプログラム・コードを実行中であるか否かをそれぞれ示す２セットの値が定義される結果となる、事実上いずれかの公式を使用して実施することができる。例示された実施形態では、たとえば２セットの値は奇数および偶数である。さらに異なるインジケータを使用して、（１）スレッドが現在区画マネージャのプログラム・コードを実行中であるかどうか、および（２）スレッドが区画マネージャと他のプログラム・コードの間の境界にまたがっているかどうかを検出することができる。さらに代替方法で、他のスレッドのステータス情報を使用することもできる。
【００５５】
次に図３〜６では、本発明に適合した方法で、論理区画の削除および関連付けられた区画制御ブロックの割当て解除を実施するためにコンピュータ１０で使用可能な、様々な例示的ルーチンが示されている。具体的に言えば、図３は、スレッドが区画制御ブロックにアクセスする必要がある場合に必ず、区画マネージャのプログラム・コードを実行中のスレッドによって実行することが可能な、区画制御ブロック・アクセス・ルーチン８０を示す図である。上記で述べたように、例示された実施形態の区画制御ブロックへは、共用ポインタを介してアクセスすることができる。したがって、ハードウェア・スレッドが（たとえば、機能呼出しまたは中断の結果として）区画マネージャのプログラム・コードを入力するといつでも、スレッドは、スレッドがアクセスする必要のある任意の区画制御ブロックを指す共用ポインタの新しいコピーの取得が必要になると想定される。ただし、ハードウェア・スレッドが区画マネージャのプログラム・コードを離れると必ず、共用ポインタのいずれの既存のコピーも廃棄されることも想定される。
【００５６】
したがってルーチン８０は、第１に、ルーチン８０を実行中の現在のスレッドが区画制御ブロックを指すポインタのコピーをすでに持っているかどうかを判別することによって、ブロック８２で開始される。たとえば、スレッドがポインタのコピーをまだ持っていないと想定すると、ブロック８２は制御をブロック８３に渡して、区画制御ブロックを指すポインタのコピーを取得する。次にブロック８４では、ポインタがｎｕｌｌ、すなわち区画制御ブロックが使用できないことを示す値に設定されているかどうかを判別する。設定されていない場合、ブロック８４は制御をブロック８６に渡し、当分野で周知の方法で、ポインタを使用して区画制御ブロックにアクセスする。次に制御はブロック８８に渡り、ルーチン８０を終了して、アクセスが成功したことを示す「ＯＫ」状況に戻る。
【００５７】
ブロック８４に戻り、ポインタがｎｕｌｌ値に設定されている場合、制御は代わりにブロック９０に渡され、アクセスが不成功であったことを示す「エラー」状況でルーチン８０を終了する。ルーチン８０の呼出し元は、その後、適切な方法で不成功のアクセスを処理することになる。さらにブロック８２に戻り、ルーチン８０が呼び出されたときに、区画制御ブロックを指すポインタがすでに取得されている場合、制御はブロック８６に直接渡され、ポインタを使用して区画制御ブロックにアクセスし、通常の様式でルーチンを終了する。
【００５８】
したがって、ポインタにアクセスするごとにセマフォまたはロックを取得するために大幅な処理オーバヘッドが必要であるセマフォまたはロックの実施とは対照的に、ルーチン８０では、スレッドが区画マネージャのプログラム・コードを実行している間にポインタが最初に検出されたときにのみ、ポインタのｎｕｌｌ値をテストするように要求される。したがって、パス長さおよび後続の処理オーバヘッドは大幅に削減される。
【００５９】
次に図４に進むと、区画マネージャ・アクセス・ルーチン９２が総称的に示されている。ルーチン９２は、スレッドが区画または他の非区画マネージャのプログラム・コードの実行から区画マネージャのプログラム・コードの実行へ移行すると必ず呼び出され、区画マネージャ内で所望のタスクを実際に実行する（ブロック９６）前（ブロック９４）および後（ブロック９８）の両方の、スレッドに関連付けられたシーケンス番号の増分概念を示すものである。この実施形態では、区画マネージャのプログラム・コードでスレッドが作成されると、シーケンス番号は初期には偶数値に設定されると想定され、その結果、奇数値は、スレッドが区画マネージャのプログラム・コード以外のプログラム・コードを実行していることを示す。
【００６０】
ブロック９４、９６、および９８は、典型的には区画マネージャのプログラム・コードによって実行されるが、一部の実施では、区画内に常駐するプログラム・コードなどの他のプログラム・コードがこれらのオペレーションのうちの１つまたは複数を実行してもよいことを理解されよう。さらに場合によっては、プログラム・コードが入力および終了されるとシーケンス番号の増分を開始する区画マネージャのプログラム・コードは、区画マネージャのプログラム・コードのディスパッチ不能部分のみ、あるいはそのディスパッチ不能部分およびディスパッチ可能部分の両方を含むことができることを理解されよう。
【００６１】
たとえば、スレッドが休眠状態であること（命令を実行していない）または区画マネージャのアイドル・ループ内で作業待機中であることを示すためのステータス・フィールドの設定には、スレッドの状態が変更されると必ずスレッド専用のステータス・フィールドに適切に書き込まれることのみが組み込まれるため、各スレッドまたはプロセッサのステータス・フィールドの設定は、本明細書では別々に例示されていない。
【００６２】
次に図５は、区画の削除に関連してコンピュータ１００で実行される、論理区画削除ルーチン１００を示す図である。例示された実施形態では、ルーチン１００は、コンピュータ内のユーザ・インターフェースからの特定の区画を削除する要求によって開始される。こうした要求に応答して、およびブロック１０２に示されるように、サービス・プロセッサは、区画マネージャのディスパッチ可能部分に要求を通知することが可能であり、その結果、コンピュータ内のスレッドは、区画マネージャのディスパッチ可能部分での制御を得ることになる。次に、ブロック１０４に示されるように、ディスパッチ可能部分は区画マネージャのディスパッチ不能部分でサービスを呼び出し、具体的には区画制御ブロックを指すポインタをｎｕｌｌ値に設定することによって、削除される予定の区画に対して区画制御ブロックの削除を開始することができる。ただし、後で区画制御ブロックを割振り解除しやすいように、ポインタの以前の値のコピーをディスパッチ不能部分に格納することができる。
【００６３】
次に、ブロック１０６に示されるように、いったんポインタがｎｕｌｌ値に設定されると、呼出しは制御を区画マネージャのディスパッチ可能部分に戻し、ポインタがコンピュータ内のいずれのスレッドによってももはや使用されていないことが判別できるまで待機する。その後、ブロック１０８に示されるように、ディスパッチ可能部分は、区画制御ブロック用のメモリを割振り解除するためのディスパッチ不能部分への呼出しを発行する。その後、制御はディスパッチ可能部分に戻り、ブロック１１０に示されるように、区画を完全に削除するために必要な任意の他のオペレーションが完了する。その後、ルーチン１００は完了する。
【００６４】
図６は、ルーチン１００のブロック１０６で待機中に、区画マネージャのディスパッチ可能部分による実行が可能な、例示的な待機ルーチン１２０を示す図である。具体的に言えば、ルーチン１２０は、コンピュータ内のアクティブ・スレッド（またはプロセッサ）のビット・マスクを準備することによって、ブロック１２２で開始される。次にブロック１２４では、各アクティブ・スレッド（またはプロセッサ）のシーケンス番号が獲得され、区画制御ブロックの割振り解除に関連してｎｕｌｌに設定された共用ポインタの以前のコピーを介して区画制御ブロックにアクセス可能なアクティブ・スレッドがないことが判別できるまで待機するループが、ブロック１２６で開始される。
【００６５】
具体的に言えば、ブロック１２６は、ブロック１２２で準備されたビット・マスク内で識別された各アクティブ・スレッドを処理するためのループを開始する。こうした各スレッドについて、制御がブロック１２８、１３０、１３２、および１３４に渡され、スレッドが区画制御ブロックの共用ポインタの以前のまたは古くなったコピーを使用できるかどうかの指標である、４つのテストが実行される。
【００６６】
ブロック１２８および１３０では、たとえばスレッドのステータス・フィールドが、スレッドがアイドル状態またはループ内にあること、またはそうでなければ休眠状態にあることを示すかどうかが判別される。ブロック１３２では、スレッドの現在のシーケンス番号が、スレッドが区画マネージャのプログラム・コード以外のプログラム・コードを実行中であることを示す、奇数値であるかどうかが判別される。ブロック１３４では、スレッドの現在のシーケンス番号が上記のブロック１２４で獲得されたものと異なるかどうかが判別され、これは、区画制御ブロックの割振り解除プロセスが開始され、ポインタがｎｕｌｌ値に設定された後の何らかの時点で、スレッドが区画マネージャのプログラム・コードを離れた（および潜在的にはこうしたプログラム・コードを再入力した）ことを示す。
【００６７】
ブロック１２８〜１３４でテストされた条件のいずれかが真である場合はいつでも、制御はブロック１３６に渡され、ビット・マスク内のスレッドに関連付けられたビットが消去される。次に制御はブロック１２６に戻り、残りのアクティブ・スレッドが処理される。これに対して、ブロック１２８〜１３４でテストされた条件のいずれも真でない場合、ブロック１３６は迂回され、制御はブロック１２６に直接渡されるが、ビット・マスク内のスレッドに関連付けられたビットは、スレッドが共用ポインタを使用することのできるプログラム・コードを依然として実行していることを示すように設定されたままとなる。
【００６８】
すべてのアクティブ・スレッドが処理されると、ブロック１２６は制御をブロック１３８に渡し、ビット・マスクが、区画制御ブロックにアクセスするために共用ポインタを使用できるアクティブ・スレッドがないことを示す、ゼロに等しいかどうかが判別される。等しい場合、ブロック１３８はルーチン１２０を終了し、区画制御ブロックの割振り解除プロセスを開始することができる。そうでない場合は、いずれかのアクティブ・スレッドが区画制御ブロックにアクセスするために共用ポインタを使用できる区画マネージャのプログラム・コードを依然として実行中である限り、ブロック１３８は制御をブロック１４０に渡し、一定期間遅延させた後、ブロック１２６のループを再開して、すべてのアクティブ・スレッドを再度ポーリングする。共用ポインタのコピーを潜在的に保持しデータ構造にアクセスすることのできるアクティブ・スレッドが検出されない限り、および検出されなくなるまで、ルーチン１２０はブロック１２６のループを繰り返すことになる。
【００６９】
本開示の恩恵を受ける当分野の通常の技術者であれば、本明細書に記載された実施形態の様々な修正形態が明らかになろう。したがって本発明は、添付の特許請求の範囲内に位置付けられる。
【００７０】
まとめとして、本発明の構成に関して以下の事項を開示する。
（１）区画マネージャによって管理される複数の論理区画を含むタイプの論理的に区分されたコンピュータから区画を削除する方法であり、前記論理的に区分されたコンピュータはその上で実行中の複数のスレッドをさらに含み、前記区画マネージャは削除される区画に関連付けられた区画制御ブロックへのアクセス権を有するものであって、前記方法は、
第１のスレッドが前記区画マネージャのプログラム・コードを入力すると必ず、複数スレッドのうちの第１のスレッドに関連付けられたシーケンス番号を、奇数値および偶数値のうちの１つに増分すること、
前記第１のスレッドがプログラム・コードを終了すると必ず、奇数値および偶数値のうちの他方からのシーケンス番号を増分すること、および
前記区画制御ブロックを、
前記区画制御ブロックを指す共用ポインタを、前記区画制御ブロックが使用可能でないことを示すｎｕｌｌ値に設定すること、
前記シーケンス番号の値を獲得すること、
第１のスレッドが非活動状態である第１の条件と、第１のスレッドが区画マネージャ内のアイドル・ループ内で実行中である第２の条件と、シーケンス番号が奇数値および偶数値のうちの１つに設定されている第３の条件と、シーケンス番号が獲得された値から変更された第４の条件とを含む、複数の条件のうちの少なくとも１つに合致することに応答して、第１のスレッドが共用ポインタをもはや使用していないことを判別することを含み、各スレッドが前記共用ポインタを使用するプログラム・コードを実行中であるかどうかを判別するために各スレッドを監視することによって、前記複数スレッドのそれぞれがもはや共用ポインタを使用しなくなるまで待機すること、および
前記複数スレッドそれぞれがもはや前記共用ポインタを使用中でなくなるまで待機した後に、前記区画制御ブロックを割振り解除することによって、割振り解除することを含む方法。
（２）コンピュータ内で実行中の複数のスレッドによってアクセス可能なデータ構造を割振り解除する方法であって、前記方法は、前記データ構造を割振り解除する要求に応答して、
前記データ構造を指す共用ポインタを、その後前記ポインタにアクセスするスレッドに対して前記データ構造が使用可能でないことを示す所定の値に設定すること、
前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラム・コードを各スレッドが実行中であるかどうかを判別するために各スレッドを監視することによって、前記複数のスレッドがもはや前記共用ポインタを使用しなくなるまで待機すること、および
前記複数のスレッドそれぞれがもはや前記共用ポインタを使用しなくなるまで待機した後に、前記データ構造を割振り解除することを含む方法。
（３）各スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラム・コードを実行中であるかどうかを判別することは、前記複数のスレッドのうちの第１のスレッドが非活動状態であるかどうかを判別することを含む、請求項２に記載の方法。
（４）各スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラム・コードを実行中であるかどうかを判別することは、前記複数のスレッドのうちの第１のスレッドがアイドル・ループを実行中であるかどうかを判別することを含む、請求項２に記載の方法。
（５）前記アイドル・ループは区画マネージャのアイドル・ループである、請求項４に記載の方法。
（６）スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラム・コードを実行中であるかどうかを判別することは、前記複数のスレッドのうちの第１のスレッドに関連付けられたインジケータが、前記第１のスレッドが現在他のプログラム・コードを実行中であることを示すかどうかを判別することを含む、請求項２に記載の方法。
（７）スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラム・コードを実行中であるかどうかを判別することは、前記複数のスレッドのうちの第１のスレッドに関連付けられたインジケータが、前記第１のスレッドが前記プログラム・コードを励起したことを示すかどうかを判別することをさらに含む、請求項２に記載の方法。
（８）スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラム・コードを実行中であるかどうかを判別することは、前記複数のスレッドのうちの第１のスレッドに関連付けられたインジケータが、前記第１のスレッドが現在前記プログラム・コードを実行中であること、または前記第１のスレッドが前記プログラム・コードを励起したことを示すかどうかを判別することを含み、前記インジケータは、前記第１のスレッドが前記プログラム・コードを入力すると必ず第１の値から第２の値に更新される、および前記第１のスレッドが前記プログラム・コードを終了すると必ず第２の値から第３の値に更新されるシーケンス番号を含み、さらに前記第１のスレッドに関連付けられた前記インジケータが前記第１のスレッドが前記プログラム・コードを励起したことを示すかどうかを判別することは、前記インジケータをその以前の値と比較することを含む、請求項２に記載の方法。
（９）第１のスレッドが前記プログラム・コードを入力すると必ず、複数スレッドのうちの第１のスレッドに関連付けられたシーケンス番号を、第１の値セットから選択された第１の値から、第２の値セットから選択された第２の値に増分すること、および
前記第１のスレッドが前記プログラム・コードを終了すると必ず、前記シーケンス番号を、前記第１の値セットから選択された第２の値から第３の値に増分することをさらに含む方法であって、
前記複数のスレッドそれぞれがもはや前記共用ポインタを使用しなくなるまで待機することは、各スレッドを監視する前に前記シーケンス番号の値を獲得することを含み、さらに各スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラム・コードを実行中であるかどうかを判別することは、前記第１のスレッドに関連付けられた前記シーケンス番号が前記第２の値セットから選択された値を有するかどうかを判別すること、および前記シーケンス番号が前記獲得された値とは異なる値を有するかどうかを判別することを含む、請求項２に記載の方法。
（１０）前記第１の値セットは奇数からなり、前記第２の値セットは偶数からなる、請求項９に記載の方法。
（１１）前記コンピュータは論理的に区分されたコンピュータであり、前記プログラム・コードは前記コンピュータ内の複数の論理区画にアクセス可能な区画マネージャを含む、請求項２に記載の方法。
（１２）前記プログラム・コードは前記区画マネージャのディスパッチ不能部分を含む、請求項１１に記載の方法。
（１３）前記データ構造は前記区画マネージャによって使用される区画制御ブロックを含む、請求項１１に記載の方法。
（１４）前記共用ポインタを所定の値に設定することは前記共用ポインタをｎｕｌｌ値に設定することを含む、請求項２に記載の方法。
（１５）前記複数のスレッドは単一スレッド・プロセッサ上で実行する第１のスレッドを含む、請求項２に記載の方法。
（１６）前記複数のスレッドはマルチスレッド・プロセッサ上で実行する第１および第２のスレッドを含む、請求項２に記載の方法。
（１７）データ構造が常駐するメモリと、
複数のスレッドを実行するように構成された少なくとも１つのプロセッサと、
前記データ構造を割振り解除する要求に応答して、前記データ構造を指す共用ポインタを、その後前記ポインタにアクセスするスレッドに対して前記データ構造が使用可能でないことを示す所定の値に設定すること、前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラムを各スレッドが実行中であるかどうかを判別するために各スレッドを監視することによって前記複数のスレッドがもはや前記共用ポインタを使用しなくなるまで待機すること、および、前記複数のスレッドそれぞれがもはや前記共用ポインタを使用しなくなるまで待機した後に前記データ構造を割振り解除することにより、前記データ構造を割振り解除するために前記少なくとも１つのプロセッサによって実行されるように構成されたプログラムとを含む装置。
（１８）前記プログラムは、前記複数のスレッドのうちの第１のスレッドが非活動状態であるかどうかを判別することによって、各スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラム手段を実行中であるかどうかを判別するように構成される、請求項１７に記載の装置。
（１９）前記プログラムは、前記複数のスレッドのうちの第１のスレッドがアイドル・ループを実行中であるかどうかを判別することによって、各スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラムを実行中であるかどうかを判別するように構成される、請求項１７に記載の装置。
（２０）前記アイドル・ループは区画マネージャのアイドル・ループである、請求項１９に記載の装置。
（２１）前記プログラムは、前記複数のスレッドのうちの第１のスレッドに関連付けられたインジケータが、前記第１のスレッドが現在他のプログラムを実行中であることを示すかどうかを判別することによって、スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラムを実行中であるかどうかを判別するように構成される、請求項１７に記載の装置。
（２２）前記プログラムは、前記複数のスレッドのうちの第１のスレッドに関連付けられたインジケータが、前記第１のスレッドが前記プログラムを励起したことを示すかどうかをさらに判別することによって、スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラムを実行中であるかどうかを判別するように構成される、請求項１７に記載の装置。
（２３）前記プログラムは、前記複数のスレッドのうちの第１のスレッドに関連付けられたインジケータが、前記第１のスレッドが現在前記プログラムを実行中であること、または前記第１のスレッドが前記プログラムを励起したことを示すかどうかを判別することによって、スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラムを実行中であるかどうかを判別するように構成され、前記インジケータは、前記第１のスレッドが前記プログラムを入力すると必ず第１の値から第２の値に更新される、および前記第１のスレッドが前記プログラムを終了すると必ず第２の値から第３の値に更新されるシーケンス番号を含み、さらに前記プログラムは、前記インジケータをその以前の値と比較することによって、前記第１のスレッドに関連付けられた前記インジケータが前記第１のスレッドが前記プログラムを励起したことを示すかどうかを判別するように構成される、請求項１７に記載の装置。
（２４）さらに前記プログラムは、第１のスレッドが前記プログラムを入力すると必ず、複数スレッドのうちの第１のスレッドに関連付けられたシーケンス番号を、第１の値セットから選択された第１の値から、第２の値セットから選択された第２の値に増分し、および前記第１のスレッドが前記プログラムを終了すると必ず、前記シーケンス番号を、前記第１の値セットから選択された第２の値から第３の値に増分するように構成されるものであって、前記プログラムは、各スレッドを監視する前に前記シーケンス番号の値を獲得することによって、前記複数のスレッドそれぞれがもはや前記共用ポインタを使用しなくなるまで待機するように構成され、前記プログラムは、前記第１のスレッドに関連付けられた前記シーケンス番号が前記第２の値セットから選択された値を有するかどうか、および前記シーケンス番号が前記獲得された値とは異なる値を有するかどうかを判別することによって、各スレッドが前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラムを実行中であるかどうかを判別するように構成される、請求項１７に記載の装置。
（２５）前記第１の値セットは奇数からなり、前記第２の値セットは偶数からなる、請求項２４に記載の装置。
（２６）前記装置は論理的に区分されたコンピュータとして構成され、前記プログラムは前記少なくとも１つのプロセッサ上で実行中の複数の論理区画にアクセス可能な区画マネージャを含む、請求項１７に記載の装置。
（２７）前記プログラムは前記区画マネージャのディスパッチ不能部分を含む、請求項２６に記載の装置。
（２８）前記データ構造は前記区画マネージャによって使用される区画制御ブロックを含む、請求項２６に記載の装置。
（２９）前記プログラムは、前記共用ポインタをｎｕｌｌ値に設定することによって、前記共用ポインタを所定の値に設定するように構成される、請求項１７に記載の装置。
（３０）前記少なくとも１つのプロセッサは単一スレッド・プロセッサを含む、請求項１７に記載の装置。
（３１）前記少なくとも１つのプロセッサはマルチスレッド・プロセッサを含む、請求項１７に記載の装置。
（３２）前記データ構造を割振り解除する要求に応答して、前記データ構造を指す共用ポインタを、その後前記ポインタにアクセスするスレッドに対して前記データ構造が使用可能でないことを示す所定の値に設定すること、前記データ構造にアクセスするために前記共用ポインタを使用することのできるプログラム・コードを各スレッドが実行中であるかどうかを判別するために各スレッドを監視することによって前記複数のスレッドがもはや前記共用ポインタを使用しなくなるまで待機すること、および、前記複数のスレッドそれぞれがもはや前記共用ポインタを使用しなくなるまで待機した後に前記データ構造を割振り解除することにより、コンピュータ内で複数のスレッドを実行することによってアクセス可能なデータ構造を割振り解除するように構成されたプログラム・コードを含む、コンピュータ読み取り可能な記録媒体。
【図面の簡単な説明】
【００７１】
【図１】本発明に適合する論理的に区分されたコンピュータにおける主要なハードウェア構成要素を示す構成図である。
【図２】図１の論理的に区分されたコンピュータにおいて区画管理に関連して使用されるいくつかのデータ構造を示した、区画管理メモリ・スペースを示す構成図である。
【図３】図１のコンピュータによって実行される区画制御ブロック・アクセス・ルーチンのプログラム流れを示す流れ図である。
【図４】図１のコンピュータによって実行される区画マネージャ・アクセス・ルーチンのプログラム流れを示す流れ図である。
【図５】図１のコンピュータによって実行される論理区画削除ルーチンのプログラム流れを示す流れ図である。
【図６】図５で参照されたディスパッチ可能サービスによって実行される待機ルーチンのプログラム流れを示す流れ図である。
【符号の説明】
【００７２】
１０    コンピュータ
１２、１２ａ、１２ｂ    システム・プロセッサ
１４    メモリ
１６    バス
１８    ＨＷスレッド
２０    バス
２２    ネットワーク・アダプタ
２４    ネットワーク
２６    記憶域コントローラ
２８    記憶デバイス
３０    ワークステーション・コントローラ
３２    端末
３４    区画
３６    区画マネージャ
３８    区画マネージャ（ディスパッチ不能部分）
４０    区画マネージャ（ディスパッチ可能部分）
４２    オペレーティング・システム
４４    ｕｓｅｒ  ａｐｐ
４６    仮想ＬＡＮ
【図１】
2004295882.tif 000003
【図２】
2004295882.tif 000004
【図３】
2004295882.tif 000005
【図４】
2004295882.tif 000006
【図５】
2004295882.tif 000007
【図６】
2004295882.tif 000008