2.Linuxカーネル学習のプロセススケジューリング初期プローブ(2)プロセススケジューリングの実現(CFS)
13954 ワード
1概要
CFSのコードはkernel/sched_fair.cで実現し、その中で最も重要なのはこの4つの部分である:時間記帳プロセス選択スケジューラ入口睡眠と起動
2時間記帳
スケジューラは、プロセスの実行時間を記帳する必要があります.これにより、プロセスの実行時間がわかります.これにより、現在実行されているプロセスタイムスライスが0に減少した場合、他のタイムスライスが0でないプロセスをスケジューリングしてプリエンプトします.
2.1スケジューラソリッド構造
Linuxでは、CFSはスケジューラエンティティ構造(で定義)を使用してプロセスを追跡して記帳します.この構造体はseと命名され、メンバー変数としてプロセス記述子task_に埋め込まれます.structで.次に、スケジューラエンティティ構造に対応するヘッダファイルコードを示します.
2.2仮想リアルタイム
Linuxカーネルでは,CFSは仮想リアルタイムで実現され,スケジューラエンティティ構造ではvruntime表現を用いる.vruntimeにはプロセスの仮想実行時間(プロセスの実行時間と)が格納され、vruntimeの計算はすべてのプロセスの標準化計算(重み付け計算)を経た.標準化計算とは,iがnice値のプロセッサウェイトマッピングにより仮想実行時間の計算を完了することである.プロセススケジューリングのポリシーでは、プロセス選択時にCFSは、実際の実行時間と理想的な実行時間の2つの重要な概念を統計します.この2つの比で、次の実行プロセスを選択します.実際には、linuxのCFSは仮想リアルタイムを使用してこの統計を実現し、時間記帳機能によってプロセスが実行された時間と実行すべき時間を記録します.この機能はkernel/sched_で定義されています.fair.cファイルのupdate_Curr()関数は実装され,この関数はシステムタイマによって周期的に呼び出されるため,vruntimeはプロセスの実行時間を正確に測定できることに注意すべきである.この関数は、現在のプロセスの実行時間を計算し、delta_に保存します.execは実行時間を__に渡すupdate_Curr()は、現在実行可能なプロセスの合計数を使用して実行時間を重み付けし、重み値と現在の実行プロセスの&&vruntime**を加算します.次は2つの関数の具体的な実装です.
3プロセス選択
プロセススケジューリングポリシーで述べたように、CFSでのプロセス選択は、実際の実行時間と理想的な実行時間の比較によって得られる.しかし、具体的な実装では、vruntimeのみを使用して次の実行プロセスを選択し、CFSのスケジューラはvruntimeの最小プロセスを選択して実行します.
3.1検索
CFSでは、最小vruntimeを有するプロセスをより迅速に見つけるために、赤黒ツリーを使用して実行可能なプロセスを組織する.赤黒樹の原理によれば,最小のvruntimeを持つプロセスは必ず赤黒樹の最左葉ノードにある.したがって、ループするだけで次の実行プロセスを見つけることができます.この機能はkernel/sched_に定義されています.fair.cのpick_next_entity()関数です.実行可能プロセスの赤と黒のツリーには、実行可能なプロセスがないことを示し、実行可能なプロセスがないことを示しますが、CFSスケジューラは待機せず、空のプロセスidleをスケジューリングして実行します.
3.2実行可能プロセスの追加
実行可能なプロセス赤と黒のツリーにプロセスを追加する場合、CFSの実装はキャッシュの方法を採用し、新しく追加したプロセス時に最も左のサブノードがある場合、キャッシュされた現在の最も左のサブノードに取って代わって、さもなくば現在キャッシュされている最も左のリーフノードは変わらず、この方法によって最も左のリーフノードの遍歴を効果的に減らすことができる.この機能はkernel/sched_に定義されています.fair.cのenqueue_entity()関数です.しかし、この関数は更新時間と統計データだけで、具体的な挿入作業は_enqueue_entity関数が完了しました.
3.3実行不可能なプロセスの削除
もちろん、プロセスがブロックされたときに、実行可能なプロセスを表すノードを赤と黒のツリーから削除する関数もあります.この機能はkernel/sched_に定義されています.fair.cのdequeue_entity()関数では、もちろん挿入と同様に関数が完了するのは統計的な作業であり、具体的な削除は_dequeue_entity()関数が完了しました.
4スケジューラ入口
プロセスがスケジューリングする主なエントリ関数は、kernel/schedで定義されるSchedule()です.c中.この関数では、カーネルの他の部分がプロセススケジューラのエントリを呼び出します.Schedule()関数は、まず最も優先度の高いスケジューリングクラス(このスケジューリングクラスには独自の実行可能なキューがある)を見つけ、その後、Schedule関数は、このスケジューリングクラスによって次の実行プロセスをSchedule関数に通知します.Schedule関数の最も重要な作業はpick_next_task()関数は、各スケジューリングクラスを優先度順にチェックし、最も優先度の高いスケジューリングクラスから最も優先度の高いプロセスを選択します.
5眠りと目覚め
プロセスがブロックされると実行不可能な状態になり、この状態は睡眠状態とも呼ばれ、スケジューラは睡眠状態にあるプロセス実行を選択することができず、プロセスはいくつかのイベントの発生を待っている間にこの状態になります.目覚ましは睡眠状態のプロセスが待っているイベントが発生すると、プロセスは実行可能な状態にあり、赤黒の木を実行できるとも言われています.
5.1待ち行列
スリープのプロセスは待機キューに格納され、カーネルはwake_を使用します.queue_head_tは待機キューを表す.待ち行列には、DECLARE_という2つの実装方法があります.WAITQUEUE()静的作成とinit_waitqueue_head()動的作成.ブロック時にプロセスは自分を待機キューに入れ、実行不可能な状態に設定し、ブロックされたイベントが発生すると、キュー上のプロセスが起動します.プロセスが待機キューに参加するには、次の手順に従います.
1.マクロDEFINE_を呼び出すWAIT()は待ち行列を作成する;2.add_を呼び出すwait_Queue()は自分をキューに追加します.プロセスは待機中の条件で起動するので、待機中のイベントが発生した場合にwake_を実行できる適切な起動条件コードを他の場所で作成する必要があります.up()操作;3.prepareを呼び出すto_wait()メソッドプロセスステータスをTASK_に設定INTERUPTIBLEまたはTASK_UNINTERRUPTIBLE.ループが経過すると、この関数はプロセスを待機キューに戻すこともできます.4.ステータスがTASK_INTERUPTIBLEのプロセスは、信号によって起動することができる.この呼び出しは偽の呼び出しです.プロセスが待っているイベントは発生していないからです.5.プロセスが起動されると、待機中のイベントが発生しているかどうかを確認します.発生するとスリープを終了し、発生しないとSchedule()関数をループ呼び出します.6.待機中のイベントが発生すると、プロセスは自分をTASK_に設定します.RUNNINGはfinish_を呼び出すwait()メソッドは待機キューを発売する.
プロセスがスリープする前に待機していたイベントが発生すると、プロセスはスリープ状態になりません.関数inotify_read()関数は、fs/notify/inotify/inotify/inotify_user.cで実現する.
5.2起動
目覚まし操作は前にも述べたようにwake_up()関数が完了すると、作成された待機キュー上のすべてのプロセスが呼び出されます.wake_up()関数では、まずtry_が呼び出されます.to_wake_up()プロセスステータスをTASK_に設定RUNNING状態;次にenqueue_を呼び出します.task()関数は、プロセスを実行可能な赤と黒のツリーに挿入します.最後に、起動されたプロセスの優先度が現在実行中のプロセスより高い場合はneed_を設定します.resched()フラグ;
これは个人が《Linuxカーネルの设计と実现》を読む时の少しの心得で、中にいくつか自分のオペレーティングシステムについての理解を加えて、自分の既存の知识に対して整理して、もし间违いがあれば指摘してください.
CFSのコードはkernel/sched_fair.cで実現し、その中で最も重要なのはこの4つの部分である:時間記帳プロセス選択スケジューラ入口睡眠と起動
2時間記帳
スケジューラは、プロセスの実行時間を記帳する必要があります.これにより、プロセスの実行時間がわかります.これにより、現在実行されているプロセスタイムスライスが0に減少した場合、他のタイムスライスが0でないプロセスをスケジューリングしてプリエンプトします.
2.1スケジューラソリッド構造
Linuxでは、CFSはスケジューラエンティティ構造(で定義)を使用してプロセスを追跡して記帳します.この構造体はseと命名され、メンバー変数としてプロセス記述子task_に埋め込まれます.structで.次に、スケジューラエンティティ構造に対応するヘッダファイルコードを示します.
struct sched_entity {
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_runtime;
u64 vruntime; /* */
u64 prev_sum_exec_runtime;
u64 nr_migrations;
#ifdef CONFIG_SCHEDSTATS
struct sched_statistics statistics;
#endif
#ifdef CONFIG_FAIR_GROUP_SCHED
struct sched_entity *parent;
/* rq on which this entity is (to be) queued: */
struct cfs_rq *cfs_rq;
/* rq "owned" by this entity/group: */
struct cfs_rq *my_q;
#endif
};
2.2仮想リアルタイム
Linuxカーネルでは,CFSは仮想リアルタイムで実現され,スケジューラエンティティ構造ではvruntime表現を用いる.vruntimeにはプロセスの仮想実行時間(プロセスの実行時間と)が格納され、vruntimeの計算はすべてのプロセスの標準化計算(重み付け計算)を経た.標準化計算とは,iがnice値のプロセッサウェイトマッピングにより仮想実行時間の計算を完了することである.プロセススケジューリングのポリシーでは、プロセス選択時にCFSは、実際の実行時間と理想的な実行時間の2つの重要な概念を統計します.この2つの比で、次の実行プロセスを選択します.実際には、linuxのCFSは仮想リアルタイムを使用してこの統計を実現し、時間記帳機能によってプロセスが実行された時間と実行すべき時間を記録します.この機能はkernel/sched_で定義されています.fair.cファイルのupdate_Curr()関数は実装され,この関数はシステムタイマによって周期的に呼び出されるため,vruntimeはプロセスの実行時間を正確に測定できることに注意すべきである.この関数は、現在のプロセスの実行時間を計算し、delta_に保存します.execは実行時間を__に渡すupdate_Curr()は、現在実行可能なプロセスの合計数を使用して実行時間を重み付けし、重み値と現在の実行プロセスの&&vruntime**を加算します.次は2つの関数の具体的な実装です.
static void update_curr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr;//
u64 now = rq_of(cfs_rq)->clock;//
unsigned long delta_exec;
if (unlikely(!curr))
return;
/*
* (this cannot
* overflow 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 (entity_is_task(curr)) {
struct task_struct *curtask = task_of(curr);
trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
cpuacct_charge(curtask, delta_exec);
account_group_exec_runtime(curtask, delta_exec);
}
}
__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
unsigned long delta_exec)
{
unsigned long delta_exec_weighted;
schedstat_set(curr->statistics.exec_max,
max((u64)delta_exec, curr->statistics.exec_max));
curr->sum_exec_runtime += delta_exec;
schedstat_add(cfs_rq, exec_clock, delta_exec);
delta_exec_weighted = calc_delta_fair(delta_exec, curr);
curr->vruntime += delta_exec_weighted;
update_min_vruntime(cfs_rq);
}
3プロセス選択
プロセススケジューリングポリシーで述べたように、CFSでのプロセス選択は、実際の実行時間と理想的な実行時間の比較によって得られる.しかし、具体的な実装では、vruntimeのみを使用して次の実行プロセスを選択し、CFSのスケジューラはvruntimeの最小プロセスを選択して実行します.
3.1検索
CFSでは、最小vruntimeを有するプロセスをより迅速に見つけるために、赤黒ツリーを使用して実行可能なプロセスを組織する.赤黒樹の原理によれば,最小のvruntimeを持つプロセスは必ず赤黒樹の最左葉ノードにある.したがって、ループするだけで次の実行プロセスを見つけることができます.この機能はkernel/sched_に定義されています.fair.cのpick_next_entity()関数です.実行可能プロセスの赤と黒のツリーには、実行可能なプロセスがないことを示し、実行可能なプロセスがないことを示しますが、CFSスケジューラは待機せず、空のプロセスidleをスケジューリングして実行します.
static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
{
struct sched_entity *se = __pick_next_entity(cfs_rq);
struct sched_entity *left = se;
if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
se = cfs_rq->next;
/*
* Prefer last buddy, try to return the CPU to a preempted task.
*/
if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
se = cfs_rq->last;
clear_buddies(cfs_rq, se);
return se;
}
3.2実行可能プロセスの追加
実行可能なプロセス赤と黒のツリーにプロセスを追加する場合、CFSの実装はキャッシュの方法を採用し、新しく追加したプロセス時に最も左のサブノードがある場合、キャッシュされた現在の最も左のサブノードに取って代わって、さもなくば現在キャッシュされている最も左のリーフノードは変わらず、この方法によって最も左のリーフノードの遍歴を効果的に減らすことができる.この機能はkernel/sched_に定義されています.fair.cのenqueue_entity()関数です.しかし、この関数は更新時間と統計データだけで、具体的な挿入作業は_enqueue_entity関数が完了しました.
static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
/*
* Update the normalized vruntime before updating min_vruntime
* through callig update_curr().
*/
if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
se->vruntime += cfs_rq->min_vruntime;
/*
* Update run-time statistics of the 'current'.
*/
update_curr(cfs_rq);
account_entity_enqueue(cfs_rq, se);
if (flags & ENQUEUE_WAKEUP) {
place_entity(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_entity(cfs_rq, se);
}
/*
* Enqueue an entity into the rb-tree:
*/
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
struct rb_node *parent = NULL;
struct sched_entity *entry;
s64 key = entity_key(cfs_rq, se);
int leftmost = 1;
/*
* Find the right place in the rbtree:
*/
while (*link) {//
parent = *link;
entry = rb_entry(parent, struct sched_entity, run_node);
/*
* We dont care about collisions. Nodes with
* the same key stay together.
*/
if (key < entity_key(cfs_rq, entry)) {//
link = &parent->rb_left;
} else {
link = &parent->rb_right;
leftmost = 0;
}
}
/*
* Maintain a cache of leftmost tree entries (it is frequently
* used):
*/
if (leftmost)//
cfs_rq->rb_leftmost = &se->run_node;
rb_link_node(&se->run_node, parent, link);
rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
}
3.3実行不可能なプロセスの削除
もちろん、プロセスがブロックされたときに、実行可能なプロセスを表すノードを赤と黒のツリーから削除する関数もあります.この機能はkernel/sched_に定義されています.fair.cのdequeue_entity()関数では、もちろん挿入と同様に関数が完了するのは統計的な作業であり、具体的な削除は_dequeue_entity()関数が完了しました.
static void
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
u64 min_vruntime;
/*
* Update run-time statistics of the 'current'.
*/
update_curr(cfs_rq);
update_stats_dequeue(cfs_rq, se);
if (flags & DEQUEUE_SLEEP) {
#ifdef CONFIG_SCHEDSTATS
if (entity_is_task(se)) {
struct task_struct *tsk = task_of(se);
if (tsk->state & TASK_INTERRUPTIBLE)
se->statistics.sleep_start = rq_of(cfs_rq)->clock;
if (tsk->state & TASK_UNINTERRUPTIBLE)
se->statistics.block_start = rq_of(cfs_rq)->clock;
}
#endif
}
clear_buddies(cfs_rq, se);
if (se != cfs_rq->curr)
__dequeue_entity(cfs_rq, se);
account_entity_dequeue(cfs_rq, se);
min_vruntime = cfs_rq->min_vruntime;
update_min_vruntime(cfs_rq);
/*
* Normalize the entity after updating the min_vruntime because the
* update can refer to the ->curr item and we need to reflect this
* movement in our normalized position.
*/
if (!(flags & DEQUEUE_SLEEP))
se->vruntime -= min_vruntime;
}
static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
if (cfs_rq->rb_leftmost == &se->run_node) {
struct rb_node *next_node;
next_node = rb_next(&se->run_node);
cfs_rq->rb_leftmost = next_node;
}
rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
}
4スケジューラ入口
プロセスがスケジューリングする主なエントリ関数は、kernel/schedで定義されるSchedule()です.c中.この関数では、カーネルの他の部分がプロセススケジューラのエントリを呼び出します.Schedule()関数は、まず最も優先度の高いスケジューリングクラス(このスケジューリングクラスには独自の実行可能なキューがある)を見つけ、その後、Schedule関数は、このスケジューリングクラスによって次の実行プロセスをSchedule関数に通知します.Schedule関数の最も重要な作業はpick_next_task()関数は、各スケジューリングクラスを優先度順にチェックし、最も優先度の高いスケジューリングクラスから最も優先度の高いプロセスを選択します.
/*
* schedule() is the main scheduler function.
*/
asmlinkage void __sched schedule(void)
{
struct task_struct *prev, *next;
unsigned long *switch_count;
struct rq *rq;
int cpu;
need_resched:
preempt_disable();
cpu = smp_processor_id();
rq = cpu_rq(cpu);
rcu_note_context_switch(cpu);
prev = rq->curr;
switch_count = &prev->nivcsw;
release_kernel_lock(prev);
need_resched_nonpreemptible:
schedule_debug(prev);
if (sched_feat(HRTICK))
hrtick_clear(rq);
raw_spin_lock_irq(&rq->lock);
clear_tsk_need_resched(prev);
if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
if (unlikely(signal_pending_state(prev->state, prev)))
prev->state = TASK_RUNNING;
else
deactivate_task(rq, prev, DEQUEUE_SLEEP);
switch_count = &prev->nvcsw;
}
pre_schedule(rq, prev);
if (unlikely(!rq->nr_running))
idle_balance(cpu, rq);
put_prev_task(rq, prev);
next = pick_next_task(rq);
if (likely(prev != next)) {
sched_info_switch(prev, next);
perf_event_task_sched_out(prev, next);
rq->nr_switches++;
rq->curr = next;
++*switch_count;
context_switch(rq, prev, next); /* unlocks the rq */
/*
* the context switch might have flipped the stack from under
* us, hence refresh the local variables.
*/
cpu = smp_processor_id();
rq = cpu_rq(cpu);
} else
raw_spin_unlock_irq(&rq->lock);
post_schedule(rq);
if (unlikely(reacquire_kernel_lock(current) < 0)) {
prev = rq->curr;
switch_count = &prev->nivcsw;
goto need_resched_nonpreemptible;
}
preempt_enable_no_resched();
if (need_resched())
goto need_resched;
}
/*
* Pick up the highest-prio task:
*/
static inline struct task_struct *
pick_next_task(struct rq *rq)
{
const struct sched_class *class;
struct task_struct *p;
/*
* Optimization: we know that if all tasks are in
* the fair class we can call that function directly:
*/
if (likely(rq->nr_running == rq->cfs.nr_running)) {
p = fair_sched_class.pick_next_task(rq);
if (likely(p))
return p;
}
class = sched_class_highest;
for ( ; ; ) {
p = class->pick_next_task(rq);
if (p)
return p;
/*
* Will never be NULL as the idle class always
* returns a non-NULL p:
*/
class = class->next;
}
}
5眠りと目覚め
プロセスがブロックされると実行不可能な状態になり、この状態は睡眠状態とも呼ばれ、スケジューラは睡眠状態にあるプロセス実行を選択することができず、プロセスはいくつかのイベントの発生を待っている間にこの状態になります.目覚ましは睡眠状態のプロセスが待っているイベントが発生すると、プロセスは実行可能な状態にあり、赤黒の木を実行できるとも言われています.
5.1待ち行列
スリープのプロセスは待機キューに格納され、カーネルはwake_を使用します.queue_head_tは待機キューを表す.待ち行列には、DECLARE_という2つの実装方法があります.WAITQUEUE()静的作成とinit_waitqueue_head()動的作成.ブロック時にプロセスは自分を待機キューに入れ、実行不可能な状態に設定し、ブロックされたイベントが発生すると、キュー上のプロセスが起動します.プロセスが待機キューに参加するには、次の手順に従います.
1.マクロDEFINE_を呼び出すWAIT()は待ち行列を作成する;2.add_を呼び出すwait_Queue()は自分をキューに追加します.プロセスは待機中の条件で起動するので、待機中のイベントが発生した場合にwake_を実行できる適切な起動条件コードを他の場所で作成する必要があります.up()操作;3.prepareを呼び出すto_wait()メソッドプロセスステータスをTASK_に設定INTERUPTIBLEまたはTASK_UNINTERRUPTIBLE.ループが経過すると、この関数はプロセスを待機キューに戻すこともできます.4.ステータスがTASK_INTERUPTIBLEのプロセスは、信号によって起動することができる.この呼び出しは偽の呼び出しです.プロセスが待っているイベントは発生していないからです.5.プロセスが起動されると、待機中のイベントが発生しているかどうかを確認します.発生するとスリープを終了し、発生しないとSchedule()関数をループ呼び出します.6.待機中のイベントが発生すると、プロセスは自分をTASK_に設定します.RUNNINGはfinish_を呼び出すwait()メソッドは待機キューを発売する.
プロセスがスリープする前に待機していたイベントが発生すると、プロセスはスリープ状態になりません.関数inotify_read()関数は、fs/notify/inotify/inotify/inotify_user.cで実現する.
static ssize_t inotify_read(struct file *file, char __user *buf,
size_t count, loff_t *pos)
{
struct fsnotify_group *group;
struct fsnotify_event *kevent;
char __user *start;
int ret;
DEFINE_WAIT(wait);
start = buf;
group = file->private_data;
while (1) {
prepare_to_wait(&group->notification_waitq, &wait, TASK_INTERRUPTIBLE);
mutex_lock(&group->notification_mutex);
kevent = get_one_event(group, count);
mutex_unlock(&group->notification_mutex);
if (kevent) {
ret = PTR_ERR(kevent);
if (IS_ERR(kevent))
break;
ret = copy_event_to_user(group, kevent, buf);
fsnotify_put_event(kevent);
if (ret < 0)
break;
buf += ret;
count -= ret;
continue;
}
ret = -EAGAIN;
if (file->f_flags & O_NONBLOCK)
break;
ret = -EINTR;
if (signal_pending(current))
break;
if (start != buf)
break;
schedule();
}
finish_wait(&group->notification_waitq, &wait);
if (start != buf && ret != -EFAULT)
ret = buf - start;
return ret;
}
5.2起動
目覚まし操作は前にも述べたようにwake_up()関数が完了すると、作成された待機キュー上のすべてのプロセスが呼び出されます.wake_up()関数では、まずtry_が呼び出されます.to_wake_up()プロセスステータスをTASK_に設定RUNNING状態;次にenqueue_を呼び出します.task()関数は、プロセスを実行可能な赤と黒のツリーに挿入します.最後に、起動されたプロセスの優先度が現在実行中のプロセスより高い場合はneed_を設定します.resched()フラグ;
これは个人が《Linuxカーネルの设计と実现》を読む时の少しの心得で、中にいくつか自分のオペレーティングシステムについての理解を加えて、自分の既存の知识に対して整理して、もし间违いがあれば指摘してください.