歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux綜合 >> Linux內核

Linux內核進程調度機制詳解

Linux的進程管理由進程控制塊、進程調度、中斷處理、任務隊列、定時器、bottom half隊列、系統調用、進程通信等等部分組成。

進程調用分為實時進程調度和非實時進程調度兩種。前者調度時,可以采用基於動態優先級的輪轉法(RR),也可以采用先進現出算法(FIFO)。後者調度時,一律采用基於動態優先級的輪轉法。某個進程采用何種調度算法由改進程的進程控制塊中的某些屬性決定,沒有專門的系統用來處理關於進程調度的相關事宜。 Linux的進程調度由schedule()函數負責,任何進程,當它從系統調用返回時,都會轉入schedule(),而中斷處理函數完成它們的響應任務以後,也會進入schedule()。

1.         進程控制塊數據結構
Linux系統的進程控制塊用數據結構task_struct表示,這個數據結構占用1680個字節,具體的內容不在這裡介紹,詳細內容見《Linux內核2.4版源代碼分析大全》第二頁。
進程的狀態主要包括如下幾個:
TASK_RUNNING   正在運行或在就緒隊列run-queue中准備運行的進程,實際參與進程調度。
TASK_INTERRUPTIBLE       處於等待隊列中的進程,待資源有效時喚醒,也可由其它進程通過信號或定時中斷喚醒後進入就緒隊列run-queue。
TASK_UNINTERRUPTIBLE         處於等待隊列的進程,待資源有效時喚醒,不也可由其它進程通過信號或者定時中斷喚醒。
TASK_ZOMBIE      表示進程結束但尚未消亡的一種狀態(僵死),此時,進程已經結束運行並且已經釋放了大部分資源,但是尚未釋放進程控制塊。
TASK_STOPPED    進程暫停,通過其它進程的信號才能喚醒。

所有進程(以PCB形式)組成一個雙向列表。next_task和prev_task就是鏈表的前後向指針。鏈表的頭尾都是init_task(init進程)。不過進程還要根據其進程ID號插入到一個hash表當中,目的是加快進程搜索速度。

