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

本文主要介紹 Linux 的 Deadline 實時調度算法。

什么是實時操作系統

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

Deadline 調度算法原理

我們先來介紹一下 Deadline 調度算法的原理。

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

Deadline 調度器定義了三個元素：

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

runtime：每周期內的運行時間，即該任務在該調度周期內至少能夠運行的時間。

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

這三個元素的關系可以見下圖：

（圖1）

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

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

?

?

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

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

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

（圖2）

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

Deadline 調度算法實現

1. 關鍵數據結構

在 Linux 內核中，每種調度器都會定義一個運行隊列來存儲系統中的任務（進程）。Deadline 調度器則通過?dl_rq?結構來描述這個運行隊列，其定義如下：

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

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

（圖3）

上圖中的數字就是任務的 deadline。

Linux 內核通過?sched_dl_entity?結構體來描述一個實時任務，其中的?deadline?字段則表示任務的 deadline。

我們來看看?sched_dl_entity?結構的定義：

struct?sched_dl_entity?{
????struct?rb_node?rb_node;??//?紅黑樹節點

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

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

下面介紹一下?sched_dl_entity?結構各個字段的作用：

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

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

dl_deadline：任務的相對限期。

dl_period：任務的調度周期。

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

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

dl_timer：高精度定時器，用來實現任務的周期性調度。

2. 實現邏輯

Deadline 調度器實現了兩種調度算法：

EDF，Early deadline first。

CBS，Constant bindwidth server。

下面我們來介紹一下 EDF 算法的實現。

所謂EDF，即 deadline 最早到期的任務優先得到調度。在 EDF 算法實現中，調度器會通過紅黑樹來存儲系統中的實時任務，而紅黑樹的鍵就是任務的 deadline，如圖 3 所示。

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

我們來看看?__enqueue_dl_entity()?函數的實現：

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.?增加運行隊列的任務數
????inc_dl_tasks(dl_se,?dl_rq);
}

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

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

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?最早到期的調度實體
????dl_se?=?pick_next_dl_entity(rq,?dl_rq);
????//?2.?獲取改調度實體對應的任務
????p?=?dl_task_of(dl_se);
????...
????//?3.?返回?deadline?最早到期的任務
????return?p;
}

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

那么 Deadline 調度器是怎么保證每個任務都能在其調度周期內執行呢？

每個任務都有一個高精度定時器（sched_dl_entity?結構的?dl_timer?字段），其超時時間為任務的調度周期。當定時器觸發時，便會調用?dl_task_timer()?函數來處理定時器事件。我們來看看?dl_task_timer()?函數的實現：

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.?進行進程調度
????????resched_curr(rq);
????}
????...
}

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

將任務重新添加到 Deadline 調度器的運行隊列中。

進行進程調度（在中斷返回時）。

?

?