# 2025-04-01 問答簡記

## [TOP500](https://top500.org/)
自 2017 年起，全球最強大的前 500 大超級電腦皆採用 Linux 系統，市佔率達 100%。1998 年 Linux 首次進入 TOP500 超級電腦排行榜。

## 軟體工程師的供需變化

從 2025 年 1 月的美國就業趨勢圖來看，若以疫情前的水準 (100) 作為基準線，軟體工程師的需求指數僅約 70，不但尚未回到疫情前的水平，甚至還遠低於其他職類。這是否意味著軟體工程師就沒有未來呢？其實不然。

在人工智慧技術快速發展的背景下，軟體工程師的生產力出現更明顯的兩極化：資深工程師能夠透過人工智慧大幅提升效率，如虎添翼；相較之下，若企業花費高額薪資 (如年薪 10 萬美元) 僱用經驗有限的初階工程師，成本效益就顯得不夠理想。因此，科技公司更傾向投資人工智慧來強化資深工程師的生產力。

更根本的變化是，AI 逐漸降低軟體開發的門檻。過去得靠本科、專業訓練與團隊磨合才能完成的專案，現在許多非典型開發者——從設計師到行銷人員——都能靠 AI 工具撰寫自動化腳本、建構原型、部署服務。當軟體開發成為一種「數位通識」，專職工程師的職缺反而遭到擠壓。

這場技術變革，不只改變誰能寫程式，更改變「誰值得被雇用來寫程式？」。

