Namaran

Code daily. Without assist.

2026-10-09

rwlock.c

#include <threads.h>

struct rwlock { mtx_t m; cnd_t cv; int readers; bool writing, writer_waiting; };

void read_lock(struct rwlock *l) {
    mtx_lock(&l->m);
    while (l->writing || l->writer_waiting) cnd_wait(&l->cv, &l->m);
    l->readers++;
    mtx_unlock(&l->m);
}

void write_lock(struct rwlock *l) {
    mtx_lock(&l->m);
    l->writer_waiting = true;
    while (l->writing || l->readers > 0) cnd_wait(&l->cv, &l->m);
    l->writer_waiting = false;
    l->writing = true;
    mtx_unlock(&l->m);
}

read_lock と write_lock は、書き込みが待っている間は新しい読み取りを待たせ、書き込みを先に通すつもりの読み書きロックです。解除の関数は、カウンタとフラグを戻して cnd_broadcast で待っているスレッドを起こすだけなので省いています。読み取りスレッド4つが3ミリ秒の読み取りを休まず繰り返しているところへ書き込みスレッドを2つ同時に走らせ、500ミリ秒後に済んだ書き込みの数を出力します。手元で20回試すと、20回とも 1 で、2つ目の書き込みは読み取りスレッドを止めるまで入れませんでした。本来は、読み取りが続いていても2つとも済んで 2 になるはずです。

Answer

Wrong

struct rwlock { mtx_t m; cnd_t cv; int readers; bool writing, writer_waiting; };

// read_lock
while (l->writing || l->writer_waiting) cnd_wait(&l->cv, &l->m);

// write_lock
l->writer_waiting = true;
while (l->writing || l->readers > 0) cnd_wait(&l->cv, &l->m);
l->writer_waiting = false;
l->writing = true;

待っている書き込みを覚えているのは、bool の writer_waiting 1つだけです。書き込みが2つ同時に来ると、どちらも writer_waiting を true にして待ちに入り、新しい読み取りは止まります。読み取りが抜けきると1つ目の書き込みが入り、そこで writer_waiting を false に戻します。2つ目の書き込みはまだ while の中で待っているのに、フラグは待っている書き込みがないことを示しています。

1つ目の書き込みが終わって待っていたスレッドが一斉に起きたとき、読み取りが1つでも先に入ると、read_lock は writer_waiting が false なので後続の読み取りも次々に通します。読み取りスレッドが4つあれば、どれかが常に読んでいて readers は0に戻りません。2つ目の書き込みは readers > 0 で待ち続けるうえ、writer_waiting = true はループの前で1度しか実行しないので、フラグを立て直せません。こうして2つ目は、読み取りが止まるまで入れなくなります。

Right

struct rwlock { mtx_t m; cnd_t cv; int readers, waiting_writers; bool writing; };

// read_lock
while (l->writing || l->waiting_writers > 0) cnd_wait(&l->cv, &l->m);

// write_lock
l->waiting_writers++;
while (l->writing || l->readers > 0) cnd_wait(&l->cv, &l->m);
l->waiting_writers--;
l->writing = true;

待っている書き込みを int の waiting_writers で数えれば、書き込みはそれぞれ自分の分だけを足し引きします。1つ目の書き込みが入って1を引いても2つ目の分が残るので、read_lock は新しい読み取りを待たせ続けます。読み取りが抜けきったところで2つ目も入り、500ミリ秒のうちに2つとも済みます1。

  1. 書き込みを優先しすぎると、今度は書き込みが途切れなく来たときに読み取りが入れなくなります。POSIX の pthread_rwlock_rdlock は、書き込みが待っているときに読み取りを入れるかどうかを実装に任せていて、glibc は既定で読み取りを優先します。