2.         進程調度
Linux進程調度由schedule()執行,其任務是在run-queue隊列中選出一個就緒進程。
每個進程都有一個調度策略,在它的task_struct中規定(policy屬性),或為SCHED_RR,SCHED_FIFO,或為SCHED_OTHER。前兩種為實時進程調度策略,後一種為普通進程調度策略。
用戶進程由do_fork()函數創建,它也是fork系統調用的執行者。do_fork()創建一個新的進程,繼承父進程的現有資源,初始化進程時鐘、信號、時間等數據。完成子進程的初始化後,父進程將它掛到就緒隊列,返回子進程的pid。
進程創建時的狀態為TASK_UNINTERRUPTIBLE,在do_fork()結束前被父進程喚醒後,變為TASK_RUNNING。處於TASK_RUNNING狀態的進程被移到就緒隊列中,當適當的時候由schedule()按CPU調度算法選中,獲得CPU。
如果進程采用輪轉法,當時間片到時(10ms的整數倍),由時鐘中斷觸發timer_interrupt()函數引起新一輪的調度,把當前進程掛到就緒隊列的尾部。獲得CPU而正在運行的進程若申請不到某個資源,則調用sleep_on()或interruptible_sleep_on()睡眠,並進入就緒隊列尾。狀態尾TASK_INTERRUPTIBLE的睡眠進程當它申請的資源有效時被喚醒,也可以由信號或者定時中斷喚醒,喚醒以後進程狀態變為 TASK_RUNNING,並進入就緒隊列。
首先介紹一下2.6版以前的的調度算法的主要思想,下面的schedule()函數是內核2.4.23中摘錄的:
asmlinkage void schedule(void)
{
struct schedule_data * sched_data;
struct task_struct *prev, *next, *p;
struct list_head *tmp;
int this_cpu, c;

spin_lock_prefetch(&runqueue_lock);

BUG_ON(!current->active_mm);
need_resched_back:
       /*記錄當前進程和處理此進程的CPU號*/
prev = current;
this_cpu = prev->processor;
/*判斷是否處在中斷當中,這裡不允許在中斷處理當中調用sechedule()*/
if (unlikely(in_interrupt())) {
        printk("Scheduling in interrupt\n");
        BUG();
}

release_kernel_lock(prev, this_cpu);

/*'sched_data' 是收到保護的,每個CPU只能運行一個進程。*/
sched_data = & aligned_data[this_cpu].schedule_data;

spin_lock_irq(&runqueue_lock);

/*如果當前進程的調度策略是輪轉RR,那麼需要判斷當前進程的時間片是否已經用完,如果已經用完,則重新計算時間片值,然後將該進程掛接到就緒隊列run-queue的最後*/
if (unlikely(prev->policy == SCHED_RR))
        if (!prev->counter) {
               prev->counter = NICE_TO_TICKS(prev->nice);
               move_last_runqueue(prev);
        }
/*假如前進程為TASK_INTERRUPTTIBLE狀態,則將其狀態置為TASK_RUNNING。如是其它狀態,則將該進程轉為睡眠狀態,從運行隊列中刪除。(已不具備運行的條件) */
switch (prev->state) {
        case TASK_INTERRUPTIBLE:
               if (signal_pending(prev)) {
                      prev->state = TASK_RUNNING;
                      break;
               }
        default:
               del_from_runqueue(prev);
        case TASK_RUNNING:;
}
/*當前進程不需要重新調度*/
prev->need_resched = 0;

/*下面是一般的進程調度過程*/

repeat_schedule:
next = idle_task(this_cpu);
c = -1000;
/*遍歷進程就緒隊列,如果該進程能夠進行調度(對於SMP來說就是判斷當前CPU未被占用能夠執行這個進程,對於非SMP系統則為1),則計算該進程的優先級,如果優先級大於當前進程,則next指針指向新的進程,循環直到找到優先級最大的那個進程*/
list_for_each(tmp, &runqueue_head) {
        p = list_entry(tmp, struct task_struct, run_list);
        if (can_schedule(p, this_cpu)) {
               int weight = goodness(p, this_cpu, prev->active_mm);
               if (weight > c)
                      c = weight, next = p;
        }
}

/* 判斷是否需要重新計算每個進程的時間片,判斷的依據是所有正准備進行調度的進程時間片耗盡,這時,就需要對就緒隊列中的每一個進程都重新計算時間片,然後返回前面的調度過程,重新在就緒隊列當中查找優先級最高的進程執行調度。 */
if (unlikely(!c)) {
        struct task_struct *p;

        spin_unlock_irq(&runqueue_lock);
        read_lock(&tasklist_lock);
        for_each_task(p)
               p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);
        read_unlock(&tasklist_lock);
        spin_lock_irq(&runqueue_lock);
        goto repeat_schedule;
}

/*CPU私有調度數據中記錄當前進程的指針,並且將當前進程與CPU綁定,如果待調度進程與前面一個進程屬於同一個進程,則不需要調度,直接返回。*/
sched_data->curr = next;
task_set_cpu(next, this_cpu);
spin_unlock_irq(&runqueue_lock);

if (unlikely(prev == next)) {
        /* We won't go through the normal tail, so do this by hand */
        prev->policy &= ~SCHED_YIELD;
        goto same_process;
}
/*全局統計進程上下文切換次數*/
kstat.context_swtch++;
/*如果後進程的mm為0 (未分配頁),則檢查是否被在被激活的頁裡(active_mm),否則換頁。令後進程記錄前進程激活頁的信息,將前進程的active_mm中的 mm_count值加一。將cpu_tlbstate[cpu].state改為 TLBSTATE_LAZY(采用lazy模式) 如果後進程的mm不為0(已分配頁),但尚未激活,換頁。切換mm(switch_mm)。 如果前進程的mm 為0(已失效) ,將其激活記錄置空,將mm結構引用數減一,刪除該頁。 */
prepare_to_switch();
{
        struct mm_struct *mm = next->mm;
        struct mm_struct *oldmm = prev->active_mm;
        if (!mm) {
               BUG_ON(next->active_mm);
               next->active_mm = oldmm;
               atomic_inc(&oldmm->mm_count);
               enter_lazy_tlb(oldmm, next, this_cpu);
        } else {
               BUG_ON(next->active_mm != mm);
               switch_mm(oldmm, mm, next, this_cpu);
        }

        if (!prev->mm) {
               prev->active_mm = NULL;
               mmdrop(oldmm);
        }
}

/*切換到後進程,調度過程結束*/
switch_to(prev, next, prev);
__schedule_tail(prev);

same_process:
reacquire_kernel_lock(current);
if (current->need_resched)
        goto need_resched_back;
return;
}

Copyright © Linux教程網 All Rights Reserved