実行モデル
実行モデル (じっこうモデル、英: execution model)は、プログラミング言語の構成要素の一つ。
プログラミング言語は、文法/構文と実行モデルで構成される。実行モデルは、言語の要素の動作を指定する。実行モデルにより、そのプログラミング言語で書かれたプログラムの振る舞いを理解できる。たとえば、プログラマーがコードを「読んでいる」とき、頭の中でコードの各行が何をするかを考え、心の中の動作をシミュレートする。プログラマーが行っているこの作業は、実行モデルをコードに適用することである。
すべてのプログラミング言語には実行モデルがあり、作業単位（プログラム構文で示される）の実行がスケジュールされる方法を決定する。言語の実行モデルの仕様の例には、Pythonの実行モデル[1]、Unified Parallel C（UPC）プログラミング言語の実行モデル[2]、そして命令/関数型言語といったさまざまなクラスの実行モデル[3]と、リアルタイム組み込みデバイス向け実行モデル[4]などがある。
実行モデルの詳細
[編集]操作的意味論は、言語の実行モデルを指定する1つの方法である。実行中のプログラムの動作は、（言語の実行モデルを定義する）操作的意味論から派生した動作と一致する必要がある。
実行モデルは、分割できない作業単位とは何か、それらの作業単位が実行される順序の制約は何かなどをカバーする。たとえば、加算操作は多くの言語で分割できない作業単位であり、順次言語では、このような作業単位は次々に実行されるように制約される。
これを説明するために、書籍プログラミング言語C (K&R)で説明されているCプログラミング言語について考えてみよう[5] 。 Cにはステートメントと呼ばれる概念がある。言語仕様では、ステートメントを「;」で終了する構文のチャンクとして定義している。次に、言語仕様には、「プログラムの実行は、次々にステートメントを順番に進める」と書かれている。 「プログラムの実行は、次々とステートメントを順番に進める」という言葉は、Cの実行モデルの一部である。これらの単語は、ステートメントが分割できない作業単位であり、コード内の構文上の外観と同じ順序で進行することを示す（IFやFORなどの制御ステートメントが順序を変更する場合を除く）。 「プログラムの実行は次々とステートメントを順番に進める」と述べることにより、プログラミングモデルは作業単位を実行する順序に関する制約を述べている。
C言語には、実際には実行モデルに追加のレベルがある。これは優先順位である。優先順位は、単一のステートメント内の操作の順序の規則を示す。優先順位は、単一のステートメント内にある作業単位の実行に関する制約を示すものと見なすことができる。そう、 ";" 「IF」と「WHILE」はステートメントの順序の制約をカバーし、優先順位はステートメント内の作業の制約をカバーする。したがって、C言語仕様のこれらの部分は、C言語の実行モデルの一部でもある。
実行モデルは、プログラミング言語から独立して存在することもできる。その例としては、 POSIXスレッドライブラリやHadoopのMap-Reduceプログラミングモデルがある。実行モデルの実装は、コンパイラまたはインタープリタを介して行い、多くの場合、ランタイムシステムが含まれる。
実行モデルの実装は、実行中に作業が行われる順序を制御する。この順序は、状況によっては事前に選択することも、実行が進むにつれて動的に決定することもできる。ほとんどの実行モデルでは、両方の程度を変えることができる。たとえば、C言語は、ステートメント内の作業の順序を修正し、IFステートメントまたはループステートメントの形式を含むステートメントを除くすべてのステートメントの順序を修正する。したがって、実行順序のほとんどは、実行が開始される前に静的に選択できるが、実行が進むにつれて、ごく一部を動的に選択する必要がある。
静的な選択は、ほとんどの場合コンパイラ内で実装されます。この場合、作業の順序は、命令が実行可能バイナリに配置される順序で表される。動的な選択は、言語のランタイムシステム内に実装される。ランタイムシステムは、コンパイラによって挿入された命令によって呼び出されるライブラリにすることも、次に実行する作業を動的に選択する分岐命令を挿入するなどして、ランタイムシステムを実行可能ファイルに直接埋め込むこともできる。
ただし、インタプリタは任意の言語用に構築することもできる。その場合、実行順序に関するすべての決定は動的となる。インタプリタは、パーツトランスレータ、およびパーツ実行モデルの実装と見なすことができる。
アセンブリ言語実行モデルとマイクロアーキテクチャによる実装
[編集]アセンブリ言語にも、他の言語と同じ実行モデルがあります。このような実行モデルは、CPUマイクロアーキテクチャによって実装されます。たとえば、5ステージのインオーダーパイプラインと大規模なアウトオブオーダーCPUの両方が、同じアセンブリ言語実行モデルを実装します。実行モデルは動作の定義であるため、すべての実装は、順序どおり、順序外、インタープリター型、JIT型など、すべてまったく同じ結果をもたらす必要があり、その結果は実行モデルによって定義されます。
並列実行モデル
[編集]現代では、並列プログラミングはますます重要なトピックになっています。並列実行モデルは、複数のタイムラインを伴うため、複雑になる傾向があります。並列実行モデルには、必然的に同期構造の動作が含まれます。同期構造には、別のタイムラインのアクティビティと比較して、あるタイムラインのアクティビティ間の順序を確立する効果があります。
たとえば、一般的な同期構造はロックです。 1つのタイムラインを考えてみましょう。タイムラインには、「ロックの所有権を取得する」同期構造を実行するポイントがあります。 Posixスレッドでは、これはpthread_mutex_lock(＆myMutex)になります。Javaでは、これはlock.lock()になります。どちらの場合も、タイムラインはスレッドと呼ばれます。 CおよびJavaの実行モデルはシーケンシャルであり、タイムラインには「ロックの所有権を取得する」ための呼び出しの前に行われるアクティビティと、呼び出しの後に行われるアクティビティがあると記載されています。同様に、「ロックの所有権を放棄する」操作があります。 Cでは、これはpthread_mutex_unlock(＆myMutex)になります。 Javaでは、これはlock.unlock()になります。この場合も、実行モデルCおよびJavaは、ロックの所有権が放棄される前に1つのステートメントグループが実行され、ロックの所有権が放棄された後に別のステートメントグループが実行されることを定義しています。
ここで、2つのスレッドとも呼ばれる2つのタイムラインの場合を考えてみましょう。 1つのスレッド（スレッドAと呼びます）は、いくつかのステートメントを実行し、それらをA-pre-gain-lockステートメントと呼びます。次に、スレッドAが「ロックの所有権を取得」を実行し、次にスレッドAがA-post-gain-lockステートメントを実行します。これは、Aがロックの所有権を取得した後に実行されます。最後に、スレッドAは「ロックの所有権を放棄する」を実行します。次に、スレッドAはA-post-giveup-lockステートメントを実行します。
2番目のスレッドはスレッドBと呼ばれ、いくつかのステートメントを実行し、それらをB-pre-lockステートメントと呼びます。次に、スレッドBは「ロックの所有権を取得」を実行し、次にスレッドBはBがロックの所有権を取得した後にBポストロックステートメントを実行します。
これで、「ロックの所有権を取得する」と「ロックの所有権を放棄する」同期構造の並列実行モデルと言えます。実行モデルは次のとおりです。
「ロックの所有権がスレッドAからスレッドBに移る場合、A-post-gain-lockステートメントはB-post-gain-lockステートメントの前に来ます。」
以上です。
簡単そうですね。複雑なのは、実行モデルには、「ロックの所有権を放棄する」の実行が、他のタイムライン（スレッド）での「ロックの所有権の取得」の実行に影響を与える手段がないという事実に起因します。 。多くの場合、特定のハンドオフのみが有効な結果をもたらします。したがって、プログラマーは、あるスレッドがロックを放棄し、別のスレッドが次にロックを取得する可能性のあるすべての組み合わせを考え、コードで有効な組み合わせのみが許可されるようにする必要があります。
唯一の効果は、A-post-gain-lockステートメントがB-post-gain-lockステートメントの前に来ることです。他の影響は発生せず、他の相対的な順序に依存することはできません。具体的には、A-post-give-up-lockとB-post-gain-lockには相対的な順序が定義されていないため、多くの人が驚いています。ただし、スレッドAは所有権を放棄した後にスワップアウトされた可能性があるため、A-post-give-up-lockステートメントは、多くのB-post-gain-lockステートメントが終了したずっと後に発生する可能性があります。これは、ロックを設計するときに考慮しなければならない可能性の1つであり、マルチスレッドプログラミングが難しい理由を示している。
最新の並列言語は、実行モデルをはるかに使いやすいことに注意してください。スレッドモデルは、元の並列実行モデルの1つでした。これは、使用が難しいにもかかわらず、スレッドモデルが存続した理由を説明している可能性があります。
関連項目
[編集]脚注
[編集]- ^ “Python Documentation: Execution Model”. 2020年12月21日閲覧。
- ^ “UPC Language Features”. 2020年12月21日閲覧。
- ^ Cardoso, J.M.P.; Diniz, P.C. (2011). Programming Languages and Execution Models. Springer US. ISBN 9780387096711
- ^ PELLIZZONI, R.; BETTI, E.; BAK, S.; YAO, G.; CRISWELL, J.; CACCAMO, M.; KEGLEY, R (2011). “A Predictable Execution Model for COTS-based Embedded Systems”. Real-Time and Embedded Technology and Applications Symposium (IEEE).
- ^ Kernighan, Brian W.; Dennis M. Ritchie (February 1978). The C Programming Language (1st ed.). Englewood Cliffs, NJ: Prentice Hall. ISBN 0-13-110163-3