Linux Kernel Sched. 2.4の復習

Linux 2.6 Schedulerの挙動の研究
Brought to you by:
キムデウン
澤井省吾
弘中健
Linux Kernel Sched. 2.4の復習



各スレッド(プロセス)は定めされた時間間隔
(“counter”)だけCPUを使ってよい。
10ms毎にtimer tickが実行され、現在走ってい
るプロセスはcounter- -される。
counter→0になったプロセスはもう走れない。
Linux Kernel Sched. 2.4の復習

各”epoch”が始まる前に各プロセスのcounter
が再計算される。
–
–
–
計算にはそのプロセスの「対話性値」(nice value)が
考慮される。
勿論、前epochで使い切れなかったcounterも考慮さ
れる。
new_counter= old_counter/2+goodness(nice)
Linux Kernel Sched. 2.4の復習

Schedule()によって次に走るべきプロセスが選
択される。
–
–

実行可能なタスクの内、最大のcounterを持つものが
選択され、実行される。
Schedule()はtimer tickで呼ばれるか、もしくは各プロ
セスがsched_yield()を使って呼ぶ。
非常に単純なアルゴリズムで宜しかった！！
が。。。
Linux Kernel Sched. 2.4の復習

欠点:O(n)のスケジュラー
–
–
–

Epoch毎に全てのプロセスのcounterを再計算:O(n)
最大のcounter値を持つプロセスを見つけ、実
行:O(n)
プロセスの数が多くなるとスケジュラーのせいで効率
が大幅に落ちる。
対話性の見積もりが雑。。。
–
counterが大きいからと言って対話的プロセスではな
い
Linux Kernel Sched. 2.6での改善

O(1)スケジュラー
–

スケジュラーの処理時間はプロセスの数に無関係な
一定時間しか掛からない。
「対話性」の見積もりヒューリスティックスを改善
し、対話的プロセス優先をより正確に実現
対話的プロセスとは？




“I/O-Bound”なプロセス
普段はスリープしていてCPUはあまり使わない
が、要求に対して直ぐ走ることが求められるプロ
セス。
「寝て。。。ちょっと走って、寝て。。。」
⇔”CPU-Bound”なプロセス
–
殆ど寝ずにCPUをがめようとするプロセス
2.6 Schedulerの構成

Runqueue
–

1つのCPUに付き1つ
Priority Array
–
1つのrunqueueに対して2つ

Active Array, Expired Array
Runqueueとは？


CPUの特別スレッド(idle thread, mitigation thread)の
管理
二つのpriority array(へのpointer)の管理
–
–
–
1つのpriority arrayに属するプロセスを実行して行く←Active
Array
それぞれのプロセスに割り当てられた時間(“Timeslice”)を使い
切ったプロセスはもう一方のpriority arrayに移される←Expired
Array
Active Arrayが空っぽになったらexpired/active arrayへのポイ
ンタを交換して新しいarrayのプロセスを実行
Priority Arrayとは？

連結リストの配列
–
–

配列長のビットマップ
–

長さはプロセスの優先度の数(具体的には140個)
一つの配列の要素、つまり一つの連結リストに属するプロセス
はすべて同じ優先度
ある配列要素にプロセスが存在すれば1が立つ、さもなければ0
O(1)アルゴリズムを可能にしているデータ構造
–
–
定数時間で一番優先度(priority)が高いプロセスを検索すること
が出来る。
定数時間で同じ優先度のプロセス同士のround-robin
一連の流れ




Active Arrayの中で最優先priority levelをビットマップで
見つける(一番indexが小さい要素の連結リスト)。
その連結リストのプロセスを順に実行する
Timesliceが使い終わったプロセスは新しいtimesliceが
与えられ、新しい優先度が計算され、Expired Arrayの
該当する優先度の要素のリストに移される。
Active Arrayにプロセスがなくなったら(全てExpired
Arrayに移動した)Active Array⇔Expired Array
本当にO(1)アルゴリズム？



