# Chapter 1 Introduction
## Computer System Srtucture
<img src="https://hackmd.io/_uploads/Hk3OslxzA.png" width="400" height="auto">

1. Hardware
provides basic computing resources
etc:CPU, memory, I/O devices
2. Operating system
Controls and coordinates use of hardware among various applications and users
3. Application programs
define the ways in which system resources are used to solve the computing problems of users
Word processors, compilers, web browsers, database systems, video games
4. Users
People, machines, other computers
## Interrupt Handling(中斷管理)
### Polling(輪詢)
逐個檢查不同資源是否有中斷服務
### Vectored Interrupt system(向量終止系統)
系統能夠利用向量，定義哪裡發生問題
## I/O Structure
### 同步（Synchronous）
在I/O开始后，只有在I/O完成后，控制权才会返回给用户程序。
1. Wait instruction idles the CPU until the next interrupt
2. Wait loop (contention for memory access)
3. At most one I/O request is outstanding at a time, no simultaneous I/O processing
### 異步（Asynchronous）
在I/O开始后，控制權会立即返回给用户程序，而不必等待I/O完成。
1. System call – request to the OS to allow user to wait for I/O completion
2. Device-status table contains entry for each I/O device indicating its type, address, and state
3. OS indexes into I/O device table to determine device status and to modify table entry to include interrupt
### Signal: hardware interrupt
1. hardware 會偵測到事情發生，對 OS 打一個 signal，並將正在執行的程式資訊記下來
2. OS 去查 function vector 找誰是主事者，然後 call 他（稱作 service routine）
3. 執行完就 return，然後回去執行原本在跑的程式
P.S: function vector 的數量是跟著硬體燒死的，所以是數量固定的 array（就是 vector)
### Trap: software interrupt
> It’s a trap!

user call 一個 system call （或是跑了個除以零的程式產生 exception）
trap 到 OS 去
查 switch case 表中要執行哪個程式
查到了就跑他
跑完就 return 到剛剛 call system call 的人身上
因為是軟體，system call 的數量是無上限的，想訂幾個就幾個，所以步驟三會用 switch case 的方式去寫。

## Process Management
> 我相信看的人有學過組語 不解釋

Single-threaded process has one program counter specifying location of the next instruction to execute
Process executes instructions sequentially, one at a time, until completion
Multi-threaded process has one program counter per thread
Typically system has many processes, (some user, some OS) running concurrently on one or more CPUs
Concurrency by multiplexing the CPUs among the processes / threads

# Chapter 2 Operating-System Services
## System Call
定義：幫助執行中的 user process 與 kernel 之間溝通，當 user peocess 需要OS提供某種服務時，會先以 Trap 通知 OS (由 User mode 轉為 Kernel mode) 並傳入System call ID (no.) 及所需參數，接著 OS 執行對應的 System call，完成後將服務結果回傳至 User process。
### 參數(Parameter) 傳遞方式
1. 暫存器( Register )：保存參數於暫存器之中傳遞給作業系統。
2. Pros：簡單、存取速度快( 無記憶體存取 )。
3. Cons：不適用於存取大量參數的情況。
2. 記憶體( Memory )：以一個區塊( Block, Table )儲存這些參數並將此區塊的起始位址存於一個暫存器之中傳遞給作業系統。
3. Pros：適用於大量參數。
4. Cons：存取速度較慢，且操作較為麻煩。
3. 系統堆疊( Stack )：將參數 Push 堆疊之中，作業系統再從堆疊 Pop 取得參數。
4. Pros：也適用大量參數的傳遞，操作也很簡單。
5. Cons：目前無( 可用暫存器或是記憶體實現堆疊 )。
### 種類
1. Process Control：建立、終止、暫停、恢復執行 process，設定/讀取 process attribute。
2. File Management：建立、讀、寫、開啟、關閉、刪除檔案。
3. Device Management：讀、寫 Device。
4. Information of Maintenance：取得系統日期、時間，取得process屬性。
5. Communications：process之間的通訊，且只針對Massage Passing方式提供服務。
6. Protection：硬體資源的保護，檔案讀取控制。
## Role of the linker and loder
<img src="https://hackmd.io/_uploads/H1lFmGxM0.png" width="400" height="auto">

## Kernel

# Chapter 3 Processes
## Memory
<img src="https://hackmd.io/_uploads/Byqrz-ezR.png" width="400" height="auto">

1. Stack containing temporary data
Function parameters, return addresses, local variables
2. Data section containing global variables
3. Heap containing memory dynamically allocated during run time
## Process State
<img src="https://hackmd.io/_uploads/r1WOzbgGA.png" width="400" height="auto">

## Process Scheduling
<img src="https://hackmd.io/_uploads/Hy4J7bxMA.png" width="400" height="auto">

## Process Creation

## Preemptive(搶佔式) vs. Non-preemptive(非搶佔式)
CPU scheduling 的決定時機主要有以下幾個
1. 從 running 換到 waiting state
2. 從 running 換到 ready state (CPU burst 被打斷，time sharing)
3. 從 waiting 到 ready state
4. 終止狀態
### Non-preemptive scheduling: 若一個 process 可以繼續執行(在 CPU burst)，則不會被打斷
1. 因此只會在上面 1. 跟 4. 的情況下作 re-scheduling
### Preemptive scheduling
在所有情況都有可能 re-sheduling

# Chapter 5: CPU Scheduling
## 指標
1. CPU的使用效率(CPU utilization) —越高越好
2. 單位時間內完成的工作量(throughput) —越多越好
3. Process進入CPU到完成的時間(turnaround time) —越短越好
4. Process被叫進ready queue到完成時，等了多久(waiting time) —越短越好
5. 當有需求時，多久能給回覆(response time) —越短越好
### Algorithms
#### FCFS
依照抵達順序執行(先來的先執行)
### SJF
#### Preemptive Version
當有新的行程且他的 CPU burst 的長度比較小，搶佔發生
#### Non-preemptive Version
永遠不會發生搶佔，每個執行完後，找尋brust時間最少當作下一個
### Priority scheduling
依據優先權來排順序，以整數代表優先權，數字越小優先權越高。
### RR(Round Robin)
給每個process一個固定的時間(time quantum ,q)執行，如果執行不完就再去排隊。如果有n個process在ready queue，每個process有1/n CPU時間，一定不會等超過(n-1)q的時間。以下有例圖，q=4:
### Multilevel Queue
這種演算法將ready queue分成兩個：Foreground(需要交談的)、Background(可以批次的)。而這兩種queue有各自運用的演算法。而在排程時，這兩種queue之間要先做優先順序的排程、CPU時間的分配。

