# Operation System
## Ch01 Introduction
### Introduction
* OS是user programs/application和硬體之間的程式，將硬體細節隱藏並分配 (fair and efficient resource):
* resouce allocator / control program

* Startup：Bootstrap program = boot loader （位於 ROM 或 EEPROM）load kernel
* Computer System Organization
* Device driver 也是 OS 的一部分，Device controller 完成 I/O 後會用 **Interrupt** 通知 CPU （由 OS 處理）。

### Interrupt
#### Common Funtion of Interrupt
* 在 CPU 和 Device 的互動中，給予 Device 任務後可以
* Polling ( request process wait Device ) = **Synchronous I/O**
* Interrupt = **Asynchronous I/O**。
* 當任務完成，Device controller 發 Interrupt Request (**IRQ**) 給 CPU，收到 IRQ 後去 Interrupt vector table (**IVT**) 查詢 Interrupt instruction = Interrupt serivce routine (**ISR**) = Interrupt handler 具體 Instrution 或其 address。
* Interrupt 也可以和軟體交互（也就是traps）：
* Error, Eg: Division by Z, Non-Authorization Access Memory.
* User request, Eg: Ctrl+C.

* **可以說OS是Interrupt driven!!**

#### Interrupt Handling
1. 硬體或 OS **Save** CPU 狀態（Eg: Register, PC, IR...）
2. 尋找 ISR or Instruction address from IVT
3. 執行ISR
4. 回復 CPU 狀態
* 這個 **save-restore** 過程就是 Interrupt 成本

#### I/O Sub-system
* OS 控管 HW 的系統: I/O subsystem
* Driver interface
* Memory Management: buffering, caching

