Develop and Download Open Source Software

1.7　事象の待ち合わせ

図1-11　入出力の待ち合わせ

　Linuxカーネル上で動作するプロセスの状態は、大きく分けて2つあります。1つは実行可能状態で、もう1つは待機状態（休止状態）です。実行可能状態のプロセスはスケジューリングの対象となり、プロセススケジューラは順番に実行権を与えていきます。待機状態のプロセスは、何らかの事象を待ち合わせている状態であり、ある条件が整うまでそれ以上の処理を継続できません。このようなプロセスは、スケジューリングの対象にはなりません。たとえば、ファイルのread処理を行っているプロセスは、ディスクへの入出力要求後、その入出力が完了するまで動作できません（図1-11）。実際、Linuxカーネル上で動作しているプロセスの大部分は、この待機状態にあります。

　待機状態のプロセスには2種類あります。1つはシグナルを受け付ける待機状態で、もう1つはシグナルを受け付けない待機状態です。前者はソケットや端末などでの事象発生を待ち合わせるときに利用します。目的の事象が発生するか、またはシグナルを受け取ると、待機状態は解除され、実行待ち状態に遷移します。後者はシグナルを受けても、シグナルを保留状態にしたまま待機状態を続けます。（「第8章シグナル処理」参照）

　Linuxカーネルはこれらの状態を区別できるように、task_struct構造体のstateメンバーに表1-2の状態を表す値を設定します。プロセスの状態遷移は図1-12のようになります。

図1-12　プロセス状態遷移

表1-2　プロセスの状態

1.7.1　待機処理

　待機の対象となる可能性のあるカーネルオブジェクト（ファイルや、実ページ、端末など）は、それぞれWAITキュー（wait_queue_head_t型のリストヘッド）を用意しています。待機状態に遷移したプロセスは、ある事象の待ち合わせ用に用意されているWAITキューに登録されます。Linuxカーネル内には、さまざまなWAITキューが存在します。たとえば、ある端末の入力待ちのWAITキュー、ページキャッシュ上のページへの入出力完了を待ち合わせるためのWAITキュー、子プロセスの終了を待ち合わせるためのWAITキューなどがあります。

図1-13　WAITキュー

　待機状態のプロセスは、図1-13のような形式でWAITキューに登録されます。WAITキューに直接task_struct構造体を登録することはせずに、wait_queue_t型のデータ構造を介して間接的に登録します。

　実行中プロセスを待機状態に遷移させる関数は、実行中プロセスを待機状態にするsleep_on()関数（リスト1-5）と、実行中プロセスをシグナル受信可能な待機状態にするinterruptible_sleep_on()関数です。これらの関数は、プロセス状態をそれぞれTASK_UNINTERRUPTIBLE、TASK_INTERRUPTIBLEに変更し（<52>）、スタック上に確保したwait構造体（<51>）を使って、目的の事象を待ち合わせるためのWAITキューに登録します（<53>）。そのあと、プロセススケジューラを呼び出し、実行権を放棄します（<54>）。

リスト1-5　sleep_on関数

void sleep_on(wait_queue_head_t *q)
{
	unsigned long flags;
	wait_queue_t wait;
	init_waitqueue_entry(&wait, current); ――<51>
	current->state = TASK_UNINTERRUPTIBLE; ――<52>
	spin_lock_irqsave(&q->lock,flags);
	__add_wait_queue(q, &wait); ――<53>
	spin_unlock(&q->lock);
	schedule(); ――<54>
	spin_lock_irq(&q->lock);
	__remove_wait_queue(q, &wait); ――<55>
	spin_unlock_irqrestore(&q->lock, flags);
}

1.7.2　起床処理

　待機状態プロセスを起床させる関数として、wake_up関数群があります。wake_up関数群は、プロセスをRUNキューに登録することと、プロセス状態をTASK_RUNNINGに変更することを行います。もし起床させたプロセスのほうが、現在実行中のプロセスより実行優先度が高かった場合、プロセススケジューラに対してプリエンプト要求も送ります。wake_up関数群には、表1-3のように微妙に動作が異なるさまざまなものがあります。

表1-3　wake_up関数群

　WAITキューからプロセスを外すのは、実は起床したプロセス自身です（<55>）。通常wake_up処理側ではWAITキューの操作は行いません（WAITキュー操作まで行うwake_up処理も存在はします）。そのため、起床させられたプロセスは実行権を得るまでは、RUNキューとWAITキューの両方に登録された状態になります（図1-14）。

図1-14　起床直後のプロセス

　図1-12の状態遷移図を見るとよく分かりますが、待機状態から直接実行権を得て実行状態になることはできず、必ず実行待ち状態を経由して、RUNキュー上で実行権が割り当てられるのを待ちます。

