Think Stitch
  最近の更新


ミューテックスと条件変数で作る rwlock

ミューテックスと条件変数を使って rwlock を作ってみます.これも pthread に専用の関数があるので,練習問題です.

0  リーダ・ライタ問題

rwlock というのはリーダ・ライタ問題用の排他制御機構です.リーダ・ライタ問題とは,共有データにアクセスするスレッドに2種類のスレッドを不整合が起こらないように制御する問題です. 1つはリーダで彼らはデータを読むだけです.ですから複数のリーダが同時にアクセスしても問題ありません.もう1つはライタで,データを読むだけでなく更新もします.共有データの一貫性を保つためには,誰もアクセスしていないときに1つのライタだけがアクセスするようにしなければなりません.

1  rwlock

このルールを守るために,リーダ用のロックとライタ用のロックを用意します.リーダは rdlock を呼び出してから共有データにアクセスし,終わったら rdunlock を呼び出します.ライタは同様にライタ用の関数 wrlock, wrunlock を使います. pthread では unlock が1つでリーダ・ライタ兼用ですが,ここでは分けて作ります.

2  rwlock のモデル

考え方はこうです.共有データにアクセスしているリーダ・ライタそれぞれの数を数えて,次に誰が入ることができるのか判断し,入れない場合は待たせます.誰かがアンロックをして状況が変わったら,待っているスレッドをすべて一度起こして,各自が条件を再チェックします.

pthread_cond_t cv = PTHREAD_COND_INITIALIZER;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
int8_t rcount;
int8_t wcount;

void rdlock(void)
{
    pthread_mutex_lock(&m);
    while (wcount > 0) {                // *A
        pthread_cond_wait(&cv, &m);
    }
    rcount++;
    pthread_mutex_unlock(&m);
}

void rdunlock(void)
{
    pthread_mutex_lock(&m);
    rcount--;
    pthread_cond_broadcast(&cv);
    pthread_mutex_unlock(&m);
}

void wrlock(void)
{
    pthread_mutex_lock(&m);
    while (wcount > 0 || rcount > 0) {  // *B
        pthread_cond_wait(&cv, &m);
    }
    wcount++;
    pthread_mutex_unlock(&m);
}

void wrunlock(void)
{
    pthread_mutex_lock(&m);
    wcount--;
    pthread_cond_broadcast(&cv);
    pthread_mutex_unlock(&m);
}

リーダがアクセスできるのはライタがいないときだけです(*A).一方,ライタがアクセスできるのは,他にリーダもライタもいないときだけです(*B).

3  安全性の検査

安全性の検査をしてみます.考え方はセマフォのときと同じで,ロック中に存在するリーダ・ライタの数をそれぞれ観測者の立場で数えます.それと同時に内部の整合性も検査しましょう.

内部の整合性についてはグローバル assert を使ってみました.

この2つをチェックします.

// @ASSERT(rcount == 0 || wcount == 0)
// @ASSERT(wcount == 0 || wcount == 1)

観測者の方の並行して,ロック中に存在するリーダ・ライタの数を数えます.こちらは当事者の立場で見て,グローバルではないふつうの assert にしてみました.

pthread_mutex_t mr = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mw = PTHREAD_MUTEX_INITIALIZER;
int8_t nr;
int8_t nw;

void *reader(void *arg)
{
    while (true) {
        rdlock();

        pthread_mutex_lock(&mr);
        nr++;
        pthread_mutex_unlock(&mr);

        assert(nw == 0);                // *A

        pthread_mutex_lock(&mr);
        nr--;
        pthread_mutex_unlock(&mr);

        rdunlock();
    }
    return NULL;
}

void *writer(void *arg)
{
    while (true) {
        wrlock();

        pthread_mutex_lock(&mw);
        nw++;
        pthread_mutex_unlock(&mw);

        assert(nw == 1);                // *B
        assert(nr == 0);                // *C

        pthread_mutex_lock(&mw);
        nw--;
        pthread_mutex_unlock(&mw);

        wrunlock();
    }
    return NULL;
}

検査を実行すると問題ないことがわかります.

4  リーダは同時アクセスできているか?

2個以上のリーダが同時にアクセスできているケースはほんとにあるんでしょうか?これを確認するには,否定をとって nr != 2 という条件を assert で調べればわかります. nr != 2 という条件に違反すれば nr == 2 である状態が存在するということになるからです.

検査してみるとたしかに違反があり,状態を見ると nr = 2 であることが確認できます.

------------------------
global vars:
    rcount = 2
    wcount = 0
    nr = 2
    nw = 0
mutex:
    m <unlocked>
    mr pthr[1]
    mw <unlocked>
thread:
0 main 5
    i = 1
1 pthr[0] 61
    t27 = 2
2 pthr[1] 57
------------------------

2017/10/10

© 2013-2017 PRINCIPIA Limited