--- title: Linux 核心設計 categories: linux, performance, security, compiler, kernel, rtos toc: no ... - Instructor: [Jim Huang](/User/jserv) (黃敬群) `` * [Facebook 粉絲專頁](https://www.facebook.com/JservFans) (不要擔心提了笨問題，這專門用來和學生互動，可預約一對一討論) - 討論區: [https://www.facebook.com/groups/system.software2019/](https://www.facebook.com/groups/system.software2019/) - 課程信箱: `` Linux 核心設計 (Spring 2019) ------------------------------------------------------ * 第 1 週 (Feb 19): 誠實面對自己 - [課程簡介和注意須知](https://docs.google.com/presentation/d/1gGqQ5mx-40pdXrqwYUtz_LieRmVZbK7eWVEQib7ssNI/edit?usp=sharing) * [完整解說錄影](https://youtu.be/tf6mpd4z4b8) (3 小時) * 每週均安排隨堂測驗，採計其中最高分的 8 次 * 學期評分方式: 隨堂測驗 (25%) + 個人作業 (25%) + 分組報告及專題 (25%) + 自我評分 (25%) - 歷屆修課學生心得: [張家榮](/User/JaredCJR), [陳品睿](/User/ggary9424), [蕭奕凱](/User/Veck) - 分組報告示範: [ARM-Linux](/embedded/arm-linux), [Xvisor](/embedded/xvisor) - [GNU/Linux 開發工具共筆](https://hackmd.io/c/rJKbX1pFZ): 務必 *自主* 學習 Linux 操作, Git, HackMD, LaTeX 語法 (特別是數學式), GNU make, perf, gnuplot - [透過 Computer Systems: A Programmer’s Perspective 學習系統軟體](https://hackmd.io/c/S1vGugaDQ): 本學期教科書 (第 2 週可向助教購書) - [Bit-wise operations](https://hackmd.io/s/By0MltO_m) / [bit-wise 的應用](https://hackmd.io/s/ByzoiggIb) / [以位元駕馭能量](https://hackmd.io/s/rk2RO0cYX) - [bit-field](https://hackmd.io/s/SJ8y82ZYQ) - [What comes after Moore’s Law?](https://enterprisersproject.com/article/2018/9/what-comes-after-moores-law): 隨著 Moore’s Law 時代的結束, 通用化硬體效能不再如以往快速進步, 因此軟硬體也必須因應如此的變化, 這篇點出 4 個面向: * [Ephemeral](https://www.dictionary.com/browse/ephemeral) applications (短暫的軟體): 這點是以企業軟體來談，許多組織的觀點認為軟體壽命比運作其的硬體來得長久。在許多大企業依然如此，然而後續將大量導入 mobile, web, analytics 與其他軟體，更趨向快速轉變以符合客戶與市場所需; * New workloads, such as machine learning: 呼應諸多計算架構大師所說的 Domain-Specific Architecture (DSA); * Cloud platforms: 對於雲端應用而言，使用者不會在意它是在哪種處理器與加速器上運作的; * Open source software: 主要在於特定的軟體開發商因人力與成本而減少支援硬體的範圍，開放原始碼軟體這時能夠作為考慮方案。儘管無法消弭對硬體的相依性，但不像軟體開發商對硬體平台支援或不支援的要求; - [The Era of General Purpose Computers is Ending](https://www.nextplatform.com/2019/02/05/the-era-of-general-purpose-computers-is-ending/): 過往是研究員和從業者就設計瓶頸與發熱問題來說明困境，這篇則由製程發展與已發生的現象，討論以下變遷: * 能追上最先進製程的晶圓廠商越來越少 * [TOP 500](https://www.top500.org/) 中使用特殊晶片比例不斷上升 * 特殊化處理器各方面變得更為經濟實惠 - [linked list 和非連續記憶體操作](https://hackmd.io/s/SkE33UTHf) / [linked list 題目分析](https://hackmd.io/s/HyELy5bTz) - [作業](https://hackmd.io/s/SJ4kPZYS4) * [lab0](https://hackmd.io/s/BJA8EgFB4), [list](https://hackmd.io/s/S12jCWKHN) - [課程基本資料表單](https://docs.google.com/forms/d/e/1FAIpQLSckrat5PryUUaX2s5W8XKe5xJj9oW9ilL3Jy_KN-K4fgZ-Sog/viewform?usp=pp_url) **務必填寫，以接收課程資訊** - Week1 隨堂測驗: [題目](https://hackmd.io/s/SyrZMGYr4) / [作答表單](https://docs.google.com/forms/d/e/1FAIpQLScd0aNqnWZNE-3MsiCOmWWZoDcg6wsccmlXj6R3ekoLkYONMA/viewform?usp=pp_url) * 第 2 週 (Feb 26): C 語言程式設計 * [系統軟體開發思維](https://hackmd.io/s/B1KnHcwBN) * [為什麼要深入學習 C 語言？](https://hackmd.io/s/HJFyt37Mx) - C 語言發明者 Dennis M. Ritchie 說：「C 很彆扭又缺陷重重，卻異常成功。固然有歷史的巧合推波助瀾，可也的確是因為它能滿足於系統軟體實作的程式語言期待：既有相當的效率來取代組合語言，又可充分達到抽象且流暢，能用於描述在多樣環境的演算法。」 * [解讀計算機編碼](https://hackmd.io/s/rylUqXLsm) / [重新理解數值](https://hackmd.io/s/BkRKhQGae) * [基於 C 語言標準研究與系統程式安全議題](https://hackmd.io/s/S15o_K3cQ) - 藉由研讀漏洞程式碼及 C 語言標準，討論系統程式的安全議題 - 透過除錯器追蹤程式碼實際運行的狀況，了解其運作原理; - 取材自 dangling pointer, CWE-416 Use After Free, CVE-2017-16943 以及 integer overflow 的議題; * [C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/s/BkuMDQ9K7) * 搭配閱讀: [The Lost Art of Structure Packing](http://www.catb.org/esr/structure-packing/) * [C 語言: 指標](https://hackmd.io/s/HyBPr9WGl) * [C 語言: 函式呼叫](https://hackmd.io/s/SJ6hRj-zg) * [C 語言: 遞迴呼叫](https://hackmd.io/s/rJ8BOjGGl) * 作業 - [fibdrv](https://hackmd.io/s/SJ2DKLZ8E), [kcalc](https://hackmd.io/s/SyC9V0gUE) * 第 3 週 (Mar 5): 編譯器和連結器 * [C 語言: 未定義行為](https://hackmd.io/s/Skr9vGiQm): C 語言最初為了開發 UNIX 和系統軟體而生，本質是低階的程式語言，在語言規範層級存在 undefined behavior，可允許編譯器引入更多最佳化 * [C 語言: 編譯器和最佳化原理](https://hackmd.io/s/Hy72937Me) * C 語言: 連結器與程式行為 * [C 語言: 動態連結器](https://hackmd.io/s/HkK7Uf4Ml) * [C 語言: 執行階段程式庫 (CRT)](https://hackmd.io/s/Hkcr5cn97) * [C 語言: 前置處理器應用](https://hackmd.io/s/S1maxCXMl) * [C 語言: goto 和流程控制](https://hackmd.io/s/B1e2AUZeM) * [C 編譯器原理和案例分析](https://hackmd.io/s/H1ZzeiCIQ) * [C 語言程式設計技巧](https://hackmd.io/s/HyIdoLnjl) * 第 4 週 (Mar 12): 計算機架構 * [CS:APP 第 3 章重點提示和練習](https://hackmd.io/s/HJDRfVCFG) * [現代處理器設計：原理和關鍵特徵](https://hackmd.io/s/Hk2CscGcl) * [Arm 處理器](https://hackfoldr.org/arm/): 系列講座導論, 架構和指令集, 基礎指令和開發環境, 虛擬化技術和應用 - 你可曾想過，就算選修了電機資訊相關科系大部份的課程，自己仍對每天用的手機，完全沒概念，是不是很沮喪呢？裡頭運作 ARM 處理器，但你知道裡面的 CPU pipeline 如何運作？裡頭的 cache 如何運作？四核心、八核心到底又如何運作？CPU 和 GPU 之間如何通訊？ - 系列講座預計涵蓋 ARMv7-A/M, ARMv8-A/M, virtualization extension, 以及對應的系統軟體技術，像是 big.LITTLE, hypervisor, 和 TEE 的概念介紹 * [虛擬機器設計與實作](https://hackmd.io/s/SkBsZoReb) * [Linux: 透過 eBPF 觀察作業系統行為](https://hackmd.io/s/SJTuuG9a7): 動態追蹤技術（dynamic tracing）是現代軟體的進階除錯和追蹤機制，讓工程師以非常低的成本，在非常短的時間內，克服一些不是顯而易見的問題。它興起和繁榮的一個大背景是，我們正處在一個快速增長的網路互連異質運算環境，工程人員面臨著兩大方面的挑戰： - 規模：無論是使用者規模還是機房的規模、機器的數量都處於快速增長的時代; - 複雜度：業務邏輯越來越複雜，運作的軟體也變得越來越複雜，我們知道它會分成很多很多層次，包括作業系統核心和其上各種系統軟體，像資料庫和網頁伺服器，再往上有腳本語言或者其他高階語言的虛擬機器或執行環境，更上面是應用層面的各種業務邏輯的抽象層次和很多複雜的程式邏輯。 * 第 5 週 (Mar 19): Linux Process/Thread * [Microkernel 設計和真實世界中的應用](https://hackmd.io/s/SJ55y7fR) * [Linux: 不僅是個執行單元的 Process](https://hackmd.io/s/r1ojuBGgE): Linux 核心對於 UNIX Process 的實作相當複雜，不僅蘊含歷史意義 (幾乎每個欄位都值得講古)，更是反映出資訊科技產業的變遷，核心程式碼的 `task_struct` 結構體更是一絕，廣泛涵蓋 process 狀態、處理器、檔案系統、signal 處理、底層追蹤機制等等資訊，更甚者，還很曖昧地保存著 thread 的必要欄位，好似這兩者天生就脫不了干係 - 探討 Linux 核心設計的特有思維，像是如何透過 LWP 和 NPTL 實作執行緒，又如何透過行程建立記憶體管理的一種抽象層，再者回顧行程間的 context switch 及排程機制，搭配 signal 處理 * [CS:APP 第 3 章重點提示和練習](https://hackmd.io/s/HJDRfVCFG) * [CS:APP 第 4 章重點提示和練習](https://hackmd.io/s/ByKFm4CFz) * 第 6 週 (Mar 26): 軟體最佳化和數學原理 * video: [為什麼要學數學？](https://www.youtube.com/watch?v=9uqq2ottHnw) - [倖存者偏差](https://en.wikipedia.org/wiki/Survivorship_bias): 只考慮到偏頗的統計數據 - 用線性思維來思考所有事物導致的謬誤 - 黑天鵝事件 - 萬物都有對應的數學模型，而掌握數學就是掌握一種認知的工具，得以更清晰地認識世界 * 為何要掌握數學？即使 Linux 核心內部也大量可見: [從 CPU cache 一致性的角度看 Linux spinlock 的 non-scalable](https://hackmd.io/s/BJ8djgdnm) * [CS:APP 第 5 章重點提示和練習](https://hackmd.io/s/SyL8m4Lnm) * [CS:APP Assign 5.18](https://hackmd.io/s/rkdzvWJTX) * 第 7 週 (Apr 2): 停課一次 * 第 8 週 (Apr 9): 記憶體階層 * [CS:APP 第 6 章重點提示](https://hackmd.io/s/H1vQ3vu2z) * [Cache 原理和實際影響](https://hackmd.io/s/HkyscQn2z) * [software-pipelining](https://hackmd.io/s/HkbPkW86f) * [CPU caches](https://lwn.net/Articles/252125/) by Ulrich Drepper * CS:APP Cache lab * 第 9 週 (Apr 16): 虛擬記憶體 * [CS:APP 第 9 章重點提示](https://hackmd.io/s/SkCLi8YgN) * [Linux: 賦予應用程式生命的系統呼叫](https://hackmd.io/s/HyNbWoD1V) * Linux: 記憶體管理機制 * 第 10 週 (Apr 23): I/O 與例外處理 * [C 語言: Stream I/O 和 EOF](https://hackmd.io/s/Sy8pJ0x9G) * CS:APP 第 8 章重點提示 * [CS:APP 第 10 章重點提示](https://hackmd.io/s/H1TtmVTTz) * [Linux: 中斷處理和現代架構考量](https://hackmd.io/s/S1WKTCFM4) * 第 11 週 (Apr 30): 資料結構 * [C 語言: 物件導向程式設計](https://hackmd.io/s/HJLyQaQMl) * [Object-oriented design patterns in the kernel, part 1](https://lwn.net/Articles/444910/) / [Object-oriented design patterns in the kernel, part 2](https://lwn.net/Articles/446317/) * Linux: linked list, Queues, Maps, Binary Trees * 第 12 週 (May 7): 同步機制 * CS:APP 第 12 章重點提示 * [Concurrent Programming (並行程式設計)](https://hackmd.io/s/Skh_AaVix) * [Linux: 淺談同步機制](https://hackmd.io/s/SJpp-bN0m) * [Linux: 多核處理器和 spinlock](https://hackmd.io/s/rJbXgzz-4) * [Linux: RCU 同步機制](https://hackmd.io/s/H19V4eyfV) * [C11 atomic variables and the kernel](https://lwn.net/Articles/586838/) / [Linux Documentation: Circular Buffers](https://www.kernel.org/doc/Documentation/circular-buffers.txt) * [Toward a Better Use of C11 Atomics: Part 1](https://developers.redhat.com/blog/2016/01/14/toward-a-better-use-of-c11-atomics-part-1/), [Part 2](https://developers.redhat.com/blog/2016/01/19/toward-a-better-use-of-c11-atomics-part-2/) + [Part 1: Mutex Locks](https://github.com/angrave/SystemProgramming/wiki/Synchronization,-Part-1:-Mutex-Locks) + [Part 2: Counting Semaphores](https://github.com/angrave/SystemProgramming/wiki/Synchronization,-Part-2:-Counting-Semaphores) + [Part 3: Working with Mutexes And Semaphores](https://github.com/angrave/SystemProgramming/wiki/Synchronization,-Part-3:-Working-with-Mutexes-And-Semaphores) + [Part 4: The Critical Section Problem](https://github.com/angrave/SystemProgramming/wiki/Synchronization,-Part-4:-The-Critical-Section-Problem) + [Part 5: Condition Variables](https://github.com/angrave/SystemProgramming/wiki/Synchronization,-Part-5:-Condition-Variables) + [Part 6: Implementing a barrier](https://github.com/angrave/SystemProgramming/wiki/Synchronization,-Part-6:-Implementing-a-barrier) + [Part 7: The Reader Writer Problem](https://github.com/angrave/SystemProgramming/wiki/Synchronization,-Part-7:-The-Reader-Writer-Problem) + [Part 8: Ring Buffer Example](https://github.com/angrave/SystemProgramming/wiki/Synchronization,-Part-8:-Ring-Buffer-Example) + [Part 9: Synchronization Across Processes](https://github.com/angrave/SystemProgramming/wiki/Synchronization,-Part-9:-Synchronization-Across-Processes) * 第 13 週 (May 14): 排程和 Scalability * Linux: 排程 * 第 14 週 (May 21): 裝置驅動程式模型 * Linux: 裝置驅動程式介面和模型 * Linux: Device Tree * [CS:APP 第 11 章重點提示](https://hackmd.io/s/ByPlLNaTG) * 第 15 週 (May 28): 檔案系統 * Linux: 檔案系統和虛擬檔案系統設計 * Flash memory * Linux: F2FS * 第 16 週 (Jun 4): 多處理器架構和時鐘管理 * Linux: Timer 及其管理機制 * Multiprocessor Hardware * Linux: Optimization for Scalability * Memory Barrier * 第 17 週 (Jun 11): 分組討論 * 第 18 週 (Jun 18): 分組討論