詳解Linux系統中的內核搶占機制

1、內核搶占概述

　　2.6新的可搶占式內核是指內核搶占，即當進程位於內核空間時，有一個更高優先級的任務出現時，如果當前內核允許搶占，則可以將當前任務掛起，執行優先級更高的進程。

　　在2.5.4版本之前，Linux內核是不可搶占的，高優先級的進程不能中止正在內核中運行的低優先級的進程而搶占CPU運行。進程一旦處於核心態（例如用戶進程執行系統調用），則除非進程自願放棄CPU，否則該進程將一直運行下去，直至完成或退出內核。與此相反，一個可搶占的Linux內核可以讓Linux內核如同用戶空間一樣允許被搶占。當一個高優先級的進程到達時，不管當前進程處於用戶態還是核心態，如果當前允許搶占，可搶占內核的Linux都會調度高優先級的進程運行。

2、用戶搶占

　　內核即將返回用戶空間的時候，如果need resched標志被設置，會導致schedule（）被調用，此時就會發生用戶搶占。在內核返回用戶空間的時候，它知道自己是安全的。所以，內核無論是在從中斷處理程序還是在系統調用後返回，都會檢查need resched標志。如果它被設置了，那麼，內核會選擇一個其他（更合適的）進程投入運行。

　　簡而言之，用戶搶占在以下情況時產生：

　　從系統調返回用戶空間。

　　從中斷處理程序返回用戶空間。

3、不可搶占內核的特點

　　在不支持內核搶占的內核中，內核代碼可以一直執行，到它完成為止。也就是說，調度程序沒有辦法在一個內核級的任務正在執行的時候重新調度—內核中的各任務是協作方式調度的，不具備搶占性。當然，運行於內核態 的進程可以主動放棄CPU，比如，在系統調用服務例程中，由於內核代碼由於等待資源而放棄CPU，這種情況叫做計劃性進程切換（planned process switch）。內核代碼一直要執行到完成（返回用戶空間）或明顯的阻塞為止，

　　在單CPU情況下，這樣的設定大大簡化了內核的同步和保護機制。可以分兩步對此加以分析：

　　首先，不考慮進程在內核中自願放棄CPU的情況（也即在內核中不發生進程的切換）。一個進程一旦進入內核就將一直運行下去，直到完成或退出內核。在其沒有完成或退出內核之前，不會有另外一個進程進入內核，即進程在內核中的執行是串行的，不可能有多個進程同時在內核中運行，這樣內核代碼設計時就不用考慮多個進程同時執行所帶來的並發問題。Linux的內核開發人員就不用考慮復雜的進程並發執行互斥訪問臨界資源的問題。當進程在訪問、修改內核的數據結構時就不需要加鎖來防止多個進程同時進入臨界區。這時只需再考慮一下中斷的情況，若有中斷處理例程也有可能訪問進程正在訪問的數據結構，那麼進程只要在進入臨界區前先進行關中斷操作，退出臨界區時進行開中斷操作就可以了。

　　再考慮一下進程自願放棄CPU的情況。因為對CPU的放棄是自願的、主動的，也就意味著進程在內核中的切換是預先知道的，不會出現在不知道的情況下發生進程的切換。這樣就只需在發生進程切換的地方考慮一下多個進程同時執行所可能帶來的並發問題，而不必在整個內核范圍內都要考慮進程並發執行問題。

4、為什麼需要內核搶占？

　　實現內核的可搶占對Linux具有重要意義。首先，這是將Linux應用於實時系統所必需的。實時系統對響應時間有嚴格的限定，當一個實時進程被實時設備的硬件中斷喚醒後，它應在限定的時間內被調度執行。而Linux不能滿足這一要求，因為Linux的內核是不可搶占的，不能確定系統在內核中的停留時間。事實上當內核執行長的系統調用時，實時進程要等到內核中運行的進程退出內核才能被調度，由此產生的響應延遲，在如今的硬件條件下，會長達100ms級。

　　這對於那些要求高實時響應的系統是不能接受的。而可搶占的內核不僅對Linux的實時應用至關重要，而且能解決Linux對多媒體（video， audio）等要求低延遲的應用支持不夠好的缺陷。

　　由於可搶占內核的重要性，在Linux2.5.4版本發布時，可搶占被並入內核，同SMP一樣作為內核的一項標准可選配置。

5、什麼情況不允許內核搶占

　　有幾種情況Linux內核不應該被搶占，除此之外Linux內核在任意一點都可被搶占。這幾種情況是：

