コグノスケ

musl libcのpthread_barrier_wait()の実装 その2、LastとOthers

目次: C言語とlibc

前回の続きです。musl libc 1.2.4のpthread_barrier_wait()の実装と動作の概要です。バリアに到達したスレッドがNスレッド（N >= 2）あるとすると、大きく分けて3つの役割に分かれます。役割名は私が適当に付けました。正式な名前はあるのかな？

• Owner: 最初にバリアに突入してきたスレッド（1スレッド）
• Last: 最後にバリアに突入してきたスレッド（1スレッド）
• Others: OwnerでもLastでもないスレッド全て（0〜N-2スレッド、平たく言えば3スレッド以上のバリアのときだけ存在する）

いっぺんに説明すると意味不明なので、順番に説明します。今回はLastとOthersです。

LastとOthers（到達側）

自分がLastかどうか判定する条件はバリア変数の_b_instがNULL以外であり、インスタンスのカウントがバリア同期するスレッド数と一致（= 最後に到達した1スレッド）することです。Lastのやることはバリア変数（pthread_barrier_t）に設定されたインスタンスを消すことと、バリア同期を待っているOthersを起こすことです。

Lastがこの時点でb->_b_instをNULLにしていること、ローカル変数instを使っていてb->_b_instを使わないことには理由があって、次のバリア処理とのオーバーラップと関係しています。同時に説明するとややこしいので、次回ご説明しようと思います。

OwnerとLast以外は全部Othersスレッドとなります。OthersのやることはLastが来るまで待つことです。

LastとOthersの到達側に関連するコードは下記のとおりです。

// musl/src/thread/pthread_barrier_wait.c

int pthread_barrier_wait(pthread_barrier_t *b)
{
	int limit = b->_b_limit;
	struct instance *inst;

	/* Trivial case: count was set at 1 */
	if (!limit) return PTHREAD_BARRIER_SERIAL_THREAD;

	/* Process-shared barriers require a separate, inefficient wait */
	if (limit < 0) return pshared_barrier_wait(b);

	/* Otherwise we need a lock on the barrier object */
	while (a_swap(&b->_b_lock, 1))
		__wait(&b->_b_lock, &b->_b_waiters, 1, 1);
	inst = b->_b_inst;

	/* First thread to enter the barrier becomes the "instance owner" */
	if (!inst) {
		//★★Ownerのスレッドの処理は省略（その1をご覧ください）★★
	}

	/* Last thread to enter the barrier wakes all non-instance-owners */
	if (++inst->count == limit) {
		//★★Lastのスレッドはこちら★★
		b->_b_inst = 0;
		a_store(&b->_b_lock, 0);
		if (b->_b_waiters) __wake(&b->_b_lock, 1, 1);
		a_store(&inst->last, 1);
		if (inst->waiters)
			__wake(&inst->last, -1, 1);
	} else {
		//★★Othersのスレッドはこちら★★
		a_store(&b->_b_lock, 0);
		if (b->_b_waiters) __wake(&b->_b_lock, 1, 1);
		__wait(&inst->last, &inst->waiters, 0, 1);
	}

細かい部分は省いてシーケンスの例を1つだけ示せば下記のようになります。

pthread_barrier_wait()のLastとOthersの到達側シーケンスの一例

見たままなので解説することがないですね。全員でインスタンスのカウントを+1して、最後のスレッドLastだけが特殊な処理を行います。

LastとOthers（脱出側）

脱出側のやることは単純ですが役割分担が少しややこしいです。到達側と同様にLastとOthersに役割が分かれますが、到達側のLast = 脱出側のLastとは限らないからです。

脱出時のLastになる条件はインスタンスのカウント値が1であることです。到達時にLastであったかOthersであったかは無関係です。脱出時のLastのやることは、インスタンスのfinishedを+1して待機中のOwnerスレッドを再開させることです。

脱出時のOthersになる条件はLastではない、インスタンスのカウント値が1以外であることです。

LastとOthersの脱出側に関連するコードは下記のとおりです。

// musl/src/thread/pthread_barrier_wait.c

int pthread_barrier_wait(pthread_barrier_t *b)
{
	int limit = b->_b_limit;
	struct instance *inst;

	//★★略★★

	/* Last thread to exit the barrier wakes the instance owner */
	if (a_fetch_add(&inst->count,-1)==1 && a_fetch_add(&inst->finished,1))
		__wake(&inst->finished, 1, 1);

	return 0;
}

細かい部分は省いてシーケンスの例を1つだけ示せば下記のようになります。

pthread_barrier_wait()のLastとOthersの脱出側シーケンスの一例

到達側のLastスレッドの処理では待機していたOthersスレッド達を全員再開させ、Lastも処理を再開します。するとLast + Othersスレッド全てがいっぺんに脱出側の処理を開始します。先ほど説明したとおり、どのスレッドが脱出側のLastになるかは運次第です。

実装の特徴はアトミックアクセスですかね。a_fetch_add(x, -1)はポインタxの指す先をアトミックに-1して、返り値でxの以前の値を返す関数です……といわれてもわかりにくいですよね。4スレッド（Owner, Others1, Others2, Last）の場合を書きましょうか。Ownerスレッドはカウント値を+1しないので、脱出処理開始時のカウント値は4 - 1 = 3です。

ちなみにアトミックアクセス以外の方法（if文とカウント値の変更など）では正常に動作しません。判定と値変更の間に他のスレッドが処理を行う可能性があるからです。

続きはまた今度。