|
unsigned long nr_uninterruptible; 下面幾個(gè)指針?lè)謩e指向當(dāng)前運(yùn)行的進(jìn)程、空閑進(jìn)程、被停止運(yùn)行的進(jìn)程 struct task_struct *curr, *idle, *stop; unsigned long next_balance; struct mm_struct *prev_mm;進(jìn)程切換時(shí)存放被替換進(jìn)程內(nèi)存描述符 字段clock用于實(shí)現(xiàn)就緒隊(duì)列自身的時(shí)鐘，每次調(diào)用周期性調(diào)度器時(shí)，都會(huì)更新clock的值。內(nèi)核還提供了函數(shù)update_rq_clock，可在操作就緒隊(duì)列的調(diào)度中多次調(diào)用。 u64 clock; ...... }; 調(diào)度類(lèi)結(jié)構(gòu)體在文件include/linux/sched.h中定義，如下： struct sched_class { next字段將各個(gè)調(diào)度類(lèi)按重要性鏈接起來(lái)，最重要的是實(shí)時(shí)進(jìn)程，其次是完全公平進(jìn)程，再次是空閑進(jìn)程 const struct sched_class *next; 向就緒隊(duì)列添加一個(gè)新進(jìn)程，在進(jìn)程從睡眠狀態(tài)變?yōu)榭蛇\(yùn)行狀態(tài)調(diào)用該操作 void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags); 將一個(gè)進(jìn)程從就緒隊(duì)列中去除。 void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags); 當(dāng)進(jìn)程志愿放棄對(duì)處理器的控制權(quán)時(shí)，可使用系統(tǒng)調(diào)用sched_yield，這將導(dǎo)致內(nèi)核調(diào)用 函數(shù)yield_task void (*yield_task) (struct rq *rq); 進(jìn)程放棄CPU控制權(quán)并將控制權(quán)交給p進(jìn)程 bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt); 用一個(gè)新喚醒的進(jìn)程來(lái)?yè)屨籍?dāng)前進(jìn)程， void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags); 選擇下一個(gè)需要運(yùn)行的進(jìn)程 struct task_struct * (*pick_next_task) (struct rq *rq); 通知調(diào)度器類(lèi)當(dāng)前運(yùn)行的進(jìn)程將要被另一個(gè)進(jìn)程代替。 void (*put_prev_task) (struct rq *rq, struct task_struct *p); ...... 用于設(shè)置調(diào)度隊(duì)列的當(dāng)前進(jìn)程，例如cfs_rq->curr void (*set_curr_task) (struct rq *rq); 由周期性調(diào)度器調(diào)用，更新一些時(shí)間統(tǒng)計(jì)量 void (*task_tick) (struct rq *rq, struct task_struct *p, int queued); 當(dāng)新進(jìn)程創(chuàng)建時(shí)調(diào)用初始化一些特定調(diào)度器類(lèi)的東西，并設(shè)置重調(diào)度標(biāo)志TIF_NEED_RESCHED void (*task_fork) (struct task_struct *p); ...... }; 調(diào)度器操作比進(jìn)程更一般的實(shí)體，每個(gè)進(jìn)程描述結(jié)構(gòu)中都嵌有一個(gè)調(diào)度實(shí)體結(jié)構(gòu)，但并不是一個(gè)調(diào)度實(shí)體就等于一個(gè)進(jìn)程，有時(shí)候?qū)⒁唤M進(jìn)程集合起來(lái)表示一個(gè)調(diào)度實(shí)體。調(diào)度實(shí)體結(jié)構(gòu)在文件include/linux/sched.h中定義，如下： struct sched_entity { load記錄一個(gè)調(diào)度實(shí)體負(fù)荷權(quán)重 struct load_weight load; /* for load-balancing */ 紅黑樹(shù)節(jié)點(diǎn)，使得實(shí)體可以在紅黑樹(shù)上排序 struct rb_node run_node; 用于鏈接到就緒隊(duì)列的cfs_tasks字段上 struct list_head group_node; 表示實(shí)體是否在就緒隊(duì)列上 unsigned int on_rq; 當(dāng)新進(jìn)程被加入就緒隊(duì)列或者在周期性調(diào)度器中，會(huì)計(jì)算當(dāng)前值和exec_start之間的差值，將差值加到sum_exec_runtime中，exec_start則更新為當(dāng)前時(shí)間 u64 exec_start; 記錄消耗的CPU時(shí)間 u64 sum_exec_runtime; 保存進(jìn)程的虛擬時(shí)間，關(guān)于虛擬時(shí)間后面講詳細(xì)講解 u64 vruntime; 當(dāng)進(jìn)程失去CPU控制權(quán)時(shí)將sum_exec_runtime保存到prev_sum_exec_runtime中 u64 prev_sum_exec_runtime; ...... 下面是跟組調(diào)度相關(guān)的字段 #ifdef CONFIG_FAIR_GROUP_SCHED struct sched_entity *parent; 建立組調(diào)度中調(diào)度實(shí)體的層次關(guān)系 struct cfs_rq *cfs_rq; 組所屬的調(diào)度隊(duì)列 /* rq "owned" by this entity/group: */ struct cfs_rq *my_q;組內(nèi)部的調(diào)度隊(duì)列 #endif }; 2 優(yōu)先級(jí)與負(fù)荷權(quán)重2.1優(yōu)先級(jí)的計(jì)算前面講過(guò)優(yōu)先級(jí)有3個(gè)，static_prio、normal_prio和prio。Static_prio在進(jìn)程啟動(dòng)時(shí)靜態(tài)設(shè)置可用nice系統(tǒng)調(diào)用修改；normal_prio與靜態(tài)優(yōu)先級(jí)和調(diào)度策略有關(guān)，調(diào)度策略可能被修改；prio是調(diào)度算法中用到的優(yōu)先級(jí)，他可能被內(nèi)核臨時(shí)改變，比如一個(gè)高優(yōu)先級(jí)的進(jìn)程在使用的互斥量，被一個(gè)低優(yōu)先級(jí)進(jìn)程占據(jù)了，這是就要臨時(shí)提高低優(yōu)先級(jí)的優(yōu)先級(jí)，這個(gè)優(yōu)先級(jí)就保存在prio中。 在用戶空間中，用nice系統(tǒng)調(diào)用設(shè)置進(jìn)程的靜態(tài)優(yōu)先級(jí)，該nice值的范圍是-20到19之間，值越低優(yōu)先級(jí)越高。內(nèi)核內(nèi)部表示優(yōu)先級(jí)的的范圍是0到139，同樣也是值越低優(yōu)先級(jí)越高。從0到99專(zhuān)事實(shí)進(jìn)程使用。Nice值-20到19映射的范圍是100到139. 優(yōu)先級(jí)prio的獲取是通過(guò)函數(shù)effective_prio來(lái)實(shí)現(xiàn)的，如下： 程序首先計(jì)算進(jìn)程的普通優(yōu)先級(jí)然后判斷進(jìn)程的優(yōu)先級(jí)是否小于MAX_RT_PRIO，這里并不考慮調(diào)度策略。如果進(jìn)程優(yōu)先級(jí)在實(shí)時(shí)進(jìn)程優(yōu)先級(jí)范圍內(nèi)就直接返回其優(yōu)先級(jí)（prio）否則返回其普通優(yōu)先級(jí)。 static int effective_prio(struct task_struct *p) { p->normal_prio = normal_prio(p); if (!rt_prio(p->prio)) return p->normal_prio; return p->prio; } 【effective_prio--->normal_prio】 由于實(shí)時(shí)進(jìn)程中，進(jìn)程描述符p->rt_priority字段表示的優(yōu)先級(jí)是其數(shù)值越大優(yōu)先級(jí)越高，與內(nèi)核內(nèi)部表示優(yōu)先級(jí)的方法剛好相反，所以在內(nèi)核內(nèi)部?jī)?yōu)先級(jí)的計(jì)算方法是 MAX_RT_PRIO-1 - p->rt_priority;。函數(shù)__normal_prio僅僅是返回進(jìn)程的靜態(tài)優(yōu)先級(jí) return p->static_prio;。 static inline int normal_prio(struct task_struct *p) { int prio; if (task_has_rt_policy(p)) prio = MAX_RT_PRIO-1 - p->rt_priority; else prio = __normal_prio(p); return prio; } 2.2 負(fù)荷權(quán)重的計(jì)算進(jìn)程每降低一個(gè)nice值，多獲得10%的CPU時(shí)間，每升高一個(gè)nice值，則放棄10%的CPU時(shí)間。為執(zhí)行該策略，內(nèi)核將優(yōu)先級(jí)轉(zhuǎn)換為權(quán)重。優(yōu)先級(jí)--權(quán)重轉(zhuǎn)換表： kernel/sched/sched.h static const int prio_to_weight[40] = { /* -20 */ 88761, 71755, 56483, 46273, 36291, /* -15 */ 29154, 23254, 18705, 14949, 11916, /* -10 */ 9548, 7620, 6100, 4904, 3906, /* -5 */ 3121, 2501, 1991, 1586, 1277, /* 0 */ 1024, 820, 655, 526, 423, /* 5 */ 335, 272, 215, 172, 137, /* 10 */ 110, 87, 70, 56, 45, /* 15 */ 36, 29, 23, 18, 15, }; 計(jì)算權(quán)重的函數(shù)是set_load_weight，空閑進(jìn)程的權(quán)重最小。負(fù)荷權(quán)重包含在數(shù)據(jù)結(jié)構(gòu)load_weight中如下： struct load_weight { unsigned long weight, inv_weight; }; Weight表示優(yōu)先級(jí)在表prio_to_weight中映射的權(quán)重，inv_weight表示被負(fù)荷權(quán)重除的結(jié)果，這些值也存在表prio_to_wmult中，這個(gè)表與表prio_to_weight中的值一一對(duì)應(yīng)。這些值的計(jì)算方法是(2^32/x)，x表示在表prio_to_weight中對(duì)應(yīng)位置中的值。 static void set_load_weight(struct task_struct *p) { int prio = p->static_prio - MAX_RT_PRIO; struct load_weight *load = &p->se.load; if (p->policy == SCHED_IDLE) { load->weight = scale_load(WEIGHT_IDLEPRIO); load->inv_weight = WMULT_IDLEPRIO; return; }
load->weight = scale_load(prio_to_weight[prio]); load->inv_weight = prio_to_wmult[prio]; } 3核心調(diào)度器調(diào)度器的實(shí)現(xiàn)基于兩個(gè)函數(shù)：周期性調(diào)度器函數(shù)和主調(diào)度器函數(shù)。 周期性調(diào)度器函數(shù)scheduler_tick：在內(nèi)核頻率HZ中斷處理函數(shù)中調(diào)用該函數(shù)。周期性調(diào)度函數(shù)的主要工作是更新各種時(shí)間統(tǒng)計(jì)量，在必要的時(shí)候進(jìn)行進(jìn)程 調(diào)度。在多CPU系統(tǒng)中它還進(jìn)行負(fù)載均衡處理。 主調(diào)度器函數(shù)schedule：如果進(jìn)程主動(dòng)放棄執(zhí)行而選擇另一個(gè)活動(dòng)進(jìn)程運(yùn)行就調(diào)用該函數(shù)。 周期性調(diào)度器函數(shù)和主調(diào)度器函數(shù)都不直接操作進(jìn)程，而是調(diào)用進(jìn)程所屬的操作類(lèi)來(lái)操作進(jìn)程。每個(gè)進(jìn)程都屬于某個(gè)調(diào)度類(lèi)（完全公平調(diào)度類(lèi)、實(shí)時(shí)調(diào)度類(lèi)）。 3.1 周期性調(diào)度器kernel/sched/core.c void scheduler_tick(void) { int cpu = smp_processor_id(); 獲取當(dāng)前CPU的cpu id struct rq *rq = cpu_rq(cpu);獲取當(dāng)前CPU對(duì)應(yīng)的就緒隊(duì)列結(jié)構(gòu) struct task_struct *curr = rq->curr;獲取當(dāng)前進(jìn)程的進(jìn)程描述符 在函數(shù)update_rq_clock中，更新就緒隊(duì)列的兩個(gè)成員rq->clock_task，rq->clock。 update_rq_clock(rq); 函數(shù)update_cpu_load_active負(fù)責(zé)更新就緒隊(duì)列的cpu_load[]數(shù)組。將數(shù)組中先前存儲(chǔ)的負(fù)荷值向后移動(dòng)一個(gè)位置，將當(dāng)前就緒隊(duì)列的負(fù)荷計(jì)入數(shù)組的第一個(gè)位置。 update_cpu_load_active(rq); 調(diào)用當(dāng)前進(jìn)程所屬的調(diào)度類(lèi)的task_tick函數(shù)，在該函數(shù)中更新一些時(shí)間計(jì)數(shù)，必要時(shí)調(diào)度其他活動(dòng)進(jìn)程來(lái)執(zhí)行。 curr->sched_class->task_tick(rq, curr, 0); ...... #ifdef CONFIG_SMP rq->idle_balance = idle_cpu(cpu); 在多處理器系統(tǒng)中進(jìn)行負(fù)載均衡，保證不同CPU的運(yùn)行隊(duì)列包含數(shù)量基本相同的可運(yùn)行進(jìn)程 trigger_load_balance(rq, cpu); #endif } 3.2 主調(diào)度器kernel/sched/core.c asmlinkage void __sched schedule(void) { struct task_struct *tsk = current； 提交一些阻塞的IO請(qǐng)求避免死鎖。 sched_submit_work(tsk); 主調(diào)度器的組要工作都在函數(shù)__schedule中實(shí)現(xiàn)。 __schedule(); } 【schedule--->__schedule】 static void __sched __schedule(void) { struct task_struct *prev, *next; unsigned long *switch_count; struct rq *rq; int cpu; need_resched: preempt_disable(); 禁止搶占 cpu = smp_processor_id(); 獲取當(dāng)前進(jìn)程CPU id rq = cpu_rq(cpu);獲取當(dāng)前cpu對(duì)應(yīng)的就緒隊(duì)列結(jié)構(gòu) 因?yàn)橐袚Q到其他活動(dòng)進(jìn)程，所以當(dāng)前進(jìn)程就變成了“以前的”進(jìn)程了。 prev = rq->curr; ...... 保存進(jìn)程切換計(jì)數(shù) switch_count = &prev->nivcsw; 標(biāo)志 PREEMPT_ACTIVE可以保證進(jìn)程被搶占但是不被移除就緒隊(duì)列 if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) { 如果進(jìn)程有非阻塞掛起信號(hào)，而且狀態(tài)為T(mén)ASK_INTERRUPTIBLE，就不將進(jìn)程移除就緒隊(duì)列，并將其狀態(tài)設(shè)為T(mén)ASK_RUNNING。 if (unlikely(signal_pending_state(prev->state, prev))) { prev->state = TASK_RUNNING; } else { 調(diào)用函數(shù) p->sched_class->dequeue_task將進(jìn)程移除隊(duì)列。 deactivate_task(rq, prev, DEQUEUE_SLEEP); prev->on_rq = 0; if (prev->flags & PF_WQ_WORKER) { struct task_struct *to_wakeup; 每一個(gè)工作隊(duì)列都有一個(gè)工作者線程，如果當(dāng)前進(jìn)程是一個(gè)工作者線程，就查看是否有其他處于等待中的工作者線程，如果有在本地CPU上喚醒。 to_wakeup = wq_worker_sleeping(prev, cpu); if (to_wakeup) try_to_wake_up_local(to_wakeup); } } switch_count = &prev->nvcsw; } 如果CPU將變?yōu)榭臻e狀態(tài)，即就緒隊(duì)列上沒(méi)有可運(yùn)行的進(jìn)程，就試圖從其他CPU上可運(yùn)行的進(jìn)程移動(dòng)到本地CPU的就緒隊(duì)列上。 if (unlikely(!rq->nr_running)) idle_balance(cpu, rq); 通知調(diào)度器類(lèi)當(dāng)前運(yùn)行的進(jìn)程將要被另一個(gè)進(jìn)程代替。 put_prev_task(rq, prev); 選擇下一個(gè)應(yīng)該執(zhí)行的進(jìn)程 next = pick_next_task(rq); 清除重調(diào)度標(biāo)志TIF_NEED_RESCHED，重調(diào)度標(biāo)志是由進(jìn)程調(diào)度類(lèi)設(shè)置的，表示調(diào)度請(qǐng)求，內(nèi)核會(huì)在適當(dāng)?shù)臅r(shí)機(jī)完成該標(biāo)志。 clear_tsk_need_resched(prev); rq->skip_clock_update = 0; if (likely(prev != next)) { rq->nr_switches++; rq->curr = next; ++*switch_count; 遞增進(jìn)程切換計(jì)數(shù) 完成進(jìn)程上下文切換，下面詳細(xì)分析。 context_switch(rq, prev, next); /* unlocks the rq */ 進(jìn)程已經(jīng)切換到其他進(jìn)程去運(yùn)行了，在后來(lái)的某個(gè)時(shí)候當(dāng)前進(jìn)程再次被調(diào)度時(shí)進(jìn)程從這里開(kāi)始運(yùn)行，但是它在這中間可能已經(jīng)被移動(dòng)到其他CPU上了，所以此時(shí)棧上的cpu和rq變量的只可能就不一樣了。 cpu = smp_processor_id(); rq = cpu_rq(cpu); } else raw_spin_unlock_irq(&rq->lock); post_schedule(rq); sched_preempt_enable_no_resched(); if (need_resched()) goto need_resched; } 【schedule--->__schedule--->context_switch】 static inline void context_switch(struct rq *rq, struct task_struct *prev, struct task_struct *next) { struct mm_struct *mm, *oldmm; mm = next->mm; oldmm = prev->active_mm; 如果將要運(yùn)行的進(jìn)程是一個(gè)內(nèi)核線程，則它是沒(méi)有進(jìn)程虛擬地址空間的，就將上一個(gè)進(jìn)程的虛擬地址空間報(bào)保存到 next->active_mm 中， if (!mm) { next->active_mm = oldmm; atomic_inc(&oldmm->mm_count); enter_lazy_tlb(oldmm, next); } else switch_mm(oldmm, mm, next); 更換虛擬內(nèi)存上下文 如果前一個(gè)進(jìn)程是內(nèi)核線程就將前一個(gè)進(jìn)程的prev->active_mm重置為NULL，rq->prev_mm指向上一個(gè)進(jìn)程的虛擬地址空間 if (!prev->mm) { prev->active_mm = NULL; rq->prev_mm = oldmm; } ...... 進(jìn)程寄存器和棧的切換，有特定體系架構(gòu)的匯編實(shí)現(xiàn)。switch_to之后進(jìn)程已經(jīng)運(yùn)行在了新進(jìn)程之上，當(dāng)前進(jìn)程再次被調(diào)度運(yùn)行時(shí)這中間可能已經(jīng)經(jīng)歷過(guò)很多次切換了，但是要保證prev指向上一個(gè)進(jìn)程。這上一個(gè)進(jìn)程可能并不是當(dāng)前進(jìn)程，所以要傳遞三個(gè)參數(shù)，下面代碼等效于prev=switch_to(next, prev); switch_to(prev, next, prev); barrier();
finish_task_switch(this_rq(), prev); |
|
|