　　內核正進行中斷處理。在Linux內核中進程不能搶占中斷（中斷只能被其他中斷中止、搶占，進程不能中止、搶占中斷），在中斷例程中不允許進行進程調度。進程調度函數schedule（）會對此作出判斷，如果是在中斷中調用，會打印出錯信息。

　　內核正在進行中斷上下文的Bottom Half（中斷的底半部）處理。硬件中斷返回前會執行軟中斷，此時仍然處於中斷上下文中。

內核的代碼段正持有spinlock自旋鎖、writelock/readlock讀寫鎖等鎖，處干這些鎖的保護狀態中。內核中的這些鎖是為了在SMP系統中短時間內保證不同CPU上運行的進程並發執行的正確性。當持有這些鎖時，內核不應該被搶占，否則由於搶占將導致其他CPU長期不能獲得鎖而死等。

　　內核正在執行調度程序Scheduler。搶占的原因就是為了進行新的調度，沒有理由將調度程序搶占掉再運行調度程序。

　　內核正在對每個CPU“私有”的數據結構操作（Per-CPU date structures）。在SMP中，對於per-CPU數據結構未用spinlocks保護，因為這些數據結構隱含地被保護了（不同的CPU有不一樣的per-CPU數據，其他CPU上運行的進程不會用到另一個CPU的per-CPU數據）。但是如果允許搶占，但一個進程被搶占後重新調度，有可能調度到其他的CPU上去，這時定義的Per-CPU變量就會有問題，這時應禁搶占。

　　為保證Linux內核在以上情況下不會被搶占，搶占式內核使用了一個變量preempt_ count，稱為內核搶占鎖。這一變量被設置在進程的PCB結構task_struct中。每當內核要進入以上幾種狀態時，變量preempt_ count就加1，指示內核不允許搶占。每當內核從以上幾種狀態退出時，變量preempt_ count就減1，同時進行可搶占的判斷與調度。

　　從中斷返回內核空間的時候，內核會檢查need_resched和preempt_count的值。如果need_ resched被設置，並且preempt count為0的話，這說明可能有一個更為重要的任務需要執行並且可以安全地搶占，此時，調度程序就會被調用。如果preempt-count不為0，則說明內核現在處干不可搶占狀態，不能進行重新調度。這時，就會像通常那樣直接從中斷返回當前執行進程。如果當前進程持有的所有的鎖都被釋放了，那麼preempt_ count就會重新為0。此時，釋放鎖的代碼會檢查need_ resched是否被設置。如果是的話，就會調用調度程序。

6、內核搶占時機

　　在2.6版的內核中，內核引入了搶占能力；現在，只要重新調度是安全的，那麼內核就可以在任何時間搶占正在執行的任務。

　　那麼，什麼時候重新調度才是安全的呢？只要premptcount為0，內核就可以進行搶占。通常鎖和中斷是非搶占區域的標志。由於內核是支持SMP的，所以，如果沒有持有鎖，那麼正在執行的代碼就是可重新導人的，也就是可以搶占的。

　　如果內核中的進程被阻塞了，或它顯式地調用了schedule（），內核搶占也會顯式地發生。這種形式的內核搶占從來都是受支持的（實際上是主動讓出CPU），因為根本無需額外的邏輯來保證內核可以安全地被搶占。如果代碼顯式的調用了schedule（），那麼它應該清楚自己是可以安全地被搶占的。

　　內核搶占可能發生在：

　　當從中斷處理程序正在執行，且返回內核空間之前。

　　當內核代碼再一次具有可搶占性的時候，如解鎖及使能軟中斷等。

　　如果內核中的任務顯式的調用schedule（）

　　如果內核中的任務阻塞（這同樣也會導致調用schedule（））

7、如何支持搶占內核

　　搶占式Linux內核的修改主要有兩點：一是對中斷的入口代碼和返回代碼進行修改。在中斷的入口內核搶占鎖preempt_count加1，以禁止內核搶占；在中斷的返回處，內核搶占鎖preempt_count減1，使內核有可能被搶占。

　　我們說可搶占Linux內核在內核的任一點可被搶占，主要就是因為在任意一點中斷都有可能發生，每當中斷發生，Linux可搶占內核在處理完中斷返回時都會進行內核的可搶占判斷。若內核當前所處狀態允許被搶占，內核都會重新進行調度選取高優先級的進程運行。這一點是與非可搶占的內核不一樣的。在非可搶占的Linux內核中，從硬件中斷返回時，只有當前被中斷進程是用戶態進程時才會重新調度，若當前被中斷進程是核心態進程，則不進行調度，而是恢復被中斷的進程繼續運行。

