前景回顧

---

進程調度

---

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

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

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

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

進程的分類

---

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

類型 描述 示例 交互式進程(interactive process) 此類進程經常與用戶進行交互, 因此需要花費很多時間等待鍵盤和鼠標操作. 當接受了用戶的輸入後, 進程必須很快被喚醒, 否則用戶會感覺系統反應遲鈍 shell, 文本編輯程序和圖形應用程序 批處理進程(batch process) 此類進程不必與用戶交互, 因此經常在後台運行. 因為這樣的進程不必很快相應, 因此常受到調度程序的怠慢 程序語言的編譯程序, 數據庫搜索引擎以及科學計算 實時進程(real-time process) 這些進程由很強的調度需要, 這樣的進程絕不會被低優先級的進程阻塞. 並且他們的響應時間要盡可能的短 視頻音頻應用程序, 機器人控制程序以及從物理傳感器上收集數據的程序

不同進程采用不同的調度策略

---

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

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

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

linux調度器的演變

---

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

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

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

Linux的調度器組成

---

2個調度器

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

一種是直接的, 比如進程打算睡眠或出於其他原因放棄CPU

另一種是通過周期性的機制, 以固定的頻率運行, 不時的檢測是否有必要

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

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

調度器類是實現了不同調度策略的實例，如 CFS、RT class等。

它們的關系如下圖

當前的內核支持兩種調度器類（sched_setscheduler系統調用可修改進程的策略）：CFS（公平）、RT（實時）；5種調度策略：SCHED_NORAML（最常見的策略）、SCHED_BATCH（除了不能搶占外與常規任務一樣，允許任務運行更長時間，更好地使用高速緩存，適合於成批處理的工作）、SCHED_IDLE（它甚至比nice 19還有弱，為了避免優先級反轉使用）和SCHED_RR（循環調度，擁有時間片，結束後放在隊列末）、SCHED_FIFO（沒有時間片，可以運行任意長的時間）；其中前面三種策略使用的是cfs調度器類，後面兩種使用rt調度器類。<喎?http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxoMSBpZD0="linux優先級的表示">linux優先級的表示

---

優先級的內核表示

---

linux優先級概述

在用戶空間通過nice命令設置進程的靜態優先級, 這在內部會調用nice系統調用, 進程的nice值在-20~+19之間. 值越低優先級越高.

setpriority系統調用也可以用來設置進程的優先級. 它不僅能夠修改單個線程的優先級, 還能修改進程組中所有進程的優先級, 或者通過制定UID來修改特定用戶的所有進程的優先級

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

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

linux2.6內核將任務優先級進行了一個劃分, 實時優先級范圍是0到MAX_RT_PRIO-1（即99），而普通進程的靜態優先級范圍是從MAX_RT_PRIO到MAX_PRIO-1（即100到139）。

優先級范圍 描述 0——99 實時進程 100——139 非實時進程

內核的優先級表示

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

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

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

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

/*  http://lxr.free-electrons.com/source/include/linux/sched/prio.h?v=4.6#L4 */
#define MAX_NICE        19
#define MIN_NICE        -20
#define NICE_WIDTH      (MAX_NICE - MIN_NICE + 1)

/* http://lxr.free-electrons.com/source/include/linux/sched/prio.h?v=4.6#L24  */
#define MAX_PRIO        (MAX_RT_PRIO + 40)
#define DEFAULT_PRIO        (MAX_RT_PRIO + 20)

宏 值 描述 MIN_NICE -20 對應於優先級100, 可以使用NICE_TO_PRIO和PRIO_TO_NICE轉換 MAX_NICE 19 對應於優先級139, 可以使用NICE_TO_PRIO和PRIO_TO_NICE轉換 NICE_WIDTH 40 nice值得范圍寬度, 即[-20, 19]共40個數字的寬度 MAX_RT_PRIO, MAX_USER_RT_PRIO 100 實時進程的最大優先級 MAX_PRIO 140 普通進程的最大優先級 DEFAULT_PRIO 120 進程的默認優先級, 對應於nice=0 MAX_DL_PRIO 0 使用EDF最早截止時間優先調度算法的實時進程最大的優先級

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

