嚴格來說，Linux 不是實時操作系統(tǒng)，但 Linux 卻支持實時調(diào)度算法。與通用調(diào)度算法（如完全公平調(diào)度算法）相比，實時調(diào)度算法更注重任務（進程）的實時性。為什么 Linux 支持實時調(diào)度算法，卻不是實時操作系統(tǒng)呢？有興趣的同學可以去網(wǎng)上查閱相關(guān)的文獻或者資料。

本文主要介紹 Linux 的 Deadline 實時調(diào)度算法。

什么是實時操作系統(tǒng)

實時操作系統(tǒng)能夠保證在一定時間限制內(nèi)完成特定功能的操作系統(tǒng)。實時操作系統(tǒng)有硬實時和軟實時之分，硬實時要求在規(guī)定的時間內(nèi)必須完成操作，這是在操作系統(tǒng)設計時保證的；軟實時則只要按照任務的優(yōu)先級，盡可能快地完成操作即可。屬于硬實時操作系統(tǒng)的有 WinDriver 公司開發(fā)的 VxWorks 和 BlackBerry 公司的 QNX 等，而 Linux 則屬于軟實時操作系統(tǒng)。

Deadline 調(diào)度算法原理

我們先來介紹一下 Deadline 調(diào)度算法的原理。

實時系統(tǒng)除了要求在確定的時間期限內(nèi)做出響應外，還要求在確定的時間期限內(nèi)完成任務，這個確定的時間期限，我們稱之為 Deadline。如果系統(tǒng)未能在 Deadline 內(nèi)完成任務，那么該系統(tǒng)就會產(chǎn)生錯誤。

Deadline 調(diào)度器定義了三個元素：

period：調(diào)度周期，即該任務需要被調(diào)度的周期時間。例如，地球圍繞太陽旋轉(zhuǎn)一周為一個周期，稱之為一年。

runtime：每周期內(nèi)的運行時間，即該任務在該調(diào)度周期內(nèi)至少能夠運行的時間。

deadline：每周期的截止時間，即該任務在一個調(diào)度周期內(nèi)，必須在截止時間之前完成任務。在 Deadline 調(diào)度器中，deadline 可以與 period 相同，稱作 “implicit deadline”，deadline 也可以小于 period，稱作 “constrained deadline”。

這三個元素的關(guān)系可以見下圖：

（圖1）

從上圖可以看出，三者之間的關(guān)系：runtime ≤ deadline ≤ period。

我們舉一個實際的例子，假設系統(tǒng)中有三個周期性任務。為了簡單起見，本例中的任務為之前面提到過的 “implicit deadline”，即 deadline 等于 period：

?

?

如果三個任務都運行在同一個 CPU 上，那么 CPU 的利用率為（未達到100%）：

CPU利用率 = 1/4 + 2/6 + 3/8 = 23/24

那么這三個任務的工作狀態(tài)可以如下圖所示：

（圖2）

通過上圖可知，三個任務都在 deadline 之前完成了各自的任務，周而復始。也就是說，當系統(tǒng)中所有任務的 CPU 利用率不超過 100% 時，Deadline 調(diào)度器能夠很好的滿足每個任務的需求。

Deadline 調(diào)度算法實現(xiàn)

1. 關(guān)鍵數(shù)據(jù)結(jié)構(gòu)

在 Linux 內(nèi)核中，每種調(diào)度器都會定義一個運行隊列來存儲系統(tǒng)中的任務（進程）。Deadline 調(diào)度器則通過?dl_rq?結(jié)構(gòu)來描述這個運行隊列，其定義如下：

struct?dl_rq?{
????struct?rb_root?rb_root;??????//?紅黑樹根節(jié)點
????struct?rb_node?*rb_leftmost;?//?保存deadline最早到期的任務
????unsigned?long?dl_nr_running;?//?隊列中有多少個實時任務
????...
};

從?dl_rq?結(jié)構(gòu)的定義可以看出，Deadline 調(diào)度器使用紅黑樹（紅黑樹是一種平衡二叉樹）來存儲系統(tǒng)中的實時任務，而紅黑樹的鍵則是任務的限期（deadline）。如下圖所示：

（圖3）

上圖中的數(shù)字就是任務的 deadline。

Linux 內(nèi)核通過?sched_dl_entity?結(jié)構(gòu)體來描述一個實時任務，其中的?deadline?字段則表示任務的 deadline。

我們來看看?sched_dl_entity?結(jié)構(gòu)的定義：

struct?sched_dl_entity?{
????struct?rb_node?rb_node;??//?紅黑樹節(jié)點

????u64?dl_runtime;??????????//?任務能夠運行的時間
????u64?dl_deadline;?????????//?任務的相對限期
????u64?dl_period;???????????//?任務的調(diào)度周期
????u64?dl_bw;???????????????//?dl_runtime?/?dl_deadline

????s64?runtime;?????????????//?任務的剩余運行時間
????u64?deadline;????????????//?任務的絕對限期（dl_deadline加上當前時間）
????...
????struct?hrtimer?dl_timer;?//?高精度定時器，用來實現(xiàn)任務的周期調(diào)度
};

下面介紹一下?sched_dl_entity?結(jié)構(gòu)各個字段的作用：

rb_node：紅黑樹節(jié)點，用來將任務添加到 Deadline 運行隊列中。

dl_runtime：任務能夠運行的時間。

