---
tags: Linux 核心設計, 進階電腦系統理論與實作, NCKU Linux Kernel Internals, 作業系統
---

# 作業系統術語及概念
contributed by <`RusselCK` >

###### tags: `RusselCK`

## [作業系統術語及概念](https://hackmd.io/@sysprog/linux-concepts#Linux-核心設計-作業系統術語及概念)
我們將回顧若干作業系統術語及概念，像是: 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/)

### User vs. Kernel
* [User mode and kernel mode](https://docs.microsoft.com/zh-tw/windows-hardware/drivers/gettingstarted/user-mode-and-kernel-mode)


* 歷史故事
* 電腦為戰爭而生
* 彈道運算
* 批次處理系統
* 一個一個傳的限制
* Compatible Time-Sharing System (CTSS)
* 第一個分時多工作業系統
* 電腦猶如電話交換機，同時為多個使用者所操作，每位使用者都能依據需求使用終端機，存取到運算和儲存資源，不會和其他使用系統的人有所衝突。
* MIT 和 通用電氣 及 貝爾實驗室 發展 MULTICS 作業系統
* 多人多工多處理器
* UNIX

### Typical operating system architecture

| Typical operating system | [Unikernel](https://en.wikipedia.org/wiki/Unikernel) |
|:----------------------------------------:|:----------------------------------------------------:|
|  |  |
| Device Driver 和 Kernel 不一定為上下關係 | 只為特定功能而生的 OS |

* [Enjoy Netflix? You Should Thank FreeBSD](https://itsfoss.com/netflix-freebsd-cdn/)
* [OSv](https://en.wikipedia.org/wiki/OSv)

### fork、join、process、scheduler
* 摘自 [UNIX 作業系統 fork/exec 系統呼叫的前世今生](https://hackmd.io/@sysprog/unix-fork-exec)
* 1963 年，電腦科學家 Melvin Conway 博士 (以 Conway’s Law 聞名於世) 發表論文〈A Multiprocessor System Design〉，正式提出 fork 思想。

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 的思想最初是作為一種「多處理器並行處理」執行模型
* join 表示多個並行處理的行程由於某種原因不得不進行同步的時間點，也就是多個並行行程會合之處。
* join 也意味著不同的行程必須經過的執行路徑
* 因此減少 join 的數量將會提高並行的效率
* 行程 (後來作業系統中的 process 的概念)
* 由 執行該行程的處理器 (即 CPU processor) 抽象出 scheduler 層面
* **只要滿足系統中的活動處理器數量是總處理器數量和並行行程總和的最小值即可**
* scheduler 可以將多處理器系統的所有處理器和系統所有行程分別看成是統一的資源提供者和消費者來一起排程

digraph Graph2 {
    graph [nodesep=2]
    node [shape=box];
    B [label="一堆處理器(processor)"];
    A [label="一堆行程(process)"];
    
    B -> A [style=dotted dir=both label="    多對多映射"]; 
    
    A -> B [dir=both label="  scheduler"]
}

* 作業系統藉由虛擬化 (virtualize) CPU 資源來達到在單一處理器實作出有如同時多個程式執行於各自的處理器之上的假象 —— 其中關鍵的手法就是分時多工 (time-sharing)

- 《[Operating Systems: Three Easy Pieces](http://pages.cs.wisc.edu/~remzi/OSTEP/)》(可簡稱為 `OSTEP`)
該書的三大主軸:
* 虛擬化 (Virtualization);
* 並行 (Concurrency);
* 持續保存 (Persistence): 主要探討檔案系統;

### Monolithic kernel & Micro-kernel
圖片可以幫助理解，但不要被限制認知

| Monolithic kernel | Micro-kernel |
|:------------------------------------------------------------:|:------------------------------------:|
|  |  |
| 整體的概念 | 設計的哲學 |
| 透過 System call 使用 kernel，user 不會知道 功能怎麼做出來的 | User 知道 kernel 管理哪些東西 |

* [Windows NT](https://zh.wikipedia.org/wiki/Windows_NT体系结构)
* Filesystem in Userspace, [FUSE](https://zh.wikipedia.org/wiki/FUSE)
* [nstack 開發紀錄](https://hackmd.io/@jD9XFdyQS0iyAaFMPYi5Ww/ryfvFmZ0f) (TCP/IP in Userspace)
* [Trusty TEE](https://source.android.com/security/trusty)
* Android 手機 使用的另一個 OS (別於 Android)
* 用於存放隱私資料
* [Secure Enclave](https://support.apple.com/zh-tw/guide/security/sec59b0b31ff/web) in Apple

:::warning
* 兩者的特性是可以結合在一起的
* 截長補短、趨同演化
:::
:dart: [Microkernel 設計與應用 筆記](https://hackmd.io/EuWB_ffqRyaCHCVBqxv4pQ)
- [ ] [Microkernels and capabilities](https://pdos.csail.mit.edu/6.828/2008/lec/l-microkernel.html)
### Mach : 第一代 Micro-kernel
Mach (發音 [mʌk])

Mach 的主要開發者
1. [Richard Rashid](https://en.wikipedia.org/wiki/Richard_Rashid) 自 1991 年就在 **Microsoft** 服務，領導 [Microsoft Research](https://en.wikipedia.org/wiki/Microsoft_Research) 若干技術突破
2. [Avie Tevanian](https://en.wikipedia.org/wiki/Avie_Tevanian) 曾在 [NeXT](https://en.wikipedia.org/wiki/NeXT) 擔任軟體主管，並在 Apple 收購 NeXT 後，轉任 **Apple** Inc. 的技術長 (已退休)。

:::warning
* Microsoft 、 Apple 兩家的 OS 現今都已不是純粹的 Micro-kernel
:::

> 詳細故事請看原共筆

* 第一個 發展出 [**Page based Virtual memory**](https://en.wikipedia.org/wiki/Page_(computer_memory))
* vs. **Swapper** in UNIX
* PID=0的交換行程
* [What is the main purpose of the swapper process in Unix?](https://superuser.com/questions/377572/what-is-the-main-purpose-of-the-swapper-process-in-unix)

### [Hybrid kernel](https://en.wikipedia.org/wiki/Hybrid_kernel)
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’.”

* [Plan 9 Filesystem](https://en.wikipedia.org/wiki/9P_(protocol))
* 已經沒落的 [Plan 9](https://zh.wikipedia.org/wiki/貝爾實驗室九號計畫)，其中的 Filesystem 還存在於 Linux 中
* [HAMMER](https://www.dragonflybsd.org/hammer/) Filesystem in [DragonFly BSD](https://www.dragonflybsd.org/features/)
* The new infrastructure will allow many parts of the kernel to be migrated out into userspace
* 優點:
* more **easily debugged** as they will be smaller, isolated programs, instead of being small parts entwined in a larger chunk of code.
* 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](https://zh.wikipedia.org/wiki/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)

* Mach kernel + BSD personality

* Steve jobs 當時無法賣 便宜的硬體 (和 Apple 搶市場，會被告)
* 轉戰 OS 市場
* [macOS](https://zh.wikipedia.org/wiki/MacOS) (注意寫法)
* [MkLinux](https://en.wikipedia.org/wiki/MkLinux) (for **Microkernel Linux**)
* Steve job 有面試過 Linus Torvalds
* Mach microkernel + Linux personality
:::danger
* 在 90 年代末期，這種混合的方式逐漸式微的原因

1. 發展複雜度變高
* 還要 debug 兩種 kernel
2. Intel 架構 (x86) 的硬體變得非常便宜
* 又剛好這些 kernel 不太支援 Intel 架構
* 即便可移植後，效能也沒有比較好
* Linux 支援 Intel 架構，直接起飛
* MySQL、PHP 也已經針對 Linux 調整
3. Google、Yahoo 等網路公司都使用 Linux、BSD

* 事實上，Linux 也逐漸將這些 "貴族" 血統的 kernel 的一些特質，帶入Linux kernel 中
:::

* Page based Virtual memory 後來也移植到 BSD
> Linux kernel 並非憑空而生，而是移植了很多前人成功的結果

* [Single-system image, SSI](https://zh.wikipedia.org/wiki/单系统映像)
* 透過網路系統，連接多個電腦、伺服器，讓用戶感覺只有使用一個電腦
:::success
大公司在解決的問題 :
* Process 之間的通訊 (InterProcess Communication, IPC)
* 電腦之間的通訊
* Clusters 間的通訊

你的問題 :
* 如何看懂 程式碼，通過面試
:::
==學 Linux 要想清楚，要解決的問題在哪裡==

### Address Space


| Virtual Address, VA | Intermediate Physical Address, IPA | Physical Address, PA |
|:--------------------:|:----------------------------------:|:--------------------:|
| 我們假想的連續記憶體 | KSM | 實際上的記憶體 |

* 若以 VA 直接對應 PA，記憶體很快就會用完
* Kernel Sameoage Merging, KSM
* [KSM(Kernel Samepage Merging) 剖析：Linux 内核中的内存去耦合](https://blog.csdn.net/summer_liuwei/article/details/6013255)

:::info
* 執行、觀察、看 code ，三者並行
* 順著 Linux 的發展方向學習
:::

#### Virtual address space
| x86 (32 bits) | [x86-64](https://zh.wikipedia.org/wiki/X86-64) | [ARMv8-A](https://documentation-service.arm.com/static/5efa1d23dbdee951c1ccdec5?token=) |
|:------------------------------------:|:----------------------------------------------:|:---------------------------------------------------------------------------------------:|
|  |  |  |
| User : Kernel = 3 : 1 | 256 TB (48 bits) | 39 bits |
x86-64
* 儘管虛擬位址有64位元的寬度，但目前的實現機制（以及任何已知處在計劃階段的晶片）並不允許整個16EB的虛擬位址空間都被使用。
* 大多數的作業系統和應用程式在可見的未來都用不到如此巨大的位址空間

ARMv8-A
* In all cases, the first level of table is omitted if the VA input range is restricted to 39 bits.

### Execution contexts

Process context
* process in user mode
* process in kernel mode
* [Zombie process](https://zh.wikipedia.org/wiki/僵尸进程)

Interrupt context
### Multi-tasking

{%youtube Q07PhW5sCEk%}

排程:
- [Memory manager](https://www.kernel.org/doc/html/latest/admin-guide/mm/index.html): virtual memory 到 physical memory 間的映射
- [hypervisor](https://en.wikipedia.org/wiki/Hypervisor): VM 到實體硬體間的映射

種類: (沒有誰較好，看==需求==)
* Cooperative
* 協同式多工 (接力賽跑)
* coroutine
:dart: [goto 筆記](https://hackmd.io/PMiRPO1CQWCjzW8xmOdnyA?view#co-routine-%E6%87%89%E7%94%A8)
* Preemptive
* 搶佔式多工 (搶親)

(綠色: preemptible; 紅色: non-preemptible)

**Non-Preemptive**
[ CONFIG_PREEMPT_NONE ]
* 在 Kernel Mode 不能被插隊
* 只有在 user space 可以被插隊

**Preemption Points in Linux Kernel**
[ CONFIG_PREEMPT ]
* 適合給會有週期性任務
* 互動、音軌
* Implicit preemption in Kernel
* preempt_count (安排定時可插隊)
* Member of thread_info
* Preemption could happen when preempt_count == 0

**Fully Preemptive**
[CONFIG_PREEMPT_RT_BASE ] / [ CONFIG_PREEMPT_RT_FULL ]

> Timeline of merged real-time features in the mainline Linux kernel, most of them coming from the PREEMPT_RT patch

### Asymmetric / Symmetric MultiProcessing (ASMP / SMP)

| ASMP | SMP |
|:------------------------------------:|:------------------------------------:|
|  |  |

:dart: [spinlock & multicore 筆記]()

### CPU Scalability
整體效能可隨著硬體的成長而比例性成長，重點是 ==**比例**==。

限制 :
* 競爭資源和 lock
* cache coherence protocol 及其共享資料的處理機制

解決方法 :
* 同步機制
* lock-free, sequence lock, RCU
* 不同情境配不同的 lock

:::info
* 作業系統 即 政治
* 資源分配
:::
:dart: [同步機制 筆記]()

### Linux development model

* Open source, [GPLv2 License](https://zh.wikipedia.org/wiki/GNU通用公共许可证)
* 已有 GPLv3 ，但某些開發者已登出，無法更改授權
* Development cycle: **3 – 4 months**
* Features are only allowed in the **merge window**
* 修改整合錯誤
* [Linus 親自教你 C 語言 array argument 的使用](https://hackmd.io/@sysprog/c-array-argument)

* 直接看 source code 和 問作者 最快
* 去 google 找老半天沒比較好

推薦閱讀順序:
1. Documentation
2. include (比較少改動)
...

### Linux kernel architecture


* arch (Architecture)
* Device drivers
* Process management
* Memory management
* Block I/O management
* Virtual Filesystem Switch
* Networking stack
* Linux Security Modules

### 進階課程
> 影片 2:50:00 ~

依據 UNSW 的 [Advanced Operating Systems](https://www.cse.unsw.edu.au/~cs9242/19/lectures.shtml) (2019) 教材 [Unix and Linux Internals](https://www.cse.unsw.edu.au/~cs9242/19/lectures/07a-unix.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)