(57)【特許請求の範囲】
【請求項１】
相互排除目的に用いられるロックを保持する先行プロセスが該ロックの所有権を喪失した場合にロバスト回復を提供する方法であって、該所有権の喪失は、該先行プロセスが停止するか、または該ロックがマッピングされないことによって発生し、該方法は、
オペレーティングシステムが、該ロックを獲得することを試みることと、
該ロックを獲得する試みが、該ロックを保持していた先行プロセスが該ロックの所有権を喪失したことを示すエラーを伴って戻ってきた場合に、
該オペレーティングシステムが、該ロックにより保護されるプログラム状態を一貫させることを試みることと、
該プログラム状態を一貫させる試みが成功した場合に、該オペレーティングシステムが、該ロックを再初期化して、該ロックを解除することと、
該プログラム状態を一貫させる試みが成功しなかった場合に、該オペレーティングシステムが、該ロックを獲得しようとする後続プロセスが、該ロックが回復不能であることを示すエラーを受け取るように、該ロックを回復不能としてマークすることと、
該ロックを獲得する試みが、該ロックが回復不能であることを示すエラーを伴って戻ってきた場合に、
該オペレーティングシステムが、非一貫であるプログラム状態に対処する動作を実行することと、
該オペレーティングシステムが、該ロックを破棄することと、
該オペレーティングシステムが、他のプロセスが該ロックを獲得し得るように、該ロックを再初期化することと
を含む、方法。
【請求項２】
前記ロックを獲得する試みがエラー条件を伴わずに戻ってきた場合に、
前記オペレーティングシステムが、該ロックにより保護される前記プログラム状態を操作することと、
該オペレーティングシステムが、ロックを解除することと
をさらに含む、請求項１に記載の方法。
【請求項３】
前記オペレーティングシステムが、プロセスが停止したことの通告を受け取ることと、
該オペレーティングシステムが、ロックの保持中において該プロセスが停止したかどうかを判定することと、
該ロックの保持中に該プロセスが停止した場合に、
該オペレーティングシステムが、該ロックの後続獲得に対し、該ロックの先行保持が停止したことを示すように該ロックをマークすることと、
該オペレーティングシステムが、他のプロセスが該ロックを獲得し得るように該ロックを解除することと
をさらに含む、請求項１に記載の方法。
【請求項４】
前記ロックを回復不能としてマークする工程は、前記オペレーティングシステムが、該ロック上で待機するプロセスを起動させ、これにより、該ロック上で待機する該プロセスが、該ロックを引き続き獲得することを試み、該ロックが回復不能であることを示すエラーを受け取ることをさらに含む、請求項１に記載の方法。
【請求項５】
前記ロックは、複数のプロセスにより共有されるメモリ内に常駐する、請求項１に記載の方法。
【請求項６】
前記ロックは、複数のプロセスにより共有されるファイル内に常駐する、請求項１に記載の方法。
【請求項７】
前記ロックは、オペレーティングシステムの呼び出しを実行せずに、複数のプロセスにより直接アクセスされ得るロケーションに常駐する、請求項１に記載の方法。
【請求項８】
相互排除目的に用いられるロックを保持する先行プロセスが該ロックの所有権を喪失した場合にロバスト回復を提供する方法であって、該所有権の喪失は、該先行プロセスが停止するか、または該ロックがマッピングされないことによって発生し、該方法は、
オペレーティングシステムが、プロセスが停止したことの通告を受け取ることと、
該オペレーティングシステムが、該ロックの保持中に該プロセスが停止したかどうかを判定することと、
該ロックの保持中に該プロセスが停止した場合に、
該オペレーティングシステムが、該ロックの後続獲得に対し、該ロックの先行保持が該ロックの所有権を喪失したことを示すように該ロックをマークすることと、
該オペレーティングシステムが、他のプロセスが該ロックを獲得し得るように該ロックを解除することと、
該オペレーティングシステムが、該ロックを獲得することを試みることと、
該ロックを獲得する試みが、該ロックを保持していた先行プロセスがロックの所有権を喪失したことを示すエラーを伴って戻ってきた場合に、
該オペレーティングシステムが、該ロックにより保護されるプログラム状態を一貫させることを試みることと、
該プログラム状態を一貫させる試みが成功した場合に、該オペレーティングシステムが、該ロックを再初期化して、該ロックを解除することと、
該プログラム状態を一貫させる試みが成功しなかった場合に、該オペレーティングシステムが、該ロックを獲得しようとする後続プロセスが、該ロックが回復不能であることを示すエラーを受け取るように、該ロックを回復不能としてマークすることと、
該ロックを獲得する試みが、該ロックが回復不能であることを示すエラーを伴って戻ってきた場合に、
該オペレーティングシステムが、非一貫であるプログラム状態に対処する動作を実行することと、
該オペレーティングシステムが、該ロックを破棄することと、
該オペレーティングシステムが、他のプロセスが該ロックを獲得し得るように、該ロックを再初期化することと、
該ロックを獲得しようとする試みが、エラー条件を伴わずに戻ってきた場合に、
該オペレーティングシステムが、該ロックにより保護されるプログラム状態を操作することと、
該オペレーティングシステムが、該ロックを解除することと
を含む、方法。
【請求項９】
前記ロックを回復不能としてマークする前記工程は、前記オペレーティングシステムが、該ロック上で待機するプロセスを起動させ、これにより、該ロック上で待機する該プロセスが、該ロックを引き続き獲得することを試み、該ロックが回復不能であることを示すエラーを受け取ることをさらに含む、請求項８に記載の方法。
【請求項１０】
前記ロックは、オペレーティングシステムの呼び出しを実行せずに、複数のプロセスにより直接アクセスされ得るロケーションに常駐する、請求項８に記載の方法。
【請求項１１】
コンピュータにより実行されるとき、相互排除目的に用いられるロックを保持する先行プロセスが該ロックの所有権を喪失した場合に、該コンピュータにロバスト回復を提供するための方法を実行させる命令を格納するコンピュータ読み出し可能な格納媒体であって、該所有権の喪失は、該先行プロセスが停止するか、または該ロックがマッピングされないことによって発生し、該方法は、
該ロックを獲得することを試みることと、
該ロックを獲得する試みが、該ロックを保持していた先行プロセスがロックの所有権を喪失したことを示すエラーを伴って戻ってきた場合に、
該ロックにより保護されるプログラム状態を一貫させることを試みることと、
該プログラム状態を一貫させる試みが成功した場合に、該ロックを再初期化して、該ロックを解除することと、
該プログラム状態を一貫させる試みが成功しなかった場合に、該ロックを獲得しようとする後続プロセスが、該ロックが回復不能であることを示すエラーを受け取るように該ロックを回復不能としてマークすることと、
該ロックを獲得する試みが、該ロックが回復不能であることを示すエラーを伴って戻ってきた場合に、
非一貫であるプログラム状態に対処する動作を実行することと、
該ロックを破棄することと、
他のプロセスが該ロックを獲得し得るように、該ロックを再初期化することと
を含む、コンピュータ読み出し可能な格納媒体。
【請求項１２】
相互排除目的に用いられるロックを保持する先行プロセスが該ロックの所有権を喪失した場合にロバスト回復を提供する装置であって、該所有権の喪失は、該先行プロセスが停止するか、または該ロックがマッピングされないことによって発生し、該装置は、
該ロックを獲得することを試みるロック獲得機構と、
該ロックを獲得する試みが、該ロックを保持していた先行プロセスが該ロックの所有権を喪失したことを示すエラーを伴って戻ってきた場合に、該ロックにより保護されるプログラム状態を一貫させることを試みる一貫性回復機構と、
該プログラム状態を一貫させる試みが成功した場合に、該ロックを再初期化し、該ロックを解除する第１のロック再初期化機構と、
該プログラム状態を一貫させる試みが成功しなかった場合に、該ロックを獲得しようとする後続プロセスが、該ロックが回復不能であることを示すエラーを受け取るように、該ロックを回復不能としてマークする第１のロックマーク機構と、
該プログラム状態を一貫させる試みに後続するプロセスが、該ロックが回復不能であることを示すエラーを受け取る場合に、非一貫であるプログラム状態に対処する動作を実行する対処機構と、
該非一貫であるプログラム状態を対処する動作が実行された後に、該ロックを破棄するロック廃棄機構と、
該ロックが廃棄された後に、該ロックを再初期化する第２のロック再初期化機構と
を含む、装置。
【請求項１３】
前記装置は、オペレーティングシステム内にある第２のロックマーク機構をさらに含み、プロセスが停止したことの通告を受け取った際に、該第２のロックマーク機構は、ロックの保持中において該プロセスが停止したかどうかを判定し、該ロックの保持中に該プロセスが停止した場合に、該ロックをマークし、該ロックの先行保持が停止したことを該ロックの後続獲得に対して示し、該ロックを解除して、これにより、他のプロセスが該ロックを獲得し得る、請求項１２に記載の装置。
【請求項１４】
前記ロックは、オペレーティングシステムの呼び出しを実行せずに、複数のプロセスにより直接アクセスされ得るロケーションに常駐する、請求項１２に記載の装置。
【請求項１５】
前記ロックを保持する先行プロセスが該ロックの所有権を喪失した場合にロバスト回復を提供することを容易にするロックデータ構造をさらに含み、該所有権の喪失は、該先行プロセスが停止するか、または該ロックがマッピングされないことによって発生し、該データ構造は、
該ロックがロックされたかどうかを示すロックフラグと、
第２のプロセスが、該ロックを保持していた第１のプロセスが該ロックの所有権を喪失した後で該ロックにより保護されるプログラム状態を一貫できなかったことを示す回復性インジケータと
を含む、請求項１１に記載のコンピュータ読み出し可能な格納媒体。
【請求項１６】
前記ロックにより保護されるプログラム状態が一貫した状態であるかどうかを示すフラグを含む、請求項１５に記載のロックデータ構造を含むコンピュータ読み出し可能な格納媒体。
【請求項１７】
前記ロックが回復性インジケータを備えるロバストロックであるかどうかを示すロック型インジケータを含む、請求項１５に記載のロックデータ構造を含むコンピュータ読み出し可能な格納媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータシステムにおけるプロセス間同期化機構に関する。より詳細には、本発明は、ロックの保持中においてプロセスが失敗した場合に、ロバストな回復を提供するプロセス間ロックを適用するための方法および装置に関する。
【０００２】
【従来の技術】
コンピュータシステムは、単一の演算タスクにおいて、ともに動作し得る複数のプロセスをしばしばサポートしている。複数のプロセスを使用する際の課題の１つは、互いに干渉しないようにプロセスを同期させることである。これは、典型的には、相互排除（mutual exclusion）ロック（ミューテックスロック（mutex lock））を介して達成される。相互排除ロックは、特定のタスクを実行したり、共有データの特別なアイテムにアクセスするのが、一度に１つのプロセスのみであることを確実にする。
【０００３】
プロセスは、典型的には、コードの重要（critical）部分を実行したり、共有データの特別なアイテムにアクセスする前に、ロックを「獲得」しようとする。その時点で他のプロセスが、ロックを保持していない場合、上記プロセスが、そのロックをロック状態に設定することによりロックを獲得する。ロックを獲得した後、そのプロセスは、他のプロセスからの干渉を受けることなく、コードの重要部分を実行したり、共有データのアイテムを操作する自由を得る。そのプロセスがロックを保持している間、そのロックを獲得しようとする他のプロセスは、「ブロック」して、そのロックを待ち、ロックが解除されるまで進行できない。上記プロセスはタスクを完了した後にロックを解除し、これにより、他のプロセスがロックを獲得できる。
【０００４】
相互排除プロセスは、ロバストな動作をするコンピュータシステムにとって複雑さを生み出している。そのような「ロバスト」コンピュータシステムは、１つの演算タスクに関わる複数のプロセスまたはプロセッサが、プログラム実行の最中にたとえ失敗しても、プロセスを継続するように設計されている。相互排除ロックを保持している間にプロセスが失敗した場合、そのロックを獲得しようと試みる他のプロセスは「ハング」して、失敗したプロセスがロックを解除するのを待つ。その結果、演算タスクは停止する。
【０００５】
この問題を解消するために、ロックを保持するプロセスが失敗した場合、単にロックを解除するコンピュータシステムもある。これにより、そのロックでブロックされていた他のプロセスは、継続することが可能になる。しかしながら、失敗したプロセスは、そのロックにより保護されるデータを、非一貫した（inconsistent）状態に取り残し得る。これにより、それ以降のある時点において、残りのプロセスが不正確な結果を生成したり、または失敗し得る。
【０００６】
プロセスが停止したときに、そのロックで保護されていた状態が、非一貫した状態に取り残されたことを、他のプロセスに通告するシステムもある。これにより、他のプロセスは、その状態を再び一貫させる動作を取ることができる。しかしながら、他のプロセスがその状態を再び一貫させることに成功しないこともあり得る。この場合、結果的に、それ以降のある時点において、残りのプロセスが不正確な結果を生成したり、または失敗し得る。
【０００７】
【発明が解決しようとする課題】
必要とされるのは、ロックを保持しているプロセスが失敗しても他のプロセスがハングしないロバストな回復可能ロックを提供する方法および装置であり、これにより、他のプロセスは、そのロックにより保護されていた状態を一貫した状態に回復することができる。
【０００８】
【課題を解決するための手段】
本発明による方法は、相互排除目的に用いられるロックを保持する先行プロセスが、該ロックの所有権を喪失した場合に、ロバスト回復を提供する方法であって、該所有権の喪失が、該先行プロセスが停止するか、または該ロックがマッピングされないことによって発生し、該方法が、該ロックを獲得することを試みる工程と、該ロックを獲得する試みが、該ロックを保持していた先行プロセスが該ロックの所有権を喪失したことを示すエラーを伴って戻ってきた場合に、該ロックにより保護されるプログラム状態を一貫させることを試みる工程と、該プログラム状態を一貫させる試みが成功した場合、該ロックを再初期化して、該ロックを解除する工程と、該プログラム状態を一貫させる試みが成功しなかった場合、該ロックを回復不能としてマークし、これにより、該ロックを獲得しようとして後続するプロセスは、該ロックが回復不能であることを示すエラーを受け取る工程と、を含み、それにより上記目的が達成される。
【０００９】
前記ロックの獲得を試みる前記工程が、エラー条件を伴わずに戻ってきた場合、該ロックにより保護される前記プログラム状態を操作する工程と、ロックを解除する工程と、をさらに含んでもよい。
【００１０】
オペレーティングシステムにおいて、プロセスが停止したことの通告を受け取る工程と、ロックの保持中において該プロセスが停止したかどうかを判定する工程と、該ロックの保持中に該プロセスが停止した場合、該ロックの後続獲得に対し、該ロックの先行保持が停止したことを示すよう該ロックをマークする工程と、
該ロックを解除し、他のプロセスが該ロックを獲得し得るようにする工程と、をさらに含んでもよい。
【００１１】
前記ロックを獲得する前記工程が、該ロックが回復不能であることを示すエラーを伴って戻ってきた場合、非一貫である前記プログラム状態に対処する動作を実行する工程と、該ロックを再初期化する工程と、をさらに含んでもよい。
【００１２】
前記ロックを回復不能としてマークする前記工程が、該ロック上で待機するプロセスを起動させ、これにより、該ロック上で待機する該プロセスが、該ロックを引き続き獲得することを試み、該ロックが回復不能であることを示すエラーを受け取ることをさらに含んでもよい。
【００１３】
前記ロックが、複数のプロセスにより共有されるメモリ内に常駐してもよい。
【００１４】
前記ロックが、複数のプロセスにより共有されるファイル内に常駐してもよい。
【００１５】
前記ロックが、オペレーティングシステムの呼び出しを実行せずに、複数のプロセスにより直接アクセスされ得るロケーションに常駐してもよい。
【００１６】
本発明の方法は、相互排除目的に用いられるロックを保持する先行プロセスが、該ロックの所有権を喪失した場合に、ロバスト回復を提供する方法であって、該所有権の喪失が、該先行プロセスが停止するか、または該ロックがマッピングされないことによって発生し、該方法が、オペレーティングシステムにおいて、プロセスが停止したことの通告を受け取る工程と、該ロックの保持中に該プロセスが停止したかどうかを判定する工程と、該ロックの保持中に該プロセスが停止した場合、該ロックの後続獲得に対し、該ロックの先行保持が該ロックの所有権を喪失したことを示すよう該ロックをマークする工程と、該ロックを解除し、他のプロセスが該ロックを獲得し得るようにする工程と、を含む工程と、該ロックを獲得することを試みる工程と、該ロックを獲得する試みが、該ロックを保持していた先行プロセスがロックの所有権を喪失したことを示すエラーを伴って戻ってきた場合に、該ロックにより保護されるプログラム状態を一貫させることを試みる工程と、該プログラム状態を一貫させる試みが成功した場合、該ロックを再初期化して、該ロックを解除し、該プログラム状態を一貫させる試みが成功しなかった場合、該ロックを回復不能としてマークし、これにより、該ロックを獲得しようとして後続するプロセスは、該ロックが回復不能であることを示すエラーを受け取る工程と、該ロックを獲得しようとする試みが、エラー条件を伴わずに戻ってきた場合、該ロックにより保護される前記プログラム状態を操作する工程と、ロックを解除する工程と、を含み、それにより上記目的が達成される。
【００１７】
前記ロックを獲得する前記工程が、該ロックが回復不能であることを示すエラーを伴って戻ってきた場合、非一貫である前記プログラム状態に対処する動作を実行する工程と、該ロックを再初期化する工程と、をさらに含んでもよい。
【００１８】
前記ロックを回復不能としてマークする前記工程が、該ロック上で待機するプロセスを起動させ、これにより、該ロック上で待機する該プロセスが、該ロックを引き続き獲得することを試み、該ロックが回復不能であることを示すエラーを受け取ることをさらに含んでもよい。
【００１９】
前記ロックが、オペレーティングシステムの呼び出しを実行せずに、複数のプロセスにより直接アクセスされ得るロケーションに常駐してもよい。
【００２０】
本発明のコンピュータ読み出し可能な格納媒体は、コンピュータにより実行されるとき、該相互排除目的に用いられるロックを保持する先行プロセスが、該ロックの所有権を喪失した場合に、該コンピュータにロバスト回復を提供するための方法を実行させる指示を格納するコンピュータ読み出し可能な格納媒体であって、該所有権の喪失が、該先行プロセスが停止するか、または該ロックがマッピングされないことによって発生し、該媒体が、該ロックを獲得することを試みる工程と、該ロックを獲得する試みが、該ロックを保持していた先行プロセスがロックの所有権を喪失したことを示すエラーを伴って戻ってきた場合に、該ロックにより保護されるプログラム状態を一貫させることを試みる工程と、該プログラム状態を一貫させる試みが成功した場合、該ロックを再初期化して、該ロックを解除する工程と、該プログラム状態を一貫させる試みが成功しなかった場合、該ロックを回復不能としてマークし、これにより、該ロックを獲得しようとして後続するプロセスは、該ロックが回復不能であることを示すエラーを受け取る工程と、を含み、それにより上記目的が達成される。
【００２１】
本発明の装置は、相互排除目的に用いられるロックを保持する先行プロセスが、該ロックの所有権を喪失した場合に、ロバスト回復を提供する装置であって、該所有権の喪失が、該先行プロセスが停止するか、またはロックがマッピングされないことによって発生し、該装置が、該ロックを獲得することを試みるロック獲得機構と、該ロックを獲得する試みが、該ロックを保持していた先行プロセスがロックの所有権を喪失したことを示すエラーを伴って戻ってきた場合に、該ロックにより保護されるプログラム状態を一貫させることを試みる一貫性回復機構と、該プログラム状態を一貫させる試みが成功した場合、該ロックを再初期化し、該ロックを解除するロック再初期化機構と、該プログラム状態を一貫させる試みが成功しなかった場合、該ロックを回復不能としてマークし、これにより、該ロックを獲得しようとして後続するプロセスは、該ロックが回復不能であることを示すエラーを受け取る第１のロックマーク機構と、を含み、それにより上記目的が達成される。
【００２２】
オペレーティングシステムにおいて第２のロックマーク機構をさらに含む装置であって、プロセスが停止したことの通告を受け取った際に、該第２のロックマーク機構が、ロックの保持中において該プロセスが停止したかどうかを判定し、該ロックの保持中に該プロセスが停止した場合、該ロックをマークし、該ロックの先行保持が停止したことを該ロックの後続獲得に対して示し、該ロックを解除して、これにより、他のプロセスが該ロックを獲得し得る、第２のロックマーク機構であってもよい。
【００２３】
プログラム回復機構をさらに含む装置であって、前記ロックを獲得する試みが、該ロックが回復不能であることを示すエラーを伴って戻ってきた場合、該プログラム回復機構が、非一貫性の前記プログラム状態に対処する動作を実行し、該ロックを再初期化してもよい。
【００２４】
前記ロックが、オペレーティングシステムの呼び出しを実行せずに、複数のプロセスにより直接アクセスされ得るロケーションに常駐してもよい。
【００２５】
本発明のコンピュータ読み出し可能な格納媒体は、ロックを保持する先行プロセスが該ロックの所有権を喪失した場合に、ロバスト回復を提供することを容易にするロックデータ構造を含むコンピュータ読み出し可能な格納媒体であって、該所有権の喪失が、該先行プロセスが停止するか、またはロックがマッピングされないことによって発生し、該データ構造が、該ロックがロックされたかどうかを示すロックフラグと、第２のプロセスは、該ロックを保持していた第一のプロセスが該ロックの所有権を喪失した後で該ロックにより保護されるプログラム状態を一貫できなかったことを示す回復性インジケータと、を含み、それにより上記目的が達成される。
【００２６】
前記ロックにより保護されるプログラム状態が、一貫した状態であるかどうかを示すフラグを備えてもよい。
【００２７】
前記ロックが回復性インジケータを備えるロバストロックであるかどうかを示すロック型インジケータを含んでもよい。
【００２８】
本発明の１実施形態は、相互排除目的に用いられるロックを保持する先行プロセスが、該ロックの所有権を喪失した場合に、回復をサポートするシステムを提供する。この所有権の喪失は、先行プロセスが停止するか、またはロックがマッピングされないことによって発生する。本発明によれば、プロセスは先ずロックの獲得を試みる。ロックを保持していた先行プロセスがロックの所有権を喪失したことを示すエラーを伴って、ロックを獲得する試みが戻ってきた場合に、そのプロセスは、ロックにより保護されるプログラム状態を一貫させることを試みる。プログラム状態を一貫させる試みが成功した場合、このロックを再初期化し解除する。そうでない場合、システムは、このロックを回復不能とマークするので、このロックを獲得しようと試みる後続プロセスは、このロックが回復不能であることを通告される。
【００２９】
本発明の１局面では、オペレーティングシステムにおいて、プロセスが停止したことの通告を受け取り、ロックの保持中においてこのプロセスが停止したかどうかを判定することを含む。ロックの保持中にプロセスが停止した場合、システムは、このロックの後続獲得に対し、ロックの先行保持が停止したことを示すようロックをマークし、このロックを解除して、他のプロセスがこのロックを獲得し得るようにする。
【００３０】
本発明の１局面では、このロックが回復不能であることを示すエラーを伴って、ロックを獲得する試みが戻ってきた場合、このプロセスは、一貫していないプログラム状態に対処する動作を実行し、このロックを再初期化することを含む。
【００３１】
【発明の実施の形態】
米国特許法施行規則第１条７１項（ｅ）に準ずる著作権表示
この特許文書の開示内容は、著作権保護の対象となる内容を含む。著作権者は、米国特許商標庁の特許資料または記録に表される形においての、本特許書類または特許開示の第三者によるファクシミリ複製に対し異議を述べないが、その他の場合には著作権に反するものである。
【００３２】
以下の説明は、任意の当業者が本発明を利用できるように提示され、特定の応用および要件における文脈で提供される。開示される実施形態の様々な変更は、当業者には直ちに明白であり、本明細書に規定される一般原則は、本発明の精神および範囲から逸脱することなく他の実施形態および用途に適用し得る。従って、本発明は、例示された実施形態により限定されることを意図しておらず、本願に開示される原理および特徴に合致する最大限の範囲に一致する。
【００３３】
この詳細な説明に記載されるデータ構造およびコードは、典型的には、コンピュータ読み出し可能の格納媒体に格納されるが、これは、コンピュータシステムにより使用されるコードおよび／またはデータを格納し得る任意のデバイスまたは媒体である。これは、ディスクドライブ、磁気テープ、ＣＤ（コンパクトディスク）およびＤＶＤ（デジタルビデオディスク）などの磁気および光学格納素子、ならびに搬送波において実施されたコンピュータ命令信号を含むが、これらに限定されるものではない。例えば、搬送波は、インターネットなどの通信網から発信され得る。
【００３４】
コンピュータシステム
図１は、本発明の実施形態により、複数プロセスを実行できるコンピュータシステムを示す。このシステムは、メモリ１０４に結合された中央プロセス装置（ＣＰＵ）１０２を含む。ＣＰＵ１０２は、コードおよび／またはデータプロセスできる任意の型の演算デバイスを含み得る。これには、メインフレームプロセッサ、マルチプロセッサ、マイクロプロセッサ、デバイスコントローラ、および器具内の演算ユニットを含むが、これらに限定されない。メモリ１０４は、ＣＰＵ１０２による実行のためのコードおよび／またはデータを格納するのに使用できる任意の型のランダムアクセスメモリを含む。ＣＰＵ１０２は、専用プロセッサ／メモリバス、システムバス、または介在（intervening）コア論理装置を介することを含む数々の様態で、メモリ１０４に結合し得る。
【００３５】
ＣＰＵ１０２は、バス１０６を介して他の周辺機器の数々にさらに結合される。これらの周辺機器は、ディスク１０８、ネットワークインターフェイス制御器（ＮＩＣ）１１０、ディスプレイ１１２およびキーボード１１４を含む。ディスク１０８は、磁気または光学ディスクドライブあるいはテープドライブを含む、任意の型の二次格納デバイスを意味する。ＮＩＣ１１０は、コンピュータシステムをコンピュータネットワーク１１３に結合するための回路を含む。ネットワーク１１３は、ローカルエリアネットワークおよび／または広域ネットワークなど、コンピュータシステムを結合するのに使用できる任意の型のネットワークまたはネットワークの集合であり得る。ディスプレイ１１２は、グラフィック画像のためのコンピュータモニタはオーディオデータのためのオーディオ出力装置を含む、コンピュータシステムのための任意の出力装置であり得る。キーボード１１４は、コンピュータシステムへの入力を受け取るための任意の型の装置を含み得る。これは、コンピュータキーボードおよびコンピュータマウスを含むが、これらに限定されない。
【００３６】
図１にはコンピュータシステムの特定の実施例を示すが、本発明は一般的に、マルチプロセッサを備えたコンピュータシステムを含む、複数プロセスを行い得るすべてのコンピュータシステムに当てはまることに留意されたい。
【００３７】
図１は、オペレーティングシステム１２０をさらに示す。オペレーティングシステム１２０は、プロセス１２２、１２４、および１２６を含むプロセスの集合の実行を容易にする。プロセス１２２、１２４、および１２６は、ライトウエイトプロセスおよびヘビーウエイトプロセス、ならびにシステムプロセスおよびユーザプロセスを含む、コンピュータシステムにより一般的に実行される任意の型のプロセスであり得る。
【００３８】
プロセス１２２、１２４、および１２６は、共有メモリ１２８にアクセスする。共有メモリ１２８は、共有半導体メモリ１０４の一領域であるか、あるいは共有ファィルであり得る。共有メモリ１２８は、ミューテックスロック１３０を含む。ミューテックスロック１３０は、プロセス１２２、１２４、および１２６により使用され、メモリ１０４内の共有データのコードまたはアイテムの重要部分に排他的アクセスを提供する。
【００３９】
オペレーティングシステム
図２は、本発明の実施形態によるオペレーティングシステム１２０の内部構造の部分を示す。オペレーティングシステム１２０は、ユーザスレッド層２０８、カーネルスレッド層２０６、スケジューラ２０４およびデバイスドライバ２０２を含む、複数の層および機能モジュールを含む。デバイスドライバ２０２は、コンピュータシステムに接続されたオペレーティング装置のためのデバイスドライバを含む。例えば、デバイスドライバ２０２は、ディスク１０８にアクセスするためのデバイスドライバ、およびＮＩＣ１１０にアクセスするためのデバイスドライバを含み得る。
【００４０】
スケジューラ２０４は、１つ以上の中央プロセス装置における実行のためのスレッドおよび／またはプロセスのスケジューリングに対するリソースを含む。スケジューラ２０４は、カーネルスレッド２０６およびユーザスレッド２０８の両方を操作する。カーネルスレッド２０６は、オペレーティングシステム１２０内のオペレーティングシステム機能全体を作動させるカーネルレベルスレッドと、ユーザスレッド２０８に関連するライトウエイトプロセススレッド２０７とを含む。ユーザスレッド２０８は、ユーザプログラムを実行するのに使用される。図２に示す実施形態では、複数のユーザスレッド２０８を、単一のライトウエイトプロセススレッド２０７にマッピングし得る。
【００４１】
図２には特定のオペレーティングシステム構造を概略するが、本発明は、マルチプロセッサが単一の演算タスクを実行できる任意のオペレーティングシステムに当てはまることに留意されたい。
【００４２】
データ構造
図３は、本発明の実施形態により、ロバストなロックを適用することに関連するデータ構造のいくつかを示す。この実施形態は、プロセス状態３０２を示す。プロセス状態３０２は、図１のプロセス１２２など、ミューテックスロック３０８へのアクセスを有するプロセスに関連する状態を含む。プロセス状態３０２は、プロセス１２２に関連する状態を含む。この状態は、オペレーティングシステム１２０内のデータ構造（またはデータオブジェクト）に格納される。例えば、プロセス状態３０２は、プロセスのためのオープンファイル３０４のリストを含む。また、プロセス状態３０２は、プロセス１２２により使用され得るロックのリストを含むロックレジストリ３０６をも含む。例えば、図３では、ロックレジストリ３０６がミューテックスロック３０８に対するポインタを含んでいる。
【００４３】
ロックレジストリ３０６により、オペレーティングシステム１２０は、ロックの保持中にプロセス１２２が停止したかどうかを判定することができる。ミューテックスロック３０８は初期化された後で、ミューテックスロック３０８へのアクセスを望む任意のプロセスのロックレジストリ３０６に登録される。例えば、ミューテックスロック３０８は、プロセス１２２のためのロックレジストリ３０６に登録され得る。これにより、オペレーティングシステムは、プロセス１２２が停止した時および場合に、プロセス１２２が保持する任意のロックを判定し識別することができる。また、ロックレジストリ３０６は、プロセス状態３０２の外で、プロセス識別子によりインデックスされる独立したロックレジストリ内に代わりに常駐し得ることに留意されたい。
【００４４】
ミューテックスロック３０８は、ロックに関連する状態を含む。この状態は、ロックフラグ３１０、一貫性フラグ３１２、回復性インジケータ３１４、およびロック型インジケータ３１６を含む。ロックフラグ３１０は、ミューテックスロック３０８がロックされたか否かを示す１バイトまたは１ワードを含む。ミューテックスロック３０８が１つのプロセスによって保持される間、ロックフラグ３１０は、ロック状態に設定されるので、他のプロセスはミューテックスロック３０８を獲得できない。一貫性フラグ３１２は、ミューテックスロック３０８により保護されるプログラム状態が一貫しているかどうかを示す。回復性インジケータ３１４は、ミューテックスロック３０８により保護されるプロセスが、ミューテックスロックを保持するプロセスの終了後に回復可能かどうかを示す。最後に、ロック型インジケータ３１６は、ミューテックスロック３０８がいかなる型のロックであるかを示す。例えば、ロック型インジケータ３１６は、ミューテックスロック３０８がロバストロックであるか非ロバストロックであるかを示し得る。
【００４５】
ロバストロックの動作
図４は、本発明の実施形態により、ミューテックスロック３０８を保持している間に停止したプロセスを、オペレーティングシステムがいかに扱うかを示すフローチャートである。図示したフローチャートでは、オペレーティングシステム１２０は先ず、プロセス１２２が停止したとの通告を受け取る（工程４０２）。オペレーティングシステム１２０は、プロセス状態３０２内のロックレジストリ３０６を検証して、ミューテックスロック３０８の保持中にプロセス１２２が停止したかどうかを判定する（工程４０４）。そうである場合は、オペレーティングシステム１２０は、ミューテックスロック３０８をマークし、ミューテックスロック３０８の保持中に先行プロセスが停止したことを示し、図３のロックフラグのマークを外すことにより、ミューテックスロック３０８のロックを解除する。これにより、後続プロセスはミューテックスロック３０８を獲得でき、ミューテックスロック３０８の保持中にプロセス１２２が停止したことを判定できる。
【００４６】
オペレーティングシステム１２０は、図３の一貫性フラグ３１２を非一貫性の状態に設定することにより、ミューテックスロック３０８の保持中に先行プロセスが停止したことを示し得ることに留意されたい。あるいは、一貫性フラグ３１２は、ミューテックスロック３０８により保護される状態を修正する前にミューテックスロック３０８を獲得したプロセスにより設定され得る。このプロセスは、ミューテックスロック３０８により保護される状態を修正し終えた後で、一貫性フラグ３１２を解除する。
【００４７】
図５は、本発明の実施形態により、ロバストなロックがいかに使用されるかを示すフローチャートである。先ず、図１のプロセス１２２などのプロセスが、図３のミューテックスロック３０８などのロックを獲得しようとして、機能呼び出しを行う（工程５０２）。機能呼び出しは、ロックフラグ３１０を検証し、別のプロセスが現時点においてミューテックスロック３０８を保持しているかどうかを判定する。別のプロセスが現時点においてミューテックスロック３０８を保持している場合、プロセス１２２は、ミューテックスロック３０８上でブロックする。他のプロセスが最終的にミューテックスロック３０８を解除したとき、プロセス１２２は、ロックフラグ３１０をマークすることによりミューテックスロック３０８を獲得し、機能呼び出しが戻ってくる。
【００４８】
機能呼び出しがエラー値を伴わずに戻ってきた場合、システムは、ミューテックスロック３０８により保護されるプログラム状態で要求された作業を行う（工程５１４）。要求された作業が実行された後で、システムは、ロックフラグ３１０のマークを外すことにより、ミューテックスロック３０８を解除するので、別のプロセスがミューテックスロック３０８を獲得できる。
【００４９】
機能呼び出しが、「所有者停止」または「ロックがマップされず」とマークされて戻ってきた場合、このプロセスは、ミューテックスロック３０８を保持する別のプロセスが停止したかミューテックスロック３０８から分離したことを知り、ミューテックスロック３０８により保護されるプログラム状態は、非一貫性状態に置かれ得る。この場合、プロセス１２２は、ミューテックスロック３０８により保護されるプログラム状態を一貫させようと試みる（工程５０４）。プロセス１２２がプログラム状態を一貫できた場合、ミューテックスロック３０８を初期化し、次にミューテックスロック３０８を解除する。プロセス１２２がプログラム状態の一貫に成功しなかった場合、（図３の回復性インジケータ３１４を設定することにより）ミューテックスロック３０８を回復不能とマークするので、後続するプロセスは、プロセス１２２がプログラム状態を一貫させることに失敗したのを知る（工程５０８）。さらに、プロセス１２２は、ロックフラグ３１０のマークを外し、ミューテックスロック３０８を解除する。これにより、他のプロセスはミューテックスロック３０８を獲得できる。また、プロセス１２２は、ミューテックスロック３０８を待つプロセスを起動させる。
【００５０】
機能呼び出しが、「回復不能」とマークされて戻ってきた（即ち、図３の回復性インジケータ３１４がマークされた）場合、プロセス１２２は、先行プロセスが既に、ミューテックスロック３０８により保護されるプログラム状態を一貫させようと試みたことを知る。プロセス１２２は、例えば、プログラム状態を生成するのに先ず必要とされたプログラム動作を反復するか、あるいは最初からプログラムを再起動するかにより、非一貫したプログラム状態に対処しようとする（工程５１０）。このタスクが完了したとき、プロセス１２２は、ミューテックスロック３０８を破棄し（工程５１２）、ミューテックスロック３０８を再初期化するので、別のプロセスはミューテックスロック３０８（工程５１２）を獲得することができる。
【００５１】
ロバストロックの使用例
表１Ａおよび１Ｂは、ロバストロックの１実施形態がいかに使用されるかの、Ｃプログラミング言語による一例を示す。メインプログラムの第１の部分（表１Ａ）はミューテックスロックを初期化する。メインプログラムの第２の部分（表１Ｂ）は「スイッチ」ステートメントを介して周期する（cycle）ループを含む。このスイッチステートメントは、図５のフローチャートの３分岐に対応する、「所有者停止」「回復不能」および「ノーエラー」の３つの場合を取り扱う。
【００５２】
【表１】
0004327972.tif 000002
【００５３】
【表２】
0004327972.tif 000003
【００５４】
本発明の１実施形態は、相互排除目的に用いられるロックを保持する先行プロセスが、該ロックの所有権を喪失した場合に、回復をサポートするシステムを提供する。この所有権の喪失は、先行プロセスが停止するか、またはロックがマッピングされないことによって発生する。本発明によれば、プロセスは先ずロックの獲得を試みる。ロックを保持していた先行プロセスがロックの所有権を喪失したことを示すエラーを伴って、ロックを獲得する試みが戻ってきた場合に、そのプロセスは、ロックにより保護されるプログラム状態を一貫させることを試みる。プログラム状態を一貫させる試みが成功した場合、システムはこのロックを再初期化し解除する。そうでない場合、システムは、このロックを回復不能とマークするので、このロックを獲得しようと試みる後続プロセスは、このロックが回復不能であることを通告される。本発明の１局面では、オペレーティングシステムにおいて、プロセスが停止したことの通告を受け取り、ロックの保持中においてこのプロセスが停止したかどうかを判定することを含む。ロックの保持中にプロセスが停止した場合、システムは、このロックの後続獲得に対し、ロックの先行保持が停止したことを示すようロックをマークし、このロックを解除して、他のプロセスがこのロックを獲得し得るようにする。本発明の１局面では、このロックが回復不能であることを示すエラーを伴って、ロックを獲得する試みが戻ってきた場合、このプロセスは、一貫していないプログラム状態に対処する動作を実行し、このロックを再初期化する。
【００５５】
本発明の実施形態の上述した記載は、例示および説明の目的でのみ示した。これらは本発明を開示された形にて網羅し、または限定するものではない。従って、開示される実施形態の様々な修正および変更は、当業者には明白である。さらに、上記開示は、本発明を限定することを意図していない。本発明の範囲は添付の特許請求の範囲により規定される。
【００５６】
【発明の効果】
本発明によれば、ロックを保持しているプロセスが失敗しても他のプロセスがハングしないロバストな回復可能ロックが提供され、これにより、他のプロセスが、そのロックにより保護されていた状態を一貫した状態に回復できるようになる。
【図面の簡単な説明】
【図１】本発明の実施形態により、複数のプロセスを実行可能なコンピュータシステムを示す図である。
【図２】本発明の実施形態によるオペレーティングシステムの内部構造の部分を示す図である。
【図３】本発明の実施形態により、ロバストなロックを適用することに関連するデータ構造のいくつかを示す図である。
【図４】本発明の実施形態により、ロックを保持している間に停止するプロセスを、オペレーティングシステムがいかに扱うかを示すフローチャートである。
【図５】本発明の実施形態により、ロバストなロックがいかに使用されるかを示すフローチャートである。
【符号の説明】
１０２  ＣＰＵ
１０４  メモリ
１０６  バス
１０８  ディスク
１１０  ＮＩＣ
１１２  ディスプレイ
１１３  ネットワーク
１１４  キーボード
１２０  オペレーティングシステム
１２２  プロセス
１２４  プロセス
１２６  プロセス
１２８  共有メモリ
１３０  ミューテックスロック
２０２  デバイスドライバ
２０４  スケジューラ
２０６  カーネルスレッド
２０７  ライトウエイトプロセススレッド
２０８  ユーザスレッド
３０２  プロセス状態
３０４  オープンファイル
３０６  ロックレジストリ
３０８  ミューテックスロック
３１０  ロックフラグ
３１２  一貫性フラグ
３１４  回復性インジケータ
３１６  ロック型
【図１】
0004327972.tif 000004
【図２】
0004327972.tif 000005
【図３】
0004327972.tif 000006
【図４】
0004327972.tif 000007
【図５】
0004327972.tif 000008