程序排程的時機
程序排程時機就是核心調用schedule函數的時機。當核心即将傳回使用者空間時，核心會檢查need_resched标志是否設定。如果設定，則調用schedule函數，此時是從中斷（或者異常、系統調用）處理程式傳回使用者空間的時間點作為一個固定的排程時間點。
除此之外，核心線程和中斷處理程式中任何需要暫時中止執行目前執行路徑的位置都可以直接調用schedule（），比如等待某個資源就緒。程序排程時機簡單總結如下：
- 使用者程序通過特定的系統調用主動讓出CPU。
- 中斷處理程式在核心傳回使用者态時進行排程。
- 核心線程主動調用schedule函數讓出CPU。
- 中斷處理程式主動調用schedule函數讓出CPU。
schedule（）在Linux核心4.15.13中實作如下：
/*
* __schedule() is the main scheduler function.
*
* The main means of driving the scheduler and thus entering this function are:
*
* 1. Explicit blocking: mutex, semaphore, waitqueue, etc.
*
* 2. TIF_NEED_RESCHED flag is checked on interrupt and userspace return
* paths. For example, see arch/x86/entry_64.S.
*
* To drive preemption between tasks, the scheduler sets the flag in timer
* interrupt handler scheduler_tick().
*
* 3. Wakeups don't really cause entry into schedule(). They add a
* task to the run-queue and that's it.
*
* Now, if the new task added to the run-queue preempts the current
* task, then the wakeup sets TIF_NEED_RESCHED and schedule() gets
* called on the nearest possible occasion:
*
* - If the kernel is preemptible (CONFIG_PREEMPT=y):
*
* - in syscall or exception context, at the next outmost
* preempt_enable(). (this might be as soon as the wake_up()'s
* spin_unlock()!)
*
* - in IRQ context, return from interrupt-handler to
* preemptible context
*
* - If the kernel is not preemptible (CONFIG_PREEMPT is not set)
* then at the next:
*
* - cond_resched() call
* - explicit schedule() call
* - return from syscall or exception to user-space
* - return from interrupt-handler to user-space
*
* WARNING: must be called with preemption disabled!
* 警告：隻能在CPU不可搶占的時候被調用
*/
static void __sched notrace __schedule(bool preempt)
{
struct task_struct *prev, *next;
unsigned long *switch_count;
struct rq_flags rf;
struct rq *rq;
int cpu;
cpu = smp_processor_id();
rq = cpu_rq(cpu);
prev = rq->curr;
schedule_debug(prev);
if (sched_feat(HRTICK))
hrtick_clear(rq);
local_irq_disable();
rcu_note_context_switch(preempt);
/*
* Make sure that signal_pending_state()->signal_pending() below
* can't be reordered with __set_current_state(TASK_INTERRUPTIBLE)
* done by the caller to avoid the race with signal_wake_up().
*/
rq_lock(rq, &rf);
smp_mb__after_spinlock();
/* Promote REQ to ACT */
rq->clock_update_flags <<= 1;
update_rq_clock(rq);
switch_count = &prev->nivcsw;
if (!preempt && prev->state) {
if (unlikely(signal_pending_state(prev->state, prev))) {
prev->state = TASK_RUNNING;
} else {
deactivate_task(rq, prev, DEQUEUE_SLEEP | DEQUEUE_NOCLOCK);
prev->on_rq = 0;
if (prev->in_iowait) {
atomic_inc(&rq->nr_iowait);
delayacct_blkio_start();
}
/*
* If a worker went to sleep, notify and ask workqueue
* whether it wants to wake up a task to maintain
* concurrency.
*/
if (prev->flags & PF_WQ_WORKER) {
struct task_struct *to_wakeup;
to_wakeup = wq_worker_sleeping(prev);
if (to_wakeup)
try_to_wake_up_local(to_wakeup, &rf);
}
}
switch_count = &prev->nvcsw;
}
next = pick_next_task(rq, prev, &rf);
clear_tsk_need_resched(prev);
clear_preempt_need_resched();
if (likely(prev != next)) {
rq->nr_switches++;
rq->curr = next;
/*
* The membarrier system call requires each architecture
* to have a full memory barrier after updating
* rq->curr, before returning to user-space. For TSO
* (e.g. x86), the architecture must provide its own
* barrier in switch_mm(). For weakly ordered machines
* for which spin_unlock() acts as a full memory
* barrier, finish_lock_switch() in common code takes
* care of this barrier. For weakly ordered machines for
* which spin_unlock() acts as a RELEASE barrier (only
* arm64 and PowerPC), arm64 has a full barrier in
* switch_to(), and PowerPC has
* smp_mb__after_unlock_lock() before
* finish_lock_switch().
*/
++*switch_count;
trace_sched_switch(preempt, prev, next);//任務切換
/* Also unlocks the rq: */
rq = context_switch(rq, prev, next, &rf);//上下文切換
} else {
rq->clock_update_flags &= ~(RQCF_ACT_SKIP|RQCF_REQ_SKIP);
rq_unlock_irq(rq, &rf);
}
balance_callback(rq);
}
那麼在core.c中有哪些地方調用了schedule（）呢？（也就是哪裡可以發生程序排程），經過搜尋發現以下幾處：
- asmlinkage __visible void __sched schedule_user(void);這個函數當set_need_resched()被調用或者被遠端喚醒但IPI尚未到達。這是注釋中給出的資訊。
- void __sched schedule_preempt_disabled(void);在禁用搶占的時候被調用。
- static void do_sched_yield(void);将目前CPU聲明給其他線程時執行此函數。
- int __sched yield_to(struct task_struct *p, bool preempt);将目前CPU聲明給同一程序組中的其他程序是調用此函數。
- void io_schedule(void);源碼中沒有注釋，不過可以推測是在目前程序準備進行IO時讓出CPU。
其實linux中程序排程發生的時機和其他作業系統差別不大，無非是以下幾種：
- 正在執行的程序執行完畢。
- 執行中的程序主動阻塞自己進入睡眠狀态，或者調用了P原語因資源不足而被阻塞，或者調用了V原語激活了等待資源的隊列。
- 程序IO準備就緒後被阻塞。
- 分時系統中時間片用完。
- 執行系統調用傳回時發生排程。
- 就緒隊列中有程序優先級高于目前程序時。
CGDB追蹤調試schedule（）
在自己系統中對menuOS進行調試，選擇之前用過的fork系列的test.c。
分别在
schedule
，
context_switch
switch_to
pick_next_task
處設定斷點。由于switch_to是内嵌彙編代碼是以無法跟蹤調試，下面會單獨分析。
另外在按s進行調試的過程中我們發現經常進入一個叫做
update_curr
的函數，該函數如下：
上下文（運作環境）的切換
為了控制程序執行，核心必須有能力挂起正在CPU種運作的程序，并恢複挂起的某個程序。這被稱為程序切換，任務切換或者程序上下文切換。
程序上下文包含了程序執行需要的所有資訊，包括使用者位址空間（程式代碼，資料，使用者堆棧），控制資訊（程序描述符，核心堆棧），硬體上下文,相關寄存器的值。
一般來說，CPU任何時刻都處于以下3中情況之中：
- 運作于使用者空間，執行使用者程序上下文。
- 運作于内和空間，處于程序，一般是核心線程的上下文。
- 運作于核心空間，處于中斷上下文。
程序上下文和中斷上下文
上下文（congtext）簡單來說就是一個環境。
使用者空間的應用程式，通過系統調用，進入核心空間。這個時候使用者空間的程序要傳遞很多變量、參數的值給核心，核心态運作的時候也要儲存使用者程序的一些寄存 器值、變量等。所謂的“程序上下文”，就是一個程序在執行的時候，CPU的所有寄存器中的值、程序的狀态以及堆棧上的内容，當核心需要切換到另一個程序時，它需要儲存目前程序的所有狀态，即儲存目前程序的程序上下文，以便再次執行該程序時，能夠恢複切換時的狀态，繼續執行。一個程序的上下文可以分為三個部分:
- 使用者級上下文：正文、資料、使用者堆棧以及共享存儲區。
- 寄存器上下文：通用寄存器、程式寄存器(IP)、處理器狀态寄存器(EFLAGS)、棧指針(ESP)。
- 系統級上下文：程序控制塊task_struct、記憶體管理資訊(mm_struct、vm_area_struct、pgd、pte)、核心棧。
當發生程序排程時，進行程序切換就是上下文切換(context switch).作業系統必須對上面提到的全部資訊進行切換，新排程的程序才能運作。而系統調用進行的模式切換(mode switch)與程序切換比較起來，容易很多，而且節省時間，因為模式切換最主要的任務隻是切換程序寄存器上下文的切換。
硬體通過觸發信号，導緻核心調用中斷處理程式，進入核心空間。這個過程中，硬體的一些變量和參數也要傳遞給核心，核心通過這些參數進行中斷處理。所謂的“ 中斷上下文”，就是硬體通過觸發信号，導緻核心調用中斷處理程式，進入核心空間。這個過程中，硬體的一些變量和參數也要傳遞給核心，核心通過這些參數進行中斷處理。中斷上下文，其實也可以看作就是硬體傳遞過來的這些參數和核心需要儲存的一些其他環境（主要是目前被中斷的程序環境）。中斷時，核心不代表任何程序運作，它一般隻通路系統空間，而不會通路程序空間，核心在中斷上下文中執行時一般不會阻塞。
簡單來說，中斷發生以後，CPU跳到核心設定好的中斷處理代碼中去，由這部分核心代碼來進行中斷。這個處理過程中的上下文就是中斷上下文。
Linux核心工作在程序上下文或者中斷上下文。提供系統調用服務的核心代碼代表發起系統調用的應用程式運作在程序上下文；另一方面，中斷處理程式，異步運作在中斷上下文。中斷上下文和特定程序無關。
switch_to關鍵彙編代碼分析
該部分定義在
/linux-3.18.6/arch/x86/include/asm/switch_to.h
中，代碼如下：
/*
* Saving eflags is important. It switches not only IOPL between tasks,
* it also protects other tasks from NT leaking through sysenter etc.
*/
#define switch_to(prev, next, last) \
do { \
/* \
* Context-switching clobbers all registers, so we clobber \
* them explicitly, via unused output variables. \
* (EAX and EBP is not listed because EBP is saved/restored \
* explicitly for wchan access and EAX is the return value of \
* __switch_to()) \
*/ \
unsigned long ebx, ecx, edx, esi, edi; \
\
asm volatile("pushfl\n\t" /* save flags */ \
"pushl %%ebp\n\t" /* save EBP */ \
"movl %%esp,%[prev_sp]\n\t" /* save ESP */ \
"movl %[next_sp],%%esp\n\t" /* restore ESP */ \
//完成核心堆棧的切換
"movl $1f,%[prev_ip]\n\t" /* save EIP */ \
"pushl %[next_ip]\n\t" /* restore EIP */ \
__switch_canary \
//next_ip一般是$1f，新建立的程序則是ret_from_fork
"jmp __switch_to\n" /* regparm call */ \
//jmp通過寄存器傳遞參數，比較直覺；而call則通過堆棧傳遞參數
"1:\t" \
"popl %%ebp\n\t" /* restore EBP */ \
"popfl\n" /* restore flags */ \
\
/* output parameters */ \
: [prev_sp] "=m" (prev->thread.sp), \
[prev_ip] "=m" (prev->thread.ip), \
"=a" (last), \
\
/* clobbered output registers: */ \
"=b" (ebx), "=c" (ecx), "=d" (edx), \
"=S" (esi), "=D" (edi) \
\
__switch_canary_oparam \
\
/* input parameters: */ \
: [next_sp] "m" (next->thread.sp), \
[next_ip] "m" (next->thread.ip), \
\
/* regparm parameters for __switch_to(): */ \
[prev] "a" (prev), \
[next] "d" (next) \
\
__switch_canary_iparam \
\
: /* reloaded segment registers */ \
"memory"); \
} while (0)
在這段代碼中有一些值得注意的地方，比如：
- next_ip一般是$1f，對新建立的子程序是ret_from_fork。
- jmp跳轉到switch_to。這是jmp和ret的搭配。通常我們看到的是call和ret的搭配，call會自動壓棧傳回位址，ret會彈出傳回位址。jmp不會壓棧，ret會彈出目前棧頂，也就是$1f所在的位置。
經驗
需要注意的是，在比較新版本的核心中，schedule（）被調用隻能是在CPU不可搶占的時候，需要檢查的标志位也變成了TIF_NEED_RESCHED。具體在Linux系統中排程何時發生、怎樣發生是一個比較複雜的問題。（我了解還比較模糊，在3.18.6這個版本的核心中甚至沒有提到過CPU搶占和不可搶占這一說法，至少在core.c中沒有。另外在3.18.6中用的都是_schedule()函數，而在4.15.13中用的都是schedule()函數，他們的寫法有很大不同。不得不感歎于計算機行業的變化之快，這也是我們為什麼需要做中學的原因之一。）
另外在這次的核心代碼中，可以看到貼近硬體的程式設計人員的特别技能——likely和unlikely。
# define likely(x) __builtin_expect(!!(x), 1)
# define unlikely(x) __builtin_expect(!!(x), 0)
likely表示該表達式取1的可能性較大，unlikely表示該表達式取0的可能性更大。
從函數功能上講這兩個宏定義是一樣的，但是在編譯器編譯時會把分支編譯成有利于順序執行的結構。