最も高いpriority levelを持つプロセスの検索=
ビットマップ長の検索:O(1)
一つのプロセスをActive→ Expired Arrayに移
す:O(1)
Active, Expired Arrayの交換:O(1)
グラフィックな理解
Active Array
Runqueue
Expired Array
1
0
0
1
1
0
0
1
1
0
0
1
0
0
1
1
0
0
0
0
0
0
1
優先度の計算

理念
–

Static Priority
–
–

対話的プロセスの優先度は高く、非対話的プロセス
の優先度は低く
初期値は0
System call: nice(int prio)で変更か(-20~19)
Dynamic Priority(priority array上の優先度)
–
Static Priority-Bonus
Dynamic Priorityの計算(1)

ヒューリスティック
–

Sleep timeが長いほど、run timeが短いほど大きい
Bonus
Sleep_avg(recalc_task_prio()で計算)
–
–
–
Sleepから復帰:sleep_avg+=sleep_time
CPUを手放す時:sleep_avg-=run_time
|sleep_avg|<=MAX_SLEEP_AVGとしてある
Dynamic Priorityの計算(2)

effective_prio(p):dynamic priorityの計算
–
–
–

recalc_task_prio(p):
–

Bonus=MAX_BONUS*sleep_avg/MAX_SLEEP_AVGMAX_BONUS/2
prio=static_prio-bonus
初期値ではbonus=[-5,5]
sleep_avgを再計算し、effective_prio(p)を実行
良く寝るプロセスほど優先的に走り、CPUをがめようとす
るプロセスほど後回しになる。
TimeSliceの計算


一つのプロセスがActive→ Expiredになるまで
に使っていいCPUの時間
Static Priorityによって決まる。
–
Timeslice=MIN_TIME_SLICE+
(MAX_TIMESLICE+MIN_TIME_SLICE)
*(MAX_PRIO-1-static_prio)/(MAX_PRIO-1)
対話的なプロセスの応答をさらに改善

ある程度以上の「対話性」を持つプロセス
は”interactive”(対話的)とされる。
–
–
プロセスは普段はTimesliceを使い切るまでCPUを独
占できるが、TIME_GRANUALITYというさらに細か
い時間粒子で、同じpriorityの連結リスト内でround
robinでCPUを使う。
さらに、他のプロセスが長時間待たされていない限り、
(“starve”していない限り)timesliceを使い切っても、
Active Arrayに再び再挿入される！
Schedulerの主な担い手


scheduler_tick()
schedule()
scheduler_tick()




Timer 割り込みで1ms刻みで実行
現在走っているプロセスのtimeslice-現在走っているプロセスのtimeslice=0だったらそのプロ
セスを退避させ(expired arrayに、interactiveな場合は
active arrayに再挿入)、TIF_TASK_NEED_SCHEDフ
ラッグを立て、schedule()が呼ばれるようにする。
InteractiveプロセスがTIME_GRANUALITY走ったら次
のプロセスに譲るように施す。
schedule()




寝るプロセスはrunqueueから外す。
Active Arrayの中から一番優先度の高いプロセ
スを見つけ、CPUを今まで使っていたプロセスと
context switchを行う。(CPU、メモリの交換)
主にscheduler_tick()によって呼ばれる。
プロセスが明示的にschedule()を呼んで、CPU
を返上することも出来る。
scheduler_tick()とschedule()の関連
scheduler_tick()とschedule()の関連


scheduler_tick()はリスケジュールが必要な時
(タスクがtimesliceを使い切った、interactiveプ
ロセスのRR)、フラッグを立ててschedule()が実
行されるようにする。
schedule()は次のプロセスを選び、CPU使用の
交代を行う。これをPreemptionと言う
–
必ずしもscheduler_tick()で呼ばれなくてもよい、プロ
セスが直接sched_yield(),schedule()を呼んでCPU
を返上することも出来る。
Preemption


現在走っているプロセスがschedule()によって
他プロセスにCPUを返上すること。
基本的にTIF_TASK_NEED_RESCHEDフラッ
グが立っている時
–
–
–
Scheduler_tick()が呼んだ時
新しいプロセスがsleepから起きた時
System callが終了した時
Kernel Preemption