　実際に起床処理のコードを見てみましょう。wake_up関数の先で呼び出されるプロセス1つだけを起床させるtry_to_wake_up関数をのぞいてみることにします（リスト1-6）。

リスト1-6　try_to_wake_up関数

static int try_to_wake_up(task_t *p, unsigned int state, int sync)
{
	int cpu, this_cpu, success = 0;
	unsigned long flags;
	long old_state;
	runqueue_t *rq;
	unsigned long load, this_load;
	struct sched_domain *sd, *this_sd = NULL;
	int new_cpu;

	rq = task_rq_lock(p, &flags); ――<60>

	old_state = p->state;
	if (!(old_state & state))
		goto out;

	if (p->array)
		goto out_running;

	cpu = task_cpu(p);
	this_cpu = smp_processor_id();

	if (unlikely(task_running(rq, p)))
		goto out_activate;

	new_cpu = cpu;

	schedstat_inc(rq, ttwu_cnt);
	if (cpu == this_cpu) {
		schedstat_inc(rq, ttwu_local);
		goto out_set_cpu;
	}

	for_each_domain(this_cpu, sd) {
		if (cpu_isset(cpu, sd->span)) {
			schedstat_inc(sd, ttwu_wake_remote);
			this_sd = sd;
			break;
		}
	}

	if (unlikely(!cpu_isset(this_cpu, p->cpus_allowed)))
		goto out_set_cpu;

	if (this_sd) {
		int idx = this_sd->wake_idx;
		unsigned int imbalance;

		imbalance = 100 + (this_sd->imbalance_pct - 100) / 2;

		load = source_load(cpu, idx);
		this_load = target_load(this_cpu, idx);

		new_cpu = this_cpu;

		if (this_sd->flags & SD_WAKE_AFFINE) {
			unsigned long tl = this_load;
			if (sync)
				tl -= SCHED_LOAD_SCALE;

			if ((tl <= load &&
					 tl + target_load(cpu, idx) <= SCHED_LOAD_SCALE) ||
					100*(tl + SCHED_LOAD_SCALE) <= imbalance*load) {
				schedstat_inc(this_sd, ttwu_move_affine);
				goto out_set_cpu;
			}
		}

		if (this_sd->flags & SD_WAKE_BALANCE) {
			if (imbalance*this_load <= 100*load) {
				schedstat_inc(this_sd, ttwu_move_balance);
				goto out_set_cpu;
			}
		}
	}
	new_cpu = cpu;
out_set_cpu:
	new_cpu = wake_idle(new_cpu, p);
	if (new_cpu != cpu) {
		set_task_cpu(p, new_cpu); ――<61>
		task_rq_unlock(rq, &flags);
		rq = task_rq_lock(p, &flags);
		old_state = p->state;
		if (!(old_state & state))
			goto out;
		if (p->array)
			goto out_running;

		this_cpu = smp_processor_id();
		cpu = task_cpu(p);
	}

out_activate:
	if (old_state == TASK_UNINTERRUPTIBLE) {
		rq->nr_uninterruptible--;
		p->activated = -1; ――<62>
	}
	if (old_state & TASK_NONINTERACTIVE)
		__activate_task(p, rq);
	else
		activate_task(p, rq, cpu == this_cpu); ――<64>
	if (!sync || cpu != this_cpu) {
		if (TASK_PREEMPTS_CURR(p, rq)) ――<65>
			resched_task(rq->curr); ――<66>
	}
	success = 1;

out_running:
	p->state = TASK_RUNNING; ――<67>
out:
	task_rq_unlock(rq, &flags);

	return success;
}

static void activate_task(task_t *p, runqueue_t *rq, int local)
{
	unsigned long long now;

	now = sched_clock();
	if (!local) {
		runqueue_t *this_rq = this_rq();
		now = (now - this_rq->timestamp_last_tick)
			+ rq->timestamp_last_tick;
	}

	if (!rt_task(p))
		p->prio = recalc_task_prio(p, now); ――<70>

	if (!p->activated) {
		if (in_interrupt())
			p->activated = 2; ――<71>
		else {
			p->activated = 1; ――<72>
		}
	}
	p->timestamp = now;

	__activate_task(p, rq); ――<73>
}

　まず、これから起床するプロセスが属するRUNキューを選択し、ロックします（<60>）。プロセスはいずれかのRUNキュー（つまりCPU）に結び付けられており、前回動作した同じCPU上で実行されるようにします。

