--- title: 系統軟體課程進度與開放資源 categories: system programming, linux, performance, security, compiler, kernel toc: no ... - Instructor: [Jim Huang](/User/jserv) (黃敬群) `` * [Facebook 粉絲專頁](https://www.facebook.com/JservFans) (不要擔心提了笨問題，這專門用來和學生互動，可預約一對一討論) - 討論區: [https://www.facebook.com/groups/system.software2020/](https://www.facebook.com/groups/system.software2020/) - 課程信箱: ``, [往年課程進度](/sysprog/schedule-old) - 注意: 下方課程進度表標註有 `*` 的項目，表示內附錄影的教材 進階電腦系統理論與實作 (Fall 2020) ------------------------------------------------------ * 第 1 週 (Sep 8): 誠實面對自己 - [課程簡介和注意須知](https://docs.google.com/presentation/d/19rwlCab5Hw-EpG8z9aanFm601TnRz7WKdkId5_dUqKA/edit?usp=sharing) / [課程簡介和作業解說錄影](https://www.youtube.com/watch?v=CbxPOYDWo1E)`*` * 每週均安排隨堂測驗，採計其中最高分的 8 次 * 學期評分方式: 隨堂測驗 (20%) + 個人作業+分組報告 (30%) + 自我評分 (50%) * 在 Dcard 的[課程問答](https://www.dcard.tw/f/ncku/p/234365647) - 歷屆修課學生心得: [張家榮](/User/JaredCJR), [陳品睿](/User/ggary9424), [蕭奕凱](/User/Veck), [方鈺學](/User/JulianATA) - 分組報告示範: [ARM-Linux](/embedded/arm-linux) - [GNU/Linux 開發工具共筆](https://hackmd.io/@sysprog/gnu-linux-dev/)`*`: 務必 *自主* 學習 Linux 操作, Git, HackMD, LaTeX 語法 (特別是數學式), GNU make, perf, gnuplot - [透過 Computer Systems: A Programmer’s Perspective 學習系統軟體](https://hackmd.io/@sysprog/CSAPP)`*`: 本課程指定的教科書 (請及早購買: [天瓏書店](https://www.tenlong.com.tw/products/9787111544937)) - [軟體缺失導致的危害](https://hackmd.io/@sysprog/software-failure) * 1970 年代推出的首款廣體民航客機波音 747 軟體由大約 40 萬行程式碼構成，而 2011 年引進的波音 787 的軟體規模則是波音 747 的 16 倍，約 650 萬行程式碼。換言之，你我的性命緊繫於一系列極為複雜的軟體系統之中，能不花點時間了解嗎？ * 軟體開發的安全性設計和測試驗證應獲得更高的重視 - [解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation) * 人們對數學的加減運算可輕易在腦中辨識符號並理解其結果，但電腦做任何事都受限於實體資料儲存及操作方式，換言之，電腦硬體實際只認得 0 和 1，卻不知道符號 + 和 - 在數學及應用場域的意義，於是工程人員引入「補數」以表達人們認知上的正負數 * 您有沒有想過，為何「二補數」(2’s complement) 被電腦廣泛採用呢？背後的設計考量是什麼？本文嘗試從數學觀點去解讀編碼背後的原理 - [linked list 和非連續記憶體操作](https://hackmd.io/s/SkE33UTHf)`*` * 安排 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 + 分析](https://hackmd.io/@sysprog/linked-list-quiz)`*` * [題目2](https://hackmd.io/@sysprog/linux2020-quiz1) (內含作答表單) / [參考題解1](https://hackmd.io/@Ryspon/HJVH8B0XU), [參考題解2](https://hackmd.io/@chses9440611/Sy5gwE37I) - [作業](https://hackmd.io/@sysprog/2020-homework1): 9 月 20 日截止繳交 * [lab0](https://hackmd.io/@sysprog/2020-lab0), [quiz1](https://hackmd.io/@sysprog/rJ7WDWNVv) - 第 1 週隨堂測驗: [題目](https://hackmd.io/@sysprog/sysprog2020-quiz1) (內含作答表單) - [課堂問答簡記](https://hackmd.io/@sysprog/r1McTjN4P) * 第 2 週 (Sep 15): C 語言程式設計 * [系統軟體開發思維](https://hackmd.io/s/B1KnHcwBN) - [C 語言: 數值系統](https://hackmd.io/@sysprog/c-numerics)`*` - 儘管數值系統並非 C 語言所特有，但在 Linux 核心大量存在 u8/u16/u32/u64 這樣透過 typedef 所定義的型態，伴隨著各式 alignment 存取，若學員對數值系統的認知不夠充分，可能立即就被阻擋在探索 Linux 核心之外 —— 畢竟你完全搞不清楚，為何在 Linux 核心存取特定資料需要繞一大圈。 - [C 語言: Bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)`*` - Linux 核心原始程式碼存在大量 bit(-wise) operations (簡稱 bitops)，頗多乍看像是魔法的 C 程式碼就是 bitops 的組合。 - [類神經網路的 ReLU 及其常數時間複雜度實作](https://hackmd.io/@sysprog/constant-time-relu) * [為什麼要深入學習 C 語言？](https://hackmd.io/@sysprog/c-standards)`*` - C 語言發明者 Dennis M. Ritchie 說：「C 很彆扭又缺陷重重，卻異常成功。固然有歷史的巧合推波助瀾，可也的確是因為它能滿足於系統軟體實作的程式語言期待：既有相當的效率來取代組合語言，又可充分達到抽象且流暢，能用於描述在多樣環境的演算法。」 - Linux 核心作為世界上最成功的開放原始碼計畫，也是 C 語言在工程領域的瑰寶，裡頭充斥各式「藝術」，往往會嚇到初次接觸的人們，但總是能夠用 C 語言標準和開發工具提供的擴展 (主要來自 gcc 的 GNU extensions) 來解釋。 * [基於 C 語言標準研究與系統程式安全議題](https://hackmd.io/s/S15o_K3cQ) - 藉由研讀漏洞程式碼及 C 語言標準，討論系統程式的安全議題 - 透過除錯器追蹤程式碼實際運行的狀況，了解其運作原理; - 取材自 dangling pointer, CWE-416 Use After Free, CVE-2017-16943 以及 integer overflow 的議題; * [C 語言: bit-field](https://hackmd.io/s/SJ8y82ZYQ) - bit field 是 C 語言一個很被忽略的特徵，但在 Linux 和 gcc 這類系統軟體很常出現，不僅是精準規範每個 bit 的作用，甚至用來「擴充」C 語言 - [作業](https://hackmd.io/@sysprog/2020-homework2): 9 月 27 日截止繳交 * [quiz2](https://hackmd.io/@sysprog/B1zAbkAEP) * Week2 隨堂測驗: [題目](https://hackmd.io/@sysprog/2020-quiz2) (內含作答表單) * 第 3 週 (Sep 22): C 語言程式設計 * 公告 - [課程基本資料表單](https://forms.gle/b7NNuzkEJEgvfk7Q6): **務必填寫，以接收課程資訊** * [C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/s/BkuMDQ9K7)`*` * 搭配閱讀: [The Lost Art of Structure Packing](http://www.catb.org/esr/structure-packing/) * 從虛擬記憶體談起，歸納出現代銀行和虛擬記憶體兩者高度相似: malloc 給出 valid pointer 不要太高興，等你要開始用的時候搞不好作業系統給個 OOM ——簡單來說就是一張支票，能不能拿來開等到兌現才知道。 * 探討 heap (動態配置產生，系統會存放在另外一塊空間)、data alignment，和 malloc 實作機制等議題。這些都是理解 Linux 核心運作的關鍵概念。 * [C 語言: 未定義行為](https://hackmd.io/s/Skr9vGiQm)`*`: C 語言最初為了開發 UNIX 和系統軟體而生，本質是低階的程式語言，在語言規範層級存在 undefined behavior，可允許編譯器引入更多最佳化 * [Greatest Common Divisor 特性和實作考量](https://hackmd.io/@sysprog/gcd-impl): 探討最大公因數 (GCD) 特性，考慮微處理器架構實作帶來的效能衝擊。考慮到 binary GCD 及其最佳化。 * [C 語言: 前置處理器應用](https://hackmd.io/s/S1maxCXMl)`*` - C 語言之所以不需要時常發佈新的語言特徵又可以保持活力，前置處理器 (preprocessor) 是很重要的因素，有心者可逕行「擴充」C 語言 * [C 語言: 指標](https://hackmd.io/s/HyBPr9WGl)`*` - 應可體會為何走訪 linked list 節點的程式碼要這樣寫: `struct list **lpp; for (lpp = &list; *lpp != NULL; lpp = &(*lpp)->next)` - [作業](https://hackmd.io/@sysprog/2020-homework3): 10 月 7 日截止繳交 * [dict](https://hackmd.io/@sysprog/2020-dict), [quiz3](https://hackmd.io/@sysprog/B12ftyoBD) * Week3 隨堂測驗: [題目](https://hackmd.io/@sysprog/2020-quiz3) (內含作答表單) * 第 4 週 (Sep 29): 浮點數 + code review * [浮點數運算](https://hackmd.io/@sysprog/c-floating-point)`*`: 工程領域往往是一系列的取捨結果，浮點數更是如此，在軟體發開發有太多失誤案例源自工程人員對浮點數運算的掌握不足，本議程希望藉由探討真實世界的血淋淋案例，帶著學員思考 IEEE 754 規格和相關軟硬體考量點，最後也會探討在深度學習領域為了改善資料處理效率，而引入的 [BFloat16](https://en.wikipedia.org/wiki/Bfloat16_floating-point_format) 這樣的新標準 * [CS:APP 第 2 章重點提示和練習](https://hackmd.io/@sysprog/CSAPP-ch2)`*` * 提升程式可讀性之實務技巧: [(1)](https://blog.niclin.tw/2020/02/29/readable-code-1/), [(2)](https://blog.niclin.tw/2020/02/29/readable-code-2/), [(3)](https://blog.niclin.tw/2020/02/29/readable-code-3/) * [作業](https://hackmd.io/@sysprog/2020-homework4): 10 月 13 日截止繳交 * [quiz4](https://hackmd.io/@sysprog/r1z0WPWLD) * Week4 隨堂測驗: [題目](https://hackmd.io/@sysprog/2020-quiz4) (內含作答表單) * 第 5 週 (Oct 6): Fixed-Point + Code Review + C 語言 * [浮點數運算和定點數操作](https://hackmd.io/@NwaynhhKTK6joWHmoUxc7Q/H1SVhbETQ)`*` * [C 語言: 函式呼叫](https://hackmd.io/s/SJ6hRj-zg)`*` - 著重在計算機架構對應的支援和行為分析 * [C 語言: 遞迴呼叫](https://hackmd.io/s/rJ8BOjGGl)`*` - 或許跟你想像中不同，Linux 核心的原始程式碼裡頭也用到遞迴函式呼叫，特別在較複雜的實作，例如檔案系統，善用遞迴可大幅縮減程式碼，但這也導致追蹤程式運作的難度大增 * [Linux: 作業系統術語及概念](https://hackmd.io/@sysprog/linux-concepts)`*` * [C 語言: goto 和流程控制](https://hackmd.io/s/B1e2AUZeM)`*` - goto 在 C 語言被某些人看做是妖魔般的存在，不過實在不用這樣看待，至少在 Linux 核心原始程式碼中，goto 是大量存在 (跟你想像中不同吧)。有時不用 goto 會寫出更可怕的程式碼 * [C 語言程式設計技巧](https://hackmd.io/s/HyIdoLnjl)`*` * [作業](https://hackmd.io/@sysprog/2020-homework5): 11 月 9 日截止繳交 - [render](https://hackmd.io/@sysprog/2020-render), [quiz5](https://hackmd.io/@sysprog/SJvxlt0vv) * Week5 隨堂測驗: [題目](https://hackmd.io/@sysprog/2020-quiz5) (內含作答表單) * 第 6 週 (Oct 13): 編譯器和最佳化概念 * [Linux-based RTOS Experimental Platform for Constructing Self-driving Vehicles](https://osseu18.sched.com/event/FxWG/linux-based-rtos-experimental-platform-for-constructing-self-driving-vehicles-jim-huang-biilabs-shao-hua-wang-national-cheng-kung-university) - [video0](https://youtu.be/1-Ro5QXyIik), [video1](https://youtu.be/GNDWEvK4M8s), [video2](https://youtu.be/0C8th6bjIKg) * [C 編譯器原理和案例分析](https://hackmd.io/s/H1ZzeiCIQ)`*` * [C 語言: 編譯器和最佳化原理](https://hackmd.io/s/Hy72937Me)`*` * [作業](https://hackmd.io/@sysprog/2020-homework6): 11 月 9 日截止繳交 - [kcalc](https://hackmd.io/@sysprog/2020-kcalc), [quiz6](https://hackmd.io/@sysprog/B1C-WK0DD) * Week6 隨堂測驗: [題目](https://hackmd.io/@sysprog/2020-quiz6) (內含作答表單) * 第 7 週 (Oct 20): 效能最佳化、連結器，和執行階段函式庫 * [CS:APP 第 5 章重點提示和練習](https://hackmd.io/s/SyL8m4Lnm)`*` * [CS:APP Assign 5.18](https://hackmd.io/s/rkdzvWJTX)`*` * [C 語言: 動態連結器](https://hackmd.io/s/HkK7Uf4Ml)`*` * [C 語言: 連結器和執行檔資訊](https://hackmd.io/s/SysiUkgUV)`*` * [C 語言: 執行階段程式庫 (CRT)](https://hackmd.io/s/Hkcr5cn97)`*` * Week7 隨堂測驗: [題目](https://hackmd.io/@sysprog/2020-quiz7) (內含作答表單) * 第 8 週 (Oct 27): ROS + Dynamic Programming + Code Review * [建構在 ROS(Robot Operating System) 之上的自動駕駛技術](https://hackmd.io/@sysprog/ros-autonomous-vehicle)`*` * Code Review: [課堂互動](https://hackmd.io/@sysprog/SkYTGNH_D) * Week8 隨堂測驗: [題目](https://hackmd.io/@sysprog/2020-quiz8) (內含作答表單) * 第 9 週 (Nov 3): 微處理器 + Code Review * [現代處理器設計：原理和關鍵特徵](https://hackmd.io/s/Hk2CscGcl)`*` * [Arm 處理器](https://beta.hackfoldr.org/arm/)`*`: 系列講座導論, 架構和指令集, 基礎指令和開發環境, 虛擬化技術和應用 - 你可曾想過，就算選修了電機資訊相關科系大部份的課程，自己仍對每天用的手機，完全沒概念，是不是很沮喪呢？裡頭運作 ARM 處理器，但你知道裡面的 CPU pipeline 如何運作？裡頭的 cache 如何運作？四核心、八核心到底又如何運作？CPU 和 GPU 之間如何通訊？ - 系列講座預計涵蓋 ARMv7-A/M, ARMv8-A/M, virtualization extension, 以及對應的系統軟體技術，像是 big.LITTLE, hypervisor, 和 TEE 的概念介紹 * Week9 隨堂測驗: [題目](https://hackmd.io/@sysprog/2020-quiz9) (內含作答表單) * 第 10 週 (Nov 10): 記憶體階層 + 虛擬記憶體 * 注意事項: [分組和課程專題](https://hackmd.io/h80aIpi9TFWSQR9Br8MyWQ) * [CS:APP 第 6 章重點提示](https://hackmd.io/s/H1vQ3vu2z)`*` * [CPU caches](https://lwn.net/Articles/252125/) by Ulrich Drepper * [CS:APP 第 9 章重點提示](https://hackmd.io/s/SkCLi8YgN)`*` * Week10 隨堂測驗: [題目](https://hackmd.io/@sysprog/2020-quiz10) (內含作答表單) * 第 11 週 (Nov 17): 虛擬記憶體 + 系統呼叫 * 注意: [分組和課程專題](https://hackmd.io/h80aIpi9TFWSQR9Br8MyWQ) 請在本日 17:10 前更新 * [CS:APP 第 9 章重點提示](https://hackmd.io/@sysprog/CSAPP-ch9)`*` * [Linux: 記憶體管理](https://hackmd.io/@sysprog/linux-memory)`*`: 記憶體管理是 Linux 核心裡頭最複雜的部分，涉及到對計算機結構, slob/slab/slub 記憶體配置器、行程和執行檔樣貌、虛擬記憶體對應的例外處理、記憶體映射, UMA vs. NUMA 等等議題。 * [C 語言: 物件導向程式設計](https://hackmd.io/@sysprog/c-oop)`*` * [Functional Programming 風格的 C 語言實作](https://hackmd.io/@sysprog/c-functional-programming) * [C 語言: Stream I/O, EOF 和例外處理](https://hackmd.io/@sysprog/c-stream-io)`*` * [高效能 Web 伺服器開發](https://hackmd.io/@sysprog/fast-web-server) * Week11 隨堂測驗: [題目](https://hackmd.io/@sysprog/2020-quiz11) (內含作答表單) * 第 12 週 (Nov 24): 共享記憶體 * 注意事項: [分組和課程專題](https://hackmd.io/h80aIpi9TFWSQR9Br8MyWQ) (第二階段分組) * [解析 Linux 共享記憶體機制](https://hackmd.io/@sysprog/linux-shared-memory) * [Linux: 檔案系統概念及實作手法](https://hackmd.io/@sysprog/linux-file-system)`*` * Week12 隨堂測驗: [題目](https://hackmd.io/@sysprog/2020-quiz12) (內含作答表單) * 第 13 週 (Dec 1): Linux 核心發展回顧 * 注意: [分組和課程專題](https://hackmd.io/h80aIpi9TFWSQR9Br8MyWQ) 請在本日 17:10 前更新 * [Linux: 發展動態回顧](https://hackmd.io/@sysprog/linux-dev-review)`*` * [Making C Less Dangerous in the Linux Kernel](https://outflux.net/slides/2019/lca/danger.pdf) / [錄影](https://www.youtube.com/watch?v=FY9SbqTO5GQ)`*` - Linux 核心中各式 C 語言程式設計的安全和正確議題 - Variable Length Arrays are bad and slow - Explicit switch case fall-through - Always-initialized automatic variables - Arithmetic overflow detection - Hope for bounds checking - Control Flow Integrity: forward edges - Control Flow Integrity: backward edges - 也提供了 gcc/clang 相關的編譯參數 - [解說1](https://news.ycombinator.com/item?id=19006025), [解說2](https://www.reddit.com/r/linux/comments/ajztr3/making_c_less_dangerous_in_the_linux_kernel_by/) * Week13 隨堂測驗: [題目](https://hackmd.io/@sysprog/2020-quiz13) (內含作答表單) * 第 14 週 (Dec 8): 專題討論 * [分組和課程專題](https://hackmd.io/h80aIpi9TFWSQR9Br8MyWQ) * Week14 隨堂測驗: [題目](https://hackmd.io/@sysprog/2020-quiz14) (內含作答表單) * 第 15 週 (Dec 15): 電腦網路 / 專題討論 * 公告 - [分組和課程專題](https://hackmd.io/h80aIpi9TFWSQR9Br8MyWQ) 已悉數更新，斟酌同學們的意願和過去開發的狀況 - 上述專題務必在 2021 年 1 月 19 日有明顯的更新 (人在做，GitHub/HackMD 在看，有空就趕快更新)，當周審視後，就會進行期末評分 - 所有修課的學生應發訊息到[授課教師的粉絲專頁](https://www.facebook.com/JservFans)，預約一對一討論 (專題執行和評分期待) * [CS:APP 第 11 章: 電腦網路](https://hackmd.io/@sysprog/CSAPP-ch11) * Week15 隨堂測驗: [題目](https://hackmd.io/@sysprog/2020-quiz15) (內含作答表單) * 第 16 週 (Dec 22): 多核處理器架構 * [Multi-Core in Linux](https://youtu.be/UNI6Mbqryv0)`*` * [What is NUMA?](https://youtu.be/M-Q02b5uvfY)`*` * [A tour of the ARM architecture and its Linux support](https://youtu.be/NNol7fRGo2E)`*` * [Multiprocessor OS](/11-smp_os.pdf) * [Linux 核心設計: 多核處理器和 spinlock](https://hackmd.io/@sysprog/multicore-locks)`*` * Week16 隨堂測驗: [題目](https://hackmd.io/@sysprog/2020-quiz16) (內含作答表單) * 第 17 週 (Dec 29): Scalability + Regular expression * [Linux: Scalability 議題](https://hackmd.io/@sysprog/linux-scalability) * [How Do Regular Expressions Really Work?](https://youtu.be/u01jb8YN2Lw)`*` * Regex 視覺化: [Regulex](https://jex.im/regulex/) * [Implementing a simple regular expression engine](https://developpaper.com/implementing-a-simple-regular-expression-engine/) * [How Regular Expression Engines Work w/ C source](http://wstoop.co.za/wregex.php) * Week17 隨堂測驗: [題目](https://hackmd.io/@sysprog/2020-quiz17) (內含作答表單) * 第 18 週 (Jan 5): 專案討論 * Week18 隨堂測驗: [題目](https://hackmd.io/@sysprog/2020-quiz18) (內含作答表單)