Linuxカーネル学習の3-プロセスのスケジューリング

一、スケジューリングの全体プロセス
プロセスのスケジューリングはプロセス部分の核心です.スケジューリングがなければ、プロセスも必要ありません.前の論文の第2部では,各プロセスが平均100ミリ秒実行される最も簡単なタイムスライスによるスケジューリングアルゴリズムを実現した.

 while (true){
     processing = nextProcessing();
     processing.run();
     wait(100); // 100    
     processing.interrupt();
 }

ではLinuxではどのように実現されているのでしょうか.まず流れを見てみましょう.スケジューリングに関連するコードはsched.cにあります.これがLinuxコードコアのコアで、億万台のマシンで実行されています.各マシンはクロックサイクルごとに実行されます.それは少し興奮しているのではないでしょうか.「高性能の最下位コード」がどうなっているかやっと分かった!
このファイルのコア関数はasmlinkage void __sched schedule(void)であり、これがスケジューリング部分の具体的なコードである.この記事のように、注釈を読んでから、注釈のバージョンがたくさんあることに気づきました.http://blog.csdn.net/zhoudaxia/article/details/7375836ああ、だからコードを貼らない.私が注釈したコードはschedです.c(4079行から)にあります.しかし、ソースコードを読まないと、キーワードを検索しなくても、良い文章が見つからないかもしれません.これも勉強の過程でしょう.
この方法には2つの重要な点があり、1つはpick_next_task(rq);であり、スケジューリングアルゴリズムに関連する次の実行可能なプロセスを取得する.一つはcontext_switch(rq, prev, next);で、これがいわゆる「コンテキスト切替」です.
二、スケジューリングアルゴリズム
我々の前の「100ミリ秒アルゴリズム」アルゴリズムはもちろん非常に粗い.本物のLinuxスケジューリングアルゴリズムを理解するには、スケジューリングシステムがどのような問題を考慮する必要があるかを見てみましょう(非公式の権威の総括):

は、CPUを最大限に利用し、プロセスが実行可能であれば、CPUを空などにしない.CPU利用率を最大限にする.

は、プロセス(特にインタラクティブプロセス)の応答時間をできるだけ短くすることを保証する.

は、システム管理者によって優先度を指定し、重要なタスクを先に実行させることができる.

スケジューリングは非常に頻繁に実行されるため、そのパフォーマンスを考慮する必要があります.

は、マルチコア平均スケジューリング、すなわち、いわゆる対称マルチプロセッサ(Symmetric Multi-Processor,SMP)をサポートする.

私たちの「100ミリ秒アルゴリズム」は1と3を満たしていません.2にとってはあまりよくありません(それほど長く実行されないプロセスもあるかもしれません).もし私たちが時間を短縮して、1ミリ秒に変えたらどうですか?「プロセス切り替え」自体にもオーバーヘッドがあることを知っていますが、このように頻繁に切り替えるのは、損をしないのではないでしょうか.
実際、その核心的な地位のため、Linuxのスケジューリングアルゴリズムはいったん少し性能を向上させると、工業界全体の向上にも巨大である.アルゴリズムの達人にとって、ここは活躍のいい場所になった.だからLinuxスケジューリングアルゴリズムの変化はかなり速く、O(n)スケジューラからO(1)スケジューラ、さらに2.6.23の「CFS(completely fair schedule)」まで、めまいがします!
解決すべき問題を理解すれば、もっと理解しやすいかもしれません.O(n)とO(1)アルゴリズムはいずれもタイムスライスに基づいており、基本的な考え方は、プロセスに優先度を指定し、IOが高く、インタラクションが強いプロセスにより高い優先度を与え、CPUが高い場合は優先度を下げ、毎回優先度が最も高い実行を選択することである.同時に、各プロセスにタイムスライス(各プロセスのタイムスライスは動的に調整されている)を割り当て、各プロセスが実行するたびにこのタイムスライスの時間になります.O(n)とO(1)の違いは,優先キューからプロセスを取り出す際の時間的複雑さにある.具体的な詳細はあまり言わない.
「CFS」は、実行時間を保存するために「vruntime」という概念を使用します.同時に赤と黒の木でプロセスをソートし、vruntimeが小さいほどプロセスが先に実行されるので、時間の複雑さはO(logn)です.そのコードはkernel/sched_fair.cにあります.
また、「リアルタイムスケジューリングアルゴリズム」の概念もあります.これらは、CFSのすべてのプロセスよりも優先される「プラグされた」プロセスです.対応するタイプはSCHED_FIFOおよびSCHED_RRであり、sched.hに見られる.
スケジューリング部分はこんなに多くて、まだいくつかの細部があって、例えばCFGは具体的に実現して、本の中ですでに詳しくて、繰り返し記録しないで、書くのが気絶しないようにします!
参考資料:

『Linuxカーネル設計と実現』LKD

Linux 2.6カーネルの新しいロックメカニズム–RCUhttp://www.ibm.com/developerworks/cn/linux/l-rcu/

Linuxプロセススケジューリング(3):プロセス切替分析http://blog.csdn.net/zhoudaxia/article/details/7375836

http://blog.csdn.net/yunsongice/article/details/8547107