JP2002505050A

JP2002505050A - 非同期メッセージ処理システム及び方法

Info

Publication number: JP2002505050A
Application number: JP50344299A
Authority: JP
Inventors: ウィリアム・ジョセフ・オールダー; エリック・ビアマン
Original assignee: Nortel Networks Ltd
Current assignee: Nortel Networks Ltd
Priority date: 1997-06-24
Filing date: 1998-06-02
Publication date: 2002-02-12
Also published as: WO1998059519A2; CA2292450A1; EP0992142A2; WO1998059519A3

Abstract

(57)【要約】状態とタイプによってプロセスが定義される非同期メッセージ処理システム及び方法を提供する。ネットワーク・ノードにおいて受信された入力メッセージは、入力メッセージ・キューに格納されて、到着した順に従って処理される。また、出力メッセージは、出力メッセージ・キューに格納されて、生成された順に従って宛先ネットワーク・ノードに転送される。プロセスにアドレスされた入力メッセージは、処理を完結しプロセス状態を修正する特定のメッセージ処理アプリケーション・コードを呼び出すことによって処理される。プロセス状態の修正は、完全に起こるか又は全く起きないという意味において最小単位であり、プロセス状態を部分的に修正することはない。

Description

【発明の詳細な説明】非同期メッセージ処理システム及び方法発明の分野本発明は、分散型非同期メッセージ処理システム及び方法に関する。発明の背景分散システムの仕様や実装のための通信処理に関する様々のモデルがポピュラーになってきた。サスペンドした送信先が応答するまでの間は送信元もサスペンドしてしまうような同期モデルの通信に基づいているのと同様に、既によく知られているシステムのほとんどは、ＡＤＡのランデブー機構から遠隔手続呼び出しに移行しつつある。このようなシステムは、実用上大きな利点を有する。何故ならば、手続呼び出しによって遠隔通信を隠すことができるので、最小限のインパクトで既存の局所アプリケーションを分散型アプリケーションに変えることができるからである。しかしながら、本質的な分散型リアクティブ・システム若しくはコマンド・アンド・コントロール・システムでは、同期モデルには幾つかの問題点がある。特定のイベントを待ってプロセス・バックするようなシステムはいずれも、通信デッドロックに陥りやすい。一般に、このようなデッドロックは、システム全体の状態に依存して発生するものであるから、極端に簡素化したシステム（すなわち、極めて少ない状態と正確な通信パターンしか持たない固定数の有限状態マシン）によってしか解析することができない。通信をクライアント／サーバ階層として厳重に組織化することによってデッドロックを回避することはできるが、アクティブなオブジェクト（すなわち自発的なメッセージ発信元）が互いに直接通信することができないという不器用な組織になりがちである。とりわけ、同位（ｐｅｅｒ）プロトコル処理や、例外や失敗状態の処理は、通常の通信パターンとは逆方向のメッセージ・フローを含むので、問題となる。結局のところ、高速ＲＩＳＣ（Reduced Instruction Set Computer：縮小命令セット・コンピュータ）を以ってしても、到着したメッセージによって生じる簡単な状態遷移や短いメッセージの伝送時間のために、コマンド・アンド・コントロール・システムのバルクを調整するので、ミリ秒単位のＣＰＵ時間が必要となる。ネットワーク上の離れたノード間の遅れはミリ秒で計測され、ラウンド・トリップ時間はしばしば数十ミリ秒になる。離れたノード間でのメッセージ伝送時間と局所でのメッセージ処理時間との比は、「時定比(time constant ratio)」と呼ばれる。上記した時間間隔における時定比は、おおよそ１０³〜１０⁴であり、既に極めて高い値となっている。ラウンド・トリップ時間は伝播遅延で占められているが、これは本質的に光の速度に依存するので減少することはない。したがって、グローバル・ネットワークかさらに成長することに伴なって、さらに１０の階乗だけ増大するであろう。しかしながら、処理時間や伝送時間は、次の数年のうちに、少なくとも１０の階乗だけ減少することが期待することができる。この結果、時定比の指数は１０⁵程度まで到達するであろう。時定比は、分散システムを特徴付ける重大なパラメータである。日々の個人的な経験から、５分間の会話を行うために５秒のテレフォン・コールを費やすのであれば好ましいが(この場合の時定比ｒは１／６０である)、もしコールに５分を要する（すなわち時定数ｒは１）ならばじれてしまうであろう。さらに、５秒間の会話のために５分待たされてしまうと当然にして怒ってしまう(時定比ｒは６０)。時定比ｒが１を超えると、待ち処理をサスペンドすることを意味する。もしコンテキスト・スイッチのコストがあまり高くなければ、何か他のことをするであろう。かくのごとく時定数ｒが高いと、プロセッサをビジー状態に保つためにいかに多くの「スレッド(thread)」が必要とされるかを考えさせられてしまう。現在のＬＡＮ（local Area Network）及びＰＣ（Personal Computer）の世界では、分散アプリケーション（典型的には１０〜１００の時定比ｒを持つ）が僅かに稼動しており、同期通信モデルが実行可能である。しかしながら、時定比ｒが１０００、単独では時定比ｒが１０⁶というのはもはや適切とは言い難い。１つの問題は、サスペンションによってスタックの実行を節約しなければならないので、サスペンド可能なプロセス又はスレッドを最悪のケースにおいて充分なスタック領域に割り当てなければならない。このため、スタック領域は、通常、１０キロ・バイトから１メガ・バイトの範囲になる。比較的多数の「オブジェクト」が同時発生するようなシステムの場合、時定比ｒの大きさ次第では、過度又は実行不可能なメモリ要求を招来してしまう。第２の問題は、現在のアプリケーションでは、サスペンションによるオーバーヘッドそれ自体が、典型的な遷移時間よりも長くなってしまうことである。発明の概要本発明の目的は、上述した欠点を未然に防止し若しくは緩和することにある。本発明の第１の側面は、プロセッサとメモリを有するネットワーク・ノードにおける非同期メッセージ処理方法であって、プロセス状態と関連するアプリケーション・コードからなりｐｉｄ（process i dentifier：プロセス識別子）によって識別可能な複数のプロセスをメモリ中に維持するステップと、プロセッサが、受信される各メッセージに対して、メッセージの一部を構成する宛先ｐｉｄを基にして前記複数のプロセスのうちいずれに対してアドレスされているのかを判断し、宛先ｐｉｄに関連付けられたアプリケーション・コードを実行して該メッセージを宛先プロセスのプロセス状態のファンクションとして処理し、必要であれば宛先プロセスのプロセス状態を変更するとともに、その間アプリケーション・タスクは必要であれば送出メッセージを生成するステップと、該ノードが送出メッセージを転送するステップと、を具備することを特徴とする非同期メッセージ処理方法である。また、本発明の第２の側面は、デジタル・ネットワークに接続するためのネットワーク・ノードであって、送られてくるメッセージを受信して入力メッセージ・キューに格納するとともに、送出するメッセージを出力メッセージ・キューから読み出して転送する、デジタル・ネットワークとのインターフェースと、プロセス状態と関連するアプリケーション・コードからなりｐｉｄ（process i dentifier：プロセス識別子）によって識別可能な複数のプロセスをメモリ中に維持するとともに、入力メッセージ・キューからメッセージを１度に１つずつ受信した順番に読み出して、メッセージの一部を構成する宛先ｐｉｄを基にして前記複数のプロセスのうちいずれに対してメッセージがアドレスされているのかを判断し、宛先ｐｉｄに関連付けられたアプリケーション・コードを実行して該メッセージを宛先プロセスのプロセス状態のファンクションとして処理し、必要であれば宛先プロセスのプロセス状態を変更するとともに、必要であれば出力メッセージ・キューの次の利用可能なバッファ位置に送出メッセージを書き込むプロセッサと、を具備することを特徴とするネットワーク・ノードである。また、本発明の第３の側面は、複数のネットワーク・ノードで構成されるデジタル・ネットワークであって、各ネットワーク・ノードは、送られてくるメッセージを受信して入力メッセージ・キューに格納するとともに、送出するメッセージを出力メッセージ・キューから読み出して転送する、デジタル・ネットワークとのインターフェースと、プロセス状態と関連するアプリケーション・コードからなりｐｉｄ（process i dentifier：プロセス識別子）によって識別可能な複数のプロセスをメモリ中に維持するとともに、入力メッセージ・キューからメッセージを１度に１つずつ受信した順番に読み出して、メッセージの一部を構成する宛先ｐｉｄを基にして前記複数のプロセスのうちいずれに対してメッセージがアドレスされているのかを判断し、宛先ｐｉｄに関連付けられたアプリケーション・コードを実行して該メッセージを宛先プロセスのプロセス状態のファンクションとして処理し、必要であれば宛先プロセスのプロセス状態を変更するとともに、必要であれば出力メッセージ・キューの次の利用可能なバッファ位置に送出メッセージを書き込むプロセッサと、を具備することを特徴とするデジタル・ネットワークである。図面の簡単な説明図１は、本実施例に係るネットワークの模式的なブロック図である。図２は、図１に示したネットワーク上の１つのノードに関するブロック図である。図３は、本発明の実施形態に係るノード内におけるメッセージの全体フローを示した図である。図４は、共有入力バッファ・リングを示した図である。図５は、代表的なメッセージ構文を示した図である。図６は、カーネル・データ構造の要約と状況レジスタを示した図である。図７は、取り消しログ（トレイル）メカニズムを示した図である。図８は、カーネル・ループを示したフローチャートである。好ましい実施形態に関する詳細な記述図１には、本発明の実施形態に係るシステム及び方法を実装したネットワーク・コンテキストを示している。該ネットワーク・コンテキストは、デジタル通信ネットワーク２０によって相互接続された複数の処理ノード１０で構成されている。通信ネットワーク２０は、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワーク、あるいは、グローバル・ネットワークであってもよい。ネットワーク２０は、いかなる処理ノード１０間においても、デジタル・メッセージを適度の最大サイズに至るまで送信する能力を有するものとする。ネットワーク２０は、コネクション指向、又は、コネクションレス・メディアのいずれであってもよいが、メッセージ損失、データ汚染、若しくは配信故障を起こす割合が容認し得る程度に低いことが好ましい。低層のプロトコルを用いることによって、多くの通信技術を本発明の実現に利用し又は適用することができる。但し、代表的な具体的な例として、本実施例では、単一セルＡＴＭ（asynchronous transfer mode ：非同期転送モード）を用いることを想定する。この場合には、各ノード１０のペアの間には、各方向毎に単一の仮想チャネルが存在し、また、ノード識別子を局所仮想チャネル識別子にマップするテーブルが各ノード毎に存在するものと想定する。さらに、提供されるサービス品質は、上位層プロトコルが必要でない程度にメッセージ破損が生ずる可能性が充分に低いものであるとする。ノード・ストラクチャ図２には、個々のノード１０の構造を図解している。図示の通り、ノード１０は、少なくとも、高速のローカル・バス３０と、プロセッサ若しくはＣＰＵ３２と、幾つかの共有ランダム・アクセス・メモリ３４と、通信ネットワーク２０（図１を参照のこと）へのアクセスを提供するインテリジェント通信アダプタ３６とを備えている。通信アダプタ３６とバス３０は、通信アダプタ３６と共有メモリ３４内のメッセージ・バツファとの間で直接メモリ・アクセス(Direct Memory Access ：ＤＭＡ)が可能な構成となっている。また、メッセージ・バッファは、プロセッサ３２からもみえるものとする。本発明の好ましい実施形態では、プロセッサ３２と通信アダプタ３６との間の通常の通信は、共有メモリ３４を介してのみ行われるものとし、考え得る例外的な条件下以外では、通信アダプタ３６は割り込みを発生しないものとする。各ノードのペア間での仮想チャネルの他に、各ノードは自分自身に対する「ループ・バック」チャネルを有しており、ノードは自分自身にメッセージを送信することができる。かかるループ・バック・チャネルは、通信アダプタ３６内で実行されるか、プロセッサ３２においてエミュレートされるか、若しくは、通信ネットワーク経由で行われる。各プロセッサは、標準的なＯＳ(オペレーティング・システム)の介在なしに、本発明の実施形態に係るランタイム環境や、幾つかのアプリケーション・コードを実行している。ランタイム環境は従来のＯＳのコンテキストによっても実行することができるが、記述が相当複雑となるという点を理解されたい。リアルタイム環境の概観さらに、単一のノード１０におけるオペレーションに関して考察しながら、本発明の実施例を詳解することにする。プロセッサ３２におけるランタイム環境は、プロセッサ３２上で周期的に若しくは継続的に実行されるカーネルによってコントロールされる。「周期的」というケースは、ＯＳのコンテキストにおいて用いられるオペレーション方法であるが、継続的な実行の方が好ましいので、以下の記述では後者を想定することにする。各プロセット３２は、カーネルによって呼び出されたアプリケーションの「プロセス」も実行する。各プロセスは、他のプロセスによって生成されてから自発的に終了するまでの間の寿命を有する。本明細書中で「プロセス」という用語を用いるときは、プロセッサ時間を時分割するとともに特定のプロセスに割り当てられた時分割の間でスタックを節約することによって他のプロセスと同時に実行するアプリケーション・コードの継続的なストリームというような、従来の意味とは相違する。本明細書で言う「プロセス」は、以下の事柄によって定義される。（１）プロセスが生成されてから終了するまでの間に存在するプロセスによって所有される共有メモリ３４内に格納される種々の状態からなるプロセス状態（２）プロセスの振舞い（behavior）を定義するとともに種々の状態上で動作して状態遷移を引き起こすコードによって定義されるプロセス・タイプ繰言になるが、プロセス状態及びプロセス・タイプ定義のみがプロセスの寿命の間で継続して存在する。開始し終了しないという意味において、カーネルは継続的である。アプリケーション・プロセスが実行する間、カーネルがコントロールする。カーネルは、アプリケーション・プロセスを直接呼び出す。この意味において、カーネルは常に実行していると言える。広い意味では(概観的には)、カーネルは、特定のノードによって受信されたメッセージを１度に１つだけ取り、メッセージの予定された宛先はどのプロセスかを判断し、宛先のプロセスのプロセス・タイプで示される完了コードを実行し、プロセス状態に従って可能な１又はそれ以上の状態に変化し、他のプロセスに送信すべき１又はそれ以上のメッセージを出力し、最終的にカーネルに戻す。各メッセージ毎に処理されるこのようなステップからなるシーケンスは、１つの「状態遷移」、又は、単に１つの「遷移」を構成するとみなされる。カーネルは、以前のメッセージに関連する状態遷移が完了するまでは、特定のノードによって受信された次のメッセージを処理しない。事実、カーネルは、アプリケーション・コードからのリターンが実行して、遷移が発生するまでは、何も行わない。特定のプロセスに関連して呼び出されたアプリケーション・コードが実行する間、プロセスは「アクティブ」モードにある。アプリケーション・タスクが完了したとき、プロセスは「インアクティブ」モードとなる。インアクティブの間、プロセス状態とタイプは存在し続けるが、プロセッサは、プロセスに関連するいかなるアプリケーション・コードも実行しないし、このプロセスに起こり得るいかなる状態の変化も発生しない。時分割も他のプロセスの介在なしにアプリケーション・コードの遷移が完了するので、プロセス間のコンテキスト・スイッチを実行する必要が全くない。状態遷移が最小単位（atomic）であることは、本発明の好ましい特徴である。最小単位とは、状態遷移に関連するすべてのオペレーションが発生するか、又は、いずれも発生しないことを意味する。もし何らかの理由により、状態遷移に関連するすべてのオペレーションが完了しないならば、既に完了したいかなるオペレーションの状態に対する効果も後退復帰する必要がある。各プロセスの振舞いは、プロセスの状態やプロセス・タイプによって独自に決定される。異なるプロセスの状態同士が重なり合うことはない。プロセスのプロセス状態は、メッセージの受信とその処理によってのみ変化することができる。プロセスの状態遷移は、直列化され、厳格なシーケンスを形成する。プロセスは、状態データやストレージを、排他的に「所有」する(責任も負う)。プロセス・タイプに関連するアプリケーション・コードは、状態変化と、各種の受信メッセージに対する送信メッセージを完全に指定する。このコードからの成功裡の返信によって状態遷移は完了する。遷移の間、各プロセスは、インアクティブ・モードとなって、次のメッセージを待機する。各遷移に対するアプリケーション・コードが完了すると、リターン・コードがカーネルに戻される。リターン・コードは、コードが成功裡に実行されたことを示す「完遂(commit)」か、又は、コードの実行に成功しなかったことを示す「中止( abort)」のいずれかである。完遂リターン・コードの場合には、成功裡の状態遷移が発生する。カーネルは、次に到来するメッセージに移行する前に、何らかの「遷移後(post-transition)」処理を実行することになるが、この点については後に詳解する。プロセス生成、終了、及び識別すべてのプロセス"Ｐ"は、同一のプロセッサ上における既存のプロセス"Ａ"の状態遷移の副産物として生成される。Ｐは、Ａとは独立していることを選択している間は存在し続ける。プロセスは、最後のメッセージを受信したときに、完遂リターン・コードを修正することによって、終了する。このような修正は、カーネルによって検知され、遷移後処理の間に処理される。このとき、終了処理に割り当てられている状態ストレージが適当なメモリ・プールに戻され、プロセス・タイプはデフォルト・タイプに戻されて、すべてのメッセージが廃棄される。また、実現番号（incarnation number）が増分されるので、終了した処理に対する未解決のメッセージはすべて廃棄される。プロセスの生成と終了はいずれも、最小単位の遷移の一部である。とりわけ、Ｐの生成は、その生成側であるＡについての最小単位の遷移の一部である。直接的な生成は局所的にのみ（すなわち同一の共有メモリ上で）行われるので、生成された遠隔的なプロセスを得るためには、プロセスは既に存在するエージェント経由で間接的に稼動しなければならないが、エージェントは、適切なセキュリティ限定を課すこともある。一旦生成されたプロセスの各々は、宛先ｐｉｄ（プロセス識別子）を有しており、他のプロセスがメッセージをプロセスにアドレスするために使用される。宛先ｐｉｄについては後述する。宛先ｐｉｄをグローバルに利用可能にするためには、初期接続プロトコルが必要である。初期的には、プロセスＰのｐｉｄを知るプロセスとＰ自身のみが局所的な生成元である。遠隔プロセスのｐｉｄを取得する通常の方法は、周知の「ネーム・サーバ」プロセスに対して初期要求を送信することであり、其処からの応答には所望のｐｉｄが含まれている。このことは、既存のプロセスと、新規に生成されたプロセスの双方に当てはまる。周知のネーム・サーバ・プロセス（少なくとも各ノード毎に１つある）のプロセス名は、２通りの方法で扱うことができ、好ましくは各方法の組み合わせで使用することである。第１の方法は、すべてのノード上で至る所にある優れたサーバの各々に対して固定インデックス（固定又は実現番号）を与えることである。第２の方法は、周知のプロセス・レジスタ自身を持つことに基づく一般的な分散ネーム・サービスに依るものである(ネーム・サーバそれ自身は、第１の方法を利用する)。概略的なメッセージ・フローメッセージは、プロセスが同一のノード上にあるか否かに拘らず、ノード間で通信を行うただ１つの手段である。図３には、単一のノード上におけるメッセージのフローを概略的に図解している。各ノードは、回転式の入力バッファ・リング５０と、回転式の出力バッファ・リング５２を有しているが、これらバッファ・リングはいずれも共有メモリ（図２を参照のこと）の一部を用いて形成される。プロセッサ３２は、カーネル５４を実行するとともに、アプリケーション・プロセス５６の実行をコントロールする。カーネル５４は、種々の機能を持つが、ここではディスパッチャ機能を実行するとともに、入力バッファ５０からの読み出しを行う。アプリケーション・プロセス５６は、出力バッファ５６への書き込みを行う。他のすべてのノードからの順序付けられた入力ストリーム５８は、単一の直列入力ストリーム６０に統合（merge）される。ＡＴＭの場合であれば、ＡＴＭネットワークないの何処かで統合が行われるが、他のネットワーク環境であれば、図示のようにアダプタ３６内で統合が行われる。送られてくるメッセージは、回転式入力バッファ・リング５０の次の空きスロットに挿入される。カーネル５４は、入力バッファ・リング５０からメッセージを非同期的に引き出し、いかなるプロセスのスケジューリングも必要なしに適切なアプリケーション・プロセス５６を活動化することによって、到着した順にメッセージの処理を行う。適切なアプリケーション・プロセス５６の活動化については、後にさらに詳解することにする。出力メッセージは、回転式出力バッファ・リング５２中の引き続くスロットに入力される。アダプタ３６は、出力バッファ・リング５２からメッセージを順次引き出して、他のすべてのノードへの順序ストリーム６４を含んだ単一の直列出力ストリーム６２中に配置する。アダプタが、種々のストリーム間でメッセージを並べ替えすることも可能であるが、単一のストリーム内で並べ替えを行うことはできない。回転式入力バッファ・リング５０と回転式出力バッファ・リング５２は、回転リング・メカニズムを利用することによって、カーネル５４の明確な介在を必要とすることなしに、空きバッファの自動再利用を実現するものである。リングのサイズにより、遷移実行速度の変動を許容しなから、入力プロセス、コード実行、及び出力プロセスを非同期化することができる。システムに対する負荷は、各バッファ・リング５０，５２の占有期間によって表すことができる。バッファの氾濫に依拠する損失率が許容できる程度に低くなるように、バッファ・リング５０，５２のサイズは充分大きく（すなわち、他の損失メカニズムと同様の程度に）しなければならない。入力バッファ・リング入力バッファ・リング５０の記録又は個々のバッファの詳細について、図４を参照しながら説明する。回転式入力バッファ・リング５０は、通信アダプタ３６から受信されるメッセージを処理するための、共有メモリ３４内のデータ構造である。回転式入力バッファ・リング５０は、より好ましくは、固定（最大）サイズのメッセージ・バッファからなるリング（すなわち、環状に接続されたリスト）として、例えばノード初期化時などに静的に構成される。静的なリング構造を使用することによって、処理期間中における動的なリスト操作を行う必要がなくなるとともに、相互排除問題や、明確なバッファ再利用管理の問題を回避することができる。あるいは、プロセッサによってバッファを動的にリングに付加したり削除したりして、占有統計上の緩やかな変化に適応するようにしてもよい。個々のメッセージ・バッファは、チェーン中の次のメッセージ・バッファのアドレスを含んでいる。これらのアドレスは、リングがメモリ中の何処に格納されているかをひとまとめに定義するものである。静的に構成されたリングの場合、これらのアドレスは一定値である。図４には、各メッセージ・バッファ中のフィールド（但し、次のバッファのアドレスを除く）が示されている。各メッセージ・バッファは、後述する同期化に使用される状態ワード７０を有する他、可能であれば、幾つかの付加的制御情報(例えばＡＴＭの場合であれば仮想チャネル識別子)を含んでもよい。各メッセージ・バッファは、メッセージの本体７２（若しくはコンテンツ）を格納するスペースを有する。各バッファが持つフィールドの順番やコンテンツは、特定のメッセージ・プロトコルやバッファリングの手法に適合するように設定することができる。他の実施形態では(図示しない)、メッセージ本体と、幾つかの又はすべての動的制御／状態フィールドを、メモリの異なる領域に置いて、本体へのポインタのみをバッファ・リング中に書き込むようにしてもよい。このような変形例は、プロセッサによって使用される仮想メモリ・アドレスがアダプタによって使用される物理メモリ・アドレスとは相違するようなシステムにおいて有効である。何故ならば、この変形例によれば、それぞれが同一の（リンクしていない）メッセージ・バッファ上で独自の静的なリング構造のポインタを(異なるメモリ・アドレス空間に)持つことができるからである。図４に示すように、メッセージ７２の本体は、宛先ｐｉｄフィールド７４と、発信元ｐｉｄフィールド７６と、データ・フィールド７８とを含んでいる。メッセージは、対応するｐｉｄをその宛先ｐｉｄフィールド７４に持つことによって、個々のプロセスにアドレスされる。宛先ｐｉｄフィールド７４や発信元ｐｉｄフィールド７６のサイズや構造は、ネットワークにおけるそれぞれの特定の例に関するアドレッシングの要求に応じて決定される。ｐｉｄフィールドの一般的な構造は、プロセスに関連するノードを識別するために利用されるノード識別子８０と、各ノード上のプロセスを識別するための局所ｐｉｄ８２と、特定の局所ｐｉｄ８２を持つプロセスが生成する毎に増分される増分カウンタとして使用される実現番号８４とを含んでいる。実現番号８４は、ｐｉｄの再利用を制限したり、プロセスを分散させたるするために設けられている。プロセス・タイプの特定の実現は、プロセス・インスタンスである。プロセス・インスタンス・テーブルは、宛先ｐｉｄの局所ｐｉｄ８２から指示されたプロセスに関連するアプリケーション・コードを実行するために必要とされる情報へのマッピングを保持している。プロセス・インスタンス・テーブルには、各局所ｐｉｄ８２毎に１つのレコード８３が用意される。レコードは、主として、プロセス・インスタンスに対するメッセージを処理するためのアプリケーション・コードを格納する共有メモリ中の位置に対するコード・ポインタ８６と、プロセス・インスタンスの状態情報に対する状態ポインタ８８とで構成される。ｐｉｄの実現インデックスも、このレコードのフィールド９０中に保持されている。プロセス・タイプの包括的な属性を含んだ構造に対するポインタを含んでもよい。デバッグ・コントロール若しくはパフォーマンス測定に関連するその他の属性を(インスタンス毎に)さらに含んでもよい。これらの属性は、変形例や実行モード（例えば、シミュレーション、開発、フィールド・コンテキスト）毎に相違する。出力バッファ・リング出力バッファ・リングは、入力バッファ・リングと同様である。アダプタによる入力パッファオペレーション通信アダプタ３６の１つの機能は、例えば、有効な受信メッセージ（すなわち「空(ｅｍｐｔｙ)」でないセル）を、入力バッファ・リング５０中の状態変数inp ut_write_headによって指し示されているバッファに、（ＤＭＡ経由で）転送することである。状態変数input_write_headは、入力バッファ・リング５０中において次の空のバッファを指し示すために使用される。この状態変数は、アダプタ３６専用であっても、あるいは共有メモら３４上で保持されていてもよいが、アダプタ３６のみが読み出したり再書き込みすることができるものとする(初期化時は別として)。メッセージ転送に成功する度に、アダプタ３６は、現在のバッファ中の状態フィールドにフラグをセットして、バッファが有効なメッセージで占有されていることを示すようにするとともに、input_write_headをチェーンの次のバッファに進める。例えば、他の状態変数input_read_headは、カーネル５４によって維持され、入力バッファ・リングからのメッセージ読み出しをコントロールするために利用されるが、この点は後に詳解する。アダプタによる出力バッファオペレーション通信アダプタ３６の他の機能は、出力バッファ・リング５２に書き込まれた有効な（すなわち「空（ｅｍｐｔｙ）でないセル」）メッセージを、出力通信ストリーム６２に、（ＤＭＡ経由で）転送することである。例えば、出力バッファ・リング５２から読み出すべきメッセージを指し示すために、状態変数output_read_ headが使用される。この状態変数は、アダプタ３６専用であっても、あるいは共用メモリ３４中に保持されていてもよいが、アダプタ３６のみが読み出し及び再書き込みを行うことができるものとする(但し、初期化時を除く)。メッセージ転送に成功する度に、アタプタ３６は、現在のバッファの状態フィールドにフラグをセットして、バッファが再び利用可能になったことを示すとともに、output_r ead_headをチェーンの次のバッファに進める。例えば、出力バッファ・リング５２へのメッセージ書き込みをコントロールするために、他の状態変数output_wri te_headがカーネル５４によって保持されているが、この点は後に詳解することにする。メッセージ構文図５には、代表的なメッセージ構文を示している。上述したように、メッセージ構文は、各メッセージの先頭に宛先ｐｉｄ７４と、発信元ｐｉｄ７６を含んでいる。発信元ｐｉｄ７６は、カーネル７４のラン・タイム・システムによって各メッセージに対して自動的にスタンプされる。また、宛先ｐｉｄ７４は、カーネルによって、メッセージ送信プリミティブ・オペレーションの一部として挿入される。アプリケーション・コード５６は、メッセージ中のこれらいずれのフィールドにも直接アクセスすることはできないが、メッセージ発信元に対して明示コールとして尋ねることができる。残りのメッセージ・コンテンツ（すなわち、データ・フィールド７８）はメッセージ・マーシャル／デマーシャル装置に関連するものであり、理想的には、アプリケーション・プログラミング言語と一体化されている。この詳細については本明細書中では言及しない。典型的には、メソッド９２、フォーマット・インジケータ９４(引数９６の個数や署名の圧縮タイプなど)、標準機械非依存の基本タイプ表示(ｐｉｄを含む)、及びある種のチェックサム９８を符号化する。このフォーマットは、暗号化することもできる。カーネル・データ構造及び環境レジスタ図６には、特定の実施形態においてラン・タイム・システムをどのように構成するかを図解している。この実施形態では、カーネルは、システム・スタック１００とトレイル・スタック１０２（後述）を維持する。また、一連の環境レジスタは以下に示す通りである。 mi‐"mssage in"=input_read_head：入力バッファ・リング５０中のメッセージについてのメッセージ発信元ｐｉｄと宛先ｐｉｄにアクセスする。メッセージが存在する場合はmi.statusは真（ｔｒｕｅ）である。mi.dest.pidは、メッセージに含まれる宛先ｐｉｄである。 in‐input byte stream：コードをデマーシャルして、入力バッファ・リング５０内でメッセージからメッセージ・フィールドを引き出すために使用される。 no‐"next out"=output_write_head：出力バッファ・リング５２内で、宛先ｐｉｄや発信元ｐｉｄをセットするために次に利用可能な出力バッファである。 out‐output byte stream：出力バッファ・リング５２内で出力メッセージをフォーマットするためのコードをマーシャルすることによって使用される。 pe‐process entry：プロセス・インスタンス・テーブル８５経由ですべてのプロセス・インスタンス及びタイプ属性にアクセスする。 sp‐stack pointer：システム・スタック１００の先頭 te‐trail stack end：取り消しログ・トレイル・スタック１０２の最後尾 pc‐program counter：実行コード中の次に実行可能なインストラクションを指す。以上、入力及び出力バッファ・リングに関連する変数について説明してきた。システム・スタック及びトレイル・スタックに関する主な利点は、全システムにおいて、各プロセッサ毎にただ１つしか必要としないという点にある。図示のメモリ・プール１０４は、プロセス状態ストレージのために予約されたメモリ３４（図２を参照のこと）中の領域である。また、コード・メモリ１０６は、アプリケーション・コードを保存するための共有メモリ３４中の領域である。アクティブ・タイマ・リスト１１２（カーネルによって管理される）も、共有メモリ３４内に置かれている。コード・ポインタ８６は、プロセス・インスタンス・テーブル８５中でｐｅによって指し示されているレコードから、コード・メモリ１０６内のアプリケーション・コードが格納されている場所を指し示すように図示されている。状態ポインタ８８は、プロセス・インスタンス・テーブル８５中の同じレコードから状態メモリ１０４中で当該プロセス・インスタンスに関するプロセス状態を格納した場所を指し示すように図示されている。プロセス状態は、アクティブ・タイマ・リスト１１２中のタイマに対する１又はそれ以上のタイマ・ポインタ１１４を含んでもよい。取り消しログ・メカニズム状態遷移の最小単位を実装するには、幾つかの方法が挙げられる。ほとんどのメッセージによってごく僅かな状態しか更新されず、且つ、旧い状態を回復する現実的な必要性は極めて稀であるという前提の下で、図７に図解するように、変化したすべての状態変数の旧い値についてのログをとることに基づいた、ソフトウェアによる効率的な実装を行うことができる。この目的のためには、トレイル・スタック１０２と呼ばれる充分に大きなサイズを持つ、単一のシステム・リソースが必要である。トレイル・スタック１０２は、（アドレス、値）のペアからなるアレイ（若しくはスタック）で構成される。初期的には、及び、各アプリケーション・タスクが実行される直前には、環境レジスタｔｅ(ｔｒａｉｌｅｎｄ)は、トレイル・スタック１０３の開始位置１０３を指し示すようにセットされる。アプリケーション・タスク実行期間中に状態のワードを書き込むときは、まず、指し示された場所のアドレス（ａｄｄｒ）と現在の値(ｏｌｄｖａｌ)をトレイル・スタック１０２に書き込まなければならない。(言語コンパイラとコード・ジェネレータのサポートにより、この要求を効率的に実現することができる。)遷移が完遂したとき(すなわち、アプリケーション・タスクが成功裡に完了して、プロセスがサスペンドされたモードに戻されたとき )、ｔｅはトレイル・スタック１０２の先頭にリセットされ、次のメッセージに対する準備が整う。遷移を中断する必要があるときには、トレイルは（後方から）逆の順序で処理され、旧い値がプロセス状態メモリ１０４によって指示されている場所に回復する。このような処理は例えば、以下に示すコードによって実現される。失敗した遷移の間に書き込まれた新しい値（ｎｅｗｖａｌ）は廃棄される。トレイリングは、すべての状態変数の更新に対して適用される。状態変数は、メモリ・セグメント内でプロセスの状態ポインタによって指し示されたもので構成され、其処から届くところにある。状態変数の更新は、タイマ領域（プロセスによって使用されるタイマの生成、再セット、削除に関連する。タイマに関しては後に詳解する）や、プロセス・インスタンス・テーブル(プロセスの生成に関連する)、メモリ・プール（動的メモリ割り当てに関連する）における変化を含むものとする。現在では、タイマ・オペレーション、プロセス生成、及びメモリ割り当てはすべて、最小単位のアクションに自動的に含まれる。トレイリングは、スタック、又は出力メッセージ・バッファ、若しくは、他の揮発性変数の更新に対しては必要でない。勿論、最適化のためであれば、状態オブジェクトのための初期化（構築）コードが必要とされる。勿論、本発明の要旨を逸脱することなしに最小単位であることを実現するために他のメカニズムを用いることができるということも充分理解されたい。カーネルのディスパッチ・プロセスプロセッサ３２は、アプリケーション・コード実行の間において、カーネルを実行する。カーネルは、入力メッセージ毎に１回だけ実行するメイン・ループを有している。図８には、カーネル・ループをフローチャートの形式で図解している。カーネル・ループに関しては、図６を参照しながら記述されたカーネル・データ構造及び環境レジスタを紹介する前記の文脈中で記述される。既に言及したように、カーネルは、入力バッファ５０中で次に利用可能なメッセージを指し示す内部状態変数input_read_head（若しくはｍｉ）を有している。カーネルは、状態レジスタmi.statusがゼロに等しいことによって入力バッファが空であることが示されている間は、アイドル・タスクを実行する(ブロック２００で分岐Ｙｅｓに抜けてブロック２０２に進む)。カーネルの機能は、入力されたメッセージを到着順に従って可能な限り迅速に処理することである。入力メッセージが到着し (ブロック２００の分岐Ｎｏに進む)、さらに、input_read_headによって指し示されているメッセージ・バッファの状態フラグ・フィールドが有効メッセージである旨を示す場合には、カーネルは、メッセージの宛先ｐｉｄであるｍｉ．ｄｅｓｔを引き出し、宛先ｐｉｄから局所ｐｉｄを引き出し、該局所ｐｉｄが正しい範囲内にあることを検証し、そして、プロセス・インスタンス・テーブル８５内のレコードにアクセスするためにこれを使用する。プロセス・インスタンス・レコードのフィールドは、実現インデックスを含んでいるが、これは入力されたメッセージから引き出された宛先ｐｉｄと正確に一致しなければならない。もし、引き出された実現インデックスが範囲外であるならば、入力メッセージは無効であるとみなされ(ブロック２０４の分岐Ｎｏに進む)、エラー・カウンタが増分され(ブロック２０６)、その状態フィールドをクリアするとともにinput_read_headポインタを進めることによって(ブロック２２２)、メッセージは廃棄される。もしメッセージｐｉｄが有効であるならば(ブロック２０４において分岐Ｙｅｓに進む)、カーネルは、環境変数をプロセス実行や最小単位サポートのために設定するとともに、プロセス・インスタンス・テーブル中のコード・ポインタによって指し示されているアプリケーション・コードを呼び出す。アプリケーション・コードがアクセスする必要がある場合には、１つの（概念的な）環境変数がメッセージ発信元ｐｉｄを与えるようにしてもよい。（しかしながら、アプリケーションがメッセージの発信元を問い合わせる必要があるのはごく稀であり、単にメッセージ送信元フィールドに対するポインタを隠し環境変数（可能であればレジスタ）にコピーするだけの方で充分であり、効果的でさえある。また、アプリケーションが必要とする場合には、発信元フィールドを引き出すために間接メモリ参照を使用するだけで充分である。）同様に、アプリケーション・コードがこの場所で利用可能な情報（例えば、ｐｉｄ又はプロセス・タイプ属性）を要求する場合には、プロセス・インスタンス・テーブル・レコードへのポインタが環境変数内(可能であればレジスタ)に残される。アプリケーション・コードを呼び出すためには、状態ポインタ８８とコード・ポインタ８６がプロセス・インスタンス・テーブル８５から読み出され、コール規定に応じてレジスタにフェッチされ、及び／又は、スタックにプッシュされる。メソッド又はメッセージのコマンド・フィールドを引き出さなければならない。また、このコマンド後のメッセージの次のフィールドに対するポインタすなわち入力バイト・ストリーム・レジスタも、レジスタにフェッチされ、及び／又は、スタックにプッシュされる。出力するメッセージに対する最小単位をサポートするために、output_write_headのコピー（カーネルの局所）が作成される(ブロック２１０)。次いで、コード・ポインタによって指し示されるアプリケーション・コードを呼び出し、入力バイト・ストリーム・インと状態ポインタをパラメータとして渡し、リターン・コード若しくは結果"ｒｅｓ"を予期して、アプリケーション・コードが実行される(ブロック２１２)。アプリケーション・コードがカーネルに戻されたとき、そのリターン・コードｒｅｓ（都合に応じてレジスタ内にあるか又はスタックの先頭に置かれる）は、「完遂(commit)」又は「中止(abort)」を示す。もし中止するように決定が下されたことをコードが示すならば(ブロック２１４の分岐Ｎｏ)、カーネルは output_write_headをその局所に保存された値からリセットして、すべての出力メッセージを取り消す。次いで、プロセスの初期状態を回復する必要がある(ブロック２１６)。次いで、状態フィールドをクリアするとともにinput_read_head を次のメッセージに進めることによって、入力メッセージが廃棄される(ブロック２２２)。もしリターン・コードが「完遂(commit)」を示すならば(ブロック２１４の分岐Ｙｅｓ)、アプリケーション・コードによって生成された出力メッセージはすべて、output_write_headの保存された値で開始しoutput_write_headの現在の値に続くが、通信アダプタで処理されるように、状態フィールドをセットしなければならない。単にtrail_endにtrail_startを代入することによって、トレイルをリセットすることができる(ブロック２１８)。プロセスが終了するという特別な場合には、プロセスに関連するｐｉｄ及びプロセス状態は割り当て解除される(ブロック２２０)。最終的には、状態フィールドをクリアするとともにinput_read_he adを次の入力メッセージに進めることによってことによって入力メッセージが廃棄される(ブロック２２２)。アプリケーション・コードの実行期間中にソフトウェア例外が発生した場合には(矢印２２３)、適切な診断情報を取得することができ(ブロック２２４)、システム・スタックは通常の時点（すなわち、アプリケーション・コードをコールする直前の時点）にリセットされ、コントロールは上述したような中止処理（ブロック２１６）に移行する。関連する診断情報は、大まかにサイズの昇り順及びユーティリティの降り順で言えば、以下に示すもので構成される。（０）エラー・タイプ及びプログラム・カウンタ（１）現在の入力メッセージ（２）(完全な)現在のプロセス状態（３）完全な入力バッファ・リング(最近処理されたメッセージと近い将来のメッセージの双方を含む) ソフトウェア例外の例として、プロセスの各タイプ毎に、該タイプについてのプロセス遷移のための最大許容時間が存在することもある。遷移がこの制限時間を超過した場合には、例外が発生して、上述したように処理される。本明細書で記述される実施形態では、メッセージが外部又は完全に内部的なものかによってプロセッサ・オーバーヘッドの相違は全くない。内部メッセージが出力バッファから入力バッファへの潜在的なコピー操作を除去するように最適化されている場合、この相違はせいぜいコピーのＤＭＡコストにしかならない。上述したようなカーネル・ループを（アセンブラ言語で）最適に実装する場合、およそ５０の機械語インストラクションで充分であり、典型的なワークステーションであればカーネルのオーバーヘッドは数分の１マイクロ秒にしかならない。プロセス遷移は、応答が要求される出力メッセージを生成してもよい。このようなプロセス遷移は、（通常通りに）完結して、プロセスは「インアクティブ」モードに突入する。期待される応答が受信されたとき、入力バッファ・リングに入れられて、通常の方式によりオリジナルのプロセスを活動化することによって処理される。メッセージが失われる可能性があると仮定されているので、このような失われたメッセージを検出するための設備がタイマに要求される。１つの可能な一般的な規則は、メッセージに対する応答が待たれているプロセスは損失メッセージを検出するためのタイマを利用するようにすることである。このようなプロセスは、「一時的な状態(transient state)」にあると呼ばれ、もしオリジナルのメッセージ又はその応答のいずれか失われたならば、プロセスはその代わりにこのような状態に無限にとどまることができる。タイマが消滅すると、タイムアウト・メッセージが送信されて、プロセスによるある種の回復アクションのトリガとなる。採用することができる回復アクションの種類は、関連するプロセスの種類や失敗の性質に依存する。例えば、「持続的な(persistent)」プロセス（バックアップを伴なうプロセスや、自動的に再生成されるプロセス）間での交換の場合には、アクションとは、(メッセージを送ることによって)パートナーの状態をチェックしたり、パートナーの名前を再綴じ込みすることであってもよいし、成功するまで継続的に行ってもよい。束の間のプロセス（例えば、コール・セットアップやトランサクションを管理するプロセス）の場合、該プロセスに対する外部手段によって生成される何らかのエントリを用いてアクションを単に中止することである。数多くのプロセスが束の間の状態に突入し、ほとんどいつも直ぐにその状態を立ち去るようなシステムでは、タイマのセッティングと取り消しの双方にかかる費用を極めて低く維持することが重要である。本明細書中では、タイムアウト値は任意の値であることを前提とし、通常の応答時間よりも相当大きいタイムアウト値を用いるものとする。タイムアウトの実際の値は特に重要ではなく、通常、タイムアウト遅延を正確に与える必要は全くない。このような状況においては、極めて低いコストを実現するために、以下に示すような形式のデータ構造を使用する。以下に示す２通りの処理手順を用いるプロセスによって、タイマを生成したり破壊することができる。タイマ・ポインタは、プロセス状態内に維持される。このプロセスは、新しいタイマ・レコードを生成して、そのポインタを戻す。所有者フィールドは現在実行しているプロセスのｉｄを取得して、タイマ・レコードがグローバル・タイマ・チェーンに添付される。（異なるクロック解像度が必要とされる場合には、その解像度が入力パラメータとなる。）このようなタイマ・チェーンは、カーネルによって管理されるグローバル変数である。上式によって、タイマをグローバル・タイマ・チェーンから削除され、(効率化のため、二重リンク・チェーンである必要がある)、次いでタイマを割り当て解除する。以下に示すマクロを用いることによって、非常に安価にタイマのセッティングと取り消しを行うことができる。リアル・タイム・クロックによる規則的な割り込みによって、非否定的値フィールドを減分しながらすべてのチェーン接続されたタイマ上で実行するタイマ・スキャン（アプリケーション・プロセス実行の合間）を実行するように構成することができる。ゼロになる値フィールドはすべて、所有者プロセスに送信されるメッセージになる。本実施例では、タイムアウト・メッセージは、コマンド「タイムアウト」を持つと仮定しているので、その結果として起こるアクションは、純粋に状態駆動型である。その代替技術として、set_timerがタイムアウト・メッセージ上で使用するメッセージ・コードを含むことができる。上述した教示を考慮して、本発明に関する数多くの修正や変更を行うことが可能である。したがって、特許請求の範囲に記載されている範囲を逸脱することなく、本明細書中で明確に記述した以外の形態で本発明を実現することができるという点を充分留意されたい。本明細書中では、状態遷移の最小単位を実現するための特定のメカニズムについて記述してきたが、他のメカニズムを利用することもできるという点を留意されたい。プロセスの能力をあらわすためにプロセスＩＤ（ｐｉｄ）を用いることができる。ｐｉｄを持つことによって、ある実体に対して関連するプロセスが受容するすべてのメッセージを送信することができる権利を与え、これによってあることができるという能力を表すことになる。本明細書において記述された実施形態では、ｐｉｄは、２値であり、手近ないかなるデータ構造の中にも格納し、またメッセージに入れて自由に引き渡すなどすることができる。また、引き渡す能力に関して、何らコントロールや制限を必要としない。このようなシステムでは、プロセスを破壊し、次いで、別のｐｉｄを持つ新しいプロセスを生成して、必要であればその機能を実行することによってのみ、以前に許可された能力を取り消すことができる。ノードの再初期化はこれの極端な例である。実用上の仮定は、すべてのノードが悪意がないという点で信用することができるが、故障条件下では誤動作する可能性があるような、温和で協力的な環境ということである。実現番号は、ｐｉｄのその他の未使用ビットを埋めるが、ある時間間隔の間は同じプロセスｉｄが再利用されることはなく、したがって、記憶された旧いｐｉｄを一掃（ｐｕｒｇｅ）するには充分となっている。目立った能力を取り消す安価な方法は、その状態を維持している期間中にプロセスの実現番号を増分することである。勿論、実現番号を用いない実装形態も可能である。

