# 同期プリミティブ ## 定義 同期プリミティブは、信号機が交差点へのアクセスを規整するのと同じように、メモリアクセスを規整してデータの完全性を保障する仕組みであり、トラフィックの流れを停止させるぶんの待ち時間(レイテンシ)を発生させる。広く使われている同期プリミティブは次の4種類である。(1) ミューテックスロック(MUTually EXclusive lock): ロックを持つスレッドだけがCPUを使え、他のスレッドはブロックされてoff-CPUで待つ。(2) スピンロック(spin lock): ロックを持つスレッドが処理を実行できる点は同じだが、他のスレッドはon-CPUのままタイトループでロック解放をチェックする。レイテンシの低いアクセスを提供する一方、スピン中にCPUリソースを無駄にする。(3) RWロック(RW lock): リーダーライターロック。複数のリーダーを認めてライターを認めないか、単一のライターだけを認めてリーダーを一切認めないかのどちらかでデータ完全性を保証する。(4) セマフォ: 指定した数までのスレッドの並列処理を認めるか、単一スレッドの実行だけを認める(実質的にミューテックスロックになる)かを選べる。(Source: [[@2023__OReillyJapan__詳解 システム・パフォーマンス 第2版 - Chapter 5 アプリケーション]] §5.2.5.1) ミューテックスロックは、ライブラリまたはカーネルでスピンロックとミューテックスロックのハイブリッドとして実装されることがある。Linuxでは2009年に初めて実装され、ロックの状態によって次の3パスを通るアダプティブ実装になっている。(1) fastpath: cmpxchg命令でオーナーとなりロック獲得を試みる(どのスレッドもロックを保持していないときのみ成功)。(2) midpath(楽観的スピン、optimistic spinning): ロックの保持者が実行中であれば、すぐに解放されブロックせずに獲得できることを期待してCPUスケジューリングを受けながらスピンする。(3) slowpath: スレッドをブロックし、あとでロックが獲得できるようになったら起こす。Linuxのread-copy-update(RCU)メカニズムはカーネルコードで多用される別種の同期メカニズムで、読み出し処理をロックなしで実行できるようにする。書き込みは保護されたデータのコピーを作って更新し、処理中の読み出しはオリジナルにアクセスし続け、リーダーがいなくなったことを検知してからもとのデータを置き換える。(Source: [[@2023__OReillyJapan__詳解 システム・パフォーマンス 第2版 - Chapter 5 アプリケーション]] §5.2.5.1) ### ロックのハッシュテーブル 大量のデータ構造体のために最適な数のロックを使い回すには、ロックのハッシュテーブルが使われる。全データ構造に1個のグローバルミューテックスを使う方法は単純だが競合によるレイテンシが高く、全データ構造に個別ロックを与える方法は競合こそ減るがストレージ・CPUオーバーヘッドが増える。ロックのハッシュテーブルはこの中間解で、決められた数のロックを作りハッシュアルゴリズムでどのデータ構造にどのロックを使うかを選択する。ハッシュの衝突が起きた入力データ構造は同じバケットのハッシュチェインに連結されるが、ハッシュチェインは1個のロックだけで保護され長時間保持されうるため、チェインが長くなりすぎるとパフォーマンス障害が起きる。バケット数は最大限の並列処理のためCPU個数以上にすべきである。ロックを配列として隣接配置すると、複数のロックが同じキャッシュラインに入り、異なるCPUが同じキャッシュラインの別々のロックを更新しようとして互いのキャッシュラインを無効化し合う「偽共有(false sharing)」が起きる。一般にこれは、ロックの間に未使用バイトをパディングして1キャッシュラインに1ロックだけになるようにして解決する。(Source: [[@2023__OReillyJapan__詳解 システム・パフォーマンス 第2版 - Chapter 5 アプリケーション]] §5.2.5.2) ロックに関連するパフォーマンス障害の調査は時間がかかり、アプリケーションのソースコードの知識を要することが多く、通常は開発者の仕事である。スピンロックやアダプティブミューテックスロックの競合はCPU使用率に現れやすく、スタックトレースからのCPUプロファイリングで見つけられることが多いが、ブロックされスリープしているスレッドはCPUプロファイリングでは見えない。(Source: [[@2023__OReillyJapan__詳解 システム・パフォーマンス 第2版 - Chapter 5 アプリケーション]] §5.2.5.1, §5.4.6) ## 横断的知見 - (このconceptは本ソース1件からの立ち上げ。カーネル内部のロック実装([[Linux]]カーネルソース等)や別のロックフリーデータ構造系ソースとの突き合わせで横断的知見を蓄積する。) ## 未解決の問い - ロックのハッシュテーブルにおけるバケット数の選び方(CPU数以上という指針)と、実際のワークロードでの最適なバケット数の関係を定量化した一次資料はあるか。 - 偽共有(false sharing)対策のパディングは、キャッシュライン長がCPUアーキテクチャによって異なる(64バイト/128バイト等)場合にどう移植性を確保すべきか。 - Linuxのアダプティブミューテックス(fastpath/midpath/slowpath)とRCUを、同一ワークロードで比較したベンチマーク・スループット/レイテンシデータは本wikiに未収載。 ## 関連 - ソース: [[@2023__OReillyJapan__詳解 システム・パフォーマンス 第2版 - Chapter 5 アプリケーション]](§5.2.5.1〜§5.2.5.2) - 書籍: [[詳解 システム・パフォーマンス 第2版]] - 概念: [[アプリケーション並行実行モデル]] / [[フレームグラフ]] ## 出典 - [[@2023__OReillyJapan__詳解 システム・パフォーマンス 第2版 - Chapter 5 アプリケーション]](§5.2.5.1 同期プリミティブ、§5.2.5.2 ハッシュテーブル、§5.4.6 ロック分析)