Foreground：RR演算法、高優先、80%的CPU時間
Background：FCFS演算法、低優先、20％的CPU時間
### Multilevel feedback queue
因為Multilevel queue的順序是固定的，有時還是需要調整一下順序，所以產生Multilevel feedback queue演算法，所以他是一種動態的排程機制。但這種演算法需要考量：
有幾個queue
每個queue的演算法
什麼時候要把順序往前調
什麼時候要把順序往後調
queue的選擇
## real-time scheduling
### Rate Monotonic Scheduling：
是最常用的演算法，依據頻率高低決定優先權，週期短(頻率高)有高優先權，週期長(頻率低)較低優先權。以下為例題跟運算：
### Earliest Deadline First Scheduling：
依據誰的deadline先到，誰的優先權就越高。以下有範例即運算：
### Deterministic modeling
是以分析的方式，選擇哪種演算法適合。但是我們沒有那麼多時間，可以用運算waiting time的時間做分析。
### Queueing modeling Little’s Law
## NUMA and CPU Scheduling

# Chapter 6 Synchronization Tools(同步工具)
Mutual Exclusion - If process Pi is executing in its critical section, then no other processes can be executing in their critical sections
Progress - If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the process that will enter the critical section next cannot be postponed indefinitely
Bounded Waiting - A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted
Assume that each process executes at a nonzero speed
No assumption concerning relative speed of the n processes
## Tool
mutex locks, semaphores, monitors
### Mutex
### Semaphore
### monitors
# Chapter 7
## Bounded-Buffer Problem：
假設有n個buffers，每個都有資料，三個semaphore預設值為mutex=1、full=0、empty=n
Producer要將資料放進去，以下是他的結構圖：
## Readers and Writers Problem：
有一個data set，有很多process同時共享著。
Readers：只能讀data set，不能寫，可以同時有多個readers
Writers：可讀可寫data set，但同時只能有一個writer取得
Writer和reader考慮的幾種變化，都涉及某種形式的優先事項。
## Dining-Philosophers Problem
五個哲學家要吃飯，桌上有五支筷子，而他們只會思考跟吃飯而已，而且不跟隔壁交談。以下有一個架構，這個會造成deadlock，因為大家都拿起右邊的筷子，這樣大家都不能吃

要解決這個deadlock，有幾個解決辦法：

4個人上餐桌
左右筷子都空下來才能吃
非對稱式方法：奇數先取左邊再取右邊，偶數先取右邊再取左邊
用semaphore解決問題，但他也不保證不會出現deadlock和starvation。
## Montiter sloution
## Deadlock

- A situation in which **every** process in a set of processes is **waiting** for an event that can be caused only by another process in the set

:::success
**Ex.**
- 2 processes and 2 tape drivers
- Each process holds a tape drive
- Each process requests another tape drive
:::

## System Model

A **thread** may use a resource in the following sequence
- **Request**
- 要求分配某些資源
- **Use**
- 使用分配到的資源
- **Release**
- 釋出分配到的資源
---
- Resources types $R_1,R_2,...R_m$
- E.g., CPU, Disk, I/O devices, ...
- Each resource type $R_i$ has $W$ instances
- E.g, a computer has 4 CPU cores, 1 networking interface ...

## Deadlock in Multithreaded Applications

- 若 work 1 等到 `second_mutex` 前， work 2 已取得 `second_mutex`，就會產生 deadlock
- work1 持有 `first_mutex`，並等待 work 2 持有的 `second_mutex`，但 work2 也在等 work1 的 `first_mutex`
- work2 需要 work1 釋出 `first_mutex`，才能釋出 `second_mutex`，但同時 `second_mutex` 要先被釋出 work1 才會釋出 `first_mutex`

## Deadlock Characterization

### Necessary Conditions
- A deadlock can arise when four conditions hold simultaneously
- **Mutual Exclusion**
- Only 1 process at a time can use a resource
- 一個 resource 一次只能被一個 process 使用
- **Hold** & **wait**
- A process holding some resources and is waiting for another resource
- Process 至少取得一個 resource，然後等其他 process 握住的 resource 釋出
- **No preemption**
- a resource can be only released by a process voluntarily
- 釋放資源時，是 process 自願的，沒有被中斷
- **Circular wait**
- there exists a set $\{P_0,P_1,...,P_n\}$ of waiting processes such that $P_0 \rightarrow P_1 \rightarrow ... \rightarrow P_n \rightarrow P_0$
- 每個 process 都在等另一個 process 握住的 resource 釋放，這也代表 single process 不會有 deadlock

:::warning
**All 4 conditions** must hold for **possible deadlock**
(要形成deadlock，必須同時滿足 4 個條件)
:::

### Resource-Allocation Graph

- System resource-allocation graph
- Request edge
- Assignment edge


## Methods for Handling Deadlocks

- Deal with the deadlock problem in one of three way
- Ignore the problem
- Use a protocol to **prevent** or **avoid** deadlocks, ensuring that the system will never enter a deadlock state
- Allow the system to enter a deadlock state, **detect** it, and **recover**

## Deadlock prevention

- For a deadlock to occur, each of the four conditions necessary conditions must hold
- By ensuring that **at least one of these conditions cannot hold**, we can prevent the deadlock
- 設計時就不讓 deadlock 產生

### Mutual exclusion

- sharable resources
- Non-sharable resources
- 對**不可共用**的資源類型(例如寫檔)而言，**互斥一定成立**
- 而可共用的資源類型(例如讀檔，因為可以同時讀取相同檔案)，一定不會產生

### Hold and wait

- Process 必須保證在要求一項資源時，不能佔用其他資源，除非他可以一次取得所有資源
- Require each process to request and be allocated all its resources before it begins execution; or, allows a process to request resources only when it has none
- Disadvantages
- Low resource utilization
- Starvation is possible

### No Preemption

- 只要 process 握著一些資源，但得不到其他的，就要先全部釋放，再重新申請
- If a process is holding some resources and requests another resources that cannot be immediately allocated to it, then all resources the process is currently holding are preempted

### Circular wait

- 對 resource type 強制安排線性順序，不讓 circular wait 的條件達成
- Impose a total ordering of all resource types and to require that each process requests resources in an increasing order of enumeration

void transaction(Account from, Account to, double amount) {
    mutex lock1, lock2;
    lock1 = get_lock(from);
    lock2 = get_lock(to);
    
    acquire(lock1);
        acquire(lock2);
    
            withdraw(from, amount);
            deposit(to, amount);
    
        release(lock2);
    release(lock1);
}

## Deadlock Avoidence

## Safe state

