(57)【特許請求の範囲】
【請求項１】
複数のコンテキスト間において階層呼出し構造を強制するためにカーネルで実行する方法であって、低実行優先順位のコンテキストと高実行優先順位のコンテキストとが供給されたときに、低実行優先順位のコンテキストから高実行優先順位のコンテキストへの呼び出しだけが許可されるものにおいて、
呼び出しコンテキストによって呼び出されるコンテキストの呼び出しを指示するステップと、
前記呼び出しコンテキストの実行優先順位を判定するステップと、
前記呼び出されるコンテキストの実行優先順位が前記呼び出しコンテキストの実行優先順位よりも高い場合、前記呼び出しを前記カーネルにより許可するステップと、
前記呼び出されるコンテキストの実行優先順位が前記呼び出しコンテキストの実行優先順位よりも低い場合、前記呼び出しを前記カーネルにより禁止するステップと、
からなる方法。
【請求項２】
前記方法は、高実行優先順位のコンテキストが低実行優先順位のコンテキストにイベントを通知するものであり、
イベントを定義するステップと、
定義されたイベントを少なくとも１つのコンテキストによって把握すべきことを指示するステップと、
前記イベントを通知するための手段を指定するステップと、
前記イベントを把握しているコンテキストを判定するステップと、
前記イベントを把握しているコンテキストのアドレス空間においてカウンタをインクリメントするステップと、
をさらに含む、請求項１に記載の方法。
【請求項３】
前記方法は、前記コンテキストの実行を前記イベントの発生に基づいてプリエンプティブに行うものであり、
イベントルーチンを定義するステップと、
前記イベントルーチンを前記コンテキストによる前記イベントの把握に結び付けるステップと、
前記イベントが前記コンテキストによって把握されたとき、前記イベントルーチンをスケジューリングするステップと、
前記イベントを把握しているコンテキストの実行優先順位レベルに基づいて、前記イベントルーチンの実行を前記カーネルによりスケジューリングするステップと、
をさらに含む、請求項１または請求項２に記載の方法。
【請求項４】
前記方法は、コンテキスト間に暗黙の並列処理を生成するものであり、
実行すべきものとしてスケジューリングされたイベントルーチンを判定するステップと、
前記イベントルーチンが定義されたコンテキスト内に活動中のスレッドが存在するか否かを判定するステップと、
前記コンテキストが活動中である場合、前記イベントルーチンの実行を遅らせるステップと、
をさらに含む、請求項３に記載の方法。
【請求項５】
前記コンテキスト内に活動中のスレッドが存在しないという判定に応じて、
前記イベントルーチンの実行のためのスレッドを生成するステップと、
前記イベントを把握しているコンテキストと同じ実行レベルの優先順位を前記スレッドに付けるステップと、
前記イベントルーチンの完了時に前記スレッドを破棄するステップと、
をさらに含む、請求項４に記載の方法。
【請求項６】
前記方法は、コンテキスト内におけるコードの並列処理を禁止するものであり、
呼び出しコンテキストと呼び出されるコンテキストを判定するステップと、
前記呼び出されるコンテキスト内に活動中のスレッドが存在するか否かを判定するステップと、
前記呼び出されるコンテキスト内に活動中のスレッドが存在しないことに応じてそのコンテキストの呼び出しを許可するステップと、
活動中のスレッドが存在する場合、前記呼び出しの要求を待ち行列に入れるステップと、
スレッドがコンテキストの実行を完了する時を判定するステップと、
前記コンテキストの完了を待っている呼び出し要求があるか否かを判定するステップと、
前記待ち行列の先頭から前記完了を待っている呼び出し要求を取り除くステップと、
前記呼び出し要求を再開し、呼び出されたコンテキストを活動中であるものとしてマークするステップと、
を含む、請求項５に記載の方法。
【請求項７】
前記方法は、プログラムによる「所有」要求または「把握」要求の使用に基づいて、イベント把握の優先順位を前記カーネルによって記録するものであり、
各把握要求について、コンテキストにより把握レコードを生成するステップと、
前記把握が「所有」要求によるものか否かを判定するステップと、
前記「所有」要求が存在するという判定に応じて、高実行優先順位のコンテキストが低実行優先順位のコンテキストよりも前にくるような優先順位を有する「所有」コンテキストのリストを走査し、前記把握要求を前記待ち行列内の低実行優先順位のコンテキストによる最初の要求の直前に入れるステップと、
前記「把握」要求が存在するという判定に応じて、低実行優先順位のコンテキストが高実行優先順位のコンテキストよりも前にくるような逆の優先順位を有する「把握」コンテキストのリストを走査し、前記把握要求を前記待ち行列内の高実行優先順位のコンテキストによる最初の要求の直前に入れるステップと、
を含む、請求項１〜６のうちのいずれか一項に記載の方法。
【請求項８】
イベントの発生時に、把握コンテキストを判定する方法であって、イベント把握の優先順位が、請求項７に記載の方法に従ってプログラムにより指定されるものにおいて、
当該イベントの「把握」レコードおよび「所有」レコードのリストを探すステップと、
「所有」コンテキストのリストを走査し、当該イベントを発生させたコンテキストよりも低い優先順位を持ち、当該イベントを把握している第１のコンテキストを見つけるステップと、
当該イベントを発生させたコンテキストよりも低い優先順位を持ち、当該イベントを把握している第１のコンテキストが見つからないことに応じて、前記「把握」リストを走査し、当該イベントを発生させたコンテキストよりも低い優先順位を持ち、当該イベントを把握している第１のコンテキストを見つけるステップと、
把握コンテキストを見つけることに応じて、前記リストから前記把握レコードを削除し、前記把握レコードのアドレス空間内のカウンタをインクリメントするステップと、
からなる方法。
【請求項９】
前記方法は、イベント把握をプログラムによって優先順位付けするものであり、コンテキストによるイベントの把握をプログラマ構文を使用して指定するステップを含み、前記プログラマ構文は、
（１）イベント発生時に、該イベントを把握しているコンテキストよりも高い優先順位のコンテキストが存在しない場合に、該コンテキストによって把握されるイベントと、
（２）イベント発生時に、該イベントを把握しているコンテキストよりも低い優先順位のコンテキストが存在しない場合に、該コンテキストによって把握されるイベントと
を両方とも使用することができる、請求項２に記載の方法。
【請求項１０】
前記呼び出しを許可するステップは、あるコンテキストからそのコンテキスト自体への再帰的な呼び出しを許可するサブステップをさらに含む、請求項１〜９のうちのいずれか一項に記載の方法。
【請求項１１】
前記あるコンテキストからそのコンテキスト自体への再帰的な呼び出しを許可するサブステップは、再帰的であることを明示的に宣言されたルーチンに対してのみ再帰的コンテキスト呼び出しを許可するサブステップをさらに含む、請求項１０に記載の方法。
【発明の詳細な説明】
発明の背景
発明の技術分野
本発明は一般にソフトウエア・アーキテクチャに関し、より詳しくは、ソフトウエア・アプリケーションにおいてリアルタイムの会話を制御するカーネルを使用する方法に関する。
背景技術の説明
ソフトウエア・アプリケーションは伝統的にリアルタイム・アプリケーションと非リアルタイム・アプリケーションに分けられてきた。非リアルタイム・アプリケーションは、スプレッドシート、ワープロ、グラフィック設計プログラム等のような、従来の単一ユーザ・プログラムに含まれる。一定の時間に依存する性能基準を満足させなければならない物理装置を制御するソフトウエア・アプリケーションは伝統的にリアルタイム・アプリケーションであると考えられており、それは飛行制御システム、工業処理制御プログラム等のアプリケーションを含むものである。
ソフトウエア・アプリケーションをリアルタイムと非リアルタイムのカテゴリに分割することは、通常そのアプリケーションによって要求される動作が、制御の単一スレッドの中で実行されるべきかどうかに基づいている。従来より、制御の様々なスレッドに関して別のローカル記憶域を提供するために、リアルタイム・アプリケーションのクラスに関してマルチタスキングが用いられている。マルチタスキング・カーネルは、複数の制御のスレッドの生成、及び同期のためのメカニズムを提供し、それ以外はタスク、又はプロセスとして知られている。制御のスレッドのそれぞれに関するローカル記憶域は通常、スタックの形態をとる。スタックは、通常ほとんどのコンピュータの命令セットに提供されるメカニズムである。スタックによって、複数のコード・シーケンスからのサブルーチン呼び出しが可能になる。呼び出しコード・シーケンスの戻りアドレスがスタック上にプッシュされ、即ち記憶される。サブルーチンが完了すると、そのアドレスがスタックからポップされ、即ち除去され、呼び出しコード・シーケンスからのコードの実行が続けられる。リアルタイム・アプリケーションを作成するために使用されるマルチタスキング・プログラミング環境は複数のスタックを提供する一方、従来のプログラミング環境は単一スタックを提供する。マルチタスキングは通常、リアルタイム・プログラミングに必要と考えられているが、ソフトウエアは各タイプのプログラミング環境内でリアルタイム・イベントに応答するよう構築されうる。
より洗練されたソフトウエア・アプリケーションを作成することは、リアルタイム・アプリケーションと非リアルタイム・アプリケーションの間の従来の制限を不鮮明にする。洗練された単一ユーザ・アプリケーションは、ユーザ入力を待つ間バックグラウンド・プロセシング（スプレッドシートの再計算のような）を実行するかもしれない。ここで、マルチタスキング、及び非マルチタスキング環境両方におけるソフトウエア開発において、解決が必要な一般的問題は、いかにして、ユーザ入力、外部イベント、又はデータ・アクセスのようなある条件を、他の目的のための処理命令が続けられている間で「待機する」ことができるソフトウエア命令を書くか、つまり、いかにソフトウエア・アプリケーションによって実行されている様々な処理やタスクに関して複数の、制御のスレッドを提供するかということである。
最も単純な待機の問題に対する解決策は、一時点で１つの条件に関してのみ待機するようなプログラムを構築することである。例として、単純な抵当償却プログラムが、利率、支払額等の入力をユーザに促し、そのそれぞれの値の入力を待って次の値の入力を促す、制御の単一スレッドで書かれうる。この単純なプログラム構造は、現存のソフトウエア・アプリケーションの多くの部分に対し十分なものである。しかし、アプリケーションの性質が、複数で非同期に発生する条件を処理する必要のある場合には、この構造では十分でない。
単一スタック環境用に書かれたプログラムは、何度も起こるリアルタイム・イベントをいくつかの異なる方法で処理することができる。リアルタイムの条件を処理するための一つの可能な単一スタック・プログラム構造は、イベントのある種のソート、またはメッセージ・ベースのカーネルの使用を必要とし、非同期条件に応答してコードのタスク指名(dispatch)を処理する。こうしたアプリケーションに関しては、アプリケーションの主要部は、様々なメッセージやイベントを再入可能に処理できなければならないイベント、又はメッセージ・ハンドラからなる。マイクロソフトのウインドウズ、またはアップルのマッキントッシュのオペレーティング・システムが、このタイプのプログラミング環境を提供しているので、このプログラム構造は、グラフィカル・ユーザ・インタフェース・ベースの多くのアプリケーションでは代表的なものである。様々なカーネルのアーキテクチャは、メッセージの待ち行列化、及び／又はメッセージ処理の優先順位付けを含むことができる。
アプリケーションとオペレーティング・システムの間でのメッセージングに基づく、現在使用されている全てのカーネル・アーキテクチャは、２つの顕著な問題点を有する傾向が強い。図1Aは、システム・カーネル93からのメッセージを介してそのカーネルと対話しているアプリケーション91と、そのアプリケーション91からコールするアプリケーション・プログラミング・インタフェース97との間の基本的な関係を概略的に示す図である。第１の顕著な問題は無制限の再帰の問題である。カーネル93からのメッセージＭが、アプリケーション91のカーネル機能Ｆのコールの結果生成され、カーネル機能Ｆが別のメッセージＭを生成する場合、このシーケンスがそれ自身を無限に繰り返す可能性があり、最終的にスタックを物理制限まで使い果たすことになる。
第２の問題は非再入コードとして知られ、通常は無制限の再帰より大きく関係する。前述の例において、カーネル機能Ｆは、その機能の最初の呼び出しが終了する前に、アプリケーション91から２度コールされうる。その機能が再入するようコード化されていない場合、これはプログラミング・エラーとなる可能性がある。更に、アプリケーション91内のメッセージ・ハンドラ機能も、この再入の影響を受ける。無制限の再帰の問題と非再入コードの問題はまた、コードの個々の単位が実行プロセスの間で互いに呼び出しを行うアプリケーションの内部構造に関連して発生する。現在、アプリケーション内、またはアプリケーションとオペレーティング・システムの間で、こうした問題が発生しないことを保証する唯一の方法は、アプリケーション開発者による細心のプログラミングである。
従って、プログラマから無制限の再帰の問題と非再入コードの問題を避けるための負担を取り除く、これらの問題を抑止するためのメカニズムを提供することが望ましい。
問題の第２のクラスは、リアルタイム・イベントを処理するために、複数の非同期プロセスを処理する必要がある場合に発生する。単一スタック環境におけるアプリケーションは、他の全てのイベント及びメッセージ処理を遅延させる好ましくない影響を有することなく、単に特定のイベント、又はメッセージを待つように構築することができない。非同期で発生する条件を確実に処理しようとする、全ての単一スタック実施に共通の一つの好ましくない結果は、これらのアプリケーションが状態駆動型でなければならないことである。状態駆動型アプリケーションは、変数を設定することによって現在のプログラム状態を記憶し、メッセージを受信した際に、これらの変数の状態がアプリケーションによって取られる動作を判定する。状態駆動型アプリケーションにおける問題は、条件の待機を処理するように適切に書くことが非常に困難であり、それによって無制限の再帰と非再入コードの発生する可能性が高くなることである。従って、条件の待機を処理する面での大きな利便性から、マルチタスキングが使われる。
マルチタスキングによって、コードは多数でバラバラの待機操作で構成できるが、この柔軟性は複雑さが増すという代償を備えている。再帰及び再入という２重の問題に加えて、マルチタスキングの実例は、危険地域(critical section)の複雑さを増加させ、デッドロックを招く。デッドロックは、２つのプロセスが実行を継続するために、互いに他方のプロセスによる動作を待つ場合に起きる。危険地域は、複数のスレッドによって現在実行されればエラーとなる可能性のある、コードの個別セグメントである。これらの問題は当業者には周知であり、こうした問題を回避する技法は、多くの研究の対象となってきた。しかし、再入と再帰の問題のために、こうした問題の最終的な検出及び訂正は、プログラマによる注意深いコーディングに依存する。
ソフトウエア・バグという用語は、プログラミングの問題とエラーのある実行時条件の発生の両方を示すためによく使用される。正しくないコード・シーケンスに対する、より正確な用語はプログラム障害(program fault)である。プログラム不良(program failure)は、コードの実行中のプログラム障害を表現するものである。
無制限の再帰、非再入、デッドロック、及び危険地域の問題は、一時的な不良を引き起こす。これらの問題は、それらがアプリケーションの単一実行の際、又は複数の実行の際でさえ、必ずしも発生するものではなく、むしろ、典型的には繰り返された実行の後で、アプリケーションの単位の間での会話が特定の方法で行われる場合にのみ発生する。
これらの４つのタイプのプログラミング・エラーは、周期的エラーと呼ばれるプログラミング・エラーのクラスに属する。これらの周期的エラーは、ソフトウエア・アプリケーションの呼び出し構造に対しトレースされうる。呼び出し構造は、アプリケーションの単位の間の関係を順序づけ、コールするものである。呼び出し構造は有向グラフによって示される。図1Bは、６つのコード単位ＡないしＦを含むソフトウエア・アプリケーション91の呼び出し構造の、有向グラフを示す。ある単位から別の単位に向かう矢印は、実行中に発信単位が受信単位に１つ以上の手順コールを呼び出したことを示す。ここで、図1Bにおいて、単位Ａから単位Ｂ、更に単位Ｅに命令実行が進みうるが、単位Ｄから単位Ｃへの命令の進行は明らかにない。
伝統的設計のソフトウエア・アプリケーションは、下向きの矢印によって示されている手順の呼び出しを有する、純粋に階層的なアプリケーションに非常に近いことが多い。しかし、非同期イベントを処理する必要性の高まりによって、この階層的な呼び出し構造は徐々に移動され、単位間のコールが次第に非階層的になってきた。これは、単位Ｅから単位Ａへのコール103のような上方向コールによって示される。この上方向コールは、有向グラフ内で周期（コール101、109、103）を作り出す。あるノードからそれ自身に戻る、矢印の方向に従う経路がある場合、有向グラフ内には周期が存在する。図1Bの有向グラフに示された呼び出し構造においては、上方向コール103が経路、または単位Ａがそれ自身を呼び出すことのできる手順コールの組を生成するので、周期が存在する。コール101、109、及び103の間の図1B内の周期は、非再入と無制限の再帰に２重に関連する。同様に、デッドロックの可能性を検出することもでき、ここでは単位Ｄ及び単位Ｅの間のコール115及び117を有する周期によって示され、各単位は一方を実行中にコールする。単位Ｂ及び単位Ｃは、それらが論理的には同時に単位Ｅをコールできないので、危険地域となりうる。周期を生成するのは、主として呼び出し構造内の上方向コールの存在である。呼び出し構造内にある周期は、周期的エラーが存在することを例示するものではなく、こうしたバグがアプリケーションの実行の間に起こりうることを示している。
周期のない、有向グラフが、非周期有向グラフとして知られており、それは純粋な階層化グラフを示す。純粋な階層化呼び出し構造は周期エラーの可能性を除去するが、リアルタイム性能に関して必要な非同期イベントを処理するための伝統的な技法の使用を妨げる。それは、これらのイベントが現在、単一スタック環境の上方向コールで、又はマルチタスク環境の優先順位ベースの強制排除(preemption)によって処理されているためである。こうしたタイプのプログラミング方法は純粋に階層的な構造を強制せず、従って、周期エラーの可能性を許容することになる。現在、リアルタイム・アプリケーションのアプリケーション開発に適用可能で、一時的な不良を防止する、共用プログラミング方法論はない。更に今日、使用時にこうしたプログラミング方法論を強いるメカニズムはない。
前述のことから、アプリケーション・プログラミングに非同期イベントをリアルタイムに処理するための動作を可能にしつつ、そのプログラムの呼び出し構造において純粋な階層を作成する方法を使用して、ソフトウエア・アプリケーションが開発されることは、そのソフトウエア・アプリケーションの動作にとって有利なことである。階層構造でソフトウエア・アプリケーションを単に開発することは、周期的なエラーの発生を防止するには十分であるが、実行時にその構造を強いる外部メカニズムがない場合、その階層呼び出し構造から導かれる利点を保証する道はない。
従って、実際の実行時操作で階層呼び出し構造を強要し、それによって周期的なエラーを除去するという形で階層呼び出し構造の利点を保証する、単一スタック、または複数スタック・プログラミング開発環境のどちらにおいても使用できるソフトウエア・カーネルを提供することが望ましい。
更に、呼び出し階層の強制は、強制排除コードを処理するための従来のメカニズムを妨げるので、強制階層呼び出し構造と共存しながら、強制排除と並行処理を提供するカーネルを提供することが好ましい。こうしたメカニズムは、アプリケーション内で単一の制御のスレッドを保持する機能を備えることが好ましい。
本発明の概要
本発明は、アプリケーションを含む構成要素（コンテキスト）の間の階層呼び出し構造を強制する方法、アプリケーション内で制御の単一スレッドを保証する方法、及びイベント・ルーチンを含むコンテキストの優先順位に基づいてイベント・ルーチンの優先順位付けされた実行を提供する方法からなる。階層呼び出し構造を強制する方法の実施例は、呼び出しコンテキストによる呼び出されたコンテキストの呼び出しを示すステップ、呼び出しコンテキストの実行優先順位を判定するステップ、及び呼び出されたコンテキストの実行優先順位が呼び出しコンテキストの実行優先順位より高い場合に、その呼び出しを許可するステップを含んでいる。各コンテキストが、関連する実行優先順位を有しているので、より低い実行優先順位を有するコンテキストだけが、より高い実行優先順位を有するコンテキストを呼び出すことができる。このことは、上述のような、様々な周期的エラーにつながる上方向コールを防止する。この方法は、複数スタック、または単一スタック・プログラミング環境のどちらでも実施可能で、またマイクロプロセッサの命令セットに含むこともできる。
更に本発明の方法を洗練するために、呼び出しコンテキストの実行優先順位を判定するステップは、コンテキストがそれ自身を呼び出しているかどうかを判定し、呼び出されたコンテキストの優先順位が呼び出しコンテキストの優先順位より高いかどうかを判定するステップを含む。これらのステップは、呼び出しコンテキストの性質に基づいて、その呼び出しの代替的な処理を提供する。更に本発明の方法を洗練するために、制御の戻りを呼び出しコンテキストに対して許容するために、呼び出しコンテキストのインジケータを記憶し、呼び出されたコンテキストの実行優先順位に基づいて呼び出されたコンテキスト内のイベント・ルーチンに関する実行優先順位を確立し、及び呼び出されたコンテキストの実行レベルを上げるステップを更に含む、呼び出しを許可するステップが提供される。これらのステップは、再帰レベルの制御、及び現在活動している様々なコンテキストの実行優先順位を確立するためのメカニズムを提供する。
本発明はまた、アプリケーションが多くのコンテンツを含む場合、コンテキスト内に制御の単一スレッドを強制する方法も提供する。その方法は、ルーチンを実行するためのコンテキストを判定し、ルーチンを実行するためのコンテキスト内に制御の活動スレッドが存在するかどうか判定し、次に、そのコンテキストが制御の活動スレッドをもはや持たなくなるまで、そのコンテキストによってルーチンの実行を遅らせる。そのコンテキストが制御の活動スレッドをもはや持たなくなったとき、そのルーチンの実行は続けられる。
本発明はまた、アプリケーション内の多くのコンテキスト内のスケジュールされたイベント・ルーチンの実行を、コンテキスト内のイベント・ルーチンをスケジューリングすることによって優先順位付け、次に、そのコンテキスト内に制御の活動スレッドがあるかどうかを判定する。そのコンテキスト内に制御の活動スレッドがない場合、本発明の方法は、コンテキストの実行優先順位と同じ実行優先順位を、スケジュールされたイベント・ルーチンを実行するためのタスクに割り当てる。次に、スケジュールされたイベント・ルーチンを実行するためのタスクが起動される。本発明の方法を洗練するために、イベント・ルーチンは、イベントの発生とそのイベントをコンテキストによって処理する要求を示すことによってスケジュールされる。次にこの方法は、そのイベントを処理するためのコンテキストを判定し、処理するためのコンテキスト内にイベント・ルーチンがある場合、方法はタスクによる実行に関し、そのイベント・ルーチンを指定する。そのタスクは、処理するためのコンテキストの実行優先順位に基づいて実行優先順位が割り当てられるので、そのタスクに関連づけられスケジュールされた全てのイベント・ルーチンは、その実行優先順位のレベルで実行される。
【図面の簡単な説明】
図1Aは、ソフトウエア・アプリケーションとメッセージング・システム・カーネルの間の関係を示す図である。
図1Bは、多くのコンテキストを含むソフトウエア・アプリケーションの呼び出し構造を示す図である。
図２は、本発明のシステムのブロック図である。
図３は、アプリケーションの呼び出し構造を示す図である。
図4A、及び4Bは、プリエンプティブ複数スタック環境におけるEnter_ContextとExit_Contextルーチンのフローチャートである。
図5A、及び5Bは、ポーリング単一スタック環境におけるEnter_ContextとExit_Contextルーチンのフローチャートである。
図６は、ソフトウエア・アプリケーションの呼び出し構造を示す図である。
図7A、及び7Bは、Single_EventとRaise_Eventルーチンのフローチャートである。
図7C、7D、及び7Eは、内部起動(Internal Raise)、及び処理配置ルーチンのフローチャートである。
図８は、複数スタック及び単一スタック・カーネルの両方におけるCapture_Eventルーチンのフローチャートである。
図９は、複数スタック及び単一スタック・カーネルの両方におけるCapture_As_Eventルーチンのフローチャートである。
図10は、複数スタック及び単一スタック・カーネルの両方におけるUncapture_Eventルーチンのフローチャートである。
図11A、及び11Bは、プリエンプティブ複数スタック環境におけるWait_Event、及びCheck_Eventルーチンのフローチャートである。
図12A、及び12Bは、ポーリング単一スタック環境におけるWait_Event、及びCheck_Eventルーチンのフローチャートである。
図13は、本発明のカーネルの内部Check_Eventルーチンのフローチャートである。
図14A、及び14Bは、複数スタック及び単一スタック・カーネルの両方におけるSchedule_Eventルーチンのフローチャートである。
図15A、及び15Bは、プリエンプティブ、及びポーリング・カーネル両方のTask_to_Dispatch_Events、及びPolling_to_Dispatch_Eventルーチンのフローチャートである。
図15Cは、プリエンプティブ複数スタック・カーネルのDispatch_All_Eventsルーチンのフローチャートである。
図16は、プリエンプティブ、及び複数スタック・カーネル両方のDispatch_Eventルーチンのフローチャートである。
図17は、アプリケーションの呼び出し構造を示す図である。
発明の好適実施例の説明
本発明の様々な実施例を説明する前に、本発明の特徴と動作を理解する上で類似が有用である。
コンピュータ・プログラムは抽象的な問題を解決するための命令の集合として見ることができる。同様に人は、組織化された問題を解決するために、様々な職種に分割される。ファースト・フード事業の店舗を管理する問題を考えると、組織化された問題の要件は言葉で指定される。例えば、ドライブスルーの窓のサービスは、中の顧客のサービスより優先すべきである、顧客サービスの平均時間は３分を越えてはならない、フレンチフライは30秒計が時間切れになる間に熱油から取り出さなければならないなどである。
組織化された問題の要件を満たす、多くの異なる方法の様々な組織化のタスクがある。この店舗の効率は、いかに効果的にこれらのタスクが雇用者に分割されるかにかかっている。ビジネスは通常、要件を満たすタスクの組織化のためにいくつかのシステムを判定し、各雇用者に、それらのタスクに関して彼らの特定の義務を定義した書かれた命令を提供する。これらの書かれた命令は、コンピュータ・プログラムにおける書かれた命令と類似する。雇用者は互いにあるタスクを実行するよう要求することを含む、様々な仕事を実行するのに必要な情報を交換するために、互いの間で通信することができる。同様に、コンピュータ・プログラムは、互いに通信してある機能（例えば、リアルタイム制御、スプレッドシート計算等）を実行するコード・エンティティ（例えば、オブジェクト、モジュール、タスク）の集合として見ることができる。
人間の通信とコンピュータの命令実行の間の１つの大きな違いは、個々のコード・エンティティが与えられた全ての命令を実行しようとすることである。ファースト・フードの類似例では、店員がマネジャが処理の空くのを待つとすると、マネジャはどれだけのバーガー・パティをフリーザから取り出すかをコックに尋ねて待ち、コックは店員が特別の注文を受けるのを待つ。各人は別の人間の動作を、それらが割り当てられていた命令から少しだけずらされて、デッドロックを解消するよう実行されるまで待つので、人間はすぐ、この周期的なデッドロック条件に気づく。しかし、コンピュータ・プログラムは、この待機状態の周期の中に永久に居座る可能性がある。
ここで、ファースト・フード店の効率と信頼性を、以下のシステムを実装することによって向上させるように決定された事業管理を仮定する。
・全ての雇用者は数字のランクに割り当てられる。
・同じランクの雇用者は、互いに話すことはできない。
・ランクの高い雇用者がランクの低い雇用者にタスクを実行するよう命令できる。
・ランクの低い雇用者はランクの高い雇用者との通信を起動できないが、高いランクの雇用者によって持ち出された特定の質問には答えることができる。
・ランクの低い雇用者は、彼らが高いランクの雇用者への値の情報を有していると思う場合に、手を挙げることによって高いランクの雇用者に信号を送ることができる。
これらの条件は、雇用者に階層呼び出し構造を強いるものであり、彼らが他の雇用者の情報やサービスを使用できる場合、及び時を制御する。このシステムと一致する命令セットが書かれうることは明白であるが、人間に適用する場合に、こうしたシステムが非効率的で非生産的となることにはほとんど疑いの余地はない。
しかし、ソフトウエア・アプリケーション内のコード・エンティティに適用した場合、こうしたシステムはコード・エンティティに関して階層呼び出し構造を強要し、それによって上述の周期的なエラーを効果的に取り除く。本発明はこうした階層呼び出し構造を強いるためのメカニズムを提供する。このことは、コンテキストが別のコンテキストを呼び出す毎に、呼び出されたコンテキストが、呼び出しコンテキストより高い実行優先順位（即ちランク）を有するかどうかを判定することによって行われる。より高い実行優先順位を有している場合、呼び出されたコンテキストはその手順を実行することを許され、それによって制御の活動スレッドを得る。呼び出されたコンテキストがより低い実行優先順位であった場合、試みられた呼び出しは禁止された上方向コールであり、その呼び出しは成功しない。
呼び出しレベルにおけるコード・エンティティ間に階層を適用し、強制することによって、プログラマはコードを開発する間、再入、再帰、デッドロック、及び危険地域に関する考慮から解放され、それによって開発プロセスがスピードアップされる。本発明は、カーネル操作の使用によってこの呼び出し階層を強制する。カーネルは通常、ソフトウエア・システムの最下層に属する。本発明は、既存のオペレーティング・システム・カーネルと非常に類似した１組のメカニズムを提供するものなので、カーネルとして記述されうる。しかし、現存のオペレーティング・システム・カーネルとは異なり、本発明のカーネルは、呼び出し構造が階層的な、厳正な内部コード構造に適合するためにそのカーネルを使用するアプリケーションを要求する。更に、カーネルは、この階層フレームワーク内で非同期イベントを処理するためのイベント・メカニズムを提供し、制御の単一スレッドを強制し、及び操作のプリエンプティブ処理を提供する。
ここで、図２を参照すると、本発明の一実施例の環境のブロック図が示されている。本発明は、マイクロプロセッサ201、キーボード207、ディスプレイ203、プリンタ209、及びアプリケーション開発と実行時実行の間の両方でソフトウエア・アプリケーション215を記憶するためのメモリ211を含むコンピュータ・システムで実施される。ソフトウエア・アプリケーション215は、単一スタックまたは複数スタック環境のどちらかの操作であることができ、非同期イベントのリアルタイム処理に関して設計される。メモリ211は、本発明を実施するカーネル213も記憶する。プロセッサ201はバス229を介してこのメモリ211と通信する。
メモリ211内に記憶されたソフトウエア・アプリケーション215は、それぞれが選択された他のコンテキストからのコール又は呼び出しに応答して、任意の数の操作または手順を実行する、多くのコンテキスト、又はコードの単位からなる。より詳しくは、コンテキストは、本発明の階層強制メカニズムを実行させるコード・ステートメント内に含まれているコードの単位である。操作の間に、新しいコンテキストが必要に応じて追加され、破棄される。各コンテキストは、そのコンテキストが手順を実行するためにコールされているかを示すためのフラグとして機能する入れ子カウンタを有する。各コンテキストはまた、他のコンテキストから伝えられた条件に応答するためのイベント・ルーチンも含む。そのイベント・ルーチンの制御、及び順序づけは、以下で図７ないし図16に関連して説明する。
アプリケーション215の呼び出し構造は、アプリケーション215のコンテキスト間の関係をコールする手順の組である。アプリケーション215では、本発明で使用するよう最適に開発された呼び出し構造は、常に階層的である。このことは、呼び出し構造の有向グラフの中に周期がないことを意味している。階層呼び出し構造301の例が図３に示されている。図３は、有向グラフで、図２のソフトウエア・アプリケーション215に関する階層呼び出し構造301を示している。図３では、各コンテキストは、より低レベル（つまり高優先順位）またはそれ自身にのみ手順コールを行う(303)。呼び出し構造301が階層であるため、より高い優先順位を持つ、より低いレベルのコンテキスト（図の底部近くに示されている）から、より低い優先順位を有する、より高いレベルのコンテキストへの手順呼び出しである、上方向コールは存在しない。上方向コールを禁止することによって、有向グラフ内に周期を持たない呼び出し構造301が得られ、従って、デッドロック、無制限の再帰、危険地域、または非再入の周期的なエラーの可能性が除去される。
概念のレベルでは、各コンテキストは、非同期イベントを処理するリアルタイム・アプリケーション内の実行の別のスレッドとして考えられる。ここで、コンテキスト呼び出しは、ある手順から他の手順への要求として考えられる。本発明で使用されるプログラミング方法論は、制御の１つのスレッドだけが任意の所与の時間におけるコンテキストの範囲内において活動中であることを必要とし、本発明がこの要件を強制するためのメカニズムを提供する。コンテキストの範囲は、コンテキストで定義された手順全てを含む。これらの条件が破られない限り、実際のコンテキスト間の呼び出しは、現在使用されているいくつかの形態のうち１つを取ることができる。従って、本発明はアプリケーション215の階層呼び出し構造301を強制する様々な実施例を有する。
開始コンテキスト(Enter Context)、及び終了コンテキスト(Exit Context)操作
階層呼び出し構造の実行時チェックを強制するために、カーネル213は、Enter_ContextとExit_Context操作に関係のある、２つのタイプの呼び出しを実行し、これらの操作はコンテキストの呼び出しと戻りの間にプロセッサ201によって実行される。これらの操作は、より高い優先順位、即ち低レベルのコンテキストがより低い優先順位、即ち高いレベルのコンテキストを直接呼び出すのを防止することによって、階層的な呼び出しをカーネル213が強制することを可能にする。ここで、図4A、及び4Bを参照すると、プリエンプティブ・複数スタック環境で実施されるEnter_ContextとExit_Context操作のフローチャートが示されている。
図4AはEnter_Context操作400を示す。このEnter_Context操作400はカーネル213内に常駐し、コンテキストが別のコンテキストを呼び出す場合、プロセッサ201によって実行される。最初に、プロセッサ201は、そのコンテキストがそれ自身を呼び出しているかどうかを判定する(401)。コンテキスト内のコールは許可され、再帰をもたらす。無制限の再帰は、それがコード自体の中で簡単に識別可能で、再帰コール数の制限を備える入れ子カウンタで容易に処理することができるので、コンテキスト内のコールにとっては重要な問題ではない。従って、コンテキストがそれ自体を呼び出している場合、コンテキストの入れ子カウンタがインクリメントされる(413)。このフラグは更に、そのコンテキストが制御の活動スレッドを有することを示す。そのコンテキストが自身を呼び出さないが、別のコンテキストを呼び出す場合、プロセッサ201は、呼び出されたコンテキストの優先順位が呼び出しているコンテキストの優先順位より高いかどうかを判定する(403)。このステップは、それが上方向コールが試みられているかどうか、即ち、図1Bに示すように、高い優先順位の低レベル・コンテキストが低い優先順位の高レベル・コンテキストを呼び出そうとしているかどうかをチェックするので、呼び出し構造の階層を維持する。上方向コールが試みられている場合、プロセッサ201はそのコールをエラーとし、アプリケーション215に伝える(409)。
呼び出しが順当に、低優先順位コンテキストから高優先順位コンテキストへのものである場合、プロセッサ201はスタック上にある呼び出しコンテキストに対するポインタをメモリ211内に記憶し、プロセッサ201が制御のスレッドを後で呼び出しコンテキストに戻すことができるようにする。次にプロセッサ201は、コールされた手順の優先順位を、呼び出されたコンテキストの優先順位にセットする(407)。このことによって、プロセッサ201は、図７、及び図15ないし図16に関連して更に説明されるように、異なる優先順位のコンテキスト内で、コールされている様々な手順をスケジュールすることができる。
プロセッサ201は次に、コンテキストが入力され、タスクを実行するよう活動中であることを示すセマフォ、またはそれと同様のものを、呼び出されたコンテキストから待つ(411)。コンテキストによるタスクの実行は更に、図15Aに関連して以下で説明される。
最後に、プロセッサ201はその呼び出されたコンテキストの入れ子カウンタをインクリメントし(413)、それはコンテキストが制御の活動スレッドを有することを示す。そのコンテキストが最も高い優先順位を有しているとすると、呼び出されたタスク、又は手順は、呼び出されたコンテキストによって実行される。そのコンテキストの実行が終了すると、Exit_Context操作417がプロセッサ201によって実行される。
要するに、Enter_Context操作が、コンテキストの各呼び出しで発生し、呼び出されたコンテキストが呼び出しコンテキストより高い実行優先順位を有する場合に、呼び出しの許可だけがされる。呼び出しが許可されると、追加ステップが、実行をコンテキストに戻す間、呼び出しコンテキストに関する情報を維持し、また呼び出されたコンテキストが再帰、又は再入を記録する間に呼び出された回数も記録する。更に、更なる呼び出しが許可される前に、呼び出されたコンテキストからセマフォ、又はそれと同等のものを待つことによって、操作が制御の単一のスレッドのみを保証する援助を行う。
図4BはExit_Context操作のフローチャートである。この操作は、各コンテキストの操作の終了の際に実行される。最初に、プロセッサ201が、呼び出されたコンテキストの入れ子カウンタをデクリメントし(419)、これは１つのレベルの実行が終了したことを示している。プロセッサ201は、その入れ子カウンタが０に達したかどうかをテストし(421)、これはそのコンテキストが全ての呼び出しを完了したことを示す。０でない場合、プロセッサ201は制御を呼び出されたコンテキストに戻し(429)、実行を続けるよう許可する。呼び出されたコンテキストの入れ子フラグが０である場合、プロセッサ201はそのコンテキストのイベント・ルーチンをタスク指名する(422)。このステップは、そのコンテキストに関連づけられたイベント・ルーチンの全てが、現在の呼び出しの完了前に終了することを保証する。このステップは図16に示すルーチンに従って実行される。プロセッサ201は次に、コンテキストのエントリ・セマフォを開放し(423)、このことはそのコンテキストがもはや制御の活動スレッドでないことを示している。プロセッサ201は、記憶されたスタックに関するポインタを用いて、呼び出しコンテキストを復元し(425)、現在実行中のタスクの優先順位レベルを現在のコンテキスト、即ち呼び出しコンテキストの優先順位レベルにセットする(427)。
Enter_Context400、及びExit_Context417操作はまた、ポーリング、単一スタック環境のカーネル213で実施されうる。このような操作のフローチャートが図5A、及び5Bに示されている。これらの操作の使用は、機能的にはプリエンプティブな実施と同じであり、基本的な差は、カーネル213が、呼び出されたコンテキストが呼び出しコンテキストより高い優先順位を有するかどうかを判定した(507)後に、イベントにポーリングを行う(505)ことである。ポーリングとプリエンプティブ環境の間の差は、更に以下で説明する。ポーリング操作は、図15Bに関して以下で説明される。
実行時に階層呼び出し構造を強制するためのカーネル213は、本発明で使用されるシステムの実施要件に従って、様々な形態で実施可能である。Enter_Context、及びExit_Context操作は、コンテキストの呼び出しと戻りのそれぞれについて実行されなければならず、カーネル213の好適実施例は、アプリケーション215を実行するプロセッサ201の命令セットにこうした操作を提供するものである。この実施例において、アプリケーションが終了すると、コンパイラがこれらの操作を実行するために必要なコードを完成する。代替案として、コンテキスト操作はプロセッサ201によって使用されるオペレーティング・システム内に含むことができ、ソフトウエア、又はファームウエアのどちらかで提供される。どちらにしても、プログラマは、アプリケーション開発において手でコンテキスト操作をコード化する必要はない。
本発明のカーネル213はまた、ここで記述されたプログラミング方法論に基づいて開発されたコードからコールされうるルーチンのライブラリとして見ることもできる。カーネル213はここで、図２に示すように、アプリケーション215のアドレス空間のどれかにリンクされうる。別の代替実施例では、本発明で使用されるプログラミング方法論を直接支援するプログラミング言語によって、及びカーネル213の操作を達成するためのプログラミング言語の構文を使用することによって、カーネル213を容易に使用することができる。こうした言語の疑似コードが、本発明のカーネル操作に関連して以下で例示される。
最後に、プロセッサ201、オペレーティング・システム、又は新しいプログラミング言語の命令セットのどれにも直接的な組み込みがなされない場合、本発明はコード・プロセッサ227を使用して既存のコンピュータ・システムに実装されうる。コード・プロセッサ227は、既存のcfrontプロセッサと同様に動作し、例えば、C++のコードをＣプログラミング言語に変換する。この実施例では、コード・プロセッサ227はプログラミング言語抽象化(abstractions)を既存のプログラミング言語、好適にはC++に統合する。本発明はC++言語の使用を必要としないが、C++は、コードの簡潔さとプログラミング・エラーに対する保護のために、好適なプログラミング言語である。カーネル213、及びコード・プロセッサ227としての本発明の実施は、常にコンテキスト操作をアプリケーション手順コールに統合することによって、Enter_Context、及びExit_Context操作の省略を防ぎ、それによってプログラマが手でこれらの操作を提供しなくてもいいようにする。
コード・プロセッサ227によって、プログラマは、プロセッサ227によって処理される時に、Enter_Context、及びExit_Context操作をアプリケーション・コードにリンクさせる、様々なプログラミング言語の拡張を使用することができる。これらの操作の関数プロトタイプが資料Ａに示されている。疑似コードの例は以下に示す。
0003863917.tif 000002
この疑似コードにおけるキーワードContextは、C++のクラス・キーワードと同様である。キーワードServiceは、New_Messageメソッドが他のコンテキストに呼び出されようとしていることを示すものである。キーワードServiceがないと、プロセッサ227はそのメソッド宣言を、クラス定義のセクション：private内に移動する。コード・プロセッサ227は先行するコードを得て、以下のC++出力を生成する。
0003863917.tif 000003
includeステートメントは通常、言語抽象化によって参照される望ましいコード表現を完成させるために、コード・プロセッサ227によって使用されるべきコード・ライブラリ内のヘダー・ファイルを識別する。コード・プロセッサ227は、K_の抽象化が定義されることを保証するように、事前コンパイルされたコード内にkernel.hxxヘダー・ファイルを含む。キーワードContextは、Message_Boxオブジェクトに関するクラスがK_Contextクラスから導出されるべきであることを示すものであり、カーネル・ヘダーに定義されている。K_Context_Protector変数、dummyはそのコンストラクタ内の現在のthisポインタを取る。dummy変数のコンストラクタは単に、K_Enter_Contextカーネル操作を実行し、そのデストラクタはK_Exit_Context操作を実行する。そのコードは、両方の操作がコンテキストの開始とコンテキストの終了で実行されることを保証する。
イベント
これまで、本発明の一態様として、カーネル213を使用した階層呼び出し構造の強制が記述されてきた。本発明の更なる態様は、こうした階層呼び出し構造にプリエンプティブな性質を提供することである。
図1Bに関して前述したように、より低レベルのコード単位から、より高レベルの単位への上方向コールが周期的なエラーの可能性を作り出す。本発明で使用されるプログラミング方法論は、こうしたクラスのプログラム不良を排除するために上方向コールを禁止する。しかし、プリエンプティブ、またはポーリング環境のどちらかで非同期イベントのリアルタイム処理を提供するために、より低レベルのコンテキストがより高レベルのコンテキスト実行を起動できるメカニズムを提供することが依然として必要とされている。
従って、本発明によって、重要性のあると思われるより低レベルのコンテキストからの条件の発生を、より低レベルのコンテキストに伝えるための、イベント・メカニズムが提供される。呼び出し構造でイベントを使用すると、コンテキスト間で送信されるパラメータが常に、より高レベルのコンテキストによって起動される、要求時駆動型プログラム構造となる。イベント・メカニズムは、より高レベルのコンテキストの中のコードの実行をスケジューリングする方法を提供する。このコードの実行は、高レベルのコンテキストが、低レベル、即ちより高い優先順位のコンテキストの完了に続いてイベントを処理することによって、その要求を処理できるまで延期される。イベント・メカニズムの様々な要素に関する関数プロトタイプは、資料Ａに示されている。
好適実施例では、イベントは、Eventステートメントの使用によって定義されうる。コンテキストの範囲内に定義されたイベントは、そのコンテキストに対してはローカルであると考えられ、コンテキストの範囲外に定義されたイベントは、グローバルな範囲を有すると考えられる。
0003863917.tif 000004
この疑似コード・プログラミングの例は、イベントを参照するためにC++構文を使用して、イベントoopsの定義を例示する。
イベントの最も単純な実装は、Deviceコンテキストで割り当てられる構造内にイベントに関する変数を割り当てることである。変数のアドレスは、カーネル213によって実行されるイベント操作に関するハンドルを提供する。この実装は、アプリケーション215内にリンクされるよう意図したカーネル実装にとっては十分である。
プログラミング・イディオムという用語は、プログラミング言語の特徴を使用する技法について述べるために使用されてきた。本発明の一実施例に有用なプログラミング・イディオムの１つは、Event_Handleの使用である。コンテキストはイベントを定義し、そのイベントを把握し、そしてそのイベントを後で伝える(signal)１つ以上のコンテキストにハンドルを送信する。あるカーネル実装では、Event_Handleは単に、イベント変数のアドレスである。より複雑なカーネル実装では、イベントの生成がカーネル自身のアドレス空間内の記憶域の割り当てにつながることがあり、Event_Handleが単に、カーネル213が適切な操作を判定するために解釈する抽象キーとなる。イベントのハンドルを得るための疑似コードの例を以下に示す。
Event_Handle eh;
eh=Event_Handle(oops);
カーネル213は、操作が直接そのイベントに関して行われるように、構文的にEvent_Handlesに関して操作を行う。
イベントの通知(signaling)と起動(raising)
本発明は、その様々な実施例において、イベントを「通知(signal)」し、及び「把握(capture)」するためのメカニズムを提供する。通知は通常、コンテキストが、他のコンテキストに対して重要である可能性のある条件を、別のコンテキストに伝えていることを示すためのメカニズムを指す。把握は通常、通知された条件が伝えられるべきことを示すコンテキストによるメカニズムを指す。ファースト・フードの店舗に話を戻すと、通知メカニズムは個々の高いランクの雇用者に、より低いランクの雇用者が、ある高いランクの雇用者との通信を要していることを知らせる。把握メカニズムは、高いランクの雇用者が、店員が通知を行ったときにマネジャに伝達を行うといった、マネジャに対する伝達の条件をセットできるようにする。異なるランクの多くの異なる雇用者が、他の雇用者からの通信を受信しようとしている場合、雇用者間の通信をスケジュールする必要がでてくる。高いランクの雇用者は彼らの要求をタスク指名するので、より低いランクの雇用者は彼らの義務を実行できる。本発明はこの通信を強制し、アプリケーション215のコンテキストに関する構造を実行するメカニズムを提供する。
本発明は所与の時間において、コンテキストの範囲内の制御の活動スレッドを１つだけ要求するので、通知、及び把握メカニズムは、カーネル213が、制御の活動スレッドを管理し、タスクのスケジューリングを遅らせることができるようにし、従って、プリエンプティブ、又はポーリング・マルチタスキングを可能にする。こうしたメカニズムは、本発明で用いられるプログラミング方法論でコンパイルを行うソース・コードの開発を可能にするのに十分な表現力を有する。一般に、イベント・メカニズム内の複雑さの増大と、イベントを処理するためのソース・コード内での余分な要求はトレード・オフの関係にある。
より詳しくは、カーネル213によって、イベントの発生を通知するための２つのメカニズム、Signal_EventとRaise_Event関数が提供される。この実施例では、イベントを把握するための２つのメカニズム、Capture_EventとSeize_Event関数も提供される。
イベントは、次のどちらかの方法で通知される。
Signal(oops);
Raise(oops);
Signal()関数は、コンテキスト・クラスに関して定義されたC++メソッドであり、コード・プロセッサ227によってSignal_Event関数に変換される。同様に、Raise()関数は、コード・プロセッサ227によってカーネル関数Raise_Eventへのコールに変換されるメソッドであり、それは、イベントを起動するコンテキストを識別する余分なパラメータをとる。これらの関数は、範囲の判定の際においてのみ異なり、カーネル213によって使用され、通知されたイベントを処理するための把握コンテキストを見つけだす。Signal_Event関数はグローバルな範囲を有する。アプリケーション215内の任意のコンテキストはそのイベントを把握できる。Raise_Event関数は、以下に示すように、より制限された範囲を有する。
１．上位の（高レベル、低優先順位の）コンテキストだけが、別のコンテキストによって起動されたイベントを把握できる。
２．そのイベントを起動しているコンテキスト内に制御の活動スレッドが存在する場合、「コール連鎖」の一部であるコンテキストだけがそのイベントを把握できる。
３．そのイベントが活動呼び出しを有していないコンテキストによって起動された場合、イベントの範囲は、そのイベントを起動したコンテキストより低い優先順位のコンテキスト全てに制限される。
コール連鎖は、現在のスタックに関する戻りアドレスを有するコンテキストからなると考えられる。図６は、多くのコンテキストからなるソフトウエア・アプリケーション215に関する呼び出し構造601を示す。図６では、経路<Ａ、Ｂ、Ｅ、Ｇ>を含むコール連鎖603が示されており、これは、コンテキストＡ、Ｂ、Ｅ及びＧを結合する太い矢印によって示されている。コンテキストＧが、ＡからＧまでの活動コール連鎖がある間にイベントを起動した場合、このコール連鎖内のコンテキストだけがイベントを把握する資格がある。コンテキストＧが同じイベントを通知する場合、アプリケーション215内の任意のコンテキストがイベントを把握できる。上述の範囲のルールは、以下に示す図7Dに関連して記述されるLocate_Contextルーチン内で使用される。把握コンテキストの範囲を洗練するためのコール連鎖の使用は、既存の例外メカニズムと同様である。
ここで図7A、及び7Bを参照すると、コンテキストによる通知と起動に関する、ルーチンの実施例のフローチャートが示されている。
Signal_Event操作700によって、コンテキストは、アプリケーション215のあるコンテキスト内で特定の条件が発生したことを示すことができる。一旦通知が行われると、その条件の伝達（把握）に関して以前に登録されているコンテキストの１つが、イベントを処理するものとして指名され、そのイベントは、その実行優先順位に従う処理コンテキストによって実行される。図7Aでは、Signal_Event操作700の一実施例が、その操作のパラメータとして渡されたイベント・ハンドルが、カーネル213のアドレス空間に対してローカルかどうかを判定する(701)ことから実行を開始する。ローカルであれば、そのイベント・ハンドルがローカル・イベントへのポインタに変換される(705)。ローカルでなければ、そのイベントはアプリケーション215の外部のルーチンに依存し、そのイベント・ハンドルが、オペレーティング・システム、及びネットワーク上の他のアプリケーションで利用できるようにする待ち行列内に配置される(703)。従って、あるリモート・イベントが通知されていることを示す内部イベントに対するポインタが、ローカル・イベントに対するポインタの代わりに使用される(707)。イベント・レコードが、イベント・ポインタの１つ、及びそのイベントの優先順位が最も高い優先順位にセットされる設定を行うフラグを使用して生成される(709)。イベント・レコードは、通知、又は起動されているイベントに対するポインタ、通知、又は起動するコンテキストの優先順位、及び範囲のルールに使用するためのフラグを含む。通知されたイベントがグローバルなコンテキストであるため、範囲のフラグは、通知されたイベントに対して「偽」と設定される。これは、そのイベントにグローバルな範囲を与え、アプリケーション内のどのコンテキストによっても把握が可能となる。イベントの優先順位が最も高い値にセットされるので、イベントは、それを処理することができるコンテキストで最も優先順位の高いものによって処理される。次にイベント・レコードは、通知コンテキストの優先順位に基づいてイベントを処理するための適当なコンテキストを判定する、カーネル213の内部操作に渡される(711)。このルーチンは更に、図7Cに関連して以下で記述される。
図7Bでは、プリエンプティブ、及びポーリング環境の両方で使用されるRaise_Event操作713の一実施例のフローチャートが示されている。Signal_Event同様、Raise_Eventは起動コンテキストのコール連鎖内の把握コンテキストに優先を与えるために使用される。イベント・レコードは渡されたイベントからのポインタを使用して生成される(717)。しかし、そのイベントにSignal_Event操作700内で最も高い優先順位を割り当てる代わりに、そのイベントを起動するコンテキストの優先順位に、そのイベントが割り当てられる。このことは、起動コンテキストより低い優先順位のコンテキストだけがそのイベントを処理することを保証する。このステップは、上述の第１の範囲のルールの実装を助ける。次にカーネル213は、そのイベントを起動したコンテキスト内で活動中のEnter_Context操作があるかを、そのコンテキストの入れ子カウンタの状態に基づいて判定する(719)。コンテキストが活動中のEnter_Contextを有し、従って制御の活動スレッドを有する場合、範囲のルールが使用中で、従って、コール連鎖内のコンテキストだけがそのイベントを処理できることを示すようにフラグがセットされる(721)。このことは第２の範囲のルールの実装を助ける。制御の活性スレッドがない場合、フラグは偽にセットされる(723)。次に、イベント・レコードは、イベント内部起動ルーチンに渡され(725)、そのルーチンから戻り値を得た際(745)に、その値が通知／起動コンテキストに戻される(727)。この戻り値は、イベントを処理するコンテキストが見つかったかどうかを示す。
図7Cは、イベント内部起動ルーチン731の実施例のフローチャートを示す。ここで、そのルーチンは、そのデフォルトの戻り値に偽をセットし(733)、次に、通知された／起動されたイベントを処理する適当なコンテキストを上述の範囲のルールに従って判定するために、カーネル213の内部のLocate_Handling_Contextルーチンにイベント・レコードを渡す(735)。その後続のルーチンが完了すると、カーネル213は、イベントを処理するためのコンテキストが識別されているかどうかを判定する(737)。識別されている場合、その戻り値は真にセットされ(739)、見つけられたコンテキストのアドレス空間内のイベント・カウンタがインクリメントされる(741)。このカウンタはコンテキストがイベントを把握した場合に、以下に述べるようにして確立される。このカウンタは、イベントの発生数を記録する。
イベント・カウンタは、そのイベントが処理された回数を判定するためにテストされる(743)。そのカウンタが丁度１にインクリメントされた場合、そのイベントは現在の呼び出しの間において、以前に処理されたことがなく、それは、そのイベントを処理するためのイベント・ルーチンをスケジュールするのに必要である。カウンタが１より大きい場合、そのイベントを処理するためのイベント・ルーチンは既にスケジュールされ、そのメソッドはそのイベント・ルーチンの実行回数の記録だけを必要とする。
そのイベントに関するイベント・ルーチンをスケジュールするために、カーネル213は、通知された／起動されたイベントに関連づけられたイベント・ルーチンがあるかどうかを判定する(751)。イベント・ルーチンがある場合、内部スケジューリング・ルーチンをコールすることによって、カーネル213はそのイベント・ルーチンをスケジュールする(753)。このスケジューリング・ルーチンは、図14Aに関して以下で更に記述される。イベント・ルーチンがない場合、カーネル213は、通知されたイベントに関するエイリアス・イベントがあるかどうか判定し(755)、そのエイリアスを参照するようイベント・レコードを修正する(757)。イベント・レコードは再び、Locate_Handling_Contextに渡され、そのエイリアス・イベントを処理するためのコンテキストを更に見つけだす。イベントを処理するためのコンテキストが見つからない場合(739)、戻り値（偽にセットされている）が戻される(745)。
図7Dは、Locate_Handling_Contextルーチンの一実施例のフローチャートを示す。このルーチンはカーネル213の内部で動作し、イベントが起動されているときに、上述の範囲のルールを使用して、イベントを処理するのに適したコンテキストを判定するのに使用される。第１に、カーネル213は、範囲のルールを使用するための範囲のフラグが真にセットされるかどうかを判定する(763)。真にセットされている場合、範囲のルールは以下のように使用される。
テスト・コンテキストは起動コンテキストにセットされる(765)。範囲のルールは、テスト・コンテキストがコールの連鎖の頂部にあるかどうか判定する(769)ことによって適用される。頂部にない場合、テスト・コンテキストはテスト・コンテキストを呼び出したコンテキストにセットされ(771)、ここでテスト・コンテキストは、テスト・コンテキストが所有(seizing)コンテキストのリスト上にあるかどうかを判定するテストを行う(773)。リスト上にない場合、ステップ769は繰り返される。テスト・コンテキストが所有コンテキストである場合、それはコールしているルーチンに戻される(783)。テスト・コンテキストがコールの連鎖の頂部であった場合、カーネル213はそのテスト・コンテキストが依然、起動コンテキストにセットされているかどうか判定し(775)、セットされている場合は、そのコールの連鎖内には１つのコンテキストだけが存在するので、ルーチンは空(null)コンテキストを返す(781)。テスト・コンテキストが別のコンテキストにセットされている(771)場合、そして、そのコンテキストが把握コンテキストのリスト上にある(777)場合、それはコーリング・ルーチンに戻される(783)。そうでない場合、テスト・コンテキストは、コール連鎖内で次に呼び出されたコンテキストにセットされる(779)。このループは、そのイベントを把握するようセットされた最も低い優先順位、即ち最も高いレベルのコンテキストが見つけられるまで繰り返される。
範囲のルールを使用する例が示されている。図６に示されるコール連鎖が現在活動中であり、コンテキストＧがイベントを起動していると仮定する。更に、コンテキストＢだけがイベントを把握しており、即ちコンテキストＧからの通知の伝達を要求すると仮定する。コール連鎖が活動中で、イベントが起動されているので、範囲フラグがRaise_Eventルーチン内にセットされる(721)。Locate_Handling_Contextルーチンでは次に、テスト・コンテキストがコンテキストＧにセットされる(765)。これには、コール連鎖の頂部であるかのテストがなされる(769)。コンテキストＡがコール連鎖の頂部であるため、テスト・コンテキストはコンテキストＥにリセットされ(771)、それはコンテキストＧの呼び出し者となる。テスト・コンテキストは、それが所有コンテキストのリスト上にあるかどうか判定するためにテストされる(773)。コンテキストＡがイベントの所有を示す場合、それは処理コンテキストとして戻される(783)。この例の目的のために、そうでないと仮定すると、ステップ769でテストが繰り返され、今はコンテキストＥであるテスト・コンテキストが再び、コール連鎖の頂部にない。従って、テスト・コンテキストがコンテキストＢにセットされる(771)。コンテキストＢは同様に、所有コンテキストのリストに含まれるかに関するテストがなされる。コンテキストＢがイベントの把握を示すので、ループは、コール連鎖内の各コンテキストがテストされるまで繰り返される。従って、テスト769のループ、セットを行う771、及びテストを行う773は、イベントを処理するための起動コンテキストより上の、最も高い優先順位、即ち最も低いレベルのコンテキストを見つけるために使用される。
起動されたイベントを所有するコール連鎖内にコンテキストがない場合、テスト775からセット779へのループは、そのイベントを処理するコンテキストが見つけられるまで、コール連鎖を下方向に横断する。従って、コンテキストＡから始めて、カーネル213は、コンテキストＡがイベントの把握のためにリストされたかどうか判定する(777)。この例において、コンテキストＡがリストされず、コンテキストＢがリストされている場合、コール連鎖内で次に呼び出されるコンテキストは、テスト・コンテキストとしてセットされる。ここで、コンテキストＢがイベントを把握するよう示されていると仮定すると、それは戻されることになる(783)。コンテキストＢは、たとえコンテキストＥもまたそのイベントを把握するよう示されていても、コンテキストＢがより低い優先順位、即ちより高いレベルのコンテキストであるため、処理コンテキストとして選択される。
ここで図7Dを参照すると、イベントが通知される（フラグがステップ709で偽にセットされる）か又は、カーネルが起動コンテキスト内に制御の活動スレッドがないことを判定する(719)ので、範囲のルールのアプリケーションに関するフラグが、ステップ763で偽にセットされる。どちらにしても、カーネル213は、最初に最も高い優先順位の所有コンテキストを見つけようとし、次に最も低い優先順位の把握コンテキストを見つけようとする、前と意味的に同じステップに基本的に従うことによって、適当な処理コンテキストを判定する。
従って、カーネル213は、起動されたイベントを所有するよう示されたコンテキストのリストを横断し(785)、起動コンテキストの優先順位より低いもので、最も高い優先順位を有するコンテキストを判定する。このようなコンテキストが見つかった場合(787)、処理コンテキストがこのコンテキストにセットされ(789)、この識別されたコンテキストが所有コンテキストのリストから除去され(791)、全ての同じレベルの優先順位のエントリの後ろに再インサートされる。次にコンテキストがコールしているルーチンに処理コンテキストとして戻される(800)。適当なコンテキストが見つからない場合(787)、カーネル213は起動されたイベントを把握するようセットされたコンテキストのリストを横断し(793)、起動コンテキストの優先順位より低いもので、最も低い優先順位を有するコンテキストを見つけようとする。こうしたコンテキストが見つかった場合(799)、処理コンテキストとしてこのコンテキストにセットされ(797)、このコンテキストが同様に把握コンテキストのリストから除去され(799)、全ての同じ優先順位のコンテキストの後ろのリストの端部に再インサートされる。次にその処理コンテキストがコールしているルーチンに戻される(800)。適当な処理コンテキストが見つからない場合、空コンテキストがまたコールしているルーチンに戻される(781)。
上述のイベント・メカニズムは、これらがイベントの発生以外の情報を提供しないという点で、現存の同様の有名なメカニズムと異なっている。結果として、イベントを「把握」するより高いレベルのコンテキストが、そのイベントを処理するのにふさわしい動作を実行できる。
把握(capturing)、及び所有(seizing)
Signal_Event、及びRaise_Event関数は、処理コンテキストを判定するための更なる考察の対象である。これらの考察は、イベントが「把握」される方法に依存する。イベントの把握は、コンテキストがイベントの発生を伝達されるべきであることを、カーネル213に登録する方法である。通知されるか又は、起動されることによってイベントが発生すると、把握コンテキスト全てが判定され、そのイベントに関連づけられたカウンタが、各把握コンテキストのアドレス空間内でインクリメントされる。
イベントは把握されるか又は、所有されうる。イベントの把握に関する構文は、以下の形態のうち１つを取る。
Capture(oops);
Seize(oops);
イベント把握の意味論は、把握コンテキストのアドレス空間内のカウンタのインクリメントを含む。このインクリメント操作は、極めて小さいものであるという保証がなされる。イベントを把握する各コンテキストによって、イベントに対して割り当てられた個別のカウンタがあり、イベントの把握に関する目標コンテキストが、コンテキスト構造に関して課せられた階層の範囲のルールを使用することによって解決されうる。把握コンテキストによって続けて取られる動作は、その把握コンテキスト内に関連するイベント・ルーチンがあるかどうかに依存する。この把握コンテキストがイベントを起動するコンテキストより低い優先順位のものである場合、カーネルによって、このイベント・ルーチンの実行が遅延される。
本発明の好適実施例において、イベントの把握に関するデフォルト・ルールは、そのイベントを最も高い意味レベルで把握するようにできるものである。例えば、ホストのオペレーティング・システムの一部としてカーネルが実施される場合、アプリケーション・プログラムがオペレーティング・システム・シェルによって支援されうる。プログラム・エラー条件が論理的にグローバルなイベントとして表現される。カーネルによって定義されたDIVISION_BY_ZEROイベントがアプリケーション・プログラムによって把握される場合、そのアプリケーション・プログラムは、この条件を適切に処理できる。しかし、アプリケーション・プログラムとオペレーティング・システム・シェルが両方、DIVISION_BY_ZEROイベントを把握する場合、より高いレベルのコンテキスト（そのアプリケーション）が実際にそのイベントを処理する。イベント把握に関してカーネル内に定義されたルールが２つの同等のレベルの（同じ優先順位の）コンテキストの間で解決されない場合、カーネルはイベントのラウンドロビン分配を提供する。
Seize()メソッドは意味的には、Capture()メソッドと同じである。しかし、これは、デフォルトの最も高い意味レベルの把握ルールを却下する。O/SシェルがDIVISION_BY_ZEROイベントを所有することになる場合、イベントはアプリケーションによって見られることはない。所有と把握は両者とも、Capture_Eventカーネル関数を呼び出すコンテキスト・クラスに関して定義されるC++メソッドとして実装される。この関数に対するパラメータは、イベントが所有されるかどうか、又は把握されるかどうかを判定するために使用される。把握停止(Uncapture)メソッドは、イベントの把握を停止するために使用される。
ここで図８を参照すると、プリエンプティブ、及びポーリング・マルチタスキング・カーネルの両方でイベントの把握と所有をするためのフローチャートが示されている。Capture_Eventルーチンは、コンテキストが別のコンテキスト内の条件を通知されるべきであることを示すアプリケーション215のコンテキストのうちの１つによってコールされる(801)。オプションで、イベント・ルーチンに対するハンドル、及びコンテキストがそのイベントを所有、又は把握するものであるかどうかを示すフラグを含むパラメータは、そのルーチンに渡される。新しい把握レコードは、コンテキストのアドレス空間内に割り当てられ(803)、ここで、カウンタはそのイベントに関して初期化され、把握コンテキストはスタック上に記憶される。カーネル213は次に、イベント・ルーチンが把握されるべきイベントに関して指定されているかどうかを判定する(805)。指定されている場合、その把握コンテキスト内のそのイベント・ルーチンに対するポインタは、把握レコード内に記憶される(807)。一旦ポインタが記憶されると、あるいは、１つもイベント・ルーチンが指定されていない場合、カーネル213は、そのコンテキストが既にそのイベントを把握、または所有しているかどうか判定する(809)。コンテキストがそのイベントを把握、又は所有している場合、そのコンテキストは把握されたイベントの把握コンテキストのリストから除去され(811)、前の把握レコードが削除される。このことは、１時点で所与のイベントに対して１つの把握レコードだけが存在することを保証する。どちらの場合にしても、カーネルは次に、その所有フラグが、イベントが所有されていることを示すようセットされているかどうかを判定する(813)。そのイベントが所有されている場合、所有されたイベントのカーネルのリストは、そのイベントを把握することができる最も高い優先順位の、即ち最も低いレベルのコンテキストを識別するために横断される。新しい把握レコードは、所有されたイベントのカーネルのリストの先頭に挿入され(821)、このイベントが最も高い優先順位の処理を受ける。このイベントが所有されておらず、むしろ把握されている場合、把握レコードのリストは、そのイベントを処理することができる最も低い優先順位で、最も高いレベルのコンテキストを判定するために横断され(815)、そして再び、新しい把握レコードが把握レコード・リストの先頭に挿入される(817)。このことによって、最も低い優先順位のコンテキストが、そのイベントを処理することができる。一旦、そのイベントが把握、又は所有されると、制御がカーネル213に戻る(823)。
図９はCapture_As_Eventルーチンのフローチャートを示している。このルーチンは、イベント・ルーチンがパラメータとして渡されているかどうか判定し(805)、次に、このイベントに対するポインタを記憶する(807)代わりに、エイリアス・イベントに対するハンドルが把握レコードに記憶される(905)ことを除いて、基本的にCapture_Eventルーチンと同じである。このルーチンは次に、Capture_Eventルーチンと同様の方法で処理を続ける。
コード・プロセッサ227は、いくつかの異なるイベントの把握を、ローカル・コンテキストの範囲内に定義された単一イベントとして支援する。例えば、アテンション(attention)イベントを定義する３つの変数ｘ、ｙ、及びｚがあるとすると、これらのイベントは以下のように共通のイベントとして把握され、処理されうる。
Capture(x.attention, y.attention, z.attention, Attention);
Attentionが、把握コンテキストに対してローカルに定義されたイベントであるとすると、後続のC++コードがプリプロセッサによって生成される。
Capture(Attention);
Capture_As_Event(x.attention, Attention);
Capture_As_Event(y.attention, Attention);
Capture_As_Event(z.attention, Attention);
カーネル213はまた、制御のスレッドを、イベントの把握を停止することによってコールしているコンテキストに戻すために、イベントの把握停止も提供する。図10はUncapture_Eventルーチンのフローチャートを示す。カーネル213は最初に、把握停止イベント・ルーチンを呼び出し(1001)、把握コンテキストの把握レコードが、コンテキスト及び、最も直近に処理されたイベント、又はイベントのエイリアスを含む把握レコードを見つけるために横断される(1003)。把握レコードが見つかった場合(1005)、それは削除され(1007)、コンテキストが把握コンテキストのリストから除去される。上記以外の場合、所有コンテキストのリストが、コンテキスト及びイベントに一致する把握レコードを見つけるために横断される(1009)。そのレコードが見つかった場合(1011)、コンテキストが所有コンテキストのリストから除去され(1013)、把握レコードが削除される。制御は次に、カーネル213に戻される(1015)。
処理(Handling)イベント
コンテキストによって把握されたイベントは多くの異なる方法で処理されうる。イベントの通知、又は把握に加え、コンテキストはイベントのチェックも待つ可能性がある。最初に、コンテキストは、イベントが発生し（かつ把握され）たかどうか「チェック」しうる。図11Bはイベントのチェックのフローチャートを示す。コンテキストはカーネル213によってチェック・ルーチンを呼び出す(1113)。カーネル213は、任意の数のイベントの状態を判定するための、所望のイベントに対するポインタをパラメータとして使用する内部チェック・ルーチンを実行し(1115)、そのフロー・チャートは図13に示されている。カーネル213は次に、そのイベントのチェックの状態を示す値を戻す(1117)。
内部チェック・ルーチンは図13に示されている。ここで、カーネル213はそこに渡されたイベントの数をカウントし(1301)、各イベントが適当なカーネル・イベント記号を持つことを確認する。カーネルは、パラメータ全てが満足なものであり、イベントの数が０より大きいかどうか判定する(1303)。これらの条件のどれかが偽である場合、カーネルはエラーで戻る(1305)。そうでない場合、カーネル213は、渡されたイベントの数が１であるかどうか判定する。１である場合、テストは、イベントに関連づけられたカウンタが０にセットされているかどうか判定し(1313)、それが０である場合、その値を返す(1319)。カウンタが１にセットされている場合、その値は返され(1321)、そのイベント・パラメータに関連づけられたイベント・ルーチンがタスク指名され(1323)、そこで、制御がカーネルに戻る。イベントの数がステップ1307において１より大きい場合、コールしているコンテキストのイベント・リストは、非ゼロのカウンタを有してカーネルに渡されたイベントを見つけるために横断される(1309)。こうしたイベントが見つかった場合(1311)、そのイベントはイベントのリストの先頭から除去され、最後に置かれる。戻り値がパラメータのインデックス番号にセットされ(1317)、そのイベントのイベント・ルーチンが実行される(1323)。
チェック・イベント・ルーチンは以下のCheck節を使用することによって呼び出される。
0003863917.tif 000005
前述の疑似コードの例において、oopsイベントの発生が把握されていない場合、Check節は０で戻る。これが非ゼロで戻る場合、イベントの把握に関連づけられたカウンタがデクリメントされる。Check節はまた、コード・プロセッサ227によって以下のように複数のイベントをテストするよう支援されたプログラミング環境でも使用されうる。
0003863917.tif 000006
この構文は、C++、及びCで用いられるswitchステートメントの構文に似ている。switchステートメントと異なり、caseはイベント・タイプ（例えばx.attention)の評価を行う表現で構成されうる。これは、コード・プロセッサ227が以下のC++コードをCheck節の処理後に生成するので可能となる。
0003863917.tif 000007
Check節のcaseの使用は、Check_Eventルーチンから戻るイベントに関連づけられたカウンタのデクリメントも行う。Check節のcaseの使用は、以下のプログラミング例と対照的である。
0003863917.tif 000008
case節の結果は前述のコード例と同じものになる。しかし、Check_Eventカーネル関数は、複数の重要なイベント間のラウンドロビン選択を提供するよう保証される。対照的に、前述のコードの例は常に、x.attentionイベントより、oopsイベントの発生のチェックに優先を与え、従って、複数の非同期イベントのテストにおける使用には不適格である。
イベントをチェックすることが、コンテキストがイベントの発生を処理する唯一の方法ではない。wait節は意味的にCheck節と同じであり、Wait_Eventカーネル・ルーチンに対するコールを生成する。図11Aは、Wait_Eventルーチンのフローチャートを示す。Wait_EventルーチンとCheck_Eventルーチンの唯一の違いは、カーネル213が、Wait_Eventルーチンに渡されたイベントが発生していない(1105)（戻り値が０）かどうか判定する場合に、Wait_Eventルーチンが、指定されたイベント（１つ又は複数）が発生するまで、更なる実行によるコンテキストをブロックする(1107)ことである。コンテキストの実行をブロックした結果はカーネルの実装のタイプに依存し、本発明のカーネルの単一スタック実装と、複数スタック実装の間の違いに関連して以下で更に説明される。
図12A及び12Bは、ポーリング単一スタック環境におけるWait_EventとCheck_Eventルーチンの実装を示している。Check_Eventルーチンは機能的には同じで、Wait_Eventルーチンはイベントに対してポーリングを行い(1207)、その待たされたイベントが把握されていないときに、最も高い優先順位のコンテキスト内でイベント・ルーチンをコールする(1205)。
イベント・ルーチン、プリエンプティブでかつ優先付けされたコードの実行
コンテキストの範囲内に定義されたイベントは、関連するイベント・ルーチンを有する可能性がある。このイベント・ルーチンは、本発明のカーネルを使用してプリエンプティブで優先付けされた、コードの実行のための手段を提供し、それによって、プリエンプティブ・マルチタスキング環境で必要とされる非同期イベントのリアルタイム処理が可能となる。イベント・ルーチンの宣言は以下の疑似コードで例示される。
0003863917.tif 000009
イベント・ルーチンの優先付けされた実行は、そのルーチンが定義されるコンテキストの優先順位レベルに基づいている。全てのコンテキストは、それらに関連づけられた実行優先順位を有し、全ての呼び出しは、より低い優先順位のコンテキストからより高い優先順位のコンテキストに対してでなければならない。イベントが、現在実行しているコンテキストより高い優先順位のコンテキストによって把握されている場合、カーネル213は、そのコンテキストに関して定義されたイベント・ルーチンを実行するために、より低い優先順位のコンテキストの実行を強制排除することができる。
イベント・ルーチンの実行は同期であることも、また非同期であることも可能である。コンテキストの範囲内の制御の活動スレッドがなく、ルーチンがカーネルによる実行に関してタスク指名される場合、そのイベント・ルーチンの非同期の実行が発生する。複数スタック環境では、このタスク指名プロセスは、イベント・ルーチンを実行するタスク（制御の個別スレッド）の選択を含むことができる。単一スタック環境では、カーネルはルーチンの単一コールを行うことができる。コンテキスト内に制御の活動スレッドがある場合、イベント・ルーチンの実行はWait節、またはCheck節のどちらかが続くまで、又は現在活動中のスレッドがコンテキストの範囲を終了するまで遅延される。
イベント・ルーチンの同期実行は、コンテキストの中の活動スレッドが明白にイベントに関するCheck節、又はWait節を実行する場合、発生する。この場合、前に議論した節の意味論に加えて、関連するイベント・ルーチンが、Check節、又はWait節から戻る前に実行される。イベント・ルーチンの実行は、コンテキストに関する制御の現在スレッド内で発生しうる（即ち、同期的に）。
イベント・ルーチンはパラメータなしでなければならず、戻り値を持たない（空の戻り値を持つ）。カーネル213は、Capture_Event関数に対し、パラメータとして任意の関数ポインタの指定を可能にするが、それは、イベントの宣言と実行されるべきルーチンの間の言語レベルの結合を強いるために、カーネル213によって支援されるプログラミング方法論を意図するものである。このため、コード・プロセッサ227は、イベント・ルーチンで宣言されているイベントが把握された場合に、適切なルーチンの自動割り当てを支援する。別のコンテキスト内で定義されたイベントが発生した場合に、イベント・ルーチンを実行することが、時として好ましい場合がある。任意のルーチンをこの外部で宣言されたイベントの把握に割り当てることができるが、好ましいプロセスは、関連するルーチンで、把握しているコンテキストに対してローカルに新しいイベントを宣言し、その外部イベントをこの新しく定義されたイベントとして把握することである。これは、以下の疑似コードの例で示される。
0003863917.tif 000010
一般的に上述したようなイベント・メカニズムの実施例は、図14ないし図16のフローチャートに示されている。ここで、図14Aを参照すると、本発明に従うプリエンプティブ複数スタック・カーネル213においてイベントをスケジュールするルーチンの一実施例のフローチャートが示されている。Schedule_Eventルーチンは、イベントを処理するためのコンテキストがカーネル213によって見つけられた後に、内部イベント起動ルーチンからコールされる(753)。一旦コールされると、カーネル213はイベント・ルーチンに対するポインタを含む、スケジュールされているイベント・ルーチンに関する要素をコンテキスト・ルーチン・リストに追加する(1403)。コンテキストによるイベント・ルーチンの非同期実行を提供するためには、そのイベント・ルーチンが実行される場合に、コンテキスト内に制御の活動スレッドが存在できない。従って、カーネル213は、コンテキストの入れ子フラグが０より大きいかどうか、又は制御の活動スレッドが既にそのコンテキストに割り当てられているかどうかを判定する(1405)。どちらの場合でも、Schedule_Eventルーチンは内部イベント起動ルーチンに制御を戻し、そのイベントはそのスケジュール・リストの最後に追加される。それ以外の場合、コンテキストが現在活動中でない場合、カーネル213はタスク・プールからタスクを選択し(1407)、利用可能な空でないタスクがあるか判定する(1409)。タスクが利用可能である場合、それには、そのイベントを処理しているコンテキストの実行優先順位と等しいタスク実行順位が割り当てられ(1413)、そのコンテキストには制御の活動スレッドが割り当てられる。この、タスクにコンテキストの実行優先順位を割り当てることは、処理しているコンテキストの優先順位に従う、優先付けられたタスクの処理に関するメカニズムを提供する。従って、低レベル、即ち高い優先順位のコンテキストがイベントを処理するよう指定された場合、カーネルはそのコンテキストの優先順位を使用して、より低い実行優先順位のタスク、即ちより高いレベルのコンテキストによって把握されたタスクの実行を強制排除する。そのコンテキストに対するポインタは、そのタスクのアドレス空間内に記憶され、wakeupセマフォがそのタスクに関して通知される(1415)。
図14Bは、ポーリング単一スタック実施例におけるSchedule_Eventルーチンの実施例を示している。ここでカーネル213は、把握しているコンテキストに対するポインタを有するリスト要素を生成する(1421)ことだけが必要であり、スケジュールされたイベントのカーネルのリスト内のその要素を配置し(1423)、それは次に、処理しているコンテキストの優先順位に従って先入れ先出し法(first in first out)に基づいて処理される。
図15Aは、コンテキストによって処理されたイベント・ルーチンを、実行の優先順位を保証しながら実行するためのルーチン1501の一実施例のフローチャートを示す。好適実施例では、イベント・ルーチンはタスクによって実行される。このタスクは従来のプリエンプティブな優先付けられた複数スタック環境によって実装される。このタスクは、タスクに通知された(1415)wakeupセマフォを待つ(1503)。セマフォが通知された場合、実行コンテキストに対するポインタが検索される(1505)。ルーチンは次にエントリ・セマフォを待つ(1507)。このセマフォは、コンテキストが呼び出しを終えた場合に通知される(423)。このセマフォを待つことによって、このルーチンは、重要なイベント・ルーチンが処理されている間に、コンテキストがイベント・ルーチンを実行するために呼び出されることがないことを保証する。エントリ・セマフォが通知されると(423)、コンテキストが実行を終了したことを示し、次に、スケジュールされたイベント・ルーチンをタスク指名するためのルーチンがコールされ(1509)、こうしたルーチンの一例が図15Cに示されている。コンテキストに関する全てのイベント・ルーチンがタスク指名され、次に、制御のコンテキストのスレッドが非活動にセットされ(1511)、コンテキストのエントリ・セマフォが通知される(1513)。このことは、コンテキストがイベント・ルーチンを実行するためにコールされていることを示している。タスクは次に、タスク・プールに戻る(1515)。
図15Cは、コンテキストにとって重要な全てのイベント・ルーチンが、新しくスケジュールされたイベント・ルーチンの非同期実行の前にタスク指名されることを保証するための、Dispatch_All_Eventsルーチンの一実施例のフローチャートを示す。この実施例では、ルーチンが、コンテキストのルーチン・リストから、イベント・ルーチンに対するポインタを検索し(1537)、その要素をそのリストから除去する。カーネル213は次に、コンテキストのルーチン・リストが空かどうか判定し(1539)、空であれば、そのコンテキストに関してスケジュールされた全てのルーチンが処理され、ルーチンが戻る(1541)。コンテキストのルーチン・リスト上にイベント・ルーチンが残っていれば、イベント・タスク指名ルーチンをコールすることによって、検索されたイベント・ルーチンがタスク指名される(1543)。ルーチンが実行されると(1543)、それは、イベント・ルーチンが、完了を待っている実行のためにスケジュールされた回数を示す値を戻す。このカウンタが０である場合（ステップ1545）、そのルーチンはコンテキストのルーチン・リストから削除される。それ以外の場合、ルーチンは、それが再度検索され(1537)、タスク指名され(1543)るように、ルーチン・リストの最後に再インサートされる(1549)。このループは、イベント・ルーチンが、スケジュールされた全ての実行を完了するまで繰り返される。
図16は、Dispatch_All_Eventsルーチン1535、及びExit_Contextルーチン417によってコールされる(1543)、イベント・ルーチンをタスク指名するためのDispatch_Eventルーチン1601の一実施例を示す。このルーチンは、コールされた場合、そのルーチンが現在活動中かを、そのルーチンに関するフラグが示すかどうかを判定する(1603)。活動中である場合、カーネル213はエラーとなる(1605)。それ以外の場合、カーネル213は、ルーチンが現在活動中であることを示すようにそのフラグをセットする(1607)。イベント・ルーチンは、そのイベント・ルーチンへのポインタを使用してコールされ(1609)、実行される。実行が完了すると、フラグが、そのルーチンがもはや活動中でないことを示すようリセットされる(1611)。実行前のこれらの制御フラグのスレッドをチェックするステップ、及びフラグをセット、及びリセットする次のステップは、直接的、あるいは間接的にイベント・ルーチンがそれ自身をコールすることを防止することによって、無制限の再帰を防ぐ。フラグの使用は、任意の所与の時間においてコンテキスト内に単一の制御のスレッドだけを保証することによって、非再入コードも防止する。フラグをリセットした後で、イベント・ルーチンのカウンタがデクリメントされ(1613)、そのイベントの実行サイクルの１つが完了したことを示す。このカウンタ値は次に、上述したようにコールしているルーチンに戻され(1615)、イベント・ルーチンに対するポインタを検索し(1537)、イベント・ルーチンを再度タスク指名する(1543)ことによって、別の実行サイクルを生じさせる。
図15Bは、ポーリング、単一スタック環境におけるDispatch_Eventルーチンの実施例のフローチャートを示す。このルーチンは、それがイベントにポーリングを行い、それらを優先順位に従って実行するのに必要である場合に、ポーリング環境でコールされる。図5A、5B、及び12Aは、ポーリングDispatch_Eventルーチン1518をコールするルーチンを示す。
複数スタック・カーネル対単一スタック・カーネル
上述したように、本発明は単一スタック環境でも、複数スタック環境でも実施される。カーネル213によって提供された優先付けられたイベント処理によって、リアルタイム・アプリケーションの開発に関して両方の環境が使用可能である。複数スタック・カーネルは、イベントの発生を、好ましくない他のコードの単位のブロッキングを起こすことなく待つことができる、有利なコードを提供する。
図17は、複数スタック環境で使用されるソフトウエア・アプリケーションの呼び出し構造を示す。この例では、コンテキストＨが、コンテキストＣによって提供されたサービスにコールを行う(1701)ことを仮定する。更にこのサービスが、コールしたコンテキストに戻る前に、イベントの発生を待つものとする。ここでは、非同期イベントがコンテキストＧによって把握され、それがコンテキストＤへのサービス・コールを生成する(1703)ものとする。このコード実行のシーケンスは、コンテキストＣが依然イベントが起きるのを待っているときでさえ、実行を許可される。カーネルの複数スタック実装は、このタイプの同時実行を許可する。しかし、コンテキストＡが非同期イベントを把握し、かつコンテキストＣにサービス・コールをする(1705)ものである場合、コンテキストＨから起動しているコンテキストＣ内に、制御の活動スレッドが既に存在するため、そのイベントはEnter_Contextメカニズムによってブロックされる。従って、このカーネルの複数スタックの実施例は、コールされたコンテキストの中に制御のスレッドがなく、更にそのコールされたコンテキストがコールしたものの優先順位より高いことを保証するためにチェックを行う。
カーネル213は、単一スタック実装においても具現化される。図17のソフトウエア・アプリケーション、及び呼び出し構造を使用すると、コンテキストＨがコンテキストＣをコールし(1701)、コンテキストＣがイベントの発生を待つ場合、コンテキストＣより高い優先順位のコンテキスト内のイベント・ルーチンだけが、この待機期間の間に実行を許容される。従って、コンテキストＣが依然イベントを待っている間に、非同期イベントがコンテキストＡ内で把握されたとすると、コンテキストＡは、コンテキストＨからコンテキストＣへの実行のスレッドが完了するまで、ブロックされる。カーネルの単一スタックの実施例は、コンテキストＣ内のイベントを待っている間、依然として、コンテキストＤ、Ｅ、及びＦに関連付けられたイベント・ルーチンをタスク指名することができる。更に、このカーネルの単一スタック実施例は、コールされたコンテキスト内に制御の活動スレッドがあるかどうかチェックする必要がない。コールされたコンテキストがコールしたコンテキストの優先順位より高いことを単にチェックすることで、この条件を十分保証できる。
カーネル213の両バージョンは、コードの構造に一定の保証を提供するものである。コンテキスト条件毎の制御の単一スレッドが維持される。従って、コードの再入が除去され、プログラマに見える危険地域がない。コンテキストの呼び出しが完全に階層的であるため、コンテキスト間の再帰はあり得ない（コンテキスト内の再帰は許される）。両タイプのカーネルは、Wait条件の周期的入れ子がコンテキストの範囲内で発生しないことを保証するよう、イベント・ルーチン内でWaitステートメントの使用を制限する。コンテキスト間の待ちが階層的であるよう保証されたので、待ち(wait-for)条件の周期が禁止され、デッドロック条件は発生しない。
カーネル213の複数スタックのバージョンを単一スタックのバージョンの上級版として見ることができるが、両タイプのカーネルはそれぞれ用途がある。単一スタック・カーネルは、複数スタック操作を支援しない既存のコードと、より良好に統合される。コードの構成要素は、好ましくないブロッキングを避けるために状態駆動型で書かれうる。ある例では、支援されるアプリケーションはいくつかの同位レベルのコード・エンティティを必要とせず、単一スタック環境内で提供される強制排除機能が、アプリケーションに求められる全てとなることがある。組み込みシステムにおいて特に真であり、その場合、単一スタック・カーネルは小さなアドレス空間を有する構成要素のボード上で使用されうる。単一スタック・カーネルに対する縮小システムの要件は、こうした場合にそれを最も好ましいカーネルとすることである。
単一スタック／複数スタックはカーネル実装において最も差があるが、他の変形が存在する。分散カーネルは、バラバラなアドレス空間にわたるEvent_Handleの実施を提供する。マルチプロセッサ・カーネルは、複数のCPUを、様々なコンテキストを正しく同時に実行させるように同調させる。これらの様々な実装は、ここで開示する本発明の範囲内に含まれるものと考えられる。
プリエンプティブ・カーネル対ポーリング・カーネル
本発明のカーネルの実施例は更に、ポーリング・カーネルとプリエンプティブ・カーネルに分割される。イベントがコンテキストによって把握されると、イベント・ルーチンは実行のためにスケジュールされる。コンテキストを把握する優先順位が、現在実行しているコンテキストの優先順位より高ければ、カーネルはそのイベント・ルーチンをプリエンプティブに実行することができる。上述の複数スタック・カーネルは、プリエンプティブ・カーネルの例である。
図5A及び5Bはポーリング・カーネルにおけるEnter_ContextとExit_Contextルーチンを示している。本発明のポーリング・カーネルの実施は、図15Bに示すようにPoll_Eventカーネル関数505が実行されるまで、実際にイベント・ルーチンの実行を遅延させる。このイベントは、次のコンテキストの呼び出しの前に発生しなければならない。このため、Poll_Event関数は、単一スタック・カーネル213のEnter_Context操作501内で呼び出される(505)。この要件は、カーネルのポーリング・カーネルの実装を、イベントの発生とそのイベントに関連づけられたイベント・ルーチンの実行の間に大きな待ち時間の遅れが存在するという１つの例外を有する、プリエンプティブ・カーネルと意味的に同等に保つ。更に、カーネル213のポーリング実施において、アプリケーション215は、Poll_Eventカーネル・メカニズムが、システムがアイドル状態の時はいつでも周期的に呼び出されるか、又はイベント処理がイネーブルとなる、繰り返された命令のループ内に関与することを保証しなければならない。
ポーリング・カーネルが提供する、プリエンプティブの実装より有利な点は、それが従来のプログラミング環境に、いかなる特別のオペレーティング・システムの支援なしに組み込まれうることである。
ポーリング・カーネルとプリエンプティブ・カーネルの間の差に関して、本発明の範囲内の他の実施例は、複数スタック・ポーリング・カーネル、及び単一スタック・プリエンプティブ・カーネルを含み、その構成は前述した説明及びプロセスに基づく。
カーネル・メカニズムのハードウエア実装
ハードウエア・アーキテクチャはコンピュータの設計に含まれるトレード・オフに関連する。この設計の一態様は、コンピュータの命令セットの定義である。命令セットによってコンピュータの処理能力を低レベルで見ることができる。命令セットの単純さ（例えば縮小命令セット・コンピュータ(RISC)）の維持、及び命令セットを複雑にする、より強力なメカニズム(CISC)の提供との間には通常トレード・オフがある。
本発明のカーネルによって提供されたメカニズムの全ては、コンピュータの命令セット内に実装されうる。特に、コンテキストの開始／終了毎に実行されなければならないEnter_Context、及びExit_Contextカーネル関数は、それらの操作を保証し、システム性能を向上させるために命令セット内に好適に組み込まれうる。これらの操作を支援するためのルーチンは、提供されたカーネルのタイプ（単一スタック／複数スタック）に依存するので、全体の操作が単一のマシン命令内に統合されている必要はない。その代わり、単純な現在コンテキスト・ポインタの組み込み、及びコンテキストの開始／終了に関して自動優先順位チェック及び変更を支援することは、両方の環境に対して命令レベルの支援を提供する。終了コンテキスト・ルーチンは、手順コール命令からの従来の戻りを、ランタイム・システムに割り込む命令に置換することによって、命令セット内で拡張され、イベントのタスク指名に関するテストを行う。
命令セット内の開始／終了コンテキスト支援に加えて、全体イベント・メカニズムはプロセッサ201の命令セット内に含まれる。その命令セット内のイベント・メカニズムの直接の支援は、多くのコンピュータの命令セット内で支援されている割り込みサービス・ルーチン(ISR)の存在を不必要にする。
メモリの可視性
本発明の更なる一実施例は、コンテキスト間のメモリの可視性を制御する方法を支援することである。ここで述べられた様々な実施例が、コンテキスト間に無制限のメモリの可視性を提供する。しかし、本発明で使用されるプログラミング方法論は、コンテキストの可視性の要件を支援するのに十分で、より高い優先順位のコンテキストがより低い優先順位のコンテキストのアドレス空間を変更する権利を有しており、逆は不可である。プロセッサ201の命令セット内でイベント及びコンテキスト・メカニズムが支援される、カーネル213の好適実施例は、これらの可視性の要件を強制する。このコンテキストの階層は、むしろプログラマが明確に可視性を指定するより、メモリの可視性を暗に定義するのに使用される。メモリの保護がプロセッサ201によって直接支援されるので、ソフトウエア・プログラマは、メモリの保護要件を直接指定しなければならないということから開放され、またここでもアプリケーション215の信頼性と性能を向上させる。
【図１Ａ】
0003863917.tif 000011
【図１Ｂ】
0003863917.tif 000012
【図２】
0003863917.tif 000013
【図３】
0003863917.tif 000014
【図４】
0003863917.tif 000015
【図５】
0003863917.tif 000016
【図６】
0003863917.tif 000017
【図７Ａ】
0003863917.tif 000018
【図７Ｂ】
0003863917.tif 000019
【図７Ｃ】
0003863917.tif 000020
【図７Ｄ】
0003863917.tif 000021
【図７Ｅ】
0003863917.tif 000022
【図８】
0003863917.tif 000023
【図９】
0003863917.tif 000024
【図１０】
0003863917.tif 000025
【図１１】
0003863917.tif 000026
【図１２】
0003863917.tif 000027
【図１３】
0003863917.tif 000028
【図１４Ａ】
0003863917.tif 000029
【図１４Ｂ】
0003863917.tif 000030
【図１５Ａ】
0003863917.tif 000031
【図１５Ｂ】
0003863917.tif 000032
【図１５Ｃ】
0003863917.tif 000033
【図１６】
0003863917.tif 000034
【図１７】
0003863917.tif 000035