# OS Midterm Review
## Chapter 1: Introduction
:::info
### OS 的功能
- 資源分配者
- 監控使用者程式的執行，以防止不正常的運作造成對系統的危害
#### 一個標準 PC 的 OS 應該提供的功能：
- 行程管理（Processing management）
- 記憶體管理（Memory management）
- 檔案系統（File system）
- 網路通訊（Networking）
- 安全機制（Security）
- 使用者介面（User interface）
- 驅動程式（Device drivers）
:::
:::info
### OS 的分類
#### 系統大小
- 大型電腦
- IBM OS/360
- 個人電腦
- Windows
- Linux
- BSD
- Mac OS X
- 嵌入式
- VxWorks
- eCos
- Symbian OS
- Palm OS
#### 演進
- batch：單一指令、簡單
- Multi-programming：多工、資源分配
- Time-sharing：分時、資源分配、互動
#### 單一電腦
- Single-core：單核心
- Multi-core：多核心
- Multi-processor
- 可加上例如 GPU、加速卡
- 不一定只有 CPU
#### 分散電腦
- Cluster：
- 多台電腦在一起
- 區域網路的方式
- 比較近
- 管理者、OS 是單一的
- Distributed
- 分散式系統
- 資料中心、雲端計算等
:::
:::info
### 多工技術
#### Symmetric multiprocessor system（SMP）
由 OS 決定，每個 Core 都是平等的
##### 分類
- Uniform-memory-access（UMA）
統一記憶體存取架構，物理記憶體被均勻共用
- Nonuniform-memory-access（NUMA）
非統一記憶體存取架構，共用的記憶體物理上是分散式
#### Asymmetric multiprocessor system（AMP）
有 Master 的 CPU，由 Master 分配指令，只做管理不做計算
:::
:::info
### I/O
#### Buffering
是記憶體中的一個空間
- 將 I/O 的資料先收集至 buffer 中
- 達到 CPU 可運算的資料量時，CPU 再將資料由 buffer 中一次取出計算
- 在 CPU 開始計算的同時，I/O 則可繼續收集資料
- 達到 CPU 與 I/O 可同時運行的目的
#### Simultaneous Peripheral Operations On-Line（SPOOL）
將磁碟機視為一個大 buffer
- 資料讀取與寫入時，不直接讀取，而由磁碟機中讀取。
##### SPOOL 的案例
多筆資料要交給印表機輸出時
- 將待印資料的清單放在一個表格中
- 印表機印完依筆資料後，可直接至表格讀取下一比待印資料
- CPU 把待印資料的清單放在表格中後，可以去做別的計算
- 此時 I/O 也可繼續執行。
#### Buffering 與 SPOOL 的不同
- SPOOL 可允許某個工作的 CPU 計算（Computation）與另一個工作的 I/O 操作（Operation）同步執行（Overlay execution）。
- Buffering 只允許許某個工作的 CPU 計算與 I/O 操作同步執行。
:::
:::info
### I/O 間傳送的方法
#### Polling
- I/O 裝置只要將資訊放進狀態暫存器
- CPU 會周期性的檢查並取得資訊來得知需要服務的裝置。
#### Interrupt-driven I/O
- 利用 Interrupt 的機制
- 當一個 I/O 裝置需要服務時，會發出 Interrupt 來通知 CPU
- 非同步 I/O
#### Direct Memory Access（DMA）
- 提供一個裝置控制器，讓 I/O 裝置能夠直接在記憶體做資料的傳輸
- 不需要 CPU 的參與
#### Cycle Stealing
- DMA 向 CPU 竊用機器週期，直接向記憶體存取資料
- 因此 CPU 可與週邊裝置的工作同時進行
- CPU 與 DMA 對記憶體存取發生衝突時，給 DMA 較高的優先權
- 執行消耗小的先執行
:::
:::info
### 電腦系統架構
- User
- Application
- Compiler
- Assenbler
- Test Rditor
- Browser
- OS
- 負責 Application 跟 Hardware 的溝通
- 操作：控制（Controls）、協調（Coordinates）
- 將 Hardware 抽象化，提供 API
- Hardware
- 提供的資源量，不管硬體驅動
:::
:::info
### Interrupt
#### Hardware
- 硬體所產生的。
- 產的出 Interrupt 時 os 會先去察看 Interrupt vector。
- 這些 Interrupt vector 是固定的。
- 每一個 Hardware 都會有一個 Port，而且這些 Port 都有個 Singal number。
- 裝 Driver 的時候就會 Overwriter 到 Interrupt vector pointer 的位子。
- 專有名詞：Singal
#### Software
- 由軟體產生的，例如 System call、Error。
- System call
- 由 Program 所產生的，由程式去 Call OS API。
- Error
- 由 OS throw 出來的。
- 專有名詞：Trap
:::
:::info
### 儲存系統的分類
- Rigisters
- Cache
- Main memory
- Electronic disk
- Magnetic disk
- Optical disk

CPU 能直接訪問的只有 Main memory 以上
:::
:::info
### Protection
系統使用穩定的保護
- 以最單純的 CPU 來說，無法分別是否是 OS 還是一般使用者發出來的指令
- 但其實在實際運作時，有一個 Dual-Mode 會區分是否是由 OS 所發出來的