- Safe sequence


### Resource-Allocation Graph Algorithm

- Single instance of each resource type
- Use a variant of the resource-allocation graph
- 以下圖為例，方框表示 resource、圓形表示 process
- 從 process 指向 resource 的虛線箭頭: 表示 process 想要該資源
- 從 resource 指向 process 的實線箭頭: 表示資源被分配給該 process



## Banker's Algorithm

- Data structures
- Available: 目前系統中可用的閒置資源
- Max: 某個 process 要完成執行，需要的資源數量
- Allocation: 某個 process 已分配到的資源數量
- Need: Max - Allocation，即某 process 還需要多少資源以完成執行

<!-- example to do -->

## Deadlock Detection

### Single Instance of Each Resource Type

- Wait for graph


### Several Instances of a Resource Type

- Deadlock detection algorithm
- Data structure
- Available
- Allocation
- Request

### Detection-Algorithm Usage

- How often is a deadlock likely to occur?
- How many processes will be affected by a deadlock when it happens?

## Recovery from Deadlock

### Process and Thread Termination

- Abort **all** deadlocked processes
- Abort **one** process at a time **until the deadlock cycle is eliminated**

---

- The factors may affect which process is chosen
- What the **priority** of the process is?
- **How long** process has computed and **how much longer** the process will compute before completing its designated task?
- How many and what types of **resources** the process has used?
- **How many more resources** the process needs to complete?
- **How many** processes will **need to be terminated**?
- Whether the process is **interactive or batch**?
- 停止 batch process 使用者比較無感
- QoE (Quality of Experience)

### Resource Preemption

- Three issues need to be addressed
- Selecting a victim
- 選擇哪個 process 要被搶佔 (preempted)。
- 確保搶佔的順序以最小化成本。
- Rollback
- 從某個 process 搶佔資源可能會使其無法正常執行，必須 rollback 回到某個安全的狀態再繼續。
- 最簡單的 rollback 是直接中止這個 process；較有效率的方法是僅在必要時打破 deadlock，但系統需要保存更多關於每個 process 的 state 的資訊。
- Starvation
- 如何保證資源不會總是被同一個 process 搶佔？
# Chapter 9

## Background

### Basic Hardware

- Instruction execution cycle
- Stall
- Cache
- Base register
- Limit register
- 這兩個暫存器定義 logical address space，分別記錄 process 起始記憶體位置 (base register) 跟 process 所占記憶體位置大小 (limit register)。


### Address Binding


- Bind
- The binding of instructions and data to memory addresses **can be done at any step**
- Compile time
- 由 compiler 決定
- 如果知道 compile 時 process 在 memory 的位置，可以產生 **absolute address**。
- 假設知道 process 會在 location *R*，則 compile 出來的 code 會從這個位置開始 extend up。
- Load time
- 由 linking loader 或 linker editor 決定
- 編譯時無法確認，則生成 **relocation address** (不一定由固定位置執行)
<!-- TODO -->
- Execution time
- 由 OS 動態決定
- 如果記憶體區段要執行時被移動，連結才會延到這時
<!-- TODO -->

### Logical Versus Physical Address Space

- Logical Address
- Logical Address Space
- CPU 所產生的位置，又叫做 virtual address
- Physical Address
- Physical Address Space
- 記憶體看到的位置 (經過 MMU 處理過)
- <font class='red'>MMU (Memory Management Unit)</font>
- 可將虛擬位置轉換成實體位置的硬體裝置
- Relocation register
- Base register 在這被稱為 relocation register

### Dynamic Loading

- Dynamic Loading

### Dynamic Linking and Shared Libraries

- Dynamically linked libraries (DLLs)
- Static linking
- Dynamic linking

## Contiguous Memory Allocation

- Two partitions of memory
- Operating system
- User processes
- Contiguous memory allocation

### Memory Protection


### Memory Allocation

- Variable-partition scheme
- Hole
- Solutions to dynamic storage-allocation problem
- First fit
- 第一個容納得下就直接使用
- Best fit
- 看完所有記憶體空間，選一個夠大，而且最接近自己大小的使用。最後可能會生成許多很小的記憶體空間。
- Worst fit
- 看完所有記憶體空間，選一個最大的使用。最後可能會生成很大的記憶體空間。

## Fragmentation

- External fragmentation
- 剩下小塊小塊的記憶體空間，無法使用
- Internal fragmentation
- 記憶體空間給過大使用時， process 用不到，外面需要使用的也用不到
- Compaction
- 解決 fragmentation 的方法，將 process 移來移去，讓其餘的記憶體空間能夠聚在一起，但是 process 必須是 dynamic 才可以這樣做

## Paging

- Paging 是為了解決 fragmentation (external fragementation 可以解決，但 internal fragmentation 還是會存在) 跟處理很多不同大小的 process。

### Basic Method

- Frames & pages
- **Frames**: 將實體記憶體 (physical memory) 切割成固定大小的 block
- **Pages**: 將邏輯記憶體 (logical memory) 分成大小相同的 block
- Frames 跟 pages 的大小相同，當 program 需要 n 個 pages 時， OS 會去 physical memory 找 n 個 free frames 來放，frame 並不需要連續
- Page number (`p`)
- Page offset (`d`)
- Page table
- OS 會設置 page table，轉換 logical address 變成 physical address。


### Hardware Support


- <font class='red'>Translation Look-aside Buffer</font> (類似 cache 的概念)
- Parallel search
- TLB miss
- TLB 找不到的話就回去找 page table
- **有找到**：1 次 memory access；**找不到**：2 次 memory access (page table 算 memory)
- Hit ratio
- Effective memory access time

### Protection

- Valid-invalid bit


### Shared Pages

- Reentrant code
- 每次看都一樣（不能改內容）


## Structure of the Page Table

### Hierarchical Paging



### Hashed Page Tables


### Inverted Page Tables


- <process-id, page-number, offset>

## Swapping

- Backing store (disk)
- 在程式執行時，process 有時會需要暫時離開記憶體，之後會再搬回來執行，這就叫做 swapping，搬上搬下的動作我們稱為 **roll out** 跟 **roll in**。而在這裡的硬碟 (disk) 我們會將它稱作 backing store，兩者是互通的。

### Standard Swapping

- Standard swapping involves moving processes between main memory and a backing store


### Swapping with Paging

- Page out
- Page in


### Swapping on Mobile Systems

- Mobile systems typically do not support swapping in any form
# Chapter 10
## Paging vs Segmentation
## Least Recently Used (LRU) Algorithm
## FIFO Algorithm


* **Belady’s Anomaly**
Adding more frames can cause more page faults
$e.g.$ 1,2,3,4,1,2,5,1,2,3,4,5

## Optimal Algorithm

* Replace page that will not be used for **longest period of time**
* Not that possible to implement

## Trashing產生：

Frame不夠，發生page fault
Page replacement發生
很快的frame又不夠用，又需要Page replacement (2 3之間會產生很多page fault)
導致CPU使用效率低，因為process都在忙著swap in/out，CPU就空閒下來，這時CPU就會想提高程度，抓更多process進來工作。
### Working-set model：
預估process在不同時間內所需要的frame數量，並提供足夠的frame防止thrashing。他將∆定義working-set window，如果∆太小，會無法包含整個locality; 如果∆太大，就會重複很多locality，在∆等於無限大時，就等於整個program。而將Ｄ代表process對frame的總需求量，如果Ｄ>可用量時，就會發生thrashing，以下有例圖：
### Page fault frequency：
解決thrashing更直接的策略，如果錯誤率太高，就增加frame給process; 如果錯誤率太低，就會收回一些frame。
# Chapter 11 Mass-Storage Systems
## 1. FCFS（First-Come, First-Served，先到先服務）
概念：這種調度算法按請求到達的順序處理磁碟I/O請求。
優點：
簡單易實現。
保證公平，所有請求按到達順序處理。
缺點：
可能會導致高平均尋道時間。
當請求順序隨機時，磁碟頭移動距離大，導致性能低下。
示例：
請求序列：98, 183, 37, 122, 14, 124, 65, 67
磁碟頭起始位置：53
順序處理：53 -> 98 -> 183 -> 37 -> 122 -> 14 -> 124 -> 65 -> 67
## 2. SCAN（電梯算法）
概念：磁碟頭像電梯一樣來回掃描磁碟。在一端開始，移向另一端，處理沿途的所有請求。到達另一端後方向反轉，繼續處理請求。
優點：
適合高負載環境，系統性覆蓋所有請求，減少總尋道距離和變異。
相比FCFS，平均尋道時間更低。
缺點：
請求可能因磁碟頭剛剛經過而需要等待完整的掃描周期。
示例：
請求序列：98, 183, 37, 122, 14, 124, 65, 67
磁碟頭起始位置：53，初始方向向右
順序處理：53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183，反轉方向，處理剩餘請求：183 -> 37 -> 14
## 3. C-SCAN（循環掃描）
概念：與SCAN類似，但在到達另一端後，磁碟頭直接返回起始端而不處理返回途中請求。只在一個方向掃描並處理請求。
優點：
提供更一致的等待時間，防止末端請求等待時間過長。
相對於SCAN，提供更均勻的性能。
缺點：
返回途中不處理請求，可能被視為低效，但這通常被一致的等待時間和性能均勻性所抵消。
示例：
請求序列：98, 183, 37, 122, 14, 124, 65, 67
磁碟頭起始位置：53，初始方向向右
順序處理：53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183，直接返回起始端，再次處理剩餘請求：14 -> 37
這些調度算法各有優缺點，
## Raid
# File System
## 架構
檔案的架構分成三種：

沒有架構(none)：就只是文字或是bytes的序列而已
簡單記錄架構(simple record structure)：一筆筆的資料，可以是固定長度或是沒有固定的
複雜架構(complex structure)：格式化文件或是relocatable load file
至於要使用哪種架構就由作業系統或是program決定。
### 屬性
Name：給人看得，能夠讀懂
Identifier：給系統看得，唯一的標示
Type：給系統支援不同型態的檔案資訊
Location：指標指向裝置內檔案位置
Size：檔案大小
Protection：控制誰能夠讀、寫、執行
Time, date, user identification：保護和安全的資訊(保存上次修改和使用資料)，使用監督
## 目錄
### Single-level directory：
單層式的目錄，將所有檔案都放在同一個目錄內。但這樣就沒又辦法依照屬性分類，或是名稱方面不能有相同的存在。
### Two-level directory：
### Tree-structured directories
### Acyclic-graph directories
非循環式圖形目錄，他能共享子目錄跟檔案，也就是說會有別名。
### General graph directories：
一般的圖形目錄，就是有迴圈存在。如果我們不想要有迴圈，那就要規定link只能指向檔案，不能指向子目錄。或是當有新的link加入時，用cycle detection演算法看有沒有迴圈產生。.

# HW1

## Written Exercises

解答來源自助教

### 1.16

直接記憶體存取用於高速 I/O 裝置，以避免增加 CPU 的執行負荷。
**(a) CPU 如何與裝置連接以協調傳輸？**
> CPU 可透過寫入特殊暫存器來啟動 DMA 操作，裝置可獨立存取這些暫存器。 一旦收到 CPU 的命令，設備就會啟動相應的操作。

**(b) CPU 如何知道記憶體操作何時完成？**
> 當設備完成操作時，它會中斷 CPU 以指示操作完成。

**\(c) 在 DMA 控制器傳輸數據時，允許 CPU 執行其他程式。這一過程是否會干擾使用者程式的執行？如果是，請描述會造成那些形式的干擾。**
> 設備和 CPU 可同時存取記憶體。 記憶體控制器會以公平的方式讓這兩個實體存取記憶體匯流排。 因此，CPU 可能無法以最高速度執行記憶體操作，因為它必須與裝置競爭才能獲得記憶體匯流排的存取權。

### 2.15

**進程間通訊有哪兩種模式？ 這兩種方法的優缺點是什麼？**
> 進程間通訊的兩種模式是訊息傳遞模式和共享記憶體模式。 訊息傳遞適用於交換少量數據，因為無需避免衝突。 在電腦間通訊方面，它也比共享記憶體更容易實現。
共享記憶體可以最大限度地提高通訊速度和便利性，因為在電腦內部進行通訊時，可以以記憶體傳輸速度進行。 不過，這種方法在共享記憶體的進程之間的保護和同步方面有所妥協。

### 2.19

**微核心系統設計方法的主要優點是什麼？ 在微核心架構中，使用者程式和系統服務如何互動？ 使用微內核方法有哪些缺點？**
> 其優點通常包括以下幾點： (a) 新增服務不需要修改核心；(b) 在使用者模式下進行的操作比在核心模式下進行的操作更多，因此更安全；\(c) 核心設計和 功能更簡單，因此作業系統通常更可靠。
在微核心架構中，使用者程式和系統服務透過使用進程間通訊機制（如訊息傳遞）進行互動。 這些資訊由作業系統傳遞。
微核心架構的主要缺點是與進程間通訊相關的開銷，以及需要頻繁使用作業系統的訊息傳遞功能才能實現使用者進程和系統服務之間的互動。

### 3.12

**描述核心在進程間進行上下文切換時所採取的動作。**
> 一般來說，作業系統必須保存目前運行進程的狀態，並恢復計劃下一個運行進程的狀態。
保存進程的狀態除了記憶體分配外，通常還包括所有 CPU 暫存器的值。 上下文切換還必須執行許多特定於體系結構的操作，包括刷新資料和指令快取。

### 3.18

**舉例說明普通管道比命名管道更合適的情況，以及命名管道比普通管道更合適的情況。**
> 使用普通管道進行簡單通訊效果很好。 例如，假設我們有一個計算檔案中字元數的進程。 可以使用普通管道，生產者將文件寫入管道，消費者讀取文件併計算文件中的字元數。
接下來，我們來舉例說明命名管道更適合的情況，即多個進程可能會向日誌中寫入資訊。 當進程希望向日誌寫入訊息時，它們會將訊息寫入命名管道。 伺服器從命名管道中讀取訊息並將其寫入日誌檔案。

# HW2

## Written Exercises

解答來源自 ChinoCoCo

### 4.8

**提供兩個程式設計範例，說明多執行緒不會比單執行緒解決方案提供更好的效能。**
> 串行操作爲主的程序，例如:圖像進行處理的各個步驟之間通常是無法並行的
大量需要同步等待資源的程式

### 4.10

**在多執行緒進程中，程式狀態的下列哪些部分是跨執行緒共享的？
(a) 暫存器值 (b) 堆疊記憶體 \(c) 全域變數 (d) 堆疊記憶體**
> a. Register values (寄存器/CPU)
**(b.) Heap memory (動態配置變數)
(c.) Global variables (全域變數)**
d. Stack memory (區域變數)

> **stack：區域變數**
堆疊區段（stack segment）用於儲存函數的區域變數，以及各種函數呼叫時需要儲存的資訊（例如函數返回的記憶體位址還有呼叫者函數的狀態等），每一次的函數呼叫就會在堆疊區段建立一個 stack frame，儲存該次呼叫的所有變數與狀態，這樣一來同一個函數重複被呼叫時就會有不同的 stack frame，不會互相干擾，遞迴函數就是透過這樣的機制來執行的。
**heap：動態配置變數**
heap 區段的記憶體空間用於儲存動態配置的變數，例如 C 語言的 malloc 以及 C++ 的 new 所建立的變數都是儲存於此。
堆疊區段一般的狀況會從高記憶體位址往低記憶體位址成長，而 heap 剛好從對面以相反的方向成長。
## 4.16

有兩個雙核心處理器的系統有四個處理器可用於調度
- 該系統正在運行一個 CPU 密集型應用程式
- 所有輸入都在程式啟動時進行，此時必須開啟一個文件
- 同樣，所有輸出都在程式結束前進行，此時必須將程式結果寫入一個文件
- 在啟動和終止之間，程式完全依賴 CPU
- 你的任務是透過多執行緒來提高該程式的效能
- 該程式運行在使用一對一執行緒模型（每個使用者執行緒映射到一個核心執行緒）的系統上

1. **您將創建多少個執行緒來執行輸入和輸出？ 解釋一下。**
> 由於必須按順序存取文件，因此讀取和寫入文件的工作不能合理地並行化。
合理的並行化，因此每項任務只能使用一個執行緒。
2. **您將為應用程式的 CPU 密集型部分建立多少個執行緒？ 解釋一下。**
> 4個 題目有說 four processors

## 5.14

大多數調度演算法都會維護一個運行佇列，列出有資格在處理器上運行的進程。 在多核心系統中，一般有兩種選擇：
(1) 每個處理核心都有自己的運行佇列，或
(2) 所有處理核心共用一個運行佇列。

**這兩種方法各有什麼優缺點？**
> 第一種的優點在，任務不會互相干擾，也不需要等待資源，但需要更多管理以及同步，以避免資源競爭
第二種的優點在簡單方便有效率的使用系統資源，而且較好管理，但必須管控資源開銷，同步問題，可能會造成效率不佳

## 5.18

以下進程正在使用
、基於優先權的循環調度演算法進行調度。
- 每個行程都有一個數字優先級，數字越大表示相對優先級越高。
- 對於優先權相同的進程，將使用時間量為 10 個單位的循環調度器。
- 如果一個行程被優先權較高的行程搶佔，被搶佔的程序將被置於佇列的末端。

**(a) 以甘特圖顯示流程的安排順序。**
**(b) 每個流程的周轉時間是多少/等待時間是多少？**

## 5.22

考慮一個執行十個 I/O 綁定任務和一個 CPU 綁定任務的系統。
- 假設 I/O 綁定任務每計算一毫秒 CPU 就發出一次 I/O 操作，每次 I/O 操作需要 10 毫秒才能完成。
- 也假設上下文切換開銷為 0.1 毫秒，且所有進程都是長期運行任務。

**描述循環調度程式在下列情況下的 CPU 使用率：
(a) 時間量子為 1 毫秒**
$\frac{1 \text{ ms} \times 10 \text{ task}}{11 \text{ ms}} = \frac{10 \text{ ms}}{11 \text{ ms}} \approx 0.91 \text{ or } 91%$
**(b) 時間量子為 10 毫秒**
$\frac{10 \text{ ms（計算時間）}}{10 \text{ ms}} = 1 \text{ or} 100\%$

## 5.25

**解釋下列調度演算法在多大程度上有利於短進程的差異：(a) FCFS (b) RR \(c) 多層回饋佇列**
> **a 先來先服務（FCFS）**：這種排程算法不太偏向於短進程，因為它按照進程到達的順序進行調度。如果有長進程在短進程之前到達，那麼短進程需要等待長進程執行完畢才能被執行，這可能導致短進程的等待時間變長。
**b 輪轉（RR）**：這種排程算法傾向於短進程，因為它使用固定的時間片來輪流執行進程。當一個時間片用完時，如果進程還沒有執行完，它會被放回隊列的末尾，而短進程通常可以在一個時間片內完成執行，因此有更多的機會被執行
**c 多級反饋隊列**：多級反饋隊列排程算法也傾向於短進程，因為它將進程按照優先級分成多個隊列，並且對於短進程使用較短的時間片，對於長進程使用較長的時間片。這意味著短進程有更高的機會被執行，因為它們會在較短的時間內完成，並且會經常被提升到較高優先級的隊列中。

## 6.7

圖 6.15 的偽代碼說明了基於陣列的堆疊的基本 push() 和 pop() 操作。 假設該演算法可用於並發環境，請回答下列問題：

