Linux的進程優先級(4)

　　O1調度器在處理流程上大概是這樣進行調度的：

　　首先，進程產生(fork)的時候會給一個進程分配一個時間片長度。這個新進程的時間片一般是父進程的一半，而父進程也會因此減少它的時間片長度為原來的一半。就是說，如果一個進程產生了子進程，那么它們將會平分當前時間片長度。比如，如果父進程時間片還剩100ms，那么一個fork產生一個子進程之后，子進程的時間片是50ms，父進程剩余的時間片是也是50ms。這樣設計的目的是，為了防止進程通過fork的方式讓自己所處理的任務一直有時間片。不過這樣做也會帶來少許的不公平，因為先產生的子進程獲得的時間片將會比后產生的長，第一個子進程分到父進程的一半，那么第二個子進程就只能分到1/4。對于一個長期工作的進程組來說，這種影響可以忽略，因為第一輪時間片在耗盡后，系統會在給它們分配長度相當的時間片。

　　針對所有R狀態進程，O1算法使用兩個隊列組織進程，其中一個叫做活動隊列，另一個叫做過期隊列?；顒雨犃兄蟹诺亩际菚r間片未被耗盡的進程，而過期隊列中放時間片被耗盡的進程。

　　如1所述，新產生的進程都會先獲得一個時間片，進入活動隊列等待調度到CPU執行。而內核會在每個tick間隔期間對正在CPU上執行的進程進行檢查。一般的tick間隔時間就是cpu時鐘中斷間隔，每秒鐘會有1000個，即頻率為1000HZ。每個tick間隔周期主要檢查兩個內容：1、當前正在占用CPU的進程是不是時間片已經耗盡了?2、是不是有更高優先級的進程在活動隊列中等待調度?如果任何一種情況成立，就把則當前進程的執行狀態終止，放到等待隊列中，換當前在等待隊列中優先級最高的那個進程執行。

　　以上就是O1調度的基本調度思路，當然實際情況是，還要加上SMP(對稱多處理)的邏輯，以滿足多核CPU的需求。目前在我的archlinux上可以用以下命令查看內核HZ的配置：

　　我們發現我當前系統的HZ配置為300，而不是一般情況下的1000。大家也可以思考一下，配置成不同的數字(100、250、300、1000)，對系統的性能到底會有什么影響?

　　CFS完全公平調度

　　O1已經是上一代調度器了，由于其對多核、多CPU系統的支持性能并不好，并且內核功能上要加入cgroup等因素，Linux在2.6.23之后開始啟用CFS作為對一般優先級(SCHED_OTHER)進程調度方法。在這個重新設計的調度器中，時間片，動態、靜態優先級以及IO消耗，CPU消耗的概念都不再重要。CFS采用了一種全新的方式，對上述功能進行了比較完善的支持。

　　其設計的基本思路是，我們想要實現一個對所有進程完全公平的調度器。又是那個老問題：如何做到完全公平?答案跟上一篇IO調度中CFQ的思路類似：如果當前有n個進程需要調度執行，那么調度器應該再一個比較小的時間范圍內，把這n個進程全都調度執行一遍，并且它們平分cpu時間，這樣就可以做到所有進程的公平調度。那么這個比較小的時間就是任意一個R狀態進程被調度的最大延時時間，即：任意一個R狀態進程，都一定會在這個時間范圍內被調度相應。這個時間也可以叫做調度周期，其英文名字叫做：sched_latency_ns。進程越多，每個進程在周期內被執行的時間就會被平分的越小。調度器只需要對所有進程維護一個累積占用CPU時間數，就可以衡量出每個進程目前占用的CPU時間總量是不是過大或者過小，這個數字記錄在每個進程的vruntime中。所有待執行進程都以vruntime為key放到一個由紅黑樹組成的隊列中，每次被調度執行的進程，都是這個紅黑樹的最左子樹上的那個進程，即vruntime時間最少的進程，這樣就保證了所有進程的相對公平。

　　在基本驅動機制上CFS跟O1一樣，每次時鐘中斷來臨的時候，都會進行隊列調度檢查，判斷是否要進程調度。當然還有別的時機需要調度檢查，發生調度的時機可以總結為這樣幾個：

　　當前進程的狀態轉換時。主要是指當前進程終止退出或者進程休眠的時候。

　　當前進程主動放棄CPU時。狀態變為sleep也可以理解為主動放棄CPU，但是當前內核給了一個方法，可以使用sched_yield()在不發生狀態切換的情況下主動讓出CPU。

　　當前進程的vruntime時間大于每個進程的理想占用時間時(delta_exec > ideal_runtime)。這里的ideal_runtime實際上就是上文說的sched_latency_ns/進程數n。當然這個值并不是一定這樣得出，下文會有更詳細解釋。

原文轉自：http://www.testwo.com/article/659