- 在 CPU 的指令集中，有 Privileged instruction（特權指令）
- 必須要由 OS 所發出來，才能執行
#### 特權指令的種類
- 保護 I/O
- 防止 User 同時或惡意修改 Shared I/O。
- I/O 指令
- 保護記憶體
- 已保證程式不會竄改其他人的記憶體空間。
- 與記憶體管理有關的暫存器之修改指令。
- 確保程式使用的記憶體不超過系統上限或者範圍外的空間。
- 保護 CPU
- 防止 CPU 被長期霸佔。
- 與 Timer 設定有關的指令。
:::
## Chapter 2: Operating-System Structures
:::info
### OS Srevices
- User Interface
- CLI（Command line interface）
- Shell: Command line interface
- GUI（Graphic user interface）
- Program Execution
- I/O operation
- File system manipulation
- communtication
- message passing - 可以跨不同電腦之間
- 訊息傳遞。
- memory copy
- 必須通過 OS 來處理
- 因為 protection
- shared memory
- Error detection
- Resource allocation
- Accounting
- Protection and security
:::
:::info
### System calls v.s. API
#### System calls
##### [功能]
- Process Control
- File Management
- Device Management
- Information Management
- Communications
##### [特點]
- 是 OS 的 Interface
- OS 提供的 Function 就是 System call
- 講求的是效能，因此功能單一
- 發出 Softwave Interrupt
- 由 User mode 到 Kernel mode
- 組合語言（Assembly language）所撰寫的
- System Call 傳遞參數給 OS
- 用暫存器儲存這些參數。
- 將參數用表儲存在記憶體中，同時用一個暫存器記錄此表起始位址並傳給 OS。
- 利用 System Stack。
- 要存放參數時將之 Push 到 Stack 再由 OS 從 Stack 中 Pop 取出參數。
#### Application Program Interface (API)
因為 System Call 不方便撰寫同時提供工功能單一，所以就有了 API。API 方便大家使用，用來跟 System Call 溝通的管道
- 撰寫的語言不一定。
##### [特點]
- 在 System calls 的上層。
- 並沒有直接轉換成 Kernel mode，除非 System call。
- 是方便 Program 使用。
- 不是單純轉換成 System call。
- 可能一對多、多對一 System call 或一對零 System call。
- 例如：C Library。
##### [種類]
- Win32 API：for windows
- POSIX API：for UNIX、Linux、Max OS X
- Java API：for Java Virtual Machine （JVM）
##### [Pros]
- 簡單（Simplicity）。
- 方便移動、攜帶、轉移（Portability）。
- 有效率（Efficiency）。
- 很多都不需要去 System call。
:::
:::info
### OS 架構分類
:::
:::info
### Simple OS Architecture
早期的 Structure
#### 案例
MS-DOS
#### 架構層
- Application program
- Resident system program
- MS-DOS device drivers
- ROM BIOS device drivers
#### 概念
- 幾乎沒什麼架構。
- 除了把 Driver 跟 OS 分開來而已。
#### [Pros]
- 簡單
#### [Cons]
- 結構不合理
- 沒有保護
- MS-DOS 別無選擇，因為 CPU 8088 沒有用戶內核模式的硬件支持
:::
:::info
### Layer OS Architecture
概念好但不存在，因為完全分層設計困難。
#### 案例
早期 Linux。
#### 架構層
- Operator
- User program
- I/O management
- Device driver
- Memory management
- Process allocation multiprogramming
- Hardware
概念
- 強迫把 Process 切成每一個 Layer
- 上面能呼叫下層，但不可呼叫上層
#### [Pros]
- 更結構化
- 易於調試和擴展
#### [Cons]
- 難以遵守
- 很難定義圖層
- 有些上下要互相呼叫，但 Layer 不允許
- 導致會繞來繞去，必要 Memory Copy 跟 Function call
:::
:::info
### Microkernel OS
核心功能能省則省，把很多功能都放到核外
#### 案例
Mach
#### 架構層
- MicroKernel（Kernel）
- Module（User）
- I/O Management
- Graphics Subsystem
- Network Drivers
#### 概念
- Kernel 越少越好
- 使用 Modularize
- 把 Subsystem 變成 Module
- Kernel 負責溝通不同的 Module
#### [Pros]
- 穩健性，可擴展性和安全性
- 隨時能替換不同的 Module
#### [Cons]
- 效率低下
- 每一個 Module 溝通都要 Call System call
:::
:::info
### Modular OS
大多數現代操作系統實現內核模塊
#### 案例
Linux
#### 架構層
- Kernel
- Kernel Module
- User Module
#### 概念
- 類似於圖層但更靈活。
- Define 好 interface，將功能變成 Subsystem。
- 與 Microkernel 不同的是，將 Module 變成 Kernel Module。
- 叫 Modular 因此能寫一個功能 Load 到 Kernel 裡成為新的 Kernel 功能
- system call 有 Table 會創建好一些空的 entry
- 所以能替代或插入一些 Kernel module 然後再接回原本的 Module
- Table 如同硬體的 Signal，會有個 Interrupt vector
#### [Pros]
- 高效，無須 Passing message。
:::
:::info
### Virtual Machine
大多數現代操作系統實現內核模塊
#### 架構層
- Hardware
- Virtual machine implementation
- Virtual machine
- Other OS
#### 概念
- 期望能在同一台硬體上有不同的 OS 系統。
- 其他的 OS 完全不知有他在此機器上，以為自己有全部機器的使用權
- 但事實上由 VM 來做切割管理，讓多個 OS 跑在各自的 VM 上
- 雖然是做 Instruction Translation，但會遇到很多的困難，例如：
- Privileged Instruction
事實上其他的 OS 是在 VM 上，當 OS 使用 Privileged Instruction 的時候，因為有 VM 的關係導致其實上面的 OS 是在 User Space，因此無法執行
- 這時 VM 會先收到 fail 的訊號後，再一次以 Kernel 的方式執行此指令，就能解決
- 但會必需要跑兩次（因為會被一次）
- 有些 CPU 會有 Hardware Support，除了 Kernel Mode 跟 User Mode 之外會有 Virtual Mode，來避免上面的問題。
- Critical instruction
- User Mode 也能執行，但結果出來會跟 kernel 的不一樣
- 導致 VM 不會接受到 fail 的訊號，而 OS 以為自己是 Kernel Mode 的結果但實際上是 User Mode 的
- 這個問題也不能直接寫死
- 因為 OS 也有可能上面的 User 是以 User Mode 來發出指令的
- 這下 VM 就不好判斷是 Kernel 還是 User 發出的。
#### [Pros]
- 安全
能區隔不同的 OS，攻擊 A 系統也不能影響到 B 系統
- 相容性（Compatibility）
為了相容不同的 APP 因此就需要不同的 OS
- 開發 OS 方便
只要 OS 出現 Bug 就會 Crash，很麻煩，但有 VM 的時候就能隔離開，還能紀錄
#### [Cons]
- 開發上會遇到很多困難
- 效率低
- Translation 可能失敗
:::
:::info
### VM 的延伸
#### Full Virtual
- 分成
- Host OS：主要控制硬體的 VM OS
- Guest OS：其他的 VM OS
- Guest OS 會感知不到其他的 OS，同時認為自己能直接操控硬體。
- 但會遇到 VM 的很多問題
#### Para Virtualization
- 分成
- Host OS：主要控制硬體的 VM OS
- Guest OS：其他的 VM OS
- Global Zone：能感知到全部的 OS（連同 Host OS）
- 比較容易實現虛擬化
- 效率好
- 因為能多做一層的優化來處理不同 OS 的請求
- 但同時必需要跟 Global Zone 溝通
#### Java Virtual Machine（JVM）
- Bytecodes
- 將程式碼轉換成 OS 的 Instruction
- Java 有 JIT（Just In Time）
- 會紀錄翻譯過的 Instruction，以加快速度
:::
## Chapter 3: Processes
:::info
### Process v.s. Program：是否處於執行狀態
- Program：只是儲存於 **disk** 中等待被執行的程式碼
包含：
- Code segment
- Data section：全域變數
- Stack：區域變數、Function
- Heap：Class、動態配置的變數
- Current Activity：管理 Process 的 Meta data
e.g. Program counter
- A set of associated resources：相關資源
e.g. Open file handlers
- Process：則是位於**記憶體**中的正在被執行的程式
:::
:::info
### stack
- 放 value type
- 只存在於 function 執行期間
### heap
- 放 reference type
- function 執行完仍在
- 沒有 GC：（e.g. C++) 需要用 delete 清除物件
- 有 GC：（e.g. Java）的 garbage collector 會自動釋放 heap 上的記憶體空間，防止 memory leak
:::
:::info
### Process
#### States
- new：當 process 被創建時，將 code 讀到記憶體中，並初始化前述記憶體狀態
- ready：等待被執行的階段，會被放在 queue 裡
- running：被 CPU 排程選到，執行 instructions
- waiting：有些指令不會直接使用 CPU（e.g. I/O），因為不需要 CPU，又需等待某些指令完成，所以進入 Waiting 狀態，待完成後重新放回 Ready
- terminated：Process 完成執行，釋放資源給 OS。

