【第8回】元東大教員から学ぶLinuxカーネル「同期」

こういった私から学べます．

前回を読んでいない方はこちらからどうぞ．

Linuxカーネルの記事一覧はこちらからどうぞ．

LinuxカーネルはC言語で書かれています．

私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．

私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！

独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！

今回のテーマは同期です．

同期を理解すると，カーネルの本質的な課題が深く理解できます．

本記事はとても長いので，時間がある時に読み込みましょう！

同期の背景

まずは同期が必要になる背景を紹介します．

データ量とシングルコアプロセッサの性能向上の限界

同期の背景としてデータ量とシングルコアプロセッサ（ユニプロセッサ）の性能向上の限界が挙げられます．

データ量はすでに指数関数的に増加していることが挙げられます．

• The Exponential Growth of Data
• Big Data for Operational Efficiency of Transport and Logistics: A Review

2020年代で世界中のデータ量は，数十～数百エクサバイトにも達すると予想されています．

※1エクサバイト = 100万（\(10^6\)）テラバイトです．

このような大量のデータを処理するためには，コンピュータの性能向上は必要不可欠です．

CPUのクロック周波数を上げることは，消費電力（周波数が高くなると消費電力が高くなる）や配線遅延（1クロックで1本の配線ができる範囲）から難しい状況になっています．

また，命令レベル並列化（ILP：Instruction-Level Parallelism）の限界も影響しています．

1980年代はトランジスタの増加により，スーパースカラ方式やパイプライン方式が進歩することで，10 CPI（Cycles Per Instruction）から1 CPIに削減できました．

1990年代はマルチウェイ実行（同時に複数の命令を実行），アウトオブオーダー実行（命令の順番を変えて実行），分岐予測（if文の真偽を予測）により，1 CPIから0.5 CPIに削減できました．

しかしながら，2010年代以降ではシングルコアプロセッサの性能はほとんど向上していません．

マルチコア（メニーコア）プロセッサ時代の到来

2010年代以降では，シングルコアプロセッサからマルチコア（メニーコア）プロセッサへの転換が標準のアプローチとなりました．

マルチコア（メニーコア）プロセッサ時代の到来です！

※メニーコアプロセッサは厳密な定義はないですが，16～32コア以上のプロセッサのことを指す場合が多いです．

マルチコアプロセッサにより，消費電力の上昇を抑えながら，並列処理による性能向上を実現します．

ここで，1965年に発表されたムーアの法則は，大規模集積回路のトランジスタの数が約2年ごとに2倍になります．

2007年以前は，シングルコアプロセッサの高速化として，プロセッサのパイプラインの深化，分岐予測，アウトオブオーダー実行に利用されたことで，ムーアの法則通りに成長しました．

2007年以降は，チップ内のコア数を増やすマルチコアプロセッサに利用されているため，こちらもムーアの法則通りに成長しています．

ムーアの法則は，こちらの動画がわかりやすいです．

代表的なメニーコアプロセッサとして以下が挙げられます．

• Intel Xeon Platinum 8380：基本2.3GHz（最大3.4GHz），40コア/80スレッド
• AMD EPYC 7763：基本2.45GHz（最大3.5GHz），64コア/128スレッド
• ARM Altra MAX M128-30：基本2.8GHz（最大3.0GHz），128コア
• MPPA3-80 Coolidge：基本600MHz（最大1.2GHz），80コア

マルチコアプロセッサでは，小さな逐次的処理は性能向上において重要になります．

アムダールの法則は，タスクの実行に関する理論的な性能向上の上限を算出する法則のことです．

アムダールの法則による性能向上率Sは下式になります．

$$S = \frac{1}{(1 - P + P / N)}$$

ここで，Pは高速化によって影響を受ける部分の割合，Nはコア数になります．

アムダールの法則の解説は，こちらの動画がわかりやすいです．

逐次的な処理は以下になります．

• アプリケーション：シーケンシャルアルゴリズム
• ライブラリ：メモリアロケータ（バディ構造）
• OSカーネル
  • メモリ管理：VMA （仮想メモリ領域）
  • ファイルシステム：ファイルディスクリプタテーブル，ジャーナリング
  • ネットワークスタック：受信キュー

スケーラブルな設計・実装であっても，アプリケーションはスケーラブルでない場合があります．

そこで，本記事では，スケーラビリティの課題となる同期の概念について解説していきます．

同期

クリティカルセクション

同期を理解するためには，まずはカーネルのメモリモデルを学びましょう．

カーネルは共有メモリモデルでプログラムされています．

共有データにアクセスし，操作するためには，クリティカルセクションを理解する必要があります．

クリティカルセクションは，コンピュータ上において，単一の計算資源に対して，複数の処理が同時期に実行されると，破綻をきたす部分を指します．

クリティカルセクションにおいては，排他制御を行うなどしてアトミック性を確保する必要があります．

また，マルチコアプロセッサでも，クリティカルセクションは並列に実行してはいけませんので，必ず逐次的に実行します．

2つ以上のスレッドが同じクリティカルセクションを同時に実行すると競合状態と呼ばれるバグが発生します！

カーネルにおける並行データアクセスのケースを紹介します．

マルチコアプロセッサで実際の並行アクセスやシングルコアでのプリエンプションは，ユーザ空間のスレッドプログラミングと同じです．

