例 4–1 に、mutex ロックを使用したコードの抜粋を示します。
#include <pthread.h> pthread_mutex_t count_mutex; long long count; void increment_count() { pthread_mutex_lock(&count_mutex); count = count + 1; pthread_mutex_unlock(&count_mutex); } long long get_count() { long long c; pthread_mutex_lock(&count_mutex); c = count; pthread_mutex_unlock(&count_mutex); return (c); }
例 4–1 では、2 つの関数がそれぞれ別の目的で相互排他ロックを使用しています。increment_count() 関数は、相互排他ロックによって共有変数の不可分操作による更新を保証しています。get_count() 関数は、相互排他ロックによって 64 ビット 値の count が不可分に読み取られるようにしています。32 ビットアーキテクチャーでは、long
long
は実際には 2 つの 32 ビット値として処理されます。
整数はほとんどのマシンで共通のワードサイズであるため、整数値の読み取りは不可分操作です。
同時に 2 つのリソースをアクセスすることがあります。一方のリソースを使用しているとき、もう一方のリソースも必要となる場合があります。2 つのスレッドが同じ 2 つのリソースを要求しようとして、対応する相互排他ロックを異なる順序で獲得しようとすると、問題が発生します。たとえば、2 つのスレッドがそれぞれ mutex の 1 と 2 をロックし、次に各スレッドが互いにもう一方の mutex をロックしようとすると、デッドロックが発生します。例 4–2 に、デッドロックが発生する場合のシナリオを示します。
この問題を回避する最善の方法は、スレッドで複数の mutex をロックする場合、常に同じ順序でロックすることです。ロックが常に規定された順序で実行されれば、デッドロックは起こらないはずです。この方法を「ロック階層」と呼びます。この方法では、mutex に論理的な番号を割り振って、mutex に順序を付けます。
自分が持つ mutex の番号より小さい番号が割り振られている mutex はロックできないという規定を守るようにします。
ただし、この方法が使用できない場合もあります。規定と違う順序で相互排他ロックを獲得しなければならないこともあるからです。そのような状況でデッドロックを防ぐには、pthread_mutex_trylock() を使用します。デッドロックが避けられないような事態が生じた場合は、あるスレッドが現在保持している mutex のロックを解除する必要があります。
スレッド 1 |
スレッド 2 |
---|---|
pthread_mutex_lock(&m1); pthread_mutex_lock(&m2);
/* 解放 */
pthread_mutex_unlock(&m2); pthread_mutex_unlock(&m1); |
for (; ;) { pthread_mutex_lock(&m2);
if(pthread_mutex_trylock(&m1)==0) /* 獲得成功 */ break; /* 獲得失敗 */ pthread_mutex_unlock(&m2); } /* ロックを獲得し、解放 */ pthread_mutex_unlock(&m1); pthread_mutex_unlock(&m2); |
例 4–3 では、スレッド 1 は mutex を規定通りの順序でロックしようとしていますが、スレッド 2 ではロックの順序が違います。デッドロックが発生しないようにするために、スレッド 2 は mutex 1 を慎重にロックしなければなりません。これは、スレッド 2 が mutex 1 が解放されるまで待つとすると、スレッド 1 との間にデッドロックの関係が生じる恐れがあるからです。
デッドロックの発生を防ぐため、スレッド 2 は pthread_mutex_trylock() を呼び出し、mutex が使用可能な状態であれば獲得します。mutex が使用可能な状態でない場合、スレッド 2 はただちに終了し、エラーを返します。その時点で、スレッド 2 は mutex 2 を解放しなければなりません。その結果、スレッド 1 は mutex 2 をロックでき、その後 mutex 1 と mutex 2 の両方を解放します。
例 4–4 と例 4–5 では、一度に 3 つのロックを獲得する方法について説明します。デッドロックを防ぐため、規定された順序でロックします。
typedef struct node1 { int value; struct node1 *link; pthread_mutex_t lock; } node1_t; node1_t ListHead;
この例で使用する片方向リンクのリスト構造体は、各ノードに相互排他ロックを含んでいます。このリストから特定のノードを削除する場合は、最初に ListHead の位置からリストをたどって目的のノードを探します。ListHead が削除されることはありません。
この検索を同時並行的に行われる削除から保護するために、各ノードをロックしてからノードの内容にアクセスしなければなりません。すべての検索が ListHead の位置から開始されるので、常にリストの順序でロックされます。このため、デッドロックが発生することはありません。
目的のノードが見つかったら、この変更がそのノードと直前のノードの両方に影響を与えるため、両方をロックします。直前のノードのロックが常に最初に獲得されるので、ここでもデッドロックの心配はありません。例 4–5 は、片方向リンクリストから特定のノードを削除する C コードです。
node1_t *delete(int value) { node1_t *prev, *current; prev = &ListHead; pthread_mutex_lock(&prev->lock); while ((current = prev->link) != NULL) { pthread_mutex_lock(¤t->lock); if (current->value == value) { prev->link = current->link; pthread_mutex_unlock(¤t->lock); pthread_mutex_unlock(&prev->lock); current->link = NULL; return(current); } pthread_mutex_unlock(&prev->lock); prev = current; } pthread_mutex_unlock(&prev->lock); return(NULL); }
例 4–6 は、前述のリスト構造を修正して循環リストにしたものです。先頭のノードとして識別されるノードはありません。スレッドは適当な 1 つのノードに関連付けられ、そのノードと近傍ノードに対して操作を行います。この状況ではロック序列は適用できません。明らかに階層 (つまり、リンクをたどる順番) が循環的だからです。
typedef struct node2 { int value; struct node2 *link; pthread_mutex_t lock; } node2_t;
以下は、2 つのノードをロックし、両方のノードに対してある操作を行う C コードです。
void Hit Neighbor(node2_t *me) { while (1) { pthread_mutex_lock(&me->lock); if (pthread_mutex_trylock(&me->link->lock)!= 0) { /* failed to get lock */ pthread_mutex_unlock(&me->lock); continue; } break; } me->link->value += me->value; me->value /=2; pthread_mutex_unlock(&me->link->lock); pthread_mutex_unlock(&me->lock); }