一個 Processor 一次只執行一個 Process ; 但同時可能有多個 Process 處於 Ready 或 Waiting 的狀態。
:::
:::info
### Process Control Block (PCB)
User 創建 Process 後，OS 會自動建立 PCB 來做管理。
**將 Process 放進 Queue 中**：將 Process 的 pointer 放到 Queue 中（使用 Linked list）。
#### 包含
- Process state
- Program counter
- CPU registers
- CPU scheduling information
- memory management information (base & limit register)
只有 process 在執行時才會把這兩個值從 memory load 進 CPU 的 register。
- I/O status/information
- accounting information

這些資訊放在 kernel space 的記憶體空間。
:::
:::info
### Context Switch
因為 CPU 一次只能執行一個 Process，透過 Context Switch 切換至其他 Process
#### 步驟
- 執行 Process P
- Process P 被打斷讓出 CPU，此時處於 idle 狀態
- 進行 Context Switch
- 將 Process P 的狀態存於 PCB
- 載入 Process Q 的 PCB
- 執行 P1
#### 縮短 Context Switch 時間的方法
- memory speed
- number of registers
越少則存取的次數降低
但現在的系統中為了更快速的計算，register 數量是變多的
- 合併 load 及 save PCB 的 instruction $\implies$ 讓 CPU 一次做完
- 硬體支援
- multiple sets of registers
一次記住多個 Process 的狀態，快速在 registers 間進行切換，無須透過 memory access
:::
:::info
### Process Scheduling
#### Multiprogramming
多工處理：讓 CPU 執行多個 Process，以最大化利用 CPU
- 保存多個 process 在 memory 中
- 一次只有一個 process 在 CPU 執行，其他的 process 處於 waiting 狀態
- 當執行狀態的 process 必須等待資源才能繼續執行（I/O request）時，作業系統拿回 CPU 的控制權，交給其他等待的 process

#### Time sharing
分時系統：系統頻繁進行 Context Switch，讓多個 User 同時使用 Program
（參考Round Robin Scheduling）
:::
:::info
### Process Termination
Process 終止後，相關資源都會清空，將資源還給 OS
- e.g. 記憶體空間、I/O buffer、open files

