同期(コンピュータサイエンス)

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

コンピュータサイエンスでは同期とは、プロセスの同期とデータの同期という、2つの異なるが関連する概念の1つを指しますプロセスの同期とは、合意に達するか、特定の一連のアクションにコミットするために、複数のプロセスが特定の時点で参加またはハンドシェイクするという考え方を指します。データ同期とは、データセットの複数のコピーを相互に整合性を保つ、またはデータの整合性を維持するという考え方を指します。プロセス同期プリミティブは、データ同期を実装するために一般的に使用されます。

同期の必要性

同期の必要性は、マルチプロセッサシステムだけでなく、あらゆる種類の並行プロセスで発生します。シングルプロセッサシステムでも。同期の主なニーズのいくつかを以下に示します。

同時に2つ以上の作品


フォークと結合ジョブがフォークポイントに到着すると、N個のサブジョブに分割され、n個のタスクによって処理されます。サービスが提供された後、各サブジョブは他のすべてのサブジョブの処理が完了するまで待機します。その後、それらは再び結合され、システムを離れます。したがって、すべての並列プロセスは他のいくつかのプロセスが発生するのを待つため、並列プログラミングには同期が必要です。

生産者/消費者:生産者/消費者関係では、必要なデータが生成されるまで、消費者プロセスは生産者プロセスに依存します。

排他的使用リソース:複数のプロセスがリソースに依存していて、それらが同時にリソースにアクセスする必要がある場合、オペレーティングシステムは、特定の時点で1つのプロセッサのみがリソースにアクセスするようにする必要があります。これにより、同時実行性が減少します。

スレッドまたはプロセスの同期

図1:共有リソース(クリティカルセクション)に同時にアクセスする3つのプロセス。

スレッドの同期は、2つ以上の同時プロセスまたはスレッドがクリティカルセクションと呼ばれる特定のプログラムセグメントを同時に実行しないようにするメカニズムとして定義されます。クリティカルセクションへのプロセスのアクセスは、同期技術​​を使用して制御されます。一方のスレッドがクリティカルセクション(プログラムのシリアル化されたセグメント)の実行を開始すると、もう一方のスレッドは最初のスレッドが終了するまで待機する必要があります。適切な同期手法[1]が適用されない場合、変数の値が予測できず、プロセスまたはスレッド のコンテキストスイッチのタイミングによって異なる競合状態が発生する可能性があります。

たとえば、1、2、3の3つのプロセスがあるとします。これらはすべて同時に実行されており、図1に示すように、共通のリソース(クリティカルセクション)を共有する必要があります。この共有リソースにアクセスするための競合を回避します。したがって、プロセス1と2の両方がそのリソースにアクセスしようとする場合、一度に1つのプロセスにのみ割り当てる必要があります。プロセス1に割り当てられている場合、他のプロセス(プロセス2)は、プロセス1がそのリソースを解放するまで待機する必要があります(図2を参照)。

図2:同期技術に基づいて、利用可能な場合は共有リソースにアクセスするプロセス。

考慮する必要があるもう1つの同期要件は、特定のプロセスまたはスレッドを実行する順序です。たとえば、チケットを購入する前に飛行機に搭乗することはできません。同様に、適切な資格情報(たとえば、ユーザー名やパスワード)を検証する前に電子メールをチェックすることはできません。同様に、ATMは正しいPINを受信するまでサービスを提供しません。

相互排除以外に、同期は次のことも処理します。

  • デッドロック。これは、他のプロセスによって保持されている共有リソース(クリティカルセクション)を多くのプロセスが待機している場合に発生します。この場合、プロセスは待機を続け、それ以上実行されません。
  • プロセスがクリティカルセクションに入るのを待っているが、他のプロセスがクリティカルセクションを独占し、最初のプロセスが無期限に待機することを余儀なくされたときに発生する飢餓。
  • 優先順位の逆転。これは、優先度の高いプロセスがクリティカルセクションにあり、優先度の高いプロセスによって中断された場合に発生します。この優先ルールの違反は、特定の状況下で発生する可能性があり、リアルタイムシステムに深刻な結果をもたらす可能性があります。
  • ビジー待機。これは、プロセスがクリティカルセクションにアクセスできるかどうかを判断するために頻繁にポーリングするときに発生します。この頻繁なポーリングにより、他のプロセスから処理時間が奪われます。

同期の最小化

