一、引出
在在嵌入式操作系統(tǒng)中，很多線程都可以為實時任務(wù)，因為畢竟這些線程很少和人接觸，而是面向任務(wù)的。所有就有一個搶占的時機(jī)問題。特別是2.6內(nèi)核中引入了新的內(nèi)核態(tài)搶占任務(wù)，所以就可以說一下這個內(nèi)核態(tài)搶占的實現(xiàn)。
內(nèi)核態(tài)搶占主要發(fā)生在兩個時機(jī)，一個是主動的檢測是否需要搶占，另一個就是在異常處理完之后的異常判斷。
#define preempt_enable() \
do { \
?preempt_enable_no_resched(); \
?barrier(); \
?preempt_check_resched(); \
} while (0)
這一點和用戶態(tài)的pthread_setcanceltype中也有使用，也就是如果禁止線程的異步取消，在使能之后的第一時間判斷線程是不是已經(jīng)被取消，包括內(nèi)核態(tài)對信號的處理也是如此，例如，當(dāng)sigprocmask開啟一個信號屏蔽之后，也需要在第一時間來判斷系統(tǒng)中是否有未處理的信號，如果有則需要及時處理，這個操作是在sys_sigprocmask--->>>recalc_sigpending--->>>set_tsk_thread_flag(t, TIF_SIGPENDING)中完成。
另一個就是內(nèi)核線程無法預(yù)測的中斷或者異常處理結(jié)束之后的判斷。
linux-2.6.21\arch\i386\kernel\entry.S:? ret_from_exception（ret_from_intr）--->>>>
#ifdef CONFIG_PREEMPT
ENTRY(resume_kernel)
?DISABLE_INTERRUPTS(CLBR_ANY)
?cmpl $0,TI_preempt_count(?p)?# non-zero preempt_count ?首先判斷線程是否禁止了搶占，如果禁止搶占，則不檢測是否重新調(diào)度標(biāo)志。
?jnz restore_nocheck
need_resched:
?movl TI_flags(?p), ?x?# need_resched set ?
?testb $_TIF_NEED_RESCHED, %cl檢測是否需要重新調(diào)度。
?jz restore_all
?testl $IF_MASK,PT_EFLAGS(%esp)?# interrupts off (exception path) ?
?jz restore_all
?call preempt_schedule_irq?這里就是第二個搶占發(fā)生的時機(jī)，就是內(nèi)核線程不可預(yù)測的時候發(fā)生的。
?jmp need_resched
END(resume_kernel)
在preempt_schedule_irq中引入了一個比較常見的概念，就是這個PREEMPT_ACTIVE，
add_preempt_count(PREEMPT_ACTIVE);
/*
?* We use bit 30 of the preempt_count to?indicate that kernel
?*?preemption is occurring.? See include/asm-arm/hardirq.h.
?*/
#define PREEMPT_ACTIVE?0x40000000
這個標(biāo)志位在內(nèi)核中的線程搶占統(tǒng)計中將會用到，在schedule函數(shù)中
switch_count = &prev->nivcsw;
?if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {這里判斷的是搶占標(biāo)志是否被置位，如果沒有置位，也就是如果不是被搶占，則認(rèn)為是自愿放棄CPU，也就是Voluntary釋放CPU，否則認(rèn)為是被搶占。
??switch_count = &prev->nvcsw;
??if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
????unlikely(signal_pending(prev))))
???prev->state = TASK_RUNNING;
??else {
???if (prev->state == TASK_UNINTERRUPTIBLE)
????rq->nr_uninterruptible ;
???deactivate_task(prev, rq);
??}
?}
通過/proc/$PID/status可以看到這個切換次數(shù)記錄。
static inline void task_context_switch_counts(struct seq_file *m,
??????struct task_struct *p)
{
?seq_printf(m,?"voluntary_ctxt_switches:\t%lu\n"
???"nonvoluntary_ctxt_switches:\t%lu\n",
???p->nvcsw,
???p->nivcsw);
}
從調(diào)度的代碼中可以看到，如果線程禁止了搶占，那么線程是不能執(zhí)行調(diào)度的，這樣可以推出線程在關(guān)掉搶占之后不能睡眠，如果需要等待，應(yīng)該應(yīng)該用spinlock，在asmlinkage void __sched schedule(void)的開始有這個判斷
if (unlikely(in_atomic() && !current->exit_state)) {
??printk(KERN_ERR "BUG: scheduling while atomic: "
???"%s/0xx/%d\n",
???current->comm, preempt_count(), current->pid);
??debug_show_held_locks(current);
??if (irqs_disabled())
???print_irqtrace_events(current);
??dump_stack();
?}
也就是，如果 線程是禁止搶占之后進(jìn)行調(diào)度，后果是很嚴(yán)重的，直接內(nèi)核就dump_stack了(但是沒有panic，至少對386是如此)。這一點也容易理解，因為在自愿和非自愿的兩個搶占判斷中，都判斷了線程的preempt_count的值，如果非零就退出，所以應(yīng)該是不能走到這一步的。
二、多核中的運行隊列
這個在大型服務(wù)器中是比較有用的一個概念，就是線程在CPU之間的均勻分配或者非均勻分配問題。目的就是讓各個CPU盡量負(fù)載平衡，不要忙的忙死，閑的閑死。按照計算機(jī)的原始概念，CPU可以作為一個資源，然后等待使用這個資源的線程就需要排隊。如果要排隊，就需要有一個約定的地點讓大家在這里排隊，這樣便于管理，比如說先來先服務(wù)，然后優(yōu)先級的判斷等。
在內(nèi)核里，這個隊列就是每個CPU都定義的一個為struct rq 結(jié)構(gòu)的runqueue變量，這個是每個CPU的一個排隊區(qū)，可以認(rèn)為是CPU的一個私有資源，并且是靜態(tài)分配，每個CPU有天生擁有這么一個隊列，拿人權(quán)的角度看，這個也就是CPU的一個基本權(quán)利，并且是一個內(nèi)置權(quán)利。當(dāng)CPU存在之后，它的runqueue就存在了。注意：這是一個容器，它是用來存放它的客戶線程的，所以的線程在這里進(jìn)行匯集和等待；對每個CPU來說，它的這個結(jié)構(gòu)本身是不會變化的，變化的只是這個隊列中的線程，一個線程可以在這個CPU隊列里等待并運行，也可以在另一個CPU中運行，當(dāng)然不能同時運行。這個變量的定義為
static DEFINE_PER_CPU(struct rq, runqueues);
現(xiàn)在，一個CPU需要服務(wù)的所有的線程都在這個結(jié)構(gòu)里，所以也就包含了實時線程組和非實時線程組，它們在rq的體現(xiàn)為兩個成員。
?struct cfs_rq cfs;
?struct rt_rq rt;
同一個CPU上的兩個運行隊列采用不同的調(diào)度策略，實時策略也就是內(nèi)核中希望實現(xiàn)的O(1)調(diào)度器，所以它的內(nèi)容中包含了100個實時隊列結(jié)構(gòu)。這個結(jié)構(gòu)也和信號相同，首先有一個位圖，表示這個優(yōu)先級是否有可運行線程，然后有一個指針數(shù)組，指向各個優(yōu)先級的就緒線程，前者用于快速判斷最高優(yōu)先級隊列下表，后者用于真正取出該優(yōu)先級的線程。
對于cfs調(diào)度，它一般是為了保證系統(tǒng)中線程對用戶的及時響應(yīng)，也就是說這個線程和用戶交互，不能讓用戶感覺到某個任務(wù)有“卡”的感覺。保證這個流暢的方法就是快速切換，從而在某個時間段內(nèi)所有的cfs任務(wù)都可以被運行一次。也就是不會出現(xiàn)某個任務(wù)跑的很歡樂，另外某個跑的很苦逼。
這個的實現(xiàn)就是大家經(jīng)常說的內(nèi)核紅黑樹結(jié)構(gòu)，很多地方都有說明。這里注意紅黑樹是一個有序樹，有序就需要有鍵值，并且有鍵值的比較方法。在內(nèi)核中這個鍵值就是每個線程的一個調(diào)度實體的vruntime成員，在linux-2.6.37.1\kernel\sched_fair.c中我們看到的鍵值比較為put_prev_task_fair--->>>put_prev_entity--->>>__enqueue_entity--->>>entity_key
static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
?return se->vruntime?- cfs_rq->min_vruntime;
}
而這個調(diào)度實體是一個抽象的概念，它可能考慮到了任務(wù)組的調(diào)度吧。實時任務(wù)和cfs任務(wù)的調(diào)度實體結(jié)構(gòu)并不相同，并且這個兩個在task_struct結(jié)構(gòu)中兩個并不是一個union，而是實實在在兩個獨立的實體，在task_struct結(jié)構(gòu)中可以看到：
?struct sched_entity se;
?struct sched_rt_entity rt;
這個可能是為了保證線程的優(yōu)先級可以在運行時通過sys_sched_setscheduler來動態(tài)修改而設(shè)置的吧。
對于一個runqueue，它對應(yīng)一個CPU，由于一個CPU上只能同時運行一個線程，所以一個runqueue只有一個curr，因為我們可以看到一個rq有一個curr結(jié)構(gòu)
?struct task_struct *curr, *idle, *stop;
注意的是，同一時間真正使用CPU的線程只有一個，但是一個CPU上可以有多個線程都是處于就緒狀態(tài)，也就是running狀態(tài)，我們可以看到這個running在rq、rt_rq、cfs_rq中都有相應(yīng)的成員(nr_running)。這里說的running并不是他們在運行，而是可運行，他們是用來進(jìn)行CPU之間負(fù)載均衡的，和是否正在CPU上運行沒有直接關(guān)系。反過來，一個線程是否處于可運行狀態(tài)，是通過p->se.on_rq 來判斷的。
我們看一下系統(tǒng)喚醒一個線程時的操作：
wake_up_new_task--->>>activate_task--->>enqueue_task
p->se.on_rq = 1; 這里可以看到，實時任務(wù)也是用了task_struct中的struct sched_entity se;成員，所以可以認(rèn)為這是一個線程固有的成員，而struct sched_rt_entity rt;是為rt線程專門另外設(shè)置的一個附加成員，它們不是互斥或者說可替代的，而是基礎(chǔ)和附加屬性的關(guān)系。
而對于某個CPU上正在運行的線程的判斷則使用的是
static inline int task_current(struct rq *rq, struct task_struct *p)
{
?return rq->curr == p;
}
而對于nr_running的設(shè)置為
wake_up_new_task--->>>activate_task--->>inc_nr_running(rq);
static void inc_nr_running(struct rq *rq)
{
?rq->nr_running ;
}
