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

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

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

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

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

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

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

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

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

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

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

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

（圖1）

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

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

?

?

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

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

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

（圖2）

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

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

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

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

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

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

（圖3）

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

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

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

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

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

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

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

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

dl_runtime：任務(wù)能夠運行的時間。

dl_deadline：任務(wù)的相對限期。

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

runtime：任務(wù)的剩余運行時間。

deadline：任務(wù)的絕對限期（dl_deadline 字段加上當(dāng)前時間）。

dl_timer：高精度定時器，用來實現(xiàn)任務(wù)的周期性調(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 最早到期的任務(wù)優(yōu)先得到調(diào)度。在 EDF 算法實現(xiàn)中，調(diào)度器會通過紅黑樹來存儲系統(tǒng)中的實時任務(wù)，而紅黑樹的鍵就是任務(wù)的 deadline，如圖 3 所示。

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

我們來看看?__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.?通過任務(wù)的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.?如果當(dāng)前任務(wù)是隊列中deadline最早到期的，那么緩存到運行隊列的rb_leftmost字段中
????if?(leftmost)
????????dl_rq->rb_leftmost?=?&dl_se->rb_node;

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

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

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

當(dāng)進行任務(wù)切換時，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)度實體對應(yīng)的任務(wù)
????p?=?dl_task_of(dl_se);
????...
????//?3.?返回?deadline?最早到期的任務(wù)
????return?p;
}

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

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

每個任務(wù)都有一個高精度定時器（sched_dl_entity?結(jié)構(gòu)的?dl_timer?字段），其超時時間為任務(wù)的調(diào)度周期。當(dāng)定時器觸發(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.?將任務(wù)添加到運行隊列中
????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ù)的主要完成以下兩個步驟：

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

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

?

?