# [Linux 核心設計](https://beta.hackfoldr.org/linux/): 作業系統術語及概念 Copyright (**慣C**) 2020 [宅色夫](http://wiki.csie.ncku.edu.tw/User/jserv) ==[直播錄影](https://www.youtube.com/watch?v=nrkq2WUacz4)== ## 點題 面對原始程式碼近兩千八百萬行規模的 Linux 核心,最令人感到挫折的,絕非缺乏程式註解,而是就算見到滿滿的註解,自己卻有如文盲,全然無從理解起。為什麼呢?往往是因為對作業系統的認知太侷限。 示範: ```cpp /** * struct cacheinfo - represent a cache leaf node * @id: This cache's id. It is unique among caches with the same (type, level). * @type: type of the cache - data, inst or unified * @level: represents the hierarchy in the multi-level cache * @coherency_line_size: size of each cache line usually representing * the minimum amount of data that gets transferred from memory * @number_of_sets: total number of sets, a set is a collection of cache * lines sharing the same index * @ways_of_associativity: number of ways in which a particular memory * block can be placed in the cache * @physical_line_partition: number of physical cache lines sharing the * same cachetag * @size: Total size of the cache * @shared_cpu_map: logical cpumask representing all the cpus sharing * this cache node * @attributes: bitfield representing various cache attributes * @fw_token: Unique value used to determine if different cacheinfo * structures represent a single hardware cache instance. * @disable_sysfs: indicates whether this node is visible to the user via * sysfs or not * @priv: pointer to any private data structure specific to particular * cache design * * While @of_node, @disable_sysfs and @priv are used for internal book * keeping, the remaining members form the core properties of the cache */ struct cacheinfo { ... ``` > 取自 [include/linux/cacheinfo.h](https://github.com/torvalds/linux/blob/master/include/linux/cacheinfo.h) 我們將回顧若干作業系統術語及概念,像是: userspace vs. kernel space, Monolithic kernel vs. Microkernel, Address space, sharing between virtual address space, Execution context, Multi-tasking, Preemptive kernel, Symmetric MultiProcessing (SMP), CPU Scalability, Copy-On-Write, lock。探討的過程中,我們除了將術語對應到 Linux 核心外,也會參照 Solaris, Microsoft Windows NT, Plan 9, CMU Mach 等經典作業系統來解說。 ## 高階觀點 投影片: [Linux Kernel: Introduction](https://linux-kernel-labs.github.io/refs/heads/master/lectures/intro-slides.html) * [重點描述](https://linux-kernel-labs.github.io/refs/heads/master/lectures/intro.html) [ Page 2 ] User vs. Kernel ![](https://i.imgur.com/SV9wAwH.png) > 取自 [User mode and kernel mode](https://docs.microsoft.com/zh-tw/windows-hardware/drivers/gettingstarted/user-mode-and-kernel-mode) 1963 年麻省理工學院的科學記者採訪當時計算中心,並與 Fernando J. Corbató (2019 年七月因糖尿病的併發症過世,享年 93 歲) 教授對話,後者是世界上第一個分時多工作業系統 Compatible Time-Sharing System (CTSS) 的主導設計者,Corbató 教授在 CTSS 獲得巨大成功後,帶領 MIT 團隊,和通用電氣及貝爾實驗室發展 MULTICS 作業系統,許多慣例和概念一路從 CTSS、MULTICS,到後來重新實作的 UNIX 作業系統。 在這部短片中,Corbató 教授談及過往批次處理系統的限制,並快速回顧電腦運作原理及如何實作分時多工、依據優先權進行排程等等,是此,電腦猶如電話交換機,同時為多個使用者所操作,每位使用者都能依據需求使用終端機,存取到運算和儲存資源,不會和其他使用系統的人有所衝突。可留意到,Corbató 教授在訪談中提到 [Supervisory program](https://en.wikipedia.org/wiki/Supervisory_program)。 另外,也不難從影片中看到形似打字機、可和電腦對話互動的裝置,那就是 teletyper (電傳打字機) —— 早期的電腦沒有配備螢幕,而是透過 teletyper,藉由訊號連線,建立人機互動的終端機 (console),這也是 UNIX 作業系統多人多工的操作還境一直具備的特徵,後來的 Linux 也延續 teletyper 的概念,實作 tty 子系統。 {%youtube Q07PhW5sCEk%} [ Page 3 ] Typical operating system architecture :dart: 摘自 [UNIX 作業系統 fork/exec 系統呼叫的前世今生](https://hackmd.io/@sysprog/unix-fork-exec): 1963 年,電腦科學家 [Melvin Conway](https://en.wikipedia.org/wiki/Melvin_Conway) 博士 (以 [Conway's Law](https://en.wikipedia.org/wiki/Conway%27s_law) 聞名於世) 發表論文〈[A Multiprocessor System Design]( https://archive.org/details/AMultiprocessorSystemDesignConway1963/page/n7)〉,正式提出 fork 思想。從論文標題不難發現,fork 的思想最初是作為一種「多處理器並行處理」執行模型,這個想法非常有意思,該想法源於下方流程圖。 :::success 此處「並行」通指 [concurrent](https://dictionary.cambridge.org/dictionary/english/concurrent) (形容詞) 和 [concurrency](https://dictionary.cambridge.org/dictionary/english/concurrency) (名詞),這詞彙在中國簡體稱為「并发」。「並行」這譯詞在 1970 年代就出現於台灣的資訊科技刊物中,本文沿用。 ::: 我們考慮以下流程圖: ```graphviz digraph Graph1 { graph [splines=ortho]; node [style=rounded shape=box label=""]; A; subgraph cluster_fork { style="rounded"; label=" fork 點" B[style=diagonal shape=diamond]; } subgraph cluster_join { style="rounded"; label=" join 點" D; } subgraph cluster_parallel1 { label="可並行 " CL; } subgraph cluster_parallel2 { label=" 可並行" CR; } E; A -> B; B -> {CL CR}; {CL CR} -> D; D -> E; } ``` 若我們確立電腦程式可用一套明確的流程來表達,我們即可聲明該並行處理的方案是可行的。流程圖的分岔處,fork —— 叉子,多麼生動的類比。 一個流程圖上的分支點分裂出來的分支顯然是邏輯獨立的,這便是可並行化處理的前提,於是他們便可表現為不同的*行程 (process)* 的形式。當時的表達還只是 **process** 這個術語,還不具備現代作業系統的「行程」概念。 join 表示多個並行處理的行程由於某種原因不得不進行同步的時間點,也就是多個並行行程會合之處。在當今的多執行緒程式中,這個點依然叫作 join。比如 Java 核心套件裡頭的 [java.lang.Thread](https://docs.oracle.com/javase/8/docs/api/java/lang/Thread.html) 的 join 方法以及 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 函式庫的 [pthread_join](http://man7.org/linux/man-pages/man3/pthread_join.3.html) 函式。 廣義來說,join 也意味著不同的行程必須經過的執行路徑,因此減少 join 的數量將會提高並行的效率。 Conway 的論文另一個創舉是,他將行程 (也就是後來作業系統中的 process 的概念) 及執行該行程的處理器 (即 CPU processor) 分離出來,抽象出 scheduler 層面。 大意是說:「只要滿足系統中的活動處理器數量是總處理器數量和並行行程總和的最小值即可」。這意味著 scheduler 可以將多處理器系統的所有處理器和系統所有行程分別看成是統一的資源提供者和消費者來一起排程。 ```graphviz digraph Graph2 { graph [nodesep=2] node [shape=box]; B [label="一堆處理器"]; A [label="一堆行程"]; B -> A [style=dotted dir=both label=" 多對多映射"]; A -> B [dir=both label=" scheduler"] } ``` 在 Unix 引入 fork 之後,這種多處理器並行的設計思想就深入到 Unix 的核心。這個思想最終也影響 Unix 及後來的 Linux,並延續至今。 關於這個設計思想為何得以影響 Unix (及其家族) 超過五十年,和 [Conway's law](https://en.wikipedia.org/wiki/Conway%27s_law) 不無關係。這定律中提到: > Any organization that designs a system (defined broadly) will produce a design whose structure is a copy of the organization's communication structure. 美國威斯康辛大學教授 Remzi H. Arpaci-Dusseau 和 Andrea C. Arpaci-Dusseau 撰寫的開放存取式教科書《[Operating Systems: Three Easy Pieces](http://pages.cs.wisc.edu/~remzi/OSTEP/)》,在〈[The Abstraction: The Process](http://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](http://www.cs.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/) 發表,正是採用分時多工作為主題。 :::success 至於《[Operating Systems: Three Easy Pieces](http://pages.cs.wisc.edu/~remzi/OSTEP/)》(可簡稱為 `OSTEP`) 的 "Three Easy Piece" 也有典故,是向已故物理學家費曼致敬,後者著有《Six Easy Pieces: Essentials Of Physics Explained By Its Most Brilliant Teacher》。用 `OSTEP` 作者的話說,作業系統只有物理學一半難度,那就折半為 《Three Easy Pieces》,該書的三大主軸: * 虛擬化 (Virtualization); * 並行 (Concurrency); * 持續保存 (Persistence): 主要探討檔案系統; ::: [ Page 4 ] Monolithic kernel [ Page 5 ] Microkernel :dart: 摘自 [淺談 Microkernel 設計和真實世界中的應用](https://hackmd.io/@sysprog/microkernel-design): ![](https://i.imgur.com/HPDuaT9.png) > source: [Kernel vs Microkernel vs Multikernel – Explained Visually](https://bsdmag.org/kernel/) Mach (發音 [mʌk]) 是美國 Carnegie-Mellon 大學 (CMU) 的 microkernel 作業系統,發展於 1980 年代,著眼點是,隨著功能越來越多,UNIX 也日漸龐大複雜而難以掌握,Mach 的設計概念就是「去蕪存菁」,僅留下真正關鍵的部份,其餘的功能都用使用者層級 (user-level) 的程式 (特徵 server) 來實做,藉此減低核心的複雜度。 Mach 設計目標: * 與 UNIX 相容 * 物件導向設計 * 跨平台:在單處理器、多處理器上都能執行 * 適合分散式運算環境 值得一提的是,儘管 Mach 已式微,但 Mach 的眾多技術突破陸續被 BSD 和 Linux kernel 所吸收。Mach 2.5 是許多商業 UNIX,像是 DEC OSF/1, NeXTSTEP (後來移轉到 Apple Computer) 的基礎,Mach 3.0 才是真正純粹的完全 microkernel 化的實做,而 Mach 4.0 則由 Utah (猶他) 大學維護。 Mach 的主要開發者 [Richard Rashid](https://en.wikipedia.org/wiki/Richard_Rashid) 自 1991 年就在 Microsoft 服務,領導 [Microsoft Research](https://en.wikipedia.org/wiki/Microsoft_Research) 若干技術突破,另一位主要 Mach 開發者 [Avie Tevanian](https://en.wikipedia.org/wiki/Avie_Tevanian) 曾在 [NeXT](https://en.wikipedia.org/wiki/NeXT) 擔任軟體主管,並在 Apple 收購 NeXT 後,轉任 Apple Inc. 的技術長 (已退休)。 Mach 被視為以下這些元件所組成:  * ports  (埠) * messages (訊息) * tasks (工作) * threads (執行緒) * virtual memory (虛擬記憶體) 如同一個設計成熟的物件導向系統,這些物件的介面已經定義明確,因此物件內的改變不會影響到使用這些物件的行程 (process)。 可將 Mach 中的 task  看待為 UNIX 環境中的 process。 對執行中的行程而言,它是一個可執行的環境,如同虛擬記憶體或是處理器的執行週期。不過,相對於傳統  UNIX 的 process,Mach 的 task 並不表示包含一個正在執行的 thread,對 Mach 而言,thread 也是一個獨立的物件 (!) :::info 對比 Android,後者底層是 Linux 核心,但是設計卻高度有 microkernel 的影子,像是: * Framework: task, thread, activity, service (microkernel terms) * Android: binder IPC/RPC ::: 因此,一個有用的 task 必須包含至少一個 thread。Mach 的 thread 與其它常見作業系統的 thread 相仿,在同一個 task 中的 thread 相互分享記憶體與其它資源。Mach 在設計時,就希望成為一個 multi-threaded,而可有效執行於多顆處理器 (SMP) 上。 相較之下,Linux 發展之初,只是一個以 single thread 為導向的作業系統,multi-threaded 與 SMP 也在發展 10 年後才納入,早期甚至得用彆腳的 LinuxThread 套件來實現 multi-threading,而 Mach 與 Hurd 在設計初期,就已經考慮這些需求。在 [NPTL](https://en.wikipedia.org/wiki/Native_POSIX_Thread_Library) 出現之前,Linux 的 multi-threaded 實做非常奇怪,仍然把 process 當作最基本的 abstraction,也就是說 scheduling, context switch 等基本操作對象仍是 process,而thread / LWP 只是和別人分享定址空間和資源的 process。因此: * 嚴格來說,Linux 只實做一半的 thread,但這並不是壞事,因為許多的應用程式不見得用到 thread,且簡化 thread 實做的結果,使得 process 管理變得更有效率,副作用是產生出來的 "thread" 比其它作業系統的實做,顯得更 heavy-weight,可以說,過去 Linux 犧牲 thread 的效率,以換取 process 的效率 * 以 abstraction 的角度來看  Linux 過去並非在本質上支援 thread,但以 programming model 來看,Linux 的確是有 thread 可用,儘管效率較差 早期 Linux 的 process 和 thread 的效能和其他作業系統的數據比較,可參照論文 "[An Overview of the Singularity Project](http://research.microsoft.com/pubs/52716/tr-2005-135.pdf)"  (Microsoft Research, 2005 年) 的第 31 頁 延伸閱讀: * [Linux 核心設計: 不僅是個執行單元的 Process](https://hackmd.io/@sysprog/linux-process) [ Page 6 ] Monolithic kernels can be modular :dart: Linux 核心模組掛載機制參見 [fibdrv](https://hackmd.io/@sysprog/linux2020-fibdrv) [ Page 7 ] Hybrid kernels Linus Torvalds [表示](https://www.realworldtech.com/forum/?threadid=65915&curpostid=65936): > “As to the whole ‘hybrid kernel’ thing - it’s just marketing. It’s ‘oh, those microkernels had good PR, how can we try to get good PR for our working kernel? Oh, I know, let’s use a cool name and try to imply that it has all the PR advantages that that other system has’.” [Hybrid kernel](https://en.wikipedia.org/wiki/Hybrid_kernel) 案例: * DragonFly BSD - [HAMMER](https://www.dragonflybsd.org/hammer/) - [DragonFly's Major Features List](https://www.dragonflybsd.org/features/) > The new infrastructure will allow many parts of the kernel to be migrated out into userspace; here they will be more easily debugged as they will be smaller, isolated programs, instead of being small parts entwined in a larger chunk of code. Additionally, the migration of select kernel code into **userspace** has the benefit of making the system more robust; if a userspace driver crashes, it will not crash the kernel. * [XNU](https://en.wikipedia.org/wiki/XNU) * Apple Inc. 現在許多技術來自 Steve Jobs 於 1985 年離開 Apple Computer 後,所創立的 NeXT 公司,後者的主力產品就是 NeXTSTEP 作業系統,以 CMU Mach 為基礎,並且整合 4.3BSD userspace 作為 Mach 上的 server。 * 後來 Apple Inc. 把 NeXTSTEP 的技術發揚光大,演化為 XNU (核心) / Darwin (作業系統),造就 iPhone OS / macOS 的關鍵技術。 * 技術簡報: [The Microkernel Mach Under NeXTSTEP](http://www.slideshare.net/schmidt/the-microkernel-mach-under-ne-xtstep-stripped) * 延伸閱讀: [Inside the Mac OS X Kernel](https://www.youtube.com/watch?v=-7GMHB3Plc8) (錄影) [ Page 8 ] Address space :dart: 摘自 [Linux 核心設計: 不僅是個執行單元的 Process](https://hackmd.io/@sysprog/linux-process): ![](https://i.imgur.com/qM1j7cJ.png) ![](https://i.imgur.com/GSyiqJ8.png) (和作業系統和計算機組織結構的設計有極大的落差) [ Page 9 ] User and Kernel sharing the virtual address space :dart: 摘自 [Linux 核心設計: 記憶體管理](https://hackmd.io/@sysprog/linux-memory) ![](https://i.imgur.com/gCBAKWC.png) 對於記憶體的部分需要知道: * 地址映射 * 記憶體管理的方式 * Page fault [ Page 10 ] Execution contexts :dart: 參見 [Linux 核心設計: 中斷處理和現代架構考量](https://hackmd.io/@sysprog/linux-interrupt) 中斷處理相信是人們不陌生的主題,甚至在中學生的計算機概論教材都出現這字眼,但在 Linux (或任何有規模的作業系統核心) 裡頭,中斷處理背後涉及的硬體特性、多種周邊 I/O、中斷控制器 (如是否支援 nested)、相關的排程和任務調度、延遲和即時處理等等,仍舊讓工程人員頭痛,特別將多核處理器、虛擬化技術,和為了實踐資訊安全而進行的隔離執行納入考量之後。 ![](https://i.imgur.com/YaxH1O1.png) [ Page 11 ] Multi-tasking :dart: 摘自 [Linux 核心設計: 不只挑選任務的排程器](https://hackmd.io/@sysprog/linux-scheduler): 先不講 Linux 排程器,資訊系統存在多種排程器,例如: 1. [erlang scheduler](http://erlang.org/doc/man/scheduler.html): erlang processes 到 threads 間的映射; 2. [nginx](https://nginx.org/en/): HTTP/HTTPS 請求到 processes / application 間的映射; 3. [Memory manager](https://www.kernel.org/doc/html/latest/admin-guide/mm/index.html): virtual memory 到 physical memory 間的映射; 4. [hypervisor](https://en.wikipedia.org/wiki/Hypervisor): VM 到實體硬體間的映射; 5. [Amazon Elastic Compute Cloud (EC2)](https://aws.amazon.com/ec2/): VM 到 hypervisor 間的映射; 6. [Apache Spark](https://spark.apache.org/): map/reduce job 到計算節點間的映射; 經由上述映射,我們可得到額外的好處: * 資源得到更高效的利用; * 由於增加一層 indirection,任務和任務所需要的資源間的耦合度大幅下降; * 更好的服務質量([quality of service](https://en.wikipedia.org/wiki/Quality_of_service), QoS); [ Page 12 ] Preemptive kernel :dart: 參見 [Linux 核心設計: PREEMPT_RT 作為邁向硬即時作業系統的機制](https://hackmd.io/@sysprog/preempt-rt) (綠色: preemptible; 紅色: non-preemptible) **Non-Preemptive** ![](https://i.imgur.com/gNXyQoz.png) [ CONFIG_PREEMPT_NONE ] * Preemption is not allowed in Kernel Mode * Preemption could happen upon returning to user space **Preemption Points in Linux Kernel** ![](https://i.imgur.com/7591V5x.png) [ CONFIG_PREEMPT ] * Implicit preemption in Kernel * preempt_count * Member of thread_info * Preemption could happen when preempt_count == 0 **Fully Preemptive** ![](https://i.imgur.com/rotZoIu.png) [CONFIG_PREEMPT_RT_BASE ] / [ CONFIG_PREEMPT_RT_FULL ] * Difference appears in the interrupt context * Goal: Preempt Everywhere except * Preempt disable * Interrupt disable * Reduce non-preemptible cases in kernel * spin_lock * Interrupt ![](https://i.imgur.com/oLbYnVd.png) > Timeline of merged real-time features in the mainline Linux kernel, most of them coming from the PREEMPT_RT patch [ Page 16 ] ASMP [ Page 17 ] SMP :dart: 參見 [Linux 核心設計: 多核處理器和 spinlock](https://hackmd.io/@sysprog/multicore-locks): [ Pafe 18 ] Scalability :dart: 參見 [Linux 核心設計: Scalability 議題](https://hackmd.io/@sysprog/linux-scalability) Wikipedia 對於 [scalability](https://en.wikipedia.org/wiki/Scalability) 的說明: > A system whose performance improves after adding hardware, proportionally to the capacity added, is said to be a scalable system. 整體效能可隨著硬體的成長而比例性成長,重點是比例。 許多 scalability 議題來自其中一個處理器核要使用另外一個處理器核所寫入的資料,進而導致 cache miss,這兩個處理器核競爭資源和 lock 是常見的狀況,恰好可對比於韓國瑜先生提出的「棋子」和「塞子 」觀點。於是,在多核處理器中的 cache coherence protocol 及其共享資料的處理機制,自然是 Linux 核心的 scalability 關鍵考量。 ![](https://i.imgur.com/hEWU0I9.png) [ [電視辯論](https://youtu.be/ZAdnf1Oqcz8) ] 解決 scalability 的手法有 lock-free, sequence lock, RCU 等等。 延伸閱讀: * [Linux 核心設計: 淺談同步機制](https://hackmd.io/@sysprog/linux-sync) * [Linux 核心設計: RCU 同步機制](https://hackmd.io/@sysprog/linux-rcu) * [從 CPU cache coherence 談 Linux spinlock 可擴展能力議題](https://hackmd.io/@sysprog/linux-spinlock-scalability) [ Page 28 ] Virtual File System :dart: 參見 [Linux 核心設計: 檔案系統概念及實作手法](https://hackmd.io/@sysprog/linux-file-system) ## 細部切入點 依據 UNSW 的 [Advanced Operating Systems](https://www.cse.unsw.edu.au/~cs9242/20/lectures.shtml) (2020) 教材 [Unix and Linux Internals](https://www.cse.unsw.edu.au/~cs9242/20/lectures/08b-linux.pdf)。 [ Page 3 ] 基礎概念: * Process model * File system model * IPC 現代作業系統的關鍵特徵: * Paged virtual memory (3BSD, 1979) * TCP/IP Networking (BSD 4.1, 1983) * Multiprocessing (Vendor Unices such as Sequent’s ‘Balance’, 1984)