Linux進程優先順序的處理--Linux進程的管理與調度(二十二)

03-03

存了對每個進程的唯一描述, 並通過若干結構與其他進程連接起來.

調度器面對的情形就是這樣, 其任務是在程序之間共享CPU時間, 創造並行執行的錯覺, 該任務分為兩個不同的部分, 其中一個涉及調度策略, 另外一個涉及上下文切換.

內核必須提供一種方法, 在各個進程之間儘可能公平地共享CPU時間, 而同時又要考慮不同的任務優先順序.

調度器的一個重要目標是有效地分配 CPU 時間片，同時提供很好的用戶體驗。調度器還需要面對一些互相衝突的目標，例如既要為關鍵實時任務最小化響應時間, 又要最大限度地提高 CPU 的總體利用率.

調度器的一般原理是, 按所需分配的計算能力, 向系統中每個進程提供最大的公正性, 或者從另外一個角度上說, 他試圖確保沒有進程被虧待.

1.2 進程的分類

Linux把進程區分為實時進程和非實時進程, 其中非實時進程進一步劃分為互動式進程和批處理進程

Llinux中, 調度演算法可以明確的確認所有實時進程的身份, 但是沒辦法區分互動式程序和批處理程序, linux2.6的調度程序實現了基於進程過去行為的啟發式演算法, 以確定進程應該被當做互動式進程還是批處理進程. 當然與批處理進程相比, 調度程序有偏愛互動式進程的傾向

1.3 不同進程採用不同的調度策略

根據進程的不同分類Linux採用不同的調度策略.

對於實時進程，採用FIFO, Round Robin或者Earliest Deadline First (EDF)最早截止期限優先調度演算法|的調度策略.

對於普通進程，則需要區分互動式和批處理式的不同。傳統Linux調度器提高互動式應用的優先順序，使得它們能更快地被調度。而CFS和RSDL等新的調度器的核心思想是」完全公平」。這個設計理念不僅大大簡化了調度器的代碼複雜度，還對各種調度需求的提供了更完美的支持.

注意Linux通過將進程和線程調度視為一個，同時包含二者。進程可以看做是單個線程，但是進程可以包含共享一定資源（代碼和/或數據）的多個線程。因此進程調度也包含了線程調度的功能.

目前非實時進程的調度策略比較簡單, 因為實時進程值只要求儘可能快的被響應, 基於優先順序, 每個進程根據它重要程度的不同被賦予不同的優先順序，調度器在每次調度時, 總選擇優先順序最高的進程開始執行. 低優先順序不可能搶佔高優先順序, 因此FIFO或者Round Robin的調度策略即可滿足實時進程調度的需求.

但是普通進程的調度策略就比較麻煩了, 因為普通進程不能簡單的只看優先順序, 必須公平的佔有CPU, 否則很容易出現進程飢餓, 這種情況下用戶會感覺操作系統很卡, 響應總是很慢，因此在linux調度器的發展歷程中經過了多次重大變動, linux總是希望尋找一個最接近於完美的調度策略來公平快速的調度進程.

1.4 linux調度器的演變

一開始的調度器是複雜度為的始調度演算法(實際上每次會遍歷所有任務，所以複雜度為O(n)), 這個演算法的缺點是當內核中有很多任務時，調度器本身就會耗費不少時間，所以，從linux2.5開始引入赫赫有名的調度器

然而，linux是集全球很多程序員的聰明才智而發展起來的超級內核，沒有最好，只有更好，在調度器風光了沒幾天就又被另一個更優秀的調度器取代了，它就是CFS調度器Completely Fair Scheduler. 這個也是在2.6內核中引入的，具體為2.6.23，即從此版本開始，內核使用CFS作為它的默認調度器，調度器被拋棄了, 其實CFS的發展也是經歷了很多階段，最早期的樓梯演算法(SD), 後來逐步對SD演算法進行改進出RSDL(Rotating Staircase Deadline Scheduler), 這個演算法已經是」完全公平」的雛形了，直至CFS是最終被內核採納的調度器, 它從RSDL/SD中吸取了完全公平的思想，不再跟蹤進程的睡眠時間，也不再企圖區分互動式進程。它將所有的進程都統一對待，這就是公平的含義。CFS的演算法和實現都相當簡單，眾多的測試表明其性能也非常優越

