4. Process Scheduling

4. Process Scheduling
eden
プロセススケジューラとは？
•  限りあるコンピュータのリソースをプロセス間
で分配するため、「どの」プロセスが「いつ」
「どれだけ」動作するか決めるカーネルサブシ
ステムマルチタスキング
•  シングルプロセッサ上では –  複数のプロセスが同時に動いていると見せかけ
る •  e.g. block/sleepしたプロセスを他と交代させるなど •  マルチプロセッサ上では –  実際に複数のプロセスが同時に動く •  一般的なOSでは、メモリ上には複数のプロセ
スが存在するが、実行されているのは1/プロ
セッサのみである Coopera:ve vs Preemp:ve
•  マルチタスキングの実現方法はcoopera:veと
preemp:veに大別される •  Preemp:ve –  スケジューラが強制力をもってプロセスの一時停止、
再開をコントロールできる •  preemp:on = 非自発的にプロセスを中断させること –  現代OSは大体全部これ(Linuxもこれ) •  Coopera:ve –  プロセスが自発的にCPUを明け渡すまで中断しない –  当然プロセスがhungすればOSもhung –  Mac OS 9やWindows 3.1はこれだった（らしい） Linuxスケジューラ史
•  Linuxは最初からpreemp:veスケジューラ •  初期〜2.4時代 –  詳しくは解説されていないが、非常にシンプルだったらしい –  当然スケールもしないしマルチプロセッサは考慮されていない –  特に気にしないでいいです •  O(1)時代 – 
– 
– 
– 
– 
プロセスを優先度別キューに入れて実行順を管理ある程度実行したプロセスはexpira:onキューに捨てるキューが掃けたら最初から繰り返す latency-‐sensi:veなアプリケーションの実行には向いていなかったあとで少しでてきますが、詳しくは各自調べてね！ •  CFS(Completely Fair Scheduler)←いまここ –  O(1)の弱点を克服するためにスクラッチで設計・実装 –  詳しくは後ほど注意
•  ここからは基本的にスケジューラと言ったら
preemp:ve process schedulerです I/O-‐Bound vs Processer-‐Bound
•  スケジューリングポリシーを考えるにあたって重要な概念 •  I/O-‐Bound Process –  多くの時間をI/O処理に費やすプロセス –  当然blockしている時間が圧倒的に長い –  e.g. テキストエディタ、GUIアプリケーションなど •  Processor-‐Bound Process –  多くの時間をコードの実行に費やすプロセス –  計算している時間が圧倒的に長い –  e.g. ssh-‐keygenとか •  これらは排他的性質ではない –  wordとか入力してなくても糞重くなることありますよねスケジューリングポリシー
•  スケジューラは同時に以下を達成することを目
標とする –  Low latency •  fast process response :me •  I/O-‐Boundなプロセスの応答性を上げること –  High throughput •  maximal system u:liza:on •  Processor-‐Boundなプロセスを速く動かすこと –  ただし、これらは典型的なトレードオフ –  基本的にはUNIX(Linux含む)はI/O-‐Boundを優先させ
る傾向あり
プロセス優先度
•  プロセスを「重要性」と「必要な計算時間」によって順位付
けする –  というスケジューリングポリシーの一形態 •  Linuxでは –  優先度の高いプロセスは低いプロセスよりも先に実行される –  優先度の高いプロセスは低いプロセスよりも長く実行される –  優先度を表すパラメータとしてniceと呼ばれる数値が使用され
る • 
• 
• 
• 
-‐ 20 から + 19の間でプロセス毎に設定可能デフォルトは0 意味は文字通りどれだけイケてるプロセスか、ということらしいちなみに数値が低いほうが優先度高いらしいです・・・タイムスライス
•  あるプロセスがpreemptされるまで実行され続け
る時間 –  長すぎるとシステムの応答性が悪くなる •  Processor-‐Boundなプロセスには長いタイムスライスが適し
ている –  短すぎるとコンテキストスイッチのコストが増える •  I/O-‐Boundなプロセスには短いタイムスライスが適している –  Linuxでは基本的にI/O-‐Boundを優先し、短いタイムス
ライスを採用 •  10msぐらいのオーダー CFS(Completely Fair Scheduler)
•  プロセスにはタイムスライスではなくプロセッ
サに占める割合を割り当てる –  タイムスライスとはなんだったのか。。 •  プロセスが実行される時間はプロセスがプロ
セッサに占める割合によって決まる –  e.g. O(1)スケジューラにおいては、優先度から絶
対的なタイムスライスが決定する一般的なUNIXスケジューラ
•  niceをタイムスライスに静的にマップする、これだけ –  e.g. 0 nice -‐> 100ms 1 nice -‐> 95ms •  シンプル！これでいいじゃん！ –  と思いきや •  niceを高くしすぎるとタイムスライスが短くなりすぎる –  結果context switchが膨大なコストに –  チューニングできるniceの幅が限られてしまう •  niceが0:1の場合と18:19の場合で恐ろしく挙動が変わる –  niceが1増えるごとに5msタイムスライスが減るとすると –  0nice:1nice = 100ms:95ms 18nice:19nice = 10ms:5ms •  タイムスライスの割合が20:19から2:1に・・ •  context switch激増 •  絶対的タイムスライスを保証するにはタイマーの精度が必要 –  だがカーネルタイマでは10ms – 1ms程度の精度しか提供されていない •  一時的なタイムスライスの融通が不可能 –  重量級ソフトの起動時だけタイムスライス倍プッシュみたいなことができない CFSについて考える前に
•  CFSが採用する、perfect mul:taskingという概念
について –  全てのプロセスは1/n(n = プロセス数)のプロセッサ時
間を享受する –  スケジューラはプロセッサ時間を無限に小さく分割し
てプロセスを実行できる •  つまりcontext switchのコストが0だったりprocess scheduling
そのもののコストが0だったりする世界 –  無限にプロセッサ時間を分割できるということは、任
意の時刻において全てのプロセスが同時に動いてい
るように見えるということ –  もちろん、こんなことは現実には不可能です CFSについて(1)
•  近似的perfect mul:tasking –  無限ではないが「できるだけ短い時間」中にプロセスが全て動
作するよう分割する •  この「できるだけ短い時間」はtarget latencyと呼ばれる •  つまり、target latency中に全てのプロセスは一巡する •  実行時間 –  1回あたりのプロセス実行時間（タイムスライス）は以下の式で
動的に計算される •  weight = 1.25 ^ (-‐nice) •  slice = target latency * (weight / total weight) –  これが”プロセッサ時間に占める割合を割り当てる”の所以 –  よくCFSにはタイムスライスの概念がないとか書いてありますが
あれは嘘です CFSについて(2)
•  実行順序 –  スケジューラが呼ばれたとき、その時点で一番積算実行
時間が少ないプロセスにコンテキストスイッチする •  もちろんいま実行しているプロセスの実行時間が一番少なければ
そのまま実行する •  これによりI/O-‐Boundなプロセスが優先して実行されることになる –  実行時間は、実際の実行時間ではなく、niceを掛けた値 •  この値は仮想実行時間(virtual run:me)と呼ばれている •  vrun:me = run:me * (1.25 ^ (-‐nice)) •  つまりCFSにおいてはniceはメトリックを決める際の係
数 CFSについて(3)
•  当然プロセスが増えれば1つのプロセスが実
行される時間もどんどん減っていく –  というわけで、CFSでは最低でも1msはタイムスラ
イス長を保証 –  つまり弱者プロセスのせいでtarget latencyを達成
できない場合もある –  全然Completely Fairじゃないですね •  ベーシックインカム的な？ CFSについて(4)
•  例えば、プロセスAとプロセスBがあり、 –  nice値 = A:B = 0:5 –  target latency = 20ms –  5niceにつき1/3のペナルティがかかる •  とすると –  0:5 = (1/(3 ^ 0)) : (1/(3 ^ 1)) = 15ms:5ms –  10:15 = (1/(3 ^ 2)) : (1/(3 ^ 3)) = 15ms:5ms •  niceを変えてもタイムスライスは変わらない！ –  その他いろいろメリットあり •  グループ毎に割合調整が可能 •  niceの絶対値に縛られない優先度管理 •  などここまでのまとめ
•  Coopera:ve vs Preemp:ve •  Low latency (I/O-‐Bound friendly) vs High throuthput (Processor-‐Bound friendly) •  O(1) vs CFS –  O(1)はniceから絶対的なタイムスライスを決める –  CFSでは絶対的なタイムスライスが存在しない •  代わりに全体の中での割合から動的にタイムスライスを決める –  O(1)はpriority毎のqueueを持ちpriorityの高いqueueから
順に掃いていく –  CFSはvirtual run:meが一番少ないプロセスから実行する Linux scheduler Implementa:on
•  主にCFSのコードを扱います •  O(1)などは解説されていないので各自調べて
ください
Scheduler classes
•  Linuxではスケジューラがモジュール化されて
いる –  つまりCFSではない別のスケジューラと同時に動
作させることが可能 •  e.g. リアルタイムプロセスはリアルタイムスケジューラ
がスケジューリングする –  CFSは主に<kernel/sched_fair.c>に実装されてい
る struct sched_en:ty
•  スケジューリングに関する情報をストアするための構造体 •  プロセス毎に持っている •  task_struct構造体（前回qooさんが解説したやつ）に埋め込まれている
struct sched_en:ty { struct load_weight load; /* for load-‐balancing */ struct rb_node run_node; struct list_head group_node; unsigned int on_rq; u64 exec_start; u64 sum_exec_run:me; u64 vrun:me; u64 prev_sum_exec_run:me; u64 nr_migra:ons; /* SNIP */
Virtual Run:meの管理(1)
•  kernel :ckで呼ばれるが、計算自体は:ckから切り離されているため、ナノ
秒単位で実行時間を計算可能 –  “now”はnano秒単位 •  update_curr()にて実際の実行時間を計算する •  さらに、__update_curr()にてweightをかけたvirtual run:meを計算する sta:c void update_curr(struct cfs_rq *cfs_rq) { struct sched_en:ty *curr = cfs_rq-‐>curr; u64 now = rq_of(cfs_rq)-‐>clock_task; unsigned long delta_exec; if (unlikely(!curr)) return; /* * Get the amount of :me the current task was running * since the last :me we changed load (this cannot * overﬂow on 32 bits): */ delta_exec = (unsigned long)(now -‐ curr-‐>exec_start); if (!delta_exec) return; __update_curr(cfs_rq, curr, delta_exec); curr-‐>exec_start = now; if (en:ty_is_task(curr)) { struct task_struct *curtask = task_of(curr); trace_sched_stat_run:me(curtask, delta_exec, curr-‐>vrun:me); cpuacct_charge(curtask, delta_exec); account_group_exec_run:me(curtask, delta_exec); } account_cfs_rq_run:me(cfs_rq, delta_exec); } Virtual Run:meの管理(2)
• 
• 
update_curr()はシステムタイマーにより呼び出され、周期的に実行時間の計算を
行っている update_curr()の実行中はあらゆるプロセスが停止する（厳密な実行時間を計るた
め）
sta:c inline void __update_curr(struct cfs_rq *cfs_rq, struct sched_en:ty *curr, unsigned long delta_exec) { unsigned long delta_exec_weighted; schedstat_set(curr-‐>sta:s:cs.exec_max, max((u64)delta_exec, curr-‐>sta:s:cs.exec_max)); curr-‐>sum_exec_run:me += delta_exec; schedstat_add(cfs_rq, exec_clock, delta_exec); delta_exec_weighted = calc_delta_fair(delta_exec, curr); curr-‐>vrun:me += delta_exec_weighted; update_min_vrun:me(cfs_rq); } Process selec:on
•  vrun:meが最小であるプロセスを選択する –  それ以外は何も考えない！ •  最小vrun:meを持つプロセスの選択にはred-‐black treeを
用いる –  が、red-‐black treeについてはここでは割愛(Chap.6にて詳述と
のこと) –  ここで知っておくべきことは •  与えられたkeyからvalueを高速に検索できる二分探索木に近いデー
タ構造 •  CFSにおいては、最小vrun:meを持つプロセスが自動的に探索木に
おいて一番左(lenmost)のノードとなる •  red-‐black treeはLinux kernelがライブラリとして提供している –  ぐらいで十分 red-‐black treeのイメージ
これが次に実行するプロセスへのポインタになる
Next Taskの選択
•  red-‐black treeを常に左に探索する –  かと思いきやその必要はない –  なぜならlenmostなノードを常にキャッシュしているから –  lenmostがNULLの場合、実行できるプロセスがないため、CFSはidleをスケ
ジュールする
sta:c struct sched_en:ty *__pick_next_en:ty(struct sched_en:ty *se) { struct rb_node *next = rb_next(&se-‐>run_node); if (!next) return NULL; return rb_entry(next, struct sched_en:ty, run_node); } red-‐black treeへのプロセス追加
•  次のいずれかの場合に呼ばれる –  プロセスがrunnableになった –  プロセスがforkされて新たに作成された •  lenmostのキャッシュもここで行う •  実際のred-‐black tree操作はここから呼ばれる
__enqueue_en:ty()が行う
sta:c void enqueue_en:ty(struct cfs_rq *cfs_rq, struct sched_en:ty *se, int ﬂags) { if (!(ﬂags & ENQUEUE_WAKEUP) || (ﬂags & ENQUEUE_WAKING)) se-‐>vrun:me += cfs_rq-‐>min_vrun:me; update_curr(cfs_rq); enqueue_en:ty_load_avg(cfs_rq, se, ﬂags & ENQUEUE_WAKEUP); account_en:ty_enqueue(cfs_rq, se); update_cfs_shares(cfs_rq); if (ﬂags & ENQUEUE_WAKEUP) { place_en:ty(cfs_rq, se, 0); enqueue_sleeper(cfs_rq, se); } update_stats_enqueue(cfs_rq, se); check_spread(cfs_rq, se); if (se != cfs_rq-‐>curr) __enqueue_en:ty(cfs_rq, se); se-‐>on_rq = 1; if (cfs_rq-‐>nr_running == 1) { list_add_leaf_cfs_rq(cfs_rq); check_enqueue_throule(cfs_rq); } }
sta:c void __enqueue_en:ty(struct cfs_rq *cfs_rq, struct sched_en:ty *se) { struct rb_node **link = &cfs_rq-‐>tasks_:meline.rb_node; struct rb_node *parent = NULL; struct sched_en:ty *entry; int lenmost = 1; /* * Find the right place in the rbtree: */ while (*link) { parent = *link; entry = rb_entry(parent, struct sched_en:ty, run_node); /* * We dont care about collisions. Nodes with * the same key stay together. */ if (en:ty_before(se, entry)) { link = &parent-‐>rb_len; } else { link = &parent-‐>rb_right; lenmost = 0; } } /* * Maintain a cache of lenmost tree entries (it is frequently * used): */ if (lenmost) cfs_rq-‐>rb_lenmost = &se-‐>run_node; rb_link_node(&se-‐>run_node, parent, link); rb_insert_color(&se-‐>run_node, &cfs_rq-‐>tasks_:meline); }
red-‐black treeからのプロセス削除
•  次のいずれかの場合に呼ばれる –  プロセスがブロックした –  プロセスが死んだ •  こちらも追加と同じく実際のred-‐black treeの
操作はhelper関数が行う
sta:c void dequeue_en:ty(struct cfs_rq *cfs_rq, struct sched_en:ty *se, int ﬂags) { /* * Update run-‐:me sta:s:cs of the 'current'. */ update_curr(cfs_rq); dequeue_en:ty_load_avg(cfs_rq, se, ﬂags & DEQUEUE_SLEEP); update_stats_dequeue(cfs_rq, se); if (ﬂags & DEQUEUE_SLEEP) { #ifdef CONFIG_SCHEDSTATS if (en:ty_is_task(se)) { struct task_struct *tsk = task_of(se); if (tsk-‐>state & TASK_INTERRUPTIBLE) se-‐>sta:s:cs.sleep_start = rq_of(cfs_rq)-‐>clock; if (tsk-‐>state & TASK_UNINTERRUPTIBLE) se-‐>sta:s:cs.block_start = rq_of(cfs_rq)-‐>clock; } #endif } clear_buddies(cfs_rq, se); if (se != cfs_rq-‐>curr) __dequeue_en:ty(cfs_rq, se); se-‐>on_rq = 0; account_en:ty_dequeue(cfs_rq, se); /* * Normalize the en:ty aner upda:ng the min_vrun:me because the * update can refer to the -‐>curr item and we need to reﬂect this * movement in our normalized posi:on. */ if (!(ﬂags & DEQUEUE_SLEEP)) se-‐>vrun:me -‐= cfs_rq-‐>min_vrun:me; /* return excess run:me on last dequeue */ return_cfs_rq_run:me(cfs_rq); update_min_vrun:me(cfs_rq); update_cfs_shares(cfs_rq); }
sta:c void __dequeue_en:ty(struct cfs_rq *cfs_rq, struct sched_en:ty *se) { if (cfs_rq-‐>rb_lenmost == &se-‐>run_node) { struct rb_node *next_node; next_node = rb_next(&se-‐>run_node); cfs_rq-‐>rb_lenmost = next_node; } rb_erase(&se-‐>run_node, &cfs_rq-‐>tasks_:meline); } Scheduler Entry Point
•  メインエントリポイントは有名なschedule()関
数 –  __schedule()を呼ぶだけ –  __schedule()はスケジュールクラスを選択する
pick_next_task()を呼ぶだけ –  ここでは割愛
pick_next_task()
sta:c inline struct task_struct * pick_next_task(struct rq *rq) { const struct sched_class *class; struct task_struct *p; /* * Op:miza:on: we know that if all tasks are in * the fair class we can call that func:on directly: */ if (likely(rq-‐>nr_running == rq-‐>cfs.h_nr_running)) { ←もしタスク数 = CFSで管理するタスク数なら自動
p = fair_sched_class.pick_next_task(rq); 的にCFSを選ぶ
if (likely(p)) return p; } for_each_class(class) { p = class-‐>pick_next_task(rq); ←プライオリティの高いクラス順にタスクを選ばせる（誰かが結果を返したらその時点でreturn）
if (p) return p; } BUG(); /* the idle class will always have a runnable task */ } ところで
•  本文ではこのあたりからいきなり「プロセス」とい
う言葉が消えて「タスク」という言葉になります •  Linuxにおけるプロセスとタスクの違いってなんな
んでしょうか？ •  とりあえずこの資料は本文中の表現をそのまま
日本語にしてあります •  あと一部O(1)時代の名残と見受けられる記述が
でてきますが（図中の説明分とか）、そのあたり
は省略したり修正したりしています –  原文を知りたい人は自分で読んでね！ sleepとwake up
•  タスクにはnonrunnableを表すステートがある –  これがないと、sleepはbusy waitでしか実装できなくなってしまう –  while(1){sleep(1);}しても重くならないのはこれのおかげ –  もちろんI/O待ち（read()など）の場合にもnonrunnableになる •  sleep処理 1. 
2. 
3. 
4. 
そのタスクが自身をsleep状態にする自身をwait queueに入れる red-‐black treeから自身を削除する schedule()を呼ぶ •  wake up処理 1.  自身をrunnable状態にする 2.  自身をwait queueから出す 3.  自身をred-‐black treeに入れる sleep state
•  sleep中のタスクステートには2種類ある –  TASK_INTERRUPTIBLE •  シグナルを無視しない •  つまり、眠っているタスクに対してシグナルがきた場合
そのタスクは起こされる（そしてシグナルを処理する） –  TASK_UNINTERRUPTIBLE •  シグナルを無視して眠り続ける •  それ以外は何も変わらない
wait queue
•  スリープ中のタスクはwait queueによって管
理される –  これは単純なリスト構造 •  カーネル内ではwake_queue_head_t型で表
現される •  wait queueを作成する関数 –  DECLARE_WAITQUEUE() -‐> 静的に作成 –  init_waitqueue_head() -‐> 動的に作成 sleepと競合状態
•  sleep処理を実装する際には競合状態に気を配る必要がある –  眠る前に起こす条件が満たされてしまうことを避ける •  でないと永遠に目覚めることがない、つまり植物状態に・・・ –  模範的コードの例 /* ‘q’ is the wait queue we wish to sleep on */ DEFINE_WAIT(wait); add_wait_queue(q, &wait); while(!condi:on){ prepare_to_wait(&q, &wait, TASK_INTERRUPTIBLE); if(signal_pending(current)) /* handle signal */ schedule(); } ﬁnish_wait(&q, &wait);
wake up
•  wake_up()関数がwait queueにいる全てのタスクを起こして回る •  wake_up()はtry_to_wake_up()を呼び、try_to_wake_up()は次の仕
事をする –  タスクのステートをTASK_RUNNINGにする –  enqueue_task()を呼んでタスクをred-‐black treeに戻す –  起こしたタスクの優先度がカレントタスクよりも高い場合は
need_reschedフラグを立ててコンテキストスイッチを促す（後述） •  つまりタスクを起こすこととそれを実際に実行することは別 •  さらにタスクを起こしたからといってそのタスクが望む状態になっているとは
限らない(spurious wake-‐up) •  wake_up()は自分を待っているプロセスがいそうな関数によって呼
ばれる –  e.g. VFSなど
sleep & wake up状態遷移
__add_wait_queue() adds task to a wait queue, sets the task’s state to TASK_INTERRUPTIBLE, and calls schedule() receive a signal
TASK_RUNNING
TASK_INTERRUPTIBLE
try_to_wake_up() sets the task to TASK_RUNNING enqueue_task() adds the task to red-‐black tree set need_resched if necessary
Preemp:on&Context switching
•  コンテキストスイッチはcontext_switch()でハンド
ルされる •  context_switch()はschedule()が新しいタスクが選
んだ際に呼ばれる •  context_switch()が行う仕事は大きく分けて2つ –  switch_mm() •  仮想メモリのマッピングを変更する –  switch_to() •  プロセッサのステートを変更する •  スタックやレジスタ、アーキテクチャ依存のパラメータなど
per-‐processなものをスイッチする schedule()が呼ばれるタイミング
•  Linuxでは、need_reschedフラグをスケジューリングのシグナリングに用い
ている –  need_reschedがセットされるタイミングは •  scheduler_:ck()がpreemp:onを判断したとき •  try_to_wake_up()がカレントプロセスよりも優先度の高いプロセスを起こしたとき –  もちろん直接schedule()してもOK •  need_reschedはper-‐processに存在する（thread_info構造体） –  グローバル変数でない理由はそのほうがキャッシュされていて速い可能性が
高いから •  need_resched関連関数 –  set_tsk_need_resched() •  need_reschedフラグをセットする –  clear_tsk_need_resched() •  need_reschedフラグをアンセットする –  need_resched() •  need_reschedフラグをチェックする User-‐preemp:onとKernel-‐preemp:on
•  User-‐preemp:on –  タスクがカーネルでの処理を終えてユーザモードに
戻るときに起きるpreemp:on •  Kernel-‐preemp:on –  タスクがカーネルモードでの処理中に起きる
preemp:on –  カーネルモードでもpreemp:on可能なカーネル = preemp:ve kernel •  Linuxでは条件を限定してpreemp:ve kernel（次項で説明） –  カーネルモードではpreemp:on不可能なカーネル = nonpreemp:ve kernel Kernel-‐preemp:onの条件
•  LinuxはSMPセーフなので、preemp:on時にロッ
クを持っていない必要がある –  でないとpreemp:onして別のプロセスが始まった後に
デッドロックしてしまう –  preemp:veかどうかは、カレントプロセスの
thread_infoのpreempt_countで管理する
•  preempt_count –  初期値は0 –  カーネルモード中にロックをとるとインクリメントされ、
反対にロックを解放するとデクリメントされる •  これが0ならpreempt可能、0でないなら不可能
preemp:onが起きるタイミング
•  User-‐preemp:on 1.  system callからユーザモードに戻るとき 2.  割り込みからユーザモードに戻るとき •  Kernel-‐preemp:on 1.  割り込みからカーネルモードに戻るとき 2.  カーネルモード中に再びpreemp:veになったとき •  つまりpreempt_countが0になったとき 3.  明示的にschedule()を呼んだとき 4.  カーネルモード中にカーネル内でブロックしたとき •  結果的に3.に含まれる need_reschedの全体像 (割り込み終了時のpreemp:onの場合)
__schedule()
set_tsk_need_resched()
preempt_schedule_irq()
need_resched
リスケしてもらいたい人たち
need_resched() == true
scheduler_:ck()
try_to_wake_up()
割り込み終了後のアセンブラコード各アーキテクチャ毎の<kernel/entry.S>などで実装
など
リアルタイムスケジューラ
• 
LinuxではCFSとは別に2種類のリアルタイムスケジューラが提供されている – 
– 
– 
– 
• 
SCHED_FIFO SCHED_RR 主に<kernel/sched_rt.c>で実装ちなみにCFSはSCHED_NORMAL SCHED_FIFO – 
– 
– 
– 
その名の通りFIFOでスケジューリングをおこなう常にSCHED_NORMALよりも優先度が高い SCHED_FIFOによって管理されるタスクは明示的にyieldするかblockするまで止まらないただし優先度の高いSCHED_FIFOまたはSCHED_RRのタスクはSCHED_FIFOのタスクを必ず
preemptする –  本当にタイムスライスの概念がないのはこいつ • 
SCHED_RR – 
– 
– 
– 
ほとんどSCHED_FIFOと同じ動作ただし、こちらにはタイムスライスがあるつまりSCHED_FIFO + タイムスライス = SCHED_RR ただし、タイムスライスが適用されるのは同一プライオリティのSCHED_RRのタスクがある場合
のみ –  優先度が一番高いタスクが一つしかない場合はSCHED_FIFOと同じ Son real-‐:me vs Hard real-‐:me
•  Son real-‐:me system –  なるべく早く処理を終わらせるように計らうが、決めら
れた時間内に処理が終わることは保証しないシステ
ム –  LinuxはSon real-‐:meしか提供しない •  が著者曰くパフォーマンスは極めて良好らしい •  Hard real-‐:me system –  ある決められた時間内に処理が終わることを保証す
るシステム –  Hard real-‐:meが求められる例 •  自動車のABSなど
niceのカーネル内の扱い
•  （もう忘れかけてるかもしれませんが）ユーザから見た
niceの値は – 20から+ 19 •  実は内部的にはリアルタイムスケジューラ用のnice値
が 0 – 99(MAX_RT_PRIO -‐ 1)で予約済み –  CFSなど他のスケジューラが使うnice値はMAX_RT_PRIO – MAX_RT_PRIO + 40の範囲にマップされる •  従ってCFSから見るとniceは実際には100 – 139の値に
なる •  ただし、SCHED_FIFO/SCHED_RRではniceが高いほうが
優先度が高い –  どうしてこうなった・・・
関連system call
•  nice() –  niceを設定する •  sched_getscheduler()/sched_setscheduler() –  scheduling policyを取得/設定する •  sched_getparam()/sched_setparam() –  real-‐:me priorityを取得/設定する •  sched_get_priority_max()/sched_get_priority_min() –  最大/最小 real-‐:me priorityを取得する •  sched_rr_get_interval() –  SCHED_RRのタイムスライスを取得する •  sched_getaﬃnity()/sched_setaﬃnity() –  動作CPUを取得/設定する（動作させるcpuを限定することができる） •  sched_yield() –  カーネルにschedule()させる

Download Report