作業系統_謝仁偉
[TOC]
# 期中考重點複習
## Chapter 1: Introduction
- 什麼是 Operating System
- 是一個 program 能夠讓使用者使用電腦和電腦硬體溝通。
- Computer system 可以分成 4 個 components：
- Hardware
- Operating system
- Application programs
- Users
- Software 的 Interrupt 叫做 **Trap or Exception**
- Hardware 就叫 Interrupt
- OS 是 Interrupt driven
- 當發生 Interrupt 時
- OS 會利用 registers 和 Program Counter 保存 CPU 的狀態
- 兩種模式去處理多個 interrupts
- **polling** ⇒ 輪詢，輪流處理 interrupt，比較慢，但 reliable，因為要依序檢查 device
- **vectored interrupt system** ⇒ 比較快，但設計較為複雜，不需要依序檢查 device，會設計一個 priority system 去處理優先處理比較重要的 interrupt
- Interrupt time ⇒ 注意反應時間
- Storage-Device Hierarchy


- Caching Replacement Poliy
- LRU ⇒ Least Recently Used 淘汰最久沒被使用的
- LFU ⇒ Least Frequently Used 淘汰最不常（頻率）使用的
- Multiprocessors ⇒ parallel system 平行化系統、tightly-coupled systems 緊密耦合系統
- 優點：
- 增加 throughput
- 規模經濟 ⇒ 符合經濟效益（？）
- 增加 reliability → graceful degradation or fault tolerance （單顆核心故障，不影響整體運作）
- graceful degradation（優雅降級）
- 當有部分設備故障時，能夠確保整體還能正常運作，雖然可能會降低性能，但可用。所以 graceful degradation 主要是維護部分的功能，確保整體能夠運作。
- fault tolerance（容錯性）
- 不僅僅是在部分設備故障時，能夠確保設備能正常運作，還會確保設備性能保持在原有的水準。
- 兩種 Multiprocessors
- Asymmetric Multiprocessing ⇒ 可能會設計特別的 processor 處理特殊的任務（如：高負載的運算，而有些只需要負責低負載的運算）
- Symmetric Multiprocessing ⇒ 每個 processor 之間沒有差異，都能夠做相同的工作
- 每個 Computer System Components 的定義
- CPU：中央處理單元，執行指令
- Consistency ⇒ 對 multiple locations
- 一致性關心的是分散式系統中的數據一致性
- 在分散式系統中，每個系統可能同時要做同樣的操作，為了讓數據保持正確，會有順序的執行 program，前一個做完，才能往下繼續。
- Processor：由單個或多個 CPU 組成的晶片
- Core：CPU 的基本運算單元
- Multicore：在同一個 CPU 中有多個 core
- Multiprocessor：多個 processor 組合在一起
- Clustered system ⇒ 把多個系統串接在一起，交互運算。每個系統（電腦）都是獨立的。
- Asymmetric → 有一個機器是 Hot-standby mode
- Hot-standby mode：會監測 active server，如果 server 掛掉，Hot-standby host 就會變成 active server
- Symmetric → 每個機器會互相監控
- Multiprocessor system ⇒ 一個系統有多個 processor 組成，共用同一個儲存單元、記憶體。
- 各個等級的儲存單元
- registers ⇒ < 1KB
- cache ⇒ < 16MB
- main memory ⇒ < 64GB
- solid state disk ⇒ < 1TB
- magnetic disk ⇒ < 10TB
- Coherence vs Consistency
- Coherence ⇒ 對單一的 location 或 variable
- 一致性關心的是多核處理器系統中的緩存和內存之間的數據一致性。
- 在 shared memory 的 multiprocessor system 中，保持每個 processor 對於指向相同的 variable 的一致性。
- 對 I/O 的 memory management 有包含
- Buffering，緩衝，儲存待處理的資料，穩定處理的速度。
- Caching，快取，將特定部分的資料放在比較快的 memory 中，加速 CPU 存取資料的過程。
- Spooling，排隊，在處理一個 job 的輸出時，在輸入處理其他的 job，使處理效率增加。
- Privilege escalation ⇒ 權限升級，使 user 有更多的權限做比較危險的事情，例如在指令前面加上 sudo。
- Virtualization vs Emulation
- Virtualization 虛擬化，把實際有的硬體資源，拆分成多個資源，供給不同的執行環境使用。
- Emulation 模擬，主要是讓原生 CPU 透過模擬的方式運作不同種類的 CPU，實現跨平台的環境。例如 x86 的架構，模擬成 ARM 架構，得以運行對應的作業系統。
- Distributed Systems
- Local Area Network (LAN) ⇒ 房間、住宅、校園
- Wide Area Network (WAN) ⇒ 社區、城市、國家
- Metropolitan Area Network (MAN) 大都會的 ⇒ 一個城市
- Personal Area Network (PAN) ⇒ 短距離，如藍芽，802.11 的 WiFi
- Computing Environments
- Traditional Computing ⇒ 傳統運算
- Mobile Computing ⇒ 行動運算
- Client-Server Computing ⇒ 主從式架構運算
- Peer-to-Peer Computing ⇒ 對等網路運算
- Cloud Computing ⇒ 雲端運算
- Real-Time Embedded Systems ⇒ 及時嵌入式系統運算
## Chapter 2: Operating-System Structures
- System Call：讓 Application Program 能夠透過 system call 呼叫、執行 kernall 或是 硬體的功能。
- 三種方式用於傳遞 parameters 給 OS
- 使用 Register 傳送
- 儲存在 block or table in memory 把對應的位址 使用 register 傳送
- Program 把 parameters push 至 stack，OS 再 pop stack 中的 parameter
- System Call 的類別
- Process control 控制 Process
- File management 檔案管理
- Device management 裝置管理
- Information maintenance 資訊維護：如，get/set time or date, get/set system data, get/set process or file or device attributes
- Communications 溝通
- Protection 保護
- 名詞解釋：
- Policy → What will be done? 要做甚麼？
- Mechanism → How to do it? 怎麼去做
## Chapter 3: Process
- Process ⇒ a program in execution
- 一個 process 在 memory 中會被劃分不同的區域：
- text section：儲存 code
- data section：儲存 global variables
- stack：儲存 teporary data（如 funciton parameters, return address, local variables）
- heap：儲存 在 run time 動態分配的記憶體空間


