# 作業系統 Operating System 筆記
## Ch1 Introduction
作業系統(Operating system, OS)是管理電腦硬體與軟體資源的電腦程式，同時也是電腦系統的核心與基石。OS 主要有以下兩個功能：
1. 資源分配者
2. 監控使用者程式的執行，以防止不正常的運作造成對系統的危害

一個標準PC的作業系統應該提供以下的功能：
- 行程管理(Processing management)
- 記憶體管理(Memory management)
- 檔案系統(File system)
- 網路通訊(Networking)
- 安全機制(Security)
- 使用者介面(User interface)
- 驅動程式(Device drivers)

### 作業系統類別
#### 1. Mainframe Systems
最早的計算機之一，更好的可靠性與安全性，應用在醫院銀行等，由Batch演進到Time-sharing。
- Batch
OS 只是將控制權從一個程式轉移到下一個程式，缺點是一次只有一個程式且無法與使用者交互，CPU使用率低。
- Multi-programming
系統中存在多組行程同時(concurrent)執行，透過Spooling(Simultaneous Peripheral Operation On-Line)的機制讓CPU跟I/O時間重疊，提升 CPU 利用度(注意，不是並行執行(parallel))。
Multi-programming OS任務有Memory management、CPU scheduling and I/O system。
- Time-sharing
CPU在執行的時候頻繁的在跟device做交換，OS在程式間快速切換，每個程式執行幾個ms，time slot就換下一個程式。
Time-sharing OS任務有Virtual memory、File system、disk management、Process synchronization and deadlock。
#### 2. Computer-system architecture
- Desktop Systems
Personal computers (PC) – 計算機系統專用於單個用戶有GUI與許多I/O devices方便操作，像是Windows、MacOS、Unix、Linux，但是缺乏對用戶的文件和作業系統保護。
- Parallel Systems
也稱為 multiprocessor or tightly coupled system，多個CPU/核心緊密通訊，通常通過共享內存進行通信，優點是Throughput、Economical、Reliability。通常又可分為SMP與AMP。
- Symmetric multiprocessor system (SMP)
- 每個處理器運行相同的作業系統
- 最流行的多處理器架構
- 需要廣泛的同步來保護數據的完整性
- Asymmetric multiprocessor system (AMP)
- 每個處理器被分配一個特定的任務
- 一個Master CPU & 多個Slave CPU
- 常見於超大型系統中

從Processor可分為以下兩種：
- Multi-Core Processor：在同一個die上具有多個core的CPU，在chip上通訊更快，一個多核比多個單核工皓更低。
- Many-Core Processor：一個divice上有幾百個計算核心，像是Nvidia GPU，Intel Xeon Phi，TILE64等。

從Memory可分為以下兩種：
- Uniform Memory Access (UMA)：目前最常見的代表是對稱多處理器(SMP)，相同的處理器，內存訪問次數相等，最常見的架構。
- Non-Uniform Memory Access (NUMA)：通過物理連接多個SMP來實現，一個SMP可以直接訪問另一個SMP的內存，跨鏈接的內存訪問速度較慢。
- Distributed Systems
也稱為loosely coupled system，每個處理器都有本地的內存，透過I/O bus或網路相互通信，容易擴展大量節點像是Internet。
- Client-Server Distributed System：容易管理與分配資源，但是server會成為瓶頸與單一故障點。
- Peer-to-Peer Distributed System：每台機器在分佈式系統中的角色都是相同的(去中心化)，像是bitTorrent，Internet。
- Clustered Systems：集群計算機共享存儲並通過局域網 (LAN) 或更快的互連（例如 InfiniBand（高達 300Gb/s））緊密相連。
#### 3. Special-purpose Systems
- Real-Time Systems
- "Real-time"並不意味著速度，而是要keeping deadlines，保證響應和反應時間，Real-time又可以分為Soft real-time與Hard real-time。
Soft real-time requirements：不期望錯過deadline，但錯過也不嚴重，一個關鍵的real-time task獲得優先於其他任務，並保持該***優先級***直到它完成，例如多媒體串流。
Hard real-time requirements：錯過deadline會導致失敗，例如：核電站控制器，Hard real-time通常沒有Secondary storage，資料都存在short term memory或read-only memory (ROM)。
- Multimedia Systems
廣泛的應用程序，包括音頻和視頻文件，例如online TV
- Embedded Systems
移動裝置，通常內存較小，電池容量有限，處理器速度慢，顯示器較小。

### Computer system
- 用戶(User)：人、機器、其他computer。
- 應用程序(Application)：定義系統資源用於解決計算問題的方式。
- 作業系統(Operating System)：控制和協調硬件/資源的使用。
- 硬件(Hardware)：提供基本的計算資源(CPU、內存、I/O設備)。
#### Operating System的定義
- 資源分配器：管理和分配資源以確保效率和公平。
- 控製程序：控制用戶程序的執行和I/O設備的操作，防止計算機出錯和不當使用。
- 內核Kernel：一直運行的一個程序(其他都是系統/應用程序)。
#### Operating System的目標：
- 方便(使computer system易於使用和計算，適用於小型PC)。
- 效率(有效率使用電腦硬體，適用於大型、共享、多用戶系統)。
#### Operating System的重要性：
- 系統 API 是用戶應用程序和硬件之間的唯一接口，API是為通用目的而設計。
- OS code不允許任何錯誤，任何中斷（例如無效訪問）都會導致重啟。
- OS technology的擁有者控制著軟硬件產業(Wintel)。
- Operating systems和computer architecture相互影響。
#### Modern Operating Systems
- x86 platform：Linux，Windows
- Smartphone Mobile OS：iOS，Android
- Embedded OS：Embedded Linux，RTOS，Raspberry Pi，Xbox

### Computer-System Organization(計算機組織)
一個或多個CPU、設備控制器通過公共總線連接，提供對共享內存的訪問，並發執行CPU和競爭內存週期的設備。
每個device controller都有一個local buffers，I/O是從device到device controller的local buffers，CPU將數據從內存移動到device controller的local buffers。
#### I/O的操作有兩種
1. Busy/wait output
CPU不斷監控等待I/O，但是CPU在監控device時不能做其他工作，很難同時進行其他I/O。
2. Interrupt I/O
Interrupt允許device改變CPU的控制流，透過改變CPU的控制流在I/O與user process間切換。

### Interrupt
現代OS都是中斷驅動的，事件的發生由來自hardware或software的中斷發出信號。
- Hardware(signal)：可以隨時通過向 CPU 發送信號***signal***來觸發中斷。
- Software(trap)：可能會因錯誤（被零除或無效內存訪問）或用戶對作業系統服務的請求（系統調用）而觸發中斷，稱為**trap**。
中斷的常用功能
- 中斷一般通過中斷向量將控制轉移到中斷服務例程，中斷向量包含所有服務(即中斷處理程序)例程的地址(函數指針)。
- 中斷架構必須保存被中斷指令的地址。
- 在處理另一個中斷時禁止傳入中斷以防止丟失中斷。

### Storage-Device Hierarchy
存儲系統的結構(**速度**、成本、揮發性)，其中又可大致分為
- Main memory：CPU可以直接訪問的大型存儲介質，RAM(Random Access Memory)。
- Secondary storage：主存儲器的擴展，提供非揮發性的大存儲容量，例如Hard disk，tapes。

RAM: Random-Access Memory
- DRAM (Dynamic RAM)：主記憶體(Access Speed:>= 30ns)。
- SRAM (Static RAM)：CPU cache(Access Speed:10ns~30ns)。

Disk Mechanism：旋轉磁盤，並透過磁頭去去讀取(寫入)磁盤資料

Caching：使用中的資料暫時從較慢的存儲，複製到較快的存儲
>Coherency and Consistency Issue：更改register中的副本，使其與其他副本不一致
>- Single task accessing：沒有問題，總是使用Highest level copy。
>- Multi-task accessing：需要獲取最近的值。
>- Distributed system：Difficult b.c. copies are on different computers。

### Hardware Protection
#### 1.Dual-Mode Operation
- 共享系統資源需要OS保證一個不正確的程序不會導致其他程序的錯誤執行，提供硬件支持以區分至少兩種操作模式
1. User mode：代表User執行。
2. Monitor mode：也叫kernel mode或system mode，代表作業系統執行。
- hardware中加入Mode bit以指示當前模式的：kernel(0) or user(1)，當interrupt/trap或故障發生時，hardware切換到Monitor mode。
>Privileged instructions
>- Executed only in monitor mode
>- Requested by users (system calls)
#### 2. I/O Protection
- 所有I/O instructions都是Privileged instructions，任何I/O設備在user之間共享，必須確保user program永遠無法在monitor mode下獲得對computer的控制權。
#### 3. Memory Protection
- Memory Protection，保護中斷向量和中斷服務程序，還有數據訪問與被其他程序over-write。
HW support：兩個合法可使用地址的寄存器，超出定義範圍的內存受到保護
1. Base register：保存最小的合法物理內存地址。
2. Limit register：包含範圍的大小。
#### 4. CPU Protection
-防止user program不返回CPU控制權，造成陷入死循環或無法調用系統服務。
HW support：定時器Timer，在指定時間後interrupts computer，Timer在每個clock中遞減，當Timer達到值0時，發生interrupts。
>Timer常用於實現time sharing。
>Load-timer is a privileged instruction。

## Ch2 OS Structure

### OS Services
OS服務可大致分為以下這幾種
- User interface(用戶界面)
- Program Execution(程式執行)
- I/O operations(輸入輸出操作)
- File-system manipulation(文件系統操作)
- Communication(通訊)
- Error detection(錯誤檢測)
- Resource allocation(資源分配)
- Accounting(計數)
- Protection and security(保護和安全)
#### User interface
- CLI (Command Line Interface)
從用戶獲取命令並執行它，Shell(命令行解釋器，如CSHELL、BASH)。
- GUI (Graphic User Interface)
通常是滑鼠、鍵盤和螢幕，圖標代表文件、程序、動作等，界面中對像上的各種鼠標按鈕會導致各種操作。
#### Communication
可以使用消息傳遞或共享內存進行通信。

### OS-Application Interface
#### System calls
運行程序的作業系統接口，請求作業系統服務，通過軟件中斷向內核發出的明確請求，通常是組合語言。
- 進程控制——中止、創建、終止進程分配/釋放內存
- 文件管理——創建、刪除、打開、關閉文件
- 設備管理——讀、寫、重定位設備
- 信息維護——獲取時間或日期
- 通訊—發送接收信息
#### API(Application Program Interface)
用戶主要針對API進行編程而不是system call，通常由language libraries實現，例如 C Library，API 調用可能涉及零個或多個系統調用。
>Both malloc() and free() use system call brk()
>Math API functions, such as abs(), don’t need to involve system call

三個最常見的API:
1. Win32 API for Windows
2. POSIX API for POSIX-based systems (including virtually all versions of UNIX, Linux, and Mac OS X)
3. Java API for the Java virtual machine (JVM)
#### Why use API?
- 簡單(API是為應用程序而設計的)。
- 可移植性(API是統一定義的接口)。
- 效率(並非所有功能都需要OS services或涉及kernel)。
#### System Calls傳遞參數
System Calls傳遞參數通常使用以下三種方法，在運行程式和作業系統之間傳遞參數。
1. 在寄存器中傳遞參數。
2. 將參數存儲在memory中的一個table中，table的address作為參數傳遞到一個寄存器中。
3. 程式將參數push(store)入stack ，作業系統將參數pop出stack。

### OS Structure
從用戶角度，作業系統應該易於使用和學習，以及可靠、安全和快速。
從系統角度，作業系統應該易於設計、實施和維護，並且可靠、無錯誤且高效。
#### 1. Simple OS Architecture
只有一層或兩層代碼，缺點:不安全，難以增強改善。
#### 2. Layered OS Architecture
下層獨立於上層，第N層只能訪問第0~(N-1)層提供的服務。優點式更容易調試與維護，缺點是效率較低，難以定義層。
#### 3. Microkernel OS
盡可能多地從kernel移動到userspace像是一個program，通過消息傳遞提供通信，容易擴展和移植。缺點是效能更差，因為所有的動作都要再透過kernel。

#### 4. Modular OS Structure
大多數現代作業系統都實現了kernel modules，與Microkernel不同之處在於Modular OS全部都在kernel space。
- 使用物件導向的方法(object-oriented approach)。
- 每個核心組件都是獨立的。
- 每個模組都通過已知接口與其他模組通訊。
- 每一個模組都可以根據需要在kernel中掛載。
>kernel module實作
>http://www.linuxchix.org/content/courses/kernel_hacking/lesson8
>http://en.wikibooks.org/wiki/The_Linux_Kernel/Modules
>https://www.thc.org/papers/LKM_HACKING.html
#### 5. Virtual Machine
虛擬機採用分層方法得出其邏輯結論，它將hardware和operating system kernel視為硬體。虛擬機提供與底層bare hardware相同的接口，為每個process提供底層計算機的(virtual) copy。
由於VM是執行在user space，當遇到無效的instruction會透過interrupt去call底層的kernel space執行，而目前有hardware support的硬體是透過加一個bit去判斷kernel mode,user mode,VM mode。
>虛擬機的困難點在於"critical instruction"難以處理。

VM的用處:
- 提供對系統資源的完整保護。
- 解決系統兼容性問題的手段。
- 作業系統研究和開發的完美工具。
- 一種提高雲計算資源利用率的方法。
- 資安作滲透測試。

Vmware (Full Virtualization)
以user mode運行，作為作業系統之上的應用程序，虛擬機認為它們是在bare hardware上運行，但實際上是在user-level應用程序中運行。

Para-virtualization: Xen
向guest提供與guest系統相似但不相同的系統(必須修改guest)，只有一半被虛擬化。在container (zone)processes中認為它們是系統上唯一的進程，Hardware被虛擬化(只安裝一個kernel)。
#### 6. Java Virtual Machine
已編譯的 Java 程式是由Java Virtual Machine(JVM)執行與平台無關的bytecodes，Just-In-Time(JIT)編譯器可提高性能。
>JVM consists of
> - class loader
> - class verifier
> - runtime interpreter

## Ch3 Processes Concept

### Process Concept
Process與Program最主要的差異，在於是否處於執行狀態
- Program (Passive entity) 只是儲存於"disk"中等待被執行的程式碼
- Process (Active entity) 則是位於記憶體中的正在被執行的"Program"

一個"Process"由以下內容組成：
Code segment：也稱text section，將 program (已編譯為instruction) 讀到記憶體中，等待被 CPU fetch 並執行
Data section：global variables
Stack：temporary local variables and functions(方便使用後直接pop掉)
Heap：dynamic allocated variables or classes
Current Activity：管理 Process 的 Meta data，如Program counter, Register Contents
A set of associated resources：相關資源的 set，如 Open file handlers (檔案的開啟、或是跟 OS 要某些硬體的控制權)
#### 1. Threads
Threads 又稱為 Lightweight process，是使用 CPU 的最小單位，同 Process 的 Threads 有共享的記憶體空間。在 Parent Process 創造 Threads 時就會 allocate ，因此省去在空間管理及處理上的執行動作。
- 同Process中，Threads共用以下內容
- code section
- data section
- OS resources (e.g. open files and signals)
- 但以下部份各自獨立
- stack
- register set
- thread ID
- program counter
#### 2. Process State
Process 在其生命週期中，共有 5 個狀態
- New：當 process 被創建時，將 code 讀到記憶體中，並將前述記憶體狀態初始化
- Ready： Process 競爭的資源是 CPU 的核心，管理的方式為佇列 (Queue)，在等待被執行的階段，會被放在佇列當中，此狀態稱為"Ready"
- Running：被 CPU 排程選到，執行 instructions。OS 為了確保主控權，一段時間就會將 CPU switch 給 scheduler 而"打斷(interrupt)"程序
- Waiting：有些指令不會直接使用 CPU (如 I/O)，因為不需要 CPU ，又需等待某些指令完成，所以進入 Waiting 狀態，待完成後重新放回 Ready
- Terminated：Process 完成執行，釋放資源給 OS。
#### 3. Process Control Block (PCB)
User 創建 Process 後，OS 會自動建立 PCB 來做管理。
我們說將 Process 放到佇列當中，指得是將 Process 的 pointer 放到佇列中，而非記憶體空間，使用的資料結構為"Linked list"。PCB 包含以下內容：
- Process state
- Program counter
- CPU registers
此外還有：
- CPU scheduling information(e.g. priority)
- memory management information(e.g. base/limit register):只有 process 在執行時才會把這兩個值從 memory load 進 CPU 的 register。
- I/O status/information
- accounting information
#### 4. Context Switch
CPU 一次只能執行一個 Process，要切換給另一個 Process 時，必須將舊 Process 的資訊 (e.g. PCB) 儲存起來，並載入新 Process 的資訊，這個動作稱為 「Context Switch」。
CPU 完整切換的流程如下:
1. 執行 P0
2. P0 被打斷讓出 CPU ，此時處於 idle 狀態
3. 進行 Context Switch
4. 將 P0 的狀態存於 PCB
5. 並讀取 P1 的 PCB。
6. 完成 Context Switch
7. 執行 P1

Context switch 的過程中， CPU 沒有執行任何 instrunction，因此 Context Switch 其實是 overhead，浪費 CPU 的資源。但為了 CPU sharing 及 time sharing，Context switch 無法避免地經常發生，所以我們只能盡可能縮短時間：
- memory speed
- number of registers：越少則存取的次數降低，但現在的系統中為了更快速的計算，register 數量是變多的
- special instructions：合併 load & save PCB 的 instruction，讓 CPU 一次做完
- hardware support：multiple sets of registers，一次記住多個 Process 的狀態，可以快速的在 registers 間進行切換，無須透過 memory access