これに対して，割り込みは，カーネル空間のプログラミングのみです．

割り込みコンテキストでアクセスされるデータ構造は，Top HalfかBottom Halfかが重要になります．

クリティカルセクションのATMによる実例

クリティカルセクションのATMによる実例を紹介します．

上記にATMからお金を引き出すwithdraw_money関数を示します．

withdraw_money関数を逐次的に実行する場合は正常に動作します．

ここで複数のATMからの同時出金をした場合はどうなるのでしょうか？

例えば，以下の場合は「(100円 + 50円) > 110円」なので，どちらかの取引は失敗するはずです．

• total：110円
• withdrawal：100円
• withdrawal2：50円

不正確なシナリオの可能性は以下になります．

1. 3行目：2つのスレッドが100 < 110と50 < 110を確認する．
2. 9行目：update_total関数でスレッド1が更新（total = 110 - 100 = 10）
3. 9行目：update_total関数でスレッド2が更新（total = 110 - 50 = 60）

合計の出金金額は150円ですが，60円が口座に残っています．

特定の操作の間，口座をロックする必要があり，各トランザクションをアトミック操作で実行する必要があります．

このアトミック操作中のコードがクリティカルセクションになります！

1つの変数の更新

上記のfoo関数で1つの変数の更新を考察します．

以下の疑問に回答していきます．

• 2つのスレッドが同時にfoo()を実行するとどうなりますか？
• 2つのスレッドが同時にiを更新するとどうなりますか？
• iの増加はアトミック操作ですか？

C言語の1行のコード「i++;」は以下の複数の命令に翻訳されます．

• 現在のiの値を取得し，レジスタにコピーする．
• レジスタに格納されている値に1を加える．
• 新しいiの値をメモリに書き戻す．

ここで，2つのスレッドが同時にiを更新した場合に何が起こるかを確認します．

2つのスレッドが動作し，iの初期値が5の場合を考えます．

以下のようにスレッドが実行する場合，予想通り5を2回インクリメントして7になります．

スレッド1	スレッド2
get i(5)	-
increment i(5->6)	-
set i(6)	-
-	get i(6)
-	increment i(6->7)
-	set i(7)

次に，もし両方の実行スレッドがiの初期値をインクリメントする前に読み込んだ場合，両方のスレッドが同じ値をインクリメントして書き込みます．

この場合，最終的にiの値が7ではなく6になってしまいます．

スレッド1	スレッド2
get i(5)	get i(5)
increment i(5->6)	-
-	increment i(5->6)
set i(6)	-
-	set i(6)

そこで，以下のようにアトミック操作をすれば解決できます．

スレッド1	スレッド2
get, increment, and set i(5->6)	-
-	get, increment, and set i(6->7)

また，以下のようにスレッド2が先行するアトミック操作でも正常に動作します．

スレッド1	スレッド2
-	get, increment, and set i(5->6)
get, increment, and set i(6->7)	-

アトミック命令

アトミック命令は，アトミック操作を実現するためのCPU専用命令です．

アトミック命令を利用することで，CPUが同時に一度しか実行しないことを保証します．

x86-64のXADD（Exchange and Add）命令は，交換と加算を行う命令です．

「XADD DST, SRC」の命令は以下の3ステップで実行します．

• TMP = SRC + DST
• SRC = DST
• DST = TMP

XADD命令の実行中に他の操作がプリエンプションする場合，アトミック操作にならなくなってしまいます．

そこで，「LOCK XADD DST, SRC」のようにLOCKプレフィックスをXADD命令に設定することで，上記の3ステップをアトミック操作で実行することができます．

volatile型修飾子の必要性

アトミック操作におけるvolatile型修飾子の必要性を解説します．

まずはvolatileを知りたいあなたはこちらからどうぞ．

volatile変数の操作は，アトミックではありません．

volatileは，コンパイラの最適化により最適化されない，または実行順序が変わらないという意味になります．

先述した上記の関数では，コンパイラの最適化により，変数iが正常にインクリメントされない可能性があります．

また，変数iとjをインクリメントする場合，コンパイラの最適化により，iとjの順番ではなくjとiの順番でインクリメントする可能性があります．

iとjのインクリメントの順番で実行する必要があるプログラムの場合，正常に動作しない可能性があります．

そこで，volatileを利用することで，変数iとjが，この順番で正常にインクリメントすることを保証することができます．

ただし，volatileはコンパイラの最適化を抑制するため，性能とのトレードオフになることに注意して下さい．

本当に必要な箇所のみvolatileを利用しましょう！

volatileの主な利用箇所は，以下のようにメモリ配置が他のエンティティ（MMU等）によって変更される可能性がある場合です．

• メモリ配置に対する他のスレッド
• 共有メモリ配置に対する他のプロセス
• I/OデバイスのI/Oアドレス

ロック

ロックとは，コンピュータシステム内に複数のプロセスやスレッド等のある環境で，データやデバイスなどの計算資源へのアクセス制限を課す同期機構のことです．

ロックは，アトミック操作では難しかった「長くて複雑なクリティカルセクションの共有データの保護」を実現します．

また，ロックすることで，他のプロセスやスレッドがクリティカルセクションに同時に入ることを防ぐことができます．

