森田/研究/Linuxカーネル解読室
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
#contents
---------------------
**第一章プロセススケジューリング [#g94d971e]
-参考URL
--http://d.hatena.ne.jp/naoya/20071010/1192040413 マルチスレッドのコンテキスト切り替えに伴うコスト
***1.1マルチタスク [#ce358dbc]
-複数のプロセスを同時に実行すること。
-実際は複数のプロセスを細かく切り替えながら動作させ、同時にプロセスを実行しているようにみせる。
***1.2プロセスとは? [#j8659492]
-プログラムが動いていること。プログラムが一つで、プロセスが複数あることがある。
-各々のプロセスは、それぞれ固有のコンテキストを持つ。
-Linuxカーネルでは、スレッドも一種のプロセスとして扱う。
--スレッド同士がプロセス空間を共有していることを除けば、通常のプロセスと同じ。
--スケジューリングの際も、スレッドはプロセスと同様の扱いでスケジューリングを行う。
***1.3プロセス切り替え [#sd2ef7fc]
-もともとCPU上で動作していたプロセスの実行を中断し、新しいプロセスの実行を開始すること。
-実際にプロセスはどう稼働しているか?
--用意されたプロセス空間上で走行している。
--変数の値はメモリもしくはレジスタ上に存在している。
--実行中の命令はプロセスカウンタレジスタが指している。
--利用中のスタックはスタックポインタが指している。
--プロセス空間そのものが、特殊レジスタによって管理されている。
-これらのレジスタ群を全て、切り替えするプロセスのレジスタ値で書きなおせば、プロセスの切り替えは完了する。
-その前に、今まで動いていたプロセスのレジスタ値を退避する必要がある。
-これらのレジスタ群の値のことをコンテキストと呼ぶ。実行待ちのプロセスはコンテキストをtask_struct構造体やカーネルスタックに退避しておき、実際に実行状態になるとCPU上に読み込む。
***1.4プロセスディスパッチャ [#zf72802d]
-1.4.1context_switch関数
--Linuxカーネルのプロセスディスパッチャのコードは、context_switch関数にある。以下の二つの処理から成る。
---プロセス空間の切り替え処理(swtich_mm関数)
---各種レジスタ切り替え処理(swtich_to関数)
-1.4.2swtich_toマクロ
--prevを今まで動作していたプロセス、nextを切り替えるプロセスとする
--EIPとESPの切り替えに注目
---EIP(Extended Instruction Pointer):命令ポインタ
---ESP(Extended Stack Pointer:スタックポインタ
--task_struct構造体に、EIP、ESPがそれぞれ格納される。
--switch_toマクロの動作概要
++prevで示されるプロセスのESPレジスタを退避、nextで示されるプロセスのESPレジスタを復帰することで、スタックの切り替えを実現。
++prevプロセスが次回動作時に、同じ場所から再開できるようにEIPレジスタを退避。プロセスnextの実行再開箇所は、nextのレジスタの退避域から取り出したEIPレジスタの値をスタック上に置いておく。
++__switch_to関数を呼び出した後、その関数から戻る時スタックに積んだEIPレジスタの値が自動的にCPUに読み込まれる。
---C言語でいう関数呼出はcallにあたりスタックに次の命令のポインタを保存し、、retするときにスタック上に積んである命令の場所に戻る。
---ここでは、直接jmp命令で__swich_to関数に飛び込むことで、retするとき次の命令はスタック上に積んだEIPレジスタの値であると信じこむ。
--例外あり。forkで生成された子プロセスや、カーネルスレッドはeipレジスタ退避域に直接特定のアドレスを書き込んで、退避していないのに、さも復帰したかのように動作する。
--switch_toマクロの3つ目の変数であるlastはどのプロセスから切り替わったかという情報を保持している。なぜなら再スケジューリングなどで、どのプロセスから切り替わったというデータが失われる可能性があるため。
***1.5プロセススケジューラ [#g2a21283]
-1.5.1スケジューリングの方針~
Linuxでは応答性能とスループットという互いに矛盾する要求に対応できるように設計。~
--優先度
---固定優先度(nice値)と変動優先度
---変動優先度は時間経過とともに変動
---応答性能のために、対話型プロセスの優先度を高める
---実行中のプロセスから実行権を奪う処理をプリエンプションと言う
--実行保証
---公平性を保つことにも配慮 一部のプロセスのみが実行権を握り、スケジューリング対象から漏れてしまうプロセスが発生しないように実行権を与える。
---実行割り当て時間(タイムスライス)
---固定優先度によって実行割り当て時間を割り当てる。これが残っている間は実行権を持ち続けることが可能。
---再割り当てはすべての実行可能プロセスの実行割り当て時間がなくなった時。
-1.5.2 スケジューリング契機
--現在実行中のプロセスが自ら実行権を手放したとき。具体的に二つの場合。
---ある事象が成立することを待ち合わせるために待機状態に遷移した場合。
---明示的に他のプロセスに実行権を譲る場合。 非常に長いカーネル処理を実行する時など、応答性に悪影響を与えないようにするため。
--前述のプリエンプションが起こったとき。新しいプロセスが実行待ち状態のプロセス群に加わったとき、その新しいプロセスが現在実行中のプロセスより優先度が高いことがわかると、プロセススケジューラに対して再スケジューリング要求を出す(resched_task関数)
--プロセスが実行割り当て時間を使い果たした場合。
---Linuxカーネルが強制的に実行権を取り上げ、プロセススケジューラに再スケジューリング要求を出す。実際にプロセススケジューラが動作するのは、Linuxカーネルが行うべき処理が完了するまで遅延させられる。
-1.5.3 リアルタイムプロセス
--Linuxのプロセススケジューリングはすべてのプロセスを公平に扱うことを方針としているため、実時間処理(リアルタイム処理)を行いたい場合、これが仇となる。
--このような用途のためにリアルタイムプロセス機能を提供。
--リアルタイムプロセスは通常のプロセスより高い優先度を持ち、勝手に優先度を下げられることもなく、実行割り当て時間も無制限。
--切り替えが発生するのは、より高い優先度のリアルタイムプロセスが来たとき(プリエンプション)か、自ら実行権を放棄したとき。
-1.5.4 マルチプロセッサシステムにおけるプロセススケジューリング
--実行優先度の逆転が起きても、プロセスがCPU間を移動しないように抑制するほうが効率は良くなる。
--あるプロセスがあるCPU上で一度動作した場合、次回動作する場合も同じCPU上で動作させるべき。
--そのプロセスが利用した実メモリの内容がキャッシュメモリに蓄えられているから。
--キャッシュメモリと実メモリの速度差は大きくなる傾向があるので、キャッシュをどれだけ有効活用できるかが鍵になる。
--TLBの利用効率も関係ある。最近利用されたアドレス変換情報はTLBにキャッシュされ、再度計算するときのオーバーヘッドを減らすことができる。
--Linuxカーネル2.6のプロセススケジューラは各CPUでそれぞれ独立して動作している。
--1.5.4.1 ハイパースレッディング
---Intel Xeonプロセッサから導入された新しい技術 Core i7とか
---演算機ひとつにレジスタセットを二組持っていて、片方のレジスタセットを利用して動作している命令コード列がメモリアクセスのためにストールした場合、もう片方のレジスタセットで別の命令コードを実行する。
---OSからみると、仮想的なCPUが二つ存在するように見える。
--1.5.4.2 NUMA
---SPMシステムではスケーラビリティに限界がある。
---SPMマシンを一つのノードとし、複数のノードを高速スイッチで相互接続したような構造。
---同じノード内のメモリアクセス << 他のノード上にあるメモリへのアクセス これを強く意識。
---ノード間を超えてのプロセス移動は禁止。ただし、exec処理のタイミングでのみ移動可能。
***1.6プロセススケジューラの実装 [#o383d753]
-1.6.1実行優先度毎のRUNキュー
--実行可能なプロセスはRUNキューに登録
--実行優先度ごとにスロットが用意されていて、次に実行するプロセスは最も優先度の高いスロットに登録されているプロセスを選択するだけ。
--再スケジューリングに時間がかからない。O(1)スケジューラ
-1.6.2二種類のRUNキュー
--スケジューラは二つのRUNキューを持つ。
--activeキュー
---実行割り当て時間を持っているプロセスが登録されるキュー
--expiredキュー
---実行割り当て時間を使い果たしたプロセスが登録されるキュー
--activeキューからプロセスが選択され、実行割り当て時間を使い果たすとexpiredキューに登録される
--activeに登録されているプロセスがすべて実行される(実行割り当て時間を使い果たす)と、activeキューとexpiredキューは交換され、expiredキューがactiveキューとなる。
--activeキューに登録されれば必ずCPU時間が使えるときが来る→公平性の確保
-1.6.3CPUごとのRUNキュー
--CPUごとにRUNキューを持っている。(スケジューラもCPUごとなんで直感的には当たり前かも)
--特定のプロセスは、基本的には同じCPUで動く。TLBやキャッシュの有効利用。
--負荷が偏った場合、実行待ちプロセスの移動を行う。
-1.6.4アイドルプロセス
--何も実行すべきプロセスがないときに実行するプロセス。
--実行可能なプロセスが現れ、プリエンプトされるのを待ち続ける。
--各CPU毎に一つ用意されている
-1.6.5カレントプロセス
--現在実行されているプロセスのことを指す。当然CPUの数だけカレントプロセスは存在する。
--カレントプロセスはRUNキューに登録されたままだが、currentというポインタ変数で指されている。
-1.6.6プロセッサバインド機能
--プロセッサを明示的に特定のCPU用のRUNキューにくくりつけることが可能。
--もともと、CPU間のプロセス移動は抑制気味だが、明示的に移動を禁止することが可能。
--システム構築者が前もって負荷バランスを見積もり、プロセスをCPUに固定する時に使える。
-1.6.7プロセススケジューラのアルゴリズム
--prev変数:カレントプロセス next変数:次に実行権を与える候補のプロセス
++カレントプロセスが待機状態になった場合、スケジューラはそのプロセスをRUNキューから外す処理を行う。
---しかし、そのプロセスがTASK_INTERRUPTING(シグナル受信可能な待機状態)かつ、シグナルを受信していたら、TASK_RUNNINGに戻す。RUNキューから外さない。
++activeキューを検索し、次に実行権を与えるべきプロセスとして最も実行優先度の高いプロセスを選ぶ。
---つまり、プロセスが登録されているスロットで先頭のものを選ぶ。
---また、activeキューが空ならactiveとexpiredキューを逆にする。
+++もし、このプロセススケジューラが担当してるRUNキュー上に、実行可能プロセスがなければ、他のCPU用のプロセススケジューラから奪ってくる。
+++奪えるプロセスがなければ、アイドルプロセスを実行権を与えるプロセスとして選択。
++次に動作すべきプロセスnextが決定したらプロセスディスパッチャを呼び出し、prevからnextにコンテキストを切り替える。~
~
--スケジューリング処理の間に新しいスケジューリング要求が発生することがあるが、
プロセススケジューリング処理中は再度プロセススケジューリング処理が動作しないように抑制する必要あり。
--新しいスケジューリング要求は、現在のプロセススケジューリング処理が完全に終了した時点で再度行うことで対応。
--変動優先度はプロセスの走行時間と待機時間をベースに求める。対話型と思われるプロセスに対しては、走行時間を短めに見積もることにより、優先度を上げ応答性を高めようとする。
--nextがTASK_INTERRUPTIBLEから起床したばかりであれば、実行優先度の再計算を行う。
---プロセス起床処理で、TASK_INTERRUPTIBLEから起床したときは応答性確保のために高めの実行優先度を与えてあるので、本来の優先度に戻す処理をしなければならない。
--割り込み処理による起床の場合は、その後も少しだけ高い優先度を確保。対話型プロセスである可能性が高いため。
***1.7事象の待ち合わせ [#o2a5d7f6]
-1.7.1待機処理
--待機の対象となり得るカーネルオブジェクト(ファイルや、実ページ、端末など)には、WAITキューが用意されている。
--待機状態に遷移したプロセスはある事象の待ち合わせ用に用意されているWAITキューに登録される。
---たとえば、ある端末の入力待ちのWAITキュー、ページキャッシュ上のページへの入出力完了を待ち合わせるためのWAITキューなど……
--WAITキューに直接登録することはせず、wait_queue_t型のデータ構造を介して間接的に登録する
--実行中プロセスを待機状態にする関数を呼び出すことにより、待機状態に移行する。
---関数が呼び出されると、プロセス状態を変更し、スタック上に確保したwait構造体を使って、目的の事象を待ち合わせるためのWAITキューに登録し、スケジューラを呼び出し実行権を放棄する。
-1.7.2起床処理
--起床用の関数として、wake_up関数群がある
---プロセスをRUNキューに登録することと、プロセス状態をTASK_RUNNINGに変更することを行う。
---もし起床させたプロセスのほうが現在実行中のプロセスより優先度が高ければ、プリエンプト要求も送る。
---But, WAITキューからプロセスを外すことはしない。(はずすのはプロセス自身)
++これから起床するプロセスが属するRUNキューを選択し、プロセスをそのRUNキューに登録する。
++activate_task関数を呼び出し、優先度の再計算を行う。
---プリエンプションを発生させない指定の場合は行わない。
---長く待機状態であったプロセスのほうがより高い実行優先度を得られる。
++もし、現在実行しているプロセスの優先度が、起床させたプロセスの優先度より低いならばプリエンプト要求をスケジューラに送信する。
++プロセスをRUNキューに登録し終わったら、プロセスを実行可能状態に遷移させる。
--ひとつのプロセスが複数のWAITキューに登録することが可能
-1.7.3そのほかの待機/起床処理関数
--completionという仕組み。事象の発生回数とプロセスの起床回数をそろえることが可能。
-1.7.4子プロセスのスケジューリング
--forkにより子プロセスが生成されたとき、実行状態としてスケジューリング対象へ追加
--優先度は親から引き継ぎ、親プロセスと同じRUNキューの親プロセスの前に挿入し、プリエンプト要求を出す。
--また生成した時、親は実行割り当て時間の半分を子プロセスに譲る。大量の子プロセスが生成されても公平性を保つため。
終了行:
#contents
---------------------
**第一章プロセススケジューリング [#g94d971e]
-参考URL
--http://d.hatena.ne.jp/naoya/20071010/1192040413 マルチスレッドのコンテキスト切り替えに伴うコスト
***1.1マルチタスク [#ce358dbc]
-複数のプロセスを同時に実行すること。
-実際は複数のプロセスを細かく切り替えながら動作させ、同時にプロセスを実行しているようにみせる。
***1.2プロセスとは? [#j8659492]
-プログラムが動いていること。プログラムが一つで、プロセスが複数あることがある。
-各々のプロセスは、それぞれ固有のコンテキストを持つ。
-Linuxカーネルでは、スレッドも一種のプロセスとして扱う。
--スレッド同士がプロセス空間を共有していることを除けば、通常のプロセスと同じ。
--スケジューリングの際も、スレッドはプロセスと同様の扱いでスケジューリングを行う。
***1.3プロセス切り替え [#sd2ef7fc]
-もともとCPU上で動作していたプロセスの実行を中断し、新しいプロセスの実行を開始すること。
-実際にプロセスはどう稼働しているか?
--用意されたプロセス空間上で走行している。
--変数の値はメモリもしくはレジスタ上に存在している。
--実行中の命令はプロセスカウンタレジスタが指している。
--利用中のスタックはスタックポインタが指している。
--プロセス空間そのものが、特殊レジスタによって管理されている。
-これらのレジスタ群を全て、切り替えするプロセスのレジスタ値で書きなおせば、プロセスの切り替えは完了する。
-その前に、今まで動いていたプロセスのレジスタ値を退避する必要がある。
-これらのレジスタ群の値のことをコンテキストと呼ぶ。実行待ちのプロセスはコンテキストをtask_struct構造体やカーネルスタックに退避しておき、実際に実行状態になるとCPU上に読み込む。
***1.4プロセスディスパッチャ [#zf72802d]
-1.4.1context_switch関数
--Linuxカーネルのプロセスディスパッチャのコードは、context_switch関数にある。以下の二つの処理から成る。
---プロセス空間の切り替え処理(swtich_mm関数)
---各種レジスタ切り替え処理(swtich_to関数)
-1.4.2swtich_toマクロ
--prevを今まで動作していたプロセス、nextを切り替えるプロセスとする
--EIPとESPの切り替えに注目
---EIP(Extended Instruction Pointer):命令ポインタ
---ESP(Extended Stack Pointer:スタックポインタ
--task_struct構造体に、EIP、ESPがそれぞれ格納される。
--switch_toマクロの動作概要
++prevで示されるプロセスのESPレジスタを退避、nextで示されるプロセスのESPレジスタを復帰することで、スタックの切り替えを実現。
++prevプロセスが次回動作時に、同じ場所から再開できるようにEIPレジスタを退避。プロセスnextの実行再開箇所は、nextのレジスタの退避域から取り出したEIPレジスタの値をスタック上に置いておく。
++__switch_to関数を呼び出した後、その関数から戻る時スタックに積んだEIPレジスタの値が自動的にCPUに読み込まれる。
---C言語でいう関数呼出はcallにあたりスタックに次の命令のポインタを保存し、、retするときにスタック上に積んである命令の場所に戻る。
---ここでは、直接jmp命令で__swich_to関数に飛び込むことで、retするとき次の命令はスタック上に積んだEIPレジスタの値であると信じこむ。
--例外あり。forkで生成された子プロセスや、カーネルスレッドはeipレジスタ退避域に直接特定のアドレスを書き込んで、退避していないのに、さも復帰したかのように動作する。
--switch_toマクロの3つ目の変数であるlastはどのプロセスから切り替わったかという情報を保持している。なぜなら再スケジューリングなどで、どのプロセスから切り替わったというデータが失われる可能性があるため。
***1.5プロセススケジューラ [#g2a21283]
-1.5.1スケジューリングの方針~
Linuxでは応答性能とスループットという互いに矛盾する要求に対応できるように設計。~
--優先度
---固定優先度(nice値)と変動優先度
---変動優先度は時間経過とともに変動
---応答性能のために、対話型プロセスの優先度を高める
---実行中のプロセスから実行権を奪う処理をプリエンプションと言う
--実行保証
---公平性を保つことにも配慮 一部のプロセスのみが実行権を握り、スケジューリング対象から漏れてしまうプロセスが発生しないように実行権を与える。
---実行割り当て時間(タイムスライス)
---固定優先度によって実行割り当て時間を割り当てる。これが残っている間は実行権を持ち続けることが可能。
---再割り当てはすべての実行可能プロセスの実行割り当て時間がなくなった時。
-1.5.2 スケジューリング契機
--現在実行中のプロセスが自ら実行権を手放したとき。具体的に二つの場合。
---ある事象が成立することを待ち合わせるために待機状態に遷移した場合。
---明示的に他のプロセスに実行権を譲る場合。 非常に長いカーネル処理を実行する時など、応答性に悪影響を与えないようにするため。
--前述のプリエンプションが起こったとき。新しいプロセスが実行待ち状態のプロセス群に加わったとき、その新しいプロセスが現在実行中のプロセスより優先度が高いことがわかると、プロセススケジューラに対して再スケジューリング要求を出す(resched_task関数)
--プロセスが実行割り当て時間を使い果たした場合。
---Linuxカーネルが強制的に実行権を取り上げ、プロセススケジューラに再スケジューリング要求を出す。実際にプロセススケジューラが動作するのは、Linuxカーネルが行うべき処理が完了するまで遅延させられる。
-1.5.3 リアルタイムプロセス
--Linuxのプロセススケジューリングはすべてのプロセスを公平に扱うことを方針としているため、実時間処理(リアルタイム処理)を行いたい場合、これが仇となる。
--このような用途のためにリアルタイムプロセス機能を提供。
--リアルタイムプロセスは通常のプロセスより高い優先度を持ち、勝手に優先度を下げられることもなく、実行割り当て時間も無制限。
--切り替えが発生するのは、より高い優先度のリアルタイムプロセスが来たとき(プリエンプション)か、自ら実行権を放棄したとき。
-1.5.4 マルチプロセッサシステムにおけるプロセススケジューリング
--実行優先度の逆転が起きても、プロセスがCPU間を移動しないように抑制するほうが効率は良くなる。
--あるプロセスがあるCPU上で一度動作した場合、次回動作する場合も同じCPU上で動作させるべき。
--そのプロセスが利用した実メモリの内容がキャッシュメモリに蓄えられているから。
--キャッシュメモリと実メモリの速度差は大きくなる傾向があるので、キャッシュをどれだけ有効活用できるかが鍵になる。
--TLBの利用効率も関係ある。最近利用されたアドレス変換情報はTLBにキャッシュされ、再度計算するときのオーバーヘッドを減らすことができる。
--Linuxカーネル2.6のプロセススケジューラは各CPUでそれぞれ独立して動作している。
--1.5.4.1 ハイパースレッディング
---Intel Xeonプロセッサから導入された新しい技術 Core i7とか
---演算機ひとつにレジスタセットを二組持っていて、片方のレジスタセットを利用して動作している命令コード列がメモリアクセスのためにストールした場合、もう片方のレジスタセットで別の命令コードを実行する。
---OSからみると、仮想的なCPUが二つ存在するように見える。
--1.5.4.2 NUMA
---SPMシステムではスケーラビリティに限界がある。
---SPMマシンを一つのノードとし、複数のノードを高速スイッチで相互接続したような構造。
---同じノード内のメモリアクセス << 他のノード上にあるメモリへのアクセス これを強く意識。
---ノード間を超えてのプロセス移動は禁止。ただし、exec処理のタイミングでのみ移動可能。
***1.6プロセススケジューラの実装 [#o383d753]
-1.6.1実行優先度毎のRUNキュー
--実行可能なプロセスはRUNキューに登録
--実行優先度ごとにスロットが用意されていて、次に実行するプロセスは最も優先度の高いスロットに登録されているプロセスを選択するだけ。
--再スケジューリングに時間がかからない。O(1)スケジューラ
-1.6.2二種類のRUNキュー
--スケジューラは二つのRUNキューを持つ。
--activeキュー
---実行割り当て時間を持っているプロセスが登録されるキュー
--expiredキュー
---実行割り当て時間を使い果たしたプロセスが登録されるキュー
--activeキューからプロセスが選択され、実行割り当て時間を使い果たすとexpiredキューに登録される
--activeに登録されているプロセスがすべて実行される(実行割り当て時間を使い果たす)と、activeキューとexpiredキューは交換され、expiredキューがactiveキューとなる。
--activeキューに登録されれば必ずCPU時間が使えるときが来る→公平性の確保
-1.6.3CPUごとのRUNキュー
--CPUごとにRUNキューを持っている。(スケジューラもCPUごとなんで直感的には当たり前かも)
--特定のプロセスは、基本的には同じCPUで動く。TLBやキャッシュの有効利用。
--負荷が偏った場合、実行待ちプロセスの移動を行う。
-1.6.4アイドルプロセス
--何も実行すべきプロセスがないときに実行するプロセス。
--実行可能なプロセスが現れ、プリエンプトされるのを待ち続ける。
--各CPU毎に一つ用意されている
-1.6.5カレントプロセス
--現在実行されているプロセスのことを指す。当然CPUの数だけカレントプロセスは存在する。
--カレントプロセスはRUNキューに登録されたままだが、currentというポインタ変数で指されている。
-1.6.6プロセッサバインド機能
--プロセッサを明示的に特定のCPU用のRUNキューにくくりつけることが可能。
--もともと、CPU間のプロセス移動は抑制気味だが、明示的に移動を禁止することが可能。
--システム構築者が前もって負荷バランスを見積もり、プロセスをCPUに固定する時に使える。
-1.6.7プロセススケジューラのアルゴリズム
--prev変数:カレントプロセス next変数:次に実行権を与える候補のプロセス
++カレントプロセスが待機状態になった場合、スケジューラはそのプロセスをRUNキューから外す処理を行う。
---しかし、そのプロセスがTASK_INTERRUPTING(シグナル受信可能な待機状態)かつ、シグナルを受信していたら、TASK_RUNNINGに戻す。RUNキューから外さない。
++activeキューを検索し、次に実行権を与えるべきプロセスとして最も実行優先度の高いプロセスを選ぶ。
---つまり、プロセスが登録されているスロットで先頭のものを選ぶ。
---また、activeキューが空ならactiveとexpiredキューを逆にする。
+++もし、このプロセススケジューラが担当してるRUNキュー上に、実行可能プロセスがなければ、他のCPU用のプロセススケジューラから奪ってくる。
+++奪えるプロセスがなければ、アイドルプロセスを実行権を与えるプロセスとして選択。
++次に動作すべきプロセスnextが決定したらプロセスディスパッチャを呼び出し、prevからnextにコンテキストを切り替える。~
~
--スケジューリング処理の間に新しいスケジューリング要求が発生することがあるが、
プロセススケジューリング処理中は再度プロセススケジューリング処理が動作しないように抑制する必要あり。
--新しいスケジューリング要求は、現在のプロセススケジューリング処理が完全に終了した時点で再度行うことで対応。
--変動優先度はプロセスの走行時間と待機時間をベースに求める。対話型と思われるプロセスに対しては、走行時間を短めに見積もることにより、優先度を上げ応答性を高めようとする。
--nextがTASK_INTERRUPTIBLEから起床したばかりであれば、実行優先度の再計算を行う。
---プロセス起床処理で、TASK_INTERRUPTIBLEから起床したときは応答性確保のために高めの実行優先度を与えてあるので、本来の優先度に戻す処理をしなければならない。
--割り込み処理による起床の場合は、その後も少しだけ高い優先度を確保。対話型プロセスである可能性が高いため。
***1.7事象の待ち合わせ [#o2a5d7f6]
-1.7.1待機処理
--待機の対象となり得るカーネルオブジェクト(ファイルや、実ページ、端末など)には、WAITキューが用意されている。
--待機状態に遷移したプロセスはある事象の待ち合わせ用に用意されているWAITキューに登録される。
---たとえば、ある端末の入力待ちのWAITキュー、ページキャッシュ上のページへの入出力完了を待ち合わせるためのWAITキューなど……
--WAITキューに直接登録することはせず、wait_queue_t型のデータ構造を介して間接的に登録する
--実行中プロセスを待機状態にする関数を呼び出すことにより、待機状態に移行する。
---関数が呼び出されると、プロセス状態を変更し、スタック上に確保したwait構造体を使って、目的の事象を待ち合わせるためのWAITキューに登録し、スケジューラを呼び出し実行権を放棄する。
-1.7.2起床処理
--起床用の関数として、wake_up関数群がある
---プロセスをRUNキューに登録することと、プロセス状態をTASK_RUNNINGに変更することを行う。
---もし起床させたプロセスのほうが現在実行中のプロセスより優先度が高ければ、プリエンプト要求も送る。
---But, WAITキューからプロセスを外すことはしない。(はずすのはプロセス自身)
++これから起床するプロセスが属するRUNキューを選択し、プロセスをそのRUNキューに登録する。
++activate_task関数を呼び出し、優先度の再計算を行う。
---プリエンプションを発生させない指定の場合は行わない。
---長く待機状態であったプロセスのほうがより高い実行優先度を得られる。
++もし、現在実行しているプロセスの優先度が、起床させたプロセスの優先度より低いならばプリエンプト要求をスケジューラに送信する。
++プロセスをRUNキューに登録し終わったら、プロセスを実行可能状態に遷移させる。
--ひとつのプロセスが複数のWAITキューに登録することが可能
-1.7.3そのほかの待機/起床処理関数
--completionという仕組み。事象の発生回数とプロセスの起床回数をそろえることが可能。
-1.7.4子プロセスのスケジューリング
--forkにより子プロセスが生成されたとき、実行状態としてスケジューリング対象へ追加
--優先度は親から引き継ぎ、親プロセスと同じRUNキューの親プロセスの前に挿入し、プリエンプト要求を出す。
--また生成した時、親は実行割り当て時間の半分を子プロセスに譲る。大量の子プロセスが生成されても公平性を保つため。
ページ名: