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

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

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

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

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

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

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

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

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

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

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

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

（圖1）

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

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

?

?

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

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

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

（圖2）

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

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

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

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

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

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

（圖3）

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

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

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

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

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

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

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

rb_node：紅黑樹節(jié)點(diǎn)，用來(lái)將任務(wù)添加到 Deadline 運(yùn)行隊(duì)列中。

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

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

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

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

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

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

2. 實(shí)現(xiàn)邏輯

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

EDF，Early deadline first。

CBS，Constant bindwidth server。

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

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

Deadline 調(diào)度器通過(guò)調(diào)用?enqueue_dl_entity()?函數(shù)來(lái)將一個(gè)實(shí)時(shí)任務(wù)添加到運(yùn)行隊(duì)列中，而?enqueue_dl_entity()?函數(shù)最終會(huì)調(diào)用?__enqueue_dl_entity()?函數(shù)來(lái)實(shí)現(xiàn)將任務(wù)添加到隊(duì)列中。

我們來(lái)看看?__enqueue_dl_entity()?函數(shù)的實(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.?通過(guò)任務(wù)的deadline，找到其在運(yùn)行隊(duì)列紅黑樹中的位置
????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ù)是隊(duì)列中deadline最早到期的，那么緩存到運(yùn)行隊(duì)列的rb_leftmost字段中
????if?(leftmost)
????????dl_rq->rb_leftmost?=?&dl_se->rb_node;

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

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

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

當(dāng)進(jìn)行任務(wù)切換時(shí)，Deadline 調(diào)度器選擇紅黑樹最左面的節(jié)點(diǎn)進(jìn)行調(diào)度，其通過(guò)?pick_next_task_dl()?函數(shù)來(lái)實(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)度實(shí)體
????dl_se?=?pick_next_dl_entity(rq,?dl_rq);
????//?2.?獲取改調(diào)度實(shí)體對(duì)應(yīng)的任務(wù)
????p?=?dl_task_of(dl_se);
????...
????//?3.?返回?deadline?最早到期的任務(wù)
????return?p;
}

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

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

每個(gè)任務(wù)都有一個(gè)高精度定時(shí)器（sched_dl_entity?結(jié)構(gòu)的?dl_timer?字段），其超時(shí)時(shí)間為任務(wù)的調(diào)度周期。當(dāng)定時(shí)器觸發(fā)時(shí)，便會(huì)調(diào)用?dl_task_timer()?函數(shù)來(lái)處理定時(shí)器事件。我們來(lái)看看?dl_task_timer()?函數(shù)的實(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ù)添加到運(yùn)行隊(duì)列中
????enqueue_task_dl(rq,?p,?ENQUEUE_REPLENISH);
????if?(dl_task(rq->curr))?{
????????check_preempt_curr_dl(rq,?p,?0);
????}?else?{
????????//?2.?進(jìn)行進(jìn)程調(diào)度
????????resched_curr(rq);
????}
????...
}

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

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

進(jìn)行進(jìn)程調(diào)度（在中斷返回時(shí)）。

?

?