　　另一基本修改是重新定義了自旋鎖、讀、寫鎖，在鎖操作時增加了對preempt count變量的操作。在對這些鎖進行加鎖操作時preemptcount變量加1，以禁止內核搶占；在釋放鎖時preemptcount變量減1，並在內核的搶占條件滿足且需要重新調度時進行搶占調度。

另外一種可搶占內核實現方案是在內核代碼段中插入搶占點（preemption point）的方案。在這一方案中，首先要找出內核中產生長延遲的代碼段，然後在這一內核代碼段的適當位置插入搶占點，使得系統不必等到這段代碼執行完就可重新調度。這樣對於需要快速響應的事件，系統就可以盡快地將服務進程調度到CPU運行。搶占點實際上是對進程調度函數的調用，代碼如下：

復制代碼代碼如下:
if(current->need_resched)schedule();</p> <p>if(current->need_resched)schedule();
　　通常這樣的代碼段是一個循環體，插入搶占點的方案就是在這一循環體中不斷檢測need_ resched的值，在必要的時候調用schedule()令當前進程強行放棄CPU

8、何時需要重新調度

　　內核必須知道在什麼時候調用schedule()。如果僅靠用戶程序代碼顯式地調用schedule()，它們可能就會永遠地執行下去。相反，內核提供了一個need_resched標志來表明是否需要重新執行一次調度。當某個進程耗盡它的時間片時，scheduler tick()就會設置這個標志；當一個優先級高的進程進入可執行狀態的時候，try_to_wake_up也會設置這個標志。

　　set_ tsk_need_resched：設置指定進程中的need_ resched標志

　　clear tsk need_resched：清除指定進程中的need_ resched標志

　　need_resched()：檢查need_ resched標志的值;如果被設置就返回真，否則返回假

　　信號量、等到隊列、completion等機制喚醒時都是基於waitqueue的，而waitqueue的喚醒函數為default_wake_function，其調用try_to_wake_up將進程更改為可運行狀態並置待調度標志。

　　在返回用戶空間以及從中斷返回的時候，內核也會檢查need_resched標志。如果已被設置，內核會在繼續執行之前調用調度程序。

　　每個進程都包含一個need_resched標志，這是因為訪問進程描述符內的數值要比訪問一個全局變量快(因為current宏速度很快並且描述符通常都在高速緩存中)。在2.2以前的內核版本中，該標志曾經是一個全局變量。2.2到2.4版內核中它在task_struct中。而在2.6版中，它被移到thread_info結構體裡，用一個特別的標志變量中的一位來表示。可見，內核開發者總是在不斷改進。

9、避免內核搶占
進程一旦調用了schedule，如果再次被調度運行，那麼有下面幾種可能：1.狀態為TASK_RUNNING，處於運行隊列，那麼它肯定有機會再運行；2.處於睡眠隊列，那麼一旦條件滿足被喚醒，那麼它就會運行。那麼如果一個進程被搶占的話，而且它不在運行隊列，那麼怎麼再讓它運行呢？答案是它不能運行了。為了避免這種情況，就必須避免處於非TASK_RUNNING的進程被搶占的進程不被趕出運行隊列，也就是下面的代碼，schedule的代碼：

