Linux 核心設計
(Spring 2025) 課程進度表暨線上資源
第 1 週 (Feb 18, 20): 誠實面對自己
課程簡介和注意須知 / 課程簡介解說錄影 *
每週均安排隨堂測驗,採計其中最高分的 12 次
學期評分方式: 隨堂測驗 (20%) + 個人作業+報告及專題 (30%) + 自我評分
(50%)
留意資訊科技詞彙翻譯
部分教材解說 *
(僅止於概況,請詳閱下方教材及個別的對應解說錄影)
歷屆修課學生心得: 葉惟欣 , 向景亘 , 張家榮 , 方鈺學
佳句偶得:「大部分的人一輩子洞察力不彰,原因之一是怕講錯被笑。想了一點點就不敢繼續也沒記錄或分享,時間都花在讀書查資料看別人怎麼想。看完就真的沒有自己的洞察了」(出處 )
分組報告示範: ARM-Linux , Xvisor / 2024
年課程期末展示 *
GNU/Linux
開發工具共筆 *
: 務必 自主 學習 Linux 操作, Git,
HackMD, LaTeX 語法 (特別是數學式), GNU make, perf, gnuplot
確認 Ubuntu Linux 24.04-LTS 已順利安裝到你的電腦中
透過 Computer Systems: A
Programmer’s Perspective 學習系統軟體 *
:
本課程指定的教科書 (請及早購買: 天瓏書店 )
軟體缺失導致的危害
1970 年代推出的首款廣體民航客機波音 747 軟體由大約 40
萬行程式碼構成,而 2011 年引進的波音 787 的軟體規模則是波音 747 的 16
倍,約 650
萬行程式碼。換言之,你我的性命緊繫於一系列極為複雜的軟體系統之中,能不花點時間了解嗎?
軟體開發的安全性設計和測試驗證應獲得更高的重視
The
adoption of Rust in Business (2022)
解讀計算機編碼
人們對數學的加減運算可輕易在腦中辨識符號並理解其結果,但電腦做任何事都受限於實體資料儲存及操作方式,換言之,電腦硬體實際只認得
0 和 1,卻不知道符號 + 和 -
在數學及應用場域的意義,於是工程人員引入「補數」以表達人們認知上的正負數
您有沒有想過,為何「二補數」(2’s complement)
被電腦廣泛採用呢?背後的設計考量是什麼?本文嘗試從數學觀點去解讀編碼背後的原理
你所不知道的 C
語言:指標篇 *
linked list
和非連續記憶體操作 *
安排 linked list 作為第一份作業及隨堂測驗的考量點:
檢驗學員對於 C 語言指標操作的熟悉程度 (附帶思考:對於 Java
程式語言來說,該如何實作 linked list 呢?)
linked list
本質上就是對非連續記憶體的操作,乍看僅是一種單純的資料結構,但對應的演算法變化多端,像是「如何偵測
linked list 是否存在環狀結構?」和「如何對 linked list
排序並確保空間複雜度為 O(1) 呢?」
linked list 的操作,例如走訪 (traverse) 所有節點,反映出 Locality of
reference (cache 用語) 的表現和記憶體階層架構 (memory hierarchy)
高度相關,學員很容易從實驗得知系統的行為,從而思考其衝擊和效能改進方案
無論是作業系統核心、C
語言函式庫內部、應用程式框架,到應用程式,都不難見到 linked list
的身影,包含多種針對效能和安全議題所做的 linked list
變形,又還要考慮到應用程式的泛用性 (generic
programming),是很好的進階題材
題目 1 +
分析 *
題目 2 / 參考題解1 , 參考題解2
題目 3 /
參考題解
題目 4 / 參考題解
題目 5 / 參考題解
題目 6 / 參考題解
題目 7 / 參考題解
Linus Torvalds: Nothing
better than C
Linux:
作業系統術語及概念 *
作業 :
截止繳交日: Mar 11, 2025
第 1 週隨堂測驗: 題目
(內含作答表單)
課堂問答簡記
第 2 週 (Feb 25, 27): C 語言程式設計
公告
第一份及第二份作業均已指派,務必及早進行
隨堂測驗佔學期總分的 20%,其登錄分數的先決條件是,截至 6 月 19
日前,每位學員至少要進行課堂問答二次,並完成後續議題追蹤,彙整於當週的「課堂問答簡記」。若不滿足這條件,則隨堂測驗分數不予採計
個人作業 + 報告及專題佔學期總分的 30%,其登錄分數的先決條件是,截至
6 月 7 日前,每位學員至少要跟授課教師進行一對一討論
(第六週公告相關辦法並起算)
並完成後續議題追蹤,彙整於指定的作業筆記中。若不滿足這條件,則個人作業分數不採計
部分教材解說 *
(僅止於概況,請詳閱下方教材及個別的對應解說錄影)
video: engineer 詞源
校友經驗分享: Google ,
Apple
系統軟體開發思維
分析「快慢指標」
C 語言:
數值系統 *
儘管數值系統並非 C 語言所特有,但在 Linux 核心大量存在
u8/u16/u32/u64 這樣透過 typedef 所定義的型態,伴隨著各式 alignment
存取,若學員對數值系統的認知不夠充分,可能立即就被阻擋在探索 Linux
核心之外 —— 畢竟你完全搞不清楚,為何在 Linux
核心存取特定資料需要繞一大圈。
C 語言: Bitwise
操作 *
Linux 核心的
hash table 實作
為什麼要深入學習 C
語言? *
C 語言發明者 Dennis M. Ritchie 說:「C
很彆扭又缺陷重重,卻異常成功。固然有歷史的巧合推波助瀾,可也的確是因為它能滿足於系統軟體實作的程式語言期待:既有相當的效率來取代組合語言,又可充分達到抽象且流暢,能用於描述在多樣環境的演算法。」
Linux 核心作為世界上最成功的開放原始碼計畫,也是 C
語言在工程領域的瑰寶,裡頭充斥各式「藝術」,往往會嚇到初次接觸的人們,但總是能夠用
C 語言標準和開發工具提供的擴展 (主要來自 gcc 的 GNU extensions)
來解釋。
基於 C
語言標準研究與系統程式安全議題
藉由研讀漏洞程式碼及 C 語言標準,討論系統程式的安全議題
透過除錯器追蹤程式碼實際運行的狀況,了解其運作原理;
取材自 dangling pointer, CWE-416 Use After Free, CVE-2017-16943 以及
integer overflow 的議題;
C
語言:記憶體管理、對齊及硬體特性 *
搭配閱讀: The
Lost Art of Structure Packing
從虛擬記憶體談起,歸納出現代銀行和虛擬記憶體兩者高度相似: malloc
給出 valid pointer 不要太高興,等你要開始用的時候搞不好作業系統給個 OOM
——簡單來說就是一張支票,能不能拿來開等到兌現才知道。
探討 heap (動態配置產生,系統會存放在另外一塊空間)、data
alignment,和 malloc 實作機制等議題。這些都是理解 Linux
核心運作的關鍵概念。
C 語言:
bit-field
bit field 是 C 語言一個很被忽略的特徵,但在 Linux 和 gcc
這類系統軟體很常出現,不僅是精準規範每個 bit 的作用,甚至用來「擴充」C
語言
參考題目 /
參考題目 / 參考題目 / 參考題目 *
/ 參考題解
1 , 參考題解 2 ,
參考題解 3 , 參考題解 3
作業 :
截止繳交日 Mar 17
第 2 週隨堂測驗: 題目
(內含作答表單)
課堂問答簡記
第 3 週 (Mar 4, 6): 數值系統和 C 語言程式設計
第 4 週 (Mar 11, 13): 數值系統 + 編譯器
公告
本週安排邱冠維分享 Linux
核心貢獻的第一手資訊,課堂「舉手」討論並追蹤後續,視為有效的問答
第 2 份作業的作答表單已開放,第 3 份作業已指派
第 5 週檢討第一份作業,務必做好準備
教材解說 *
(僅止於概況,請詳閱下方教材及個別的對應解說錄影)
貢獻程式碼到 Linux 核心
追求神乎其技的程式設計之道
「可以看出抄襲風氣在台灣並不只是小時候在學校抄抄作業而已;媒體工作者在報導中任意抄襲及轉載是種不尊重自己專業的表現,不但隱含著一種應付了事的心態,更代表著這些人對於自己的工作沒有熱情,更沒有著一點堅持。如果要說我在美國看到這邊和台灣有什麼最大的不同,我想關鍵的差異就在對自己的工作有沒有熱情和堅持而已了。」
「程式藝術家也不過是在『簡潔』、『彈性』、『效率』這三大目標上進行一連串的取捨
(trade-off) 和最佳化。」
Linux
核心的紅黑樹
CS:APP 第 2
章重點提示和練習 *
核心開發者當然要熟悉編譯器行為
C
編譯器原理和案例分析 *
C 語言:
未定義行為 *
: C 語言最初為了開發 UNIX
和系統軟體而生,本質是低階的程式語言,在語言規範層級存在 undefined
behavior,可允許編譯器引入更多最佳化
C 語言:
編譯器和最佳化原理 *
錯誤更正碼 (ECC)
介紹和實作考量
作業 :
截止繳交日: Apr 15
Week4 隨堂測驗: 題目
(內含作答表單)
課堂問答簡記
第 5 週 (Mar 18, 20): Code Review
公告
回顧學員的參與狀況
Week5 隨堂測驗: 題目
(內含作答表單)
課堂問答簡記
第 6 週 (Mar 25, 27): C runtime/linker 及 fork/exec 系統呼叫
第 7 週 (Apr 1, 3): Process 和 CPU 排程
公告:
留意第五份作業 的規範
第三、四、五份作業對應的表單均已開放填寫
4 月 3 日晚間依舊授課 (線上,備有錄影),4 月 8 日改為線上授課,4 月
15 日改在資訊系「舊館」4203 教室
凡是「選課」且「成功繳交第一份作業」的學員,在 4 月 1
日下午會收到授課教師撰寫、尚未出版的《Demystifying the Linux CPU
Scheduler》電子書,請留意電子郵件信箱
(任何形式的)
旁聽的學員亦可向授課教師索取書稿,前提是已充分投入第一份和第二份作業,去信
<jserv.tw@gmail.com>
附上繳交作業的證明
(需要在作業區正確收錄) 和個人簡介
開放預約「一對一」討論,請留意相關辦法 。期末自我評量要反映出「專業的成長」,見範例
歐拉數:描述連續變化的基石
Linux:
不只挑選任務的排程器 *
: 排程器 (scheduler)
是任何一個多工作業系統核心都具備的機制,但彼此落差極大,考量點不僅是演算法,還有當應用規模提昇時
(所謂的 scalability) 和涉及即時處理之際,會招致不可預知的狀況
(non-determinism),不僅即時系統在意,任何建構在 Linux
核心之上的大型服務都會深受衝擊。是此,Linux
核心的排程器經歷多次變革,需要留意的是,排程的難度不在於挑選下一個可執行的行程
(process),而是讓執行完的行程得以安插到合適的位置,使得 runqueue
依然依據符合預期的順序。
Linux:
不僅是個執行單元的 Process *
: Linux 核心對於 UNIX
Process 的實作相當複雜,不僅蘊含歷史意義
(幾乎每個欄位都值得講古),更是反映出資訊科技產業的變遷,核心程式碼的
task_struct
結構體更是一絕,廣泛涵蓋 process
狀態、處理器、檔案系統、signal
處理、底層追蹤機制等等資訊,更甚者,還很曖昧地保存著 thread
的必要欄位,好似這兩者天生就脫不了干係
探討 Linux 核心設計的特有思維,像是如何透過 LWP 和 NPTL
實作執行緒,又如何透過行程建立記憶體管理的一種抽象層,再者回顧行程間的
context switch 及排程機制,搭配 signal 處理
利用 lkm
來變更特定 Linux 行程的內部狀態
Linux:
賦予應用程式生命的系統呼叫 *
vDSO: 快速的 Linux
系統呼叫機制
《Demystifying the Linux CPU Scheduler》第 1 章
測試 Linux
核心的虛擬化環境
建構
User-Mode Linux 的實驗環境 *
課堂問答簡記
第 8 週 (Apr 8, 10): 並行程式設計, Linux 同步機制
第 9 週 (Apr 15, 17): futex, 伺服器開發與 Linux 核心對應的系統呼叫
第 10 週 (Apr 22, 24): 現代微處理器
第 11 週 (Apr 29, May 1): 作業回顧 + 期末專題
第 12 週 (May 6, 8): 現代微處理器 + 記憶體管理
課程期末專題
教材解說 *
(僅止於概況,請詳閱下方教材及個別的對應解說錄影)
並行和多執行緒程式設計 講座:
《Demystifying the Linux CPU Scheduler》
2.4 Multiprocessing
3.2 Time keeping
3.4 Per-Entity Load Tracking
4.1 Group scheduling and cgroups: Introduction
4.2 Group scheduling and CPU bandwidth
CS:APP 第 6
章重點提示 *
CPU caches by Ulrich
Drepper
進行中的繁體中文翻譯: 《每位程式開發者都該有的記憶體知識 》
本文解釋用於現代電腦硬體的記憶體子系統的結構、闡述 CPU
快取發展的考量、它們如何運作,以及程式該如何針對記憶體操作調整,從而達到最佳的效能。
CS:APP 第 9
章重點提示 *
Week12 隨堂測驗: 題目
(內含作答表單)
課堂問答簡記
第 13 週 (May 13, 15): 記憶體管理 + 裝置驅動程式
第 14 週 (May 20, 22): 虛擬記憶體管理、記憶體模型、虛擬化技術
公告
隨堂測驗佔學期總分的 20%,其登錄分數的先決條件是,截至 6 月 19
日前,每位學員至少要進行課堂問答二次,並完成後續議題追蹤,彙整於當週的「課堂問答簡記」。若不滿足這條件,則隨堂測驗分數不予採計
個人作業 + 報告及專題佔學期總分的 30%,其登錄分數的先決條件是,截至
6 月 7 日前,每位學員至少要跟授課教師進行一對一討論
(第六週公告相關辦法並起算)
並完成後續議題追蹤,彙整於指定的作業筆記中。若不滿足這條件,則個人作業分數不採計
佔學期總成績 50% 的自我評量,請在 7 月 3 日中午前完成 (自 6 月 20
日開放填寫,注意:只受理 6 月 20 日到 7 月 3
日中午前的內容,不要過早填寫)。範例: User/weihsinyeh
自我評量的網址必須 符合
/User/你的GitHub帳號名稱
格式
(區分大小寫),請不要打錯字。「不能」用「上傳檔案」的功能,使用文字編輯
填寫你的法定姓名和 GitHub 帳號名稱
自我評分項目
(都要有對應的狀況說明、超連結、延伸資訊,和用客觀事實佐證,每項不少於 70
個 Unicode 字元,用流暢清晰的漢語書寫,採用指定的資訊科技詞彙翻譯 ,你日後的同事和主管可能會看到你的評量),務必詳細閱讀「課程自我評量 」(含錄影)
成果發表和貢獻: 與 Linux 核心相關的公開演講、貢獻到 Linux
核心和相關專案 (應標註對應的公開
commits/patches)、貢獻本課程的教材和使用的專案,包含授課教師編撰/翻譯的書籍
(即《Demystifying the Linux CPU Scheduler》, 《Concurrency Primer》,
《Linux Kernel Module Programming Guide》,
〈每位程式開發者都該有的記憶體知識〉),必須要獲得採納才算,即便只是修正錯字,也可列入貢獻。有效採計區間為
2 月 18 日到 7 月 2 日
作業/隨堂測驗: 你的開發紀錄,人在做,Google 在看
期末專題: 開發紀錄、評量成果和產出,以及觀摩其他學員的期末專題並提問
(要有對應的公開軌跡),且至少要涵蓋 5 項列於課程期末展示 的專案。注意:你有義務回覆其他學員
(和授課教師) 對你期末專題的提問,並在 7 月 4
日中午前做出回應且更新更新在期末專題頁面
與授課教師的互動:
標注與授課教師「一對一討論」的時間,並列出你針對授課教師的問答、測驗和後續討論及啟發。課堂問答也可列入
所見所聞所感,務必提及閱讀〈因為自動飲料機而延畢的那一年〉和回顧自身在本課程的投入狀況,尤其是重視細節、數學、謹慎用詞 、實驗設計等
上述 (1) 到 (6) 各項都該有對應的評分,皆為介於 1 到 10
之間的「整數」(不要自作主張寫 8.7
這樣的數值)
並要能充分反映上述評分項目,附上對應的「公開」證明,如 commit log 和
pull requests
計算方式 (GEOMEAN 即針對上述 (1) 到 (5) 各項的幾何平均 ,沒有加權。若有計算錯誤,整個自我評量不計分)
如下,若超過 10,則取 10
方案 A (針對已對 Linux, glibc, gcc, llvm, rv32emu 等專案做出超過 3
項 non-trivial 貢獻 [僅修正錯字或沒有改變程式行為的修改視為 trivial]
並獲得開發者採納): 8 + floor(0.3 * GEOMEAN)
方案 B: 1 + floor(GEOMEAN)
Memory
Model
Linux
核心 Copy On Write 實作機制
Embedded
Virtualization applied in Mobile Devices / info
KVM: Linux
虛擬化基礎建設 *
LKL: 重用 Linux
核心的成果
課堂問答簡記
第 15 週 (May 27, 29): 網路封包處理 + 多核處理器架構
第 16 週 (Jun 3, 5): 程式碼最佳化概念 + 多核處理器架構
第 17 週 (Jun 10, 12): 即時 Linux 的基礎建設
第 18 週 (Jun 17, 19): 多核處理器 + Rust
第 19 週 (Jun 24, 26): Rust, Linux 核心除錯
第 20 週 (Jul 1): 回顧和檢討
注意事項
之所以將 6 月 28
日訂為期末專題錄影解說的繳交時限,是便於同儕檢討,學員應持續改進期末專題,作為日後能寫在個人簡歷的成果。
倘若你沒在 6 月 28 日進行專題展示發表 ,就要在
7 月 2 日中午前,挑出至少 5
個由其他學員進行的題目,觀看其解說錄影、開發紀錄、程式碼和成果進行批評,紀錄於下方對應專案的開發紀錄中,針對個別題目,至少提出
1 個問題或建議。注意:比照第三次作業 的風格,在
(自己以外) 學員的開發紀錄上留言。
針對其他學員 (含授課教師和社會人士)
在開發紀錄頁面提出的問題或建議,務必在 7 月 3
日中午前予以回應和改進。
課程自我評量 *
透過 Linux
核心重新認識數位化世界 : 藉由 Dominic Walliman 製作的〈Map of Computer
Science 〉短片,探討電腦科學的多個面向,諸如電腦網路、圖形處理、抽象機器及理論
(如Turing machine)、NP-Complete
問題、計算機架構、排序演算法、資料壓縮、現代密碼學、形式化方法、作業系統排程、異質多核運算、編譯器,和程式語言,來回顧今日的
Linux 核心 ── 電腦科學的子學科幾乎都可反映在 Linux 核心中。
課程期末展示 *
期末專題 檢討
Please enable JavaScript to view the comments powered by Disqus.