- Program vs Process
- Program → passive
- Process → active
- Program 被載入到 memory 中，就會變成 Process 等待處理。
- 當 process 執行時，會改變 state
- new → The process is being created
- running → Instructions are being executed
- waiting → The process is wating for some event to occur
- ready → The process is waiting to be assigned to a processor
- terminated → The process has finished execution


- 管理 Process 的結構 ⇒ Process Control Block (PCB) or Task Control Block
- Process state
- Program counter ⇒ 當 interrupt 發生時，PC 會被記錄
- CPU register
- CPU scheduling information
- Memory-management infromation
- Accounting information
- I/O status infromation


- 為了要 maxmize CPU 的 utilization 會使用 Time Sharing 處理 processes
- 就會需要 Process Scheduler 安排 process 的執行順序
- Ready queue - 準備要在 CPU’s core 上執行
- Wait queue - 等待其他 event，像是 I/O


- 不同的 Schedulers
- Short-term scheduler (CPU scheduler) → 決定哪個 process 是下一個要執行，分配給 CPU 做運算
- 觸發頻繁 → CPU 要很快
- 目的：讓每個 process 都有機會被 CPU 執行到
- Long-term scheduler (job scheduler) → 決定哪個 process 要被放入 ready queue 裡面
- 觸發較不頻繁 → 比較慢
- 目的：控制系統的負載，防止內存爆滿
- Medium-term scheduler → 當附載太高時，可以先把 process 從內存中釋放出來（swap out 至 disk），等待內存空間足夠時，再把 process swap in 至 ready quene 中處理。


- 兩種 process 的類型
- I/O-bound process：處理 I/O 的時間大於 CPU 運算的時間
- CPU-bound process：處理 CPU 運算的時間大於 I/O 的時間
- 而 Long-term scheduler 是 process mix，在 I/O 跟 CPU 中達到平衡
- Context Switch → 指 CPU 在交換不同的 process 運算的動作。
- 透過 context switch 可以把原本的 process state save 起來
- pid ⇒ process identifiler
- load 新的 process 的 saved state
- Process Creation → Parent creat a Child process
- fork() ⇒ create new process
- exec() ⇒ after fork(), 執行此 process


- 當 parent fork() child 時，會等待 child 做完再換 parent 執行
- Process Termination
- process 執行的最後會 exit() 使 OS 刪除 process
- Parent 可以 abort() 中斷正在執行的 child process
- 當 parent 被 terminated 時，會觸發 cascading termination 使 parent 底下的所有 child 都會被 terminated
- Zombie process → 當 child process 結束時，parent 沒有呼叫 wait() 接收 child 的資源，則 child 就換變成一個 zombie process 佔用資源。
- Orphan → parent 結束時，child 沒有被 parent 呼叫 wait()，則 child 會變成 orphan process
- 最後會交由 init process 負責回收這些 orphan process
- Interprocess Communication ⇒ Process 之間的溝通，有兩種方式
- Interprocess Communication (IPC)
- Shared memory
- Message passing
- Process 溝通會需要 buffer 暫存資料 (Producer ↔ Consumer)
- unbounded-buffer ⇒ 儲存空間無限制
- bounded-buffer ⇒ 固定 buffer size，通常會使用 circular array
- Producer


- Consumer


- Message passing 有兩種傳遞訊息的種類
- Blocking (synchronous 同步) ⇒ 可靠且有序，但會有掛機的問題，降低效率。
- sender 必須等待 message 被接收
- receiver 必須等待 message 到達
- Non-blocking (asynchronous 異步) ⇒ 提高程序的執行速度，但是要進一步處理資料的一致性和正確性。
- sender 發送後就繼續做其他事情
- receuver 可能會收到訊息，但也可能會收到 Null message
- Remote Procedure Calls (RPC)
- Messages can be delivered **exactly once** rather than **at most once**
- exactly once ⇒ 確保訊息只傳遞一次，不會被重複傳送，也會使用 ack 等機制，確保有被接收
- at most once ⇒ 訊息傳遞最多一次，意思是沒有 ack 等機制，確保被接收，所以訊息可你會遺失
## Chapter 4: Threads & Concurrency
- Thread 的優點
- Resposiveness
- Resource Sharing：因為 threads 共享資源，所以更方便做 shared memory or message passing
- Economy：因為資源共享，在做 context switch 會比 process 更快、更低的 cost
- Scalability：因為 thread 能夠平行處理，有效利用多核心處理器的架構。
- Multicore 或 Multiprocessor 要處理：
- Dividing activities
- Balance
- Data splitting
- Data dependency
- Testing and debugging
- Concurrency and Parallelism
- Parallel system ⇒ 同時能夠執行多個任務，平行處理（多核心）
- Concurrent system ⇒ 依序執行任務，分時多工（單核行）
- It is possible to have concurrency without paralleism（能做到 concurrent 的話，不能做到 parallel）反過來說，能做到 parallel 一定可以做到 concurrent


- Types of parallelism
- Data parallelism ⇒ 多個處理器，在處理相同的資料。
- Task parallelism ⇒ 多個處理器，在處理不同的任務。
- Amdahl’s Law
- S → serial portion 無法平行運算的序列部分
- N → processing cores


- 在增加 N 的情況下，相較於單核心，能夠提高速度的倍數
- Relationship between user threads and kernel threads
- Many-to-One
- 一次只能執行一個 thread
- 若有一個 user thread blocking，則其他 user thread 就無法使用 kernel thread
- 無法平行運算


- One-to-One
- 比 Many to One 有更好的 Concurrency
- 有更多的 kernel thread 會降低整體效能


- Many-to-Many
- kernel thread 數量 ≤ user thread 數量
- 難以實作
- 因為硬體效能越來越好，所以 kernel thread 的數量不再是限制


- Two-level Model = Many-to-Many + One-to-One


- Programmer 可以透過 thread library 的 API 去 createing and managing threads
- POSIX Pthreads
- Windows threads
- waiting for multiple threads ⇒ 設定要等待的時間
- Java threads
- 交由 Compiler 自行決定並呼叫 thread 完成 program ⇒ Implicit Threading
- Thread Pools ⇒ 在一個有限制 thread 數量的 pool 中，讓 compiler 呼叫 thread
- OpenMP ⇒ 在指定的 parallel regions 中，用平行的方式執行
- Grand Central Dispatch
- Threading Issues
- Semantics of fork() and exec()
- 若 有一個 thread call fork()，那麽新的 process 會複製原本所有的 thread 還是只會複製 single-thread ⇒ 會依照 exec() 是否在 fork() 後面被呼叫
- exec() - replace the running process including all threads
- Signal Handling：用來發送異常訊號
- Thread Cancellation ⇒ 在 thread 結束前，會先 terminating
- Asynchronous cancellation：terminates immediately
- Deferred (延期) cancellation：terminates periodically
- Thread-Local Stroage (TLS)
- 讓 thread 在資源供想的情況下，有私有的儲存空間
- Scheduler Activations
- 在 Many-to-Many 或 two-level model 中，會去動態分配 kernel thread 的數量
- 透過 lightweight process (LWP) 使 user thread 跟 kernel thread 互相溝通
- upcall ⇒ 一種通訊機制，使 kernel 可以使用 upcall 提供 thread 的數量，使 application 可以確保可用的資源。

## Chapter 5: CPU scheduling
- 在 multiprogramming 中，要 maximize CPU 的 utilization ⇒ CPI 跟 IO Burst 不斷輪流執行。
- 所以要如何分配 CPU burst 是主要關鍵。
- Histogram of CPU-burst Times


- Nonpreemptive (cooperative) 非搶占式
- 一段 process 會使用 CPU 直到那個工作要進入 waiting state 或是 terminate
- 其他 process 無法中斷正在進行的 process
- Preemptive 搶占式
- 作業系統可以在任何時間點中斷正在進行的 process，把 CPU 分配給其他 process 使用
- 會需要大量的 context switch ⇒ 提高成本
- race condition ⇒ 可能會讓結果不正確
- Dispatch ⇒ 把 process 派送給 CPU 做處理
- Dispatch latency ⇒ 停止 process 然後開始其他 process 的時間
1. 儲存原本的 process state
2. 載入新的 process
3. 把 CPU switch 到新的 process 做處理
- Scheduling Criteria
- CPU utiliztion
- Throughput ⇒ 在單位時間內能做多少件事情
- Turnaround time ⇒ 一個 process 執行的總時間
- Waiting time ⇒ 一個 process 在 ready queue 等待的總時間 (等待次數可能不只一次)
- Response time ⇒ 一個 process 進到 ready queue 到第一次被處理的時間
- FCFS, First Come First Served Scheduling
- Convoy effect - short process behind long process，短的 process 會被長的 process 擋住在後面。
- Shortest Job First (SJF) Scheduling ⇒ Nonpreemptive
- 但不知道下一個 process 的 CPU burst 所以會用 Prediction 的方式預測下一個的長度
- Solution: 藉由先前的 CPU burst 來推估下一個的 CPU burst time


- 如果 a = 0 → 不考慮實際的歷史資訊
- 如果 a = 1 → 這一次的 burst time 直接當作下一次的 burst time
- Shortest Remaining Time First (SRTF) ⇒ Preemptive
- 當有 process arival，就會進行比較，選擇最小的執行
- vs SJF ⇒ 每次比較，只會發生在當前 process 結束時
- Priority Scheduling
- 有分 preemptive 跟 nonpreemptive
- 數字越小，Priority 越高
- Problem ⇒ starvation 若一直有 priority 比較高的 process 進來，比較低的就永遠無法被處理到。
- Solution ⇒ Aging 隨著 waiting 時間越久， priority 會提高
- Round Robin
- time quantum → q (通常是 10-100 milliseconds)
- q 太小，輪到 process 根本還沒開始，就要換到下個人做。等於沒做
- Multilevel Queue Scheduling ⇒ 用不同的 queue 組合在一起，每個 queue 不一定是相同的 scheduling
- Example


- Thread Scheduling
- Multiple-Processor Scheduling
- Approachs
- Asymmetric ⇒ 沒有 data sharing 的問題
- Symmetric multiprocessing (SWP) ⇒ 每個 processor 做自己的 scheduling，但可以共用同個 ready queue 或是有自己的 ready queue
- Processor affinity ⇒ process 會指定 processor
- soft ⇒ process 能根據情況變換處理的 processor
- hard ⇒ process 只能夠在特定幾個 processor 之間變換
- NUMA and CPU Scheduling
- NUMA: Non-Uniform Memory Access
- NUMA system 能夠讓 CPU 透過 interconnect 取得其他 core 的 memory 資料，但會比較慢。


- Load Balancing ⇒ 透過一些方法讓 multiprocessor 能夠平均、有效的利用資源
- Push migration：週期性檢查 loading，把 overload 的工作，分配給 Idle 的處理器
- Pull migration：當處理器閒置時，會主動去找忙碌的處理器，分配工作
- Multithreaded Multicore System
- 情境：當 CPU 在處理 thread 時，會需要花時間 access memory (這時稱為 memory stall cycle)，所以為了有效利用這個空檔，不要讓 CPU 閒著，設計成 Multithread
- 同一個 core 底下，利用空檔，分時處理多條 threads


- Real-Time CPU Scheduling
- soft ⇒ 不保證 process 會在 deadline 前完成
- hard ⇒ 保證 process 會在 deadline 前完成
- Rate Monotonic (RM) Scheduling ⇒ 處理有週期性的 process
- 週期越短的 process, priority 越高
- 如果 miss deadline，則先做 priority 高的，等空閒時，再回來處理還沒做完的 process

- Earliest Deadline First Scheduling (EDF) ⇒ 最佳的排程 algorithm
- deadline 越近，priority 越高


- Algorithm Evaluation
- Deterministic Modeling ⇒ 使用已知的 workload 計算並比較每個 algorithm 的 performance
- Queueing Models ⇒ 基於排隊理論，計算 CPU burst 跟 I/O burst 的機率
- Little’s Formula


- Simulations ⇒ 模擬整個電腦系統，統計各項數據
- Input 數據可能是隨機產生 or 用某種 distribution or 使用實際收集到的真實數據
- 比前面的方法更加準確
- Implementation
- 結果最為準確
- 直接時做出一個 real system
- 成本高、風險高
- 考慮多樣的環境 ⇒ 會更難實作

## 業師課