欄位版本O(n)的始調度演算法linux-0.11~2.4O(1)調度器linux-2.5CFS調度器linux-2.6~至今

1.5 Linux的調度器組成

2個調度器

可以用兩種方法來激活調度

一種是直接的, 比如進程打算睡眠或出於其他原因放棄CPU
另一種是通過周期性的機制, 以固定的頻率運行, 不時的檢測是否有必要

因此當前linux的調度程序由兩個調度器組成：主調度器，周期性調度器(兩者又統稱為通用調度器(generic scheduler)或核心調度器(core scheduler))

並且每個調度器包括兩個內容：調度框架(其實質就是兩個函數框架)及調度器類

6種調度策略

linux內核目前實現了6中調度策略(即調度演算法), 用於對不同類型的進程進行調度, 或者支持某些特殊的功能

5個調度器類

而依據其調度策略的不同實現了5個調度器類, 一個調度器類可以用一種種或者多種調度策略調度某一類進程, 也可以用於特殊情況或者調度特殊功能的進程.

其所屬進程的優先順序順序為

3個調度實體

調度器不限於調度進程, 還可以調度更大的實體, 比如實現組調度.

這種一般性要求調度器不直接操作進程, 而是處理可調度實體, 因此需要一個通用的數據結構描述這個調度實體,即seched_entity結構, 其實際上就代表了一個調度對象，可以為一個進程，也可以為一個進程組.

linux中針對當前可調度的實時和非實時進程, 定義了類型為seched_entity的3個調度實體

sched_dl_entity 採用EDF演算法調度的實時調度實體
sched_rt_entity 採用Roound-Robin或者FIFO演算法調度的實時調度實體 rt_sched_class
sched_entity 採用CFS演算法調度的普通非實時進程的調度實體

調度器整體框架

每個進程都屬於某個調度器類(由欄位task_struct->sched_class標識), 由調度器類採用進程對應的調度策略調度(由task_struct->policy )進行調度, task_struct也存儲了其對應的調度實體標識

linux實現了6種調度策略, 依據其調度策略的不同實現了5個調度器類, 一個調度器類可以用一種或者多種調度策略調度某一類進程, 也可以用於特殊情況或者調度特殊功能的進程.

2 linux優先順序的表示

2.1 優先順序的內核表示

linux優先順序概述

內核使用一些簡單的數值範圍0~139表示內部優先順序, 數值越低, 優先順序越高。

從0~99的範圍專供實時進程使用, nice的值[-20,19]則映射到範圍100~139

內核的優先順序表示

內核表示優先順序的所有信息基本都放在include/linux/sched/prio.h中, 其中定義了一些表示優先順序的宏和函數.

優先順序數值通過宏來定義, 如下所示,

其中MAX_NICE和MIN_NICE定義了nice的最大最小值

而MAX_RT_PRIO指定了實時進程的最大優先順序, 而MAX_PRIO則是普通進程的最大優先順序數值

而內核提供了一組宏將優先順序在各種不同的表示形之間轉移

還有一些nice值和rlimit值之間相互轉換的函數nice_to_rlimit和rlimit_to_nice, 這在nice系統調用進行檢查的時候很有用, 他們定義在include/linux/sched/prio.h, L47中, 如下所示

DEF最早截至時間優先實時調度演算法的優先順序描述

此外新版本的內核還引入了EDF實時調度演算法, 它的優先順序比RT進程和NORMAL/BATCH進程的優先順序都要高, 關於EDF的優先順序的設置信息都早內核頭文件include/linux/sched/deadline.h

因此內核將MAX_DL_PRIO設置為0, 可以參見內核文件include/linux/sched/deadline.h

