排他制御

排他制御とは

排他制御とは、複数のプロセスが共有資源に同時にアクセスする際に発生する競合を防ぎ、データの整合性を保つための仕組みです。これは、特に並行処理を行うシステムにおいて不可欠な技術であり、相互排除（mutual exclusion）とも呼ばれます。具体的には、クリティカルセクションと呼ばれる、共有資源にアクセスするコード領域に、複数のプロセスが同時に侵入することを防ぐことを目的としています。

排他制御の歴史

排他制御の問題は、1965年にエドガー・ダイクストラによって、並行プログラミング制御における問題の解決策として初めて取り上げられました。この研究が、今日の排他制御技術の基礎となっています。

排他制御の重要性

排他制御の重要性を示す例として、片方向連結リストの操作があります。複数のプロセスが同時に連結リストのノードを削除しようとすると、ポインタの書き換えが競合し、リストの整合性が失われる可能性があります。排他制御を導入することで、このような競合を防ぎ、データの整合性を確保することができます。

排他制御の実施方法

排他制御は、ハードウェアによる方式とソフトウェアによる方式の二つに大きく分けられます。

ハードウェアによる方式

割り込み禁止: シングルプロセッサシステムでは、クリティカルセクションに入る際に割り込みを禁止することで排他制御を実現できます。しかし、この方法はクリティカルセクションが長くなるとシステム時刻が遅れたり、プロセスの停止によってシステム全体が停止する可能性があるという問題点があります。
ビジーウェイト: 共有メモリと不可分なテスト・アンド・セット命令を用いることで、排他制御を実現します。この方法では、一度に一つのプロセスだけがフラグをセットできることが保証され、他のプロセスはフラグがセットできるまで待機します。プリエンプションが可能なため、プロセスが停止した場合でもシステム全体は機能し続けるという利点があります。
コンペア・アンド・スワップ (CAS) 命令: CAS命令を用いることで、wait-freeと呼ばれる排他制御を実装できます。この方法は、連結リストのノード挿入時に使用され、複数のプロセスが同時に挿入を試みても、一度に一つのプロセスしか成功しないように制御します。

ソフトウェアによる方式

ソフトウェアのみで排他制御を実現する方法もあります。以下のようなアルゴリズムが知られています。

デッカーのアルゴリズム
ピーターソンのアルゴリズム
ランポートのパン屋のアルゴリズム
Szymanskiのアルゴリズム
Taubenfeld の Black-White Bakery Algorithm

これらのアルゴリズムは、アウト・オブ・オーダー実行が働く環境では動作しない場合があるため、注意が必要です。

OSの同期機構の利用

OSのマルチスレッドライブラリが提供する同期機構を利用することが推奨されます。これらのライブラリは、ハードウェアサポートを利用したり、ソフトウェアによる排他制御を実装したりしています。OSは、ロックの獲得に失敗したスレッドを中断させたり、他のスレッドを動作させたりすることで、効率的な排他制御を実現します。

高度な排他制御

これまでに説明した方式を基に、以下の同期プリミティブを構築することができます。

ロック: 共有資源へのアクセスを制御するための基本的な仕組み
スピンロック: ロックが解放されるまでビジーウェイトで待機するロック
ミューテックス: 相互排除を実現するためのシンプルなロック
セマフォ: k-相互排除を実現するためのロック
モニタ: 共有資源へのアクセスを制御するための高レベルな機構
メッセージパッシング: プロセス間でメッセージを交換することで同期を取る方法

排他制御の副作用

排他制御には、デッドロックやリソーススタベーション、優先順位の逆転といった副作用があります。これらの問題を解決するために、Lock-freeやWait-freeアルゴリズムといった研究も行われていますが、まだ完璧な解決策は見つかっていません。

留意すべき現象と性質

デッドロック

複数のプロセスが互いに相手が持つ資源の解放を待つ状態です。この状態になると、どのプロセスも処理が進まなくなります。

ライブロック

複数のプロセスがお互いに資源を譲り合っている状態です。処理は進んでいますが、どのプロセスも資源を獲得できず、処理が完了しません。

フェアネス

共有資源を利用したいユーザが、いつかは必ず資源を利用できるという性質です。フェアネスが満たされないと、一部のユーザが資源をいつまでも利用できないという問題が発生します。

k-バイパス

共有資源へのアクセス要求を出したユーザが、後から要求を出した最大k個のユーザによって、先に資源を使われてしまう可能性があるという性質です。

コンボイ

あるプロセスがロックを獲得したにもかかわらず、そのプロセスがCPU上で実行されていない状態です。この状態では、ロックの獲得からクリティカルセクション内の処理を開始するまでに遅延が発生し、システムの性能が低下します。

まとめ

排他制御は、並行処理システムにおけるデータの整合性を保つために不可欠な技術です。様々な実装方法が存在しますが、デッドロックやライブロックといった問題も抱えています。適切な排他制御方式を選択し、これらの問題に注意を払いながらシステムを設計する必要があります。

参考文献

Michel Raynal: Algorithms for Mutual Exclusion, MIT Press, ISBN 0-262-18119-3
Sunil R. Das, Pradip K. Srimani: Distributed Mutual Exclusion Algorithms, IEEE Computer Society, ISBN 0-8186-3380-8
Thomas W. Christopher, George K. Thiruvathukal: High-Performance Java Platform Computing, Prentice Hall, ISBN 0-13-016164-0
Gadi Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson/Prentice Hall, ISBN 0-13-197259-6

関連項目

不可分操作
並行性制御
セマフォ
食事する哲学者の問題
インターロック (安全技術)

外部リンク

"Common threads: POSIX threads explained - The little things called mutexes" by Daniel Robbins
Mutual exclusion algorithm discovery
Mutual Exclusion Petri Net
Mutual Exclusion with Locks - an Introduction
Mutual exclusion variants in OpenMP
* The Black-White Bakery Algorithm

もう一度検索