- Floating Gate ⇒ 降低或提高截止電壓（Vt），且Floating Gate 不會消失，則可以做成儲存單元，保存上一次的結果。
- 把電子打入 Floating Gate 原理是量子穿梭
- NAND Flash
- 清除資料會一次清除一個 Block（物理限制）
- 寫入是 page by page (WL by WL)
- 讀取是 page by page (WL by WL)
- NAND Flash Ctroler
- 資料處理
- 錯誤處理

### Lab

---

- FUSE SSD
- 1 個 page 有 512Bytes
- 把 sequence A 改成 sequence B 才能夠做後續的 GC (Garbage Collection)
- Tasks：
- Read/Write
- Sequence A → B
- Garbage Collection
- 目標：
- Keep WAF lower，越小越好，排名越高
- 確保 data 存取的正確性 ⇒ 測資要自己想

# 期末考重點複習
## Chapter 6: Synchronization Tools
- 因為多個 processes 要能夠同時地執行 → 必須維護執行的順序，確保結果正確。
- Consumer-producer problem
- Consumer 消費者(消耗者)
- Producer 生產者(提供者)
- 注意：Race Condition，因為順序不同，導致結果不正確

- Critical Section Problem
- 架構的 3 個主要 components
- entry section
- exit section
- remainder section

        do {
            :: entry section
                    critical section
            :: exit section
                    remainder section
        } while(true);

- Solution requirements：
- Mutual Exclusion **互斥**：一次只能有一個 Process 在他自己的 Critical section
- Progress **要能夠持續運作**：若目前沒有 Process 在 Critical Section，且有 Process (可能不只一個)想要進入，則必須選擇一個 Process 進入。
- Bounded Waiting **限制等待時間**：若有一個 Process 等待進入 Critical Section，不能夠讓他一直等待，需要設定一些條件，使得 Process 可以在未來被選擇進入。
- 例如，設定等待時間，等待越久 Priority 越高。
- Critical Section Handling in OS
- Preemptive：允許直接中斷，並執行
- Non-preemptive：必須等待離開 Kernal mode 之後才執行

- Peterson’s Solution 大同世界
- 限制：兩個 Process 的情況

- Synchronization Hardware
- 使用硬體的方式實現 critical section code
- 方法 ⇒ locking：用 Lock 保護 critical section
- 作法：Atomic hardware instructions → non-interruptible 不會被中斷，有效率的做法


- 兩個 Atomic 的指令作法，管理 lock
- Test-and-set Instruction


- 用一個 flag 記錄原本的值
- 把 lock 設成 TRUE
- 回傳 flag
- ⇒ 不管怎麼樣， lock 最後都會變成 TRUE，只是當傳進來的 lock 是 FALSE 時，回傳的值才會是 FALSE，然後進入到 critical section（此時 lock 會是 TRUE 的，確保其他 process 不會同時進入 CS），做完後，lock 設定成 FALSE 讓其他 process 進入。
- Compare-and-swap Instruction


- 先**比較**，比較通過，才**替換**


- 等待 lock 變成 0，先把 lock 設定成 1，把 0 回傳回去，進入 Critical Section
- Bounded-Waiting Mutual Exclusion


- Mutex Locks

- 前面提到的 程式設計起來比較複雜，且不夠彈性(沒有辦法 access 到應用程式)
- Mutex lock 是利用 acquire() 跟 release() 保護 lock，且這兩個功能必須是 atomic 的(硬體實現)
- 缺點：Busy waiting → 使用迴圈等待條件不成立，並跳出迴圈。浪費 CPU 資源 ⇒ 這樣子的 lock 稱作為 spinlock
- 程式碼：


- Semaphore

- 提供更精細的方法，使 process 能夠同步(Synchronization)他們的 activities ⇒ 讓 processes 能夠照著期望的順序執行
- 主體 Semaphore S → 一個 integer variable 用來記錄剩餘資源 (Source)
- 兩個不可分個的 atomic operation
- wait() ⇒ P()
- signal() ⇒ V()

- 兩種 Semaphore
- Counting semaphore → S 的數量範圍可不受限制
- Binary semaphore → S 的數量範圍只能是 0 或 1 ⇒ 操作就如同 Mutex lock
- 實作方面
- 為了確保 Semaphore 能夠按照順序執行 process，必須要確保不會任意兩個 process 同時對同一個 S 執行 wait() 跟 signal() ⇒ 這就變成了 Critical Section Problem (不能同時進入 Critical Section)
- 所以就還是會有 busy waiting 的情況發生

- Implementation with No Busy Waiting

- Waiting queue → 讓每一個 Semaphore 都有一個2jo4uwaiting queue
- Waiting queue
- value：紀錄 S 的數量
- pointer：指向下一個等待被處理的 process
- Two operations
- block → 用來把 process 放入到 waiting queue
- wakeup → 用來呼叫 process，把 process 移出 waiting queue，放到 ready queue 裡面



- Deadlock and Starvation

- Deadlock：兩個或是多個 process 在互相等待，導致沒有 process 能夠繼續執行，因為每個人都在等待對方的資源。
- 舉例：
- P0 得到 S 的資源，P1 得到 Q 的資源，現在 P0 等待 Q，P1 等待 S，但是它們要先得到對方的資源後，才會釋放手中的資源，導致 Deadlock 發生。


- Starvation → indefinite blocking 無限的 blocking
- 某個 process 一直等待
- Priority Inversion
- 一個具有較低優先級的任務卻在持有一個較高優先級任務所需的資源時，導致較高優先級的任務被阻塞。
- 舉例：
- priority: A > B > C。C 正在執行，並且進入 critical session，此時 A 要佔用 CPU 所以 C 中斷，直接換 A，接著 A 執行需要進入 critical session 但是 C 還沒結束，所以要跳回 C 讓他做完（預期接下來換 A），但是 C 做到一半，B 搶佔 CPU 導致明明 A 在等待，結果 B 搶佔 A 的資源。造成 Priority Inversion。
- 假設系統中有三個任務 A、B 和 C，其中 A 的優先級最高，B 的優先級次之，C 的優先級最低。現在如果 B 持有了一個資源（例如一個互斥鎖或信號量），而 C 需要這個資源才能執行，但 A 需要等待 C 執行完成才能繼續，這樣就產生了優先級反轉的情況：C 因為 B 的佔用而阻塞，A 也因為 C 的等待而被阻塞，導致系統中的最高優先級任務被延遲執行。
- 解決方法：
- **優先級繼承（Priority Inheritance）**：當一個較低優先級的任務獲取了一個資源時，它會暫時提高到這個資源所需的最高優先級，以防止高優先級的任務被阻塞。這樣可以保證資源的優先級與需求的優先級相符。

