linux進程調度線程調度
執行一個 ，但是只要任何修改，都造成分裂如，修改了chroot,寫memory，mmap，sigaction 等。
p1 是一個 task_struct, p2 也是一個 task_struct. linux內核的調度器只認得task_struck （不管你是進程還是線程）, 對其進行調度。
p2 的task_struck 被創建出來後，也有一份自己的資源。但是這些資源會短暫的與p1 相同。
進程是區分資源的單位，你的資源是我的資源，那從概念上將就不叫進程。
其他資源都好分配，唯一比較難的是內存資源的重新分配。
非常簡單的程序，但是可以充分說明 COW。
結果：10 -> 20 -> 10
COW 是嚴重依賴於CPU中的MMU。CPU如果沒有 MMU,fork 是不能工作的。
在沒有mmu的CPU中，不可能執行COW 的，所以只有vfork
vfork與fork相比的不同
P2沒有自己的 task_struct, 也就是說P1 的內存資源 就是 P2的內存資源。
結果 10,20,20
vfork：
vfork 執行上述流程，P2也只是指向了P1的mm，那麼將這個vfork 放大，其餘的也全部clone，共同指向P1，那麼就是線程的屬性了。
phtread_create -> Clone()
P1 P2 在內核中都是 task_struct. 都可以被調度。共享資源可調度，即線程。 這就是線程為什麼也叫做輕量級進程
不需要太糾結線程和進程的區別。
4651 ： TGID
4652, 4653 tid 內核中 task_struct 真正的pid
linux 總是白發人 送 黑發人。如果父進程在子進程推出前掛掉了。那麼子進程應該怎麼辦？
p3 -> init， p5 -> subreaper
每一個孤兒都會找最近的火葬場
可以設置進程的屬性，將其變為subreaper，會像1號進程那樣收養孤兒進程。
linux的進程睡眠依靠等待隊列，這樣的機制類似與涉及模式中的訂閱與發布。
睡眠，分兩種
每一個進程都是創建出來的，那麼第一個進程是誰創建的呢？
init 進程是被linux的 0 進程 創建出來的。開機創建。
父進程就是 0 號進程，但在pstree，是看不到0進程的。因為0進程創建子進程後，就退化成了idle進程。
idle進程是 linux內核里，特殊調度類。 所有進程都睡眠停止 ，則調度idle進程，進入到 wait for interrupte 等中斷。此時 cpu及其省電，除非來一個中斷，才能再次被喚醒。
喚醒後的任何進程，從調度的角度上說，都比idle進程地位高。idle是調度級別最最低的進程。
0 進程 一跑，則進入等中斷。一旦其他進程被喚醒，就輪不到 0進程了。
所有進程都睡了，0就上來，則cpu需要進入省電模式
Ⅱ linux進程、線程及調度演算法（三）
調度策略值得是大家都在ready時，並且CPU已經被調度時，決定誰來運行，誰來被調度。
兩者之間有一定矛盾。
響應的優化，意味著高優先順序會搶占優先順序，會花時間在上下文切換，會影響吞吐。
上下文切換的時間是很短的，幾微妙就能搞定。上下文切換本身對吞吐並多大影響， 重要的是，切換後引起的cpu 的 cache miss.
每次切換APP, 數據都要重新load一次。
Linux 會盡可能的在響應與吞吐之間尋找平衡。比如在編譯linux的時候，會讓你選擇 kernal features -> Preemption model.
搶占模型會影響linux的調度演算法。
所以 ARM 的架構都是big+LITTLE， 一個很猛CPU+ 多個 性能較差的 CPU, 那麼可以把I/O型任務的調度 放在 LITTLE CPU上。需要計算的放在big上。
早期2.6 內核將優先順序劃分了 0-139 bit的優先順序。數值越低，優先順序越高。0-99優先順序 都是 RT（即時響應）的 ，100-139都是非RT的，即normal。
調度的時候 看哪個bitmap 中的 優先順序上有任務ready。可能多個任務哦。
在普通優先順序線程調度中，高優先順序並不代表對低優先順序的絕對優勢。會在不同優先順序進行輪轉。
100 就是比101高，101也會比102高，但100 不會堵著101。
眾屌絲進程在輪轉時，優先順序高的：
初始設置nice值為0，linux 會探測 你是喜歡睡眠，還是幹活。越喜歡睡，linux 越獎勵你，優先順序上升（nice值減少）。越喜歡幹活，優先順序下降（nice值增加）。所以一個進程在linux中，干著干著 優先順序越低，睡著睡著 優先順序越高。
後期linux補丁中
紅黑樹，數據結構， 左邊節點小於右邊節點
同時兼顧了 CPU/IO 和 nice。
數值代表著 進程運行到目前為止的virtual runtime 時間。
（pyhsical runtime） / weight * 1024(系數)。
優先調度 節點值（vruntime）最小的線程。權重weight 其實有nice 來控制。
一個線程一旦被調度到，則物理運行時間增加，vruntime增加，往左邊走。
weight的增加，也導致vruntime減小，往右邊走。
總之 CFS讓線程 從左滾到右，從右滾到左。即照顧了I/O(喜歡睡，分子小) 也 照顧了 nice值低（分母高）.所以 由喜歡睡，nice值又低的線程，最容易被調度到。
自動調整，無需向nice一樣做出獎勵懲罰動作，個人理解權重其實相當於nice
但是 此時 來一個 0-99的線程，進行RT調度，都可以瞬間秒殺你！因為人家不是普通的，是RT的!
一個多線程的進程中，每個線程的調度的策略 如 fifo rr normal, 都可以不同。每一個的優先順序都可以不一樣。
實驗舉例, 創建2個線程，同時開2個：
運行2次，創建兩個進程
sudo renice -n -5(nice -5級別) -g(global)， 會明顯看到 一個進程的CPU佔用率是另一個的 3倍。
為什麼cpu都已經達到200%，為什麼系統不覺得卡呢？因為，我們的線程在未設置優先順序時，是normal調度模式，且是 CPU消耗型 調度級別其實不高。
利用chrt工具，可以將進程 調整為 50 從normal的調度策略 升為RT （fifo）級別的調度策略，會出現：
chrt , nice renice 的調度策略 都是以線程為單位的，以上 設置的將進程下的所有線程進行設置nice值
線程是調度單位，進程不是，進程是資源封裝單位！
兩個同樣死循環的normal優先順序線程，其中一個nice值降低，該線程的CPU 利用率就會比另一個CPU的利用率高。
Ⅲ linux調度是基於進程還是線程
在LINUX系統之中，被調度的應該是進程。因為只有進程才擁有一個獨立的上下文環境，是分配系統資源的最小單位……而線程在SMP體系中加速了執行的效率……
在LINUX之中，線程也可稱作輕量級進程，它能享有自己的堆棧，線程ID等獨立資源，但大多還是要依賴其創建進程，比如地址空間，信號，文件句柄……
Ⅳ Linux 進程管理之進程調度與切換
我們知道，進程運行需要各種各樣的系統資源，如內存、文件、列印機和最
寶貴的 CPU 等，所以說，調度的實質就是資源的分配。系統通過不同的調度演算法（Scheling Algorithm）來實現這種資源的分配。通常來說，選擇什麼樣的調度演算法取決於資源分配的策略（Scheling Policy）。
有關調度相關的結構保存在 task_struct 中，如下：
active_mm 是為內核線程而引入的，因為內核線程沒有自己的地址空間，為了讓內核線程與普通進程具有統一的上下文切換方式，當內核線程進行上下文切換時，讓切換進來的線程的 active_mm 指向剛被調度出去的進程的 active_mm（如果進程的mm 域不為空，則其 active_mm 域與 mm 域相同）。
在 linux 2.6 中 sched_class 表示該進程所屬的調度器類有3種：
進程的調度策略有5種，用戶可以調用調度器里不同的調度策略：
在每個 CPU 中都有一個自身的運行隊列 rq，每個活動進程只出現在一個運行隊列中，在多個 CPU 上同時運行一個進程是不可能的。
運行隊列是使用如下結構實現的：
tast 作為調度實體加入到 CPU 中的調度隊列中。
系統中所有的運行隊列都在 runqueues 數組中，該數組的每個元素分別對應於系統中的一個 CPU。在單處理器系統中，由於只需要一個就緒隊列，因此數組只有一個元素。
內核也定義了一下便利的宏，其含義很明顯。
Linux、c/c++伺服器開發篇-------我們來聊聊進程的那些事
Linux內核 進程間通信組件的實現
學習地址：C/C++Linux伺服器開發/後台架構師【零聲教育】-學習視頻教程-騰訊課堂
需要C/C++ Linux伺服器架構師學習資料加qun812855908獲取（資料包括 C/C++，Linux，golang技術，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協程，DPDK，ffmpeg 等），免費分享
在分析調度流程之前，我們先來看在什麼情況下要執行調度程序，我們把這種情況叫做調度時機。
Linux 調度時機主要有。
時機1，進程要調用 sleep() 或 exit() 等函數進行狀態轉換，這些函數會主動調用調度程序進行進程調度。
時機2，由於進程的時間片是由時鍾中斷來更新的，因此，這種情況和時機4 是一樣的。
時機3，當設備驅動程序執行長而重復的任務時，直接調用調度程序。在每次反復循環中，驅動程序都檢查 need_resched 的值，如果必要，則調用調度程序 schele() 主動放棄 CPU。
時機4 ， 如前所述， 不管是從中斷、異常還是系統調用返回， 最終都調用 ret_from_sys_call()，由這個函數進行調度標志的檢測，如果必要，則調用調用調度程序。那麼，為什麼從系統調用返回時要調用調度程序呢？這當然是從效率考慮。從系統調用返回意味著要離開內核態而返回到用戶態，而狀態的轉換要花費一定的時間，因此，在返回到用戶態前，系統把在內核態該處理的事全部做完。
Linux 的調度程序是一個叫 Schele() 的函數，這個函數來決定是否要進行進程的切換，如果要切換的話，切換到哪個進程等。
從代碼分析來看，Schele 主要完成了2個功能：
進程上下文切換包括進程的地址空間的切換和執行環境的切換。
對於 switch_mm 處理，關鍵的一步就是它將新進程頁面目錄的起始物理地址裝入到寄存器 CR3 中。CR3 寄存器總是指向當前進程的頁面目錄。
switch_to 把寄存器中的值比如esp等存放到進程thread結構中，保存現場一邊後續恢復，同時調用 __switch_to 完成了堆棧的切換。
在進程的 task_struct 結構中有個重要的成分 thread，它本身是一個數據結構 thread_struct, 裡面記錄著進程在切換時的（系統空間）堆棧指針，取指令地址（也就是「返回地址」）等關鍵性的信息。
關於__switch_to 的工作就是處理 TSS （任務狀態段）。
TSS 全稱task state segment，是指在操作系統進程管理的過程中，任務（進程）切換時的任務現場信息。
linux 為每一個 CPU 提供一個 TSS 段，並且在 TR 寄存器中保存該段。
linux 中之所以為每一個 CPU 提供一個 TSS 段，而不是為每個進程提供一個TSS 段，主要原因是 TR 寄存器永遠指向它，在任務切換的適合不必切換 TR 寄存器，從而減小開銷。
在從用戶態切換到內核態時，可以通過獲取 TSS 段中的 esp0 來獲取當前進程的內核棧 棧頂指針，從而可以保存用戶態的 cs,esp,eip 等上下文。
TSS 在任務切換過程中起著重要作用，通過它實現任務的掛起和恢復。所謂任務切換是指，掛起當前正在執行的任務，恢復或啟動另一任務的執行。
在任務切換過程中，首先，處理器中各寄存器的當前值被自動保存到 TR（任務寄存器）所指定的任務的 TSS 中；然後，下一任務的 TSS 被裝入 TR；最後，從 TR 所指定的 TSS 中取出各寄存器的值送到處理器的各寄存器中。由此可見，通過在 TSS 中保存任務現場各寄存器狀態的完整映象，實現任務的切換。
因此，__switch_to 核心內容就是將 TSS 中的內核空間（0級）堆棧指針換成 next->esp0。這是因為 CPU 在穿越中斷門或者陷阱門時要根據新的運行級別從TSS中取得進程在系統空間的堆棧指針。
thread_struct.esp0 指向進程的系統空間堆棧的頂端。當一個進程被調度運行時，內核會將這個變數寫入 TSS 的 esp0 欄位，表示這個進程進入0級運行時其堆棧的位置。換句話說，進程的 thread_struct 結構中的 esp0 保存著其系統空間堆棧指針。當進程穿過中斷門、陷阱門或者調用門進入系統空間時，處理器會從這里恢復期系統空間棧。
由於棧中變數的訪問依賴的是段、頁、和 esp、ebp 等這些寄存器，所以當段、頁、寄存器切換完以後，棧中的變數就可以被訪問了。
因此 switch_to 完成了進程堆棧的切換，由於被切進的進程各個寄存器的信息已完成切換，因此 next 進程得以執行指令運行。
由於 A 進程在調用 switch_to 完成了與 B 進程堆棧的切換，也即是寄存器中的值都是 B 的，所以 A 進程在 switch_to 執行完後，A停止運行，B開始運行，當過一段時間又把 A 進程切進去後，A 開始從switch_to 後面的代碼開始執行。
schele 的調用流程如下：
Ⅳ Linux進程的調度
上回書說到 Linux進程的由來 和 Linux進程的創建 ，其實在同一時刻只能支持有限個進程或線程同時運行(這取決於CPU核數量，基本上一個進程對應一個CPU)，在一個運行的操作系統上可能運行著很多進程，如果運行的進程占據CPU的時間很長，就有可能導致其他進程餓死。為了解決這種問題，操作系統引入了 進程調度器 來進行進程的切換，輪流讓各個進程使用CPU資源。
1）rq： 進程的運行隊列( runqueue)， 每個CPU對應一個 ，包含自旋鎖(spinlock)、進程數量、用於公平調度的CFS信息結構、當前運行的進程描述符等。實際的進程隊列用紅黑樹來維護(通過CFS信息結構來訪問)。
2）cfs_rq： cfs調度的進程運行隊列信息 ，包含紅黑樹的根結點、正在運行的進程指針、用於負載均衡的葉子隊列等。
3）sched_entity： 把需要調度的東西抽象成調度實體 ，調度實體可以是進程、進程組、用戶等。這里包含負載權重值、對應紅黑樹結點、 虛擬運行時vruntime 等。
4）sched_class：把 調度策略(演算法)抽象成調度類 ，包含一組通用的調度操作介面。介面和實現是分離，可以根據調度介面去實現不同的調度演算法，使一個Linux調度程序可以有多個不同的調度策略。
1） 關閉內核搶占 ，初始化部分變數。獲取當前CPU的ID號，並賦值給局部變數CPU， 使rq指向CPU對應的運行隊列 。 標識當前CPU發生任務切換 ，通知RCU更新狀態，如果當前CPU處於rcu_read_lock狀態，當前進程將會放入rnp-> blkd_tasks阻塞隊列，並呈現在rnp-> gp_tasks鏈表中。 關閉本地中斷 ，獲取所要保護的運行隊列的自旋鎖， 為查找可運行進程做准備 。
2） 檢查prev的狀態，更新運行隊列 。如果不是可運行狀態，而且在內核態沒被搶占，應該從運行隊列中 刪除prev進程 。如果是非阻塞掛起信號，而且狀態為TASK_INTER-RUPTIBLE，就把該進程的狀態設置為TASK_RUNNING，並將它 插入到運行隊列 。
3）task_on_rq_queued(prev) 將pre進程插入到運行隊列的隊尾。
4）pick_next_task 選取將要執行的next進程。
5）context_switch(rq, prev, next)進行 進程上下文切換 。
1) 該進程分配的CPU時間片用完。
2) 該進程主動放棄CPU(例如IO操作)。
3) 某一進程搶佔CPU獲得執行機會。
Linux並沒有使用x86 CPU自帶的任務切換機制，需要通過手工的方式實現了切換。
進程創建後在內核的數據結構為task_struct ， 該結構中有掩碼屬性cpus_allowed，4個核的CPU可以有4位掩碼，如果CPU開啟超線程，有一個8位掩碼，進程可以運行在掩碼位設置為1的CPU上。
Linux內核API提供了兩個系統調用 ，讓用戶可以修改和查看當前的掩碼：
1) sched_setaffinity()：用來修改位掩碼。
2) sched_getaffinity()：用來查看當前的位掩碼。
在下次task被喚醒時，select_task_rq_fair根據cpu_allowed里的掩碼來確定將其置於哪個CPU的運行隊列，一個進程在某一時刻只能存在於一個CPU的運行隊列里。
在Nginx中，使用了CPU親和度來完成某些場景的工作：
worker_processes 4;
worker_cpu_affinity 0001001001001000;
上面這個配置說明了4個工作進程中的每一個和一個CPU核掛鉤。如果這個內容寫入Nginx的配置文件中，然後Nginx啟動或者重新載入配置的時候，若worker_process是4，就會啟用4個worker，然後把worker_cpu_affinity後面的4個值當作4個cpu affinity mask，分別調用ngx_setaffinity，然後就把4個worker進程分別綁定到CPU0～3上。
worker_processes 2;
worker_cpu_affinity 01011010;
上面這個配置則說明了兩個工作進程中的每一個和2個核掛鉤。
Ⅵ 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小，將得到優先調度。這是一個隨運行而動態變化的過程。
Ⅶ 一文讀懂Linux任務間調度原理和整個執行過程
在前文中，我們分析了內核中進程和線程的統一結構體task_struct，並分析進程、線程的創建和派生的過程。在本文中，我們會對任務間調度進行詳細剖析，了解其原理和整個執行過程。由此，進程、線程部分的大體框架就算是介紹完了。本節主要分為三個部分：Linux內核中常見的調度策略，調度的基本結構體以及調度發生的整個流程。下面將詳細展開說明。
Linux 作為一個多任務操作系統，將每個 CPU 的時間劃分為很短的時間片，再通過調度器輪流分配給各個任務使用，因此造成多任務同時運行的錯覺。為了維護 CPU 時間，Linux 通過事先定義的節拍率（內核中表示為 HZ），觸發時間中斷，並使用全局變數 Jiffies 記錄了開機以來的節拍數。每發生一次時間中斷，Jiffies 的值就加 1。節拍率 HZ 是內核的可配選項，可以設置為 100、250、1000 等。不同的系統可能設置不同的數值，可以通過查詢 /boot/config 內核選項來查看它的配置值。
Linux的調度策略主要分為實時任務和普通任務。實時任務需求盡快返回結果，而普通任務則沒有較高的要求。在前文中我們提到了task_struct中調度策略相應的變數為policy，調度優先順序有prio, static_prio, normal_prio, rt_priority幾個。優先順序其實就是一個數值，對於實時進程來說，優先順序的范圍是 0 99；對於普通進程，優先順序的范圍是 100 139。數值越小，優先順序越高。
實時調度策略主要包括以下幾種
普通調度策略主要包括以下幾種：
首先，我們需要一個結構體去執行調度策略，即sched_class。該類有幾種實現方式
普通任務調度實體源碼如下，這裡麵包含了 vruntime 和權重 load_weight，以及對於運行時間的統計。
在調度時，多個任務調度實體會首先區分是實時任務還是普通任務，然後通過以時間為順序的紅黑樹結構組合起來，vruntime 最小的在樹的左側，vruntime最多的在樹的右側。以CFS策略為例，則會選擇紅黑樹最左邊的葉子節點作為下一個將獲得 CPU 的任務。而這顆紅黑樹，我們稱之為運行時隊列（run queue），即struct rq。
其中包含結構體cfs_rq，其定義如下，主要是CFS調度相關的結構體，主要有權值相關變數、vruntime相關變數以及紅黑樹指針，其中結構體rb_root_cached即為紅黑樹的節點
對結構體dl_rq有類似的定義，運行隊列由紅黑樹結構體構成，並按照deadline策略進行管理
對於實施隊列相應的rt_rq則有所不同，並沒有用紅黑樹實現。
下面再看看調度類sched_class，該類以函數指針的形式定義了諸多隊列操作，如
調度類分為下面幾種：
隊列操作中函數指針指向不同策略隊列的實際執行函數函數，在linux/kernel/sched/目錄下，fair.c、idle.c、rt.c等文件對不同類型的策略實現了不同的函數，如fair.c中定義了
以選擇下一個任務為例，CFS對應的是pick_next_task_fair，而rt_rq對應的則是pick_next_task_rt，等等。
由此，我們來總結一下：
有了上述的基本策略和基本調度結構體，我們可以形成大致的骨架，下面就是需要核心的調度流程將其拼湊成一個整體，實現調度系統。調度分為兩種，主動調度和搶占式調度。
說到調用，逃不過核心函數schele()。其中sched_submit_work()函數完成當前任務的收尾工作，以避免出現如死鎖或者IO中斷等情況。之後首先禁止搶占式調度的發生，然後調用__schele()函數完成調度，之後重新打開搶占式調度，如果需要重新調度則會一直重復該過程，否則結束函數。
而__schele()函數則是實際的核心調度函數，該函數主要操作包括選取下一進程和進行上下文切換，而上下文切換又包括用戶態空間切換和內核態的切換。具體的解釋可以參照英文源碼注釋以及中文對各個步驟的注釋。
其中核心函數是獲取下一個任務的pick_next_task()以及上下文切換的context_switch()，下面詳細展開剖析。首先看看pick_next_task()，該函數會根據調度策略分類，調用該類對應的調度函數選擇下一個任務實體。根據前文分析我們知道，最終是在不同的紅黑樹上選擇最左節點作為下一個任務實體並返回。
下面來看看上下文切換。上下文切換主要干兩件事情，一是切換任務空間，也即虛擬內存；二是切換寄存器和 CPU 上下文。關於任務空間的切換放在內存部分的文章中詳細介紹，這里先按下不表，通過任務空間切換實際完成了用戶態的上下文切換工作。下面我們重點看一下內核態切換，即寄存器和CPU上下文的切換。
switch_to()就是寄存器和棧的切換，它調用到了 __switch_to_asm。這是一段匯編代碼，主要用於棧的切換， 其中32位使用esp作為棧頂指針，64位使用rsp，其他部分代碼一致。通過該段匯編代碼我們完成了棧頂指針的切換，並調用__switch_to完成最終TSS的切換。注意switch_to中其實是有三個變數，分別是prev, next, last，而實際在使用時，我們會對last也賦值為prev。這里的設計意圖需要結合一個例子來說明。假設有ABC三個任務，從A調度到B，B到C，最後C回到A，我們假設僅保存prev和next，則流程如下
最終調用__switch_to()函數。該函數中涉及到一個結構體TSS(Task State Segment)，該結構體存放了所有的寄存器。另外還有一個特殊的寄存器TR（Task Register）會指向TSS，我們通過更改TR的值，會觸發硬體保存CPU所有寄存器在當前TSS，並從新的TSS讀取寄存器的值載入入CPU，從而完成一次硬中斷帶來的上下文切換工作。系統初始化的時候，會調用 cpu_init()給每一個 CPU 關聯一個 TSS，然後將 TR 指向這個 TSS，然後在操作系統的運行過程中，TR 就不切換了，永遠指向這個 TSS。當修改TR的值得時候，則為任務調度。
更多Linux內核視頻教程文本資料免費領取後台私信【 內核大禮包 】自行獲取。
在完成了switch_to()的內核態切換後，還有一個重要的函數finish_task_switch()負責善後清理工作。在前面介紹switch_to三個參數的時候我們已經說明了使用last的重要性。而這里為何讓prev和last均賦值為prev，是因為prev在後面沒有需要用到，所以節省了一個指針空間來存儲last。
至此，我們完成了內核態的切換工作，也完成了整個主動調度的過程。
搶占式調度通常發生在兩種情況下。一種是某任務執行時間過長，另一種是當某任務被喚醒的時候。首先看看任務執行時間過長的情況。
該情況需要衡量一個任務的執行時間長短，執行時間過長則發起搶占。在計算機裡面有一個時鍾，會過一段時間觸發一次時鍾中斷，通知操作系統時間又過去一個時鍾周期，通過這種方式可以查看是否是需要搶占的時間點。
時鍾中斷處理函數會調用scheler_tick()。該函數首先取出當前CPU，並由此獲取對應的運行隊列rq和當前任務curr。接著調用該任務的調度類sched_class對應的task_tick()函數進行時間事件處理。
以普通任務隊列為例，對應的調度類為fair_sched_class，對應的時鍾處理函數為task_tick_fair()，該函數會獲取當前的調度實體和運行隊列，並調用entity_tick()函數更新時間。
在entity_tick()中，首先會調用update_curr()更新當前任務的vruntime，然後調用check_preempt_tick()檢測現在是否可以發起搶占。
check_preempt_tick() 先是調用 sched_slice() 函數計算出一個調度周期中該任務運行的實際時間 ideal_runtime。sum_exec_runtime 指任務總共執行的實際時間，prev_sum_exec_runtime 指上次該進程被調度時已經佔用的實際時間，所以 sum_exec_runtime - prev_sum_exec_runtime 就是這次調度佔用實際時間。如果這個時間大於 ideal_runtime，則應該被搶佔了。除了這個條件之外，還會通過 __pick_first_entity 取出紅黑樹中最小的進程。如果當前進程的 vruntime 大於紅黑樹中最小的進程的 vruntime，且差值大於 ideal_runtime，也應該被搶佔了。
如果確認需要被搶占，則會調用resched_curr()函數，該函數會調用set_tsk_need_resched()標記該任務為_TIF_NEED_RESCHED，即該任務應該被搶占。
某些任務會因為中斷而喚醒，如當 I/O 到來的時候，I/O進程往往會被喚醒。在這種時候，如果被喚醒的任務優先順序高於 CPU 上的當前任務，就會觸發搶占。try_to_wake_up() 調用 ttwu_queue() 將這個喚醒的任務添加到隊列當中。ttwu_queue() 再調用 ttwu_do_activate() 激活這個任務。ttwu_do_activate() 調用 ttwu_do_wakeup()。這裡面調用了 check_preempt_curr() 檢查是否應該發生搶占。如果應該發生搶占，也不是直接踢走當前進程，而是將當前進程標記為應該被搶占。
由前面的分析，我們知道了不論是是當前任務執行時間過長還是新任務喚醒，我們均會對現在的任務標記位_TIF_NEED_RESCUED，下面分析實際搶占的發生。真正的搶占還需要一個特定的時機讓正在運行中的進程有機會調用一下 __schele()函數，發起真正的調度。
實際上會調用__schele()函數共有以下幾個時機
從系統調用返回用戶態：以64位為例，系統調用的鏈路為do_syscall_64->syscall_return_slowpath->prepare_exit_to_usermode->exit_to_usermode_loop。在exit_to_usermode_loop中，會檢測是否為_TIF_NEED_RESCHED，如果是則調用__schele()
內核態啟動：內核態的執行中，被搶占的時機一般發生在 preempt_enable() 中。在內核態的執行中，有的操作是不能被中斷的，所以在進行這些操作之前，總是先調用 preempt_disable() 關閉搶占，當再次打開的時候，就是一次內核態代碼被搶占的機會。preempt_enable() 會調用 preempt_count_dec_and_test()，判斷 preempt_count 和 TIF_NEED_RESCHED 是否可以被搶占。如果可以，就調用 preempt_schele->preempt_schele_common->__schele 進行調度。
本文分析了任務調度的策略、結構體以及整個調度流程，其中關於內存上下文切換的部分尚未詳細敘述，留待內存部分展開剖析。
1、調度相關結構體及函數實現
2、schele核心函數
Ⅷ 淺析Linux下進程的調度策略與優先順序
在 Linux 中，線程是由進程來實現的，可以認為線程就是一個輕量級的進程，因此，線程調度是按照進程調度的方式來進行的。這樣設計，線程調度流程可以直接復用進程調度流程，沒必要再設計一個進程內的線程調度器了。
在 Linux 中，進程調度器是基於進程的調度策略與調度優先順序來決定調度哪個進程運行。
調度策略主要包括：
調度優先順序的范圍是 0~99，數值越大，表示優先順序越高。
其中，SCHED_OTHER、SCHED_IDLE、SCHED_BACH 為非實時調度策略，其調度優先順序為 0。而 SCHED_FIFO、SCHED_RR 是實時調度策略，其調度優先順序范圍為 1~99。
實時調度策略的進程總是比非實時調度策略的進程優先順序高。
在 Linux 內部實現中，調度器會為每個可能的調度優先順序維護一個可運行的進程列表，以最高優先順序列表頭部的進程作為下一次調度的進程，所有的調度都是搶占式的，如果一個具有更高調度優先順序的進程轉換為可運行狀態，那麼當前運行的進程將被強制進入其等待的隊列中。
SCHED_OTHER
該調度策略是默認的 Linux 分時調度策略，該調度策略為非實時的，其調度優先順序總是為 0。
對於該調度策略類型的進程，調度器是基於動態優先順序來調度的。動態優先順序跟屬性 nice 有關，nice 的值會隨著進程的運行時間而動態改變，以確保所有具有 SCHED_OTHER 策略的進程公平地得到調度。
在 Linux 中，nice 的值范圍為-20 ~ +19，默認值為 0。nice 值越大，則優先順序越低，因此相對較低 nice 值的進程可以獲得更多的處理器時間。
通過命令 ps -el 查看系統中的進程列表，其中 NI 列就是進程對應的 nice 值。
使用 top 命令，看到的 NI 列也是進程的 nice 值。
調整 nice 值，可以通過 shell 命令 nice ，該命令可以按照指定的 nice 值運行 cmd ，命令的幫助信息為：
重新調整已運行進程的 nice 值，可通過 renice 命令實現，命令的幫助信息為：
另外，可以執行 top 命令，輸入 r ，根據提示輸入進程的 pid ，再輸入 nice 數值，也可以調整進程的 nice 值。
SCHED_FIFO
該調度策略為先入先出調度策略，簡單概括，就是一旦進程佔用了 CPU，則一直運行，直到有更高優先順序的任務搶占，或者進程自己放棄佔用 CPU。
SCHED_RR
該調度策略為時間片輪轉調度策略，該調度策略是基於 SCHED_FIFO 策略的演進，其在每個進程上增加一個時間片限制，當時間片使用完成後，調度器將該進程置於隊列的尾端，放在尾端保證了所有具有相同調度優先順序的進程的調度公平。
使用 top 命令，如果 PR 列的值為 RT ，則說明該進程採用的是實時調度策略，其調度策略為 SCHED_FIFO 或者 SCHED_RR，而對於非實時調度策略的進程，該列的值為 NI + 20 。
可以通過命令 ps -eo state,uid,pid,ppid,rtprio,time,comm 來查看進程對應的實時優先順序，實時優先順序位於 RTPRIO 列下，如果進程對應的列顯示為 - ，說明該進程不是實時進程。
chrt 命令可以用來很簡單地更改進程的調度策略與調度優先順序。在 Linux 下查看 chrt 命令的幫助信息：
比如，獲取某個進程的調度策略，使用如下命令：
在比如，設置某個進程的調度策略為 SCHED_FIFO，調度優先順序為 70，使用如下命令：
Ⅸ Linux中進程和線程的對比與區別
線程和進程是另一對有意義的概念，主要區別和聯系如下：
進程是操作系統進行資源分配的基本單位，擁有完整的進程空間。進行系統資源分配的時候，除了CPU資源之外，不會給線程分配獨立的資源，線程所需要的資源需要共享。
線程是進程的一部分，如果沒有進行顯示的線程分配，可以認為進程是單線程的；如果進程中建立了線程，則可認為系統是多線程的。
多線程和多進程是兩種不同的概念。多線程與多進程有不同的資源共享方式。
進程有進程式控制制塊PCB，系統通過PCB對進程進行調度。進程有線程式控制制塊TCP，但TCB所表示的狀態比PCB要少的多。