同時実行コンピューティング

同時実行コンピューティングとは、複数の計算を順番に実行するのではなく、重複する期間に同時に実行し、1 つの計算が完了してから次の計算を開始する コンピューティング形式です。

これは、プログラム、コンピュータ、ネットワークなど、各プロセスに個別の実行ポイントまたは「制御スレッド」が存在するシステムの特性です。並行システムとは、他のすべての計算が完了するのを待たずに計算を進めることができるシステムです。^[1]

並行コンピューティングはモジュールプログラミングの一種です。そのパラダイムでは、全体的な計算が並行して実行できるサブ計算に分解されます。並行コンピューティングの分野の先駆者としては、エドガー・ダイクストラ、ペル・ブリンチ・ハンセン、CAR・ホーアなどがいます。^[2]

同時実行コンピューティングの概念は、関連しているが異なる概念である並列コンピューティングと混同されることが多いが^{[3] [4]、}どちらも「同じ期間に複数のプロセスが実行される」と説明できる。並列コンピューティングでは、実行は物理的に同じ瞬間に発生する。たとえば、マルチプロセッサマシンの別々のプロセッサでは、計算を高速化することが目的である。並列コンピューティングは、( 1 コアの) 単一プロセッサでは不可能である。なぜなら、どの瞬間にも (どのクロック サイクルでも) 1 つの計算しか実行できないからである。^[a]これとは対照的に、同時実行コンピューティングは、プロセスの存続期間が重なり合うが、実行は同時に発生しない。ここでの目標は、複数のクライアントが同時にサーバーにアクセスするなど、同時に発生するプロセスをモデル化することにある。ソフトウェア システムを複数の同時通信部分で構成されるものとして構造化することは、部分が並列実行できるかどうかに関係なく、複雑さに対処するのに役立つ可能性がある。^{[5] : 1}

たとえば、各プロセスの実行ステップをタイムシェアリングスライスでインターリーブすることで、1 つのコアで並行プロセスを実行できます。一度に実行されるのは 1 つのプロセスのみで、タイムスライス中に完了しない場合は一時停止され、別のプロセスが開始または再開され、その後、元のプロセスが再開されます。このように、複数のプロセスが 1 つの瞬間に実行の途中ですが、その瞬間に実行されているのは 1 つのプロセスだけです。^{[引用が必要]}

同時計算は、例えば各プロセスを別々のプロセッサまたはプロセッサコアに割り当てたり、計算をネットワーク全体に 分散したりすることによって並列に実行することができる^{[3] [6] 。}

並行システムにおけるタスクが実行される正確なタイミングはスケジューリングに依存し、タスクは常に並行して実行される必要はありません。たとえば、2つのタスクT1とT2があるとします。^{[引用が必要]}

• T1 は T2 より先に実行されて終了する可能性があり、その逆も成り立ちます(シリアルおよびシーケンシャル)
• T1とT2は交互に実行される可能性がある（シリアルおよび同時）
• T1 と T2 は同時に実行される可能性がある (並列かつ同時)

「シーケンシャル」という言葉は、「同時」と「並列」の両方の反意語として使用されます。これらが明示的に区別されている場合、同時/シーケンシャルと並列/シリアルは反対のペアとして使用されます。^[7]タスクがインターリーブなしで（シーケンシャル、並列性なし：前のタスクが終了するまでタスクは開始されません）一度に1つずつ実行されるスケジュール（シリアル、並列性なし）は、シリアルスケジュールと呼ばれます。シリアルにスケジュールできるタスクのセットはシリアル化可能であり、これにより同時実行制御が簡素化されます。^[要出典]

並行プログラムの設計における主な課題は並行性制御です。つまり、異なる計算実行間の相互作用や通信の正しい順序付けを保証し、実行間で共有されるリソースへのアクセスを調整します。^[6]潜在的な問題には、競合状態、デッドロック、リソース不足などがあります。たとえば、共有リソースで表される当座預金口座から引き出す次のアルゴリズムを考えてみましょうbalance。