【手続補正書】特許法第１８４条の８第１項【提出日】平成１１年８月２０日（１９９９．８．２０）【補正内容】請求の範囲１．プロセッサとメモリを有するネットワーク・ノードにおける非同期メッセージ処理方法であって、複数のアプリケーション・タスクについてのアプリケーション・コードを該メモリ中に格納するステップと、複数のプロセス状態をメモリ中に維持するとともに、各プロセス状態を前記アプリケーション・タスクの１つと関連付けて、各プロセス状態をｐｉｄ（プロセス識別子）によって識別可能にするステップと、該ノードが、それぞれ前記ｐｉｄのうち特定の１つを含んだ入力メッセージを受信するステップと、受信された各入力メッセージに対して、該プロセッサが、割り込みなしに、前記ｐｉｄのうち特定の１つと関連付けられたアプリケーション・タスクを該特定のｐｉｄによって識別される特定のプロセス状態のファンクションとして実行するステップと、を具備することを特徴とする非同期メッセージ処理方法。２．さらに該特定のプロセス状態に変更を加えるステップを具備することを特徴とする請求項１に記載の非同期メッセージ処理方法。３．さらに、実行中に、アプリケーション・タスクが出力メッセージを生成するステップと、該アプリケーション・タスクが成功裡に終了した後に、該ノードが出力メッセージを転送するステップと、を具備することを特徴とする請求項１に記載の非同期メッセージ処理方法。４．さらに、インターフェースが入力メッセージを受信するノードの一部を形成して、入力メッセージを受信した順番に従って入力メッセージ・キュー内に格納するステップを備え、該プロセッサは、該関連するアプリケーションを完了まで割り込みなしに実行することによって、該入力メッセージ・キューに格納されたメッセージを読み出して１度に１つずつ処理する、ことを特徴とする請求項１に記載の非同期メッセージ処理方法。５．さらに、アプリケーション・タスクが、生成された順番に従って出力メッセージを出力メッセージ・キューに格納するステップと、該アプリケーション・タスクが成功裡に完了したことに応答して、該アプリケーション・タスクによって生成されたメッセージを転送することができる旨の表示を該メッセージ・キューに格納するステップと、を備え、該インターフェースは、転送することができる旨の表示を含んだメッセージを該出力メッセージ・キューの中から読み出して、１度に１つずつ転送する、ことを特徴とする請求項４に記載の非同期メッセージ処理方法。６．各プロセスは、関連するアプリケーション・タスクを識別するプロセス・タイプ定義を有することを特徴とする請求項１に記載の非同期メッセージ処理方法。７．新しいプロセスのインスタンスを生成するために、該プロセッサは新しいプロセス状態を該メモリ中にそれぞれ割り当てることを特徴とする請求項６に記載の非同期メッセージ処理方法。８．該プロセス状態は、アプリケーション・タスクの開始前に存在した過去の値を持つ複数の状態変数で構成され、該プロセッサが、アプリケーション・タスクによって修正されたすべての状態変数についての過去の値のログをとるステップと、該アプリケーション・タスクが、完遂、中止、又は例外のうちいずれかの形態で終了するステップと、該アプリケーション・タスクが中止又は例外のいずれかの形態で終了した場合に、該プロセッサが、修正された状態変数を過去の値に回復するステップと、をさらに具備することを特徴とする請求項１に記載の非同期メッセージ処理方法。９．アプリケーション・タスクによって修正されたすべての状態変数についての過去の値のログをとるステップは、該プロセッサが、各々の過去の値とそのアドレスをトレイル・スタック・ポインタによって指示されるトレイル・スタックとして割り当てられたメモリ中の場所に保存して、次いで、トレイル・スタック・ポインタを増分することによって実現され、該アプリケーション・タスクが完遂して終了した場合には、該プロセッサは該トレイル・スタック・ポインタをリセットし、該アプリケーション・タスクが中止又は例外終了した場合には、該プロセッサは該トレイル・スタック内の過去の値の各々を該メモリ中の元のアドレスに回復する、ことを特徴とする請求項８に記載の非同期メッセージ処理方法。１０．アプリケーション・タスクによって出力メッセージ・キューに格納されたメッセージは、アプリケーション・タスクが完遂して終了した場合にのみ転送されることを特徴とする請求項８に記載の非同期メッセージ処理方法。１１．入力されるメッセージは、メッセージを送信したプロセスを識別する送信元ｐｉｄを含むことを特徴とする請求項１に記載の非同期メッセージ処理方法。１２．入力メッセージ・キュー及び出力メッセージ・キューは、該メモリ内に保存されて該プロセッサによってアクセス可能であるとともに、該インターフェースによる直接メモリ・アクセスによってアクセス可能であり、プロセスと該インターフェース間のすべての通信とコントロールはこれらキュー経由でのみ行われることを特徴とする請求項５に記載の非同期メッセージ処理方法。１３．各ｐｉｄを対応するプロセス状態の該メモリ中の場所や関連するアプリケーション・タスクの該メモリ中の場所とマッピングするために、プロセス・インスタンス・テーブルが使用されることを特徴とする請求項１に記載の非同期メッセージ処理方法。１４．アプリケーション・タスクの実行はこれらを直接呼び出すカーネル・タスクによってコントロールされ、特定のｐｉｄに関連するアプリケーション・タスクによってメッセージが生成され、続いてノードによって転送され、且つ、入力メッセージに対する応答を期待する場合には、該アプリケーション・タスクがタイマを始動し、アプリケーション・タスクが完了まで実行するとともにカーネル・タスクに対するコントロールを放棄し、カーネル・タスクがこれを周期的に減分するステップと、該タイマが消滅したときに、該カーネル・タスクが該特定のｐｉｄにアドレスされたタイムアウト・メッセージを生成するステップと、をさらに具備することを特徴とする請求項１に記載の非同期メッセージ処理方法。１５．デジタル・ネットワークに接続するためのネットワーク・ノードであって、送られてくるメッセージを受信して入力メッセージ・キューに格納するとともに、送出するメッセージを出力メッセージ・キューから読み出して転送する、デジタル・ネットワークとのインターフェースと、複数のアプリケーション・タスクについてのアプリケーション・コードを格納するように稼動するとともに、複数のプロセス状態を格納するように稼動することができるメモリと、プロセス状態を前記メモリ中に維持し、各プロセス状態をｐｉｄ（プロセス識別子）によって識別し、各ｐｉｄを前記アプリケーション・タスクのうちの１つと関連付け、該入力メッセージ・キューからメッセージを１度に１つずつ受信した順番に従って読み出し、入力メッセージのｐｉｄに関連付けられたアプリケーション・タスクを該入力メッセージのｐｉｄによって識別される特定のプロセス状態のファンクションとして割り込みなしに実行するように稼動することができるプロセッサと、を具備することを特徴とするネットワーク・ノード。１６．前記プロセッサは、さらに、該特定のプロセス状態を変更するとともに、出力メッセージを該出力メッセージ・キューの次に利用可能なバッファ位置に書き込むように稼動することができることを特徴とする請求項１５に記載のネットワーク・ノード。１７．複数のネットワーク・ノードで構成されるデジタル・ネットワークであって、各ネットワーク・ノードは、送られてくるメッセージを受信して入力メッセージ・キューに格納するとともに、送出するメッセージを出力メッセージ・キューから読み出して転送する、デジタル・ネットワークとのインターフェースと、複数のアプリケーション・タスクについてのアプリケーション・コードを格納するように稼動するとともに、複数のプロセス状態を格納するように稼動することができるメモリと、プロセス状態を前記メモリ中に維持し、各プロセス状態をｐｉｄ(プロセス識別子)によって識別し、各ｐｉｄを前記アプリケーション・タスクのうちの１つと関連付け、該入力メッセージ・キューからメッセージを１度に１つずつ受信した順番に従って読み出し、入力メッセージのｐｉｄに関連付けられたアプリケーション・タスクを該入力メッセージのｐｉｄによって識別される特定のプロセス状態のファンクションとして割り込みなしに実行し、該特定のプロセス状態を変更するとともに、出力メッセージを該出力メッセージ・キューの次に利用可能なバッファ位置に書き込むように稼動することができるプロセッサと、を具備することを特徴とするデジタル・ネットワーク。１８．さらに、各ノード上で実行される幾つかのプロセスのｐｉｄを知るプロセス・ネーム・サーバを具備し、前記複数のネットワーク・ノードのうち第１のノードが前記複数のネットワーク・ノードのうち第２のノード上におけるプロセスを識別するために、該第１のノードが該プロセス・ネーム・サーバに対して問い合わせを送信し、該プロセス・ネーム・サーバは該第２のノード上の該プロセスのプロセス識別子を伴なう応答をすることを特徴とする請求項１７に記載のデジタル・ネットワーク。

