3 分で読了 #linux-kernel #synchronization-mechanisms
このページの目次

ロック機構

カバー範囲: spinlock (qspinlock) → mutex (楽観的スピン) → rw_semaphore (percpu) → seqlock → atomic → メモリバリア (acquire/release) カーネルバージョン: 2.6 ~ 6.x。qspinlock (4.2以降) と percpu rwsem (5.x以降) を重点的に注釈付きで解説

概要

カーネルの並行制御における核心的な課題は、複数のCPUが同時に共有データにアクセスすることです。解決策は、最も軽量なアトミック操作から重量級のミューテックスまで、明確な「ロック選択チェーン」を形成しています。間違ったロックを選択すると、不要なキャッシュラインのバウシングからデッドロックに至るまで、深刻な代償を払うことになります。

重要な原則：⁠ロックが保護するのはデータであり、コードではないです。ロック戦略を設計する際は、まず「どのデータがどのコンテキストによってアクセスされるか」を特定し、その後で適切なロックを選択してください。

ロック選択の意思決定ツリー

flowchart TD
    START["共有データへのアクセス<br/>同期が必要か?"]

    START --> Q1{"単一の整数型のみか<br/>(加算/減算/ビットセット)?"}
    Q1 -->|"はい"| ATOMIC["atomic_t / atomic64_t<br/>ロックレス、ハードウェアがアトミック性を保証 ✅"]

    Q1 -->|"いいえ"| Q2{"スリープ可能か?"}

    Q2 -->|"はい"| Q3{"読み取りが多く書き込みが少ないか?"}
    Q3 -->|"はい"| RWSEM["rw_semaphore<br/>複数のリーダーが同時にロックを保持可能"]
    Q3 -->|"いいえ"| MUTEX["mutex (推奨)<br/>楽観的スピン → スリープ"]

    Q2 -->|"いいえ<br/>(割り込み/softirqコンテキスト)"| Q4{"書き込みが少なく読み取りが多く<br/>かつ読み取りがブロックしてはならないか?"}
    Q4 -->|"はい"| RCU["RCU / seqlock<br/>リーダーのオーバーヘッドゼロ"]

    Q4 -->|"いいえ"| Q5{"複数のリーダーが<br/>同時にロックを保持する必要があるか?"}
    Q5 -->|"はい"| RWLOCK["rwlock_t"]
    Q5 -->|"いいえ"| SPIN["spinlock"]

    SPIN --> Q6{"何を防止するか?"}
    Q6 -->|"softirqのみを防止"| SPIN_BH["spin_lock_bh"]
    Q6 -->|"割り込みとsoftirqの両方を防止"| SPIN_IRQ["spin_lock_irqsave"]

    classDef start fill:#e3f2fd,stroke:#1565c0
    classDef decision fill:#fff3e0,stroke:#ef6c00
    classDef lock fill:#e8f5e9,stroke:#2e7d32
    classDef api fill:#f3e5f5,stroke:#7b1fa2
    class START start
    class Q1,Q2,Q3,Q4,Q5,Q6 decision
    class ATOMIC,RWSEM,MUTEX,RCU,RWLOCK,SPIN lock
    class SPIN_BH,SPIN_IRQ api

Spinlock: qspinlock (4.2以降)

qspinlock が必要な理由

従来の ticket spinlock の問題点:
  各CPUがlock word上でスピンする → 全CPUが同じキャッシュラインを読み取る
  → キャッシュラインが全CPU間でバウシングする
  → 16コア以上でパフォーマンスの破綻

qspinlock (queued spinlock):
  各CPUが独自のper-CPU MCSノード上でスピンする
  → 各CPUが異なるキャッシュラインでスピンする!
  → unlock時に次のCPUのノードへの書き込みのみが必要 → キャッシュライン転送は1回
  → 128コア以上でも効果的

// kernel/locking/qspinlock.c
// qspinlockの4バイトアトミックワード:
//   byte 0: locked (1ビット) + pending (1ビット)
//   byte 1: tailインデックス (MCSノードキューの末尾を指す)
//   bytes 2-3: tail CPU

void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) {
    // 1. ロックが空の場合 → 直接取得 (locked byteのCAS)
    // 2. pendingビットが立っていない場合 → pendingを立て、lockedビットがクリアされるのを待つ
    // 3. それ以外の場合 → MCSノードキューに追加 (自身のノード上でスピン)
}

// API (include/linux/spinlock.h):
spin_lock(&lock);            // ロック取得 (プリエンプション無効化済みと仮定)
spin_unlock(&lock);          // 解放
spin_lock_irq(&lock);        // ローカル割り込み無効化 + ロック取得
spin_unlock_irq(&lock);
spin_lock_irqsave(&lock, flags);   // IF状態を保存 + 割り込み無効化 + ロック取得
spin_unlock_irqrestore(&lock, flags);
spin_lock_bh(&lock);         // ボトムハーフ (softirq) を無効化 + ロック取得
spin_unlock_bh(&lock);

Mutex: 楽観的スピン

// kernel/locking/mutex.c
struct mutex {
    atomic_long_t       owner;          // 現在の保持者のtask_struct *
    raw_spinlock_t      wait_lock;      // wait_listを保護
    struct list_head    wait_list;      // 待機キュー
};

mutex_lock(&lock):
  1. クイックパス: 保持者がいない場合 → atomic_long_cmpxchgでowner=currentを設定し、返す
  2. 楽観的スピン: ownerが別のCPUで実行中か?
     → スピン待機 (スリープせず、ownerがすぐに解放すると期待)
     → ownerが実行中でない (スリープした) → スピン停止、スリープへ移行
  3. スリープ待機: TASK_UNINTERRUPTIBLEを設定し、wait_listに追加、schedule()

mutex_unlock(&lock):
  1. owner = 0 を設定
  2. wait_listが空でない場合 → 最初の待機者をウェイクアップ
      → wake_up_process() → 待機者はmutex_lockのステップ2に戻る

rw_semaphore: 読み書きセマフォ

// kernel/locking/rwsem.c
// percpu rwsem (5.x以降の最適化):
//   読み取りロック: percpu refcountを増加 → グローバルロック不要 (ローカルCPU操作)
//   書き込みロック: 全CPUのpercpu refcountを走査 → 全ゼロになるのを待機

// リーダー飢餓防止:
//   rwsemは待機中のライターを追跡する
//   待機中のライターがいる場合 → 新しいリーダーは進入しない → ライターは飢餓しない

down_read(&sem);              // 読み取りロック取得
up_read(&sem);
down_write(&sem);             // 書き込みロック取得
up_write(&sem);
down_read_trylock(&sem);      // ブロックしない

Seqlock: 順序ロック

// include/linux/seqlock.h
// ライターは排他制御 (spinlock取得)、リーダーはロックレス
// リーダーはシーケンス番号で「ライターが修正中かどうか」を検出し、必要に応じて再試行する

struct seqlock {
    seqcount_t seq;       // シーケンス番号 (偶数=安定、奇数=書き込み中)
    spinlock_t lock;      // ライターを保護
};

// リーダー:
do {
    seq = read_seqbegin(&seqlock);   // シーケンス番号を記録
    // ... データを読み取る ...
} while (read_seqretry(&seqlock, seq));  // シーケンス番号が変わったか? 再試行

// ライター:
write_seqlock(&seqlock);
seq++;    // 奇数 → リーダーが検出して再試行
// ... データを修正 ...
seq++;    // 偶数 → リーダーが読み取り可能
write_sequnlock(&seqlock);

// 典型的な用途: timekeeper (gettimeofdayのロックレス読み取り、稀な書き込み)

アトミック操作

// include/linux/atomic/atomic-instrumented.h
// 全アーキテクチャで保証される基本アトミック操作:

// 算術演算
atomic_inc(&v);  atomic_dec(&v);
atomic_add(n, &v);  atomic_sub(n, &v);

// CAS (Compare-And-Swap)
atomic_cmpxchg(&v, old, new);  // if (v==old) v=new; return old;

// メモリ順序付きRMW (5.x以降)
atomic_add_return(n, &v);       // return v+n (フルバリア)
atomic_add_return_acquire(n, &v);  // ACQUIREセマンティクス
atomic_add_return_release(n, &v);  // RELEASEセマンティクス

// ビット操作
set_bit(nr, addr);  clear_bit(nr, addr);
test_and_set_bit(nr, addr);  // アトミックなtest + set → 単純なロックの実装に使用

メモリバリア

コンパイラバリア:
  barrier(): コンパイラの並べ替えを防ぐ (CPUハードウェアの並べ替えには影響しない)

CPUメモリバリア:
  smp_mb():  フルバリア (前後の全メモリ操作の順序付け)
  smp_rmb(): 読み取りバリア (loadが跨げない)
  smp_wmb(): 書き込みバリア (storeが跨げない)

Acquire/Releaseセマンティクス:
  ACQUIRE: この操作以降のload/storeは、前に並べ替えられない
  RELEASE: この操作以前のload/storeは、後に並べ替えられない
  
  spin_lock()   = ACQUIRE (クリティカルセクション内の操作がロック外に漏れない)
  spin_unlock() = RELEASE

明示的なバリアが必要な場合:
  → ロックレスデータ構造 (リングバッファ、RCU)
  → デバイスDMA (DMAバッファへの書き込みがDMA開始前に完了していることを保証)

デバッグとロック分析

# lockdep: ロック依存関係の検証 (デッドロック検出)
dmesg | grep -i lockdep   # 起動時に自動チェック

# lockstat: ロック競合の統計
cat /proc/lock_stat | head -20

# ロック競合のトレースをトリガー
echo 1 > /sys/kernel/debug/tracing/events/lock/lock_acquire/enable
echo 1 > /sys/kernel/debug/tracing/events/lock/lock_release/enable

参考

  • ソースコード⁠: kernel/locking/ (qspinlock, mutex, rwsem, rtmutex), include/linux/seqlock.h, include/linux/atomic/
  • カーネルドキュメント⁠: Documentation/locking/ ディレクトリ
  • LWN: "Queued spinlocks", "The percpu rwsem", "Memory barriers for kernel hackers"

キーワード: qspinlock, mutex, rw_semaphore, seqlock, atomic, CAS, memory barrier, acquire/release, lockdep

関連ページ

© 2026 liz's doc