# 作業系統 Introduction & OS Structure
[TOC]

## Ch1 Introduction
### Operating System:a Program
- 介在 hardware 跟 application program 之間
- kernel program
- runnint all the time（除非關機）
- 資源管理
- manage all resource
- fair and efficient
- control program
- control execution of program
- to prevent errors and improper use
- interrupt base
- interrupt:中斷 CPU 正在做的事

### Interrupt
- step
- CPU 叫 device 去做任務（device 可能是硬體也可能是軟體）
- Device 做事期間 CPU 去做別的事
- Device 完成後發出 **interrupt** 給 CPU（IRQ）
- CPU 回來處理後續的事情(執行 ISR)
- 這裡要把 **registers** 紀錄本來在做的事存到 **memory(DRAM)**
- CPU 去做下一件事
- Type
- External Interrupt
- CPU 以外的 component 引發的
- Ex. I/O
- Internal Interrupt
- CPU 本身引發的
- Software Interrupt（traps）
- User 需要 OS 提供服務
- service routine
- Interrupt vector
- 紀錄 interrupt 的 address
- jump to ISR
- Interrupt service routine(ISR)
- 處理 Interrupt
- 高優先級
- 處理時間短

### Memory Manage

#### DMA
- CPU move data between memory and device buffer(local buffer?)in usual.
- Device controller can transfer data from local buffer to main memory w/o CPU inter vention.
- Raise in terrupt when DMA transfer is done.


#### Caching
- 把常用的資料存在較高級的 memory
- 不局限於 cache

#### main memory
data 跟 instructions 在執行之前就要被放進 memory
要決定「要把什麼放進記憶體」，目標是最佳化 CPU 的使用

Memory management 會做的事：
- allocating and deallocating memory space
- 追蹤哪些 memory 正在被使用？被誰使用？
- 決定哪些 processes 跟 data 要被放進 / 移除記憶體

#### storage mamagement
Disk 硬碟容量的管理
OS 會統一顯示容量的資訊

##### file system

OS 提供統一的介面

### I/O

### Computer-system Architecture

#### Multi-processor system
- 分為 Asymmetric 跟 Symmetric
- Asymmetric mutiprocessung 會有一顆 processer 控制 OS
- 共用 system bus 連接 main memory(除非 NUMA)

#### NUMA
- 需要 OS 的配合
- 為了解決多顆 CPU 會搶奪 system bus 的問題
- 切割 memory 讓每顆 processor 都有一個 local memory
- 如果要 access memory(去使用別顆 processor 的 memory)就要通過別的 CPU，速度會變慢
#### Clustered System
- 用網路串起多顆 processors
- 設計重點在於不能讓其中幾台 processors 壞掉就整組不能用
- 也分為 Asymmetric 跟 Symmetric
- Asymmetric Clustring：有一顆以上在備用(hot-stand)
- Symmetric Clustring：All in 所有的處理器，有一顆壞掉就重新分配工作

#### Multiprogramming & Timesharing
- 在等 I/O 的時候把 CPU 拿去做別的事
- CPU scheduling：選擇哪些 job 要從 main memory 送進 CPU，OS 執行
- job scheduling：選擇哪些 job 要從 on-disk job pool 送進 main memory，OS 執行
- Timesharing：快速切換正在處理的工作（小於一秒）讓 user 覺得 CPU 只在服務他一個人（時間管理大師）

#### 易混淆名詞
- multi-processor system
- 多處理器系統
- multi-core
- 一個 chip 裡面很多 core
- cheaper
- multiprogramming
- 可以同時 run 多支程式
- multitasking
- aka timesharing
- multi-threaded
- process vs program
- process 是正在執行的 program(已經 load 到 memory 中)

#### OS mode
分為 user mode 跟 kernel mode，用來管理權限
當 process 需要 OS 的服務時就會發布 system call 來切換到 kernel mode
不同處理器可能會有不同的切分方式：
1. Intel 8088 CPU 只有一個 mode -> user program 也可以直接呼叫 OS
2. Modern x86 有四個以上的 mode

