- 論壇徽章:
- 0
|
總結(jié)了篇關(guān)于cfs調(diào)度器的文檔
喜歡pdf的可以查看檔案~
CFS 調(diào)度器
--wxc200
大家好哈，
兄弟最近在學(xué)習(xí)調(diào)度器，有點(diǎn)兒心得，更多得是迷惑，寫出心得來與大家分享，貼出迷惑來請(qǐng)大家解答。呵呵
linux自2.6.23后引入了一種新的調(diào)度器，叫'Completely Fair Scheduler'（wiki）.是由Ingo Molnar在很短的時(shí)間內(nèi)寫的。他與的cfs代碼是對(duì)之前另一種調(diào)度器 "O(1) scheduler" 的替換.
先扯一下o(1)調(diào)度.
先看wiki的解釋:
"An O(1) scheduler is a kernel scheduling design that can schedule processes within a constant amount of time, regardless of how many processes are running on the operating system (OS)."
Understanding Linux Kernel(3th) 這本書chapter 7講的進(jìn)程調(diào)度,7.2節(jié)提到"Scheduling Algorithm",說2.6 對(duì)進(jìn)程的選擇是constant time,兼顧了批處理和交互式進(jìn)程.進(jìn)程分類,實(shí)時(shí)進(jìn)程(又分為SCHED_FIFL AND SCHED_RR)和普通進(jìn)程.
最主要的問題是這些進(jìn)程怎么組織的,簡單看下結(jié)構(gòu):
沒辦法傳圖片,請(qǐng)參照附件"數(shù)組".
它有兩個(gè)數(shù) 組,active里面是has time-slice 的,expired數(shù)組是out-of-slice。簡單的說，一個(gè)普通的進(jìn)程被調(diào)度運(yùn)行后，放在active里，當(dāng)其時(shí)間片用光后，可能就要移到 expired數(shù)組里了。說“可能”是因?yàn)橛械倪M(jìn)程就不移走。比如交互式進(jìn)程。
說白了,就是把所有的process按照優(yōu)先級(jí)掛在鏈表上,從里面按照優(yōu)先級(jí)高低選擇第一個(gè)不為空的進(jìn)程運(yùn)行.
普通進(jìn)程的優(yōu)先級(jí)是100~139,實(shí)時(shí)進(jìn)程要更低,這符合調(diào)度的算法.
我有點(diǎn)等不及了,咱們直接奔cfs吧~
另外有點(diǎn)就是,引入hrtimer之后,進(jìn)程調(diào)度還是在tick中斷完成的.每個(gè)tick都會(huì)檢查進(jìn)程是否應(yīng)該調(diào)度,當(dāng)然,主動(dòng)讓cpu(即調(diào)用scheduler().)的就不算了吧...
hrtimer那部分東東等咱們聊完了cfs再說，那個(gè)主要是在原有的時(shí)間管理layer上新添加了“時(shí)間事件”，把時(shí)間中斷以事件的方式注冊(cè)。精確度由之前的hz提升到了ns（需要硬件支持）。。。
cfs
Documentation/scheduler/sched-design-CFS.txt 介紹了cfs相關(guān)東西，也可以在線看.
我按照我的理解來“添油加醋”地翻譯下。
1 概括
“80% of CFS's design can be summed up in a single sentence: CFS basically models
an "ideal, precise multi-tasking CPU" on real hardware.”
""Ideal multi-tasking CPU" is a (non-existent  ) CPU that has 100% physical
power and which can run each task at precise equal speed, in parallel, each at
1/nr_running speed. For example: if there are 2 tasks running, then it runs
each at 50% physical power --- i.e., actually in parallel.
"
模 擬了個(gè)理想的，多任務(wù)cpu.假如有n個(gè)進(jìn)程，那么每個(gè)進(jìn)程 的執(zhí)行速度是1/n,,即所有的任務(wù)都是并行執(zhí)行的。我認(rèn)為就算是有并行執(zhí)行的cpu，速度也不應(yīng)該完全平均，按照優(yōu)先級(jí)再分比較劃算。比如2個(gè)進(jìn) 程，a,b，a 的優(yōu)先級(jí)是b的兩 倍，那么就照著速度比a:b = 2:1唄~
“On real hardware, we can run only a single task at once, so we have to
introduce the concept of "virtual runtime." The virtual runtime of a task
specifies when its next timeslice would start execution on the ideal
multi-tasking CPU described above. In practice, the virtual runtime of a task
is its actual runtime normalized to the total number of running tasks. ”
當(dāng)然沒有這種cpu,故引進(jìn)了個(gè)新概念"virtual runtime",這個(gè)概念真是折磨人好久。我曾經(jīng)在clf上發(fā)帖子問過，有個(gè)兄弟回復(fù)還是不錯(cuò)的。后面看過代碼后，我的理解是：1） 紅黑樹結(jié)點(diǎn)排列的值 2） 每次task run time轉(zhuǎn)換的一個(gè)值 .
先看上文顏色部分，我真是很難翻譯它~ 照字面理解，是實(shí)際運(yùn)行時(shí)間與任務(wù)數(shù)量的一個(gè)比值？ 我舉個(gè)例子來說明它是怎么計(jì)算 的吧。。
在 __update_curr(）這個(gè)函數(shù)里，會(huì)更新當(dāng)前任務(wù)的運(yùn)行時(shí)間信息。假如一個(gè)任務(wù)a自上次調(diào)度到這次調(diào)度時(shí)間間隔為delta,那么它的 vrumtime的增量是按照這個(gè)公式：delta * NICE_0_LOAD / a->se.load。假如把NICE_0_LOAD / a->se.load作為一個(gè)比值p的話，我們可以這么描述p的變化：優(yōu)先級(jí)越高，p越小。這個(gè)load是與nice值 相關(guān)的，有一個(gè)靜態(tài)的數(shù)組，我后面在代碼里會(huì)介紹。
所以，一堆進(jìn)行都運(yùn)行了一段時(shí)間delta，那么它們的vrumtime就遵循上面的公式。很明顯，優(yōu)先級(jí)最大的進(jìn)程vrumtime增量最小。。。
2 操作細(xì)節(jié)
cfs就是通過追蹤這個(gè)vruntime來進(jìn)行任務(wù)調(diào)度的。它總是選 vruntime最小的進(jìn)程來運(yùn)行。
3 紅黑樹。
紅黑樹這個(gè)數(shù)據(jù)結(jié)構(gòu)在內(nèi)核里用得還不少嘛，不過俺不太懂。哪位兄弟給掃掃盲？ hrtimer里也用到了red-black-tree。這里把進(jìn)程的vruntime用rb-tree來存儲(chǔ)。
4 一些feature
cfs has no time-slice concept.o(1)有的，cfs沒有“明顯”得用，它偷偷摸摸地用。呵呵 翻譯完這幾段咱再說這個(gè)。文檔里面那個(gè)接口估計(jì)是用來調(diào)整“最小粒度”的。用于“桌面”和“服務(wù)器“兩 種不同的調(diào)度。后者可能不太希望頻繁的調(diào)度，浪費(fèi)時(shí)間。前者則希望面面俱到--”不患寡婦而患不均也“
5 調(diào)度policy
SCHED_FIFO/_RR are implemented in sched_rt.c and are as specified by POSIX. 實(shí)時(shí)進(jìn)程調(diào)度
實(shí)時(shí)調(diào)度和普通進(jìn)程調(diào)度。
6 調(diào)度的類。
調(diào)度哭可以模塊化注冊(cè)，所以你可以選擇實(shí)時(shí)調(diào)度或者是cfs調(diào)度。不錯(cuò)！
sched_fair.c文件實(shí)現(xiàn)了cfs調(diào)度的所以classes
7 組調(diào)度。
不光是普通進(jìn)程，組調(diào)度也實(shí)現(xiàn)了。。這個(gè)是后來一個(gè)patch加的。
×××××××××××××××××××××××××××××××××××
上面 是對(duì)著內(nèi)核的一篇文檔，簡要地說了幾部分 。。。在正式進(jìn)行我們的hack之前，先嘮叨幾句，算是個(gè)總結(jié)和感性的認(rèn)識(shí)吧~吼吼
關(guān)于實(shí)時(shí)進(jìn)程的調(diào)度，這一次先不分析，它和o1差不多，還保持著優(yōu)先級(jí)數(shù)組的做法，那是”上流社會(huì)“玩兒的游戲，后面再折騰它。”普通大眾“們玩兒的就是cfs了。
cfs調(diào)度，我寫兩 部分，一部分是普通進(jìn)程的調(diào)度，沒有組的概念。一部分是組的調(diào)度。我個(gè)人覺得組得調(diào)度比較難理解~ 這幾天一直在思考。。。今天下午好像豁然開朗了。。。畫了個(gè)草圖，到后面我做出這張圖來，大家看看對(duì)不對(duì) 
咱們先說普通進(jìn)程的調(diào)度
關(guān)于普通進(jìn)程的組織，應(yīng)該有這么一種印象。
有一個(gè)隊(duì)列，叫cfs_rq,里面維護(hù)了個(gè)紅黑樹。每一個(gè)task_struct has a se,稱為調(diào)度實(shí)體。它就代表了一個(gè)被調(diào)度的進(jìn)程，里面有此進(jìn)程的一些信息，比如前面提到的vruntime.
一個(gè)進(jìn)程創(chuàng)建的時(shí)候，就會(huì)被放置在這個(gè)紅黑樹里。它自己的位置是由它的vruntime值 來決定的。在每個(gè)tick中斷的時(shí)候，會(huì)更新進(jìn)程的信息，并檢查這個(gè)紅黑樹，判斷某些進(jìn)程是不是要被替換掉。
現(xiàn)在我們來想象下面一個(gè)例程。
進(jìn) 程a被創(chuàng)建了，sched_fork()會(huì)做一些新創(chuàng)建進(jìn)程調(diào)度方面的初始化。然后應(yīng)該嘗試把此進(jìn)程放到隊(duì)列里啊，讓它被調(diào)度。 set_task_cpu()做了這部分工作。然后這個(gè)進(jìn)程如果不是實(shí)時(shí)進(jìn)程，就讓它跟cfs的類綁定在一塊兒，這樣下面用到調(diào)度的一些方法，就會(huì)到 cfs相關(guān)的類去找嘍~ 這時(shí)候如果搶占打開了，會(huì)去調(diào)度一次，以讓新創(chuàng)建的進(jìn)程有機(jī)會(huì)被調(diào)度一次�；蛘咴谙乱粋�(gè)tick的時(shí)候，會(huì)檢查已經(jīng)紅黑樹，以確認(rèn)這個(gè)進(jìn)程是不是調(diào)度。（注：上面紅色這句有點(diǎn)胡扯的嫌疑，請(qǐng)明白人指點(diǎn)）
比如在每個(gè)tick中斷的時(shí)候，會(huì)去紅黑樹里面找vruntime最小的那個(gè)（紅黑樹最左邊的葉子）去調(diào)度。那么這個(gè)調(diào)度過程，所有用到的方法，就是上面提到的cfs的類給實(shí)現(xiàn)的。
最后，大家再對(duì)rb-tree里面的任務(wù)結(jié)點(diǎn)有個(gè)感性的認(rèn)識(shí)吧：
優(yōu)先級(jí)高的進(jìn)程，總是靠左，以有最大調(diào)度機(jī)會(huì)。比如說有n個(gè)進(jìn)程，那么在一段時(shí)間內(nèi)，應(yīng)該把n個(gè)進(jìn)程都運(yùn)行一遍。這兒有兩三個(gè)問題，一段時(shí)間是多久？每個(gè)進(jìn)程有多少時(shí)間去運(yùn)行呢？每個(gè)進(jìn)程分到的運(yùn)行時(shí)間跟vruntime有什么關(guān)系呢？
一段時(shí)間，與運(yùn)行著的進(jìn)程數(shù)目有關(guān)。進(jìn)程越多，時(shí)間越長。每個(gè)進(jìn)程并不是平均分配這些時(shí)間的。按照我的理解，分到這個(gè)時(shí)間越多的進(jìn)程，后面vruntime增長得越慢。
上面 這幾句話，我可是暈了近一個(gè)星期才明白的。不知道跟大家的理解一致么？
本 來我錯(cuò)誤得理解是這樣的，完全公平調(diào)度么，當(dāng)然所有的進(jìn)程有同樣的運(yùn)行時(shí)間。如果是這樣，那么rb-tree就沒用了。因?yàn)槊總�(gè)結(jié)點(diǎn)都一樣的值。所以，請(qǐng) 大家有這樣一種概念：兩 個(gè)進(jìn)程，a優(yōu)先級(jí)特別低，b特高。假如現(xiàn)在有n個(gè)正被調(diào)度的進(jìn)程，它們都被調(diào)度一遍的時(shí)間是delta，那么b會(huì)占很高的時(shí)間，a 很低的時(shí)間。運(yùn)行完成后，b還是在很靠左的地方呆著，而a一定往最靠右的地方。。。。哎，表述不清啊，，最好畫個(gè)圖。。。這樣就為了讓b得到更常的運(yùn)行時(shí) 間。。。而其vruntime仍然很�。ǹ梢詤⒄丈戏忄]件里面那個(gè)計(jì)算vruntime的公式）
好了
我們開始真正的代碼旅行吧。
1 幾個(gè)重要的數(shù)據(jù)結(jié)構(gòu)
1）task_struct : 大家都知道這個(gè)。
struct task_struct {
...
int prio, static_prio, normal_prio; 進(jìn)程的優(yōu)先級(jí)
unsigned int rt_priority;實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)
const struct sched_class *sched_class; 調(diào)度類，一堆函數(shù)指針，實(shí)現(xiàn)調(diào)度
struct sched_entity se;調(diào)度實(shí)體 一個(gè)進(jìn)程對(duì)應(yīng)一個(gè)調(diào)度實(shí)體，，
struct sched_rt_entity rt;
....
}
2) sched_class 調(diào)度相關(guān)的函數(shù)指針。
struct sched_class {
...
void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup); 入列
void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);出列
void (*yield_task) (struct rq *rq);
void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int sync);檢查當(dāng)前進(jìn)程可否被新進(jìn)程搶占
struct task_struct * (*pick_next_task) (struct rq *rq); 選擇下一個(gè)進(jìn)程運(yùn)行
void (*put_prev_task) (struct rq *rq, struct task_struct *p);
#ifdef CONFIG_SMP
int (*select_task_rq)(struct task_struct *p, int sync);
....
#ifdef CONFIG_FAIR_GROUP_SCHED 請(qǐng)格外留意此宏。。。。跟組調(diào)度相關(guān)的，，暫時(shí)不管它，后面跟組相關(guān)的調(diào)度再回來看它。
void (*moved_group) (struct task_struct *p);
#endif
};
3） 調(diào)度實(shí)體
struct sched_entity {
struct load_weight load; /* for load-balancing */ nice對(duì)應(yīng)的load值
struct rb_node run_node; 紅黑樹結(jié)點(diǎn)
struct list_head group_node;
unsigned int on_rq; 這個(gè)是什么呢？不知道
u64 exec_start; 上次開始調(diào)度時(shí)的運(yùn)行時(shí)間
u64 sum_exec_runtime; 總運(yùn)行時(shí)間
u64 vruntime;呵呵 都知道了
u64 prev_sum_exec_runtime; 上次調(diào)度總運(yùn)行時(shí)間
...
#ifdef CONFIG_FAIR_GROUP_SCHED 如果是組調(diào)度的話，就多了些部分。
struct sched_entity *parent;
/* rq on which this entity is (to be) queued: */
struct cfs_rq *cfs_rq;
/* rq "owned" by this entity/group: */
struct cfs_rq *my_q;
#endif
}
4)cfs 運(yùn)行隊(duì)列
/* CFS-related fields in a runqueue */
struct cfs_rq {
struct load_weight load;
unsigned long nr_running;
u64 exec_clock;
u64 min_vruntime;
5)大boss，運(yùn)行隊(duì)列
struct rq {
,...
unsigned long nr_running;
#define CPU_LOAD_IDX_MAX 5
unsigned long cpu_load[CPU_LOAD_IDX_MAX];
...
struct cfs_rq cfs;
..
struct task_struct *curr, *idle;
}
6）調(diào)度相關(guān)類
/*
* All the scheduling class methods:
*/
static const struct sched_class fair_sched_class = {
.next = &idle_sched_class,
.enqueue_task = enqueue_task_fair,
.dequeue_task = dequeue_task_fair,
.yield_task = yield_task_fair,
.check_preempt_curr = check_preempt_wakeup,
.pick_next_task = pick_next_task_fair,
.put_prev_task = put_prev_task_fair,
#ifdef CONFIG_SMP
.select_task_rq = select_task_rq_fair,
.load_balance = load_balance_fair,
.move_one_task = move_one_task_fair,
#endif
.set_curr_task = set_curr_task_fair,
.task_tick = task_tick_fair,
.task_new = task_new_fair,
.prio_changed = prio_changed_fair,
.switched_to = switched_to_fair,
#ifdef CONFIG_FAIR_GROUP_SCHED
.moved_group = moved_group_fair,
#endif
};
2 吃代碼
上面幾個(gè)結(jié)構(gòu)體的關(guān)系還是很好理解的，它們的關(guān)系我本來想畫個(gè)圖表示下的，覺得有點(diǎn)麻煩，何況也不難，我就不畫了。。直接進(jìn)代碼了哈~
在進(jìn)行之前呢，先介紹兩 篇文章，是一個(gè)網(wǎng)友寫的。之前和他聊cfs，后來我迷糊了，他沒迷糊，就寫了這篇文章。。。還不錯(cuò)。
Linux進(jìn)程管理之CFS調(diào)度器分析
Linux進(jìn)程管理之CFS組調(diào)度分析
大家的理解差不多，他寫得很條理，為了防止雷同，雷著大家了，我不會(huì)引用它里面的文字的。我就在邊讀代碼的過程中邊把自己的體驗(yàn)和疑惑貼出來，大家一同討論吧~ 錯(cuò)誤，一定要指出我的錯(cuò)誤啊~呵呵
咱們先從新創(chuàng)建的一個(gè)進(jìn)程說起吧。
1) kernel/fork.c里,fork routine,do_fork() will create a new process,if its state is running,it will
call wake_up_new_task() to wake up the newly created process FOR THE FIRST TIME.
do_fork(){
...
if (unlikely(clone_flags & CLONE_STOPPED)) {
...
} else {
wake_up_new_task(p, clone_flags);
}
...
}
2) 這個(gè)函數(shù)做什么呢？
void wake_up_new_task(struct task_struct *p, unsigned long clone_flags)
{
unsigned long flags;
struct rq *rq;
rq = task_rq_lock(p, &flags);順序操作運(yùn)行隊(duì)列
BUG_ON(p->state != TASK_RUNNING);
update_rq_clock(rq);
p->prio = effective_prio(p); 計(jì)算priority,,普通進(jìn)程的priority就是static priority
if (!p->sched_class->task_new || !current->se.on_rq) {如果條件不滿足，直接入列，但請(qǐng)注意active_task()的最后參數(shù)0，不喚醒
activate_task(rq, p, 0);
} else {
/*
* Let the scheduling class do new task startup
* management (if any):
*/
p->sched_class->task_new(rq, p);調(diào)用完全公平類里面的task_new做些初始化的操作。
inc_nr_running(rq);增加運(yùn)行隊(duì)列的運(yùn)行進(jìn)程數(shù)目
}
trace_sched_wakeup_new(rq, p);
check_preempt_curr(rq, p, 0); 可不可以搶占當(dāng)前進(jìn)程？
#ifdef CONFIG_SMP
if (p->sched_class->task_wake_up)
p->sched_class->task_wake_up(rq, p);
#endif
task_rq_unlock(rq, &flags);
}
3) 先看task_new()吧，它會(huì)掉到fair_sched_class類里的task_new_fair.
static void task_new_fair(struct rq *rq, struct task_struct *p)
{
struct cfs_rq *cfs_rq = task_cfs_rq(p);
struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
int this_cpu = smp_processor_id();
sched_info_queued(p);
update_curr(cfs_rq); 更新cfs的一些信息
place_entity(cfs_rq, se, 1);初始化se在cfs里的信息，包括vruntime
/* 'curr' will be NULL if the child belongs to a different group */
if (sysctl_sched_child_runs_first && this_cpu == task_cpu(p) &&
curr && curr->vruntime < se->vruntime) {
/*
* Upon rescheduling, sched_class::put_prev_task() will place
* 'current' within the tree based on its new key value.
*/
swap(curr->vruntime, se->vruntime);
resched_task(rq->curr);
}
enqueue_task_fair(rq, p, 0); 放進(jìn)隊(duì)列里面
}
4) 我們先看update_curr()吧
static void update_curr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr;
u64 now = rq_of(cfs_rq)->clock;
unsigned long delta_exec;
if (unlikely(!curr))
return;
/*
* Get the amount of time the current task was running
* since the last time we changed load (this cannot
* overflow on 32 bits):
*/
delta_exec = (unsigned long)(now - curr->exec_start);計(jì)算自上次調(diào)度此進(jìn)程到這次又調(diào)度，經(jīng)過的時(shí)間
這個(gè)時(shí)間比較鬼異，是多久呢？假如在運(yùn)行隊(duì)列里的n個(gè)進(jìn)程之一的a,再一次被調(diào)度到時(shí)，這個(gè)delta_exec是多大呢？ 如果中途有進(jìn)程退出或睡眠，
那么運(yùn)行隊(duì)列會(huì)動(dòng)態(tài)更新的，所以這個(gè)delta_exec的變化曲線是什么樣子的難說。
__update_curr(cfs_rq, curr, delta_exec); 把剛計(jì)算出來的運(yùn)行時(shí)間作為參數(shù)傳進(jìn)去，它做什么事情呢？
curr->exec_start = now;呵呵，更新完了立刻打個(gè)時(shí)間戳。
if (entity_is_task(curr)) { 這個(gè)條件比較有趣，我喜歡。跟過去發(fā)現(xiàn)是這樣定義的：
"/* An entity is a task if it doesn't "own" a runqueue */
#define entity_is_task(se) (!se->my_q) " 如果是組調(diào)度，調(diào)度實(shí)體可能代表一個(gè)組，不單單是一個(gè)task。就是看看有沒有my_q這個(gè)指針了，
即有沒有它c(diǎn)ontrol的cfs_rq
如果是task,條件滿足，
struct task_struct *curtask = task_of(curr);
cpuacct_charge(curtask, delta_exec);
account_group_exec_runtime(curtask, delta_exec); 這兩 個(gè)不管了，看不懂
}
} |
-
-
cfs.pdf
2009-03-02 14:53 上傳
點(diǎn)擊文件名下載附件
712.74 KB, 下載次數(shù): 1227
評(píng)分
-
查看全部評(píng)分
|
免費(fèi)注冊(cè)
發(fā)表于 2009-03-02 14:52
發(fā)表于 2009-03-02 15:05