Parent 可利用 PID(abort) 來中止特定 Child Process
#### Cascading termination
因為是樹狀結構，所以當 Parent 被中止，Child Process 也會被中止
- Ctrl+C、kill 可以強制停止 Process
:::
:::info
### Interprocess Communication（IPC）
在多個 Process (或 Threads) 間溝通的機制
#### 目的
- 資訊的共享
- 加快計算速度（不必然）
- 便利性（一次執行多個 task）
- modularity (e.g. micro-kernel)
#### Communication
##### Shared memory
共用記憶體空間
- 透過 memory 的 address 存取資料
- 快（以 memory address 實作）
- 需要小心處理 sync
- 資料格式為 bytes，由 process 自行定義
- Process 要能創建 shared memory 的區塊
- attach：通知 OS "自己要共用這塊記憶體位置"
- 不同 Process 不能同時讀寫相同記憶體
##### Message passing
透過 memory 的
- 沒有 conflict 的問題
- 慢（以 system call 實作）
- 若資料小反而會略快
因為避免 share memory 的 lock 等額外資源消耗
- 不用在意 sync 的問題
- 使用 send/recv message
- 常用於網路程式、跨電腦的程式
:::
:::info
#### Communication Methods
##### Sockets
- 透過 IP & Port 來 identify 使用者，port number 指得就是 Process
- 傳輸未結構化的位元資料 (unstructed stream of bytes)
- 會有 client & server
- server 要先打開 client 才能連
- client 進行 connect 之後，就可以盡情 read / write
- server 在 accept 之後，會動態開 thread，因此可以一次處理多個 request
##### Remote Procedure Calls (RPC)
- 可以呼叫其他的 Process
- 甚至其他電腦的 Process
- 參數以及回傳值以 message 傳遞
- 傳輸的資料有 data type
- Library 通常會有 stubs
- 在 server 端、client 端會各有一隻小程式負責 implement 細節
- server 端的叫 skeleton
- parameter mashaling
把 params 包進 message 管理
:::
:::info
### Consumer & Producer Problem
兩個 Process 共用一塊 Buffer 記憶體
Buffer 是 circular array
- next free: in
- first available: out
- empty: `in = out`（out 拿光）
- full: `(in + 1) % BUFFER_SIZE = out`
- 為了 sync，避免無法判斷 in = out 時是 empty 還是 full，必須使用 in + 1 留一個空格
- 以 locking 的方式使用所有的 Buffer
:::
:::info
### Message-Passing System
讓 Process 之間可以溝通、同步
必須建立 communication link
Message system : Process 不使用 shared variable 達到溝通的目的
#### 操作
- Send(message)
- Receive(message)
#### Direct communication（如打電話）
##### Processes 必須要有對方的名稱
- Send(P, message) : 傳輸 message 給 Process P
- Receive(Q, message) : 從 Process Q 接收 message
##### communication link 的特性
- Links 通常為自動建立
- Link 與 Process 間為一對一的關係
- link 可以是單向，但通常是雙向
##### [Cons]
- 一對一
- 且連線的對象無法變更，除非重新建立
- 因此難以模組化 (modularity)
#### Indirect communication （如寄信）
##### Messsages 由 mailboxes （或 port） 導向及接受
- 每一個 mailbox 有自己的 ID
- Processes 透過共享 mailbox 互相溝通
- Send(A, message)：將 message 放到 mailbox A
- 沒有指定接收者
- Receive(A, message)：將 message 由 mailbox A 接收
- 沒有指定傳送者
##### communication link 的特性
- Link 必須由 programmer 建立
- Link 與 Process 間為多對多的關係（因為沒有指定接收者/傳送者）
- Link 可以為單向或雙向
- Mailbox 可以由 Process 或 OS 擁有
- 通常處理 message 的是另一隻程式
##### Mailbox Sharing
- 可能同時多人讀取 message，但一個 message 應只有一個 receiver
解決方法
- 最糟的解法：Link 只允許兩個 Process（即 direct）
- 利用 lock 一次只允許一個 Process 拿取 message
- 讓 mailbox 決定接收者
1. receiver 先提出要求
2. mailbox 決定接收者
3. sender 被告知 receiver 是誰
4. 告知 receiver 來取得 message
#### Synchronization
##### Message passing
- blocking（synchronous）
- send：sender 被 blocked 直到 message 被 receiver 或 mailbox 接收才 return
- receive：receiver 被 blocked 直到皆收到 message 才 return
- non-blocking（asynchronous）
- send：sender 送出 message 之後繼續執行
- receive
- 若 sender 先 call，receiver 再收
$\implies$ receiver 正常接收 message
- 若 receiver 先收，sender 才 call
$\implies$ receiver 只會收到之前的值
（所以 function call 通常會 return 一個 token，確定是否真的收到 message）
##### Buffer implementation
non-blocking 通常透過 buffer 實作，只要 buffer 空間沒滿，就可以一直 send，對 receiver 來說就是一直接收，不管 buffer 有沒有東西
- Zero capacity：通常是 blocking send/receive
- Bounded capacity：若 buffer 滿了，sender 會被 blocked，或是 return 一個 error
- Unbounded capacity：一直送直到系統滿了為止
:::
## Chapter 4: Threads
:::info
### Thread（Lightweight process）
- 使用 CPU 的最小單位
- 相同 Process 的 Threads
- 共享
- code section
- data section
- OS resources (e.g. open files and signals)
- 不共享
- stack
- register set
instruction 的執行位置可能不同
甚至可能執行不同的 function call
- thread ID
- program counter
:::
:::info
### Motivation
#### web browser
- 如一個 thread 負責顯示文字，其他 thread 接收資料等
#### web server
- One request / process: poor performance
- One request / thread: 因為 code 及 data sharing，效率較高
會有一個 main thread 一直在等待，當接收到新 request 時，會產生一個 thread 專門處理，讓 main thread 可以繼續等待連接
#### RPC server
- One RPC request / thread
:::
:::info
### Multithreading
[Pros]
- Responsiveness
即使 program 的一部分被 block 住，或是執行冗長的操作，仍可繼續運行，加速響應時間
- Resource sharing
不同的 threads 可利用相同記憶體位置共享資源
- Utilization of MP arch
多核心 $\implies$ thread 可以在不同 processors 上平行執行
- Economy
- thread 無須記憶體空間管理及處理，建立 thread 的 cost 比 process 來得小
- 因為 thread 共用 process 資源，thread 之間的 context switch 比 process 快
:::
:::info
### Multithcore Programming
- Multithreaded programming 提供更有效率使用多核心的機制
$\implies$ 改善共時性（concurrency）
#### Challenges
- Dividing activities：將 program 拆成多個可以同時處理的任務
- Data splitting：除了計算任務要拆，資料也要能夠拆開給不同任務處理。有時候 data 很複雜，不一定是平分給所有任務處理
- Data dependency：shared data 的同步，是平行程式中最複雜且重要的部份
- Balance：各個任務的執行時間要差不多，否則會受限於執行最久的任務
- Testing and debugging 困難
:::
:::info
### User Thread vs. Kernel Threads
#### User threads
由 user 透過 threads library 進行的 thread 控制
- 雖然由 user 創建，但實際 thread 要執行任務時，OS 會將該 thread binding 到某一個 kernel thread 上，每次可對應到不同的 kernel thread。
- user level 的 thread，不由 kernel 直接控制
$\implies$ 創建、管理快
- 但如果 kernel thread 只有一個，即便有多個 user threads，若某個 user thread 執行時呼叫 I/O 或 sleep()，其他 threads 便無法再使用該 kernel thread
- 因為 binding
##### 案例
- POSIX Pthreads
- Win32 threads
- Java threads
#### Kernel threads
由 kernel（即 OS）直接控制
- 由 kernel 進行創建及管理，速度較慢
- 若某個 thread 被 block，仍可由 kernel 安排其他 threads 執行工作
##### 案例
- Windows 2000(NT)
- Solaris
- Linux
- Tru64 UNIX
:::
:::info
### Kernel mapping threads
#### Many-to-One
許多 user thread mapping 到一個 kernel thread
- 在不支援多 trheads 的 kernel 使用
##### [Pros]
- Thread 管理在 user space 完成，效率高
##### [Cons]
- 整個 process 可能被 block
- 一次只有一個 thread 可以 access kernel
多執行緒在多處理器的環境下也無法平行化
#### One-to-One
每個 user thread mapping 到一個 kernel thread
- kernel thread 數量通常受到限制
##### [Pros]
- More concurrency
##### [Cons]
- 有較高的 overhead
因為創建 user thread 要同時創建對應的 kernel thread
#### Many-to-Many
多個 user threads 對應到相同或較少數量的 kernel threads
- 是在 runtime 期間做 mapping
##### [Pros]
- user threads 數量不受限制
- kernel threads 可以在多核心系統中平行執行
- 當某個 thread 被 block 時，可安排其他 kernel thread 來執行
:::
:::info
### Shared-Memory Programming
Processes 透過 shared memory space 進行溝通及協作
- 比 messgae passing 更快也更有效率
#### Challenges
- Synchronization
- deadlock
- two or more processes are waiting **indefinitely** for an event that can be caused by only one of the waiting processes
- Cache coherence
#### POSIX
POSIX (Portable Operating System Interface)
- 只定義行為不定義實作，也就是 API 層面必須相同
- 標準針對 Unix 類的不同系統
- 程式碼只需要重新編譯而不用修改即可執行
- Message passing 的 library MPI 也有相同概念
##### Pthread
定義在 POSIX 標準下的 thread 庫
#### Linux Threads
- Linux 在 kernel 不支援 multithreading
- 因為 Linux 只有 process 或 task，沒有 thread
- User-level 可以使用 Pthreads 實作多執行緒
- `fork` system call
產生新的 process、完全複製 parent 的 data 及程式執行狀態
- `clone` system call
產生新的 process、控制哪些 segment 要與 parent share
- Linux 用 clone system call 來達到 thread 的概念
- 因為 Linux 沒有 thread
- 有一系列的 flag 來控制資料共享的程度，共享的資料以 pointer 的方式指向
:::
:::info
### Threading Issues
#### fork()
- 若 process 有兩個 thread，其中一個 thread call fork() 可能有以下兩種情況
- 