#### timer
實際上 user processes 是直接跑在 CPU 的，也就是 OS 把 CPU 的控制權交給程式
-> 如何確保拿回控制權？
**設定一個 timeout period**
由 timer 來做（timer interrupt）

#### process management
Process 分為 single-threaded 跟 muti-threaded 兩種，每個 threaded 會有一個 program counter

**threaded**:執行緒，process 是裝載 threaded 的容器

## Ch2
先介紹 OS services 跟五種 OS structure。
其中 OS services 有以下幾種：
- User Interface
- Program execution
- I/O operations
- File-system manipulation
- Communication
- Error detection
- Resource allocation
- Logging/Accounting
- Protection & Security

## Ch3
### Process state
Process 在其生命週期中，共有 5 個狀態

- New：當 process 被創建時，將 code 讀到記憶體中，並將前述記憶體狀態初始化
- Ready： Process 競爭的資源是 CPU 的核心，管理的方式為佇列 (Queue)，在等待被執行的階段，會被放在佇列當中，此狀態稱為 Ready
- Running：被 CPU 排程選到，執行 instructions。OS 為了確保主控權，一段時間就會將 CPU switch 給 scheduler 而 ==打斷(interrupt)== 程序 (會回到 ready)
- Waiting：有些指令不會直接使用 CPU (如 I/O)，因為不需要 CPU ，又需等待某些指令完成，所以進入 Waiting 狀態，待完成後重新放回 Ready
- Terminated：Process 完成執行，釋放資源給 OS (exit)。
一個 Processor 一次只執行一個 Process ; 但同時可能有多個 Process 處於 Ready 或 Waiting 的狀態。

### PCB(process control block)
also call TCB(task control block)
OS 自動創建的資料結構，用來管理 process，每個 process 都有
- process state
- CPU register
- program counter
- 也可能全部 push 到 stack，PCB 儲存 stack pointer
- CPU scheduling information
- memory management information
- I/O status/information
- 打開的檔案之類的
- accounting information
- PID
- CPU time
- time limits

## Ch4 Threads & Concurrency
thread，執行緒，使用 CPU 的最小單位，一個 process 裡面如果有 2 個以上的 threads 就稱為 multithreaded process（我是不是在講廢話）
同 Process 中，Threads 共用以下內容
- code section
- data section (global variable, heap)
- OS resources (e.g. open files and signals)

每個 thread 會有各自的 stack 跟 PC(program counter) 通常存在 register 裡
### data type
- local variable
- 只在某個 function 裡面宣告跟使用的變數。
- global variable
- 在所有 thread 跟 function 之間都共享的變數。
- Thread-specific data
- 某個 thread 自己的 data，不跟其他 thread 共享，在 thread 內部的 function 之間共享。

## Ch5 CPU scheduling

需要 Scheduling 的前提是 muti-programming(CH1. 要同時 run 多支程式，所以在等 I/O 的時候會讓 CPU 去做其他事情)

- CPU bursts：使用 CPU 的期間
- I/O bursts：等 I/O 的期間

執行一支程式的過程中會是這兩種交替，但是中間不一定是連續的(不是每次從 I/O 回來都可以馬上被選中進入 CPU bursts)

Process 可以分成 I/O bound & CPU bound：
- I/O bound：以使用 I/O 為主，使用 CPU 的時間極短
- CPU bound：使用 CPU 為主

兩者的差異就像是到全聯櫃檯 (CPU) 結帳，有人只買一個小東西 (I/O bound)；有人買一車 (CPU bound)。

CPU Scheduler 的任務就是從 memory 選一 process 來 run，介入時機有以下四種：(參照 CH3 process state)
1. process state 從 running 換成 waiting (換去跑 I/O 或等 child)
2. process state 從 running 換成 ready (超時了！)
3. process state 從 waiting 換成 running (I/O 跑完了)
4. Terminate

2, 4 會被強制切換
- Non-preemptive Scheduling
- 非強制，要在 run 的 process 主動放棄
- 不需要 hardware 特別 support 什麼
- MAC OS X 之前的
- Preemptive Scheduling
- 大多數使用的
- 對於 time-sharing 跟 real-time 系統來說比較好(參見 Ch1 名詞解釋)