//  http://lxr.free-electrons.com/source/include/linux/sched/prio.h?v=4.6#L27
/*
 * Convert user-nice values [ -20 ... 0 ... 19 ]
 * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
 * and back.
 */
#define NICE_TO_PRIO(nice)      ((nice) + DEFAULT_PRIO)
#define PRIO_TO_NICE(prio)      ((prio) - DEFAULT_PRIO)

/*
 * 'User priority' is the nice value converted to something we
 * can work with better when scaling various scheduler parameters,
 * it's a [ 0 ... 39 ] range.
 */
#define USER_PRIO(p)            ((p)-MAX_RT_PRIO)
#define TASK_USER_PRIO(p)       USER_PRIO((p)->static_prio)
#define MAX_USER_PRIO           (USER_PRIO(MAX_PRIO))

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

/*
 * Convert nice value [19,-20] to rlimit style value [1,40].
 */
static inline long nice_to_rlimit(long nice)
{
    return (MAX_NICE - nice + 1);
}

/*
 * Convert rlimit style value [1,40] to nice value [-20, 19].
 */
static inline long rlimit_to_nice(long prio)
{
    return (MAX_NICE - prio + 1);
}

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

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

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

#define MAX_DL_PRIO             0

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

static inline int dl_prio(int prio)
{
    if (unlikely(prio < MAX_DL_PRIO))
            return 1;
    return 0;
}

static inline int dl_task(struct task_struct *p)
{
    return dl_prio(p->prio);
}

static inline bool dl_time_before(u64 a, u64 b)
{
    return (s64)(a - b) < 0;
}

進程的優先級表示

---

struct task_struct
{
    /* 進程優先級
     * prio: 動態優先級，范圍為100~139，與靜態優先級和補償(bonus)有關
     * static_prio: 靜態優先級，static_prio = 100 + nice + 20 (nice值為-20~19,所以static_prio值為100~139)
     * normal_prio: 沒有受優先級繼承影響的常規優先級，具體見normal_prio函數，跟屬於什麼類型的進程有關
     */
    int prio, static_prio, normal_prio;
    /* 實時進程優先級 */
    unsigned int rt_priority;
}

動態優先級 靜態優先級 實時優先級

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

為什麼表示動態優先級需要兩個值prio和normal_prio

調度器會考慮的優先級則保存在prio. 由於在某些情況下內核需要暫時提高進程的優先級, 因此需要用prio表示. 由於這些改變不是持久的, 因此靜態優先級static_prio和普通優先級normal_prio不受影響.

此外還用了一個字段rt_priority保存了實時進程的優先級

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

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

進程優先級的計算

---

前面說了task_struct中的幾個優先級的字段

靜態優先級 普通優先級 動態優先級 實時優先級 static_prio normal_prio prio rt_priority

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

normal_prio設置普通優先級normal_prio

---

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

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

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

/*
 * __normal_prio - return the priority that is based on the static prio
 * 普通進程(非實時進程)的普通優先級normal_prio就是靜態優先級static_prio
 */
static inline int __normal_prio(struct task_struct *p)
{
    return p->static_prio;
}

/*
 * Calculate the expected normal priority: i.e. priority
 * without taking RT-inheritance into account. Might be
 * boosted by interactivity modifiers. Changes upon fork,
 * setprio syscalls, and whenever the interactivity
 * estimator recalculates.
 */
static inline int normal_prio(struct task_struct *p)
{
    int prio;

    if (task_has_dl_policy(p))              /*  EDF調度的實時進程  */
            prio = MAX_DL_PRIO-1;
    else if (task_has_rt_policy(p))       /*  普通實時進程的優先級  */
            prio = MAX_RT_PRIO-1 - p->rt_priority;
    else                                              /*  普通進程的優先級  */
            prio = __normal_prio(p);
    return prio;
}

進程類型 調度器 普通優先級normal_prio EDF實時進程 EDF MAX_DL_PRIO-1 = -1 普通實時進程 RT MAX_RT_PRIO-1 - p->rt_priority = 99 - rt_priority 普通進程 CFS __normal_prio(p) = static_prio

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