- Problims with Semaphore

- 使用不當，導致錯誤發生，但是難以偵測，因為錯誤通常是在特別的情況下才會發生，而不是常常發生。
- 順序相反：signal() … wait() → 只有在 2 個以上的 process 都先進入 signal 後 wait 的時候才有可能發生問題。
- 連續使用兩個 wait() → 導致 permanently block，因為沒有使用 signal 釋放資源。
- 省略掉 wait() 或是 signal()
- Deadlock 和 starvation 也都有可能發生

- Monitor

- 是一種用於控制並發存取共享資源的同步機制
- 同時只會有一個 process 被 active 進 monitor
- Abstract data type：隱藏資源的內部細節，只讓 programmer 透過 Monitor 提供的介面進行 access → 保護資源


- Condition Variables

- condition x, y; → x 跟 y 是條件變數。
- 條件變數可以使用兩個 operation
- x.wait() ⇒ 進入等待狀態，直到 x.signal() 被呼叫
- x.signal() ⇒ 用來喚醒 x.wait()，若 x.wait() 沒有被呼叫，則呼叫 x.signal() 不會有任何事情發生


- Condition Variables Choices

- 如果 process P 呼叫 x.signal()，且 process Q 有先呼叫過 x.wait()，但是要遵守一次只有一個 process 在 monitor 中 active，則要怎麼做？
- Signal and wait → P 先等待 Q 做完，再換 P。
- Signal and continue → Q 等待 P 做完，再換 Q。

- Monitor Implementation Using Semaphores (重要！！)

- 若要使用 Semaphore 實作 Monitor 機制


- 針對 Condition Variables



## Chapter 8: Deadlocks
- 每個 process 在使用 resource 時，會按照：
- request
- use
- release

- Deadlock Characterization

- 必須同時滿足四個條件，才有可能影發 deadlock
- Mutual exclusion：互斥條件，一個資源同時只能被一個 process 使用。
- Hold and wait：一個 process 手上握有一個資源，且正在等待其他資源。
- No preemption：不會搶奪其他人的資源，一定會等待其他人釋放資源。
- Circular wait：當多個 process 等待下一個 process 所持有的資源，並形成一個循環。

- Resource-Allocation Graph

- P: process
- R: resource
- Request edge: P → R process 請求資源
- Assignment edge: R → P 資源分配給 process
- 定義


- 範例


- Deadlock 範例


- Basic Facts
- No cycles ⇒ No deadlock
- contains a cycle ⇒
- 每個 resource type 只有一個 instances ⇒ deadlock
- 每個 resource type 有多個 instances ⇒ 有可能 deadlock

- Methods for Handling Deadlocks

- Deadlock prevention → 讓一種 deadlock condition 不成立
- Deadlock avoidance → 確保系統在 safe state
- Recover deadlock 解決發生 deadlock 的狀況
- Igbore the problem 忽略 deadlock

- Deadlock Prevention
- 讓一種 condition 不成立
- Mutual Exclusion
- 不提供 sharable resources，每個 process 都是使用 non-sharable resources，就不會發生需要取用同一個資源的問題
- Hold and Wait
- 當 process 要去 request 其他 resources 時，手上不可以有任何 resources
- Low resource utilization 且可能會發生 starvation
- No preemption
- process 可以搶佔其他人的資源，以確保資源能夠有效地被使用
- Circular Wait
- 取得 resource 順序要由小到大，可以避免 cycle 產生

- Deadlock Avoidance

- 核心想法
- 在資源分配時，動態地檢視 resource-allocation state，確保他不會有 circular-wait 的情況發生
- Safe State 定義：
- 找到一個 sequence，確保(目前的 R + (Pj 有的 Resource)) 可以滿足 Pi (j < i) ⇒ 就代表 Pj 做完，釋放資源後可以繼續往 Pi 進行。

<aside>
📌 演算法 DAG ⇒ Directed Acyclic Graphs
有向無環圖，每個節點會有 topological order


</aside>

- Basic Facts
- safe state ⇒ no deadlocks
- unsafe state ⇒ 可能發生 deadlocks
- Avoidance ⇒ 確保 system 永遠不會進入 unsafe state
- Algorithm
- Single instance ⇒ resource-allocation graph
- Multiple instances ⇒ Banker’s Algorithm

- Banker’s Algorithm

- Data Structures


- Safety Algorithm


- Resource-Request


- Example
- The content of the matrix Need is defined to be Max – Allocation


- Deadlock Dection

- 目的
- 檢測出可能發生 deadlock 的情況 ⇒ cycle
- 如果有 cycle 則嘗試 recovery
- Single Instance
- Maintain wait-for graph
- 如果 Pi → Pj 形成一個 cycle
- 週期性檢測
- O(n^2)
- Several Instances
- Available ⇒ 目前 system 擁有的閒置資源
- Allocation ⇒ 每個 P 目前所分配的資源
- Request ⇒ 每個 P 還需要請求的資源
- Algorithm


- Example

- Recovery
- Process Termination
1. 終止所有 deadlock 的 processes
2. 一次終止一個 process 直到解除 deadlock cycle
- Process Preemption：如果可以使用 preemption，就可以解決 deadlock 問題。
- Selecting a victim - 選代價最小的 process
- Rollback - 重新執行
- Starvation - 但如果每次選擇的 victim 都是同一個，就有可能 starvation ⇒ 可以在被選擇為 victim 時，提高他的 priority

## Chapter 9: Main Memory

- Background
- program 必須從 disk 載入到 memory 裏面，才能夠執行。
- Main memory 和 register 是能夠被 CPU 直接 acess 的儲存裝置
- Register 的 access 會在 一個 CPU clock 以內完成
- Main memory 的 access 可能會花費很多個 cycles，導致 stall
- Cache 是介於 main memory 和 register 之間的

- Base and Limit Registers

- Base Register 跟 Limit Register 是用來實現 protection of memory 的機制。 ⇒ 使 CPU 在讀取記憶體時，不會存取到其他不合法的東西。
- Base Register：用來記錄在記憶體中的起始位址。
- Limit Register：用來記錄區段在記憶體中的大小。
- 每當 CPU 在訪問、存取記憶體內的資料時，藉由 Base 跟 Limit 取得資料在記憶體中的實際、正確的位址。


- Address Binding
- 綁定 program 的 symbolic 的位址和實際位址
- 在以下三個階段，會有不同的 Binding：
- Compile time：要能夠取得 code 在 memory 的位址，如果無法得知就必須 recompile code
- Load time：如果不知道 process 在 memory 的哪個地方，則需要 relocatable code
- Execution time：如果memory segment要執行時被移動，binding才會延到這時

- Logical vs. Physical Address Space

- logical address：由 CPU 產生，也被稱為 virtual address
- physical address：在 memory unit 所看到的位址
- 在 compile-time 跟 load-time 時，logical 跟 physical 是一樣的；只有在 execution time 時才會不一樣。因為 execution time 是 dynamic bind 的，所以有可能會發生改變。

- Memory-Management Unit (MMU)

- MMU 是一個硬體裝置，用來 map virtual 與 physical 的 address


- user program (CPU side) 只需要處理 logical address，不需要管 physical address。因為 MMU 中的 relocation register 會去協助 CPU 轉換 logical address。

- Dynamic Linking and Shared Libraries

- Dynamically linked libraries (DLLs) 是一個 system libraries
- 能夠在程序執行時連結 user program
- Static linking：打包程式專案時，連同程式所寫需的 libraries 也一起打包。確保程式可以在任何地方執行，但是檔案可能會很大。
- Dynamic linking：打包程式專案時，只打包最重要的程式部分，程式所需要的函式庫，可以在執行時動態去連結，減少了檔案的大小，但很有可能會因為執行環境不同，導致無法與函式庫做動態連結，導致不相容的問題。
- DLLs 是一個 shared libraries
- 需要 OS 協助管理及保護 dynamic linking 和 shared libraries

- Swapping
- 程式需要執行時，swap in Main memory。不需要時，swap out Main memory。
- Backing store
- 要是一個 fast disk，有足夠的空間容納所有 copies of memory images
- 能夠直接 access 這些 memory images
- Roll out, roll in：swap 的變形，使用 priority 管理。低順位的，會被 swap out，使高順位的能夠 swap in main memory 執行
- 大部分的 swap time 是 transfer time（搬入、搬出記憶體的時間）
- 交由 ready queue 存放即將要 swap in memory 執行的 processes


- Context Switch Time and Swapping
- 如果我要做 context switch，但是 next process 不在 memory，則我必須要把原本的 process swap out，再把需要的 process swap in 進來，則會需要兩倍的 transfer time。 ⇒ 這樣的 context switch 代價很高。
- 減少的方法：藉由知道需要多少的 memory 空間
- 如果在執行到 I/O 時，不可以 swap out 否則會發生錯誤
- Double buffering：
- 當要載入 I/O 的資料到 Main memory 時，假設是直接載入到 user memory 中，若發生 context switch 時，會直接把 user memory 的內容覆蓋掉，則 I/O 就會遺失，必須重新 request。
- 所以使用 Double buffering 的概念，先讓 I/O 載入到 kernal memory 中，等到 CPU 要取用那些資料時，再把資料載入到 user memory，進行兩次的 buffer。

- Contiguous Allocation

- Main memory 通常會被分為兩個部分：
- low memory：存放跟作業系統操作相關的內容
- high memory：存放 user process
- 每個 process 都會是以連續的 section 存在 memory 中
- 因為 Main memory 也會存放 OS code 所以必須要有 relocation register 保護這些 code 被存取到
- Base register
- Limit register


- 是可以讓 kernal code 短暫的儲存在 memory 中。

- Multiple-partition Alloction
- 系統會分配一個符合需求大小的 memory size 給 process
- Variable-partition：Main memory 會被劃分成大小不同且可改變的子空間。
- Hole：block of avaliable memory 可用空間。
- 當 process 結束，會釋放 partition，只有鄰近的 free partition 才可以 combined 成大的 partition
- OS 會取 maintain
- allocated patitions
- free partitions (hole)


- Dynamic Storage-Allocation Problem

- 如果有一個 process 要求空間，那 memory 有什麼策略可以提供空間？
- First-fit：分配 the first 可以滿足的 hole
- Best-fit：分配 the smallest 可以滿足的 hole
- search list
- sort by size
- Worst-fit：分配 the largest 可以滿足的 hole
- First-fit 跟 best-fit 的操作速度以及 utilization 會比 worst-fit 好。

- Fragmentation
- External Fragmentation：不是連續的 free memory，加總起來可以滿足 request（被要求的記憶體空間）
- Reduce：compaction ⇒ 把 free memory 放在一起，形成一個足夠大的空間。要求 relocation 機制是 dynamic 的。
- Internal Fragmentation：當某個 process 要求的 memory 大小與分配給的 memory 大小之間有較大差異。那個剩餘的空間，未被使用，但也沒辦法分配給其他 process 使用。

- Segmentation Architecture


- Logical address：<segment-number, offset>
- Segment table：儲存每個 segment 的實際位址，透過
- base：segment 在 memory 的起始位址
- limit：length of the segment
- Segment-table base register (STBR)：這個暫存器會指向 segment-table 的位址。
- Segment-table length register (STLR)：這個暫存器表示 segment-table 的大小。所以 segment number 必須 < STLR


- Paging
<aside>
📌 Frames ⇒ 把 physical memory 分成 fixed-sized blocks
Pages ⇒ 把 logical memory 分成 相同的 size

</aside>

- Page table：logical 跟 physical address 之間的轉換
- 雖然避免 external fragmentation
- External 是指，不連續的 free fragment，可以組合成一個足夠的空間。
- Paging 可以使用不連續的 physical 空間，提供對應到連續的 Logical 空間。每個儲存單位根據 page size 而定。
- 但還是有 internal fragmentation
- 因為不一定使用的 Page size 剛剛好，所以一定會有 internal fragmentation

- Address Translation Scheme
- page number (p)：page 的編號
- page offset (d)：在 page 中的第幾個元素


- Paging Harware


- Paging Example