會用來衡量的指標：
- CPU 使用率
- Throughput
- 完成的 processes 數量

(以上兩個越多越好，以下越少越好)
- Turnaround time
- 從 submission 到 termination 經歷的時間
- 完成 - arrival time
- Waiting time
- 在 ready queue 等了多久
- 開始做 - arrival time
- Response time
- 從被 summit 到生出第一個 response (不是 output) 所需的時間

#### Scheduling 的方法
先預告有以下幾種：
- FCFS(first-come, first-served)
- SJF(shortest-job-first)
- RR(round robin)
- Priority scheduling
- Multilevel Queue
- (衍生出來的)Multilevel Feedback Queue
- 剩下的是期末考的範圍
===

1. FCFS
- 就是 FIFO 啦
- non-preemptive
- 但會遇到 convey effect 的問題，也就是拿一盒優格要結帳結果前一個人一大車(I/O bound 排在 CPU bound 後面)

2. SJF
- 從現有的裡面選需要 CPU 時間最短的來做
- 可以是 preemtive 也可以是 non-preemtive
- 取決於新來的 process 比正在 run 剩下的時間還少時有沒有要強制切換
- 有的話也叫作 SRTF(shortest remain time first)
- 要猜下一個來的人是一盒優格還是一大車
- 有個公式用 a (應該要是阿爾法啦但我懶得打字)決定對於真實數據的依賴程度，通常預設 a = 0.5

5. RR(round robin)
- 設定一個使用時間上限(time quantum, q)，超時就換人
- 通常設定在 10 ~ 100 milliseconds
- 一定是 preemptive
- 講求公平！
- 跟 SFJ 比的話 turnaround time 會輸，但 response time 比較好
- 但是換人是有成本的！(context switch) q 值的設定會影響效能，太大就跟 FCFS 沒啥區別；太小又會浪費很多時間在換人
6. Priority scheduling
- 設定 process 之間的優先權（有超級多種設計方法）
- 可以是 preemtive 也可以是 non-preemtive
- 但有可能會有人永遠等不到 XD -> Starvation
- 解決方法是 Aging，就是隨等待時間增加逐漸提高 priority
7. Multilevel Queue
- 把 ready queue 拆成 n 個 queue，queue 之間有 priority 的區別
- 每個 queue 內部可以使用不同的演算法
- 有不同的使用方法
- Fixed priority scheduling：有 starvation 問題，若最上層的 queue 先做，下層的 process 可能一直做不到
- Time slice：每個 queue 分配一定的 CPU time
8. Multilevel Feedback Queue
- 根據使用的 CPU time 會升降級 (使用太多就放到 priority 低的 queue)
- 目前最常用的演算法

---

## Ch 13 File-System Interface
**File System** (FS) 包含 directories & files ， 他們存放在 disk 中。
### File Concept
- Open Files
- 需要 maintain 的 information
1. File pointer
- 指向前一次 read/write 到的地方 (每個 process 可以有自己的)
3. File-open count
- 用來紀錄 file 目前被多少 process open
- 當最後一個 process close 該 file 時，File information 就可以被 open-file table 刪掉
5. Disk location
- file 在 disk 中的位置 (多個 process 可以共用這個資訊)
7. Acess rights
- 每個 process 的 access mode
- **Two-Level Open-File Table**
1. Per-process table (for proc.)
- 紀錄該 process 開啟的 file information
- Current file pointer, access rights, accounting information
- **File handles** 用來幫 table 編號 (index)
3. System-wide table (for FS)
- 存放 **process-independent** 的資訊 (所以才可以多個 process 共用)

- **Open File Locking**
- 避免發生 race condition
- lock 類型
1. Exclusive (write) lock
2. Shared (read) locks
- lock 機制類型
1. Mandorty(強制)
access 可能被 FS 拒絕 (因該 process 沒有取得 lock)
2. Advisor(建議)
即使 process 沒取得 lock 還是可以 access file

### Access Methods
- Sequential Access
會照著順序去 acess file
- Direct Access
file 會被切成多個固定長度的 block ， user 可以直接要求 acess 第 n 個 block

