実行モデル

コンピューティングでは、プログラミング言語は構文と実行モデルで構成されます。実行モデルは、言語の要素の動作を指定します。実行モデルを適用することで、そのプログラミング言語で記述されたプログラムの動作を導き出すことができます。たとえば、プログラマーがコードを「読む」とき、頭の中でコードの各行が何をするかを順に考えます。つまり、頭の中で動作をシミュレートするのです。プログラマーが行っているのは、実行モデルをコードに適用することであり、その結果、コードの動作が生まれます。

あらゆるプログラミング言語には実行モデルがあり、これによって（プログラム構文で示される）作業単位の実行スケジュール方法が決まります。一般的な言語の実行モデルの仕様に関する詳細な例としては、Python、^{[1] 、} Unified Parallel C （UPC）プログラミング言語 の実行モデル、 ^[2]、命令型言語と関数型言語 などのさまざまなクラスの実行モデルに関する説明、^{[3] 、}リアルタイム組み込み言語 の実行モデルに関する記事などがあります。^[4]

操作的セマンティクスは、言語の実行モデルを指定する方法の 1 つです。実行中のプログラムの観察された動作は、操作的セマンティクス (言語の実行モデルを定義する) から派生した動作と一致する必要があります。

実行モデルは、分割不可能な作業単位とは何か、それらの作業単位が実行される順序にどのような制約があるかなどについて扱います。たとえば、加算演算は多くの言語で分割不可能な作業単位であり、シーケンシャル言語では、そのような作業単位は次々に実行されるように制約されます。

これを説明するために、カーニハンとリッチーの著書で説明されているC プログラミング言語を考えてみましょう。 ^[5] C にはステートメントと呼ばれる概念があります。言語仕様では、ステートメントは「;」で終了する構文のチャンクとして定義されています。言語仕様では、「プログラムの実行は、ステートメントが 1 つずつ順番に実行されます」と述べています。「プログラムの実行は、ステートメントが 1 つずつ順番に実行されます」という文は、C の実行モデルの一部です。これらの文は、ステートメントが分割できない作業単位であり、コード内での構文上の出現と同じ順序で実行されることを示しています (IF や FOR などの制御文によって順序が変更される場合を除きます)。「プログラムの実行は、ステートメントが 1 つずつ順番に実行される」と述べることで、プログラミング モデルは作業単位の実行順序に制約を規定しています。

C 言語には、実行モデルに優先順位という追加レベルがあります。優先順位は、1 つのステートメント内での操作の順序のルールを示します。優先順位は、1 つのステートメント内の作業単位の実行に対する制約を示すものと考えることができます。つまり、「;」と「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 プレロック ステートメントと呼びます) を実行します。次に、スレッド B は「ロックの所有権の取得」を実行し、次にスレッド B は B がロックの所有権を取得した後に実行される B ポストロック ステートメントを実行します。

ここで、「ロックの所有権の取得」と「ロックの所有権の放棄」の同期構造の並列実行モデルについて説明できます。実行モデルは次のようになります。

「ロックの所有権がスレッド A からスレッド B に移る場合、A のロック取得後のステートメントは B のロック取得後のステートメントの前に来ます。」

実行モデルには、「ロックの所有権を放棄する」という実行が、他のタイムライン (スレッド) で次に実行される「ロックの所有権を取得する」という実行に影響を与える手段がないため、状況が複雑になります。多くの場合、特定のハンドオフのみが有効な結果をもたらします。したがって、プログラマーは、1 つのスレッドがロックを放棄し、次に別のスレッドがロックを取得するというすべての可能な組み合わせを考え、コードが有効な組み合わせのみを許可するようにする必要があります。

唯一の効果は、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 つであり、使いにくいにもかかわらず、それが存続している理由であると考えられます。

無料辞書のウィクショナリーで「run-time」を調べてください。

• ランタイムシステム
• 実行（コンピューティング）
• スケジューリング（コンピューティング）