C++ での競合状態
このチュートリアルでは、競合状態の概念について学びます。 最初にスレッドの概要を説明し、次にスレッドの競合状態について例を挙げて説明します。
最後に、競合状態を回避/制御するためのソリューションについて説明します。
スレッドとは
スレッドは軽量プロセスです。 プロセスは、プロセスの多くのリソースを共有する複数のスレッドを持つことができます。
スレッドは協力することを意図しています。 したがって、他のリソース間でメモリ/変数を共有します。
スレッドは、プロセス内で並行タスクを実行するために使用されます。 たとえば、MS Word の処理プロセスには、同時に実行される複数のタスクがあります。
これらのタスクには、スペル、文法、自動保存、キーワードのラベル付け、インデント、および書式設定が含まれます。 別々のスレッドを使用して、これらの同時タスクを同時に実行できます。
並べ替えと印刷の同時実行
ここでは、スレッドをよりよく理解するために、1つのコーディング例について説明します。 多くの値をソートして出力する必要があるとします。
まず、印刷する前に、それらを完全に整理する必要があります。
ただし、selection sort のようないくつかの並べ替え手法があります。これは、各反復で、リストの先頭に小さい要素を取得するように数値を並べ替えます。 したがって、並行して印刷を開始できます。
コードは次のとおりです。
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define SIZE 1000
int x[SIZE];
void init() {
int i;
for (i = 0; i < SIZE; i++) x[i] = rand() % 1000;
}
void* print(void* a) {
int i;
for (i = 0; i < SIZE; i++) printf("%d ", x[i]);
printf("\n");
}
void* sort(void* b) {
int i, j, temp;
for (i = 0; i < SIZE - 1; i++)
for (j = SIZE - 1; j >= 1; j--)
if (x[j] < x[j - 1]) {
temp = x[j];
x[j] = x[j - 1];
x[j - 1] = temp;
}
}
int main() {
srand(time(0));
init();
pthread_t tSort, tPrint;
pthread_create(&tSort, NULL, sort, NULL);
pthread_create(&tPrint, NULL, print, NULL);
pthread_join(tSort, NULL);
pthread_join(tPrint, NULL);
return 0;
}
このコードでは、sort 関数と print 関数が並行して実行されています。 ただし、出力が表示された場合、それは正しくありません。
その理由は、並べ替えスレッドが印刷スレッドよりも遅く、それらの間に同期がないためです。 したがって、印刷スレッドは、まだソートされていない値をすばやく印刷します。 したがって、出力はソートされていません。
マルチスレッド プログラムでは、これらの同期の問題やその他の問題が発生する傾向があります。 次に、競合状態と呼ばれる問題の 1つについて説明します。
競合状態とは
競合状態は、複数のプロセスまたはスレッドが共有データに同時にアクセスするときに発生する可能性がある望ましくない状態です。
最終的な値は、最後にデータにアクセスするプロセス/スレッドによって異なります。 例を挙げて説明しましょう。
A と B という 2つのスレッドと共有変数 x があるとします。 両方のスレッドが命令 x++ を並行して実行しています。
この命令を低水準言語で批判的に調べると、この命令は 3つの命令で構成されています。 3つの指示は次のとおりです。
read x inc x write x
最初の命令は、変数をメモリからレジスタ (プロセッサ内) に読み込みます。 2 番目の命令では、変数が 1 インクリメントされ、結果がレジスタに格納されます。
変数は、3 番目と最後の命令でメモリに書き戻されます。
2つのスレッドがこれらの命令を並行して実行しているとします。 それらの実行シーケンスについてはわかりません。 スケジューリングアルゴリズム、タイムスライス、プロセスの優先度、実行中/新しいプロセスのセットなど、さまざまな要因に依存します。
これらの命令を実行する複数のシーケンスが考えられる場合があり、毎回異なるシーケンスが発生する可能性があります。 たとえば、スレッド A が最初の 2つの命令を実行すると、オペレーティング システムがコンテキストを切り替えます。
変数の値が 5 で、スレッド A が 5 を読み取り、それを 1 だけインクリメントしたとします。したがって、値は 6 になります (ただし、レジスタ内)。 コンテキストが切り替わり、スレッド B が実行を開始すると、同じ値 5 も読み取られます。
スレッド B は値を 1 ずつ増やします。 値は≪6≫になります。
スレッド B は最後の命令を完了し、6 値をメモリに書き込みます。
コンテキストが再び切り替わり、最終的に制御はスレッド A に移ります。 ここで、スレッド A が最後の命令を実行し、x を書き込みます。
スレッド A が値 5 を読み取り、それを 1 だけインクリメントしたことを思い出してください。 スレッド A も 6 をメモリに書き込みます。
その結果、値は 7 ではなく 6 になり、2つのスレッドがインクリメント操作を実行したため、値は 7 になるはずです。 したがって、予期しないコンテキストの切り替えにより、結果は正しくありません。
生産者と消費者の問題
Producer-Consumer の問題について説明する前に、次のコーディング例を見てみましょう。
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
int count = 0;
void* producer(void* arg) {
for (int i = 0; i < 50000; i++) count++;
}
void* consumer(void* arg) {
for (int i = 0; i < 50000; i++) count--;
}
int main() {
pthread_t tid1, tid2;
printf("Count = %d\n", count);
pthread_create(&tid1, NULL, producer, NULL);
pthread_create(&tid2, NULL, consumer, NULL);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
printf("Count = %d\n", count);
return 0;
}
このコードは、生産者と消費者の問題と呼ばれるオペレーティング システムの古典的な問題を示しています。 このコードには、0 で初期化されたグローバル (共有) 変数 count があります。
producer 関数はカウントを 1 ずつ増やし、consumer 関数はカウントを 1 減らします。
ただし、両方の関数は 2つの異なるスレッドによって実行され、コンテキストの切り替えはいつでも発生する可能性があります。 これは、コードを実行することで簡単に体験できます。
競合状態がなければ、結果は 0 になるはずです。これは、両方の関数がインクリメントとデクリメントを同じ回数実行しているためです。 単位のインクリメントとデクリメントは、count の値が最後にゼロになることを意味します。
ただし、このコードを実行すると、値がゼロではないことがわかります。 むしろ、反復ごとに異なる値が発生し、スケジューリングが予測不可能であることを明確に示しています。
いくつかの実用的な生産者と消費者の例
上で説明した 2つのスレッドのインクリメントの例は、仮説上の問題ではありません。 マルチスレッドを使用する場合、このような実用的なシナリオが多数存在します。
たとえば、銀行システムでは、顧客は金額を引き出すために 2つの選択肢があります。 1つは小切手を銀行に提示することですが、同時に、誰かが顧客の ATM カードを使用して ATM から金額を引き出すことができます。
同様に、偶然にも 2 人以上の教師が同じ生徒の点数を更新/投稿し、それによって生徒の合計点数が増減する可能性があります。 2 社以上の会社が、顧客の毎週、毎月、または年間のサブスクリプションを同時に差し引くことができます。
競合状態により、不適切な結果が生じる可能性があり、これは手頃な価格ではありません。 したがって、競合状態の問題により、マルチスレッドの適用性が多くのシナリオで実用的ではないことを発表する必要がありますか?
いいえ、競合状態を回避/制御するソリューションがあります。
競合状態を避ける
競合状態に対するハードウェアとソフトウェアの両方のソリューションがあります。 ハードウェア ソリューションは、関連するアトミック命令を CPU 命令セットの一部として提供することです (x86 アーキテクチャの CMPXCHG など)。
ソフトウェア ソリューションでは、ミューテックスまたはセマフォを使用して、クリティカル セクションへのプロセスのエントリを正規化します。
アトミック操作
メーカーは、ハードウェアにアトミック操作を実装できます。 ハードウェアでアトミック操作を実装した後、そのような命令はコンテキスト切り替えなしで実行を完了します。 言い換えれば、プロセス/スレッドの実行は部分に分割されるべきではありません。
ただし、このソリューションはメーカー向けであり、一般ユーザーが実装することはできません。
相互排除
相互排除とは、あるプロセス/スレッドが共有変数にアクセスしている場合、他のプロセス/スレッドが別のプロセス/スレッドによって既に保持されている共有変数にアクセスすることを許可しないことを意味します。
Mutual Exclusion は、ミューテックス (ロック) またはセマフォを使用して実装できます。 Mutex vs. Semaphore をクリックして、概念を明確にすることができます。
Mutex を使用して競合状態を回避する
Mutex は特別なロックの概念です。 このロックはスレッド間で共有されます。 ただし、複数のスレッドがミューテックスをロックしたい場合、1つの (最初の) スレッドのみがロックに成功し、クリティカル セクション に入ります。
ミューテックスをロックしようとしている残りのスレッドは、最初のスレッドがクリティカル セクションから出てミューテックスのロックを解除するまでブロックされます。
ロックされていないミューテックスは、いつでも 1つのスレッドでロックできます。 ミューテックスのロックを解除すると、ブロッキングスレッドのいずれかがミューテックスをロックしてクリティカルセクションに入る機会を得ることができます。
ミューテックスにはキューの概念がありません。 ブロッキング/待機中のスレッドはいずれも、ミューテックスを取得してロックする機会を得ることができます。
これは非常に単純なソリューションであり、競合状態で 2つのスレッドまたは競合状態で複数のスレッドがあり、ターン/キューの問題がない場合に非常に役立ちます。
pthread Linux ライブラリを使用してミューテックス ロックを実装する次の C の例を使用して、ソリューションを実現しましょう。
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
int count = 0;
pthread_mutex_t lock;
void* producer(void* arg) {
for (int i = 0; i < 50000; i++) {
pthread_mutex_lock(&lock);
count++;
pthread_mutex_unlock(&lock);
}
}
void* consumer(void* arg) {
for (int i = 0; i < 50000; i++) {
pthread_mutex_lock(&lock);
count--;
pthread_mutex_unlock(&lock);
}
}
int main() {
pthread_t tid1, tid2;
printf("Count = %d\n", count);
pthread_mutex_init(&lock, NULL);
pthread_create(&tid1, NULL, producer, NULL);
pthread_create(&tid2, NULL, consumer, NULL);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
pthread_mutex_destroy(&lock);
printf("Count = %d\n", count);
return 0;
}
このコードは複数回実行できます。 毎回、カウント 0 の値が返されます。
このコードには、特殊なタイプの共有変数ロック pthread_mutex_t があります。 プロデューサー関数とコンシューマー関数は、クリティカル セクション命令 count++ と count-- を実行する前にロックされます。
繰り返しますが、どちらもクリティカル セクションの終了後に unlock 関数を呼び出してミューテックスを解放します。
main 関数では、ミューテックスを初期化し、ミューテックスの使用後にミューテックスを破棄しています。
セマフォを使用して競合状態を回避する
セマフォは、オペレーティング システムによって提供されるソリューションです。 セマフォは、スレッド同期のソリューションです。
命令の特定の実行順序が必要な場合があります。 ただし、競合状態を回避するために使用することはできますが、正確な解決策ではありません。 後で、その理由について説明します。
ここでは、同期の長くて詳細なトピックを避け、セマフォを使用して競合状態を回避する方向に進んでいます。 セマフォを使用すると、特定の時点でスレッドが停止し、別のスレッドからのシグナルを待機します。
セマフォをゼロで初期化し、wait 関数を呼び出して、セマフォを 1 減らしてスリープ状態に入ります。
その後、別のスレッドがシグナル操作を呼び出し、セマフォを 1 ずつインクリメントし、キュー内のスリープ状態のスレッドを呼び起こします。
Linux では、セマフォはライブラリ semaphore.h で利用できます。 待機操作とシグナル操作のための待機関数とポスト関数があります。
コードを参照してください：
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
int count = 0;
sem_t semaphore1, semaphore2;
void* producer(void* arg) {
for (int i = 0; i < 50000; i++) {
count++;
sem_post(&semaphore1);
sem_wait(&semaphore2);
}
}
void* consumer(void* arg) {
for (int i = 0; i < 50000; i++) {
sem_wait(&semaphore1);
count--;
sem_post(&semaphore2);
}
}
int main() {
pthread_t tid1, tid2;
printf("Count = %d\n", count);
sem_init(&semaphore1, 0, 0);
sem_init(&semaphore1, 0, 0);
pthread_create(&tid1, NULL, producer, NULL);
pthread_create(&tid2, NULL, consumer, NULL);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
sem_destroy(&semaphore1);
sem_destroy(&semaphore2);
printf("Count = %d\n", count);
return 0;
}
繰り返しますが、このコードを実行して、共有変数の正確な/正しい値を取得できます。 実装はミューテックスに似ています。 ただし、大きな違いの 1つは初期化ステップです。
初期化関数には 3つのパラメーターがあります。 1つ目はセマフォ変数です。
2 番目は 0 または 1 です。 ここで、0 はセマフォが同じプロセスのスレッド間で共有されることを意味し、1 はセマフォが異なるプロセスのスレッド間で共有されることを意味します。
3 番目のパラメータはセマフォの値です。 複数のスレッド (ただし、いくつかのカウントに制限されています) が一緒にクリティカル セクションに入ることができるようにする場合は、セマフォ値をカウントで初期化できます。
この実装の 2つ目の違いは、2つのセマフォを使用しているのに対し、ミューテックスの場合は 1つのロックしか使用していないことです。
ミューテックス コードは、共有変数を使用する前にロックを設定し、共有変数を使用した後にロックを解放します。 顧客が銀行のロッカールームでロッカーを操作しようとするときはいつでも、スタッフはロッカーを開く前にロッカーをロックするためのキーを顧客に渡し、ロッカーがロックされた後にロッカールームを開きます。
ただし、セマフォでは、2つのセマフォを使用します。 どちらも 0 で初期化されます。これは、他のスレッドがシグナルを出すまで、呼び出しスレッドの待機がブロックされることを意味します。 ここで、コンシューマは、カウントをインクリメントした後、プロデューサ スレッドによって通知されたセマフォ 1 を待機しています。
同時に、プロデューサー スレッドはセマフォ 2 を待機しています。これは、カウントをデクリメントした後にコンシューマー スレッドによって通知されます。
このようにして、プロデューサーとコンシューマーはカウントを 1つずつ増減します。これが同期です。 セマフォを使用して、カウントを正しく保ちます。 ただし、スレッドが順番に実行されるように制限しています。
ミューテックスの場合、共有変数カウントの値を損なうことなく、両方のスレッドを任意の順序で実行できます。
まとめ
スレッドは、コード/関数を並行して実行するのに非常に役立ちます。 ただし、競合状態など、スレッドに関するいくつかの問題があります。 この状態は、予期しない結果を引き起こす可能性があります。
幸いなことに、ミューテックス ロックとセマフォを使用して競合状態を回避できます。 競合状態を処理する最善かつ正しい方法は、ミューテックスです。