(註: cp = current position)
- direct access + index
由一個 index table 和 Relative Files 組成， 每個 index table entry 包含一個 pointer 指向 Relative Files
優點 (因為只有index table需要存在 memory 中):
- 適合大型檔案
- 可減少很多 IO
### Directory Structure
- 定義: 一堆 dentry ( Directory entry) ， 每個 dentry 包含 file 的資訊
- 設計目標:
- Efficiency: 方便快速找到檔案
- Naming: 讓使用者方便
>多個 file 可使用一個 name
>一個 file 可使用多個 name
- Grouping: 可以依據文件特性分類
- **類型**
1. Single-level directory
所有使用者用同一個 directory
缺點:
- 一個 file 只能有一個 name
- 無法 grouping files
3. Two-level directory
每個使用者有自己的 directory
- 優點:
- 不同使用者可以使用相同的 file name
- 可以把共用的 system files 放在特定的 directory (e.g. /user0 )
- Efficient searching
- 缺點:
- 使用者無法 grouping files
4. Tree-structured directory
- 優點:
- Efficient search
- 可以 grouping
- 特性:
- 有絕對/相對路徑
- 可以在 current directory creating file, deleting file, creating directory
- **不同的路徑不能共享 file 或 directory**
5. Acyclic-graph directory
- 特性:
- 可以有共享的 file 或 subdirectory
- **Link** 是一個 directory entry type，link file 的內容就是其他 file 的 path name。 (ex. desktop 上的捷徑 icon)
- 缺點:
- 統計 file 數量時可能會把 shared file 多算幾次
- 檔案備份時可能重複備份到 shared file
- Deletion:
- 只刪掉 file 占用的 space，會造成 **dangling link**
- 在刪掉file 占用的 space 前先確保所有 references 都刪了，就需要 maintain references count
6. General graph directory
link 可以指向 directory >> 可能出現 cycle >> 造成缺點
- 缺點:
- 系統要可以處理 infinite loop
- self-referencing directory 的 reference count 永遠不會為0
>Solution: garbage collection (標記有被使用的data；刪掉沒被使用的) >> 耗時 (需要遍歷記憶體)
### File-System Mounting
在 access 一個 FS 前， 需要將他 mount 到 mount point (一個directory) 上。
### File Sharing
#### Multiple Users
file attributes 中會存 "**誰**有哪些**權限**"
>**誰**: User ID & Group ID
>**權限**: Read, Wright, Execute
#### Remote File Systems
不同的機器可以利用 client-server model，從 server 端 mount FS 到 client 端。
>UNIX 利用 NFS(Network File System) 協定
>Windows 利用 CIFS 協定
#### Failure Modes
當發生 network failure 或 server failure ，就會在 Remote File Systems 中加入新的 Failure Modes。
>client 可以直接終止執行或延後執行
#### Consistency Semantics
定義多個使用者要如何 access shared file
- UNIX Semantics
>其他使用者可以即時的看到被修改的檔案
- Session Semantics
>其他使用者須在檔案 closed 後才能看到修改結果
- Immutable-Shared-Files Semantics
>只要是共享的檔案就不能被修改
### Protection
利用 **ACL**(Access Control List) 記錄使用者對 file 或 directory 的權限
> Access mode: read, write, execute
> user type: owner, group, public

## Ch 14 Implementing File System
### File-System Structure
資料在記憶體跟硬碟之間做 I/O 傳輸的單位為 **block**
#### Layered File System

Application Programs    #傳 file name 給 Logical FS
    V
    V
Logical File System    #管理 metadata，利用 directory structure 找到 FOM 需要的 file information 
    V
    V
File-Organization Module (FOM)    #將 logical block address 轉換成 physical block address
    V
    V
Basic File System     #發出 I/O command 給 device driver
    V
    V
I/O Control    #把 I/O command 轉換成 HW-specific commands
    V
    V
Devices

