歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

Linux CFS 虛擬時間更新

參考文獻:《linux kernel development》P43 下載見 http://www.linuxidc.com/Linux/2011-06/37776.htm

P43講到關於linux的CFS的調度依據vruntime的時候,想對起做一些深入的了解,加深記憶。

我就暫且從書上所提到的Update_curr函數開始,前面的某些函數調用過程,待清楚之後再做分享。

首先做摘要:

nice和prio的關系如下:

#define NICE_TO_PRIO(nice) (MAX_RT_PRIO+nice+20)

#define PRIO_TO_NICE(prio) (prio-MAX_RT_PRIO-20)

其中,MAX_RT_PRIO=100,nice的值在-20到19之前,那麼優先級就在100 -139之間。

prio和weight之間的轉換關系參見prio_to_weight。

CFS可實現幾種不同的公平策略,這些策略是根據調度的對象的不同來區分的。

默認的是不開組調度的公平策略,即調度的單位是每個調度實體。我們來詳細看一下是怎麼調度的:

  假設現在系統有A,B,C三個進程,A.weight=1,B.weight=2,C.weight=3.那麼我們可以計算出整個公平調度隊列的總權重是cfs_rq.weight = 6,很自然的想法就是,公平就是你在重量中占的比重的多少來拍你的重要性,那麼,A的重要性就是1/6,同理,B和C的重要性分別是2/6,3/6.很顯然C最重要就應改被先調度,而且占用的資源也應該最多,即假設A,B,C運行一遍的總時間假設是6個時間單位的話,A占1個單位,B占2個單位,C占三個單位。這就是CFS的公平策略。

   linux內核采用了計算公式:

 ideal_time = sum_runtime *se.weight/cfs_rq.weight

ideal_time:每個進程應該運行的時間

sum_runtime:運行隊列中所有任務運行完一遍的時間

se.weight:當前進程的權重

cfs.weight:整個cfs_rq的總權重

這裡se.weight和cfs.weight根據上面講解我們可以算出,sum_runtime是怎們計算的呢,linux內核中這是個經驗值,其經驗公式是:

(1) sum_runtime=sysctl_sched_min_granularity *nr_running(if 進程數 > 5)

(2) sum_runtime=sysctl_sched_latency = 20ms           (if 進程數 <=5)

注:sysctl_sched_min_granularity =4ms

linux內核代碼中是通過一個叫vruntime的變量來實現上面的原理的,即:

每一個進程擁有一個vruntime,每次需要調度的時候就選運行隊列中擁有最小vruntime的那個進程來運行,vruntime在時鐘中斷裡面被維護,每次時鐘中斷都要更新當前進程的vruntime,即vruntime以如下公式逐漸增長:

  (1) vruntime +=  delta* NICE_0_LOAD/se.weight;(if curr.nice!=NICE_0_LOAD)

  (2)vruntime += delta;                      (ifcurr.nice=NICE_0_LOAD)

下面看看vruntime更新具體是怎麼實現的。


Update_curr:delta_exec=(unsignedlong)(now->curr->exec_starrt);

                      __update_curr(cfs_rq,curr,delta_exec);

__update_curr:delta_exec_weighted=calc_delta_fair(delta_exec,curr);

                       Curr->vruntime+=delta_exec_weighted;

Calc_delta_fair:   

if (unlikely(se->load.weight != NICE_0_LOAD)) 

1.        delta = calc_delta_mine(delta, NICE_0_LOAD, &se->load); 

2.         return delta; //nice=/!=NICE_0_LOAD

 

Calc_delta_mine: /* delta*=weight/lw */

 tmp = (u64)delta_exec * weight; 

1.    if (unlikely(tmp > WMULT_CONST)) 

2.            tmp = SRR(SRR(tmp, WMULT_SHIFT/2) * lw->inv_weight, 

3.                WMULT_SHIFT/2); 

4.        else 

5.            tmp = SRR(tmp * lw->inv_weight, WMULT_SHIFT);

從這些代碼可以看出上述結論!

繼續摘抄。。。

在每次更新完vruntime之後,將會進行一次檢查,要不要設置調度位TIF_NEED_SCHED。

通過以上分析,我們基本上已經分析了不開組調度的情況下,進程一般的調度的原理。

附加

我們再舉一個極端的情況假設有兩個用戶A,B,注意這裡使用戶。A用戶有1個進程a且a.weight=1;B用戶也有1個進程b且b.weight=1000,根據上面的公平理論,我們可以發現B用戶可能會一直霸占cpu,在用戶更多的情況下,肯能會更糟。為了解決這種問題,CFS引入了組調度,即調度的對象不僅僅限於調度實體,而是可以以用戶為調度單位,即A和B位調度單位的話,A B各占50%的CPU。而且只要一個組裡的進程被調度,其他的進程也會跟著被調度,但是占用的CPU卻至於用戶有關。

在文件sched.c中可以找到關於NICE_TO_PRIO和PRIO_TO_NICE以及prio_to_weight的定義。

Copyright © Linux教程網 All Rights Reserved