並行プログラミング入門 ―Rust、C、アセンブリによる実装からのアプローチ

7章同期処理2

　同期処理は並行プログラミングになくてはならない基本的な要素であることはこれまで説明した。これまでに説明したスピンロックやミューテックスといった基本的な同期処理手法でも基本的な要件を満たすことはできるが、いくつか考慮すべき点がある。例えば、高速なCPUと低速なCPUがスピンロックでロックを獲得すると、高速なCPUばかりがロックを獲得してしまい公平性に問題が残る。また、食事する哲学者の例で見たように、並行プログラミングではデッドロックにも気を付けなければならない。そこで、本章では、公平性やデッドロックといった問題を解決する、より発展的な同期処理手法について説明する。

　本章では、はじめに、公平性を担保するロックについて説明し、その後、ソフトウェアトランザクショナルメモリ（STM）について解説する。STMは従来のロック手法と違い、デッドロックの起きない同期処理手法となる。最後に、複数のプロセスから同時にアクセス可能なデータ構造である、ロックフリーデータ構造について説明する。ロックフリーデータ構造を用いると、排他ロックなどを用いずとも、複数のプロセスで更新可能なデータ構造を実現できる。なお、本章の実装はすべてスレッドを用いているため、プロセスではなくスレッドと表記するが、これらアルゴリズムはカーネル内プログラムへも適用可能である。

7.1　公平な排他制御

　本節では公平な排他制御について説明する。はじめに弱い公平性を担保するロックについて説明し、その後、共有資源へのアクセス頻度、つまりコンテンション（contention）を減らす手法について説明する。コンテンションとは競争という意味であり、ロック獲得の競争が激しくなると、その分実行速度が低下し無駄にCPUリソースを消費してしまう。特に、Non-Uniform ...