Rev.9を表示中。最新版はこちら。

1. 概要

RunQueueにはRUNNING状態のプロセスがつながれる。スケジューラがプロセスの実行を管理するのに使用する。

2. RunQueueの構造

RunQueueの構造を図1に示す。

2.1 CPU毎のRunQueue

RunQueueはCPU毎に存在する。Running状態のプロセスはシステム内のいずれかのCPUに割り当てられ、対応するCPUのRunQueue(struct runqueue)に入れられる。

2.2 struct runqueue

struct runqueueがRunQueueの管理構造体。struct runqueueはActive,Expiredの2種類のリストを持つ。struct runqueue内のprio_array_t arrays[2]がリストの管理テーブルの実体で、active,expiredポインタがarray[0],[1]をそれぞれ指している。

フィールド	意味
nr_running	RUNNINGプロセス数(active,expireにつながれている総プロセス数)
active	CPU時間が残っているRUNNINGプロセスが保持される。優先度毎にリストがある。
expired	CPU時間を使い切ったRUNNINGプロセスが保持される。優先度毎にリストがある。
expired_timestamp	expireに初めてプロセスを移動した時間。 active<->expireの入れ換えをしたり、IDLE状態になるとクリアされる。

2.3 Active,Expiredリスト

RunQueueにはActiveリストとExpireリストがある(上記の優先度毎のリストはActive,Expireリストの中にそれぞれ収容されている)。

Activeリストは、まだCPU時間が残っているプロセスがチェーンされ、ExpireリストにはCPU時間を使い切ったプロセスがチェーンされる。スケジューラはActiveリスト内のプロセス間でスケジューリングを行う。

CPU時間を使い切ったプロセスはExpireリストに移動されスケジューリングの対象外となり、ここで、全RUNNINGプロセスがCPU時間を使い切るのを待つ。

Activeリストの全プロセスがCPU時間を使いきってActiveリストが空になると、Active,Expireリストを入れ換えて、新たにCPU時間が割り当てられ(*1)、スケジューリングが再開される。

(*1) 正確にはExpireに移動した時に、次のCPU時間が設定されている。

Linux2.2 ではActive,Expireリストはなく、リストが一つだったので、スケジューリングの際、CPU時間を使い切ったRUNNINGプロセスを毎回読み 飛ばしていた。CPU時間が残っているプロセスと使いきったプロセスの区別を軽くするために用意された。

2.4 struct prio_array

図2 struct prio_array

さらに、RunQueueはプロセスの優先度毎(0-139)にリストを持ち、プロセスは自分の 動的優先度に該当するキューにつながれる。優先度毎にリストを持つことで最高優先度のプロセスを高速に取りだせる。

関連ページ

スケジューラ