狠狠撸

狠狠撸Share a Scribd company logo

Kernel vm study_2_xv6_scheduler_part1_revised

?
?
Toshiaki Nozawa
Toshiaki Nozawa

カーネルVM勉強会第二回 scheduler 文字化けがあるけどひとまず

1 of 16
Download to read offline
xv6 scheduler Part 1 ( 修正版 ) @noztos 2012.9.2 カーネル VM 勉強会 第二回 OS 基礎 (xv6)
Scheduling ● ひとつの物理プロセッサを多重化する 複数の ( 仮想 ) プロ セッ サが存在する かのよ う に動作 ● ユーザープロセスに錯ーさせる – 専用のメモリ空間 – 専用プロセッサ 12/09/02 xv6 scheduler part1 2
Multiplexing ● タイマ割込み 100ms( 固定 ) ● 多重化の実装 1.コンテキスト切り替え：標準的機構 2.透過的コンテキスト切り替え方法 : タイ ー割ーみハンド ( プリエンプティブ ) マ ラ 3.複数 CPU × マルチプロセスの同時実行 : 競合回避のための lock 4.プロセス終了時 : メモリ、リソースの解放 12/09/02 xv6 scheduler part1 3
Context Switching 12/09/02 xv6 scheduler part1 4
Context Switching ● Scheduler thread を必ず経由 プロセスから system call or interrupt ↓ scheduler ↓ 他プロセスへ trap return ● Scheduler thread は CPU 毎 ● 旧スレッドの register をセーブ 保存し て いた新スレ ッ ド の register をリストア cf. swtch.S 12/09/02 xv6 scheduler part1 5
Context Switching - swtch() ● Thread について は知ら ず、 "contexts” を管理 す る のみ ● void swtch(struct context **old, struct context *new); # Save old registers # Load new registers movl 4(%esp), %eax movl 4(%esp), %eax # not 8(%esp) - popped return address above popl 0(%eax) # %eip movl %esp, 4(%eax) movl 28(%eax), %ebp movl %ebx, 8(%eax) movl 24(%eax), %edi movl %ecx, 12(%eax) movl 20(%eax), %esi movl %edx, 16(%eax) movl 16(%eax), %edx movl %esi, 20(%eax) movl 12(%eax), %ecx movl %edi, 24(%eax) movl 8(%eax), %ebx movl %ebp, 28(%eax) movl 4(%eax), %esp pushl 0(%eax) # %eip 12/09/02 xv6 scheduler part1 6
Scheduling – sched() ● CPU を解放するには – ptable.lock を取得 – 取得している他の lock の解放 – 自身の proc->state の更新 – sched() の呼出 proc.c: yield(), sleep(), exit() からのみ ● sched() 内でもチェック + 割込み禁止確認 12/09/02 xv6 scheduler part1 7
Scheduling – sched() を抜けるとそこは ● sched() において swtch() を呼ぶことにより proc->context(=current context) から cpu->scheduler(=scheduler context) へー身 ● “Scheduler context へ変身” ... ということは swtch() から戻るのは proc.c:scheduler() そして何事もなかったかのように RUNNABLE プロセスを探す proc.c: scheduler() 内 l.214 – l.231 12/09/02 xv6 scheduler part1 8
Scheduling – ptable.lock ● swtch() を呼ぶ前に ptable.lock を取得 lock の取得、解放は thread の責任 – Unusual swtch() 中の proc->state, cpu->context の 整合性保持をシンプルに ● おまけ情報 カーネル空間で使用する sleep() は、引数で lock を指定 void sleep(void*, struct spinlock*); ptable.lock で sleep() 呼ぶのは wait() のみ 12/09/02 xv6 scheduler part1 9
Scheduling ? ptable.lock acquire() ? release() process(kernel space) scheduler yield() { sched() { scheduler() { acquire(ptable.lock); ... … sched(); swtch(); for(p = ptable.proc; …) { ... ... ここに …. 戻る } } swtch(); … } release(ptable.lock); } 12/09/02 xv6 scheduler part1 10
Scheduling ー scheduler thread ● swtch() による CPU 解放 Kernel thread: scheculer() から process: sched() から ● forkret() のみ swtch() によらないスケジューリング cf. Chapter 1 プロセス生成 forkret() → forkret1() → trapret() 12/09/02 xv6 scheduler part1 11
Scheduling - scheduler() For(;;) { 割込み許可 ptable.lock 取得 実行するプロセスを探す (proc[] の探索 ) プロセスが止まるまで走らせる ptable.lock 解放 } 12/09/02 xv6 scheduler part1 12
Scheduling – scheduler() 実行可能プロセス探索 1.p->state == RUNNABLE を探す 2.見つかったら (CPU 毎に ) – proc にプロセス情報をセット – switchuvm() - プロセスページ切替 – p->state = RUNNNING – swtch() 12/09/02 xv6 scheduler part1 13
Scheduling – scheduler() lock について ● Schesuler() が ptable.lock を保持することは、 RUNNABLE プ ロセスが見つからない場合のように CPU アイ リ ド ングの特殊な ケースで重要である ● もし、アイドリング CPU のスケジュ ラが lock を継続的に保 ー 持してループしていれば、プロセスが動作している他の CPU ではコンテキスト切替やプロセス関連のシステムコールを実 行できない。つまり 他 CPU がプロセス状態を RUNNABLE に変 、 更することはできない。 ● 周期的に割り み許可するのは、 ー プロセスが IO を待っているた め 12/09/02 xv6 scheduler part1 14
Scheduling ー プロセス状態の保持と lock ● プロセス状態の一貫性 – プロ セスページテーブ ル – プロ セスカ ーネルスタ ッ ク – cpu->curproc が正しく proc[] を指している これを維持するため – ユーザースレッドで lock を取得 – スケジューラー又はカーネルスレッドで解放 ● あと プロセステーブルへの配置と 解放もあるよ wait→wakeup については注意な !( つづく ! かも ) 12/09/02 xv6 scheduler part1 15
“lost wake up” problem 12/09/02 xv6 scheduler part1 16

