『Linuxカーネル解読室』輪講 #1「プロセススケジューリング」
Linuxカーネルの話を知りたいなーってんで、『Linuxカーネル解読室』の輪講を始めました。とりあえず、カーネルのソースをがりがり読み込むというよりは、ざっくりと動作を把握しようという感じで。今日の初回は、第1章「プロセススケジューリング」を読みました。この分野にまったくもって不案内なので、難しい……。少しづつでも理解を進めたいです。
以下に資料を貼り付けておきます。実際には、
id:naoyaをはじめとした参加者によるフォローに助けられて進めた感じなので、資料だけだといろいろとアレな面もあるとは思います。
- 作者: 高橋浩和,小田逸郎,山幡為佐久
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2006/11/18
- メディア: 単行本
- 購入: 13人 クリック: 189回
- この商品を含むブログ (116件) を見る
![[24時間365日] サーバ/インフラを支える技術 ?スケーラビリティ、ハイパフォーマンス、省力運用 (WEB+DB PRESS plusシリーズ)](http://ecx.images-amazon.com/images/I/51uK4ACymiL._SL160_.jpg "[24時間365日] サーバ/インフラを支える技術 ?スケーラビリティ、ハイパフォーマンス、省力運用 (WEB+DB PRESS plusシリーズ)")
[24時間365日] サーバ/インフラを支える技術 ?スケーラビリティ、ハイパフォーマンス、省力運用 (WEB+DB PRESS plusシリーズ)
- 作者: 安井真伸,横川和哉,ひろせまさあき,伊藤直也,田中慎司,勝見祐己
- 出版社/メーカー: 技術評論社
- 発売日: 2008/08/07
- メディア: 単行本（ソフトカバー）
- 購入: 128人 クリック: 2,192回
- この商品を含むブログ (283件) を見る
『Linuxカーネル解読室』第1章「プロセススケジューリング」
- 担当:
id:antipop
プロセススケジューリング
- マルチタスクの実現に必要な、基本的な仕組み
- 複数のプロセスを並列に実行
- プロセスに実行権を与える ... プロセスディスパッチャ
- プロセスの実行切り替えを制御する ... プロセススケジューラ
- Linuxカーネル2.4 → 2.6で、「O(1)スケジューラ」に書き直された(具体的には後述)
- 複数のプロセスを並列に実行
「負荷」とは何か
結局のところ「負荷」というのは、複数のタスクによるサーバリソースの奪い合いの結果生じる待ち時間を一言で表した言葉でしかありません。その正体を知るためには、「タスクが待たされるのはどのような場合か」というOSの挙動、つまりLinuxカーネルの動作を理解する必要があります。
『24時間365日 サーバ/インフラを支える技術』p.153より
- 以降、「負荷」について知る端緒を得るために、プロセススケジューリングを見ていく
プロセス
- 詳細は第7章「プロセス管理」で見るとして、ここで「プロセス」とは:
- あるプログラムが動いている状態のこと
- プログラムの実行に必要な命令やデータなどの固まり(コンテキスト)
- task_struct構造体によって管理されている
- あるプログラムが動いている状態のこと
- これら多数のプロセスを並列に実行するための仕組みがプロセススケジューラ
task_struct構造体 (include/linux/sched.h)
- 以下のようなメンバを持つ構造体
- この章で出てくるもののみ掲載
| メンバ | 説明 |
|---|---|
| pid | プロセスID |
| thread | アーキテクチャ依存のCPU状態の保存領域 |
| state | プロセスの実行状態 |
| ... | ... |
プロセス切り替え概略
- プロセスを切り替えるとは:
- 各プロセスが実行されているコンテキストの退避、復帰を繰替えすこと
- メモリやレジスタ上に記録された変数の値
- プログラムカウンタ
- スタックポインタ
- などなど
- 各プロセスが実行されているコンテキストの退避、復帰を繰替えすこと
プロセス切り替え概略(図)
プロセス切り替えの実装
- kernel/sched.cのcontext_switch()
- プロセス空間の切り替え
- 各種レジスタの状態を切り替える
プロセス空間の切り替え
- arch/x86/include/asm/mmu_context.hのswitch_mm()関数
- なんかいろいろやってるけどよくわからないので放置
- 仮想メモリアドレスを切り替えたり、ってことなんだと思う
ソースは2.6.33のものを貼っています(以下同様)。
static inline void switch_mm(struct mm_struct *prev, struct mm_struct *next, struct task_struct *tsk) { unsigned cpu = smp_processor_id(); if (likely(prev != next)) { /* stop flush ipis for the previous mm */ cpumask_clear_cpu(cpu, mm_cpumask(prev)); #ifdef CONFIG_SMP percpu_write(cpu_tlbstate.state, TLBSTATE_OK); percpu_write(cpu_tlbstate.active_mm, next); #endif cpumask_set_cpu(cpu, mm_cpumask(next)); /* Re-load page tables */ load_cr3(next->pgd); /* * load the LDT, if the LDT is different: */ if (unlikely(prev->context.ldt != next->context.ldt)) load_LDT_nolock(&next->context); } #ifdef CONFIG_SMP else { percpu_write(cpu_tlbstate.state, TLBSTATE_OK); BUG_ON(percpu_read(cpu_tlbstate.active_mm) != next); if (!cpumask_test_and_set_cpu(cpu, mm_cpumask(next))) { /* We were in lazy tlb mode and leave_mm disabled * tlb flush IPI delivery. We must reload CR3 * to make sure to use no freed page tables. */ load_cr3(next->pgd); load_LDT_nolock(&next->context); } } #endif }
各種レジスタの状態を切り替える
arch/x86/include/asm/system.hのswitch_toマクロ
- 現在のプロセス: A
- 次のプロセス: B
として、
- 現在のCPUの各種フラグを退避
- 演算結果を表すフラグなど(条件分岐の時などに使うzero flagとかそういう連中)
- Aのフレームポインタ、スタックポインタを退避
- Bのスタックポインタを復帰
- Aが復帰した時のインストラクションポインタを退避
- Bのインストラクションポインタをスタックに復帰
- その他の、各種レジスタの内容を切り替え(詳細略)
- Aが復帰した後にフレームポインタ、CPUのフラグを復帰させる
#define switch_to(prev, next, last) \ do { \ /* \ * Context-switching clobbers all registers, so we clobber \ * them explicitly, via unused output variables. \ * (EAX and EBP is not listed because EBP is saved/restored \ * explicitly for wchan access and EAX is the return value of \ * __switch_to()) \ */ \ unsigned long ebx, ecx, edx, esi, edi; \ \ asm volatile("pushfl\n\t" /* save flags */ \ "pushl %%ebp\n\t" /* save EBP */ \ "movl %%esp,%[prev_sp]\n\t" /* save ESP */ \ "movl %[next_sp],%%esp\n\t" /* restore ESP */ \ "movl $1f,%[prev_ip]\n\t" /* save EIP */ \ "pushl %[next_ip]\n\t" /* restore EIP */ \ __switch_canary \ "jmp __switch_to\n" /* regparm call */ \ "1:\t" \ "popl %%ebp\n\t" /* restore EBP */ \ "popfl\n" /* restore flags */ \ \ /* output parameters */ \ : [prev_sp] "=m" (prev->thread.sp), \ [prev_ip] "=m" (prev->thread.ip), \ "=a" (last), \ \ /* clobbered output registers: */ \ "=b" (ebx), "=c" (ecx), "=d" (edx), \ "=S" (esi), "=D" (edi) \ \ __switch_canary_oparam \ \ /* input parameters: */ \ : [next_sp] "m" (next->thread.sp), \ [next_ip] "m" (next->thread.ip), \ \ /* regparm parameters for __switch_to(): */ \ [prev] "a" (prev), \ [next] "d" (next) \ \ __switch_canary_iparam \ \ : /* reloaded segment registers */ \ "memory"); \ } while (0)
プロセススケジューラ
優先度
- 固定優先度
- nice値(niceコマンドで指定できる)
- たとえばこのように実行するとプロセスの優先度を下げて実行する → $ nice -n 19 重い検索
- nice値(niceコマンドで指定できる)
- 変動優先度
- プロセスの状態や、CPUの利用状況により変動(後述)
スケジューリングが行われるタイミング
- 実行中のプロセスが自ら実行権を手放した時
- 実行中のプロセスが割り当て時間を使い果たした時
- 新しく実行可能状態になったプロセスがあった時
- 以上の場合にスケジューラは、現在最も高い優先度を持つプロセスを選択し、切り替えを行う
プロセススケジューリング概略(図)
マルチプロセッサにおけるプロセススケジューリング
- 基本的には、プロセッサをまたがってプロセスを実行することはない
- キャッシュメモリ内のデータなどをコピーする等のオーバヘッドが発生するため
- ただし、CPU間の負荷の偏りがある場合には、CPUの持つ実行待ちプロセスキュー(RUNキュー)間で、プロセスの移動が行われる場合もある
Linuxカーネル2.6のプロセススケジューラ
Linuxカーネル2.4以前のプロセススケジューラは非常に単純な構造で、マルチプロセッサシステムであっても、単一のキューに実行可能プロセスをすべてつなぎ、再スケジューリングの度にキューに登録されているすべてのプロセスを検索して、実行権を与えるプロセスを選び出していました。
(中略)
Linuxカーネル2.6のRUNキューは実行優先度ごとにスロットを用意しています。次に実行するプロセスは、プロセスが存在する最も高い実行優先度のスロットから、先頭に登録されているプロセスを選択するだけです。これによって、再スケジューリング時、最も実行優先度の高いプロセスを容易に見つけることができます。実行可能なプロセスがいくつ存在していても、検索量は常に一定であるため、検索指定（オーダー）が1のスケジューラ、つまり「O(1)スケジューラ」と呼ばれています
- 2.4のプロセススケジューラ
- コアの数に関わらずRUNキューはひとつ
- マルチコア環境だと、キューへの競合が発生してボトルネックになる
- 次に実行するプロセスを取得するために、優先度の高いプロセスを線形探索する
- コアの数に関わらずRUNキューはひとつ
- 2.6のプロセススケジューラ
- 各CPUごとにactive/expiredのキューのリストを持つ
- 各キューは優先度別にまとめられているので、次に実行するべきプロセスを効率的に取得できる
プロセススケジューラの実装
kernel/sched.cのschedule()関数
2.6.33では、本書の2.6.15からずいぶん変わっている。以下は本書の解説の要約だが、最新版のコードではschedule()関数の中では優先度の計算を行っていないぽい。
- 現在のプロセスが待機状態になった時、RUNキューから外す
- 待機状態にはTASK_INTERRUPTIBLE/TASK_UNINTERRUPTIBLEのふたつの状態がある(後述)
- RUNキューから最も実行優先度の高いプロセスを取り出す
- プロセスの走行時間、待機時間を元に決定
- 前述のcontext_switch()関数によりプロセスを切り替える
- 切り替え中にスケジューリング要求があった場合は、その間はロックしておき、切り替え後に改めてスケジューリングしなおす
- 優先度の調整
- TASK_INTERRUBTIBLEから復帰したばかりのプロセスは優先度を上げる
- 対話型プロセスについては、走行時間を短めに見積ることで優先度を上げる
- 割り込み処理による復帰についても優先度を上げる
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_sched_qs(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); update_rq_clock(rq); 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, 1); 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, cpu); 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; } EXPORT_SYMBOL(schedule);
事象の待ち合わせ(待機状態)
| 値 | 意味 |
|---|---|
| TASK_RUNNING | 実行可能状態（実行状態、実行待ち状態） |
| TASK_INTERRUPTIBLE | 待機状態。シグナルによる待機状態解除可能 |
| TASK_UNINTERRUPTIBLE | 待機状態。シグナルによる待機状態解除不可 |
- TASK_RUNNING
- TASK_RUNNNINGという名前だが、実際には「実行可能な状態」と「まさに実行している状態」とがある
- TASK_INTERRUPTIBLE
- ソケットや端末を待っている状態など。復帰時間が予測不可能な事象発生を待ち合わせる状態
- TASK_UNINTERRUPTIBLE
- ディスクの入出力など。シグナルを受けても、シグナルを保留状態にしたまま待機する(詳細第8章「シグナル処理」)
psで見てみる
- STAT欄が:
- S(Sleep) ... TASK_INTERRUPTIBLE
- R(Run) ... TASK_RUNNING
- D(Disk Sleep) ... TASK_UNINTERRUPTIBLE
$ ps auxw | egrep '(STAT|httpd)' USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMAND apache 1004 0.0 1.3 456244 112360 ? S Mar09 0:03 /usr/sbin/httpd -f /home/httpd/vhosts/... apache 1009 0.0 1.3 453164 109160 ? R Mar09 0:01 /usr/sbin/httpd -f /home/httpd/vhosts/... apache 1011 0.0 0.9 405088 74164 ? S Mar09 0:00 /usr/sbin/httpd -f /home/httpd/vhosts/...
「負荷」が高いというのはどういう状態か
- load avarageとは？
- 単位時間あたりの待ちタスク数
- 処理を実行したくても実行できなくて待たされているプロセスがどれぐらいあるか
- ここで見た待機状態のうち、TASK_RUNNINGとTASK_UNINTERRUPTIBLEだけが換算される
- TASK_INTERRUPTIBLEなプロセスはload averageに影響しない
- 単位時間あたりの待ちタスク数
- load averageでは、具体的にどのような原因によるものなのかまではわからない
- CPU bound/IO boudいずれによる負荷なのかについては、sarなどのツールを使ってさらに調査する必要がある。
参考文献
- Linux Kernel Documents Wiki - SourceForge.JP
- 第3回 プロセス・スケジューリング - Linuxカーネルの基本機能：ITpro
- gccのfastcall関数呼び出しについて : no hacking, no life
ふつうのコンパイラをつくろう 言語処理系をつくりながら学ぶコンパイルと実行環境の仕組み
- 作者: 青木峰郎
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2009/07/24
- メディア: 単行本
- 購入: 25人 クリック: 382回
- この商品を含むブログ (46件) を見る