クリティカルセクションに入る際は「ロックを獲得する（ロックする）」，クリティカルから出る際は「ロックを解放する（アンロックする）」必要があります．

※個室トイレの出入りをイメージしてもらうとわかりやすいです．

Linuxカーネルのinodeでロックの利用

Linuxカーネルでロックは，linux/include/linux/fs.hにあるinodeのi_pagesメンバ変数（ページキャッシュ）で利用されます．

• inode構造体：inodeを管理する構造体
• address_space構造体：キャッシュ可能，マップ可能なオブジェクトを管理する構造体

xarray構造体にあるxa_lock変数をロックすることで，i_pagesの中身（ページキャッシュ）を保護することができます．

※address_space構造体にあるxarray構造体のi_pagesメンバ変数は，以前はradix_tree_root構造体のpage_treeメンバ変数でした．

Radix TreeやXArrayを知りたいあなたはこちらからどうぞ．

ロックは完全にプログラマが利用しなければならないプログラミング構造です．

ロックで保護しないと一般的にデータが壊れます．

また，Linuxには以下のようなロック機構があります．

• ノンブロッキング（またはスピニング）ロック
• ブロッキング（またはスリーピング）ロック

ロックと並行処理

ロックを深く理解するためには，並行処理の概念をきちんと理解しましょう！

並行処理とは，1つのコンピュータで複数のプロセスやスレッドが実行することです．

並行処理は以下のケースがあります．

• 対象型マルチプロセッシング（SMP：Symmetric Multiprocessing）（真の並行処理）
  • 2つ以上のプロセッサが全く同時にカーネルコードを実行することができます．
• カーネルのプリエンプション（擬似並行処理）
  • カーネルはプリエンプティブなので，カーネル内のあるタスクは別のタスクをプリエンプションできます．
  • （コアが1つのユニプロセッサの場合は）2つのことは実際には同時に発生しませんが，インターリーブすることで同様のことが発生します．
• スリープとユーザ空間との同期
  • カーネル内のタスクがスリープすることで，スケジューラが起動し，新しいプロセスが実行されることがあります．
• 割り込み
  • 実行中のコードに割り込みをかけて，非同期で実行することができます．
• softirqとtasklet
  • カーネルは，softirqやtaskletの起動やスケジューリングにより，現在実行中のコードに割り込みできます．

ここで，並列処理は真の並行処理になり，疑似並行処理ではないことに注意して下さい．

なので，並行処理は並列処理を含む概念となります．

並行実行の安全性は，以下の3レベルがあります

• SMP-safe
  • SMP上での並行実行に対して安全なコード
• Preemption-safe
  • カーネルのプリエンプションによる並行処理に対して安全なコード
• Interrupt-safe
  • 割り込みハンドラからの同時アクセスに対して安全なコード

先述したxarray構造体にあるxa_lock変数は，i_pagesの中身のデータを保護します．

ロックを利用する時のチェックリストは以下になりますので，うまく活用しましょう！

• そのデータはグローバルですか？
• 現在の実行スレッド以外からアクセス可能か？
• データはプロセスコンテキストと割込みコンテキストの間で共有されていますか？
• データは2つの異なる割込みハンドラ間で共有されていますか？
• あるプロセスがこのデータにアクセス中にプリエンプションされた場合，新たにスケジューリングされたプロセスは同じデータにアクセスできますか？
• もし現在のプロセスが何かでスリープした場合，共有データはどのような状態になりますか?
• この関数が他のプロセッサで再び呼ばれた場合はどうなりますか?

デッドロック

デッドロックは，1つまたは複数のスレッドが，決して解放されることのない1つまたは複数のリソースのロックを待っている状況のことです．

つまり，デッドロックはどのスレッドも実行を継続できない状況になることです．

※デッドロックをDeadly Embrace（死の抱擁）と呼ぶことがあります．

また，同じロックを2度獲得しようとすると自己デッドロック状態になります．

Linuxは再帰的ロックをサポートしていないことに注意して下さい．

デッドロックのシンプルな例としてABBAロックを紹介します．

スレッド1がA->B，スレッド2がB->Aの順番でロックを獲得するプログラムを考えます．

スレッド1がA，スレッド2がBのロックを獲得し，次にスレッド1がB，スレッド2がAのロックを獲得しようとします．

しかし既に両方ともロックは獲得されているので，ロックを解放するまで待つ必要があります．

スレッド1のスレッド2の両方とも待ち状態になって実行が継続できなくなるので，デッドロックが発生します（下表）．

スレッド1	スレッド2
ロックAを獲得する．	ロックBを獲得する．
ロックBを獲得しようとするが失敗する．	ロックAを獲得しようとするが失敗する．
ロックBが解放されるまで待ち状態になる．	ロックAが解放されるまで待ち状態になる．
以降同様．．．	以降同様．．．

デッドロックの回避方法

デッドロックの回避方法は主に以下になります．

• ロックを獲得する順番（ロック順序：Lock Ordering）を全てのプログラムで同じにする．
• AとBにの両方にアクセスするという1つのロックを定義する．
• クリティカルセクションに入れない場合は，既に入っているクリティカルセクションから出て処理を終了するようにする．

Linuxカーネルにおけるロック順序は，linux/mm/filemap.cに丁寧なコメントがあります．

このようなコメントがあると，ロックを獲得する順番を正しくプログラムできますね！