- 部份 UNIX 系統支援兩種 fork() 的方式
- execlp() 會取代整個 Process，而不是單一 thread
#### Thread Cancellation
- 一個 thread 若執行結束後，main thread 必須有一系列 cancel 的動作
- Asynchronous cancellation
main thread 會馬上中止 target thread
- Deferred cancellation (default option)
target thread 會預設一些中斷點
main thread 會週期性地確認 target thread 是否執行到中斷點
等 target thread 執行到中斷點才中斷
#### Signal Handling
Signals（sync/async）在 UNIX 系統中用來告知 process 某個事件發生
- synchronous：如不合法的記憶體存取
- asynchronous：Ctrl + C

Signal handler 處理 signals 的順序
1. Signal 被特定事件產生
2. Signal 被送到 process
3. Signal 被處理
4. Signal 處理的 Options

傳送 signal 給 deliver signal 的 thread
- 傳送 signal 給所有 thread
- 傳送 signal 給特定的 thread
- 直接由 main thread 來處理 signal（如 file handler 的操作）
:::
:::info
### Thread Pools
很多程式（e.g. web server）是直接產生一定數量的 threads
- 避免動態 thread 的產生、刪除時造成的 overhead
- 程式執行比較有效率
#### [Pros]
- 直接接收 request 比創建一個新的 thread 再接收 request 快
- 可以控制 threads 數量 $\implies$ 控制系統的資源用量
#### 決定 Threads pool size 的因素
- CPU 的數量
- 預期 request 的數量
- 記憶體大小
:::
## Chapter 5: Process Synchronization
:::info
### Race Condition
多個 Processes 同時存取及操作 shared data 時，最終的值取決於最後一個完成執行的 Process
- 在 single-processor machine 中，我們可以 disable interrupt 或著使用 Non-preemptive scheduling 來達成同步
- 但在 User Program 中不可能如此使用，會影響整個系統的運作
- 通常將可能產生 Race Condition 的區域稱作 Critical Section
:::
:::info
### Critical-Section Problem
#### 目的
建立 Processes 之間合作的 protocal
#### 問題敘述
- N 個 Processes 競爭使用 shared data
- 每一個 Process 存取 shared data 的 code segment 稱為 critical section
#### 解法：Mutually exclusion
（比較暴力的解法）
##### [Mutual Exlusion]
當一個 Process 執行 critical section 時，其他 Processes 不得執行 critical section
##### [Progress]
若沒有 Process 在執行 critical section，且有某些 Processes 希望進入它的 critical section，則 Process 不得在未定義的情況下被推遲，一定要進的去
##### [Bounded Waiting]
Process 等待進入 critical section 的期限必須受到限制，不可一直排隊等待
:::
:::info
### A Simple algorithm (for two processes)
- Process：$P_0$、$P_1$
- Shared Data：$\text{turn}$
- $\text{turn = i}$ 時，$P_i$ 可以進入 critical section

