linux搶占式

1. linux內核搶占是否搶占正在執行的系統調用

任務調度只對進程（線程）有效。
任務調度只能調度「調用的write系統調用」的進程。
一旦已經進入系統調用，就必須等到系統調用執行完畢。

2. linux3.10內核是搶占還是非搶占

UNIX採用搶占式內核，Linux採用非搶占式內核
內核搶占（可搶占式內核）：即當進程位於內核空間時，有一個更高優先順序的任務出現時，如果當前內核允許搶占，則可以將當前任務掛起，執行優先順序更高的進程。

非搶占式內核：高優先順序的進程不能中止正在內核中運行的低優先順序的進程而搶佔CPU運行。進程一旦處於核心態（例如用戶進程執行系統調用），則除非進程自願放棄CPU，否則該進程將一直運行下去，直至完成或退出內核

搶占式內核的意義：首先，這是將Linux應用於實時系統所必需的。實時系統對響應時間有嚴格的限定，當一個實時進程被實時設備的硬體中斷喚醒後，它應在限定的時間內被調度執行。而Linux不能滿足這一要求，因為Linux的內核是不可搶占的，不能確定系統在內核中的停留時間。事實上當內核執行長的系統調用時，實時進程要等到內核中運行的進程退出內核才能被調度，由此產生的響應延遲，在如今的硬體條件下，會長達100ms級。這對於那些要求高實時響應的系統是不能接受的。而可搶占的內核不僅對Linux的實時應用至關重要，而且能解決Linux對多媒體（video， audio）等要求低延遲的應用支持不夠好的缺陷。

頂

3. Linux - 進程調度

進程調度演算法也稱 CPU 調度演算法，畢竟進程是由 CPU 調度的。

當 CPU 空閑時，操作系統就選擇內存中的某個「就緒狀態」的進程，並給其分配 CPU。

什麼時候會發生 CPU 調度呢？通常有以下情況：

其中發生在 1 和 4 兩種情況下的調度稱為「非搶占式調度」，2 和 3 兩種情況下發生的調度稱為「搶占式調度」。

非搶占式的意思就是，當進程正在運行時，它就會一直運行，直到該進程完成或發生某個事件而被阻塞時，才會把 CPU 讓給其他進程。

而搶占式調度，顧名思義就是進程正在運行的時候，可以被打斷，使其把 CPU 讓給其他進程。那搶占的原則一般有三種，分別是時間片原則、優先權原則、短作業優先原則。

你可能會好奇為什麼第 3 種情況也會發生 CPU 調度呢？假設有一個進程是處於等待狀態的，但是它的優先順序比較高，如果該進程等待的事件發生了，它就會轉到就緒狀態，一旦它轉到就緒狀態，如果我們的調度演算法是以優先順序來進行調度的，那麼它就會立馬搶占正在運行的進程，所以這個時候就會發生 CPU 調度。

那第 2 種狀態通常是時間片到的情況，因為時間片到了就會發生中斷，於是就會搶占正在運行的進程，從而佔用 CPU。

調度演算法影響的是等待時間（進程在就緒隊列中等待調度的時間總和），而不能影響進程真在使用 CPU 的時間和 I/O 時間。

最簡單的一個調度演算法，就是非搶占式的先來先服務（First Come First Severd, FCFS）演算法了。

顧名思義，先來後到，每次從就緒隊列選擇最先進入隊列的進程，然後一直運行，直到進程退出或被阻塞，才會繼續從隊列中選擇第一個進程接著運行。

這似乎很公平，但是當一個長作業先運行了，那麼後面的短作業等待的時間就會很長，不利於短作業。

FCFS 對長作業有利，適用於 CPU 繁忙型作業的系統，而不適用於 I/O 繁忙型作業的系統。

最短作業優先（Shortest Job First, SJF）調度演算法同樣也是顧名思義，它會優先選擇運行時間最短的進程來運行，這有助於提高系統的吞吐量。

這顯然對長作業不利，很容易造成一種極端現象。

比如，一個長作業在就緒隊列等待運行，而這個就緒隊列有非常多的短作業，那麼就會使得長作業不斷的往後推，周轉時間變長，致使長作業長期不會被運行。