**(a) 哪些數據存在競賽條件？**
> push跟POP都會影響top數據會在過程中被修改，而導致is_empty有時候調用會有競爭

**(b) 如何解決競賽條件？**
> 在所有修改操作之前加上互斥鎖（mutex），以避免對堆疊頂部（top）的競爭條件。

## 6.15

**如果同步原語要在使用者層級程式中使用，請解釋為什麼在單處理器系統中不適合透過停用中斷來實現同步原語。**
> 如果要在用戶級程序中使用同步原语，通過禁用中斷來實現同步原语在單處理器系統中是不合適的。如果一個用戶級程序被賦予禁用中斷的能力，那麼它可以禁用計時器中斷並阻止上下文切換發生，從而允許它使用處理器而不讓其他進程執行。
# HW3
## 7.8
The Linux kernel has a policy that a process cannot hold a spinlock while attempting
to acquire a semaphore. Explain why this policy is in place.
## 答案
你不能在獲取信號量的同時持有自旋鎖，因為在等待信號量時可能需要休眠，而在持有
自旋鎖時是不能休眠的。
## 8.27
Consider the following snapshot of a system
留言
建議修訂

Use the banker’s algorithm, determine whether or not each of the following states is unsafe. If the state is safe, illustrate the order in which the processes may complete. Otherwise, illustrate why the state is unsafe.

Need = Max - Allocation

A	B	C	D
P0	3	1	1	4
P1	2	3	1	2
P2	2	4	1	1
P3	1	4	2	2
P4	2	1	1	1

(a) Available=(2,2,2,3)

Need(P0) > Available : 無法分配
Need(P1) > Available : 無法分配
Need(P2) > Available : 無法分配
Need(P3) > Available : 無法分配
Need(P4) <= Available : Available += Allocation(P4) 目前 Available 為 (3,2,2,4)
Need(P0) <= Available : Available += Allocation(P0) 目前 Available 為 (4,4,2,6)
Need(P1) <= Available : Available += Allocation(P1) 目前 Available 為 (4,5,3,8)
Need(P2) <= Available : Available += Allocation(P2) 目前 Available 為 (5,7,7,8)
Need(P3) <= Available : Available += Allocation(P3) 目前 Available 為 (6,9,7,9)
Safe Sequence: P4,P0,P1,P2,P3

(b) Available=(4,4,1,1)

Need(P0) > Available : 無法分配
Need(P1) > Available : 無法分配
Need(P2) <= Available : Available += Allocation(P2) 目前 Available 為 (5,6,5,1)
Need(P3) > Available : 無法分配
Need(P4) <= Available : Available += Allocation(P4) 目前 Available 為 (6,6,5,2)
Need(P0) > Available : 無法分配
Need(P1) <= Available : Available += Allocation(P1) 目前 Available 為 (6,7,6,4)
Need(P3) <= Available : Available += Allocation(P3) 目前 Available 為 (7,9,6,5)
Need(P0) <= Available : Available += Allocation(P0) 目前 Available 為 (8,11,6,7)
Safe Sequence: P2,P4,P1,P3,P0
## 9.24
Consider a computer system with a 32-bit logical address and 8-KB page size. The
system supports up to 1 GB of physical memory. How many entries are there in each
of the following?
(a) A conventional, single-level page table
(b) An inverted page table
## 答案
Logical address size: 32 bits
Page size: 8 KB (8 * 1024 bytes)
Physical memory size: 1 GB (1 * 1024 * 1024 KB)
First, let's calculate the number of pages and frames:
Number of pages = Physical memory size / Page size
Number of frames = Physical memory size / Page size
a. Conventional, single-level page table:
In a conventional page table, each page entry corresponds to a page in memory.
Number of entries = Number of pages = Physical memory size / Page size
Number of entries = (1 * 1024 * 1024 KB) / (8 * 1024 bytes)
Number of entries = 128, meaning there are 128 entries in the conventional, singlelevel page table.
b. Inverted page table:
In an inverted page table, each entry corresponds to a frame in memory.
Number of entries = Number of frames = Physical memory size / Page size
Number of entries = (1 * 1024 * 1024 KB) / (8 * 1024 bytes)
Number of entries = 128, meaning there are also 128 entries in the inverted page
table
# Hw4
## 10.21
Assume that we have a demand-paged memory.
The page table is held in registers.
It takes 8 milliseconds to service a page fault if an empty frame is available or if the replaced page is not modified and 20 milliseconds if the replaced page is modified.
Memory-access time is 100 nanoseconds.
Assume that the page to be replaced is modified 70 percent of the time.
What is the maximum acceptable page-fault rate for an effective access time of no more than 200 nanoseconds?
### 解答
EAT(Effective Access Time): 有效存取時間 = 200納秒
MAT(Memory Access Time): 記憶體存取時間 = 100納秒
$PF_{modified}$: 替換頁面被修改時的頁面錯誤處理時間 = 20毫秒 = 20,000,000納秒
$PF_{unmodified}$: 替換頁面未被修改時的頁面錯誤處理時間 = 8毫秒 = 8,000,000納秒
P: 替換頁面被修改的概率 = 0.70
## 10.24
> Apply the (1) FIFO (2) LRU (3) Optimal (OPT) replacement algorithms for the following page reference string:
3, 1, 4, 2, 5, 4, 1, 3, 5, 2, 0, 1, 1, 0, 2, 3, 4, 5, 0, 1.
Indicate the number of page faults for each algorithm assuming demand paging with three frames.
### FIFO
Fault count: 15
| Page | Frames | Fault |
|------|----------|-------|
| 3 | 3, X, X | V |
| 1 | 3, 1, X | V |
| 4 | 3, 1, 4 | V |
| 2 | 2, 1, 4 | |
| 5 | 2, 5, 4 | V |
| 4 | 2, 5, 4 | |
| 1 | 3, 5, 1 | V |
| 3 | 3, 5, 1 | |
| 5 | 3, 5, 1 | |
| 2 | 3, 2, 1 | V |
| 0 | 3, 2, 0 | V |
| 1 | 1, 2, 0 | V |
| 1 | 1, 2, 0 | |
| 0 | 1, 2, 0 | |
| 2 | 1, 2, 0 | |
| 3 | 3, 2, 0 | V |
| 4 | 3, 4, 0 | V |
| 5 | 3, 4, 5 | |
| 0 | 0, 4, 5 | V |
| 1 | 0, 1, 5 | V |