bool撤回( int撤回)  
{
    if (残高>=引き出し)   
    {
        残高-=引き出し;  
        trueを返します。 
    } 
    falseを返します。 
}

と仮定しbalance = 500、2 つの同時スレッドが呼び出しwithdraw(300)と を実行します。withdraw(350)両方の操作の 3 行目が 5 行目より前に実行される場合、両方の操作でbalance >= withdrawalが と評価されることがわかりtrue、実行は引き出し額の減算に進みます。ただし、両方のプロセスが引き出しを実行するため、引き出される合計額は元の残高よりも多くなります。共有リソースに関するこのような問題は、同時実行制御または非ブロッキング アルゴリズムの使用によって解決できます。

同時実行コンピューティングの利点は次のとおりです。

• プログラムスループットの向上 - 並行アルゴリズムの並列実行により、一定時間内に完了するタスクの数は、グスタフソンの法則に従ってプロセッサの数に比例して増加します。
• 入出力に対する高い応答性 - 入出力を多用するプログラムは、ほとんどの場合、入力または出力操作が完了するまで待機します。並行プログラミングにより、待機に費やされる時間を別のタスクに使用することができます。^[8]
• より適切なプログラム構造 - 一部の問題と問題領域は、並行タスクまたはプロセスとして表現するのに適しています。たとえば、MVCCです。

1962 年に導入されたペトリ ネットは、並行実行のルールを体系化する初期の試みでした。その後、データフロー理論はこれを基に構築され、データフロー理論の考え方を物理的に実装するためにデータフロー アーキテクチャが作成されました。1970 年代後半から、相互作用するコンポーネントで構成されるシステムについて代数的推論を可能にするために、通信システムの計算( CCS) や通信順次プロセス(CSP)などのプロセス計算が開発されました。π計算により、動的トポロジについて推論する機能が追加されました。

入出力オートマトンが 1987 年に導入されました。

並行システムの動作を記述するために、 Lamport のTLA+などのロジックや、トレースやアクター イベント ダイアグラムなどの数学モデルも開発されてきました。

ソフトウェア トランザクション メモリは、データベース理論からアトミック トランザクションの概念を借用し、それをメモリ アクセスに適用します。

並行プログラミング言語とマルチプロセッサ プログラムには、一貫性モデル(メモリ モデルとも呼ばれる)が必要です。一貫性モデルは、コンピュータ メモリでの操作の実行方法と結果の生成方法に関するルールを定義します。

最初の一貫性モデルの 1 つは、レスリー ランポートのシーケンシャル一貫性モデルでした。シーケンシャル一貫性とは、プログラムを実行するとシーケンシャル プログラムと同じ結果が生成されるというプログラムの特性です。具体的には、プログラムは「すべてのプロセッサの操作が何らかのシーケンシャルな順序で実行された場合と同じ結果になり、各プロセッサの操作がそのプログラムで指定された順序でこの順序で表示される」場合、シーケンシャル一貫性があります。^[9]

並行プログラムを実装するには、各計算実行をオペレーティング システム プロセスとして実装したり、計算プロセスを単一のオペレーティング システム プロセス内の スレッドのセットとして実装するなど、さまざまな方法を使用できます。

一部の並行コンピューティング システムでは、並行コンポーネント間の通信はプログラマーから隠されています (たとえば、futuresを使用することにより)。一方、他のシステムでは、通信を明示的に処理する必要があります。明示的な通信は、次の 2 つのクラスに分けられます。

共有メモリ通信