More Related Content

Kernel vm study_2_xv6_scheduler_part1_revised

  • 1. xv6 scheduler Part 1 ( 修正版 ) @noztos 2012.9.2 カーネル VM 勉強会 第二回 OS 基礎 (xv6)
  • 2. Scheduling ● ひとつの物理プロセッサを多重化する 複数の ( 仮想 ) プロ セッ サが存在する かのよ う に動作 ● ユーザープロセスに錯ーさせる – 専用のメモリ空間 – 専用プロセッサ 12/09/02 xv6 scheduler part1 2
  • 3. Multiplexing ● タイマ割込み 100ms( 固定 ) ● 多重化の実装 1.コンテキスト切り替え：標準的機構 2.透過的コンテキスト切り替え方法 : タイ ー割ーみハンド ( プリエンプティブ ) マ ラ 3.複数 CPU × マルチプロセスの同時実行 : 競合回避のための lock 4.プロセス終了時 : メモリ、リソースの解放 12/09/02 xv6 scheduler part1 3
  • 4. Context Switching 12/09/02 xv6 scheduler part1 4
  • 5. Context Switching ● Scheduler thread を必ず経由 プロセスから system call or interrupt ↓ scheduler ↓ 他プロセスへ trap return ● Scheduler thread は CPU 毎 ● 旧スレッドの register をセーブ 保存し て いた新スレ ッ ド の register をリストア cf. swtch.S 12/09/02 xv6 scheduler part1 5
  • 6. Context Switching - swtch() ● Thread について は知ら ず、 "contexts” を管理 す る のみ ● void swtch(struct context **old, struct context *new); # Save old registers # Load new registers movl 4(%esp), %eax movl 4(%esp), %eax # not 8(%esp) - popped return address above popl 0(%eax) # %eip movl %esp, 4(%eax) movl 28(%eax), %ebp movl %ebx, 8(%eax) movl 24(%eax), %edi movl %ecx, 12(%eax) movl 20(%eax), %esi movl %edx, 16(%eax) movl 16(%eax), %edx movl %esi, 20(%eax) movl 12(%eax), %ecx movl %edi, 24(%eax) movl 8(%eax), %ebx movl %ebp, 28(%eax) movl 4(%eax), %esp pushl 0(%eax) # %eip 12/09/02 xv6 scheduler part1 6
  • 7. Scheduling – sched() ● CPU を解放するには – ptable.lock を取得 – 取得している他の lock の解放 – 自身の proc->state の更新 – sched() の呼出 proc.c: yield(), sleep(), exit() からのみ ● sched() 内でもチェック + 割込み禁止確認 12/09/02 xv6 scheduler part1 7
  • 8. Scheduling – sched() を抜けるとそこは ● sched() において swtch() を呼ぶことにより proc->context(=current context) から cpu->scheduler(=scheduler context) へー身 ● “Scheduler context へ変身” ... ということは swtch() から戻るのは proc.c:scheduler() そして何事もなかったかのように RUNNABLE プロセスを探す proc.c: scheduler() 内 l.214 – l.231 12/09/02 xv6 scheduler part1 8
  • 9. Scheduling – ptable.lock ● swtch() を呼ぶ前に ptable.lock を取得 lock の取得、解放は thread の責任 – Unusual swtch() 中の proc->state, cpu->context の 整合性保持をシンプルに ● おまけ情報 カーネル空間で使用する sleep() は、引数で lock を指定 void sleep(void*, struct spinlock*); ptable.lock で sleep() 呼ぶのは wait() のみ 12/09/02 xv6 scheduler part1 9
  • 10. Scheduling ? ptable.lock acquire() ? release() process(kernel space) scheduler yield() { sched() { scheduler() { acquire(ptable.lock); ... … sched(); swtch(); for(p = ptable.proc; …) { ... ... ここに …. 戻る } } swtch(); … } release(ptable.lock); } 12/09/02 xv6 scheduler part1 10
  • 11. Scheduling ー scheduler thread ● swtch() による CPU 解放 Kernel thread: scheculer() から process: sched() から ● forkret() のみ swtch() によらないスケジューリング cf. Chapter 1 プロセス生成 forkret() → forkret1() → trapret() 12/09/02 xv6 scheduler part1 11
  • 12. Scheduling - scheduler() For(;;) { 割込み許可 ptable.lock 取得 実行するプロセスを探す (proc[] の探索 ) プロセスが止まるまで走らせる ptable.lock 解放 } 12/09/02 xv6 scheduler part1 12
  • 13. Scheduling – scheduler() 実行可能プロセス探索 1.p->state == RUNNABLE を探す 2.見つかったら (CPU 毎に ) – proc にプロセス情報をセット – switchuvm() - プロセスページ切替 – p->state = RUNNNING – swtch() 12/09/02 xv6 scheduler part1 13
  • 14. Scheduling – scheduler() lock について ● Schesuler() が ptable.lock を保持することは、 RUNNABLE プ ロセスが見つからない場合のように CPU アイ リ ド ングの特殊な ケースで重要である ● もし、アイドリング CPU のスケジュ ラが lock を継続的に保 ー 持してループしていれば、プロセスが動作している他の CPU ではコンテキスト切替やプロセス関連のシステムコールを実 行できない。つまり 他 CPU がプロセス状態を RUNNABLE に変 、 更することはできない。 ● 周期的に割り み許可するのは、 ー プロセスが IO を待っているた め 12/09/02 xv6 scheduler part1 14
  • 15. Scheduling ー プロセス状態の保持と lock ● プロセス状態の一貫性 – プロ セスページテーブ ル – プロ セスカ ーネルスタ ッ ク – cpu->curproc が正しく proc[] を指している これを維持するため – ユーザースレッドで lock を取得 – スケジューラー又はカーネルスレッドで解放 ● あと プロセステーブルへの配置と 解放もあるよ wait→wakeup については注意な !( つづく ! かも ) 12/09/02 xv6 scheduler part1 15
  • 16. “lost wake up” problem 12/09/02 xv6 scheduler part1 16