スレッドとプロセス 本題: スケジューリング

Presentation on theme: "スレッドとプロセス 本題: スケジューリング"— Presentation transcript:

1 スレッドとプロセス 本題: スケジューリング
田浦健次朗

2 スレッド・プロセスの目的 CPUを仮想化 物理的なCPU数は固定, 少数 ラップトップ, スマホ: 1, 2, 4, 8くらい
サーバ: 数十 ポイント: にもかかわらず数十, 数百のプログラムを立ち上げることができる 個々のプログラムを書く人が明示的な「譲り合い」をする必要はない

3 スレッドとは? 制御の流れ(thread of control) OSに「スレッドを作りたい」と要求 OSはスレッドにCPUを割り当て，実行
スレッドは「たくさんあってよい」 OSが交互に実行 CPUが複数あれば各CPU上で

4 プロセスとは?  プログラムの起動したときにできるもの プロセス=論理アドレス空間+(1つ以上の)スレッド 論理アドレス空間の生成
+mainスレッドの生成 プロセス=論理アドレス空間+(1つ以上の)スレッド

5 実践的知識 システム内のプロセス・スレッドの観察 自分のマシンには何個くらいプロセス, スレッドが走っているでしょう?
Linux : ps, top, htop, システムモニタ Windows : タスクマネージャ, perfmon 自分のマシンには何個くらいプロセス, スレッドが走っているでしょう?

6 スレッド・プロセス関係API 共通な主要概念 代表的スレッドAPI名 代表的プロセスAPI 生成，終了 同期，実行の制御
Unix: POSIX Threads (pthread) Windows: Win32 thread 代表的プロセスAPI POSIX Win32

7 まめ知識: APIの調べ方 Unix : man API名 Windows : MSDN Emacs : M-x man
webまたはVisual Studio

8 プロセス生成 Win : CreateProcess(file, cmd, …, &pid);
Unix : pid = fork(); /* プロセス複製 */ if (pid == 0) { /* 子プロセス */ execv(file, cmdline); /* fileを実行 */ } else { /* 親プロセス */ }

9 プロセス終了 Win : ExitProcess(s); Unix : exit(s);
またはプログラムのmain関数が終了したとき，自動的に終了

10 プロセス終了待ち プロセスpidが終了するのを待つ 実例 Win : WaitForSingleObject(pid, timeout)
Unix : wait(&status), waitpid(pid, &status, …);

11 いわゆる「シェル」の動作 エラー処理などを除いた, コマンドシェル(bashなど)の議事コード
while (…) { show_prompt(); char ** cmd = read_command(); int cid = fork(); if (cid == 0) { file = search_PATH(cmd[0]); execv(file, cmd); } else { waitpid(pid, &status); } }

12 高水準なAPI system(command_string) popen(command_string)
command_stringを実行するプロセスを作り, 終了を待つ ( fork + exec + wait) popen(command_string) command_stringを実行するプロセスを作り, そのプロセスと通信するチャネル(パイプ)を返す(パイプ作成 + fork + exec) すべて最終的にはfork, exec, waitpid, etc.の組み合わせ(Unixの場合)

13 スレッド生成 基本: 実例 命令列が始まるアドレスを指定．そこから実行を開始するスレッドを生成 命令列のアドレス: Cの関数ポインタ
Pthread : pthread_create(&id, .., f, x) Win : CreateThread(.., .., f, x, .., &id) f(x) を実行するスレッドを生成．スレッド名をidに格納

14 スレッド終了 スレッドの終了 実例 Pthread : pthread_exit(s) Win : ExitThread(s)
または生成時に指定された関数fが終了すると自動的にスレッドが終了する s : status

15 スレッドの終了待ち スレッドidが終了するのを待つ(idはpthread_createなどによって得られたスレッド名) 実例
Pthread: pthread_join(id, &return_status) Win: WaitForSingleObject(id, timeout) その他の同期方法は後述 pthread_create pthread_join pthread_exit

16 そのほかの言語 ほとんどの言語(Java, C++, Python, etc.)でスレッド, プロセス関係のAPIが提供されている
(名前は違うが)概念は似ている 多くの場合C用のライブラリ, それが最終的には fork, exec, etc.を呼び出している(Unixの場合)

17 プロセスとスレッド スレッドとプロセスは似ているようだが何が違う? 現時点では, 正確な違いは数週間後, メモリについて語るときにわかる
スレッド: 一筋の実行の流れ プロセス: 「プログラムを起動したときにできるもの」 1個以上任意個のスレッドを含む「箱」 mainを実行するスレッドは自動的に含まれる