### Process Scheduling
- Multiprogramming：多工處理， CPU 可以執行多個 Process，以最大化利用 CPU
- Time sharing：分時系統，為一種資源的共享方式，系統可以頻繁地進行 Context Switch，讓多個 User 可以同時使用 Program
由於 Process 共享 CPU，使用的先後順序就是由 scheduler 來決定。
#### 1. Process Scheduling Queues
- Job queue (New State)： 系統中所有的 Process
- Ready queue (Ready State)： 在主記憶體中正在及等待執行的 Process
- Device queue (Wait State)： 等待 I/O 處理的 Process

>- 會有一個 ready queue for CPU，很多個 I/O 的 waiting queue，看是哪個 device 或 disk，會有自己獨立的 queue，利用 PCB 中的 pointer 串起來
>- queue 之間的 tail 和 head 都有串起來，比較容易做 reordering，不同的 Scheduling Algorithm，可能會 dynamically 決定 ordering (run time做調整)，需要其他 pointer 串起來，變成雙向或把前、後記起來
>- ready queue 可能會有 level 1、level 2、level 3，取決於 Scheduling Algorithm 自身管理方式

- Ready queue 中的 process 會等待被 load 進 CPU
- Waiting queue 發生的原因有很多種，OS 會有專門的 queue 去處理這些 event 的發生：
- I/O request：若自己發出 I/O request，這時候會被放到 I/O queue，等到做完 I/O，會 throw 一個 interrupt 回來，OS就會把它放回 ready queue，e.g. call printf()，會被放到 monitor queue
- time slice expired：timer的 alarm 被 fire，會從 CPU(running state) 直接回到 ready queue，這是為了確保主控權可以回到OS的手上
- fork a child：process 可以自己 create process，在Linux中，create process的動作叫做"fork"有兩種實做方式
1. 可能自己繼續執行讓children等Parent執行完在執行
2. 先讓children先執行，原來的Parent process會被放在waiting queue，等到Children執行完，才可以再回到ready queue執行
- wait for an interrupt：e.g. call sleep() 的 system call，call sleep() 的 process 會被放在 waiting queue 裡，等著 interrupt 的發生，才可以回到 ready queue 裡面
#### 2. Schedulers
Scheduling 分為 CPU 及 Job Scheduling