Layered File System 優點: 減少重複的程式碼
>因為不同的 FS 可以共用 I/O Control 和 Basic File System 的部分
### File-System Implementation
#### On Disk Data Structure
1. Boot Control Block: 開機用的 code
- 通常會放在 partition 的第一個 block
- UFS (Unix File System): boot block
- NTFS: partition boot sector
3. Volume Control Block: 記錄這個 disk partiton 中的細節
- No. of blocks, size of the blocks, free-block count, free block pointers, free FCB count, FCB pointers
- UFS : superblock
- NTFS: master file table
5. Directory Structure:
- UFS : 包含 file name 跟 FCB num.
- NTFS: 在 master file table 裡
7. FCB(File Control Block): 每個 file 都有一個，用來記錄檔案細節
- 包含 file permissions, ownership, size, location of the data blocks…..
- UFS : inode
- NTFS: 在 master file table 裡
#### In-Memory Data Structure
會 caching 一些資訊：
- mount table
- System-wide & per-process open-file table
- FCBs 的資訊會貼來這裡
- 在 kernel memory 裡面
- Directory-structure cache
- Buffer cache

##### Open File 的步驟
1. **查找檔案**：
- 操作系統首先會在目錄結構(in kernel memory)中查找給定的檔案名稱。
2. **緩存目錄結構**：
- 查找過程中，系統可能會將部分目錄結構緩存在內存中，以提高未來的訪問速度。
3. **創建進程專屬的開檔表條目**：
- 當找到檔案後，OS 會在每個 process 的開檔表中創建一個條目，記錄該進程當前打開的檔案。
4. **讀取文件控制塊（FCB）**：
- OS 會讀取該檔案的 FCB，並將其內容複製到 system-wide open-file table 跟 per-process open-file table 中（如果該檔案尚未存在於此表中）。

5. **返回文件描述符**：
- 最後，操作系統會 return 一個 file descriptor，這是一個整數，用於識別該檔案在進程的開檔表中的位置。

##### Read File 的步驟
1. **使用文件描述符**：
- 當進程需要讀取檔案時，它會使用之前獲得的 file descriptor 來訪問相應的 open-file table。

2. **獲取FCB資訊**：
- 系統通過文件描述符獲取與該檔案相關的 FCB 資訊，包括檔案大小和數據位置等。

3. **從磁碟讀取數據塊**：
- 根據 FCB 中的信息，系統發出 I/O 命令，從 disk 讀取相應的數據塊到 main memory 中。

### Directory Implementation
連接 file name 跟 FCB(inode)(的 pointer)
- linear list
- hash table
- 可能發生 hash collisions：同一個 file name hash 到同一個位置
- hash table entry 連接到 linear list

### Allocation Methods
如何把 disk 的空間分配給 file
- contigunous allocation：同一個檔案連續放在一起。有 first fit 跟 best fit
- 存 start 跟 lenth
- high performance（好尋找）
- 對大型檔案來說好儲存
- 空間可能浪費（external fragmentation）
- 不好擴張檔案
- linked allocation：同一個檔案分散，彼此之間 linked list 起來
- 每個 block 指向下一塊
- FCB 存第一個跟最後一個的 pointer（方便往下接 aka 擴充）
- 沒有 external fragmentation 且好擴充
- 要隨機存取特定一塊的時候要從頭找起很麻煩
- 需要額外的空間儲存 pointer
- reliabiliy：其中一塊壞掉就找不到後面的了
- 用 pointer reconstruction 解決
- ECC(error correction code)
- doubly linkedlist
- store filename
- indexed allocation：同一個檔案分散，所有 pointer 集中在一個 index block
- 可以隨機存取特定一塊
- index block 本身需要空間，對小檔案來說可能沒必要而浪費
- 要思考該給 index block 多大的空間，太小會沒辦法處理 large file
### Free-Space Management
keep track of free disk space
- bit vector
- 用一個 bit 表示 block 是否空間
- bit map 也需要空間
- bitmap size = disk size/block size
- linked list
- grouping
- counting
### Efficiency and Performance
### Recovery

## Ch 9~10 Main Memory

每個process都有自己的memory space。
並且有base&limit兩個register儲存每個process的起始記憶體。
- Base & Limit Register 會被 OS 特權控制 (by privileged instructions)
- 且CPU在 access 記憶體的時候 OS 會透過檢查 base/base+limit 來確認正確讀取


### Address Binding