前面的「先來先服務調度演算法」和「最短作業優先調度演算法」都沒有很好的權衡短作業和長作業。

那麼，高響應比優先 （Highest Response Ratio Next, HRRN）調度演算法主要是權衡了短作業和長作業。

每次進行進程調度時，先計算「響應比優先順序」，然後把「響應比優先順序」最高的進程投入運行，「響應比優先順序」的計算公式：

從上面的公式，可以發現：

最古老、最簡單、最公平且使用最廣的演算法就是時間片輪轉（Round Robin, RR）調度演算法。

每個進程被分配一個時間段，稱為時間片（Quantum），即允許該進程在該時間段中運行。

另外，時間片的長度就是一個很關鍵的點：

通常時間片設為 20ms~50ms 通常是一個比較合理的折中值。

前面的「時間片輪轉演算法」做了個假設，即讓所有的進程同等重要，也不偏袒誰，大家的運行時間都一樣。

但是，對於多用戶計算機系統就有不同的看法了，它們希望調度是有優先順序的，即希望調度程序能從就緒隊列中選擇最高優先順序的進程進行運行，這稱為最高優先順序（Highest Priority First，HPF）調度演算法。

進程的優先順序可以分為，靜態優先順序或動態優先順序：

該演算法也有兩種處理優先順序高的方法，非搶占式和搶占式：

但是依然有缺點，可能會導致低優先順序的進程永遠不會運行。

多級反饋隊列（Multilevel Feedback Queue）調度演算法是「時間片輪轉演算法」和「最高優先順序演算法」的綜合和發展。

顧名思義：

工作原理：

設置了多個隊列，賦予每個隊列不同的優先順序，每個隊列優先順序從高到低，同時優先順序越高時間片越短；

新的進程會被放入到第一級隊列的末尾，按先來先服務的原則排隊等待被調度，如果在第一級隊列規定的時間片沒運行完成，則將其轉入到第二級隊列的末尾，以此類推，直至完成；

當較高優先順序的隊列為空，才調度較低優先順序的隊列中的進程運行。如果進程運行時，有新進程進入較高優先順序的隊列，則停止當前運行的進程並將其移入到原隊列末尾，接著讓較高優先順序的進程運行；

可以發現，對於短作業可能可以在第一級隊列很快被處理完。對於長作業，如果在第一級隊列處理不完，可以移入下次隊列等待被執行，雖然等待的時間變長了，但是運行時間也會更長了，所以該演算法很好的兼顧了長短作業，同時有較好的響應時間。

整體架構如下，即調度策略是模塊化設計的，調度器根據不同的進程依次遍歷不同的調度策略，找到進程對應的調度策略，調度的結果即為選出一個可運行的進程指針，並將其加入到進程可運行隊列中。

以一棵紅黑樹管理所有需要調度的進程，
紅黑樹，左邊節點小於右邊節點的值，運行到目前為止vruntime最小的進程，同時考慮了CPU/IO和nice，總是找vruntime最小的線程調度。
vruntime = pruntime/weight × 1024;
vruntime是虛擬運行時間，pruntime是物理運行時間，weight權重由nice值決定(nice越低權重越高)，則運行時間少、nice值低的的線程vruntime小，將得到優先調度。這是一個隨運行而動態變化的過程。

4. linux是搶占性的操作系統么

他問：UCOS 和 Linux 那個是搶占式的操作系統：一直認為沒去研究過這個概念，結果混亂答到：linux應該是強占式的吧？結果，面試官回答，錯，ucos是，而linux不是。。。。Linux是按照時間片輪巡。。。
汗，這個職位本來很適合，結果黃了
今天研究了一下定義：簡單講，
Linux搶占式內核就是由Robert Love修改實現的。在他的書中有如下描述： -----------
User Preemption User preemption occurs when the kernel is about to return to user-space, need_resched is set, and therefore, the scheler is invoked. If the kernel is returning to user-space, it knows it is in a safe quiescent state. In other words, if it is safe to continue executing the current task, it is also safe to pick a new task to execute. Consequently, whenever the kernel is preparing to return to user-space either on return from an interrupt or after a system call, the value of need_resched is checked. If it is set, the scheler is invoked to select a new (more fit) process to execute. Both the return paths for return from interrupt and return from system call are architecture dependent and typically implemented in assembly in entry.S (which, aside from kernel entry code, also contains kernel exit code).

