# Linux 核心專題: CPU 排程器之理論基礎
> 執行人: salmoniscute
> [專題解說錄影](https://www.youtube.com/live/Ae0jVIDCycU?si=A_fDISbU_vyK8Bm3&t=423)

### Reviewed by `EricccTaiwan`
> 下方問題於[2024 年 Linux 核心設計/實作課程期末展示(上)](https://youtu.be/kwYgfkD1dWA?t=1666)有同學發問、老師也有對此回應，可以作為參考!
1. 當兩個任務的 $vruntime$ 完全一致時，CFS 會採用什麼機制來決定下一個執行任務？同樣情況下，EEVDF 又如何處理？（我推測可能回退至 Round-Robin 的方式輪替執行）
2. 若核心確實回退至 Round-Robin，Linux 核心中可從哪些函式或程式區段驗證這項行為？
>[name=salmoniscute]
> 以下用核心原始碼的行為統一回答兩個問題（CFS 參考 `v4.4`，EEVDF 參考 `v6.12`）
> CFS：
> ```c
> static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
> {
> /*
> * Find the right place in the rbtree:
> */
> while (*link) {
> parent = *link;
> entry = rb_entry(parent, struct sched_entity, run_node);
> /*
> * We dont care about collisions. Nodes with
> * the same key stay together.
> */
> // se 的 vruntime < entry 的 vruntime
> if (entity_before(se, entry)) {
> link = &parent->rb_left;
> } else { // se 的 vruntime >= entry 的 vruntime
> link = &parent->rb_right;
> leftmost = 0;
> }
> }
> ...
> ```
> Tie-breaking 比較邏輯：
> ```c
> static inline int entity_before(struct sched_entity *a,
> struct sched_entity *b)
> {
> return (s64)(a->vruntime - b->vruntime) < 0;
> }
> ```
> 首先看到 `__enqueue_entity` 函式，觀察 CFS 把任務放到樹中的行為。當待插入的任務 `se` 其 `vruntime` 跟目前走訪到的節點任務之 `vruntime` 相同時，會把新任務 `se` 插入到 `entry` 的右邊子樹，代表後插入的任務會被排在後面。
> CFS 是選擇 `vruntime` 最小的任務來執行，所以當兩個任務的 `vruntime` 一樣時，CFS 確實會回退到類似 RR 的行為，按照任務的插入順序（FIFO）來決定排程的順序。
>
> EEVDF：
> 至於 EEVDF 的紅黑樹的 key 並不是以 `vruntime` 排序了，而是改成 virtual deadline，所以我假設你想問的是兩個任務都變為合格且他們的 virtual deadline 相同的話 CPU 排程器會怎麼選：
> ```c
> static inline bool entity_before(const struct sched_entity *a,
> const struct sched_entity *b)
>{
> /*
> * Tiebreak on vruntime seems unnecessary since it can
> * hardly happen.
> */
> return (s64)(a->deadline - b->deadline) < 0;
>}
> ```
> EEVDF 跟 CFS 行為類似，當兩個任務的 virtual deadline 一樣時，按照任務的插入順序（FIFO）來決定排程的順序。相同 deadline 的任務按插入順序排列在樹中，`pick_eevdf` 函式會選擇最左邊的 eligible 任務，最左邊的任務也代表較早插入的任務。

### Reviewed by `charliechiou`

1. EEVDF 相比 CFS 有不足之處嗎 ? 或是其完整保持了 CFS 所有優點且進一步改善 ?
2. 若要觀察 CFS 及 EEVDF 兩者的差異，應該比較哪些表現比較能看出 EEVDF 的提升 ?
(類似如果是 EEVDF 開發者要說服社群接受該改進，應該提出何種數據佐證 ? )
>[name=salmoniscute]
> 1. EEVDF 不論是演算法或是實作上，都相比於 CFS 多帶了 request length 的參數，CPU 排程器不單單像 CFS 只有 `nice`，也就是 `weight` 參數來作為 fairness 判斷的指標。而 request length （`time_slice`）本身就帶有隱含的急迫性概念，任務請求的 CPU 執行時間越短，算出的虛擬截止時間自然越近，根據 EEVDF 的演算法，此任務自然也更有機會被 CPU 排程器選中來執行。
> EEVDF 在 CFS fairness 的基礎上，擴充了任務 responsive 的需求，並且根據證明出來的延遲上下界以及更直接反應 fairness 的指標 $lag$，提供比 CFS 的比例分配方式更為嚴格的 fairness。
> 2. 以下列出幾個在開發者的 patch series 中，常常作為 CPU 排程器演進依據的測試 [benchmark](https://lore.kernel.org/lkml/[e-mail]/T/)，也可參考[學長筆記](https://hackmd.io/@sysprog/H1Eh3clIp)：
> * schbench：測量 wakeup latency。創建多個 worker thread，測量從喚醒到實際執行的延遲時間，重點關注 95% tail latency。
> * hackbench：throughput 測試。建立大量 process 或 thread，測量完成所有任務的總時間。
> * stress-ng：系統壓力測試。
> * unixbench：在傳統 Unix 環境的效能。
> * netperf：測試網路 I/O 密集型環境下的排程效能。

### Reviewed by `yy214123`
在專題講解影片 [3:21](https://www.youtube.com/live/Ae0jVIDCycU?t=423s) 提到的 `latency-nice`，這項機制引入後對於後期的 CFS 有甚麼重大影響嗎?
>[name=salmoniscute]
> 因為 CFS 原本只有 `nice`（對應到權重）來調整 CPU 資源的分配比例，對於 latency 的沒有直接的控制方法。`latency-nice` 引入後，開發者或系統可以指定任務對延遲的偏好，這不影響用 `nice` 計算出來的 CPU 佔比，但會影響像是任務在 runqueue 中的相對排序等等機制。可以想成 CFS 試圖以 `nice` 控制 throughput，`latency-nice` 控制 latency。關於 `latency-nice` 更詳細的發展過程可以去看看這份筆記：[Target latency 相關研究](https://hackmd.io/@salmonii/SJGiekyVgg)

### Reviewed by `horseface1110`
>透過 $r = S(t, d)$ ，可以在理想系統中求出該任務應在時間 $d$ 之前完成所要求的服務時間。假設任務的分配比例 $f$ 在時間區間 $[t, d)$ 內不變，則可得：
$$S(t, d) = f (d - t)$$
移項得到：
$$d = t + r/f$$

這裡的$f$是一個數值還是一個函數？為什麼第一個式子中$f$像是函數，但第二個又是放在分母的數值
>[name=salmoniscute]
> 很抱歉這裡是我偷懶沒打乘法運算符號造成的誤會，已修正，謝謝。

## 任務簡述
修訂《Demystifying the Linux CPU Scheduler》並探究 CFS/EEVDF 背後的理論基礎，包含 fairness, proportional share scheduler, bandwidth control, EEVDF 的 target latency 等議題，適度貢獻回電子書。

## TODO: 修訂電子書
> 研讀《Demystifying the Linux CPU Scheduler》、紀錄問題並提交修正修訂針對用語和敘述。列出提交並收錄的 pull request

[#265 ](https://github.com/sysprog21/linux-kernel-scheduler-internals/pull/265)
[#266](https://github.com/sysprog21/linux-kernel-scheduler-internals/pull/266)
[#267](https://github.com/sysprog21/linux-kernel-scheduler-internals/pull/267)
[#286](https://github.com/sysprog21/linux-kernel-scheduler-internals/pull/286)

## TODO: 重新審視 GPS
> 探究 Generalized Processor-shareing (GPS) model，搭配論文和課程討論

[學習 GPS](https://hackmd.io/@salmonii/HJSvKVOlle)

:::danger
展開上方筆記到此頁面
:::

## TODO: 理解 CFS 到 EEVDF 的轉變
> 從著重 fairness 到 target latency，討論核心開發者的考量，搭配閱讀對應的論文，並整理課程討論

[EEVDF 論文研讀](https://hackmd.io/@salmonii/eevdf_paper)
[WIP: EEVDF 理論實作比較](https://hackmd.io/@salmonii/ryRHMZgMlg)
[WIP: 理解 CFS 到 EEVDF](https://hackmd.io/@salmonii/SJudgzSmxx)
[WIP: target latency 相關研究](https://hackmd.io/@salmonii/SJGiekyVgg)

## [EEVDF 論文](https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=805acf7726282721504c8f00575d91ebfd750564)研讀

### 引言

* proportional share
更有彈性，並且在系統過載的情況下能夠提供 graceful degradation，也就是說即使資源不足，所有客戶端仍然能獲得一定比例的資源，避免部分任務完全無法執行。
* real-time based
即時排程器可以保證所有被接受的事件都能在他的截止時間之前完成處理。

#### EEVDF
在保留 proportional share 排程器所有優點的同時，為客戶端接收到的服務時間提供及時性的保證。代表 EEVDF 既要像 proportional share 排程器一樣靈活的分配資源，又要像 real-time 排程器一樣確保對時間較為敏感的應用程式的需求。

> In part, the algorithm builds on ideas found in previous network fair-queueing algorithms, and general-purpose proportional share allocation algorithms.

虛擬時間（virtual time）的概念，用在模擬在一個理想的流體流模型（fluid-flow based system）中的工作進度。fluid-flow model 是一種理想化的模型，假設資源可以以無限小的單位連續的分配，可以作為實際離散資源分配的參考。

> A request is said to be eligible if its virtual eligible time is less than or equal to the current virtual time.

> The algorithm simply allocates a new time quantum to the client that has the eligible request with the earliest virtual deadline.

> We note that while the concept of virtual deadline is also employed by other proportional-share algorithms, the concept of eligible time is a unique feature of our algorithm.

### 模擬理想模型以及假設
因為主要探討 CPU 排程器，論文中的 「client」 我都會改成「任務」，更直接對應。但要注意到的是本篇論文所指的「資源」是通用於不論是 CPU 資源還是網路世界中的 communication bandwidth 。 EEVDF 是不限於 CPU 排程器的。
> 參照 [jserv 的筆記](https://hackmd.io/uiNwM35dQ6qeFQwfTypc_w)

對於一組競爭同一個時間共享資源的任務，資源是以 time quanta 為單位進行分配，每個 time quanta 的最大長度為 $q$。代表資源的分配是離散的，而不是連續的。在每個時間量開始時，會選擇一個任務來使用資源。一旦任務獲得了資源，它可以一直使用到該時間量結束，也可以在時間量結束之前主動釋放資源。（ preempt 的概念）

每個任務都會有對應一個權重，這個權重決定了它應該獲得的資源的相對比例。資源的分配是透過任務的權重與所有 active 任務權重總和的比值來計算的。（跟 GPS 中的 backlogged session 很像）

假設 $w_i$ 對應到任務 $i$ 的權重，$\mathcal{A}(t)$ 代表在時間 $t$ 所有活躍任務的集合。
以下定義了在時間 $t$ 任務 $i$ 的資源分配 $f_i(t)$：

$$
f_i(t) = \frac{w_i}{\sum_{j \in \mathcal{A}(t)} w_j}
$$

相應的在時間區間 $[t_0, t_1]$ 內，任務 $i$ 應獲得的理想累積服務時間 $S_i(t_0, t_1)$ 即為 $f_i(t)$ 在該區間的積分：
$$
S_i(t_0, t_1) = \int_{t_0}^{t_1} f_i(\tau) \, d\tau
$$

上述公式對應一個理想的 fluid model，在這個系統中，資源可以用很小且任意的時間間隔進行分配。在離散時間模型中，這相當於時間量的大小 $q$ 趨近於零的情況。

但是在許多實際情況下，時間量的大小不能無限小。一個主要原因是排程的演算法本身以及從一個任務切換到另一個任務（context switch）所帶來的開銷。另一個原因像是網路中一旦開始為一個 session 發送封包，就必須等到整個封包發送完畢後才能服務其他 session。代表時間量的最小粒度受到不可中斷操作的限制。

在 CPU 排程器中主要是成本的問題，不可能花費大量 CPU 資源隨時做統計，排程的週期（ time quanta $q$ ）
* 太大 $\to$ RR 退化成 FIFO
* 太小 $\to$ 浪費 CPU 資源

由於資源是以離散的時間量進行分配的，因此任務不可能總是很精確的獲得其應得的服務時間。這是時間量化所帶來的必然結果。

假設任務 $i$ 在時間 $t^i_0$ 變為活躍，並且在整個時間間隔 $[t^i_0,t]$ 內都保持活躍，它在該時間間隔內實際接收到的服務時間是 $s_i(t^i_0, t)$。那麼任務 $i$ 在時間 $t$ 的應該接收到的服務時間與實際接收到的服務時間之間的差值可以用以下公式表示：

$$
\operatorname{lag}_i(t^i_0, t) = S_i(t^i_0, t) - s_i(t^i_0, t)
$$

> 若 $\operatorname{lag}_i > 0$，任務 $i$ 服務滯後；若 $\operatorname{lag}_i < 0$，則服務超前。Lag 是衡量 fairness 的重要指標，並與任務延遲特性密切相關。排程演算法致力於將 lag 控制在小且有界的範圍內。

論文中強調 $lag$ 是衡量比例資源分配演算法性能的關鍵指標，因為它直接關係到系統的 fairness 和 predictability 。

這句話我讀到目前還沒有太大的感覺，尤其是 predictability 的部分，還會繼續研讀。

### 演算法前導說明
結合上述提及的兩個式子，資源分配比例以及理想服務時間：

$$
f_i(t) = \frac{w_i}{\sum_{j \in \mathcal{A}(t)} w_j}
$$

$$
S_i(t_0, t_1) = \int_{t_0}^{t_1} f_i(\tau) \, d\tau
$$

得出活躍任務 $i$ 在時間間隔 $[ t_0,t_1 )$ 內理想上應該要得到的服務時間：

$$
S_i(t_0, t_1) = w_i \int_{t_0}^{t_1} \dfrac{1}{\sum_{j \in \mathcal{A}(\tau)} w_j} \, d\tau
$$

每一個時刻 $τ$，任務 $i$ 拿到的 Cpu 速率是它的權重占比：
$$ \dfrac{w_i}{\sum_{j \in \mathcal{A}(\tau)} w_j}$$
所以總服務時間 $S_i(t_0, t_1)$ 就是把這個速率對時間積分。

#### request 是什麼？

為了獲得 cpu 資源的使用權，任務必須發出指定所需服務時間長度的請求。當任務的請求完成後，可以發出新的請求，或者變為不活躍狀態（ passive ）。可以進一步定義：只要任務有待處理的請求，就視為活躍狀態（ active ），否則，視為不活躍狀態。

在EEVDF 中，每個請求在被任務發起時會帶有幾個參數：
* 發起時間 $t$
* 所需的服務時間 $r$

透過 $r = S(t, d)$ ，可以在理想系統中求出該任務應在時間 $d$ 之前完成所要求的服務時間。假設任務的分配比例 $f$ 在時間區間 $[t, d)$ 內不變，則可得：
$$S(t, d) = f * (d - t)$$
移項得到：
$$d = t + r/f$$

> 但是不可能不變，不可能推算出實際時間 $\to$ 所以有了虛擬時間的計算方法，後續會說明
所以更精確來講，其實請求算的是 $ve$、$vd$（虛擬時間軸）

#### eligible time 是什麼意思？

一個活躍任務所發出的請求在時間 $e$ 變為 eligible 。要找到一個時間點 $e$，讓任務在理想 GPS 模型下應得的服務時間 $S_i(t^i_0,e)$ 剛好等於此任務目前實際已經獲得的服務 $s_i(t^i_0,t)$。

>複習 $\operatorname{lag}$ 通則：
$$
\operatorname{lag}_i(t^i_0, t) = S_i(t^i_0, t) - s_i(t^i_0, t)
$$
從任務 $i$ 開始變成活躍狀態的時間 $t^i_0$ 到目前時間 $t$ 為止，此任務在理想世界中應該得到的服務量減去實際世界中它得到的服務量。此差值定義為 $\operatorname{lag}$，用來衡量任務 $i$ 在某一個時間點 $t$ 的落後情況。

$$S_i(t^i_0,e) = s_i(t^i_0,t)$$

也就是把理想時間拉到 $e$，實際時間定在 $t$。

在 GPS 模型中，到了時間 $e$ 時，任務應該剛好得到它在現實世界中，到請求時間 $t$ 為止所得到的服務量，這樣才能達到公平。
為了模擬這樣的理想情況，如果任務在現實中已經領先了，那它所發出的請求就不應該馬上 eligible，而要等到時間走到 $e$。換句話說，當任務在理想模型中的進度趕上其實際進度時，再讓新的請求進入系統，任務得以被排程。

實際舉例說明，假設在實際時間 $t$ 時 $\operatorname{lag}$ 為正（落後）
$$
\operatorname{lag}_i(t^i_0, t) = S_i(t^i_0, t) - s_i(t^i_0, t) > 0
$$
可以推導出：
$$S_i(t^i_0, t) > s_i(t^i_0, t)$$

這時候要試圖找出滿足 $S_i(t^i_0,e) = s_i(t^i_0,t)$ 的 $e$ 點，讓任務的實際服務量追上理想應得的。因此要符合：
$$S_i(t^i_0, t) > S_i(t^i_0, e)$$

已知 $S_i(t^i_0, t)$ 會是遞增函數。所以一定會是找到 $e<t$。

理解為當 $\operatorname{lag}$ 為正時，任務已經落後於其在理想模型中的進度。計算出的 eligible time $e$ 會小於目前時間 $t$，這表示如果該請求在理想模型中發生，它在過去的時間點 $e$ 就應該已經開始被處理了。因此，在實際系統中，這個請求一發出就立即變為 eligible，允許它有機會被排程以減少 $\operatorname{lag}$。

在 $\operatorname{lag} = 0$ 成立之外會有兩種情況：
1. 任務超前進度 $\operatorname{lag} < 0$
$e>t$，任務 $i$ 實際拿得比他理想上該拿的還多，為了公平，必須 delay 它發出的新請求直到時間 $e$
> In this way a client that has received more service time than its share is "slowed down", while giving the other active clients the opportunity to "catch up"
2. 任務落後進度 $\operatorname{lag} > 0$
$e<t$，任務 $i$ 被服務得太少，對它的新請求應該馬上可以排程

#### 為什麼要 virtual ?

如果任務超前進度的狀況發生，代表要找到一個 $e$ 使得 $e > t$，但是不可能從實際時間 $t$ 算出未來的實際時間 $e$ ，論文中給出的例子是空水庫和注水去水庫的泉水。就像只能去判斷說水庫的水滿會是在某個時刻，但不能算出實際的那一刻，因為在未來泉水的流速流量都是有可能會浮動的。

因此 EEVDF 演算法使用虛擬時間的概念，目的在離散時間系統中模擬理想流體模型的公平性，同時避免了計算未來實際時間點的困難。以下說明：

首先定義 system virtual time ，一個抽象虛擬的時間軸：

$$
V(t) = \int_{0}^{t} \dfrac{1}{\sum_{j \in \mathcal{A}(\tau)} w_j} \, d\tau
$$

$V(t)$ 是實際時間 $t$ 時的虛擬時間。 EEVDF 會維護一個全局的虛擬時間 $V(t)$ 。

可以看到虛擬時間的增長率與所有活躍任務的權重之和成反比。這代表當競爭加劇時（更多任務或更高權重），虛擬時間的流逝會變慢，而當競爭減少時，虛擬時間的流逝會加快。

虛擬時間的流逝速度會自動調整，以便在一個虛擬時間單位內可以「容納」所有活躍任務。也就是說，在相應的 ideal fluid model 中，把虛擬時間想成一個公平的單位時間刻度。在每個虛擬時間單位裡，任務 $i$ 按照自己的權重，應該得到 $w_i$ 單位的實際服務時間。

舉例來說，假設有兩個任務，權重分別是 $w_1 = 2$ , $w_2 = 3$，虛擬時間增長的速率是 $\dfrac{1}{(w₁+w₂)}=0.2$，代表實際時間每流逝五個單位，虛擬時間就會流逝一個單位，在每個虛擬時間單位中，兩個任務會分別獲得 $w_1=2$ 和 $w_2=3$ 個實際時間單位。

任務 $i$ 在時間間隔 $[ t_0,t_1 )$ 內應得的服務時間 $S_i(t_0,t_1)$ 等於其權重 $w_i$ 乘以該時間間隔內虛擬時間的增量。

$$
S_i(t_0,t_1 )=w_i*(V(t_1)−V(t_0))
$$

> 複習：
$$V(t_1)−V(t_0) = \int_{t_0}^{t_1} \dfrac{1}{\sum_{j \in \mathcal{A}(\tau)} w_j} \, d\tau$$
>
>$$
S_i(t_0, t_1) = w_i \int_{t_0}^{t_1} \dfrac{1}{\sum_{j \in \mathcal{A}(\tau)} w_j} \, d\tau
$$

如果更進一步假設所有活躍任務的總權重為 $1$，那虛擬時間就與實際時間同步消逝（每單位實際時間，虛擬時間也前進 $1$ 單位）。此時：

$$
\sum_{i \in \mathcal{A}} w_i = 1
$$

在這種情況下，任務 $i$ 的分配額 $f_i$ 就等於其權重 $w_i$，在時間間隔 $[ t_0,t_1 )$ 內，任務 $i$ 應得的服務時間就簡化為：

$$
S_i(t_0,t_1 )=w_i*(t_1−t_0)
$$

---

任務 $i$ 在實際時間 $t$ 發出請求。根據目前任務收到的服務量 $s_i(t^i_0,t)$，推算出虛擬時間中它何時可以開始再被服務 $V(e)$：

首先計算理想系統中的服務時間：

$$
S_i(t^i_0,e)=w_i*(V(e)−V(t^i_0))
$$

帶入：
$$S_i(t^i_0, e) = s_i(t^i_0, t)$$

代表在 $V(e)$ 時刻，理想系統中應得的服務時間等於實際已獲得的服務時間，即 $\operatorname{lag} = 0$

得到：
$$
w_i*(V(e)−V(t^i_0)) = s_i(t^i_0, t)
$$

移項後得到：
$$V(e) = V(t^i_0) + \dfrac{s_i(t^i_0,t)}{w_i}$$

Virtual Eligible Time $V(e)$ 的計算基於公平性原則，表示在理想系統中，任務 $i$ 的累積延遲剛好為零的虛擬時間點。

當任務 $i$ 在時間 $t$ 發起新請求時，已經累積獲得了 $s_i(t^i_0, t)$ 單位的實際服務時間。在理想流體模型中，任務 $i$ 每單位的虛擬時間能獲得 $w_i$ 單位的實際服務時間。因此在理想流體模型中，這相當於消耗了 $\dfrac{s_i(t^i_0,t)}{w_i}$ 單位的虛擬時間。於是從任務開始活躍的虛擬時間點 $V(t^i_0)$ 出發，加上這個已消耗的虛擬時間量，得到最終的虛擬 eligible 時間 $V(e)$。

$V(e)$ 的意義是確保公平性，新請求只有在系統虛擬時間達到 $V(e)$ 時才符合排程條件，這樣可以防止某個任務連續獲得過多服務而造成其他任務延遲過大。

確定了請求的虛擬合格時間 $V(e)$ 後，接下來需要推算虛擬截止時間 $V(d)$，使得在理想流體模型中，任務 $i$ 在時間區間 $[ e, d ]$ 內恰好接收 $r$ 單位的服務（請求的長度是 $r$ ），根據同樣的原則：

$$S_i(e,d) = r$$

$$r = w_i*(V(d)−V(e))$$
移項後得到：

$$V(d) = V(e) + \dfrac{r}{w_i}$$

>複習：
$$d = t + r/f$$

---

接下來計算請求發起時間 $t$ 的 $\operatorname{lag}$，注意到這個不是通則，通則是最一開始介紹到的理想服務時間減去實際服務時間。

從虛擬合格時間的定義：
$$s_i(t^i_0, t) = w_i*(V(e) - V(t^i_0))$$
代入：
$$\operatorname{lag}_i(t) = w_i*(V(t) - V(t^i_0)) - s_i(t^i_0, t)$$
得到：
$$\operatorname{lag}_i(t) = w_i*(V(t) - V(t^i_0)) - w_i*(V(e) - V(t^i_0))$$
簡化：
$$\operatorname{lag}_i(t) = w_i*(V(t) - V(e))$$

> 所以比上述 $e > t$ 更為精確的表示方法應該是 $V(e) > V(t)$
虛擬時間是實際物理時間的遞增函數

以下的 $\operatorname{lag}$ 以虛擬時間的角度重新詮釋：
$V(t)$ 代表系統全局目前的虛擬時間，$V(e)$ 指該請求推算出的 eligible virtual time（這個請求應該從虛擬時間 $V(e)$ 開始被服務）

1. 任務超前進度 $\operatorname{lag} < 0$
$V(e) > V(t)$，任務 $i$ 實際拿得比他理想上該拿的還多，為了公平，必須 delay 它發出的新請求直到時間 $V(e)$
2. 任務落後進度 $\operatorname{lag} > 0$
$V(e) < V(t)$，任務 $i$ 被服務得太少，對它的新請求應該馬上可以排程
> 對應到 Lemma 1，Lemma 1 計算的是目前時間 $t$ 的 $\operatorname{lag}$，而目前時間可能已經超過請求發起時間 $t'$。

>todo
確認理解正確
重新編排這個 section，讓他看起來更有一個脈絡

### EEVDF 演算法
根據前面的前導說明，論文給出的 EEVDF 演算法：
* $r_k$ 代表任務 $i$ 所發出的第 $k$ 個請求的長度
* $ve_k$，$vd_k$ 分別代表這個請求的虛擬合格時間還有虛擬截止時間
* $t^i_0$ 一樣代表任務 $i$ 變成活躍狀態的時間

$$ve_1 = V(t^i_0)$$

$$vd_k = ve_k + \dfrac{r_k}{w_i}$$

$$ve_{k+1} = vd_k$$

假設任務的每個請求都完整被執行完畢，下一個請求會根據前一個請求的完成點繼續計算。
$$ve_{k+1} = ve_k + \dfrac{u_k}{w_i}$$

如果任務每個請求都完整執行：
* 累積服務時間 = $r_1 + r_2 + ... + r_k$
* 對應虛擬時間 = $\dfrac{(r_1 + r_2 + ... + r_k)}{w_i}$

因此：
\begin{align*}
V(e) &= V(t_0^i) + \dfrac{(r_1 + r_2 + ... + r_k)}{w_i} \\
&= V(t_0^i) + \dfrac{r_1}{w_i} + \dfrac{r_2}{w_i} + ... + \dfrac{r_k}{w_i} \\
&= ve_1 + \dfrac{r_1}{w_i} + \dfrac{r_2}{w_i} + ... + \dfrac{r_k}{w_i} \\
&= ve_{k+1}
\end{align*}

遞迴的方法讓實作上不需要追蹤整個服務的歷史，每次只需要知道前一個請求的資訊。

如果任務的第 $k$ 次請求只實際使用了 $u_k < r_k$ 的服務時間（可能中斷、提早完成等），那麼下一個請求的虛擬合格時間應該從這裡開始計算。允許任務的請求沒有完整執行，但還是要維持公平，**根據實際用到的服務時間來調整後續請求的時間點**。

EEVDF 排程器會根據請求的 $(ve, vd)$ 值進行排序，優先選擇目前已 eligible 且擁有最早 virtual deadline 的任務執行。

### 在動態系統中如何維持公平性

在理想化流體系統中，動態的操作很簡單，因為在任何時刻，所有活動任務的 $\operatorname{lag}$ 都是 $0$，也就是說每個任務都剛好拿到自己該得的資源。但在實際的系統中，服務時間是以離散的 time quanta $q$ 分配的，使得延遲不再總是為 $0$。

這個部分想要探討以下關於維持公平性的核心問題：

1. 一個有 $\operatorname{lag}$ 的任務（拿多或拿少）如果加入、離開或改變權重，會對其他任務造成什麼影響？
1. 一個有 $\operatorname{lag}$ 的任務離開競爭，之後重新加入時，應該用什麼 $\operatorname{lag}$ 重新加入？

### 問題 1：一個有 $\operatorname{lag}$ 的任務（拿多或拿少）如果加入、離開或改變權重，會對其他任務造成什麼影響？

針對第一個問題，論文中舉例解釋當一個任務離開競爭時，如何維持剩餘任務之間的公平資源分配，如下：

假設系統中有三個任務，在時間 $t_0$ 時開始活躍，而在時間 $t$ 時任務 3 離開競爭。在這個時間區間 $[t_0, t)$ 內，由於活躍任務的數量和它們的分配比例沒有變化，所以虛擬時間的斜率是恆定的，等於 $\dfrac{1}{w_1+w_2+w_3}$。每個任務在時間 $t$ 的 $\operatorname{lag}$ 可以表示為：

$$\operatorname{lag}_i(t) = w_i\dfrac{t-t_0}{w_1+w_2+w_3} - s_i(t_0, t) \quad, \quad i = 1, 2, 3$$

由於 EEVDF 是一個 work-conserving （不浪費 CPU）演算法，所有活躍任務在區間 $[t_0, t)$ 內，總共有 $t - t_0$ 單位的處理器時間被分給三個任務。任務 3 要離開競爭，因此剩下能分配給任務 1 和 2 的服務時間為：
$$t-t_0-s_3(t_0, t)$$

用 $t^+$ 表示任務 3 離開競爭後的時間點，忽略離開操作的開銷，$t^+ → t$。
任務 1 和 任務 2 在時間 $t^+$ 應該接收多少服務時間？
最直觀的方法是將兩個任務接收的整個服務時間按照任務的權重比例分配：
$$S_i(t_0 , t^+) = (t-t_0-s_3(t_0, t))\dfrac{w_i}{w_1+w_2} \quad, \quad i = 1, 2$$

這是不夠精確的定義，因為它沒有考慮到任務 3 可能 $\operatorname{lag}$ 的影響。

#### 修正後的服務時間分配

如果 $\operatorname{lag}_3(t) \neq 0$，任務 3 離開後，剩餘的兩個任務應該按比例承擔可能的 loss 或 gain。因此以下重新定義 $S_i(t_0 , t^+)$：
首先已知：

$$\operatorname{lag}_3(t) = w_3\dfrac{t-t_0}{w_1+w_2+w_3} - s_3(t_0, t)$$

移項後：
$$s_3(t_0, t) = w_3\dfrac{t-t_0}{w_1+w_2+w_3} - \operatorname{lag}_3(t)$$

帶入上述公式：

$$S_i(t_0 , t^+) = (t-t_0-(w_3\dfrac{t-t_0}{w_1+w_2+w_3} - \operatorname{lag}_3(t)))\dfrac{w_i}{w_1+w_2} \quad, \quad i = 1, 2$$

簡化後得到：

$$S_i(t_0 , t^+) = (t-t_0)\dfrac{w_i}{w_1+w_2+w_3} + w_i\dfrac{\operatorname{lag}_3(t)}{w_1+w_2} \quad,\quad i = 1, 2$$

根據全局虛擬時間的定義，以及在時間區間 $[t_0, t)$ 內，活躍任務的集合不變，所以：

$$V(t)−V(t_0)=(t-t_0)\dfrac{1}{w_1+w_2+w_3}$$

可以進一步得到：
$$S_i(t_0 , t^+) = w_i*(V(t)-V(t_0)) + w_i\dfrac{\operatorname{lag}_3(t)}{w_1+w_2} \quad,\quad i = 1, 2$$

#### 全局虛擬時間的更新
全局虛擬時間 $V(t)$ 是用來衡量任務在理想公平模型下應該獲得多少服務的基準。一旦某個任務離開，為了讓剩下的任務繼續跟這個公平模型對齊，必須把離開任務造成的「不公平程度」（$\operatorname{lag}$）放回虛擬時間中。從上一個公式可以知道：
$$w_i(V(t^+)-V(t_0)) = w_i*(V(t)-V(t_0)) + w_i\dfrac{\operatorname{lag}_3(t)}{w_1+w_2} \quad,\quad i = 1, 2$$

去掉 $w_i$，並且化簡後：

$$V(t^+) = V(t) + \dfrac{\operatorname{lag}_3(t)}{w_1+w_2} \quad,\quad i = 1, 2$$

這個公式代表當任務 3 離開競爭時，需要根據它的 $\operatorname{lag}$ 來調整全局虛擬時間 $V$。
* 任務 3 落後（$\operatorname{lag}$ > 0）：全局虛擬時間往前推進
* 任務 3 領先（$\operatorname{lag}$ < 0）：代表它多拿了資源，所以虛擬時間要往回退

#### 每個剩下任務 $\operatorname{lag}$ 的更新
全局虛擬時間的更新對應到的就是每個剩下任務 $\operatorname{lag}$ 也會更新，直觀的方式為當任務 3 離開時，它的延遲按比例分配給剩餘的任務。
>複習 $\operatorname{lag}$ 的定義：
$$\begin{aligned}
\operatorname{lag}_i(t^+) &= S_i(t_0, t^+) - s_i(t_0, t^+) \\
&= w_i*(V(t^+)-V(t_0)) - s_i(t_0, t^+)
\end{aligned}$$

由於 $t^+$ 非常接近 $t$，任何任務在 $t^+$ 時接收的服務時間等於它在 $t$ 時接收的服務時間，所以：
$$s_i(t_0, t) = s_i(t_0, t^+)$$

將以上以及虛擬時間更新的公式代入得到：
$$\operatorname{lag}_i(t^+) = w_i*(V(t) + \dfrac{\operatorname{lag}_3(t)}{w_1+w_2}-V(t_0)) - s_i(t_0, t)
$$
展開後：

$$\operatorname{lag}_i(t^+) = w_i*(V(t)-V(t_0)) + w_i\dfrac{\operatorname{lag}_3(t)}{w_1+w_2} - s_i(t_0, t)$$

將第一項與第三項結合成 $\operatorname{lag}_i(t)$：

$$\operatorname{lag}_i(t^+) = \operatorname{lag}_i(t) + w_i\dfrac{\operatorname{lag}_3(t)}{w_1+w_2} \quad , \quad i = 1,2$$

這個公式代表當任務 3 離開競爭時，需要根據它的 $\operatorname{lag}$ 來調整剩餘任務的 $\operatorname{lag}$。
* 任務 3 落後（$\operatorname{lag}$ > 0）：剩餘任務的 $\operatorname{lag}$ 會增加
* 任務 3 領先（$\operatorname{lag}$ < 0）：則剩餘任務的 $\operatorname{lag}$ 會減少

---

以下一起對任務 3 離開競爭之後的全局虛擬時間更新以及任務各自的延遲更新做說明來嘗試理解：

> 複習：
當任務 $i$ 發出一個新請求時，會推算出 $V(e)$。請求只有在 $V(t) \geq V(e)$ 時才會變成 eligible（可被排程器考慮執行）。

在看這個部分花了許多時間理解，但還是不懂

舉例來說，進度落後的任務 3 離開時，它所累積的「虛擬時間債務」（也就是正的 $\operatorname{lag}$）不會消失。為了維持系統的公平性，這個債會被分攤給剩餘的任務。所以全局虛擬時間 $V(t)$ 被往前推，導致剩下的任務在虛擬世界中也落後更多（$\operatorname{lag}$ 變大）。

那這樣 $V(t)$ 增加是代表會比較快走到 $V(e)$，更快變成eligible 嗎？所以當進度落後的任務 3 離開時，剩下的任務會比較有機會被執行到嗎？

> 重新瀏覽發現原本的寫法不夠清楚

所謂的比較快走到 $V(e)$，是指：

* 在任務 3 離開時，因為原本的 $\operatorname{lag}$ 是正的，造成的一個瞬間的跳躍，將虛擬時間 $V(t)$ 基準往前推。對應的公式：

$$V(t) = V(t) + \dfrac{\operatorname{lag}_j(t)}{\sum_{i \in \mathcal{A}(t^+)} w_i}$$

* 當 $\mathcal{A}(t)$ 減少時，分母變小，代表虛擬時間之後的流逝速度會變快。對應的公式：
$$\frac{dV(t)}{dt} = \frac{1}{\sum_{j \in \mathcal{A}(t)} w_j}$$

使得原本不 eligible 的請求更快變成 eligible，剩餘任務更容易獲得執行機會。

#### 全局虛擬時間更新通則
任務 $j$ 在時間 $t$ 離開競爭：
$$V(t) = V(t) + \dfrac{\operatorname{lag}_j(t)}{\sum_{i \in \mathcal{A}(t^+)} w_i}$$

任務 $j$ 在時間 $t$ 加入競爭：
$$V(t) = V(t) - \dfrac{\operatorname{lag}_j(t)}{\sum_{i \in \mathcal{A}(t^+)} w_i}$$

任務 $j$ 在時間 $t$ 把權重從 $w_j$ 改成 $w'_j$：

$$V(t) = V(t) + \dfrac{\operatorname{lag}_j(t)}{(\sum_{i \in \mathcal{A}(t)} w_i) - w_j} - \dfrac{\operatorname{lag}_j(t)}{(\sum_{i \in \mathcal{A}(t)} w_i) - w_j+ w'_j}$$

### 問題 2：一個有 $\operatorname{lag}$ 的任務離開競爭，應該用什麼 $\operatorname{lag}$ 重新加入？

假設有一個 $\operatorname{lag} > 0$ 離開競爭的任務。這個任務在重新加入競爭時是否應該得到補償？

* 如果不給補償：
如果這個任務常常短暫離開，然後回來時都不補償，那它的總服務時間會一直落後，長期下來會拿到遠少於它應該得到的資源。
* 如果給予補償：
這可能會對其他任務造成不好的影響，舉例說明：
假設在時間 $t$ 之前有兩個活躍任務 1 和 2，在時間點 $t$，任務 2 帶著 $\operatorname{lag} > 0$ 變為不活躍。在之後的時間 $t'$，任務 2 重新加入競爭，而此時任務 1 已經不再活躍了，剩下另一個任務 3 是活躍的。
如果幫任務 2 補回它和任務 1 一起活躍時那段沒拿到的服務時間，那這個服務時間只能從現在唯一還在活躍的任務 3 拿來補。任務 3 就只因為它現在在場而被懲罰，這對任務 3 不公平，因為它沒做錯什麼。

這種情況形成了一個兩難困境，不補償可能導致長期不公平，而補償又可能對新任務造成不公平，因此論文作者說這個問題沒有簡單的答案。第五章針對這個問題提出三種策略，每種都對這個問題採取了不同的處理方式，根據系統的具體需求和優先級來選擇合適的策略。

### EEVDF 演算法的公平策略
#### 策略 1
任務們可以在任何時候加入或離開競爭，無論 $\operatorname{lag}$ 為何。當任務重新加入競爭時，會保留其離開時的 $\operatorname{lag}$，即如果任務在時間 $t$ 離開競爭並在 $t'$ 重新加入，則$\operatorname{lag}(t) = \operatorname{lag}(t')$。
每當發生事件（任務加入、離開或權重變更）時，虛擬時間會根據上述的全局虛擬時間更新公式進行更新。

#### 策略 2
跟策略 1 很像，但主要區別在於任務離開競爭後不保留其 $\operatorname{lag}$，任何（重新）加入競爭的任務 $\operatorname{lag} =0$。這種策略適用於任務事件相互獨立的系統，像是 real-time 系統。

#### 策略 3

一個任務只能在 $\operatorname{lag} =0$ 的時候才被允許離開、加入或改變權重。避免了更新虛擬時間。

在 fluid-flow 模型中，任務會在當 $\operatorname{lag}$ 為 0 的那一瞬間離開。但在實際系統裡，因為是離散時間的，例如一個 time quantum 為單位，它可能會晚一點才真的離開。

假設：在任何一個 time quantum 中，只能發生一件事件
如果一個任務想離開時 $\operatorname{lag} <0$，表示它已經拿太多服務了，不能現在就離開，否則不公平。

所以系統會幫它加一個 dummy request，這個請求的排程點會被設為 $\operatorname{lag} =0$ 的時間。這個 dummy request 不會佔用資源（長度是 0），但它的存在會拖延這個任務的離開時機，直到它的 $\operatorname{lag}$ 自然回到 0。系統在 time quantum 的結尾處處理這個 dummy request，剛好讓 $\operatorname{lag}$ 歸零。由於假設整個 time quantum 中不發生其他事件，這個「延遲」不會造成其他任務被影響，所以是可接受的近似。

還有一個問題：
那如果任務離開時它最後一個請求還沒處理完怎麼辦？
這個策略中會把這些沒用到的 time quantum 隨機分給其他活躍的任務
而且這些任務的 lag 不會被改變，當成免費 bonus

### 延遲上界以及公平性

針對某個任務，它的請求會被延遲多久，推得一個上界（Theorem 1）

### Definition 1
> A system is said to be steady if all the events occurring in that system involve only clients with zero lag.

$\to$ 虛擬時間的連續性
如果 $\operatorname{lag}$ 不為零的任務參與這些事件，根據更新虛擬時間的方式，會導致虛擬時間產生跳躍。

> 複習：
> 任務 $j$ 在時間 $t$ 離開競爭：
$$V(t) = V(t) + \dfrac{\operatorname{lag}_j(t)}{\sum_{i \in \mathcal{A}(t^+)} w_i}$$

當系統中的事件（任務加入、離開或改變權重）僅涉及 $\operatorname{lag}$ 為零的任務時，虛擬時間的變化是連續的。

> 這個連續的性質對於任務 $\operatorname{lag}$ 的 tight bound 很重要，後續的證明會說明

### Definition 2
> An interval is said to be steady if all the events occurring in that interval involve only clients with zero lag.

### Lemma 1
一個在時間 $t$ 具有正 $\operatorname{lag}$ 的活躍任務 $k$：
$$\operatorname{lag}_k(t) ≥ 0$$

則任務 $k$ 在時間 $t$ 有一個 pending eligible request。

#### proof
假設 $r$ 是任務 $k$ 在時間 $t$ 的待處理請求的長度，並且讓 $ve$ 和 $vd$ 分別表示該請求的虛擬合格時間和虛擬截止時間。
> 複習：
只要任務有待處理的請求，就視為活躍狀態（active），否則，視為不活躍狀態（passive）。

使用反證法，假設請求在時間 $t$ 不是 eligible：
$$ve > V(t)$$

假設 $t'$ 為該請求的發起時間，得到：

$$ve = V(t^k_0) + \dfrac{s_k(t^k_0, t')}{w_k}$$

> 複習：
$$V(e) = V(t^i_0) + \dfrac{s_i(t^i_0,t)}{w_i}$$

已知：
$$\operatorname{lag}_k(t) = w_k*(V(t) - V(t^k_0)) - s_k(t^k_0, t)$$

由於在 $t'$ 和 $t$ 之間請求不為 eligible，所以任務在時間區間 $[t', t)$ 內沒有獲得任何服務時間，因此：
$$s_k(t^k_0, t') = s_k(t^k_0, t)$$

進一步獲得：

\begin{aligned}
\operatorname{lag}_k(t) &= w_k*(V(t) - V(t^k_0)) - s_k(t^k_0, t') \\
&= w_k*(V(t) - V(t^k_0)) - w_k*(ve - V(t^k_0)) \\
&= w_k*(V(t) - ve)
\end{aligned}

從不等式 $ve > V(t)$ 可知 $\operatorname{lag}_k(t) < 0$，這與 $\operatorname{lag}$ 不可能為負的事實矛盾。
因此如果任務有正 $\operatorname{lag}$，則其請求必須是 eligible，確保了有正 $\operatorname{lag}$ 的任務總是有機會獲得服務，從而使系統朝著更均衡的資源分配方向發展。

### Corollary 1
根據 Lemma 1，論文給出的第一個推論：假設 $\mathcal{A}(t)$ 是時間 $t$ 時所有活躍任務的集合，使得
$$\sum_{i \in \mathcal{A}(t)} \operatorname{lag}_i(t) = 0$$

則在時間 $t$ 至少會有一個 eligible 的請求。

由於所有 $\operatorname{lag}$ 的總和為零，其中至少有一個任務 $k$ 的 $\operatorname{lag}_k(t) >=0$。根據 lemma 1，這個具有非負延遲的任務一定會有一個合格的請求，因此系統中至少存在一個合格的請求。

### Lemma 2
在任何時間點 $t$，所有活躍任務的延遲總和為零，即剛剛 Corollary 1 裡面的：
$$\sum_{i \in \mathcal{A}(t)} \operatorname{lag}_i(t) = 0$$

#### proof
證明採用歸納法
* **basic case：**
在 $t=0$ 時，系統中沒有活躍的任務，$\sum_{i \in \mathcal{A}(t)} \operatorname{lag}_i(t) = 0$ 成立。
* **歸納步驟：**
證明在以下每種情況發生後，$\sum_{i \in \mathcal{A}(t)} \operatorname{lag}_i(t) = 0$ 仍然成立：
* 情況（i）：任務加入競爭
* 情況（ii）：任務離開競爭
* 情況（iii）：任務改變權重
* 情況（iv）：在沒有上述事件發生的時間區間 $[t, t')$ 內

1. **情況（i）：任務加入競爭**

假設任務 $j$ 在時間 $t$ 加入競爭，當時其延遲為 $\operatorname{lag}_j(t)$。
假設 $t^-$ 表示時間 $t$ 的瞬間前一刻，$t^+$ 表示瞬間後一刻。定義時間 $t$ 所有活躍任務的權重總和為 $W(t) = \sum_{i \in \mathcal{A}(t)} w_i(t)$，由於 $t^-$ 到 $t^+$ 之間時間趨近於零，因此：

$$s_i(t^i_0, t^-) = s_i(t^i_0, t^+) = s_i(t^i_0, t)$$

根據 $\operatorname{lag}_i(t) = S_i(t_0, t) - s_i(t_0, t)$，把上式帶入後移項，並且由於服務量 $S$ 沒有變，簡化可以得到：

$$
\operatorname{lag}_i(t^+) = \operatorname{lag}_i(t^-) = \operatorname{lag}_i(t)
$$

> 複習，當任務 $j$ 加入競爭，虛擬時間的更新：
$$V(t) = V(t) - \frac{\operatorname{lag}_j(t)}{\sum_{i \in \mathcal{A}(t^+)} w_i}$$
>
> 其他任務 $i$ 的 $\operatorname{lag}$ 更新：
$$\operatorname{lag}_i(t) = \operatorname{lag}_i(t) - w_i\dfrac{\operatorname{lag}_j(t)}{\sum_{i \in \mathcal{A}(t^+)}}$$

然而當任務 $j$ 在時間 $t$ 加入系統後，對於所有活躍任務 $i$（包括 $j$ 本身），延遲變為：

$$
\operatorname{lag}_i(t^+) = \operatorname{lag}_i(t^-) - w_i\dfrac{\operatorname{lag}_j(t)}{W(t^+)}
$$

由於 $\mathcal{A}(t^+) = \mathcal{A}(t^-) \cup \{j\}$ 且依歸納假設：

$$
\sum_{i \in \mathcal{A}(t^-)} \operatorname{lag}_i(t^-) = 0
$$

則：

\begin{align*}
\sum_{i \in \mathcal{A}(t^+)} \operatorname{lag}_i(t^+)
&= \sum_{i \in \mathcal{A}(t^+)} \left( \operatorname{lag}_i(t^-) - w_i\frac{\operatorname{lag}_j(t)}{W(t^+)} \right) \\
&= \sum_{i \in \mathcal{A}(t^+)} \operatorname{lag}_i(t^-) - \operatorname{lag}_j(t) \sum_{i \in \mathcal{A}(t^+)} \frac{w_i}{W(t^+)} \\
&= \left( \sum_{i \in \mathcal{A}(t^-)} \operatorname{lag}_i(t^-) + \operatorname{lag}_j(t^-) \right) - \operatorname{lag}_j(t) \frac{W(t^+)}{W(t^+)} \\
&= 0 + \operatorname{lag}_j(t^-) - \operatorname{lag}_j(t) = 0
\end{align*}

因此證明，即使有新的任務加入，其帶來的 $\operatorname{lag}$ 會在系統中平均攤分，讓整體 $\operatorname{lag}$ 保持為 0。

2. **情況（ii）：任務離開競爭：** 證明過程同情況（i）
3. **情況（iii）：任務改變權重：** 視為舊權重任務離開，新權重任務加入競爭的過程，因此同情況（i）以及情況（ii）
4. **情況（iv）：在沒有上述事件發生的時間區間 $[t, t')$ 內：**

basic case 的假設是 $\sum_{i \in \mathcal{A}(t)} \operatorname{lag}_i(t) = 0$，要證明 $\sum_{i \in \mathcal{A}(t')} \operatorname{lag}_i(t') = 0$

根據已知的延遲的定義，以及理想服務時間 $S_i$ 和實際服務時間 $s_i$ 的加法性質，推導出以下：

\begin{align*}
\sum_{i \in \mathcal{A}(t')} \operatorname{lag}_i(t') &= \sum_{i \in \mathcal{A}(t')} \left(S_i(t^i_0, t') - s_i(t^i_0, t')\right) \\
&= \sum_{i \in \mathcal{A}(t')}\Bigg( S_i(t^i_0, t) + S_i(t, t') \Bigg) - \sum_{i \in \mathcal{A}(t')}\Bigg( s_i(t^i_0, t) + s_i(t, t') \Bigg) \\
&= \sum_{i \in \mathcal{A}(t')}\Bigg( S_i(t^i_0, t) - s_i(t^i_0, t)\Bigg) + \sum_{i \in \mathcal{A}(t')}\Bigg( S_i(t, t') - s_i(t, t')\Bigg) \\
\end{align*}

由於在時間區間內 $[t, t')$ 無事件發生，$\mathcal{A}(t) = \mathcal{A}(t')$，故可以進一步改寫成：

$$
= \sum_{i \in \mathcal{A}(t)} \Bigg(S_i(t^i_0, t) - s_i(t^i_0, t)\Bigg) + \sum_{i \in \mathcal{A}(t)} \Bigg(S_i(t, t') - s_i(t, t')\Bigg)
$$

即：

$$
\sum_{i \in \mathcal{A}(t')} \operatorname{lag}_i(t') = \sum_{i \in \mathcal{A}(t)} \operatorname{lag}_i(t) + \sum_{i \in \mathcal{A}(t)} \Bigg(S_i(t, t') - s_i(t, t')\Bigg)
$$

根據假設，第一項為 0，處理第二項就好。已知 $S_i(t, t') = w_i *(V(t') - V(t))$，所以第二項：

$$
\sum_{i \in \mathcal{A}(t)} \Bigg(S_i(t, t') - s_i(t, t')\Bigg) = \sum_{i \in \mathcal{A}(t)} w_i* (V(t') - V(t)) - \sum_{i \in \mathcal{A}(t)} s_i(t, t')
$$

在時間區間 $[t,t')$ 內無事件發生的情况，當活躍任務集合 $W(\tau)$ 不變時：

$$V(t') - V(t) = \int_{t}^{t'} \frac{1}{W(\tau)} d\tau = \frac{t' - t}{W}$$

即：
$$t' - t = W *(V(t') - V(t))$$

代入到原等式：

\begin{align*}
\sum_{i \in \mathcal{A}(t)} w_i *(V(t') - V(t)) - \sum_{i \in \mathcal{A}(t)} s_i(t, t')
&= (V(t') - V(t)) \cdot W - \sum_{i \in \mathcal{A}(t)} s_i(t, t') \\
&= (t' - t) - \sum_{i \in \mathcal{A}(t)} s_i(t, t')
\end{align*}

最終得到：
$$\sum_{i \in \mathcal{A}(t')} \operatorname{lag}_i(t') = (t' - t) - \sum_{i \in \mathcal{A}(t)} s_i(t, t')$$

可以理解為 $(t' - t)$ 是總共經過的時間，$\sum_{i \in \mathcal{A}(t)} s_i(t, t')$ 是實際分配給所有活躍任務的總服務量，所以這兩者的差，就是 $\operatorname{lag}$ 的總和。

---

接下來要證明 Cpu 資源在時間區間 $[t, t')$ 是完全忙碌的。使用反證法，假設在 $[t, t')$中，存在某個時刻 $l$，是 Cpu 首次變成空閒的時間。

根據上式，來寫出在時間 $l$ 的 總 $\operatorname{lag}$ 是：
$$
\sum_{i \in \mathcal{A}(l)} \operatorname{lag}_i(l) = (l - t) - \sum_{i \in \mathcal{A}(t)} s_i(t, l)
$$

但如果資源在 $[t, l)$ 完全忙碌，則實際總服務時間 = 時間區間長度：

$$\sum_{i \in \mathcal{A}(t)} s_i(t, l) = l - t$$

代回等式得到：
$$\sum_{i \in \mathcal{A}(l)} \operatorname{lag}_i(l) = 0$$

根據 Lemma 1，這表示在 $l$ 時刻必定存在 eligible 請求，cpu 資源不應該是空閒的，與假設矛盾。現在知道了 Cpu 在區間 $[t, t')$ 中不可能有空閒，必定是一直忙碌的。因此，整段期間所有任務獲得的總服務量為：

$$
\sum_{i \in \mathcal{A}(t)} s_i(t, t') = t' - t
$$

最終可得：

$$
\sum_{i \in \mathcal{A}(t')} \operatorname{lag}_i(t') = (t' - t) - (t' - t) = 0
$$

得證。

這個 Lemma 建立了 EEVDF 演算法的一個基本性質，系統中的所有延遲總和始終保持為零。代表如果某些任務獲得了多於其應得的資源（負 $\operatorname{lag}$），那麼必定有其他任務獲得了少於其應得的資源（正 $\operatorname{lag}$）。是公平性的基礎。
結合 Lemma 1，Lemma 2 也證明了 EEVDF 是 work-conserving：只要有活躍任務，資源就不會閒置。

### Lemma 3
在穩定系統（definition 1）中，任何活躍任務的任何請求都會在不晚於 $d+q$ 時刻完成，其中 $d$ 是請求的截止時間，$q$ 是 time quantum 的大小。

> 複習 Definition 1：
A system is said to be steady if all the events occurring in that system involve only clients with zero lag.

#### proof

考慮任務 $k$ 的一個請求，其具有合格時間 $e$ 和截止時間 $d$。接下來將在時間 $d$ 的所有活躍任務分為兩個集合 $\mathcal{B}$ 和 $\mathcal{C}$：

* 集合 $\mathcal{B}$：包含所有在時間區間 $[e,d]$ 中至少有一個截止時間的任務
* 集合 $\mathcal{C}$：包含所有其他活躍任務（即其所有截止時間都在 $d$ 之後）

因為任務 $k$ 的請求的 deadline 是 $d$，且其合格時間是 $e$，所以它屬於集合 $B$。

假設 $t$ 為不超過 $d$ 的最晚時間（$t \leq d$），使得集合 $\mathcal{C}$ 中的某個任務收到一個 time quantum $q$（即 Cpu 被分配給了集合 $\mathcal{C}$ 的任務）

**證明分為兩種情況：**
要證明的是任務 $k$ 的請求在時間 $d + q$ 之前就已完成。

**情況（i）：存在這樣的時間 $t$**
這種情況又分為兩個子情況：
1. **$t∈[e,d)$：**

集合 $\mathcal{C}$ 中的任務，其所有請求的截止時間都大於 $d$，也就是說，這些任務不是目前緊急的任務，因為它們的 deadline 還沒到。若排程器在時間 $t$ 將 Cpu 分配給集合 $\mathcal{C}$ 的某個任務，代表當時所有在 $[e,d]$ 內有 deadline 的請求（也就是集合 $\mathcal{B}$ 的任務請求）都已處理完成，因為否則這些有更早 deadline 的請求會被優先執行。

在時間 $t \in [e,d)$ 排程器已經執行集合 $\mathcal{C}$ 中的任務，這表示集合 $\mathcal{B}$ 中的所有請求都已經完成了。既然任務 $k$ 的請求屬於集合 $\mathcal{B}$，因此它的請求也已完成，且完成時間 $< d$。

2. $t<e$：

此時考慮的時間點是 $t<e$，所以任務 $k$ 的請求還尚未合格。

定義一個新集合 $\mathcal{D}$，包含所有在區間 $[t, d)$ 之間有合格時間 $e_j$ 且截止時間 $d_j$ 的活躍任務。這是時間區間 $[t, d)$ 內會需要服務、且 deadline 不晚於 $d$ 的任務集合。

這些截止時間 $< d$ 的請求，在各自合格時間到截止時間的區間 $[e_j, d_j)$，需要累積總服務時間：

$$\sum_{j \in \mathcal{D}} S_j(e_j, d_j) = \sum_{j \in \mathcal{D}} \left( \int_{e_j}^{d_j} \frac{w_j}{\sum_{i \in \mathcal{A}(\tau)} w_i} d\tau \right)$$

接下來，將整個時間區間 $[t, d)$ 分割成不重疊的子區間 $J_l=[a_l,b_l) \quad (1 ≤ l ≤ m)$，使得所有子區間的聯合剛好覆蓋整個 $[t, d)$ ，且每個子區間的邊界點 $a_l$ 和 $b_l$ 不是任何任務的合格時間 $e_j$ 或截止時間 $d_j$。$m$ 代表子區間的數量。

這樣的設計會讓活躍任務的集合保持不變（因為任務只在其合格時間或截止時間改變狀態），並且積分中的分母 $\mathcal{A}(\tau)$ 在整個子區間內保持常數。

有了這種分割，原始的複雜積分可以重寫成子區間 $J_l$ 上的積分之和：：

$$\sum_{j \in \mathcal{D}} S_j(e_j, d_j) = \sum_{l=1}^{m} \left( \int_{a_l}^{b_l} \frac{\sum_{i \in \mathcal{D}(a_l)} w_i}{\sum_{i \in \mathcal{A}(a_l)} w_i} d\tau \right) $$

由於在每個子區間內，$\frac{\sum_{i \in \mathcal{D}(a_l)} w_i}{\sum_{i \in \mathcal{A}(a_l)} w_i}$ 是常數，所以積分會比較簡單：
$$\int_{a_l}^{b_l} \frac{\sum_{i \in \mathcal{D}(a_l)} w_i}{\sum_{i \in \mathcal{A}(a_l)} w_i} d\tau = \frac{\sum_{i \in \mathcal{D}(a_l)} w_i}{\sum_{i \in \mathcal{A}(a_l)} w_i} (b_l-a_l)$$

因為 $D(\tau)$ 是 $A(\tau)$ 的真子集（至少某些 $\tau$ 是這樣），所以權重比例小於 $1$，推出：

$$\sum_{l=1}^{m} \left( \int_{a_l}^{b_l} \frac{\sum_{i \in \mathcal{D}(a_l)} w_i}{\sum_{i \in \mathcal{A}(a_l)} w_i} d\tau \right) < \sum_{l=1}^{m} (b_l-a_l) = d-t$$

進一步整理出：

$${\sum_{j \in D} S_j(e_j, d_j)} < d - t $$

使用反證法，假設任務 $k$ 的請求在 $d + q$ 時尚未完成（即過了 deadline $d$ 也還沒完成）。
根據證明一開始對 $t$ 的定義，在時間 $t$ 到 $t+q$ 期間，集合 $\mathcal{C}$ 中的某個任務正在使用 Cpu 資源，這時候任務 $k$ 還沒變成 eligible。而從 $t+q$ 到 $d+q$ 這段時間內，只有 $\mathcal{D}$ 的任務會被服務（因為 $k$ 還未完成，集合 $\mathcal{C}$ 的任務不會被排程）。所以在 $[t+q, d+q)$ 這段期間，所有 $d - t$ 單位的服務時間都給了 $\mathcal{D}$ 中的任務。

然而根據上述公式，$\mathcal{D}$ 任務完成其所有在 $[t, d)$ 有 deadline 的請求所需的服務時間少於 $d - t$。因此代表在某個時間點，系統將是閒置的狀態，但這與 EEVDF 的 work-conserving 性質相矛盾。

所以得證任務 $k$ 的請求在 $d + q$ 之前就會完成。

**情況（ii）：不存在這樣的時間 $t$**

表示系統中根本沒有需要輪到集合 $\mathcal{C}$ 任務執行的時刻，也就代表直到時間 $d$，排程都專注於集合 $\mathcal{B}$ 中的任務。
可以視為 $\mathcal{C}=∅$，或說 $\mathcal{C}$ 中的任務不參與資源競爭。因此，假設任務 $k$ 的請求具有合格時間 $e$、截止時間 $d$，則它會在區間 $[e,d)$ 中獲得足夠的資源，並在時間 $d$ 前完成，不會錯過截止時間。

### Lemma 4

Lemma 4 是對穩定區間（Definition 2）的延伸分析。它說明了在穩定區間內，某些子區間仍能保持與 Lemma 3 相同的性質。
> 比 Lemma 3 更微觀？

> 複習 Definition 2：
> An interval is said to be steady if all the events occurring in that interval involve only clients with zero lag.

假設 $I = [t_1, t_2)$ 為一個穩定區間，設 $d_m$ 為在時間 $t_1$ 時所有具有負 lag 的活躍任務的待處理請求中最大的截止時間。挑出某個時間點 $d \in [d_m, t_2)$，保證在 $d + q$ 之前，所有在 $d$ 時間前產生 deadline 的任務都會被完成。

#### proof
證明用與 Lemma 3 相似的方法，將所有活躍任務分為兩個集合：

* 集合 $\mathcal{B}$：包含所有在時間區間 $[e,d]$ 中至少有一個截止時間的任務
* 集合 $\mathcal{C}$：包含所有其他活躍任務（即其所有截止時間都在 $d$ 之後）

假設 $t$ 為時間區間 $[t_1, d]$ 中的最晚時間，使得集合 $\mathcal{C}$ 中的某個任務收到一個 time quantum $q$（即 Cpu 被分配給了集合 $\mathcal{C}$ 的任務）

**證明分為兩種情況：**
要證明的是任務 $k$ 的請求會在 $d+q$ 之前完成。

**情況（i）：存在這樣的時間 $t$**
證明過程與 Lemma 3 的情況（i）相同。

**情況（ii）：不存在這樣的時間 $t$**
也就是整段 $[t_1, d]$，Cpu 都只服務 $\mathcal{B}$ 的任務，$\mathcal{C}$ 中的任務都沒被服務。
將集合 $\mathcal{C}$ 進一步分為兩個子集：

- **$\mathcal{C}^-$**：在時間 $t_1$ 時具有負 $\operatorname{lag}$ 的任務
- **$\mathcal{C}^+$**：在時間 $t_1$ 時具有非負 $\operatorname{lag}$ 的任務

1. **對於 $\mathcal{C}^-$ 中的任務**：
因為是穩定區間，它們在 $[t_1, d_m]$ 沒有被服務，但 $d_m$ 是它們所有未完成請求的最大 deadline，所以到了 $d_m$，這些任務會變成 $\operatorname{lag} >= 0$
2. **對於 $\mathcal{C}^+$ 中的任務**：
在 $t_1$ 時已有非負 $\operatorname{lag}$，然後又沒被服務，$\operatorname{lag}$ 只會變得更大，所以到了 $d_m$，會是 $\operatorname{lag} > 0$

所以到了 $d$ 時會發生什麼事？
集合 $\mathcal{C}$ 的 $\operatorname{lag}$ 和：
$$\sum_{i \in \mathcal{C}} \operatorname{lag}_i(d) > 0$$

假設任務 $k$ 的請求在截止時間 $d$ 前未完成（即代表在 $d+q$ 之前也還沒完成），而 $\mathcal{B}$ 的 $\operatorname{lag}$ 和：
$$\sum_{i \in \mathcal{B}} \operatorname{lag}_i(d) \geq 0$$

將上述式子相加：
$$\sum_{i \in \mathcal{A}(d)} \operatorname{lag}_i(d) > 0 $$

所以整體系統的 $\operatorname{lag}$ 和是大於 0 ，這與 Lemma 2（所有活躍任務的 lag 總和為零）矛盾。

所以得證任務 $k$ 的請求會在 $d+q$ 之前完成。

Lemma 4 代表的是即使在允許非零 $\operatorname{lag}$ 任務加入、離開或改變權重的系統中，最終會達到穩定狀態（Lemma 3），並在穩定狀態的某些子區間內保持 Lemma 3 的性質。

### Theorem 1

在穩定系統中，任何活躍任務 $k$ 的延遲都被限制在以下範圍內：

$$-r_{\max} < \operatorname{lag}_k(t) < \max(r_{\max}, q)$$

- $r_{\max}$ 表示任務 $k$ 發出的任何請求的最大持續時間
- $q$ 表示 time quantum 的大小
- 這些界限是 asymptotically tight

#### proof

假設 $e$ 和 $d$ 分別為持續時間為 $r$ 的請求的合格時間和截止時間。
已知 $S_k$ 為單調遞增且斜率不超過 1，任務 $k$ 的延遲在接收服務時間時遞減，否則遞增。

> 複習 $S_k$：
$$
S_i(t_0, t_1) = w_i \int_{t_0}^{t_1} \dfrac{1}{\sum_{j \in \mathcal{A}(\tau)} w_j} \, d\tau
$$

1. **下界證明（$\operatorname{lag}_k(t) > -r_{\max}$）**

直觀來說最小延遲發生在請求一旦變為合格就立即接收到完整服務時間的情況。

若請求在時間 $e + r$ 前完成，則在時間 $e + r$ 的延遲為：
\begin{align*}
\operatorname{lag}_k(e + r) &= S_k(t_k^0, e + r) - s_k(t_k^0, e + r) \\
&= \Bigg( S_k(t_k^0, e) + S_k(e, e + r) \Bigg)- \Bigg(s_k(t_k^0, e) + s_k(e, e + r)\Bigg) \\
&= \Bigg( S_k(t_k^0, e) - s_k(t_k^0, e) \Bigg) + \Bigg( S_k(e, e + r) - s_k(e, e + r)\Bigg)\\
&= \operatorname{lag}_k(e) + S_k(e, e + r) - s_k(e, e + r)
\end{align*}

> p.s 這個拆開重組的手法在 Lemma 2 也有出現過。

因為 $e$ 是這個請求變成合格的時間，合格的意思是說此時服務延遲還沒超過應給的值，所以 lag 是非負的。$\operatorname{lag}_k(e) \geq 0$，因此：

$$\operatorname{lag}_k(e + r) \geq S_k(e, e + r) - s_k(e, e + r) $$

在理想情況下，系統會更公平的持續服務所有任務，因此理想服務量大部分時候會小於等於實際服務量。現在假設的是最悲觀的情況，也就是任務 $k$ 立即獲得完整的服務：$s_k(e, e + r) = r$，但是由於 $S_k$ 的斜率永遠不超過 $1$（即理想系統中任務不能獲得超過 100% 的資源），所以：

$$S_k(e, e + r) <= r$$

因此整理出：
$$S_k(e, e + r) - s_k(e, e + r) >= S_k(e, e + r) -r > -r$$

進一步推導：
$$\operatorname{lag}_k(e + r) > -r$$

因為 $r$ 是這個請求的持續時間，而 $r_{\max}$ 是所有請求的最大持續時間，所以對任何時間 $t$，整理出：
$$\text{lag}_k(t) > -r_{\max}$$

2. **上界證明（$\operatorname{lag}_k(t) < \max(r_{\max}, q)$）**

直觀來說最大延遲發生在請求在它變成合格之後，被拖到最晚還能完成的時間才開始被服務的情況。於是根據 Lemma 3，請求最晚在 $d + q$ 時完成，因此任務 $k$ 最晚應在 $d + q - r$ 時接收第一個 quantum。

**情況（i）：$r \geq q$ （請求時間長 $≥$ quantum 大小）**
此時 $d + q - r \leq d$，所以：
$$S_k(e, d + q - r) < S_k(e, d) = r$$

考慮最壞情況，任務在區間 $[t_1, d + q - r)$ 內完全沒有接收到任何服務時間，其中 $t_1$ 是請求發出的時間。在這種情況下 $s_k(t_1, d + q - r) = 0$（沒有接收到服務），因此 $s_k(t^k_0, d + q - r) = s_k(t^k_0, t_1)$（只有之前的服務時間）

假設 $t$ 是這段等待中的某個時刻，延遲最多是：
\begin{align*}
\operatorname{lag}_k(t) &<= S_k(t^k_0, d + q - r) - s_k(t^k_0, d + q - r) \\
&= S_k(t^k_0, d + q - r) -s_k(t^k_0, t_1) \\
&= \Bigg(S_k(t^k_0, e) + S_k(e, d + q - r)\Bigg) -s_k(t^k_0, t_1) \\
&= S_k(e, d + q - r) + \Bigg(S_k(t^k_0, e) - s_k(t^k_0, t_1)\Bigg)
\end{align*}

根據合格時間 $e$ 的定義：
$$S_k(t_k^0, e) = s_k(t_k^0, t_1)$$

整理出：

$$\operatorname{lag}_k(t) <= S_k(e, d + q - r) < r$$

而因為 $r \leq r_{\max}$，因此：
$$\operatorname{lag}_k(t) < r_{\max}$$

**情況（i）：$r < q$ （請求時間長 $<$ quantum 大小）**

一樣考慮的是最壞的情況，任務在區間 $[t_1, d + q - r)$ 內完全沒有接收到任何服務時間，其中 $t_1$ 是請求發出的時間。

假設 $t$ 是這段等待中的某個時刻，延遲最多是：
$$\operatorname{lag}_k(t) <= S_k(e, d + q - r)$$

> 這個公式已經在上一個情況已經推導過

已知：
$$S_k(e, d + q - r) = S_k(e, d) + S_k(d, d + q - r) $$

而 $S_k$ 是理想服務，由於通常存在競爭（多個任務），斜率不會超過 $1$：
$$S_k(d, d + q - r) < q - r$$

因此：
$$\operatorname{lag}_k(t) <= S_k(e, d + q - r) < r + q - r = q$$

所以在這段時間內的延遲上限是：
$$\operatorname{lag}_k(t) < q$$

結合兩種情況：
$$\operatorname{lag}_k(t) < \max(q, r_{\max})$$

### Corollary 2
Corollary 2 是從 Theorem 1 直接推導出來的結果，是針對穩定系統中請求長度不超過一個 time quantum 的特殊情況。

假設一個穩定系統和一個任務 $k$，使得任務 $k$ 的任何請求都不大於一個 time quantum $q$。那麼在任何時間 $t$，任務 $k$ 的延遲會被約束如下：

$$-q < \operatorname{lag}_k(t) < q$$

> 複習 theorem 1：
$$-r_{max} < \operatorname{lag}_k(t) < max(r_{max}, q)$$

根據 $r_{max} ≤ q$：
* 下界：$-r_{max} > -q$
* 上界：$max(r_{max}, q) = q$

### Lemma 5
給定任何具有大小為 $q$ 的 time quantum 的穩定系統和任何比例共享的演算法，任何任務的延遲被限制在 $−q$ 和 $q$ 之間。

這個 Lemma 證明了 Corollary 2 給出的界限是最優的，即沒有任何比例分享演算法能夠達到比 $±q$ 更好的界限。

#### proof
假設 $n$ 個具有一樣權重的任務在時間 $0$ 同時變為活躍狀態。

**證明分兩種情況：**
**情況 (i)：理想的平均分配**
即為每個任務在前 $n$ 個 time quantum 中剛好都接收一個 time quantum。
* 分析第一個 time quantum 的任務在時間 $q$ 的 $\operatorname{lag}$
根據：
$$lag_i(t) = S_i(t^i_0, t) - s_i(t^i_0, t)$$

在理想流體模型中，任務的分配額是 $\dfrac{1}{n}$，總可用時間 $q$，至於任務 $1$ 實際上接收了完整的第一個 time quantum，因此計算 $\operatorname{lag}$：

$$\operatorname{lag}(q) = \dfrac{q}{n} - q = -q\dfrac{(n-1)}{n}$$

當 $n$ 很大時，這個延遲逼近 $-q$。

* 分析最後一個 time quantum 的任務，即為在時間 $q(n-1)$（即將接收第 $n$ 個 time quantum 之前），最後一個任務的 $\operatorname{lag}$ ：

在理想流體模型中，任務的分配額是 $\dfrac{1}{n}$，總可用時間 $q(n-1)$，至於任務 $n$ 實際上接收了 $0$，因為還沒輪到他。
$$\operatorname{lag}(q(n-1)) = q - \dfrac{q}{n} = q\dfrac{(n-1)}{n}$$

當 $n$ 很大時，這個延遲逼近 $+q$。可以想成最後一個任務等了很久都沒有服務，累積了接近 $+q$ 的正延遲。

**情況 (ii)：不平均分配**
* 上界：
假設存在一個比例分享演算法能夠達到上界小於 $q$ 的界限，即 $q - ε$（其中 $ε > 0$）。

選擇 $n > \dfrac{q}{ε}$，因此：
$$ε > \dfrac{q}{n}$$

從情況 (i) 的分析，在時間 $q(n-1)$，最後接收 time quantum 的任務延遲為：
$$\operatorname{lag}(q(n-1)) = q\dfrac{(n-1)}{n} = q - \dfrac{q}{n} > q - ε$$

這與假設的上界 $q - ε$ 矛盾。
* 下界：
跟上屆的證明一樣，假設存在比 $-q$ 更好的下界 $-q + ε$，選擇足夠大的 $n$，第一個任務的延遲會跟這個下界矛盾。

### 第六章的意義（不講證明來看 fairness）

service time lag 作為公平性的量化指標。

延遲 = 理想系統中應獲得的服務時間 - 實際獲得的服務時間

#### Lemma 1 的意義
若系統中某個任務的 $\operatorname{lag}$ 為正，那一定存在一個符合排程條件的請求，其虛擬時間最小，應被立即選擇執行。代表只要有任務落後，就一定可以從中挑選出一個有效的請求來執行，排程器永遠不會在有落後任務時讓資源閒置。

#### Lemma 2 的意義
在任何時刻，系統中所有活躍任務的 $\operatorname{lag}$ 值總和為 0。如果某些任務落後於其理想進度（$\operatorname{lag} > 0$），那必然有其他任務超前（$\operatorname{lag} < 0$）。這代表系統中的排程公平性是以誰快就讓誰等，誰慢就先執行來動態維持的。是 EEVDF 滿足 proportional fairness 條件的關鍵理論依據。

#### Lemma 3 和 Lemma 4 的意義
在穩定運作的系統中，每個請求的完成時間不會超過他的理想完成時間 virtual finish time $vd$ 加上一個 time quantum。這表示請求的完成延遲有一個明確的上界，即使有排程競爭與資源共享，最壞情況下的延遲也是可預期的，且只比理想時間最多多一個 $q$。

防止某些任務被無限期的延遲。

> WFQ 的延遲可能會以 $O(n)$ 線性增長
> 詳情請看 GPS 筆記

#### Theorem 1 的意義
此 Theorem 給出 EEVDF 在一般情況下的 $\operatorname{lag}$ 範圍：
任一請求的延遲被限制在區間 $(-r_{\max}, \max(r_{\max}, q))$ 內。其中 $r_{\max}$ 是系統中最大請求長度，$q$ 是 time quantum。

上界保證：任何任務都不會被過度延遲，下界保證：任何任務都不會獲得過多優勢，且界限取決於任務自己的請求大小。

> 這個算是對於 fairness 的證明嗎？

#### Corollary 2 的意義
當所有請求的長度都小於等於一個 time quantum，即 $r_i \leq q$，此時 Theorem 1 的延遲界限簡化為 $(-q, q)$。這表示延遲永遠不會早於理想完成時間 $q$ 單位以上，也不會晚於理想完成時間 $q$ 單位以上。

#### Lemma 5 的意義
Lemma 5 證明在請求長度不超過一個 time quantum 的條件下，沒有任何比例共享的排程策略可以做到比 $(-q, q)$ 更窄的延遲界限。換言之 EEVDF 已達到理論上可能的最佳公平性。