# 作業系統程式
## 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 通知
- 
- 依照有無 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 本身
- 對檔案內容進行修改，會影響到所有檔案名
- 刪除一個檔案名，不影響另一個檔案名的訪問

            $ 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 的連結數不會增加

            $ 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)

        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)

        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

        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 互斥鎖`

        mutex m;
        void print_thread_id (int id) {
            m.lock();
            // critical section
            cout << "thread #" << id << endl;
            m.unlock();
        }

- `Conditional Variable 條件變數`

        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 的釋放，計數值加一

            //大致上會做以下的事情
            void wait(S){
                while (S <= 0) ;
                S--;
            }
            void signal(S){
                S++;
            }

- 要保證對 semaphore 的操作是 atomic operation
- 決定有多少 thread 可以進入 access 資源
- 若初始化決定只能有一個，則可以建立 critical section
- POSIX standard 裡就有實作，因為作業系統很需要

            #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
- 
- P 指向 R 表示正在要求資源；R 指向 P 表示已經分配資源
- Safety演算法
- Banker's演算法
- Deadlock detection 演算法

## Signal
- 信號
- 用來通知 process 發生了某事件
- 並不給傳遞任何資料給 process
- 處理方法可以分為三類
- 指定 handler，由該函數來處理
- 忽略某個信號，對該信號不做任何處理
- 對該信號的處理保留系統的預設值
- 透過 `kill -l` 可看到所有的訊號表
- 
- 處理 signal
- 透過 `signal(int signum, void (*handler)(int));` 設定 handler

    #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;
    }

    $ ./a.out &
    [2] 31423
    $ kill -SIGUSR1 31423
    Get a signal -- SIGUSR1
    $ kill 31423
    [2]-  Terminated              ./a.out

- 若處理不好程式會壞掉
- 在 handler 尚未處理完時就接受到另一個 signal
- 還沒有準備好要接受時收到

        int main() {
            signal(SIGINT, handler);
            while(flag == 0){
                //萬一在 pause 前收到 signal 就會壞掉
                pause();
            }
            // do something
        }
        void handler(int signo) {
            flag = 1;
        }

## 其他
- RAID
- 
- RAID 0 : 平行
- 將兩個以上的磁碟並聯起來，成為一個大容量的磁碟
- 速度最快，但是不具備容錯能力
- RAID 1 : 備份
- N個磁碟相互作鏡像
- 安全性最好
- RAID 2
- RAID 0的改良版，以漢明碼（Hamming Code）的方式將資料進行編碼
- 
- RAID 10: 底層備份上層平行 / RAID 01: 底層平行上層備份
- 
- 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

        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)