The kernel is capable of preempting a task running in the kernel so long as it does not hold a lock. That is, locks are used as markers of regions of non-preemptibility. Because the kernel is SMP-safe, if a lock is not held, the current code is reentrant and capable of being preempted. The first change in supporting kernel preemption was the addition of a preemption counter, preempt_count, to each process's thread_info. This counter begins at zero and increments once for each lock that is acquired and decrements once for each lock that is released. When the counter is zero, the kernel is preemptible. Upon return from interrupt, if returning to kernel-space, the kernel checks the values of need_resched and preempt_count. If need_resched is set and preempt_count is zero, then a more important task is runnable and it is safe to preempt. Thus, the scheler is invoked. If preempt_count is nonzero, a lock is held and it is unsafe to reschele. In that case, the interrupt returns as usual to the currently executing task. When all the locks that the current task is holding are released, preempt_count returns to zero. At that time, the unlock code checks whether need_resched is set. If so, the scheler is invoked. Enabling and disabling kernel preemption is sometimes required in kernel code and is discussed in Chapter 9. Kernel preemption can also occur explicitly, when a task in the kernel blocks or explicitly calls schele(). This form. of kernel preemption has always been supported because no additional logic is required to ensure that the kernel is in a state that is safe to preempt. It is assumed that the code that explicitly calls schele() knows it is safe to reschele. Kernel preemption can occur When an interrupt handler exits, before returning to kernel-space

5. linux內核：非同步中斷，搶占及SMP都是什麼意思

非同步中斷就是中斷的中斷源不是當前進程，其實硬體中斷都是非同步的。

搶占是指高優先順序的進程可以強占低優先順序的進程的運行資源。

SMP，是對稱多處理的意思，就是幾個CPU核心對於內存來講是地位相同的，沒有主次之分

6. linux是搶占性的操作系統么

今天研究了一下定義：簡單講，
所謂非搶占，就是如果在當前進程被中斷剝奪控制權後，無論如何都能回到原來的任務。任務有優先順序別。可用不可重入函數
反之，搶占任務就是當前低優先順序別的任務會被高優先順序別任務打斷。

至於 linux

Linux搶占式內核就是由Robert Love修改實現的。

7. linux 內核搶佔比較的是靜態優先順序還是動態

Linux是仿照Unix開發的，二者的內核架構接近。 Unix的開發早，商業化應用多，相對成熟穩定，源代碼不開放。 Linux開放，版本多，更新快。

8. linux進程處於內核態會被更高優先順序搶占嗎

內核態搶占(Kernel
Preemption)
在2.6
kernel以前，kernelcode(中斷和系統調用屬於kernel
code)會一直運行，直到code被完成或者被阻塞(系統調用可以被阻塞)。在
2.6kernel里，Linuxkernel變成可搶占式。當從中斷處理常式返回到內核態(kernel-space)時，kernel會檢查是否可以搶占和是否需要重新調度。kernel可以在任何時間點上搶佔一個任務(因為中斷可以發生在任何時間點上)，只要在這個時間點上kernel的狀態是安全的、可重新調度的。

9. linux 用戶進程 可以搶占內核進程嗎

1.2.1 調度過程中關閉內核搶占
我們在上一篇linux內核主調度器schele(文章鏈接, CSDN, Github)中在分析主調度器的時候, 我們會發現內核在進行調度之前都會通過preempt_disable關閉內核搶占, 而在完成調度工作後, 又會重新開啟內核搶占
參見主調度器函數schele
do {
preempt_disable(); /* 關閉內核搶占 */
__schele(false); /* 完成調度 */
sched_preempt_enable_no_resched(); /* 開啟內核搶占 */

} while (need_resched()); /* 如果該進程被其他進程設置了TIF_NEED_RESCHED標志，則函數重新執行進行調度 */123456123456