並行コンポーネントは、共有メモリの場所の内容を変更することによって通信します( JavaおよびC#で例を示します)。このスタイルの並行プログラミングでは、通常、スレッド間の調整に何らかの形式のロック (ミューテックス、セマフォ、モニターなど)を使用する必要があります。これらのいずれかを適切に実装したプログラムは、スレッドセーフであると言われています。

メッセージパッシング通信

並行コンポーネントは、メッセージを交換することで通信します( MPI、Go、Scala、Erlang、occamが例です)。メッセージの交換は非同期で実行される場合もあれば、送信者がメッセージが受信されるまでブロックする同期の「ランデブー」スタイルを使用する場合もあります。非同期のメッセージ パッシングは、信頼できる場合と信頼できない場合があります (「送信して祈る」と呼ばれることもあります)。メッセージ パッシングの並行性は、共有メモリの並行性よりもはるかに簡単に理解できる傾向があり、通常、並行プログラミングのより堅牢な形式であると考えられています。^[要出典]アクター モデルやさまざまなプロセス計算など、メッセージ パッシング システムを理解および分析するためのさまざまな数学理論が利用可能です。メッセージ パッシングは、共有メモリキャッシュ コヒーレンスの有無にかかわらず、対称型マルチプロセッシングを介して効率的に実装できます。

共有メモリとメッセージ パッシングの同時実行には、異なるパフォーマンス特性があります。通常 (常にではありませんが)、プロセスごとのメモリ オーバーヘッドとタスク切り替えオーバーヘッドはメッセージ パッシング システムの方が低くなりますが、メッセージ パッシングのオーバーヘッドはプロシージャ呼び出しよりも大きくなります。これらの違いは、他のパフォーマンス要因によって圧倒されることがよくあります。

並行コンピューティングは、19 世紀から 20 世紀初頭にかけての鉄道と電信に関する初期の研究から発展したもので、セマフォなどの用語もこの時代に遡ります。これらは、同じ鉄道システムで複数の列車を処理する方法 (衝突を回避し、効率を最大化) や、時分割多重化 (1870 年代) などによって、特定の一連の配線で複数の伝送を処理する方法 (効率を向上) などの問題に対処するために生まれました。

並行アルゴリズムの学術研究は1960年代に始まり、ダイクストラ（1965）が相互排除を特定して解決したこの分野で最初の論文を書いたとされています。^[10]

同時実行性はコンピューティングの分野で広く普及しており、単一チップ上の低レベル ハードウェアから世界規模のネットワークにまで及びます。次に例を示します。

プログラミング言語レベル:

• チャネル
• コルーチン
• 未来と約束

オペレーティング システム レベル:

• コンピュータのマルチタスク（協調型マルチタスクとプリエンプティブ型マルチタスクの両方を含む）
  • タイムシェアリングは、ジョブの連続バッチ処理をシステムの同時使用に置き換えたものである。
• プロセス
• 糸

ネットワーク レベルでは、ネットワーク システムは個別のデバイスで構成されているため、その性質上、通常は同時実行可能です。

並行プログラミング言語は、並行性のための言語構造を使用するプログラミング言語です。これらの構造には、マルチスレッド、分散コンピューティングのサポート、メッセージパッシング、共有リソース（共有メモリを含む）、またはフューチャーとプロミスが含まれます。このような言語は、並行性指向言語または並行性指向プログラミング言語（COPL）と呼ばれることもあります。^[11]

現在、並行処理のための特定の構造を持つ最も一般的に使用されているプログラミング言語は、JavaとC#です。これらの言語はどちらも、基本的に共有メモリ並行処理モデルを使用し、モニターによってロックが提供されます(ただし、メッセージ パッシング モデルは、基盤となる共有メモリ モデルの上に実装できますし、実際に実装されています)。メッセージ パッシング並行処理モデルを使用する言語の中で、現在業界で最も広く使用されているのはErlangです。 ^{[引用が必要]}

多くの並行プログラミング言語は、生産用言語としてよりも研究用言語 (例: Pict )として開発されてきました。しかし、 Erlang、Limbo、occamなどの言語は、過去 20 年間にさまざまな時期に産業用として使用されてきました。並行プログラミング機能を使用または提供する言語の非網羅的なリスト:

• Ada —汎用、メッセージパッシングとモニターベースの並行処理をネイティブサポート
• Alef — スレッドとメッセージ パッシングを備えた並行処理。ベル研究所の Plan 9の初期バージョンにおけるシステム プログラミング用。
• Alice —Standard MLの拡張で、futuresによる並行性のサポートを追加
• Ateji PX —π計算からヒントを得た並列プリミティブを備えたJavaの拡張
• Axum —ドメイン固有、同時実行、アクター モデルと C のような構文を使用した .NET 共通言語ランタイムに基づく
• BMDFM —バイナリ モジュラー データフロー マシン
• C++ —スレッドとコルーチンのサポートライブラリ^{[12] [13]}
• Cω (C オメガ) - 研究用、C# を拡張、非同期通信を使用
• C# — lock、yieldを使用した並行コンピューティングをサポートし、バージョン5.0以降ではasyncおよびawaitキーワードも導入されました。
• Clojure —Javaプラットフォーム上のLispの現代的な関数型方言
• Concurrent Clean —Haskellに似た関数型プログラミング
• 並行コレクション（CnC） - データと制御のフローを明示的に定義することで、メモリモデルに依存しない暗黙の並列処理を実現します。
• Concurrent Haskell —共有メモリ上で並行プロセスを実行する遅延型の純粋関数型言語
• 並行ML —標準MLの並行拡張
• 並行パスカル—Per Brinch Hansen 著
• カレー
• D —並行プログラミング (アクター モデル)を明示的にサポートするマルチパラダイム システム プログラミング言語
• E —デッドロックを防ぐためにPromiseを使用する
• ECMAScript —非同期操作にPromiseを使用する
• エッフェル—契約による設計の概念に基づくSCOOPメカニズムを通じて
• Elixir — Erlang VM 上で実行される動的かつ関数型のメタプログラミング対応言語。
• Erlang —共有メモリなしで同期または非同期のメッセージパッシングを使用する
• FAUST —リアルタイム機能、信号処理用、コンパイラはOpenMPまたは特定のワークスティーリングスケジューラを介して自動並列化を提供します。
• Fortran —共配列と同時実行はFortran 2008標準の一部です
• Go —CSPに基づく並行プログラミング モデルを使用したシステム プログラミング用
• Haskell —並行・並列関数型プログラミング言語^[14]
• ヒューム- 機能的、並行的、同期チャネルパターンとメッセージパッシングによってオートマトンプロセスが記述される、制限された空間と時間の環境向け
• Io —アクターベースの同時実行
• ヤヌス-論理変数、バッグチャネルに対する明確な質問者と回答者を特徴としており、純粋に宣言的です。
• Java —スレッドクラスまたはRunnableインターフェース
• Julia —「並行プログラミングの基本要素：タスク、非同期待機、チャネル」^[15]
• JavaScript —ブラウザ環境でのWeb ワーカー、 Promise、コールバック経由。
• JoCaml —OCamlの拡張で、並行分散チャネルベース、プロセスの結合計算を実装します。
• Join Java —Java言語に基づく並行処理
• Joule —データフローベース、メッセージパッシングによる通信
• Joyce — 並行、教育、Concurrent Pascal上に構築、 Per Brinch HansenによるCSPの機能を搭載
• LabVIEW —グラフィカル、データフロー、関数はグラフ内のノード、データはノード間のワイヤ、オブジェクト指向言語を含む
• Limbo — Alefの関連語。Inferno (オペレーティング システム)のシステム プログラミング用。
• Locomotive BASIC —BASICのAmstrad版には、並行サブルーチン用のEVERYコマンドとAFTERコマンドが含まれています。
• MultiLisp —並列処理をサポートするように拡張されたSchemeバリアント
• Modula-2 —システムプログラミング用。N. Wirth による、コルーチンをネイティブにサポートする Pascal の後継。
• Modula-3 —スレッド、ミューテックス、条件変数を幅広くサポートする Algol ファミリーの最新メンバー
• Newsqueak — チャネルを第一級の価値とするリサーチ用。Alef の前身。
• オッカム—通信シーケンシャルプロセス（CSP） の影響を強く受けている
  • オッカムπ —ミルナーのπ計算のアイデアを取り入れたオッカムの現代版
• ooRexx —通信と同期のためのオブジェクトベースのメッセージ交換
• Orc — 高度に並行、非決定性、クリーネ代数に基づく
• Oz-Mozart —マルチパラダイム、共有状態とメッセージパッシングの並行性、および未来をサポート
• ParaSail — オブジェクト指向、並列、ポインタや競合状態がない
• PHP —Goからヒントを得たメッセージパッシングを実装した並列拡張によるマルチスレッドサポート^[16]
• Pict — 本質的にはミルナーのπ計算の実行可能な実装
• Python — スレッドベースの並列処理とプロセスベースの並列処理を使用する^[17]
• Rakuにはデフォルトでスレッド、プロミス、チャネルのクラスが含まれています^[18]
• Reia —共有なしオブジェクト間の非同期メッセージパッシングを使用する
• Red/System —Rebolに基づくシステムプログラミング用
• Rust —システムプログラミング用。移動セマンティクスによるメッセージパッシング、共有不変メモリ、共有可変メモリを使用する。^[19]
• Scala — 一般的なプログラミングパターンを簡潔かつエレガントに、型安全に表現できるように設計された汎用言語です。
• SequenceL —汎用機能。主な設計目標は、プログラミングの容易さ、コードの明瞭性と可読性、マルチコアハードウェアでのパフォーマンスのための自動並列化、競合状態がないことが証明されていることです。
• SR —研究用
• SuperPascal — 教育用の並行処理。Per Brinch HansenによるConcurrent PascalとJoyce をベースに構築。
• Swift —構造化された方法で非同期および並列コードを記述するための組み込みサポート^[20]
• ユニコン—研究用
• TNSDL —通信交換を開発するためのもので、非同期メッセージパッシングを使用します。
• VHSIC ハードウェア記述言語 ( VHDL ) - IEEE STD-1076
• XC — XMOSによって開発された、C 言語の並行性拡張サブセット。通信する順次プロセスと、プログラム可能な I/O の組み込み構造に基づいています。

他の多くの言語では、上記のリストとほぼ同等のレベルで、ライブラリの形で並行性のサポートを提供しています。

• 非同期I/O
• チュースペース
• フローベースプログラミング
• Java コンカレントマップ
• プトレマイオスプロジェクト
• 競合状態 § コンピューティング
• 構造化された同時実行
• トランザクション処理

• Dijkstra, EW (1965). 「並行プログラミング制御における問題の解決」Communications of the ACM . 8 (9): 569. doi : 10.1145/365559.365617 . S2CID  19357737.
• ハーリヒ、モーリス (2008) [2008].マルチプロセッサプログラミングの芸術. モーガン・カウフマン. ISBN 978-0123705914。
• ダウニー、アレン B. (2005) [2005]. セマフォの小さな本(PDF) . グリーンティープレス. ISBN 978-1-4414-1868-5. 2016年3月4日時点のオリジナル（PDF）からアーカイブ。2009年11月21日閲覧。
• Filman, Robert E.; Daniel P. Friedman (1984)。Coordinated Computing: Tools and Techniques for Distributed Software。ニューヨーク: McGraw-Hill。p. 370。ISBN 978-0-07-022439-1。
• Leppäjärvi, Jouni (2008). 同期プリミティブの普遍性に関する実用的かつ歴史的指向の調査(PDF) 。オウル大学。2017-08-30 にオリジナル(PDF)からアーカイブ。2012-09-13に取得。
• Taubenfeld, Gadi (2006)。同期アルゴリズムと並行プログラミング。Pearson / Prentice Hall。p. 433。ISBN 978-0-13-197259-9。

• ウィキメディア・コモンズの並行プログラミングに関連するメディア
• コンカレントシステム仮想ライブラリ