Loading article…
コンピュータ科学において、同期とは、合意に達したり、特定の一連の動作を実行したりするために、複数のプロセスを特定の時点で連携させたり、ハンドシェイクしたりするように調整する作業のことである。
同期の必要性は、マルチプロセッサシステムに限らず、あらゆる種類の並行プロセス、さらにはシングルプロセッサシステムにおいても生じます。以下に、同期が必要となる主な理由をいくつか挙げます。
分岐と結合：ジョブが分岐点に到達すると、N個のサブジョブに分割され、それぞれがn個のタスクによって処理されます。処理が完了した後、各サブジョブは他のすべてのサブジョブの処理が完了するまで待機します。その後、再び結合され、システムから離脱します。このように、並列プログラミングでは、すべての並列プロセスが他の複数のプロセスの実行を待つ必要があるため、同期処理が不可欠です。
生産者-消費者関係：生産者-消費者関係では、消費者プロセスは必要なデータが生成されるまで生産者プロセスに依存します。
排他的使用リソース：複数のプロセスがリソースに依存しており、同時にアクセスする必要がある場合、オペレーティングシステムは、特定の時点でそのリソースにアクセスできるプロセッサが1つだけであることを保証する必要があります。これにより、並行処理が制限されます。
スレッド同期とは、2 つ以上の同時実行プロセスまたはスレッドが、クリティカル セクションと呼ばれる特定のプログラム セグメントを同時に実行しないようにするメカニズムです。プロセスのクリティカル セクションへのアクセスは、同期技術を使用して制御されます。1 つのスレッドがクリティカル セクション(プログラムのシリアル化されたセグメント) の実行を開始すると、他のスレッドは最初のスレッドが終了するまで待機する必要があります。適切な同期技術[ 1 ]が適用されない場合、プロセスまたはスレッドのコンテキスト スイッチのタイミングに応じて変数の値が予測不可能で変化する競合状態が発生する可能性があります。
例えば、プロセス1、2、3の3つのプロセスがあるとします。これら3つのプロセスはすべて同時に実行され、図1に示すように共通のリソース（クリティカルセクション）を共有する必要があります。この共有リソースへのアクセスに関する競合を避けるために、同期を使用する必要があります。したがって、プロセス1とプロセス2の両方がそのリソースにアクセスしようとすると、一度に1つのプロセスにのみ割り当てられる必要があります。プロセス1に割り当てられた場合、もう一方のプロセス（プロセス2）は、プロセス1がそのリソースを解放するまで待機する必要があります（図2参照）。
考慮すべきもう一つの同期要件は、特定のプロセスやスレッドを実行する順序です。例えば、航空券を購入する前に飛行機に搭乗することはできません。同様に、適切な認証情報（ユーザー名とパスワードなど）を確認する前にメールをチェックすることもできません。また、ATMも正しい暗証番号を受け取るまでサービスを提供しません。
同期は、相互排他以外にも、以下の点にも対処します。
エクサスケールアルゴリズム設計の課題の1つは、同期を最小限に抑えるか削減することです。同期は、特に分散コンピューティングでは、計算よりも時間がかかります。同期の削減は、数十年にわたりコンピュータ科学者の注目を集めてきました。一方、計算の改善とレイテンシの間のギャップが拡大するにつれて、これは最近ますます重要な問題になっています。実験では、分散コンピュータでの同期による（グローバル）通信が、疎な反復ソルバーで支配的な割合を占めていることが示されています。[ 2 ]この問題は、上位500台のスーパーコンピュータをランク付けするための新しいベンチマークメトリックである高性能共役勾配（HPCG）[ 3 ]の出現後、ますます注目を集めています。
同期に関する典型的な問題点をいくつか挙げます。
これらの問題は、新たに提案されるほぼすべての同期方式やプリミティブをテストするために使用されます。
同期オーバーヘッドは並列コンピューティング環境のパフォーマンスに大きな影響を与える可能性があり、複数のプロセスからのデータをマージすると、プロセス間通信と同期メカニズムの追加オーバーヘッドが主な原因で、同じデータを単一のスレッドで処理する場合よりも大幅に高いコスト（多くの場合2桁以上）が発生することがあります。[ 4 ] [ 5 ] [ 6 ]
多くのシステムは、クリティカルセクションコードのためのハードウェアサポートを提供している。
単一プロセッサまたはユニプロセッサシステムでは、プリエンプションなしで現在実行中のコードを実行することで割り込みを無効にすることができますが、これはマルチプロセッサシステムでは非常に非効率的です。[ 7 ] 「マルチプロセッサで同期を実装するために必要な重要な機能は、メモリ位置をアトミックに読み書きできるハードウェアプリミティブのセットです。このような機能がなければ、基本的な同期プリミティブを構築するコストが高すぎ、プロセッサ数が増えるにつれてコストも増加します。基本的なハードウェアプリミティブにはいくつかの代替的な構成があり、いずれもメモリ位置をアトミックに読み書きする機能と、読み書きがアトミックに実行されたかどうかを判断する方法を提供します。これらのハードウェアプリミティブは、ロックやバリアなど、さまざまなユーザーレベルの同期操作を構築するために使用される基本的な構成要素です。一般的に、アーキテクトはユーザーが基本的なハードウェアプリミティブを使用することを想定しておらず、代わりにシステムプログラマが同期ライブラリを構築するためにプリミティブを使用することを想定しています。同期ライブラリの構築プロセスは、多くの場合複雑で扱いにくいものです。」[ 8 ]多くの現代のハードウェアはこのようなアトミック命令を提供しており、一般的な例としては、単一のメモリワードを操作するテストアンドセットと、2 つのメモリワードの内容を交換する比較アンドスワップがあります。
Javaでは、スレッドの干渉やメモリの一貫性エラーを防ぐ方法の 1 つは、メソッド シグネチャの前にsynchronizedキーワードを付けることです。この場合、宣言オブジェクトのロックを使用して同期が強制されます。もう 1 つの方法は、コード ブロックをsynchronized(someObject){...}セクションで囲むことです。これにより、よりきめ細かい制御が可能になります。この方法では、どのスレッドも、含まれるブロックを実行する前にsomeObjectのロックを取得する必要があります。ロックは、ロックを取得したスレッドがこのブロックを離れるか、ブロック内で待機状態に入ると自動的に解放されます。synchronized ブロック内のスレッドによって行われた変数の更新は、他のスレッドが同様にロックを取得してブロックを実行すると、他のスレッドから見えるようになります。どちらの実装でも、すべての Java オブジェクトはインスタンス化時に固有のロックまたはモニタ ロックが関連付けられているため、任意のオブジェクトを使用してロックを提供できます。 [ 9 ]
Javaの同期ブロックは、相互排他とメモリの一貫性を実現するだけでなく、シグナリング、つまりロックを取得してコードブロックを実行しているスレッドから、ブロック内でロックを待っているスレッドへイベントを送信する機能も備えています。したがって、Javaの同期セクションは、ミューテックスとイベントの両方の機能を組み合わせて同期を保証します。このような構造は、同期モニタとして知られています。
.NET Frameworkも同期プリミティブを使用します。[ 10 ]「同期は協調的に設計されており、一貫した結果を得るために、すべてのスレッドが保護されたリソースにアクセスする前に同期メカニズムに従うことを要求します。ロック、シグナリング、軽量同期タイプ、スピンウェイト、インターロック操作は、.NET の同期に関連するメカニズムです。」[ 11 ]
多くのプログラミング言語は同期機能をサポートしており、厳密な決定論的同期が最重要となる組み込みアプリケーション開発向けに、専用の言語が開発されている。
同期を実装するもう 1 つの効果的な方法は、スピンロックを使用することです。共有リソースまたはコードにアクセスする前に、すべてのプロセッサはフラグをチェックします。フラグがリセットされている場合、プロセッサはフラグを設定してスレッドの実行を続行します。しかし、フラグが設定されている場合 (ロックされている場合)、スレッドはループでスピンし続け、フラグが設定されているかどうかをチェックし続けます。スピンロックは、フラグが低サイクルでリセットされる場合にのみ効果的です。そうでない場合、待機に多くのプロセッササイクルが浪費されるため、パフォーマンスの問題につながる可能性があります。[ 12 ]
バリアは実装が簡単で、応答性も良好です。バリアは、同期を実現するために待機サイクルを実装するという概念に基づいています。バリア 1 から開始して同時に実行される 3 つのスレッドを考えてみましょう。時間 t が経過すると、スレッド 1 はバリア 2 に到達しますが、正しいデータがないため、スレッド 2 と 3 がバリア 2 に到達するまで待機する必要があります。すべてのスレッドがバリア 2 に到達すると、すべてが再び開始されます。時間 t が経過すると、スレッド 1 はバリア 3 に到達しますが、スレッド 2 と 3 および正しいデータを再び待機する必要があります。
したがって、複数のスレッドのバリア同期では、上記の例のようにスレッド 1 がスレッド 2 と 3 を待ち続けるなど、常にいくつかのスレッドが他のスレッドを待つことになります。これは、プロセスのパフォーマンスの著しい低下につながります。[ 13 ]
i番目のスレッドのバリア同期待機関数は、次のように表すことができます。
(Wbarrier)i=f ((Tbarrier)i, (Rthread)i)
ここで、Wbarrierはスレッドの待機時間、Tbarrierは到着したスレッドの数、Rthreadはスレッドの到着率である。[ 14 ]
実験によると、実行時間全体の34%は他の遅いスレッドの待機に費やされている。[ 13 ]
セマフォは、1つまたは複数のスレッド/プロセッサがセクションにアクセスできるようにするシグナルメカニズムです。セマフォには、特定の固定値が関連付けられたフラグがあり、スレッドがセクションにアクセスしようとするたびに、このフラグがデクリメントされます。同様に、スレッドがセクションから離れると、フラグがインクリメントされます。フラグがゼロの場合、スレッドはセクションにアクセスできず、待機を選択した場合はブロックされます。
セマフォの中には、コードセクション内で1つのスレッドまたはプロセスのみを許可するものがあります。このようなセマフォはバイナリセマフォと呼ばれ、ミューテックスと非常によく似ています。ここでは、セマフォの値が1の場合はスレッドのアクセスが許可され、値が0の場合はアクセスが拒否されます。[ 15 ]
イベント駆動型アーキテクチャでは、リクエスト/レスポンスパラダイムを使用することで同期トランザクションを実現でき、2 つの方法で実装できます。[ 16 ]
同期は元々、オブジェクトにロックを取得できるプロセスベースの概念でした。主な用途はデータベースです。ファイルロックには、読み取り専用ロックと読み書きロックの2種類があります。読み取り専用ロックは、複数のプロセスやスレッドで取得できます。読み書きロックは排他的であり、一度に1つのプロセス/スレッドしか使用できません。
ロックはもともとファイルデータベースのために開発されたものですが、データはプロセス間やスレッド間でメモリ上で共有されることもあります。場合によっては、複数のオブジェクト（またはファイル）が同時にロックされることがあります。それらが同時にロックされない場合、ロックが重複してデッドロック例外が発生する可能性があります。
JavaとAdaが排他ロックを持つのは、それらがスレッドベースであり、比較交換プロセッサ命令に依存しているためである。
同期プリミティブの抽象的な数学的基礎は、履歴モノイドによって与えられる。また、履歴モノイドの上に構築できる、プロセス計算やペトリネットなどの高レベルの理論的手法も数多く存在する。
以下に、さまざまなプラットフォームに関する同期の例を示します。[ 17 ]
Windowsは以下を提供します：
Linuxは以下を提供します：
カーネルのプリエンプションの有効化と無効化は、単一プロセッサシステムにおけるスピンロックに取って代わった。カーネルバージョン2.6より前は、Linuxは短いクリティカルセクションを実装するために割り込みを無効にしていた。バージョン2.6以降、Linuxは完全にプリエンプティブになっている。
Solarisは以下の機能を提供します。
Pthreadsはプラットフォームに依存しないAPIであり、以下の機能を提供します。
{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク)