# Chapter 1 Introduction

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

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

硬體 <-> 作業系統 <-> 應用程式 <-> 使用者

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

- 單一程式(Single-programming systems)

- 多元程式(Multi-programming systems)
記憶體中存在多組Process同時執行
- 並行(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中是否有暫存資料。若有，則直接讀取數據。
越左越快

### I/O Subsystem

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

## 1-7 Virtualization 虛擬化


# Chapter 2 Operating-System Structures

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


## 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()


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

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


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


### Application Interface 應用程式介面

類似函庫
使用者使用來呼叫System Call的介面
可攜性/移植性(portability)高
當syscall指令被執行時，根據系統呼叫號碼和參數，查找並執行Kernel中對應的open() 系統呼叫處理函數

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

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

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

## 2-4 Systems Services

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

## 2-5 Linkers and Loaders

- 鏈結器(Linkers )
- 把程式物件檔換成可執行檔
- 載入器(Loaders )
- 將可執行檔載入記憶體
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：呼叫函數時臨時的資料儲存

Stack Heap 碰撞，out of memory
return 值會保留

### Process state


new -> ready -> running -> terminated

if interrupt -> ready

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

ready running waiting -> in memory

### Process Control Block (PCB)

儲存行程的資訊

## 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 有多個



### Swapping

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

### Context Switch 內容切換

CPU 在多個程式中切換
並行(Concurrent)
把 PCB 保留下來
Save the state <-> Restore the state
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() 直接載入一個新的程式

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 )
程式間可以共同讀寫同一塊記憶體區域，共享資料，可能有==競爭情況==
讀寫比較快

- 訊息傳遞(message passing )
透過OS維護的訊息佇列讓程式共享資訊。
必較不會有衝突

**共享記憶體 會遇到 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 )**
非同步，佇列無限長度，傳送者不會有等待狀況發生

共 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)
- 
> Ｑ：為什麼 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

- 並行 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)

- OpenMP
- compiler directives和API 組合
- 必須在程式碼中定義parallel regions，告訴Compiler哪一段程式碼需要parallel執行
- 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 )**
- 不可搶先演算法
**護衛效應**：後面都在等前面的　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
- 每個 queue 也有排班邏輯
- 一個 queue 全部做完才換，可能產生 starving
- time quantum (分配每個 queue 一段時間)

- **多層回饋佇列( Multilevel Feedback Queue )**
- 一個 process 可以在不同 queue 間切換 (如：RR、FCFS 切換)
- 優點
- 需要越多 CPU 資源的 process 的權限越低
- 需要越多 I/O 資源的 process 的權限越高
- 若發生某個 process 在低權限 queue 等待太久，可以用 Aging 提高權限。

## 5-4 Thread Scheduling

### 競爭範圍
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:
硬體在實作，晶片多執行緒

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

### 負載平衡 (Load Balancing )

程式轉移 ( 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 )**

解決方法：確保同一時間點下，只有一個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]：告訴對方自己要進去還是出來

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

## 6-4 Hardware Support for Synchronization

透過硬體指令解決

1. 記憶體屏障 (Memory barriers or memory fences):
一個指令，可以用來強制其前後指令執行必須依照順序，不能對調

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

一直輪不到 P1 執行，尚未做到Bounded Waiting，需要再改寫

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

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

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

調整後的程式

## 6-5 Mutex Locks

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

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


缺點：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。

可以讓程式一個比另外一個先走

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


Uniprocessor system
OS 先關掉 interrupts

## 6-7 Monitors

### Monitor usages

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

可能遇到 >100
一直輪不到其他程式執行
因此要 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)

### 優先權繼承(Priority inheritance)
把優先權拉高﹐才不會卡到高優先權

## 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 就不能取。


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)

 

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。


---

請改用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 關係。

- 沒有發生 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 )
- 範圍的大小


### 位址鏈結(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格式先放在硬碟
- 讓記憶體空間可以更有效率地使用


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

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


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


## 9-2 Contiguous Memory Allocation

記憶體區分2區塊，for user process and OS

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

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

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

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


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

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


- ==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使用
沒用到的部分為 **內部斷裂**

## 9-3 Paging

### 基本方法 (Basic Method)

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

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

大小由硬體決定，Frame 和 Page 大小一樣大

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. 讀取指令位址


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

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

位置空間識別碼 (address-space identifiers, ASIDs )
TLB 中多一欄紀錄是哪一個 Process 的

### 保護 (Protection)

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

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

### 共用分頁 (Shared Pages)


## 9-4 Structure of the Page Table

- 階層式分頁 ( Hierarchical Page Table)
- 一頁 page table 太大，就分割成數個小page tables。
- 數個小 page tables 各自存放，達到non-contiguous。
- 虛擬位置，然後一個一個階層去找到實際位置
- 雜湊分頁表 ( Hashed Page Table )
- 

- 反轉分頁表 ( Inverted Page Table )
- 將原先page對應frame的方式，變成frame對應page的方式建表儲存。
- 

- 

## 9-5 Swapping

OS可將記憶體中page先移到backing store

# Chapter 10 Virtual Memory

## 10-1 Background

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

## 10-2 Demand Paging

需要再載來
用以實現virtual memory的技術
當需要使用，再從硬碟載進來，稱 Page in/Page out
和 Swap 不同，只搬動 Pages
當遇到 invalid 時，trap 後去載入 Newpage
Process 會有 frame table 記錄所有frame狀態
zero-fill-on-demand 避免獨到舊的資料

**分頁錯誤**( Page-fault )：
程式所需執行的分頁未被載入記憶體中

**需求分頁**(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


##### Optimal algorithm

在 replace 前，把未來最少用或最後用的踢掉
最理想，但執行上最困難，因為必須先知道未來的狀況

##### LRU algorithm

過去部不會用到，未來可能也不會用到
最常用的演算法

實踐方法
1. Counter implementation
利用 counter，找到最小的值
但可能是剛剛才進來，就被拿走

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(收穫者)，進行記憶體回收。直到可用記憶體閥值達到最小閥值。

## 10-6 Thrashing
如果 pages 不夠，會一直 page fault，頻繁 I/O，稱為 trashing，OS會更頻繁去切換執行更多程式 -> 造成更低CPU utility，形成惡性循環

### Locality model (局部區域模式)
程式在一段時間內通常會集中訪問某些特定區域的記憶體區域

#### 時間區域性 （Temporal Locality）
如果一個記憶體位置在某個時間點被存取，那麼之後很可能再次被存取

#### 空間區域性 （Spatial Locality）
如果一個記憶體位置在某個時間點被存取，那麼它附近記憶體位置很可能之後也會很快被存取

### 實作的方式

#### Working-Set Model


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

#### Page-Fault Frequency
If actual rate too low, process loses frame
If actual rate too high(trashing), process gains frame

## 10-7 Memory Compression
)
不把它 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
但會發生 fragmentation 的問題

### Slab Allocator
==Slab== is one or more physically contiguous pages
==Cache== consists of one or more slabs
每個 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

for( j = 0; j < 128; j++)
    for( i = 0; i < 128; i++)
        data[i,j] = 0;

for( i = 0; i < 128; i++)
    for( j = 0; j < 128; j++)
        data[i,j] = 0;


### Data Structure


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

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

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