本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Assembler (x64，ARM)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
こういった私から学べます．
前回を読んでいない方はこちらからどうぞ．
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による実例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
int withdraw_money(int total, int withdrawal) { if (total < withdrawal) { fprintf(stderr, "You do not have that much money!\n"); return -1; } total -= withdrawal; update_total(total); give_user_to_money(withdrawal); return 0; } |
クリティカルセクションのATMによる実例を紹介します．
上記にATMからお金を引き出すwithdraw_money関数を示します．
withdraw_money関数を逐次的に実行する場合は正常に動作します．
ここで複数のATMからの同時出金をした場合はどうなるのでしょうか？
例えば，以下の場合は「(100円 + 50円) > 110円」なので，どちらかの取引は失敗するはずです．
- total：110円
- withdrawal：100円
- withdrawal2：50円
不正確なシナリオの可能性は以下になります．
- 3行目：2つのスレッドが100 < 110と50 < 110を確認する．
- 9行目：update_total関数でスレッド1が更新（total = 110 - 100 = 10）
- 9行目：update_total関数でスレッド2が更新（total = 110 - 50 = 60）
合計の出金金額は150円ですが，60円が口座に残っています．
特定の操作の間，口座をロックする必要があり，各トランザクションをアトミック操作で実行する必要があります．
このアトミック操作中のコードがクリティカルセクションになります！
1つの変数の更新
|
1 2 3 4 5 6 |
int i; void foo(void) { i++; } |
上記の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は，コンパイラの最適化により最適化されない，または実行順序が変わらないという意味になります．
|
1 2 3 4 5 6 |
int i; void foo(void) { i++; } |
先述した上記の関数では，コンパイラの最適化により，変数iが正常にインクリメントされない可能性があります．
|
1 2 3 4 5 6 7 |
int i, j; void foo(void) { i++; j++; } |
また，変数iとjをインクリメントする場合，コンパイラの最適化により，iとjの順番ではなくjとiの順番でインクリメントする可能性があります．
iとjのインクリメントの順番で実行する必要があるプログラムの場合，正常に動作しない可能性があります．
|
1 2 3 4 5 6 7 |
volatile int i, j; void foo(void) { 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構造体：キャッシュ可能，マップ可能なオブジェクトを管理する構造体
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
/* * Keep mostly read-only and often accessed (especially for * the RCU path lookup and 'stat' data) fields at the beginning * of the 'struct inode' */ struct inode { umode_t i_mode; unsigned short i_opflags; kuid_t i_uid; kgid_t i_gid; unsigned int i_flags; #ifdef CONFIG_FS_POSIX_ACL struct posix_acl *i_acl; struct posix_acl *i_default_acl; #endif const struct inode_operations *i_op; struct super_block *i_sb; struct address_space *i_mapping; ... }; /** * struct address_space - Contents of a cacheable, mappable object. * @host: Owner, either the inode or the block_device. * @i_pages: Cached pages. * @invalidate_lock: Guards coherency between page cache contents and * file offset->disk block mappings in the filesystem during invalidates. * It is also used to block modification of page cache contents through * memory mappings. * @gfp_mask: Memory allocation flags to use for allocating pages. * @i_mmap_writable: Number of VM_SHARED mappings. * @nr_thps: Number of THPs in the pagecache (non-shmem only). * @i_mmap: Tree of private and shared mappings. * @i_mmap_rwsem: Protects @i_mmap and @i_mmap_writable. * @nrpages: Number of page entries, protected by the i_pages lock. * @writeback_index: Writeback starts here. * @a_ops: Methods. * @flags: Error bits and flags (AS_*). * @wb_err: The most recent error which has occurred. * @private_lock: For use by the owner of the address_space. * @private_list: For use by the owner of the address_space. * @private_data: For use by the owner of the address_space. */ struct address_space { struct inode *host; struct xarray i_pages; struct rw_semaphore invalidate_lock; gfp_t gfp_mask; atomic_t i_mmap_writable; #ifdef CONFIG_READ_ONLY_THP_FOR_FS /* number of thp, only for non-shmem files */ atomic_t nr_thps; #endif struct rb_root_cached i_mmap; struct rw_semaphore i_mmap_rwsem; unsigned long nrpages; pgoff_t writeback_index; const struct address_space_operations *a_ops; unsigned long flags; errseq_t wb_err; spinlock_t private_lock; struct list_head private_list; void *private_data; } __attribute__((aligned(sizeof(long)))) __randomize_layout; |
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に丁寧なコメントがあります．
このようなコメントがあると，ロックを獲得する順番を正しくプログラムできますね！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
/* * Lock ordering: * * ->i_mmap_rwsem (truncate_pagecache) * ->private_lock (__free_pte->__set_page_dirty_buffers) * ->swap_lock (exclusive_swap_page, others) * ->i_pages lock * * ->i_rwsem * ->invalidate_lock (acquired by fs in truncate path) * ->i_mmap_rwsem (truncate->unmap_mapping_range) * * ->mmap_lock * ->i_mmap_rwsem * ->page_table_lock or pte_lock (various, mainly in memory.c) * ->i_pages lock (arch-dependent flush_dcache_mmap_lock) * * ->mmap_lock * ->invalidate_lock (filemap_fault) * ->lock_page (filemap_fault, access_process_vm) * * ->i_rwsem (generic_perform_write) * ->mmap_lock (fault_in_pages_readable->do_page_fault) * * bdi->wb.list_lock * sb_lock (fs/fs-writeback.c) * ->i_pages lock (__sync_single_inode) * * ->i_mmap_rwsem * ->anon_vma.lock (vma_adjust) * * ->anon_vma.lock * ->page_table_lock or pte_lock (anon_vma_prepare and various) * * ->page_table_lock or pte_lock * ->swap_lock (try_to_unmap_one) * ->private_lock (try_to_unmap_one) * ->i_pages lock (try_to_unmap_one) * ->lruvec->lru_lock (follow_page->mark_page_accessed) * ->lruvec->lru_lock (check_pte_range->isolate_lru_page) * ->private_lock (page_remove_rmap->set_page_dirty) * ->i_pages lock (page_remove_rmap->set_page_dirty) * bdi.wb->list_lock (page_remove_rmap->set_page_dirty) * ->inode->i_lock (page_remove_rmap->set_page_dirty) * ->memcg->move_lock (page_remove_rmap->lock_page_memcg) * bdi.wb->list_lock (zap_pte_range->set_page_dirty) * ->inode->i_lock (zap_pte_range->set_page_dirty) * ->private_lock (zap_pte_range->__set_page_dirty_buffers) * * ->i_mmap_rwsem * ->tasklist_lock (memory_failure, collect_procs_ao) */ |
linux/include/linux/fs.hのinode_i_mutex_lock_classでinodeのロックを獲得する順番が定義されています．
具体的には，15行目の「parent[2] -> child -> grandchild -> normal -> xattr -> second non-directory」の順番でロックを獲得します．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
/* * inode->i_mutex nesting subclasses for the lock validator: * * 0: the object of the current VFS operation * 1: parent * 2: child/target * 3: xattr * 4: second non-directory * 5: second parent (when locking independent directories in rename) * * I_MUTEX_NONDIR2 is for certain operations (such as rename) which lock two * non-directories at once. * * The locking order between these classes is * parent[2] -> child -> grandchild -> normal -> xattr -> second non-directory */ enum inode_i_mutex_lock_class { I_MUTEX_NORMAL, I_MUTEX_PARENT, I_MUTEX_CHILD, I_MUTEX_XATTR, I_MUTEX_NONDIR2, I_MUTEX_PARENT2, }; |
linux/fs/namei.cのlock_rename関数が，ロック順序のわかりやすいコード例です．
inodeの親（I_MUTEX_PARENT）から子（I_MUTEX_CHILD），または親（I_MUTEX_PARENT）から親2（I_MUTEX_PARENT2）という順番でロックを獲得していることがわかります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
/* * p1 and p2 should be directories on the same fs. */ struct dentry *lock_rename(struct dentry *p1, struct dentry *p2) { struct dentry *p; if (p1 == p2) { inode_lock_nested(p1->d_inode, I_MUTEX_PARENT); return NULL; } mutex_lock(&p1->d_sb->s_vfs_rename_mutex); p = d_ancestor(p2, p1); if (p) { inode_lock_nested(p2->d_inode, I_MUTEX_PARENT); inode_lock_nested(p1->d_inode, I_MUTEX_CHILD); return p; } p = d_ancestor(p1, p2); if (p) { inode_lock_nested(p1->d_inode, I_MUTEX_PARENT); inode_lock_nested(p2->d_inode, I_MUTEX_CHILD); return p; } inode_lock_nested(p1->d_inode, I_MUTEX_PARENT); inode_lock_nested(p2->d_inode, I_MUTEX_PARENT2); return NULL; } EXPORT_SYMBOL(lock_rename); |
ロックとスケーラビリティ
ロックとスケーラビリティの関係性を議論します．
ロック競合（Lock Contention）とは，現在獲得中のロックで，他のスレッドが獲得しようとしているものです．
スケーラビリティとは，多数のプロセッサでシステムを拡張できることです．
粗粒度ロック（Coarse-Grained Lock）と細粒度ロック（Fine-Grained Lock）にはトレードオフがあります．
粗粒度ロックは，コア数の多いマシンではボトルネックになります．
これに対して，細粒度ロックは，コア数の少ないマシンではオーバーヘッドになります．
ロックに関しては，最初はシンプルでわかりやすい利用をし，スケーラビリティに必要なだけ複雑化していくアプローチが重要になります．
ロックはバグの原因にもなりますので，シンプルであることが重要です！
アトミック操作のLinuxカーネルにおける実装
Linuxカーネルで1つの変数をアトミック操作でインクリメントしたい場合は，atomic_inc関数（関数内でarch_atomic_inc関数を呼び出し）を利用します．
|
1 2 3 4 5 6 |
static __always_inline void atomic_inc(atomic_t *v) { instrument_atomic_read_write(v, sizeof(*v)); arch_atomic_inc(v); } |
他にもアトミック操作の例は以下になります．
- 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メンバ変数のみがあります．
|
1 2 3 4 5 6 7 8 9 10 11 |
typedef struct { int counter; } atomic_t; #ifdef CONFIG_64BIT typedef struct { s64 counter; } atomic64_t; #endif #define ATOMIC_INIT(i) { (i) } |
主な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マクロがあります．
|
1 |
#define DEFINE_SPINLOCK(x) spinlock_t x = __SPIN_LOCK_UNLOCKED(x) |
linux/include/linux/spinlock.hに以下のスピンロックの関数があります．
- spin_lock関数：ロック変数を獲得するまでスピンロックする．
- spin_trylock関数：ロック変数を獲得するが，もし獲得できない場合はすぐに関数から返る．
- spin_unlock関数：ロック変数を解放する．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
static __always_inline void spin_lock(spinlock_t *lock) { raw_spin_lock(&lock->rlock); } static __always_inline int spin_trylock(spinlock_t *lock) { return raw_spin_trylock(&lock->rlock); } static __always_inline void spin_unlock(spinlock_t *lock) { raw_spin_unlock(&lock->rlock); } |
spin_lock関数は再帰的でなく，同じロック変数を獲得する場合は自己デッドロックするので注意して下さい．
ロック/アンロック関数は，カーネルのプリエンプションを無効化/有効化し，ロックを獲得/解放します．
ユニプロセッサの場合，ロックはコンパイル時に取り除かれる可能性があります．
ただし，タスク実行のインターリーブを防ぐために，ロックを獲得時にプリエンプションを無効にし，ロック解放時に有効にする必要があります．
スピンロックの割り込みハンドラでの利用
スピンロックの割り込みハンドラでの利用を解説します．
スピンロックはスリープしないので，割り込みコンテキストで使用しても安全です．
割り込みハンドラでロックを使用する場合，ロックを取得する前にローカル割り込みを無効にする必要があります．
そうしないと，ロックが保持されている間に割り込みハンドラがカーネルのコードに割り込み，ロックを再獲得しようとする可能性があります．
割り込みハンドラはロックが利用可能になるのを待ちながらスピンロックしています．
しかし，ロックホルダは割り込みハンドラが完了するまで実行されません．
この多重割り込みによりロックを再獲得する際に発生するデッドロックのことを，二重獲得デッドロック（double-acquire deadlock）と呼びます．
Bottom Halfの割り込みハンドラでは，以下の関数を利用します．
- spin_lock_bh関数：Bottom Halfでロック変数を獲得するまでスピンロックする．
- spin_trylock_bh関数：Bottom Halfでロック変数を獲得するが，もし獲得できない場合はすぐに関数から返る．
- spin_unlock_bh関数：Bottom Halfでロック変数を解放する．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
static __always_inline void spin_lock_bh(spinlock_t *lock) { raw_spin_lock_bh(&lock->rlock); } static __always_inline int spin_trylock_bh(spinlock_t *lock) { return raw_spin_trylock_bh(&lock->rlock); } static __always_inline void spin_unlock_bh(spinlock_t *lock) { raw_spin_unlock_bh(&lock->rlock); } |
与えられたロックを獲得し，すべての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関数があります．
プリエンプションカウンタは，プリエンプション可能などうかを判定するために利用します．
|
1 2 3 4 |
static __always_inline int preempt_count(void) { return READ_ONCE(current_thread_info()->preempt_count); } |
linux/include/linux/preempt.hで定義されているプリエンプションの操作マクロや関数は以下になります．
- preempt_disableマクロ：カーネルプリエンプションを無効にし，プリエンプションカウンタをインクリメントする．
- preempt_enableマクロ：プリエンプションカウンタをデクリメントし，ちょうどゼロになる場合はサービスや中断されたリスケジュールがあるかどうかチェックする．
- preempt_enable_no_reschedマクロ：カーネルプリエンプションを有効にするが，サービスや中断されたリスケジュールがあるかどうかチェックしない．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#define preempt_disable() \ do { \ preempt_count_inc(); \ barrier(); \ } while (0) #define preempt_enable() \ do { \ barrier(); \ if (unlikely(preempt_count_dec_and_test())) \ __preempt_schedule(); \ } while (0) #define preempt_enable_no_resched() sched_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があります．
|
1 2 3 4 5 6 7 8 9 10 11 12 |
typedef struct { arch_rwlock_t raw_lock; #ifdef CONFIG_DEBUG_SPINLOCK unsigned int magic, owner_cpu; void *owner; #endif #ifdef CONFIG_DEBUG_LOCK_ALLOC struct lockdep_map dep_map; #endif } rwlock_t; #define DEFINE_RWLOCK(x) rwlock_t x = __RW_LOCK_UNLOCKED(x) |
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 2 3 4 5 6 7 |
#define read_lock(lock) _raw_read_lock(lock) #define read_trylock(lock) __cond_lock(lock, _raw_read_trylock(lock)) #define read_unlock(lock) _raw_read_unlock(lock) #define write_lock(lock) _raw_write_lock(lock) #define write_trylock(lock) __cond_lock(lock, _raw_write_trylock(lock)) #define write_unlock(lock) _raw_write_unlock(lock) |
セマフォ
セマフォは，並列プログラミング環境での複数の実行単位（主にプロセス）が共有する資源にアクセスするのを制御する際の，シンプルで便利な抽象化を提供する変数または抽象データ型です．
セマフォは，スリーピングロックで，割り込みコンテキストでは利用できないので注意して下さい．
タスクが利用できないセマフォを獲得しようとすると，セマフォはそのタスクを待ち行列に入れ，タスクをスリープさせます．
その後，プロセッサは他のコードを実行できるようになります．
タスクがセマフォを解放すると，待ち行列上のタスクの1つが起床し，セマフォを獲得することができます．
セマフォは，スリープ，待ち行列の維持，起床のオーバーヘッドがロック保持時間の合計を簡単に上回ってしまうため，短時間保持するロックには最適ではありません．
セマフォは，複数個のホルダーを許容します．
カウンタは与えられた値で初期化されます．
スレッドがセマフォを獲得するたびに減少します．
カウンタが0になるとセマフォは使用できなくなります．
カーネルでは，ほとんどのセマフォはバイナリセマフォ（または後述するミューテックス）です．
ユーザ空間でセマフォの使い方を知りたいあなたはこちらからどうぞ．
linux/include/linux/semaphore.hで定義されているセマフォを管理するsemaphore構造体と，セマフォを操作する関数は以下になります．
- DEFINE_SEMAPHOREマクロ：セマフォ変数を1（バイナリセマフォ）で初期化する．
- sema_init関数：セマフォ変数を指定した値で初期化する．
- down関数：セマフォ変数を獲得する．
- down_trylock関数：セマフォ変数を獲得するが，もし獲得できない場合はすぐに関数から返る．
- up関数：セマフォ変数を解放する．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
struct semaphore { raw_spinlock_t lock; unsigned int count; struct list_head wait_list; }; #define DEFINE_SEMAPHORE(name) \ struct semaphore name = __SEMAPHORE_INITIALIZER(name, 1) static inline void sema_init(struct semaphore *sem, int val) { static struct lock_class_key __key; *sem = (struct semaphore) __SEMAPHORE_INITIALIZER(*sem, val); lockdep_init_map(&sem->lock.dep_map, "semaphore->lock", &__key, 0); } extern void down(struct semaphore *sem); extern int __must_check down_trylock(struct semaphore *sem); extern void up(struct semaphore *sem); |
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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
struct rw_semaphore { struct rwbase_rt rwbase; #ifdef CONFIG_DEBUG_LOCK_ALLOC struct lockdep_map dep_map; #endif }; extern void down_read(struct rw_semaphore *sem); extern int down_read_trylock(struct rw_semaphore *sem); extern void up_read(struct rw_semaphore *sem); extern void down_write(struct rw_semaphore *sem); extern int down_write_trylock(struct rw_semaphore *sem); extern void up_write(struct rw_semaphore *sem); extern void downgrade_write(struct rw_semaphore *sem); |
ミューテックス
ミューテックスは，より厳格な使用条件を備えたバイナリセマフォです．
一度に1つのスレッドだけがミューテックスを保持できます．
ミューテックスをロックしているスレッドは，ロックを解除する必要があります．
再帰的なロックとアンロックはできません．
ミューテックスを保持したままスレッドを終了することはできません．
また，割り込みコンテキストでミューテックスを取得することはできません．
ミューテックスは関数を通じてのみ管理できます．
ミューテックスとセマフォのどちらを利用するか悩む場合，最初はミューテックスで，必要なときだけセマフォに移行するやり方がおすすめです！
ユーザ空間でミューテックスの使い方を知りたいあなたはこちらからどうぞ．
linux/include/linux/mutex.hで定義されているミューテックスを管理するmutex構造体と，ミューテックスを操作する関数は以下になります．
- mutex_initマクロ：ミューテックス変数を初期化する．
- mutex_lock関数：ミューテックス変数を獲得する．
- mutex_trylock関数：ミューテックス変数を獲得するが，もし獲得できない場合はすぐに関数から返る．
- mutex_unlock関数：ミューテックス変数を解放する．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
/* * Simple, straightforward mutexes with strict semantics: * * - only one task can hold the mutex at a time * - only the owner can unlock the mutex * - multiple unlocks are not permitted * - recursive locking is not permitted * - a mutex object must be initialized via the API * - a mutex object must not be initialized via memset or copying * - task may not exit with mutex held * - memory areas where held locks reside must not be freed * - held mutexes must not be reinitialized * - mutexes may not be used in hardware or software interrupt * contexts such as tasklets and timers * * These semantics are fully enforced when DEBUG_MUTEXES is * enabled. Furthermore, besides enforcing the above rules, the mutex * debugging code also implements a number of additional features * that make lock debugging easier and faster: * * - uses symbolic names of mutexes, whenever they are printed in debug output * - point-of-acquire tracking, symbolic lookup of function names * - list of all locks held in the system, printout of them * - owner tracking * - detects self-recursing locks and prints out all relevant info * - detects multi-task circular deadlocks and prints out all affected * locks and tasks (and only those tasks) */ struct mutex { atomic_long_t owner; raw_spinlock_t wait_lock; #ifdef CONFIG_MUTEX_SPIN_ON_OWNER struct optimistic_spin_queue osq; /* Spinner MCS lock */ #endif struct list_head wait_list; #ifdef CONFIG_DEBUG_MUTEXES void *magic; #endif #ifdef CONFIG_DEBUG_LOCK_ALLOC struct lockdep_map dep_map; #endif }; /** * mutex_init - initialize the mutex * @mutex: the mutex to be initialized * * Initialize the mutex to unlocked state. * * It is not allowed to initialize an already locked mutex. */ #define mutex_init(mutex) \ do { \ static struct lock_class_key __key; \ \ __mutex_init((mutex), #mutex, &__key); \ } while (0) extern void mutex_lock(struct mutex *lock); extern int mutex_trylock(struct mutex *lock); extern void mutex_unlock(struct mutex *lock); |
ミューテックスとスピンロックの要求とおすすめのロックは以下になります．
| 要求 | おすすめのロック |
|---|---|
| 低オーバーヘッドロッキング | スピンロックが望ましい． |
| 短いロックホールド時間 | スピンロックが望ましい． |
| 長いロックホールド時間 | ミューテックスが望ましい． |
| 割り込みコンテキストからロック | スピンロックが要求される． |
| ロック保持中にスリープ | ミューテックスが要求される． |
Completion
Completionは，あるタスクが他のタスクにイベントの発生を通知する必要がある場合に使用されます．
linux/include/linux/completion.hにあるCompletionを管理するcompletion構造体と，Completionの操作関数は以下になります．
- init_completion関数：Completion変数を初期化する．
- DECLARE_COMPLETIONマクロ：Completion変数の定義と初期化する．
- wait_for_completion関数：Completion変数がシグナルを受信するまで待つ．
- complete関数：待機状態のタスクを起床するためにシグナルを送る．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
/* * struct completion - structure used to maintain state for a "completion" * * This is the opaque structure used to maintain the state for a "completion". * Completions currently use a FIFO to queue threads that have to wait for * the "completion" event. * * See also: complete(), wait_for_completion() (and friends _timeout, * _interruptible, _interruptible_timeout, and _killable), init_completion(), * reinit_completion(), and macros DECLARE_COMPLETION(), * DECLARE_COMPLETION_ONSTACK(). */ struct completion { unsigned int done; struct swait_queue_head wait; }; /** * DECLARE_COMPLETION - declare and initialize a completion structure * @work: identifier for the completion structure * * This macro declares and initializes a completion structure. Generally used * for static declarations. You should use the _ONSTACK variant for automatic * variables. */ #define DECLARE_COMPLETION(work) \ struct completion work = COMPLETION_INITIALIZER(work) /** * init_completion - Initialize a dynamically allocated completion * @x: pointer to completion structure that is to be initialized * * This inline function will initialize a dynamically created completion * structure. */ static inline void init_completion(struct completion *x) { x->done = 0; init_swait_queue_head(&x->wait); } extern void wait_for_completion(struct completion *); extern void complete(struct completion *); |
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の書き込み側のクリティカルセクションを終了する．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
/* * Sequential locks (seqlock_t) * * Sequence counters with an embedded spinlock for writer serialization * and non-preemptibility. * * For more info, see: * - Comments on top of seqcount_t * - Documentation/locking/seqlock.rst */ typedef struct { /* * Make sure that readers don't starve writers on PREEMPT_RT: use * seqcount_spinlock_t instead of seqcount_t. Check __SEQ_LOCK(). */ seqcount_spinlock_t seqcount; spinlock_t lock; } seqlock_t /** * DEFINE_SEQLOCK(sl) - Define a statically allocated seqlock_t * @sl: Name of the seqlock_t instance */ #define DEFINE_SEQLOCK(sl) \ seqlock_t sl = __SEQLOCK_UNLOCKED(sl) /** * seqlock_init() - dynamic initializer for seqlock_t * @sl: Pointer to the seqlock_t instance */ #define seqlock_init(sl) \ do { \ spin_lock_init(&(sl)->lock); \ seqcount_spinlock_init(&(sl)->seqcount, &(sl)->lock); \ } while (0) /** * read_seqbegin() - start a seqlock_t read side critical section * @sl: Pointer to seqlock_t * * Return: count, to be passed to read_seqretry() */ static inline unsigned read_seqbegin(const seqlock_t *sl) { unsigned ret = read_seqcount_begin(&sl->seqcount); kcsan_atomic_next(0); /* non-raw usage, assume closing read_seqretry() */ kcsan_flat_atomic_begin(); return ret; } /** * read_seqretry() - end a seqlock_t read side section * @sl: Pointer to seqlock_t * @start: count, from read_seqbegin() * * read_seqretry closes the read side critical section of given seqlock_t. * If the critical section was invalid, it must be ignored (and typically * retried). * * Return: true if a read section retry is required, else false */ static inline unsigned read_seqretry(const seqlock_t *sl, unsigned start) { /* * Assume not nested: read_seqretry() may be called multiple times when * completing read critical section. */ kcsan_flat_atomic_end(); return read_seqcount_retry(&sl->seqcount, start); } /** * write_seqlock() - start a seqlock_t write side critical section * @sl: Pointer to seqlock_t * * write_seqlock opens a write side critical section for the given * seqlock_t. It also implicitly acquires the spinlock_t embedded inside * that sequential lock. All seqlock_t write side sections are thus * automatically serialized and non-preemptible. * * Context: if the seqlock_t read section, or other write side critical * sections, can be invoked from hardirq or softirq contexts, use the * _irqsave or _bh variants of this function instead. */ static inline void write_seqlock(seqlock_t *sl) { spin_lock(&sl->lock); do_write_seqcount_begin(&sl->seqcount.seqcount); } /** * write_sequnlock() - end a seqlock_t write side critical section * @sl: Pointer to seqlock_t * * write_sequnlock closes the (serialized and non-preemptible) write side * critical section of given seqlock_t. */ static inline void write_sequnlock(seqlock_t *sl) { do_write_seqcount_end(&sl->seqcount.seqcount); spin_unlock(&sl->lock); } |
メモリ順序とメモリバリア
メモリの読み込み（ロード）および書き込み（ストア）操作は，性能上の理由からコンパイラによって順序を変更することができます．
- コンパイル時にコンパイラが行う：コンパイラの最適化
- 実行時のCPUによる最適化：Total Store Ordering（TSO），Partial Store Ordering（PSO）
コンパイラの最適化やCPUのアウトオブオーダー実行により，自分のコードは以下のようなコードの並び替えが可能です．
|
1 2 |
a = 1; b = 2; |
|
1 2 |
b = 2; a = 1; |
また，以下のコードは，aとbの間には依存関係があるため，決して並べ替えられません．
|
1 2 |
a = 3; b = a; |
|
1 2 |
a = 3; b = a; |
メモリバリア（メモリフェンス）は，CPUまたはコンパイラに，バリア命令の前後に発行されるメモリ操作の順序制約を実施させるバリア命令の一種です．
これは通常，バリアより前に発行された操作は，バリアより後に発行された操作より前に実行されることが保証されることを意味します．
以下のように「a = 4;」と「b = 5;」の間にバリア命令を発行するbarrier関数を挿入しています．
|
1 2 3 |
a = 4; barrier(); b = 5; |
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コンパイラのビルトインとして実装されています．
|
1 |
#define barrier() __memory_barrier() |
また，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関数：猶予期間が経過するのを待つ．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 |
/** * rcu_read_lock() - mark the beginning of an RCU read-side critical section * * When synchronize_rcu() is invoked on one CPU while other CPUs * are within RCU read-side critical sections, then the * synchronize_rcu() is guaranteed to block until after all the other * CPUs exit their critical sections. Similarly, if call_rcu() is invoked * on one CPU while other CPUs are within RCU read-side critical * sections, invocation of the corresponding RCU callback is deferred * until after the all the other CPUs exit their critical sections. * * In v5.0 and later kernels, synchronize_rcu() and call_rcu() also * wait for regions of code with preemption disabled, including regions of * code with interrupts or softirqs disabled. In pre-v5.0 kernels, which * define synchronize_sched(), only code enclosed within rcu_read_lock() * and rcu_read_unlock() are guaranteed to be waited for. * * Note, however, that RCU callbacks are permitted to run concurrently * with new RCU read-side critical sections. One way that this can happen * is via the following sequence of events: (1) CPU 0 enters an RCU * read-side critical section, (2) CPU 1 invokes call_rcu() to register * an RCU callback, (3) CPU 0 exits the RCU read-side critical section, * (4) CPU 2 enters a RCU read-side critical section, (5) the RCU * callback is invoked. This is legal, because the RCU read-side critical * section that was running concurrently with the call_rcu() (and which * therefore might be referencing something that the corresponding RCU * callback would free up) has completed before the corresponding * RCU callback is invoked. * * RCU read-side critical sections may be nested. Any deferred actions * will be deferred until the outermost RCU read-side critical section * completes. * * You can avoid reading and understanding the next paragraph by * following this rule: don't put anything in an rcu_read_lock() RCU * read-side critical section that would block in a !PREEMPTION kernel. * But if you want the full story, read on! * * In non-preemptible RCU implementations (pure TREE_RCU and TINY_RCU), * it is illegal to block while in an RCU read-side critical section. * In preemptible RCU implementations (PREEMPT_RCU) in CONFIG_PREEMPTION * kernel builds, RCU read-side critical sections may be preempted, * but explicit blocking is illegal. Finally, in preemptible RCU * implementations in real-time (with -rt patchset) kernel builds, RCU * read-side critical sections may be preempted and they may also block, but * only when acquiring spinlocks that are subject to priority inheritance. */ static __always_inline void rcu_read_lock(void) { __rcu_read_lock(); __acquire(RCU); rcu_lock_acquire(&rcu_lock_map); RCU_LOCKDEP_WARN(!rcu_is_watching(), "rcu_read_lock() used illegally while idle"); } /* * So where is rcu_write_lock()? It does not exist, as there is no * way for writers to lock out RCU readers. This is a feature, not * a bug -- this property is what provides RCU's performance benefits. * Of course, writers must coordinate with each other. The normal * spinlock primitives work well for this, but any other technique may be * used as well. RCU does not care how the writers keep out of each * others' way, as long as they do so. */ /** * rcu_read_unlock() - marks the end of an RCU read-side critical section. * * In almost all situations, rcu_read_unlock() is immune from deadlock. * In recent kernels that have consolidated synchronize_sched() and * synchronize_rcu_bh() into synchronize_rcu(), this deadlock immunity * also extends to the scheduler's runqueue and priority-inheritance * spinlocks, courtesy of the quiescent-state deferral that is carried * out when rcu_read_unlock() is invoked with interrupts disabled. * * See rcu_read_lock() for more information. */ static inline void rcu_read_unlock(void) { RCU_LOCKDEP_WARN(!rcu_is_watching(), "rcu_read_unlock() used illegally while idle"); __release(RCU); __rcu_read_unlock(); rcu_lock_release(&rcu_lock_map); /* Keep acq info for rls diags. */ } /** * rcu_assign_pointer() - assign to RCU-protected pointer * @p: pointer to assign to * @v: value to assign (publish) * * Assigns the specified value to the specified RCU-protected * pointer, ensuring that any concurrent RCU readers will see * any prior initialization. * * Inserts memory barriers on architectures that require them * (which is most of them), and also prevents the compiler from * reordering the code that initializes the structure after the pointer * assignment. More importantly, this call documents which pointers * will be dereferenced by RCU read-side code. * * In some special cases, you may use RCU_INIT_POINTER() instead * of rcu_assign_pointer(). RCU_INIT_POINTER() is a bit faster due * to the fact that it does not constrain either the CPU or the compiler. * That said, using RCU_INIT_POINTER() when you should have used * rcu_assign_pointer() is a very bad thing that results in * impossible-to-diagnose memory corruption. So please be careful. * See the RCU_INIT_POINTER() comment header for details. * * Note that rcu_assign_pointer() evaluates each of its arguments only * once, appearances notwithstanding. One of the "extra" evaluations * is in typeof() and the other visible only to sparse (__CHECKER__), * neither of which actually execute the argument. As with most cpp * macros, this execute-arguments-only-once property is important, so * please be careful when making changes to rcu_assign_pointer() and the * other macros that it invokes. */ #define rcu_assign_pointer(p, v) \ do { \ uintptr_t _r_a_p__v = (uintptr_t)(v); \ rcu_check_sparse(p, __rcu); \ \ if (__builtin_constant_p(v) && (_r_a_p__v) == (uintptr_t)NULL) \ WRITE_ONCE((p), (typeof(p))(_r_a_p__v)); \ else \ smp_store_release(&p, RCU_INITIALIZER((typeof(p))_r_a_p__v)); \ } while (0) /** * rcu_dereference() - fetch RCU-protected pointer for dereferencing * @p: The pointer to read, prior to dereferencing * * This is a simple wrapper around rcu_dereference_check(). */ #define rcu_dereference(p) rcu_dereference_check(p, 0) void call_rcu(struct rcu_head *head, rcu_callback_t func); void synchronize_rcu(void); |
RCUの制限は以下になります．
今後のLinuxカーネルの発展に期待しましょう！
- 複数のWriterを調整する機構を提供していない．
- RCUベースのアルゴリズムの多くは，書き込みの同時実行を防ぐためにスピンロックを使用しています．
- すべての変更はシングルポインタアップデート（一箇所のポインタの更新）であるべきですが，現在は複数箇所のポインタの更新が必要とのことです．
RCUの解説動画は以下がわかりやすいです．
鏡文字で書きながら教える授業スタイルが興味深いです！
RCUを深掘りしたいあなたは，RCUの開発者「ポール・マッケニー」の解説動画がおすすめです！
動画は結構長いですが，RCUを深く学べます！
また，ポール・マッケニーが著書のRCUの論文「READ-COPY UPDATE: USING EXECUTION HISTORY TO SOLVE CONCURRENCY PROBLEMS」もおすすめです！
参考：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におけるメモリオーダーの話
- Introduction to RCU Concepts
- What is RCU? – “Read, Copy, Update”
- What is RCU, Fundamentally?
以下の動画もおすすめです！
LinuxカーネルはC言語で書かれています．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
次回はこちらからどうぞ．