輔助函數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中的哪個, 從而確定其所屬的調度類, 進一步就確定了其進程類型

static inline int idle_policy(int policy)
{
    return policy == SCHED_IDLE;
}
static inline int fair_policy(int policy)
{
    return policy == SCHED_NORMAL || policy == SCHED_BATCH;
}

static inline int rt_policy(int policy)
{
    return policy == SCHED_FIFO || policy == SCHED_RR;
}

static inline int dl_policy(int policy)
{
        return policy == SCHED_DEADLINE;
}
static inline bool valid_policy(int policy)
{
        return idle_policy(policy) || fair_policy(policy) ||
                rt_policy(policy) || dl_policy(policy);
}

static inline int task_has_rt_policy(struct task_struct *p)
{
        return rt_policy(p->policy);
}

static inline int task_has_dl_policy(struct task_struct *p)
{
        return dl_policy(p->policy);
}

關於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的值，所以越大，優先級越高。

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

為什麼需要__normal_prio函數

---

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

effective_prio設置動態優先級prio

---

可以通過函數effective_prio用靜態優先級static_prio計算動態優先級, 即·

p->prio = effective_prio(p);

該函數定義在kernel/sched/core.c, line 861

/*
 * Calculate the current priority, i.e. the priority
 * taken into account by the scheduler. This value might
 * be boosted by RT tasks, or might be boosted by
 * interactivity modifiers. Will be RT if the task got
 * RT-boosted. If not then it returns p->normal_prio.
 */
static int effective_prio(struct task_struct *p)
{
    p->normal_prio = normal_prio(p);
    /*
     * If we are RT tasks or we were boosted to RT priority,
     * keep the priority unchanged. Otherwise, update priority
     * to the normal priority:
     */
    if (!rt_prio(p->prio))
            return p->normal_prio;
    return p->prio;
}

我們會發現函數首先effective_prio設置了普通優先級, 顯然我們用effective_prio同時設置了兩個優先級(普通優先級normal_prio和動態優先級prio)

因此計算動態優先級的流程如下

設置進程的普通優先級(實時進程99-rt_priority, 普通進程為static_priority)

計算進程的動態優先級(實時進程則維持動態優先級的prio不變, 普通進程的動態優先級即為其普通優先級)

最後, 我們綜述一下在針對不同類型進程的計算結果

進程類型 實時優先級rt_priority 靜態優先級static_prio 普通優先級normal_prio 動態優先級prio EDF調度的實時進程 rt_priority 不使用 MAX_DL_PRIO-1 維持原prio不變 RT算法調度的實時進程 rt_priority 不使用 MAX_RT_PRIO-1-rt_priority 維持原prio不變 普通進程 不使用 static_prio static_prio static_prio 優先級提高的普通進程 不使用 static_prio(改變) static_prio 維持原prio不變

為什麼effective_prio使用優先級數值檢測實時進程

---

t_prio會檢測普通優先級是否在實時范圍內, 即是否小於MAX_RT_PRIO.參見include/linux/sched/rt.h#L6

static inline int rt_prio(int prio)
{
    if (unlikely(prio < MAX_RT_PRIO))
        return 1;
    return 0;
}

而前面我們在normal_prio的時候, 則通過task_has_rt_policy來判斷其policy屬性來確定

policy == SCHED_FIFO || policy == SCHED_RR;

那麼為什麼effective_prio重檢測實時進程是rt_prio基於優先級數值, 而非task_has_rt_policy或者rt_policy?

對於臨時提高至實時優先級的非實時進程來說, 這個是必要的, 這種情況可能發生在是哦那個實時互斥量(RT-Mutex)時.

設置prio的時機

---

在新進程用wake_up_new_task喚醒時, 或者使用nice系統調用改變其靜態優先級時, 則會通過effective_prio的方法設置p->prio

wake_up_new_task(), 計算此進程的優先級和其他調度參數，將新的進程加入到進程調度隊列並設此進程為可被調度的，以後這個進程可以被進程調度模塊調度執行。

進程創建時copy_process通過調用sched_fork來初始化和設置調度器的過程中會設置子進程的優先級

nice系統調用的實現

---

nice系統調用是的內核實現是sys_nice, 其定義在kernel/sched/core.c#L7498，

它在通過一系列檢測後, 通過set_user_nice函數， 其定義在kernel/sched/core.c#L3497

關於其具體實現我們會在另外一篇博客裡面詳細講

fork時優先級的繼承

---

在進程分叉處子進程時, 子進程的靜態優先級繼承自父進程. 子進程的動態優先級p->prio則被設置為父進程的普通優先級, 這確保了實時互斥量引起的優先級提高不會傳遞到子進程.

可以參照sched_fork函數, 在進程復制的過程中copy_process通過調用sched_fork來設置子進程優先級, 參見sched_fork函數

/*
 * fork()/clone()-time setup:
 */
int sched_fork(unsigned long clone_flags, struct task_struct *p)
{
    /*  ......  */
    /*
     * Make sure we do not leak PI boosting priority to the child.
     * 子進程的動態優先級被設置為父進程普通優先級 
     */
    p->prio = current->normal_prio;

    /*
     * Revert to default priority/policy on fork if requested.
     * sched_reset_on_fork標識用於判斷是否恢復默認的優先級或調度策略

     */
    if (unlikely(p->sched_reset_on_fork))  /*  如果要恢復默認的調度策略, 即SCHED_NORMAL  */
    {
        /*   首先是設置靜態優先級static_prio
         *   由於要恢復默認的調度策略
         *   對於父進程是實時進程的情況, 靜態優先級就設置為DEFAULT_PRIO
         *
         *   對於父進程是非實時進程的情況, 要保證子進程優先級不小於DEFAULT_PRIO
         *   父進程nice < 0即static_prio < 的重新設置為DEFAULT_PRIO的重新設置為DEFAULT_PRIO
         *   父進程nice > 0的時候, 則什麼也沒做
         *   */
        if (task_has_dl_policy(p) || task_has_rt_policy(p))
        {
            p->policy = SCHED_NORMAL;           /*  普通進程調度策略  */
            p->static_prio = NICE_TO_PRIO(0);   /*  靜態優先級為nice = 0 即DEFAULT_PRIO*/
            p->rt_priority = 0;                             /*  實時優先級為0  */
        }
        else if (PRIO_TO_NICE(p->static_prio) < 0)  /*  */
            p->static_prio = NICE_TO_PRIO(0);   /*  */

        /*  接著就通過__normal_prio設置其普通優先級和動態優先級
          *  這裡做了一個優化, 因為用sched_reset_on_fork標識設置恢復默認調度策略後
          *  創建的子進程是是SCHED_NORMAL的非實時進程
          *  因此就不需要繞一大圈用effective_prio設置normal_prio和prio了 
          *  直接用__normal_prio設置就可  */
        p->prio = p->normal_prio = __normal_prio(p); /*  設置*/

        /*  設置負荷權重  */
        set_load_weight(p);

        /*
         * We don't need the reset flag anymore after the fork. It has
         * fulfilled its duty:
         */
        p->sched_reset_on_fork = 0;
    }
    /*  ......  */
}

總結

---

task_struct采用了四個成員表示進程的優先級:prio和normal_prio表示動態優先級, static_prio表示進程的靜態優先級. 同時還用了rt_priority表示實時進程的優先級

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

調度器會考慮的優先級則保存在prio. 由於在某些情況下內核需要暫時提高進程的優先級, 因此需要用prio表示. 由於這些改變不是持久的, 因此靜態優先級static_prio和普通優先級normal_prio不受影響.
此外還用了一個字段rt_priority保存了實時進程的優先級靜態優先級static_prio(普通進程)和實時優先級rt_priority(實時進程)是計算的起點, 通過他們計算進程的普通優先級normal_prio和動態優先級prio.

內核通過normal_prIo函數計算普通優先級normal_prio
通過effective_prio函數計算動態優先級prio