# 重新看懂 GPS 相關的東西
[參考論文1：A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case](https://pbg.cs.illinois.edu/courses/cs598fa09/readings/pg93.pdf)

[參考論文2：WF2Q : Worst-case Fair Weighted Fair Queueing](https://www.cs.cmu.edu/~hzhang/papers/INFOCOM96.pdf)

[參考論文3：Earliest eligible virtual deadline first: A flexible and accurate mechanism for proportional share resource allocation](https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=805acf7726282721504c8f00575d91ebfd750564)

[EEVDF 論文研讀筆記](https://hackmd.io/@salmonii/SkXQvDKZel)

## generalized processor-sharing (GPS) model
在設計 Integrated Services Networks 時，選擇網路中排隊節點的封包的規則（packet service discipline）是很重要的議題。

先從 Processor Sharing（PS）開始，there is a separate FIFO queue for each session sharing the same link.
在任意的時間區間內，若有正好 N 個不是空的佇列，伺服器會同時服務這 N 個佇列的第一個封包，每個封包的服務速率為 link 速率的 1/N。

> GPS allows different sessions to have different service shares and serves the non-empty queues in proportion to the service shares of their corresponding sessions.

GPS 則是在同時服務所有佇列之下，可以有不同的比例來服務不是空的佇列。

> 用「服務」還是「傳輸」比較好？ 我是 service 直翻

### GPS 定義與數學公式
首先是符號釋義表

| 符號 | 意思 |
| -------- | -------- |
| $a^k_i$ | 第 $k$ 個封包在 session $i$ 中的到達時間 |
| $b^k_{i,s}$ | 第 $k$ 個封包在 session $i$ 上於 server $s$ 開始的服務時間 |
| $d^k_{i,s}$ | 第 $k$ 個封包在 session $i$ 上於 server $s$ 離開時間|
| $B_s(\tau)$ | 在 server $s$ 上，時間 $\tau$ 時處於 backlogged 狀態的 session 集合 |
|$W_{i,s}(t_1,t_2)$ | session $i$ 在 server $s$ 上於時間區間 [ $t_1$, $t_2$ ] 所獲得的服務量（bits） |
| $L^k_i$ | 第 $k$ 個封包在 session $i$ 的長度（packet size in bits） |
| $L_{i,max}$ | session $i$ 中的最大封包大小 |
| $L_{max}$ | 所有 session 中的最大封包大小 |
| $r$ | link speed |
|$r_i$ | 為 session $i$ 保證的服務速率（guaranteed rate）|

此處的 server $s$ 可能是 GPS 或是 WFQ，後續會說明。

---

GPS 是一個理想化的 fluid model。

假設有 $N$ 個 sessions，每個 session $i$ 都會被指派一個正的權重 $φ_1$，$φ_2$，$φ_3$ ...... $φ_N$。假設 server 的服務速率是固定的 $r$ 且是 work-conserving 的。
> A server is work-conserving if it is never idle there are packets to be transmitted. Otherwise, it is conserving.

以下是 GPS 基於上述假設的公平性定義:

$$\dfrac{W_i(t_1,t_2)}{W_j(t_1,t_2)} \ge \dfrac{φ_i}{φ_j} \quad ,\quad j=1,2,....N$$

代表如果 session $i$ 和 $j$ 都在時間區間內是 backlogged（即為不是空的佇列：都有資料在等待傳輸），則它們被服務的 bits 數應該要按照其權重比例來分配。也就是說，服務量與權重的比值要公平。

根據以上的定義，可以推知某個 session $i$ 理想上應該會獲得的服務速率公式（Ideal Fair Share Rate）：
$$r_i = \dfrac{φ_i}{\sum_{j=1}^{N}φ_j}r$$
$\sum_{j=1}^{N}φ_j$ 代表系統中所有 session 的權重之和，且這些 session 都是 backlogged 的狀態。

不過當然不可能所有 session 一定隨時都有資料在傳輸的，以上只是理想情況，所以有了 Instantaneous Guaranteed Rate 的公式：

$$r^*_i(t_1, t_2) = \dfrac{φ_i}{\sum_{j=1\in B_{GPS}(t_1)}φ_j}r$$

$\sum_{j=1\in B_{GPS}(t_1)}φ_j$ 代表在時間 $t_1$ 時，所有處於 backlogged 的 session 的權重之和。

這個公式說明，在任何給定時刻 $t_1$，link speed $r$ 會根據當時所有活動中的 session 的權重比例進行分配。所以仍然符合比例分配的公平定義。

另外一個要看到的是，基於只有部分 session 是 backlogged 情況下的 Actual Service Rate Lower Bound：
$$r^*_i(t_1, t_2) = \dfrac{W_i(t_1,t_2)}{t_2-t_1}$$
* $r^*_i(t_1, t_2)$ 代表session $i$ 在時間區間 [ $t_1$, $t_2$ ]內實際獲得的平均服務速率。
* $r_i$ 代表session $i$ 在理想的、始終有所有 session 處於 backlogged 狀態下的平均服務速率。$r$ 總是根據所有 session 的權重比例進行分配。

$$r^*_i(t_1, t_2) \ge r_i$$

以上公式代表即使在某些 session 可能空閒的情況下，session $i$ 在任何時間區間內獲得的實際平均服務速率至少不會低於其在所有 session 都持續 backlogged 的理想情況下應獲得的平均速率。

## Weighted Fair Queuing（WFQ）/ Packet Generalized Processor Sharing（PGPS）

不過在實際網路世界中，是不可能像 GPS 運作的，因為封包是離散的，而且是一次服務一個封包。所以在真實世界中（packet system）想要模擬 GPS 這樣理想的行為，有一個常見的方法是 Weighted Fair Queuing（WFQ），也就是所謂的 Packet Generalized Processor Sharing（PGPS）或是 Packet-by-Packet Generalized Processor Sharing。

> Then, a very good approximation of GPS would be a work-conserving scheme that serves packets in increasing order of $d^k_{i,GPS}$

### 首先，如何模擬？
理想 GPS 情況之下，當目前系統在時間 $\tau$ 時成為閒置的狀態，要挑選下一個服務的封包，會以封包的 finish time 以遞增順序來服務。
為了避免閒置（如上述所說，GPS 是 work-conserving 的），PGPS 會在時間 $\tau$ 時，從目前已經到達系統並且等待服務的封包中做選擇。假設在時間 $\tau$ 開始，沒有新的封包再到達，那麼這些封包將會以各自的權重比例持續獲得服務，並計算出它們各自的完成時間。PGPS 會選擇在這次模擬中完成時間最早的那個已到達的封包來服務。

在保持系統不閒置的前提之下，盡可能接近理想 GPS 的服務順序。

論文中給出的例子，順便理解 GPS、PGPS 行為上的差異：
假設有兩個 session，在時間 0，只有 session 2 的 A 封包在佇列裡面，而且這是個比較長的封包，長度為 3。session 1 的另一個長度為 1 的 B 封包在時間 1 才到達。

首先計算 GPS 模型下 B 封包的服務完成時間：
到時間 1，session 2 還沒結束（size = 3，需要時間），session 1 才剛加入，因此從時間 1 開始，session 1 和 session 2 同時是 backlogged，分別拿到一半的 bandwidth。

所以是 $1+ \dfrac{1}{\dfrac{1}{2}} = 3$

PGPS 模型下 B 封包的服務完成時間：
由於時間 0 沒有其他選擇，系統去服務 A 封包，且基於一次服務一個完整封包的真實世界的樣子，要等到 A 封包服務完成才能回頭處理 B 封包。

所以是 $3+1 = 4$

可以看到 B 封包在 PGPS 中晚了 $1$ 秒離開系統。

### 再來，證明 PGPS 真的可以逼近 GPS 的行為？

#### Lemma 1

如果在時間 $\tau$，在模擬的 GPS 中，封包 p 會比 p' 早完成（假設之後不再有新封包到達），那麼即使之後有新的封包進入，p 還是會比 p' 早完成。GPS 中的完成順序 不受未來到達的封包影響。

> A consequence of this lemma is that if PGPS schedules a packet p at time $\tau$ bfore another packet p’ that is also backlogged at time $\tau$, then in the simulated GPS system, packet p cannot leave later than packet p’. Thus, the only packets that are delayed more in PGPS are those that arrive too late to be transmitted in their GPS order. Intuitively, this means that only the packets that have a small delay under GPS are delayed more under PGPS.

> 我還看沒懂這段的意思

#### Definition 1
若兩個排程系統雖然使用不同的服務策略，只要它們擁有：
* same speed $r$
* same set of sessions
* same arrival pattern $a^k_i$
* same service share for each session $φ_1$，$φ_2$，$φ_3$ ...... $φ_N$

那麼就稱這兩個系統是 corresponding systems。

這個定義讓論文可以比較兩個不同的排程策略 PGPS 與 GPS 在相同輸入條件下對封包的服務差異，並且進行分析。

首先要定義誤差，針對封包離開時間（完成時間）以及服務量為量度：
1. 離開時間

這個誤差值的來源是因為 GPS 是 fluid model，可以同時在傳輸在不同 session 之下的資料。PGPS 是實際實作，必須一次處理一個封包，而且因為 packetization 的效果，封包不能被中斷，PGPS 在處理完目前的封包後才能切換到下一個應該被服務的 session，這可能導致一個 session 的封包完成時間比在 GPS 下還要晚。這部分剛剛有用例子簡單說明過：

#### Theorem 1

以下 Theorem 定義了 PGPS 相對於 GPS 的延遲時間差異：

$$d^k_{i,PGPS} - d^k_{i,GPS} \le \dfrac{L_{max}}{r} \quad , \quad \forall i,k$$

$\dfrac{L_{max}}{r}$ 可以理解成傳輸一個最大尺寸封包所需要的時間。代表 PGPS 下的延遲時間最多比 GPS 下的時間大 $\dfrac{L_{max}}{r}$，且是可界定的。

proof：
busy periods

2. 服務量差異
#### Theorem 2
$$W_{i,GPS}(0,\tau) - W_{i,WFQ}(0,\tau) \le L_{max} \quad , \quad \forall i,\tau$$

在任何時間點，WFQ 提供給 session $i$ 的服務量可能比 GPS 少，但這個差距被限制在一個最大封包的長度之內。

> 這兩個 Theorem 怎麼計算出來的？
在[參考論文1：A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case](https://pbg.cs.illinois.edu/courses/cs598fa09/readings/pg93.pdf) 裡面有證明
> 我還沒細看
> todo

### Virtual Time Implementation of GPS
GPS 作為理想的 fluid model，同時為所有 backlogged sessions 提供服務。因此在數學上，$V(t)$ 是一個連續隨時間變化的函數，因為是理想模型，所以在任何極短的時間間隔內，只要有 backlogged session，虛擬時間就會以前面提到的速率持續增長。

在一開始介紹的理想 GPS 之下，要傳輸一個 $L$ 位元的封包，需要的實際時間是：
$\dfrac{L}{r_i} = \dfrac{L}{\dfrac{φ_i}{\sum_{j=1}^{N}φ_j}r}$

假設 $r$ 是 1 ，只看 $\dfrac{L}{φ_i}$。

> In the following, we assume that the server works at rate 1.

以下公式的 $\dfrac{L}{φ_i}$ 並不是實際的傳輸時間，可以想成在一個虛擬的時間軸上要推進的量。代表比較高權重的 session 會更快的傳輸完成相同大小的封包。

### Virtual Time Implementation of PGPS

> Denote as an **event** each arrival and departure from the GPS server, and let $t_j$ be the time at which the $jth$ event occurs (simultaneous events are ordered arbitrarily).

> 這段話的意思是把 GPS model 用離散事件的角度去觀察嗎？
為了將 GPS 的概念應用到實際的 PGPS，想像 fluid 是封包？想像封包的開始服務是到達事件、封包的結束服務是離開事件？

在 PGPS 或 WFQ 中，是想要模擬一個理想的 GPS 系統。但實體硬體無法像 GPS 那樣同時處理多個封包，也沒辦法持續追蹤每個 session 的狀態（很花運算資源跟時間），因此使用 Virtual Time 來近似模擬理想服務的進度，以決定封包的服務順序。

PGPS 維護一個 Virtual Time 函數 $V(τ)$，它在概念上類似於 GPS 中的 virtual time，但他的更新是基於已經完成服務的封包，就不是連續的時間刻度之下。PGPS 的核心思想是按照封包的 $F^k_i$ 的非遞減順序來服務封包。也就是說，具有最小 Virtual Finish Time 的封包將會被優先傳輸。

* **Virtual Time $V(t)$**
$$V(0) = 0$$
若上一個事件發生在時間 $t_{j-1}$，接下來在 $t_{j-1} + \tau$ 有新事件（比如說封包抵達或完成）：
$$V(t_{j-1} + \tau) = V(t_{j-1}) + \dfrac{\tau}{\sum_{i\in B(t_j)}φ_i} $$

這段公式最直觀的解釋就是，實際的時間每流逝 $\tau$，虛擬的時間就會增加 $\dfrac{\tau}{\sum_{i\in B(t_j)}φ_i}$。

Virtual time 的增長速率 $\dfrac{\partial{V(t_j + \tau)}}{\partial{\tau}}$，也就是 $\dfrac{1}{\sum_{i\in B(t_j)}φ_i}$，可以看出在任何時間 $\tau$，Virtual time 的增長速率與當時所有 backlogged session 的權重之和成反比。可以理解為：當有更多總權重的 session 需要服務時，$V(t)$ 的增長速度更慢；當總權重較小時，增長速度較快。

> Thus, V can be interpreted as increasing at the marginal rate at which backlogged sessions receive service.
marginal rate 是什麼意思

* **Virtual Start Time $S^k_i$**
$$S^k_i = max\{F^{k-1}_i,V(a^k_i)\}$$

$max\{F^{k-1}_i,V(a^k_i)\}$ 用於計算 Virtual Start Time
如果前一個封包的 Virtual Finish Time 大於目前封包到達時的虛擬時間 $V(a^k_i)$，則目前封包的服務必須在前一個封包完成之後才能公平的開始。

* **Virtual Finish Time $F^k_i$**
$$F^0_i = 0$$

$$F^k_i = S^k_i + \dfrac{L^k_i}{φ_i}$$

兩者合併會是：
$$F^k_i = max\{F^{k-1}_i,V(a^k_i)\} + \dfrac{L^k_i}{φ_i}$$

$\dfrac{L^k_i}{φ_i}$ 這部分是指傳輸 session $i$ 中第 $k$ 個封包在虛擬的時間軸上造成的推進量，假設 $r$ 是 1 。
* 封包越大 -> 推進量越多
* 權重越高 -> 推進量越短（因為它在 GPS 中分到更多資源）

在對於 session $i$ 的第 $k$ 個封包到達時，根據目前的虛擬時間還有封包的長度以及所在 session 的權重計算其 $F^k_i$。這個 Virtual Finish Time 預先計算了此封包在 GPS 模型下完成服務的 virtual 時間點。

> 這個虛擬完成時間點，代表在理想的 GPS 模型下，該工作單元應當完成服務的虛擬時刻。WFQ/PGPS 排程器在做出排程決策時，總是優先選擇具有最小虛擬完成時間的工作單元進行服務。此機制能在離散服務環境下，使每個任務獲得的服務量長期、近似地與其權重成正比，並提供可證明的延遲上界。

### event driven
論文提及這種算法的優點：
* 封包一進入系統時，就可以算出其 $F^{k}_i$，不需等到封包被處理時才決定何時完成。
* 服務順序不是按照到達時間，而是按照 Virtual Finish Time。模擬 GPS 的公平機制。
* $V(t)$ 作為模擬 GPS 進度的指標，可以不需要隨時更新，減少了運算負擔。就像前面有提到的，PGPS 是一個離散而非連續的視角。只有以下情況才需要去更新她：
* 封包到達或離開的事件發生？
* 由於封包到達導致新的 session 變為 backlogged
* 封包完成服務導致 session 變為 idle

一旦 $B(t)$ 改變，就要重新計算 virtual time 的增長速率，這需要追蹤每個 session 的狀態。

> However, the price to be paid for these advantages is some overhead in keeping track of sets Bj, which is essential in the updating of virtual time.

---
> Define $Next(t)$ to be the real time at which the next packet will depart the GPS system after time $t$ if there are no more arrivals after time $t$.

$$F_{min} = V(t)+ \dfrac{Next(t)-t}{\sum_{i\in B(t_j)}φ_i}$$
$$Next(t) = t + (F_{min} - V(t))\sum_{i\in B(t_j)}φ_i$$

在上一個部分說明 virtual time 時有提到，在時間區間 [ $t$ , $Next(t)$ ] 內，實際的時間每流逝 $Next(t)-t$，虛擬的時間就會增加 $\dfrac{Next(t)-t}{\sum_{i\in B(t_j)}φ_i}$。

$Next(t)$ 是下一個封包預計完成服務的實際時間。用這個真實完成時間來推算對應的 Virtual Finish Time。$Next(t)−t$：從目前時間 $t$ 到下一個封包預計完成服務的時間間隔。

> Given this mechanism for updating virtual time, PGPS is defined as follows: When a packet arrives, virtual time is updated and the packet is stamped with its virtual time finishing time. The server is work conserving and serves packets in an increasing order of timestamp.

根據論文中這句話，$V(t)$ 會在有新封包到達時進行更新。從目前的 $V(t)$ 開始，然後根據從現在到下一個封包完成服務所需的實際時間，以及當時系統中 backlogged session 的總權重，來推算出虛擬的時間會前進多少，記錄他的 Virtual Finish Time $F_{min}$。

> 所以封包離開不用 update virtual time？但是 $B(t)$ 不是有可能改變嗎？

## PGPS 跟 CFS 的關係
雖然一個是用在網路世界，一個是核心中的 CPU 排程器

vruntime = delta_exec × (weight_of_nice_0 / task_weight)

每個 nice 值會對應到一個權重
權重較高的任務，其 vruntime 增長較慢，權重較低的任務，其 vruntime 增長較快。CFS 總是選擇 vruntime 最小的任務來執行

CFS 的 vruntime 是每個任務獨立計算和累計的
PGPS 的虛擬時間 $V(t)$，增長速率受到所有目前 backlogged session 的總權重影響

都是離散的視角 但是 CFS 的任務可以被 preempt ?
PGPS 的封包需要被完整的傳輸

CFS 是挑選最小 virtual runtime
PGPS 挑選最小 virtual finish time

> todo

## WFQ（PGPS）的缺點
[第二篇的論文](https://www.cs.cmu.edu/~hzhang/papers/INFOCOM96.pdf)有提到第一篇論文所證明出的

$$d^k_{i,WFQ} - d^k_{i,GPS} \le \dfrac{L_{max}}{r} \quad , \quad \forall i,k$$

$$W_{i,GPS}(0,\tau) - W_{i,WFQ}(0,\tau) \le L_{max} \quad , \quad \forall i,\tau$$

兩個 Theorem 會很容易讓人產生 WFQ 的系統提供比 GPS 最多一個封包的延遲量而幾乎一樣服務的錯覺。但其實不是這樣的

以下結合論文 2 的例子還有論文 3 的計算說明
> -> 進化成 EEVDF 的其中一個原因？

---

假設有 11 個 session，每個封包的長度為 1，link speed 為 1（即每單位時間傳送一個 packet）。session 1 的 guaranteed rate 是 0.5，其餘 10 個 session 各自是 0.05。

> 複習 guaranteed rate $r_i$，跟 session 的權重息息相關：
> $$r_i = \dfrac{φ_i}{\sum_{j=1}^{N}φ_j}r$$

在時間 0，session 1 傳送了 11 個連續的封包，而其他 10 個 session 各傳送 1 個封包。

理想 GPS 系統下的行為：
session 1 中的第一個封包的完成傳輸時間
$$\dfrac{1}{\dfrac{1}{2}} = 2$$

其他 session 的風包則各自是第時間 20 完成

$$\dfrac{1}{\dfrac{1}{20}} = 20$$

WFQ 行為：
在時間 0，所有 session 都有封包等待排程。

session 1 中 p1 的 finish time：$\dfrac{1}{\dfrac{1}{2}} = 2$
p2：$2 + \dfrac{1}{\dfrac{1}{2}} = 4$
p3：$4 + \dfrac{1}{\dfrac{1}{2}} = 6$

p10：20

session 1 的前 9 個封包的 finish time 都比其他 session 的更早，WFQ 在模擬 GPS 時會將這些 finishing time 作為排程依據，就會導致 session 1 的前 10 個封包先被送出。

在短時間內 burst 發送了 10 個封包之後，WFQ 會接著服務其他 10 個 session 各自的 packet，session 1 會進入 silence 狀態。造成以下可能的振盪：

burst 10 packets → silence 10 packet times → burst again

> With more sessions, the length of the period between bursting and silence can be larger.

> Such oscillation is undesirable for feedback-based congestion control algorithms used in data communication networks. Within the framework of feedback-based congestion control, a data source has to balance between two considerations: on the one hand, it wants to send data to the network as fast as possible, on the other hand, it does not want to send data so fast that causes network congestion

---

[論文三](https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=805acf7726282721504c8f00575d91ebfd750564)量化了這樣情況下的延遲差距

假設有 $n + 1$ 個 active sessions，session 1 權重為 $n$。其餘 n 個 sessions 的權重為 1。 一樣每單位時間傳送一個封包。

在 WFQ 中，所有封包一到系統中就成為 eligible 的選手，導致高權重的 session 可能連續佔用資源，以下說明：

假設 $S_i(t_1, t_2)$ 代表時間間隔 [ $t_1$ , $t_2$ ) 中 session $i$ 理想上應該要獲得的服務量

$S^*_i(t_1, t_2)$ 代表時間間隔 [ $t_1$ , $t_2$ ) 中 session $i$ 實際獲得的服務量

總權重 $$W = φ_1 + \sum_{i=2}^{n+1}φ_i = n + n = 2n$$

對於 session 1，計算出的 finish time 分別是 $\dfrac{1}{n}$、$\dfrac{2}{n}$、$\dfrac{3}{n}$... $\dfrac{n-1}{n}$、$1$

因此，在 WFQ 中，virtual finish time 最小的先被送出，結果會是：
時間 [ $0$, $n−1$ ) 全部拿去傳 session 1 的前 $n−1$ 個封包。其他 sessions 的封包要等到時間 $\ge n−1$ 才開始被傳輸。

根據 ideal fluid system（GPS），session 1 應該在這段時間得到的服務量為：
$$S_1(0, n-1) = \dfrac{n}{2n}n-1 = \dfrac{n-1}{2}$$

WFQ 中的實際服務時間，在區間 [ $0$ , $n-1$ ) 內，每個時間單位傳一個封包：
$$S^*_1(0, n-1) = n-1 $$

計算出 session 1 中的

$$lag_1(n-1) = S_1(0, n-1) - S^*_1(0, n-1)= \dfrac{n-1}{2} - n-1 = -\dfrac{n-1}{2}$$

這是負的 lag，表示 session 1 得到的服務超過了理論值。
> 若 $\operatorname{lag}_i < 0$，表示行程 $i$ 所獲得的服務量已超過其應得的公平份額，即處於「超前」狀態

雖然單個封包延遲時間不超過 $\dfrac{L_{max}}{r}$，但多個封包的累積 lag 可是線性成長的 $O(n)$

---

> 對於具有重尾特性的工作負載，例如其 CPU 突發需求的持續時間或計算強度之分布，呈現出類似柯西分布的特徵，即存在不可忽略的機率發生極端長時或高強度 CPU 佔用事件，CFS 機制可能導致此類任務在其 $v_i$ 顯著超前之前，持續佔用 CPU 資源。

> Lag 的有界性是改善延遲的基礎：EEVDF 的設計確保每個任務的 lag 被嚴格限制在一個已知的範圍內 (如 $0 \le \operatorname{lag}_i \le \text{slice_value}$，其中 $\text{slice_value}$ 與分配的時間片相關)。這種有界的 lag 特性，使得即便在系統高負載的情況下，任務的延遲 (尤其是喚醒延遲) 也能保持在相對可預測的水準，從而有效彌補 CFS 在這方面的不足

## 待整理

我想問如果 CFS 就是建立在網路世界的基礎上，為什麼當初的設計不運用 PGPS 中的全局虛擬計算概念，而是每個任務個別維護？一開始設計的考量是什麼？

書中介紹 CFS 的章節目前也是寫說參考 WFQ，但是他的行為還是跟 WFQ 很不一樣，他是用 virtual runtime 而不是 virtual finish time，也不是用全局的概念。硬要說的話我覺得 EEVDF 跟 WFQ 還比較像。前者主要是多了 eligible

另外目前核心中 EEVDF 的演算法是用平均的 vruntime 跟 vruntime 的差值去算 lag，lag < 0 才是符合的第一階段可能被挑選的任務
已知每個任務都維護自己的 vruntime ，runqueue 也會維護平均 vruntime
我在看書的時候就有一個疑問是
那為什麼每個任務還要額外去維護另一個參數 lag 值？
目前還沒真正看懂的部分

> 在面對雲端運算所需要的 bandwidth control (BWC)，CFS 無法保證 target latency 的缺點逐步浮現
todo

釐清 CFS 無法保證 target latency 的缺點跟 WFQ 缺點的 $lag$ 是 $O(n)$ 是否有關係

釐清 latency 跟 lag 的差異