エクサスケールアルゴリズム設計の課題の1つは、同期を最小化または削減することです。特に分散コンピューティングでは、同期は計算よりも時間がかかります。同期を減らすことは、何十年にもわたってコンピューター科学者から注目を集めました。一方、コンピューティングの改善とレイテンシーのギャップが大きくなるにつれて、最近ますます重大な問題になっています。実験によると、分散コンピューターでの同期による(グローバル)通信は、スパース反復ソルバーで支配的なシェアを占めます。[2]この問題は、上位500台のスーパーコンピューターをランク付けするため の新しいベンチマークメトリックであるHigh Performance Conjugate Gradient(HPCG) [3]の出現後、ますます注目を集めています。

同期の古典的な問題

以下は、同期のいくつかの典型的な問題です。

これらの問題は、新しく提案されたほぼすべての同期スキームまたはプリミティブをテストするために使用されます。

ハードウェア同期

多くのシステムは、クリティカルセクションコード のハードウェアサポートを提供します。

シングルプロセッサまたはユニプロセッサシステムは、プリエンプションなしで現在実行中のコードを実行することによって割り込みを無効にする可能性があります。これは、マルチプロセッサシステムでは非常に非効率的です。[4] 「マルチプロセッサで同期を実装するために必要な主要な機能は、メモリ位置をアトミックに読み取って変更する機能を備えたハードウェアプリミティブのセットです。このような機能がないと、基本的な同期プリミティブを構築するコストが高すぎて、次のように増加します。プロセッサ数が増加します。基本的なハードウェアプリミティブにはいくつかの代替定式化があり、それらはすべて、読み取りと書き込みがアトミックに実行されたかどうかを判断する方法とともに、場所をアトミックに読み取りおよび変更する機能を提供します。これらのハードウェアプリミティブロックバリアなど、さまざまなユーザーレベルの同期操作を構築するために使用される基本的な構成要素です。一般に、アーキテクトは、ユーザーが基本的なハードウェアプリミティブを使用することを期待していませんが、代わりに、システムプログラマーが、複雑でトリッキーなプロセスである同期ライブラリを構築するためにプリミティブを使用することを期待しています。」[ 5]メモリワードをテストアンドセットするか、2つのメモリワードの内容を コンペアアンドスワップすることによる特別なアトミックハードウェア命令。

プログラミング言語での同期戦略

Javaでは、スレッドの干渉とメモリの整合性エラーを防ぐために、コードのブロックは同期された (lock_object)セクションにラップされます。これにより、スレッドはブロックを実行する前に、上記のロックオブジェクトを取得するように強制されます。ロックを取得してブロックを実行しているスレッドがブロックを離れるか、ブロック内で待機状態になると、ロックは自動的に解放されます。同期されたブロック内のスレッドによって行われた変数の更新は、他のスレッドが同様にロックを取得してブロックを実行すると、他のスレッドから見えるようになります。

Java同期ブロックは、相互排除とメモリの一貫性を有効にすることに加えて、シグナリングを有効にします。つまり、ロックを取得してコードブロックを実行しているスレッドから、ブロック内でロックを待機しているスレッドにイベントを送信します。これは、Java同期セクションがミューテックスとイベントの機能を組み合わせていることを意味します。このようなプリミティブは、同期モニターとして知られています。

Javaでは、任意のオブジェクトをロック/モニターとして使用できます。メソッド全体がsynchronizedでマークされている場合、宣言オブジェクトはロックオブジェクトです。

.NET Frameworkには、同期プリミティブがあります。「同期は協調するように設計されており、一貫した結果を得るために、保護されたリソース(クリティカルセクション)にアクセスする前に、すべてのスレッドまたはプロセスが同期メカニズムに従う必要があります。」.NETでは、ロック、シグナリング、軽量同期タイプ、スピンウェイト、およびインターロック操作は、同期に関連するメカニズムの一部です。[6]

同期の実装

スピンロック

同期を実装するもう1つの効果的な方法は、スピンロックを使用することです。共有リソースまたはコードの一部にアクセスする前に、すべてのプロセッサがフラグをチェックします。フラグがリセットされると、プロセッサはフラグを設定し、スレッドの実行を続行します。ただし、フラグが設定されている(ロックされている)場合、スレッドはループで回転し続け、フラグが設定されているかどうかをチェックし続けます。ただし、スピンロックは、フラグがより低いサイクルでリセットされた場合にのみ有効です。そうでない場合、待機中の多くのプロセッササイクルを浪費するため、パフォーマンスの問題が発生する可能性があります。[7]

バリア

バリアは実装が簡単で、優れた応答性を提供します。これらは、同期を提供するために待機サイクルを実装するという概念に基づいています。バリア1から開始して3つのスレッドが同時に実行されているとします。時間tの後、スレッド1はバリア2に到達しますが、正しいデータがないため、スレッド2と3がバリア2に到達するまで待機する必要があります。すべてのスレッドがバリア2に到達すると、すべてが再開されます。時間tの後、スレッド1はバリア3に到達しますが、スレッド2と3、および正しいデータを再度待機する必要があります。

