背景
任何排程器的主要責任是在所有希望使用排程器的執行緒之間，共用處理器時間的有限資源。在一般用途的作業系統中，系統會嘗試以公平的方式嘗試，確保所有執行緒都能接受某些進度。
我們的排程器是 LK 的排程器。因此，一開始我們採用最少的排程器實作方式，並在專案成長時加以擴充，滿足我們的需求。
設計
總覽
基本上，排程器會在機器中的每個邏輯 CPU 上執行。這些排程器會獨立執行，並使用 IPI (處理序間中斷) 來協調。但每個 CPU 會負責排程在其中執行的執行緒。請參閱下方的 CPU 指派作業，瞭解我們如何決定執行緒所在的 CPU，以及遷移的方式/時間。
每個 CPU 都有一組專屬的優先順序佇列。系統中每個優先順序等級各一個，目前是 32 個。請注意，這些是傳真佇列，不是資料結構，也稱為優先順序佇列。每個佇列中，都是待執行的執行緒的已排序清單。當新執行緒需要執行時，排程器只會查看包含執行緒且數量最多的佇列，從該佇列的前端彈出並執行該執行緒。詳情請參閱下方的優先順序管理，進一步瞭解如何決定執行緒應位於哪個佇列。如果佇列中沒有任何可執行的執行緒，會改為執行閒置的執行緒，詳情請參閱下方的「即時和閒置的執行緒」一節。
每個執行緒在獲選開始執行時，會獲派相同的時間片段大小 (THREAD_INITIAL_TIME_SLICE)。如果它使用了整個時間範圍，系統會在適當的優先順序佇列的結尾重新插入該方法。不過，如果先前執行作業中仍有部分時間片段，則會插入優先佇列的頂端，以便盡快繼續執行。再次校正時，只有在前一個時間片段的剩餘時間內才會執行。
排程器從優先順序佇列中選取新執行緒時，會將 CPU 的先佔計時器設定為完整時間片段，或是之前的時間片段的其餘部分。當計時器觸發時，排程器將停止在該執行緒上執行時，請將排程器新增至適當的佇列，選取其他執行緒，然後重新開始。
如果執行緒封鎖等待共用資源，則會從優先順序佇列中移出，並排入共用資源的等候佇列中。而在解除封鎖後，系統會把它重新插入到符合資格的 CPU 的適當優先順序佇列中 (CPU 指派)；如果仍有剩餘時間片段來執行，這項作業會新增至佇列前方，以便加快處理。
優先順序管理
系統會根據三個不同因素決定執行緒的有效優先順序，系統會根據有效優先順序決定要位於哪個佇列。
第一個因素是基本優先順序，也就是執行緒要求的優先順序。目前有 32 個級別，0 為最低級別，31 為最高級別。
第二個因子是優先順序提升。這是一個介於 [-MAX_PRIORITY_ADJ, MAX_PRIORITY_ADJ] 之間限制的值，用來偏移基本優先順序，以下情況會修改這個值：
如果執行緒解除封鎖，則在等待共用資源或睡眠時，即可提升 1 分。
當執行緒產生 (自願放棄控制) 或志工重新安排時，強化模式會減少 1，但上限為 0 (不會變成負值)。
當執行緒先佔且用完其整個時間片段時，執行緒會減少，但可能會變成負值。
第三個因素是沿用的優先順序。如果執行緒可控制共用資源，且封鎖了較高優先順序的另一個執行緒，系統會在該執行緒的優先順序內暫時提升該執行緒，以便快速完成作業，並且讓優先順序較高的執行緒能夠繼續使用。
執行緒的有效優先順序是繼承的優先順序 (如果有)，或是基本優先順序再加上提升。當這個優先順序發生變化時，由於任何因素有所變更，排程器會將工作移至新的優先順序佇列，並重新安排 CPU。允許其控制目前優先順序最高的工作，或允許其控制狀態是否不再最高。
這個系統的用意是確保能快速提供互動式執行緒。這些執行緒通常是直接與使用者互動，並導致使用者感知延遲的執行緒。這些執行緒通常不太耗時，而且大部分時間都會遭到封鎖，正在等候其他使用者事件。因此，系統會優先提高解除封鎖，而執行大部分處理作業的背景執行緒，則會針對使用整個時間片段取得優先度懲處。
CPU 指派與遷移
執行緒可以用 CPU 相依性遮罩來要求執行要於哪些 CPU 執行的 CPU。這個 32 位元遮罩，其中 0b001 為 CPU 1，0b100 為 CPU 3，0b101 為 CPU 1 或 CPU 3。系統通常會遵循這個遮罩，但如果其要求的 CPU 全都為停用中，就會指派給其他 CPU。另外值得注意的是，如果它「固定」為 CPU，且其遮罩只包含一個 CPU，而該 CPU 不再使用，則執行緒會一直停止提供服務，直到 CPU 再次啟用為止。詳情請參閱下方的「CPU 啟用」一節。
選取執行緒的 CPU 時，排程器會依序選擇：
如果選擇「閒置」且位於相依性遮罩中，選取範圍的 CPU。
執行緒上次執行時的 CPU (如果為「閒置」及相依性遮罩)。
相依性遮罩中的任何「閒置」 CPU。
執行緒上次執行時的 CPU (如果狀態為使用中且位於相依性遮罩中)。
如果選擇的 CPU 是相依性遮罩中唯一的 CPU，或遮罩中的所有 cpus 都未啟用，則選取該 CPU。
相依性遮罩中的任何使用中的 CPU。
如果執行緒在不在其相依性遮罩的 CPU 上執行 (由於上述情況 5)，排程器會在每次執行緒遭到先佔、產生或自願重新排程時，嘗試修正此執行緒。此外，如果執行緒變更其相依性遮罩，排程器可能會進行遷移。
每次執行緒返回正在等待共用資源或休眠中，且需要指派優先順序佇列時，排程器都會使用上述邏輯重新評估執行緒的 CPU 選擇，然後可能會移動執行緒。
CPU 啟動
當 CPU 停用時，關閉並從系統中移除，排程器會將所有執行中的執行緒轉換至其他 CPU。唯一的例外是「固定」的執行緒，也就是在相依性遮罩中只有停用 CPU 的執行緒。這些執行緒會放回執行佇列中，並在 CPU 重新啟用前停止提供服務。
CPU 重新啟用後，由於上述規則的關係，等待的固定執行緒和執行緒在非相依性 CPU 上執行時，其 CPU 排程器應該很快就會完成遷移。目前沒有主動重新平衡執行緒至新喚醒的 CPU，但由於閒置頻率應該較高，系統應會因為上述的 CPU 指派與遷移邏輯而進行遷移。
即時與閒置執行緒
這類特殊執行緒的處理方式略有不同。
閒置的執行緒會在沒有其他執行緒可以執行時執行。每個 CPU 上都有一個 1 個，它位於優先順序佇列之外，但實際上是在優先佇列中 -1。用於追蹤閒置時間，可供平台實作用於低耗電模式。
即時執行緒 (標有 THREAD_FLAG_REAL_TIME 標記) 不必先佔即可執行，且會執行到封鎖、產生或手動重新排程為止。