### LRU
Fault count: 15
| Page | Frames | Fault |
|------|----------|-------|
| 3 | 3, X, X | V |
| 1 | 3, 1, X | V |
| 4 | 3, 1, 4 | V |
| 2 | 2, 1, 4 | V |
| 5 | 2, 5, 4 | V |
| 4 | 2, 5, 4 | |
| 1 | 2, 5, 1 | V |
| 3 | 3, 5, 1 | V |
| 5 | 3, 5, 1 | |
| 2 | 3, 2, 1 | V |
| 0 | 3, 2, 0 | V |
| 1 | 1, 2, 0 | V |
| 1 | 1, 2, 0 | |
| 0 | 1, 2, 0 | |
| 2 | 1, 2, 0 | |
| 3 | 1, 2, 3 | V |
| 4 | 1, 4, 3 | V |
| 5 | 5, 4, 3 | V |
| 0 | 5, 4, 0 | V |
| 1 | 1, 4, 0 | V |

### Optimal
Fault count: 11
| Page | Frames | Fault |
|------|----------|-------|
| 3 | 3, X, X | V |
| 1 | 3, 1, X | V |
| 4 | 3, 1, 4 | V |
| 2 | 2, 1, 4 | V |
| 5 | 5, 1, 4 | V |
| 4 | 5, 1, 4 | |
| 1 | 5, 1, 4 | V |
| 3 | 5, 1, 3 | V |
| 5 | 5, 1, 3 | |
| 2 | 2, 1, 3 | V |
| 0 | 2, 1, 0 | V |
| 1 | 2, 1, 0 | V |
| 1 | 2, 1, 0 | |
| 0 | 2, 1, 0 | |
| 2 | 2, 1, 0 | |
| 3 | 3, 1, 0 | V |
| 4 | 4, 1, 0 | V |
| 5 | 5, 1, 0 | V |
| 0 | 5, 1, 0 | |
| 1 | 5, 1, 0 | |

## 10.37: Thrashing 的原因、檢測方法及解決方案
### 問題:
Thrashing 的原因是什麼？
系統如何檢測 thrashing？
一旦檢測到 thrashing，系統可以做什麼來消除這個問題？
1. Thrashing 的原因
Thrashing 是指系統在過度交換頁面而不是執行有意義的工作時發生的現象。其原因主要有以下幾點：

記憶體不足: 當可用物理記憶體無法容納正在運行的進程所需的所有頁面時，系統會頻繁地發生頁面錯誤，導致頻繁的頁面交換。
進程的工作集大小: 進程的工作集（工作集中頻繁使用的頁面集合）超過了可用的物理記憶體。
高度多工: 過多的進程同時運行，導致每個進程可用的記憶體不足。
2. 系統如何檢測 thrashing
系統可以通過監測頁面錯誤率來檢測 thrashing：

高頁面錯誤率: 如果系統檢測到頁面錯誤率非常高，而且系統的 CPU 使用率很低（因為大部分時間花在頁面交換上而不是執行用戶程序），這可能表明系統正在 thrashing。
工作集模型: 系統可以使用工作集模型來監控每個進程的工作集大小。如果總的工作集大小超過了可用物理記憶體，則系統可能會進入 thrashing 狀態。
3. 檢測到 thrashing 後系統的應對措施
一旦系統檢測到 thrashing，可以採取以下措施來消除這個問題：

減少多工進程數量: 暫停或終止一些進程以減少記憶體需求。
增加物理記憶體: 增加系統的物理記憶體，以容納所有進程的工作集。
調整工作集大小: 通過動態調整進程的工作集大小來控制記憶體的分配。
分配更多的記憶體資源: 給 thrashing 的進程分配更多的記憶體資源，以減少頁面錯誤的發生。
### 結論
原因: Thrashing 是由於記憶體不足、工作集過大或過多進程同時運行引起的。
檢測: 系統可以通過監測頁面錯誤率和工作集大小來檢測 thrashing。
解決: 一旦檢測到 thrashing，可以通過減少多工進程、增加物理記憶體或調整工作集大小來解決問題。
## 11.13
## 11.20 RAID 5 中的區塊存取
(a) 寫入一個數據區塊
在 RAID 5 中，每次寫操作涉及以下步驟：

讀取舊的數據區塊。
讀取舊的奇偶校驗區塊。
寫入新的數據區塊。
寫入新的奇偶校驗區塊。
這個過程是必要的，因為需要更新奇偶校驗以反映數據的變化。

對於單個區塊的寫入：

讀取舊的數據區塊：1 個區塊
讀取舊的奇偶校驗區塊：1 個區塊
寫入新的數據區塊：1 個區塊
寫入新的奇偶校驗區塊：1 個區塊
總共存取的區塊數：1（舊數據） + 1（舊奇偶校驗） + 1（新數據） + 1（新奇偶校驗） = 4 個區塊

(b) 寫入七個連續的數據區塊
寫入多個連續的區塊需要考慮奇偶校驗如何分佈在磁碟上。為簡單起見，我們假設這七個區塊跨越多個奇偶校驗條帶。

對於每個區塊寫入：

讀取舊的數據區塊：7 個區塊
讀取舊的奇偶校驗區塊（每個條帶一個，但假設七個區塊跨越兩個條帶）：2 個區塊
寫入新的數據區塊：7 個區塊
寫入新的奇偶校驗區塊：2 個區塊
總共存取的區塊數：7（舊數據） + 2（舊奇偶校驗） + 7（新數據） + 2（新奇偶校驗） = 18 個區塊
## 11.21：RAID 5 與 RAID 1 的吞吐量比較
(a) 單個區塊的讀取操作
RAID 5：

每個單個區塊的讀取操作可以通過訪問包含所請求區塊的磁碟來滿足。無需讀取奇偶校驗區塊。
吞吐量相對較高，因為每次讀取只涉及單個磁碟的訪問。
RAID 1：

每個單個區塊的讀取操作也可以通過訪問包含所請求區塊的其中一個鏡像磁碟來滿足。這允許負載均衡。
由於可以將讀取負載分佈到多個磁碟上，吞吐量可以高於 RAID 5。
比較：
RAID 1 在單個區塊的讀取操作中通常比 RAID 5 具有更高的吞吐量，因為可以從任意一個鏡像磁碟讀取數據。

(b) 多個連續區塊的讀取操作
RAID 5：

多個連續區塊的讀取操作可以在多個磁碟上並行進行，因為數據是分條的。
吞吐量因並行訪問而提高，奇偶校驗數據不涉及讀取操作，使過程高效。
RAID 1：