linux/include/linux/fs.hのinode_i_mutex_lock_classでinodeのロックを獲得する順番が定義されています．

具体的には，15行目の「parent[2] -> child -> grandchild -> normal -> xattr -> second non-directory」の順番でロックを獲得します．

linux/fs/namei.cのlock_rename関数が，ロック順序のわかりやすいコード例です．

inodeの親（I_MUTEX_PARENT）から子（I_MUTEX_CHILD），または親（I_MUTEX_PARENT）から親2（I_MUTEX_PARENT2）という順番でロックを獲得していることがわかります．

ロックとスケーラビリティ

ロックとスケーラビリティの関係性を議論します．

ロック競合（Lock Contention）とは，現在獲得中のロックで，他のスレッドが獲得しようとしているものです．

スケーラビリティとは，多数のプロセッサでシステムを拡張できることです．

粗粒度ロック（Coarse-Grained Lock）と細粒度ロック（Fine-Grained Lock）にはトレードオフがあります．

粗粒度ロックは，コア数の多いマシンではボトルネックになります．

これに対して，細粒度ロックは，コア数の少ないマシンではオーバーヘッドになります．

ロックに関しては，最初はシンプルでわかりやすい利用をし，スケーラビリティに必要なだけ複雑化していくアプローチが重要になります．

ロックはバグの原因にもなりますので，シンプルであることが重要です！

アトミック操作のLinuxカーネルにおける実装

Linuxカーネルで1つの変数をアトミック操作でインクリメントしたい場合は，atomic_inc関数（関数内でarch_atomic_inc関数を呼び出し）を利用します．

他にもアトミック操作の例は以下になります．

• fetch-and-add : アトミックなインクリメント
• test-and-set : あるメモリ位置に値を設定し，以前の値を返す．
• compare-and-swap : 直前の値が与えられた値と等しい場合のみ，メモリ位置の内容を変更する．

Linuxでは，整数のアトミック操作の関数とビット単位のアトミック操作の関数が提供されていますので，それぞれ解説していきます．

整数のアトミック操作の関数

linux/include/linux/types.hにアトミック操作のためのatomic_t/atomic64_t構造体の定義と，32ビットのアトミック操作の変数を初期化するATOMIC_INITマクロは以下になります．

atomic_t/atomic64_t構造体にはcounterメンバ変数のみがあります．

主な32ビット整数のアトミック操作の関数は以下になります．

• arch_atomic_read関数：アトミック変数を読み込む．
• arch_atomic_set関数：アトミック変数を設定する．
• arch_atomic_add関数：アトミック変数に整数を加算する．
• arch_atomic_sub関数：アトミック変数から整数を減算する．
• arch_atomic_sub_and_test関数：アトミック変数から整数を減算し，結果をテストする．
• arch_atomic_inc関数：アトミック変数をインクリメントする．
• arch_atomic_dec関数：アトミック変数をデクリメントする．
• arch_atomic_dec_and_test関数：アトミック変数をデクリメントし，結果をテストする．
• arch_atomic_inc_and_test関数：アトミック変数をインクリメントし，結果をテストする．
• arch_atomic_add_negative関数：アトミック変数に整数を加算し，結果が負の場合は真，正か0の場合は偽を返します．
• arch_atomic_add_return関数：アトミック変数に整数を加算し，結果を返す．
• arch_atomic_sub_return関数：アトミック変数に整数を減算し，結果を返す．

その他の32ビット整数のアトミック操作の関数や64ビット整数のアトミック操作の主な関数「arch_atomic64_XX」の定義は，linux/include/atomic/atomic-arch-fallback.hにあります．

64ビットの関数の使い方は，32ビットの関数の使い方と同様ですね．

ビット単位のアトミック操作の関数

主なビット単位のアトミック操作の関数は以下になります．

• set_bit関数：メモリアドレスにビットをアトミックに設定する．
• clear_bit関数：メモリアドレスにビットをアトミックにクリアする．
• change_bit関数：メモリアドレスにビットをアトミックに反転する．
• test_and_set_bit関数：メモリアドレスにビットをアトミックに設定し，その古い値を返す．
• test_and_clear_bit関数：メモリアドレスにビットをアトミックにクリアし，その古い値を返す．
• test_and_change_bit関数：メモリアドレスにビットをアトミックに反転し，その古い値を返す．
• test_bit関数：ビットが設定されているかアトミックにテストする．

ノンアトミックなビット演算の関数も提供されています．

ノンアトミックなビット演算の関数のプレフィックスはダブルアンダースコア（__）になり，例えばtest_bit関数は__test_bit関数になります．

アトミック演算を必要としない場合（ロックでデータを保護している場合等) は，ノンアトミックなビット演算の関数を利用した方が高速に処理できるかもしれません．

スピンロック

スピンロックは，Linuxカーネルで最も一般的に使用されるロックです．

スレッドが既に保持されているロックを取得しようとすると，ロックが利用可能になるのを待つ間，スレッドがスピンします．

スピンロックが長すぎるとCPU時間を浪費してしまいます．

また，スピンロックはスレッドがスリープできない割り込みコンテキストでも使えます．

割り込みコンテキストで共有されるデータ構造に対して，カーネルは特別なスピンロック関数を提供します．

ただし，プロセスコンテキストでは，カーネルプリエンプションは無効になるので，スピンロックを保持したままスリープしてはいけないことに注意して下さい．

スピンロックの操作関数

linux/include/linux/spinlock_types.hにスピンロックの変数を定義するDEFINE_SPINLOCKマクロがあります．

linux/include/linux/spinlock.hに以下のスピンロックの関数があります．

• spin_lock関数：ロック変数を獲得するまでスピンロックする．
• spin_trylock関数：ロック変数を獲得するが，もし獲得できない場合はすぐに関数から返る．
• spin_unlock関数：ロック変数を解放する．

spin_lock関数は再帰的でなく，同じロック変数を獲得する場合は自己デッドロックするので注意して下さい．

ロック/アンロック関数は，カーネルのプリエンプションを無効化/有効化し，ロックを獲得/解放します．

ユニプロセッサの場合，ロックはコンパイル時に取り除かれる可能性があります．

ただし，タスク実行のインターリーブを防ぐために，ロックを獲得時にプリエンプションを無効にし，ロック解放時に有効にする必要があります．

スピンロックの割り込みハンドラでの利用

スピンロックの割り込みハンドラでの利用を解説します．

スピンロックはスリープしないので，割り込みコンテキストで使用しても安全です．

割り込みハンドラでロックを使用する場合，ロックを取得する前にローカル割り込みを無効にする必要があります．

そうしないと，ロックが保持されている間に割り込みハンドラがカーネルのコードに割り込み，ロックを再獲得しようとする可能性があります．

割り込みハンドラはロックが利用可能になるのを待ちながらスピンロックしています．

しかし，ロックホルダは割り込みハンドラが完了するまで実行されません．

この多重割り込みによりロックを再獲得する際に発生するデッドロックのことを，二重獲得デッドロック（double-acquire deadlock）と呼びます．

Bottom Halfの割り込みハンドラでは，以下の関数を利用します．

• spin_lock_bh関数：Bottom Halfでロック変数を獲得するまでスピンロックする．
• spin_trylock_bh関数：Bottom Halfでロック変数を獲得するが，もし獲得できない場合はすぐに関数から返る．
• spin_unlock_bh関数：Bottom Halfでロック変数を解放する．

与えられたロックを獲得し，すべてのBottom Halfを無効にします．

Bottom Halfはプロセスコンテキストコードをプリエンプションする可能性があるため，Bottom Halfのプロセスコンテキスト間でデータを共有する場合は，ロックとBottom Halfの無効化の両方を使用してプロセスコンテキスト内のデータを保護する必要があります．

同様に，割り込みハンドラがBottom Halfをプリエンプションする可能性があるため，データが割り込みハンドラとBottom Halfの間で共有されている場合，適切なロックを獲得し，割り込みを無効にすることの両方を行う必要があります．

スピンロックとプリエンプション

スピンロックが保持されている場合，プリエンプションは無効化されます．

スピンロックを使用せずにプリエンプションを無効にする必要がある場合があります．

例えば，以下のようにコア毎のデータ操作をする場合です．

タスクAが変数fooを操作中にプリエンプションされてタスクBが実行すると，タスクBが変数Bの操作することでデータが破損してしまうことがわかります．

• タスクAがロックで保護されていないコア毎の変数fooを操作する．
• タスクAがプリエンプションされる．
• タスクBがスケジューリングされる．
• タスクBが変数fooを操作する．
• タスクBが終了する．
• タスクAがリスケジュールされる．
• タスクAが変数fooの操作を継続する．

linux/include/asm-generic/preempt.hにプリエンプションカウンタを取得するpreempt_count関数があります．

プリエンプションカウンタは，プリエンプション可能などうかを判定するために利用します．

linux/include/linux/preempt.hで定義されているプリエンプションの操作マクロや関数は以下になります．

• preempt_disableマクロ：カーネルプリエンプションを無効にし，プリエンプションカウンタをインクリメントする．
• preempt_enableマクロ：プリエンプションカウンタをデクリメントし，ちょうどゼロになる場合はサービスや中断されたリスケジュールがあるかどうかチェックする．
• preempt_enable_no_reschedマクロ：カーネルプリエンプションを有効にするが，サービスや中断されたリスケジュールがあるかどうかチェックしない．

Read-Write Lock

Read-Write Lockは，複数のReaderを同時使用可能になるスピンロックです．

共有データにアクセスするスレッドがReaderとWriterに明確に分けられる場合を考えてみましょう．

例えば，リストが更新（書き込み）され，検索（読み込み）された場合です．

更新される時は，他のスレッドは更新も検索もしてはなりません．

検索される時は，他のスレッドは更新してはいけませんが，複数のReaderを並列に許可しても安全です．

つまり，Readerの並列化により，スケーラビリティを向上させることができます．

Read-Write Lockは，Shared-Exclusive LockやConcurrent-Exclusive Lockと同じ意味になります．

LinuxのRead-Write Lockは，WriterよりReaderを優先します．

Readロックが保持され，Writerが排他的アクセスを待っている場合，ロックを獲得しようとするReaderは成功し続けます．

したがって，十分な数のReaderが保留中のWriterを飢えさせることができてしまいます．

つまり，Writerの性能が低下します．

ユーザ空間でRead-Write Lockの使い方を知りたいあなたはこちらからどうぞ．．