Program 在被執行之前通常是存儲於 disk ， 再被存進 memory 裡面。
所以 Addresses 可以被表示成
- Symbol ( 像是變數/函數，最後都會變成後面兩者 )
- Relocatable address 可重置位址
- Absolute address 絕對地址

知道 Addresses 如何表示之後 ， 我們要來看 **Address Binding 會發生的三個時機**
<font color="#449df9"> 這邊要注意的是，我們在編譯的時候 program 不一定在 memory 裡面 </font>
圖片請配合下面文字服用

- **Compile time**
如果在編譯的時候就知道在 memory 中的確切位置 (memory lacaion)，
那就可以直接生成 Absolute address ，
阿如果 program 的 starting location 改變，那就要重新編譯。
- **Load time**
如果在編譯的時候還不知道 memory location ， 那就會生成 relocatable 的地址，
等到知道 memory location 再轉成 absolute

> e.g. “byte 104 from beginning of this module”
Linker/loader 會再重新 bind 可重置地址到 absolute addresses ，
舉例來說 “byte 104 of this module” = address 01104
- **Execution time**
如果在執行過程中 **process 可以從 A segment 移動到 B segment** ，
那麼 Bind 將會延遲到運行時，**大多數 OS 使用這個方法**

### Logical / Physical address
- **Logical address ( Virtual address )**
給 CPU 看ㄉ，由 program 生成，固定不變
- **Physical address**
樓上的人對應的物理地址，基本上會 == 虛擬地址
**==當 Execution time 的綁定策略時，會與虛擬地址不同==**

### MMU ( Memory-Management Unit )
把虛擬跟物理地址 mapping 在一起的 Hardware
很簡單，就是把虛擬地址+上 relocation register = 物理地址
CPU **只看的到虛擬地址**

### Dynamic
- **Dynamic Loading**
運行的時候只載入主函數，
routine / func 在被 call 的時候才會 loaded ，
沒被叫的就不會出來佔位子 => ==省空間==
Loader 會把還沒放進來過的東西更新進 program’s addr table。

- **Dynamic Linking**
- Static linking
不管三七二十一，只要 Program 有用到的 library 我就載入記憶體
每個人都帶著 Library ， 聽起來就會因為飽讀詩書所以超胖
- **Dynamic linking**
把 Linking 推到要執行的時候才 Link ，圖片支援
且通常用的是系統的 libraries，透過 **Stub** (小段的code) 儲存 library routine 的位置， 方便執行，瘦身大成功!
<font color="#fd4340">要注意的是要實現需要 OS 支援多進程同時訪問相同地址的功能，這樣才能共享。</font>
- **Swapping**
暫時把 lower-priority process 踢進 Backing store (夠大的disk空間) 蹲，
higher-priority process 弄完了才會讓 lower 滾回來。
> **如果 process 正在處理 I/O ，那他是不能被中斷被 Swap 的**
>解決方法 : 讓 process 的 I/O 跟 OS 做溝通， process 變成跟 OS 做 I/O ，這樣你想怎麼swap就怎麼swap

這個東西最大的問題是 swap in / out 的時間很容易太大，通常不太值得把程式搬來搬去
除非把 Swap 的 IO size 縮小才比較好處理。 所以swap的變體像是
>只有很小的程式可以被swap
>swap only a part of a process
### Memery Allocation
Main memory 會被簡單分成兩區
1. OS code / data
2. User process 後面講的應該都是在說這裡面的分配方法

==這邊的連續跟分散指的是單一process在memory中的儲存方法==
- **Contigious Allocation**
- **單一個 process**
跟最一開始差不多，阿 MMU 是 OS 在管的
透過 relocation / limit register 來保證不超出記憶體範圍
- **好多個 process in memory**
從上圖我們可以看到在 main memory 中 process 不一定會連續，那我們怎麼決定塞哪?
**1. First - fit** : 塞在第一個遇到的足夠大的洞，**快**
**2. Best - fit** : 找到所有夠大的洞中最小的那個，塞進去
**3. Worst-fit** : 塞在最大的洞

2 / 3 都要額外找到剩餘的洞的大小 會比較麻煩
速度上 1 > (2/3)
儲存利用的效率上 ， 2 > 3