這個很容易理解, 我們在內核完成調度器過程中, 這時候如果發生了內核搶占, 我們的調度會被中斷, 而調度卻還沒有完成, 這樣會丟失我們調度的信息.
1.2.2 調度完成檢查need_resched看是否需要重新調度
而同樣我們可以看到, 在調度完成後, 內核會去判斷need_resched條件, 如果這個時候為真, 內核會重新進程一次調度.
這個的原因, 我們在前一篇博客中, 也已經說的很明白了,
內核在thread_info的flag中設置了一個標識來標志進程是否需要重新調度, 即重新調度need_resched標識TIF_NEED_RESCHED, 內核在即將返回用戶空間時會檢查標識TIF_NEED_RESCHED標志進程是否需要重新調度，如果設置了，就會發生調度, 這被稱為用戶搶占
2 非搶占式和可搶占式內核
為了簡化問題，我使用嵌入式實時系統uC/OS作為例子
首先要指出的是，uC/OS只有內核態，沒有用戶態，這和Linux不一樣
多任務系統中, 內核負責管理各個任務, 或者說為每個任務分配CPU時間, 並且負責任務之間的通訊.
內核提供的基本服務是任務切換. 調度（Scheler）,英文還有一詞叫dispatcher, 也是調度的意思.
這是內核的主要職責之一, 就是要決定該輪到哪個任務運行了. 多數實時內核是基於優先順序調度法的, 每個任務根據其重要程度的不同被賦予一定的優先順序. 基於優先順序的調度法指，CPU總是讓處在就緒態的優先順序最高的任務先運行. 然而, 究竟何時讓高優先順序任務掌握CPU的使用權, 有兩種不同的情況, 這要看用的是什麼類型的內核, 是不可剝奪型的還是可剝奪型內核
2.1 非搶占式內核
非搶占式內核是由任務主動放棄CPU的使用權
非搶占式調度法也稱作合作型多任務, 各個任務彼此合作共享一個CPU. 非同步事件還是由中斷服務來處理. 中斷服務可以使一個高優先順序的任務由掛起狀態變為就緒狀態.
但中斷服務以後控制權還是回到原來被中斷了的那個任務, 直到該任務主動放棄CPU的使用權時，那個高優先順序的任務才能獲得CPU的使用權。非搶占式內核如下圖所示.

非搶占式內核的優點有
中斷響應快(與搶占式內核比較)；
允許使用不可重入函數；
幾乎不需要使用信號量保護共享數據, 運行的任務佔有CPU，不必擔心被別的任務搶占。這不是絕對的，在列印機的使用上，仍需要滿足互斥條件。
非搶占式內核的缺點有
任務響應時間慢。高優先順序的任務已經進入就緒態，但還不能運行，要等到當前運行著的任務釋放CPU
非搶占式內核的任務級響應時間是不確定的，不知道什麼時候最高優先順序的任務才能拿到CPU的控制權，完全取決於應用程序什麼時候釋放CPU
2.2 搶占式內核
使用搶占式內核可以保證系統響應時間. 最高優先順序的任務一旦就緒, 總能得到CPU的使用權。當一個運行著的任務使一個比它優先順序高的任務進入了就緒態, 當前任務的CPU使用權就會被剝奪，或者說被掛起了，那個高優先順序的任務立刻得到了CPU的控制權。如果是中斷服務子程序使一個高優先順序的任務進入就緒態，中斷完成時，中斷了的任務被掛起，優先順序高的那個任務開始運行。
搶占式內核如下圖所示

搶占式內核的優點有
使用搶占式內核，最高優先順序的任務什麼時候可以執行，可以得到CPU的使用權是可知的。使用搶占式內核使得任務級響應時間得以最優化。
搶占式內核的缺點有：
不能直接使用不可重入型函數。調用不可重入函數時，要滿足互斥條件，這點可以使用互斥型信號量來實現。如果調用不可重入型函數時，低優先順序的任務CPU的使用權被高優先順序任務剝奪，不可重入型函數中的數據有可能被破壞。
3 linux用戶搶占
3.1 linux用戶搶占
當內核即將返回用戶空間時, 內核會檢查need_resched是否設置, 如果設置, 則調用schele()，此時，發生用戶搶占.
3.2 need_resched標識
內核如何檢查一個進程是否需要被調度呢?
內核在即將返回用戶空間時檢查進程是否需要重新調度，如果設置了，就會發生調度, 這被稱為用戶搶占, 因此內核在thread_info的flag中設置了一個標識來標志進程是否需要重新調度, 即重新調度need_resched標識TIF_NEED_RESCHED
並提供了一些設置可檢測的函數

