D-OS-Ch05iaa-vruntime

Virtual Clock (vruntime)

Introduction

在 proportional share scheduling 中每個 task 都被分配到一定比例的 CPU time，而 virtual clock 就是 CFS 為每個 task 維護的一個人工時鐘，它會記錄經過權重調整後此 task 已經使用的 CPU time

Implementation

$${\text{vruntime}}_i={\text{vruntime}}_i+\frac{{\text{weight}}_0}{{\text{weight}}_i}\cdot {\text{runtime}}_i$$

Variables

1. ${\text{vruntime}}_i$ 是第 $i$ 個 task 的 current virtual clock
2. ${\text{runtime}}_i$ 是實際上（real clock）第 $i$ 個 task 在此 time slice 跑的時長
3. ${\text{weight}}_0$ 是 base 權重
4. ${\text{weight}}_i$ 是第 $i$ 個 task 的權重

real clock

real clock 是真實的物理時間

Virtual Clock Rate

$$\text{Virtual Clock Rate}=\frac{\text{virtual clock}}{\text{real clock}}$$

當某 task 權重高，其 virtual clock rate < 1，此時 vruntime 增加的速度比 runtime 慢，也就是其比起低權重的 task 更能保持低 vruntime，如此一來這個 task 就更容易被 scheduler 選中來跑

反之亦然，task 權重低 virtual clock rate > 1，vruntime 增加速度快更不容易被 scheduler 選中來跑

CFS 每次會選擇 virtual clock 最小的 task 來跑