進程的調度與切換直接影響著進程子系統的執行效率.Linux摒棄了i386 硬件提供的進程切換方法.手動保存進程上下文.在調度策略上,近幾個版本對其都有很大的改動.特別是在2.6.23版本與以前發布的2.6.0更是相差甚遠.在調度方面.我們以2.6.9在代碼作為基准作為分析.
一:進程切換
進程的切換過程是在context_switch()中實現的.從它的代碼說起:
static inline void context_switch(struct rq *rq, struct task_struct *prev, struct task_struct *next) { struct mm_struct *mm, *oldmm; prepare_task_switch(rq, prev, next); mm = next->mm; oldmm = prev->active_mm; /* * For paravirt, this is coupled with an exit in switch_to to * combine the page table reload and the switch backend into * one hypercall. */ arch_enter_lazy_cpu_mode(); //task->mm 為空.則是一個內核線程 if (unlikely(!mm)) { //內核線程共享上一個運行進程的mm next->active_mm = oldmm; //增加引用計數 atomic_inc(&oldmm->mm_count); enter_lazy_tlb(oldmm, next); } else //如果是用戶進程,則切換運行空間 switch_mm(oldmm, mm, next); //如果上一個運行進程是內核線程 if (unlikely(!prev->mm)) { //賦active_mm為空. prev->active_mm = NULL; //更新運行隊列的prev_mm成員 rq->prev_mm = oldmm; } /* * Since the runqueue lock will be released by the next * task (which is an invalid locking op but in the case * of the scheduler it's an obvious special-case), so we * do an early lockdep release here: */ #ifndef __ARCH_WANT_UNLOCKED_CTXSW spin_release(&rq->lock.dep_map, 1, _THIS_IP_); #endif /* Here we just switch the register state and the stack. */ //切換進程的執行環境 switch_to(prev, next, prev); barrier(); /* * this_rq must be evaluated again because prev may have moved * CPUs since it called schedule(), thus the 'rq' on its stack * frame will be invalid. */ //進程切換之後的處理工作 finish_task_switch(this_rq(), prev); }
實際上,進程切換包括進程的執行環境切換和運行空間的切換。運行空間的切換是由switch_mm()完成的。代碼如下:
//切換進程的執行空間 static inline void switch_mm(struct mm_struct *prev, struct mm_struct *next, struct task_struct *tsk) { //得到當前進程運行的cpu int cpu = smp_processor_id(); //如果要要切換的prev!=next 執行切換過程 if (likely(prev != next)) { /* stop flush ipis for the previous mm */ //清除prev的cpu_vm_mask標志.表示prev已經棄用了當前CPU cpu_clear(cpu, prev->cpu_vm_mask); #ifdef CONFIG_SMP //在SMP系統中.更新cpu_tlbstate per_cpu(cpu_tlbstate, cpu).state = TLBSTATE_OK; per_cpu(cpu_tlbstate, cpu).active_mm = next; #endif //設置cpu_vm_mask.表示next占用了當前CPU cpu_set(cpu, next->cpu_vm_mask); /* Re-load page tables */ //加載CR3 load_cr3(next->pgd); /* * load the LDT, if the LDT is different: */ //如果LDT不相同,還要加載LDT if (unlikely(prev->context.ldt != next->context.ldt)) load_LDT_nolock(&next->context); } #ifdef CONFIG_SMP else { per_cpu(cpu_tlbstate, cpu).state = TLBSTATE_OK; //prev == next .那當前cpu中的active_mm就是prev. 也即next BUG_ON(per_cpu(cpu_tlbstate, cpu).active_mm != next); //在SMP系統中.雖然MM是一樣的,但需要加載CR3 //執行cpu_test_and_set()來判斷next是否正運行在此CPU上,這裡是判斷在切換之前next //是否運行在當前的cpu中 //假設當前cpu為1..一個進程在1上執行的時候,被調度出來.再次調度的時候 //又發生在cpu 1 if (!cpu_test_and_set(cpu, next->cpu_vm_mask)) { /* We were in lazy tlb mode and leave_mm disabled * tlb flush IPI delivery. We must reload %cr3. */ load_cr3(next->pgd); load_LDT_nolock(&next->context); } } #endif }
我們在上面的代碼分析中可以看到。它主要是切換了進程的CR3。
執行環境的切換是在switch_to()中完成的。它的代碼如下:
#define switch_to(prev,next,last) do { \ unsigned long esi,edi; \ asm volatile("pushfl\n\t" /* Save flags */ \ "pushl %%ebp\n\t" \ "movl %%esp,%0\n\t" /* save ESP */ \ "movl %5,%%esp\n\t" /* restore ESP */ \ "movl $1f,%1\n\t" /* save EIP */ \ "pushl %6\n\t" /* restore EIP */ \ "jmp __switch_to\n" \ "1:\t" \ "popl %%ebp\n\t" \ "popfl" \ :"=m" (prev->thread.esp),"=m" (prev->thread.eip), \ "=a" (last),"=S" (esi),"=D" (edi) \ :"m" (next->thread.esp),"m" (next->thread.eip), \ "2" (prev), "d" (next)); \ } while (0)
這段代碼是用AT&T嵌入式匯編寫的。如果對相關語法不熟悉,請查閱相關資料。它的運行流程如下:
它總共有9個參數。程序開始時,先把這9個參數壓棧。
後面一個冒號跟的是輸入部。它表示程序開始運時的一系列初始化。初始化如下:
Prev à eax
Next à edx
它的執行流程如下:
Flag寄存器入棧(pushfl)
Ebp入棧(pushl %%ebp.在C中。Ebp寄存器用來存放當前的運行函數的幀指針)
Esp à prev->tread.esp(movel &&esp, %0 保存當前寄存器指針到prev->tread.esp)
Next->tread.esp à esp(將next->tread.esp加載esp寄存器.這一步實際上是加載next進程的內核棧。運行到這裡。理論上prev已經被切換到next了。因為因此如果用curret獲得當前進程應該是next)
將標號為1的地址 à prev->thread.eip (movl $1f,%1.雖然理論是進程是切換完成了,但是需要保存prev的執行環境。這裡是指明prev進程的下一條運行指令。這樣如果切換進prev進程的話,就會從標號1的地址開始運行)
Next->thread.eip壓棧(pushl %6)
跳轉到__switch_to()函數(jmp __switch_to)
這裡要注意的是__switch_to函數是經過regparm(3)來修飾的。這個是GCC的一個擴展語法。即從eax.ebx.ecx寄存器取函數的參數。這樣:__switch_to()函數的參數指是從寄存器裡取的。並不是像普通函數那樣從當前堆棧中取得.在調用函數__switch_to()之前。將next->thread.eip壓棧了。這樣從函數返回之後,它的下一條運行指令就是next->thread.eip了
我們可以想象一下:
對於新創建的進程。我們設置了 p->thread.eip = (unsigned long) ret_from_fork。這樣子進程被切換進來之後,就會通過ret_from_fork返回到用戶空間了。(詳情請參照本站的相關文檔)
對於已經運行的進程。我們在這裡可以看到,在進程被切換出去的時候,prev->thread.eip會被設置成標號1的地址。即是從標號1的地址開始運行的。
標號1的操作:
恢復ebp (popl %%ebp)
恢復flags (popfl)
這樣就恢復了進程的執行環境
這段代碼有很多讓人疑惑的地方:
在進程切換的時候,只是顯示保存了flags esp和 ebp寄存。顯示的用到了eax.edx.那其它寄存器怎麼保存的呢?
實際上,過程切換只是發生在內核態中。對於內核態中的寄存器來說。它們的段寄存器都是一樣的。所以不需要保存。
另外:對於通用寄存器。Esi edi ecx怎麼保存的呢?我查閱了相關資料。沒有發現能完全解釋清楚的。現將我各人意見所列如下:
Esi.edi寄存器:有人認為在輸出部中有這兩句:"=S" (esi),"=D" (edi) 認為會將esi edi壓棧。這際上這是錯誤的。壓棧的只是esi edi變量(在嵌入代碼之前定義的).而不是esi edi寄存器。在這裡。它只是在嵌入代碼運行之後。將esi edi寄存器的內容分別放到esi edi變量中而已。在我用gcc –S 測試結果看來也確實如此。
那即然這樣。Esi edi ecx寄存器怎麼被保存。以便將來在prev運行的時候被恢復呢?
我認為:esi edi ecx沒有被保存。也不用保存。
我們來看一下切換的整個過程:
在switch_to()中執行環境的切換過程。在prev被切換回來之後。是從switch_to中標號1的地址繼續執行的。這時候已經被切換回了進程prev的內核棧。假設此時沒有保存其它的寄存器(flags ,ebp是必須要保存的哦 ^_^ ).它的後續操作是barrier()(GCC的一段嵌入代碼。聲明內存已經變動.它實際上沒有任何操作,這跟寄存器沒關系).調用函數finish_task_switch().再從context_switch()函數中返回。再從schedule()中返回。再繼續執行prev進程流。
我們知道,C函數的調用機制中。在調用之前先會執行進程環境的保存,再推入參數。最後推入下一條執令地址。然後跳轉到函數地址。從函數中返回之後。會將環境恢復。繼續執行。
這樣我們知道。在switch_to()後的finish_task_switch()的函數調用是不受寄存器影響的(因為這是個函數。在進入函數後相當是一個全新的“世界”).然後從context_switch()返回之後就會恢復schedule()中的執行環境了。到了schedule()之後,這時候的環境跟之前切換出去的環境是完全一樣的了.
當然,這樣做的前提時:在switch_to()之後的代碼對寄存器沒有依賴。也就是全為函數。假設在switch_to()之後,有對ecx .edi esi寄存器的讀取操作就會產生錯誤了。
在switch_to中會調用__switch_to()。它的代碼如下所示:
struct task_struct fastcall * __switch_to(struct task_struct *prev_p, struct task_struct *next_p) { struct thread_struct *prev = &prev_p->thread, *next = &next_p->thread; int cpu = smp_processor_id(); struct tss_struct *tss = &per_cpu(init_tss, cpu); /* never put a printk in __switch_to... printk() calls wake_up*() indirectly */ //MMX,FPU,XMM寄存器的相關操作 //我們在前面已經詳細分析過這個函數。詳細請參閱本站相關文檔 __unlazy_fpu(prev_p); /* we're going to use this soon, after a few expensive things */ if (next_p->fpu_counter > 5) prefetch(&next->i387.fxsave); /* * Reload esp0. */ //將next->thread.esp0 --> tss //從用戶態切換到內核態的時候,將此值加載esp寄存器.即為進程的內核棧頂位置 load_esp0(tss, next); /* * Save away %gs. No need to save %fs, as it was saved on the * stack on entry. No need to save %es and %ds, as those are * always kernel segments while inside the kernel. Doing this * before setting the new TLS descriptors avoids the situation * where we temporarily have non-reloadable segments in %fs * and %gs. This could be an issue if the NMI handler ever * used %fs or %gs (it does not today), or if the kernel is * running inside of a hypervisor layer. */ //為 prev保存gs savesegment(gs, prev->gs); /* * Load the per-thread Thread-Local Storage descriptor. */ //從next的tls_array 緩存中加載線程的Thread-Local Storage描述符 load_TLS(next, cpu); /* * Restore IOPL if needed. In normal use, the flags restore * in the switch assembly will handle this. But if the kernel * is running virtualized at a non-zero CPL, the popf will * not restore flags, so it must be done in a separate step. */ //如果當前特權級別是0並且prev->iopl != next->iopl則恢復IOPL設置set_iopl_mask(next->iopl)。 if (get_kernel_rpl() && unlikely(prev->iopl != next->iopl)) set_iopl_mask(next->iopl); /* * Now maybe handle debug registers and/or IO bitmaps */ // 根據thread_info的TIF標志_TIF_WORK_CTXSW和TIF_IO_BITMAP判斷是否需要處理debug寄存器和IO位圖 if (unlikely(task_thread_info(prev_p)->flags & _TIF_WORK_CTXSW_PREV || task_thread_info(next_p)->flags & _TIF_WORK_CTXSW_NEXT)) __switch_to_xtra(prev_p, next_p, tss); /* * Leave lazy mode, flushing any hypercalls made here. * This must be done before restoring TLS segments so * the GDT and LDT are properly updated, and must be * done before math_state_restore, so the TS bit is up * to date. */ //arch_leave_lazy_cpu_mode()設置CPU的lazy模式 arch_leave_lazy_cpu_mode(); /* If the task has used fpu the last 5 timeslices, just do a full * restore of the math state immediately to avoid the trap; the * chances of needing FPU soon are obviously high now */ // 如果next_p->fpu_counter > 5則恢復next_p的FPU寄存器內容 if (next_p->fpu_counter > 5) math_state_restore(); /* * Restore %gs if needed (which is common) */ //如果需要,恢復gs寄存器 if (prev->gs | next->gs) loadsegment(gs, next->gs); //把當前的task寫入current_task(一個per-cpu變量) x86_write_percpu(current_task, next_p); return prev_p; }
這個函數涉及到很多硬件相關的東西。需要參閱x86的架構體系方面的資料才能完全理解。
進程切換完了之後,還得要進行一些清理工作,這是由finish_task_switch()完成的。它的代碼如下:
static inline void finish_task_switch(struct rq *rq, struct task_struct *prev) __releases(rq->lock) { struct mm_struct *mm = rq->prev_mm; long prev_state; //清空運行隊列的prev_mm . rq->prev_mm = NULL; /* * A task struct has one reference for the use as "current". * If a task dies,then it sets TASK_DEAD in tsk->state and calls * schedule one last time. The schedule call will never return, and * the scheduled task must drop that reference. * The test for TASK_DEAD must occur while the runqueue locks are * still held, otherwise prev could be scheduled on another cpu, die * there before we look at prev->state, and then the reference would * be dropped twice. * Manfred Spraul <[email protected]> */ prev_state = prev->state; finish_arch_switch(prev); finish_lock_switch(rq, prev); fire_sched_in_preempt_notifiers(current); //mmdrop:減少mm的引用計數,如果引用計數為零,釋放之 if (mm) mmdrop(mm); //如果過時程已經終止 if (unlikely(prev_state == TASK_DEAD)) { /* * Remove function-return probe instances associated with this * task and put them back on the free list. */ //釋放該進程的task kprobe_flush_task(prev); put_task_struct(prev); } }
這個函數比較簡單。不需要做詳細分析了。
到這裡,進程切換已經分析完了。那進程什麼時候切換呢?切換的依據又是什麼呢?這就是我們接下來要分析的進程調度方面的內容了。
二:進程調度
進程調度在近幾個版本中都進行了重要的修改。我們以2.6.9版為例過行分析。在進行具體的代碼分析之前。我們先學習一下關於進程調度的原理。
1:進程類型:
在linux調度算法中,將進程分為兩種類型。即:I/O消耗型和CPU消耗型。例如文本處理程序與正在執行的Make的程序。文本處理程序大部份時間都在等待I/O設備的輸入,而make程序大部份時間都在CPU的處理上。因此為了提高響應速度,I/O消耗程序應該有較高的優先級,才能提高它的交互性。相反的,Make程序相比之下就不那麼重要了。只要它能處理完就行了。因此,基於這樣的原理,linux有一套交互程序的判斷機制。
在task_struct結構中新增了一個成員:sleep_avg.此值初始值為100。進程在CPU上執行時,此值減少。當進程在等待時,此值增加。最後,在調度的時候。根據sleep_avg的值重新計算優先級。
2:進程優先級
正如我們在上面所說的:交互性強的需要高優先級,交互性弱的需要低優先級。在linux系統中,有兩種優先級:普通優先級和實時優先級。我們在這裡主要分析的是普通優先級,實時優先級部份可自行了解。
3:運行時間片
進程的時間片是指進程在搶占前可以持續運行的時間。在linux中,時間片長短可根據優先級來調度。進程不一定要一次運行完所有的時間片。可以在運時的中途被切換出去。
4:進程搶占
當一個進程被設為TASK_RUNING狀態時。它會判斷它的優先級是否高於正在運行的進程。如果是,則設置調度標志位,調用schedule()執行進程的調度。當一個進程的時間片為0時,也會執行進程搶占.
重要的數據結構:
在2。6。9中,每個CPU都有一個運行隊列,這樣就避免了競爭所帶來的額外開銷。運行隊列的結構如下所示:
struct runqueue { spinlock_t lock; /* * nr_running and cpu_load should be in the same cacheline because * remote CPUs use both these fields when doing load calculation. */ //運行隊列中進程數目 unsigned long nr_running; #ifdef CONFIG_SMP unsigned long cpu_load; #endif //進程切換的總數 unsigned long long nr_switches; //當新一輪的時間片遞減開始後, //expired_timestamp變量記錄著最早發生的進程耗完時間片事件的時間 //nr_uninterruptible: 記錄本 CPU 尚處於 TASK_UNINTERRUPTIBLE 狀態的進程數,和負載信息有關 unsigned long expired_timestamp, nr_uninterruptible; //本就緒隊列最近一次發生調度事件的時間 unsigned long long timestamp_last_tick; //當前CPU上運行的進程和指定的空閒進程 task_t *curr, *idle; //上一次調度時的MM結構 struct mm_struct *prev_mm; //兩個隊列:active與expired //active記錄的是活動的隊列 //expired:記錄的是時間片運行完了的隊列 prio_array_t *active, *expired, arrays[2]; //記錄 expired 就緒進程組中的最高優先級(數值最小) // 該變量在進程進入 expired 隊列的時候保存 int best_expired_prio; //記錄本 CPU 因等待 IO 而處於休眠狀態的進程數 atomic_t nr_iowait; …… …… }
prio_array_t的定義如下:
struct prio_array { //該隊列的進程數 unsigned int nr_active; //位圖.每一位表示一個隊列,如果該隊列有可以運行的進程,置該位為1 unsigned long bitmap[BITMAP_SIZE]; //運行隊列 struct list_head queue[MAX_PRIO]; };
進程調度的實現
對調度有了一般的了解之後,我們來看下進程調度到底是怎麼樣實現的:
進程調度由schedule()完成,它的代碼如下:
asmlinkage void __sched schedule(void) { long *switch_count; task_t *prev, *next; runqueue_t *rq; prio_array_t *array; struct list_head *queue; unsigned long long now; unsigned long run_time; int cpu, idx; //WARN_ON(system_state == SYSTEM_BOOTING); /* * Test if we are atomic. Since do_exit() needs to call into * schedule() atomically, we ignore that path for now. * Otherwise, whine if we are scheduling when we should not be. */ //in_atomic:判斷是否在一個中斷上下文或者是原子上下文 if (likely(!(current->state & (TASK_DEAD | TASK_ZOMBIE)))) { if (unlikely(in_atomic())) { printk(KERN_ERR "bad: scheduling while atomic!\n"); dump_stack(); } } need_resched: //禁止搶占 preempt_disable(); prev = current; //得到當前CPU上的運行隊列 rq = this_rq(); /* * The idle thread is not allowed to schedule! * Remove this check after it has been exercised a bit. */ //如果當前進程是空閒進程而且不處於運行狀態. //BUG: if (unlikely(current == rq->idle) && current->state != TASK_RUNNING) { printk(KERN_ERR "bad: scheduling from the idle thread!\n"); dump_stack(); } release_kernel_lock(prev); schedstat_inc(rq, sched_cnt); now = sched_clock(); //timestamp: 1:切換上去的時間戳 // 2:切換下來的時間戳 // 3:被喚醒的時間恰戳 //prev是當前正在運行的進程.這個timestamp應該是表示被切換上去的時間戳 //當前運行的時間.如果超過了NS_MAX_SLEEP_AVG. 取運行時間為NS_MAX_SLEEP_AVG if (likely(now - prev->timestamp < NS_MAX_SLEEP_AVG)) run_time = now - prev->timestamp; else run_time = NS_MAX_SLEEP_AVG; /* * Tasks with interactive credits get charged less run_time * at high sleep_avg to delay them losing their interactive * status */ //HIGH_CREDIT()判斷是否是一個交互式進程 //interactive_credit 超過了閥值 //如果是交互式進程,則它參與優先級計算的運行時間會比實際運行時間小 //以此獲得較高的優先級 if (HIGH_CREDIT(prev)) run_time /= (CURRENT_BONUS(prev) ? : 1); spin_lock_irq(&rq->lock); /* * if entering off of a kernel preemption go straight * to picking the next task. */ switch_count = &prev->nivcsw; //state: -1:不可運行 0:可運行的 >0 暫停的 if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) { switch_count = &prev->nvcsw; //可中斷且有末處理的信號.激活之. if (unlikely((prev->state & TASK_INTERRUPTIBLE) && unlikely(signal_pending(prev)))) prev->state = TASK_RUNNING; else //從運行隊列中移除 deactivate_task(prev, rq); } //當前CPU cpu = smp_processor_id(); //運行隊列中沒有可供運行的進程了 if (unlikely(!rq->nr_running)) { go_idle: //如果沒有可運行的進程了.從其它CPU上"搬"進程過來 idle_balance(cpu, rq); //如果還是沒有可運行進程.則將Next賦值為空閒進程. //再跳轉到switch_tasks.將空閒進程切換進去 if (!rq->nr_running) { next = rq->idle; rq->expired_timestamp = 0; wake_sleeping_dependent(cpu, rq); /* * wake_sleeping_dependent() might have released * the runqueue, so break out if we got new * tasks meanwhile: */ if (!rq->nr_running) goto switch_tasks; } } else { if (dependent_sleeper(cpu, rq)) { schedstat_inc(rq, sched_goidle); next = rq->idle; goto switch_tasks; } /* * dependent_sleeper() releases and reacquires the runqueue * lock, hence go into the idle loop if the rq went * empty meanwhile: */ if (unlikely(!rq->nr_running)) goto go_idle; } //活動隊列 array = rq->active; //如果活動隊列中進程數為0. if (unlikely(!array->nr_active)) { /* * Switch the active and expired arrays. */ //對換expired 與active schedstat_inc(rq, sched_switch); rq->active = rq->expired; rq->expired = array; array = rq->active; rq->expired_timestamp = 0; rq->best_expired_prio = MAX_PRIO; } else schedstat_inc(rq, sched_noswitch); //在活動隊列組中取第一個不為空的隊列 idx = sched_find_first_bit(array->bitmap); queue = array->queue + idx; next = list_entry(queue->next, task_t, run_list); //next進程即是將要被切換進的進程 //rt_task():判斷是否是一個實時進程 if (!rt_task(next) && next->activated > 0) { unsigned long long delta = now - next->timestamp; //task->activated:表示進程因什麼原因進入就緒態,這一原因會影響到調度優先級的計算 //-1,進程從 TASK_UNINTERRUPTIBLE 狀態被喚醒 //0,缺省值,進程原本就處於就緒態 // 1,進程從 TASK_INTERRUPTIBLE 狀態被喚醒,且不在中斷上下文中 // 2,進程從 TASK_INTERRUPTIBLE 狀態被喚醒,且在中斷上下文中 //如果是中斷服務程序調用的 activate_task(),也就是說進程由中斷激活,則該進程最有可能是交互式的,因此,置 activated=2;否則置activated=1。 //如果進程是從 TASK_UNINTERRUPTIBLE 狀態中被喚醒的,則 activated=-1(在try_to_wake_up()函數中)。 if (next->activated == 1) delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128; array = next->array; //將進程移出隊列 dequeue_task(next, array); //重新計算優先級 recalc_task_prio(next, next->timestamp + delta); //重新插入運行隊列 enqueue_task(next, array); } next->activated = 0; switch_tasks: prefetch(next); //清除調度標志 clear_tsk_need_resched(prev); rcu_qsctr_inc(task_cpu(prev)); //更新prev->sleep_avg prev->sleep_avg -= run_time; //如果sleep_avg小於零 if ((long)prev->sleep_avg <= 0) { prev->sleep_avg = 0; if (!(HIGH_CREDIT(prev) || LOW_CREDIT(prev))) prev->interactive_credit--; } prev->timestamp = prev->last_ran = now; sched_info_switch(prev, next); //如果prev與next不相等,則執行切換過程 if (likely(prev != next)) { next->timestamp = now; rq->nr_switches++; rq->curr = next; ++*switch_count; //執行進程的切換過程 prepare_arch_switch(rq, next); prev = context_switch(rq, prev, next); barrier(); finish_task_switch(prev); } else spin_unlock_irq(&rq->lock); reacquire_kernel_lock(current); preempt_enable_no_resched(); //如果還有調度標志.那就重新執行調度過程. //這個調度標志可能是在別處被設置的 if (unlikely(test_thread_flag(TIF_NEED_RESCHED))) goto need_resched; }
在上面的代碼中涉及到了SMP的負載平衡,動態優先級的知識。
所謂SMP負載平衡是指,當一個CPU的運行進程過多,但是另一個CPU的進程過少。需要在兩者之間平衡運行的進程數。顯而易見,這樣可以提高系統的運行效率。
動態優先級中涉及到很多的公式,在這裡不加詳細分析,請自行了解。
我們接著看,如果一個進程的時間片完了,會進行怎麼的處理。這個處理過程是在時間中斷中完成的。詳細請參閱本站的相關分析。
在時間中斷處理程序中,會調用sheduler_tick()對當前進程運行的時間片做特定的處理。它的代碼如下:
void scheduler_tick(int user_ticks, int sys_ticks) { //當前CPU int cpu = smp_processor_id(); struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat; //取得當前CPU的運行隊列 runqueue_t *rq = this_rq(); task_t *p = current; //更新timestamp_last_tick為當前時間 rq->timestamp_last_tick = sched_clock(); if (rcu_pending(cpu)) rcu_check_callbacks(cpu, user_ticks); /* note: this timer irq context must be accounted for as well */ if (hardirq_count() - HARDIRQ_OFFSET) { cpustat->irq += sys_ticks; sys_ticks = 0; } else if (softirq_count()) { cpustat->softirq += sys_ticks; sys_ticks = 0; } //如果當前進程為空閒進程 if (p == rq->idle) { if (atomic_read(&rq->nr_iowait) > 0) cpustat->iowait += sys_ticks; else cpustat->idle += sys_ticks; if (wake_priority_sleeper(rq)) goto out; rebalance_tick(cpu, rq, IDLE); return; } if (TASK_NICE(p) > 0) cpustat->nice += user_ticks; else cpustat->user += user_ticks; cpustat->system += sys_ticks; /* Task might have expired already, but not scheduled off yet */ //如果當前進程不是在活動隊列中 //說明P是過期但末移除的進程 if (p->array != rq->active) { //設置調度標志位 set_tsk_need_resched(p); goto out; } spin_lock(&rq->lock); /* * The task was running during this tick - update the * time slice counter. Note: we do not update a thread's * priority until it either goes to sleep or uses up its * timeslice. This makes it possible for interactive tasks * to use up their timeslices at their highest priority levels. */ //實時進程的處理 if (rt_task(p)) { /* * RR tasks need a special form of timeslice management. * FIFO tasks have no timeslices. */ if ((p->policy == SCHED_RR) && !--p->time_slice) { p->time_slice = task_timeslice(p); p->first_time_slice = 0; set_tsk_need_resched(p); /* put it at the end of the queue: */ dequeue_task(p, rq->active); enqueue_task(p, rq->active); } goto out_unlock; } //如果進程的時間片用完 if (!--p->time_slice) { //移出活動隊列 dequeue_task(p, rq->active); //設置調度標志 set_tsk_need_resched(p); //重新計算優先級與時間片 p->prio = effective_prio(p); p->time_slice = task_timeslice(p); p->first_time_slice = 0; //如果rq->expired_timestamp 為空,則設為當前時間 //expired_timestamp:表示運行隊列中最先時間片耗完的時間 if (!rq->expired_timestamp) rq->expired_timestamp = jiffies; //在這裡要注意了: //如果是一個交互性很強的進程.如果它時間版運行完了.將它移至expired隊列的 //話,那就必須要等active隊列的進程運行完之後才能被調度.這樣會影響用戶的交互性 //判斷是否是一個交互性很強的進程.如果不是,將其加至expired隊列 //如果是,將其加至active隊列 if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) { //加入expired隊列 enqueue_task(p, rq->expired); if (p->static_prio < rq->best_expired_prio) rq->best_expired_prio = p->static_prio; } else //移至active隊列 enqueue_task(p, rq->active); } else { /* * Prevent a too long timeslice allowing a task to monopolize * the CPU. We do this by splitting up the timeslice into * smaller pieces. * * Note: this does not mean the task's timeslices expire or * get lost in any way, they just might be preempted by * another task of equal priority. (one with higher * priority would have preempted this task already.) We * requeue this task to the end of the list on this priority * level, which is in essence a round-robin of tasks with * equal priority. * * This only applies to tasks in the interactive * delta range with at least TIMESLICE_GRANULARITY to requeue. */ //當前進程的時間片沒有運行完... //如果進程的剩余時間超長. if (TASK_INTERACTIVE(p) && !((task_timeslice(p) - p->time_slice) % TIMESLICE_GRANULARITY(p)) && (p->time_slice >= TIMESLICE_GRANULARITY(p)) && (p->array == rq->active)) { //從活動隊列中移除 dequeue_task(p, rq->active); //設置調度標志 set_tsk_need_resched(p); //重新計算優先級 p->prio = effective_prio(p); //重新插入活動隊列 enqueue_task(p, rq->active); } } out_unlock: spin_unlock(&rq->lock); out: rebalance_tick(cpu, rq, NOT_IDLE); }
總結:
操作系統用的進程調度算法是衡量一個操作系統的重要標志。在2.4之前,調度部份算法變動很少。但是在2.6版中的近幾個版本中發生了很大的變化。其中重要的變化是支持內核搶占。內核搶占導致了內核的復雜性。很多代碼都必須要保持重入。