Loading article…
コンピュータ サイエンスにおいて、同期とは、合意に達したり、特定の一連のアクションを実行したりするために、 複数のプロセスを調整して特定の時点で結合またはハンドシェイクするタスクです。
モチベーション
同期の必要性は、マルチプロセッサ システムだけでなく、あらゆる種類の同時実行プロセス、さらにはシングルプロセッサ システムでも生じます。同期の主な必要性を次に示します。
フォークと結合:ジョブがフォーク ポイントに到達すると、ジョブは N 個のサブジョブに分割され、n 個のタスクによって処理されます。処理が終わった後、各サブジョブは他のすべてのサブジョブの処理が完了するまで待機します。その後、サブジョブは再び結合され、システムから出ます。したがって、並列プログラミングでは、すべての並列プロセスが他のいくつかのプロセスの発生を待機するため、同期が必要です。
プロデューサーとコンシューマー:プロデューサーとコンシューマーの関係では、必要なデータが生成されるまで、コンシューマー プロセスはプロデューサー プロセスに依存します。
排他的使用リソース:複数のプロセスがリソースに依存しており、同時にアクセスする必要がある場合、オペレーティング システムは、特定の時点で 1 つのプロセッサのみがそのリソースにアクセスするようにする必要があります。これにより、同時実行性が低下します。
要件
スレッド同期は、2つ以上の同時プロセスまたはスレッドが、クリティカルセクションと呼ばれる特定のプログラムセグメントを同時に実行しないようにするメカニズムとして定義されます。プロセスのクリティカルセクションへのアクセスは、同期技術を使用して制御されます。1つのスレッドがクリティカルセクション（プログラムのシリアル化されたセグメント）の実行を開始すると、他のスレッドは最初のスレッドが終了するまで待機する必要があります。適切な同期技術[1]が適用されない場合、変数の値が予測できず、プロセスまたはスレッドのコンテキストスイッチのタイミングに応じて変化する競合状態が発生する可能性があります。
たとえば、プロセス 1、2、3 の 3 つのプロセスがあるとします。3 つのプロセスはすべて同時に実行されており、図 1 に示すように、共通のリソース (クリティカル セクション) を共有する必要があります。この共有リソースへのアクセスの競合を回避するには、同期を使用する必要があります。したがって、プロセス 1 と 2 の両方がそのリソースにアクセスしようとする場合、そのリソースは一度に 1 つのプロセスにのみ割り当てる必要があります。プロセス 1 に割り当てられている場合、もう一方のプロセス (プロセス 2) は、プロセス 1 がそのリソースを解放するまで待機する必要があります (図 2 を参照)。
考慮する必要があるもう 1 つの同期要件は、特定のプロセスまたはスレッドを実行する順序です。たとえば、チケットを購入せずに飛行機に乗ることはできません。同様に、適切な資格情報 (ユーザー名とパスワードなど) を検証せずに電子メールをチェックすることはできません。同様に、ATM は正しい PIN を受信するまでサービスを提供しません。
相互排他性の他に、同期では次のことも処理されます。
- デッドロックは、多くのプロセスが、他のプロセスによって保持されている共有リソース (クリティカル セクション) を待機しているときに発生します。この場合、プロセスは待機し続けるだけで、それ以上実行されません。
- 飢餓状態は、プロセスがクリティカル セクションに入るのを待機しているときに、他のプロセスがクリティカル セクションを独占し、最初のプロセスが無期限に待機を強いられる場合に発生します。
- 優先度の逆転は、優先度の高いプロセスがクリティカル セクションにあり、優先度が中程度のプロセスによって割り込まれた場合に発生します。この優先度規則の違反は特定の状況下で発生する可能性があり、リアルタイム システムでは深刻な結果につながる可能性があります。
- ビジー待機。これは、プロセスがクリティカル セクションにアクセスできるかどうかを判断するために頻繁にポーリングするときに発生します。この頻繁なポーリングにより、他のプロセスの処理時間が奪われます。
最小化
エクサスケールアルゴリズム設計の課題の1つは、同期を最小限に抑えるか削減することです。同期は、特に分散コンピューティングでは、計算よりも時間がかかります。同期の削減は、何十年もの間、コンピュータ科学者の注目を集めてきました。一方、コンピューティングの改善とレイテンシのギャップが拡大するにつれて、最近ではますます重要な問題になっています。実験では、分散コンピュータ上の同期による（グローバル）通信が、スパース反復ソルバーで大きな割合を占めることが示されています。[2]この問題は、スーパーコンピュータのトップ500をランク付けするための 新しいベンチマークメトリックである高性能共役勾配（HPCG）[3]の出現により、ますます注目を集めています。
典型的な問題
同期に関する典型的な問題は次のとおりです。
- 生産者-消費者問題（境界バッファ問題とも呼ばれる）
- 読者と作家の問題;
- 食事をする哲学者の問題。
これらの問題は、ほぼすべての新しく提案された同期スキームまたはプリミティブをテストするために使用されます。
ハードウェア同期
多くのシステムは、クリティカル セクションコードに対してハードウェア サポートを提供します。
単一プロセッサまたは単一プロセッサのシステムでは、現在実行中のコードをプリエンプションなしで実行することで割り込みを無効にすることができますが、これはマルチプロセッサシステムでは非常に非効率的です。[4] 「マルチプロセッサで同期を実装するために必要な主要な機能は、メモリ位置をアトミックに読み取りおよび変更する機能を備えたハードウェア プリミティブのセットです。このような機能がなければ、基本的な同期プリミティブを構築するコストが高すぎ、プロセッサ数が増えるにつれて増加します。基本的なハードウェア プリミティブにはいくつかの代替定式化があり、それらはすべて、位置をアトミックに読み取りおよび変更する機能と、読み取りと書き込みがアトミックに実行されたかどうかを判断する方法を提供します。これらのハードウェア プリミティブは、ロックやバリアなど、さまざまなユーザー レベルの同期操作を構築するために使用される基本的な構成要素です。一般に、設計者はユーザーが基本的なハードウェア プリミティブを使用することを期待していません。代わりに、システム プログラマがプリミティブを使用して同期ライブラリを構築することを期待しています。これは、複雑で扱いにくいプロセスであることがよくあります。」[5]現代のハードウェアの多くはこのようなアトミック命令を提供しており、その例としては、単一のメモリワードを操作するテストアンドセットと、2つのメモリワードの内容を交換する比較アンドスワップの2つが挙げられます。
プログラミング言語のサポート
Javaでは、スレッドの干渉やメモリの一貫性エラーを防ぐ方法の 1 つは、メソッド シグネチャの前にsynchronizedキーワードを付けることです。この場合、宣言オブジェクトのロックを使用して同期が強制されます。2 つ目の方法は、コード ブロックをsynchronized(someObject){...}セクションでラップすることです。これにより、より細かい粒度の制御が可能になります。これにより、すべてのスレッドは、含まれているブロックを実行する前にsomeObjectのロックを取得することが強制されます。ロックを取得したスレッドがこのブロックを離れるか、ブロック内で待機状態に入ると、ロックは自動的に解放されます。同期ブロック内のスレッドによって行われた変数の更新は、他のスレッドが同様にロックを取得してブロックを実行すると、そのスレッドから見えるようになります。どちらの実装でも、すべての Java オブジェクトはインスタンス化時に固有のロックまたはモニター ロックが関連付けられているため、任意のオブジェクトを使用してロックを提供できます。[6]
Java の同期ブロックは、相互排他性とメモリの一貫性を可能にするだけでなく、シグナリングも可能にします。つまり、ロックを取得してコード ブロックを実行しているスレッドから、ブロック内でロックを待機しているスレッドにイベントを送信します。したがって、Java の同期セクションでは、ミューテックスとイベントの両方の機能を組み合わせて同期を保証します。このような構造は、同期モニターと呼ばれます。
.NET Frameworkも同期プリミティブを使用します。[7]「同期は協調的に設計されており、一貫した結果を得るために、保護されたリソースにアクセスする前にすべてのスレッドが同期メカニズムに従うことを要求します。ロック、シグナリング、軽量同期タイプ、スピンウェイト、インターロックされた操作は、.NET の同期に関連するメカニズムです。」[8]
多くのプログラミング言語は同期をサポートしており、厳密に決定論的な同期が最も重要である組み込みアプリケーション開発専用の言語も作成されています。
実装
スピンロック
同期を実装するもう 1 つの効果的な方法は、スピンロックを使用することです。共有リソースまたはコードにアクセスする前に、すべてのプロセッサがフラグをチェックします。フラグがリセットされている場合、プロセッサはフラグを設定し、スレッドの実行を続行します。ただし、フラグが設定されている (ロックされている) 場合、スレッドはループ内で回転し続け、フラグが設定されているかどうかを確認し続けます。ただし、スピンロックは、フラグが低いサイクルでリセットされている場合にのみ有効です。そうでない場合、待機に多くのプロセッサ サイクルが無駄になり、パフォーマンスの問題が発生する可能性があります。[9]
障壁
バリアは実装が簡単で、応答性も優れています。これは、同期を提供するために待機サイクルを実装するという概念に基づいています。バリア 1 から開始して、3 つのスレッドが同時に実行されているとします。時間 t の後、スレッド 1 はバリア 2 に到達しますが、正しいデータがないため、スレッド 2 と 3 がバリア 2 に到達するまで待機する必要があります。すべてのスレッドがバリア 2 に到達すると、すべてのスレッドが再び開始します。時間 t の後、スレッド 1 はバリア 3 に到達しますが、再びスレッド 2 と 3 と正しいデータを待機する必要があります。
したがって、複数のスレッドのバリア同期では、上記の例のようにスレッド1がスレッド2と3を待ち続けるように、他のスレッドを待つことになるスレッドが常にいくつか存在します。これにより、プロセスのパフォーマンスが著しく低下します。[10]
i番目のスレッドのバリア同期待機関数は次のように表すことができます。
(Wバリア)i=f ((Tバリア)i、(Rスレッド)i)
ここで、Wbarrierはスレッドの待機時間、Tbarrierは到着したスレッドの数、Rthreadはスレッドの到着率です。[11]
実験によると、総実行時間の34%が他の遅いスレッドを待つことに費やされていることがわかりました。[10]
セマフォ
セマフォは、1 つ以上のスレッド/プロセッサがセクションにアクセスできるようにするシグナル メカニズムです。セマフォには、特定の固定値が関連付けられたフラグがあり、スレッドがセクションにアクセスするたびに、フラグが減算されます。同様に、スレッドがセクションを離れると、フラグが増分されます。フラグが 0 の場合、スレッドはセクションにアクセスできず、待機することを選択した場合はブロックされます。
一部のセマフォでは、コードセクションに1つのスレッドまたはプロセスのみを許可します。このようなセマフォはバイナリセマフォと呼ばれ、ミューテックスに非常に似ています。ここで、セマフォの値が1の場合、スレッドはアクセスを許可され、値が0の場合、アクセスは拒否されます。[12]
数学の基礎
同期は、もともとプロセス ベースの概念であり、オブジェクトに対してロックを取得できます。同期は主にデータベースで使用されます。(ファイル)ロックには、読み取り専用と読み取り/書き込みの 2 種類があります。読み取り専用ロックは、多くのプロセスまたはスレッドによって取得できます。読み取り/書き込みロックは排他的であり、一度に 1 つのプロセス/スレッドによってのみ使用できます。
ロックはファイル データベース用に派生したものですが、データはプロセスとスレッド間でメモリ内で共有されることもあります。 複数のオブジェクト (またはファイル) が同時にロックされることもあります。 同時にロックされない場合、ロックが重複してデッドロック例外が発生する可能性があります。
JavaとAda はスレッドベースであり、比較とスワップのプロセッサ命令に依存しているため、排他ロックのみを備えています。
同期プリミティブの抽象的な数学的基礎は、履歴モノイドによって与えられます。また、プロセス計算やペトリネットなど、履歴モノイドの上に構築できる高レベルの理論的デバイスも多数あります。
例
以下はさまざまなプラットフォームにおける同期の例です。[13]
Windowsの場合
Windows は以下を提供します:
- 割り込みマスク。単一プロセッサ システム上のグローバル リソース (クリティカル セクション) へのアクセスを保護します。
- スピンロックは、マルチプロセッサ システムでスピンロック スレッドがプリエンプトされるのを防ぎます。
- 動的ディスパッチャ[要出典]は、ミューテックス、セマフォ、イベント、タイマーのように動作します。
Linuxの場合
Linux は以下を提供します:
- セマフォ;
- スピンロック;
- 障壁;
- ミューテックス;
- 非常に頻繁にアクセスされるが、あまり頻繁に変更されない長いコードセクション用のリーダー/ライター ロック。
- 読み取り・コピー・更新（RCU）。[14]
カーネル プリエンプションの有効化と無効化により、ユニプロセッサ システム上のスピンロックが置き換えられました。カーネル バージョン 2.6 より前では、Linux は短いクリティカル セクションを実装するために割り込みを無効にしていました。バージョン 2.6 以降では、Linux は完全にプリエンプティブです。
Solarisの場合
Solaris は以下を提供します:
Pthreadsでは
Pthreads は、以下を提供するプラットフォームに依存しないAPIです。
- ミューテックス;
- 条件変数;
- リーダー/ライターロック;
- スピンロック;
- 障壁。
参照
参考文献
- ^ Gramoli, V. (2015). 同期について知りたいこと以上のこと: Synchrobench、同時実行アルゴリズムに対する同期の影響を測定(PDF)。第 20 回 ACM SIGPLAN 並列プログラミングの原理と実践に関するシンポジウムの議事録。ACM。pp. 1–10。
- ^ Shengxin, Zhu、Tongxiang Gu、 Xingping Liu (2014)。「分散型スーパーコンピューターのスパース反復ソルバーの同期の最小化」。Computers & Mathematics with Applications。67 ( 1): 199–209。doi : 10.1016/j.camwa.2013.11.008。
- ^ 「HPCGベンチマーク」。
- ^ Silberschatz, Abraham; Gagne, Greg; Galvin, Peter Baer (2008 年 7 月 11 日)。「第 6 章: プロセス同期」。オペレーティング システムの概念(第 8 版)。John Wiley & Sons。ISBN 978-0-470-12872-5。
- ^ Hennessy, John L.; Patterson, David A. (2011 年 9 月 30 日)。「第 5 章: スレッドレベルの並列処理」。コンピュータ アーキテクチャ: 定量的アプローチ(第 5 版)。Morgan Kaufmann。ISBN 978-0-123-83872-8。
- ^ 「固有ロックと同期」。Javaチュートリアル。Oracle 。 2023年11月10日閲覧。
- ^ 「同期プリミティブの概要」。Microsoft Learn。Microsoft。2022年 9 月。2023 年11 月 10 日に閲覧。
- ^ Rouse, Margaret. 「同期」。Techopedia 。 2023年11月10日閲覧。
- ^ マッサ、アンソニー (2003)。ECosによる組み込みソフトウェア開発。ピアソン エデュケーション社。ISBN 0-13-035473-2。
- ^ ab Meng、Chen、Pan、Yao、Wu、Jinglei、Tianzhou、Ping、Jun. Minghui (2014)。「バリア同期のための推測メカニズム」。2014 IEEE 国際高性能コンピューティングおよび通信会議 (HPCC)、2014 IEEE 第 6 回サイバースペースの安全性とセキュリティに関する国際シンポジウム (CSS)、および 2014 IEEE 第 11 回組み込みソフトウェアおよびシステムに関する国際会議 (ICESS)。
{{cite journal}}: CS1 maint: multiple names: authors list (link) - ^ Rahman, Mohammed Mahmudur (2012). 「マルチプロセッサおよびマルチコアプロセッサにおけるプロセス同期」2012 International Conference on Informatics, Electronics & Vision (ICIEV) pp. 554–559. doi :10.1109/ICIEV.2012.6317471. ISBN 978-1-4673-1154-0. S2CID 8134329。
- ^ Li, Yao, Qing, Carolyn (2003).組み込みシステム向けリアルタイムコンセプト. CMP Books. ISBN 978-1578201242。
{{cite book}}: CS1 maint: multiple names: authors list (link) - ^ Silberschatz, Abraham; Gagne, Greg; Galvin, Peter Baer (2012 年 12 月 7 日)。「第 5 章: プロセス同期」。オペレーティング システムの概念(第 9 版)。John Wiley & Sons。ISBN 978-1-118-06333-0。
- ^ 「RCU とは、根本的に何ですか? [LWN.net]」。lwn.net。
- ^ 「アダプティブ ロック プローブ」。Oracle Docs。
- ^ マウロ、ジム。「ターンスタイルと優先権継承 - SunWorld - 1999 年 8 月」。sunsite.uakom.sk。
- シュナイダー、フレッド B. (1997)。並行プログラミングについて。Springer-Verlag New York, Inc. ISBN 978-0-387-94942-0。
外部リンク
- IBM developerWorks の Linux 同期方法の分析
- セマフォの小冊子、アレン・B・ダウニー著
- プロセス同期の必要性