- CPU Scheduling : 因為 time sharing 的原因，發生頻率非常高，又稱為 Short-term scheduler。CPU Scheduler 會選擇該被執行的 Process 並 Load 到 CPU 當中，從"Ready State" 轉換成 "Run State"
- Job Scheduling : 可能幾秒或幾分鐘才需要scheduling，又稱為 Long-term scheduler，通常是使用者人為觸發，新的程式被執行，產生程序時才需要被排程，從 "New State" 轉換成 "Ready State"
- Medium-term : 跟虛擬記憶體結合產生的一種 scheduler，因為 memory 空間是有限的，有時會將 disk 的空間拿來使用，當 memory 不夠時，就會將部份 Process 從 memory 踢回 disk，這個動作即由 Medium-term scheduler 來處理，由 "Ready state" 轉換為 "Wait state"
#### 3. Long-Term Scheduler
- 控制在記憶體中 Process 的數量 (degree of multi-programming)
- 當 degree 太低時， CPU 有很多的時間在 idle
- 當 degree 太高時，會發生 Thrashing，有太多的 Process 在爭搶有限的 memory，導致 Process 一直在 memory 跟 disk 之間 swap，不斷的做 I/O
- 因我們希望 CPU 跟 I/O 執行的時間差不多，負載盡可能平衡而最大化系統效能，所以 Process 要能夠在 CPU-Bound & I/O-Bound 良好的混合
- 在 UNIX/NT 系統中，並沒有 Long-Term Scheduler
直接將 Process 放到 short-term scheduler 中 (現今電腦的記憶體空間通常是足夠的)
Multipropramming degree 受硬體限制 (e.g. # of terminals) 或著由使用者自己調整
#### 4. Short-Term Scheduler
- 執行頻率很高，大約 100ms 執行一次
- 由演算法來縮短每個 Process 的等待時間
- 因為效率要高，演算法也不能太過複雜，避免 CPU overhead 過高
overhead = (time of pick) / (time of execution + time of pick)
#### 5. Medium-Term Scheduler
因現代 memory 空間的增長以及虛擬記憶體的觀念引入，過往由 Long-Term Schduler 處理的動作多改由 Medium-Term Schduler 執行
- swap out : 將 Process 由 memory 搬到 disk 中
- swap in : 將 Process 由 disk 搬到 memory 中
- propose : 改善 Process mix / 減少記憶體中的 Process 數量，降低 degree釋放記憶體空間

### Operations on Processes
回到 programmer 及 user 角度，我們到底如何跟 Process 溝通
#### 1. Tree of Processes
- 無論什麼作業系統， Processes 一定可以畫成如下的樹狀結構
- 每一個 Process 由 unique processor identifier (pid) 識別
#### 2. Process Creation
- 資源之間的關聯性可能如下
- Process 的 Parent 及 Child 共享資源
- Child Process 共享部份 Parent 的資源
- Parent 及 Child 完全不分享資訊
- 兩種可能的執行方式
- Parent 及 Children 同時執行
- Parent 等到 Children 結束後才執行
- 兩種可能的記憶體空間
- Child 為 Parent 的複製 (執行碼、counter 等與 Parent 完全一樣)，透過 sharing variable 溝通 (address 不同)
- 將特定的 program 丟進 Child 的 code section，重設 counter，讓 Child 變成完全不同狀態的 Process，透過 message passing 溝通
#### 3. UNIX/Linux Process Creation
[Reference](https://hackmd.io/@Chang-Chia-Chi/MIT6S081_XV6_and_Unix#find-moderate)
- fork system call (Create Process)
- 創建新的 (child) process
- 該 process 複製其 parent 的記憶體空間
- Child 與 Parent 在 fork 後同時執行 (execution concurrently)
- Child 在 fork 的回傳值為 0
- Parent 在 fork 的回傳值為 Child process 的 PID
- execlp system call (Reset Process)
- 先創建 Process 及 OS 要記憶體空間，並註冊新的 PID
- 將新的 binary file 讀入記憶體，並將內容如變數 (heap、stack)、counter 等全部清空 (reset) ，等於讓新的 Child Process 執行不同的程式
- wait system call
- 因 Child & Parent 在 Unix 中是 concurrent 執行，若要控制執行的順序，必須用 wait system call，強制 parent 直到其中一個 Child 的 process 完成後才執行
- Memory space of fork()
- 舊的實作 Child 為 Parent 的完整複製
- 新的實作使用 copy-on-wirte 技術，在 Run time 過程中，儲存 Child 的與 Parent 的不同處 (A’s Child 在執行過程中會慢慢增長)
- 若 call execlp，則會產生完全獨立的 Child Process

以下為 UNIX/Linux Process Creation 的範例程式碼
以下範例簡單示意 fork 的特性， Child Process 會保存 fork() 呼叫當下 Parent Process 的狀態。注意如果過程中呼叫 execlp ，則該分支會斷掉，樹不會繼續往下生長
#### 4. Process Termination
當 Process 執行到最後一個指令或是呼叫 exit()，都會中止程序

- 該 Process 所有相關資源，如記憶體空間 (physical, virtual)、I/O buffer、open files 等都會清空並將資源還給 OS
- Parent 可利用 PID(abort) 來中止特定 Child Process
- 當 Child 配置太多記憶體
- Child Process 執行的任務不再需要
- Cascading termination：因為是樹狀結構，所以當 Parent 被中止，則 Child Process 也會被中止，這也是為什麼 "ctrl+C" 可以強制停止 Process，因為其他程序都是由 console 程序創建，更進階的是呼叫 "kill"，但需要管理者權限

### Interprocess Communication
- 定義：在多個 Process (或 Threads) 間溝通的機制
- 目的：
- 資訊的共享
- 加快計算速度 (not always true)
- 便利性 (performs several tasks at one time)
- modularity (e.g. [micro-kernel](https://en.wikipedia.org/wiki/Microkernel))

Communication Methods
要做到 IPC 用 memory 分別有幾種方式
- Shared memory：共用記憶體空間
- 需要小心處理 synchronization
- 利用 memory address 實作，好處就是快
- 透過 memory 的 address 存取資料
- Message passing：透過 memory 的 copy，網路或跨電腦的程式通常都是以這種作法溝通
- 沒有 conflict 的問題，但若資料小，用這個方法的話可以省去 share memory 的 lock 之類的額外資源消耗，反而會略快（且不用在意 sync 的問題）
- 使用 send/recv message
- 以 system call 實作，通常較慢
- Sockets
- 透過 IP & Port 來 identify 使用者，port number 指得就是 Process
- 藉由未結構化的位元資料來溝通 (unstructed stream of bytes)
- 會有 client & server
- server 要先打開 client 才能連
- client 進行 connect 之後，就可以盡情 read / write
- 補充：server 在 accept 之後，會動態開 thread，如此才能一次處理多個 request
- [Remote Procedure Calls (RPC)](https://en.wikipedia.org/wiki/Remote_procedure_call)
- 可以呼叫其他的 Process 甚至其他電腦的 Process
- 參數以及回傳值以 message 傳遞
- 與 socket 不同，傳輸的資料是有 data type 的
- Library 通常會有 stubs，在 client 端和 server 端會各有一隻小程式，（server 端的叫 skeleton）會負責 implement 細節
- 其實通常下面也可能用 socket，只是幫 programmer 包起來而已
- [parameter mashaling](https://en.wikipedia.org/wiki/Marshalling_(computer_science)): 把 params 包進 message 且嚴謹的管理。要把兩台電腦串在一起其實有許多細節要處理，RPC 就要負責幫使用者把這些繁瑣的事情解決掉
> In distributed computing, a remote procedure call (RPC) is when a computer program causes a procedure (subroutine) to execute in a different address space (commonly on another computer on a shared network), which is coded as if it were a normal (local) procedure call, without the programmer explicitly coding the details for the remote interaction.

#### 1. Shared Memory
Process 要能夠 …
- 創建 shared memory 的區塊
- 共享的記憶體區塊通常會在創建 shared memory 的 Process 的附近
- 透過這個 shared memory 溝通的 Processes，要告知 OS 說我要共用這塊記憶體位置 (attach)
- 資料格式為 bytes，由 process 自行定義， OS 不處理
- Processes 不能同時對同一塊記憶體做讀寫的動作
Consumer & Producer Problem
- 兩個 Process 共用一塊 Buffer 記憶體
- Buffer 是大小為 B 的 circular array
- 因為 Buffer 有空間限制，必須有以下資訊來控制
- next free: in
- first available: out
- empty: in = out (out 拿光)
- full: (in + 1) % B = out
- 這邊為了 sync，避免無法判斷 in = out 時是 empty 還是 full，必須使用 in+1 留一個空格。之後會提到以 locking 的方式使用所有的 Buffer 空間
#### 2. Message Passing
- 讓 Process 之間可以溝通且同步
- IPC 一般來說 OS 會提供兩種操作：Send/Receive 的方式達到同步化，並在背後做各種 memory copy 的處理
- Send(message)
- Receive(message)
- Message system : Process 不使用 shared variable 達到溝通的目的
- 為了 Process 間的溝通
- 必須建立 communication link
- 藉由 Send/Receive 交換資訊
- 實作 communication link 的方式
- physical (e.g. shared memory, HW bus or network)
- logical (e.g. logical properties, programmer 在意的事情)
- communication 是否有方向性
- 角色是否相對
- Blocking / non-blocking：傳輸行為執行完成才會回傳，或不管對方是否有收到立刻回傳
- send by copy or by reference
- 固定大小 / 可變大小 的 message

Direct communication (如打電話)
- Processes 必須要有對方的名稱
- Send(P, message) : 傳輸 message 給 Process P
- Receive(Q, message) : 從 Process Q 接收 message
- communication link 的特性
- Links 通常為自動建立
- links & processes 為一對一的關係
- link 可以是單向，但通常是雙向
- Direct communicatioｎ　最大的缺點是關係唯一對一，且連線的對象無法變更，除非重新建立，所以比較難以模組化 (modularity)

Indirect communication (如寄電子郵件)
- Messsages 由 mailboxes(或稱為 port) 導向及接受
- 每一個 mailbox 有自己的 ID
- Processes 若共享 mailbox 則可以互相溝通
- Send(A, message)：沒有指定接收者，單純將 message 放到 mailbox A
- Receive(A, message)：沒有指定傳送者，單純將 message 由 mailbox A 接收
- communication link 的特性
- Link 必須由 programmer 建立，透過 Process 間共享 mailbox 來溝通
- 因為沒有指定接收者/傳送者，所以 Link 與 Process 間為 Many-to-Many
- Link 可以為單向或雙向
- Mailbox 可以由 Process 或 OS 擁有，通常處理 message 的是另一隻程式
- Mailbox Sharing
- 因為可能同時有很多人去讀取 message，但理論上一個 message 應該只能有一個人拿到，有以下幾種解決方法：
- Link 只允許兩個 Process (一個 send 及一個 receive，等同 direct，最糟的解法)
- 利用 lock 一次只允許一個 Process 拿取 message
- 讓 mailbox 自行決定誰來接收。receiver 會先提出要求， mailbox 決定接收者後， sender 會被告知 receiver 是誰，再告知 receiver 來取得 message

Synchronization
- Message passing 可以為 blocking (synchronous）或是 non-blocking (asynchronous)
- Blocking send: sender 被 blocked 直到 message 被 receiver 或 mailbox 接收才 return
- Nonblocking send: sender 送出 message 之後繼續執行
- Blocking receive: receiver 被 blocked 直到皆收到 message 才 return
- Nonblocking receive:若 sender 先 call，則 receiver 正常接收 message ; 若 sender 前 call，則 receiver 只會收到之前的值。所以 function call 通常還會 return 一個 token ，來確定是否真的收到 message
- Buffer implementation : non-blocking 通常透過 buffer 實作，只要 buffer 空間沒有滿，就可以一直 send ; 對 receiver 來說就是一直接收，不管 buffer 有沒有東西
- Zero capacity ： 通常是 blocking send/receive
- Bounded capacity ： 若 buffer 滿了， sender 會被 blocked，或是 return 一個 error
- Unbounded capacity ： 一直送直到系統滿了為止
#### 3. Socket
socket只負責建立channel，passing由programmer負責。
- server端先開一個socket，
- bind到一個port，OS才知道哪個人要用這個port做溝通
- server要先listen，等人進來
- client 開socket，然後connect過去server
- server等到有人就accept，建立兩邊通訊
- 建立起來就可以read，write
- 結束後兩端可以選擇close，server close後就沒人可以連進去
>大部分web server或是socket programming，都是設計可以讓許多人連線，如果server是single thread，就只能handle一個user，所以實際上accept後，server side會去creat一個thread(動態建立)。
#### 4. Remote Procedure Calls
socket只能傳bytes，RDC能夠傳struct，類似透過網路remote的functon call。
RDC有stubs在client與server運行，幫忙處理parmeter，把東西package跟unpackage，底層再透過socket傳輸。
RDC可以跨電腦(eg.big/small endian的問題，32跟64位元int定義長度不同)，marshaling需要處理不同平台的問題；如果要pass pointer大部分的RDC是不支援的，因為pointer指向可能會用到的memory都要copy。

## Ch8 Memory Management

### Background
- 主記憶體和暫存器為唯二 CPU 可以直接存取資料的地方
- Processes 在硬碟中等待被讀入記憶體中及被執行
- 多個 program 被讀入記憶體中可以改進資源使用率以及反應時間
- Process 在執行期間有可能在硬碟及記憶體之間移動
#### How to refer memory in a program? – Address Binding
- Compile Time
程式中的資料、參數等必須要有對應的記憶體位置，早期的作法是在編譯期間，就決定要放在哪裡，送進 CPU 時 CPU 就知道該去哪裡存取資料

- Compiler 會將組合語言轉換成實際的記憶體位置(absolute code)
- 若起始地址變更(可能該地址被其他 process 占住)，則需要重新編譯 (recompile)，等於要關閉並重新執行
- ex: MS-DOS .COM format
- Load Time
- Compiler 不會決定實際的記憶體地址，而是會留一個變數(Base Register)，給出相對位置。程式讀取後(loader，loader 一般假設程式是重新執行，因此會執行非常多動作，如 process 的 control block、記憶體初始化、data structure 的創建等，也就是 program 變成 process 的過程)，才透過該變數決定真正的地址(relocatable code)
- 若 run time 起始地址變更，則需要重新讀取 (reload)
- Execution Time
- Compiler 將組合語言轉換成 logical-address(i.e. virtual-address)
- 雖然看似 compile time 決定實際地址，但這其實是個虛擬的地址。
- CPU 以為記憶體地址就是 compiler 轉換的位置，但送要求去記憶體存取資料時，中間還有一個硬體單元 MMU(i.e. Memory-Management-Unit, MMU)，會做記憶體地址的轉換，導向正確的實際地址
- MMU 將虛擬地址 map 為實際地址
- 由 logical-address 加上 relocation register 產生實際地址
- MMU 可以看成 OS 的一部分，但因為使用頻率非常高，所以一般用硬體來實作
- 多數 general-purpose 的作業系統使用這個方法

- Logical vs. Physical Address
- Logical address 為 CPU 送出的地址，也就是 virtual address
- Physical address 為記憶體看到的真實地址
- Compile time & Load time address binding 的方式，logical address = physical address
- Execution-time address binding 的方式，logical address != physical
- User program(Programming, Compiling…etc) 只管 "logical" address，永遠不會看到 "physical" address
### How to load a program into memory? – static/dynamic loading and linking
#### Dynamica Loading
- 不會將整個程式 load 到記憶體，子程式在 function call 的時候才 load
- 這樣做有更好的記憶體空間使用
- 未用到 routine 不會被載入記憶體
- 在大量程式碼使用率較低時(如 error handling code)特別有用
- OS 提供功能，但不會決定 routine 是 dynamic 或 static loading，而是由使用者決定(library, API)
- 在 C 語言中使用 Dynamic Loading 的範例，當呼叫 ``` printf("%f\n", (*cosine)(2.0)) ```時，``` cosine ```才會讀到記憶體中。現在 programmer 使用 Dynamic Loading 常常是希望在 run time 決定該使用哪個函式。
#### Static Linking
- 函式庫透過 loader 被結合進 program 的 image 當中，compile 的時候，將函式庫加入程式碼
- 每一個用到函式庫的 program 都有一份，浪費記憶體資源，但執行比較快
- 即便改用 Static Linking 加上 Dynamic Loading，因為函式庫仍然需要，因此無法解決程式碼重複複製的問題
#### Dynamic Linking
- Dynamic Linking 在 run time 才去找連結
- 因此只需要一份 library 在記憶體當中
- OS 在 program 中加入 stub，call stub 的時候會向 OS 確認 library 是否在記憶體中
- stub call --> 找 referred lib 是否在 memory 中，沒有的話則 Load 進來 --> 將其位址替換掉，之後就不用經過 stub(relocation)
- 因為在 run time 時期才找函式庫，執行速度較慢
在 windows 中為了系統效能，是編譯成 DLL(Dynamic link library)
### How to move a program between mem. & disk? – Swap
- Process 可以從記憶體中 swap 到 backing store，稍後再 swap 回記憶體中執行
- virtual memory 及 mid-term scheduler 使用
- backing store 是與檔案系統(file system)分離的一塊硬碟空間，透過 OS 的 MMU 直接管理
- 為何需要 Swap
- 釋放 memory space
- 讓重要性較低的 process roll out，roll in 重要性較高的 process
- swap back memory location
- 若 binding address 是在編譯或 load 時期決定，則 swap 回去的記憶體位置要相同
- 若 binding address 是在 run time 動態決定，則 swap 回去的記憶體位置可以不同
- 程序被 swap 前， OS 會確認是否是閒置的(idle)，除 CPU 執行外，也不能執行 I/O
- 若想 swap 在 I/O pending 的 process，有以下解法：
- 乾脆不要 swap 的 I/O pending 的 process
- 做完的 I/O 先copy 資料到 OS buffers(memory space 不屬於任何 user process)，就能把 process swap 出去，swap 回來時，只要 OS buffer 中的資料複製到 process 的 buffer 即可
- swap 主要時間花在資料的傳輸，transfer time 與資料傳輸的大小成正比，該如何決定被 swap 的 process 非常重要，詳見 CH9 - virtual memory

### Contiguous Memory Allocation
相關資料 [CS:APP Malloc Lab 解題筆記](https://hackmd.io/@Chang-Chia-Chi/r13xrF0Vt)
#### Memory Allocation
- Fixed-partition allocation:
- 每個 process 讀進一個 fixed-size 的 partition
- Multi-programming 的程度由 partition 的數量決定
- Variable-size partition (Multiple Partition)
- Hole 定義為一塊連續的記憶體位置
- 不同大小的 Holes 散布在記憶體當中
- 當有 process 抵達，會被 allocate 在一個夠大的 hole 裡頭
- OS 會理 in-use 及 free 的 hole 的資訊
- 一個被釋放的 hole 能夠跟其他 hole 合併成一個更大的 hole
#### Dynamic Storage Allocation Problem
- 問題：如何從一串 free holes 中找出符合大小 n 要求的 hole
- 解法：
- First fit - 1st 符合的 hole 就直接配置
- Best fit - 配置大小最剛好的 hole
- 可能要搜尋整個 hole list
- Worst fit - 配置最大的 hole
- 可能要搜尋整個 hole list
- First fit and Best fit 無論在速度或空間使用上都比 Worst fit 好
#### Fragmentation
- External fragmentation (frag space 在 process 外)
- 全部的 free memory space 是足夠滿足需求的，但卻不是連續的
- 發生在 variable-size allocation
- 解法： Compaction
- 將記憶體空間做 shuffle，在 execution time 讓 free memory 結合成一整塊
- 只有 binding address 在 run time 決定才能使用
### Non-Contiguous Memory Allocation — Paging
相關資料 [MIT6.s081 Lab: page tables](https://hackmd.io/@Chang-Chia-Chi/rkPuUJVaY)
#### Paging Concept
- Method:
- 將 physical memory 切成 fixed-sized blocks 稱為 frames
- 將 logical address space 切成一樣大小的 blocks 稱為 pages
- 為了要 run 一個有 n pages 的 program，需要找 n 個 free frames 並載入 program
- OS 會持續追蹤 free frames，以 page table 建立 logical to physical address 的轉換關係
- Benefit:
- 允許 process 的 physical-address space 可以是不連續的
- 避免 external fragmentation
- 盡可能降低 internal fragmentation
- 提供 shared memory/pages
#### Page Table
- 每一個 entry 對應到在 physical memory 中的 page 的 base address
- 每一個 process 有一個 page table，由 OS 直接進行管理
- Page table 只包含 process 擁有的 pages
- process 無法存取不是其 space 的記憶體地址
#### Address Translation Scheme
- Logical address 分成兩部份
- Page number ( p )
- 為 page table 的 key 值，對應 value 為 page 在 physical memory 的 base address
- N bits 代表一個 process 最多可配置 2^N 個 pages 的記憶體，限制住 programm 可 allocate 的大小 (例如 32-bits 的電腦，一個 program 最多 allocate 4GB 左右的空間)
- Page offset ( d )
- 與 base address 結合定義 physical memory address
- N bits 代表 page size 為 2^N
- 由 page number 找出放在第幾個 page，再加上 page offset 得到實際的記憶體位置
- physical address = page base address + page offset
- 如果 page size 為 1kb(2^10) 且 page 2 map 到 frame 5
- 若 logical address 為 13 bits (p=2, d=20)，則 physical address 為？
- 5 * 1kB + 20 = 1,010,000,000,000 + 0,000,010,100 = 1,010,000,010,100
- pages 的總數量不一定和 frames 的總數量相同
- pages 的總數量決定 process 的 logical memory size
- frames 的總數量則與 physical memory 大小有關
- 例如： 給定一個 32-bits 的 logical address，36 bits 的 physical address 以及 4KB 的 page size，這代表？
- page table size = 2^32 / 2^12 = 2^20 個 entries
- Max program memory: 2^32 = 4GB
- Total physical memory size = 2^36 = 64GB
- Number of bits for page number = 2^20 pages -> 20 bits
- Number of bits for frame number = 2^24 frames -> 24 bits
- Number of bits for page offset = 4KB page size = 2^12 bytes -> 12 bits
#### Free Frames
OS 用 free frame list 記下所有 free 的 frame
#### Page/Frame Size
- page & frame size 由 hardware 定義
- 通常是 2 的冪次
- 通常從 512 bytes 到 16 MB/page
- 最常見的是 4KB/8KB(32bit -> 4KB；64bit -> 8KB)
- Internal fragmentation?
- Larger page size -> 更多空間的浪費
- 但因為以下原因， page sizes 有變大的趨勢
- 記憶體、process、data sets 變得更大， process 變大代表要 access 的 page 也越多，若 page size 太小一來找尋的次數增加，二來因為 page 太多很可能部份的 page 放在 disk 中，降低執行及讀取速度
- 更好的 I/O performance(during page fault)
- page table 可以比較小
#### Page Summary
- 使用者看到的是連續性的記憶體，但實際上是分散的
- OS 為每個 process 維持一個 page table
- OS 維持 frame table 管理 physical memory
- 每個 frame 有自己的 entry
- 表示 frame 是 free 還是 allocated
- entry 記 " process id " 和 " page number "
#### Implementation of Page Table
- Page table 保存在記憶體中
- 因為做 translate 的為 MMU，而 MMU 是硬體單元，所以 Page table 在記憶體中的位置會存在 Page-table base register (PTBR)
- 記憶 Page table 在記憶體的位置
- PTBR value 存在 Process Control Block 裡頭(PCB)
- 在 Context switch 時更新 PTBR value (除了 CPU 的 register，MMU 的 register 也要重新 load)
- 每一次讀取記憶體實際上動作有兩步
- 第一步先找到 Page Table，mapping 後才到真實的記憶體地址存取資料
- 兩步讀取的動作可以由 Translation Look-aside Buffers (TLB) 解決，簡單來說是一個 cache，若 cache hit，則可以縮短為 1 步，以 Asscociative Memory 實作
#### Asscociative Memory
- Associative Memory 為硬體，所有的 memory entires 可以同時被讀取 (查詢為 O(1))
- 每一個 entry 對應一個 associative register
- 但 entries 的數量是有限制的，一般來說是 64~1024 左右
#### Translation Look-aside Buffer (TLB)
- 由 Associative Memory 組成，是硬體單元
- page table 的快取被所有的 process 共享
- Context switch 後，因為 process 不同，page table 也不同，一般會 flush 整個 TLB; 另一個解法是在 TLB entry 增加 PID 的欄位，同時符合 page number 及 PID 才叫做 hit (address-space identifiers(ASIDs))
- 因為 context switch 後 TLB 被清空，等於剛開始記憶體地址都要兩步才能取得，是 context switch 拖慢效能的主要原因
#### Effective Memory-Access Time
- 20ns for TLB search
- 100 ns for memory access
- Effective Memory-Access Time (EMAT)
- 假設 70% TLB hit-ratio: EMAT = 0.7x(20+100) + (1-0.7)x(20+100+100) = 150 ns
- 假設 98% TLB hit-ratio: EMAT = 0.98x120 + 0.02x220 = 122 ns
#### Memory Protection
- page table 中，每一個 page 都有 protection bit ，表示 “唯讀” 或 “可讀寫”
- valid-invalid bit
- Valid: page/frame 在 process 的 logical address space，process 可以讀取
- Invalid: page/frame 不在 process 的 logical address space ，禁止 process 存取
- 早期會先創建固定大小的 page table，因為 program 會長，有可能目前 page 的數量少於 page table 的大小，若此時有 pointer 不小心指到該處，就會報 segmentation fault
- 缺點是可能很多 entry 沒有用到 -> 使用 page table length register (PTLR)，動態變更 page table 的大小。
- program 配置記憶體以 byte 為單位，而 valid-invalid bit 以 page 為單位，因此需要 memory limit register 紀錄 program 真正使用的記憶體空間，限制無效的存取
#### Shared Pages
- 允許 page 在不同 processes 間共享相同的 Reentrant code(read only)
- Reentrant code (Pure code)
- 在執行期間不會改變
- 如 text editors, compilers, web servers, etc
- 在 physical memory 中只需要保存一份 shared code
- Process 保有自己的 private data 以及 code
- 數個 virtual address map 到相同的 physical address
#### Page Table Memory Structure
- Page table 有可能很大而且難以存取
- 4GB (2^32) logical address space with 4KB (2^12) page
- 要有 1 million(2^20) page table entry
- 若一個 entry 4 bytes，則 page table 要 4MB，又因為 page table　是給 MMU 讀取的，MMU 沒有 address translation，所以這 4MB 的空間必須連續，但 physical address 通常很難找到 4MB 的連續空間
- 需要將 page table 切分成數個較小的 page tables，最好在一個 page size 大小(4KB) 的範圍內
- 或著將 page table 的總大小限縮
- 解法：
- Hierarchical Paging
- Hash Page Tables
- Inverted Page Table
#### Hierarchical Paging
將 page table 拆成數個較小的 table，將 logical address space 化成多層 page tables (n-level page table)，但因為多層的結構，實際上總 entry 是增加的。ex: A[1000] -> A[10][100] -> A[10][10][10]
- 64-bit Address
- 如果切成 42(p1) + 10(p2) + 12(offset)
- outer table 需要 2^42 X 4B = 16TB 的連續記憶體!!
- 如果切成 12(p1) + 10(p2) + 10(p3) + 10(p4) + 10(p5) + 12(offset)
- outer table 需要 2^12 X 4B = 16KB 的連續記憶體
- 但記憶體存取次數變成 6 倍
#### Hashed Page Table
- 通常用在 address > 32 bits
- Virtual page number 會被 hash 進 hash table
- Hash table 的大小影響 bucket 的 chain 的長度
- 每一個 hash table 的 entry 包含以下資訊
- Virtual Page Number, Frame Number, Next Pointer
- 不過 pointer 的結構會浪費額外記憶體。另外，linked-list 搜尋時間為 O(N)
- 一個改善的實作是將 linked-list 的 element 設為 array，降低 linked-list traverse 的次數
#### Inverted Page Table
- 不使用 page table，而是改用 frame table， entry 為 PID + Page Number
- 若使用 page table，當 process 數量越來越多， page table 的數量跟著增加
- frame table 只需要一個，可以事先配置，且使用率接近 100%，減少儲存 table 的記憶體需求
- 但存取時要搜尋整個 table，增加存取的時間
- 最麻煩的是難以實作 page 的 sharing，所以這種作法比較少見

### Non-Contiguous Memory Allocation — Segmentation
#### Segmentation
- 以使用者的角度來決定如何切割記憶體
- 一個 program 可以看成 segments 的集合，segment 是一個 logic unit，可能包含：
- main program
- function, object
- local/global variables
- stack, symbol table
- arrays, etc…
#### Segmentation Table
- Logical address:(seg#, offset)
- Offset 可以描述的長度不受 program 長度限制，只受限於系統定義 program 最多可配置多少記憶體有關
- Segmentation table - map 二維的 physical address，每一個 entry 有
- Base(4 bytes): physical address 的起始位置
- Limit(4 bytes): segment 的長度
- Segment-table base register (STBR)：儲存 table 的 physical addr.
- Segment-table length register (STLR): 儲存 segment 的數量
#### Segmentation Hardware
- limit register 檢查 offset 有沒有超過範圍
- MMU 指派一個合適的 base address 給 segment 以配置 memory
- segment 之間的 physical address 不能重疊
- s 為 table 的 index， d 是 offset，若 offset 超過 limit，就發生 segmentation fault; 若符合條件，與 page table 不同， physical address 為 base + offset 直接相加沒有單位(page) 的概念
- 每一個 segment 的 control 是獨立的，如 heap, stack 允許的空間可能不同
#### Address Translation Comparison
- Segment
- Table entry: segment base address, limit
- Segment base address 可以為任意值
- Offset 的最大值等同於 physical memory size
- Page
- Table entry: frame base address
- Frame base address = frame number * page size
- Offset 的最大值等同於 page size
#### Example of Segmentation
#### Sharing of Segments
#### Protection & Sharing
- Segments 的 protection bits
- Read only segment (code)
- Read-write segments (data, heap, stack)
- Code sharing 發生在 segment level
- Shared memory communication
- Shared library
- 不同的 segment tables 有相同的 base address 就共享 segment
### Segmentation with Paging
#### 基本概念
- 在 logical address space 使用 segmentation，映射到 pages 時再切，compiler 不用管 physical address 怎麼對應
- 在 physical address space 使用 paging，藉由 MMU 做地址的映射，提高記憶體使用的效率
#### Address Translation
- CPU 產生 logical address
- 交給 segmentation unit 後產生 linear address
- Linear address 交給 page unit
- 產生 physical memory address
- Segmentation & pageing units 都由 MMU 處理
#### Example: Intel Pentium
- Logical-address space 分成兩部份
- 1st: 8K(2^13) segments(private), local descriptor table
- 2st: 8K(2^13) segments (shared), global descriptor table
- private & share 會是兩個分開的 segment
- Logical address
- 一個 process 其 segments 的數量為 2^14 = 16K
- segment 的大小 <= 2^32 = 4GB

#### Segmentation
- Segment descriptor
- Segment base address & length
- 存取權利及優先級
#### Paging (2 Level)
- Page size 可以是 4KB 或 4MB
- 將 32 bits 切成 page directory(outer page table), page tables(inner page table) & offset
- 每一個 page directory entry 有 indication 用的 flag，代表使用 4KB 或是 4MB 的 page，系統會動態決定，若是 4MB 則 32 bits 只切兩份，後面的 bits 都給 offset
#### 範例題目
- physical mem size = 512B 代表 seg offset 為 9 bits
- page size = 32 B 代表 page offest 為 5 bits
- 8 個 segments linear address 前 3 bits 是 segment table 的 index 現有 12 bits 的 logical address = 448 -> 010|001001000
1. segment index = 010 = 2
2. 對應到 001110110
3. 加上 segment offset 001110110 + 001001000 = 0101|11110
4. 因為 page offset 為 5 bits，所以 page table index = 0101 = 5
5. 對應到 physical frame number = 2
6. 所以最終結果為 0010|11110

## Ch9 Virtual Memory Management

### Background
- 為何我們不希望執行 program 時，將所有內容放進 memory 中
- 有許多程式碼負責不常使用的 erros 或 conditions
- 部份 program routine 不常使用
- 很多 program 使用相同的 libary
- 已經配置但沒有被使用的 Arrays, lists & tables
- 我們希望更好的 memory 使用率，真的需要使用的才放入 memory 中
- Virtual memory: 將 user logical memory 從 physical memory 分離
- 因為 logical -> physical 只是 mapping 的問題，所以 logical memory 可以比 physical memory 來的大，可以執行非常大的 process
- 提高 CPU/resources 的使用率，越多 process 在 virtual memory 中，degree 越高，就越容易找到需要某個資源的 process 去使用
- 簡化 compiling 的工作，不需要管 memory 的限制
- 提昇 programs 的執行速度，因為不用將整個 program 讀進 memory，有較低的 I/O load & swap 的負載
- Virtual memory 可以透過以下兩種方式實作
- Demand paging，因為是 fix-size，對硬體使用來說資源分配比較容易管理
- Demand segmentation -> 因 segmentation 大小不固定，要找到空間的複雜度較高，效率較低，但對 user 來說比較容易理解及使用 (heap, stack…etc)
- Virtual Memory vs. Physical Memory

### Demand Paging
#### Demand Paging
- 當 Page 被需要時才讀進 memory 中，好處是
- 較少的 I/O 需求 --> 更快的響應
- 較少的 memory 需求 --> 可以有更多 programs 執行
- 當 Page 有 reference 指向它時，代表 Page 被需要
- 若 reference invalid --> abort (沒有 allocate)
- Not-in-memory --> 利用 paging 讀入記憶體 (page fault)
- pure demand paging
- process 啟動時完全沒有 page
- 只有當 page 需要時才讀進 memory
- swapper (midterm scheduler) 管理整個 process ，而 pager 則是管理 process 的一個 page 為單位
- 硬體支援
- Page Table: valid-invalid bit 來表示 page 是否在記憶體中
- 1 -> page in memory
- 0 -> page not in memory
- 一開始該 bits 都設成 0
- Secondary memory (swap space, backing store): page 從 memory 被 swap 出去的儲存空間，通常是 high-speed disk
#### Page Fault
相關資料:[MIT6.s081 Lab: xv6 lazy page allocation](https://hackmd.io/@Chang-Chia-Chi/SyVVrPBRt)
- 第一次的 reference 會引發 trap to OS
- 稱為 page fault trap
1. OS 會查看在 PCB 裡頭的 internal table ，確認是 Invalid 或只是 not in memory，決定後續動作
2. 找到一個 empty frame (可以置放 page 的空間)
3. 將 page 從 disk (swap space) 移到 frame
4. 設定 Page-table，將 valid-invalid bit 設為 1
5. 重啟 instruction
#### Page Replacement
- 若 page fault 時沒有 free frame 的話
- Swap 一個 frame 回 backing store
- Swap 目標 page 進 frame
#### Demand Paging Performance
- Effective Access Time (EAT): (1 – p) * ma + p * pft
- p 為 page fault rate, ma 為 mem. access time, pft 為 page fault time
- mem. access time 包含找到位置及將資料從 memory chip 搬到 CPU register 的時間
- page fault time 則多了資料在記憶體 - disk 之間 swap 的時間
- pft 遠大於 ma，EAT 基本上由 pft 及 page fault rate 決定
- 假設 ma = 200 ns, pft = 8 ms，若 1000 次產生 1 次 page fault，則速度就會慢上 40 倍 ; 換個角度如果我們希望 page fault 對讀取時間的影響小於 10%，則 page fault rate 必須小於 0.0000025
- Programs 的 refernce 通常是 locality 的，代表 program 通常會存取在鄰近位置的 memory address
- 一個 page fault 可以讀取 4KB 的資料進來
- 大幅降低 page fault 發生的機率
- Page fault time 的時間組成
1. page-fault 中斷
2. 將 page 從 disk 中讀進 memory (最花時間)
3. 重啟 process
### Process Creation
#### Process & Virtual Memory
- Demand Paging: 當有需要時才 swap page 進 memory
- Copy-on-Write: parent 跟 child processes 一開始共享 frames，當有內容發生不同時，才會 copy frame
- Memory-Mapped File: 將 file 的 disk content 當作 memory content，用 virtual address space 做 mapping，避開 file system，增加 I/O 效能。通常適用於大檔案，因為 paging 需要 4KB 的空間，小檔案使用會有記憶體空間碎片化的問題
#### Copy-on-Write
相關資料:[MIT6.s081 Lab: Copy-on-Write Fork for xv6](https://hackmd.io/@Chang-Chia-Chi/BkMAP0Hk5)
- 允許 parent & child 共享 frames
- 若其中一者變更 frame，則僅對該 frame 進行 copy 的動作
- COW 使得 process creation 有效率(e.g. fork())
- 通常 free frame 時會完全清空，避免前一個 process 使用的一些 content 被其他 process 看見，造成潛在的安全性問題
- When a child process is forked
- After a page is modified
#### Memory-Mapped Files
- 方法：
- MMF 透過 disk block to memory frame 的 mapping，讓 I/O 像一般的記憶體存取，略過 file system calls (eg. read(), write())
- file 一開始使用 demand paging 讀取，之後的讀寫動作視作一般的 memory access
- 好處：
- 略過 file system calls (如 read(), write())
- 允許多個 processes 共享 file 的內容
- 壞處：
- 安全性、資料遺失、更多的 programming efforts
- 範例：
### Page Replacement
Page Replacement 的演算法會嚴重影響系統的速度，假設演算法經常將需要用到的 pages swap 去 disk，則 pages 在 memory 跟 disk 一直來回的時間會大幅拖慢系統的效能
#### Page Replacement Concept
- 當沒有 free frame 時發生 page fault
- 將整個 process swap 掉，釋放所有 process 佔有的 free frames，但這樣 process 就完全不能使用，並不是一個好方法
- 採用 page replacement ，找到一個目前沒有被使用的 frame 將其 free 掉
- 使用 dirty bit 表示 page 的內容是否被修改過，若 page 沒有被修改過，就直接 free 掉 frame 的內容; 有修改過才將資料寫回 disk ，來減少 page transfers 的 overhead，
- replacement 必須要處理兩個問題
- free-allocation algorithm: 演算法必須決定多少 frames 應該 allocate 給 process
- page-replacement algorithm: 選擇哪些 frames 被取代
#### Page Replacement Step
1. 在 disk 中找到需要的 page
2. 若有 free frame，則直接使用; 若沒有 free frame 則執行 page replacement 演算法來選擇被取代的 frame
3. 將需求的 page 讀進 free frame 中，並更新 page & frame tables
4. 重啟 process 的指令
#### Page Replacement Algorithms
- 目標：最低的 page-fault rate
- 評估：一連串的 page id (reference string, memory refernces) 為輸入，計算 page fault 發生的次數
#### FIFO algorithm
- 在佇列中最舊的 page 會被取代
- 範例：
- 假設 available memory frames = 3
- 產生 9 次 page fault
- Belady’s Anomaly: 即便增加 frames 的數量，page fault 的數量不一定會減少，還有可能會增加
- 假設 available memory frames = 4
- 產生 10 次 page fault
- 因為 Belady’s Anomaly，使得我們很難對系統進行調整，例如插越多條記憶體，反而執行速度有機會變慢
#### Optimal (Belady) Algorithm
- 取代未來最長時間不會被使用的 page
- 但實際上我們不會有未來的資訊
- 因此這個演算法比較類似提供我們一個基準
_Algorithm.jpg)
#### LRU Algorithm (Least Recently Used)
- 一種 optimal algorithm 的近似
- 因為無法預測未來，所以我們往回看
- 取代最長時間沒有被使用的 page
- 因為 locality 及時間複雜度低(O(1))的緣故，LRU 很常被使用
- Counter implementation
- 紀錄每個 page 最近被使用的 time-stamp
- 取代 time-stamp 最舊的 page
- 時間複雜度 O(N)
- Stack implementation (實際使用)
- 當 page 被使用時，將 page 移到 double-linked list 最前方
- 可以用 hash map 紀錄 double-linked list 每個 element 的指標，達成 O(1) 的實作
- 取代 linked list 中位在 tail 的 page
#### Stack Algorithm
Optimal & LRU 都是 stack algorithm，有以下這些特性
- n frames 的 pages 一定是 n+1 frames pages 的 subset，也就是說因為 stack 的特性，先被放入的元素一定會先被看到，若增加 frames，也只是在原 stack 後面增加一些 pages 而已
- Stack algorithm 不會有 Belady’s anomaly 問題
#### LRU 近似的演算法
- additional-reference-bits algorithm
- second-chance algorithm：2 個 LRU stack
- enhanced second-chance algorithm
#### Counting Algorithms
- LFU Algorithm (least frequently used)
- 每一個 page 有 counter
- 經常被使用的 page 應該要有大的 count value
- MFU Algorithm (most frequently used)
- 不過常用不代表正在用，有可能在某些時刻集中使用，將 count 拉高，但多數時間沒有使用
- 最小的 count 有可能是剛帶進來的，還沒被使用，所以應該留著
- 兩者都不常用
- 要一直執行加法成本很高
- 有 overflow 的問題
- 表現不一定較佳

### Allocation of frames
每個 process 最少都需要一定數量的 frames
#### Frame Allocation
- Fixed allocation: 根據 process 在一開始就決定要 allocate 多少 frame
- Equal allocation: 每個 process 配置到的 frames 數目相同
- Proportional allocation: 根據 process 的大小來配置
- Priority allocation
- 在 run time 的時候，根據 process 的優先度決定配置
- 如果 process 發生 page fault
- 選擇 process 本身的一個 frame 來替代
- 或著選擇低優先度的 process 的 frame 來替代
- Local allocation: 只能替換自己的 frames，通常跟 fixed allocation 綁在一起
- Global allocation: 從所有的 frames 中選擇一個來替代
- 可以拿其他 process 的 frame
- 例如讓高優先度的 process 搶低優先度的 process
- 有好的系統表現，所以較常使用
- 會有一個問題是如果一直搶低優先度 process 的 frame，有可能該 process 甚至無法維持最低的 frames 數量，所以要有機制來維持最低 frames，避免 process 被 thrashing

### Thrashing
如果一個 process 沒有足夠的 frames，代表 process 在記憶體中的 frames 數量不足以支撐 process 執行，導致 page fault 一直在發生 (且 page fault 是 instruction level，無法 overlap)，等於 CPU 要一直等待 I/O，造成 CPU 使用率反而下降的情況
- Thrashing 的定義為： 當一個 process 花在 paging 的時間比執行時間更高時，稱為 thrashing
- Thrashing 造成的 performance 問題
- processes 因 page fault 在等待 I/O
- 因此 CPU 使用率下降
- OS 發現 CPU 使用率下降，增加 degree of multiprogramming
- 新產生的 processes 從舊的 processes 搶 frames，導致更多的 page fault
- 結果 CPU 的使用率繼續下降
- 為了避免 Thrashing，必須要控制 degree of multiprogramming
#### Working-Set Model
- 從 Locality 的角度思考，對一個 process 而言，我們可以計算在這段時間內使用多少 pages，這個數量就是要 assign 給 process 的 frames 數量
- 因為 process 的需求是動態變化的，所以 locality 會隨時間改變，OS 必須要持續追蹤 processes 的 locality
- 例如 program structure (如 subroutine, loop, stack)
- 或 data structure (array, table…etc)
- Working-set Model
- Working-set window: 觀察的一段時間
- Working set: 這一段時間內，被 process reference 到的 page 數
- 每一個 process 的 working set size $WSS_i$
- frames 的總需求數 $D=∑WSS_i$
- 如果 D > m (available frames) ，則有 thrashing 發生
- OS 會監控每個 process 的 $WSS_i$ ，並配置足夠的 frames 給每個 process
- 如果 D << m，增加 degree of multiprogramming
- 如果 D > m，把整個 process suspend (mid-term scheduler) 掉，free 該 process 所有的 frames
- 優點
1. 在最大化 multiprogramming 的情況下，同時防止 trashing 的發生
2. 可以最大化 CPU 使用率
- 缺點
1. tracking 的成本很高
#### Page Fault Frequency Scheme
- 監控每個 process 發生 page fault 的機率，控制 page fault rate 在一定範圍內來防止 thrashing 的現象
- 依據 page fault rate 為每一個 process 建立 upper 跟 lower bounds
- 如果 page fault rate 超過 upper limit，則配置更多的 frames
- 如果 page fault rate 低於 lower limit，則移除部份的 frames
#### Working Sets and Page Fault Rates
重點是 memory 的 locality 會變化，所以需要追蹤 process 的使用情況，動態地調整 processes 及 frames 的配置情況

## Ch4 Multithreaded Programming

### Threads
Threads 又稱為 Lightweight process，是使用 CPU 的最小單位，同 Process 的 Threads 有共享的記憶體空間。在 Parent Process 創造 Threads 時就會 allocate ，因此省去在空間管理及處理上的執行動作。
- 同 Process 中，Threads 共用以下內容
- code section
- data section (global variable, heap)
- OS resources (e.g. open files and signals)
- 但以下部份各自獨立
- stack
- register set -->可能 instruction 的執行位置不同，甚至執行不同的 function call
- thread ID
- program counter

### Motivation
- web browser
- 如一個 thread 負責顯示文字，其他 thread 接收資料等
- web server
- One request / process: poor performance
- One request / thread: 因為 code 及 data sharing，效率較高
- 會有一個 main thread 一直在等待，當接收到新 request 時，會產生一個 thread 專門處理，讓 main thread 可以繼續等待連接
- RPC server
- One RPC request / thread

### Benefits of Multithreading
- Responsiveness : 即使 program 的一部分被 block 住，或是執行冗長的操作，仍可繼續運行，加速響應時間
- Resource sharing : 不同的 threads 可利用相同的記憶體位置來共享資源
- Utilization of MP arch : 因為現在都是多核心，因此 thread 可以在不同 processors 上平行執行
- Economy : thread 無須記憶體空間管理及處理，建立 Thread的 cost 比 process 來得小。而且因為 thread 共用 process 資源，thread 之間的 context switch 也比 process 來得快。
- Multithreaded programming 提供一種更有效率使用多核心的機制，改善共時性 (concurrency)
- 多核心系統使 system designer 以及 application programmer 面對更多挑戰
- 對 OS 設計者 : 如何設計 scheduling algorithms 讓多核心可以平行執行

### Challenges in Multicore Programming
- Dividing activities : 將 program 拆成多個可以同時處理的任務
- Data splitting : 除了計算任務要拆，資料也要能夠拆開給不同任務處理。有時候 data 很複雜，不一定是平分給所有任務處理
- Data dependency : shared data 的同步，是平行程式中最複雜且重要的部份
- Balance : 各個任務的執行時間要差不多，否則會受限於執行最久的任務
- Testing and debugging 非常困難

### User vs. Kernel Threads
- User threads : 由 user 透過 threads library 進行的 thread 控制。雖然由 user 創建，但實際 thread 要執行任務時， OS 會將該 thread binding 到某一個 kernel thread 上，每次可對應到不同的 kernel thread。
- POSIX Pthreads
- Win32 threads
- Java threads
- 所謂 user thread 就是 thread library，更重要的是 user level 的 thread，不由 kernel 直接控制，通常在創建及管理上會比較快
- 但如果 kernel thread 只有一個的話，即便有多個 user threads，因為有 binding 的關係，只要某個 user thread 執行時呼叫 I/O 或 sleep()，則其他 threads 就沒辦法再使用該 kernel thread
- Kernel threads : 由 kernel(OS) 直接控制
- Windows 2000(NT)
- Solaris
- Linux
- Tru64 UNIX
- 由 kernel 進行創建及管理，速度較慢
- 若某個 thread 被 block，仍可由 kernel 安排其他 threads 執行工作

### Multithreading Models
Kernel mapping threads 的方式通常有以下幾種：
1. Many-to-One
- 許多 user thread mapping 到一個 kernel thread
- 在不支援多 trheads 的 kernel 使用
- Thread 管理在 user space 完成，效率高
- 但整個 process 可能被 block
- 一次只有一個 thread 可以 access kernel，多執行緒在多處理器的環境下也無法平行化
2. One-to-One
- Windows XP/NT/2000
- Linux
- Solaris 9 and later
- 每個 user thread mapping 到一個 kernel thread
- 因為 kernel thread 數量通常受到限制，所以 user thread
- More concurrency
- 因為創建一個 user thread 必須同時創建一個對應的 kernel thread，所以有較高的 overhead
3. Many-to-Many
- 多個 user threads 對應到相同或較少數量的 kernel threads，而且是在 runtime 期間做 mapping
- user threads 數量不受限制
- kernel threads 可以在多核心系統中平行執行
- 當某個 thread 被 block 時，可安排其他 kernel thread 來執行

### Shared-Memory Programming
- 定義：Processes 透過 shared memory space 進行溝通及協作
- 比 messgae passing 更快也更有效率
- 有許多議題需要處理：
- Synchronization
- deadlock
- Cache coherence
- Programming 的技巧
- Parallelizing compiler
- Unix Processes
- Threads (Pthreads, Java)
#### What is Pthread
- POSIX (Portable Operating System Interface，只定義行為不定義實作，也就是 API 層面必須一模一樣) 標準針對 Unix 類的不同系統 (MacOs, Linux…等)，程式碼只需要重新編譯而不用修改即可執行
- Message passing 的 library MPI 也有相同概念
- Pthread 即是定義在 POSIX 標準下的 thread 庫

Pthread Creation
- pthread_create(thread, attr, routine, arg)
- 有時我們會指定某個 thread 榜在某個指定的 core 上，因為不同 core 的 L1 cache 不共享，這個行為可以透過 attr 參數來控制

Pthread Joining & Detaching
- pthread_join(threadId, status)
- Block 直到特定 threadId 的 thread 結束
- 達成 threads 之間同步化的一種方法
- 範例：產生 pthread barrier

  for (int i = 0; i < n; i++) pthread_join(thread[i], NULL)

- 要注意的是，若今天 thread 執行完之後，我們不需要把資料讀回來，則不用 call pthread_join，但多數的 thread 庫會要求 programmer call pthread_detach，告訴 library thread 結束後就直接 free 掉。若不去 call detach， OS 無法知道 thread 是否之後會被 join，導致 thread 的回傳值一直在等待，程式無法結束
- pthread_detach(threadId)
- 一但 thread 被 detached，則永遠無法被 join
- Detach 一個 thread 可以 free 掉 thread 的資源
#### Linux Threads
- Linux 在 kernel 不 support multithreading(因為 Linux 只有 process 或 task)
- User-level 可以使用 Pthreads 來實作多執行緒
- `fork` system call: 產生新的 process 並完全複製 parent 的 data 及程式執行狀態
- `clone` system call: 產生新的 process 並控制哪些 segment 要與 parent share 哪些不需要。因為 Linux 沒有 thread ，所以用 `clone` system call 來達到 thread 的概念
- 有一系列的 flag 來控制資料共享的程度，共享的資料以 pointer 的方式指向
- Semantics of fork() and exec()
- 若 process 有兩個 thread，其中一個 thread call `fork()` 可能有以下兩種情況
- 部份 UNIX 系統支援兩種 `fork()` 的方式
- `execlp()` 會取代整個 Process，而不是單一 thread
- Thread Cancellation
- 一個 thread 若執行結束後， main thread 必須有一系列 cancel 的動作
- Asynchronous cancellation : main thread 會馬上中止 target thread
- Deferred cancellation (default option) : target thread 會預設一些中斷點，main thread 會週期性地確認是否執行到中斷點，等 target thread 執行到中斷點才中斷。
- Signal Handling
- Signals(synchronous or asynchronous) 在 UNIX 系統中用來告知 process 某個事件發生
- synchronous : 如不合法的記憶體存取
- asynchronous : control-C
- Signal handler 處理 signals 的順序
1. Signal 被特定事件產生
2. Signal 被送到 process
3. Signal 被處理
- Signal 處理的 Options
- 傳送 signal 給 deliver signal 的 thread
- 傳送 signal 給所有 thread
- 傳送 signal 給特定的 thread
- 直接由 main thread 來處理 signal，如 file handler 的操作
#### Thread Pools
- 很多應用是直接產生一定數量的 threads，避免動態 thread 的產生、刪除時造成的 overhead，程式執行比較有效率，如 web server
- 優點
- 直接接收 request 通常比創建一個新的 thread 再接收 request 來得快
- 可以控制 threads 數量，進而控制系統的資源用量
- threads pool size 的決定: 利用 # of CPUs, 預期的 # of request 以及記憶體大小來決定

## Ch6 CPU Scheduling
[相關資料](https://hackmd.io/@Chang-Chia-Chi/BkoQi26kq)
### Basic Concepts
- Multiprogramming
- keep 多個 process 在 memory 中
- 一次只有一個 process 在 CPU 執行，其他的 process 處於 waiting 狀態
- 當執行狀態的行程必須等待資源才能往下執行（I/O request），作業系統拿回CPU的控制權交給等待的行程
- Process Scheduling 的目的是讓 CPU 在每個時刻都有工作可以做，增加使用效率
- Process 基本上不是在執行 instruction，就是在執行 I/O，執行一連串的 instrunction 又稱為 burst(CPU burst & I/O burst)
- 一般來說，多數的 CPU burst 時間很短，少部份的 CPU burst 時間很長
- 一個 I/O Bound(I/O 密集) 的 Program 通常有很多短的 CPU burst (若沒有很長的 CPU burst，則通常是 I/O Bound)
- 一個 CPU Bound(計算密集) 的 Program 可能有一些很長的 CPU burst (如很長的 for loop)
#### CPU Scheduler
從 Ready Queue 選擇誰可以被執行 (也就是將 Process 讀到 CPU 當中)
#### Preemptive vs. Non-preemptive
- CPU scheduling 的決定時機主要有以下幾個
1. 從 running 換到 waiting state
2. 從 running 換到 ready state (CPU burst 被打斷，time sharing)
3. 從 waiting 到 ready state
4. 終止狀態
- Non-preemptive scheduling: 若一個 process 可以繼續執行(在 CPU burst)，則不會被打斷
- 因此只會在上面 1. 跟 4. 的情況下作 re-scheduling
- 例如 Window 3.X
- Preemptive scheduling
- 在所有情況都有可能 re-sheduling
- 如 Windows 95 及之後的版本, Mac OS X
#### Preemptive Issues
- Preemptive 最大的缺點是 synchronization 的問題
- 需要同步化
- 導致存取 shared data 的問題與對應的 cost
- 對 OS kernel 設計的影響
- 在 kernel 中做 lock & unlock 的設計
- Unix 的解決方法是: 當在 run OS kernel 的 instruction 時，會把 timer disable，從 preemptive 變成 non-preemptive
#### Dispatcher
- 由 scheduler 決定誰被執行，dispatcher 執行換人的動作，其負責
- switching context
- 從 kernel mode 轉換到 user mode
- process 換了之後，page table 的 pointer、program counter(load 到新的 state)
- Dispatch latency: dispatcher 執行換人動作，停止一個 process，啟動另一個 process 所需的時間
- Scheduling time
- Interrupt re-enabling time
- Context switch time

### Scheduling Algorithms
#### Scheduling Criteria
- CPU utilization
- 理論上是 0% ~ 100%
- 實際上是 40% ~ 90%
- Throughput(從系統的角度)
- 單位時間完成的 processes 量
- Turnaround time(從 single job 的角度)
- submission ~ completion（從ready ~ terminate的時間）
- Waiting time
- Process 執行期間在 ready queue 中等待的時間
- 所以 I/O Burst 不算在 waiting time
- Response time
- submission ~ 第一個 response 產生(第一個 CPU burst 開始執行)
#### Algorithms
1. FCFS Scheduling
- 依 (Burst time) 抵達順序執行(先來的先執行)
- P1(24), P2(3), P3(3)
- Waiting time: P1=0, P2=24, P3=27
- Average Waiting Time (AWT): (0 + 24 + 27)/3 = 17
- Non-preemptive
- Convoy effect: 很多 process 在等待一個很長 CPU Time 的 process，造成平均等待時間大幅增加的不良現象
2. Shortest-Job-First (SJF) Scheduling
- 時間最短的 process 先處理
- 運用行程下一個 CPU burst 的長度，而非 CPU burst total 長度
- SJF 的 average waiting time 一定是最短的
- Schemes
- Non-Preemptive SJF: 當一個行程拿到 CPU，不會被搶佔直到他完成
- Preemptive SJF: 當有新的行程且他的 CPU burst 的長度比較小，搶佔發生
3. Approximate Shortest-Job-First (SJF)
- SJF 的難處是在執行下一個 CPU burst 之前，無法得知實際的執行長度
- Approximate SJF: 下一個 burst 可預測為過去 CPU burst 長度的 exponential average
4. Priority Scheduling
- 每一個 process 有一個 priority number
- CPU 被分配給高優先度的行程
- Preemptive
- Non-preemptive
- SJF 可視為優先度的排程，其優先度是下一個預測的行程 CPU burst time
- 問題：Starvation – 優先度低的 process 可能不會被執行
- 解法：aging – 隨時間增加，若 process 還沒被執行到，則增加優先度
- ex: 每 15 分鐘增加優先度 1
5. Round-Robin(RR) Scheduling
- process 執行時，可在 CPU 執行的時間(time quantum)有限制，通常是 10~100 ms
- 達規定的執行時間後，程式被 preempted 並加到 ready queue 的尾端
- Performance
- TQ Large --> 類似 FIFO
- TQ small --> (context swtich) overhead 增加
Scheduling.jpg)
6. Multilevel Queue Scheduling
- Ready queue 切成分開的 queue
- 同一個 queue 通常放類似功能的 process
- 每一個 queue 有自己的排程演算法
- 因為還是只有一個 queue 的程式可以執行，所以 queue 之間也有排程，常見的作法是用權重的方式隨機挑選一個出來
- Fixed priority scheduling：有 starvation 問題，若最上層的 queue 先做，下層的 process 可能一直做不到
- Time slice：每個 queue 分配一定的 CPU time
7. Multilevel Feedback queue Scheduling
- process 執行的狀況在 run time 才能得知，如過去 CPU burst 多少、呼叫了哪些 system call 等等，系統會在 run time 接收這些資訊並分類放到合適的 queue 中
- process 可以在不同的 queue 中移動，因為也是一種 priority queue，也會有 starvation 的問題，通常搭配 aging 實作
- 一定先執行上層的 queue
- 依照 process CPU burst 的特性分類
- I/O-bound 及 interactive 的 process 在較高層的 queue --> short CPU burst
- CPU-bound 的 process 在較低層的 queue --> long CPU burst
- 當新的 job 抵達 Q0，以 FCFS (First Come First Serve) 演算法排程，若沒辦法在 8ms 內完成，則將 job 移到 Q1
- 同樣地 Q1 也是 FCFS ，若 job 在 16ms 內還是沒執行完，則被 preempted 並丟到 Q2
- 只有當 Q0 ~ Qi-1 是空的時候， Qi 中的 job 才會被執行
- 下一次回來 ready queue 時，系統會依照 feedback 判斷放在哪個 queue 中 (feedback 資訊會放在 PCB 中)
- 通常 scheduling 演算法由以下參數決定
- queues 數量
- 每個 queue 的排程演算法
- 提昇/降級一個行程的方法
#### Evaluation Methods
- Deterministic modeling
- 以預定義的 workload 及演算法表現的好壞，缺點是難以通用化
- Queueing model
- 數學分析
- Simulation
- 以隨機數字產生器或 trace tapes 產生 workload
- Implementation
- 最準確的方式就是直接實作並觀察

### Multi-Processor Scheduling Multi-Core Processor Scheduling Real-Time Scheduling
#### Multi-Processor Scheduling
- Asymmetric multiprocessing
- 所有系統的執行會由一個 master processor 掌控
- 其他 processors 只執行 user code (由 master 配置)
- 遠比 SMP 簡單
- Symmetric multiprocessing (SMP)
- 每一個 processor 都是 self-scheduling
- 所有 processors 共用 ready queue，或是每一個 processor 有自己的 ready queue
- 需要同步機制
#### Processor affinity
- Processor affinity: process 與執行它的 processor 之間有 affinity 關係
- process 會將最近常使用的資料放在執行它的 processor 的快取中
- 快取的無效及資料重新放入是高成本的行為
- Solution
- soft affinity: 允許 process 在不同 processor 執行
- hard affinity: 只能在同一個 processor 執行
#### NUMA and CPU Scheduling
- NUMA (non-uniform memory access)
- 發生在結合 CPU 與 memory boards 的系統中
- CPU scheduler 及 memory-placement 會一起工作
- process 被配置在有 affinity 關係的 CPU 的 memory board
- Load-balancing
- 讓不同 processors 間的 workload 盡量平均
- 只在 processor 有 private queue 的系統下才需要
- 兩種策略
- Push migration: 將 processes 移動到閒置或 less-busy 的 processor 中
- Pull migration: 閒置的 processor 將等待中的 task 從其他忙碌的 processor 中拉過來
- 通常是平行實作
- Load balancing 經常抵銷 processor affinity 帶來的效益
#### Multi-core Processor Scheduling
- Multi-core Processor:
- 更快且更少的 power 消耗
- memory stall: 當存取記憶體時，花費許多時間在等待資料 available (e.g. cache miss)
- Multi-threaded multi-core systems
- 兩個(或更多)的硬體 thread 被 assign 給每一個 core (i.e. Intel Hyper-threading)
- 當一個 thread 在存取記憶體時，其他 thread 就可以執行 CPU 指令
- Two ways to multithread a processor
- coarse-grained: 當 memory stall 發生時切換到另一個 thread，因為 instruction pipeline 必須被 flush 所以成本很高
- fine-grained(interleaved): 把 pipeline 的狀態保留並切換到另一個 thread 執行，需要更多的 register 來保存資料
- Scheduling for Multi-threaded multi-core systems
- 1st level: 選擇某個 software thread 執行在每個 hardware thread([logical processor](https://daniel-jiang.medium.com/computer-science-101-in-depth-operating-systems-part-1-processes-and-scheduling-df9b9cd5b573))
- 2nd level: 每個 core 如何決定執行哪一個 hardware thread
#### Real-Time Scheduling
- Real-time 不代表越快越好，重點在 deadline 前要完成
- Soft real-time
- 雖然不希望超過 deadline，但並不會馬上出問題
- 例如影音串流
- Hard real-time
- 若超過 deadline 則導致 fundamental failure
- 例如核電廠的控制
- Hard real-time
#### Real-Time Scheduling Algorithms
- FCFS scheduling algorithm – Non-RTS
- T1 = (0, 4, 10) == (Ready, Execution, Period)
- T2 = (1, 2, 4)
- Rate-Monotonic (RM) algorithm
- 依據頻率的大小來做排程
- 更短的週期(週期是固定的數值，在 run time 期間不會變動) --> 更高的優先度
- 同一個 task 的所有 job 都有一樣的 priority
- task 的優先度是固定的
- Fixed-priority RTS scheduling algorithm
- Earliest-Deadline-First (EDF) algorithm
- 更早 deadline --> 更高的優先度
- 動態優先的演算法
### Operating System Examples
#### Solaris Scheduler
- Priority-based multilevel feedback queue scheduling
- 有六類 scheduling，一個 process 只會屬於某一類:
1. real-time
2. system
3. time sharing
4. interactive
5. fair share
6. fixed priority
- 每一個類有自己的 priority & scheduling 演算法
- Scheduler 會將類的優先度轉換為 global 的優先度
- Solaris Example(time sharing, interactive)
- 優先度與 time slices 成反向關係，time slice 越小的優先度越高
- Time quantum expired: 當 thread 在沒有 blocking 的狀況下使用整個 TQ，則重新排優先度
- Return from sleep: 若 thread 從 sleeping(I/O wait)回來 ready queue 時，會重新排優先度
- 期望 CPU-bound 的 process 慢慢往下沉，I/O-bound 的 process 慢慢上浮
#### Windows XP Scheduler
- Multilevel feedback queue
- 優先度分為 0~31，由優先度最高的 queue 開始排程
- 優先度最高的 thread 永遠在執行
- 每一個 priority queue 使用 Round-robin
- 除了 Real-time 的 task 之外，優先度在 run time 時期動態變更
#### Linux Scheduler
- Preemptive priority based scheduling
- 只有 user mode processes 可以被 preempted
- 兩個不一樣的 process priority ranges
- 值越低優先度越高
- TQ 較高者有更高的優先度
- Real-time tasks: (priority range 0~99)
- static priorities
- Other tasks: (priority range 100~14-)
- 依 task 執行狀況動態決定優先度
- Scheduling algorithm
- 若一個 task 還有剩餘的 TQ，則 task 可以被執行，只要還沒耗盡 TQ，都會保留在 active array，希望每一個 task 都能用完它的 TQ
- 當 task 耗盡 TQ，則為 expired 且不應被執行，移到 expired array
- task expire 後，系統會決定新的優先度以及 TQ

## Ch5 Process Synchronization
當共享的資料同時被不同 Process / threads 存取時，因為執行順序的不確定性，很容易發生 data inconsistency 的狀況，所以需要額外的機制來確保程式的正確性，也就是 Synchronization
以下為常見的 Consumer & Producer Problem
除了 Buffer 之外， Counter 也是 share variable，要注意的是 `counter++` 及 `counter--` 在 instruction level 其實有三道指令，以 `counter++` 為例，要先將 counter 從記憶體中移到 register，加上 1 之後，再存回記憶體。由於 `context switch`, `Preemptive scheduling` 等因素， 這些指令可能不是一次執行完成，導致執行結果不符合預期

move ax, counter
add ax, 1
move counter, ax


### Race Condition
當多個 Processes 同時存取及操作 shared data 時，最終的值取決於最後一個完成執行的 Process，這個現象稱為 Race Condition
- 在 single-processor machine 中，我們可以 disable interrupt 或著使用 Non-preemptive scheduling 來達成同步，但在 User Program 中不可能使用，會影響整個系統的運作
- 通常將可能產生 Race Condition 的區域稱作 `Critical Section`

### Critical-Section Problem
- 目的：建立 Processes 之間合作的 protocal
- Problem description
- N 個 Processes 競爭使用 shared data
- 每一個 Process 存取 shared data 的 code segment 我們稱為 critical section
- 若我們確保當一個 Process 執行 critical section 時，其他 Processes 不得執行 critical section，稱之為 `mutually exclusive`，是比較暴力的解法
- 一般常見 critical section 的架構如下

### Critical-Section Requirements
1. Mutual Exlusion：
- 當一個 Process 執行 critical section 時，其他 Processes 不得執行 critical section
2. Progress：
- 若沒有 Process 在執行 critical section，且有某些 Processes 希望進入它的 critical section，則 Process 不得在未定義的情況下被推遲，一定要進的去
3. Bounded Waiting：
- Process 等待進入 critical section 的期限必須受到限制，不可一直排隊等待

### Critical-Section Solution & Synchronization
#### Algorithm for Two Processes
- 我們先以兩個 Processes 的簡單例子做講解
- 只有兩個 Process P0 & P1
- 共享變數
- int turn
- turn = i --> Pi 可進入 critical section
以上的程式碼其實並不完美，這個程式要能順利運作的前提是，兩個 Process 必須輪流執行，但 while loop，並不保證執行的順序，很有可能 Process 0 執行完一次，又想進入 critical section，但 Process 1 還沒執行到 turn = 0 這一行，P0 就會卡在 while loop ，不符合 progress
#### Peterson’s Solution for Two Processes
為了解決上述 Progress 的問題，我們引入另一個變數 `flag` ，用來表示 Process 是否想要進入 critical section 中，當 `flag[i] = True` 的時候，代表 Pi 已經準備好要進入 critical section，`turn = j` 代表把 key 交給別人。所以 while 條件式 `flag[j] && turn==j` 的意義為檢查其他 Process 是否可進入 critical section，確認沒有其他 Process 要進入 critical section 後，自己再進入 critical section。
要注意如果 `turn = j` 不是把 token 交給別人而是搶過來用，當某個 Process 先進入 critical section，輪到另一個 Process 時也可以 break while 迴圈，但無法進入 critical section 導致 deadlock
簡單的證明 Peterson’s Solution
- Mutual exclusion : turn 不可能同時為 0 或 1，因此不可能同時進入 critical section
- Progress :
- 若 P1 尚未準備好 --> flag[1] = False --> P0 可以進入
- 若兩者都準備好 --> flag[0] = flag[1] = True
- 若 turn = 0 則 P0 進入，否則 P1 進入
- 以上兩種狀況，Process 都可以順利進入 critical section
- Bounded waiting :
- 若 P1 離開 critical section --> flag[1] = False --> P0 可以進入
- 若 P1 離開 critical section 後，繼續執行 while loop --> flag[1] = True --> turn = 0 (覆寫 P0 原先的 turn = 1) --> P0 可以進入
- 以上兩種狀況，P1 進入後接著進去的一定是 P0，符合 Bounded Waiting 的要求
#### Producer/Consumer Problem
- 情況一：我們將所有程式碼都放入 critical section，如果 consumer 先 call，因為 buffer 是空的，所以 consumer 會卡在 while 迴圈 ; 這時再 call producer ，因為 consumer 已經在 critical section 裡頭， producer 無法進入導致 `deadlock`
- 情況二：我們只將可能產生 race condition 的程式碼放進 critical section，雖然執行結果正確，但如果某一個 Process 進入 critical section 其他 Process 進不去，可能導致無謂的 context switch 降低效率

### Bakery Algorithm (n processes)
- 在進入 critical section 之前，每一個 Process 會抽號碼牌
- 號碼牌數字最小的先進入 critical section (注意可能有相同的號碼牌，如下方程式碼以 max 實作，而 `max` 指令其實有好幾行)
- 號碼牌數字的產生一定是 non-decreasing order; i.e. 1,2,3,3,4,5,5,5…
- 若兩個 Process Pi & Pj 有相同的號碼牌，則 PID 小的先進入
- `choosing[i]` 為是否正在抽號碼牌的 flag，在與其他 Process j 比較之前，我們必須等待 Process j 抽完號碼牌。考慮一個狀況， Process j 比 i 晚抽完號碼牌，但號碼與 i 一樣大，又 j 的 PID 比 i 小，所以 Process j 應該要先執行 ; 如果在 j 還沒抽號碼牌之前就進行比較，此時 num[j] = 0，程式會以為 j 不要執行，反而先執行 i，當 j 抽完號碼牌之後發現數字與 i 相同，因此也可以進入 critical section，但這時 i 已經在裡頭，導致 deadlock。

### Pthread Lock/Mutex Routines

### Condition Variables (CV)
- Condition Variables 代表一個條件，符合該條件時可以觸發 thread 執行某些動作
- 三種 CV 的操作
- `wait()` : 直到其他 thread 呼叫 signal()/broadcast()，thread 處於等待狀態
- `signal()` : 喚醒一個等待中的 thread
- `broadcast()` : 喚醒所有等待中的 thread
- 在 Pthread 中，CV type 為 `pthread_cond_t`
- 使用 pthread_cond_init() 來初始化
- pthread_cond_wait (&theCV, &somelock)
- pthread_cond_signal (&theCV)
- pthread_cond_broadcast (&theCV)
- 上圖執行順序如下：
1. action() 進入 CS，呼叫 `thread_cond_wait` 並釋放 lock
2. counter() 取得 lock 進入 CS
3. counter() 呼叫 `singal()` ，action() 被喚醒，注意這時候 action() 是沒有 lock 的
4. counter() 釋放 lock
5. action() 取得 lock 並執行函式
#### ThreadPool Implementation
一次創建一定數量的 threads，讓系統不用一直增刪 threads，並且讓系統可以有效控制 threads 的數量，避免過多的 context switch 反而降低效率，達到效能最佳化。

創建 threads 後，為了讓 threads 執行不同的 function，會建立一個 `threadpool_task_t` 的結構體，存放函式及對應參數的指標，因此 threads 在經過 while loop 被喚醒之後，執行目前看到 `threadpool_task_t` 的函式，等於處理了一個 request，處理完成後進入 wait 狀態，等待下次被喚醒。而 threads 要如何知道被喚醒，其中一個方式是透過 Condition Variable 判斷
以下程式碼為一個簡單的範例：

1. 創建 threads pool 以及 task 的 queue
2. thread 執行 while loop 處於 wait 狀態
3. 若 thread 被喚醒則離開 while loop，並執行 queue 中 pool->head 的函式
4. 執行後 pool->head 加 1，再判斷該值是否等於 `queue_size`，若相等表示已經執行到最後一個函式，將 `pool->head` 設為 0
5. 離開 critical section 執行任務

### Hardware Support
Critical Section Problem 的發生是因為 shared variable 的修正可能被打斷，若某些指令我們可以一行完成，就可以避免 race condition 的問題。前面都是在說軟體上的支援，若硬體可以將指令變成 `atomic instructions` ，就沒有同步的問題
- atomic : 無法中斷執行的最小單元
- 例如 : `TestAndSet(var)`, `Swap(a,b)`
#### Atomic Test And Set()
注意以下程式碼不符合 Bounded waiting
#### Atomic Swap()
先 call Swap 的取得進入 critical section 的權力，執行完成後將 token 還給 lock。注意以下程式碼不符合 Bounded waiting

### Semaphores
- `Samaphores` 是一個通用的同步處理工具，其紀錄某個資源有多少 units 可以去使用
- 若 # of record = 1 --> binary semaphore, 但其實用 mutex lock 就好
- 若 # of record > 1 --> counting semaphore
- 利用兩個 atomic operations `wait` & `signal` 來存取 (注意與 critical section 的 wait & signal 不同)
- 簡單的 Spinlock 以 semaphore 實作
- Semaphore 為 POSIX 標準庫之一，不屬於 Pthread，所以使用上不限於 thread ，也可以用於 Process
#### Non-busy waiting Implementation
Busy waiting (SpinLock) 因為 while loop，執行效率沒有被最佳化，所以相對 busy waiting 就有 non-busy waiting 的實作方式，但 system call 要考慮 context switch、re-scheduing 的影響，成本比 while 來得高。一般來說，等待時間很短的，我們會用 busy waiting，反之則使用 non-busy waiting
- Semaphore 為一個有 `queue` 的結構體，包含 Semaphore 的值以及有哪些 Processes 等待被執行
- wait() & signal()
- 使用 system calls: sleep() & wakeup()
- 一樣必須為 atomic 的操作
- 必須先進行 value--(++) 操作，避免進入 if 區域後被 sleep 無法執行
- 由於 `value--(++)` 還有 queue 的 insert, delete 等，必須確保 `wait()` & `signal()` 為 atomic 操作
- single-processor : 透過 disable interrupts
- multi-processor :
- HW Support (e.g. Test-And-Set, Swap)
- SW Support (Peterson’s solution, Bakery algorithm)
- Semaphore with Critical Section
- 將 `value--(++)` 以及 queue 的操作包進 critical section
- 因為 `sleep()` 及 `wakeup()` 為 system calls，無須擔心同步的問題， OS 會妥善處理，所以不用包進 critical section 中(也不該包進去)
#### Cooperation Synchronization
- 有些情況不同 Process 間的執行順序很重要，考慮兩個 thread P1 & P2 分別執行 S1 & S2，S2 必須在 S1 完成後才可執行
- 實作方式 : 利用 shared variable `semaphore sync` ，以下程式碼確保 S1 一定先執行完成
- 更複雜的情況概念相同，由上述兩個 Processes 的例子做延伸
### Classical Synchronization Problems
常見的問題如下：
1. Bounded-Buffer (Producer-Consumer) Problem
2. Reader-Writers Problem
3. Dining-Philosopher Problem
#### Reader-Writers Problem
- 標準在處理 I/O 會遇到的問題
- A set of shared data objects
- A group of processes
- reader processes (read shared objects)
- writer processes (update shared objects)
- writer process 對 shared object 有獨佔權
- 不同的種類
- first RW problem : 只要確定 writer 有 access 的獨佔權即可，不關心 reader 要等多久，或要做什麼事情。reader 取得 token 時，可以傳給其他 reader，可能造成 writer 一直被其他 reader 插隊，永遠拿不到 lock
- second RW problem : 不只要確定 writer 的 access 權限，另外當 writer ready 且 object 被釋放時，writer 的優先性必須高於 reader ，不可有新的 reader 進來插隊

**First Reader-Writer Algorithm**
- writer 為 binary semophore
- Reader 共享一個 block
- `readcount` 計算有幾個人要讀
- 當 `readcount > 1` 時，代表已經有 reader 拿了 lock，所以這個 reader 也可以讀
- 當 `readcount = 1` 時，因為是第一個 reader，可能要等 writer 結束才可讀取
- 當 `readcount= 0` 岱表示最後一個讀的，讀完後要 signal writer
- `readercount` 為 shared variable，必須受到保護
- Writer可能會有 *starvation problem* ，因為只要有 reader 在讀，其他 reader 都可以進入 critical section，造成 writer 一直在等待狀態

// mutual exclusion for write 
semaphore wrt=1
// mutual exclusion for readcount
semaphore mutex=1
int readcount=0;

// writer
Writer(){
    while(TRUE){
        wait(wrt);
        // Writer Code
        signal(wrt);
    }
}

// reader
Reader(){
    while(TRUE){
        wait(mutex);
        readcount++;
        if(readcount==1)
            wait(wrt);
        signal(mutex);
        
        // Reader Code

        wait(mutex);
        readcount--;
        if(readcount==0)
             signal(wrt);
        signal(mutex);
    }
}

#### Dining-Philosopher Problem
- 5 個人坐在 5 張椅子上，且有 5 支筷子
- 每個人只會思考或是吃飯
- 思考時與剩下 4 個人沒有互動
- 每個人要用餐需要兩支筷子
- 一個人 1 次只能拿 1 支筷子
- 吃完飯後，將兩支筷子都放下
- 若每個人都拿其中一邊的筷子，就 deadlock 了
- starvation problem

### Monitor
雖然 semaphores 提供非常便利及有效的同步機制，但正確性主要是依賴 programmer
- 所有存取 shared data object 的 processes 都需確保 wait() & signal() 的執行順序及位置正確
- 但是人總有可能犯錯
- 可以將 Moniter 想成一個特殊 class (high level language construct)，每一個 Moniter 都有可能發生 race condition 的 local variable (對應下圖的 shared data) 需要保護，而要操作這些 var 必須透過 Moniter 的 method。
- Monitor 與 OO 最重要的差異為，Monitor 一次只有一個 thread 可以執行其 method。(但可以很多個 threads 同時 call 這個 method，只是會處於 inactive 狀態)
- monitor 利用 queue 做排程，確保一次只有一個 process 是 active 的，保護 shared data
#### Monitor Condition Variables
- 為了允許 process 等待 monitor，需要宣告 condition variable，例如 `condition x, y`;
- condition variable 只能與 `wait()` 及 `signal()` 一起使用
- x.wait()
- 代表調用這個 operation 的 process 被閒置，直到其他 process 完成為止
- x.signal()
- 啟動一個等待中的 process，若沒有 process 處於等待狀態，則 `signal()` 操作沒有任何影響。與其相反，semophore 的 `signal()` 一定會改變 semaphore 的狀態 (`wait` 把 counter 減 1; `signal` 把 counter 加 1)
- 在 monitor 當中，condition variable 不是 counter 而是一個佇列，所以 x.wait() 類似把 process 放到 waiting queue (enqueue)，而 signal 則是在 dequeue，所以如果 queue 是空的，signal 就沒有任何作用
- Monitor 可以有很多個 threads 存在，但一次只有一個 active
#### Dining Philosophers Example
**monitor type**
- 建立三個狀態 `thinking`, `hungry` & `eating`
- 建立 shared variable `self[5]`，存放每個人的狀態
- P.S. 可以用 shared variable 都還算好解決，難解的是無法得知他人狀態的問題
- 定義 4 個 method

monitor dp {
    enum {thinking, hungry, eating} state[5]; //current state
    condition self[5]; //delay eating if can’t obtain chopsticks
    void pickup(int i) // pickup chopsticks
    void putdown(int i) // putdown chopsticks
    void test(int i) // try to eat
    void init() {
        for (int i = 0; i < 5; i++)
            state[i] = thinking;
    }
}

- void pickup(int i)
- 將狀態設為 `hungry`，代表要吃東西了
- 測試拿筷子後是否可以吃
- 若狀態沒有改變，表示測試失敗，把自己放到 wating queue

void pickup(int i) {                
state[i] = hungry;                  
test(i); // try to eat               
if (state[i] != eating)                  
    // wait to eat                   
    self[i].wait();             
}   

- voild putdown(int i)
- 吃完了將狀態改為 `thinking`
- 告知左右兩邊進行測試，看有沒有辦法吃

void putdown(int i) {
state[i] = thinking;
// check if neighbors are waiting to eat
test((i+4) % 5); 
test((i+1) % 5);
}

- void test(int i)
- 若左右兩邊的人都沒在吃，代表左右兩邊手上都沒筷子，還要確認自己是否想吃東西
- 都符合的話，將狀態改為 `eating` 並喚醒 thread/process

// t## Ch7 Deaklock

### Deadlock Problem
- 一系列被 blocked 的 processes 持有部份資源且都在等待獲得其他 processes 擁有的資源
- Ex1: 2 processes and 2 tape drivers
  - 每一個 process 擁有一個 tape drive
  - 每一個 process 要求其他的 tape drive
- Ex2: 2 processes and semaphores A &
  - P1 (holb B, wait A): wait(A), signal(B)
  - P2 (holb A, wait B): wait(B), signal(A)
#### 必要條件
- Mutual exlusion
  - 一次只能有一個 process 可以使用資源
- Hold & Wait (同時 Hold & Wait)
  - 一個 process 持有某些資源且等待其他 processes 擁有的資源
- No preemption (有些情況很難保存 state 或保存的 cost 很高)
  - 資源只能被持有的 process 自己放棄
- Circular wait
  - 存在一系列等在中的 processes {P0, P1, …, Pn} 形成環狀等待
  - P0 -> P1 -> P2 -> … -> Pn -> P0
- 當以上*四個條件*都發生時，才會有可能的 deadlock 的情況發生
#### System Model
- 資源類型 R1, R2,…,Rm
  - 如 CPU, memory pages, I/O devices
- 每一個資源類型 Ri 有 Wi 個 instance
  - 如一個電腦有兩個 CPUs
- 每一個 process 使用資源方式如下
  - Request -> use -> release
#### Resource-Allocation Graph
- 3 個 processes, P1 ~ P3
- 4 個 resources, R1 ~ R4 (資源可能有多個 instances)
  - R1 & R3 各有一個 instance
  - R2 有兩個 instance
  - R4 有三個 instance
- Request edges
  - P1 -> R1: P1 要求 R1
- Assignment edges
  - R2 -> P1: 一個 R2 的 instance 被 assign 給 P1
- 若圖上有 *circular* 存在，則*可能*有 deadlock 存在
- 左圖有 deadlock，右圖沒有 deadlock  
![](img/Ch7.Deadlock.jpg)![](img/Ch7.Cycle_No_Deadlock.jpg)  
#### Deadlock Detection
- 若圖沒有 cycle --> 沒有 deadlock
  - 因為 Circular wait 不會形成
- 若圖有 cycle
  - 若每一個資源類型都只有一個 instance --> deadlock
  - 若每一個資源類型都有多個 instance --> 可能會 deadlock
#### Handling Deadlocks
- 方法1.，確保系統永遠不會進入 deadlock 的狀態
  - deadlock prevention: 確保四個條件中至少一個條件沒有滿足
  - deadlock avoidance: 分配資源前，Run-time 動態地檢查目前資源分配的狀況
- 方法2.，允許 deadlock，發生再想辦法修復
  - deadlock detection
  - deaklock recovery
- 方法3.，忽略問題且假設系統中永遠不會發生 deadlock
  - 大多數作業系統使用此方法，包含 Unix 系統
### Deadlock Prevention
- Mutual exclusion (ME): 將不需要 ME 的資源取消 ME
  - read-only 的資料不需要 mutual exclusion
  - 但有些資源不能共享，如 critical section、printer 等
- Hold & Wait:
  - 當一個 process 請求資源時，process 不能持有任何資源
  - 必須讓所有的資源一次性地都有對應的 process 處理，才進行下一步動作
  - 缺點是資源使用率非常低，可能很多 process 一直在 acquire 跟 release，沒辦法真正的執行
- No preemption:
  - 當 process 在等待資源時，該 process 持有的所有資源必須 preempted 掉
    - e.g. P1 請求目前被 P2 使用的 R1，而 P2 在等待 R2
    - P2 紀錄目前執行的狀態後，R1 可以被 preempted 掉，並重新分配給 P1 使用
    - 適合用在容易紀錄及恢復狀態的資源，如 CPU 的 register (context switch) 或 memory
- Circular Wait:
  - 對所有資源類型加上 total ordering，讓資源的取得有方向性
  - process 依遞增的順序來取得資源
    - 若$R=R_0,R_1,...,R_N$為一系列資源
    - 當 process 要求 $R_k$時，必須將所有$R_i,i>=k$ 釋放掉才可拿取資源
  - 例如現在有三個資源 F(tape drive) = 1, F(disk drive) = 5, F(printer) = 12，process 在拿 printer 的資源時，一定要將 printer 釋放掉，才能拿 tape & disk drive
  - 證明：要形成 Circular Wait，一定有以下情況
    - $P_0(R_0)->R_1,P_1(R_1)->R_2,...,P_N(R_N)->R_0$
    - 但這樣代表 $R_0$ 必須大於 $R_N$，產生矛盾

### Deadlock Avoidance
若無法做 Preventon，則必須在 run time 期間進行動態檢查
#### Avoidance Algorithms
- Single instance of a resource type
  - resource-allocation graph (RAG) algorithm based on circle detection
- Multiple instances of a resource type
  - banker’s algorithm based on safe sequence detection
#### Resource-Allocation Graph (RAG) Algorithm
- Request edge:
  - $P_j->R_j$，$P_j$在等待$R_j$的資源
- Assignment edge:
  - $R_j->P_j$，$R_j$被$P_j$所持有
- Claim edge:
  - $P_j->R_j$，$P_j$在未來可能要求$R_j$
  - 當 process 要求資源時，claim edge 轉換成 request edge
- 當資源被 process 釋放時，Assignment edge 轉換成 Claim edge

- Avoidance 基本上使用有向圖的方式建立 Claim edge，確認當任務 Assign 時是否有 Loop 產生，若產生迴圈則將拒絕或延遲該請求，如下圖 $P_1−>R_2$的請求在該狀況下不會被同意  
![](img/Ch7.Resource-Allocation_Graph_Algorithm.jpg)  
- Cycle detection 的演算法為 $O(n^2)$
#### Multiple instances
- Safe state: 若存在 sequence allocation 滿足所有 process 的請求，則系統處於 safe state
  - 此 sequence of allocation 稱為 safe sequence
- safe state -> no deadlock
- unsafe state -> 可能有deadlock
- deadlock avoidance: 確保系統永遠不會進入 unsafe state  

**Safe State with Safe Sequence**
- 有 12 個 tape drives
- t0 的狀態如下  
![](img/Ch7.Safe_State_with_Safe_Sequence.jpg)  
- $P_0$最多可能會一次要 10 個資源，才能執行下一個動作
- 目前已使用 9 個資源，剩下 3 個資源，因為$P_1$最多只需要 4 個，所以我們可以先把剩下的 3 個資源全部先給$P_1$，$P_1$執行完之後可用資源變成 5 個。這時候將 5 個資源全部給$P_0$，最後再給$P_2$就可以順利執行所有的 process，$<P_1,P_0,P_2>$稱為 safe sequence

**Un-Safe State w/o Safe Sequence**
- 仍然可能找不到 safe sequence，如下圖剩下 2 個資源，$P_1$執行後無論給$P_0$或$P_2$都不夠  
![](img/Ch7.Un-Safe_State.jpg)  
- 但仍未進入 deadlock 的狀態
- 這時候$P_0\&P_0$的請求就會被拒絕或延遲

**Banker’s algorithm**
- 適用於對每個資源是 multiple instances 的情況
- 使用通用的 *safety algorithm* 預先決定是否有 safe-sequence 存在
- 只在 safe-sequence 存在時才會去執行動作
- Algorithm：
  1. 假設 processes 需要 *Maximum resources*
  2. 找到一個 free resources 可以滿足的 process，將所有 free resources 給它
  3. 將該 process 的所有資源釋放掉
  4. 重複上述動作直到所有的 processes 都可滿足執行條件
- 範例：
  - Total instances: A=10, B=5, C=7
  - 初始 available 的 instances: A=3, B=3, C=2
  - Safe sequence 為 P1 -> P3 -> P4 -> P2 -> P0  
![](img/Ch7.Banker’s_Algorithm.jpg)  

### Deadlock Detection
偵測目前系統狀態有沒有 deadlock
- Single instance
  - 將 request/assignment edges 轉換為 wait-for graph
  - 若 wait-for 存在 circle 則有 deadlock
  ![](img/Ch7.Resource_allocation_graph_Corresponding_wait-for_graph.jpg)  
- Multiple instances: 不用管 Maximum Needs，只要確認 request 會不會造成 deadlock
  - Total instances: A:7, B:2, C:6
  - Available instances: A:0, B:0, C:0
  - safe state -> <P0, P2, P3, P1, P4> -> no deadlock
  - If P2 request = <0, 0, 1> -> no safe sequence -> deadlock  
![](img/Ch7.Multiple-Instance_for_Each_Resource_Type.jpg)  

### Deadlock Recovery
- Process termination
  - kill 全部的 deadlock processes
  - kill 一個或多個在 deadlock circle 的 process
    - 要決定哪些 process 應該被砍掉，即便砍掉 priority 最低的 process 也不一定能解決 deadlock 的問題，這是一個需獨立出來討論的議題
- Resource preemption
  - 選擇一個 victim 去 preempt
    - 哪一個應該被 preempt ?
  - rollback
    - 部份或全部 rollback ?
  - starvation
    - 若一直 preempt 相同的 process，則該 process 可能要等待很久的時間才能被執行

## CH11 File System Interface
### File Concept
- File: 為 OS 所創造的邏輯儲存單元 (logical storage unit)
  - 實體儲存單元 (physical storage unit) 則是 disk (sector, track)
- File 的屬性
  - Identifier: non-human-readable name, Name, Type, Location, Size, Protection, Last-access time, Last update time
- File 的操作
  - 創建、讀寫、repositioning、刪除、截斷 (truncate)、串接 (concatenate)
- Process 會儲存一個 open-file table
- Os 會儲存一個 system-wide table
#### Open-File Tables
- Open-file table 儲存 process 開啟的檔案資訊
  - 紀錄所有被這個 process 開啟的檔案
  - 每一個開啟檔案的指標
  - 檔案的存取權以及 Accounting information (CPU數量，真實使用的時間, 時間限制, 帳戶數量, 行程數量)
- System-wide table 儲存 OS 系統所有開啟的檔案資訊
  - open-file tables 所有檔案指向 system-wide table
  - 還會儲存獨立於 process 的資訊，如 disk location, access dates 還有 file size
  - Open count
    - 紀錄各個檔案被指向的次數，代表目前有多少 user 在存取該檔案
    - 若不同 process 存取同一個檔案，只會有一份檔案，確保資料的一致性  
    ![](img/Ch11.Open-File_Tables.jpg)  
#### Open-File Attributes
- Open-file attributes (metadata)
  - File pointer (per-process)
  - File open count (system table)
  - Dist location (system table)
  - Access rights (per-process)
- File types
  - 副檔名，如 .exe, .com, .obj …etc
  - 副檔名沒有實質意義，只是讓 OS 先嘗試用副檔名對應的應用程式開啟

### Access Method
- Sequential access: 檔案可以視為 Array of bytes，Sequential access 在讀檔時是連續讀取的，因此需要的資訊就是目前的位置以及要讀取多少長度
  - Read/write next (block)
  - Reset: 將 file pointer 重設到檔案的開頭
  - Skip/rewind n record
  - 因為硬碟磁寫頭的關係，連續的檔案讀寫效率較高
  - 邏輯上的連續，檔案儲存的實體硬碟位置不一定要連續  
  ![](img/Ch11.Sequential-access_file.jpg)  
- Direct (relative) access: 直接告訴系統要讀取檔案什麼位置的資料
  - 讀取 sequence 資料的任意元素
  - File operations 需要 block number 作為參數
  - 通常是為了 random access 的執行
  - 檔案由多個*大小固定*的區塊所組成，可直接將檔案指標移動到某個特定的區塊，並一次讀取整個區塊  
  ![](img/Ch11.Simulation_of_sequential_access_on_a_direct-access_file.jpg)  
- Index Access Methods
  - Index: 檔案各區塊的指標
  - 為了找到檔案中的 record:
  - 尋找 index file --> 找到指標
  - 利用指標去直接存取 record
  - 若檔案太大， index 有可能太大  
  ![](img/Ch11.Example_of_index_and_relative_files.jpg)  
- Physical 的硬體設備，執行 random access 類型的操作效率較低，如果要支援 random access，通常要有 memory cache 才會夠快

### Directory Structure
#### Partition, Volume & Directory
- A partition 硬碟分割 (formatted or raw)
  - raw partition (無檔案系統)： UNIX swap space, database
  - Volume 意指在硬碟格式化有了檔案系統之後的磁碟區域
  - 一個 partition 可以為硬碟的部份區域或是由多個硬碟組成 (如分散式系統)
  - 有一些儲存設備無法被分割，如 floppy disk (ex: 3.5 磁碟片)
- Dirctories 為檔案系統在 partition 儲存檔案資訊的區塊  
![](img/Ch11.A_typical_file-system_organization.jpg)  
#### Directory vs. File
- Directory: 為一群包含所有檔案資訊的節點
  - Directory structure 跟 files 都位於硬碟中  
  ![](img/Ch11.Directory_structure.jpg)  
- Directory 相關的操作
  - 搜尋檔案、創建檔案、刪除檔案、列出目錄清單(對現代檔案系統常常是效能瓶頸處，因為可能資料很多、檔案的樹狀結構很深)、重新命名檔案、遍歷檔案樹狀結構
#### Single-Level Directory
- 所有檔案都在一個 Directory 底下
- 檔案名稱必須唯一
- 當檔案越來越多，找尋檔案的效率非常差 (一定要遍歷)  
![](img/Ch11.Single-level_directory.jpg)  
#### Two-Level Directory
- 對每一個使用者有不同的 directory
- 路徑 = user name + file name
- 但是對每一個 user 來說，搜尋的效率仍然很差  
![](img/Ch11.Two-level_directory_structure.jpg)  
#### Tree-Structured Directory
- 絕對路徑： 由根節點開始
- 相對路徑： 由 directory (子節點)開始  
![](img/Ch11.Tree-structured_directory_structure.jpg)  
#### Acylic-Graph Directory
- 使用 links 來共享檔案或 directories
  - UNIX-like: symbolic link (ln -s/spell/count/dict/count)(<新連結位置> <原被連結位置>)
- 檔案可以有多個絕對路徑 (同個檔案給不同節點使用)
- 那何時檔案才真正被刪除？
  - 刪除檔案但留下 link --> dangling pointer
  - 真正保險的作法是刪除 link 但不刪除檔案，當檔案的 counter 歸零時才把檔案刪除  
  ![](img/Ch11.Acyclic-graph_directory_structure.jpg)  
#### Gerneral-Grpah Directory  
![](img/Ch11.General_graph_directory.jpg)  
- 與 Acylic-Graph 最大的差異是可能有迴圈
  - counter 在這邊無法確保 dangling pointer
  - 可能有 self-referencing file
- 所以問題在於要如何處理 dangling pointer
  - 定期做 Garbage collection
    - 首先遍歷整棵樹，標記樹可達到的檔案及 directories
    - 將沒有被標記的檔案 free 掉
    - 但是當檔案很多時效率很差，所以很多檔案系統不支援
  - 另一種解法是在檔案被建立時確認是否會產生迴圈  
  ![](img/Ch11.General-Graph_Directory.jpg)  

### File-System Mounting & File Sharing
#### File Mounting
- 要使用檔案系統時，必須先掛載到系統中，系統才能存取
- Mounting point: 意指 File System 被掛載的根路徑
- Mounting time:
  - boot time (如系統槽，作業系統也是存在檔案系統中)
  - automatically at run-time，如 usb 自動偵測
  - manually at run-time  
  ![](img/Ch11.File_System_Mounting_Example.jpg)  
#### File Sharing on Multiple Users
- 對每一個使用者會有 (userID, groupID)
  - ID is associated with every ops/process/thread the user issues
  - 一個 user 可以屬於多個 groupID
- 每一個 file 有三種屬性等級
  - owner (擁有者權限)
  - group (所屬 group 的權限)
  - others (非擁有者也非 group 成員的權限)
- 擁有者 attributes 描述擁有者對檔案操作的權限
  - group/others 也有對應的 attributes
  - group/others 的權限由 owner 或 root 決定  
  ![](img/Ch11.File_Sharing_on_Multiple_Users.jpg)  
#### Access-Control List
- 為了控制不同層級使用者的檔案權限，對每個 user 建立 Access-control list
  - 當使用者發出對檔案操作的請求時，透過 ACL 的資訊來確認是否合法
  - 但當使用者數量很多時，透過 ACL 確認太耗費資源及時間
- 現行作法是將使用者分成 3 類 --> 用 3 個 bit (RWX) 描述不同層級 user 對檔案的執行權限
  - owner (e.g. 7 = RWX = 111)
  - group (e.g. 6 = RWX = 110)
  - public (others) (e.g. 4 = RWX = 100)
  - 如下圖第一行中的 -rw-rw-r–，分別代表 owner-group-others 的權限  
  ![](img/Ch11.Access-Control_List.jpg)  
#### File Protection
- 檔案的擁有者/創建者必須能控制
  - 能執行哪些操作
  - 誰能執行這些操作
  - 由 ACL 定義
- 檔案應該要防止以下問題
  - physical damage (reliability): i.e. RAID
  - 不適當的存取: i.e. 密碼
- RAID:
  - 以下出自 Wiki
  > 容錯式磁碟陣列（RAID, Redundant Array of Independent Disks），舊稱容錯式廉價磁碟陣列（Redundant Array of Inexpensive Disks），簡稱磁碟陣列。利用虛擬化儲存技術把多個硬碟組合起來，成為一個或多個硬碟陣列組，目的為提升效能或資料冗餘，或是兩者同時提升。
  > 在運作中，取決於 RAID 層級不同，資料會以多種模式分散於各個硬碟，RAID 層級的命名會以 RAID 開頭並帶數字，例如：RAID 0、RAID 1、RAID 5、RAID 6、RAID 7、RAID 01、RAID 10、RAID 50、RAID 60。每種等級都有其理論上的優缺點，不同的等級在兩個目標間取得平衡，分別是增加資料可靠性以及增加記憶體（群）讀寫效能。  

  - 再參考 [筆記](https://hackmd.io/@Pl-eQT9CQaS0jhExKqL8_w/BkhOSR4jW/https%3A%2F%2Fhackmd.io%2Fs%2FByk4uIjGG)  
  > RAID在實體上是多顆硬碟，在系統中被當作一顆硬碟使用，而在作業系統底下，也還是可以將它分割為單一或多個分割區。因此建立好的RAID，使用起來跟單一硬碟是完全相同的，只是依組成方式的不同。RAID可以提供更大的容量、更高的讀寫效能，或是額外的「安全性」。（這裡所說的「安全性」，是指硬碟損毀之後資料重建、回復的能力，與加密防駭等功能無關）  

## Ch12 File System Implementation
### File-System Structure
#### File-System Structure
- 記憶體跟硬碟之間資料傳輸 I/O 的單位為 block
  - 一個 block 可能有多個 sector
  - 一個 sector 通常為 512 bytes
- 一個作業系統可以使用多個檔案系統
  - 如 NTFS, FAT32
- 檔案系統設計的兩個主要的問題
  - 與使用者程序的介面 (上層)
  - 與硬碟的介面 (下層)
#### Layered File System
- File System 實作上通常由以下三個部份組成
  - manages metadata: 找到 file 並提供 file handler
  - logical <–> physical mapping: 將程序要讀取內容的位置轉換成 block 的位置
  - read d1, c73…: 轉換後 physical 的 hard-drive 及 block 位置  
  ![](img/Ch12.Layered_File_System.jpg)  
- 對使用者而言，只有一個檔案系統的 Interface (FS manager) 存在，而 FS manager 會去呼叫檔案對應的檔案系統來執行  
![](img/Ch12.Layered_File_System_2.jpg)  

### File-System Implementation
#### On-Disk Structure(Structrue 要永久存在，所以一定要在 disk 上)
- Boot control block (per partition): 存放啟動作業系統相關資訊的 partition
  - 通常為 partition 的第一個 block (若是空的代表沒有 OS)
  - UFS (Unix File Sys.): boot block, NTFS: partition boot sector
- Partition control block (per partition): partition details
  - details: blocks 的數量, block 的大小, free-block-list, free FB pointers 等
  - UFS: superblock, NTFS: Master File Table
- File control block (per file): 跟檔案相關的 details
  - details: 權限, 大小, data blocks 的位置 (physical 的位置)
  - UFS: inode, NTFS: stored in MFT (relational database)
- Directory structure (per file system): organize files  
![](img/Ch12.On-Disk_Structure.jpg)  
#### In-Memory Structure
- in-memory partition table: 每個被掛載的 partition 的資訊
- in-memory directory structure: 最近存取的 directories 的資訊
- system-wide open-file table: 保存每一個被開啟檔案的 File Control Block
- per-process open-file table: 記錄僅跟 process 有關的資訊，比如讀檔位置、開檔權限等，另外會有 pointer (file handler/descriptor) 指到對應的 system-wide table entry
####  File-Open & File-Read
- 開檔時，會先去 directory structure 看檔案是否在記憶體中，若不存在則去硬碟把檔案的 directory structure 資訊讀進來，找到我們要的節點並指向 file control block，這樣就有了檔案的所有資訊
- 讀檔時，File handler 為 per-process open-file table 的某一個 entry，拿到 handler 確保檔案的確 open 之後，必須從 system-wide table 取得檔案的實際位置，才能從硬碟存取檔案內容  
![](img/Ch12.File-Open&File-Read.jpg)  
#### File Creation Procedure
1. 作業系統配置一個新的 FCB
2. 更新 directory structure
   - OS 將對應的 directory structure 讀進記憶體中，檢查有無同名稱的檔案
   - 將新的檔案名稱以及 FCB 更新進 directory structure
   - (在檔案關閉後) OS 將 directory structure 寫回硬碟中
3. 檔案出現在 user 的 directory command
#### Virtual File System
- VFS 提供物件導向的方法實作 file system
- 對於不同檔案系統，VFS 使用同一個 system call interface
- VFS 依 partition info 呼叫適當的 file system routines
- 在 Linux VFS 中有 4 個主要的物件類型
  - inode --> 單獨的檔案 (on disk)
  - file object --> 開啟的檔案 (檔案開啟後的操作物件)
  - superblock object --> 整個 file system (對應到 partition)
  - dentry object --> 單獨的 directory entry
- VFS 定義一系列需要實作的操作
  - int open(…) --> 開啟檔案
  - ssize_t read() --> 讀取檔案
#### Directory Implementation
- Linear lists (Linked list)
  - 檔案名稱的串列，且有相應的指標指向 data blocks
  - 容易實作但 performance 差
    - insertion, deletion, searching
- Hash table --> linear list w/ hash data structure
  - O(1) 搜尋時間
  - 每一個 hash key 對應到一個 linked list，避免 hash collision
  - hash table 通常有固定數量的 entry 數量  
  ![](img/Ch12.Directory_Implementation.jpg)  

### Allocation Method
#### Contiguous allocation
- 檔案在硬碟中的 block 擺放位置要連續
  - 不需要 traverse 整個硬碟，只要簡單的計算就知道檔案在哪一個 block --> *磁頭轉動的數量最小化*
  - Directory entry 只要存 start 跟 length，非常簡單
- 無論是 sequential 或 random 的存取都可以有效率地實作
- 很容易有 External fragment
  - 解法 --> compaction
- 檔案不能隨意地增長
  - 解法 --> extend-based FS (跟 linked list 結合)
#### Extent-Based File System
- 許多新的 file system 使用 modified contiguous allocation scheme
- extent 是一個硬碟連續的 blocks
  - 一個檔案可以有一個或多個 extents
  - 一個 extent 若用完了，系統會給檔案另一個 extent，利用 linked list 串起來
  - extents block 必須有一個 pointer 紀錄下一個 extent 的位置
- 缺點
  - Random access 的成本增加 (例如檔案在第三個 extent，必須要讀前兩個 extent 才知道第三個 extent 的位置，增加硬碟讀取的次數)
  - 仍然有 internal & external 的 fragment  
  ![](img/Ch12.Extent-Based_File_System.jpg)  
#### Linked Allocation
- 檔案由一個 linked list of blocks 所組成
  - 每一個 block 有 pointer 指向下一個 block
  - 因為需要空間放 pointer，所以 block 中實際存放的大小為 block size - pointer size
- Directory 只需要存起始跟結束的 block id
- 建立新檔案時並不需同時就宣告檔案大小
- 缺點
  - 只適合 sequential-access
    - random access 需要遍歷 linked list
    - 因為 link pointer 存放在 block 中，每次存取 block 硬碟都要讀取一次
  - 需要 pointer 的空間 (4/512 = 0.78%)
    - 解法：unit = cluster of blocks (把很多 blocks 組成一個大的 blocks，減少遍歷的長度)
    - 會有 internal fragment 的問題
  - Reliability
    - 只要遺失一個 link 等於整份檔案遺失  
    ![](img/Ch12.Layered_File_System_2.jpg)  
#### FAT (File Allocation Table) file system
- FAT32
  - 在 MS/DOS & OS/2 中使用
  - 將 links 存成一個 table (所有檔案的 links)
  - 每一個 table entry 大小為 32 bits
  - 放在 partition 的起始點  
![](img/Ch12.FAT32.jpg)  
- FAT (table) 通常會 cache 在記憶體中
  - Random access 的效率改善
  - 硬碟只要讀取 FAT 就可以找到檔案 block 的位置
#### Indexed Allocation Example
- Diretory 擁有 file index block 的 address
- 每一個 file 有自己的 index block
- index block 儲存檔案資料的 block id
- 將所有 blocks 的 pointer 集中存在一個 block 中
- 優點
  - direct & random access 非常有效率
  - 沒有 external fragmentation
  - 很容易去建立檔案 (只要有 free list，就知道哪裡有空間放檔案)
- 缺點
  - 需要額外放置 index 的 blocks，這些 blocks 只能放 index，空間被浪費掉
  - 另一個問題是，當檔案太大，一個 index block 存不下時，那 index block 應該要多大？
    - linked scheme
    - multilevel index
    - combined（inode in BSD UNIX） 
    ![](img/Ch12.Indexed_Allocation_Example.jpg)  

**Linked Indexed Scheme**
- 將 index blocks 用 linked list 串起來
- 適合 small to medium size 的檔案  
![](img/Ch12.Linked_Indexed_Scheme.jpg)  
**Multilevel Scheme (two-level)**
- 第一階的 index block 儲存第二階 index blocks 的指標
- 第二階 index blocks 的指標才指向 file blocks
- 適合 large size 的檔案  
![](img/Ch12.Multilevel_Scheme.jpg)  
**Combined Scheme: UNIX inode**
- File pointer: 4B (32 bits) --> 只能存放 4GB ($2^{32}$) 的檔案
- 可以讓不同大小的檔案，使用不同類型的 index scheme，提昇檔案讀取的效率
- 假設一個 block 的 entry 數量為 12，綠色因為每個 index blocks 還要存 2 個其他 index - blokcs 的 pointer，所以檔案大小乘上 $2^{10}$  
![](img/Ch12.UNIX_inode.jpg)  

### Free-Space Management
- Free-Space list: 紀錄所有硬碟中 free 的 blocks
- Scheme
  - Linked list (same as linked allocation)
  - Grouping (same as linked index allocation)
  - Counting (same as contiguous allocation)
- 檔案系統通常用與管理檔案相同的方式管理 free space
#### Bit vector
- Bit Vector (bitmap): 一個 block 一個 bit 來表示，0 為 free; 1 為 occupied
- 優點
  - 簡單且快速 (硬體支援 bit-manipulation instruction)
- 缺點
  - 為了效能必須存在快取中，當檔案很大時 bitmap 會非常大，超過快取的空間
  - 例如一個 1TB(4KB block) 的硬碟需要 32MB 的 bitmap  
  ![](img/Ch12.Bit_vector.jpg)  
#### Grouping & Counting
- Linked List
  - 所有的 free blocks 利用 linked-list 串在一起
  - 將第一個 free block pointer 存在 disk 和快取中的特別位置
  - 遍歷 list 效率低
  - 可參考 FAT 的作法所有的 link-pointers 存在一個 table 當中
- Grouping
  - 與 linked-index allocation 一樣
  - 將 n free blocks 的 address 放在 1st block
  - 前（n-1） pointers 是 free blocks
  - 最後一個 pointers 指向另一個 grouping block
- Counting
  - 與 contiguous allocation 一樣
  - 儲存第一個 free block 的指標和 contiguous free blocks 的數量
 
## Ch10 Mass Storage Structure
### Disk Structure
- 硬碟被 addressed 為一維的 logical blocks 陣列
  - logical block 為最小的轉換單位，一個 block 有很多個 sector
- Logical block 以 sequential 的方式映射到硬碟當中
  - Sector 0 為最外圈 1st track 的 1st sector
  - 從最外圈到最內圈  
  ![](img/Ch10.Disk_Mechanism.jpg)  
#### Sectors per Track
- Constant linear velocity (CLV)
  - 每一個 track bits 的密度相等
  - 外圈有更多的 sectors
  - 保持相同的 data rate
    - 所以內圈的旋轉速度要加快
  - 應用： CD-ROM & DVD-ROM
- Constant angular velocity (CAV)
  - 保持相同的旋轉速度
  - 內圈的 bit density 較高
  - 保持相同的 data rate
  - 應用：硬碟
#### Disk I/O
- 硬碟逆用 I/O bus 跟電腦連接
  - EIDE, ATA, SATA (Serial ATA), USB, SCSI 等等
  - I/O bus 利用 controller 來控制
    - Host controller (computer end)
    - Disk controller (disk drive 內建)

### Disk Scheduling
#### Introduction
- Disk-access 時間主要分成三個部份
  - seek time: 將讀寫頭移到需求的環上 (因為移動磁頭是機械式的行為， seek time 是影響硬碟讀取時間最主要的成份，scheduling 要盡可能讓磁頭在讀取多個檔案時能沿著一個方向移動)
  - rotational latency: 旋轉讀寫頭到需求的 sector 上
  - read time: 資料轉移的時間
- Disk bandwidth
  - bytes transferred/(完成最後一個請求的時間 - 開始讀取的時間)
#### Disk Scheduling
- 最小化 seek time
- 處理硬碟 I/O 請求的算法
  - FCFS（first-come, first-served）
  - SSTF（shortest-seek-time-first）
    - 普遍使用，但不是最佳的算法，且可能有 starvation 的問題
    - 適合 loading 輕的情況
  - SCAN
    - 在高負載的情況下表現佳
    - 沒有 starvation 的問題
  - C-SCAN（circular SCAN）
  - SCAN 的延伸，讓等待時間更為平均
  - LOOK and C-LOOK
#### FCFS (First-Come-First-Served)
- 對磁頭移動來說，只關心 track 的 ID
- 假設現在的 request queue 為 98, 183, 37, 122, 14, 124, 65, 67，Head pointer 為 53，總移動量為 640  
![](img/Ch10.FCFS.jpg)  
#### SSTF (Shortest-Seek-Time-First)
- SSTF 排程為 SJF 的一種，可能導致 starvation 的問題
- 總移動量為 236  
![](img/Ch10.SSTF.jpg)     
#### SCAN Scheduling  
- 磁頭先往一邊走再往另一邊走
- A.K.A elevator algorithm
- 各個請求被讀取的時間容易不平均 (ex: 若磁頭往左邊移動但新請求剛好再最右側)
- 總移動量為 236  
![](img/Ch10.SCAN.jpg)
#### C-SCAN Scheduling
- 磁頭只往一個方向移動
- 同方讀到底之後，會直接回到另一頭 (Round-Robin)
- 各個讀取時間比 SCAN 算法更為平均
- 總移動量 382  
![](img/Ch10.C_SCAN.jpg)  
#### C-Look
- 會看是否有新的請求與目前磁頭移動方向同向，有的話繼續延該方向移動
- 若同方向沒有新的請求，則磁頭不會回到最開頭，會從另一個方向最靠近目前位置的請求開始
- 若決定好移動位置，但此時有個介於之間的請求進來 (如 53 -> 65，決定了之後 64 才進來)，必須要等到下一次才會被讀取  
![](img/Ch10.C_LOOK.jpg)  
### Disk Management
#### Disk Formatting
- Low-level formatting (or physical formatting):
  - 硬碟出廠時，已完成格式化作業
  - 將 disk （magnetic recording material）切分成數個 dist controller 可讀寫得 sectors
  - 每個 sector = header + data area + trailer
    - header & trailer 存放 sector 的數量及 ECC (error-correcting code)
    - ECC 藉由所有在 data area 的 bytes 計算，用 trailer 的 ECC 檢查硬碟有無壞軌
    - data area size 通常為 512B, 1KB or 4KB
- OS 接著做以下兩個步驟來使用硬碟
  - 將硬碟 partition 成一個或多個 groups of cylnders
  - logical formatting (建立 file system)
#### Boot Block
- Bootstrap program
  - 初始化 CPU, registers, device, controllers, memory 並且啟動 OS
  - 第一階段 bootstrap code 存放在主機板的 ROM (Read Only Memory)
  - 完整的 bootstap 放在 boot block of boot disk (系統碟)
- Booting from a Disk in Windows 2000
  1. 執行 ROM 中的 bootstrap code
  2. 讀取 MBR (Master boot recode) 的 boot code
  3. 利用 partition table 找到 boot 的 partition 位置
  4. 讀取 boot sector/block 並繼續開機作業  
  ![](img/Ch10.Windows_Booting.jpg)  
- Bad Blocks
  - Simple disks like IDE disks
    - 人工執行格式化程式來標記 bad block 對應的 FAT entry
    - 壞軌的區域不允許用來 allocation
  - Sophisticated disks like SCSI disks
    - disk controller 會維護一個 bad blocks list
    - List 在硬碟的生命週期會持續更新
  - Sector sparing (forwarding): 將壞軌區的資料 map 到備用的區域
    - 可能會影響到 disk-scheduling 的表現 (Physical 位置不連續)
    - 在硬碟 formatting 時，每個 cylinder 會留少數備用的 sectors
  - Sector slipping: 若要避免 physical 位置不連續的問題，則必需將整個資料做搬移
- Swap-Space Management
  - Swap-space: 虛擬記憶體使用硬碟空間 (swap-space) 作為主記憶體的延伸
  - UNIX: 允許使用多個 swap spaces
  - Location
    - 一般檔案系統的一部分 (e.g. NT)
      - 效率較差
    - 獨立的 partition (raw partition)
      - 效率較好
      - 但 Size 固定
    - 允許上面兩種方式 (e.g. Linux)
- Swap Space Allocation
  - 1st version: process 創建時放在記憶體，並複製一份完整的內容到連續的硬碟空間。主要問題是所有內容都複製，造成空間浪費
  - 2nd version: 只複製要被 swap 的 pages 到 swap space
    - Solaris 1:
      - text segments(程式碼) 可以從檔案系統讀取，所以當 swap out 的時候直接捨棄
      - 只有 anonymous memory (stack, heap, etc) 這些動態配置的記憶體空間，在虛擬記憶體創建時，會存到 swap space
    - Solaris 2:
      - 更進一步只有當動態配置的記憶體空間需要被 swap out 時，才動態配置 swap-space，而非虛擬記憶體創建時就建立副本  
      ![](img/Ch10.Linux_Swapping.jpg)  

### RAID
- RAID (Redundant Arrays of Inexpensive Disks)
  - 用多個便宜的硬碟組成
  - 利用 redundancy 提昇可靠度
  - 藉由 parallelism 提昇效能
- RAID 排成不同 levels
  - Striping: 將檔案切割放到多個硬碟上
  - Mirror (Replication): 備份
  - Error-correcting code (ECC) & Parity bit: 產生 redundant 的 code 來做 Error detection 甚至檔案修補
#### RAID 0 & RAID 1
- RAID 0: non-redudant striping
  - 透過平行讀取增加效率
  - I/O 的 bandwidth 與 striping 的數量成正比
    - 若有 N 顆硬碟，則讀寫的頻寬提昇 N 倍
- RAID 1: Mirrored disks
  - 藉由 redundancy 提昇可靠度
    - 讀取的頻寬與硬碟數量成正比
    - 寫入的頻寬保持不變，甚至比單顆硬碟還差一些  
    ![](img/Ch10.raid0.jpg)![](img/Ch10.raid1.jpg)  
#### RAID 2: Hamming code
- 以 Hamming code 將資料編碼後分割成獨立的位元
- 在資料中加入錯誤修正碼
- e.g.: Hamming code(7, 4)
  - 4 data bits (在 4 個 disks 上) + 3 paritu bits (在 3 個 disks 上)
  - 每一個 parity bits 為 3 個 data bits 的線性編碼
- 當有一個 disk 失效時，可以復原資料
  - 可以偵測到兩個 disks(bits) 的錯誤
  - 但只能還原 1 bit 的錯誤
- 比 RAID 1 更好的空間使用率 (RAID 1 100% redundancy v.s. RAID 2 75 % redundancy)  
![](img/Ch10.raid2.jpg)  
#### RAID 3 & 4: Parity Bit
- 雖然 RAID 2 可以偵測硬碟錯誤，但 disk controller 就能夠偵測 sector 的讀取是否正確
  - 因為 low level 的 controller 會提供哪個 sector 壞掉，所以 1 個 parity bit 就足夠修正 1 個 disk 的失效
- RAID 3: Bit-level striping; RAID 4: Block-level striping
  - 優點是更好的空間使用率 (33% overhead)
  - 缺點是計算與儲存 parity bit 的 cost  
  ![](img/Ch10.raid3.jpg)  
- RAID 4: 因為 controller 不需要從多顆硬碟重建 block，有更高的 throughput
  - RAID3 一個 byte 會跨多顆硬碟，速度取決於最慢的那個 bit; 而 RAID 4 可以一次從單顆硬碟讀取多個 bits 的資料  
  ![](img/Ch10.raid4.jpg)  
#### RAID 5: Distributed Parity
- RAID 2~4 都把 parity 集中在單獨的一群硬碟中，對使用者來說這些硬碟等於不存在
- RAID 5 則將資料及 parity 放在一起
- 可以避免過度使用單一顆硬碟
- RAID 3 & 4 讀的時候可以平行處理，但寫的時候因為 parity bits 集中擺放，等於只有一顆硬碟的效率  
![](img/Ch10.raid5.jpg)  
- RAID 5 讀取的 BW 增進 N 倍
- RAID 5 寫入的 BW
  - 法一: 
    1. 讀取所有未變動的資料 (N-2) bits, 
    2. 重新計算 parity bit, 
    3. 將變動及 parity bit 寫回硬碟
    - BW = N / ((N-2) + 2) = 1 倍 --> 完全沒變
  - 法二: 
    1. 只讀取變動及 parity 的 bit, 
    2. 利用更新前後的差異計算新的 partiy, 
    3. 將變動及 parity bit 寫回硬碟
    - BW = N / (2+2) = N/4 倍 --> 有加速效果
- RAID 6: P+Q Dual Parity Redundancy
  - 類似 RAID 5, 但儲存更多的 redundant 資訊來防止多顆硬碟失效的情況
  - 使用 ECE code (i.e. Error Correction Code) 而非 single parity bit
  - Parity bits 通常也 strips 到多顆硬碟中
  - 複雜度及 overhead 高，除非資料真的很重要，一般不會採用這種實作   
  ![](img/Ch10.raid6.jpg)  
#### Hybrid RAID
- RAID 0+1: Stripe then replicate
- RAID 1+0: Replicate then stripe  
![](img/Ch10.raid01.jpg)  
![](img/Ch10.raid10.jpg)  



## https://www.youtube.com/watch?v=JquP9NXoa0Y&list=PLS0SUwlYe8cxj8FCPRoPHAehIiN9Vo6VZ&index=37





## References
- [周志遠教授作業系統講義](https://ocw.nthu.edu.tw/ocw/index.php?page=course_news_content&cid=141&id=999)
- [作業系統 Operating System 筆記](https://hackmd.io/@Chang-Chia-Chi/OS)
- [Operating Systems Course Notes Main Page](https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/)
- [作業系統OS](https://hackmd.io/@Pl-eQT9CQaS0jhExKqL8_w/BkhOSR4jW)
- [Operating System Concept 9th edition](https://www.os-book.com/OS9/slide-dir/index.html)
- [Mr. Opengate.](https://mropengate.blogspot.com/2017/09/operating-system-concepts.html) 
- https://hackmd.io/@YiZjennnnn/process_scheduling
- [MarkDown語法大全](https://hackmd.io/@mrcoding/ryZE7k8cN)