したがって、複数のスレッドのバリア同期では、上記の例のように、スレッド1がスレッド2と3を待機し続けるように、他のスレッドを待機するスレッドが常にいくつかあります。これにより、プロセスパフォーマンスが大幅に低下します。[8]

i番目のスレッドのバリア同期待機関数は次のように表すことができます。

(Wbarrier)i = f((Tbarrier)i、(Rthread)i)

ここで、Wbarrierはスレッドの待機時間、Tbarrierは到着したスレッドの数、Rthreadはスレッドの到着率です。[9]

実験によると、合計実行時間の34%が、他の低速スレッドの待機に費やされています。[8]

セマフォ

セマフォは、1つ以上のスレッド/プロセッサがセクションにアクセスできるようにするシグナリングメカニズムです。セマフォには、特定の固定値が関連付けられたフラグがあり、スレッドがセクションにアクセスするたびに、フラグがデクリメントされます。同様に、スレッドがセクションを離れると、フラグがインクリメントされます。フラグがゼロの場合、スレッドはセクションにアクセスできず、待機することを選択するとブロックされます。

一部のセマフォでは、コードセクションで1つのスレッドまたはプロセスのみが許可されます。このようなセマフォはバイナリセマフォと呼ばれ、Mutexと非常によく似ています。ここで、セマフォの値が1の場合、スレッドはアクセスを許可され、値が0の場合、アクセスは拒否されます。[10]

数学的基礎

同期は元々、オブジェクトのロックを取得できるプロセスベースの概念でした。その主な用途はデータベースでした。(ファイル)ロックには2つのタイプがあります。読み取り専用および読み取り/書き込み。読み取り専用ロックは、多くのプロセスまたはスレッドによって取得される可能性があります。リーダー-ライターロックは、一度に1つのプロセス/スレッドでのみ使用できるため、排他的です。

ロックはファイルデータベースに対して派生しましたが、データはプロセスとスレッドの間でメモリ内でも共有されます。一度に複数のオブジェクト(またはファイル)がロックされる場合があります。それらが同時にロックされていない場合、それらは重なり合う可能性があり、デッドロック例外が発生します。

JavaAdaは、スレッドベースであり、コンペアアンドスワッププロセッサ命令 に依存しているため、排他ロックのみがあります。

同期プリミティブの抽象的な数学的基礎は、履歴モノイドによって与えられます。プロセス計算ペトリネットなど、履歴モノイドの上に構築できる 高レベルの理論的デバイスも多数あります。

同期の例

以下は、さまざまなプラットフォームに関するいくつかの同期の例です。[11]

Windowsでの同期

Windowsは以下を提供します:

Linuxでの同期

Linuxは以下を提供します:

カーネルプリエンプションの有効化と無効化により、ユニプロセッサシステムのスピンロックが置き換えられました。カーネルバージョン2.6より前では、Linuxは割り込みを無効にして短いクリティカルセクションを実装していました。バージョン2.6以降では、Linuxは完全にプリエンプティブです。

Solarisでの同期

Solarisは以下を提供します:

Pthreadの同期

Pthreadsは、プラットフォームに依存しないAPIであり、以下を提供します。

  • ミューテックス;
  • 条件変数;
  • リーダー-ライターロック;
  • スピンロック;
  • 障壁

データ同期

図3:サーバーとクライアントの両方からの変更が同期されます。

明らかに異なる(しかし関連する)概念は、データ同期の概念です。これは、データセットの複数のコピーを相互にコヒーレントに保つか、データの整合性を維持する必要があることを意味します(図3)。たとえば、データベースレプリケーションは、データの複数のコピーを、異なる場所にデータを格納するデータベースサーバーと同期させるために使用されます。 。

例は次のとおりです。

データ同期の課題

ユーザーがデータ同期で直面する可能性のあるいくつかの課題:

  • データ形式の複雑さ。
  • リアルタイム性;
  • データセキュリティ;
  • データ品質;
  • パフォーマンス。

データ形式の複雑さ

データ形式は、組織が成長し進化するにつれて、時間とともにより複雑になる傾向があります。これにより、2つのアプリケーション(ソースとターゲット)間に単純なインターフェイスを構築するだけでなく、データをターゲットアプリケーションに渡すときにデータを変換する必要が生じます。ETL(抽出変換読み込み)ツールは、この段階でデータ形式の複雑さを管理するのに役立ちます。

リアルタイム性