dl_deadline：任務的相對限期。

dl_period：任務的調(diào)度周期。

runtime：任務的剩余運行時間。

deadline：任務的絕對限期（dl_deadline 字段加上當前時間）。

dl_timer：高精度定時器，用來實現(xiàn)任務的周期性調(diào)度。

2. 實現(xiàn)邏輯

Deadline 調(diào)度器實現(xiàn)了兩種調(diào)度算法：

EDF，Early deadline first。

CBS，Constant bindwidth server。

下面我們來介紹一下 EDF 算法的實現(xiàn)。

所謂EDF，即 deadline 最早到期的任務優(yōu)先得到調(diào)度。在 EDF 算法實現(xiàn)中，調(diào)度器會通過紅黑樹來存儲系統(tǒng)中的實時任務，而紅黑樹的鍵就是任務的 deadline，如圖 3 所示。

Deadline 調(diào)度器通過調(diào)用?enqueue_dl_entity()?函數(shù)來將一個實時任務添加到運行隊列中，而?enqueue_dl_entity()?函數(shù)最終會調(diào)用?__enqueue_dl_entity()?函數(shù)來實現(xiàn)將任務添加到隊列中。

我們來看看?__enqueue_dl_entity()?函數(shù)的實現(xiàn)：

static?void?__enqueue_dl_entity(struct?sched_dl_entity?*dl_se)
{
????struct?dl_rq?*dl_rq?=?dl_rq_of_se(dl_se);
????struct?rb_node?**link?=?&dl_rq->rb_root.rb_node;
????struct?rb_node?*parent?=?NULL;
????struct?sched_dl_entity?*entry;
????int?leftmost?=?1;

????//?1.?通過任務的deadline，找到其在運行隊列紅黑樹中的位置
????while?(*link)?{
????????parent?=?*link;
????????entry?=?rb_entry(parent,?struct?sched_dl_entity,?rb_node);

????????if?(dl_time_before(dl_se->deadline,?entry->deadline))
????????????link?=?&parent->rb_left;
????????else?{
????????????link?=?&parent->rb_right;
????????????leftmost?=?0;
????????}
????}

????//?2.?如果當前任務是隊列中deadline最早到期的，那么緩存到運行隊列的rb_leftmost字段中
????if?(leftmost)
????????dl_rq->rb_leftmost?=?&dl_se->rb_node;

????//?3.?將任務添加到運行隊列的紅黑樹中
????rb_link_node(&dl_se->rb_node,?parent,?link);
????rb_insert_color(&dl_se->rb_node,?&dl_rq->rb_root);

????//?4.?增加運行隊列的任務數(shù)
????inc_dl_tasks(dl_se,?dl_rq);
}

從上面代碼可以看到，當把一個實時任務添加到運行隊列的紅黑樹中時，是根據(jù)該任務的 deadline 來找到其在紅黑樹中的相應位置，然后添加到運行隊列的紅黑樹中。任務添加成功后，會增加運行隊列的任務計數(shù)器。

當進行任務切換時，Deadline 調(diào)度器選擇紅黑樹最左面的節(jié)點進行調(diào)度，其通過?pick_next_task_dl()?函數(shù)來實現(xiàn)，代碼如下：

struct?task_struct?*
pick_next_task_dl(struct?rq?*rq,?struct?task_struct?*prev)
{
????struct?sched_dl_entity?*dl_se;
????struct?task_struct?*p;
????struct?dl_rq?*dl_rq;

????dl_rq?=?&rq->dl;
????...
????//?1.?找到?deadline?最早到期的調(diào)度實體
????dl_se?=?pick_next_dl_entity(rq,?dl_rq);
????//?2.?獲取改調(diào)度實體對應的任務
????p?=?dl_task_of(dl_se);
????...
????//?3.?返回?deadline?最早到期的任務
????return?p;
}

pick_next_task_dl()?函數(shù)通過取得運行隊列紅黑樹的最左邊的節(jié)點，并返回該節(jié)點上對應的任務。

那么 Deadline 調(diào)度器是怎么保證每個任務都能在其調(diào)度周期內(nèi)執(zhí)行呢？

每個任務都有一個高精度定時器（sched_dl_entity?結(jié)構(gòu)的?dl_timer?字段），其超時時間為任務的調(diào)度周期。當定時器觸發(fā)時，便會調(diào)用?dl_task_timer()?函數(shù)來處理定時器事件。我們來看看?dl_task_timer()?函數(shù)的實現(xiàn)：

static?enum?hrtimer_restart?dl_task_timer(struct?hrtimer?*timer)
{
????struct?sched_dl_entity?*dl_se?=?container_of(timer,?struct?sched_dl_entity,?dl_timer);
????struct?task_struct?*p?=?dl_task_of(dl_se);
????...
????//?1.?將任務添加到運行隊列中
????enqueue_task_dl(rq,?p,?ENQUEUE_REPLENISH);
????if?(dl_task(rq->curr))?{
????????check_preempt_curr_dl(rq,?p,?0);
????}?else?{
????????//?2.?進行進程調(diào)度
????????resched_curr(rq);
????}
????...
}

dl_task_timer()?函數(shù)的主要完成以下兩個步驟：

將任務重新添加到 Deadline 調(diào)度器的運行隊列中。

進行進程調(diào)度（在中斷返回時）。

?

?