---
# System prepended metadata

title: 課程｜作業系統程式
tags: [課程]

---

# 作業系統程式
## System Call
- `Dual Mode` (雙重模式):
    - 必須要有硬體的支持才可以實現，CPU 內有「Mode bit」以區分現在狀態為何
    - 目的：確保任何 process 執行時，不會更動其他 process 的變數，或是占用或更改 OS 內部的資源
    - `User Mode`：透過 OS 所提供的 system call，切換到 kernel mode 取得資源
    - `Kernel Mode`：可以存取硬體支援的指令動作
- System Call 的意義
    - process 向 OS 提出請求，以取得 kernel 所提供的服務
- 種類：
    - Process Control : `fork(), wait4()`
    - File Management : `open(), read(), write(), close()`
    - Device Management : `ioctl()`
    - Information Maintenance : `getpid(), getppid(), getpgid(), setpgid()`
    - Communication : `pipe(), socket()`
## I/O
- 依照是否被 block 區分
    - `Synchronous`
        - `Blocking`
            - 等待直到 I/O 完成
            - 系統歸還控制權之前， process 都不能做任何的事情
        - `Nonblocking`
            - 若 request 無法得到回覆, 就直接回傳 error
            - 實務上會用 `polling` 機制，不斷地去問 kernel 說資料好了沒
        - `I/O multiplexing` (常見的 API 是 `select` 或 `poll`)
            - 要用兩次 system call 
            - `select` : 同時監視多個 socket，block 住直到任一個 I/O 完成
            - `recvfrom` : 去該 socket 取回資料
        - `Signal Driven`
            - 透過 `sigaction` 去設定一個 signal handler
            - 當 kernel 資料準備好的時候， 發 SIGIO 信號，再由 handler 去讀取
    - `Asynchronous` (非同步)
        - 透過 `aio_read` 及 `aio_sigevent` 設定 ( [Example](https://blog.csdn.net/eZiMu/article/details/54892088) )
        - kernel 在整個操作完成 (wait + copy) 後發 signal 通知
    - ![](https://i.imgur.com/2fWjfUG.png)
- 依照有無 buffer 區分
    - `Buffer Cache` : Kernel 當中的緩衝區，避免每次都對硬碟操作
    - `Buffer` : 
    - Unbuffered I/O
        - `open, close, read, write, lseek, dup, fcntl, ioctl`
        - 每次 read, write 都會調用 system call
    - Buffered I/O
        - `fread, fwrite, scanf, printf`
        - 使用到 C library 提供的 buffer
        - 可使用 `fflush()` 清空 buffer ( [說明](https://www.itread01.com/content/1550266048.html) )

## File System
- File 在系統的儲存
    - `File Descriptor table` ( 每個 process 一個 )
        - 每個 open() 的 file 會有一個編號 `File Descriptor`
        - 紀錄跟 fd 有關的一些參數及指向 System-wide table 的指針
    - `System-wide Open-File table` ( 系統共用一個 )
        - 引用計數 `reference count`，當降為 0 時會把資料清空
        - 下一次讀或寫的位置 (offset)
        - 指向 V-node table 的指針
    - `V-node table` ( 系統共用一個 )
        - 系統真正儲存檔案 meta data 的地方
        - 包含檔案權限、擁有者、類型、檔案長度
- 一些跟 file 有關的函數
    - `int open(const char *pathname, int flags, mode_t mode);`
    - `ssize_t read(int fd, void *buf, size_t cnt);`
    - `ssize_t write(int fd, const void *buf, size_t cnt);`
    - `off_t lseek(int fd, off_t offset, int whence);`
    - `int dup(int oldfd);`
    - `int dup2(int oldfd, int newfd);`
    - ```clike=
        int fd1 = open("hello.txt", O_RDONLY, 0);
        int fd2 = open("hello.txt", O_RDONLY, 0);
        read(fd1, &c, 1);
        read(fd2, &c, 1);
        printf("%c\n",c);     // 印出第一個字元
    - ```clike=
        int fd = open("hello.txt", O_RDONLY, 0);
        if(fork()==0){        // child 
            read(fd, &c, 1);
            exit(0);
        }else{                //parent
            wait(NULL);
            read(fd, &c, 1);
            printf("%c\n",c); // 印出第二個字元
            exit(0);
        }
    - ```clike=
        int fd1 = open("hello.txt", O_RDONLY, 0);
        read(fd1, &c, 1);
        dup2(fd1, fd2)
        read(fd2, &c, 1);
        printf("%c\n",c);    // 印出第二個字元
- 檔案的 meta data 
    - 存在 inode table 中，可在 C 中用 `stat()` 得到
    - 1.`st_mode`: 檔案的類型和存取許可權
        - 一般 File 由 RWX 來決定是否可以讀、寫、執行，e.g. `-rw-r--r--` = `644`
            - Owner 可讀寫
            - 同 group 可讀
            - 其他人可讀
        - Directory
            - R : 列出目錄底下所有檔案
            - W : 更改目錄 (新增刪除檔案)
            - X : 遍歷檔案 (search)
    - 2.檔案的時間戳
        - ctime 指 inode 上一次變動的時間
        - mtime 指檔案內容上一次變動的時間
        - atime 指檔案上一次開啟的時間
    - 3.檔案位元組數
    - 4.owner 的 `UID` 及檔案的 `GID`
    - 5.連結數: 有多少檔名指向這個檔案
- [inode table](https://www.ruanyifeng.com/blog/2011/12/inode.html)
    - 硬碟格式化時被區分成資料區 (檔案本身) 及 inode 區 (meta data)
        - 有可能發生 inode 已經用光，但是 disk 還未存滿的情況
    - 除了檔名以外的所有檔案資訊，都存在 inode table 中
    - `目錄`本身也是一種文件，只存有兩樣東西
        - 檔案名
        - 對應的 inode 號碼
    - 檔案的 Link
        - Linux系統允許，不同文件名可以指向同一個 inode 號碼
        - 目錄創立時，會自動加入 `.` 以及 `..` 兩個連結
            - 因此 parent 的連結數會多一
            - 每個目錄的連結數，總是等於 2 加上它的子目錄總數
        - `Hard Link`
            - 連結到 Inode 本身
            - 對檔案內容進行修改，會影響到所有檔案名
            - 刪除一個檔案名，不影響另一個檔案名的訪問
            ```c=
            $ ls -li
            total 4
            27134321 -rw-rw-r-- 1 mark mark 2  六  19 16:07 a.txt
            
            $ ln a.txt b.txt
            $ ls -li
            total 8
            27134321 -rw-rw-r-- 2 mark mark 2  六  19 16:07 a.txt
            27134321 -rw-rw-r-- 2 mark mark 2  六  19 16:07 b.txt
            // 兩個其實是同一個檔案
            ```
        - `Soft Link` 又稱為 Symbolic Link
            - 檔案 B 的內容是檔案 A 的路徑，則讀取檔案 B 最終也會導向檔案 A
            - 檔案 B 依賴於檔案 A 而存在
                - 如果刪除了檔案 A，打開檔案 B 就會報錯："No such file or directory"
                - 建立檔案 B 時，檔案 A 的連結數不會增加
            ```c=
            $ ls -li
            total 4
            27134321 -rw-rw-r-- 1 mark mark 2  六  19 16:07 a.txt
            $ ls -li
            total 4
            27134321 -rw-rw-r-- 1 mark mark 2  六  19 16:07 a.txt
            27134320 lrwxrwxrwx 1 mark mark 5  六  19 16:08 b.txt -> a.txt
            // b 的內容是 a 的位置
            ```
- 每個 process 的權限
    - 分為 real UID/GID，及 effective UID/GID
        - 根據 effective ID 決定可否存取檔案
    - 若檔案有 Set-UID，則 effective UID 會變成擁有者的 UID
        - `chmod 4xxx file` 或 `chmod u+s file`
        - 權限將由 `0xxx` 變成 `4xxx`
        - 舉例: 如果 rm 有 setuid (owner 是 root)，則任意使用者可以任意刪檔案
    - 若檔案有 Set-GID，則 effective GID 會變成擁有者的 GID
        - `chmod 2xxx file` 或 `chmod g+s file`
        - 權限將由 `0xxx` 變成 `2xxx`
        - 舉例: 如果某目錄有 setgid，則使用者於內建立檔案會有相同的 GID
    - Sticky Bit 黏滯位元
        - `chmod 1xxx file` 或 `chmod +t dir`
        - 一般而言，具有目錄寫和執行權限的用戶，可以刪除和移動其中的文件
        - 若開啟 Sticky Bit，只有所有者 root 可以刪除或移動該文件
        - 用於 `/tmp` 目錄，共用目錄但刪除或移動其他用戶的文件
## Process
- Process
    - 定義: 執行起來的 program，是 OS 分配資源之對象單位
    - 一個 process 在記憶體中有以下區段
        - Text Section : 存程式碼
        - Data Section : 存全域變數
            - 未初始化區段又稱為 BSS 區段
        - Heap Section : 存動態空間
        - Stack Section : 存區域變數
- Process status
    - New : 準備要 load 到 memory，初始化各個 section
    - Ready : 競爭 CPU，在 queue 裡面等待被 OS 排程
    - Running : 執行程式
        - 如果 Interrupt 則回到 ready
        - 如果要做 I/O 則進入 waiting
    - Waiting : process 想做 I/O 造成 idle
    - Terminated : 完成
- Process Control Block (PCB)
    - 放在 Memory 裡面，而且是 Kernel Space 
    - 內容
        - Process State
        - Program Counter
        - CPU registers
        - CPU scheduling information
        - Memory-management information
        - I/O status information
        - Accounting information
- Context Switch
    - 把 CPU 上正在執行的 process，switch 成另外一個 process 的動作就叫做 context switch
    - 舊的狀態要存進 PCB，並從新的 process 的 PCB 讀入狀態
- CPU Scheduling
    - CPU 由三種不同類型排班器同時排班
        - Short-Term: 決定要從 ready queue 執行哪個 process
        - Long-Term: 決定何時要把 process 由 disk 讀到 memory
        - Medium-Term: 決定何時把 process Swap 回 disk，為了空出 disk
    - 排班演算法 : 決定要從 ready queue 執行哪個 process 的策略
        - First Come First Served 先到先做
        - Shortest Job First 最短的工作先做
        - Shortest Remaining Time First 最短剩餘時間先做
        - Priority Scheduling 優先權排班
        - Round Robin 依序循環
        - Multilevel Queue 多層佇列
        - Multilevel Feedback Queue 多層回饋佇列
    - 可搶先排班 (Preemptive)
        - 當一個 process 尚未執行完時，能否被另一個 process 插隊
        - FCFS 是 NonPreemptive，RR 是 Preemptive，而 SJF 及 PS 則可自行決定是否被插隊
    - Dispatcher 負責將 CPU 控制權交給被選中的 Process
- Process 創立與終結
    - 系統一定是由第一個 Process 不斷創造其他的，所以可以形成一棵樹
    - 有關的函數
        - `pid_t fork(void);`
            - parent 的 return 值是 child PID，child 得到的是 0
        - `int execve(const char *path, char *const argv[], char *const envp[]);`
        - `pid_t wait(int *wstatus);`
            - 為了同步使用
        - `noreturn void exit(int status);`
        - `pid_t vfork(void);`
            - child 與 parent 共用記憶體，基本上除了 PID 之外的記憶體都共用
    - 當 process 結束時，PCB 資料不會馬上清空，為了讓 parent process 能夠讀取 child process 的退出狀態
        - `Zombie Process`: Child process 已完成執行，但 Parent process 尚未回收其 PCB，直到以下事情發生
            - Parent process 調用 wait() 讀取退出狀態
            - Parent process 完成執行，child process 由 init（PID 為 1）收養並退出
        - `Orphan Process`: Parent process 已完成執行，Child 仍在正常執行
            - Parent process 由 init（PID 為 1）收養並 wait() 其退出
- Process 之間溝通 (Inter Process Communication)
    - Shared memory
    - Message passing
    - Sockets
    - Remote Procedure Calls (RPC)
    - [Pipe and FIFO](https://yayaya6d.pixnet.net/blog/post/350045449-linux%E5%90%84%E7%A8%AE%E9%9B%9C%E8%AB%87--process%E9%96%93%E7%9A%84%E6%BA%9D%E9%80%9A%EF%BC%9Apipe%E5%92%8Cfifo)
- Interrupt 中斷
    - Interrupt 的種類
        - External Interrupt（外部中斷）: CPU 外的週邊元件所引起的。
            - e.g. I/O Complete Interrupt, I/O Device error
        - Internal Interrupt（內部中斷）:不合法的用法所引起的。
            - e.g. Debug、Divide-by-zero、overflow
        - Software Interrupt（軟體中斷）：使用者程式在執行時，若需要OS 提供服務時，會藉由 System Call 來呼叫OS 執行對應的 service routine，完成服務請求後，再將結果傳回給使用者程式。
    - Interrupt 的處理流程
        - 暫停目前 process ，並保存此process 當時執行狀況
        - 根據 `Interrupt ID` 查尋 Interrupt vector。
        - 取得 `ISR（Interrupt Service Routine）` 起始位址。
        - 執行 ISR ，完成後回復原先中斷前的執行。
 
## Thread
- Thread
    - 分配 CPU Time 的單位
    - 共用
        - Code section
        - Data section
        - OS resources (例如 open file 及 signal)
    - 自己擁有
        - thread ID
        - program counter
        - register set
        - stack
- Multithreading Models
    - User threads
        - 使用者管理，透過 Thread library 調用
        - user thread 要完成的工作，會連接到 kernel thread 來完成
    - Kernel threads
        - OS 管理
    - Many-to-one Model
        - 同一時間只有一個 thread 在存取 kernel，沒有平行化
        - 可能會因為一支 thread「卡住」而導致整個 process 跟著「卡住」
    - One-to-One Model
        - 當一個 thread blocking 時，其他 thread 仍可繼續執行
        - 產生一個 user thread 時，需連帶產生一個 kernel thread，會佔用較多資源
    - Many-to-Many Model
        - 可以對每個 process 限制其對應 kernel threads 的數量
        - 也可以對整個作業系統限制 kernel threads 的總量
## Memory
- 記憶體空間可區分成 
    - User Space：處在 User Mode 可以使用的空間
    - Kernel Space：處在 Kernel Mode 才能使用的空間
- 程式 Load 到記憶體
    - Dynamic Loading
        - 不一次 load 完所有程式，而是用到才 load
    - Static Linking
        - 整個 library 都會被 load 進 memory
    - Dynamic Linking
        - runtime 時檢查是否有其他程式用到相同的 library
        - 有則 link 過去，沒有要先 load 再 link
        - 避免重複把 library load 到 memory
    - Address Binding
        - 決定一個程式要 load 到記憶體的哪裡
        - 在 Compile Time 決定
        - 在 Load Time 決定
        - 在 Execution Time 決定
    - Swap
        - 程式在記憶體執行時，可能被暫時置換到備份記憶體(backing store)
- 記憶體使用分布
    - Fixed-partition allocation: 一開始就先切好固定大小
    - Variable-size partition: 分配 process 在足夠大的地方
    - Dynamic Storage Allocation
        - First-fit
        - Best-fit
        - Worst-fit
    - Fragmentation 斷裂
        - External fragmentation: process 間有零碎的記憶體區塊
        - Internal fragmentation: process 內有零碎的記憶體區塊
        - 解決方法: 定期清理整理壓縮(compaction)
- 記憶體位置對應
    - 記憶體位置區分為 Logical 及 Physical 以方便管理
        - Physical 為真正記憶體位置
        - Logical(Virtual) 為虛擬位址
    - `Memory-Management Unit (MMU)`
        - 把 virtual address 對應到 physical address
        - 硬體，整合在 CPU 裡面
    - Page / Frame Size : 通常都是 4KB 或 8KB
        - `Frame`: 將實體記憶體切割成相同大小的 blocks
        - `Page`: 將虛擬記憶體切割成相同大小的 blocks
- `Page Table`
    - 每個 Process 都有一個 Page Table
    - 把 Virtual Address : `p d` -> Physical Address `f d`
        - 記憶體位置可以分為頁數 (page number) 及頁偏移量 (offset)
        - page number p 對應到 frame number f
    - 做 Context Switch 時，會把 PCB 中的 page table 資訊 load 到 PTBR 及 PTLR
    - 真正要 access data 要做兩次 memory access
        - 根據 PTBR 到實體記憶體存取 page table
        - 根據 page table 得到 physical Address `f d` 再存取 data
- `Translation Look Aside Buffer`
    - 像是 MMU 的 Cache，很快的
    - 一樣是把 page number 對應到 frame number
        - 有 -> 輸出 frame 位置，記憶體只存取一次
        - 無 -> 到記憶體取 page table 再查，記憶體存取兩次
    - 做 Context Switch 時，TLB 會被 flush
- Page Table Memory Structure
    - 有時候很難 allocate 一塊空間去放 Page Table，因此有不同的結構
    - Hierarchical page table(層次式分頁表)
    - Hashed page table(雜湊分頁表)
    - Inverted page table(反轉分頁表)
- Segmentation
    - 系統不一定只能將記憶體切割成 pages，也可以根據目的有不同切法
    - Segmentation Table
        - Virtual Addr: `(seg#, offset)` -> Physical Addr `(Base, limit, offset)`
    - `Segmentation With Paging`
        - 混合了 paging 及 segmentation
        - 先把 Process 做 Segment，再把 Segment 做 Paging 
- Memory Mapped File
    - 把檔案對應到一段虛擬記憶體
    - 主要用處是增加 I/O 效能，特別是用於大檔案
    - 常用在 screen、printer
## Virtual Memory
- Virtual Memory
    - 有些資料會存放在disk上，當有需要時再交換進實體記憶體
    - Logical address space 空間大於 physical address space
    - 記憶體空間可以和許多 process 共享，提高 CPU 效率
    - 可以不用一次 load 所有東西到實體記憶體而加速
- Demand paging
    - 當 page 被需要時，才把 page swap 進實體記憶體
    - Page table 中會加入一個 valid-invalid bit的值，紀錄 page 是不是在實體記憶體中
    - `Page Fault`: 當程式要使用的記憶體還沒 swap 進記憶體
        - 1.檢查是否為合法的記憶體存取
            - 若不是則直接 abort
        - 2.找到一個free frame
        - 3.將資料由 disk swap 進入free frame
        - 4.將 table 的 valid-invalid bit 的值標示為 valid
        - 5.繼續執行因為 page fault 出錯的指令
    - 一開始執行 process 時，會不斷出現 page fault 稱為 pure demand paging
- Copy-on-Write
    - fork 出 child process 時，理論上要幫他配置實體記憶體空間
    - 暫時允許兩 process 共用實體記憶體空間
    - 直到 frame 被其中一個寫入資料時，才會複製一個 page 出來
- [Cache 快取記憶體有三種對映函數](https://hackmd.io/@sysprog/HkW3Dr1Rb?type=view)
    - Direct Mapped: 每個 data 被對應到唯一位置
    - Fully Associative: 任何 data 可以被 cache 在任何一個 Cache Line 裡
    - n-way associative: 每個 data 被對應到一個 set 中
- Page Replacement
    - 用 modify(dirty) bit 判斷 page 是否有被修改過，如果有被修改過，就會被 swap 到 disk 去，釋放空間給其他 page
    - Page Replacement步驟
        - 在 disk 找需要用的page
        - 找一個free frame
            - 有，直接使用
            - 沒有，就找一個 victim frame (用dirty bit找)作 page replacement
        - 將 page 載入 free frame，更新 page 和 frame table
        - 從剛剛中斷的地方開始執行
    - `Page Replacement Algorithm`
        - First-In-First-Out (FIFO) Algorithm
            - 先進frame中的page會先被替換掉
            - `Belady’s Anomaly`: 增加 frame 數量，page fault 次數變多
        - Optimal (Belady) Algorithm
            - 將未來最長時間用不到的 page 給交換出去
            - 預測未來，很難做到
        - LRU Algorithm (Least Recently Used)
            - 將目前最長時間未用到的 page 給交換出去
            - [leetocde 146](https://leetcode.com/problems/lru-cache/)
        - Second-Chance Algorithm
            - 得到 frame 時，設定其 reference bit 為 1
            - 要尋找 vimctim frame 時，基於 FIFO
                - reference bit 為 1，會將 reference bit 改為0，給他一次機會
                - reference bit 為 0，把他交換掉
            - Enhanced Second-Chance Algorithm
                - 用 (reference bit , dirty bit) 判斷
        - Counting Algorithms (LFU, MFU)
            - Least Frequently Used
                - 將目前用到最少次的 page 給交換出去
                - [leetcode 460](https://leetcode.com/problems/lfu-cache/)
            - Most frequently used algorithm
                - 將目前用到最多次的 page 給交換出去
    - Trashing: 花在 paging 的時間比 executing 多
- Working-set model
    - 預估 process 在一段時間內用了多少 page
    - 系統根據此決定要配置多少 frame 給此 process
## Synchronization
- Race Condition
    - 兩個 process 都對`共用資源`進行操作，而根據執行順序結果會不同
    - 因為一個高階語言指令在翻譯成機器碼時，通常會變成很多個指令，這讓修改的動作無法在單一指令內完成
- Atomic Operation
    - 指一系列不會被 context switch 的指令
    - 因為某些步驟交錯會造成結果錯誤，因此要系統保證
    - 舉例而言
        - Appending to a file
        - Seeking and reading/writing
        - Creating a file
- Critical Section
    - 存取共用資源的程式片段，而這些片段有無法同時被多個執行緒存取的特性，用來保護共用資源，以解決 race condition 問題
    - 三要件
        - Mutual Exclution (互斥存取)
            - 不會有兩個 process 同時間在 critical-section 中工作。
        - Progress (進行)
            - 當沒有 process 要在 critical-section 中執行時，不能阻擋其他想要進入 critical section 工作的 process 進入
        - Bounded Waiting (有限等待)
            - 若有 n 個 Process 在等待，則最長等待只能 (n-1) 個 Process 時間，不能被其他 process 一直占用
    - 軟體解 Peterson's Solution (兩個 process)
        ```clike=
        do{
            flag[i] = true;
            turn = j;
            while(flag[j]=true && turn==j){}
            //critical section
            flag[i] = flase;
            //remainder section
        }while(true);
        ```
        - 符合三要件
        - 只有 turn 不符合 Progress，一個 process 不能連續進去
        - 只有 flag 會形成 deadlock
    - 軟體解 Bakery algorithm (n processes)
        ```clike=
        do{
            choose[i]=true;
            num[i] = max(num[0], num[1], ..., num[n-1])+1 //抽號碼牌
            choose[i]=false;
            for(j=0;j<n;j++){
                while(choose[j]); //等待所有想領號碼牌的程式抽號碼牌
                while((num[j]!=0) && (num[j],j)<(num[i],i)); // 等待號碼牌小的程式先執行，若號碼牌相同則程式id小的優先
            }
            //critical section
            num[i] = 0;         //重置號碼牌為0，待下次重新排隊再抽號碼牌
            //remainder section
        }while(1)
        ```
        - 先領一張號碼牌，號碼最小的優先進入CS。
        - 透過 `while(choose[j]);` 避免誤以為自己抽到最小號碼牌
    - 硬體解 Atomic TestAndSet
        ```clike=
        bool TestAndSet(bool &lock){
            bool value = lock;
            lock = true;
            return value
        }
        // process code
        do{
            while( TestAndSet(bool &lock));
            //critical section
            lock = false;
            //remainder section
        }while(1)
        ```
        - 這個方法並不能保證 bounded wait
- 同步
    - `Mutex Lock 互斥鎖`
        ```clike=
        mutex m;
        void print_thread_id (int id) {
            m.lock();
            // critical section
            cout << "thread #" << id << endl;
            m.unlock();
        }
        ```
    - `Conditional Variable 條件變數`
        ```clike=
        mutex m;
        int c = 0;
        void fun1(){
            m.lock();
            // do something 1
            c = 1;
            m.unlock();
            cond.notify_one();
        }
        void fun2(){
            unique_lock<mutex> ulocker(m);
            cond.wait(ulocker,[=](){return c==1;});
            // do something 2
        }
        ```
    - `Semaphores 號誌`
        - Semaphore 是一個同步物件，用於保持在 0 至指定最大值之間的一個計數值
            - 當完成一次對 semaphore 的等待，計數值減一
            - 當完成一次對 semaphore 的釋放，計數值加一
            ```clike=
            //大致上會做以下的事情
            void wait(S){
                while (S <= 0) ;
                S--;
            }
            void signal(S){
                S++;
            }
            ```
        - 要保證對 semaphore 的操作是 atomic operation
        - 決定有多少 thread 可以進入 access 資源
            - 若初始化決定只能有一個，則可以建立 critical section
        - POSIX standard 裡就有實作，因為作業系統很需要
            ```clile=
            #include <semaphore.h>
            sem_t sem;
            sem_init(&sem);    // 設定初始值，決定
            sem_wait(&sem);    // S--
            // 只能有限的 thread 進入
            sem_post(&sem);    // S++
            ```
    - `SpinLock 自旋鎖`
        - 透過 busy waiting 實現的互斥鎖稱為 SpinLock 自旋鎖
- Classical Problems
    - Bounded-Buffer Problem
        - N 個 buffers，Producer 製造項目，Consumer 消耗項目
    - Readers and Writers Problem
        - 有一個檔案或資料，有很多 process 要平行存取
        - readers：只能讀data set，只能讀，不能更新。可允許同時讀資料。
        - writers：可同時讀寫。同一時間只能有一個writer取得分享資料。
    - Dining-Philosophers Problem
        - 五個哲學家，五個筷子，每個哲學家的動作只有思考和吃飯
    - Sleeping Barber Problem
        - Barber : 沒有客人則等待，否則一個一個剪。
        - Customer : 若有椅子可坐，則坐下等待，否則離開店內。
- `Monitors` 是一個用來解決同步問題的高階資料結構
- `DeadLock`
    - Deadlock成立的四個必要條件
        - Mutual exclusion(互斥): 資源在同一時間內，至多只允許一個 process 使用
        - Hold & wait(持有並等待): process 持有部分資源且又在等待其它 processes 所持有的資源
        - No preemption(不可強取豪奪): process 不可搶奪其它waiting process 所持有的資源，除非其自願釋放
        - Circular waiting(循環等待): `P0→P1→P2→...→Pn→P0`
    - 系統處理 Deadlock 的方法
        - 1.使用 protocol 確保系統永遠不會進入死結狀態
        - 2.允許系統進入 deadlocked state，然後偵測它，恢復它
        - 3.我們可以完全無視這些問題，假裝這些問題從來不曾發生過
            - 最多作業系統使用的方式，讓使用者自行處理
    - Resource-Allocation Graph
        - ![](https://i.imgur.com/O8XbpFU.png)
        - P 指向 R 表示正在要求資源；R 指向 P 表示已經分配資源
    - Safety演算法
    - Banker's演算法
    - Deadlock detection 演算法

## Signal
- 信號
    - 用來通知 process 發生了某事件
    - 並不給傳遞任何資料給 process
    - 處理方法可以分為三類
        - 指定 handler，由該函數來處理
        - 忽略某個信號，對該信號不做任何處理
        - 對該信號的處理保留系統的預設值
    - 透過 `kill -l` 可看到所有的訊號表
        - ![](https://i.imgur.com/NE230kl.png)
- 處理 signal
    - 透過 `signal(int signum, void (*handler)(int));` 設定 handler
    ```clike=
    #include <signal.h>
    #include <unistd.h>
    #include <stdio.h>
    void handler(int signo) { // 信號處理常式，其中 signo 將會得到信號的值
        if(signo==SIGUSR1) {
            printf("Get a signal -- SIGUSR1\n");
        }else if(signo==SIGUSR2){
            printf("Get a signal -- SIGUSR2\n");
        }else{
            printf("Get a signal %d \n", signo);
        }
        fflush(stdout);
        return;
    }
    int main() {
        signal(SIGUSR1, handler);
        signal(SIGUSR2, handler);
        for(;;)    pause;
    }
    ```
    ```c=
    $ ./a.out &
    [2] 31423
    $ kill -SIGUSR1 31423
    Get a signal -- SIGUSR1
    $ kill 31423
    [2]-  Terminated              ./a.out
    ```
- 若處理不好程式會壞掉
    - 在 handler 尚未處理完時就接受到另一個 signal
    - 還沒有準備好要接受時收到
        ```c=
        int main() {
            signal(SIGINT, handler);
            while(flag == 0){
                //萬一在 pause 前收到 signal 就會壞掉
                pause();
            }
            // do something
        }
        void handler(int signo) {
            flag = 1;
        }
        ```
## 其他
- RAID
    - ![](https://i.imgur.com/8onamxc.png)![](https://i.imgur.com/uk5i6Ak.png)
    - RAID 0 : 平行
        - 將兩個以上的磁碟並聯起來，成為一個大容量的磁碟
        - 速度最快，但是不具備容錯能力
    - RAID 1 : 備份
        - N個磁碟相互作鏡像
        - 安全性最好
    - RAID 2
        - RAID 0的改良版，以漢明碼（Hamming Code）的方式將資料進行編碼
        - ![](https://i.imgur.com/MBlcy6H.png)
    - RAID 10: 底層備份上層平行 / RAID 01: 底層平行上層備份
        - ![](https://i.imgur.com/ImUwJYH.png)![](https://i.imgur.com/V20s4Bh.png)
    - RAID 5: 透過奇偶校驗而有 Fault tolerance
    - RAID 6: 增加第二個獨立的奇偶校驗資訊塊
- CAP定理
    - 在分散式系統中，這三個特性只能同時滿足兩個。也就是說，我們必須要做出取捨（trade-off）。
    - 一致性（Consistency）：使用者讀到的”總是”最新的資料
    - 可用性（Availability）：使用者的請求”總是”可以獲得回應，也就是可以正常讀寫（回傳錯誤訊息並不算滿足可用性）
    - 分區容錯性（Partition tolerance）：就算網路出現問題導致資料分區，整個系統仍然要可以繼續運作
- Global Interpreter Lock ( [GIL](https://blog.gcos.me/post/2019-11-26_python-gil-and-thread-safe/) )
    - Python 的多線程程序並不能利用多核 CPU 的優勢
    - 全局解釋器鎖 GIL 本質上是類似作業系統的 Mutex
    - 每一個 Python 線程，在 CPython 解釋器中執行時，都會先鎖住自己的線程，阻止別的線程執行
    - 但以下程式碼也不是 thread safe
        ```python=
        import threading 
        n = 0 
        def foo(): 
            global n 
            n += 1 
        # Multi-Threading
        threads = []
        for i in range(100): 
            t = threading.Thread(target=foo) 
            threads.append(t) 
        for t in threads: 
            t.start() 
        for t in threads: 
            t.join() 
        print(n)
        # Show ByteCodes
        import dis
        dis.dis(foo)
        ```
        - 雖然 GIL 確保同時僅運行一個 Thread
        - 但 Python 要在 Threads 間切換時，只能在 Bytecode instructions 間，而不是 Python 程式碼。
        - `foo()` 的程式碼換成 Bytecode 不只一個指令
## Reference
- [郭大維教學](https://www.youtube.com/playlist?list=PLco3ZjBUnBUKNn0ANhQ1N7aJbYUmMlgc8)
- [施吉昇教學](https://systemprogrammingatntu.github.io/)
- [周志遠教學](https://ocw.nthu.edu.tw/ocw/index.php?page=course&cid=141)
- [OS作業系統學習](https://ithelp.ithome.com.tw/users/20112132/ironman/1884)
- [OS筆記](https://meteorv.dev/OS/OS/)
- [考題](/sINX_c7GQjK0zJDL1oyZ8w)