- Implementation of Page Table
- page table 會儲存在主記憶體中。
- Page-table base register (PTBR)：指向 page table 的位址
- Page-table length register (PTLR)：表示 page table 的 size
- fast-lookup hardware cache（如：associative memory、translation look-aside buffers ⇒ TLBs），當 TLB hit 時，只需要 1 次的 memory access，取代原本都要 access memory 兩次的狀況
- TLBs 用來暫存最近被訪問的地址，用來加速查找實際位址的過程。
- 有些 TLB 會儲存 address-space identifiers (ASIDs)：ASIDs 是用來區分不同的 process，防止在對不同 prcoss 做實際位址拜訪時，access 到不屬於此 process 的內容，是一個保護 process 的機制。
- 示意圖：
- 會先查找 TLB 如果 Hit，則直接計算 physical 位址
- 如果 Miss，則去 page table 查找，並更新 TLB


- Effective Access Time
- Hit ratio α：有多少的比率會 hit
- Effective Access Time (EAT)
- EAT = α * memory access time + (1 - α) * 2 * memory access time
⇒ Hit * 1 次 memory access time + Miss * 2 次 memory access time
- Miss 要乘以 2 次的原因？

- Memory Protection

- Valid-invalid bit：用來表示有效和無效，可以快速檢視是否合法。


### Shared Pages

---

多個 process 可以共享相同的 physical page，節省記憶體空間。

- Shared code
- 使用相同的 code（reentrant），做相同的事情。如 text editors
- Private code and data
- 共享相同的 code，但是還是可以保有私自的 code 跟 data


- Structure of Page Table
- 為何需要這些 structure？ ⇒ 當 page table 越來越大的話，會非常佔空間，所以透過這些方法可以減少 page table 所佔用的空間。
- Hierarchical Paging


- Hashed Page Tables

- Inverted Page Tables

## Chapter 10: Virtual Memory

- Background
---

- 因為把整個 program 載入 memory 不會使用到所有的內容
- 所以希望可以只載入部分的程式
- 每個 program 只需要更少的 memory
- 同時可以執行更多的 program
- 提高 CPU 的 utilization and throughput 且不會增加 respone time or turnaround time ⇒ 不用切換
- Virtual memory：separation of user logical memory from physical memory 把 physical memory 與 user logical memory 分離開來，讓每個程序認為他擁有連續的記憶體空間，實際上 program 只有一部分在 memory 中，其他部分都在硬碟上。
- 只把需要的部分 program 放置在 memory 中，剩下的放到硬碟上
- Logical address 空間可以比 physical address 空間來的大
- 更多的 program 可以執行 concurrently
- Virtual address space：一個空間記錄 process 儲存在 memory 中的位址
- physical memory 會使用 page frame 管理
- MMU (memory management unit) 管理 logical to physical
- Virtual memory 實作：
- Demand paging
- Demand segmentation

### Demand Paging

---

- 需要時再去載入 page
- 每次 swap 的單位是 pages
- Valid-invalid bit 記錄 page 是否在 memory 中：
- 如果是 i 代表 page fault
- Lazy swapper：除非需要page，否則永遠不會將page交換到memory中


- 發生 page-fault 的步驟：
1. choose frame ready to swap in
2. swap in to memory fram from disk
3. update valid-invalid bit table to ‘v’
4. restart the instruction


步驟：


### Performance of Demand Paging

---

- 3 major tasl componenets of the page-fault service time
- Service the page-fault interrupt ⇒ 處理 page-fault，可以靠演算法優化
- Read the page ⇒ 從 backing store 讀取 page 花最多時間
- Restart the process 可以靠演算法優化
- Effective Access Time (EAT)
- EAT = (1 - p) * memory access + p * (page fault overhead 支出 + swap out + swap in)

### Demand Paging Example

---


### Copy-On-Write

---

- Copy-On-Write (COW)：讓 parent process 跟 child process 能夠共用同一個 page
- 如果要修改資源，會先檢查目前是否有跟其他人共享，如果有，則會在修改前先複製。（Cpoy and Write）
- free pages 會在一個 pool of zero-fill-on-demand pages
- Pool 的功用在於，加速 free page 的 allocated
- 在 allocation 前，會先清除 page，保護原本 page 的內容。
- COW 的優點在於，避免不必要的資源複製，和大量的內容使用。只有要進行修改時，才執行複製。
- Example
- 假如 process 1 要對 page C 進行修改


- 先複製出來，再修改


### Page Replacement

---

- 如果沒有 free frame 的情況下，使用 page replacement，在全部的 page 當中挑選出一個 page 淘汰，換成我目前需要的 page。
- 利用 page replacement 可以防止 over-allocation (分配的空間大小超過實際所需要的大小)
- 使用 modify (dirty) bit 減少 page transfer 的成本。只有被更改過的 page 在做 page replacement 時，才需要寫回去 disk

### Basic Page Replacement

---

1. 在 disk 中找到需要寫入 memory 的 page
2. 找到 free frame
1. 如果有，直接使用
2. 如果沒有，使用 algorithm 選定 victim frame
1. 如果 victim frame 是 dirty 的則寫回 disk
3. page 寫入 frame，更新 page table 跟 frame table
4. restart instruction


### Page and Frame Replacement Algorithms

---

- Frame-allocation algorithm
- 決定給每個proces多少frames
- 決定更換哪些frame
- Page-replacement algorithm
- 希望第一次access和re-access時的page-fault rate最低

### Algorithm

---

- FIFO Algorithm
- 先來的page先放到frame裡面
- 理論上，frame 的數量越多，發生 page fault 的次數就越少
- Belady’s Anomaly：在 FIFO 的演算法中，free frame 的數量越多，但 page-fault 反而增加。
- Optimal Algorithm
- 假設知道之後所有的情況，則在此情況，最少的 page-fault 數量會為多少？
- 用來評估其他演算法之間的好壞。
- LRU (Least Recently Used) Algorithm
- 替換最久沒有使用到的
- Implementation
- Counter：每個 page entry 都有一個 counter，每當需要 replacement 時，查看最小的 counter
- Stack：當 page 被 referenced 時，會移動到 top


Use stack to record most recent page references

- LRU 跟 OPT 屬於 stack algorithm 所以不會發生 Belady’s Anomaly

<aside>
📌 Stack algorithm
n 個 frame 的情況，會是 n+1 個 frame 的 subset

</aside>

- LRU Approximation Algorithm
- 不使用 LRU，但期望可以有近似、相同的效果
- Additional-Reference-Bits Algorithm
- 額外使用一個 bit 記錄之前是否被 referenced 過。
- 選擇一個 bit = 0 的 page 做 replacement
- Second-Chance Algorithm
- 有一個指針會指向目前指到的 page，會輪流指向（clock algorithm）
- 也有額外的 bit 指向，當要取用 page 時，若指向的 page referenced bit = 1，則 reset 成 0，指針++ (Second-Chance)
- 直到指針指到 bit = 0，做 replacement


