Linux Kernel(2.6)の実装に関するメモ書き
リンク
最近更新したページ
検索

RunQueue の差分
Rev.9→最新版  追加箇所 削除箇所


1. 概要

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

2. RunQueueの構造

RunQueueの構造を図1に示す。


図1 RunQueueの構造

2.1 CPU毎のRunQueue

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

2.2 struct runqueue

struct runqueueがRunQueueの管理構造体struct runqueueActive,Expired2種類リストstruct runqueueprio_array_t arrays[2]リスト管理テーブル実体active,expiredポインタarray[0],[1]をそれぞれしている

struct runqueueはActive,Expiredの2種類のリストを持ち、ここにRUNNINGプロセスがつながれる。Active,Expiredリストはactive,expiredポインタによって指される。struct runqueue内のprio_array_t arrays[2]が2本のリストの管理テーブルの実体で、active,expiredポインタはそれぞれarray[0],[1]のどちらかを指すようになっている。Active,Expiredリストは定期的に入れ替わるが、この時はarray[0],[1]内のプロセスを移動させるのではなく、active,expiredのポイント先を入れ換えるだけよいようになっている。


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

2.3 Active,Expiredリスト

RunQueue ActiveリストQuantumでまだCPU時間っているプロセスチェーンされExpiredリストにはCPU時間使ったプロセスチェーンされるスケジューラ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時間っているプロセス使いきったプロセス区別くするために用意された

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

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

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

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

2.4 struct prio_array

Active,Expiredリストの管理構造体であるstruct prio_arrayの構造を図2に示す。



図2 struct prio_array

さらにstruct prio_array単純1リストではなくプロセス優先度毎(0-139)リストRunQueueRUNNING状態プロセス(struct task_struct)自分動的優先度該当するリストにつながれる優先度毎リストつことで最高優先度プロセス優先度毎(0-139)高速リストプロセス自分 動的優先度該当するキューにつながれる優先度毎リストつことで最高優先度プロセス高速取りだせる。

nr_activeにはPrio0〜139のリストにチェーンされているプロセスの総数が格納されている。

bitmapはPrio0〜139のリストの使用/未使用ビットマップでリストにプロセスがチェーンされている場合はビットが立つようになっており、最高優先度のプロセスを高速に取り出すことができる。

3. 関連関数

enqueue_task(struct task_struct *p, prio_array_t *array)

プロセス(p)をarrayで示すリストに入れる。

dequeue_task(struct task_struct *p, prio_array_t *array)

プロセス(p)をarrayで示すリストから取り出す。

関連ページ

スケジューラ