(57)【特許請求の範囲】
【請求項１】
分散され相互接続された複数のプロセッサを有し、該複数のプロセッサのそれぞれがメモリを有している分散形データ処理システムのプロセスに対して信号の送出を順序付ける方法であって：
前記複数のプロセッサを順序付けし；
汎用ロックを保守する制御プロセッサとして前記複数のプロセッサの一つを設定し；
プロセスのあるグループであって、該プロセスのグループの各サブグループが前記プロセッサの各々に存在するようなプロセスのグループを形成し；
前記複数のプロセッサ中の第１のシグナリングプロセッサが、前記プロセスのグループにおける各プロセスへ送出する第１の信号を生成し；
前記複数のプロセッサ中の第２のシグナリングプロセッサが、前記プロセスのグループにおける各プロセスへ送出する第２の信号を生成し；
前記第１の信号の生成の段階の後で、前記第１のシグナリングプロセッサが、前記制御プロセッサに前記汎用ロックを要求し；
前記要求の段階の後で、前記第２のシグナリングプロセッサが、前記制御プロセッサに前記汎用ロックを要求し；
前記第１のシグナルプロセッサによる要求の段階の後で、どのプロセッサも汎用ロックを有していないときには、前記制御プロセッサは、前記第１のシグナリングプロセッサが前記汎用ロックを有するということを前記第１のシグナリングプロセッサに肯定応答し；
前記第２のシグナルプロセッサによる要求の段階の後で、前記第１のシグナリングプロセッサが汎用ロックを有しているときには、前記制御プロセッサは、前記第２のシグナリングプロセッサが前記汎用ロックを有するということを前記第２のシグナリングプロセッサに肯定応答することを失敗し；
前記肯定応答の段階の後で、前記第１のシグナリングプロセッサは、前記第１の信号を前記複数のプロセッサのそれぞれに順番に送信し；
前記肯定応答することを失敗する段階の後で、前記第２のシグナリングプロセッサは、前記複数のプロセッサのいずれにも前記第２の信号を送ることを抑制し；
前記送信する段階の後で、前記第１のシグナリングプロセッサは、前記制御プロセッサに前記汎用ロックを放棄し；
前記複数のプロセッサの各々は、前記第２の信号を各プロセスに送出する前に、前記第１の信号を受信して、前記第１の信号を前記プロセスの各サブグループにおける各プロセスに送出する段階を具備することを特徴とする方法。
【請求項２】
前記第１及び第２のシグナリングプロセッサは、同じプロセッサであることを特徴とする請求の範囲第１項に記載の方法。
【請求項３】
前記肯定応答の段階が完了する前に前記第１のシグナリングプロセッサが故障した場合には、前記第２の信号を送出する手順を継続し；かつ
肯定応答の段階が完了した後であるが前記送信する段階が完了する前に前記第１のシグナリングプロセッサが故障した場合には、前記制御プロセッサが、前記第１のシグナリングプロセッサによる前記汎用ロック要求時に受信した信号により、第１のシグナリングプロセッサに代わって前記信号を送信する段階を更に具備することを特徴とする請求の範囲第１項に記載の方法。
【請求項４】
前記送信する段階は、前記第１のシグナリングプロセッサ以外の前記複数のプロセッサの一つが故障した場合に前記信号を前記複数のプロセッサの各残っているものに送信することを具備することを特徴とする請求の範囲第１項に記載の方法。
【請求項５】
前記第１の信号を送出する段階は、前記複数のプロセッサのうちの第１のプロセッサに存在する前記プロセスの第１のサブグループに属する個々のプロセスに対する送出と、前記複数のプロセッサのうちの第２のプロセッサに存在する前記プロセスの第２のサブグループに属する個々のプロセスに対する送出とが非同期に行われることを特徴とする請求の範囲第１項に記載の方法。
【請求項６】
前記第１の信号を送出する段階は、前記複数のプロセッサのうちの第１のプロセッサに存在する前記プロセスの第１のサブグループに属する個々のプロセスに対する送出と、前記複数のプロセッサのうちの残りのプロセッサに存在する前記プロセスの他のサブグループに属する個々のプロセスに対する送出とが非同期に行われることを特徴とする請求の範囲第１項に記載の方法。
【請求項７】
前記肯定応答することを失敗する段階の後でかつ前記第２の信号を送出する段階の前に、以下の段階が実行される：
第２のシグナリングプロセッサが、前記制御プロセッサに前記汎用ロックを遅らせて要求し；
前記第１のシグナリングプロセッサにより前記汎用ロックが放棄され、どのプロセッサも汎用ロックを有していないときには、前記制御プロセッサは、前記第２のシグナリングプロセッサが前記汎用ロックを有することを前記第２のシグナリングプロセッサに肯定応答し；
前記肯定応答の段階の後で、前記第２のシグナリングプロセッサは、前記第２の信号を前記複数のプロセッサのうちの最初のものから順に送信することを特徴とする請求の範囲第１項に記載の方法。
【請求項８】
以下の段階を更に具備する：
前記制御プロセッサとして連続して前記複数のプロセッサを順序付けし；
連続の順番の第１のものを前記制御プロセッサとして選択し；
前記制御プロセッサが故障した場合に該制御プロセッサを連続の順番の次のプロセッサで置換えることを特徴とする請求の範囲第１項に記載の方法。
【発明の詳細な説明】
【０００１】
【技術分野】
本発明は、プロセス間シグナリングに係るものである。以下に説明する、ある一定のプロセス間オペレーションの理解は、本発明を理解するために必要である。例としてＵＮＩＸTMを取り入れる。
【０００２】
【背景技術】
近年は、ＵＮＩＸTMオペレーティング・システムの市場人気における重要な上昇が見られる。ＵＮＩＸTMは、コンピュータ・サイエンティスト、コンピュータ・サイエンスの学生及び他の非常に技術的に熟練したコンピュータ・ユーザによってのみ最初は好まれていたが、市場プログラミング環境としてのＵＮＩＸTMに対するプリファレンス（優位）は、それらの学生がワークフォースの中に入会しかつそれらと共に彼らの開発したプリファレンスをキャリーするので大きく成長している。従って、それは、その所有権を主張できるハードウェアと一緒にＵＮＩＸTMまたはＵＮＩＸTMライク・プログラミング環境を供給することがコンピュータ製造業者の義務である。
【０００３】
しかしながら、ＵＮＩＸTMは、歴史的にユニプロセッサに対するオペレーティング・システムであった：最初は、ディジタル・イクイップメント・コーポレーションのＰＤＰ−１１、後にメインフレーム、そしてさらに後でマイクロコンピュータの人気急騰に伴うマイクロプロセッサ。今日でさえ、ひと握りのＵＮＩＸTM多重プロセッサ・インプリメンテーションが存在するだけである。この発明の出願人である、タンデム・コンピュータ・インコーポレーティッドは、製品名NonStop Kernel Software（“ＮＳＫ”），release D30.00で一つのそのような多重プロセッサ・インプリメンテーションを市販すべく準備している。ＮＳＫのＵＮＩＸTMライク部分は、Open System Services、略して“ＯＳＳ”と呼ばれる。
ＵＮＩＸTMでは、“プロセス”は、プログラムのダイナミック、ランータイム・エンボディメント（具体化）である。プログラムは、ディスクまたはテープのような記憶媒体の静的状態に一般に存在し、プロセスは、メモリにロードされかつ実行する。ＵＮＩＸTMは、マルチタスキング・オペレーティング・システムである：多くのプロセスは、本質的に同時に実行することができる。
【０００４】
ＵＮＩＸTMでは、プロセスは、ｆｏｒｋ（）システム・コールを実行することによって別のプロセスを生成することができる。ｆｏｒｋ（）システム・コールの結果は、とりわけ、それがそれ自体の固有なプロセス識別番号を有することを除き、古いプロセスのコピーである新しいプロセスの生成である。それ自体のコピーを生成するプロセスのこの手順は、“フォーキング(forking)”と呼ばれる。
プロセスは、また、“exec”もできる、即ち、プロセスは、−−再び一般的にディスクまたはテープから−−新しいプログラムに読み込み、この新しいプログラムでその古いプログラムをオーバレイし、かつ始めから新しいプログラムを実行することによって、それが走らせているプログラム・コードを変更することができる。プロセスは、ｅｘｅｃ（）システム・コールを呼び出すことによってこれを達成することができる。
【０００５】
フォーキングでは、より古いプロセスは、“親”と呼ばれかつより新しいプロセスは、“子”と呼ばれる。勿論、親は、多くの子を持つことができ、子は、一つの親だけを有する。しかしながら、ＵＮＩＸTMは、プロセス・グループ関係のような、他のプロセス間関係をプロセスに保守させる。各プロセスは、プロセス・グループのメンバーである。プロセスのデフォルト・プロセス・グループは、その親のプロセス・グループである。プロセスは、適切なシステム・コール、一般にsetpgid()を実行することによってそのプロセス・グループを変更することができる。従って、子プロセスは、その親と同じプロセス・グループまたはある他のプロセス・グループにあることを選ぶことができる。プロセス・グループは、メンバーとして一つ以上のプロセスを有しうる。
【０００６】
システム内の事象の発生が複数のプロセスに通信される必要がありうるので、プロセス・グループ・メンバーシップは、重要である。プロセス・グループは、事象が通知されるべきである全てのプロセスを識別することができる。標準的例をとるために、ユーザがＵＮＩＸシステムにログすると想定する。それによりユーザがシステムと最初に通信する“ログイン(login)”プロセスは、プロセス・グループを有する。ログイン・プロセスは、ユーザがシェル・コマンド及びプログラムを実行できるようにすべくコマンド・インタープリタ（“シェル(shell)”）をexecs（実行）する。プログラムを実行しているシェルは、フォーキングを必然的に伴いそして上記したようにプログラムを実行する。それゆえに、新しく実行されたプログラムは、シェル、その親と同じプロセス・グループを有する。事実、シェルによって実行されたプログラム、その子、その孫、等は、デフォルトによって同じプロセス・グループを有する。ここで、ユーザとシェルの間の通信回線が、意図的にまたはそれ以外で、壊れたならば、好ましいアクションは、シェル及び祖先としてシェルを有する各プロセスに対してその事象を知らせかつそれ自体を終了することである。（プロセスの終了は、“エキジッティング（出る(exiting)）”と呼ばれる。エキジッティングは、exit()システム・コールを呼び出す結果として生じる。）
【０００７】
非同期事象のプロセスを知らせるためのＵＮＩＸTMの機構は、シグナリング(signalling)と呼ばれる。プロセスは、kill()システム・コールを用いて、相互の信号を送ることができる。オペレーティング・システムそれ自体は、プロセスへ信号を送りうる。プロセスまたはオペレーティング・システムは、プロセス・グループに信号を送りうる。信号を送ることは、シグナリングと呼ばれる。
上記から、ＵＮＩＸTMの従来のマルチ−スレッディング・パラダイムは、例えば、フォーキング及びエキジスティングを介してプロセス間関係の本質的に非同期な変更を許容する。しかしながら、そのような非同期プロセス間関係変更で、問題が生じ、どのようにＵＮＩＸTMオペレーティング・システムがプロセス間関係のアトミック及び順序付けられた変更を保証するのか？
【０００８】
また、上記から明らかなことは、ＵＮＩＸTMの従来のマルチ−スレッディング・パラダイムは、シグナリングが生じている間にプロセス間関係の非同期変更を許容するということである。例えば、どのようにシステムは、フォーキングの存在において信号のアトミック、順序付けられた送付を保証するのか？シグナリング問題の特定の例は、セクションＢ．３．１．１にで、以下に説明した、ＰＯＳＩＸにおいて与えられる。
歴史的信号−プロセッサＵＮＩＸTMインプリメンテーションでは、プロセス間関係変更及びシグナリングの非同期性は、アトミック性及び順序付けに関して重要な問題を与えなかった。プロセス間関係を変更すべき呼出しのインプリメンテーションは、基礎を成しているカーネルへの無停止可能な（少なくとも重要なステージにおいて）アクセスを含みうる。それゆえに、プロセス間関係を変更することを望んでいる別のプロセスがロックアウトされる間に、プロセス間関係変更は、一つのプロセスのために実行することができる。
【０００９】
同様に、kill()への呼出しは、カ−ネルを通過する単一のパスを結果として生じ、カーネルは、一つのプロセスのために信号を生成しかつシグナルされたプロセス・グループの全てのプロセスにその信号を実質的に同時に送付する。カーネルがシグナリングのメカニクスを実行している間に、それは、プロセス・グループ・メンバーシップを同時に変更しうるあらゆるプロセスを実行から排除することができる。
プロセス間関係のアトミック及び順序付け変更と信号のアトミック、順序付け送付の問題は、ＵＮＩＸTMの多重プロセッサ・インプリメンテーションにおいてそれ以上に至難である。また、多重プロセッサ環境は、信頼性の問題を生起する：どのように多重プロセッサ・システムは、故障しているプロセッサの存在において一貫的プロセス間関係を保証するのか？どのように多重プロセッサは、プロセスが故障の場合に信号の信頼送付を保証するのか？アトミック性、順序付け及び信頼性問題の至難性を増大する−−少なくとも非共有メモリ・多重プロセッサ−−多重プロセッサ・システムの事実の一つは、プロセス・グループのプロセスが二つ以上のプロセッサにわたり分散することができかつ通常分散される。カーネルが単一−スレッディングによる可能なタイミング・コンフリクトを解消することのユニプロセッサ解決策は、多重プロセッサ環境では利用不能である：非同期的に動作している、複数のカーネルがあり、各カーネルには、それぞれが非同期で走っている複数のプロセスがある。独立して作用することにより、各プロセッサは、そのプロセッサにおいてプロセス間関係の信頼かつ順序付けられた変更だけを保証することができる。例えば、第１のプロセッサにおいて、第１のプロセスは、プロセス・グループへの送付のための信号を生成することでありうる。プロセス・グループは、第１のプロセス及び第２のプロセッサにおける第２のプロセスを含んでいるプロセスを有する。第１のプロセスがプロセス・グループに対する信号を生成していると同時に、第２のプロセスは、制限された時間に対してそのプロセス・グループのメンバーでもありそしてそのプロセス・グループ・メンバーシップを変更しうる、第３のプロセスをフォーキングする。第３のプロセスが第１のプロセスによって生成された信号を受け取るか否か？それゆえに、単に、ユニプロセッサ・システムのよりパワフルまたはより高速なバージョンである多重プロセッサ・システムのより望ましいパラダイムは、分解し始める。これらのアトミック性、順序付け、及び信頼問題の解決なしに、多重プロセッサ・システムは、シグナリングをインプリメントしているユニプロセッサＵＮＩＸTMシステムと同じサービスを提供できない。特に、多重プロセッサ・システムは、ＰＯＳＩＸに詳述されたフル・システム・サービスを提供できない。
事実、問題は、多重プロセッサ・システムでは、そのようなハードウェア・ベンダに解法なしでソフトウェア製品を供給させるように至難であった。
【００１０】
ＬＯＣＵＳ  ＴＮＣ，ＭＡＣＨ，ＯＳＦ１，及びＩＳＩＳインプリメンテーションは、次いで以下に説明される。Ｌｏｃｕｓは、ＬＯＣＵＳ  ＴＮＣと呼ばれる製品を有する。ＬＯＣＵＳ  ＴＮＣは、“ｖｐｒｏｃ”アブストラクション（抽象）に基づきＵＮＩＸTM分散型システムをインプリメントする。ｖｐｒｏｃは、プロセスだけを参照するデータ構造である。単一ｖｐｒｏｃのコピーは、多くのプロセッサに装着されたメモリに存在しうる。“owning（所有している）”または“master（マスター）”プロセッサは、非参照（non-referring）データ構造で実際のプロセスを記述する。概観レベルで、ｖｐｒｏｃアブストラクションは、ｖｐｒｏｃを有するプロセッサをマスター・コピーでアウトーオブーステップにさせ、かつローカル・コピーは、あるオペレーションに対して用いられる。それゆえに、システムは、マスター・プロセッサと変更ｖｐｒｏｒプロセッサ間のあるメッセージの費用をセーブする。ＬＯＣＵＳ  ＴＮＣは、上述したようなアトミック性、順序付け及び信頼性条件を正しく扱わない。ニューヨーク州、アーモンクのインターナショナル・ビジネス・マシン(International Business Machines)から入手可能なＭＡＣＨ、及びマサチューセッツ州、ケンブリッジのオープン・ソフトウェア・ファンデーション(Open Software Foundation)から入手可能なＯＳＦ１は、また、多重プロセッサＵＮＩＸTMインプリメンテーションである。ＭＡＣＨ／ＯＳＦ１解法は、“ＵＮＩＸTMサーバ”、プロセス関係を保守する単一の、マルチ−スレッディド・プロセスを含む。このプロセスは、分散されない。単一のコピーだけが存在する。それゆえに、ここで説明した分散型アルゴリズムをアドレスしない。
ＩＳＩＳは、メッセージ順序付け及びプロセス・グループ・メンバーシップに対する同様な問題の組を解決する−−しかし“プロセス・グループ”の異なる定義を用いてかつシグナリングに対してではなく。ＩＳＩＳは、ＵＮＩＸTM−ライク・セマンティクをインプリメントすることを試みない。
【００１１】
【発明の開示】
プロセス間関係のアトミック、順序付け及び信頼変更の知られたインプリメンテーションまたは分散型プロセッサ・システムにおける、特に共有メモリなしの多重プロセッサ・システムにおける信号送付が全くない。実際、ＯＳＳを有するＮＳＫのペンディング・リリースの前に、タンデム・コンピュータズ・インコーポレーティッドは、そのＵＮＩＸTM−ライク・オペレーティング・システム・ソフトウェアにおけるような特徴を提供しなかった。
祖先及びプロセス・グループ・メンバーシップと一緒に、別のＵＮＩＸTMプロセス間関係は、“セッション(session)”である。セッションは、プロセス・グループのコレクションであり、ユーザにプロセスの実行を選択的に中止させかつそれらの実行を後の地点で再開させる。各プロセス・グループは、セッションのメンバーであり、かつプロセスは、そのプロセス・グループがメンバーであるセッションのメンバーである。
ＵＮＩＸTMに他のプロセス間関係が存在し、示した３つは、単に主要なものである。しかしながら、ある一定のＵＮＩＸTM機能が個々のプロセスまたはプロセス・グループ、セッションまたは他のプロセス間関係で動作するということを説明すべく主要なもので充分である。多重プロセッサ環境では、これらのプロセス間関係を操作（処理）している同時、非同期オペレーションは、種々のプロセッサのプロセスが分散型データ構造を変更するときに多数のレース条件を生成することができる。
【００１２】
従って、本発明の一つの目的は、特に、プロセス形成、プロセスグループ変更およびプロセス終了の如きオペレーションの結果としてプロセスグループメンバーシップがそうしないと変更してしまうようなときに、そのプロセスグループに到着する信号がそのプロセスグループのある一貫した状態でそうするようなＵＮＩＸTM−ライク・シグナリング機能の信頼できるインプリメンテーションにある。
本発明のもう一つ別の目的は、多重プロセスがあるプロセスグループへプロセスグループ信号を送るときに、個々の各シグナラーからの信号のすべてが、他のすべてのシグナラーによって送られる信号よりも、完全に前に、または、完全に後に、そのプロセスグループのすべてのメンバーに到達するようにするＵＮＩＸTM−ライク・シグナリング機能の信頼できるインプリメンテーションにある。そのプロセスグループの各メンバーは、同じ順序で入力される信号を見る。
本発明のさらに別の目的は、もし、シグナリングプロセッサが存在するプロセッサがそのシグナリング動作中に故障する場合において、そのシグナリング動作が完全に故障してしまってそれら信号が生存プロセスへと全く送出されないか、または、そのシグナリング動作が完了してその信号がすべての生存プロセスグループメンバーへと送出されるようにする共有メモリを有していない多重プロセッサシステムにおいてＵＮＩＸTM−ライク・シグナリング機能の信頼できるインプリメンテーションにある。
本発明のさらにもう一つ別の目的は、プロセッサの一つまたはそれ以上が多重プロセッサにまたがるプロセスグループに対するシグナリング動作中に故障する場合において、その信号がそのプロセスグループのすべての生存メンバーに到達するようにする多重プロセッサシステムにおいてＵＮＩＸTM−ライク・シグナリング機能の信頼できるインプリメンテーションにある。
本発明のこれらの目的および他の目的は、以下の説明から容易に明らかとなろう。
【００１３】
ＵＮＩＸTM−ライク・オペレーティングシステムの多重プロセッサインプリメンテーションについて以下説明するが、この場合においては、もう一つ別のプロセスにシグナリングしたいどのプロセスも、制御プロセッサによって維持されるプロセッサ間ロックのためのアービトレーションに入らねばならない。
所望のプロセッサがそのプロセッサ間ロックを得るのに成功する場合には、そのプロセッサは、その時に、所定のシーケンスにて、その信号を各プロセッサに知らせる。それから、その所望のプロセッサは、プロセッサ間ロックを解除する。
所望のプロセッサがプロセッサ間ロックを得るのに失敗する場合には、その望んでいるプロセッサは、再びアービトレーションに入る前に遅延する。典型的には、その所望のプロセッサは、アービトレーションに再び入る待機中にプロセッサ間ロックを必要としないようなプロセスを行う。
信号が配分される各プロセッサは、その信号を、そのプロセッサに関する適当なプロセスが存在する場合には、そのプロセスへと送出する。
各受信プロセッサは、一度それが入力変更信号を受け取ったならば、他のプロセッサから非同期的に動作する。各受信プロセッサのプリまたはポスト信号動作は、他のプロセッサの動作と協調する必要がなく、協調されていない。
【００１４】
プロセッサ間ロックを獲得しなかったシグナリングプロセッサの失敗で、特定の分散データ構造の一貫性を確保するために回復する必要はない。プロセッサ間ロックを獲得したシグナリングプロセッサの故障時において、制御プロセッサは、受信プロセッサのすべてにその信号を知らせる機能を引き継ぐ。
制御プロセッサの故障時において、生存プロセッサは、どの生存プロセッサが制御プロセッサとして成功するかを決定すべく所定の手順に従う。
【００１５】
【発明を実施するための最良の形態】
図１は、プロセッサ２ａ、２ｂ、...、２ｎを有している多重プロセッサ・システムを示す。Ｎは、１６より大きいかまたは小さいであろうが、Ｎは、一般に１６である。各プロセッサ２は、対応メモリ３に結合される。
各プロセッサ２は、オペレーティング・システム・ソフトウェアを走らせる。好ましい実施例では、プロセッサ２は、全て同じオペレーティング・システム・ソフトウェアを走らせる。基礎を成しているオペレーティング・システムＧは、タンデム・コンピュータズ・インコーポレーティッドから入手可能な、Guardian（ガーディアン）であり、オーバレイング(overlaying)オペレーティング・システムは、Portable Operating System Interface, Part I（ここで参考文献として採り入れられる、“POSIX”, International Standard ISO/IEC 9945-1: 1990; IEEE Std 1003.1-1990）のインプリメンテーションである、ＯＳＳを有するＮＳＫである。ここでＯＳＳは、ＵＮＩＸTMの変形であると考えられる。
ＵＮＩＸTMを走らせる結果として、各プロセッサ２は、プロセスＰを有する。ＵＮＩＸTMシステムにおけるパラダイムのように、プロセスは子をフォークし、子は次いでフォークし、それら自信の子を生成する、等。多重プロセッサ・システム１の好ましい実施例では、プロセッサ２ａのプロセスは、２ａまたはプロセッサ２ｂ、...、２ｎの一つで走らせることができる子を生成することができる。
【００１６】
図２は、時間ｔ０における多重プロセッサ・システム１のプロセスを示す。プロセッサ２ａ、２ｂ及び２ｃは、それらの対応プロセス表ＰＴ４ａ、ＰＴ４ｂ、ＰＴ４ｃによって表される。プロセス表ＰＴ４ｃは、プロセス間関係分散型データ構造の例である。プロセス表は、ＵＮＩＸTMプロセス関係を定義する累積表である。プロセス表は、各プロセッサのエクスタント・プロセスが存在するようなシステム資源である。
プロセスＰ１００は、プロセッサ２ａに存在（Ｒ）する。プロセスＰ１００は、プロセッサ２ａに存在しない（〜Ｒ）がプロセス２ｂに存在している、プロセスＰ１１０の親である。プロセスＰ１１０は、次いで、プロセッサ２ｃのプロセスＰ１１１の親である。プロセスＰ１００のプロセス・グループは、プロセス・グループＧ１である。上記したように、プロセスＰ１１０のプロセス・グループは、デフォルトによりその親、プロセスＰ１００のプロセス・グループである。同様に、プロセスＰ１１１のプロセス・グループは、その親、Ｐ１１０のプロセス・グループである。プロセスＰ１００、Ｐ１１０、及びＰ１１１のそれぞれは、プロセス・グループＧ１にある。
【００１７】
以下に説明する複数のシナリオを考える。第１のシナリオは、図３に示される。図３は、時間ｔ１における多重プロセッサ・システムに存在しているプロセスのサブセットを示す。時間ｔ１、ｔ１＞ｔ０、において、プロセスＰ１００は、第２の子、プロセスＰ１２０を生んだ。プロセスＰ１２０は、その親、プロセスＰ１００のプロセス・グループで生まれる。
第２のシナリオは、図４に示される。図４は、時間ｔ２、ｔ２＞ｔ１＞ｔ０、において、プロセスＰ１１１は、そのプロセス・グループ・メンバーシップＧ１からＧ２に変更することを選んだ。従って、時間ｔ２におけるプロセス・グループＧ１は、プロセスＰ１００、Ｐ１１０及びＰ１２０を含む。プロセス・グループＧ２は、プロセスＰ１１１だけを含む。
ＵＮＩＸTMシステムにおいて一般的であるように、プロセスＰ１１０は、そのプロセス・グループＧにおける各プロセスＰに信号を送ることを欲するであろう。Ｐ１１１がそのプロセス・グループ・メンバーシップを変更している間にプロセスＰ１１０が時間ｔ２で信号を送るならば、プロセスＰ１１１が信号を受信するかどうかという不確定性が存在する。kill()またはsetpgid()がレースに勝つかどうかにより、信号は、プロセスＰ１００、Ｐ１１０、Ｐ１１１及びＰ１２０に送付されるかまたはプロセスＰ１００、Ｐ１１０及びＰ１２０にだけ送付される。プロセスＰ１１１は、信号を受信するかまたは受信しないであろう。
この非決定性のソースは、受信プロセス２ｃは、シグナリング・プロセッサ２ｂと独立に動作しているということである。プロセッサ２ｂ及び２ｃは、同じオペレーションを実行していないけれども、プロセッサ２ｃがsetpgid()を実行すると同時に、プロセッサ２ｂは、signal()を実行し、両方のオペレーションにおいて影響を及ぼされる基礎を成しているデータ構造は、プロセス表、ＰＴである。そのコピーは、各プロセッサ２のメモリ３に保守される。
【００１８】
競合機能が両方ともプロセス間関係変更である場合にもレース条件が生ずる。例えば、setpigd()は、その子がexec()コールをまだ実行していないならばターゲット子プロセスで作動すべく定義される。子がexec()コールを発行すると同時にsetpigd()コールが発行されると想定する。まずexecが生ずる（かつsetpigd()が失敗する）ようにすべきか、またはsetpigd()がまず生じそしてexec()が設置された新しいグループ−ｉｄを伴って後で生ずるかのいずれかである。
米国特許公報第４，７１８，００２号(１９８８)では、カー(Carr)は、システム１のような多重プロセッサ・システムにおけるプロセッサ中の更新された情報を通信する方法、汎用更新手順（“ＧＬＵＰＰ”）を記述している。カーは、多重故障のシステム・トレラントを生成することによってその従来技術のシングル−フォールト・トレラント・システムを改良することを考えた。
【００１９】
ＧＬＵＰＰは、以下にざっと説明する。ＧＬＵＰＰは、プロセッサ２を二重に順序付ける。第１の順序付けは、プロセッサ２が汎用更新メッセージを受け取るような合意によって定められかつ一般に知られたシーケンスである。第２の順序付けは、オリジナル制御プロセッサ（第２の順序付けにおける第１のプロセッサ）が故障（失敗）したならば、制御プロセッサとして合意によって定められかつ一般に知られたプロセッサの継承である。二つのＧＬＵＰＰ順序付けのそれぞれは、実際にループである。
ある一定の分散型、クリティカル・データ構造は、汎用更新ロック（“ＧＬＵＰＰ  ｌｏｃｋ”）によって保護される。そのような分散型、クリティカル・データ構造を変更することを望むプロセッサ２は、ＧＬＵＰＰ  ｌｏｃｋをまず獲得しなければならない。制御プロセッサは、ｌｏｃｋを保守する単独のプロセッサである；それは、ＧＬＵＰＰ  ｌｏｃｋの認可及び否認を調停する。
【００２０】
カーは、プロセッサ故障の脅威にもかかわらず分散型データ構造に対する更新を通信することに注意を注いでいるが、本発明は、プロセス間関係を変更する、非同期、競合プロセッサ及び、ほぼ同時にそのような関係及びシグナリングを変更する、非同期、競合プロセッサに固有なレース条件に注意を注いでいる。ＵＮＩＸTM−スタイル・プロセス間関係変更及びシグナリングをインプリメントすべく変更されるとき、そのプロセッサが別のプロセッサが同時発生的に変更しうるプロセス間関係を変更することを欲するならば、ＧＬＵＰＰは、プロセッサにＧＬＵＰＰ  ｌｏｃｋを獲得すべく要求する。ＧＬＵＰＰ  ｌｏｃｋは、また、シグナリングがそれに依存するプロセス・グルーピングに影響を及ぼすことができるオペレーションに対して獲得されなければならない。従って、別のプロセスへの送付のために信号を生成し、かつ分散型プロセス表ＰＴ４を従ってアクセスしなければならないプロセッサは、制御プロセッサからＧＬＵＰＰ  ｌｏｃｋをまず獲得しなければならない。即ち、上記例におけるシグナリング・プロセッサ２ｂは、プロセス・グループＧ１のプロセスＰに信号を送るためにＧＬＵＰＰｌｏｃｋを獲得しなければならない。（ＧＬＵＰＰ  ｌｏｃｋを獲得することにおいて、プロセス２は、ＧＬＵＰＰ  ｌｏｃｋの支援により送信すべき汎用更新メッセージのコピーを制御プロセスに送信する。制御プロセッサは、その汎用更新メッセージ・メモリに汎用更新メッセージのそのコピーを保守する。汎用更新メッセージ・メモリのこのコピーは、以下に説明するように用いられる。）
【００２１】
同様に、フォークすることを求めるプロセスは、制御プロセスからＧＬＵＰＰ  ｌｏｃｋをまず獲得しなければならない。フォーキングは、分散型プロセス表ＰＴ４へのアクセスを必要とする：プロセス表ＰＴ４は、ＵＮＩＸTMを走らせているシステム１におけるプロセスのレジデンスである。従って、プロセスＰ１１１は、時間ｔ２においてそのプロセス・グループ・メンバーシップを変更する前にＧＬＵＰＰ  ｌｏｃｋを獲得しなければならない。
上記に関する変更したＧＬＵＰＰの結果として、プロセス・グループＧ１のメンバーシップは、シグナリングの時に決定される。シグナリング・プロセッサ２ｂまたはグループ−チェンジング・プロセッサ２ｃのいずれかがまずＧＬＵＰＰ  ｌｏｃｋを獲得しなければならない−−それゆえに二つの他のものが待たなければならないので−−信号の送付は、因果的に順序付けられる。
【００２２】
従って、上記開示は、信号の送付が生じている間に他のプロセッサがグループ・メンバーシップを変更することを試みているときでさえも、信号がプロセス・グループのある一貫的状態でプロセス・グループに到着するようなＵＮＩＸTM−ライク・シグナリングのインプリメンテーションを記述する。プロセス・グループの一貫的状態は、シグナリング・プロセッサがＧＬＵＰＰ  ｌｏｃｋを獲得するときのプロセス・グループである。次いで他のプロセッサは、プロセス・グループをフォークし、変更することを試みるかさもなければプロセス・グループ・メンバーシップを変更することを試みるであろうが、しかしそのようにする前にＧＬＵＰＰ  ｌｏｃｋで待機する。ＧＬＵＰＰ  ｌｏｃｋは、シグナリング・プロセッサが分散型プロセス表へのその必要なアクセスを完了した場合にのみ再び利用可能になるであろう。グループ・メンバーシップ変更及び信号送付は、特定の順序で生ずることが保証され、かつその順序は、全てのプロセッサにおいて同じである。
【００２３】
この発明の変更された汎用更新手順では、シグナリング・プロセッサ・シグナリング・グループＧは、もしあれば、他の利用可能なプロセッサのプロセス・グループＧのメンバーシップである、プロセッサへ送付されるべき信号を全ての他の利用可能なプロセッサに通知しなければならない。一度シグナリング・プロセッサがＧＬＵＰＰ  ｌｏｃｋを獲得したならば、シグナリング・プロセッサは、上記した第１の順序付けによって特定された順番に各利用可能なプロセッサへのシグナリングを反映している汎用更新メッセージ・パケットを送る。それゆえに、時間ｔ３＞ｔ２でシグナリング・プロセスＰ１１０がプロセス・グループＧ１に信号Ｓ１及びＳ２を送ることを欲しておりかつシグナリング・プロセスＰ１１１がまたプロセス・グループＧ１に信号Ｓ３を送ることを欲している場合、プロセッサ２ｂまたは２ｃの一つがＧＬＵＰＰ  ｌｏｃｋを獲得するであろう。プロセッサ２ｃがＧＬＵＰＰ  ｌｏｃｋに対するアービトレーションに勝つと想定すると、プロセッサ２ｃは、受信プロセッサ２ａ、２ｂ、２ｃ、...、２ｎのそれぞれに通知する。プロセッサ２ｃは、汎用更新メッセージ順序付けで特定された順番にプロセッサに通知する。各プロセッサに送られた汎用更新メッセージは、信号Ｓ３を有するプロセス・グループＧのシグナリングを反映する。汎用更新手順が要求するように、各受信プロセッサは、汎用更新メッセージの肯定応答を送らなければならない。汎用更新メッセージ順序付けで一つの受信プロセッサからの肯定応答の受信で、シグナリング・プロセッサ２ｃは、汎用更新メッセージ順序付けで次のプロセッサに汎用更新メッセージを送る。退化の場合には、シグナリング・プロセッサ２ｃは、信号をそれ自体に通知する。非−故障の場合には、受信プロセッサ２の肯定応答は、そのプロセッサ２が、もしあれば、受信プロセッサ２のプロセス・グループＧ１における、順序付け各プロセスに汎用更新メッセージ・パケットで表された信号Ｓ３を送付したということを示す。受信プロセッサがプロセッサ２ａであれば、次いでプロセスＰ１００及びＰ１２０のそれぞれは、プロセッサ２ａがシグナリング・プロセッサ２ｃからの汎用更新メッセージを肯定応答するときにＳ３を受け取ったであろう。受信プロセッサがプロセッサ２ｃであれば、次いでプロセッサ２ｃの全てのプロセスは、プロセッサ２ｃがシグナリング・プロセッサ２ｃからの汎用更新メッセージを肯定応答するときに信号Ｓ３を受信しないであろう。
【００２４】
一度シグナリング・プロセッサ２ｃがプロセス・グループＧ１への信号Ｓ３の送付を表している汎用更新メッセージを分散したならば、プロセッサ２ｃは、ＧＬＵＰＰ  ｌｏｃｋを解放する。シグナリング・プロセッサ２ｂは、ここで、信号Ｓ１及びＳ２を送るためにロックに対してアービトレートする。同じ変更されたＧＬＵＰＰに続いて、シグナリング・プロセッサ２ｂは、プロセス・グループＧへの信号Ｓ１及びＳ２の送付を表している汎用更新メッセージの信号を送付する。
上に示したように、プロセス・グループＧ１を構成するプロセスＰ１００、Ｐ１１０及びＰ１２０のそれぞれは、まず信号Ｓ３を受信しついで信号Ｓ１及びＳ２を受信する。
従って、上記開示は、複数のシグナリング・プロセッサがプロセス・グループ信号をプロセス・グループＧに送る場合に、各シグナリング・プロセッサからの全ての信号は、全ての他のシグナリング・プロセッサによって送られたそれらの前または後のいずれかでプロセス・グループＧの全てのメンバーに到着するような、シグナリングのＵＮＩＸTM−ライク・インプリメンテーションを記述する。プロセス・グループ・メンバーは、同じ順番で同じ入力信号を常に見る。
変更したＧＬＵＰＰでは、制御プロセッサがプロセッサ２が失敗したということを決定する場合、制御プロセッサは、汎用更新がプロセッサにあったかどうか、即ち、ＧＬＵＰＰ  ｌｏｃｋがシグナリング・プロセッサによって獲得されたかどうかをチェックする。制御プロセッサは、ＧＬＵＰＰ  ｌｏｃｋがそのように獲得されていないならば、あらゆる回復を実行する必要がない。
【００２５】
しかしながら、ＧＬＵＰＰ  ｌｏｃｋが獲得されている場合、制御プロセッサは、各プロセッサに汎用更新メッセージの信号を送ることのタスクをそれ自体で引き請ける。制御プロセッサは、それが失敗した場合にシグナリング・プロセッサが送付していたシグナリング汎用更新メッセージをその汎用更新メッセージ・メモリから再構築する。次いで制御プロセッサは、結果としてシグナリング・プロセッサになり、汎用更新メッセージ順序付けにより、順次各プロセッサに信号汎用更新メッセージを送る。それゆえに、プロセッサ２ａが信号Ｓ１をプロセスＧ１に信号で知らせることを望みかつプロセッサ２ｄ（図示省略）が制御プロセッサであれば、プロセッサ２ａは、制御プロセッサ２ｄのＧＬＵＰＰ  ｌｏｃｋを要求する。要求の受け取りでかつ他のプロセッサが既にＧＬＵＰＰ  ｌｏｃｋを獲得していないならば、プロセッサ２ｄは、シグナリング汎用更新メッセージをその汎用更新メッセージ・メモリの中にコピーしかつそれがＧＬＵＰＰ  ｌｏｃｋを獲得したということをシグナリング・プロセッサ２ａに通知する。汎用更新メッセージ順序付けが２ａ、２ｂ、２ｃ、...、２ｎであると想定して、シグナリング・プロセッサ２ａは、それ自体にＳ１シグナリング汎用更新メッセージを送付し、それ自体に肯定応答する。シグナリング・プロセッサ２ａは、受信プロセッサ２ｂに汎用更新メッセージを次に送り、かつプロセッサ２ｂは、肯定応答する。再び、受信プロセッサ２ｃに対して、シグナリング・プロセッサ２ａは、汎用更新メッセージを送りかつ肯定応答を待つ。ここで、プロセッサ２ａが受信プロセッサ２ｃの肯定応答の受け取りの前に故障すると想定する。そして最終的に制御プロセッサ２ｄは、プロセッサ２ａの故障を検出する。制御プロセッサ２ｄは、その汎用更新メッセージ・メモリからのＳ１シグナリング汎用更新メッセージを次いで生成する。その再生成コピーで、制御プロセッサ２ｄは、結果としてシグナリング・プロセッサになる。それは、汎用更新メッセージ順序付けをウォークスルーしかつ順番に各プロセッサ２ｂ、２ｃ、...、２ｎに汎用更新メッセージ・コピーを送る。（制御プロセッサ２ｄは、プロセッサ２ａが利用可能でないということに気付いている。）
【００２６】
一般に、ＵＮＩＸTMプロセスは、どのくらいの数のある一定の型の信号が受信されるかということを識別することができない。従って、複製シグナリング汎用更新メッセージを拒絶することが受信プロセッサ２に対して必要ない。しかしながら、好ましい実施例では、受信プロセッサは、複製シグナリング汎用更新メッセージを拒絶すべく構成されている。例えば、各プロセッサ２は、固有の汎用更新メッセージＩＤカウンタを保守する。これら複数のカウンタは、システム・スタート・アップで同期することができる。ＧＬＵＰＰ  ｌｏｃｋの下で分散された各汎用更新メッセージは、オリジネーティング・プロセッサ２から固有の汎用更新メッセージＩＤを含み、かつ受信プロセッサ２は、そのＩＤが受信機プロセッサ２のカウンタに一致する汎用更新メッセージの受信によりその固有汎用更新メッセージＩＤカウンタを増分する。ここで、制御プロセッサ２ｄが、シグナリング・プロセッサとしてのその役割において、プロセッサ２ｃに複製シグナリング汎用更新メッセージを送付する場合、プロセッサ２ｃは、汎用更新メッセージの汎用更新メッセージＩＤとプロセッサ２ｂの汎用更新メッセージＩＤカウンタにおける対応ＩＤが一致しないので、さもなければ肯定応答できるがシグナリング汎用更新メッセージを無視する。同様に、プロセッサ２ｃは、制御プロセッサ２ｄからの複製シグナリング汎用更新メッセージを無視する。
【００２７】
従って、上記開示は、シグナリング・プロセッサがシグナリング・オペレーションの間に故障したならば、信号は、なんのプロセスにも送付されないかまたはプロセス・グループの全ての生存メンバーに送付されるかのいずれかであるような、シグナリングのＵＮＩＸTM−ライク・インプリメンテーションを記述する：ＧＬＵＰＰ  ｌｏｃｋを獲得する前にシグナリング・プロセッサが故障したならば、シグナリング・アクションは、決して行われない。−−シグナリング・プロセッサでさえも行われない。ＧＬＵＰＰ  ｌｏｃｋを獲得した後にかつ受信プロセッサのあるものに信号要求を潜在的に送付した後にシグナリング・プロセッサが故障したならば、生存しているプロセッサがなくなるまで、ＧＬＵＰＰは、生存しているプロセッサを用いて同じシグナリング汎用更新メッセージを送ることを再び試みる。それゆえに、シグナリング・プロセッサは、死ぬことができるが、生存しているプロセッサは、全ての他のプロセッサに同じ信号を送付する。汎用メッセージ更新ＩＤは、各入力要求を“新しい”対“見られかつ作用された”として識別させる。複製要求は、単に無視される。纏めると、信号は、決して部分的に送付されないかまたはプロセス・グループに二度送付されない。
【００２８】
ここで説明した変更されたＧＬＵＰＰでは、受信プロセッサ２の失敗（故障）は、一般的に全く取るに足らない。各プロセッサは、その受信プロセッサ２のプロセスＰに信号を送付することに対してのみ責任があるので、その受信プロセッサ２の故障は、一つの例外を有し、取り消されまたはアカウントされなかったタスクを残さない。故障した受信プロセッサ２が制御プロセッサであれば、重要なタスクは、アカウントされないで残される。カーは、汎用更新を実行している多重プロセッシング・システムにおけるロッカー・プロセッサの故障に対する手順を記述する。その手順は、この変更されたＧＬＵＰＰコンテキスト内で動作する。
上記手順は、システム１におけるあらゆる数のプロセッサ故障を網羅するために充分である。複数のプロセッサ故障は、上記シナリオの組合せに分解することができる。
【００２９】
従って、上記開示は、受信プロセッサが故障したならば、どのくらいその受信プロセッサがそのプロセッサに存在するプロセス・グループ・メンバーに信号を送付することに成功していたかということが全く取るに足らないようなシグナリングのＵＮＩＸTM−ライク・インプリメンテーションを記述する。受信プロセッサは、その受信プロセッサに存在するプロセス・グループ・メンバーだけを扱うことに対して責任を有する。
上記説明は、限定よりも例としての特定を含む。上記装置及び方法に対する変更は、当業者において容易に明らかであろうしかつそのような変更は、この発明の一部である。
【図面の簡単な説明】
【図１】  図１は、本発明の多重プロセッサ・システムの概略図である。
【図２】  図２は、本発明の多重プロセッサ・システムにおけるプロセスの状態の簡略図である。
【図３】  図３は、本発明の多重プロセッサ・システムにおけるプロセスの状態の簡略図である。
【図４】  図４は、本発明の多重プロセッサ・システムにおけるプロセスの状態の簡略図である。
【図１】
0003670017.tif 000002
【図２】
0003670017.tif 000003
【図３】
0003670017.tif 000004
【図４】
0003670017.tif 000005