srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

pthreadによるスレッド間でのカウンタの共有

まず以下のプログラムのように、変数xを複数のスレッドが共有し、それぞれのスレッドがCOUNT_NUM回、変数xをインクリメントする処理を行う。 あるスレッドが(*(int *)i) += 1を実行する間に、他のスレッドも同じ部分を実行すると、競合が起こり、最終的に変数xの値が期待した値と異なる。 以下のプログラムを実行すると、期待した値と異なる結果が出力される。

なぜ競合が起きるのかだが、(*(int *)i) += 1ソースコードレベルでは1行で表されているコードだが、機械語レベルで考えると、メモリからのロード、値の加算、メモリへのストアの3命令に分割されて実行される。この3命令を一つのスレッドが実行している間に、ほかのスレッドの3命令の実行が行わると、正常なインクリメントができなくなってしまう。  

実験的に、COUNT_NUM1にすると、最終的なxの値は期待した値と同じ値になる。理論的には、TH_NUM個のスレッドがそれぞれ変数xを一回ずつインクリメントとし、クロスオーバーやオーバーラップにより、最終的な値は1からTH_NUMの値すべてになる可能性があると思うのだが、なかなか'x'の値が'TH_NUM'以外にならなかった。これはスレッド1のpthread_createをして、次のスレッド2のpthread_createを行いスレッド2が(*(int *)i) += 1を実行するまでの間に、すでにスレッド1の (*(int *)i) += 1 が完全に終了しているからだろうか??

// gcc -std=c11 -pthread no_mutex.c 

#include <stdio.h>
#include <pthread.h>

#define TH_NUM 10
#define COUNT_NUM 10000

void *add(void *i) {
    for (int k = 0; k < COUNT_NUM; k++) 
        (*(int *)i) += 1; // count up
    return NULL;
}

int main() {
    int x = 0; // shared value
    pthread_t th[TH_NUM];

    for (int n = 0; n < TH_NUM; n++)
        pthread_create(&th[n], NULL, add, &x);

    for (int n = 0; n < TH_NUM; n++)
        pthread_join(th[n], NULL);

    printf("actual: %d, expected: %d\n", x, COUNT_NUM * TH_NUM);

    return 0;
}

次に、必ず期待した値になるように、mutexを使って、複数のスレッドが同時にクリティカルセクション(ここでは(*(int *)i) += 1の命令の実行開始から終了まで)へ入ることを防ぐようにコードを変更した。それが以下のようになる。

// gcc -std=c11 -pthread mutex.c 

#include <stdio.h>
#include <stdatomic.h>
#include <pthread.h>

#define TH_NUM 10
#define COUNT_NUM 10000

struct params {
    int *i;
    pthread_mutex_t *mut;
};

void *add(void *arg) {
    struct params* prm = (struct params *)arg;
    for (int k = 0; k < COUNT_NUM; k++) {
        pthread_mutex_lock(prm->mut);
        (*(int *)(prm->i)) += 1; // count up
        pthread_mutex_unlock(prm->mut);
    }
    return NULL;
}

int main() {
    int x = 0; // shared value
    pthread_t th[TH_NUM];
    pthread_mutex_t mut = PTHREAD_MUTEX_INITIALIZER;
    struct params prm = {&x, &mut};

    for (int n = 0; n < TH_NUM; n++)
        pthread_create(&th[n], NULL, add, &prm);

    for (int n = 0; n < TH_NUM; n++)
        pthread_join(th[n], NULL);

    printf("actual: %d, expected: %d\n", x, COUNT_NUM * TH_NUM);

    return 0;
}

参考

https://blog.bitmeister.jp/?p=4496