Linux內(nèi)核schedule函數(shù)分析

1：在進(jìn)程卻換前，scheduler做的事情
Schedule所作的事情是用某一個(gè)進(jìn)程替換當(dāng)前進(jìn)程。
（1）    關(guān)閉內(nèi)核搶占，初始化一些局部變量。
need_resched:

preempt_disable( );
prev = current;
rq = this_rq( );
當(dāng)前進(jìn)程current被保存在prev,和當(dāng)前CPU相關(guān)的runqueue的地址保存在rq中。
（2）       檢查prev沒有持有big kernel lock.
if (prev->lock_depth >= 0)
up(&kernel_sem);
Schedule沒有改變lock_depth的值，在prev喚醒自己執(zhí)行的情況下，假如lock_depth的值不是負(fù)的，prev需要重新獲取kernel_flag自旋鎖。所以大內(nèi)核鎖在進(jìn)程卻換過程中是自動(dòng)釋放的和自動(dòng)獲取的。
（3）    調(diào)用sched_clock( )，讀取TSC，并且將TSC轉(zhuǎn)換成納秒，得到的timestamp保存在now中，然后Schedule計(jì)算prev使用的時(shí)間片。
now = sched_clock( );
run_time = now - prev->timestamp;
if (run_time > 1000000000)
    run_time = 1000000000;
（4）    在察看可運(yùn)行進(jìn)程的時(shí)候，schedule必須關(guān)閉當(dāng)前CPU中斷，并且獲取自旋鎖保護(hù)runqueue.
spin_lock_irq(&rq->lock);
（5）    為了識(shí)別當(dāng)前進(jìn)程是否已終止，schedule檢查PF_DEAD標(biāo)志。
if (prev->flags & PF_DEAD)    prev->state = EXIT_DEAD;
（6）    Schedule檢查prev的狀態(tài)，假如他是不可運(yùn)行的，并且在內(nèi)核態(tài)沒有被搶占，那么從runqueue刪除他。但是，假如prev有非阻塞等待信號(hào)并且他的狀態(tài)是TASK_INTERRUPTBLE,配置其狀態(tài)為TASK_RUNNING，并且把他留在runqueue中。該動(dòng)作和分配CPU給prev不相同，只是給prev一個(gè)重新選擇執(zhí)行的機(jī)會(huì)。
if (prev->state != TASK_RUNNING &&
    !(preempt_count() & PREEMPT_ACTIVE)) {
    if (prev->state == TASK_INTERRUPTIBLE && signal_pending(prev))
        prev->state = TASK_RUNNING;
    else {
        if (prev->state == TASK_UNINTERRUPTIBLE)
            rq->nr_uninterruptible++;
        deactivate_task(prev, rq);
    }
}
deactivate_task( )是從runqueue移除進(jìn)程：
rq->nr_running--;
dequeue_task(p, p->array);
p->array = NULL;
（7）       檢查runqueue中進(jìn)程數(shù)，
A:假如有多個(gè)可運(yùn)行進(jìn)程，調(diào)用dependent_sleeper( )函數(shù)。一般情況下，該函數(shù)立即返回0，但是假如內(nèi)核支持超線程技術(shù)，該函數(shù)檢查將被運(yùn)行的進(jìn)程是否有比已運(yùn)行在同一個(gè)物理CPU上一個(gè)邏輯CPU上的兄弟進(jìn)程的優(yōu)先級低。假如是，schedule拒絕選擇低優(yōu)先級進(jìn)程，而是執(zhí)行swapper進(jìn)程。
if (rq->nr_running) {    if (dependent_sleeper(smp_processor_id( ), rq)) {        next = rq->idle;        goto switch_tasks;    }}
B:假如沒有可運(yùn)行進(jìn)程，調(diào)用idle_balance( )，從其他runqueue隊(duì)列中移動(dòng)一些進(jìn)程到當(dāng)前runqueue，idle_balance( )和load_balance( )相似。
if (!rq->nr_running) {    idle_balance(smp_processor_id( ), rq);    if (!rq->nr_running) {        next = rq->idle;        rq->expired_timestamp = 0;        wake_sleeping_dependent(smp_processor_id( ), rq);        if (!rq->nr_running)            goto switch_tasks;    }}
假如idle_balance( )移動(dòng)一些進(jìn)程到當(dāng)前runqueue失敗，schedule( )調(diào)用wake_sleeping_dependent( )重新喚醒空閑CPU的可運(yùn)行進(jìn)程。

假設(shè)schedule( )已決定runqueue中有可運(yùn)行進(jìn)程，那么他必須檢查可運(yùn)行進(jìn)程中至少有一個(gè)進(jìn)程是激活的。假如沒有，交換runqueue中active 和expired域的內(nèi)容，任何expired進(jìn)程變成激活的，空數(shù)組準(zhǔn)備接受以后expire的進(jìn)程。
if (unlikely(!array->nr_active)) {
       /*
        * Switch the active and expired arrays.
        */
       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;
    }
（8）    查找在active prio_array_t數(shù)組中的可運(yùn)行進(jìn)程。Schedule在active數(shù)組的位掩碼中查找第一個(gè)非0位。當(dāng)優(yōu)先級列表不為0的時(shí)候，相應(yīng)的位掩碼北配置，所以第一個(gè)不為0的位標(biāo)示一個(gè)有最合適進(jìn)程運(yùn)行的列表。然后列表中第一個(gè)進(jìn)程描述符被獲取。
idx = sched_find_first_bit(array->bitmap);
    queue = array->queue + idx;
    next = list_entry(queue->next, task_t, run_list);
    現(xiàn)在next指向?qū)⑻鎿Qprev的進(jìn)程描述符。
