哲学者の食事、問題で出てくるマルチスレッドの並行処理について学んでいます。
並行処理について学ぶ際、何冊か本を参考にしました。
書籍毎に焦点が違い、頭の中で整理するのに少し時間がかかりました。
共通して言っていることは以下のようなことです:
スレッド（マルチスレッド）はプロセスの中に作られる複数のコンテクストである。
各スレッドはスタックにあるがそれぞれ参照する関数は共有アドレスにアクセスするため、その情報を更新した場合問題が起こる。これをデータ競合という。
複数のスレッドが更新しうる箇所をクリティカルセクションを呼び、アトミックに扱わなければならない。このクリティカルセクションを１つのスレッドがアクセスしている間は相互排除を行うべきだ。この相互排除(スピンロック等を使う)歴史は紆余曲折あったが、OSサポートが入ったmutexで保護することが最善策だ。
とにかくデータ競合が起こるクリティカルセクションはmutexでlock/unlockする、で先に進むでも良さそうですが、先進む前に、マルチスレッドのデータ競合について少し深掘りました。
本記事では、"Operating Systems Three Easy Pieces" の参考書をベースにしています。
本題に入る前に、以下について基本的なイメージをつかみました。
1. 並行処理とは？
2. プロセスとスレッドの違いとは？
3. マルチスレッドにおけるデータ競合とは？
その後本題の以下についてまとめています。
4. データ競合の深掘り
1. 並行処理とは
並行処理(concurrency)とは、
複数の実行単位が時間的に重なりながら進行すること
です。
並行処理はスレッドだけではなく、大きくわけて３つの方法があります。
- プロセス
- スレッド
- I/O非同期(イベント駆動型)
-> Node.jsのイベントループやPythonのasyncioなど
2. プロセスとスレッドの違いについて
並行処理の代表的な実装形態は「プロセス」と「スレッド」です。
プロセスは以下の点において共通しています。
スレッドもプロセスもOSのスケジューラによって実行が切り替えられます、また、実行順序が保証されません。
マルチプロセスは、それぞれのプロセスは独立した仮想アドレス空間をもち、メモリは基本的に共有されません。
対してスレッドとは、１つのプロセス内に複数走るコンテクスト、と定義されています。
マルチスレッドはアドレス空間を共有し、同じデータにアクセスできます。
図にするとこのような感じです。
(参照元: p.306 "Operating Systems Three Easy Pieces")
3. マルチスレッドにおけるデータ競合とは？
データ競合とは、同じメモリ位置に複数スレッドが同期なしでアクセスし、少なくとも一方が書き込みを行うことを指します。
実際にデータ競合が起こった場合の結果を見てみます。
仮に、スレッド１とスレッド２がグローバルにおいた変数の値を加算する処理があるとします。
count = count + 1;
この変数をスレッド１が処理しようとしている間に、スレッド２も同じメモリ位置へアクセスをした場合、
出力countが期待される値にならない、というようなことです。
以下のファイル(thread.c)をコンパイル後、これを試してみてください
./a.out 200
./a.out 2000
./a.out 10000
// thread.c
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
int max;
volatile int count = 0;
void *mythread(void *arg)
{
char *letter = (char *)arg;
int i;
printf("%s: begin [addr of i: %p] [count = %d at %p]\n",
letter, &i, count, &count);
for (i = 0; i < max; i++)
{
count = count + 1; // <-クリティカルセクション
}
printf("%s: done\n", letter);
return NULL;
}
int main(int argc, char *argv[])
{
pthread_t p1, p2;
int ret;
if (argc != 2)
{
fprintf(stderr, "usage: ./a.out <loopcount>\n");
return (1);
}
max = atoi(argv[1]);
printf("main: begin [count = %d] [%p]\n",
count, (void *)&count);
ret = pthread_create(&p1, NULL, mythread, "A");
if (ret != 0)
{
fprintf(stderr, "pthread_create A failed\n");
return (1);
}
ret = pthread_create(&p2, NULL, mythread, "B");
if (ret != 0)
{
fprintf(stderr, "pthread_create B failed\n");
return (1);
}
ret = pthread_join(p1, NULL);
if (ret != 0)
{
fprintf(stderr, "pthread_join A failed\n");
return (1);
}
ret = pthread_join(p2, NULL);
if (ret != 0)
{
fprintf(stderr, "pthread_join B failed\n");
return (1);
}
printf("main: done\n");
printf("[count: %d]\n", count);
printf("[should: %d]\n", max * 2);
return (0);
}
200, 2000あたりを試した場合には値が崩れませんが、10000くらいを入力すると、期待出力と値異なっているのが分かります。
大きいループ回数で顕在化しやすいです。
データ競合が起こりうる領域をクリティカルセクションと呼びます。
ここでは、count = count + 1;がそれにあたります。
この解決方法については、クリティカルセクションにアクセスできないような措置をとることです。
これを相互排除(mutual exclusion)と言います。冒頭で、mutexでlock/unlockすれば良い、というようなことが解決策です。
相互排除については、LOCKSの歴史あれこれを辿ることになり、シングルコアCPU時代からマルチコアCPU時代の移り変わりが関係してくるようで、別の記事でまとめたいと思います。
クリティカルセクションや相互排除、セマフォといった概念は、ダイクストラによって提唱された呼び名です。
注意:
『Operating Systems: Three Easy Pieces』では、この現象を主に「競合条件（race condition）」と呼び、「data race」をその具体例として補足しています
4. データ競合の深掘り
さて、count = count + 1;このクリティカルセクションにおけるデータ競合ですが、
我々レベルからは１つの処理に見えるのでどこがどうデータ競合なのか、自分は腑に落ちませんでした。
count = count + 1; は高級言語では1行に見えますが、
CPUレベルでは多くの場合「読み込み→加算→書き戻し」のような複数命令（read–modify–write）に分解されます。
以下はその一例です（実際の命令列は環境や最適化により異なります）。
mov 0x8049alc, %eax // load: メモリから読み込み
add $0x1, %eax // modify: レジスタで加算
mov %eax, 0x8049alc // store: メモリへ書き戻し
(意味)
- アドレス0x8049alcの値をレジスタに移動します
- レジスタに１を加算します
- その値をまたアドレス0x8049alcに戻します
この理解をもとに、スレッド1, 2があったとして割り込みによるデータ競合が発生したという状況をアセンブリレベルで図解にすると、以下のようになります。
出力のcounter期待値は52ですが、データ競合によりcounterは51となっています。
OS スレッド 1 スレッド 2 PC eax counter
________________________________________________________________________________
クリティカルセクション前 100 0 50
mov 0x8049alc, %eax 105 50 50
add $0x1, %eax 108 51 50
割り込み
save T1
restore T2 100 0 50
mov 0x8049alc, %eax 105 50 50
add $0x1, %eax 108 51 50
mov %eax, 0x8049alc 113 51 51
割り込み
save T2
restore T1 108 51 51
mov %eax, 0x8049alc 113 51 51
(引用元: p.309 "Operating Systems Three Easy Pieces")
コンテキストスイッチ時にレジスタは正しく保存・復元されます。
OSやCPUが壊れているわけではありません。
問題は、count = count + 1; が1命令ではなく、
「読み込み → 計算 → 書き戻し」という複数命令に分解されていることです。
この処理が途中で分断されると、別スレッドが同じ値を基に更新してしまい、
本来2回行われるはずの加算が1回分失われます。
これがデータ競合の本質です。
よく考えれば当たり前のことかもしれませんが、アセンブリレベルを辿ることにより、データ競合がどこで起こっているのか、腑に落とすことができます。
以上となります。
CS初学者であり断片的に理解をしている部分があるので、不足事項があることをご了承ください。
何かご指摘等あればお待ちしております。
参照図書:
-
"Operating Systems Three Easy Pieces" By Remzi H.Arpaci-Dusseau & Andrea C. Arpaci-Dusseau
※PDFで公開されています： -
コンピュータ・システム プログラマの視点から Randal Bryant/David O'Hallaron 著
-
オペレーティングシステム 改訂2版 野口健一郎/光来健一/品川髙廣 共著
参考動画: