２章　プロセス管理と スケジューリング.

Presentation on theme: "２章　プロセス管理と スケジューリング."— Presentation transcript:

1 ２章　プロセス管理と スケジューリング

2 ２．プロセス管理とスケジューリング プロセスとスレッド 並列実行環境モデル ユーザレベルスレッド機構の実現方法 スケジューリング
プロセスの概念 スレッドの概念 並列実行環境モデル 概論 カーネルレベルスレッドモデル ユーザレベルスレッドモデル 協調型ユーザレベルスレッドモデル ユーザレベルスレッド機構の実現方法 単一プロセッサ上での実現 コンテキストの保存・回復機構の実現例 マルチプロセッサ上での課題と実現方法 スケジューリング スケジューリングにおける問題点 スケジューリングの分類 各種スケジューリング方式

3 プロセスとスレッド プロセスの概念 厳密な定義はない． 仮想プロセッサ 仮想プロセッサによって実行されているプログラム その他
プログラム実行環境 プログラム実行のための器 仮想プロセッサによって実行されているプログラム その他 ユーザの代理

4 プロセスとスレッド スレッドの概念 スレッドが注目されるまでの流れ ＵＮＩＸプロセス 並列処理の場合 １つのアドレス空間 １つの制御フロー
プログラムカウンタ，レジスタ内容 並列処理の場合 ＵＮＩＸでは，複数プロセス生成 アクティビティ間では，データ共有の場合が多い．

5 スレッド 制御フロー 狭義のコンテキスト プログラムカウンタ，レジスタ内容 仮想アドレス空間 仮想アドレス空間 スタック データ コード
スタック１ スタック２ データ コード SP SP1 スレッド１ SP2 コンテキスト スレッド２ pc1 PC pc2 （１）従来のプロセス （例：ＵＮＩＸ） （２）スレッド 図２．１　プロセスとスレッド

6 スレッドとプロセスの情報 ・プログラムカウンタ ・スタック ・レジスタの内容 ・子スレッド ・状態 ・仮想アドレス空間 ・大域変数
・開いたファイル ・子プロセス ・タイマー ・シグナル ・セマフォ ・アカウント情報 （１）スレッド （２）プロセス 図２．２　スレッドとプロセスの情報

7 並列実行環境モデル 概論 一般的な並列実行環境モデル ＵＮＩＸ上での実行 軽い実行環境の必要性 図２．３ 図２．４
複数ＵＮＩＸプロセスの生成 複数ＵＮＩＸプロセスの通信・同期方法 メッセージ通信 共有メモリ空間を張る． ＵＮＩＸプロセスのオーバヘッド 軽い実行環境の必要性 図２．５ スレッドの提供

8 ユ｜ザ空間 カ｜ネル空間 ＶＰ ＶＰ ＶＰ ＰＰ ＰＰ ＰＰ 図２．３ 並列実行環境モデル ユーザプログラム ＡＴ ＡＴ ＡＴ
生成（ユーザまたは言語処理系が行う） ＡＴ ＡＴ ＡＴ：アクティビティ ＡＴ マッピング カーネルインタフェース カ｜ネル空間 ＶＰ ＶＰ ＶＰ ＶＰ：仮想プロセッサ マッピング （カーネル空間にあるスケジューラが行う） ＰＰ ＰＰ ＰＰ ＰＰ：物理プロセッサ 図２．３　並列実行環境モデル

9 プロセス１ スタック データ コード プロセス２ スタック データ コード プロセス３ スタック データ コード
メッセージ通信 （１）メッセージ通信を用いる方法 プロセス１ スタック データ コード プロセス２ スタック データ コード プロセス３ スタック データ コード 共　有　メ　モ　リ （２）共有メモリを用いる方法 図２．４　ＵＮＩＸにおける並列処理

10 仮想アドレス空間 スレッド スレッド 通信 スレッド 図２．５　スレッドを用いた並列処理

11 各種スレッドモデル どのレベルでスレッドを提供するか？ カーネルレベルで提供 ユーザ空間で提供 カーネルレベルスレッドモデル
ユーザレベルスレッドモデル 協調型ユーザレベルスレッドモデル

12 カーネルレベルスレッドモデル カーネルがスレッドを提供 利点 欠点 図２．６ 仮想プロセッサがスレッド ＵＮＩＸの自然な拡張
ユーザアクティビティの挙動が把握しやすい． 欠点 高い性能を引き出せない． アクティビティの操作は，システムコール 柔軟性に欠ける． カーネルが規定したスレッドモデルに合わせたプログラミングをユーザに強要． 固定されたスケジューリング方式 オーバスペックになりやすい． より多くのスレッドモデルの包含

13 図２．６ カーネルレベルスレッドとユーザレベルスレッド
ユ｜ザ空間 ＡＴ：アクティビティ ＶＰ：仮想プロセッサ ＰＰ：物理プロセッサ ＴＨ：スレッド ＡＴ ＡＴ ＡＴ １対１のマッピング カーネルインタフェース カ｜ネル空間 ＶＰ ＶＰ ＴＨ（＝ＶＰ） カーネル・ スケジューラ カーネル・スケジューラ によるマッピング ＰＰ ＰＰ ＰＰ 図２．６（１）　カーネルレベルスレッドモデル 図２．６　カーネルレベルスレッドとユーザレベルスレッド

14 ユーザレベルスレッドモデル 図２．６（２） ユーザ空間でスレッドを管理する． 利点 欠点 スレッド生成，消滅，．．． スレッド操作が速い．
ユーザ空間で実現 関数呼出し程度の速度 欠点 仮想プロセッサのマッピング状況が把握できない． 仮想プロセッサのブロック カーネル空間実行中のブロック 入出力関連のシステムコール実行中 ユーザ空間実行中のブロック ページフォールトなど 仮想プロセッサの横取りの弊害 実行可能スレッドが実行できない． スレッドの同時実行が保証できない．

15 図２．６ カーネルレベルスレッドとユーザレベルスレッド
ユ｜ザ空間 ＡＴ：アクティビティ ＶＰ：仮想プロセッサ ＰＰ：物理プロセッサ ＴＨ：スレッド ＡＴ ユーザ・ スケジューラ ＡＴ ＡＴ ユーザスケジューラによるマッピング （多対１） カーネルインタフェース カ｜ネル空間 ＶＰ ＶＰ ＶＰ カーネル・ スケジューラ カーネル・スケジューラ によるマッピング ＰＰ ＰＰ ＰＰ 図２．６（２）　ユーザレベルスレッドモデル 図２．６　カーネルレベルスレッドとユーザレベルスレッド

16 協調型ユーザレベルスレッドモデル 仮想プロセッサのマッピング状況をユーザ空間へ通知 利点 欠点 スケジューラアクシベーション
ユーザ空間　→　カーネル空間：システムコール カーネル空間　→　ユーザ空間：マッピング状況 利点 両モデルの長所を採用 カーネルレベルスレッド：　機能性 ユーザレベルスレッド：　柔軟性 欠点 カーネルの再構築に多大な労力 スケジューラアクシベーション スケジューラアクティベーションの動き ユーザスレッドを実行するコンテキストの提供 カーネル内イベントをユーザ空間に通知 ブロックされたときのコンテキストを提供 通常のユーザレベルスレッドとの違い 仮想プロセッサのブロック時の対処法 図２．７ 表２．１

17 図２．７ ２つのユーザレベルスレッドモデル（ページフォールト時の処理）
ユ｜ザ空間 仮想アドレス空間 仮想アドレス空間 ＡＴ２ ＡＴ１ ＡＴ２ ＡＴ１ ページフォールト 発生後 （１）マッピング カ｜ネル空間 ＶＰ１ ＶＰ１ モジュール マッピングを解除してＡＴ１，ＶＰ１を事象待ちにするのみ（ＰＰがアイドルになる） マッピング （１）マッピング （２）ページフォールト ＰＰ ＰＰ 図２．７（１）　ユーザレベルスレッドモデル 図２．７　２つのユーザレベルスレッドモデル（ページフォールト時の処理）

18 図２．７（２） 協調型ユーザレベルスレッドモデル
仮想アドレス空間 ユ｜ザ空間 仮想アドレス空間 ＡＴ２ 実行時 ルーチン ＡＴ２ ＡＴ１ ＡＴ１ ページフォールト 発生後 （５）マッピング （１）マッピング （４）通知 カ｜ネル空間 ＶＰ１ ＶＰ１ ＶＰ１ モジュール マッピング （１）マッピングを解除 （１）マッピング （２）ＶＰ２を作成 （３）マッピング （２）ページフォールト モジュール ＰＰ ＰＰ 図２．７（２）　協調型ユーザレベルスレッドモデル 図２．７　２つのユーザレベルスレッドモデル（ページフォールト時の処理）

19 スケジューラアクティベーション 表２．１ スケジューラアクティベーションにおけるインタフェース
表２．１　スケジューラアクティベーションにおけるインタフェース （a）スケジューラアクティベーションからユーザ空間（アップコール） （（）内はユーザレベル・スレッドシステムがとるアクション） Add this precessor（プロセッサ番号）： ｛実行可能なユーザレベル・スレッドを実行する．｝ Processor has been preempted（横取りされたアクティベーション番号，マシン状態）： ｛横取りされたアクティベーション上で実行されていたユーザレベル・スレッドをレディキューにつなぐ．｝ Scheduler activation has blocked（ブロックされたアクティベーション番号） Scheduler activation has unblocked（ブロック解除されたアクティベーション番号，マシン状態）： ｛ブロックされていたアクティベーション上で実行されていたユーザレベル・スレッドをレディキューにつなぐ．｝ （b）ユーザ空間からカーネル（システムコール） （（）内はカーネルがとるアクション） Add more precessors（必要なプロセッサ数）： ｛プロセッサを当該ユーザ空間に割当てて，割当てられたプロセッサでアクティベーションを実行する．｝ This processor is idle（）： ｛他のユーザ空間がプロセッサを必要としていたら，当該プロセッサを横取りしてそのユーザ空間に割当てる．｝

20 ユーザレベルスレッド機構の実現方法（１／４）
単純なユーザレベルスレッド 単一プロセッサ上での実現 実現上の課題 コンテキストスイッチング １）アセンブリ言語による実現 高速 プロセッサの知識が必要で，実現が面倒 移植性が悪い． ２）システム提供の汎用的機構を用いる． 高速性？ 移植性，汎用性が高い． 例：ＵＮＩＸのsetjmp, longjmp関数

21 ユーザレベルスレッド機構の実現方法（２／４）
スタックの確保領域 １）データ領域 静的データ領域 静的にしか確保できないので，スレッド数が制限される． スタックのオーバフローが検出できない． ２）ヒープ領域 動的に確保 ＵＮＩＸのmalloc関数 スタックのオーバフロー検出機構が必要 ３）共有メモリ システムがサポートしている共有メモリ

22 ユーザレベルスレッド機構の実現方法（３／４）
スタックの初期設定 スタックポインタをスタックボトムに設定 １）直接的方法 アセンブリ言語による直接設定 プロセッサ，アセンブリ言語の知識が必要 ２）間接的方法 カーネル提供の機構を用いる． setjmpを用いた後，スタックポインタをＣ言語で書き換える． シグナルハンドラ用の機構を利用 ＢＳＤ系のsigstackシステムコール

23 ユーザレベルスレッド機構の実現方法（４／４） ーＵＮＩＸ上の簡単な実現例ー
UNIX上の機構 関数間のジャンプ setjmp, longjmp関数 プログラムカウンタ，スタックポインタ，レジスタの保存・回復を実現 setjmpの仕様 setjmp(env) env: システムが定義している構造体 jmp_bufの構造体 コンテキストを構造体envに保存 返り値 setjmp, longjmpの実行に依存する． setjmpを実行した場合：０ longjmpからのリターンの場合（引数val）:　val（≠0） longjmpの仕様 longjmp(env, val) 構造体envを復元 longjmpを実行すると，対応するsetjmpに制御が移る． setjmpの返り値は，val

24 スレッドa スレッドb （１）コルーチン実行例 図２．８　コルーチンの実現例

25 スレッドa スレッドb （２）コルーチン実現方法例 図２．８ コルーチンの実現例 Yes No Yes No Yes No Yes No
setjmp(env_a)=0　? スレッドb用のスタックに切換え スレッドbに制御を移す． No Yes longjmp(env_a,1) setjmp(env_b)=0　? No setjmp(env_a)=0　? Yes longjmp(env_b,2) No Yes longjmp(env_a,1) setjmp(env_b)=0　? No setjmp(env_a)=0　? Yes longjmp(env_b,2) No （２）コルーチン実現方法例 図２．８　コルーチンの実現例

26 コンテキストの保存・回復機構の実現（１／３）
対象 _setjmp(env), _longjmp(env, val) シグナルマスクの保存・回復は行わない． MIPS R2000/R3000 表２．２，２．３参照 _setjmp, _longjmpのレジスタの用途 jmp_bufの先頭アドレス：　レジスタa0に格納 返り値：　レジスタv0に格納 jmp_bufに保存するコンテキスト内容 整数レジスタ _setjmpを呼び出したアドレス（リターンアドレス）が格納されているraレジスタ so-s8までのレジスタ スタックポインタが格納されているspレジスタ 浮動小数点レジスタ $ f20-$ f31までのレジスタ コプロセッサ内のレジスタ：制御レジスタ $31

27 コンテキストの保存・回復機構の実現（２／３）
表２．２　汎用（整数）レジスタ レジスタ名 ソフトウェア名（regdef.hから） 用途とリンケージ $0 値は常に0 $at or $1 アセンブラのために予約されている． $2…$3 v0-v1 式の評価，および整数型関数結果を保持するために使用される．ネストされた手続きを呼び出すときにスタティックリンクを渡すのにもし四される． $4…$7 a0-a3 整数型実引数の最初の４ワードをパスするのに使用される．その値は，手続き呼出しには保存されていない． $8…$15 t0-t7 式の評価に使用されるテンポラリレジスタ．その値は，手続き呼出しには保存されていない． $16…$23 s0-s7 セーブされたレジスタ．その値は，手続き呼出しに保存されていなければならない． $24…$25 t8-t9 $26…$27 or $kt0…$kt1 k0-k1 オペレーティングシステムのカーネルのために予約されている． $28 or $gp gp グローバルポインタを含む． $29 or $sp sp スタックポインタを含む． $30 s8 セーブされたレジスタ $31 ra 式評価に使用される戻りアドレスを含む．

28 コンテキストの保存・回復機構の実現（３／３）
表２．３　浮動小数点レジスタ レジスタ名 用途とリンケージ $f0…$f2 浮動小数点型関数結果（$f0）および複素数型関数結果（$f1が実数部を，$f2が虚数部を持つ）を保持するために使用される． $f4…$f10 式の評価に使用されるテンポラリレジスタで，その値は手続き呼出しには保存されない． $f12…$f14 最初の２個の単精度または倍精度の実引数を渡すのに使用され，その値は手続き呼出しには保存されない． $f16…$f18 $f20…$f30 セーブされたリレジスタで，その値は，手続き呼出しには保存されていなければならない．

29 実現（１／２） NetBSDでの実現 jmp_buf内の対応関係 jmp_buf[3]: マジックナンバ（≠0）格納 _setjmpの処理
図２．９参照 jmp_buf[3]: マジックナンバ（≠0）格納 _longjmpでコンテキスト回復時のチェック jmp_bufに_setjmpによってコンテキストが保存されているかどうか 保存されている場合には，マジックナンバが入っている． _setjmpの処理 Raレジスタ，マジックナンバ，so-s8レジスタ，spレジスタ，$ f20-f31レジスタ，$ 31を，jmp_bufに格納 返り値をレジスタv0に格納 レジスタraで指定されたアドレスのジャンプする． _longjmpの処理 Jmp_bu[3]がマジックナンバと一致しているかチェック 一致していれば，jmp_bufの内容を対応レジスタにロード レジスタa1で渡された返り値をレジスタv0に格納 レジスタraで指定されたアドレスにジャンプ

30 実現（２／２） 未使用 1 2 ra 3 マジックナンバ 4 | 18 19 s0 20 s1 21 s2 22 s3 23 s4 24 s5 25 s6 26 s7 27 31 32 spa 33 s8 34 未使用 | 57 58 $f20 59 $f21 60 $f22 61 $f23 62 $f24 63 $f25 64 $f26 65 $f27 66 $f28 67 $f29 68 $f30 69 $f31 70 コプロセッサ内の$31 図２．９　_setjmp, _lonhjmpにおけるjmp_bufとコンテクストの対応（MIPS R3000, NetBSDの場合）

31 マルチプロセッサ上の課題と実現方法（１／３）
複数の仮想プロセッサの割当て方法 ２つの空間 応用プログラムが実行していると思っている空間U 仮想プロセッサが走る仮想アドレス空間K 図２．１０参照 空間の一致問題 空間U　＝　空間K K1=K2=．．． 単一プロセッサの場合を流用 K1=K2=… Machでは仮想プロセッサはスレッド スレッドは空間共有なので，問題なし UNIXの場合 共有メモリのシステムコールを提供 IRIS OS：　m_forkシステムコール

32 マルチプロセッサ上の課題と実現方法（２／３）
応用プログラムの仮想アドレス空間U スレッド ユーザ空間 スレッド スレッド VP1 VP2 カーネル空間 vpi　：　仮想プロセッサ 図２．１０　仮想プロセッサの空間とユーザレベルスレッドの空間 仮想アドレス空間K

33 マルチプロセッサ上の課題と実現方法（３／３）
応用プログラムの仮想アドレス空間U 応用プログラムの仮想アドレス空間U スレッド スレッド ユーザ空間 ユーザ空間 スレッド スレッド スレッド スレッド マッピング マッピング VP1 VP2 VP1 VP2 カーネル空間 カーネル空間 仮想アドレス空間K 仮想アドレス空間K１ 仮想アドレス空間K２ vpi　：　仮想プロセッサ 異なる空間 （１）Machの場合 （２）UNIXの場合 図２．１１　MachとUNIX

34 排他制御の問題（１／２） スケジューラの操作 上記操作をどのコンテキストで行うか？（どのスタックを用いるか）
１）実行スレッドのコンテキスト保存（setjmpを使用） ２）実行スレッドをレディキューに連結（エンキュー） ３）レディキューからスレッド選択（デキュー） ４）選択スレッドのコンテキスト復元（longjmpを使用） 上記操作をどのコンテキストで行うか？（どのスタックを用いるか） 実行スレッドのコンテキストで行う場合 実行スレッドのスタックを用いる． 状況：図２．１２（１） 結果 図２．１２（２） 同一のスタックを用いることになる スタックが破壊される可能性あり． スケジューラ用のスタックを用いる必要あり．

35 排他制御の問題（２／２） 図２．１２ 使用コンテクスト例 （１）状況図 （２）実行系列例 VP1 VP2 スレッドaのコンテクスト
スレッドbのコンテクスト スレッドa 仮想 プロセッサ VP1 スレッドb 仮想 プロセッサ VP2 レディキュー setjmp(old -> context) スピンロック ①エンキュー enqueue(old) デキューしようとしてスピンして待つ． ②new = deeue(old) デキュー new = dequeue() ③longjmp(new -> context) longjmp(new -> context) （１）状況図 ④同じスタックを用いることになる． （２）実行系列例 図２．１２　使用コンテクスト例

36 スケジューリング スケジューリングにおける問題点 考慮すべきオーバヘッド 単一プロセッサスケジューリングの問題点 同期に伴うオーバヘッド
ロックの獲得 生産者／消費者問題 コンテキストスイッチングのオーバヘッド レジスタの回復・復元 重いプロセスの場合 空間切り替えのオーバヘッド キャッシュ，TLBのミスヒット メモリアクセスのオーバヘッド NUMAアーキテクチャ 単一プロセッサスケジューリングの問題点 ラウンドロビン，優先度方式，．．． プロセス（スレッド）の協調動作を考慮していない．

37 スケジューリングの分類 スケジューリング資源からの分類 プロセッサ割当時期からの分類 時間資源と空間資源 時分割方式 空間分割方式 静的方式
動的方式 プロセスＡ プロセスＢ プロセスＣ プロセスＡ プロセスＣ プロセスＢ プロセッサ プロセッサ 時間 時間 （１）時分割方式 （２）空間分割方式 図２．１３　スケジューリングの基本的分類

38 各種スケジューリング方策 コスケジューリング キャッシュアフィニティスケジューリング 同期を考慮したスケジューリング
応用プログラムにヒントを与えるスケジューリング プロセスコントロールスケジューリング ２レベルスケジューリング メモリアフィニティスケジューリング

39 コスケジューリング（１／５） マルチプロセッサCm*上のMedusa OSに採用．先駆的方式 方式 行列を用いた方式（基本的）
連続アルゴリズム 非分割アルゴリズム 2 × 1 △ ○ 列／行 プロセッサ0 プロセッサ1 プロセッサ2 プロセッサ3 ○，△，×：タスクフォース 図２．１４ コスケジューリング （a）行列を用いた方法

40 コスケジューリング（２／５） プロセッサ 1 2 3 スロット 4 5 6 7 8 9 10 11 プロセス ○ △ × □ ◎ ウインド
1 2 3 スロット 4 5 6 7 8 9 10 11 プロセス ○ △ × □ ◎ ウインド （ｂ） 連続アルゴリズム 図２．１４ コスケジューリング

41 コスケジューリング（３／５） プロセッサ 1 2 3 スロット 4 5 6 7 8 9 10 11 プロセス ○ △ × □ ◎ ウインド
1 2 3 スロット 4 5 6 7 8 9 10 11 プロセス ○ △ × □ ◎ ウインド （ｃ）非分割アルゴリズム 図２．１４ コスケジューリング

42 コスケジューリング（４／５） プロセッサ 1 2 3 スロット 4 5 6 7 8 9 10 11 プロセス ○ × △ □ ◎ ●
1 2 3 スロット 4 5 6 7 8 9 10 11 プロセス ○ × △ □ ◎ ● ウインド （a）同時実行されなかったタスクフォースへ移動する方法 図２．１５ 　ウインドウの移動方法

43 コスケジューリング（５／５） プロセッサ 1 2 3 スロット 4 5 6 7 8 9 10 11 プロセス ○ × △ □ ◎ ●
1 2 3 スロット 4 5 6 7 8 9 10 11 プロセス ○ × △ □ ◎ ● ウインド （ｂ）次タスクフォースへ移動する方法 図２．１５ 　ウインドウの移動方法

44 キャッシュアフィニティスケジューリング（１／４）
キャッシュに残留している可能性の高いプロセッサ，スレッドを考慮 キャッシュの残留度をどうやって測定？ ラストプロセッサ方式（last processor） ラストプロセッサ：　プロセスが自分が最後に実行されたプロセッサ スレッドからみると ラストプロセッサに割当て プロセッサからみると 自分がラストプロセッサとなっているスレッドを実行 最小介入数方式（minimum intervening） 介入数の少ないプロセッサ 介入数＝（プロセッサ，プロセス） 限定最小介入数方式（limited minimum intervening） 記憶数を制限した最小介入数方式

45 キャッシュアフィニティスケジューリング（２／４）
プロセッサ A 割当て レディキュー プロセスa B プロセスb A プロセスc B ラストプロセッサ （１）ラストプロセッサ方式 図２．１６ 　キャッシュアフィニティスケジューリング

46 キャッシュアフィニティスケジューリング（３／４）
プロセッサ A ①アイドル ②割当て 　プロセスa A ５ B ２ C １ 　プロセスb A ２ B ４ C 　プロセスc A ３ B １ C ４ レディキュー 介入数 （a）プロセッサAのアイドル時 アイドルプロセッサ 　プロセスa A ５ B ２ C １ レディキュー A ②割当て B （２）最小介入数方式 介入数 図２．１６ 　キャッシュアフィニティスケジューリング ①連結 C （b）プロセスaのレディキューへの連結時

47 キャッシュアフィニティスケジューリング（４／４）
プロセッサ A ②割当て 限定数＝２ ①アイドル 　プロセスa A ３ C １ 　プロセスb A ２ B ３ 　プロセスc B ３ C ２ レディキュー 介入数 （a）プロセッサAの情報を持っている場合 プロセッサ D 限定数＝２ ①アイドル 　プロセスa A ３ C １ 　プロセスa D ０ C １ ②割当て 　プロセスb A ２ B ３ 　プロセスc B ３ C ２ レディキュー （３）限定最小介入数方式 図２．１６ 　キャッシュアフィニティスケジューリング サービス修了後，（A,3）を（D,０)に書き換える （ｂ）プロセッサDの情報を持っていない場合

48 同期を考慮したスケジューリング クリティカルセクション実行中のプロセッサ横取りを不可 ロック獲得待ちプロセスには，プロセッサを割り当てない．
ロック獲得方式の動的変更 スピンロックからサスペンドロックへ

49 応用プログラムにヒントを与えるスケジューリング
最適なスケジューリング方式は応用プログラムに依存 Mach OSのスケジューリングサポートヒント discourageヒント：　指定スレッドを実行すべきでないヒント Mildヒント：他スレッドが実行可能ならば，当該スレッドからプロセッサを解放 Strongヒント：　当該スレッドからプロセッサ解放，当該スレッドの優先度を下げる． Absoluteヒント：　指定した時間，当該スレッドをブロックする． ロック獲得スレッドが分からない場合に有効 Handoffヒント：スケジューラを介することなしに，指定スレッドに制御を移す． スレッドブロックさせているスレッドの起動に有効 メッセージ通信機構に多用

50 プロセスコントロールスケジューリング 実行可能プロセス数を物理プロセッサ数程度に制限 仮想プロセッサ数を制御するためには？ 実現方法
同時に実行できるプロセス数は，高々物理プロセッサ数 プロセス数増大　→　性能低下 仮想プロセッサ数を制御するためには？ 実行可能プロセス数の把握 応用プログラムごとの実行プロセス数の決定 プロセス数の調整 実現方法 ２つの実現レベル カーネル空間 ユーザ空間 ユーザ空間での実現 ユーザレベルスレッド 調整サーバ

51 ２レベルスケジューリング（１／２） 空間分割方式の一つ ２つのスケジューラ 特徴 応用プログラムごとのスケジューリング システム全体の調整
グローバルスケジューラ カーネル空間で実現 プライベートスケジューリング ユーザ空間で実現 特徴 応用プログラムごとに適したスケジューリング方式の選択 スケジューラボトルネックの緩和 キャッシュの活用

52 ２レベルスケジューリング（２／２） 方式内の選択肢 プロセッサグループ分割時期 アイドルプロセッサ処理方式 フリープロセッサ割当方式
静的 動的 アイドルプロセッサ処理方式 解放方式 保持方式 フリープロセッサ割当方式 待ちプロセス優先方式 実行プロセス優先方式 フリープロセッサ選択方式 どのフリープロセッサから割り当てるか？ キャッシュなどを活用

53 メモリアフィニティスケジューリング コード／データのメモリ場所を考慮 ＮＵＭＡマルチプロセッサ ２レベルスケジューリングと併用 追加選択肢
メモリアクセスの高速化 キャッシング技法の採用 フリープロセッサの選択順序 ホームプロセッサ：オリジナルコード／データ ローカルプロセッサ：コピー その他

54 以上