linux/include/linux/rwlock_types.hにRead-Write Lockを管理するrwlock_t構造体と初期化するDEFINE_RWLOCKがあります．

linux/include/linux/rwlock.hにRead-Write Lockを操作する関数があります．

• read_lockマクロ：Readロック変数を獲得するまでスピンロックする．
• read_trylockマクロ：Readロック変数を獲得するが，もし獲得できない場合はすぐに関数から返る．
• read_unlockマクロ：Readロック変数を解放する．
• write_lockマクロ：Writeロック変数を獲得するまでスピンロックする．
• write_trylockマクロ：Writeロック変数を獲得するが，もし獲得できない場合はすぐに関数から返る．
• write_unlockマクロ：Writeロック変数を解放する．

セマフォ

セマフォは，並列プログラミング環境での複数の実行単位（主にプロセス）が共有する資源にアクセスするのを制御する際の，シンプルで便利な抽象化を提供する変数または抽象データ型です．

セマフォは，スリーピングロックで，割り込みコンテキストでは利用できないので注意して下さい．

タスクが利用できないセマフォを獲得しようとすると，セマフォはそのタスクを待ち行列に入れ，タスクをスリープさせます．

その後，プロセッサは他のコードを実行できるようになります．

タスクがセマフォを解放すると，待ち行列上のタスクの1つが起床し，セマフォを獲得することができます．

セマフォは，スリープ，待ち行列の維持，起床のオーバーヘッドがロック保持時間の合計を簡単に上回ってしまうため，短時間保持するロックには最適ではありません．

セマフォは，複数個のホルダーを許容します．

カウンタは与えられた値で初期化されます．

スレッドがセマフォを獲得するたびに減少します．

カウンタが0になるとセマフォは使用できなくなります．

カーネルでは，ほとんどのセマフォはバイナリセマフォ（または後述するミューテックス）です．

ユーザ空間でセマフォの使い方を知りたいあなたはこちらからどうぞ．

linux/include/linux/semaphore.hで定義されているセマフォを管理するsemaphore構造体と，セマフォを操作する関数は以下になります．

• DEFINE_SEMAPHOREマクロ：セマフォ変数を1（バイナリセマフォ）で初期化する．
• sema_init関数：セマフォ変数を指定した値で初期化する．
• down関数：セマフォ変数を獲得する．
• down_trylock関数：セマフォ変数を獲得するが，もし獲得できない場合はすぐに関数から返る．
• up関数：セマフォ変数を解放する．

Read-Writeセマフォ

Read-Writeセマフォは，Read-Write Lockのセマフォ版です．

linux/include/linux/rwsem.hで定義されているRead-Writeセマフォを管理するrw_semaphore構造体と，Read-Writeセマフォの操作関数は以下になります．

• down_read関数：Readセマフォ変数を獲得する．
• down_read_trylock関数：Readセマフォ変数を獲得するが，もし獲得できない場合はすぐに関数から返る．
• up_read関数：Readセマフォ変数を解放する．
• down_write関数：Writeセマフォ変数を獲得する．
• down_write_trylock関数：Writeセマフォ変数を獲得するが，もし獲得できない場合はすぐに関数から返る．
• up_write関数：Writeセマフォ変数を解放する．
• downgrade_write関数：獲得したWriteセマフォをReadセマフォにアトミックに変換する．

ミューテックス

ミューテックスは，より厳格な使用条件を備えたバイナリセマフォです．

一度に1つのスレッドだけがミューテックスを保持できます．

ミューテックスをロックしているスレッドは，ロックを解除する必要があります．

再帰的なロックとアンロックはできません．

ミューテックスを保持したままスレッドを終了することはできません．

また，割り込みコンテキストでミューテックスを取得することはできません．

ミューテックスは関数を通じてのみ管理できます．

ミューテックスとセマフォのどちらを利用するか悩む場合，最初はミューテックスで，必要なときだけセマフォに移行するやり方がおすすめです！

ユーザ空間でミューテックスの使い方を知りたいあなたはこちらからどうぞ．

linux/include/linux/mutex.hで定義されているミューテックスを管理するmutex構造体と，ミューテックスを操作する関数は以下になります．

• mutex_initマクロ：ミューテックス変数を初期化する．
• mutex_lock関数：ミューテックス変数を獲得する．
• mutex_trylock関数：ミューテックス変数を獲得するが，もし獲得できない場合はすぐに関数から返る．
• mutex_unlock関数：ミューテックス変数を解放する．

ミューテックスとスピンロックの要求とおすすめのロックは以下になります．

要求	おすすめのロック
低オーバーヘッドロッキング	スピンロックが望ましい．
短いロックホールド時間	スピンロックが望ましい．
長いロックホールド時間	ミューテックスが望ましい．
割り込みコンテキストからロック	スピンロックが要求される．
ロック保持中にスリープ	ミューテックスが要求される．

Completion

Completionは，あるタスクが他のタスクにイベントの発生を通知する必要がある場合に使用されます．

linux/include/linux/completion.hにあるCompletionを管理するcompletion構造体と，Completionの操作関数は以下になります．

• init_completion関数：Completion変数を初期化する．
• DECLARE_COMPLETIONマクロ：Completion変数の定義と初期化する．
• wait_for_completion関数：Completion変数がシグナルを受信するまで待つ．
• complete関数：待機状態のタスクを起床するためにシグナルを送る．