- **Fragmentaion**
- **External Fragmentation**
解釋：當記憶體空間完全可以容納一個新Process，但因為可用空間不連續，所以無法容納。
解法：
**1. Compaction**
重新整理瑣碎的記憶體空間，整合成一塊大的白紙
->需要複製記憶體
->當 relocation 是動態的，且 address binding 是在執行階段才可以這樣搞
->會有 I/O problem
**2. non-contiguous memory allocation**
- **Internal Fragmentation**
解釋：指分配給Process的空間比實際需要的還大，導致有剩餘空間無法有效利用，
導致內部碎片化。
- **Paging**
既然碎片那就把完整記憶體拆開來放
並且透過 P = page number ; d = page offset 來找到物理位置
如下圖所示
logical A = 5 -> data = f ，
page 是在 1 -> frame = 6，
offset = 1 -> physical A = 6*4 (4 = 每個 frame 大小) + 1 = 25
''
- page table ENTRY ( PTE )
PTE 中有 protection bit with each PTE
like Read-only, read-write, execute-only
還有 valid-invalid bit
valid 表示這個 page 是有在 process 的 logical address space 裡面
invalid 表示 page 是不在 process 的 logical address space 裡面
- use page table length register (PTLR)
Valid / Invalid 其實沒那麼常用 直接透過限制長度比較實在
但PTLR有限制 對於用了最高最低的地址來說沒用

- **Translation look - aside buffers (TLB)**
就是類似快取了
滿了的取代方式可以是隨機或是去掉LRU(Least Recently Used)
然後有些TLB的entries可以被固定住不會被踢掉 像是kernel code
如果我們要計算時間
hit ratio = a ;
Associative Lookup (TLB) = t time units ; 如果 no hit 這邊的時間就要變兩倍
Assume memory cycle time = m time units ;
Effective Access Time (EAT) = a ( m * t ) + ( 1 - a ) ( 2t * m )
### Sharing Data Pages
除了自己的 data 以外 程式碼共用同一組 memory
需要確保程式的 memory 是可以多進程重複進入 以及 Read-Only
### Hierarchical Page Tables
分層的page table 
- **1-level paging**
32 - bit virtual address with 4k byte page size
- 12 bits page offset
- 因為 page size = 4k = 2^12 -> 12 bits
- 20 bits page number / index
- 這樣可以有 2^20 個 pages 嗎
- 有 2^20 個 page index 就又有一樣多的 PTE
- **2-level paging**
32 - bit virtual address with 4k byte page size
- 12 bits page offset
- 因為 page size = 4k = 2^12 -> 12 bits
~~- 20 bits page number / index~~
- 10 + 10 bits page number / index
- 這就變成第一層 10 bits 跟第二層 10 bits
### Hashed Page Tables
### Inverted Page Tables

## CH10
前提：一般來說 program 都要被完整的 load 到 memory 中才可以被執行，但其實可能不需要。Virtual memory 讓 program 可以被部分 load 到 memory 中。
好處：
- Program 不用再受到 physical memory 大小的限制
- 每個 program 所需要使用的 memory 變少 -> 可以同時執行的 program 數量增加、preformance 變好
- 減少 I/O
- 減少 memory load/swap
- program 執行速度變快、startup time 減少
-
### Virtual memory
- 分離 logical memory 跟 physical memory -> logical memory 可以大於 physical memory
- address spaces 可以 share 在不同 processes 之間（ch9 但我還沒讀）
- 上述的好處都有
- 需要兩個技術
- paging
- segmentation

### Paging 的步驟
1. Program 跟 page table 要指定 page
2. 檢查 present bit(in page table)
- P -> access(done)
- NP -> trap to OS(step 3)
3. trap to OS 要求 reference 到指定 page
4. OS 檢查該 page 是否 valid：
- Invalid -> segmentation fault
- valid but not in memory -> page fault(後面的步驟)
6. 看是否有空的 frame(free frame)
- if not, do page replacement
7. page-in the page into a free frame(from disk to memory)
8. update PTE(page table entry) & MMU(Memory Management Unit)
9. restart this instruction