リアルタイムシステムでは、顧客はe-shopでの注文の現在のステータス、小包の配達の現在のステータス(リアルタイムの小包追跡)、アカウントの現在の残高などを確認したいと考えています。これは、リアルタイムシステムも更新されており、リアルタイムでスムーズな製造プロセスを可能にします。たとえば、企業の在庫がなくなったときの材料の注文、顧客の注文と製造プロセスの同期などです。実生活からは、非常に多くのことが存在します。リアルタイム処理が成功し、競争上の優位性をもたらす例。

データセキュリティ

データセキュリティを実施するための固定されたルールやポリシーはありません。使用しているシステムによって異なる場合があります。データをキャプチャするソースシステムでセキュリティが正しく維持されている場合でも、情報の潜在的な誤用を防ぐために、セキュリティと情報アクセスの特権をターゲットシステムにも適用する必要があります。これは深刻な問題であり、特に秘密、機密、個人情報の取り扱いに関しては深刻です。したがって、機密性と機密性のために、データ転送とその間のすべての情報を暗号化する必要があります。

データ品質

データ品質はもう1つの深刻な制約です。管理を改善し、データの品質を維持するための一般的な方法は、データを1つの場所に保存し、さまざまな場所のさまざまな人やさまざまなシステムやアプリケーションと共有することです。データの不整合を防ぐのに役立ちます。

パフォーマンス

データ同期プロセスには、次の5つの異なるフェーズが含まれます。

これらの各ステップは重要です。大量のデータの場合、パフォーマンスへの悪影響を回避するために、同期プロセスを慎重に計画して実行する必要があります。

も参照してください

  • 未来と約束、純粋な機能パラダイムにおける同期メカニズム

参考文献

  1. ^ Gramoli、V。(2015)。同期について知りたいと思ったこと以上に:Synchrobench、並行アルゴリズムに対する同期の影響の測定(PDF)並列プログラミングの原理と実践に関する第20回ACMSIGPLANシンポジウムの議事録。ACM。pp。1–10。
  2. ^ Shengxin、Zhu、Tongxiang Gu、Xingping Liu(2014)。「分散型スーパーコンピューターのスパース反復ソルバーでの同期の最小化」コンピュータと数学とアプリケーション67(1):199–209。土井10.1016 /j.camwa.2013.11.008
  3. ^ 「HPCGベンチマーク」
  4. ^ シルバーシャッツ、アブラハム; ガニェ、グレッグ; Galvin、Peter Baer(2008年7月11日)。「第6章:プロセスの同期」。オペレーティングシステムの概念(第8版)。ジョン・ワイリー&サンズ。ISBN 978-0-470-12872-5
  5. ^ ヘネシー、ジョンL。; パターソン、デビッドA.(2011年9月30日)。「第5章:スレッドレベルの並列処理」。コンピュータアーキテクチャ:定量的アプローチ(第5版)。モーガンカウフマン。ISBN 978-0-123-83872-8
  6. ^ 「。NETFrameworkの同期プリミティブ」MSDN、Microsoft DeveloperNetworkMicrosoft 2014年11月23日取得
  7. ^ マッサ、アンソニー(2003)。ECosによる組み込みソフトウェア開発Pearson Education Inc. ISBN 0-13-035473-2
  8. ^ a b Meng、Chen、Pan、Yao、Wu、Jinglei、Tianzhou、Ping、Jun。Minghui(2014)。「バリア同期の投機的メカニズム」。2014 IEEE International Conference on High Performance Computing and Communications(HPCC)、2014 IEEE 6th International Symposium on Cyber​​space Safety and Security(CSS)、および2014 IEEE 11th International Conference on Embedded Software and Systems(ICESS){{cite journal}}: CS1 maint: multiple names: authors list (link)
  9. ^ Rahman、Mohammed Mahmudur(2012)。「マルチプロセッサおよびマルチコアプロセッサでのプロセス同期」。2012情報学、電子工学、ビジョンに関する国際会議(ICIEV)pp。554–559。土井10.1109 /ICIEV.2012.6317471ISBN 978-1-4673-1154-0
  10. ^ Li、Yao、Qing、Carolyn(2003)。組み込みシステムのリアルタイムコンセプトCMPブック。ISBN 978-1578201242
  11. ^ シルバーシャッツ、アブラハム; ガニェ、グレッグ; Galvin、Peter Baer(2012年12月7日)。「第5章:プロセスの同期」。オペレーティングシステムの概念(第9版)。ジョン・ワイリー&サンズ。ISBN 978-1-118-06333-0
  12. ^ 「基本的にRCUとは何ですか?[LWN.net]」lwn.net
  13. ^ マウロ、ジム。「回転式改札口と優先度継承-SunWorld- 1999年8月」sunsite.uakom.sk
  • シュナイダー、フレッドB.(1997)。並行プログラミングについてSpringer-Verlag New York、Inc。ISBN 978-0-387-94942-0

外部リンク