Sequential Lock（seqlock）

Sequential Lock（seqlock）は，共有データの読み書きのためのシンプルな機構です．

シーケンスカウンタ（またはバージョン番号）を保持することで機能します．

当該データに書き込みが行われるたびにロックがかかり，シーケンス番号をインクリメントします．

データを読み出す前と後に，シーケンス番号を読み出します．

値が同じであれば，読み出しの途中で書き込みが開始されたわけではありません．

さらに，値が偶数であれば，書き込みが途中でない（完了している）ことを意味します．

なぜかというと，書き込みロックをかけると値が奇数になり，解除すると0から始まるので偶数になるからです．

seqlockは以下のような場合に有効です．

• Readerが多く，Writerが少ない場合
• ReaderよりWriterを優先したい場合

linux/include/linux/seqlock.hに定義されているseqlockを管理するseqlock_t構造体と，seqlockの操作関数は以下になります．

• DEFINE_SEQLOCKマクロ：seqlock変数の定義と初期化する．
• seqlock_initマクロ：seqlock変数を初期化する．
• read_seqbegin関数：seqlock_tの読み込み側のクリティカルセクションを開始する．
• read_seqretry関数：seqlock_tの読み込み側のクリティカルセクションを終了する．
• write_seqlock関数：seqlock_tの書き込み側のクリティカルセクションを開始する．
• write_sequnlock関数：seqlock_tの書き込み側のクリティカルセクションを終了する．

メモリ順序とメモリバリア

メモリの読み込み（ロード）および書き込み（ストア）操作は，性能上の理由からコンパイラによって順序を変更することができます．

• コンパイル時にコンパイラが行う：コンパイラの最適化
• 実行時のCPUによる最適化：Total Store Ordering（TSO），Partial Store Ordering（PSO）

コンパイラの最適化やCPUのアウトオブオーダー実行により，自分のコードは以下のようなコードの並び替えが可能です．

また，以下のコードは，aとbの間には依存関係があるため，決して並べ替えられません．

メモリバリア（メモリフェンス）は，CPUまたはコンパイラに，バリア命令の前後に発行されるメモリ操作の順序制約を実施させるバリア命令の一種です．

これは通常，バリアより前に発行された操作は，バリアより後に発行された操作より前に実行されることが保証されることを意味します．

以下のように「a = 4;」と「b = 5;」の間にバリア命令を発行するbarrier関数を挿入しています．

LinuxカーネルのメモリバリアのAPIは以下になります．

※主にマクロで実装しています．

• rmb()：バリアを越えてロードが並べ替えられるのを防ぐ（SMP版はsmp_rmb()）．
• wmb() : ストアがバリアを越えて並べ替えられるのを防ぐ（SMP版はsmp_wmb()）．
• mb()：バリア内でロードとストアの順序が入れ替わるのを防ぐ（SMP版はsmp_mb()）．

種類	必須	SMP版
読み込みバリア	rmb()	smp_rmb()
書き込みバリア	wmb()	smp_wmb()
一般（読み書き）バリア	mb()	smp_mb()

上記のAPIが未定義の場合，barrier()になります．

barrier()は一般的なメモリバリアのマクロで，linux/inlcude/linux/compiler-intel.hにある__memory_barrier()というIntelコンパイラのビルトインとして実装されています．

また，barrier()に相当するメモリバリアとして，GCCのビルトインの__sync_synchronize関数があります．

※Intelコンパイラのビルトインの__memory_barrier()とGCCのビルトインの__sync_synchronize関数は同等だと思われます．

詳細を知りたいあなたはメモリオーダリングを読みましょう！

__sync_synchronize関数を利用する排他制御アルゴリズムを知りたいあなたはこちらからどうぞ．

上記のAPIは，アーキテクチャ固有のメモリバリア命令を利用して実装します．

x86-64のメモリバリア命令は以下になります．

• lfence命令：lfence命令より後ろのロード操作が，lfence命令より先に実行されることを防ぐ．
• sfence命令：sfence命令より前のストア操作が完了するのを待つ．
• mfence命令：lfence命令とsfence命令を組み合わせた命令．

ARM64のメモリバリア命令は以下になります．

• isb命令（命令同期バリア命令）：isb命令は，後続の命令のフェッチを保証するために使用され，特権とアクセスが現在のMMU構成でチェックされるようにします．isb命令が完了するまでに，システム制御レジスタへの書き込みなど，以前に実行されたコンテキスト変更操作が完了していることを保証するために使用されます．ハードウェア的には，命令パイプラインをフラッシュすることを意味します．
• dmb命令（データメモリバリア命令）：dmb命令は，DMB命令をまたぐデータアクセス命令の並べ替えを防止します．バリアタイプに応じて，DMBの前にこのCPUによって実行される特定のデータアクセス，すなわちロードまたはストア（命令フェッチではない）は，DMBの後の特定の他のデータアクセスよりも前に，指定された共有可能領域内の他のすべてのマスターから見えるようになります．
• dsb命令（データ同期バリア命令）：dsb命令は，データメモリバリアと同じ順序を強制しますが，同期が完了するまで，ロードやストアに限らず，それ以降の命令の実行をブロックします．例えば，イベントが発生したことを他のコアに知らせるsev命令の実行を防止するために使用できます．このCPUが発行するキャッシュ，TLB，分岐予測のメンテナンス動作が，指定された共有可能ドメインに対してすべて完了するまで待機します．