18 しかし両者の境界は曖昧で，厳密に区別する意味もそれほどない(要するにあまり気にしなくていい)
まめ知識(言葉の問題) システムコール vs ライブラリ システムコール: 厳密には，トラップ命令によって突入する，OSカーネル内の手続き ライブラリ: (時にシステムコールを使いながら)ある機能を提供する手続き．まったくシステムコールを使わないものもある しかし両者の境界は曖昧で，厳密に区別する意味もそれほどない(要するにあまり気にしなくていい) mallocはシステムコール? printfはシステムコール? readはシステムコール? APP ライブラリ OSカーネル

19 スケジューリング システム内には多数のスレッドが同時に存在する OSはそれらに「適切に」CPUを割り当てる(スケジューリング)必要がある
基本: 変わりばんこ

20 スレッドスケジューリングの目標 公平性 効率性 対話的プログラムの応答性 独占の禁止 公平なCPUの割り当て
スレッド切り替えのオーバーヘッドを少なくする 対話的プログラムの応答性

21 スケジューラの挙動観察実験(1) いくつかのスレッド(プロセス)を立ち上げる スレッドがいつからいつまで「実行中だったか」を調べる 注目
「時刻を知るシステムコール」 注目 どのくらいの頻度でスレッドは入れ替わっているか? その状態でエディタやブラウザの応答性に影響は?

22 スケジューラの挙動観察実験(2) 各スレッド f (x) { t =現在時刻(); while (1) { t’ = 現在時刻(); if (t’ – t > 1ms) { 記録(); } t = t’; } 記録を出力; }

23 注目 スレッド数を変えて実験してみる エディタなど，対話的なプログラムを並行して走らせみる

24 ヒント: 時刻を知るシステムコール UNIX : gettimeofday Win : QueryPerformanceCounter
man gettimeofday Win : QueryPerformanceCounter MSDNライブラリで検索 授業のHPに例題掲載

25 特定のCPUへスレッドを固定する システムコール コマンド sched_setaffinity(pid, size, mask)
mask : size bitのbit列 maskで1となっているCPUでのみ, pidを実行 子プロセスへ自動的に継承 コマンド taskset –c 0,1 command

26 スレッドスケジューラの実現

27 クイズ あなたが無限ループするプログラムを書いてもマウスが動き, ブラウザが動き, Ctrl-Cで消せる(事もある)のはなぜですか?
(a) マウスはプログラムで動いているわけではないから (b) マシンにCPUコアが2個(以上)あるから(ブラウザと無限ループは別のコアで動いている) (c) 実は無限ループであってもC言語処理系が時々他のスレッドに譲るような機械語に変換しているから (d) その他

28 復習: OSのないCPU CPUの状態：レジスタ CPUの動作: 汎用 プログラムカウンタ(PC) モード(ユーザモード・特権モード)
etc. CPUの動作: 以下を永遠に繰り返す { PCが指す場所の命令を取り出す 命令を実行(状態書き換え) } 外部割込みが発生していれば割り込み処理

29 もし割り込みがなかったら? 以下のようなプログラム(無限ループ)がCPUを独占するのを防ぐ方法はない C: for (;;) { }
機械語: L: jmp L

30 割り込み処理 割り込み: CPU外部からの信号 割り込み時にCPUが行うこと
if (その割り込み許可中) { 割り込みを禁止にする; 一部の状態(割り込み発生時PCなど) を特定のレジスタに保存; 割り込みベクタを参照し，指定されてい る値をPCに設定(制御の移動)； 特権モードへ移行; } IRQ Line

31 割り込みベクタ 割り込みハンドラ アドレス 割り込みベクタレジスタ (trap base register) メモリ TBR 割り込みベクタ
0x1234 0x1288 IRQ番号 0x1346 0x1390 割り込みベクタ 0x1432 … 0x2084

32 割り込みベクタ 通常OSの起動時に設定される IRQ通常の用途 各種入出力装置からの通知 キーボード，ネットワークコントローラ，etc.
タイマ!! システムコール(トラップ命令)

33 タイマ割り込み CPUの独占を防ぐための鍵 通常定期的(1- 10ms 程度に一度程度)発生させる
Linux (2.4) on x86, Windows on x86, BSDなどで10ms Linux on Alpha 1ms Linux 以前 1ms, 4ms, または必要に応じて(tickless) タイマ割り込み間隔，クロック間隔，クロックチックなどと呼ぶ 必要な時にOSがCPUをアプリケーションから奪う「機会」を保障する

34 スケジューリングアルゴリズム

35 各スレッドの状態 生成  CPUの数 実行可 “reschedule” 実行中 (runnable, (running) active)
yield, “reschedule” 中断 (suspend, block) 中断からの復帰 (resume, unblock) 中断中 (blocked, suspended)

36 中断状態 (たとえCPUがあいていても)直ちに実行をすることができない状態 OSは中断状態のスレッドを(当然)CPU割り当ての対象から外す

37 中断と復帰 スレッドが中断する理由(代表例) 復帰の理由(中断の逆) 入出力待ち(recv, read, etc.)
自主的休眠(sleep) スレッド間の同期(pthread_join, wait, etc.) ページフォルト(後述) 復帰の理由(中断の逆) 入出力完了 休眠時間経過 スレッド間の同期成立 ページフォルト処理完了

38 実行可能キュー 実行可能スレッドのリスト OSは「機会あるごとに」，実行可能キューから最も適切なスレッドを選んで実行(reschedule)
「スケジューリングキュー」，「ランキュー」 スレッドが実行可能キューにある  そのスレッドが実行可能 OSは「機会あるごとに」，実行可能キューから最も適切なスレッドを選んで実行(reschedule)

39 中断 例: ネットワークからのデータ待ちによる中断
recv() { … if (読むべきdataがない) { 現スレッドを実行可能キューからはずす; reschedule(); } … }

40 中断からの復帰 例: ネットワークからのデータ到着による復帰
/* 割り込み  OS内のネットワークからの入力を 処理する部分 */ if (あるスレッドが今到着したデータ待ち) { そのスレッドを実行可能キューに入れる; 　reschedule(); }

41 Rescheduleの機会 OSカーネルが制御を得るあらゆる時点が，潜在的なrescheduleの機会 タイマ割り込み時 クロック間隔に一度
そのほかの割り込み(e.g, 入力)からの復帰時 実行中スレッドが中断したとき システムコールからの復帰時 etc.

42 Reschedule Rescheduleの機会をOSが得るたびに，「次に実行すべきスレッド」を選択して実行(CPUの割り当て)
次に実行すべきスレッドの選択の仕方が重要 公平 効率 対話的プログラムの応答

43 単純なスケジューラの例 Roundrobin (ラウンドロビン; 変わりばんこ)スケジューリング ポリシーの例:
定数 Q (time quantum; 例えば10程度) 1スレッドは最大Q clock ticksまで連続して実行許可 連続してQ clock ticks走ったら他のスレッドに交代

44 単純なラウンドロビン 方針: 最大Q clock ticksで実行中スレッドを切り替える オーバーヘッドを減らす(Qがある程度大)
実行可能なスレッドがnあるとき，各スレッドは高々(n – 1) * Q clock ticksで「自分の番」になる

45 単純なラウンドロビンの実装(1) 各スレッドにカウンタ(timeslice; 残り時間)を保持 0  c  Q
意味: (他のスレッドに順番をまわすことなく)自分があと，何clock tick実行し続けてよいか

46 単純なラウンドロビンの実装(2) タイマ割り込み時: t = そのとき実行中だったスレッド; tc--; if (tc == 0) reschedule(); else tを継続して実行 Reschedule() { if (すべての実行可能スレッドのtc == 0) { for (すべてのスレッドt) t->c = Q; /* リセット! */ } tc > 0なる適当な実行可能スレッドtを選び実行; }

47 単純なラウンドロビンスケジューラの挙動 すべてのスレッドが「決して中断しない」(＝常に実行可能な)場合 スレッド 時刻 タイマ割り込み
c=0 c=Q スレッド 時刻 タイマ割り込み reschedule カウンタリセット Epoch, Scheduler epochなどと呼ぶ

48 Unix nice値やWindowsのタスク優先度の効果
通常, time quantum (Q)を変える効果を持つ 例 Linux 2.6 通常(nice = 0) : 100ms 最低(nice = 19) : 5ms 最大(nice = –20) : 800ms 800ms 100ms 5ms nice値 –20 19

49 対話的なスレッドの応答性 エディタ，パワーポイント，ブラウザ，メーラに「キー入力」したらすぐに反応してほしい 対話的なスレッドの特徴
I/Oによる中断が非常に頻繁 キーボード，マウス，ネットワークなどの入力待ち 中断が多いため, CPU利用量は少ない

50 対話的スレッド存在下での単純なラウンドロビンスケジューラ
c=0 c=Q … スレッド 時刻 応答までの遅延 タイマ割り込み reschedule カウンタリセット 入力(resumeイベント) epochの最後まで待たされる可能性がある

51 単純なラウンドロビンの何がいけなかったか?
Reschedule() { if (すべての実行可能スレッドのtc == 0) { for (すべてのスレッドt) tc = Q; /* リセット! */ 　} tc > 0のtを選び実行; } 対話的なスレッドもそれ以外のスレッドも t->c > 0である限りすべて平等なのが問題

52 Linux 2.4 (and before)スケジューラ
Reschedule() { if (すべての実行可能スレッドのtc == 0) { for (すべてのスレッドt) tc = tc / 2 + Q; } tc が最大のtを選び実行; }

53 Windowsスケジューラ 復帰時に明示的に動的優先度をあげる キーボード入力だったら +5 など Priority Boost

54 現在のLinuxスケジューラ カーネル2.6.23以降. Completely Fair Scheduler (CFS)
各スレッドが使用したCPU時間を管理 vruntime (virtual runtime) Reschedule時には毎回, vruntimeが最小のスレッドを選ぶ  つまり最もCPUを使っていないスレッドを選ぶ  公平性の保証

55 vruntime管理の実際 スレッドが生まれたとき スレッドがA  Bに切り替わるとき 子は親のvruntimeを引き継ぐ
Aのvruntime += 今回消費した時間 Bのvruntime = 基本はそのまま. ただし, それだけだと問題がある

56 vruntime管理の実際 ABに切り替え時
Bのvruntime 何もしないが,  全スレッドのvruntimeの最小値 – 20 ms を保証 つまり長時間中断していてもその分をまるごと「貯金」はできない

57 Linux 2.6 O(1)スケジューラ(2.6.22まで) 基本はラウンドロビンだが, epoch更新時の操作を含め, 一回のスケジューリングのコストがプロセス数によらない(O(1)スケジューラ) スレッドがどのくらいの時間running/blockedであったか(sleep_avg)による優先度

58 O(1)スケジューラのroundrobin
Runnableなスレッドは二つの配列(active, expired)のどちらかに入る Expired :現epochにおいて自分のtime sliceを使い果たしたスレッド Active : まだtime sliceが残っているスレッド

59 O(1)スケジューラのroundrobinの実装(2)
タイマ割り込み時: t = そのとき実行中だったスレッド; tc--; if (tc == 0) reschedule(); else tを継続して実行 Reschedule() { t をactive配列からexpired配列へ移動; tc = Q; /* 次epoch用 */ if (active配列が空) { activeとexpiredをそっくり入れ替え; } active配列から最大優先度(後述)の tを選び実行; }

60 O(1)スケジューラでの優先度 よく blockするスレッドに高優先度 各スレッドが変数 sleep_avg をもつ
1 sec 0 sec

61 sleep_avgの意味 基本思想: sleep_avg が高いよくblockしている優先度を上げる
これまでCPUを使っていないのだから優先度を上げるのは理にかなっている 対話的スレッド(よくblockしている)の応答性を高める効果がある

62 sleep_avgの更新ロジック Running  runnable/blocked になるとき:
runtime = 今回走り続けた時間; sleep_avg = sleep_avg – runtime; if (sleep_avg < 0) sleep_avg = 0; Blocked  runnable になるとき: sleep_time = blockしていた時間; sleep_avg = sleep_avg + sleep_time; if (sleep_avg > max_sleep_avg) sleep_avg = max_sleep_avg;

63 sleep_avg の実際の使われ方(1) 優先度に反映(sleep_avgが大きければ優先度大 すぐにスケジュールされる)
runtime = 今回走り続けた時間; sleep_avg = sleep_avg – runtime / ; if (sleep_avg < 0) sleep_avg = 0; sleep_avgに応じて大きくなる値(1 – 10)

64 sleep_avgの実際の使われ方(2) 通常のスレッドは割り当てられたtime sliceを使い切ったら次epochまでスケジュールされることは決してない(expired配列へ格納される) sleep_avgが大きいスレッドは, 割り当てられたtime sliceを使い切ってもactive配列へ格納される! 対話的スレッドを優先しすぎ? 実はO(1)にこだわったツケ?

65 チャレンジ課題1 Linux 2.6のスケジューラについて調べよ(授業HPにポインタを掲載する) 文献とソースコードの両方を調べる
実験を行って挙動を確かめること 特に「対話的プログラム」に対する優先度の割り当て方法，およびそれを出し抜いて多数のCPU時間を割り当てる方法について考察・実験を行うこと デモを伴った発表

66 チャレンジ課題1 OSスケジューラを「だます」プログラムを書いてみよう N個の計算スレッド+1個のサギスレッド
N個の計算スレッドは計算only (ブロックしない) チャレンジ: サギスレッドをうまく工夫してなるべくたくさんのCPUを消費する Linux 2.4では簡単 + 過去の挑戦者によってやり尽くされた Linux 2.6, FreeBSD, Windowsなどで研究してください 各OSでスケジューラの挙動観察からはじめる Web, 本などでスケジューラの挙動を調べる

67 補足: いわゆる「優先度」 明示的に設定される優先度 動的優先度とは別物(間接的に影響はする) Windows : タスクマネージャ
Unix : スケジューリングクラス，nice/renice (システムコール, コマンド) 動的優先度とは別物(間接的に影響はする) Windows : 静的優先度ごとにqueue Linux : スケジューリングクラス(Realtime, Kernel, TimeSharing)ごとにqueue Nice 値は，スレッドごとにQの値を決める