### Storage Structure
#### Storage Hierarchy
* [Direct Memory Access (**DMA**)](https://blog.csdn.net/as480133937/article/details/104927922): The process of transferring data without the involvement of the processor (CPU) itself.
* Transfered by Device controller.
* Raise Interrupt when done.

* Only Primary Storage in storage hierarchy would be accessed by CPU directly.
* Caching: Information in use copied from slower to faster storage temporarily.

#### Memory Management
* **Data** and **Instruction** are in memory
* File-System management / Access control
* OS's job:
* Stores files into the storage devices.
* Creating and deleting files and directories
* Primitives (操作, Eg: read/write/append, set/get status/permission ) to manipulate files and dirs.
* Free-space management, Storage allocation, Disk scheduling

### Computer-System Archutecture

* Multi-processor systems = parallel systems = tightly-coupled systems.
* 不同 processor 共用 main memory。
* [Symmetric (reliability) / Asymmetric (Master/Slave)](https://tomchen.me/2020/03/19/OS/%5BOS%5D%20%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1%E7%AD%86%E8%A8%98-%E7%B3%BB%E7%B5%B1%E6%9E%B6%E6%A7%8B/)

* Multi-core Systems
* 單一處理器 `processor` 上有多個 `CPU`，處理器上共用 `L2 cache`，`CPU` 有自己的 `L1 cache`。

* Non-Uniform Memory Access (**NUMA**)
* Porblem: Multi-core + Multi-processor = system bus 上出現效能瓶頸。
* Solution: local memory，Access 本地資料加快；Access其他資料變慢 $\Rightarrow$ 需要 OS 謹慎的安排 task / data.

* Clustered Systems
* 通過 Local area network (LAN) 或其他方法連接很多電腦。
* High availability, Fault tolerant, Graceful degradation.
* Symmetric (efficient) / Asymmetric (hot-standby mode)

### Program Scheduling
* **Long-term scheduler = Job scheduler** (不頻繁)
* 多工處理， CPU 可以執行多個 Process，以最大化利用 CPU，由它決定哪個 Process 從 job queue 到 ready queue (admit)
* Process被分成兩種，最好是混合
1. I/O-bound = short CPU bursts
2. CPU-bound = long CPU bursts
* Windows 和 UNIX 沒有，所有 job 都被丟進 memory。
* 為了 Improve process mix => Midterm Scheduling
* **Short-term scheduler = CPU scheduler** (頻繁，millisec.)
* 決定 ready queue 上的 proocess 哪個該被執行
* 經常做 Context Switch

### OS Operation
#### Dual-Mode Operation
* OS 通過 Dual-mode Operation 保護自己
* User mode = non-privileged mode
* Kernel mode = privileged mode (for OS)
* Transition from user mode to kernel mode (by system call)
* Eg: read file, send pkg, etc.

#### Process Management
* **Process = Program in Exection**
* Single-thread process (1 PC) / Multi-thread process (Multiple PC, 1PC per thread)
* Create / Delete / Suspend / resume / synchronization / communication / deadlock handling

#### Protection and Security
* 每個 user 有自己的 userID，用於處理 Process 和 File 的 access control。
* Group ID 可以讓多的 user 擁有 Process / File 權限
* **Privilege escalation (特權提升)** 使 user 可以暫時提高權限
* Eg: Setuid (UNIX), [passwd (UNIX)](https://blog.gtwang.org/linux/linux-passwd-command-examples/)

### Virtualization
* 為硬體 (單一電腦) 提供不同的執行環境 (Create Illusion of environment)
$\Rightarrow$ **Allows OSes to run on other OSes**
1. Emulation (仿真): 通過軟體模擬硬體去支援另一種OS，較慢
2. Virtualization (虛擬化): 由 VMM (Virtual Machine Manager) = Hypervisor 支援此服務
**可以(不)通過 host OS** 直接取用 HW source
* Type I: 不通過 host OS，直接由 VMM 銜接，VMs 有自己的 kernel
* Type II: 通過 host OS，分成 host 和 guest

### Computing Environment
* 除了 Traditoinal Computing / Mobile Computing，還有：
1. Client-Server Computing
* Application-server: 提供 Client interface for request service
* File-server: 提供 store / retrieve files insterface for Client
2. Peer-to-Peer Computing
* peers 概念無 Server / Client, Eg: Skype
3. Cloud Computing
* Categories of Services
1. Software as a Service (SaaS)
2. Platform as a Service (PaaS)
3. Infrastructure as a Srevice (IaaS)
* Categories of Authority: Public / Private / Hybrid
4. Real-Time Embedded System
* No OS / Tiny embedded OS / Standard OS

## Ch02 System Structure
### Operating System Services
* Functions helpful to user / applications:
* User Interface: CLI / GUI
* Program execution: Load program into memory and run, terminate execution.
* I/O operations (involve file or I/O device)
* File-system manipulation (操作): read / write / create / delete / search / list info. / permission management
* Communications, between processes or computer
* Error detection
* Hardware Errors (CPU, memory, I/O devices)
* Software Error (Invalid memory access)
* Finctions ensures efficient operation of system
* Resource allocation
* Logging / Accouting
* Protection / Security

### Interface Provided by OS
1. User Interface:
* CLI: Shell, fetch command from user and executes it.
* GUI :+1:
2. Programming Interface
* **System call**: Programming Interface provided by OS.
* System call 有**編號 (number)**，以 table 紀錄
* Caller 不知道 System call 如何運作，傳進 OS 後由 sys. call handler 處理。
* 通常user使用更high-level的API, Eg: Windows API, POSIX API, JavaAPI
* 不同 OS 的 sys. call 參數/名稱不同，但 API 可以用於多數 OS，圖上 C library 就是包裝過後的 system call
* System call 如果要傳參數
1. Register: 太小 :-1:
2. Memory Address / Table: 參數放在 Table 裡，只傳 Address :+1:
3. Stack :+1:
* 分類：
1. Process Control
2. File Management
3. Information Maintenance
4. Communication
5. Protection

### System Programs
* 部分是 interface of sys. call, 部分更複雜
* 功能：
1. File management / modification, Eg: File manager
2. Status information, Eg: date, time...
3. Programming language support / loading and execution, Eg: compiler, assembler, ELF loader...
4. Communication, Eg: Chrome
* [Linker and Loader ](https://hackmd.io/@alan303138/Sy26KTAJY#%E9%80%A3%E7%B5%90%E5%99%A8)
* Linker: 將許多目的檔連結成一個執行檔的程式
* Loader: 將可執行檔載入到記憶體當中執行的程式。

### OS Design & Implementation
1. User Goal (convenient to use) vs. System Goal (easy to design)
2. 因為 Compiler 的進步，是否使用組語寫 OS 差異減小，主要是資料結構和算法影響較大。

### OS Structure
* Simple Structure
* Eg.1: MS-DOS
* Eg.2: UNIX (Monolithic kernel)

* Layered Approach
* 將 OS 分層，上層 call 下層，難以定義每層為何且效率較低。

* Microkernels [2022 OS midterm]
* 將 OS 部分功能(Eg: File System, Device Driver...)上推至User mode與Applications同級，而 Basic IPC, memory, CPU Scheduling...等等功能維持在kernel里共用，使被分區的功能之間通過Kernel mode 傳遞 message (message passing)。
* pros: 容易擴展功能、OS較能適應別的架構、kernel mode code 減少 $\Rightarrow$ reliale & secure
* cons: inter-subsystem communication 成本增加，component分得越細，成本越高。
* [More Detail](https://hackmd.io/@sysprog/microkernel-design)

* [Modules (Object-Oriented)](http://cc.ee.ntu.edu.tw/~farn/courses/OS/slides/ch02.pdf)
* 現在大多數系統使用 loadable kernel modules，Core Components 是分離的，需要時可以被 kernel 動態加載

* Hybrid Systems
* 就是上面的都來一點以兼顧不同 Policy
* Linux: monolithic + modular
* Windos: monolithic (most) + microkernel + modular

### Virtual Machines
* 為硬體 (單一電腦) 提供不同的執行環境 (Create Illusion of environment)
⇒ **Allows OSes to run on other OSes**
1. Emulation (仿真): 通過軟體模擬虛擬機硬體，慢
2. Virtualization (虛擬化): VMM (Virtual Machine Manager) = Hypervisor **可以不通過 host OS** 直接取用 HW source

## Ch03 Process
### Process Concept
* job = process (active) = program (passive stored on disk (**executable file**)) in execution
* Memory Layout of C Program
#### Process State
* new: being created
* ready: runnable, waiting to be assigned CPU
* running: being executed, owns the CPU is one of running status
* waiting: waiting for event occur
* terminated: finished execution
#### Process Control Block **(PCB)** =Task Control Block
* 一種資料結構，每一個process有自己的PCB，存儲資料如下：
1. Process Status
2. CPU register, Eg: PC, IR etc
3. Memory-management information, memory allocated to the process
4. Accounting & identification information, Eg: CPU time, PID
5. I/O status information

#### Threads $\Rightarrow$ Ch04
* a process is a program that performs **a single thread of execution**

#### **Process Queues**
1. Job queue: all process in system
2. Ready queue = run queue: queue 所有 ready state 的 process
3. Device queues: queue 在等 I/O 的 process
4. Event queues: queue 在等特定 event 的 process, 各種 event 有自己的 event queue

### Process Scheduling
#### Goal
1. Multi-programming: High CPU utilization
2. Time-sharing = Multi-tasking: Short response time

#### Implement
* Context Switch (around millisec)
* 當 CPU switch，需要替換 PCB 資料 (做SL) 這就是 Context Switch，也就是switch process 的成本
* 可以通過增加 CPU register 數量降低 Switch 成本
* Schedulers
* **Long-term sceduler = Job scheduler** (不頻繁)
* 多工處理， CPU 可以執行多個 Process，以最大化利用 CPU，由它決定哪個 Process 從 job queue 到 ready queue (admit)
* Process被分成兩種，最好是混合
1. I/O-bound = short CPU bursts
2. CPU-bound = long CPU bursts
* Windows 和 UNIX 沒有，所有 job 都被丟進 memory。
* 當希望保有但 degree of multi-programming 降級：Midterm Scheduling
* **Short-term scheduler = CPU scheduler** (頻繁，millisec.)
* 決定 ready queue 上的 proocess 哪個該被執行
* 經常做 Context Switch (PCB 資料轉換)
* **mid-term scheduler**
原因是：**improving process mix**
* 可能因為一開始沒有正確評估出 memory 大小
* 可能不確定是 I/O bound 還是 CPU bound
### Operations on Process
#### Creation
* 根據Creation關係，可以畫出 tree of processes, 他們的 **pid** 不同
* Child 的 資源可以由 OS 或 Parent 給予，後者的好處有可以避免 Child 一直做 Creation 吃掉系統資源
* Parent 和 Child 的關係可以有
* 資源分配: 共用、Child使用部分Parent資源、不共用(Child資源由OS提供)
* 執行: concurrently (同時)、Parent wait for child termination
* [Address space](https://ntust-csie-islab.github.io/106-OS-homework1/%E9%9A%A8%E7%8F%AD%E9%99%84%E8%AE%80m121355/): 相同 / 不同
* 舉例(UNIX):
* **fork()** system call creates new process
* [**exec()**](https://jasonblog.github.io/note/linux_system/linuxxi_tong_bian_cheng_zhi_jin_cheng_ff08_wu_ff09.html) system call used after a fork() to **replace** the process’ memory space with a new program

int main() {
    pid_t ret, dead;
    int status;
    
    ret = fork(); // fork another process, ret = child pid
    if (ret < 0) { // Error occured
        fprint(stderr, "Fork Failed.");
        exit(-1);
    }
    else if (ret == 0) { // child process
       execlp("/bin/ls", "ls", NULL);
       // 用/bin/ls的檔案取代接下來的code
    }
    else { // parent process
        dead = wait(&status); //dead = -1 代表 Child terminal，否則會回傳 Child pid
        printf("Child Complete.");
        exit(0);
    }
}


#### Termination
* Process 結束時，通過 `exit()` system call 呼叫 OS 刪除自己 (Free / Deallocate PCB and resource)，其 Parent 可以通過 Wait 指令 get exit status
* Parent 可以主動 terminate Children
* 可能因為吃太多資源或不需要了
* 有的 OS 在 Parent Terminate 時會讓所有 Children termiated $\Rightarrow$ cascading termination, Eg: VMS
* 也可能是將 Parent 設成 init/systemd (pid = 1), Eg: UNIX
### [Inter-Process Communication (IPC)](https://tomchen.me/2020/06/07/OS/%5BOS%5D%20%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1%E7%AD%86%E8%A8%98-Process%E9%96%93%E7%9A%84%E6%BA%9D%E9%80%9A/)
* Independent process 不受其他 process 影響，也不影響其他 Process；Cooperating Process 則相反
* 任何共用 Data 的 Process 都是 Cooperating Process，對於需要切割 job 後平行跑的 MP system 而言是必要功能* Communications Models
* [兩種model](https://hackmd.io/@YiZjennnnn/ipc_interprocess_communication#Message-Passing)
* Shared Memory: 更快，不用 System Call for read / write
* Message Passing: 更慢，需要 System Call for sending / receiving，但更容易實現

#### Shared Memory
* Memory region 需要先宣告，然後被 attached to processes 的 address space (不再使用時被 detach)
* Producer-Consumer Problem
* 實作時因為 Memory 存在容量問題，根據盛裝 Data 的 Buffer 分類為
* unbounded-buffer: Producer 不用等, Consumer 可能要等
* bounded-buffer: 兩個都可能要等
* Shared Memory:

#define BUFFER_SIZE 10
// 實際可以有 BUFFER_SIZE-1 個 elements
typedef { ... } item; // 宣告 Data 的資料結構
item buffer[BUFFER_SIZE];
int in = 0, out = 0;
if (in == out) {
    // empty
}
else if ((in + 1) % BUFFER_SIZE == out) { 
    // full
}

* Producer:

while (1) {
    while ((in + 1) % BUFFER_SIZE == out) {
        //full, do nothing
    }
    buffer[in] = item;
    in = (in + 1) % BUFFER_SIZE;
}

* Comsumer:

while (1) {
    while (in == out) {
        // do nothing, nothing in buffer
    }
    item = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
}

> skip the POSIX code，寫了我也不會記得 :+1:

#### Message Passing
* Operation: Send and Receive
* Sender 和 Reciever 要有 Communication link，Message size 可變可不變
* 分成 Direct Communication 和 Indirect Communication
* 也分成 Synchronization = Blocking 和 Asynchronous = Non-Blocking
* Blocking 和 Non-Blocking 可以成對，比如 Blocking Sender + Non-Blocking Receiver
##### Direct Communication
通過 Link 連接一對 processes，必須一邊 call send 一邊 call recieve 才能溝通
* Properties:
1. Processes 之間必須**明確**知道收 / 送件人
2. Link 自動建立，一對 process pair 一個 Link
3. Symmetric Addressing
4. Pid 嚴格規範，如果 Pid 改變就出事
##### Indirect Communication
通過 Mailboxes = ports 運送 msg，mailbox 有自己的id，只有共享 mailbox 的 Processes 能交流
* Properties:
1. 共享 mailbox 的 processes 有 Link (不局限於兩個 Processes，同時 pair of processes 之間也可能不只一個 Link)
2. Link 可以是單向也可以是雙向
3. Mailbox owner 可能是 creator 或 OS
* Creator:
代表 Mailbox 存在該 Process 的 address space 且該 Process 是唯一的 reciever；當 Process terminal，Mailbox 消失
* OS:
OS 會給 User 刪除 Mailbox 的方法，即使 Creator Process terminal，Mailbox 仍可能存在
##### Synchronization = Blocking
* Blocking Sender: 一定要確認 receiver 有收到 message ，才能 return
* Blocking Receiver：一定要拿到 message 才能 return

##### ASynchronization = Non-Blocking
* Non-Blocking Sender: 反正我是送出去了，但可能有 drop
* Non-Blocking Receiver: **多 return 一個 token**，檢查到底有沒有真的收到訊息
##### Buffer
1. **0 capacity**：Sender 要等 receiver
2. **Bounded capacity**：Full 時 Sender 等；Empty 時 Receiver 等
3. **Unbounded capacity**：Sender都不用等；Empty 時 Receiver 等
> skip POSIX and System V API again :+1:
### Examples of IPC Systems
#### Pipes = Anonymous Pipes in Windows
* Require **Parent-Child relationship**, 通常單向

int main(int argc, char *argv[]) {
    int pipefd[2];
    pid_t cpid;
    char buf;
    if (argc != 2) {
        fprintf(stdrr, ": %s<string>\n, argv[0].");
        exit(EXIT_FAILURE);
    }
    if (pipe(pipefd) == -1) {
        perror("pipe");
        exit(EXIT_FAILURE);
    }
    cpid = fork();
    if (cpid == -1) {
        perror("fork");
        exit(EXIT_FAILURE);
    }
    if (cpid == 0) { // Child read from pipe
        close(pipefd[1]); // Close unused write end
        while(read(pipefd[0], &buf, 1) > 0) {
            write(STDOUT, &buf, 1);
        }
        write(STDOUT_FILENO, "\n", 1);
        close(pipefd[0]);
        exit(EXIT_SUCCESS);
    }
    else{
        close(pipefd[0]);
        wrtie(pipefd[1], argv[1], strlen(argv[1]));
        close(pipefd[1]);
        wait(NULL);
        exit(EXIT_SUCCESS);
    }
}

> 關於 [argc, argv](https://blog.gtwang.org/programming/c-cpp-tutorial-argc-argv-read-command-line-arguments/)，argc 的報錯指定只有兩個參數
> argv[1] 是要丟進 pipe 的 data，argv[0] 則指向程序運行的全路徑名
> 操作解析：
> 1. 檢查兩個參數、檢查 pipe 兩端有 process
> 2. Fork (檢查是否失敗)
> 3. cpid = 0 $\Rightarrow$ Child: 關閉 pipe[1]\(sender)，將 pipe[0]資料儲存，關閉 pipe[0]，EXIT(0)
> 4. cpid != 0 $\Rightarrow$ Parent: 關閉 pipe[0]\(reciever)，將 argv[1] 資料寫入 pipe[1] ，關閉 pipe[1]，EXIT(0)
#### Named Pipes = FIFOs
* **不必須是 Parent-Child relationship**
### Communication in Client-Server Systems
#### Socket
* 定義：Endpoint for Communication，由 IP address 和 port 組成
#### Remote Procedure Calls (RPC)
* 讓 Client 如同呼叫本機一樣呼叫 remote host，msg 通過 RPC daemon；msg 包含 function id and parameter，結果再以 msg 方式回傳
* Issues
1. 協定，需要統一 Data 存放、表現方式，由 marshaling 處理
2. Error handling
* 可能因為網路錯誤而 fail 或 丟出很多次 msg
* ALO && AMO
* **At Least Once (ALO)**:
Server 收到會回 Client **Ack**，即"至少成功傳出一次"
* **At Most Once (AMO)**:
Server 收到一樣 (timestamp) 的 msg 會直接 drop 掉
3. Blinding: Client 不知道 Server 的 Port？會有 daemon 在監聽固定的 port 去確認 server port
#### Remote Method Invocation (RMI, for Java)
> 就 Java 版，不想寫


## Ch04 Threads & Concurrency
### Overview
* Process 是 OS 分配資源的最小單位；Thread 則是 CPU 運用的基本單元
* Process 是 Thread 的容器，Process 分為 Single- / Multi-Threaded Process

### Multithreading
* 因為 Process Creation 很耗時，當我們想要一個 Server 提供給大量 Client 就會很卡 $\Rightarrow$ 改用更輕量的 Thread
* 在 RPC (Remote Procedure Calls) 中 Thread 也被使用
* 優點(前二者也是 multi-process 的優點，後二者針對 multi-thread)：
* Responsiveness: 可以服務很多 Client，不會被一個 Client 卡死
* Utilization of MP Architecture，可以實現平行運算
* Resource Sharing
* 更輕量 = Economy

* System 處理 Task 可以分成
* Concurrency: 跑跑 A 再跑跑 B，算都有 support
* Parallelism: 同時在跑很多 task
* Data Parallelism: 切割 Data 後對 Data 做一樣的事
* Task Parallelism: 對同一份 Data，不同任務自己拉要用的去跑
#### Amdahl’s Law
根據系統的 parallel 和 serial 比例以及 core 數推估速度提升
#### Thread Types
1. User thread: done by **thread libarary**
2. Kernel thread: Supported by kernel
#### Multi-thread models
1. Many-to-One
* 好處: thread 管理上比較 efficient
* 壞處: 只要一個 user thread 做 blocking system call，就會卡住其他所有 thread $\Rightarrow$ 無法做 Multi-Thread
2. One-to-One
* 好處: 沒有上面的 blocking 問題
* 壞處: 過多的 kernel thread 對 kernel 負擔過大
3. Many-to-Many (M user thread $\Rightarrow$ N kernel thread, N $<=$ M)
* 好處: 沒有 Blocking 問題、Kernel 負擔不過重
* 壞處: 設計複雜
4. Two-level Model(類似M:M，只是允許少部分 thread 單獨 map 成 kernel thread)

### Thread Libarary
* 提供 API 去創建和管理 thread
* 分成
* User-level library: code 和 data structure 都在 user space，library call 不會產生 system call
* Kernel-level library: code 和 data structure 都在 kernel space，library call 通常會產生 system call
* Eg:
1. Pthread (User / Kernel)

int sum; // global variable, 不同 threds 共用
void *runner(void *param); // sub-thread code

main(int argc, char *argv[]) {
    pthread_t tid; //thread id
    pthread_attr_t attr; //thread attribute
    if (argc != 2) {
        fprintf(stderr, "usage: a.out <integer value>\n");
    }
    if (atoi(argv[1]) < 0) {
        fprintf(stderr, "%d must be <= 0.\n", atoi(argv[1]));
    }
    
    pthread_attr_init(&attr); // get default attribute value
    pthread_create(&tid, &attr, runner, argv[1]); // 回傳新建 tid，賦其 attr 以及 function name and input
    pthread_join(tid, NULL); // 等新 thread 結束
    printf("sum = %d.\n", sum);
}

void *runner(void *param) {
    int upper = atoi(param);
    int i; // These are local var.
    sum = 0; //This is global var.
    if (upper > 0) {
        for (i = 1; i <= upper; i++)
            sum += i;
    }
    pthread_exit(0); // end thread
}

2. Windows (Kernel)

CreateThread() => create the thread
WaitForSingleObject() => wait for thread to finish

3. Java threads
> Skip, 我肯定不會記得

#### Implicit Threading ($\Leftrightarrow$ Explicit threading)
告訴系統這塊要平行，但是不自己寫
Eg: OpenMP
`#pragma omp parallel` 用於宣告 parallel region

### Threading Issue
#### Semantics of fork() and exec()
* Question: 當一個 process 有 5 個 thread，其中一個 call fork()，該怎麼處理？
Ans. 1: 複製全部
Ans. 2: 只複製 call fork() 的 caller thread
$\Rightarrow$ 當該 thread 接下來會 call exec()，可以只複製 caller，其他情況則複製全部 thread

#### Thread cancelling
* 想要在一個 thread 結束前 terminate
* Solution:
1. Asynchronous Cancellation:
* 馬上 terminate thread
* 缺點：資源已被分配、該 thread 可能正在更新共用的資料
2. Deffered Cancellation:
* 讓 thread 在安全點檢查是不是有人叫他刪掉: `pthread_testcancel()`
* 確保 thread 是在 Cancellation Point (save point) = `open()/close()/read()/write()` 被刪除
3. 就不給刪

#### [Signal handing](https://hackmd.io/@Chang-Chia-Chi/OS/https%3A%2F%2Fhackmd.io%2F%40Chang-Chia-Chi%2FOS-CH4)
Signal are used in UNIX systems to notify a process that a particular event has occurred
**A signal can be handled only once!!**
1. Signal 由特定事件產生
2. Signal 會被送給 Process (Signal destination)
3. Signal is handled by signal handlers
* What if a multi-threaded process 收到 Signal？
1. 給 signal 指定的 thread.
- For syn signals, 要送給搞出 signal 的 thread
2. 給 process 裡所有 thread
- For Ctrl-C, 要送給所有 thread
3. 給 process 某個特定 thread
4. 設定一個 thread 接收所有 process
- 直接由 main thread 來處理 signal，如 file handler 的操作

#### Thread pools
考慮一個面對大量 Client 的 web server，如果每個 Client 來都創一個 thread 給他：
1. Thread creation and termination 都要成本 (Thread 有自己的 register 和 Stack)
2. Thread 沒有上限

Solution: Thread Pools
* 先建好 Pool of Thread，創好的 thread 放在裡面等著被用
* \# of thread in pools 取決於 (部分 pool 架構的 thread 數量是可調整的):
* CPU 數量
* 實際 memory 大小
* 預期的使用量

#### Thread specific data = Thread-Local Storage (TLS)
* 讓 Thread 擁有自己的一份 Data copy
* 注意：封裝性
1. Global variable: 不同 threads 都能看到
2. Thread specific data: 僅有該 thread 和被該 thread call 的 fuction 才能看到該 variable
3. Local variables: 只有 during single function invocation 可視

### Operating-System Example
> 放棄背 code :crying_cat_face:

## Ch05 CPU Scheduling
### Basic Concepts
* Scheduling: **basis of multi-programming** = switch CPU between process to improve CPU utilization
* CPU burst cycle: cycle of CPU execution, 包含執行指令以及等待被從 rea待被從ready 選回 running 的時間
* I/O burst cycle: cycle of I/O waI/O wait

* CPU Scheduler = short-term scheduler: 從 ready to execute 的 process 中選擇，並給它 CPU。出現時機：
1. Process 在等 I/O 或 children: 從running 移到 waiting (主動放棄)
2. Process 跑太久了 (time expire): 從 running 移到 ready (被 Scheduler 趕走)
3. Process 完成 I/O: 從 waiting 回到 ready (被 Scheduler 趕走)
4. 在跑的 Process 做完了: Terminate (主動放棄)

* Non-preemptive vs. Preemptive
* Non-preemptive Scheduling = Cooperative Scheduling：
* 只要不主動放棄 CPU，就沒人能搶
* 需要 Process 自主合作
* Code 好寫、不用額外硬體支援、USER感受可能較差
* Preemptive Scheduling:
* 對於 Time-sharing system 或 real-time system 較合適
* 更多的 context switch (cost)、額外的硬體、複雜的 code

### Scheduling Criteria
1. CPU Utilization ($\Uparrow$ , better)
* CPU 有多少比例的時間是非閒置的
2. Throughput ($\Uparrow$ , better)
* 單位時間可以完成多少 process
3. Turnaround time ($\Downarrow$, better)
* 對於一個 process，從 process submission 到 process termination 的時間 (即開始到結束)
4. Waiting time ($\Downarrow$, better)
* 從進 ready queue 到被選走的時間
5. Response time ($\Downarrow$, better)
* 從 request submmitted 到第一個 response 的時間

### Scheduling Algorithm
1. FCFS
* 先到先做
* 缺點: non-preemptive
* 護衛效應(_Convoy Effect_): 如果第一個 process 很長，會使所有 process waiting time 上升
* 低 CPU 利用率
2. SJF
* Burst短的先做
* 分成兩種：
* Non-preemptive: 不檢查 new process 的時間，只在每次拿 Process 時挑最短的，一定會把手頭上的做完
* Preemptive = **Shortest-Remaining-Time-First (SRTF)**:
發現新的 process 進來，所有 process 的剩餘時間進行比較

3. Predicting of Next CPU Burst

4. **Round Robin (RR)**
* 設定一個時間 Time Quantum **q**，大家都上來跑，不能超過 **q**，否則就 Time expire 請下去 ready queue
* 較差的 average turnaround time 和較好的 response time
* **q** 太大 $\Rightarrow$ FIFO
**q** 太小 $\Rightarrow$ 太多 Context Switch 消耗
* 經驗法則：CPU burst * 80% < **q**

5. Priority Scheduling
* 進來的 Process 有 Priority 編號，由小到大做；其實 SJF 就是 Priority 的一種
* 缺點：**Starvation** - 低優先度的可能永遠做不到
Solution: **Aging**

6. Multiple-Processor Scheduling
* 當 Process 可以被輕鬆分類時使用，將Process 分在不同的 Queue 並依據特性決定算法
* Eg: Foreground (有互動需求) 和 Background (可以分批處理)，FG可以有比較高的 Priority $\Rightarrow$ FG uses RR + BG uses FCFS
* Scheduling 要兼顧不同的 Queue
* Eg: 固定 Priority 先做 FG 再做 BG；或 Time slice，大多數時間做 FG、少部分做 BG

**$\overrightarrow{\rm improved}$ Multilevel Feedback Queue:** 配合已經處理的資訊換 Queue
* Eg: 如果 CPU bound Process 一直占用資源 $\Rightarrow$ 降級去低優先級的 Queue；如果低優先級 Queue 裡有 Process 一直沒拿到 CPU 就：$\overrightarrow{\rm aging}$ 移動到更高優先級的 Queue
* The most **generic and complex** algorithm

## Reference
Mainly Based on CSIE, NCKU OS class 2023

### Ch01
1. [陳士杰-作業系統(Operating Systems) (Operating Systems)](http://debussy.im.nuu.edu.tw/sjchen/OS/97Spring/Ch_1.pdf)
2. [作業系統筆記-電腦系統架構](https://tomchen.me/2020/03/19/OS/%5BOS%5D%20%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1%E7%AD%86%E8%A8%98-%E7%B3%BB%E7%B5%B1%E6%9E%B6%E6%A7%8B/)

### Ch02
1. [系統程式ch5:Linker/Loader](https://hackmd.io/@alan303138/Sy26KTAJY#%E9%80%A3%E7%B5%90%E5%99%A8)
2. https://hackmd.io/@sysprog/microkernel-design
3. http://cc.ee.ntu.edu.tw/~farn/courses/OS/slides/ch02.pdf

## Midterm
### 簡稱練習
1. RPC
2. PCB
3. NUMA
4. IVT
5. DMA
6. SJF / SRTF
7. ALO & AMO
8. ISR
9. RR
10. TLS

### 名詞練習

1. Storage Hierarchy
2. Multi-processor systems
3. Multi-core systems
4. Clustered Systems
5. Long-term scheduler & short-term scheduler & mid-term scheduler
6. Dual-Mode Operation
7. Privilege escalation
8. Emulation & Virtualization (type I & II)
1. Linker and Loader
2. Simple Structure - Layered Approach - Microkernels - Modules
3. Process State Diagram
4. Process Queues
5. Context Switch
6. Tree of processes Diagram
7. Parent & Children fork() & exec() Diagram
8. Shared Memory & Msg passing
9. direct Communication & Indirect Communication
10. Pipes & Named Pipes
11. Socket
12. Multithreading
13. Throughput
14. Multilevel Feedback Queue
15. Turnaround time
16. Non-preemptive vs. Preemptive
17. Thread Pools
18. Deffered Cancellation
19. Concurrency
20. Implicit Threading