### Page Replacement
當 memory 內的pages已滿，要選擇踢出哪個
- **Optimal**
理論上最理想情況：能夠預測未來最不會用到的，把他踢掉
可用來比較其他 Replacement 的效能
- **FIFO(First in first out)**
- **LRU(Least recently used)**
- Second Chance Clock
- Additional Reference bit
historial reference bits

## Ch 6 Synchronizaion
這章節要處理 shared data 可能同時被多個 processors 使用導致不一致或資料錯誤。方法就是排序（order）讓不同人輪流 access。

race condition：兩支 processes 交錯執行指令。E.g.`a++`這個指令會拆成三個步驟，但三個步驟之間可能被穿插另一個指令。或是 kernel 在做 fork() 時同時 access next_available_pid 這個變數導致有兩個 child 拿到一樣的 pid。
解法：設定 critical section（一段有 access shared data 的 code）-> 當有一個 process 在 critical section 時其他 process 就不能進入自己的 critical section。
所以要設計一個 protocol 達成以下三個效果：
1. mutual exclusion：互斥，不會有人同時進入 critical section
2. progress：選人進入 critical section
3. bounded waiting：不能有人一直沒有被選

### 演算法們
1. Peterson's Solution
適用在兩個 processes 之間，software based
作法：
假設 load & store 兩個都是 atomic 指令（不可切割的指令）
int turn：誰進入 critical section
flag[i]：true = $P_i$ 想進入 critical section
缺點：現在的 processors 跟 compilers 會做 reorder：（在 multithreads 的情況下）指令執行的先後順序會被調換。
-> 這會讓 turn 跟 flag[i] 賦值的順序會錯。

(以下是 Hardware 達成 Synchronizaion)
2. 關掉 interrupts，特別是嵌入式系統（uniprocessor）。但在 multiprocessor 時效率會不好，因為每顆都要關。
3. Memory Barriers
分為 Strongly/Weakly ordered：當其中一個 processor 做了 memory 更新時，其他會/不會馬上看到。
Weakly ordered 的 performance 比較好因此比較常被用。

(以下是 atomic hardware instructions 達成 Synchronizaion)
設定一個 lock(boolean) 搶到可以進 criical section
4. Test and Set instruction
test = 抓取某個 memory 的值並設定為 true，return 舊值。
第一個做 test & set 的人 = 搶到 lock = 把 lock from false to true = test(lock) 如果 return false 就可以進入 critical section
離開 critical section 後再把 lock 設回 true
5. compare & swap instruction
比較 value 跟 expected，如果一樣 -> set new value
如果不一樣 -> do nothing, return 原值
lock 初始化為 0，誰把 lock from 0 to 1 就是可以進 critical section 的人
while(compare and swap(&lock, 0, 1)! = 0)
6. swap instruction
設定 key = true，拿 key 跟 lock 做 swap，如果換回 false = 搶到
結束再把 lock = false

但上面 4~6 的方法沒有保證 bounded waiting
-> 多用一個 wating[i] (=true 表示 $P_i$ 想進入 critical section)
結束的時候看下一個人有沒有要進入 `j = (i+1)%n` 再看 waiting[j]。如果有的話直接給 lock，沒有 `j==i` 就 release（把 lock 跟 waiting[j] 都設為 false）

以下底層會透過 4~6 完成

7. atomic variable
此變數的 update 過程不會被切開
8. mutex lock
支援拿/放 lock 的 API
when available = true = 可以使用 critical section
9. Semaphore
設一個 s(integer)
`wait()`：s 一直減到 0
`signal()`：s++
分為 counting 跟 binary
使用方法：

    initialize s = 1
    wait(s)
        critical section
    signal(s)

以上還沒做到 bounded waiting

如果 S 初始化為 N -> 最多同時 N 個人使用
如果 S 初始化為 0 -> 用於 synchronization between processes
其他人在等 critical section 時會 sleep or block 而非 busy waiting（避免浪費）
-> Semaphore 要連接到一個 waiting queue（把 PCB 串在一起）並有 block 跟 wake up 機制。這有賴於 scheduler
wait() 就是把 process 丟進 waiting queue 並讓它 block(sleep)
signal() 就是移出 waiting queue(wakeyup())