メモリバリアのAPIの利用例は以下になります．

初期値は「a = 1」と「b = 2」に設定しています．

mb()はaがbよりも先に書き込まれること，rmb()はbがaより先に読み込まれることを保証します．

結果として，「a = 3」，「b = 4」，「c = 2」，「d = 3」になることを保証します．

※「c = 4」にならないことに注意して下さい．

スレッド1	スレッド2
a = 3;	-
mb();	-
b = 4;	c = b;
-	rmb();
-	d = a;

Read-Copy-Update（RCU）

Read-Copy-Update（RCU）は，複数のスレッドがポインタを通じてリンクされた共有データ構造 (リンクリスト，ツリー，ハッシュテーブル等) の要素を同時に読み取り，更新する際にロックプリミティブを使用しない同期化メカニズムです．

スレッドが共有メモリ内のデータ構造の要素を挿入または削除するときは常に，すべての読者は古いまたは新しい構造のいずれかを参照して走査することが保証されます．

これにより，不整合（例：NULLポインタの再参照）を回避することができます．

読み込みの性能が重要な場合に使用され，空間計算量とのトレードオフの一例で，より多くの空間を犠牲にして高速な操作を可能にします．

これにより，すべての読み出しは同期がないかのように進行することで，高速になりますが，更新はより困難になります．

つまり，RCUの特徴は以下になります．

• WriterがReaderをブロックすることはない．
• ほぼゼロのオーバーヘッドで複数のRaderを許可する．
• Readerの性能を最適化する．

Writerにのみロックを要求し，データ構造を慎重に更新することで，読者が常に一貫したデータビューを見られるようにします．

RCUは，オブジェクトの複数のバージョンを維持し，既存の読み取り側クリティカルセクションがすべて完了するまでオブジェクトを解放しないことで，読み取りが一貫したものになるようにします．

以下のような読み取り処理の頻度が多いデータ構造に広く利用されています．

• ディレクトリエントリーキャッシュ
• DNSネームデータベース

また，既存のRead-Write LockをRCUに書き換えることで性能が大幅に向上します．

RCUの主な操作関数とマクロは以下になります．

• rcu_read_lock関数：RCUのReader側のクリティカルセクションの先頭をマークする．
• rcu_read_unlock関数：RCUのReader側のクリティカルセクションの終了をマークする．
• rcu_assign_pointerマクロ：RCUで保護されたポインタに割り当てる．
• rcu_dereferenceマクロ：RCUで保護されたポインタをdereferenceする（参照から外す）ために取得する．
• call_rcu関数：猶予期間後の呼び出しのためにRCUコールバックをキューに入れる．
• synchronize_rcu関数：猶予期間が経過するのを待つ．

RCUの制限は以下になります．

今後のLinuxカーネルの発展に期待しましょう！

• 複数のWriterを調整する機構を提供していない．
• RCUベースのアルゴリズムの多くは，書き込みの同時実行を防ぐためにスピンロックを使用しています．
• すべての変更はシングルポインタアップデート（一箇所のポインタの更新）であるべきですが，現在は複数箇所のポインタの更新が必要とのことです．

RCUの解説動画は以下がわかりやすいです．

鏡文字で書きながら教える授業スタイルが興味深いです！

RCUを深掘りしたいあなたは，RCUの開発者「ポール・マッケニー」の解説動画がおすすめです！

動画は結構長いですが，RCUを深く学べます！

また，ポール・マッケニーが著書のRCUの論文「READ-COPY UPDATE」もおすすめです！

参考：Read-Log-Update（RLU）

Read-Log-Update（RLU）は，RCUを拡張した同期機構です．

RLUの特徴は以下になります．

• RCUではできなかった複数のWriterによる読み込みの同時実行を実現
• RCUプログラミングが複雑になる部分を排除する自動化を実現（並行コードの拡張性をサポート）
• ソフトウェアのトランザクションメモリアルゴリズムからヒントを得たロギングおよび調整機構

※LinuxカーネルのメインラインにRLUはマージされていないので注意して下さい．

RLUの解説動画はこちらです．

まとめ

今回は同期を紹介しました．

具体的には，以下の内容を解説しました．

• 同期の背景
• 同期
• ロック
• スピンロック
• Read-Write Lock
• セマフォ
• Read-Writeセマフォ
• ミューテックス
• Completion
• Sequential Lock（seqlock）
• メモリ順序とメモリバリア
• Read-Copy-Update（RCU）
• Read-Log-Update（RLU）

（RLU以外の）Linuxカーネルの同期プログラミングを知りたいあなたはこちらからどうぞ．

同期を深掘りしたいあなたは以下の記事を読みましょう！

• Is Parallel Programming Hard, And, If So, What Can You Do About It?
• Structured Deferral: Synchronization via Procrastination
• INUX KERNEL MEMORY BARRIERS
• x86/x64におけるメモリオーダーの話
• What is RCU? – “Read, Copy, Update”
• What is RCU, Fundamentally?

以下の動画もおすすめです！

LinuxカーネルはC言語で書かれています．

私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．

私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！

独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！

次回はこちらからどうぞ．