───────────────────────────────────────────────────── フロントページの続き (72)発明者エリック・ビアマンカナダ国，ケー２ピー２ジー２，オンタリオ，オタワ，1701―71 サマセットストリートダブリュー

Claims

【特許請求の範囲】１．プロセッサとメモリを有するネットワーク・ノードにおける非同期メッセージ処理方法であって、プロセス状態と関連するアプリケーション・コードからなりｐｉｄ（process i dentifier：プロセス識別子）によって識別可能な複数のプロセスをメモリ中に維持するステップと、ノードが入力メッセージを受信するステップと、プロセッサが、受信される各メッセージに対して、メッセージの一部を構成する宛先ｐｉｄを基にして前記複数のプロセスのうちいずれに対してアドレスされているのかを判断し、宛先ｐｉｄに関連付けられたアプリケーション・コードを実行して該メッセージを宛先プロセスのプロセス状態のファンクションとして処理し、必要であれば宛先プロセスのプロセス状態を変更するステップと、アプリケーション・タスクが、実行中に、送出メッセージを生成するステップと、該ノードが送出メッセージを転送するステップと、を具備することを特徴とする非同期メッセージ処理方法。２．さらに、インターフェースが入力メッセージを受信するノードの一部を形成して、入力メッセージを受信した順番に従って入力メッセージ・キュー内に格納するステップを備え、プロセッサは、該入力メッセージ・キューに格納されたメッセージを読み出して１度に１つずつ処理する、ことを特徴とする請求項１に記載の非同期メッセージ処理方法。３．さらに、アプリケーション・コードが、出力メッセージを生成された順番に従って出力メッセージ・キューに格納するステップを備え、該インターフェースは、該出力メッセージ・キューからメッセージを読み出して、１度に１つずつ転送する、ことを特徴とする請求項２に記載の非同期メッセージ処理方法。４．各プロセスは、関連するアプリケーション・コードを識別するプロセス・タイプ定義をメモリ中に格納して有することを特徴とする請求項１に記載の非同期メッセージ処理方法。５．新しいプロセスのインスタンスを生成するために、該プロセッサは新しいプロセス状態を該メモリ中にそれぞれ割り当てることを特徴とする請求項４に記載の非同期メッセージ処理方法。６．該プロセス状態は、アプリケーション・コードの開始前に存在した過去の値を持つ複数の状態変数で構成され、さらに、該プロセッサが、遷移期間中にアプリケーション・コードによって修正されたすべての状態変数についての過去の値のログをとるステップと、該アプリケーション・コードが、完遂、中止、又は例外のうちいずれかの形態で終了するステップと、該アプリケーション・コードが中止又は例外のいずれかの形態で終了した場合に、該プロセッサが、状態変数を過去の値に修正することで回復するステップと、を具備することを特徴とする請求項１に記載の非同期メッセージ処理方法。７．アプリケーション・コードによって修正されたすべての状態変数についての過去の値のログをとるステップは、該プロセッサが、各々の過去の値とそのアドレスをトレイル・スタック・ポインタによって指示されるトレイル・スタックとして割り当てられたメモリ中の場所に保存して、次いで、トレイル・スタック・ポインタを増分することによって実現され、該アプリケーション・コードが完遂して終了した場合には、該プロセッサは該トレイル・スタック・ポインタをリセットし、該アプリケーション・コードが中止又は例外終了した場合には、該プロセッサは該トレイル・スタック内の過去の値の各々を該メモリ中の元のアドレスに回復する、ことを特徴とする請求項６に記載の非同期メッセージ処理方法。８．アプリケーション・コードによって出力メッセージ・キューに格納されたメッセージは、アプリケーション・コードが完遂して終了した場合にのみ転送されることを特徴とする請求項６に記載の非同期メッセージ処理方法。９．入力されるメッセージは、メッセージを送信したプロセスを識別する送信元ｐｉｄを含むことを特徴とする請求項１に記載の非同期メッセージ処理方法。１０．入力メッセージ・キュー及び出力メッセージ・キューは、該メモリ内に保存されて該プロセッサによってアクセス可能であるとともに、該インターフェースによる直接メモリ・アクセスによってアクセス可能であり、プロセスと該インターフェース間のすべての必要な通常の通信とコントロールはこれらキュー経由でのみ行われることを特徴とする請求項３に記載の非同期メッセージ処理方法。１１．各ｐｉｄを対応するプロセス状態の該メモリ中の場所やアプリケーション・コードの該メモリ中の場所とマッピングするために、プロセス・インスタンス・テーブルが使用されることを特徴とする請求項１に記載の非同期メッセージ処理方法。１２．さらに、特定のプロセスによってメッセージが生成され、続いてノードによって転送され、且つ、該特定のプロセスが入力メッセージに対する応答を期待する場合には、該プロセスがタイマを始動して、カーネルがこれを周期的に減分するステップと、該タイマが消滅したときに、該プロセッサがタイムアウト・メッセージを該特定のプロセスに送信するステップと、を具備することを特徴とする請求項１に記載の非同期メッセージ処理方法。１３．デジタル・ネットワークに接続するためのネットワーク・ノードであって、送られてくるメッセージを受信して入力メッセージ・キューに格納するとともに、送出するメッセージを出力メッセージ・キューから読み出して転送する、デジタル・ネットワークとのインターフェースと、プロセス状態と関連するアプリケーション・コードからなりｐｉｄ（process i dentifier：プロセス識別子）によって識別可能な複数のプロセスをメモリ中に維持するとともに、入力メッセージ・キューからメッセージを１度に１つずつ受信した順番に読み出して、メッセージの一部を構成する宛先ｐｉｄを基にして前記複数のプロセスのうちいずれに対してメッセージがアドレスされているのかを判断し、宛先ｐｉｄに関連付けられたアプリケーション・コードを実行して該メッセージを宛先プロセスのプロセス状態のファンクションとして処理し、必要であれば宛先プロセスのプロセス状態を変更するとともに、必要であれば出力メッセージ・キューの次の利用可能なバッファ位置に送出メッセージを書き込むプロセッサと、を具備することを特徴とするネットワーク・ノード。１４．複数のネットワーク・ノードで構成されるデジタル・ネットワークであって、各ネットワーク・ノードは、送られてくるメッセージを受信して入力メッセージ・キューに格納するとともに、送出するメッセージを出力メッセージ・キューから読み出して転送する、デジタル・ネットワークとのインターフェースと、プロセス状態と関連するアプリケーション・コードからなりｐｉｄ（process i dentifier：プロセス識別子）によって識別可能な複数のプロセスをメモリ中に維持するとともに、入力メッセージ・キューからメッセージを１度に１つずつ受信した順番に読み出して、メッセージの一部を構成する宛先ｐｉｄを基にして前記複数のプロセスのうちいずれに対してメッセージがアドレスされているのかを判断し、宛先ｐｉｄに関連付けられたアプリケーション・コードを実行して該メッセージを宛先プロセスのプロセス状態のファンクションとして処理し、必要であれば宛先プロセスのプロセス状態を変更するとともに、必要であれば出力メッセージ・キューの次の利用可能なバッファ位置に送出メッセージを書き込むプロセッサと、を具備することを特徴とするデジタル・ネットワーク。１５．さらに、各ノード上で実行される幾つかのプロセスのｐｉｄを知るプロセス・ネーム・サーバを具備し、前記複数のネットワーク・ノードのうち第１のノードが前記複数のネットワーク・ノードのうち第２のノード上におけるプロセスを識別するために、該第１のノードが該プロセス・ネーム・サーバに対して問い合わせを送信し、該プロセス・ネーム・サーバは該第２のノード上の該プロセスのプロセス識別子を伴なう応答をすることを特徴とする請求項１４に記載のデジタル・ネットワーク。