Linuxプロセススケジューリング

オペレーティングシステム
マルチプロセスを実現するには、プロセススケジューリングが不可欠です。プロセススケジューリングはどの程度重要ですか？まず、明確にする必要があります。プロセスのスケジューリングとは、TASK_RUNNING状態でプロセスをスケジューリングすることです。プロセスが実行不可能（スリープ中など）でない場合は、プロセススケジューリングとはほとんど関係ありません。 Linuxカーネルは、プロセスを2つのレベルに分けます。通常のプロセスとリアルタイムプロセスです。リアルタイムプロセスは通常のプロセスよりも優先度が高く、スケジューリング方法は異なります。
1.1リアルタイムプロセスのスケジューリング
リアルタイムプロセスのリアルタイムスケジューリング、本来の意味は「与えられた操作は一定時間内に完了しなければならない」です。重要なのは、操作を高速に処理する必要があるということではなく、時間が制御可能であるということです（最悪の場合、指定された時間を超えることはできません）。このような「リアルタイム」は「ハードリアルタイム」と呼ばれ、非常に高度なシステム（ロケット、ミサイルなど）で使用されています。一般に、ハードリアルタイムシステムは比較的特殊です。
Linuxのような汎用オペレーティングシステムは、明らかにそのような要件を満たすことができません割り込み処理、仮想メモリ、および他のメカニズムの存在は、処理時間に大きな不確実性をもたらします。ハードウェアキャッシュ、ディスクシーク、およびバスの競合も不確実性をもたらす可能性があります。 Linuxは、「リアルタイム」を実装する汎用オペレーティングシステムが実際には「ソフトリアルタイム」を実装していることを認識しています。これは、プロセスのリアルタイム要件を可能な限り満たすものです。
プロセスにリアルタイムの要件がある場合（リアルタイムプロセスである場合）、実行可能である限り、カーネルは可能な限りCPUのニーズを満たすために実行を続けます。その後、事はスリープまたは終了します（実行不可能になります）。実行可能状態にあるリアルタイムプロセスが複数ある場合、カーネルは、実行不可能になるまで、最優先のリアルタイムプロセスのCPUを最初に満たします。このため、優先順位の高いリアルタイムプロセスが常に実行可能状態である限り、優先順位の低いリアルタイムプロセスはＣＰＵを獲得できず、リアルタイムプロセスが常に実行可能状態である限り、通常プロセスはＣＰＵを獲得できない。 （その後、カーネルは/proc /sys /kernel /sched_rt_runtime_usと/proc /sys /kernel /sched_rt_period_usの2つのパラメータを追加しました。sched_rt_runtime_usをsched_rt_period_usの期間だけ実行するようにリアルタイムプロセスを制限しました。実行可能状態のリアルタイムプロセスが常に存在する場合は、通常のプロセスに実行される可能性を少しだけ与えますので、同じ優先順位の複数のリアルタイムプロセスが実行可能状態にある場合は、次の2つがあります。
l SCHED_FIFO
先入れ先出し最初に実行されたプロセスが実行不可能になるまで、後続のプロセスは実行されるようにスケジュールされます。 sched_yieldシステムコールを実行して、後のプロセスに電力を供給するために自発的にCPUを放棄することができます。

SCHED_RR：
Rotate schedule。カーネルはリアルタイムプロセスにタイムスライスを割り当て、タイムスライスが切れると次のプロセスに使用させます。 CPUとFIFOの違いはタイムスライスが使用されることです; Linuxでは、ユーザプログラムはsched_setschedulerシステムコールによって設定することができます。スケジューリング方針と関連するスケジューリングパラメータ、sched_setparamシステムコールはスケジューリングパラメータを設定するためだけに使用され、これら2つのシステムコールはプロセスの優先順位を設定することによってプロセス優先度（CAP_SYS_NICE、通常はroot権限を設定）を設定するSCHED_FIFOまたはSCHED_RRの場合、プロセスはリアルタイムプロセスになり、スケジューリングパラメータを設定する際に、プロセスの優先順位は上記の2つのシステムコールによって指定されますリアルタイムカーネルの場合、カーネルは優先順位の調整を試みません。これらの質問はユーザープログラムのアプリケーションシナリオに関するもので、ユーザーだけが答えられ、カーネルは中断することはできません要約すると、リアルタイムプロセスのスケジューリングは非常に簡単ですプロセスの優先順位とスケジューリング戦略はすべてですユーザーが死んだ場合、カーネルは実行をスケジュールするために常に最も優先順位の高いリアルタイムプロセスを選択する必要があるだけです。同じ優先順位を持つリアルタイムプロセスを選択する場合、2つのスケジューリング戦略を考慮する必要があります。 1.2通常のプロセスのスケジューリング
リアルタイムのプロセススケジューリングの中心的な考え方は、実行可能状態の優先順位が最も高いリアルタイムプロセスは、リアルタイム要件があるためCPUをできるだけ占有し、通常のプロセスはリアルタイム要件のないプロセスであると見なされるので、スケジューラは各実行可能状態を作成しようとします。リアルタイムプロセスと比較して、通常のプロセスのスケジューリングははるかに複雑で、カーネルは2つの問題を考慮する必要があります：（1）プロセスの優先順位を動的に調整するプロセスの動作特性に応じて、プロセスは「対話型プロセス」と「バッチプロセス」に分けることができます。対話型プロセス（デスクトッププログラム、サーバーなど）の主なタスクは、外界と対話することです。そのようなプロセスはより高い優先順位を持つべきであり、それらは常に外界からの入力を待って眠ります。入力が入ってカーネルがそれを起こしたとき、それらは応答するために素早く実行するようにスケジュールされるべきです。たとえば、デスクトッププログラムがマウスを半クリックしても応答しない場合、ユーザーはシステムの「カード」を感じることになります（バッチ処理の主なタスク（コンパイラなど）は連続的な操作を実行することです）。実行可能状態たとえば、コンパイラは数秒間実行され、ユーザーはそれほど心配する必要はありません。ユーザーがプロセスの優先順位を明確に知っている場合は、niceおよびsetpriorityシステムコールを使用して優先順位を付けることができます。レベル設定ただし、アプリケーションは必ずしもデスクトッププログラムやコンパイラほど一般的ではありません。プログラムの動作はさまざまですが、対話式のプロセスとしばらくの間バッチプロセスのようなものです。ユーザーが適切な優先順位を設定するのは困難です。したがって、結局のところ、対話式プロセスとバッチプロセスを区別するタスクは、カーネルのスケジューラにかかっています。スケジューラは、ある期間にわたるプロセスのパフォーマンス（主にそのスリープ時間と実行時間のチェック）に焦点を当てていますが、いくつかの経験式に基づいて、対話式かバッチ式かを判断しますか？程度は？最後に、優先順位を調整することにしました。プロセスの優先順位が動的に調整された後、次の2つの優先順位が表示されます。a。ユーザープログラムによって設定された優先順位（または設定されていない場合はデフォルト値）。これはプロセスの優先度のベンチマークであり、プロセスの実行中には変更されませんb。優先度が動的に調整された後、実際の優先度は動的優先度と呼ばれます。この値は常に変化する可能性があります。 （2）スケジューリングの公平性複数のプロセスをサポートするシステムでは、理想的には、各プロセスが優先順位に従ってCPUを公平に占有する必要があります。そして、「誰がラッキーで、もっと誰がいるか」というような手に負えない状況ではないようです。公平スケジューリングのLinuxによる実装は基本的に2つのアイデアです：a。実行可能状態のプロセスにタイムスライスを（優先順位に従って）割り当て、タイムスライスが切れるプロセスは「有効期限待ち行列」に置かれます。実行可能状態などのプロセスが期限切れになり、タイムスライスが再割り当てされます; b。プロセスの優先順位を動的に調整します。プロセスがCPU上で実行されると、他の優先順位の低いプロセスが実行の機会を得るようにその優先順位が連​​続的に下げられ、後者の方がスケジューリングの細分性が小さくなり、「公平性」となります。動的な優先順位付け - カーネルスケジューラのコードを大幅に簡素化するために、2つのことが組み合わされています。したがって、この方法はカーネルスケジューラの新しいお気に入りとなりました。上記の2点は通常のプロセスのためだけのものであることを強調してください。リアルタイムプロセスの場合、カーネルは優先順位を動的に調整することも公平性を持つこともできません。
1.3スケジューラの効率
優先順位>どのプロセスを実行するようにスケジュールする必要があるかは明らかであり、スケジューラは効率の問題にも注意を払う必要があります。スケジューラは、カーネル内の多くのプロセスと同じ頻度で実行されますが、効率が良くないと、多くのCPU時間を浪費し、システムのパフォーマンスが低下します。 Linux 2.4では、実行可能状態プロセスはリンクリストにハングしていました。スケジュールごとに、スケジューラはリンクリスト全体をスキャンして、実行に最適なリストを見つける必要があります。複雑さはO（n）です; Linux 2.6の初期の頃には、実行可能状態プロセスはN（N = 140）個のリンクリストにハングアップしていました。リンクリストスケジュールごとに、スケジューラーは、空ではない最初のリストからリストの先頭にある処理を実行するだけで済みます。これはスケジューラの効率を大幅に向上させ、複雑さはO（1）です;最近のバージョンのlinux 2.6では、実行可能状態プロセスは優先順位の高い順に赤黒木（バランスのとれた二分木と考えられます）にハングします。 。スケジュールごとに、スケジューラはツリーから最も優先順位の高いプロセスを見つける必要があります。複雑さはO（logN）です。では、なぜ初期のLinux 2.6から最近のLinux 2.6バージョンにスケジューラ選択プロセスの複雑さが増したのでしょうか。これは、同時に、スケジューラの公平性の実装が、（動的に優先順位を調整することによって）前述の最初のアイデアから2番目のアイデアに変わるためです。 O（1）アルゴリズムは少数のリンクリストに基づいて実装されていますが、私の理解によれば、これは値の優先順位の範囲を狭くし（差別は非常に少なく）、公平性の要件を満たしません。赤黒木を使用しても優先順位の値に制限はなく（32ビット、64ビット、またはそれ以上のビットで優先順位の値を示すことができます）、O（logN）の複雑さは依然として非常に効率的です。
1.4スケジューリング契機




1.4スケジューリングの契機スケジューリングの契機は、主に次のような場合です。（1）現在のプロセス（CPU上で動作しているプロセス）の状態が実行不能になった。プロセス実行システムコールは積極的に実行不可能になります。たとえば、ナノスリープの実装はスリープ状態に入り、出口出口を実行するなど、プロセスによって要求されたリソースは満たされず、強制的にスリープ状態になります。たとえば、readシステムコールが実行されると、ディスクキャッシュに必要なデータがないため、sleepはディスクIOを待ち、プロセスはシグナルに応答して実行不可能になります。例えば、SIGSTOPに応答して一時停止状態に入る、SIGKILL出口に応答するなどのようにします（2）プリエンプション。予想外にも、CPUはプロセスの実行中にCPUを使用する権利を奪われています。これは2つの状況に分けられます：プロセスがタイムスライスを使い果たすか、またはより高い優先順位のプロセスが発生します。
1.5その他の問題
lマルチプロセッサ下での負荷分散

Linuxでは、各CPUは対応する実行可能キューを持ち、実行可能状態プロセスは同時に1つにしかなれません。実行キュー
それで、マルチプロセッサロードバランシング'この問題は起こりつつあります。カーネルは、各CPU実行可能キュー内のプロセス数に注意を払い、数のバランスが取れていない場合は適切に調整する必要があります。いつ調整しなければならないのか、そしてどの程度プロセス調整を行うのか、これらが考慮する必要がある中心です。結局のところ、CPUと実行可能キューをロックする必要がありますが、それでもコストはわずかです。さらに、カーネルは各CPUの関係を気にする必要があります。 2つのCPU間の関係は、互いに独立している場合もあれば、キャッシュを共有している場合もあれば、ハイパースレッディングテクノロジを介して同じ物理CPUによって仮想化されている場合もあります。関係が近いほど、プロセス間の移動にかかるコストは少なくなります。
l優先度の継承
相互排除のため、プロセス（Aに設定されている）はクリティカルセクションに入るのを待つのでスリープします。対応するリソース（Bに設定されている）を占有しているプロセスがクリティカルセクションを終了するまで、プロセスAは起こされます。 Aの優先度が非常に高く、Bの優先度が非常に低い場合があります。 Bはクリティカルセクションに入りますが、他の優先順位の高いプロセス（Cに設定されている）によって横取りされ、クリティカルセクションを使い果たすことはできません。それならAは起こされることができません。 Aは高い優先順位を持っていますが、現在はBと同じレベルにまで落ちています、そしてCが優先されているので優先順位が高すぎず、実行が延期されます。この現象は優先順位の逆転と呼ばれます。この現象は非常に不合理です。より良い対策は、AがBがクリティカルセクションを終了するのを待ち始めると、処理を正常に完了してクリティカルセクションを終了するために、一時的にAの優先順位を取得します（またはAより優先順位が高いと仮定します）。その後Bの優先順位が回復します。これが優先順位継承の方法です。優先順位の継承を実現するために、カーネルは多くのことをしなければなりません。
l割り込み処理のスレッド化

Linuxでは、割り込みハンドラは予測不可能なコンテキストで実行されます。 CPU応答からハードウェア割り込みが自動的に実行するためにカーネル設定割り込みハンドラにジャンプし、割り込みハンドラが終了するまでプロセス全体を横取りすることはできません。プロセスが横取りされている場合は、プロセス制御ブロック（task_struct）に格納されている情報によって後で再開することができます。割り込みコンテキストはtask_structを持たず、それが横取りされた場合は回復できません。割り込みハンドラを横取りすることはできません。つまり、割り込みハンドラの「優先順位」はどのプロセスよりも高いということです（プロセスを実行するには、割り込みハンドラが完了するのを待つ必要があります）。ただし、実際のアプリケーションシナリオでは、一部のリアルタイムプロセスが割り込みハンドラよりも高い優先順位を受け取る必要があります。したがって、リアルタイム要件が高いシステムの中には、必要に応じて優先順位の高いプロセスが優先されるように、タスクハンドラにtask_structと優先順位を与えるものがあります。しかし、明らかに、この作業を行うとシステムにいくらかのオーバーヘッドが発生します。これは「リアルタイム」を達成するためのパフォーマンスの低下です。