只在兩個 Process 輪流執行時順利運作
:::
:::info
### Peterson’s Solution (for two processes)
- 引入 `flag`、`turn`
- `flag[i] = True`：$P_i$ 準備好要進入 critical section
- `turn = j`：讓 $P_j$ 進入 critical section
:::
:::info
### Bakery Algorithm (for n processes)
- 在進入 critical section 之前，每一個 Process 會抽號碼牌
- 號碼牌數字最大的先進入 critical section
- 若兩個 Process $P_i$、$P_j$ 有相同的號碼牌，則 PID 小的先進入
- choosing[i] 為是否正在抽號碼牌的 flag，在與其他 Process j 比較之前，我們必須等待 Process j 抽完號碼牌
#### Deadlock 的情況
$P_j$ 比 $P_i$ 晚抽完號碼牌，但號碼與 i 一樣大，又 j 的 PID 比 i 小，所以 $P_j$ 應該要先執行；如果在 j 還沒抽號碼牌之前就進行比較，此時 num[j] = 0，程式會以為 j 不要執行，反而先執行 i，當 j 抽完號碼牌之後發現數字與 i 相同，因此也可以進入 critical section，但這時 i 已經在裡頭，導致 deadlock。
:::
:::info
### Pthread Lock/Mutex Routines
:::
:::info
### Condition Variables (CV)
Condition Variables 代表一個條件，符合該條件時可以觸發 thread 執行某些動作
#### 操作
- wait() : 直到其他 thread 呼叫 signal()/broadcast()，thread 處於等待狀態
- signal() : 喚醒一個等待中的 thread
- broadcast() : 喚醒所有等待中的 thread
#### 在 Pthread 中
- CV type 為 pthread_cond_t
- 使用 pthread_cond_init() 來初始化
- pthread_cond_wait (&theCV, &somelock)
- pthread_cond_signal (&theCV)
- pthread_cond_broadcast (&theCV)
:::success
#### Example
1. action() 進入 CS，呼叫 thread_cond_wait 並釋放 lock
2. counter() 取得 lock 進入 CS
3. counter() 呼叫 singal()，action() 被喚醒
- 這時候 action() 是沒有 lock 的
5. counter() 釋放 lock
6. action() 取得 lock 並執行函式
:::
:::info
### ThreadPool Implementation
一次創建多個 threads，讓系統不用一直增刪 threads，並且讓系統可以有效控制 threads 的數量，避免過多的 context switch 反而降低效率，達到效能最佳化。

- 創建 threads 後，會建立一個 threadpool_task_t 的結構體
- 讓 threads 執行不同的 function
- 存放函式及對應參數的指標
- threads 在經過 while loop 被喚醒後，執行目前看到 threadpool_task_t 的函式，處理完成後進入 wait 狀態，等待下次被喚醒
- 而 threads 要如何知道被喚醒，其中一個方式是透過 Condition Variable 判斷
:::success
1. 創建 threads pool 以及 task 的 queue
2. thread 執行 while loop 處於 wait 狀態
3. 若 thread 被喚醒則離開 while loop，並執行 queue 中 pool->head 的函式
4. 執行後 pool->head 加 1，再判斷該值是否等於 queue_size，若相等表示已經執行到最後一個函式，將 pool->head 設為 0
5. 離開 critical section 執行任務
:::
:::info
### Hardware Support
Critical Section Problem 的發生是因為 shared variable 的修正可能被打斷，若某些指令我們可以一行完成，就可以避免 race condition 的問題
- 前面都是在說軟體上的支援
- 若硬體可以將指令變成 atomic instructions，就沒有同步的問題

- atomic：無法中斷執行的最小單元
#### Atomic TestAndSet(var)
#### Atomic Swap(a, b)
先 call Swap 的取得進入 critical section 的權力，執行完成後將 token 還給 lock。
:::
:::info
### Semaphores
Samaphores 是一個通用的同步處理工具
- 紀錄某個資源有多少 units 可以去使用
- 若 # of record = 1 --> binary semaphore
- 但其實用 mutex lock 就好
- 若 # of record > 1 --> counting semaphore
- 利用兩個 atomic operations wait & signal 來存取 (注意與 critical section 的 wait & signal 不同)
- Semaphore 為 POSIX 標準庫之一，不屬於 Pthread
- 所以使用上不限於 thread ，也可以用於 Process
#### 簡單的 Spinlock 以 semaphore 實作
:::
:::info
### Semaphores: Non-busy waiting Implementation
一般來說，等待時間很短的用 busy waiting，反之則用 non-busy waiting
- Busy waiting (SpinLock) 因為 while loop，執行效率沒有被最佳化
- Non-busy waiting 成本比 while 來得高
- 因為 system call 要考慮 context switch、re-scheduing 的影響

#### 結構
Semaphore 為一個有 queue 的結構體，包含 Semaphore 的值以及有哪些 Processes 等待被執行
#### wait() & signal()
- 使用 system calls: sleep() & wakeup()
- 一樣必須為 atomic 的操作
- 必須先進行 `value--`/`value++` 操作
- 避免進入 if 區域後被 sleep 無法執行

