《奔跑吧linux內核》3.2筆記，不足之處還望大家批評指正 建議閱讀博文https://www.cnblogs.com/openix/p/3262217.html理解linux cfs調度器 進程大致可以分為互動式進程，批處理進程和實時進程。對於不同的進程採用不同的調度策略，目前Linux內核中默 ...
《奔跑吧linux內核》3.2筆記，不足之處還望大家批評指正
建議閱讀博文https://www.cnblogs.com/openix/p/3262217.html理解linux cfs調度器
進程大致可以分為互動式進程，批處理進程和實時進程。對於不同的進程採用不同的調度策略，目前Linux內核中預設實現了4種調度策略，分別是deadline、realtime、CFS和idle，分別適用struct sched_class來定義調度類。
4種調度類通過next指針串聯在一起，用戶空間程式可以使用調度策略API函數（sched_setscheduler()）來設定用戶進程的調度策略。
問題一：請簡述對進程調度器的理解，早起Linux內核調度器（包括O(N)和O(1)）調度器是如何工作的？
調度器是按一定的方式對進程進行調度的一種機制，需要為各個普通進程儘可能公平地共用CPU時間。
O(N)調度器發佈與1992年，從就緒隊列中比較所有進程的優先順序，然後選擇一個最高優先順序的進程作為下一個調度進程。每一個進程有一個固定時間片，當進程時間片使用完之後，調度器會選擇下一個調度進程，當所有進程都運行一遍後再重新分配時間片。這個調度器選擇下一個調度進程前需要遍歷整個就緒隊列，花費O(N)時間。
O(1)調度器用於Linux2.6.23內核之前，它為每個CPU維護一組進程優先順序隊列，每個優先順序一個隊列，這樣在選擇下一個進程時，只要查詢優先順序隊列相應的點陣圖即可知道哪個隊列中有就緒進程，查詢時間常數為O(1)。
問題二：請簡述進程優先順序、nice和權重之間的關係。
內核使用0~139的數值表示進程的優先順序，數值越低優先順序越高。優先順序0~99給實時進程使用，100~139給普通進程使用。在用戶空間由一個傳統的變數nice值映射到普通進程的優先順序(100~139)。
nice值從-20~19，進程預設的nice值為0。這可以理解為40個等級，nice值越高，則優先順序越低，反之亦然。（nice每變化1，則相應的進程獲得CPU的時間就改變10%）。
權重信息即為調度實體的權重，為了計算方便，內核約定nice值為0的權重值為1024，其他的nice值對應相應的權重值可以通過查表的方式來獲取，表即為prio_to_weight。
問題三：請簡述CFS調度器是如何工作的。
CFS調度器拋棄以前固定時間片和固定調度周期的演算法，採用進程權重值的比重來量化和計算實際運行時間。引入虛擬時鐘的概念，每個進程的虛擬時間是實際運行時間相對nice值為0的權重的比例值。進程按照各自不同的速率比在物理時鐘節拍內前進。nice值小的進程，優先順序高且權重大，其虛擬時鐘比真實時鐘跑得慢，但是可以獲得比較多的運行時間；反之，nice值大的進程，優先順序低，權重也低，其虛擬時鐘比真實時鐘跑得快，獲得比較少的運行時間。CFS調度器總是選擇虛擬時鐘跑得慢的進程，類似一個多級變速箱，nice值為0的進程是基準齒輪，其他各個進程在不同變速比下相互追趕，從而達到公正公平。
問題四：CFS調度器中的vruntime是如何計算的？
vruntime=(delta_exec*nice_0_weight)/weight。其中，delta_exec為實際運行時間，nice_0_weight為nice為0的權重值，weight表示該進程的權重值。在update_curr()函數中，完成了該值的計算，此時，為了計算高效，將計算方式變成了乘法和移位vruntime=(delta_exec*nice_0_weight*inv_weight)>>shift，其中inv_weight=2^32/weight，是預先計算好存放在prio_to_wmult中的。
問題五：vruntime是何時更新的？
創建新進程，加入就緒隊列，調度tick等都會更新當前vruntime值。
問題六：CFS調度器中的min_vruntime有什麼作用？
min_vruntime在CFS就緒隊列數據結構中，單步遞增，用於跟蹤該就緒隊列紅黑樹中最小的vruntime。
問題七：CFS調度器對新創建的進程和剛喚醒的進程有何關照？
對於睡眠進程，其vruntime在睡眠期間不增長，在喚醒後如果還用原來的vruntime值，會進行報複性滿載運行，所以要修正vruntime，具體在enqueue_entity()函數中，計算公式為vruntime+=min_vruntime，vruntime=MAX(vruntime, min_vruntime-sysctl_sched_lantency/2)。
對於新創建的進程，需要加上一個調度周期的虛擬是時間(sched_vslice())。首先在task_fork_fair()函數中，place_entity()增加了調度周期的虛擬時間，相當於懲罰，se->vruntime=sched_vslice()。接著新進程在添加到就緒隊列時，wake_up_new_task()->activate_task()->enqueue_entity()函數里，se->vruntime+=cfs_rq->min_vruntime。
問題八：如何計算普通進程的平均負載load_avg_contrib？runnable_avg_sum和runnable_avg_period分別表示了什麼含義？
load_avg_contrib=runnable_avg_sum*weight/runnable_avg_period。
runnable_avg_sum為調度實體的可運行狀態下總衰減累加時間。
runnable_avg_period記錄的是上一次更新時的總周期數（一個周期是1024us），即調度實體在調度器中的總衰減累加時間。
runnable_avg_sum越接近runnable_avg_period，則平均負載越大，表示該調度實體一直在占用CPU。
問題九：內核代碼中定義了若幹個表，請分別說出它們的含義，比如prio_to_weight、prio_to_wmult、runnable_avg_yN_inv、runnable_avg_yN_sum。
prio_to_weight表記錄的是nice值對應的權重值。
prio_to_wmult表記錄的是nice值對應的權重值倒轉後的值inv_weight=2^32/weight。
runnable_avg_yN_inv表是為了避免CPU做浮點計算，提前計算了公式2^32*實際衰減因數（第32ms約為0.5）的值，有32個下標，對應過去0~32ms的負載貢獻的衰減因數。
runnable_avg_yN_sum表為1024*（y+y^2+…+y^n），y為實際衰減因數，n取1~32。（實際衰減因數下圖所示）
圖 實際衰減因數
問題十：如果一個普通進程在就緒隊列里等待了很長時間才被調度，那麼它的平均負載該如何計算？
一個進程等待很長時間之後（過了很多個period），原來的runnable_avg_sum和runable_ave_period值衰減後可能變成0，相當於之前的統計值被清0。