（9）    檢查next->activated，他標(biāo)示喚醒進(jìn)程的狀態(tài)。
（10）   假如next是個(gè)普通進(jìn)程，并且是從TASK_INTERRUPTIBLE 或TASK_STOPPED狀態(tài)喚醒。Scheduler在進(jìn)程的平均睡眠時(shí)間上加從進(jìn)程加入到runqueue開始的等待時(shí)間。

if (!rt_task(next) && next->activated > 0) {
        unsigned long long delta = now - next->timestamp;
        if (unlikely((long long)(now - next->timestamp)
            delta = 0;

        if (next->activated == 1)
            delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;

        array = next->array;
        new_prio = recalc_task_prio(next, next->timestamp + delta);

        if (unlikely(next->prio != new_prio)) {
            dequeue_task(next, array);
            next->prio = new_prio;
            enqueue_task(next, array);
        } else
            requeue_task(next, array);
    }
    next->activated = 0;
Scheduler區(qū)分被中斷或被延遲函數(shù)喚醒的進(jìn)程和被系統(tǒng)調(diào)用服務(wù)程式或內(nèi)核線程喚醒的進(jìn)程。前者，Scheduler加整個(gè)runqueue等待時(shí)間，后者只加一部分時(shí)間。
2：進(jìn)程卻換時(shí)，Scheduler做的事情：
現(xiàn)在，Scheduler已確定要運(yùn)行的進(jìn)程。
（1）       訪問next的thread_info,他的地址保存在next進(jìn)程描述符的頂部。
switch_tasks:
       if (next == rq->idle)
              schedstat_inc(rq, sched_goidle);
       prefetch(next)
（2）       在替換prev前，執(zhí)行一些管理工作
clear_tsk_need_resched(prev);
    rcu_qsctr_inc(task_cpu(prev));
clear_tsk_need_resched清除prev的TIF_NEED_RESCHED，該動(dòng)作只發(fā)生在Scheduler是被間接調(diào)用的情況。
（3）       減少prev的平均睡眠時(shí)間到進(jìn)程使用的cpu時(shí)間片。
    prev->sleep_avg -= run_time;
    if ((long)prev->sleep_avg
        prev->sleep_avg = 0;
    prev->timestamp = prev->last_ran = now;
（4）       檢查是否prev和next是同一個(gè)進(jìn)程，假如為真，放棄進(jìn)程卻換，否則，執(zhí)行（5）
   if (prev == next) {
    spin_unlock_irq(&rq->lock);
    goto finish_schedule;
}

（5）       真正的進(jìn)程卻換
        next->timestamp = now;
        rq->nr_switches++;
        rq->curr = next;
        ++*switch_count;

        prepare_task_switch(rq, next);
        prev = context_switch(rq, prev, next);
context_switch建立了next的地址空間，進(jìn)程描述符的active_mm指向進(jìn)程使用的地址空間描述符，而mm指向進(jìn)程擁有的地址空間描述符，通常二者是相同的。但是內(nèi)核線程沒有自己的地址空間，mm一直為NULL。假如next為內(nèi)核線程，context_switch確保next使用prev的地址空間。假如next是個(gè)正常的進(jìn)程，context_switch使用next的替換prev的地址空間。
    struct mm_struct *mm = next->mm;
    struct mm_struct *oldmm = prev->active_mm;

    if (unlikely(!mm)) {
       next->active_mm = oldmm;
       atomic_inc(&oldmm->mm_count);
       enter_lazy_tlb(oldmm, next);
    } else
       switch_mm(oldmm, mm, next);
假如prev是個(gè)內(nèi)核線程或正在退出的進(jìn)程，context_switch在runqueue的prev_mm中保存prev使用的內(nèi)存空間。
    if (unlikely(!prev->mm)) {
       prev->active_mm = NULL;
       WARN_ON(rq->prev_mm);
       rq->prev_mm = oldmm;
    }
調(diào)用switch_to(prev, next, prev)進(jìn)行prev和next的轉(zhuǎn)換。（參見“進(jìn)程間的轉(zhuǎn)換“）。 3：進(jìn)程轉(zhuǎn)換后的工作（1）       finish_task_switch()：         struct mm_struct *mm = rq->prev_mm;         unsigned long prev_task_flags;          rq->prev_mm = NULL;          prev_task_flags = prev->flags;         finish_arch_switch(prev);         finish_lock_switch(rq, prev);         if (mm)                 mmdrop(mm);         if (unlikely(prev_task_flags & PF_DEAD))                 put_task_struct(prev)假如prev是內(nèi)核線程，runqueue的prev_mm保存prev的內(nèi)存空間描述符。Mmdrop減少內(nèi)存空間的使用數(shù)，假如該數(shù)為0，該函數(shù)釋放內(nèi)存空間描述符，連同和之相關(guān)的頁表和虛擬內(nèi)存空間。finish_task_switch()還釋放runqueue的自選鎖，開中斷。（2）       最后         prev = current;         if (unlikely(reacquire_kernel_lock(prev)                  goto need_resched_nonpreemptible;         preempt_enable_no_resched();         if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))                 goto need_resched;
schedule獲取大內(nèi)核塊，重新使內(nèi)核能夠搶占，并且檢查是否其他進(jìn)程配置了當(dāng)前進(jìn)程的TIF_NEED_RESCHED，假如真，重新執(zhí)行schedule，否則該程式結(jié)束