函數
描述
定義

set_tsk_need_resched 設置指定進程中的need_resched標志 include/linux/sched.h, L2920
clear_tsk_need_resched 清除指定進程中的need_resched標志 include/linux/sched.h, L2926
test_tsk_need_resched 檢查指定進程need_resched標志 include/linux/sched.h, L2931
而我們內核中調度時常用的need_resched()函數檢查進程是否需要被重新調度其實就是通過test_tsk_need_resched實現的, 其定義如下所示
// http://lxr.free-electrons.com/source/include/linux/sched.h?v=4.6#L3093
static __always_inline bool need_resched(void)
{
return unlikely(tif_need_resched());
}

// http://lxr.free-electrons.com/source/include/linux/thread_info.h?v=4.6#L106
#define tif_need_resched() test_thread_flag(TIF_NEED_RESCHED)1234567812345678

3.3 用戶搶占的發生時機(什麼時候需要重新調度need_resched)
一般來說，用戶搶占發生幾下情況：
從系統調用返回用戶空間；
從中斷(異常)處理程序返回用戶空間
從這里我們可以看到, 用戶搶占是發生在用戶空間的搶占現象.
更詳細的觸發條件如下所示, 其實不外乎就是前面所說的兩種情況: 從系統調用或者中斷返回用戶空間
時鍾中斷處理常式檢查當前任務的時間片，當任務的時間片消耗完時，scheler_tick()函數就會設置need_resched標志；
信號量、等到隊列、completion等機制喚醒時都是基於waitqueue的，而waitqueue的喚醒函數為default_wake_function，其調用try_to_wake_up將被喚醒的任務更改為就緒狀態並設置need_resched標志。
設置用戶進程的nice值時，可能會使高優先順序的任務進入就緒狀態；
改變任務的優先順序時，可能會使高優先順序的任務進入就緒狀態；
新建一個任務時，可能會使高優先順序的任務進入就緒狀態；
對CPU(SMP)進行負載均衡時，當前任務可能需要放到另外一個CPU上運行
4 linux內核搶占
4.1 內核搶占的概念
對比用戶搶占, 顧名思義, 內核搶占就是指一個在內核態運行的進程, 可能在執行內核函數期間被另一個進程取代.
4.2 為什麼linux需要內核搶占
linux系統中, 進程在系統調用後返回用戶態之前, 或者是內核中某些特定的點上, 都會調用調度器. 這確保除了一些明確指定的情況之外, 內核是無法中斷的, 這不同於用戶進程.
如果內核處於相對耗時的操作中, 比如文件系統或者內存管理相關的任務, 這種行為可能會帶來問題. 這種情況下, 內核代替特定的進程執行相當長的時間, 而其他進程無法執行, 無法調度, 這就造成了系統的延遲增加, 用戶體驗到」緩慢」的響應. 比如如果多媒體應用長時間無法得到CPU, 則可能發生視頻和音頻漏失現象.
在編譯內核時如果啟用了對內核搶占的支持, 則可以解決這些問題. 如果高優先順序進程有事情需要完成, 那麼在啟用了內核搶占的情況下, 不僅用戶空間應用程序可以被中斷, 內核也可以被中斷,
linux內核搶占是在Linux2.5.4版本發布時加入的, 盡管使內核可搶占需要的改動特別少, 但是該機制不像搶佔用戶空間進程那樣容易實現. 如果內核無法一次性完成某些操作(例如, 對數據結構的操作), 那麼可能出現靜態條件而使得系統不一致.
內核搶占和用戶層進程被其他進程搶占是兩個不同的概念, 內核搶佔主要是從實時系統中引入的, 在非實時系統中的確也能提高系統的響應速度, 但也不是在所有情況下都是最優的，因為搶占也需要調度和同步開銷，在某些情況下甚至要關閉內核搶占, 比如前面我們將主調度器的時候, linux內核在完成調度的過程中是關閉了內核搶占的.
內核不能再任意點被中斷, 幸運的是, 大多數不能中斷的點已經被SMP實現標識出來了. 並且在實現內核搶占時可以重用這些信息. 如果內核可以被搶占, 那麼單處理器系統也會像是一個SMP系統
4.3 內核搶占的發生時機
要滿足什麼條件，kernel才可以搶佔一個任務的內核態呢?
沒持有鎖。鎖是用於保護臨界區的，不能被搶占。
Kernel code可重入(reentrant)。因為kernel是SMP-safe的，所以滿足可重入性。
內核搶占發生的時機，一般發生在：
當從中斷處理程序正在執行，且返回內核空間之前。當一個中斷處理常式退出，在返回到內核態時(kernel-space)。這是隱式的調用schele()函數，當前任務沒有主動放棄CPU使用權，而是被剝奪了CPU使用權。
當內核代碼再一次具有可搶占性的時候，如解鎖（spin_unlock_bh）及使能軟中斷(local_bh_enable)等, 此時當kernel code從不可搶占狀態變為可搶占狀態時(preemptible again)。也就是preempt_count從正整數變為0時。這也是隱式的調用schele()函數
如果內核中的任務顯式的調用schele(), 任務主動放棄CPU使用權
如果內核中的任務阻塞(這同樣也會導致調用schele()), 導致需要調用schele()函數。任務主動放棄CPU使用權
內核搶占，並不是在任何一個地方都可以發生，以下情況不能發生
內核正進行中斷處理。在Linux內核中進程不能搶佔中斷(中斷只能被其他中斷中止、搶占，進程不能中止、搶佔中斷)，在中斷常式中不允許進行進程調度。進程調度函數schele()會對此作出判斷，如果是在中斷中調用，會列印出錯信息。
內核正在進行中斷上下文的Bottom Half(中斷下半部，即軟中斷)處理。硬體中斷返回前會執行軟中斷，此時仍然處於中斷上下文中。如果此時正在執行其它軟中斷，則不再執行該軟中斷。
內核的代碼段正持有spinlock自旋鎖、writelock/readlock讀寫鎖等鎖，處干這些鎖的保護狀態中。內核中的這些鎖是為了在SMP系統中短時間內保證不同CPU上運行的進程並發執行的正確性。當持有這些鎖時，內核不應該被搶占。
內核正在執行調度程序Scheler。搶占的原因就是為了進行新的調度，沒有理由將調度程序搶佔掉再運行調度程序。
內核正在對每個CPU「私有」的數據結構操作(Per-CPU date structures)。在SMP中，對於per-CPU數據結構未用spinlocks保護，因為這些數據結構隱含地被保護了(不同的CPU有不一樣的per-CPU數據，其他CPU上運行的進程不會用到另一個CPU的per-CPU數據)。但是如果允許搶占，但一個進程被搶占後重新調度，有可能調度到其他的CPU上去，這時定義的Per-CPU變數就會有問題，這時應禁搶占。

