CPU MLFQ 調度

MLFQ即多級反饋隊列調度。在給定時間片中，任務存在不同優先隊列之中等待被執行，MLFQ根據優先級去決定哪個任務在該時間片執行

Round Robin

Round Robin即RR，是基于時間片的輪詢調度算法。給每個任務分配一個時間片，當任務時間片用完之后，會中斷當前任務，切換到下一個

改變優先級的第一次嘗試

初始規則如下

1. 若任務A優先級高于任務B，則調度A
2. 若任務A、B優先級一致，則根據RR調度A、B

根據上述兩條規則，若存在任務C優先級低于A和B，那么C就會一直不被執行，導致饑餓。因此引入第三條規則

第四條規則則是考慮到對于需要高響應的任務多是短執行的，所以會頻繁讓出CPU，因此為了保證響應時間，就保持現有優先級

而對于CPU密集型，則不太需要高響應，所以可以降低優先級

3. 當新任務到達之后放置最高優先級隊列

4. 如果任務A運行了一個時間片都沒有主動讓出CPU（比如I/O操作），則優先級降低一級

   如果任務A在時間片用完之前，有主動讓出CPU，則優先級保持不變

在上面的嘗試中仍然存在以下問題

• 仍然存在饑餓問題。若存在大量短執行任務，就會導致長執行任務無法得到執行
• 被利用導致某些任務一直處于高優先級。

公平還是公平

為了解決饑餓問題，可以引入一個很簡單的規則

5. 系統運行S時長后，將所有任務放到最高優先級

這就確保所有的任務都會最終處于一個優先級中，那么所有任務即使是最低優先級的都有可能被調用，所以至少此時，眾生平等

不要被利用

在解決了饑餓問題之后，惡意利用還是存在。

這樣必須對規則4進行改變

4. 給每個優先級分配一個時間片，當任務用完該優先級的時間片后，優先級降一級

最終塵埃落定

最終規則如下

1. 若任務A優先級高于任務B，則調度A
2. 若任務A、B優先級一致，則根據RR調度A、B
3. 當新任務到達之后放置最高優先級隊列
4. 給每個優先級分配一個時間片，當任務用完該優先級的時間片后，優先級降一級
5. 系統運行S時長后，將所有任務放到最高優先級

流程如下

1. 新進程插入到最高優先隊列尾

2. 一段時間后，進程到達隊列頭并分配CPU

3. 如果進程在給定時間片內完成，將離開調度系統

   如果進程自愿放棄CPU執行，則會在再次就緒時，插入原放棄隊列尾部

   如果進程使用所有配額CPU時間，則會被搶占并插入到下一個較低隊列尾部

   低級別隊列CPU配額比高級別隊列低

調度器總是從高級別隊列頭開始選擇進程進行分配，在高級別隊列為空之后，才會接管低級別隊列。

進程在隊列的遷移總是插入到目標隊列尾部，并且進程在給定隊列級別只有一次完成任務的機會，然后就會被下放到較低級別的隊列

Linux CFS調度

CFS代表完全公平的調度器。CFS的設計理念是在真實硬件上實現理想的、精確的多任務CPU。CFS調度器和以往的調度器不同之處在于沒有時間片的概念，而是分配cpu使用時間的比例。例如：2個相同優先級的進程在一個cpu上運行，那么每個進程都將會分配50%的cpu運行時間。這就是要實現的公平

調度類

調度類是表示一種特定的調度策略和算法，定義了如何選擇下一個要運行的任務，如何將任務插入到運行隊列中，以及如何處理任務的喚醒和睡眠等

在Linux內核中有以下調度類

• CFS調度類(SCHED_NORMAL): 默認的調度類，用于大多數普通的非實時任務。它使用完全公平調度器（CFS）算法，以實現公平和高效的CPU調度
• 實時調度類: 用于實時任務
  • SCHED_FIFO: 先進先出。
  • SCHED_RR: 處于runqueue中的線程輪流獲取時間片
• Deadline調度類(SCHED_DEADLINE): 針對有明確截止時間要求的實時任務的調度類。它使用EDF（最早截止時間優先）算法和CBS（恒定帶寬服務器）算法，以確保所有的實時任務都能在截止時間之前完成
• Idle調度類(SCHED_IDLE): 優先級最低的調度類，只有當系統中沒有其他任何任務需要運行時，才會運行屬于這個調度類的任務。

核心結構

• vruntime: 表示進程在所有CPU的總執行時間

  $vruntime+=實際運行時間?1024/進程權重$

• runqueue: 每個CPU上的可運行進程隊列

• 基于時序的紅黑樹: 每個CPU上根據vruntime組織所有進程

CFS調度策略

常規調度分為

• SCHED_NORMAL: 用于常規任務的調度策略
• SCHED_BATCH: 運行長，能更好利用緩存，但損失響應性
• SCHED_IDLE: 并不是一個真正的空閑定時器調度器，以避免優先級反轉問題，防止機器死鎖。

其中CFS屬于SCHED_NORMAL

CFS調度利用紅黑樹優先調度執行總時間更低的，在每次時間片執行完會對執行的進程累加執行時間，并重新選擇最低執行時間的進程進行執行

這也就意味著執行越久，執行優先級越低。那么計算密集型執行優先級低，IO密集型執行優先級高

當然這樣的調度也會使得同一個進程連續執行多次，不過這也不是壞事，畢竟之前用的上下文還能接著用

SCHED_RR與SCHED_NORMAL對比

	sched_RR	Sched_normal
調度進程類型	實時進程	普通進程
時間片	靜態	動態。根據系統進程數量變化
下一個進程的選擇	從runqueue選擇下一個	從紅黑樹選擇vruntime最小的

CPU限額問題

配額機制限制了每個容器的攤銷CPU使用率，但它沒有限制任務在任何給定時刻可以使用多少個內核。相反，如果一個任務“想”在一個配額的時間片上使用更多的內核，它就會在短時間內使用多于配額的內核，然后進入節流狀態，也就是說基本上進入睡眠狀態，以保持它的攤銷內核使用量低于配額，這對于尾延遲來說是災難性的

比如垃圾回收器，可能在一次GC期間，所有這些GC線程將同時運行，迅速耗盡cpu配額，從而導致節流。由此產生的效果是，次秒級的GC暫停可能需要數秒的時間才能完成。

Ref

1. https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-mlfq.pdf
2. https://en.wikipedia.org/wiki/Multilevel_feedback_queue
3. https://github.com/torvalds/linux/blob/v5.10/Documentation/scheduler/sched-design-CFS.rst
4. https://arthurchiao.art/blog/linux-cfs-design-and-implementation-zh/
5. https://danluu.com/cgroup-throttling/