　次に起床するプロセスをRUNキューに登録します。プリエンプションを発生させない指定の場合は、__activate_task関数で単にRUNキューにつなぐだけです（<63>）。通常の場合は、activate_task関数を呼び出し（<64>）、実行優先度の再計算を行い（<70>）、RUNキューにつなぎます（<73>）。長く待機状態であったプロセスのほうが、より高い実行優先度を得られます。現在実行権を握っているカレントプロセスより実行優先度が高くなるようだと（<65>）、プロセススケジューラに対し、再スケジューリング要求（プリエンプト要求）を出します（<66>）。ほかのCPUのプロセススケジューラに対して要求する場合は、プロセッサ間割り込みを利用します。

　プロセスをRUNキューにつなぎ終わったら、プロセスを実行可能状態に遷移させます（<67>）。

　また、これらの処理の中で、task_struct構造体のactivatedメンバーに値を設定しています。activatedメンバーには表1-4のような意味があります。activatedメンバーの値はプロセススケジューラ（schedule関数）が、スケジューリングする際の参考値にし、この値が大きいほど、優先的にスケジューリングしようとします。

表1-4　activatedメンバーの値とその意味

　ところでLinuxカーネル内のコードでは、プロセスを待機状態に遷移させるとき、sleep_on関数やsleep_on_interruptible関数を利用せず、その関数と同等のこと（WAITキュー操作とプロセススケジューラの呼び出し）を直接行っている個所があちこちにあります。これはなぜでしょうか？　実は微妙なタイミングが関係しています。先ほども述べたように、待機状態への遷移処理は、通常以下の手順を踏みます。

　しかし、1と2の間で事象が起きてしまう可能性のある場合、運が悪いとこのプロセスは永久に起床させられることがなくなります。そのため、標準のsleep_on関数を利用する代わりに、次のような順序で処理を行います。

　この手順によって、目的の事象が成立しているか調べた直後に事象が発生しても、そのプロセス自身はすでにWAITキューに登録されているため、その事象発生により、実行可能状態に戻されることになります。プロセススケジューラを呼び出したとき、自プロセス自身も実行対象の候補となります。

　事象の成立条件が単純なときは、wait_event/wait_event_interruptibleマクロ関数を利用しても、上記処理を簡単に記述できます。

図1-15　複数の事象待ち

　ところで、もう1つ実装上の疑問点を持たれた方もおられると思います。プロセスが待機状態になったとき、そのプロセス用のtask_struct構造体をWAITキューに直接登録しないのはなぜなのでしょうか？　実はこの構造には面白い特徴があり、プロセスを同時に複数のWAITキューに登録できます。複数の事象を同時に待ち合わせ、いずれかの事象が成立したら起床できます（図1-15）。この仕組みはselectシステムコールやpollシステムコールの実現に利用しています。

1.7.3　そのほかの待機/起床処理関数

　待機/起床を行う関数の一種として、completionという仕組みも用意しています（表1-5）。この仕組みを利用すると、事象の発生回数とプロセスの起床回数とをそろえることができます。プロセスの待機処理前に事象が発生してしまっても、期待どおりに動作する作りになっています。

表1-5　completion

1.7.4　子プロセスのスケジューリング

　forkシステムコールによって子プロセスが生成されたときは、この子プロセスを実行状態としてスケジューリング対象に加えます（wake_up_forked_process関数）（「第7章プロセス管理」参照）。子プロセスの実行優先度は親プロセスから引き継ぎ*2、親プロセスと同じRUNキューの親プロセスの前に挿入し、プリエンプト要求を発生させます（set_need_resched関数）。これによって子プロセスは親プロセスより、少しだけ先に動作することになります。ほとんどの子プロセスはすぐにexecシステムコールを発行するため、この順序で動作させたほうが、プロセス空間のコピーオンライト処理（「第13章プロセス空間の管理」参照）の発生を抑制できるというメリットがあるためです。

　また子プロセスを生成したとき、親プロセスは実行割り当て時間の半分を子プロセスに譲るようになっています。この仕組みによって、特定のプロセスから大量にプロセスが生成された場合でも、そのことによるほかプロセスへ与える影響を最小限に抑え、スケジューリングの公平性を保つことができます。

1. *1パイプ処理で利用。パイプへの書き込みや読み出しにより、通信相手プロセスが実行可能状態になっても、現在の処理が終わるまで実行権を明け渡さない。パイプでつながったプロセス群は全体で1つの処理であるため、そのプロセス間でプリエンプトしてもオーバーヘッドが増えるだけであるため。
2. *2親子ともに変動優先度は低めになるようにします。子プロセスがどんどん生成されたとき、その親子プロセスばかりを実行対象として選択してしまわないようにするためです。