## 當創作變得「太容易」
> 改寫自[午夜翻牆](https://www.facebook.com/rrroundmidnight/posts/pfbid02AJpHjt8Pr2wDhG2vRxMtasmmFXAqNDj2SXDBGdjJCPrVm3CbwBcsmiDVkYkRHPJsl)

這樣的故事不只發生在工程界，也在文化創作圈中不斷重演。

當 OpenAI 推出能生成吉卜力風格圖像的新版本 ChatGPT-4o，網路上一片驚嘆：「好像」、「好美」、「比原作更吉卜力」。但，這樣的「像」是怎麼來的？宮崎駿與吉卜力工作室花數十年構築的美學體系，如今被拆解為大語言模型與相關素材，變成一份又一份免費的訓練樣本，成為科技公司獲利的基石 —— 且無須支付持續的授權費用。

這讓人想起「[血鑽石](https://zh.wikipedia.org/zh-tw/%E8%A1%80%E9%91%BD_(%E9%9B%BB%E5%BD%B1))」的隱喻：非洲礦工冒著生命危險挖掘寶石，最後的利潤卻全流向跨國財團。同樣的，藝術家的手稿與音樂人的創作，如今在數位時代被視為「可標註、可量化、可運算」的素材，一經 AI 加工，即變成平台可販售的產品，藝術成商品，創作者卻不見得分得任何紅利。

人們常說，AI 正掀起一場新的「創作民主化」浪潮，人人都能成為藝術家、音樂人或開發者。但這種民主化，若建立在對過去作品的無償攫取上，本質上其實是另類的資本壟斷。它不是開放創作，而是將創作過程自動化、平台化，讓少數科技公司控制大多數內容的生產與分發。

正如音樂 YouTuber Rick Beato 所指出的：
>「音樂變得太容易製作、太容易消費。」

當一切變得「隨手可得」，我們是否也失去對創作過程的敬意？當創作不再需要投入時間、技巧與情感，它還能留下什麼價值？

技術無罪，但若它只服務於少數人的權力，那麼我們需要的不只是更好的模型，而是更公平的制度設計。

$\to$ [當 AI 用一秒超車你的一萬小時，程式老鳥的生存之道](https://blog.darkthread.net/blog/10k-hours-vs-ai/)

## 關稅
> [出處](https://www.facebook.com/windhong/posts/pfbid032XznMkbsd9u7fugKXF4qN3gF4Go421qJPCzvwSHxit4B64XojnVww8boLymGbMCUl)

解讀 [Reciprocal Tariff Calculations](https://ustr.gov/issue-areas/reciprocal-tariff-calculations)：

互惠關稅是為了平衡美國與各貿易夥伴之間的雙邊貿易赤字所計算出的關稅稅率。此一計算假設貿易赤字持續存在，是由於關稅與非關稅因素共同造成，使得貿易無法自然達成平衡。關稅透過直接抑制進口來發揮作用。互惠關稅稅率介於 0% 至 99% 之間，未加權平均為 20%，以進口金額加權後的平均為 41%。

設定以下：
- $\tau_i$：美國對第 $i$ 國課徵的關稅稅率
- $\Delta\tau_i$：關稅變動量
- $\varepsilon < 0$：進口需求對進口價格的彈性 (價格彈性)
- $\varphi > 0$：關稅轉嫁至進口價格的程度 (轉嫁率)
- $m_i > 0$：來自第 $i$ 國的進口總額
- $x_i > 0$：對第 $i$ 國的出口總額

則因關稅變動所造成的進口減少量為：
$$
\Delta \tau_i \cdot \varepsilon \cdot \varphi \cdot m_i < 0
$$

在可忽略匯率調整與總體均衡效果的假設下，使雙邊貿易達成平衡 (即出口等於進口) 的互惠關稅變化量應滿足：
$$
\Delta \tau_i = \dfrac{x_i - m_i}{\varepsilon \cdot \varphi \cdot m_i}
$$

結果發現
- 計算出的關稅稅率範圍：0% 至 99%
- 赤字國家的未加權平均：50%
- 全球未加權平均：20%
- 赤字國家依進口加權平均：45%
- 全球依進口加權平均：41%
- 標準差介於 20.5 至 31.8 個百分點之間

為何不設定 $\varepsilon \cdot \varphi = 2$ 呢？如此一來，$\frac{(x - m)}{m}$ 再除以 2，不就等同於 $\frac{(x - m)}{2m}$ 嗎？從形式上來看，這確實是數學上的等價轉換，但這種處理方式更像是心理操作策略：先丟出一個看起來很高的關稅計算式，例如 $\frac{(x - m)}{m}$，再主張「我們已幫你減半」，藉此營造折衷與合理的印象。

然而，這種做法模糊模型設定中真正關鍵的部分：參數 $\varepsilon$ (價格彈性) 與 $\varphi$ (轉嫁率) 的估計與設定。這些參數本應該建立在實證分析與理論支持，若直接指定而未經合理推導，勢必會引發專業領域的質疑。如同預算刪減，確實有些支出可以調整或刪除，但應有客觀依據與評估過程，而非憑空假設或外行判斷。

根據中華經濟研究院的分析，當初是根據財政部長提出的多個因素進行評估，認為對等關稅的推導牽涉複雜變數與模型，是一項需要縝密作業的大工程。因此曾預測若要在 4 月 2 日前提出方案，美方可能傾向採用統一稅率而非個別設定。但如今美方對台灣的「對等關稅障礙」計算：2024 年台灣對美貿易順差為 739 億美元，美國自台灣進口金額為 1162 億美元，則 $739 / 1162 \approx 64\%$。隨後表示「出於善意」減半處理，因此設定為 32%。若以 2023 年資料估算，當年對美順差為 478 億美元，進口金額為 877 億美元，則 $478 / 877 \approx 58\%$，對應的關稅為 29%。

從中可以看出，美方策略相當清晰：
1. 想避免被課高關稅，就應將製造移回美國本土
2. 若無法移轉，則應展開協商，尋求減少對美順差的方式

這項新關稅機制的主體公式，其實就是「該國對美貿易逆差 ÷ 美國自該國進口額 ÷ 設定的參數」。目前這個參數被設定為 2，目的是使雙邊貿易達成平衡。經濟學界曾評估此類計算需考慮關稅、非關稅障礙、匯率、稅制與其他制度差異，這不再是什麼最適關稅或比較利益的經濟理論，而是赤裸的結果導向談判。

美國憑藉二次世界大戰後的地緣優勢、軍力與美元霸權，成為全球最終消費市場。從日本到中國，多數出口導向國家都是靠賣給美國而壯大。這種結構也讓美國長期承擔巨額逆差，川普所謂的「不公平」正是針對這點：你們賺飽，卻沒給出對等的代價。川普不談多邊協定，不信國際組織，只相信逐案交易。

這也讓台灣走上談判桌成為必然。在美國是最大出口市場的情況下，我們不可能置身事外。主動應對，比被動防守來得現實。擴大採購能源、農產品，換取關鍵產業空間，是務實起點。像台積電赴美設廠，就是用技術與資本換取市場安全。這類交換未來恐將常態化。

川普沒有發動熱戰，而是挑起他熟悉的全球商戰。透過關稅與談判，重構全球貿易秩序，讓人才、資金、技術逆流回美國。亦即第三次世界大戰的樣貌：用交易取代戰火，用結果重劃權力，而中國，顯然是這場新冷戰的主戰場。

除台灣外，這幾年台資部分轉往的國家如越南，其對等關稅為 $46%$，泰國為 $36%$。加上日本與韓國的稅率低於台灣，若這項稅制正式實施，可能對台灣的電子與出口製造業帶來顯著壓力，經濟成長亦將面臨下行風險。

台灣 2024 年對美國出口的主要貿易品類及其佔比:
| 項目 | 貿易額 | 比重 |
|-----|-------|-----|
| 自動資料處理設備及其零組件 <br> (如筆電、伺服器、硬碟) | 514.94 億元 | 46.24% |
| 積體電路 (晶片) | 74 億元 | 6.65% |
| 機械及電機設備 | 524 億元 | 45% |
| 其他產品 | - | < 3% |

## 研究指數函數
> [出處](https://www.facebook.com/jeffcheng2020/posts/pfbid0jXcVmiNhs3xc6MKkbkhLv9azpEjbHx3Z81AiSA95Am8Av35a5nFwLejDdHNUkLBql) / [報導](https://www.mirrormedia.mg/story/20250402edi023)

原來張安樂和區老師討論指數函數，教材: [歐拉數 $e$：描述連續變化的基石](https://hackmd.io/@sysprog/S1lBrHrp1e)

## 議題追蹤
[2025-03-18 問答](https://hackmd.io/EFs_Nfs6TOmIA5ldA_tZsQ)

[2025-03-25 問答](https://hackmd.io/QISdbcjUShy1Be48NHVqaw)

## 作業回顧

### HenryChaing

理由一 : 為了 Fairness 。 不會被高優先權的行程霸佔, `waiting` 結束的行程會返回 `ready` ，而不是直接返回 `running` 。
理由二 : 有機會動態調整 priority （例如 interactive 性質的任務會被 bonus ）
理由三 : 考慮 Liveness 或其他排程器目標 (詳見第二章)，降低其他任務等待時間

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

[Generalized Processor Sharing](https://www.cs.utexas.edu/~lam/396m/papers/PG1993.pdf)

沒有區分 running 及 ready 。 但有區分 Interruptible (打斷) 及 Uninterruptible ，

### Objectives of the sheduler

- [ ] Response time & Throughput

在設計排程器時，有很多重要的指標可以考量，首先課本提到的第一個指標是 *response time* ，而舉的例子是文字編輯器這項任務 (task) ，以使用者的角度來說，會希望每次輸入都能立即得到回應，也就是希望這個任務具有 *interactive* 的性質 ; 以 CPU 排程器的角度來看，則是會設計與使用者互動的程式會有較高的優先權。

但是以互動性為設計的排程器會對另一個衡量指標帶來衝擊，也就是排程器最基礎的衡量指標 *throughput* 。會帶來衝擊的原因是因為互動性的任務往往會產生大量的 context switch ，這也代表著處理器要時常因為任務的切換而處於閒置的狀態，間接造成吞吐量下降。

- [ ] Fairness & Liveness

*Fairness* 也是排程器的衡量指標之一，它代表著每個任務都應該被分配到一定比例的執行時間，並且相同優先權的任務分配到的比例必須相同。比較著名的公平排程器模型例如 generalized processor-sharing (GPS) ，它將數個處理器模擬成處理器資源，並且按比例分配給每個任務，讓每個任務彷彿有一個專屬的虛擬處理器。

最後是 *Liveness* ，這項指標目的是要防止 starvation，只要是處於 Running/Ready 狀態的任務，都能在足夠長的時間內取得處理器資源。

$\to$ [作業系統術語及概念](https://hackmd.io/@sysprog/linux-concepts)

美國威斯康辛大學教授 Remzi H. Arpaci-Dusseau 和 Andrea C. Arpaci-Dusseau 撰寫的開放存取式教科書《[Operating Systems: Three Easy Pieces](https://pages.cs.wisc.edu/~remzi/OSTEP/)》，在〈[The Abstraction: The Process](https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-intro.pdf)〉一章提到:
> HOW TO PROVIDE THE ILLUSION OF **MANY CPUS**?
Although there are only a few physical CPUs available, how can the OS provide the illusion of a nearly-endless supply of said CPUs?

作業系統藉由虛擬化 (virtualize) CPU 資源來達到在單一處理器實作出有如同時多個程式執行於各自的處理器之上的假象 —— 其中關鍵的手法就是分時多工 (time-sharing)，而 Unix 的第一篇論文《[The UNIX Time Sharing System](https://people.eecs.berkeley.edu/~brewer/cs262/unix.pdf)》，由 Ken Thompson 和 Dennis Ritchie 在 1973 年 10 月 ACM [Symposium on Operating Systems Principles](http://www.sosp.org/) (SOSP) 中提出，該論文在 1974 年 7 月的 [Communications of the ACM](https://cacm.acm.org/) 發表，正是採用分時多工作為主題。

- [ ] Real-Time vs. Non-RT

排程器還有一個指標是可以處理即時任務 (Real-Time task) ，即時任務的特點在考慮了截止時間 (deadline) 這項因素。並且以 Real-Time 為導向的排程器會讓這些即時任務有較高的優先權。其中即時任務又分成 hard real-time 以及 soft real-time 的任務，前者對截止時間有著絕對的要求，必須在截止時間前完成該任務，否則意味著系統的失敗; 後者也注重截止時間，但任務的失敗只會影響到系統的服務品質。

在現實當中的 soft real-time 任務常見於我們日常生活當中。例如我們要進行線上會議，會非常在意聲音與影像的同步性，一旦這些任務沒有在一定時間內完成，就會造成系統服務品質的下降。另外還有智慧型手機所使用的人臉辨識以及指紋辨識，這些有包含個人隱私或是安全議題的資料若無法在一定時間內處理，也會造成使用者的風險。因此基於這些任務 RT 顯然成為了排程的目標之一。

與之相對的概念稱為 Non-real-time tasks (簡稱 non-RT)，例如批次任務 (batch-task) 以及與使用者互動的任務等，這些任務分別在乎吞吐量以及反應時間，而非截止時間。其中批次任務對吞吐量相當重視，因此會盡量減少搶佔發生的次數。

$\to$ [Linux 核心設計: `PREEMPT_RT` 作為邁向硬即時作業系統的機制](https://hackmd.io/@sysprog/preempt-rt)

- [ ] Power Efficiency

這項指標的目的在減少系統使用的電量，不論是桌機或是伺服器都有這項要求。以桌機來說會提高 idle-task 的優先權，並且在以 idle-task 為主的時段降低 CPU 的功耗; 但是以伺服器來說，必須同時在意吞吐量以及能耗，因此伺服器 CPU 排程器的策略是會提高 CPU 密集任務的優先權，優化快取的使用效率以及降低行程間通訊的成本，藉此減低 CPU 等待資料的時間。

## Linux CPU 排程器設計

透過上一小節可以得知 CPU 排程器需要處理許多不同類型的任務，因此要設計一個通用於各項任務的排程器是很困難的，因為某些任務彼此的需求會相衝突，例如與使用者互動的任務以及 CPU 密集的任務。因此在 Linux CPU 排程器的設計當中，我們將不同性質的任務分成各項 *scheduling classes*，每個類別除了有不同排程策略，類別彼此之間也有層級以對應不同的優先權。每當創造新的任務時，必須標明它所屬的類別。


### Classes and policies

每個類別都有其對應的 *scheduling policies* ，這樣的設計有助於類別去封裝對應的排程演算法，並且讓使用類別的核心程式碼無法得知現在正在使用的策略。這項概念由 Linux CPU 排程器先驅 **Ingo Molnar** 所提出並落實在 Linux 核心當中。

$\to$ [Modular Scheduler Core and Completely Fair Scheduler](https://lwn.net/Articles/230501/)

### Scheduling classes

目前 Linux 核心採用了 6 個類別，如上表格 Table 2.1 所呈現。其中優先權最高的是 stop_sched_class ，它負責停用 CPU 的功能以及任務在不同 CPU 之間的移轉。優先權最低的是 idle_sched_class ，會安排到這個類別的任務表示 CPU 當前沒有任務可以執行。 再來是 dl_sched_class 這個對應到之前提到的 Hard Real-Time 任務排程，使用的是 EDF [(Earliest Deasdline First)](https://en.wikipedia.org/wiki/Earliest_deadline_first_scheduling) 策略。

接著是 rt_sched_class ，對應到 Soft Real-Time 的任務排程，使用的策略是接下來會提到的 SCHED_FIFO 以及 SCHED_RR 。最後是 fair_sched_class ，也就是一般任務的處理， 分成 SCHED_NORMAL , SCHED_BATCH 兩項策略來應付使用者互動程式以及 CPU 密集的程式。

::: success
這個類別的實作可以參考到課本第 3.1 節，可以發現每個類別都必須實作自己的函式例如 `enqueue_task`, `yield_task` ，這個對應到 lab0-c 所提到的 [function hooking](https://en.wikipedia.org/wiki/Hooking) 。
:::

### Scheduling policies

在 Linux 提供的這幾個排程策略中，都允許高優先權的任務進行搶佔，因此接下來也會以搶佔的觀點分析排程策略。首先介紹 SCHED_FIFO 以及 SCHED_RR 排程策略，這兩者唯一的差別在於後者有 timeslices ，固定時間得要切換任務。因此這裡只介紹 SCHED_FIFO 排程策略，

### Task Lifetime


- [ ] `TASK_RUNNING`
在這之中又分成 **Running — on a core** 以及 **Running - wants a core** ，其中前者是已持有處理器資源的行程，後者則是等待中。這兩者狀態的轉換取決於 `schedule()
` 以及 `yield()` 或是搶佔，並且都會觸發 context_switch ，讓候選者得到處理器資源。

之所以不存在 TASK_READY ，一部分原因是 Linux 核心初期關於 CPU 排程器的設計將 ready 以及 running 的任務一併放在 running_queue 當中，因此不須用另一個狀態來表示行程，排程器依然能正常排程。

- [ ] `EXIT_DEAD`, `EXIT_ZOMBIE`
當行程終止時，行程會處於 **EXIT_ZOMBIE** 的狀態，處於這個狀態的行程不會運作，但會保留行程鎖匙有的資源給親代行程使用。當親代行程呼叫 `wait()` 時，子行程才會進入 **EXIT_DEAD** 狀態並且釋放所持有的資源。反之若親代行程沒有呼叫 `wait()` 而進入終止狀態，這時子行程會變成 orphan 狀態，在 Linux 的設計當中會將它轉換給 **init** 行程管理，並定期回收這些 orphan 子行程。

- [ ] `TASK_INTERRUPTIBLE`, `TASK_UNINTERRUPTIBLE`
當行程需要進行 I/O 或是等待事件發生時，就會轉換成 **TASK_INTERRUPTIBLE** 或是 **TASK_UNINTERRUPTIBLE** 狀態，這二個狀態的差別在於是否會接收並處理 signal，前者若有其他行程發出 signal ，則會立即返回運行狀態，而後者則是一定要等到特定事件發生。二者都要藉由 `try_to_wake_up()` 函式離開等待狀態。

$\to$ [Linux 核心搶佔](https://hackmd.io/@sysprog/linux-preempt)

Linux 行程狀態與恐龍書的差異：將 ready 整合到 running 當中，並且 waiting 有區分成可以打斷以及不可打斷的狀態，並且在終止階段有考慮到並行程式因此採納更多的機制作處理。

## 案例探討：異質多核排程
[Cgroup-Aware Load Balancing in Heterogeneous Multi-Processor Scheduler](https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7763425) (2016 年)

Arm 發展出稱為 [big.LITTLE](https://en.wikipedia.org/wiki/ARM_big.LITTLE) 的高效能異質多核處理器架構，其中 big 代表高效能核心，而 LITTLE 則為低功耗核心 (口訣：該大的不大，該小的不小)。此架構需要個有效率的排程器來在兩種核心間遷移行程，以在維持高效能的同時，降低功耗。現有的 HMP (異質多處理) 排程器對所有行程使用相同的遷移門檻，難以有效達成此目標。

本論文提出針對前景與背景行程使用不同的遷移門檻的 CPU 排程，藉由模擬與實驗，本方法在不降低效能的前提下，可減少約 9% 的耗電量。

Arm 推出的 big.LITTLE 架構結合兩種核心：高效能但高功耗的 big 核，與低效能但低功耗的 LITTLE 核。此架構運行於 Linux 的 HMP 排程機制之上，而 HMP 則建構在 CFS 排程器。

在 HMP 排程中，系統根據可執行時間與等待時間來評估行程負載。新建立的行程預設會分派到 LITTLE 核，以節省能源。若執行時間增加，則遷移到 big 核；反之，負載降低則遷回 LITTLE 核。這種遷移策略讓 HMP 主要貢獻為降低功耗，而非單純提升效能。

Linux 中行程可依照用途分為兩類：
- 前景行程：與使用者互動，須具備即時回應能力；
- 背景行程：如網路或服務管理等，對反應時間要求較低。

行程類型可於執行期間動態改變，例如使用者切換 App 時，前景行程轉為背景行程。作業系統通常會分配較多資源給前景行程，而背景行程則較少。

目前的 HMP 排程器對所有行程設定統一的遷移門檻，且在執行期間無法動態調整。論文提出以 [cgroups](https://man7.org/linux/man-pages/man7/cgroups.7.html) 為基礎、區分行程種類並設定個別門檻的手法，改善能源效率與系統反應能力。

### HMP 排程運作方式
HMP 支援「切換模式」與「多核並行模式」，後者允許 big 與 LITTLE 核同時啟動。Linux HMP 排程器定期追蹤每個行程的可執行時間，並透過類幾何級數的方式加權歷史執行片段。

以時間區段（約 1 毫秒）為單位，最新區段權重最大，過去越久權重越低。此方法可動態反映行程近期負載狀況。

### 行程放置與門檻策略
當行程負載超過「上遷移門檻」，即從 LITTLE 遷移到 big；若低於「下遷移門檻」，則從 big 遷回 LITTLE。雙門檻設計可避免頻繁遷移所造成的額外開銷。

但若行程負載長時間維持在門檻附近，可能導致 suboptimal 核心分配。因此，動態門檻調整與類型感知的排程策略將能改善此問題。

### Cgroup 機制
Cgroup（控制群組）為 Linux 核心提供的機制，可將行程分組並限制其資源使用。Android 使用 Cgroup 來區分前景與背景行程，並限制背景行程的 CPU 使用比例（如 5%）。這項特性可被排程器利用，而無需額外開銷。

### Cgroup 感知排程
透過 Android 的 AMS（Activity Manager Service），系統可於行程狀態變更時通知核心，並調整其 Cgroup 分類。CFS 本身無法依行程優先度動態給予更多資源，因此需藉由 Cgroup 控制背景行程的資源比重。

然而，在現有 HMP 機制下，即使背景行程使用率提高，也可能被遷移至 big 核，導致資源競爭與耗電量增加。

為此，本文提出使用不同門檻值的 Cgroup 感知排程策略：
- 前景行程門檻設為：上 700，下 256
- 背景行程門檻設為：上 800，下 512（較高，避免遷徙）

此方式使背景行程更常駐於 LITTLE 核，而前景行程有更高機率分派到 big 核，提高互動性並降低不必要的功耗。

### 遷移模型：泊松分佈
> [談 Poisson Process](https://episte.math.ntu.edu.tw/articles/mm/mm_02_4_01/)

Poisson 分佈是種離散機率分佈，用於描述在固定時間間隔內，事件以固定平均發生率獨立出現的次數其機率密度函數 (PDF) 與累積分佈函數 (CDF)如下：
$$
P(K = k) = \frac{e^{-\lambda T} (\lambda T)^k}{k!}
$$

$$
F(K \leq k) = \sum_{i=0}^{k} \frac{e^{-\lambda T} (\lambda T)^i}{i!}
$$

其中：
- $K$：在時間 $T$ 內發生的事件次數（此處為行程遷移次數）
- $\lambda$：平均事件發生率（平均每單位時間的遷移次數）
- $T$：觀察時間長度

在此排程器模型中，K 被用來表示在單位時間內 big ↔ LITTLE 的遷移次數。假設某行程的遷移行為遵循 Poisson 分佈，則我們可以根據其平均遷移率 $\lambda$ 預測遷移次數機率。
- 當 $\lambda$ 增大時，在固定 $k$ 的情況下，遷移發生的機率 $P(K=k)$ 提高
- 這意味著：遷移門檻設得越低，平均遷移率 $\lambda$ 越高，行程越常被遷移
- 相反地，提高背景行程的遷移門檻值相當於降低 $\lambda$，從而降低不必要的遷移次數與功耗

看出 $\lambda$ 越大，分布越向右偏移，代表高遷移頻率。調整 $\lambda$ 可視為一種「控制遷移頻率」的手段，進而改進能源效率。

遷移次數 (k) 的機率分佈 P(K=k)
  ^ P(K=k)
  |
  |       .--.
  |      /    \
  |     /      \   <-- 低 λ (高門檻值 / 不易遷移)
  |    /        \      - 遷移次數集中在低位
  |   /          \     - 潛在風險: 反應慢, 任務滯留
  |  *------------*----
  | ............... / \ ..............................
  | .            /   \           .--.   <-- 高 λ (低門檻值 / 易遷移)
  | .           /     \         /    \    - 遷移次數分佈更廣, 平均更高
  | .          /       \       /      \   - 潛在風險: 遷移開銷大
  | .---------*---------*-----*--------*--
  |__________________________________________> k (單位時間內遷移次數

## 遷移狀態模型：馬可夫鏈
本文進一步使用馬可夫鏈來建模行程於 big 核與 LITTLE 核之間的遷移行為。狀態定義如下：
- S~1~：行程駐留於 LITTLE 核
- S~2~：行程駐留於 big 核

轉移機率如下：
- p~1~：從 LITTLE 遷移至 big
- p~2~：從 big 遷移至 LITTLE

若行程負載未超過上門檻，則留在 LITTLE；若負載未低於下門檻，則留在 big。

馬可夫鏈的轉移矩陣 $P$ 定義如下：
$$
P = \begin{bmatrix}
1 - p₁ & p₁ \\
p₂ & 1 - p₂
\end{bmatrix}
$$

給定初始狀態分佈，經過足夠多次轉移後，系統會趨近穩態分佈 $\pi$，即：
$$
\pi P = \pi
$$

以現有 HMP 排程器為例，從實驗中觀察到的遷移矩陣為：
$$
P_{\text{base}} = \begin{bmatrix}
0.645 & 0.355 \\
0.744 & 0.256
\end{bmatrix}
\Rightarrow
\pi_{\text{base}} = [0.676979 \quad 0.323021]
$$

這表示：在穩態下，行程有約 67.7% 的時間待在 LITTLE 核，32.3% 的時間待在 big 核。

應用所提的 Cgroup 感知排程（C-A）後，其轉移機率矩陣變為：
$$
P_{\text{C-A}} = \begin{bmatrix}
0.688 & 0.312 \\
0.723 & 0.277
\end{bmatrix}
\Rightarrow
\pi_{\text{C-A}} = [0.698551 \quad 0.301449]
$$

啟發：
- 行程駐留在 LITTLE 核的比例提升至近 70%，在 big 核的比例下降
- 這清楚顯示：所提方法成功透過提升背景行程門檻值，降低其進入高耗能 big 核的機率，從而達到節能目的

這二個模型（泊松分佈與馬可夫鏈）不僅提供排程行為的數學分析工具，也讓系統設計者能依據統計模型精確地調整遷移政策、門檻參數與資源分配策略。

## 案例探討: [The Linux Scheduler: a Decade of Wasted Cores](https://dl.acm.org/doi/pdf/10.1145/2901318.2901326)

Linux 核心中的 Completely Fair Scheduler（CFS，已被 EEVDF 取代）實作 [Weighted Fair Queueing](https://en.wikipedia.org/wiki/Weighted_fair_queueing)（WFQ，加權公平佇列）排程策略，其主體理念是將處理器資源依照執行緒的權重分配，以達到加權 fairness。

在這個模型中，每個執行緒 $i$ 被分配一個正數權重 $w_i$，此權重來自於 [nice 值](https://man7.org/linux/man-pages/man2/nice.2.html)的轉換。`nice` 值越小，對應的優先順序越高 (口訣：人善被人欺)，也就是 $w_i$ 越大。WFQ 的理論依據來自一種稱為 Ideal Fluid Model 的概念：假設處理器可同時執行所有可運行的執行緒，每個執行緒 $i$ 在任一時間點 $t$ 所獲得的服務速率 $r_i(t)$，與其權重 $w_i$ 成正比。

設 $R$ 為處理器的總服務速率（例如單核系統中 $R = 1$），而 $A(t)$ 是時間 $t$ 當下所有處於可運行狀態的執行緒集合。則所有可運行執行緒的總權重為：
$$
W(t) = \sum_{j \in A(t)} w_j
$$

根據理想模型，執行緒 $i$ 在時間 $t$ 所應得的處理器資源比例為：
$$
r_i(t) = \frac{w_i}{W(t)} \cdot R
$$

若將 $R$ 正規化為 1，則簡化為：
$$
r_i(t) = \frac{w_i}{W(t)}
$$

不過，真實的處理器一次僅能執行一個執行緒，因此需透過離散地安排每次輪轉的執行緒，來模擬上述連續模型。WFQ 的實作方式之一，就是引入「虛擬時間」的概念，以追蹤每個執行緒在理想模型中理應獲得的服務量。在 CFS 中，這個概念以每個執行緒的 virtual runtime (`vruntime`）實作。

對任一執行緒 $i$，當它實際執行一段時間 $\Delta t$ 時，CFS 不直接將這段時間加到它的 `vruntime` 上，而是以其權重為基礎進行標準化：
$$
\Delta \text{vruntime}_i = \frac{\Delta t}{w_i}
$$

CFS 實作上實際採用的公式會進一步乘上一個參考值比例（例如將 $w_i$ 與預設優先權之權重 $w_0$ 做比），但基本原則仍然是：權重越大，`vruntime` 累積速度越慢。整體的 `vruntime` 會持續累積：
$$
\text{vruntime}_i(\text{t+Δt}) = \text{vruntime}_i(t) + \Delta \text{vruntime}_i
$$

排程器在每次決策時，會選擇 `vruntime` 最小的可運行執行緒來執行，即：
$$
k = \arg\min_{j \in \text{Runnable}} \text{vruntime}_j
$$

這樣的設計自然導向加權 fairness。對於具有較大權重 $w_i$ 的執行緒而言，在相同的實體執行時間內，它的 `vruntime` 增加得比較慢，因此會更頻繁地被挑選執行；而權重較小的執行緒則累積得快，在 fairness 考量下會較少被選擇。透過這樣的機制，CFS 能夠近似達成理想模型中的資源分配關係：
$$
r_i(t) = \frac{w_i}{W(t)} \cdot R
$$

這正是 CFS 的 fairness 想法：以最少的狀態資訊與簡單的機制，模擬出連續模型中「按權重分配資源」的行為。

當基於 `vruntime` 的公平性排程機制被延伸應用到現代的多核心架構 ──尤其是在具備 NUMA、階層式快取、多層 scheduling domains/groups 與複雜負載均衡策略的系統中 ── 為了維持理想的加權公平性，同時兼顧 locality、降低同步與通訊成本，以及節能效能的需求，Linux 核心必須引入大量啟發式規則 (heuristics) 與分層邏輯以輔助決策。然而，這些額外的邏輯層級本身也可能成為 fairness 與效率的瓶頸。

〈[The Linux Scheduler: a Decade of Wasted Cores](https://dl.acm.org/doi/pdf/10.1145/2901318.2901326)〉揭露的 *Group Imbalance* 錯誤指出：CFS 在評估是否需要進行負載重分配時，所依據的「負載」指標 ── 它結合行程權重、CPU 使用率、autogroup 層級資訊等 ── 有時會失準。系統可能顯示二個 CPU 群組的「平均負載」相當平衡，但實際上，一組中仍有閒置核心，而另一組內的執行緒正在排隊等待排程。

CPU 排程器的負載均衡策略具有分層結構，其決策流程涉及：在哪個層級啟動平衡操作？基於哪些條件判定是否需遷移行程？哪些核心或節點之間可以參與平衡？這些層次化邏輯若有缺陷，會導致即便整體系統存在嚴重的不均（例如某些核心完全閒置），排程器也可能錯過啟動均衡行動的時機，或無法在適當的範圍內進行修正。這類問題可見於如 Scheduling Group Construction 錯誤、或 Missing Scheduling Domains 的情境。

最後，locality 最佳化與全域狀態感知之間的權衡也是個重要議題。例如在 Overload-on-Wakeup 錯誤中，排程器為了保留快取 locality，在執行緒被喚醒時僅考慮其原本所在節點的核心集合。這種做法雖有助於減少快取失效，但卻忽略其他節點上可能存在的閒置核心。結果是，系統偏向執行局部最佳化，反而犧牲全系統資源的使用效率與整體平衡性。

$\to$ [Linux 核心設計: Scalability 議題](https://hackmd.io/@sysprog/linux-scalability)

## 案例探討
> [Worst case response time analysis for completely fair scheduling in Linux systems](https://link.springer.com/content/pdf/10.1007/s11241-025-09435-x.pdf)

為何 Linux 從 CFS 轉向 EEVDF？

自 Linux v2.6.23 起，CFS 取代 $O(1)$ 排程器，引入 proportional-share 手法以便按比例分配運算資源，自此奠定 Linux 核心的排程機制，Linux v6.6 以 EEVDF 成為新的預設 CPU 排程器，對 CFS 十餘年打下的基礎進行升級。

Linux 將 CFS 作為預設排程器多年，其設計理念是「CFS 的原則是所有可執行的行程應公平地共享處理器資源」。然而，這種設計對於具即時性需求的工作負載而言存在明顯限制，但它缺乏針對延遲需求的直接支援機制。此外，由於 CFS 的時間片與排程決策是動態調整的 (基於目前 `vruntime` 及可執行行程集合)，導致傳統的最壞反應時間（WCRT）分析難以套用或不再適用（見第 3 頁）。這對需要可預測性與確定性的即時系統來說是一大挑戰。

CFS 在處理延遲敏感的任務時效果不佳，因此，EEVDF 被引入，以兼顧延遲需求與行程 fairness。這說明轉換的原因並非因為 CFS 的公平機制「錯誤」，而是它對於現代多樣化工作負載而言已顯不足，EEVDF 則是為了解決這個平衡問題而提出的新機制。

CFS 的排程規則是：選擇目前可執行行程中 $V_i$ 最小者執行。每個行程的時間片 $\delta_i$ 依其權重、總權重 $\sum_j w_j$、目標延遲（target latency, $L$）與最小粒度（$G$）動態計算而得。

[EEVDF](https://docs.kernel.org/scheduler/sched-eevdf.html) 的主體思維是「最早到達虛擬截止時間優先」。相較於 CFS 根據目前最小 `vruntime` 作為選擇依據，EEVDF 則引入 virtual deadline 的概念，提前為行程安排一個時間片的完成目標。

當行程 $i$ 成為可排程狀態 (如被喚醒或結束前一時間片)，會被指派一個虛擬截止時間 $\text{VD}_i$，推測其計算方式為：
$$
\text{EligibleTime}_i = \max(\text{CurrentVirtualTime}, \text{PreviousVD}_i)
$$
$$
\text{VD}_i = \text{EligibleTime}_i + \frac{s_i}{w_i}
$$

其中 $s_i$ 為行程 $i$ 所需的虛擬服務量。這個公式表示：一個高權重行程需要較短虛擬時間來完成同樣的時間片，反映其優先性。

值得注意的是，EEVDF 並非每個可執行行程都立即納入排程考量，而是僅挑選那些「已具備排程資格（eligible）」的行程，這種設計允許排程器在公平性與延遲控制之間取得更佳平衡。

EEVDF 與 CFS 採用相同的權重模型，並將 `vruntime` 為基礎的機制擴展至包含虛擬截止時間，以實現更進一步的延遲控制能力。

CFS 屬於回溯式排程，依據累積的 `vruntime` 做出目前決策，主要追求 fairness；而 EEVDF 則依據虛擬截止時間選擇可執行的行程，目標是維持公平的同時，有效地控制行程的延遲行為。

$\to$ [Queuing theory and Poisson process](https://youtu.be/rBIQmwaoZfs)