#### 確保 wait() & signal() 為 atomic 操作
由於 `value--`/`value++` 及 queue 的 insert, delete 等
- single-processor：透過 disable interrupts
- multi-processor：
- HW Support (e.g. Test-And-Set, Swap)
- SW Support (Peterson’s solution, Bakery algorithm)
#### Semaphore with Critical Section
- 將 `value--`/`value++` 以及 queue 的操作包進 critical section
- 因為 sleep() 及 wakeup() 為 system calls，無須擔心同步的問題
- 所以不用包進 critical section 中（也不該包進去）
:::
:::info
### Cooperate Synchronization
有些情況不同 Process 間的執行順序很重要，考慮 P1 & P2 分別執行 S1 & S2，S2 必須在 S1 完成後才可執行
#### 實作
利用 shared variable `semaphore sync`
#### Example 1
以下程式碼確保 S1 一定先執行完成
#### Example 2
:::
:::info
### Classical Synchronization Problems
- Bounded-Buffer (Producer-Consumer) Problem
- Reader-Writers Problem
- Dining-Philosopher Problem
:::
:::info
### Reader-Writers Problem
標準在處理 I/O 會遇到的問題
- A set of shared data objects
- A group of processes
- reader processes (read shared objects)
- writer processes (update shared objects)
- writer process 對 shared object 有獨佔權
- 不同的種類
- first RW problem
- 確定 writer 有 access 的獨佔權
- 不關心 reader 要等多久，或要做什麼事情
- reader 取得 token 時，可以傳給其他 reader
- 可能造成 writer 一直被其他 reader 插隊，永遠拿不到 lock
- second RW problem
- 確定 writer 的 access 權限
- 當 writer ready 且 object 被釋放時，writer 的優先性必須高於 reader
- 不可有新的 reader 進來插隊
:::
:::info
### First Reader-Writer Algorithm
- writer 為 binary semophore
- Reader 共享一個 block
- readcount 計算有幾個人要讀
- 當 readcount > 1 時，代表已經有 reader 拿了 lock，所以這個 reader 也可以讀
- 當 readcount = 1 時，因為是第一個 reader，可能要等 writer 結束才可讀取
- 當 readcount= 0 時，表示是最後一個讀的，讀完後要 signal writer
- readercount 為 shared variable，必須受到保護
- Writer可能會有 starvation problem ，因為只要有 reader 在讀，其他 reader 都可以進入 critical section，造成 writer 一直在等待狀態
:::spoiler code

// mutual exclusion for write 
semaphore wrt=1
// mutual exclusion for readcount
semaphore mutex=1
int readcount=0;

// writer
Writer(){
    while(TRUE){
        wait(wrt);
        // Writer Code
        signal(wrt);
    }
}

// reader
Reader(){
    while(TRUE){
        wait(mutex);
        readcount++;
        if(readcount==1)
            wait(wrt);
        signal(mutex);
        
        // Reader Code

        wait(mutex);
        readcount--;
        if(readcount==0)
             signal(wrt);
        signal(mutex);
    }
}

:::
:::info
### Dining-Philosopher Problem
- 5 個人坐在 5 張椅子上，且有 5 支筷子
- 每個人只會思考或是吃飯
- 思考時與剩下 4 個人沒有互動
- 每個人要用餐需要兩支筷子
- 一個人 1 次只能拿 1 支筷子
- 吃完飯後，將兩支筷子都放下
- 若每個人都拿其中一邊的筷子，就 deadlock 了
- starvation problem
:::
:::info
### Monitor
#### 用途
雖然 semaphores 提供非常便利及有效的同步機制，但正確性主要是依賴 programmer
- 所有存取 shared data object 的 processes 都需確保 wait() & signal() 的執行順序及位置正確，但是人總有可能犯錯
#### 介紹
可以將 Moniter 想成一個特殊 class，每一個 Moniter 都有可能發生 race condition 的 local variable（對應下圖的 shared data）需要保護，而要操作這些 var 必須透過 Moniter 的 method。
- Monitor 一次只有一個 thread 可以執行其 method
- 但可以很多個 threads 同時 call 這個 method，只是會處於 inactive 狀態
- monitor 利用 queue 做排程，確保一次只有一個 process 是 active 的，保護 shared data

:::
:::info
### Monitor Condition Variables
- 為了允許 process 等待 monitor，需要宣告 condition variable，
- 例如 condition x, y;
- condition variable 只能與 wait() 及 signal() 一起使用
- x.wait()
調用這個 operation 的 process 被閒置
直到其他 process 完成為止
- x.signal()
啟動一個等待中的 process
- 若沒有 process 處於等待狀態，則 signal() 操作沒有任何影響
- 與其相反，semophore 的 signal() 一定會改變 semaphore 的狀態
- wait 把 counter 減 1
- signal 把 counter 加 1
- 在 monitor 中，condition variable 不是 counter 而是一個 Queue
- 所以 x.wait() 類似把 process 放到 waiting queue (enqueue)
- 而 x.signal() 則是 dequeue
- 所以如果 queue 是空的，signal 就沒有任何作用
- Monitor 可以有很多個 threads 存在，但一次只有一個 active

:::
:::info
### Monitor: Dining Philosophers Example
#### monitor type

monitor dp {
    enum {thinking, hungry, eating} state[5]; //current state
    condition self[5]; //delay eating if can’t obtain chopsticks
    void pickup(int i) // pickup chopsticks
    void putdown(int i) // putdown chopsticks
    void test(int i) // try to eat
    void init() {
        for (int i = 0; i < 5; i++)
            state[i] = thinking;
    }
}