second-chance page-replacement algorithm

- Enhanced Second-Chance Algorithm
- 使用兩個 bit 判斷
- using reference bit 最近有被用過
- modify bit 有被修改過（則必須先寫回 disk 再 replace）
- (0, 0) 沒有用過、沒有被修改過 → 最適合的 page to replace
- (0, 1) 沒有用過、有被修改過
- (1, 0) 有用過、沒有被修改過
- (1, 1) 有用過、有被夕改過
- Page-buffering Algorithm
- 當 page 被選為 victim 並且 replace 掉後，不急著清掉 victim，若在不久的未來需要 reference，則不用重新寫入到 memory（因為有把他 buffer 起來）
- useful to reduce penalty if wrong victim frame selected.

### Allocation of Frames

---

- 兩中主要的 allocation schemes
- fixed allocation
- Equal allocation ⇒ 每個 process 分配的 frame 數量一樣
- Proportional allocation ⇒ 根據每個 process 的大小分配 frame 的個數
- priority allocation
- Proportional allocation ⇒ 根據 process 的優先度，分配 frame
- 如果發生 page fault
- 對自己做 replacement
- 拿低 priority 的 frame 來使用

### Global vs. Local Replacement

---

- Global replacement
- 可以選擇其他人的 frame 做 replacement
- Local replacement
- 只能在自己的 set of allocated frame 中選擇 frame 做 replacement

### Non-Uniform Memory Access

---

- NUMA：不同處理器或訪問 memory 的速度可能不同的架構
- 記憶體會被分割成不同的節點，每個節點都與一組處理器相關聯。
- 處理器可以與和自己相關連的 memory 有快速的訪問速度，但是與其他節點的記憶體速度則較慢。

### Thrashing

---

- 如果 process 沒有足夠的 pages，則就很容易發生 page-fault，導致：
- Low CPU utilization
- OS 會認為需要增加 process 提高 CPU utilization
- 最終 Thrashing ⇒ busy swapping pages in and out


### Demand Paging ad Thrashing

---

- Locality Model
- 當某個 program 正在訪問 memory 時，可能會同時訪問鄰近的 memory 位置。
- 若能夠有效的使用 locality，使得加快訪問 memory 的速度。

### Working-Set Model

---

- **Δ =** working-set window：表示 number of page。
- 在 window 中，都會被提前存取，期望加速 program 的執行速度。
- WSS（working set size of Process） = total number of pages referenced in the most recent **Δ**
- D = sum of WSS = total demand for frams
- if D > m (系統提供的 frame 個數) ⇒ Thrashing

### Page-Fault Frequency

---

- 建立 page-fault frequency (PFF) rate and 使用 local replacement policy
- 如果 rate 太低，process loses frame
- 如果 rate 太高，process gains frame
- 更直接的控制 thrashing

### Working Sets and Page Fault Rates

---


### Memory-Mapped Files

---

- 透過 mapping 把 disk 上的 file 位址，map 到 virtual memory 上
- 透過 mapping 也可以實踐文件的 shared


### Allocating Kernal Memory

---

- 通常 kernel memory 會需要 contiguous (連續的空間)
- Buddy System
- Memory allocated 會是 2 的冪次
- Advantage
- 快速的把 unused chunks 合併成大的 chunk
- Disadvantage
- fragmentation (external 跟 internal)


- Slab Allocator
- Slab 是一個或多個 physically contiguous pages
- Cache 由一個或是多個 slab 組合
- 一個 cache 只能給特定的 kernal data structure 儲存
- Benefit: no fragmentation, fast memory request satisfaction


### Pre-paging 事先載入

---

- 降低 page fault
- α hit ratio
- s * α ⇒ 有使用的 page
- s * (1 - α) ⇒ 白費的 page 數量
- α near 0 ⇒ pre-paging 沒有用

### Page size

---

- page size 的決定因素有以下幾點：
- Fragmentation
- Page table size
- Resolution ⇒ 解析度，若 size 太大，浪費；size 太小 page fault 提高
- I/O overhead
- Number if page fault
- Locality
- TLB size and effectiveness

### TLB Reach

---

- the mount of memory accessible from TLB
- 可以從 TLB 存取的記憶體大小
- TLB Reach = (TLB Size) * (Page Size)
## Chapter 11: Mass-Storage Structure
- Overview of Mass Storage Structure
- Transfer rate(傳遞速率)：資料在磁碟機與電腦中傳送的速度
- Positioning time(定位時間)：又稱隨機存取時間，等於seek time加上rotational latency
- Head crash(碰劃)：一種硬碟故障，硬碟讀寫頭和旋轉的磁碟片接觸時發生，磁碟表面產生不可恢復的損害
- Hard Disk Performanc
- 公式
- Latency based on spindle speed = 60 / RPM(Revolution Per Minute)
- Average latency = 1/2 latency
- Access Latency = Average access time = average seek time + average latency
- Average I/O time = average access time + (amount to transfer / transfer rate) + controller overhead
- 例子
- Suppose we want to transfer a 4KB block on a 7200 RPM disk with a 5ms average seek time, 1Gb/sec transfer rate, and a 0.1ms controller overhead. What is the Average I/O time for 4KB block?
- latency = $\frac{60}{7200}$
- Average latency = $\frac{1}{2}*\frac{60}{7200}$=$\frac{1}{240}$(s)
- Average access time = 5 + $\frac{1}{240}$*10^3^ ≈ 5 + 4.17 = 9.17(ms)
- Amount to transfer / Transfer rate = $\frac{4k}{\frac{1Gb}{8}}$ = $\frac{4*2^{10}}{\frac{1*2^{30}}{8}}$ = $\frac{4*2^{10}}{2^{27}}$ = $\frac{4*2^{10}}{2^{27}}$=$\frac{1}{2^{15}}$(s) ≈ 0.03(ms)
- Average I/O time = 9.17 + 0.03 + 0.1 = 9.21

# Reference
https://ithelp.ithome.com.tw/m/users/20112086/ironman/1851
https://ithelp.ithome.com.tw/users/20112132/ironman/1884