復制代碼代碼如下:
if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {</p> <p>switch_count = &prev->nvcsw;</p> <p>if (unlikely((prev->state & TASK_INTERRUPTIBLE) && unlikely(signal_pending(prev))))</p> <p>prev->state = TASK_RUNNING;</p> <p>else {</p> <p>if (prev->state == TASK_UNINTERRUPTIBLE)</p> <p>rq->nr_uninterruptible++;</p> <p>deactivate_task(prev, rq);</p> <p>}

也許有人會問，怎麼會有不是TASK_RUNNING的進程而且被搶占的，這個問題實在難以回答，可是記住，進程狀態和其所在的隊列沒有關系，設置進程狀態和搶占總是有可能有間隙的。我們看看下面的代碼:

復制代碼代碼如下:
for (;;) { \</p> <p>1： prepare_to_wait(&wq, &__wait, TASK_UNINTERRUPTIBLE); \</p> <p>2： if (condition) \</p> <p>3： break; \</p> <p>4： schedule(); \</p> <p>}

如果在1中被搶占，恰恰在設置完進程為TASK_UNINTERRUPTIBLE的時候被搶占，本來馬上就要測試條件是否滿足了，結果又被加入睡眠隊列去睡眠了，如果沒有PREEMPT_ACTIVE，那麼在schedule中就會被移出運行隊列，如果只有這一次喚醒機會，那麼就永遠喚不醒這個進程了，如果本次從schedule回來條件不滿足，那麼在下面的schedue中就會被移出運行隊列，這不是搶占的職責，如果非要怎麼做就會出錯，在dequeue_task中由array->queue已經為空了，在第二次真正出隊的時候就會由於空指針引用而出錯（這其實不會發生，因為只要從schedue回來，進程的狀態肯定是TASK_RUNNING，僅僅是一個例子）。因此必須保證在將進程從運行隊列移除的時候，它必須在運行隊列，否則移個鳥啊！實際上PREEMPT_ACTIVE的作用就是防止將處於非TASK_RUNNING狀態的進程並且沒有在任何睡眠隊列的進程移出運行隊列，總之必須保證進程在一個隊列中或者可以被喚醒，被搶占的進程是不能被喚醒的，如果它還不在運行隊列中，那麼它將永遠不能再運行了。那麼PREEMPT_ACTIVE是怎麼保證被搶占的進程不會被移除運行隊列呢？就是在preempt_schedule實現的：

復制代碼代碼如下:
asmlinkage void __sched preempt_schedule(void)</p> <p>{</p> <p>struct thread_info *ti = current_thread_info();</p> <p>if (likely(ti->preempt_count || irqs_disabled()))</p> <p>return;</p> <p>do {</p> <p>add_preempt_count(PREEMPT_ACTIVE); //設置PREEMPT_ACTIVE位，一直到下面的sub_preempt_count(PREEMPT_ACTIVE)，這期間不能再搶占這個進程，不過再搶占也沒有意義，如果非要搶占，出了下面的sub_preempt_count(PREEMPT_ACTIVE)也不遲</p> <p>schedule();</p> <p>sub_preempt_count(PREEMPT_ACTIVE); //搶占完畢後清除之</p> <p>barrier();</p> <p>} while (unlikely(test_thread_flag(TIF_NEED_RESCHED)));</p> <p>}

除了這裡之外，在早一些的內核中從中斷返回內核空間時如果要搶占，在entery.S中也會加上這個這個PREEMPT_ACTIVE。現在還有一個問題，就是為何wait_event要用那種實現方式呢？為何需要一個循環呢？我的回答就是：這種情況下進程之所以能被喚醒就是因為它加入了一個睡眠隊列，如果如你所說在schedule之後直接判斷condition的話是不安全的，因為喚醒不一定是因為條件滿足了，萬一兩個進程同時被喚醒那很可能有一個進程條件不能滿足，如果正好此時進程被搶占，那麼這個進程就沒有機會加入睡眠隊列了，也就沒有機會被喚醒了，雖然PREEMPT_ACTIVE保證了這個進程不出運行隊列，但是卻失去了程序的本意，程序的本意是通過喚醒運行隊列來使進程運行，而此時卻成了完全依據優先級了，即使條件滿足因為這個進程不在睡眠隊列也不會被喚醒，系統就亂掉了。

其實很簡單，必須在將進程加入到睡眠隊列以後再判斷條件，因為這樣可以不漏掉喚醒通知，如果反過來的話，就是先判斷再加入睡眠隊列，如果在加入之前其它進程喚醒了這個睡眠隊列，那麼這個進程就會漏掉這次喚醒，之所以會有一個循環是因為可能不止一個進程被喚醒，那麼就會出現競爭，這個循環就是為了競爭而設置的，這個循環保證了每個出了這個循環的進程都能安全帶著結果為真的條件。

另外，說到TASK_RUNNING這個狀態，又有人問了，為何在缺頁中要把進程狀態設置為TASK_RUNNING，難道缺頁前不是TASK_RUNNING嗎？大部分情況下應該是，可是linux內核不敢保證，之所以在handle_mm_fault中將進程狀態設置為TASK_RUNNING是為了保證在缺頁處理中如果睡眠，那麼進程可以被喚醒，舉個例子，在select中，當進程被設置為非TASK_RUNNING之後還會copy_from_user，而這卻可能引起缺頁。如果不把進程狀態設置為TASK_RUNNING，那麼萬一在page fault中schedule了，那麼這個進程就會被趕出運行隊列，就再也回不來了，為了預防之，措施是：在任何調用schedule的地方分辨狀態，然後設置進程狀態，比如前面說的用PREEMPT_ACTIVE來預防，另外就是像handle_mm_fault中做到的一樣，盡量使進程在TASK_RUNNABE狀態下進入schedule。不過我想是不是現在這個應該去掉了，即使在缺頁中不把進程設置為運行態，如果非要調度，也在之前設為運行台了。

ACTIVE_PREEMPT的作用：防止已經處於非運行態的進程還沒有加入睡眠隊列的時候就被搶占然後剔除出運行隊列。這樣就永遠也回不來了，雖然這種情況很少見，一般都是先將進程放到睡眠隊列再設置狀態。