Kernel 2.6で新しく登場
System Callなど、kernel modeで走っている時でもリス
ケジュールフラッグが立っていればkernelは他のプロセ
スにCPUを返上する。
Critical sectionを処理している時は？
–
–
どうしてもpreemptされたくない時はlockを取得する。
preempt_count



Lock取得preempt_count++
Lock開放preempt_count-preempt_count=0の時のみkernelはpreempt可能
Sleepする


Runqueueから外れてCPUを一切使わない状態
に入る。
Interruptible/uninterruptible
–
–
Interruptibleだとsignalで起こすことが出来る。
Uninterruptibleだとsignalには自分で起きるまで応答
しない。
Sleepするための手続き

Waitqueueを作る
–


あるイベント・条件が満たされるまでプロセスたちが
待機している場所(runqueueの外)
add_wait_queue()
schedule()を呼んでCPUを返上する。
Wake Up!!



Wait queueのすべてのプロセスに対して
try_to_wake_up()が呼ばれる。
activate_task()で寝た分priorityがブーストされ、起こさ
れるタスクがactive arrayによって追加される。
もし現在走っているプロセスよりも起きたプロセスの
priorityが高かったらTIF_TASK_NEED_RESCHEDフ
ラッグを立てて、schedule()を呼ぶ。
–
–
さもないとそのタスクがCPUを使えるチャンスは次にschedule()
が呼ばれる以降。
恐らくscheduler_tick()が呼ばれないといけないから一回寝たら
大体の場合1ms以上走れないハメになる。
Real Time Processes


スケジュラーも素晴らしいけど、待てない
deadlineがある仕事もある！
Soft Real-Time Scheduling
–
きっちりtime deadlineは守れないけど、努力する
RT schedulingの実装

Priority:終わるまでCPUを使える。
–
140のpriority levelの内トップ0~99を占有


通常プロセスは100-139のレベルで、その枠を出れない
RT policy
–
–
RT FIFO
RT RR
Priority Array上の並び方構造
0
RT Prioirty
99
100(-20)
User Priority
139(19)
RT_FIFO

Real Time First In First Out
–
–
–
–

Timesliceなし！
プロセスが完了するまでCPUを独占する。
より優先度が高いRT_FIFOプロセスが登場するとそ
れにCPUを返上する。
基本的にscheduler_tick()が目をつぶっている。
「常識的設計」が求められる ;-)
RT_RR

Real Time Round Robin
–
–
–
–
完了するまで走ることには変わりない
同じpriority内で決まったtimeslice毎にround robinで
走る。
Priorityは固定される。(ペナルティを食らわない)
基本的にtimeslice=0になったらまた
scheduler_tick()が新しいtimesliceを与えて、active
arrayに戻す。
実験
お待たせしました。。。
System Calls







#include <unistd.h>,<sched.h>
**int nice(int inc);
int sched_yield(void);
**int sched_setparam(pid_t pid, const struct
sched_param *param);
**int sched_setscheduler(pid_t pid, int policy, const
struct sched_param *param);
int sched_rr_get_interval(pid_t pid, struct timespec
*interval);
**suでないと設定出来ない値もある
Bibliography:



Aas, Josh. “Understanding the Linux 2.6.8.1 CPU Scheduler.” Feb. 17,
2005
– http://josh.trancesoftware.com/linux/
Fischer, Gordon.,Rodriguez, Claudia.,Salzberg, Claudia., Smolski,
Steven., “Linux Scheduling and Kernel Synchronization.”
Prentice Hall PTR. Nov. 11, 2005
– http://www.phptr.com/articles/article.asp?p=414983&seqNum=1&rl
=1
Love, Robert. “The Linux Process Scheduler.” Nov. 13, 2003
– http://www.samspublishing.com/articles/article.asp?p=101760&seq
Num=3&rl=1
Special Thanks

田浦先生
–
–
–
質問に根気強く答えてくれるだけでなく、積極的にイ
ンプットを下さりました。
また、martenサーバーを実験用に使わせて下さいま
した。
先生の助けがなくてはこの課題達成は不可能で、個
の場を借りて感謝をしたいと思います。

Download Report