- 建立三個狀態 thinking, hungry & eating
- 建立 shared variable self[5]，存放每個人的狀態
- 定義 4 個 method
- pickup(i)
- 將狀態設為 hungry，代表要吃東西了
- 測試拿筷子後是否可以吃
- 若狀態沒有改變，表示測試失敗，把自己放到 wating queue

      void pickup(int i) {
      state[i] = hungry;
      test(i); // try to eat
      if (state[i] != eating)
        self[i].wait(); // wait to eat
      }

- putdown(i)
- 吃完了將狀態改為 thinking
- 告知左右兩邊進行測試，看有沒有辦法吃

      void putdown(int i) {
        state[i] = thinking;
        // check if neighbors are waiting to eat
        test((i+4) % 5); 
        test((i+1) % 5);
      }

- void test(int i)
- 若左右兩邊的人都沒在吃，代表左右兩邊手上都沒筷子，還要確認自己是否想吃東西
- 都符合的話，將狀態改為 eating 並喚醒 thread/process

      void test(int i) {
        if ((state[(i + 4) % 5] != eating) &&
            (state[(i + 1) % 5] != eating) &&
            (state[i] == hungry)
           ) { //No neighbors are eating and Pi is hungry
            state[i] = eating;
            self[i].signal(); // If Pi is suspended, resume it
                              // If Pi is not suspended, no effect
        }
      } 

:::
# Problems
## 2019
:::success
:::spoiler 2019 Q1
:::spoiler Ans
- a. True
- b. True（記憶體由 OS 管理）
- c. True
- d. True [Reference](https://www.ptt.cc/bbs/b97902HW/M.1267018497.A.3B1.html)
- e. True（系統 UI 由 OS 管理）
:::

:::success
:::spoiler 2019 Q2
:::spoiler Ans
By restricting the areas of memory to be exclusively used by Kernel separately.
[Reference](https://www.quora.com/How-is-an-OS-kernel-protected-from-being-modified-from-user-program)
:::

:::success
:::spoiler 2019 Q3
:::spoiler Ans
- X：No，處理 interrupt 需要跟硬體互動，應該要留在 kernel。
- Y：Yes，讓 kernel 維持小一點比較容易管理。
- Z：Yes，減少不必要的許多權限的 request。
:::

:::success
:::spoiler 2019 Q4
:::spoiler Ans
a. Multi-process。不需共用資料，不同 process 避免資源的互相干擾。
b. Multi-threading，I/O 的 memory 區塊近，multi-threading 的 shared memory 比較方便，也可以減少 overhead
:::

:::success
:::spoiler 2019 Q5
:::spoiler Ans
(b) 較久。因為如果要 cocurrent 執行 1000 個程式，代表在執行的過程中需要一直做 context switch，儲存/讀出 PCB 的資訊，會造成中間有很多時間不是在執行原本想執行的 program。
:::

:::success
:::spoiler 2019 Q6
:::spoiler Ans
The stack is where local variables, function parameters, and return addresses live. **If multiple threads shared the same stack, they would overwrite each other’s data, causing all kinds of errors and crashes.**
:::

:::danger
:::spoiler 2019 Q7
:::spoiler Ans
(a) shared memory 避免掉因 system call 產生權限 request 的步驟
(b)
:::

:::danger
:::spoiler 2019 Q8
:::spoiler Ans
:::

:::danger
:::spoiler 2019 Q9

:::spoiler Ans
:::

## 2020
:::success
:::spoiler 2020 Q1
:::spoiler Ans clc
Of course CLI
To run a script in routine, just a simple shell script can archieve the requirement. However, the system administrator may need to run the script manually every time when the machine is booted. Thus, it is better to do this by writing a service and enable it. Moreover, crontab is the service that implemented this feature and also installed in most unix-like system by default.
If you choose to use GUI, not only the system must have a desktop environment which is resource consuming, but you should also install some additional software that can simulate the input from keyboard and mouse, such as 按鍵精靈 in windows.
:::

:::success
:::spoiler 2020 Q2
:::spoiler Ans ycwang
- a. 正比於最大能跑的 n，超過則 Runtime Error
- b. 不影響
- c. 不一定
- d.
:::spoiler Ans clc
:::

:::success
:::spoiler 2020 Q3
:::spoiler Ans clc
- a. Every system call have its associated number. System-call interface will maintain this table. Before calling a system call, it is necessary to move the number to a reserved register. Moreover, application developers only call the API function implemented by the system instead of calling the system call by assembly language. Each functoin's implementation defined which system will be called.
- b. Pass the parameters in register is the simplest way. If the number of register is not enough the parameters are generally stored in a block, and the address of the bolck is passed as a parameter in a register.
- c.
- d.

:::

:::danger
:::spoiler 2020 Q4
:::spoiler Ans
:::
:::danger
:::spoiler 2020 Q5
:::spoiler Ans
:::

:::success
:::spoiler 2020 Q6
:::spoiler Ans
Stack uses FIFO, which fits the local CPU cache and thus much easier to manage (e.g. no need to merge free areas).
:::

:::success
:::spoiler 2020 Q7
:::spoiler Ans
a. `int buf[1000];`
b.

int n;
scanf("%d", n);
int* buf = (int*) malloc(sizeof(int) * n);

:::

:::success
:::spoiler 2020 Q8

:::spoiler Ans
No. Implicit declaration of function `f`.
(Declaration of function `f` should proceed the main function.)
:::warning
It is not because `int buf[n]`. That is a runtime error.
:::

:::success
:::spoiler 2020 Q9
:::spoiler Ans
Shared memory，因為 Copy、Paste 在同一台電腦下執行
:::

:::danger
:::spoiler {state="open"} 2020 Q10

:::spoiler {state="open"} Ans
a.
b.
c.
d.
e.
:::

# Reference
[作業系統 Operating System 筆記](https://hackmd.io/@Chang-Chia-Chi/OS/https%3A%2F%2Fhackmd.io%2F%40Chang-Chia-Chi%2FOS-CH3)