---
# System prepended metadata

title: 作業系統
tags: [' 作業系統', 筆記]

---

---
title: 作業系統
tags: 筆記, 作業系統
---
# Chapter 1 Introduction

## 1-1 What Operating Systems Do 作業系統用途

- 使用者觀點
    - 做為電腦使用者(User) 與電腦硬體(Hardware) 之間的介面，使得User易於使用Hardware，不用考慮資源如何分配。
    - 提供一個讓User Program 易於執行的環境。
- 系統觀點
    - 是一個資源分配者(Resource Allocator) 。
    - 解決資源使用上之衝突，讓資源公平且有效的被利用。
    - 監控User Program的執行，以防止不正常的運作造成對系統的危害

![image](https://hackmd.io/_uploads/ByYGauC3R.png =50%x)
硬體 <-> 作業系統 <-> 應用程式 <-> 使用者

CPU 一次只能跑一個程式


## 1-2 Computer-System Organization 電腦系統組織

裝置控制器( Device controller )
- Device register
- Local Buffer

**interrupt 中斷**

當收到中斷信號，暫停原本程式，

register cache RAM

**輪詢(Polling) I/O**

不斷去polling Device Controller確認I/O動作是否完成。

**DMA**

把I/O的處理交給另一個硬體，讓他直接存取記憶體以便他直接把處理好的結果放在該放的位置

## 1-3 Computer-System Architecture 電腦系統架構

- **單一處理器系統**
- **多處理器系統**
提高處理效能，但是效能不是正比增加
Multiprocessors Multi-core
- **叢集系統**
透過區域網路，共享儲存裝置。
分為
    - **Asymmetric Clustering 非對稱式叢集 :** 
一台機器處於HotStand-byMode(熱待機狀態)，負責監督其它正在執行應用程式的Server
    - **Symmetric Clustering 對稱式叢集 :** 
多部機器同時執行應用程式，也彼此(互相)監督

## 1-4 Operating-System Operations 作業系統運作

作業系統開機後載入，接下來作業系統何時會被執行?
OS is「event-driven」，有事件就會出來處理
1. Interrupt：drivenbyhardware
2. Trap(exception)：drivenbysoftware
    - Error
    - System calls
![image](https://hackmd.io/_uploads/HkMdXYAhR.png)

- 單一程式(Single-programming systems)
![image](https://hackmd.io/_uploads/Hkg6NK020.png)

- 多元程式(Multi-programming systems)
記憶體中存在多組Process同時執行
![image](https://hackmd.io/_uploads/B1IdEtR2C.png)
    - 並行(Concurrent)
        單一時間只有一個Process 在執行，需要輪流
    - 平行(Parallel)
        在單一時間點有很多的Process在執行
        
- 多任務(Time-sharing or multi-tasking systems)
    - 計時器( Timer)
    - 雙模式(Dual-mode Operation)
        - User mode
        - Kernel mode

## 1-5 Resource Management 資源管理

### Process Management
### Memory Management
### File-system Management
### Mass-Storage Management
### Caching

當CPU需要從主記憶體進行load/store數據時，CPU先檢查cache中是否有暫存資料。若有，則直接讀取數據。
![image](https://hackmd.io/_uploads/rkzA1qRnC.png)
越左越快

### I/O Subsystem

## 1-6 Protection and Security 保護與安全

## 1-7 Virtualization 虛擬化

![image](https://hackmd.io/_uploads/BkroZc0h0.png)

# Chapter 2 Operating-System Structures

## 2-1 Operating Systems Services 作業系統用途

![image](https://hackmd.io/_uploads/rJPMnjPpC.png)

## 2-2 User and Operating-System Interface

### 3 種 User Interface

1. 命令解譯器 (Command interpreter , CLI )
    Shell
    CMD
3. 圖形使用者介面 (Graphical User Interface , GUI)
4. 觸控螢幕介面 (Touch Screen )

## 2-3 System Calls

### System Calls

> 一堆由OS提供用來服務 User Applications 的 Functions
如:open ()、write()、read()

![image](https://hackmd.io/_uploads/SyDVCiDaA.png)

- Process Control
- File Management
- Device Management
- System Information Maintenance
- Communication
- Protection

### OS如何知道呼叫哪一個SystemCall?


![image](https://hackmd.io/_uploads/r1OEb2DTR.png =60%x)
![image](https://hackmd.io/_uploads/HkRSzhDp0.png =60%x)

1. 呼叫execve( )
2. int 0x80進入system call
3. 軟體中斷trap 進入kernel mode (1 -> 0)
> Controlled by a mode bit in the register.
(1= user mode ; 0 = Kernel mode)
4. 查詢system call table
5. 找尋對應的trap service routine
6. 執行完execve( ) 後return

![image](https://hackmd.io/_uploads/r1_5X2D6C.png)

### Application Interface 應用程式介面

類似函庫
使用者使用來呼叫System Call的介面
可攜性/移植性(portability)高
當syscall指令被執行時，根據系統呼叫號碼和參數，查找並執行Kernel中對應的open() 系統呼叫處理函數
![image](https://hackmd.io/_uploads/B1jTdhvTR.png =60%x)

### System Call 傳遞參數的3種方式

- Use Registers
    - 優點:速度快
    - 缺點: registers數量有限，參數不能太多
- Use Memory+Registers
    - 參數存在Memoryblock，透過將位址放至Registers
    - 優點:可存參數較多
    - 缺點:速度較慢
- Use stack
    - 優點:可存參數較多
    - 缺點:速度較慢

少量參數：優先使用暫存器來傳遞
大量參數：多餘的參數會壓入堆疊中
大數據區塊或結構體：存儲在記憶體中

## 2-4 Systems Services

>提供一個便利的環境給程式執行使用

## 2-5 Linkers and Loaders

- 鏈結器(Linkers )
    - 把程式物件檔換成可執行檔
- 載入器(Loaders )
    - 將可執行檔載入記憶體
![image](https://hackmd.io/_uploads/Bk861TvpA.png =70%x)
1. compiler 程式代碼（源代碼）轉換成機器碼
2. linker 不同來源的代碼塊“連結”起來，變成一個完整的可執行檔案。
3. loader 將可執行檔案從硬碟或存儲設備載入到記憶體

## 2-6 Why Applications Are Operating-System Specific



## 2-7 Design and Implementation

- Design Goal
    - User goal
    - system goal
- Mechanisms and Policies (**機制** 與 **策略**)
如何不佔空間 -> 採用「Timer」的機制
如何設定每個Process的計時器時間 -> 採用「優先權」的策略
- Implementation
    - 更快、精簡
    - 易於偵錯
    - 移植

## 2-8 Operating-System Structure

- 單一結構(Monolithic Structure )
    - 優點：效能很好，因為程式之間溝通很快
    - 缺點：當邏輯開始龐大複雜，更改功能就變得困難(耦合性高)
    例：MS-DOS、Unix
- 分層方法(Layered approach)
    - OS被切割成不同層
    - Hardware 最底層
    - User Interface最上層
    - 優點：容易除錯，
    - 缺點：處理效能較慢
- 微核心( Microkernels )
    - 將核心功能縮減到最小，其他系統服務則在內核之外的用戶空間運行
    - 優點：
        - 容易擴充，新功能直接加在 User Mode 上
        - 容易移植，因為小
        - 系統更安全。
    - 缺點：
        - Performance 不好!
- 模組( Modules )
    - 目前設計作業系統最好的方式
    - 核心模組可動態載入（需要再放進來）
    - 優點：
        - 具有分層概念，但不受一層只能呼叫一層限制，更有彈性
        - 運作更有效率，無須像微核心要 message 溝通。
- 混和系統( Hybrid systems )
    - 現行OS設計會結合不同結構來設計
        - Linux–大部分為單一結構(monolithic)+模組化( modular )
        - Windows  -大部分為單一結構(monolithic)+微核心( microkernel)+ 模組化( modular )


# Chapter 3 Process Management

## 3-1 Process Concept

- 文本區 Text section:program code(fixed)：可執行程式碼
- 資料區 Data section:globa; variable(fixed)：全域變數
- 堆積區 Heap section:dynamically allocatef memory：記憶體在程式運行時動態分配
- 堆疊區 Stack section:temporary data：呼叫函數時臨時的資料儲存


![image](https://hackmd.io/_uploads/Bki910vpR.png =40%x)
Stack Heap 碰撞，out of memory
![image](https://hackmd.io/_uploads/SyB2HJ-CR.png)
return 值會保留

### Process state

![image](https://hackmd.io/_uploads/BJuLPkW00.png)

new -> ready -> running -> terminated

if interrupt -> ready

if I/O (開檔案，讀檔案) -> waiting
if sleep(100) -> waiting

ready running waiting -> in memory

### Process Control Block (PCB)
![image](https://hackmd.io/_uploads/SynW6J-0C.png =30%x)

儲存行程的資訊

## 3-2 Process Scheduling

ready waiting 排隊

- Process scheduler ( CPU scheduler )
    一段程式碼，負責選哪隻程式要執行
- Degree of multiprogramming
- I/O-bound process
    程式大部分在做I/O，像從硬碟讀寫、網路溝通
- CPU-bound process
    程式大部分在做計算，像挖礦
    
### Scheduling Queues

- Ready queue
    只有1個
- Wait queue
    Wait queue 有多個
    
![image](https://hackmd.io/_uploads/HkkFT1-RC.png =70%x)

![image](https://hackmd.io/_uploads/ryntAJ-CA.png =70%x)

### Swapping

**當記憶體空間不夠時**，OS會把在記憶體中的Process先移到HD，之後再移回到記憶體。

### Context Switch 內容切換

CPU 在多個程式中切換
並行(Concurrent)
把 PCB 保留下來
Save the state <-> Restore the state
![image](https://hackmd.io/_uploads/r18JHg-AC.png =70%x)
Context switch 時 CPU 會有 idle，CPU 閒置

## 3-3 Operations on Processes

### Parent Child 
> 當一個Process_Acreateprocess_B，請問A/B誰先執行?(考慮只有一個CPU)
> [name=老師]

1. 同時執行 -> Concurrently
2. Parent等Child中止再做

行程空間

Unix fork() 可產生 Child process
直接複製 Parent 的內容到新的 Memory
Unix exec() 直接載入一個新的程式

![image](https://hackmd.io/_uploads/ryyA_ebCA.png =80%x)
Child 從 fork 完後執行
用 pid 是多少來判斷是 Parant or Child

- Zombie Process - Parent Process 還沒執行到 Wait() , Child Process 已經執行完了
- Orphan Process - Parent Process沒有呼叫 Wait() 就結束了


Parent wait() Child

> 如果Parent還沒呼叫Wait()，但Child已經結束？
> [name=老師]

Zombie process

> 如果Parent根本忘了呼叫Wait()就結束？
> [name=老師]

此時的Child稱為孤兒 (orphanProcess)。

## 3-4 Interprocess Communication
執行 Process 兩大類

- 獨立行程(Independent process )
該Process無法影響其它Process的執行，同時它也不受其他Process影響
- 合作行程( cooperating process )
該Process能夠影響其它Process，或是受其它Process影響

2 Common IPC Mechanisms
- 共享記憶體(Shared memory )
程式間可以共同讀寫同一塊記憶體區域，共享資料，可能有==競爭情況==
![image](https://hackmd.io/_uploads/BJQj3lWCR.png =30%x)
讀寫比較快

- 訊息傳遞(message passing )
透過OS維護的訊息佇列讓程式共享資訊。
![image](https://hackmd.io/_uploads/B1an2gbCR.png  =30%x)
必較不會有衝突

**共享記憶體 會遇到 Race condition 競爭情況**

- 因為執行順序不確定，取決於最後執行的 process
- 不保證程式執行過程中，不會被任意中斷

## 3-5 IPC in Shared-Memory Systems



## 3-6 IPC in Message-Passing Systems

### 兩種操作
send
recieve
 
### 建立通訊鍊

**direct communication** 
知道對方 process 名稱或 ID
網路 IP 或 port

**indirect communication**
不知道對方名稱，透過中介傳送

### 交換機制

**同步 (synchronous, blocking)**
等不到對方，waiting
**非同步 (asynchronous, nonblocking)**
一直去問

### message queue

**零容量(zero capacity )**
同步，傳送者必須等待到使用者把資料拿走
**有限容量(bounded capacity )**
非同步，有空間傳送者就可以送，不然就須等待
**無限容量(unbounded capacity )**
非同步，佇列無限長度，傳送者不會有等待狀況發生

![image](https://hackmd.io/_uploads/rkRyVwXkkl.png =200x)
共 8 個 processes

## Summary

:::spoiler 問答
- 正在執行的Program 叫做?
    - Process
- Process 在記憶體會配置成哪4個區域? 
    - Text section
    - Data section
    - Stack section
    - Heap section
- Process 有哪5種狀態?
    - New
    - Running
    - Waiting
    - Ready
    - Terminated
- OS 用何種資料結構做 Process 紀錄?
    - Process Control Block (PCB)
- OS 從一個 process 切換到另一個 Process 會做?
    - Context Switch
- Unix 和Windows 分別用何函式建立Process?
    - fork ( )
    - exec ( ) 
- 何謂 Zombie Process 與 orphan Process? 
    - Parent還沒呼叫Wait()，但Child已經結束
    - Parent忘了呼叫Wait()就結束
- 2種常用的行程間通信?
    - 共享記憶體(Shared memory )
    - 訊息傳遞(message passing )
- Race condition?
    - shared memory 共享資料可能遭同時讀寫，可能發生競爭情況(Race condition)
- Message-Passing Systems2種訊息交換機制?
    - direct communication
    - indirect communication
:::

# Chapter 4 Threads & Concurrency

## 4-1 Overview

process 不是基本執行單位，而是 thread

### Program

軟體工程師所寫的程式碼(code)

### Process
- 記憶體4大組成
    - text 
    - data 
    - stack
    - heap

### Thread

- light weight process 輕量化的 process
- process 是 thread 的容器
- 共享 text, data, heap  資源，切換成本少
- Process 有 PCB， Thread 也有 TCB (Thread Control Block)
- ![image](https://hackmd.io/_uploads/SkSmjPQ11g.png =50%x)
> Ｑ：為什麼 stack 沒有？
> A：程式執行過程大小會變，且順序堆疊，因此無法共享

#### Multithread 4 個優點

- **Responsiveness** (應答)
回應快速，一個Thread無法回應，可以有其它Thread處理其它服務
- **Resource Sharing** (資源分享)
同一Process中Thread 共享code、data、heap等，節省記憶體空間
- **Economy** (經濟)
除因為共享code、data記憶體空間外，context switch 比process 快
- **Scalability** (可擴展性)
目前電腦都是多處理器，有多個CPU，因此multi-Thread可以在不同core上同時執行，具擴展性

## 4-2 Multicore Programming

![image](https://hackmd.io/_uploads/S1tJADQJye.png =70%x)
- 並行 Concurrency
- 平行 Parallelism
    - 資料平行
    把相同資料進行切割，分配給不同Thread做同樣處理
    - 任務平行
    把工作進行切割，每個Thread做不一樣的工作
    
**Challenges**

- 一個程式切割成不同任務
- 每一個 Thread 負擔一樣
- 決定與執行資料切割
- 資料可能會有相關性
- 比單一 Thread 程式更複雜

### Types of  Thread

- User Thread
- Kernel Thread

## 4-3 Multithreading Models

1. **Many-to-One**
早期系統
Many User Thread mapping to one Kernel thread
One Thread is blocked, All Threads are Blocked.
OS 會認為只有一個 Process
即使有多 CPU ，也無法做到成平行，
2. **One-to-One**
Windows、Linux
可以做到多核心執行，且沒有Block問題
因都要呼叫system call，會有overhead，佔記憶體空間
3. **Many-to-Many**
M User Threads, N Kernel Threads
M >= N
省記憶體，沒有Block問題
難以實踐

## 4-4 Thread Libraries

- POSIX Phreads
User thread or Kernel thread 提供
- Windows threads
Kernel thread提供
One-to-one
- Java threads
User thread or Kernel thread 提供

## 4-5 Implicit Threading

Multithread 開發遇到同步(Synchronous)與死結(Deadlock)問題

使用Implicit Threading 隱性執行緒

- Fork-Join
    - 可以是顯性或隱性
    - Fork 產生 task，分不同 task 再 join 回來
    - Library 決定產生與管理幾個Threads(依照CPU Core)
![image](https://hackmd.io/_uploads/rkOUpOXJkl.png =60%x)

- OpenMP
    - compiler directives和API 組合
    - 必須在程式碼中定義parallel regions，告訴Compiler哪一段程式碼需要parallel執行
![image](https://hackmd.io/_uploads/SyuzaOQk1g.png =40%x)
- Grand Central Dispatch (GCD)
    - Apple for macOS and iOS operating systems
    - 語法不同 ````^{  ..... }````
- Intel Threading Building Blocks(TBB)


> 做的是差不多，只是語法不同

- Thread pools

:::info 
2 Problems of Multithread 

Time consuming：產生與回收 Thread 需要時間
Out of Resource：消耗系統資源
:::
Solution：**Thread pools**
事先產生 Thread，結束後不 terminate，而是 waiting

## 4-6 Threading Issues

### Semantics of fork() and exec() system calls

Q：請問當某一個Thread呼叫fork( ) 時，OS會複製所有Threads or 單一thread?
A：都可以，Some UNIX systemes have two versions of fork

Q：請問當某一個 Thread 呼叫 exec ( ) 時，會蓋掉所有 Threads or 單一 thread ?
A：會蓋掉所有 Threads (因為Threads共享code section)

### Signal handling 信號處理

**軟體中斷 trap**
1. PCB 暫存
2. 根據中斷向量找尋到對應的中斷程式 ISR (Interrupt Service Routine)
3. 執行 OS 的中斷程式
4. 執行完後，行程回復之前狀態並繼續執行

**2 Kinds of signal handlers**

1. A user-defined signal handler in the user program 
2. A default signal handler in the kernel

出錯時要把 signal 送到哪一個 thread

- Single-thread program → Signals are delivered to the process
- Multi-thread program 有 4 種可能
	- Deliver the signal to **the thread** to which the signal applies (同步信號)
	- Deliver the signal to **every thread** in the process 
	- Deliver the signal to **certain threads** in the process 
	- Assign **a specific thread** to receive all signals for the process

### Thread cancellation

***指在 Thread 執行尚未完成，即終止該 Thread***

1. **非同步取消**
立即終止
可能正與其他資源互動，造成資源釋放不完全
2. **延遲取消**
週期性檢查是否可以終止

## 4-7 Operating System Examples

## Summary

:::spoiler 問答
- cpu的最小執行單位? 
    - Thread
- 同一Process內的Thread 共享那些資源? 
    - text, data, heap
- Concurrency and Parallelism ?
- Multithreading Models 有 3 種，以及優缺點?
    - Many-to-One 
        運作效率好 One Thread is blocked，All Threads are Blocked
    - One-to-One
        可以做到多核心執行，因都要呼叫system call，會有overhead
    - Many-to-Many
        No Blocked problem，不好實作
- 有 2 種方法產生Thread?
    - User thread
    - Kernel thread
- Types of thread Libraries與其支援平台
    - POSIX Phreads
    - Windows threads
    - Java threads
- 何謂Implicit Threading?
    - 產生與管理Thread的工作，交由compiler 和libraries做
- 非同步執行緒(asynchronous threading)與同步執行緒(synchronous threading)
    - Parent 產生child後，Parent繼續執行，不用等待child 執行完成。
    - Parent 產生child後，必須等待child 執行完成，Parent才能繼續執行
- 信號處理( Signal handling )
- Thread cancellation &延遲取消(Deferred cancellation )
    - thread 被立即終止
    - 不斷週期性自我檢查是否可以終止

:::

# Chapter 5 CPU Scheduling

## 5-1 Basic Concepts

### **CPU-I/O Brust Cycle**

CPU-I/O Burst(分割)：
一個 process 不是在使用 CPU 就是在做 I/O
CPU-I/O Burst Cycle：
整個循環

### **CPU-bound and I/O-bound**

不同類型 Process 所需的 CPU Burst 與 I/O Brust 時間分布不同

### **CPU scheduling**

當 running queue 沒有東西，從 ready queue 挑一個 process 來使用 CPU

**4個時機點**

1. running to waiting state (做 I/O)
2. running to ready state (Timer 觸發)
3. ==waiting to ready== (完成 I/O ，且優先權高)
4. Terminates (沒有 process 使用 CPU)

- 不可搶先 ( Nonpreemptive ) Scheduling
Process 自己放棄CPU使用權
- 可搶先 ( Preemptive ) Scheduling
強迫 Process 放棄 CPU 使用權
造成 ==Race Conditions 問題==

**分派器** (Dispatcher )：
負責把CPU資源提供給被選到的Process
**分派延遲** (Dispatch latency)：
停止一個Process 並啟動另一個Process的時間

## 5-2 Scheduling Criteria 排班原則

評定標準
1. **CPU 使用率** ( CPU utilization ) – 讓CPU盡量忙碌
2. **吞吐量** (Throughput ) – 單位時間內可以完成的程序數量
3. **回復時間** ( Turnaround time )— 程式執行完所需時間
4. **等待時間** ( Waiting time ) — 程式在ready區等待CPU的時間
5. **回應時間** ( Response time ) — 要求送出後到第一次收到回應的時間

## 5-3 Scheduling Algorithms

- **先來先做 ( FCFS Scheduling )**
	- 不可搶先演算法
	![image](https://hackmd.io/_uploads/r1s_Njny1e.png =30%x)
	![image](https://hackmd.io/_uploads/H1ooNi2ykl.png)
	**護衛效應**：後面都在等前面的　process 跑完
	
- **最短工作先做 ( Shortest-Job-First (SJF) Scheduling )**
	- 最短 CPU burst 先做
	- 分為兩種方式
		- Nonpreemptive：不可搶
		- Preemptive：後面進來的時間比原本短，搶先做
	- 不好實作
	- 指數平均值，預估下一次的 Burst time
	- 每次都要預估，電腦 loading 大

- **依序循環 ( Round Robin (RR) )**
	- 輪流
	- q (time quantum) 很小，要一直做 Context Switch
	- q (time quantum) 很大，就等於在做 FCFS
	- 最佳設定 80% 的 CPU Burst 比 q 小

- **優先權 ( Priority Scheduling )**
	- 每個 process 給編號
	- 分為 **可搶先** 與 **不可搶**
	- 可能遇到 **飢餓現象**，逐漸提高 process 的優先權(老化)
	- 優先權存 PCB ，當 Process 多，複雜度高
	
- **多層佇列 (Multilevel Queue )**
	- 把一個 Ready queue 依照優先權 priority 分成不同類型 multilevel queue
	![image](https://hackmd.io/_uploads/HJxKZnnJyl.png =70%x)
	- 每個 queue 也有排班邏輯
		- 一個 queue 全部做完才換，可能產生 starving
		- time quantum (分配每個 queue 一段時間)

- **多層回饋佇列( Multilevel Feedback Queue )**
	- 一個 process 可以在不同 queue 間切換 (如：RR、FCFS 切換)
	![image](https://hackmd.io/_uploads/H1zB7nn11x.png =70%x)
	- 優點
		- 需要越多 CPU 資源的 process 的權限越低
		- 需要越多 I/O 資源的 process 的權限越高
		- 若發生某個 process 在低權限 queue 等待太久，可以用 Aging 提高權限。

## 5-4 Thread Scheduling

### 競爭範圍
![image](https://hackmd.io/_uploads/r1v8V3nyJl.png)
CPU 有限，user threads 去搶 kernel threads，kernel threads 搶 CPU

## 5-5 Multi-Processor Scheduling 多處理器的排班問題

### 2種Multi-Processor Scheduling方式
- **非同步多處理器 ( Asymmetric multiprocessing )**
主要一個 CPU 處理器負責所有排班決定
- **同步多處理器 ( Symmetric multiprocessing , SMP )**
每個 CPU 都可以負責安排

### 多核心處理器

遇到的問題：記憶體停滯，浪費時間
Sol:
![image](https://hackmd.io/_uploads/BkZHP2nkJe.png)
硬體在實作，晶片多執行緒

1. 作業系統先決定哪一個Kernel Thread 要在哪一個hardware Thread上 
2. CPU硬體先決定CPU中的hardware Thread哪一個要執行

### 負載平衡 (Load Balancing )

![image](https://hackmd.io/_uploads/rk9RO3nJkl.png =30%x)
程式轉移 ( Process migration )
>原來的Core 的Cache資料無用
>新的Core 的Cache資料要重新寫

**處理器親和性 (Processor Affinity)**
盡量讓同一個 Process 在同一個 Core 上執行 ( 讓Process 對同一個Process產生親和性 )

### 異構多處理器

具有不同時脈與電源管理的處理器

## Summary

:::spoiler 問答
- CPU-I/O Brust Cycle
    - 一個process不是在使用CPU就是在做I/O
- CPU-bound and I/O-bound
    - CPU Burst時間長的很多
    - I/O Burst時間長的很多
- CPU scheduling 的4個時機點
    - running to waiting state
    - running to ready state
    - waiting to ready
    - Terminates
- 不可搶先 ( Nonpreemptive) vs.可搶先 ( Preemptive) Scheduling
    - 不可搶先
        - Process 自己放棄CPU使用權
    - 可搶先
        - 強迫Process 放棄CPU使用權
- Five CPU scheduling criteria
    - CPU 使用率
    - 吞吐量(Throughput)
    - 回復時間( Turnaround time)
    - 等待時間( Waiting time)
    - 回應時間( Response time)
- 6種排班演算法
    - 先來先做(FCFS Scheduling)
    - 最短工作先做( Shortest-Job-First (SJF) Scheduling)
    - 依序循環( Round Robin (RR))
    - 優先權( Priority Scheduling )
    - 多層佇列(Multilevel Queue)
    - 多層回饋佇列(Multilevel Feedback Queue)
- 競爭範圍( contention scope ) 意思
    - Thread會競爭CPU使用權，搶奪發生地點稱為競爭範圍(User space or Kernel Space)
- 2 種 Multi-Processor Scheduling 方式
    - 非同步多處理器
        - 只有一個處理器負責所有排班決定
    - 同步多處理器
        - 每個CPU都可以負責安排
- Multicore Processors 需要哪兩種排班法?
    - 作業系統先決定哪一個Kernel Thread 要在哪一個hardware Thread上
    - CPU硬體先決定CPU中的hardware Thread哪一個要執行
- Load Balancing 與 Processor Affinity 意思
    - 負載平衡(Load Balancing )：讓每個處理器工作效率一致，不要有閒置狀況
    - 盡量讓同一個Process在同一個Core上執行(讓Process 對同一個Process產生親和性)
:::

# Chapter 6 Synchronization Tool

## 6-1 Background

因為會有 Race Condition
***執行順序的不確定性，最終的值取決於最後一個完成執行的Process***

獨立行程(Independent process )
**合作行程( cooperating process )**
![image](https://hackmd.io/_uploads/rJiIzRHl1e.png =70%x)

解決方法：確保同一時間點下，只有一個process可以存取共享記憶體資料

## 6-2 The Critical-Section Problem

要確保同一時間點下，只有一個 process 可以存取共享記憶體資料

- 臨界區區間( Critical section, CS)：會出現問題的程式區塊
- 入口區段( entry section )：說要進去了
- 出口區段( exit section)：說要出來了
- 剩餘區段( remainder section)

必須滿足
- 互斥(Mutual Exclusion )：不能同時在 CS 中執行
- 進行(Progress)：Entry 或 Exit 能參與
- 限制性的等待(Bounded Waiting )：Process 等待時間有限

方法
- Software solutions
- Hardware solutions
- Operation System solutions

## 6-3 Peterson’s Solution

- 解 2 個 Processes 的 Race condition
- 需要在使用「load」與「store」指令過程連續不被打斷
- 需要共享2個變數
    - int turn：讓對方可以進去
    - Boolean flag[2]：告訴對方自己要進去還是出來
![image](https://hackmd.io/_uploads/S19uDCBlJe.png =70%x)

問題
1. 程式容易寫錯
2. 現行 CPU 架構可能不 work( 指令順序重新排序)
3. 只能用在 2 個Process的狀況
4. process會一直等待，浪費 CPU 資源

## 6-4 Hardware Support for Synchronization

透過硬體指令解決

1. 記憶體屏障 (Memory barriers or memory fences):
    一個指令，可以用來強制其前後指令執行必須依照順序，不能對調
    ![image](https://hackmd.io/_uploads/BkAO30Hxyx.png =30%x)

2. 硬體指令 (Hardware instructions):
    - Lock 1 or 0，0 才可以進去
    因為 Lock 也是共享變數，本身也會產生 CS 的問題
    ex.進廁所後，鎖還沒按，就有人又拉門
3. 單元變數 (Atomic variables):
    - Atomic hardware instructions指是由硬體提供的一種特殊指令，這些指令保證在多處理器或多執行緒環境下執行時，不會被中斷或干擾。
        - test_and_set
            ![image](https://hackmd.io/_uploads/SyjVxkIlkx.png =60%x)
        - compare_and_swap
            ![image](https://hackmd.io/_uploads/Ske7-y8gJl.png =60%x)

![image](https://hackmd.io/_uploads/SJF5WJIekx.png =70%x)
一直輪不到 P1 執行，尚未做到Bounded Waiting，需要再改寫

-> 最終版的 Hardware instruction solution，增加一個共享變數 waiting[n]，其他也會知道

離開 CS 後，在開鎖前，先問每一個 P，有沒有想要進去的 (就是看 waiting 值)

有人在 Waiting 的話，直接給他，不用開鎖

![image](https://hackmd.io/_uploads/rJDkIkLxkl.png)
調整後的程式

## 6-5 Mutex Locks

**Hardware Support for Synchronization** 還不是最佳解

Mutex Locks 互斥鎖
使用 2 個 atomic Function
- acquire
- release

![image](https://hackmd.io/_uploads/Hk45qHObJx.png =35%x)

缺點：Busy Waiting 空等，浪費 CPU
自旋鎖(spinlock)：一種mutex lock，持續等待CS被釋放，而不做context switch

## 6-6 Semaphores

可以解決 Busy Waiting 的問題

- 使用1號誌變數(integer)
- 使用2個atomicfunction存取號誌變數
    - wait()
    - signal()

1. 計數號誌(Counting semaphore)
    Semaphore號誌變數值不受限制，你有N個資源，號誌變數值就設定N。
2. 二進制號誌(Binary semaphore)
    號誌變數值不是0就是1，專解CS問題，初始值為1。

可以讓程式一個比另外一個先走
![image](https://hackmd.io/_uploads/BJTkmUO-kg.png =70%x)

但還沒有解決 Busy waiting 的問題，一直做檢查
--> Put the process to waiting state
等到有 Lock 開了再去 ready 排隊
解決 Busy waiting 問題

![image](https://hackmd.io/_uploads/B1S8VLuWkl.png)

Uniprocessor system
OS 先關掉 interrupts


## 6-7 Monitors

### Monitor usages

高階語言解決同步方法—Java 的Monitor物件
Monitor可以確保同一時間點，只有一個Process存取monitor中的程式
裝在類別，直接使用

可能遇到 >100
![image](https://hackmd.io/_uploads/SkXiuLd-Jg.png)
一直輪不到其他程式執行
因此要 Block 讓其不會一直執行


為了避免發生上述狀況，需要加入條件變數(Condition variable)。
- 新增定義2個條件變數，使用condition做宣告。
- 透過wait( )和signal( )來操作condition variable
    - x.wait()
可以讓正在使用 CS 的 process 暫停，允許其他 process 也可以進入  CS，並等待 signal 喚醒
    - x.signal()
可以將正在 CS 中暫停的 process 喚醒繼續執行

> 考慮兩個Process都在monitor的狀況。誰要先做? 

Siganl and wait: B 呼叫 signal 後 wait，直到 A 做完再離開
Signal and Continue: B 呼叫 Signal 後 continue，A 等 B 做完離開 monitor 再做

### Implementation Using Semaphores

Monitor 中需要 Block process 的 3 個時機
1. Process 要進入已經有 process 在使用的 monitor。
2. 當 Process 呼叫 x.wait( ) 時。
3. 當 Process 呼叫 x.signal( )，採取「Signal and wait」時。

### Resuming Processes within a Monito

- FCFS
- priority

## 6-8 Liveness

### 死結(deadlock) 
2 個以上 processes 因為所需資源/事件彼此相互佔住，造成無限等待
two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes

### 優先權倒置(Priority inversion)
![image](https://hackmd.io/_uploads/BJ71Uv_W1e.png)

### 優先權繼承(Priority inheritance)
![image](https://hackmd.io/_uploads/rye8ID_Z1e.png)
把優先權拉高﹐才不會卡到高優先權



## 6-9 Evaluation

# Chapter 7 Synchronization Examples

## 7-1 The bounded-buffer synchronization problem 典型的同步問題

### 有限緩衝需問題
:::info
Q：因為產品線(buffer)容量有限，必須確保生產者不會在產品線(buffer)滿時放入產品(加入
數據)，消費者也不會在產品線(buffer)中空去時取產品(消耗數據)。

:::
解決方式：**同步**與**互斥**
寫資料前先確認有空位(同步)，再確認有沒有人正使用buffer(互斥)

程式改寫

1. Semaphore mutex，initial to 1。
--使用 buffer 過程必須要互斥。

2. Semaphore Full ，initial to 0。
--buffer 滿了，producer 就不能放。

3. Semaphore emptyinitialized to the value n。
--buffer 空了，consumer 就不能取。

![image](https://hackmd.io/_uploads/SJgzXYbM1x.png)

1. 如何知道產品線(buffer)目前狀況 ? 
利用 wait()
2. 產品線(buffer)是共享記憶體，如何防止 RC? 

## 7-2 The readers-writers synchronization problem 讀取寫入問題

Reader 不會造成 RC 
Writer 會

解決方式 
- 多個 Readers 可以同時存取資料，但當下 Writer 不能改寫資料。
- 只有一個 Writer 可以改寫資料，且同時不能有 Readers 讀取資料。

使用OS的semaphore解決方式：需要2個 semaphores
- Semaphore rw_mutex initialized to 1 → 確保只有一個 writer 讀寫 dataset
- Integer read_count initialized to 0 → 計算有多少 readers 在讀取 dataset
- Semaphore mutex initialized to 1 → 確保read_count 值可以同步(No race condition)

![image](https://hackmd.io/_uploads/HkwxSFZGJx.png =50%x ) ![image](https://hackmd.io/_uploads/H1ngLYbGkx.png =40%x)

1. 第一個人進來的 Reader，負責通知 Writer 不能進來。
2. 最後一個離開的 Reader ，負責通知 Writer 可以進來。
3. 所有的 Reader 存取 read_count 時，都要互斥。


## 7-3 The dining-philosophers synchronization problem

Problem：會遇到 Deadlock 死結

1. Semaphore Solution
2. monitor Solution

解決方式：
每一個人只能在旁邊兩隻叉子都可以取得的狀態下，才能去拿叉子

1. 使用資料結構記錄每一個人 3 種狀態。
enum{ thinking, hungry , eating } state [ i ] 。
-- 初始值都是thinking-- 只有兩邊都不是eating，中間才可以改eating。
2. 宣告等待狀態
Condition self [ 5 ] {0 , 1 , 2 , 3 , 4}： 。
-- 如果 hungry，但是拿不到叉子，必須先 wait。

![image](https://hackmd.io/_uploads/S1dZg9-Gyl.png =50%x)
![image](https://hackmd.io/_uploads/S1Mfg5-z1l.png =50%x)

---

![image](https://hackmd.io/_uploads/Bylig5ZMkx.png =50%x)
請改用Mutex Lock 取代 Semaphore
acquire() 與 release() 取代 wait(multix) signal(multix)

Problem：排除 Deadlock 但可能遇到 starvation

1. 優先權
2. 給時間

# Chapter 8 Deadlock

2個以上processes 因為所需資源/事件彼此相互佔住，造成無限等待

## 8-1 System Model

1. Request：提出對某個resource的要求
2. Use：使用resource
3. Release：釋放對某個resource的使用

## 8-2 Deadlock in Multithread applications



## 8-3 Deadlock Characterization

### Deadlock成立的 4 個特徵(需同時出現) 
- 互斥 ( Mutual exclusion )
一次只有一個Thread/process 可以使用資源。
- 占用與等候 ( Hold and wait )
必定有一個Thread/process 已經占用一個資源，且它同時等待另一個已被占用的資源。
- 不可搶先 ( No preemption )
被占用的資源不能被搶奪使用，必須等到使用該資源的 thread/process 釋放。
- 循環式等候 ( Circular wait )
存在一個等候執行的 thread/process 集合:{ T0、T1 、T2、...、Tn }。
集合元素存在 T0 → T1 → T2 → Tn → T0 關係。

![image](https://hackmd.io/_uploads/HJ7XS9bM1l.png)
- 沒有發生 Circular wait，就一定沒有 Deadlock。
- 如果有Circular wait發生
    - 如果每個資源只有一個instance，**一定會** 發生deadlock。
    - 如果每個資源有 **一個以上** instance，**可能會** 發生deadlock。

## 8-4 Methods for Handling Deadlocks

處理 deadlock 的 3 個方法
1. 不要讓 deadlock 產生
預防 ( deadlock prevention )
避免 ( deadlock avoidance )
2. 等 deadlock 產生後去處理
要先偵測 deadlock 後，然後將 deadlock 狀況復原
3. 忽略 deadlock 發生
既然發生機率很低，處理的資源消耗更大，乾脆忽視
現行如 windows 和 Linux 等 OS 採用

## 8-5 Deadlock Prevention

Prevention：就是讓以下條件「至少」其中一個不要成立!

- 互斥 ( Mutual exclusion )
    - 無法做到!! 因為這是為了解決RC，除非程式都不共享記憶體變數!
    
- 占用與等候 ( Hold and wait )
    1. Hold and no wait ：
    要求程式在開始執行程式前，先取得所有資源! (低資源使用率)
    2. Wait and no Hold ：
    如果程式必須等待資源，那就必須先放下手上所有資源! (starvation)

- 不可搶先 ( No preemption )
    不是所有資源都可以被搶先
- 循環式等候 ( Circular wait )
    - 先將每一個資源都編號
        1. 每一個Process要資源時，編號必須漸增。
        2. 當Process要資源時，如果已經取得的資源編號大於要求的資源編號，必須先將其全部釋放

    利用「資源編號」預防「循環式等候 ( Circular wait )」方式，仍無法適應所有狀況! 
    
## 8-6 Deadlock Avoidance

**Avoidance**：如果我能知道後面的資源分配狀況會導致deadlock，則不允許資源分配出去。

1. 先掌握 priori information：
    知道每個Process/Threads所需資源的數量與形式 
2. 建立deadlock-avoidance algorithm：
    動態檢查資源分配的狀況，確保不會發生 Circular wait 

- Safe State
    且能避免deadlock
    系統一定存在一個安全序列(程式執行順序)
- Unsafe State
    可能造成Deadlock 
    
確保系統處於 safe state

### Resource-Allocation Graph Scheme
1. 適用於 resources 只有 1 個 instance。
2. P 執行前必須告知系統需要用到什麼 resources。
3. 繪製申請邊 ( Claim edge )：
    「Ti → Rj」：indicated that process Ti may request resource Rj；represented by a dashed line

### the Banker's Algorithm
1. 適用於 resources 有多個 instance。
2. P 執行前必須告知系統，最大需要使用的 resources 資訊。
3. P 執行後不一定馬上可以要得到 resources ，要不到就得等。

## 8-7 Deadlock Detection 

Singleinstance of a resource type
- Use wait-forgraph
Multipleinstances of a resource type
- Use the Banker's Algorithm

中找到一個Cycle，代表有deadlock存在
系統必須不斷週期性的更新wait-for圖，並檢查是否有Cycle存在

3 種使用 Detection-Algorithm 的時機：
1. 當有Process要不到資源時。
--會相當浪費資源
2. 固定一段期間執行。
--例如每小時執行一次
3. CPU使用率降低時。
--例如CPU使用率低於40%

## 8-8 Recovery from Deadlock

2 methods of recovery from the deadlock
1. Process/Threads termination
    - Abort all deadlocked threads
        - 馬上解決deadlock，但是代價很大
    - Abort one process at a time until the deadlock cycle is eliminated
        - 誰要先 kill 掉
            - 優先權
            - 執行時間
            - 資源使用量
2. Resources preemption 
    - Selecting a victim
        - 考慮它執行的時間
    - Rollback
        - kill 掉後要讓他們回到原本的狀態
    - Starvation
        - 可能一直殺同一個 process


# Chapter 9 Memory Management

## 9-1 Background

Main memory 和registers 是CPU唯一能夠直接存取的儲存體

### 基本硬體(Basic Hardware)

#### Protection of memory

每一個process必須只能存取合法的空間。
- User process不能存取OS的空間
- User A process不能存取User B process 的空間

由硬體—CPU負責檢查。
1. 基底暫存器(base register )
    - 存放最小合法實體記憶體位置
2. 限制暫存器(limit register )
    - 範圍的大小

![image](https://hackmd.io/_uploads/Bk9PZTqzyx.png)

### 位址鏈結(Address Binding)

*將原始程式中的邏輯位址（Logical Address，例如變數名稱或指令位置）與實際的記憶體位址（Physical Address）連結的過程，就是Address Binding*


- Compile time
    - 在編譯時間中，已經知道程式在記憶體位址為何，就會產生絕對碼(absolute code )
    - 決定的位址內有其它的程式在執行，或之後要變更程式執行的起始位址，則須 recompile
- Load time
    - 無法確定記憶體位置，就會產生可重定位程式碼(relocatable code)
- Execution time
    - 由OS 動態決定，程式執行期間才決定程式執行的起始位址
    - 額外硬體支援
    
- Compile: 將原始程式轉換成object file。
    - 編譯器生成相對位址（Relative Address），例如變數result 存放於main 函式的第8 個位址單元。(main + 8)
- Linker: 將多個object files整合成一個執行檔。
    - 計算最終相對位址→生成的程式仍然是可重定位的（Relocatable），最終位址由Loader決定
- Loader: 將執行檔載入記憶體等待執行。
    - Loader 將a.exe 載入到記憶體，分配一個基址（Base Address）
    - 根據基址，將所有邏輯位址轉換為實體位址

### 邏輯位址空間與實體位址空間(Logical Versus Physical Address Space)

- Logical address：generated by the CPU; also referred to as virtual address
- Physical address：address seen by the memory unit
- Logical address space：theset of all logical addresses generated by a program
- Physical address space：the set of all physical addresses generated by a program

### 動態載入(Dynamic Loading)

- 需要的程式碼，真正要執行時，再載入到記憶體
- 尚未用到的程式碼，以relocatable格式先放在硬碟
- 讓記憶體空間可以更有效率地使用

![image](https://hackmd.io/_uploads/BkTkY6cG1l.png =50%x)


### 動態鏈結和共用程式庫 (Dynamic Linking and Shared Library)

靜態鏈結(static linking)
- 程式載入記憶體前，將主程式以及所有需要用到的 library 都鏈結在一起
- 浪費記憶體空間

![image](https://hackmd.io/_uploads/BkEOYa9zke.png)

動態鏈結(dynamic linking)
- 需要的程式碼，真正要執行時，再進行鏈結的動作

![image](https://hackmd.io/_uploads/r1WMqaqz1l.png)


## 9-2 Contiguous Memory Allocation

記憶體區分2區塊，for user process and OS
![image](https://hackmd.io/_uploads/S1i_op9fJg.png)

### 記憶體保護(Memory Protection)

- 每個 program 都有自己的記憶體空間且互相獨立
- 需要 Hardware-support -> MMU (Memory-Management Unit)

- 使用到可重定位暫存器(Relocation register) 以及Limit register

Logical address 必須小於 Limit register value
Logical address + relocation = Physical address

![image](https://hackmd.io/_uploads/ByDdhTcz1e.png)


### 記憶體配置(Memory Allocation)

記憶體會被區分為固定大小的分割
OS會分配一個足夠空間的free Partition(hole)給載入記憶體的程式

![image](https://hackmd.io/_uploads/SyH3aTcMJl.png)

- ==First-fit==：Allocate the first hole that is big enough (存取速度最快)
- ==Best-fit==：Allocate the smallest hole that is big enough；must search entire list，unless ordered bysize  Produces the smallest leftover hole
- Worst-fit：Allocate the largest hole；must also search entire list  Produces the largest leftover hole

### 斷裂(Fragmentation)

#### 外部斷裂( external Fragmentation )

總記憶體空間足夠，但卻沒有合適的 Partitions 供 Program 使用，稱為外部斷裂(External fragmentation)

- ==聚集==( compaction)：將零散的記憶體空間聚集起來。 (需要花比較多資源)
- ==不分配連續的記憶體空間==( non-contiguous memory space)：讓Program 可以分散在記憶體中。


#### 內部斷裂( internal Fragmentation )

 記憶體切成固定大小Partitions，並以整塊(block)形式提供Program使用
 ![image](https://hackmd.io/_uploads/Hy0rzWNXkl.png)
沒用到的部分為 **內部斷裂**

## 9-3 Paging

### 基本方法 (Basic Method)

以不連續的記憶體方式載入
由 OS 跟硬體去實作

- OS 負責
    - 將記憶體分割成固定大小區塊，稱為欄(Frame)
    - 程式，將其分割成大小相同區塊，稱為頁(Page)
    - 分頁表(page table)，以紀錄 page 與  frame 的對應

大小由硬體決定，Frame 和 Page 大小一樣大 
 ![image](https://hackmd.io/_uploads/H1Ta-bNQkx.png =70%x)
![image](https://hackmd.io/_uploads/SkeeDNWEXyg.png)

OS會記錄一個「Free-frame list」，當程式要載入記憶體時，OS依照Free-frame list，做出page table

仍有 Internal fragment 問題
有空間沒有被使用

### 硬體支援 (Hardware Support)

Page table 放在主記憶體中，紀錄兩種
- 分頁基底暫存器 (Page-table base register, PTBR)--指向目前執行程式的Page table。
- 分頁長度暫存器 (Page-table length register, PTLR)—紀錄Page table 的大小

每個 Process 都有自己的 page table，位置放在自己的 PCB

#### 轉譯旁觀緩衝區 (translation look-aside buffers, TLBs)

小型硬體快取記憶體
解決CPU在進行Paging過程需要2次讀取main memory的問題。
1. 讀取page table
2. 讀取指令位址

![image](https://hackmd.io/_uploads/HJlFiZ4myx.png =70%x)

如果TLBs滿了?
從TLBs中選一個紀錄移除，但硬體繞線固定(wired-down)，不能移除

當Process切換，執行Context switch 時，TLBs 會 Flush，因為可能會讀到其他 Process 的 -> 浪費 CPU 資源
存 PCB 裡面，再換其他 Process 執行

位置空間識別碼 (address-space identifiers, ASIDs )
TLB 中多一欄紀錄是哪一個 Process 的
![image](https://hackmd.io/_uploads/HyJCgfEQJg.png =30%x)

### 保護 (Protection)

#### 保護位元 ( protection bit )：
- Valid：代表此項分頁表資訊，屬於 Process 的合法 Logical address space，被分出去了，。
- Invalid：代表此項分頁表資訊，不屬於 Process 的合法 Logical address space，還沒被分配。
-> 若發生讀取到保護位元為 Invalid，就會觸發 trap


#### 分頁長度暫存器(Page-table length register, PTLR)
紀錄Page table 的大小

###  共用分頁 (Shared Pages)

![image](https://hackmd.io/_uploads/rkSs4f4myl.png)


## 9-4 Structure of the Page Table

- 階層式分頁 ( Hierarchical Page Table)
    - 一頁 page table 太大，就分割成數個小page tables。
    - 數個小 page tables 各自存放，達到non-contiguous。
    - 虛擬位置，然後一個一個階層去找到實際位置
- 雜湊分頁表 ( Hashed Page Table )
    - ![image](https://hackmd.io/_uploads/rkRT_MVX1x.png =70%x)

- 反轉分頁表 ( Inverted Page Table )
    - 將原先page對應frame的方式，變成frame對應page的方式建表儲存。
    - ![image](https://hackmd.io/_uploads/BJwlsiySkx.png =70%x)

    - ![image](https://hackmd.io/_uploads/HkR7yN6X1g.png =70%x)


## 9-5 Swapping

OS可將記憶體中page先移到backing store
![image](https://hackmd.io/_uploads/r10xeN6Xke.png =70%x)

# Chapter 10 Virtual Memory

## 10-1 Background

實現讓Process可以不用一次全部載入實體記憶體中，即可執行的技術。

## 10-2 Demand Paging

需要再載來
用以實現virtual memory的技術
當需要使用，再從硬碟載進來，稱 Page in/Page out
和 Swap 不同，只搬動 Pages
![image](https://hackmd.io/_uploads/ByOrOVamJl.png =70%x)
當遇到 invalid 時，trap 後去載入 Newpage
Process 會有 frame table 記錄所有frame狀態
zero-fill-on-demand 避免獨到舊的資料

**分頁錯誤**( Page-fault )：
程式所需執行的分頁未被載入記憶體中
![image](https://hackmd.io/_uploads/B1py0VpXkl.png =70%x)
![image](https://hackmd.io/_uploads/rym7RVaQkx.png =70%x)

**需求分頁**(demand paging)：
提前載入一些預期將來會用到的頁面

**純需求分頁**(Pure demand paging)：
程式執行時需要再載入

有效存取時間「effective access time」=(1-p) * ma + p * page fault time

上述步驟主要可概分三大階段
1. 處理 page fault
2. 從硬碟讀取程式分頁 (最花時間)
3. 重新啟動程式

## 10-3 Copy-on-Write

:::success
使用fork ( )可以產生Child Process ，會在記憶體也會出現與Parentprocess同樣大小記憶空間。
但若Child process隨即呼叫了exec ( )，代表Child process的記憶體空間將會被另一個Process蓋掉。
:::

Solution：Copy-on-Write
Child 與Parent 先共享記憶體，需要載入新程式碼，再複製寫入。

當Child 與Parentprocess 共享分頁時，可能出現2種情況
1. 當需要修改時，會將共享的分頁會複製另外一頁
2. 當Child 呼叫exec 執行新程式，則使用新的記憶體位址

### 如何實踐Copy-on-write

Copy –on-write bit =1
若是共享的為 1
當需要更改資料，就不能共享，copy 出新的，把 bit 改為 0


## 10-4 Page Replacement

當 free-frame list 沒有空間，需要 replace

### Basic Page Replacement

1.找出一個free frame -> 把victim frame page out (寫回硬碟)Page Replacement
2.update page table
3.page inthe page needed
4.update page tableand restart the instruction

:::warning
過程中會發生2次讀寫硬碟動作，影響效率
:::
solution：使用 modify bit / dirty bit
新增一個 bit，只要有改過內容，才需要重新寫回硬碟，若沒有，就直接複寫

### Demand paging 需解決2個問題

#### 1. 欄的配置演算法
要決定分配多少欄給一個process使用
#### 2. 分頁替換演算法

##### First-In-First-Out (FIFO) Algorithm

![image](https://hackmd.io/_uploads/Hy_karaXyg.png)

##### Optimal algorithm

在 replace 前，把未來最少用或最後用的踢掉
![image](https://hackmd.io/_uploads/Bkg5bZI6mkx.png =90%x)
最理想，但執行上最困難，因為必須先知道未來的狀況

##### LRU algorithm

過去部不會用到，未來可能也不會用到
![image](https://hackmd.io/_uploads/ByDkG86Qyl.png)
最常用的演算法

實踐方法
1. Counter implementation
利用 counter，找到最小的值
![image](https://hackmd.io/_uploads/SJa5MLpQke.png =30%x)
但可能是剛剛才進來，就被拿走

2. Stack implementation
最上面永遠是最新的，當沒有 free-frame 時，把最下面的移掉

##### LRU approximation algorithm
- Additional-reference-bit algorithm (reference bit)
被用過 Reference bit 寫 1，紀錄使用狀態
找到數字最小的 page 進行置換。

- Second-chance algorithm (==FIFO== + reference bit)
先 FIFO，若 Reference bit 為 1 代表最近有用過，先不將其換掉，並爸reference bit 改為 0 
又稱為 Clock 演算法

- Enhanced second-chance algorithm (FIFO + reference bit + ==Modify bit==)
多 Second-chance algorithm Modify bit，優先將 Reference bit 為 0 與 Modify bit 為 0 先替換掉 

##### Countingalgorithm
- LFU(Lease Frequently Used Algorithm)
Replaces page with smallest count
- MFU(Most Frequently Used Algorithm)
Replaces page with largest count
##### Page buffering algorithm
1. 預留free frames ，讓第3步驟先做，加速程式執行
2. 趁硬碟閒置時，先把modify/dirtybit 的 page 先寫回去，並把 dirty bit 改為 0，需要 page out 時，少一次寫硬碟時間

## 10-5 Allocation of Frames 

### Allocation Algorithm

#### Equal Allocation (同等分配)
每個程序獲得完全相等的記憶體數量
- 好實作
- 浪費記憶體空間

#### Proportional Allocation (比例分配)
按照比例分配，但不好實作

### Global vs. Local Allocation

#### Global Allocation
可以選其他 process 的 frame 來做置換
page fault 會被其他 program 影響
目前主要採用的方式

#### Local Allocation
process 只能置換自己的 frame
execution(page in、page out) 時間很多

### implement Global Page-Replacement

#### 回收分頁(Reclaiming Pages)

確保可使用記憶體空間維持在最小閥值
當可用記憶體空間數量小於最小閥值時，OS啟動核心raper(收穫者)，進行記憶體回收。直到可用記憶體閥值達到最小閥值。
![image](https://hackmd.io/_uploads/BkWFZdUE1e.png)

## 10-6 Thrashing
如果 pages 不夠，會一直 page fault，頻繁 I/O，稱為 trashing，OS會更頻繁去切換執行更多程式 -> 造成更低CPU  utility，形成惡性循環
![image](https://hackmd.io/_uploads/Hyn_M_8Eyl.png)

### Locality model (局部區域模式)
![image](https://hackmd.io/_uploads/rJ_E8dUNJe.png)
程式在一段時間內通常會集中訪問某些特定區域的記憶體區域

#### 時間區域性 （Temporal Locality）
如果一個記憶體位置在某個時間點被存取，那麼之後很可能再次被存取
![image](https://hackmd.io/_uploads/SJGGvdU4Jg.png)

#### 空間區域性 （Spatial Locality）
如果一個記憶體位置在某個時間點被存取，那麼它附近記憶體位置很可能之後也會很快被存取
![image](https://hackmd.io/_uploads/ByNNvdIN1g.png)

### 實作的方式

#### Working-Set Model

![image](https://hackmd.io/_uploads/SJliO_I41x.png)
![image](https://hackmd.io/_uploads/SydHYdL4yg.png)
![image](https://hackmd.io/_uploads/Skt8Y_IEJg.png)

##### Keeping Track of the Working Set
interval timer + a reference bit
timer 的時間點做紀錄，知道有誰在 working set
但可能不夠精準，因此可以新增 bit

#### Page-Fault Frequency
![image](https://hackmd.io/_uploads/HJY6idL4Jl.png)
If actual rate too low, process loses frame
If actual rate too high(trashing), process gains frame 

## 10-7 Memory Compression
![image](https://hackmd.io/_uploads/ryN1au84yl.png)
)
不把它 page out 出去，而是壓縮，需要用到時再解壓縮


## 10-8 Allocating Kernel Memory
User program allocated from free frame list

Kernel Often allocated from a free-memory pool
有些 Kernel 記憶體必須是連續的

### Buddy System
給 kernel 2 次方，會得到連續空間，release 後會 merge
![image](https://hackmd.io/_uploads/By6oA_LV1e.png)
但會發生 fragmentation 的問題

### Slab Allocator
==Slab== is one or more physically contiguous pages
==Cache== consists of one or more slabs
![image](https://hackmd.io/_uploads/HJ0yeYUEJx.png)
每個 caches 給特定的資料結構，不會發生斷裂問題


## 10-9 Other Considerations

### Pre-paging

在開始前先載入需要的 Pages

### Page size

Fragmentation -> small page size (比較不會內部斷裂造成浪費)
Page table size -> large page size 
I/O overhead -> large page size (分散在不同 Page 會一直跳來跳去)
Resolution(Locality) -> small page size (不會浪費那麼多空間)
Number of page faults -> large page size (越大程式可以直接載進來)

> [!note]現今電腦方案
> 最花時間的是 I/O，因此現今電腦傾向 large page size

### TLB Reach

讀取記憶體的數量
希望 working set 都可以存在 TLB 中，不用一直讀記憶體得位置

> [!Tip] 解法
Increase TLB page size -> increase fragmentaion
Provide Multiple Page Sizes

### Inverted Page Tables (反轉分業表)

> [!Caution]Problem
> 找不到 logical 記憶體位置，不知到要去哪裡載
> 需要再多一個 page 來記錄實體位置

### Program Structure

```cpp
for( j = 0; j < 128; j++)
    for( i = 0; i < 128; i++)
        data[i,j] = 0;
```
```cpp
for( i = 0; i < 128; i++)
    for( j = 0; j < 128; j++)
        data[i,j] = 0;
```
![image](https://hackmd.io/_uploads/Bysc1nJr1e.png =20%x)

### Data Structure

![image](https://hackmd.io/_uploads/SyqwlhyB1l.png)

被 page out，在錯的記憶體空間，資料被其他 Process 拿走了

> [!Tip]Solution 1
> 透過 OS 去分配，但會兩次 Copy 浪費效能

> [!Tip]Solution 2
> 在做 I/O 的，把它標註起來，但就要多一個空間去存 Mark