版本 7e5e1e233a525269c8f94ef6dac19b9d8166b593
Linux 核心設計
- Instructor: Jim Huang (黃敬群)
<jserv.tw@gmail.com>- Facebook 粉絲專頁 (不要擔心提了笨問題，這專門用來和學生互動，可預約一對一討論)
- 討論區: https://www.facebook.com/groups/system.software2019/
- 課程信箱:
<embedded.master2015@gmail.com>
Linux 核心設計 (Spring 2019)
- 第 1 週 (Feb 19): 誠實面對自己
- 課程簡介和注意須知
- 完整解說錄影 (3 小時)
- 每週均安排隨堂測驗，採計其中最高分的 8 次
- 學期評分方式: 隨堂測驗 (25%) + 個人作業 (25%) + 分組報告及專題 (25%) + 自我評分 (25%)
- 歷屆修課學生心得: 張家榮, 陳品睿, 蕭奕凱
- 分組報告示範: ARM-Linux, Xvisor
- GNU/Linux 開發工具共筆: 務必 自主 學習 Linux 操作, Git, HackMD, LaTeX 語法 (特別是數學式), GNU make, perf, gnuplot
- 透過 Computer Systems: A Programmer’s Perspective 學習系統軟體: 本學期教科書 (第 2 週可向助教購書)
- Bit-wise operations / bit-wise 的應用 / 以位元駕馭能量
- bit-field
- What comes after Moore’s Law?: 隨著 Moore’s Law 時代的結束, 通用化硬體效能不再如以往快速進步, 因此軟硬體也必須因應如此的變化, 這篇點出 4 個面向:
- 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: 過往是研究員和從業者就設計瓶頸與發熱問題來說明困境，這篇則由製程發展與已發生的現象，討論以下變遷:
- 能追上最先進製程的晶圓廠商越來越少
- TOP 500 中使用特殊晶片比例不斷上升
- 特殊化處理器各方面變得更為經濟實惠
- linked list 和非連續記憶體操作 / linked list 題目分析
- 作業
- 課程基本資料表單 務必填寫，以接收課程資訊
- Week1 隨堂測驗: 題目 / 作答表單
- 課程簡介和注意須知
- 第 2 週 (Feb 26): C 語言程式設計
- 第 1 週發展回顧
- 系統軟體開發思維
- 為什麼要深入學習 C 語言？
- C 語言發明者 Dennis M. Ritchie 說：「C 很彆扭又缺陷重重，卻異常成功。固然有歷史的巧合推波助瀾，可也的確是因為它能滿足於系統軟體實作的程式語言期待：既有相當的效率來取代組合語言，又可充分達到抽象且流暢，能用於描述在多樣環境的演算法。」
- 解讀計算機編碼 / 重新理解數值 / 浮點數運算和定點數操作
- 基於 C 語言標準研究與系統程式安全議題
- 藉由研讀漏洞程式碼及 C 語言標準，討論系統程式的安全議題
- 透過除錯器追蹤程式碼實際運行的狀況，了解其運作原理;
- 取材自 dangling pointer, CWE-416 Use After Free, CVE-2017-16943 以及 integer overflow 的議題;
- C 語言：記憶體管理、對齊及硬體特性
- C 語言: 指標
- C 語言: 函式呼叫
- C 語言: 遞迴呼叫
- 課堂互動工作區
- 作業
- Week2 隨堂測驗: 題目 / 作答表單
- 第 3 週 (Mar 5): 編譯器和連結器
- 核心開發者當然要熟悉編譯器行為
- C 語言: 未定義行為: C 語言最初為了開發 UNIX 和系統軟體而生，本質是低階的程式語言，在語言規範層級存在 undefined behavior，可允許編譯器引入更多最佳化
- C 語言: 編譯器和最佳化原理
- C 語言: 連結器與程式行為
- C 語言: 動態連結器
- C 語言: 執行階段程式庫 (CRT)
- C 語言: 前置處理器應用
- C 語言: goto 和流程控制
- C 編譯器原理和案例分析
- C 語言程式設計技巧
- 課堂互動工作區
- Week3 隨堂測驗:
- 第 4 週 (Mar 12): 計算機架構
- 重要事項宣達: Homework2 繳交截止時間調整為 3 月 19 日中午
- Linux-based RTOS Experimental Platform for Constructing Self-driving Vehicles
- CS:APP 第 3 章重點提示和練習
- 現代處理器設計：原理和關鍵特徵
- Arm 處理器: 系列講座導論, 架構和指令集, 基礎指令和開發環境, 虛擬化技術和應用
- 你可曾想過，就算選修了電機資訊相關科系大部份的課程，自己仍對每天用的手機，完全沒概念，是不是很沮喪呢？裡頭運作 ARM 處理器，但你知道裡面的 CPU pipeline 如何運作？裡頭的 cache 如何運作？四核心、八核心到底又如何運作？CPU 和 GPU 之間如何通訊？
- 系列講座預計涵蓋 ARMv7-A/M, ARMv8-A/M, virtualization extension, 以及對應的系統軟體技術，像是 big.LITTLE, hypervisor, 和 TEE 的概念介紹
- 虛擬機器設計與實作
- Linux: 透過 eBPF 觀察作業系統行為: 動態追蹤技術（dynamic tracing）是現代軟體的進階除錯和追蹤機制，讓工程師以非常低的成本，在非常短的時間內，克服一些不是顯而易見的問題。它興起和繁榮的一個大背景是，我們正處在一個快速增長的網路互連異質運算環境，工程人員面臨著兩大方面的挑戰：
- 規模：無論是使用者規模還是機房的規模、機器的數量都處於快速增長的時代;
- 複雜度：業務邏輯越來越複雜，運作的軟體也變得越來越複雜，我們知道它會分成很多很多層次，包括作業系統核心和其上各種系統軟體，像資料庫和網頁伺服器，再往上有腳本語言或者其他高階語言的虛擬機器或執行環境，更上面是應用層面的各種業務邏輯的抽象層次和很多複雜的程式邏輯。
- 作業
- Week4 隨堂測驗:
- 第 5 週 (Mar 19): Linux Process/Thread
- Microkernel 設計和真實世界中的應用
- Linux: 不僅是個執行單元的 Process: Linux 核心對於 UNIX Process 的實作相當複雜，不僅蘊含歷史意義 (幾乎每個欄位都值得講古)，更是反映出資訊科技產業的變遷，核心程式碼的
task_struct結構體更是一絕，廣泛涵蓋 process 狀態、處理器、檔案系統、signal 處理、底層追蹤機制等等資訊，更甚者，還很曖昧地保存著 thread 的必要欄位，好似這兩者天生就脫不了干係- 探討 Linux 核心設計的特有思維，像是如何透過 LWP 和 NPTL 實作執行緒，又如何透過行程建立記憶體管理的一種抽象層，再者回顧行程間的 context switch 及排程機制，搭配 signal 處理
- Linux: 不只挑選任務的排程器
- Linux 核心設計: 第 5 週課堂互動工作區
- 作業
- 第 6 週 (Mar 26): 軟體最佳化和數學原理
- 公告
- 4 月 2 日停課一週，安排學生帶試卷回家測驗 (所謂的 take-home test)
- video: 為什麼要學數學？
- 倖存者偏差: 只考慮到偏頗的統計數據
- 用線性思維來思考所有事物導致的謬誤
- 黑天鵝事件
- 萬物都有對應的數學模型，而掌握數學就是掌握一種認知的工具，得以更清晰地認識世界
- 為何要掌握數學？
- CS:APP 第 2 章重點提示和練習
- 圖解傅立葉分析
- 公告
- 第 7 週 (Apr 2): 停課一次
- 第 8 週 (Apr 9): 記憶體階層
- CS:APP 第 3 章重點提示和練習
- CS:APP 第 6 章重點提示
- Cache 原理和實際影響
- software-pipelining
- CPU caches by Ulrich Drepper
- 第 9 週 (Apr 16): 虛擬記憶體
- 第 10 週 (Apr 23): I/O 與例外處理
- 第 11 週 (Apr 30): 資料結構
- C 語言: 物件導向程式設計
- Functional Programming 風格的 C 語言實作
- 是種 programming paradigm (開發典範)，不是 design pattern 也不是 framework，更不是 language。簡單來說，FP 是種以數學函數為中心的「思考方式」與「程式風格」;
- 透過 C 語言程式提供若干案例，如列舉數值、(不需要動態配置記憶體的) 反轉 linked list 元素、對 Linked List 元素進行合併排序;
- An Introduction to Cache-Oblivious Data Structures
- 「自動快取資料結構」，特性是無視硬體特定的快取大小，可能達到接近最優化快取的效能;
- 在現代 CPU 多層多種大小的快取架構下，它的理論宣稱其能自動優化在所有層的快取的存儲效率。傳統上電腦科學做偏理論的不太重視實作上的效能，而做實作或硬體優化的則不太重視理論分析。這個學門卻是橫跨了相當理論的演算法分析（需要相當多的進階數學工具），以及相當低階的硬體效能理解;
- 影片: Memory Hierarchy Models
- Google Research 強者的心得: 關於變強這檔事（九）
- Skip List: 置放大量數字並進行排序的資料結構。不用樹狀結構，而改用高度不同的 List 來連接資料。資料結構在概念上可以表示成 Left Child-Right Sibling Binary Tree 的模式。是 Cache-oblivious Algorithm 的經典範例，時間複雜度與空間複雜度與 Binary Search Tree 皆相同，但是實際運作效率比 Binary Search Tree 還要好。
- Linux 核心: A kernel skiplist implementation (Part 1), Skiplists II: API and benchmarks
- Object-oriented design patterns in the kernel, part 1 / Object-oriented design patterns in the kernel, part 2
- Linux: linked list, Queues, Maps, Binary Trees: 錄影 / 共筆
- Week 11 隨堂測驗:
- 作業
- 第 12 週 (May 7): 同步機制
- Announcing WSL 2
- WSL (Windows Subsystem for Linux) 是 Microsoft 提供可免費下載和使用的軟體，可讓您直接在 MS-Windows 上執行原生 Linux 命令列工具與傳統 Windows 桌面，而不需要額外的虛擬機器;
- 現在為了強化相容性，WSL 2 乾脆附上真的可執行的 Linux 核心 (!) 並透過虛擬化技術，高效率地執行，目前公佈的材料指出，檔案系統方面的效能提升了 20 倍，而且 Docker 一類的容器可更好地運作;
- 這項變更預計隨著 Windows Update 釋出，預計會有全新 Windows Terminal，並且開放原始碼，關鍵特徵包含支援 Tab 和透過 GPU 加速文字描繪處理
- CS:APP 第 12 章
- Concurrent Programming (並行程式設計)
- Linux: 淺談同步機制
- Linux: 多核處理器和 spinlock
- Linux: RCU 同步機制
- C11 atomic variables and the kernel / Linux Documentation: Circular Buffers
- Toward a Better Use of C11 Atomics: Part 1, Part 2
- Part 1: Mutex Locks
- Part 2: Counting Semaphores
- Part 3: Working with Mutexes And Semaphores
- Part 4: The Critical Section Problem
- Part 5: Condition Variables
- Part 6: Implementing a barrier
- Part 7: The Reader Writer Problem
- Part 8: Ring Buffer Example
- Part 9: Synchronization Across Processes
- Announcing WSL 2
- 第 13 週 (May 14): 電腦網路和裝置驅動程式模型
- 填寫分組表格
- video: How TCP/IP Works
- CS:APP 第 11 章重點提示
- Making C Less Dangerous in the Linux Kernel / 錄影
- 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, 解說2
- Linux: 裝置驅動程式介面和模型 / 錄影 by Greg Kroah-Hartman
- How to avoid writing device driversfor embedded Linux / 錄影
- Linux: Device Tree / 錄影
- Week 13 隨堂測驗:
- 第 14 週 (May 21): 作業回顧
- video: The kernel report 2018: 對應於 v4.20
- 分組表
- Homework5
- Homework6
- 課堂互動區
- 第 15 週 (May 28): 檔案系統
- video: Introduction to Memory Management in Linux
- slides 任職於 SoftIron (銷售 64-bit ARM 伺服器的公司，提供豐富的軟體支援) 的 Alan Ott 以 “Introduction to Memory Management in Linux” 為題，在 ELC 發表演說，非常精實，一口氣回顧計算機組織結構 (根本就是真人版本的「十分鐘理解記憶體管理」)，並深入淺出地探討 Linux 的各項設計 涵蓋 CONFIG_PAGE_OFFSET 的切割、swap, page fault, mmap/brk/sbrk, kmalloc()/vmalloc(), DMA 等等。
- Linux: 檔案系統和虛擬檔案系統設計
- Drive your NAND within Linux / 錄影
- Flash-Friendly File System (F2FS) / 錄影
- PACKET_MMAP
- Binding the socket to your network interface is mandatory (with zero copy) to know the header size of frames used in the circular buffer.
- Week 15 隨堂測驗:
- video: Introduction to Memory Management in Linux
- 第 16 週 (Jun 4): 多處理器架構和 Scalability
- 第 17 週 (Jun 11): 多處理器架構和 Real-time
- 第 18 週 (Jun 18): 多核處理器和時鐘管理