10. linux里的搶占-preempt

1. 什麼是搶占？

搶占就是進城切換， 以thread_info->preempt_count標識。

thread_info->preempt_count一物多用：

bit0-7代表的是搶占的次數，最大搶占深度為256次，

bit8-15代表的是軟中斷的次數，最大也是256次，

bit16-19表示中斷的次數，注釋的大概意思是避免中斷嵌套，但是也不能防止某些驅動中斷嵌套使用中斷，所以嵌套16層也是最大次數了。

bit20~23代表的NMI中斷

2.搶占的函數：

spin_lock()/spin_unlock()

disable_preempt()/enable_preempt()--禁止或使能內核搶占，調用下面的inc_preempt_count()/dec_preempt_count()，加了memory barrier。

inc_preempt_count()/dec_preempt_count()

get_cpu()/put_cpu()

3.調度點

a) 進程被阻塞時

b) 調整參數時，比如通過sched_setscheler() ,nice()等函數調整進程的調度策略,靜態優先順序時

c) 睡眠進程被喚醒時，比如wake_up喚醒等待隊列中的進程時,如果該進程具有更高優先順序則會設置當前

  進程TIF_NEED_RESCHED,如果允許內核態搶占,則會調度一次

d)中斷處理完時,如果中斷處理過程中設置了TIF_NEED_SCHED標志,中斷返回時,不論是要返回內核態還是用戶態,都會發生一次搶占.當然,在這也會檢查有沒有軟中斷需要處理。

e)執行了preempt_enable()函數。