此外也提供了一些EDF優先順序處理所需的函數, 如下所示, 可以參見內核文件include/linux/sched/deadline.h

2.2 進程的優先順序表示

動態優先順序靜態優先順序實時優先順序

其中task_struct採用了三個成員表示進程的優先順序:prio和normal_prio表示動態優先順序, static_prio表示進程的靜態優先順序.

此外還用了一個欄位rt_priority保存了實時進程的優先順序

欄位描述static_prio用於保存靜態優先順序, 是進程啟動時分配的優先順序, ，可以通過nice和sched_setscheduler系統調用來進行修改, 否則在進程運行期間會一直保持恆定rt_priority用於保存實時優先順序normal_prio表示基於進程的靜態優先順序static_prio和調度策略計算出的優先順序. 因此即使普通進程和實時進程具有相同的靜態優先順序, 其普通優先順序也是不同的, 進程分叉(fork)時, 子進程會繼承父進程的普通優先順序prio保存進程的動態優先順序

實時進程的優先順序用實時優先順序rt_priority來表示

3 進程優先順序的計算

前面說了task_struct中的幾個優先順序的欄位

但是這些優先順序是如何關聯的呢, 動態優先順序prio又是如何計算的呢?

3.1 normal_prio函數設置普通優先順序normal_prio

靜態優先順序static_prio(普通進程)和實時優先順序rt_priority(實時進程)是計算的起點

因此他們也是進程創建的時候設定好的, 我們通過nice修改的就是普通進程的靜態優先順序static_prio

首先通過靜態優先順序static_prio計算出普通優先順序normal_prio, 該工作可以由nromal_prio來完成, 該函數定義在kernel/sched/core.c#L861

普通優先順序normal_prio需要根據普通進程和實時進程進行不同的計算, 其中__normal_prio適用於普通進程, 直接將普通優先順序normal_prio設置為靜態優先順序static_prio. 而實時進程的普通優先順序計算依據其實時優先順序rt_priority.

3.1.1 輔助函數task_has_dl_policy和task_has_rt_policy

定義在kernel/sched/sched.h#L117 中

其本質其實就是傳入task->policy調度策略欄位看其值等於SCHED_NORMAL, SCHED_BATCH, SCHED_IDLE, SCHED_FIFO, SCHED_RR, SCHED_DEADLINE中的哪個, 從而確定其所屬的調度類, 進一步就確定了其進程類型

3.1.2 關於rt_priority數值越大, 實時進程優先順序越高的問題

我們前面提到了數值越小, 優先順序越高, 但是此處我們會發現rt_priority的值越大, 其普通優先順序越小, 從而優先順序越高.

因此網上出現了一種說法, 優先順序越高？這又是怎麼回事？難道有一種說法錯了嗎？

實際的原因是這樣的，對於一個實時進程，他有兩個參數來表明優先順序——prio 和 rt_priority，

prio才是調度所用的最終優先順序數值，這個值越小，優先順序越高；

而rt_priority 被稱作實時進程優先順序，他要經過轉化——prio=MAX_RT_PRIO - 1- p->rt_priority;

MAX_RT_PRIO = 100, ;這樣意味著rt_priority值越大，優先順序越高；

而內核提供的修改優先順序的函數，是修改rt_priority的值，所以越大，優先順序越高。

所以用戶在使用實時進程或線程，在修改優先順序時，就會有「優先順序值越大，優先順序越高的說法」，也是對的。

3.1.3 為什麼需要__normal_prio函數

我們肯定會奇怪, 為什麼增加了一個__normal_prio函數做了這麼簡單的工作, 這個其實是有歷史原因的: 在早期的調度器中, 普通優先順序的計算涉及相當多技巧性地工作, 必須檢測互動式進程並提高其優先順序, 而必須」懲罰」非交互進程, 以便是得系統獲得更好的交互體驗. 這需要很多啟發式的計算, 他們可能完成的很好, 也可能不工作