多個連續區塊的讀取操作也可以分佈在鏡像磁碟上。但是，每個區塊被讀取兩次（每個鏡像各一次），這對於連續讀取來說並不一定比 RAID 5 有吞吐量優勢。
## 14.15：假設一個使用inode來表示文件的文件系統。磁碟區塊大小為8KB，一個磁碟區塊指針需要4個字節。這個文件系統有12個直接磁碟區塊，以及單重、雙重和三重間接磁碟區塊。可以存儲在這個文件系統中的文件的最大大小是多少？
14.14 答案：
(a) 邏輯地址到物理地址的映射
連續分配：

邏輯區塊號 + 基地址 = 物理地址
文件在磁碟上連續存儲。邏輯區塊到物理區塊的映射是一個簡單的加法操作：物理區塊地址 = 基地址 + 邏輯區塊號。
鏈接分配：

邏輯區塊號 = 物理區塊號
文件存儲為鏈表結構。每個區塊包含下一個區塊的指針。要訪問某個邏輯區塊，必須從文件的起始區塊開始，按照指針鏈讀取直到達到所需的邏輯區塊。
索引分配：

邏輯區塊號在索引表中找到對應的物理地址。
文件使用索引區塊來存儲所有數據區塊的地址。索引區塊包含文件所有數據區塊的物理地址。查找邏輯區塊只需查閱索引區塊。
(b) 從邏輯區塊10訪問邏輯區塊4需要讀取的物理區塊數：
連續分配：

直接訪問邏輯區塊4的物理地址。
所需讀取的物理區塊數：1（直接讀取目標區塊）。
鏈接分配：

必須從起始區塊開始，按照指針鏈讀取直到達到邏輯區塊4。
所需讀取的物理區塊數：5（10、9、8、7、6、5、4，每一個都需要讀取）。
索引分配：

直接從索引區塊找到邏輯區塊4的物理地址。
所需讀取的物理區塊數：1（查閱索引表，直接讀取目標區塊）
## 14.15
最大文件大小計算：
每個磁碟區塊大小：8KB
指針大小：4字節
直接區塊數量：12
計算過程：

直接區塊：

12個直接區塊 * 8KB = 96KB
單重間接區塊：

一個單重間接區塊可以指向的數據區塊數量 = 8KB / 4字節 = 2048個區塊
單重間接區塊數據容量 = 2048個區塊 * 8KB = 16MB
雙重間接區塊：

一個雙重間接區塊可以指向的單重間接區塊數量 = 2048個
每個單重間接區塊指向2048個數據區塊
雙重間接區塊數據容量 = 2048 * 2048 * 8KB = 32GB
三重間接區塊：

一個三重間接區塊可以指向的雙重間接區塊數量 = 2048個
每個雙重間接區塊指向2048個單重間接區塊
每個單重間接區塊指向2048個數據區塊
三重間接區塊數據容量 = 2048 * 2048 * 2048 * 8KB = 64TB
總最大文件大小：

12個直接區塊 + 單重間接區塊 + 雙重間接區塊 + 三重間接區塊
= 96KB + 16MB + 32GB + 64TB
# Extra
## DeadLock
Please answer the following questions.
(1) What are necessary conditions of Deadlock? (12%, each answer 3%)
(2) How does OS handle Deadlock? (9%, each answer 3%)
(3) How does OS recovery from Deadlock? (6%, each answer 3%)
Necessary conditions [4x] (§7 / 8.6)

Mutual exclusion 在一個時間內，只能有一個 Process 使用資源
Hold & Wait 一個行程正掌握著某些資源，且正在等待其他資源
No preemption 資源只能由 Process 自願放棄，不能被要求放棄/徵收
Circular wait Process P1 在等 P0，P2 在等 P1， …，Pn 在等 Pn-1，但是 P0 也排到隊伍內等 Pn
How OS handle DEADLOCK [3x] (§7 / 8.12)

讓 Deadlock 永不發生
讓 OS 有處理 Deadlock 的能力
裝作什麼都沒發生
如何處理期末考的壓力

讓壓力不要發生
不要修這門課
不要讓自己陷入分數壓力
讓自己有排解壓力的能力
當作沒有段考，繼續快樂過生活
JCxYIS2 days before final exam
How OS recover from DEADLOCK [2x] (§7 / 8.41)

Process Termination 關掉其中一個或所有 Process (看投影片8.41)
Resource Preemption 選一個 victim，把他 rollback 到 safe state (看投影片8.42)
## Banker's Algorithm
4. Consider the following snapshot of a system:

Answer the following questions using the banker’s algorithm:
(1) What is the content of the matrix Need? (3%)
(2) Is the system in a safe state? (3%)
(3) If a request from process P1 arrives for (0,4,2,0), can the request be granted immediately? (3%)
### (1)
### (2)
檢查 P0：
Need(P0) <= Available -> [0, 0, 0, 0] <= [1, 5, 2, 0] -> True
分配資源給 P0，更新 Available：Available += Allocation(P0) -> [1, 5, 2, 0] + [0, 0, 1, 2] -> [1, 5, 3, 2]
更新 Finish：[True, False, False, False, False]
Need(P1) <= Available -> [0, 7, 5, 0] <= [1, 5, 3, 2] -> False
依序檢查，直到卡住，如果全部都是True 即安全 反之亦然
### (3)
首先，我們需要檢查 P1 的請求是否小於等於其需要的資源 (Need) 並且小於等於系統可用的資源 (Available)。
Available=Available−Request(P1)
Allocation(P1)=Allocation(P1)+Request(P1)
Need(P1)=Need(P1)−Request(P1)
然後再做安全性檢查
## External Fragmentation
Please answer the following questions.
(1) Which algorithms (first fit, best fit, worst fit) will suffer from the "external fragmentation"? (6%)
(2) Give two solutions to the external fragmentation problem. (8%)
First Fit：
### (1)
第一適應算法從內存開始尋找第一個足夠大的空閒區塊進行分配。由於可能會留下很多小的、不連續的空閒區塊，容易產生外部碎片。
Best Fit：

最佳適應算法尋找最接近所需大小的最小空閒區塊進行分配。這種方法傾向於留下很多極小的空閒區塊，從而增加了外部碎片化的可能性。
Worst Fit：

最差適應算法尋找最大的空閒區塊進行分配。雖然這樣做可能會減少極小空閒區塊的數量，但仍可能留下大小不一的空閒區塊，導致外部碎片。
### (2)
內存壓縮（Memory Compaction）分頁（Paging）和分段（Segmentation）
## Page Replacement
Consider the following page reference string:
7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0, 1

Assuming demand paging with 3 frames, how many page faults would occur for the following replacement algorithms?
(1) LRU replacement (6%)
(2) FIFO replacement (6%)
### (1) 最少使用踢掉
### (2)