###### tags: `資工系課程` `CSnote` `os` `作業系統概論`
# 作業系統概論

[參考資料：期中重點整理](https://hackmd.io/@zsy/OS-midterm1#OS-%E7%AC%AC%E4%B8%80%E6%AC%A1%E6%9C%9F%E4%B8%AD%E9%87%8D%E9%BB%9E%E6%95%B4%E7%90%86)

## CH1

### 雙模式執行（dual mode operation）

#### Kernel mode：由硬體（CPU）所提供的執行模式，於kernel mode可以對硬體做任何的變更，在kernel mode能額外控制的部分如下：
- 控制暫存器（control registers），例如：控制MMU的相關暫存器
- 所有記憶體

#### User mode：CPU所提供的執行模式之一，只能存取有限的硬體資源
- 普通運算所需的暫存器
- 部分記憶體內容
- 也不能控制I/0

### User space/kernel space
CPU將連續的記憶體分成一個個的管理單位，這個管理單位可以是固定大小，如：4k page。或者是不定大小的segment。
每個管理單位都附加了一些屬性，其中一個重要的屬性指出這個page屬於kernel space或者user space
- Kernel space：只有在CPU執行於kernel mode時存取
- User space：只有在CPU執行於user mode或kernel mode時都能存取

**每個user space都是獨立的，不能互相存取**
**右邊不用動態配置，硬體成本上比較便宜，也比較快，嵌入式系統常用**

### 雙模式間的切換
**以x64為例，從user mode切換到kernel mode，是透過syscall（組語）**
- 指令指標（RIP）應該設定為何（通常設定為system call的進入點）
- syscall至少同時做下列二件事情：設定RIP、將模式切換為kernel mode

**從kernel mode回到user mode使用sysret指令**
- 作業系統會將返回位址（就是接下來要執行的user mode程式碼）放在一個特定的地方（x64放在RCX暫存器）
- sysret至少同時做下列二件事情：返回user mode的程式碼位置、切換為user mode

**getpid()不需要切換行程**

### blocking system call & signal
**當blocking system call遇到signal（例如：ctrl＋c所觸發的SIGINT），作業系統有二種處理方式**
- 不理會該signal，繼續完成system call
- 處理該signal，該system call變成失敗，「通常」作業系統會重新起始該system call（即：該system call重做一次）->linux大多是這樣

### Monolithic kernel
Linux和BSD，在歸類上屬於monolithic kernel，在這種設計模式下，**許多系統功能都設計於kernel mode中**，這個方法的好處之一是執行效率，各個模組間的溝通的成本僅為function call的成本，缺點是：程式碼越多，bug越多，核心的bug代價很高->簡單來說就是很多東西都在kernel mode，這樣溝通效率比較快，不需要一直切換mode

### micro-kernel
Minix、L4屬於micro-kernel，設計哲學上盡可能的將所有作業系統的服務執行於user mode，這讓系統變得較為穩定，但執行於user mode間的系統服務需要透過「行程間的通訊」交換訊息，行程間的通訊將觸發context switch及mode change，效能較為低落

**Context switch**
- 本來在執行process A，改成執行process B
- 對Linux而言，context switch一定發生在kernel mode

**Mode change**
- Process A原本執行於user mode，因為呼叫system call，而轉為執行於kernel mode
- 有時候稱之為：process A執行於kernel mode

### 主記憶體的使用
**Cache memory （也稱之為page cache）**
- 將disk或SSD等儲存裝置上的內容暫存於記憶體中，以提高存取速度
- 檔案系統的metadata！？
- 主 RAM 的快取
- 先搬進可能會用到的

**Buffer memory**
- 與I/O之間的資料交換
- 主要是因為CPU的速度高於周邊速度，格式的轉換等等（如網路卡）
- DMA
- 跟外界聯絡

**Program memory**
- 將記憶體分配給程式使用，例如：程式可以透過malloc（背後的system call常常是brk）、mmap等函數向OS索取記憶體
- 執行檔也必須載入到主記憶體才能執行

**可以使用指令setfacl及getfacl分別設定及讀取檔案或目錄的權限**

### Memory-mapped I/O
**將周邊的控制「暫存器、記憶體」映射到CPU的「記憶體映射空間（memory space）」**
　使用的指令如下：MOV CX, 0xFFFFFFFF ;將CX暫存器的值放到位址「 0xFFFFFFFF 」

### port-mapped I/O
**使用特別的指令，將資料傳輸到特定的「port」，注意：port和memory space是分開的定址空間**
- X86-32的I/O port的定址空間只有0~65535
- X86-32的記憶體定址空間有0~4G

使用的指令形式如下：
- out 0x255, AX ;將AX暫存器寫到0x255 port
- in AX, 0x100 ;從0x100 port將資料寫到AX暫存器

### DMA（direct memory access）
相較於CPU，DMA （direct memory access）是相對簡單的硬體，專門用來做主記憶體對主記憶體的傳輸或裝置記憶體對主記憶體的傳輸
- DMA可以屬於bus的一部分（如：ISA）
- 或者裝置的一部分（如：PCI）

**Bus（匯流排）：是主機板上用以傳輸CPU與主要周邊設備之間各種資料的傳導線**

### Cache與DMA的資料不一致性
**DMA直接存取記憶體，但是CPU透過cache存取記憶體，這造成資料不一致**

#### 解決之道
- **（DEV => CPU）使用硬體解決，硬體自動會將DMA的傳輸更新到cache內(利用cache coherence演算法)**
某些處理器，例如早期的ARM處理器，這部分需要特別的指令設定該段記憶體的「屬性」
例如：將該段記憶從cache上完整的移除，這樣就可以確保CPU讀取資料時從主記憶體讀。
- （CPU => DEV）藉由設定，讓CPU在該記憶體區段進行寫入時，直接寫穿（write through，或noncacheable），直達裝置上的記憶體

### DMA的其他議題
**I/O MMU**
- 類似MMU（後面會介紹）主要可以讓DMA存取實體位置不連續的記憶體
- 避免惡意的裝置或驅動程式

**DDIO（Data Direct I/O）**
- 在某些Intel平台上，DMA的傳輸可以跳過DRAM直接傳輸到cache memory（例如：Xeon，DDIO）
**但還是有限制，不能全寫到cache。只是拿來加速I/0，所以可能會設比例，剩下的由CPU使用**
- 例如ARM上的ACP（Access to Shared Caches）

### 中斷（interrupt）
**中斷是裝置主動通知CPU的機制**
#### Legacy Interrupt
- 傳統的中斷由實體線路構成，每個裝置連接到實體的中斷線（例如：第8號中斷線），中斷線連接到PIC（programmable interrupt controller），PIC再向CPU的INT接腳發出中斷訊號
- 以PC而言，中斷線共15條，PC上所需要的中斷通常不止15個，因此必須數個裝置共用同一條中斷線

#### Message Signaled Interrupts
- 所有的裝置共用「一組」中斷線路，裝置在中斷線路上寫入自己的中斷編號，便會觸發CPU中斷（有點類似SIGNAL）：**是在一條線上傳送數字，在解碼器解碼之後推向CPU，讓CPU對CPU產生中斷**
- 以PCI的MSI-X為例，支援2048個中斷編號

### interrupt service routine（ISR）
PC會設置中斷向量表，「中斷向量表」（interrupt vector table，IVT）類似於「函數指標陣列」，告訴CPU發生第X號中斷時，執行中斷向量表的的第X號函數，這個函數稱之為interrupt service routine（ISR）
**ISR一開始是用組語不是C，但有一部分可以用C寫**

### 中斷（interrupt）的軟體處理
**確保處理中斷以後，還可以繼續原本的工作**
- 發生中斷後，硬體會自動將所有中斷disable，將CPU切換到kernel mode（如果原先不在kernel mode），之後再呼叫ISR：**不然還沒把CPU狀態儲存起來，就有第二個中斷，就會很麻煩，造成巢狀中斷。
不過ISR可以視情況決定是否要enable interrupt，要enable哪些interrupt，如果在ISR中enable interrupt表示允許巢狀中斷**
- ISR中首先儲存CPU的狀態尤其是PC暫存器必須立即存下來（這部份需要硬體實現）
- ISR必須儲存足夠多的CPU狀態，讓ISR執行完畢後「將來」可以繼續中斷前的CPU工作（scheduler會決定接下來要執行誰）


**在ISR中不能呼叫任何會造成「wait」的函數，例如：semaphore中的wait()**
原因：
- 從邏輯上來看，ISR是處理I/O事件中的「必要部分」，因此不應該wait()
- 如果程式邏輯需要wait()，必須思考是否將這部分留到bottom half解決

### Linux bottom half

top half處理事情時，可能很久不會給使用者回應，導致使用者認為當機，因此需要變成可排程的，有重要的東西進入bottom half給予使用者適當的response

假設中斷的量不多，可以將所有工作在ISR處理完，驅動程式可以直接呼叫softirq。
如果系統負載比較重，會觸發迴圈把每個中斷進來的工作串成list
，就頂多執行幾個工作，剩下的丟到排程器，讓kernel thread處理。

#### 補充：
- softirq速度最快，work-queue比較好寫
- softirq、tasklet可能執行於interrupt context，也可能執行於kernel thread context，因此不能呼叫會造成sleep的函數
- 同一個工作（例如：disk driver），可以在不同處理器上執行，tasklet確保不會同時執行。因此tasklet平行度較低，但程式碼較好寫
- workqueue完全執行於kernel thread，因此可以sleep
- tasklet 和 workqueue 之中，tasklet 是首選，此機制下處理相當快但不便的是所有動作都必須一氣呵成 (atomic 連動的)。
- workqueue 容許較長的延遲或執行可能引發休眠的操作相較 tasklet 來的彈性
- Softirq 是面相性能的，相同的 softirq 可以同時在不同的 CPU 上平行進行，因此程式必須要可以reentry（可重入的，在任意時刻被中斷然後作業系統調度執行另外一段代碼，這段代碼又調用了該子程序不會出錯），對於撰寫程式就增加了一定的難度。
- softirq另一缺點是在編譯時期就決定好對應的處理，無法動態的註冊和刪除
- tasklet 的設計可以解決無法動態的註冊和刪除

#### 疑問：是由什麼去判斷要用哪種kernel thread？　
是看三個kernel thread的特性，像是softirq用來放高速裝置，通常是網路相關的，因為平行度較高。
教授答：最好寫ㄉ就可以

#### 參考資料：
[Linux 核心設計: Interrupt](https://hackmd.io/@RinHizakura/B14d-o24v)
[Linux Kernel about Bottom Half (Softirq, Tasklet, Work Queue)](https://dwei1224.wordpress.com/2018/01/26/linux-kernel-about-bottom-half-softirq-tasklet-work-queue/)

### polling
- 與interrupt不同，polling是OS主動去探詢裝置的狀態
- OS每隔一段時間就會去探詢裝置的狀態（這部分需要timer的協助）
- 如果數個裝置共用同一條interrupt，那麼當interrupt發生時，OS必須探詢掛載在該中斷線路上的所有裝置（即：interrupt + polling）
- 某些裝置同時支援interrupt和polling機制，例如網路卡，網路卡在低負載下採用interrupt機制，高負載下採用polling機制

### buffing
- Kernel分配一塊實體位址上連續的記憶體krl_buf，並且這塊記憶體必須是disk controller可以存取的位置
- 呼叫驅動程式，命令disk controller將使用者想要的資料填入krl_buf（使用DMA將資料傳到kernel buffer）
- kernel再將krl_buf內的資料複製到user space的buf

**無法直接將disk資料傳送到目標位置，因為跟底層溝通時會有記憶體位置限制，比如說資料本身要跟address做對齊，開始位置會有限制。以及kernel buffer的資料到buffer時，核心可以另外做一些事。像是原先要讀4k的檔案，但os考慮到檔案是mp4，可以自己多讀資料**

**的確有DMA可以直接從disk複製到user space，減輕kernel負擔。此技巧稱為kernel bypass（核心旁路）**

### 行程及執行緒的管理
- fork()、vfork()產生行程
- clone()產生thread（更正確來講是：task，包含了process和thread）
- execve()將一個執行檔內的程式碼載入到該行程中

**對Linux kernel而言，process和thread都是task**
- Linux kernel使用task_struct描述process、thread
- 對Linux而言process和thread的差別只是「共享的資源的多寡」，尤其是記憶體是否共用

- **fork、vfork、clone都是呼叫核心的do_fork**

**有一些thread只執行於kernel mode，Linux稱之為kernel thread**

### SMP、CMP
- SMP，全稱是symmetric multiprocessor。所有運算用的處理器是等價的，換句話說應用程式可以在這些處理器上進行移轉（migration）
- CMP，chip multiprocessor，常常稱之為multi-core，與傳統的SMP架構不同的地方在於：通常最下層的快取記憶體（LLC，last level cache）是共享的。因此CMP上不同核心間交換資料較為快速

### SMT（simultaneous multithreading）
SMT，在一個處理器上用硬體模擬出n個處理器，在硬體上主要的成本是logical register的數量增加n倍，由於更有效的利用處理器內的functional unit（如：加法器、乘法器等），可以提高若干效能
**不是增加系統速度，是提升系統（CPU運算資源）的使用率**

### 啟動作業系統

### BIOS的局限性
- BIOS必須要能夠認得硬碟上的開機磁區，如果BIOS不支援該硬碟（例如：容量超過BIOS的定址範圍），BIOS無法啟動作業系統
- BIOS內含多種「驅動程式」，最近的BIOS支援USB等裝置，但大部分的BIOS不支援藍芽功能，因此藍芽的滑鼠、鍵盤可能無法用來與BIOS互動

---

### 9/16
#### 為什麼控制權會回到OS
- 因為硬體發生ＸＸＸ（中斷、錯誤指令、錯誤指標、system call（syscall,asm）），立即切換成核心模式，同時執行位於0xＹＹＹＹ的程式碼
- OS在開機的時候，預先把適當的程式碼，放在0xYYYY
#### interrupt或exception等等中斷進來時，會自動把控制權交給OS並執行某個位址的程式碼，每次開機都會重新決定一個位址嗎？
- 每次開機就決定好，但那個位址可能一樣、可能不一樣，要看CPU能不能控制。像是Linux軟體支援KASLR，可以讓每次載入程式碼的位址都會不一樣

### 9/23
polling、interrupt：[OS - Ch2 中斷、I/O、系統呼叫、OS 結構設計 和 虛擬機](https://mropengate.blogspot.com/2015/01/operating-system-ch2-os-structures.html)

epoll：[Linux IO 複用之 epoll 介紹與 epoll 應用(編寫單執行緒多併發的 Web 伺服器)](https://iter01.com/577425.html)

### 9/24
步驟：各個程式碼分別代表66 67 68...會先push再jump，
在ISR裡面用類似cmd-ISR的指令命令CPU執行過去，
然後會全部進到一個叫common_ISR用組語的保存（一種儲存狀態）
再來是do_IRQ，是使用C語言，依push的不同呼叫對應的c函數

## CH2

### system call

**gettid() – libc未實現的一個system call （於Ubuntu 20.04已實現於libC）**

### System call的特例
System call主要的overhead（類似花費、開銷）來自於
1. 將CPU從user mode切換到kernel mode，CPU同時數個指令在執行，進行切換時或許需要flush所有執行到一半的指令
2. Kernel將user space的所有暫存器存在kernel stack中（每一個task，於kernel中有自己的stack，請注意，不是user mode stack）
3. 檢查權限
4. 依照kernel內部的calling convention（呼叫慣例），呼叫實現該system call的function，例如：sys_read() => do_read()

補充：calling convention(呼叫慣例)規範了：
1. 參數傳遞方式。看是由右至左或左至右，或者透過 register
2. 堆疊維護。看是由函式本身或由呼叫者來維護堆疊 (在呼叫返回時回復堆疊)
3. 名稱修飾 (name mangling)

### System call的特例 - vDSO
如果該system call並未牽扯到「安全性」，可以將kernel中部分資訊直接寫到user space中，讓APP以function call的方式取得該資訊

**例如：會時常變動，但又沒有機密性的資訊**
- __vdso_clock_gettime
- __vdso_getcpu
- __vdso_gettimeofday
- __vdso_time

**不會變動，又沒有機密性的資訊**
- 第一次呼叫時，真的產生system call，libc記錄下該function的值
- 第二次呼叫，由libc直接回傳
- 如：getpid

**關於vdso的一些小問題**
資料存放在vvar不一定就是使用者要的資料「格式」，例如：
- vvar內放的是從開機到現在「經過多少個machine cycles」，而gettimeofday的傳回值是「自1970/1/1至今經過多少秒」
- 因此vdso內部的程式碼會做適當的資料格式轉換

## CH3

### Process memory與系統安全
如果程式執行時，每次記憶體的layout(記憶體address)都一樣，會很容易遭受駭客攻擊

#### 解決之道 ASLR(Address space layout randomization)
- 作業系統會隨機的產生每個section的address
- 幾乎所有的作業系統都支援ASLR，例如：Linux、BSD、Windows、MAC OS
- 優點：可以避免惡意程式入侵
- 缺點：效能上的損失。如果不使用ASLR，那麼可以將常用的函數固定在同一個地方，因此在做行程切換的時候不需要切換常用函數庫的部分
- 缺點的解決之道：目前大部分的硬體都使用phy. cache可以降低這部分的影響

### Process state
process會到ready queue去等待排程器選中他running
process跑完後會到terminate去等待parent檢查是否執行完，在這時這些process稱為zombie，若parent一直沒有wait清除這些zombie，則可能發生os資源不足

### Process Control Block (PCB)
**Process control block內包含下列內容**
- Process的狀態（例如：runnable、waiting）
- 相關的CPU資訊（如果行程不在CPU執行，OS會將該process的狀態儲存於此）
- 排程的相關資訊（例如：使用者設定的nice為多少）
- 記憶體相關資訊（例如：程式碼區段、資料區段等等）
資
- 使用了多少資源（例如：行程死掉以後，parent可以使用wait()取得相關資訊）
- 正在等待的I/O
- 這個行程開啟的檔案
> Definition:
> Process control block
> ≈ Task control block

### task分類成IO及CPU


如果將I/0優先權提高，則系統使用率會非常高，因為I/0在中間只要使用CPU計算一下下就可以繼續執行接下來的I/0

但如果將CPU優先權提高，I/0要用到CPU時需要等很久

### 建立行程，fork與clone
pid=0
- idle process
- 優先權最低
- 目的：讓CPU sleep
- 省電

pid=1
- 開機第一個 user space process
- 目的：負責作業系統初始化
- daemon

**fork 和 vfork 差不多快，但 vfork 會先暫停父進程的資料結構給子進程用，所以大量fork時vfork較快**

### 同時執行多個程式 – scheduler
這張圖是在講前面要安排process從ready queue到CPU執行，是橘色的部分
- long-term scheduler，從job pool中挑選一些合適的program進入到short-term scheduler，沒有互動性（問號？
- Short-term scheduler，通常是挑選出優先權最高的task執行
- Mid-term scheduler，則是當degree of multiprogramming太高時（例如：造成記憶體不足了），將部分task暫停，process會被整個丟進去，存入硬碟，等到資源足夠時，再將task放入short-term scheduler
- 橘紅色的部分是目前大部分OS實作的部分，只有short-term scheduler針對各種事件有其專屬的waiting queue，waiting queue大多是在等I/O，short-term scheduler則是等CPU，所以又稱ready queue

### Context switch

當 CPU 做事做到一半，如果有事件發生了，而且這個事件的處理所用到的 core registers(CPU 內部的 register)會把目前的進度蓋掉的話，CPU 就會先需要把 core registers 目前的值先暫存到 memory 的某個地方，等 CPU 處理完事件之後，再把暫存的值讀回來，就可以從事件發生時中斷的地方在繼續處理。這就是所謂的 'context switch'。

### Interprocess Communication (IPC)
**IPC機制可以讓二個獨立的行程互相傳遞訊息，其目的多半是：**
- 傳遞資訊（例如：copy-paste，Information sharing ）
- 同步（例如：平行計算，master thread可以收到所有worker thread的訊息以後，繼續往下做、計算加速）
- 模組化設計（例如：master thread收request，發包給worker）：讓每個thread負責不同的工作
- 方便性（？）

### 行程間通訊－直接溝通
通常使用process id直接將訊息丟給對方：
- send(p,message)
- receive(q,message)、receive(&q,message)
- 如上，送的第一個參數通常是對方的process id
- 收的部分可以指定要從哪邊收。或者收任何訊息，並且作業系統告知由誰送

特性：
- 使用者不需要特別的建立連結，任兩個之間os就會動態的自動幫我們建立通道
- 由於使用process id 來命名一個傳輸通道，因此任兩個process之間會有一個傳輸通道，也只會有一個
- 由p和q之間，由兩個單項組合成一個雙向。因此可以雙向溝通

### 行程間通訊－間接溝通
一個傳輸通道必須由使用者特別建立：
- 例如：linux的mkfifo、pipe
- 例如：TCP/IP（如果只在同一台機器上傳輸資料，是不會經過網卡，因此是行程間通訊）

特性：
- 溝通的行程可以建立多個通道，可以簡化設計複雜度
- 可以多個傳輸行程對多個接收行程，常見於伺服器的設計
- 雙向（如：共享記憶體）和單向通道（如：pipe會建立成單向）都很常見

### Blocking & non-blocking
如果有足夠多的buffer的話，行程間的通訊可以是non-blocking
- 送出message的行程，丟出訊息後就可以下一個工作
- 例如：signal

如果buffer不足或者根本沒buffer的話，就只能是blocking機制
- 送出訊息後，必須等待接收者把訊息取走
- 常見，因為發送者下一行程式碼可以確認對方已經接收到訊息

[Blocking & Non Blocking](https://jk3527101.pixnet.net/blog/post/14108608)

## CH4
### OS scheduler的分類

進行 CPU scheduling 的可能時機有下列四種:

1. 當一個 process 的狀態由 running 轉為 waiting 時
2. 當一個 process 的狀態由 running 轉為 ready 時 e.g. time sharing 因為 timeout 回到 ready
3. 當一個 process 的狀態由 waiting 轉為 ready 時
4. 當一個 process 的狀態由 running 轉為 terminate 時

#### preemptive的概念
當 process 進入執行狀態（running state）時，排程器（scheduler）會去檢查進入該 process 優先序（priority），若該 process 的 priority 比目前執行中的 process priority 高，Linux 便會搶先（preemptive）執行該 process，因此原本的 process 便被中斷（interrupt）。

#### Non-preemptive OS
**不可搶奪型，又稱 cooperative scheduling 合作式排程**
一個 Process 除非自行放棄 CPU 的使用權，否則其他 Processes 不能奪取其 CPU 使用權

自動放棄的情況：
- process 等待 I/O, semaphore wait(task發出I/O之後就不會等CPU)
- process terminates(task執行結束)
- Non-preemptive scheduling 只可能發生在上面的1. 4.兩個時機點

#### preemptive OS
**可搶奪型**
- 不論正在執行的 process 是否可繼續執行，必要時 CPU 使用權可能被搶奪
- Preemptive scheduling 在上述的四個時間點皆會發生
- 適用於 real-time system, time sharing system
- context switch 次數較多，overhead 較大
- 產生新的task之後優先權很高，也會發生
- 如果一個task執行過久，OS會『主動地』將CPU控制權交給下一個task
- 如果要設計preemptive OS必須要有硬體支援。必須要有一個『timer』每隔一段時間，利用『interrupt』讓OS重新獲得CPU控制權。而後OS決定讓誰接下去跑
- 所有版本的Linux都是preemptive OS

### 從non-preemptive kernel到preemptive kernel
- 在non-preemptive kernel中，所有進入kernel的task可以假設自己不會被插斷，因此存取許多共用資料，不需要使用lock-unlock機制
- 在preemptive kernel，程式設計師需要仔細的思考、改寫程式碼，所有存取到共用變數的程式碼都必須使用lock-unlock保護

### Scheduling Criteria判斷排程器好壞
- CPU utilization：讓CPU維持在高使用率。
- Throughput：每單位時間可以完成的工作的數量。例如：讓I/O bound的行程優先執行。
- Turnaround time：從交付工作，到完成的時間。與scheduler及程式本身的執行長度相關。
- Waiting time：在ready queue的時間。通常高優先權的task在ready queue的時間較短。(如果因為有其他優先權高的先做，但被暫停，只要task能跑，但不讓他跑就算waitint time)
- Response time：回應時間。例如：程式需要輸出「回應」（例如：progress bar、字母）到螢幕，好的scheduler可以讓progress bar非常「即時」的反應

### Response time
- 假設系統中有10個task，這10個行程連接到10個user，如果要讓使用感覺執行流暢的話有下列做法
- 假如這10個行程是「播放影片」，那麼只要安插適當的buffer，將解碼過的影片放在buffer內，供使用者的task拿取，只要buffer夠大，即使每10秒才輪到一次執行，使用者也不會感覺lag，**在這個例子中，使用者和系統是「單向互動」**
- 假如這10個行程是「語音通話」，必須在150ms內輪到執行一次，否則使用者會覺得通話品質不好。換句話說，每個task每一回合只能執行15ms。**在這個例子中，使用者和系統是「雙向互動」**

### FCFS
**依task的抵達順序，按照順序執行**
p2等p1執行完，p3等2跟1

### SJF（shortest job first）
**工作時間最短的task優先執行**
p3等p1，p2等3跟1

#### Preemptive SJF
「Preemptive SJF」又稱之為shortest remaining time first (SRTF)
**只要有task進來或是執行結束就計算**
p3:10之後的箭頭應為RT(2)=20,RT(1)=80、P2:20之後的箭頭應為RT(1)=80

### Round robin
**在一群task中輪流執行，每一個task執行最多X個時間單位**

排程器可以把task從running變成runnable，是走紅心那條，而且還可以執行、還需要cpu time，因為要增加cpu的response


### 2.4 scheduler
在2.4核心中，是smp，當有CPU變成IDLE時，會到run queue中做搜尋及計算task多適合這cpu，
**Non-preemptible kernel**

**Round-robin**
- task_struct->counter（裡面有個counter值會不斷減1）: number of clock ticks left to run in this scheduling slice, decremented by a timer.（剩餘執行時間，每個time slice會將counter值-1，當變成0時，在這回合就不能使用cpu）

**所有人共用一個run queue**
1. Use spin_lock_irq() to lock ‘runqueue_lock’
2. Check if a task is ‘runnable’
- in TASK_RUNNING state
- in TASK_INTERRUPTIBLE state and a signal is pending
3. Examine the ‘goodness’ of each process(goodness好寶寶指數)
4. Context switch

#### goodness 好寶寶指數

**to improve multithreading performance**
- 如果task p 與之前的task共享地址空間，則它會獲得少量獎勵。
- 舉例：excel有五個thread，上次執行的是第一個thread，接下來run queue中有一個是excel的第二個thread，就會加一分。

**to improve multi-core performance**
- 上次在這顆核心上執行，這次也在同一顆執行，分數會加15

#### 問題
- scheduler要針對所有的task計算goodness，每次都要重算，非常浪費時間
- 一個重要的觀察：其實大多時候，每次算出來的goodness都是差不多的，需要每次重算嗎？

### epoch
**將執行時間分成無數個「epoch」**

**當沒有task可以執行時就換到下一個epoch**
- 此時可能有些task的time slice還沒用完，但些task正在「等待」
- 2.4假設「等待」就是在「等待I/O」

**換到下一個epoch的時候，「補充」所有的task的time slice**
- 如果是I/O-bound task因為上一個epoch還有一些time slice還未用完，因此補充過後，這些task的time slice比較多

**在Linux 2.4中，time slice即為dynamic priority**
- 因此I/O-bound task拿到比較高的優先權

下面waiting的部分，2/2+6=7 以及3/2+6(沒有浮點數運算)=7，time slice越大，優先權越高

---

### 2.6 scheduler
### Load balance
二個手段
- Put：當一個CPU覺得自己的loading太重，將task塞給另外一顆CPU
- Pull：覺得自己的loading太輕，從別人那邊拿一個task過來執行

**如何評估各個CPU的loading**
：看各個CPU上的runnable task數量

### Scalability
- 由於每一個CPU擁有自己的queue，因此當CPU增加時（通常這種系統task也很多），每一個CPU只要從自已的queue挑選適當的task起來執行
- 在這種情況下，於大型系統（例如：許多處理器），Linux的scheduler表現依然不錯

### Affinity（task與CPU之間的親和力）
- 由於每一個CPU有自己的ready queue，除非負載不平衡，否則不會觸發task migration
- 換言之，一個task一但被指定到某顆CPU上執行，除非特殊狀況，否則該task不會輕易的離開該CPU
- 在這樣的架構下，可以更有效的使用CPU cache，讓CPU的IPC（每machine cycle所完成的指令數）更高

### Fully preemptable kernel
**2.6 kernel以後，Linux中每一個task執行於kernel mode時，都有一個變數「preempt_count」用以記載該task是否可以被preempt**

- 每當lock一個資源時， preempt_count++
- 每當unlock一個資源時， preempt_count—
- 當preempt_count為0時，kernel可以做行程切換。Kernel需要做行程切換主要是因為interrupt。例如：一個高優先權的task正在等這個interrupt。

**如果核心程式碼直接執行schedule()，無論preempt_count是否為0，都會發生context switch**

**請注意，如果preempt_count由1變0，那麼OS kernel需要檢查一下，是否需要context switch**

### The Priority Arrays
每個CPU有自己的run queue，每個run queue由二個array組合而成，分別是：
- active array：存放time quantum還沒用完的task
- expired array：存放time quantum用完的task

**執行方式**
在linux Kernel 2.6 時，每個處理器都有兩個Task Queue，當位於Active Task Queue的行程執行完畢，就會依據行程的優先級，計算Priority與Time Slice，然後放到Expired Task Queue中，當Active Task Queue執行完畢後，就會Switch這兩個Task Queue，就是交換expired 跟active的指標，讓經過計算後的新Active Task Queue可以立刻加入排程。

**時間複雜度為O(1)**
- 用完time quantum的task會由active array移到expired array，並在此時「計算下一回合的動態優先權」。換言之，不用像Linux 2.4一樣，對同一個task一而再的運算優先順序
- 選出最高優先權的task（即：優先權最接近0的task。易言之，是演算法中的「求min」），之所以是O(1)是由於優先權只有140個，因此可以用特別方法予以優化

### O(1)的缺點
- 與2.4一樣使用epoch的概念區分I/O-bound和CPU-bound
- 因此每一個task使用完CPU time以後，要經過一個epoch的時間才能補充time slice
- 對於某些應用而言（例如：遊戲、多媒體），需要更頻繁的補充time slice，但在2.4無論優先權多高，補充time slice的時間跟其它task一致的

### complete fair scheduling（ＣＦＳ）
「授課老師認為」CFS最特別的地方是在「回填time quantum」的部分，
相較於前面二個演算法，高優先權的task在CFS中，回填的速度更快
換句話說，高優先權的task可以得到：
1. 更多的CPU time
2. 更好的response time

#### 設計理念：
- 希望將一顆「實體處理器」依照目前正在執行的task的數量（例如：n）虛擬成n顆「虛擬處理器」
- 假如這些task的優先權都一樣高的話，那麼每一個虛擬處理器的效能為實體處理器的1/n
- 假如有一個task的優先權為nice的話，其它task的優先權未調動，那麼虛擬處理器的效能比為：1.25^nice：1： 1： 1： 1...（1的意思是1.25^0）

#### 運作

依照等待時間排序，等待時間越久的排越前面
換句話說「虛擬執行時間」（vruntime）越短的，排得越前面

#### 虛擬執行時間」（vruntime）
「虛擬執行時間」（vruntime）是一個排程上的值，如果行程切換夠快速的話，所有task的vruntime應該要一樣。

實際上，CPU的context-switch速度有其極限（例如：切換速度太快，會造成CPU效能太過低弱），因此我們設定一個「反應時間（response time）期望值」
令每次的執行時間為λ，那麼λ = 「希望達到的反應時間」÷「# of task」

### 如果使用一顆超強處理器 要如何模擬三顆弱處理器？CPU的部分
因為藍色部分要佔CPU的1/2，所以第一個上面要寫2，代表vruntime要增加2

### I/0的部分
從I/O回來的task，相當於系統裡最低的那個值，在圖中是1
若又有一個從I/O ready queue回來，vruntime就設為min_vruntime-Δ

Δ為大於0的一個數字， Δ越大，可以讓「比較I/O」的task會得越高的優先權

## CH5
### Race condition problem
當兩個process或是thread試圖同時訪問同一資源並導致系統出現問題時，就會發生這種情況。
以之前寫的pi程式為例，程式碼的正確性，在於「操作sum_up以及sum_down的程式碼是否同時執行」。

#### 其中一個解法
- 引入critical section的觀念， critical section就是操作共通資料結構的程式碼
- 將「保護共通資料結構」問題，轉換為critical section問題。
#### 正確的解決「 critical section」須滿足三個條件
**mutual exclusion**
- 如果一個task正在critical section裡面，那麼其他task就不能進去critical section。
- 這是滿足程式碼正確性的基本條件

**progress**
- 如果沒有人在critical section的話，就要讓想進去critical section的人進入到critical section
- 如果沒有加上這個條件的話，那麼「不讓任何人進入critical section」 也算是正確的。 「不讓任何人進入critical section」 不符合我們程式碼的目的，也就是沒進行分工

**bounded waiting**
- 如果有人想要進入critical section，那麼就不能讓這個人等待太多「次」
- 假設Ａ和Ｂ二個task都想要進入critical section，我可以寫一支程式永遠只允許Ａ進入critical section，這個程式滿足「mutual exclusion」、「progress」，但這樣的程式正確嗎？
- 對我們來說，永遠只允許特定程式進入critical section當然是不對的，因此加入一個新的條件「bounded waiting」

**mutual exclusion跟progress一定要滿足，bounded waiting有滿足最好**

### 關於Peterson’s solution
- 這個演算法假設只有P0、P1二個task
- **對於硬體有一些重要的基本：假設「load」和「store」是atomic operations、共享記憶體的系統**

**假設task P0及P1「共享一些變數」**
因為「共享一些變數」因此Peterson‘s solution只能用在共享記憶體的系統。例如UMA或者NUMA的處理器。無法用在分散式系統

bool flag[2] = {false, false}; /*分別代表P0及P1是否想進入CS*/
int turn; /*turn = 1或0，代表這一回合誰的「進入權」比較高*/

#### 舉例
P0

while(1) { /*代表P0週而復始地想進入CS*/
    flag[0] = true;     /*告訴大家，P0想進入CS*/
    turn = 1;           /*如果P1也想進入CS，讓P1先進去*/
    while(flag[1] == true AND turn ==1) /*P1進入權比較高，且P1想進入CS*/
        ;//用while loop實作出wait
 
    /*critical section，可以於此更新共享資料結構*/
 
    flag[0] = false;    /*離開CS，因此將flag[0]設定為false。
                        /*表示P0目前不需要待在CS了*/
}

P1

while(1) { /*代表P0週而復始地想進入CS*/
    flag[1] = true;     /*告訴大家，P1想進入CS*/
    turn = 0;           /*如果P0也想進入CS，讓P0先進去*/
    while(flag[0] == true AND turn ==0) /*P0進入權比較高，且P0想進入CS*/
        ;//用while loop實作出wait
 
    /*critical section，可以於此更新共享資料結構*/
 
    flag[1] = false;    /*離開CS，因此將flag[1]設定為false。
                        /*表示P1目前不需要待在CS了*/
}

#### mutual exclusion的證明
**這裡要證不會有兩個人同時進去**

P0和P1同時執行，這二個task都可能設定turn變數，因此turn可能等於0要不然就是1
- 這是因為store是atomic operation，並且是共享記憶體系統，因此turn只可能等於0或者是1
- 如果store不是atomic operation，那麼有可能P0看到的turn是1，而P1看到的turn是0

由於下列程式碼的作用，當二個人同時想進入critical section時**flag[0]==flag[1]==1，因為turn要不就等於0，要不就等於1**，因此P0或P1只有一個人能進去
    while(flag[1] == true AND turn ==1)
        ;

#### progress的證明
**這裡要證有人可以進去**

假設執行到P0第三行，要考慮P1的三種情況

證明1
P1還沒說想進CS

證明2

P1還沒執行到禮讓的部分

證明3

#### bounded waiting的證明
考慮：如果P0不斷的想進入CS，系統是否會讓P0一直進入CS呢？
**證明方向：第一次是P0進去的話，下次一定是P1進去**


第六行代表P0還想進入CS，但因為有第七行的禮讓，而且P1也在不斷要求要進入CS，因此執行到第七行的時候，就會變成P1進入CS

#### 例外
（p1也採用的同樣形式的程式碼）

程式碼是按照時間排的


此時因為P1在後面才執行turn=0，因此最後turn=0

#### 使用gcc，使用優化（-O3）的正確方法
下圖是p0


要使用atomic去跑flag跟turn

atomic_thread_fence是保證flag跟turn不會對調

建議要明確指定用哪個memory_order，不然就會預設用最強的，會跑很慢

#### 錯誤版錯誤原因
因為cmpl很重要，所以被搬到最上面，造成程式邏輯順序不對，變成像下面

### Mutex（semaphore）與spinlock在使用上的差別

[同步機制比較：Spinlock v.s. Mutex](https://blog.hitripod.com/synchronization-mechanism-comparison-spinlock-mutex/)

[讓CPU瞎忙的忙碌迴圈](https://www.ithome.com.tw/voice/72578)

**在lock不成功時，「幾乎都會」context-switch**
- context-switch需要耗費一些CPU time
- 因此，除非要等很久，否則使用semaphore不見得划得來

**spinlock在lock不成功時，會使用一個loop等待**
- loop會讓CPU不斷的進行測試，測製某個變數是否為「期望的值」
- 如果loop太久，會造成浪費CPU time
- 要等很久➜使用semaphore。等一下子➜使用spinlock

**Spinlock的效能通常較高，因此資料庫系統等大型軟體使用spinlock來增加效能**

**如果使用spinlock，那麼持有lock的task被schedule out，會造成其他task做「無意義的等待」**
- 在semaphore、mutex中，因為「等待的task」都被scheduler換出了，因此不會「無意義的等待」->等不到會放出cpu讓其他task執行

### semaphore的實作
初始值value通常為0，一開始0變成-1之後就把這個task丟進waiting queue，並且block。之後有個人離開CS之後把value+1，發現剛好為0，代表原先為-1，有一個人在waiting queue所以要把他wakeup，就是wakeup上面講的被block的那個。之後被wakeup就會往下執行。

### Semaphore的通常使用方式
Semaphore的value可以是
- 「負的」，通常是多個task在等待，例如「-1、-2」代表有「一、二」個task在等待
- 「零」，沒有task在等待。初始化時，通常為零
- 「正的」，常用於「一種資源」最多可以服務「X」個task。例如：印表機共三台，因此最多3個task同時列印

Semaphore的value通常是「不可直接修改」甚至看不到
- 應該用「wait/signal」或「lock/unlock」

### 關於「mutex」
**mutex「可以有」下列特色**
- 可以判斷是誰鎖住這個mutex（owner觀念）
- 可能支援優先權繼承
- 可以支援或者不支援「巢狀鎖定」，就是f去lock（r） ，然後f呼叫g，g剛好也會lock（r）
- 可以支援「自適應鎖」，會判斷要用spinlock還是mutex

### adaptive mutex

<font color="red">注意：adaptive mutex有多種實現 這裡介紹的方法應該出自於Sun Solaris</font>

前提：p和q競爭mutex，p想要這個mutex（即lock），討論p的情況

**如果mutex未上鎖，p獲得鎖**

**如果上鎖**
- q在另外一顆處理器，且q在OS的waiting queue（例如：正在讀資料），則p進入sleep的狀態等待mutex（即context-switch）
- q在另外一顆處理器，且q不在waiting queue（表示q正在運算），則p採用busy waiting的方式等待mutex
- q和p在同一顆處理器上，則p進入sleep的狀態等待mutex（即context-switch）

#### p等q，但q在waiting queue
q已經用完time quantum，沒有在執行，p就會去判斷q有沒有在執行，如果q沒有在執行則p剩下的cpu都會拿去執行其他的task，因為等待一個目前等待不到的事件很愚蠢。

#### p等q，但q在waiting queue
p發現q正在執行，認為會很快離開CS，所以做busy waiting等待q

#### p等q，但q不在waiting queue
紅圈的部分q沒有在執行（但也可能隱約在執行，如果是在SMT處理器上執行）
如果是ＳＭＴ狀態下執行（一個core上面有兩個vcore，且會在這vcore之間快速切換），q就有機會離開CS，所以p spin也有道理。
p也可以使用一些特別指令像是：asm("pause")不會造成context switch，但會讓p執行速度變慢，讓q的vcore可以搶到比較多cpu資源，早點離開CS

#### adaptive mutex實作
**注意：adaptive mutex有多種實現 這裡介紹的方法是glibc**

大概流程
- 針對過去等待這個lock的時間，設定使用「spinlock」的loop次數
- 如果超過loop次還無法lock成功，那就釋放CPU控制權，即：LLL_MUTEX_LOCK (mutex)

wait_adaptive_mutex.c：p、q各用mutex上鎖100次

執行結果

- 使用adaptive mutex時，如果p執行nanosleep，那麼q就會做context-switch，因此context-switch的數量為400
- 如果p沒有執行nanosleep，那麼q就不會做context-switch，因此context-switch數量為201（比較少）

### futex（fast user-space locking）
**主要功能（底下都是虛擬碼）**
- futex_wait(&expected, desired, timeout)
- futex_wakeup(&val, newVal, maxWakeup)

**優先權繼承（priority inheritance）**
目的：避免Priority Inversion（高優先權的在等低優先權）
- futex_wait_pi(&expected, desired, timeout)
- futex_wakeup_pi(&val, newVal, maxWakeup)
- 如果等的人優先權較高，持有lock的人會「繼承等的人的優先權」
- unlock時，優先權最高的人優先獲得lock（注意：不是FIFO order）

假設ａ跟ｂ兩個task，其中a的優先權是-5 b是0，且b有lock，而a在等b。
此時b優先權會繼承a的變成-5，因為如果b還是0，其他的-4 -3 -2 -1等優先權task，可能會阻礙到b執行。

#### futex示意程式碼

### Producer-consumer問題

#### Bounded-Buffer – Shared-Memory Solution

Insert()

Remove()

### producer, consumer對in, out的存取
![](https://i.imgur.com/K0NEOLx.png)

- 這一個程式在producer（put）、consumer（get）不會有race condition，原因是：共享變數，in及out，不會有二個以上的thread，對其做寫入
- 基於上述理由，這個方法只適用於一個producer、一個consumer。
- 舉例：如果有二個producer，那麼in這個變數就可能會有2個thread（因為有二個producer）對其修改

#### Bounded-Buffer Problem

問號

### readers-writers problem
reader和writer的差別
- reader只可以讀
- writer可以讀、寫

**可以同時多個reader讀同一個資料結構**
reader和writer不可以同時存取同一個資料結構
不允許同時間，超過二個以上的writer存取同一個資料結構

**目標**
- 希望可以盡可能地提高平行度，例如：讓多個reader同時讀
- 上一個目標通常會造成reader的優先權比較高，希望writer和reader都有足夠高的機會進入critical section

#### Reader

如果現在有writer在cs中，R0就會卡在wait(wrt) R1、R2則是卡在wait(mutex)，因為R0還沒解開mutex

### 哲學家問題

#### 在Linux kernel中的應用
藍色的task比較少，所以會把黃色的拉來做／黃色的覺得自己的太多會推給其他人做，但可能就變成黃色的丟了兩個過去，整個會亂掉。
所以黃色CPU會做的是鎖住自己的run queue再鎖住藍色的。
藍色的是鎖住自己的再鎖住藍色的。
就是先拿左手再拿右手的概念。只要有一個人成功鎖住就好，只要保證不會同時搬

### 執行結果正確與否
已知狀況二是ok的，且兩者最後執行結果相同

**我們是否可以把平行化以後的正確性定義為「其結果等價於某一個依序執行的狀況」？**

### Cache coherence 保證快取內容的一致性
混合用法就是將各個cpu分成群組，用一些空間紀錄哪些群組可能有某種功能（Dictionary），若要更新的時候就在這些群組廣播（Snoop）

**現在的許多處理器，僅僅確保「某些指令」對「記憶體系統」的存取是atomic operation**

### 既然有cache coherence 何需atomic operation？
- 如果「說時遲那時快」的瞬間，二個core對同一個變數做修改（write），那麼其他處理器是否會看到「中間產物」（如：alignment造成的問題），像是如果要修改00 11變成01 00，會不會變成分成兩塊修改，就會有其他處理器看到01 11或是00 00，只修改一半？

- 如果在很大的處理器中，有很多核心，能保證這個core的write可以用一致的順序傳遞給所有core嗎？如果不行，那麼即使有cache coherence，write也不是atomic！

**解決方法一：**
讓所有「記憶體系統」的操作都是atomic operation（就是之前的turn，某個thread要修改就lock住bus）
這對硬體的難度太高，等於任何時間所有處理器看到「壹模壹樣資料」，「同步成本、資料交換成本」超高

**解決方法二：**
由硬體保證「部分指令」對記憶體的修改能做到「一模一樣」（依照軟體的需要，也可以「幾乎一模一樣」）
軟體和硬體工程師，共同決定「部分指令」或「創造些新指令」，以有效解決此問題（有效指的是：硬體好設計，軟體好撰寫）


**只保證某些指令是atomic operation**
傳統上有：test_n_set、swap（請注意：這二個是組合語言）
X86為例：lock bts X, Y /*Bit Test and Set*/
X86為例：lock xchg EAX,mem /*exchange*/

#### test_n_set、swap的缺點
test_n_set會一直廣播value=1，造成bus很忙，會不好。

- 對記憶體不斷的更新，意即不斷地觸發「cache coherence」
- 此外這二個指令都是「read-modify-write」，指令較為複雜，可能會讓「cache coherence」變得更加沒效率

#### 改進：compare_exchange 可以避免不斷的寫入記憶體
一開始只有先監聽，write只有一次，實際上只有obj=desired才需要廣播

- 在大部分的情況下，只會讀取值，做比較，如果和期望的值不一樣，不做任何事情，通常不需要額外的「cache coherence」
- 當讀取得值和期望的值不一樣時，才寫入。
- 請注意，通常write一定會觸發「cache coherence」。因為「值」改變了那麼需要讓各個cache的內容「一致」

### spin-lock設計的基本技巧（重要）
**「檢查-進入」這樣的方式是不對的，因為在檢查和進入之間可能會有其他thread同時做「檢查」，其結果是可能多個thread同時進入**
因為如果有很多thread同時做這件事，可能第一個還在做檢查，第二個就檢查完已經進入，但第一個檢查結果是可以進入，結果因為第二個已經先進入就出事了。

**常見的spin-lock的寫法是「改變lock 的狀態-檢查-確認是否lock成功」**
- 因為先改變lock的狀態，因此其他thread就算同時要進入critical section也都會先做這個動作
- 如果lock失敗，所有thread都重做一次（即：spin），總有一個可以成功

**另一個常見的做法是「檢查和鎖住」用一個atomic operation同時做「檢查和鎖住」 ，如： compare_exchange_weak、compare_exchange_strong、swap、test_n_set**
效率：
- compare_exchange_weak、 compare_exchange_strong較有效率
- swap、test_n_set在硬體上較沒有效率

### sequential lock
讓reader付出成本的reader-writer solution
這個版本的seqlock只可以有一個writer

#### 演算法概念
reader一開始會記錄版本編號，之後會檢查是不是跟原本的不同，如果不同代表中斷有進來，有修改時間相關資料結構，讀到一些舊的一些新的，所以要redo。


### ticket lock
具有FIFO功能的spinlock
其overhead與spinlock差不多

#### 演算法概念
- 每一個人想進入CS前先抽一張號碼牌
- 然後等「叫號」，如果叫到的號碼跟自己的號碼牌一樣，就進入CS
- 離開CS的時候，做「叫號」，即讓下一個號碼的人進入CS


### rw-spinlock
如果系統中reader的數量非常多，writer可能會starvation

#### 演算法概念
**系統中有很多張門票（例如：1000張）**
- writer要進入CS，一次要拿到1000張，這確保了其他writer、reader都不能再進入CS

- reader要進入CS，一次拿一張門票
因為已經拿了一張門票，因此writer不可能拿到全部的門票
系統有很多張門票，而每一個reader只要一張門票，因此可以有多個reader同時進入CS

在實作的時候不要把「最大門票」設定的太大（例如：不可以設定成INT_MAX ），因為在實作的時候，writer會先試著拿門票，這個步驟會將現有門票減「最大門票」值，如果多個writer同時進入CS，可能會造成underflow


### Linux kernel中的semaphore

主要的函數：
- down(semaphore *sem)，如果count>0表示lock成功，程式進入CS。否則將呼叫這個函數的task串到wait_list（相當於waiting queue），然後呼叫schedule()
- up(semaphore *sem)，如果wiait_list是空的，那麼count++，否則從wait_list找出最前面的task，將該task自wait_list移除，並呼叫wake_up_process將這個task放到適當的run-queue

#### 新版的down函數
- **down_interruptible()**
明確的告訴kernel，如果發生signal的話，喚醒這個task
- **down_killable()**
除非是fatal signal，否則這個task會一直睡下去，直到等待的事件發生（例如：waiting for I/O operations to complete）

### memory order

**atomic_store(&flag[0], 1);**
- 這一行程式碼使用了最強的記憶體模型
- 限制了compiler的優化空間，形成一個「屏障」，compiler無法跨過這個屏障做優化
- 限制了CPU的優化空間，CPU無法跨過這個「屏障」進行動態調整指令的執行順序（out-of-order execution）
- 限制了多處理器的優化空間。這行指令會強制所有處理器進行同步
- 雖然大幅度的降低電腦效能，但在程式設計上相對簡單許多
- 效能 ⇩ & 開發時間 ⇩ & 除錯時間 ⇩

typedef enum memory_order {
    memory_order_relaxed,
    memory_order_consume,
    memory_order_acquire,
    memory_order_release,
    memory_order_acq_rel,
    memory_order_seq_cst
} memory_order;

越下面越強

#### memory_order_relaxed
應用情境：
- 例如統計一個平行函數的呼叫次數，只要是atomic就好，不需要關注前後關係

#### memory_order_consume & release

應用情境：
- lock時用acquire
- unlock用release

consume & release，應用 問號？

#### memory_order_acq_rel（不是acquire & release）

應用情境：
如果對該變數做「read-modify-write」，要考慮一下是否得用acq_rel


#### memory_order_seq_cst（最strong的memory ordering）

具有acq_rel的所有特性，並且所有宣告為acq_rel的指令一定不同時執行，一定是依照某個順序執行

須滿足下列條件
- Program order: each process issues a memory request ordered by its program.（程式碼上下都不能對調）
- Write atomicity: memory requests are serviced based on the order of a single FIFO queue.


## CH6

### deadlock

**一群task，彼此等待**
有迴圈就有可能會產生deadlock

### 相似的名詞：livelock

**一群task彼此等待，但這群task不斷的改變自身的狀態，但卻無法讓行程的有任何實質的進展**
例如：
- 二個人在狹路上相遇，互讓，但這其中一個人讓出右邊時，另一個人剛好讓左邊。
- 雖然二個人不斷的互讓，但還是無法「前進」

### 相似的名詞：starvation
**starvation（飢餓）問題：來自於某種資源分配方式，讓特定的某些task幾乎拿不到任何的resource**

例如：按照優先權分配resource，優先權最低的task有可能永遠拿不到resource

### 發生deadlock必備的四條件
**一定都要滿足，才會發生deadlock**
- Mutual exclusion：資源無法共用
- Hold and wait or resource holding：握有一些資源等待另一些
- No preemption：OS無法隨意的將分配出去的資源再重新分配
- Circular wait：resource allocation graph中至少有一個等待迴圈

#### deadlock prevention－mutual exclusion
- mutual exclusion是critical section的主要功能
- mutual exclusion通常也是resource的本身特性，例如：印表機不可能讓二個process在同一個時間列印
- 有時候可以改寫演算法，讓resource可以lock-free，例如：上一個章節介紹的lock-free concurrent queue
- 或者「每個CPU自己玩自己的籃球」：互斥的資源，看看可不可以分群，每個人用自己的。不夠用再去跟別人借

#### deadlock prevention－hold and wait
**方法一：所有的process必須一開始的時候，就鎖住所有「可能」需要的資源（因此只有hold沒有wait）**
- 缺點是：會造成resource的使用率偏低，例如：打開powerpoint，因為powerpoint有可能會印出投影片，所以就鎖住印表機！？因為「有可能」就讓其他人在這段時間無法使用印表機
（假設原本是分別在不同時段要abcd四個資源，但現在變成一開始就把abcd四個資源先要來，就變成最後才要用d，但一開始就拿了，被process占用的時間便很長。）
- 其次：鎖定的時間拉長，從「需求開始到資源使用結束」變成「程式一開始到資源使用結束」

**方法二：如果要新的資源時，必須釋放掉手上所有已經鎖定的資源（因此只有wait沒有hold）**
- 缺點：換句話說，就是每次都要重新「一次性鎖定所有『目前需要』的資源」，釋放資源之時，資源可能被其他process鎖定，可能造成starvation
（舉之前的taskA taskB deadlock例子來說，就是taskB原先是先lock(y)再lock(x)，她就先unlock(y)然後lock(x,y)，就是在還沒結束cs之前就unlock(y)，會造成要很多resource的人容易變成starvation）

#### deadlock prevention－No preemption
- No preemption幾乎也是resource天生的性質，如果讓不能preempt的resource變成preemptable代價通常很大
- 例如：印表機原則上是不能preempt，因為需要緊急印資料給客戶，將印表機「關掉，重開」。算是讓印表機「preemptable」的方法之一
- 有些時候可以用rollback解決，例如：上一章節介紹的sequential lock(有點像是賽跑到終點線時兩個人先猜拳，猜輸的就重跑，猜贏的就過終點線)
- 有時候可以用multi-version解決，例如：上一章節介紹的RCU
- 也可以是沒辦法「立即」lock某個resource，該task就釋放掉手上的所有resource（意義上來說，不是搶別人，是讓別人搶）

#### deadlock prevention－circular wait
**依照特定順序鎖定資源，例如：先鎖定a再鎖定b**
「授課老師認為」這是最可行的方法，因為這個方法和資源本身的特性無關，主要是和「程式碼的撰寫方式有關」
例如：我們的作業，行員轉帳
- 缺點：有時候鎖定的順序和使用的順序相反，這會造成資源使用率偏低（舉例來說，原先是先lock(b)再lock(a)，所以a只要鎖住後面一小段區間，但現在要按照字母順序，就變成先lock(a)再lock(b)，就變成資源idle。
- 缺點：必須確認所有的programmer都牢記這個順序

#### deadlock avoidance
**與deadlock prevention不同，deadlock avoidance是不要讓系統進入「可能」造成deadlock的狀態**

我們首先定義「safe state」，表示現在絕對不會進入deadlock狀態，當系統「可能」發生deadlock就稱之為unsafe
**注意：就算是unsafe也不一定會造成deadlock**

##### priority celling protocol（PCP）
PIP就是a在鎖定某個資源的時候，b是一個高優先權的task，也來鎖這資源。
在這情況下會把a的優先權提高到跟b一樣高，讓a趕快執行完之後，再回到原本a的優先權。
但PCP是又多一個叫C的task，優先權是0，是之後有可能會也要鎖定這資源的task，此時a的優先權會提高到0，也就是只是有可能要鎖定就還是要考慮進去，但PIP是確定有擋到才考慮。

#### 如果系統進入deadlock狀態
- 假設系統支援roll back機制，讓某些task roll back，並釋放出resource再重新執行
- 直接殺掉某些task（例如：佔用系統資源特別多的task）

## CH7

### BIOS對記憶體的使用
- BIOS的資料不需要電力就可以保存
- 但BIOS的速度通常較DRAM要來慢
* 為什麼不用flash memory呢？因為flash memory是block device（電路也跟CPU不相容)，而**接到CPU的「記憶型裝置」必須是byte addressable**
- 大部分的BIOS會將自己複製到DRAM中，然後配置自己的code、data section、stack section

### X86的啟動 – BIOS的位置
- 隨後經過一連串的軟硬體設定，進入作業系統的進入點，以Linux為例，隨後進入start_kernel，開始作業系統主要的初始化
- x86的啟動時，執行的第一行程式碼一定是FFFF:0000，因此主機板在焊電路的時候，必須使用address decoder將FFFF:0000對應到BIOS的進入點

舉例一個系統中，由於address decoder固定將FFFF:0000~FFFF:FFFF映射到BIOS
因此我們無法存取主記憶體上的FFFF:0000~FFFF:FFFF，共65K

假設顯示卡上面有128MB的VRAM，處理器只能定址4GB，其中會有128MB無法使用

如果記憶體只有256MB或512MB的memory layout

如果DRAM是4GB


由於PCI等裝置與DRAM共用同一塊address space
4GB扣除掉PCI等裝置所使用的記憶體後，只剩下3.25GB
**解決之道：邁向64位元**

### RAM和VRAM（GPU上面的RAM）
physical address：實體位址，是指主記憶體的某個可以讓資料匯流排存取的特定儲存單元的記憶體位址。就是指系統的記憶體的真正位址
在和虛擬記憶體的電腦中，實體位址這個術語多用於區分虛擬位址。尤其是在使用記憶體管理單元（MMU）轉換記憶體位址的電腦中，**虛擬和實體位址分別指在經MMU轉換之前和之後的位址。**

### 關於DRAM的一些特性、使用
**大部分的系統，只要CPU開始工作，DRAM就會全速運轉，即使我們的系統上可能有多個DRAM插槽，這幾個DRAM被OS視為一體**
- 通常插滿記憶體，就是讓記憶體容量變大，頻寬變大，但OS無法獨立控制各個記憶體（即：DIMM）
- 如果是NUMA架構，OS可以獨立控制。例如：AMD Threadripper是將二顆CPU封裝在一起，二顆CPU各有自己的DRAM controller，因此對OS、程式而言，分為remote和local二種不同記憶體，local速度比較快。
* 如果程式經過優化，可以將常用的擺在local不常用的擺在remote
* 如果沒有經過優化，那麼可以使用interleaving模式，獲得比較大的頻寬

**記憶體用量比較低，省不了多少電**
- DRAM的讀取和寫入還是耗電，但耗電不會太多
- 將資料保存在記憶體必須耗電
- 如果某一個區段的記憶體沒有真正的用途，那麼還是得耗電保存這些「算是garbage的記憶體的內容」

**記憶體的主要用途**
- 執行程式的時候使用（例如：執行excel需要記憶體）
- 當快取記憶體使用，主要是當HDD或SSD的快取記憶體
- 充當buffer使用，和週邊裝置溝通的時候，需要預留一塊記憶體，讓裝置可以讀取或寫入資料（例如：DMA）

由於記憶以不管使用或者不使用，都是耗電，因此OS會盡可能的將記憶體用完，以OS Lab伺服器而言，大部分的記憶體作為cache，因此I/O效能變得更好
類似像memory cleaner這樣的軟體，雖然會釋放記憶體，但可能會造成之後的I/O效能變低。

### 記憶體配置－「區段」管理機制
1. OS找出APP所需要的記憶體

2. OS將執行檔複製到記憶體
3. OS將為給初始值的部分給「0」

### 記憶體很大，CPU很快 可以同時載入多個程式

如圖，同時載入「藍」「綠」「橘」「黃」，四支程式
綠色程式所需要的記憶體最多，藍色的最少
黑色虛線部分代表DRAM的大小
在這個例子中，「黃」的上面還有一部分的空間沒用到

#### 很直觀的解決方法：使用segmentation
- 每個 seg. 對應到特定程式的一個邏輯上的區段
- 每個 seg. 可以是不同大小，因此可以符合應用程式的真正使用情況
- 在這個例子中，不能將一個 seg. 分開存放，例如：不能將「綠色的堆疊空間」拆成二塊

#### 使用segmentation與多工
- 在這個例子中，為了保證每個應用程式在執行時「不會互相干擾（例如綠色不能存取橘色記憶體）」、「ＯＳ很容易的切換正在執行的應用程式（可以很快從綠色切換到橘色）」（即：context switch），由硬體提供映射表
- 這裡只說明需求，硬體於後面介紹
- 此例中CPU內的「區段映射表」只要4個entries
- 例如：執行藍色時，只需要『設定』CPU內的：程式碼區段、資料區段一（給初始值）、資料區段二（未給出始值）、堆疊區段

#### 載入多個程式
在執行完藍色及橘色的程式後，使用者想執行一個大型程式

**如果free space夠多 但無法滿足記憶體需求**

- 如果free space夠多，但無法滿足現有的記憶體需求，就稱之為「External fragmentation」
- 如果因為配置演算法，明明只需要X記憶體，但卻分配了「X+ε」，多出來的「ε」稱之為「internal fragmentation」

如圖，如果OS覺得剩下的空間太小了，沒辦法當作其他用途，而將剩下空間分配給「黃」，那麼就是internal fragmentation

##### 解決fragmentation
如果可以將「綠」往下搬動，那麼就可以有足夠多的空間，容納「紅」
「定址方式」必須是相對定址。
例如：regtarget = regbase + offset，只要改變regbase就可以改變這個程式的記憶體的位址

**執行方式**
為了增加擴充性，我們一次設計三個「base register」，分別是basecode
、basedata、basestack，由於我們一次增加三個暫存器，因此應用程式可以放在不連續的地方，code、data、stack可以分開存放

由作業系統進行搬移
1. 首先將「綠」暫停執行
2. 將「綠」複製到指定位置
3. 重新設定base reg. file裡面各個暫存器

**切換行程**

**加入一些保護機制**
- 為了預防程式碼寫錯，因此我們依照各個segment的大小設定limxxx
- 如果程式碼存取、執行錯誤的記憶體，那麼會觸發segmentation fault


要比較150000跟limcode（150000送到紅色箭頭處)，比較lim跟150000看是否比較小，比較小就通知（黃黃的東西）把address傳送出去，沒有比較小就是程式有問題，offset已經超出範圍

### 記憶體配置－「分頁」管理機制
但實際上會是長條的
在這個例子中，為了保證每個應用程式在執行時「不會互相干擾」、「ＯＳ很容易的切換正在執行的應用程式」（即：context switch），由硬體提供映射表
- 因為記憶體最多有48個page，因此應用程式最大可以使用48個page。那麼映射表最起碼要48個entries
- 要能針對每個page的用途設定屬性，例如：stack(rw-)，data(rw-)，code（r-x）
- 雖然stack和data的屬性是一樣的，但OS會給他們不同功能，例如：stack會自動長大

範例圖：
va（virtual address）雖然一樣，但對應的pa（physical address）不一樣

### 比較二種機制－優缺點

### 比較二種機制－碎裂問題：因動態儲存體分配
**在動態儲存體分配的情況下，例如：記憶體、磁碟空間等，必定會造成 fragmentation （碎裂）問題**
**基本定義：系統的free space大於Ｘ，卻無法配置X大小的可使用空間
在segmentation的情況下，因為free space不連續，稱之為external fragmentation（因為碎裂不隸屬於任何segmentation）**
- 在paging的情況下，由於每個page的大小一致，並且透過映射的方式將不連續的page變成連續空間，因此沒有external fragmentation
- 在paging的情況下，由於應用程式所需的記憶體不會剛好是page大小的倍數，因此只能「多給一些」，這「多給的部分」為internal fragmentation（舉例來說有個應用程式只有20Byte，但一個page是4k，還是需要給他4k的page，就會有非常多記憶體被浪費）

### MMU與MPU
- MPU的全名是memory protection unit，功能是：可以設定某段記憶體的讀寫屬性
- MMU的全名是memory management unit，可能是：可以設定某段記憶體的讀寫屬性，**並且可以透過MMU讓OS更有效的分配記憶體的使用**

### MMU的最小管理單位
**以paging為最小管理單位（本小節只討論這個）**
- 因為page比較小，因此每個應用程式擁有的page很多，在保護機制上稍稍困難些
- Page的大小為4KB及開始位置為4KB的倍數，如此規律，讓管理上簡單多了
- 因為page很小因此mapping entries很多，例如：4GB的記憶體需要1M個mapping entries，這對硬體是額外的負擔

### MMU應該長成什麼樣子
**在pageing機制，我們將「page_number + offset」送到MMU**

translation lookaside buffer（TLB）

**TLB的數量，限制了程式的大小**
x86架構下，程式碼＋資料＋堆疊 ＜ 1024（entries，程式碼用的TLB） × 4KB = 4MB
MIPS架構下，程式碼＋資料＋堆疊 ＜ 384（entries，程式碼用的TLB） × 4KB = 1,536KB

**解決之道**
- 增加TLB數量
- 動態載入TLB

### 增加TLB數量
- TLB基本上是一個「平行搜尋」的硬體
- 意即page number會同時和數十個到數百個TLB entries做比較，如果擴充TLB會增加硬體成本
- 這裡的硬體成本可能為：電晶體數量、時脈降低、耗電等等

### 增加page size（frame size）
**增加page size是個好主意，但page size越大，軟體在管理上的彈性就越小（這下一個章節virtual memory會討論）**
**各種處理器幾乎都有「huge page的選項」**
- X86-64為例，有下列選項
- 4K, 2M and 1G
- Linux可以使用mmap配置記憶體，具有「MAP_HUGETLB」選項

### 動態載入TLB entries
當MMU發現某一個記憶體位址的page number在TLB找不到對應的entries時，可以觸發某種機制，將當下要用的TLB載入
記憶體很大，可以將所有的映射表存放在主記憶體中

以下討論如何放映射表

#### 硬體做

要找到「連續的500K」、「再找到連續的700K」、「再找到連續的650K」、「再找到連續的1,500K」…「再找到連續的…」…「再找到連續的…」
這些程式會動態生成，也會消失。久而久之會造成external fragmentation問題
**paging本來是用來解決fragmentation，但自己也遭受fragmentation**

##### 對「page table structure」再paging

**對page table進行paging以後，所有的「分配單位」，包含：page table、data page的大小都4K**，對OS來說，所有的「分配單位」大小一樣，都對齊4K的倍數，徹底解決external fragmentation問題

以我們的例子來說，32位元的CPU，logical address是32bits，但page table entry只用了20個位元（因為對齊4K，後面12位元不論值是什麼，MMU視而不見，MMU只看page number）
還剩下12個位元沒用到，這些位元在下個章節會被用來描述「page的屬性」

### TLB miss硬體方法

- page table中共有1024個entries，每個entries的大小為32bits。
- 我們將page table中的entries，命名為page table entry，簡稱為「pte」或「PTE」

#### 範例


### TLB miss軟體方法
MIPS處理器使用了software-managed TLB，當TLB miss時將觸發exception將由OS kernel進行後續處理

## CH8

### page table entry(PTE)

[page table descriptor](https://zhuanlan.zhihu.com/p/67053210)

**PTE+PTE+PTE+… = page table**
i跟v代表valid invalid，是指有用或是沒用的對應，最後位元是v硬體才會去讀他。

在X86，第一層的page table放在CR3暫存器中，attr是放page table後面12bit的屬性，page table是放在DRAM中

### 什麼是virtual memory

#### 嚴格的定義
當CPU所要存取的記憶體根本不在DRAM中，該如何處理呢？這種錯誤我們稱之為「page fault」
- 如果我們假設啟動軟體時，就將這個軟體所需要的記憶體全部配置到DRAM，那麼「page fault」意味著這個軟體是有問題的「例如：segmentation fault」

設計OS的人重新詮釋了「page fault」的意義，例如：
- OS「暫時還未將」這個page載入DRAM，重新載入即可
- OS讓不同process「隱形共用」內容相同的page（例如fork）
- 只讀不寫，那麼不會有任何問題發生，而且還可以減少記憶體的時用量
- 面對寫入，OS必須保證「各個」process在邏輯上，各自有一份copy

#### 寬鬆的定義

**透過設定MMU，讓記憶體的『映射更加靈活』的各種做法**
- 例如：shared memory，使得二個process可以共享記憶體，以提高交換訊息的速度
- 可以將檔案映射到process的memory space中
- 也可以將部分I/O的記憶體映射到process的memory space中，因此可以讓user space process可以直接控制周邊（Linux中用mmap存取/dev/mem）

### Virtual memory的組成要件
**『硬體定義的表格』每個process都應該要有自己的page table（就是MMU可以讀懂的那一個。這裏假設TLB miss由硬體處理）**
- 如果TLB miss了，硬體查詢page table，還是找不到，這時候會觸發page fault exception

**『純軟體表格』每個process甚至是Linux kernel都需要一個查詢表，快速的查詢每個記憶體是否正確，如果正確還發生page fault，要怎樣處理？**
會定義process的堆疊、程式碼...等區段

**『處理page fault』OS必須有page fault handler（interrupt service routine）**
- 通常要記錄：錯誤的原因、發生錯誤的IP、造成該錯誤的address


### virtual memory的例子

#### shared pages（共用靜態資料，使用者自訂分享）
heap、stack是兩個shell各自獨立的，黑色的是兩者共享的。
共享有分兩種，一種像是code跟libc是os決定要共享這幾塊，因為這兩個是在硬碟裡面，這兩段資料會映射到硬碟裡面的同一個執行檔，所以os會非常知道這兩塊資料其實是一模一樣。
另一種分享是mmap的，不是作業系統自動分享的，而是shell呼叫mmap這system call，去講要一塊記憶體，這塊記憶體會拿到特殊的符號，去給shell-1，shell-1再傳給shell-2，兩個人就可以把這段記憶體映射到自己的記憶體空間裡面。要注意的是shell-1跟2的mmap開始的address不會一樣，所以不能互相傳遞address去存取資料，而是要傳遞offset，再加上原本的address。
要注意的是盡量不要在mmap裡面指定要映射到哪裡，因為有可能下次執行就不能用，因為mmap跟函數庫很近，如果安裝新的library之類的，可能下次執行就不能用了


##### 如何共享記憶體？

#### demand paging（執行時期，按照需要載入）
作業系統並不會立即將使用者所需要的記憶體配置給應用程式
發生 page fault 時（也就是），才會載入（或者填入）該段記憶體的資料

##### Demand paging 的優點
優點是只載入需要的資料，因此
- Less I/O needed（這邊指的是量）
- Less memory needed （通常我們不需要將應用程式每個地方都執行過一次）
- Faster response（指的是啟動時間，有時候只需要載入一點點資料就可以開始執行了）
- More users/programs（因為每個task只載入真的需要的資料，因此所需要的記憶體較少。換句話說，可以載入更多的應用程式）

##### Demand paging 的缺點

**對於磁碟系統而言，demand paging雖然減少了讀取的「量」，但demand paging往往引起大量地random access。**
- 舉例：如果執行二個應用程式，這二個應用程式各是100MB，那麼OS可以驅動disk，用2秒的時間載入這二個應用程式
- 如果使用pure demand paging，假設只要讀入10MB，那麼需要2560個pages，假設這二個程式剛好輪流執行，而且執行的程式碼「隨機散佈」，目前硬碟的IOPS約為200，因此載入二個程式的時間變為25.6秒

**除了引發大量的random access以外，demand paging也可以會造成執行期間有些「延遲」(lag)**
- 例如：我們不希望玩遊戲的時候有延遲，因此我們寧願一開始的時候就將所有遊戲所要用的資料全部載入

作業系統依照該page的屬性，從不同地方抓資料

共享的部分是mmap實體上的共享，就是zero-out page填到mmap裡面，每個process各自會有read跟write權限打開

prsent為0有兩種情況，一種是os沒有真正載入，另一個是應用程式自己寫錯的。清空為0的時候由os詮釋是甚麼情況，如果是os的問題os就載入再改成1。

##### Demand paging的做法
**事件：應用程式執行一個指令，這個指令造成Page fault**
OS收到page fault後，會去查「一個記憶體分配表格(mapping table，見下方圖)」（這個表格是在OS載入程式時設定的，即mm_struct），看看這個記憶體位址是否合法。
合法➣
- 找到一個空的frame，初始化該frame，修改page table，invalid=>valid
- 重新執行該指令

非法➣
- Segmentation fault，終止程式或者喚醒gdb


#### copy on write（用於fork，可以快速的產生child）
問號

copy-on-write讓parent和child process在記憶體能共用一個page，只有在child要寫入資料時，才會複製一個page出來，放到free page。

舉例來說如果有人要write的時候才會copy
如果沒有free page的時候，可能會需要額外的記憶體空間


**觸發時機通常是 fork()**
**因為parent和child在一開始的時候，內容完全相同（除了暫存器），因此**
- 複製parent的mm_struct給child
- 將parent和child的page table都設定為read-only<font color=red>（重要提醒：修改完後page table後，記得要去TLB把相關的entry去清空，讓她每次都發生TLB miss，重新讀一次page table）</font>
- 此時parent和child在實際上是共用所有page，但邏輯上是二個獨立的task

**如果parent或child對某個「原始屬性為可讀寫」的page做修改**
- 違反「read-only」，產生page fault
- Linux複製造成page fault的page，將其中一份給parent，另一份給child，因為parent和child都有自己的copy，因此可以將屬性變為「可讀寫」

#### zero-out-page（OS要給App什麼樣的page呢？）

page free之後os不能隨便拿給其他的task使用，要把記憶體內容填入0，避免資料外洩。

#### same-page merging（OS將同樣內容的合併）


### page replacement演算法

**目標：最小化page fault的數量**
這部分討論的演算法，把哪一種page換出

#### FIFO
越早進來的，越早剔除


#### Optimal
剔除『未來最久』沒用到

#### LRU
剔除最近最沒用到

#### second chance
可以用硬體實現
存取記錄用的，作業系統每次執行「replacement」時，會給「reference bit」為「1」的page第二次機會

紅色表示還可以給一次機會


#### LFU
剔除用過次數最少
橘色為使用過的次數，如果平手就FIFO

#### MFU
剔除用過次數最『多』

#### 總結
**『Optimal』剔除掉『未來』最不可能用到，因此一定是最佳**
- 但『未來』是什麼無法得知

**LRU，剔除掉『過去』最不可能用到**
- 基於『過去』預測未來，這個演算法實際的效能不錯
- 完全實現LRU需要高昂的硬體，例如：紀錄每個page的上次存取時間

**second chance，為LRU的近似演算法**
- 如果經常存取，那麼「reference bit」就會一直是「1」
- 作業系統每次執行「replacement」時，會給「reference bit」為「1」的page第二次機會
- 題外話，「reference bit」可以直接當作LRU方法，相當於只用一個bit實現「時間戳記」

**FIFO，放在記憶體最久的，優先替換掉**
- 放在記憶體多久的時間，與接下來是否會用到的關係不大

**MFU，最常使用的page優先替換掉**
- 邏輯是最常用的，所以接下來應該不會用到，會很奇怪

**LFU，過去少用的，優先替換掉**
- 邏輯是保留過去常用的。過去常用的，接下來也會常用

### Linux’s page replacement

先不管最近丟棄（因為很少碰到這情況）
上下兩個pages都是用LRU，當有新的page進來，會先存到inactive的head那，若inactive太滿，會從tail丟掉。如果第二次存取到同樣的page，會把他從inactive移到active的head。若active太滿則是從tail塞到inactive的head。

記錄表是當有新的page進來，會去表格裡找是不是最近丟的page，如果是的話就馬上丟到active pages中



### Linux系統的運作方式

最左邊綠色及粉紅色分別代表兩個不同的應用程式

#### 掃描」需要解決哪些問題？
需要從physical address往前去page table中找access bit

#### 「移除」需要解決哪些問題？
一樣需要從physical address往前去page table中找valid bit

#### 演算法是「記憶體多多益善」嗎？

**「記憶體多多益善」的意思是，記憶體裝的越多，那麼page miss 就越少**

**給定一個reference string，如果在任何時間點，「n」個frame所容納的page是「n+1」個frame所容納的page的子集合，則這個演算法是「多多益善」**
- 舉例：當frame個數為4時，容納的page是「a, b, c, d」
- 當frame為5時，容納的page是「a, b, c, d, e」，為「多多益善」
- 當frame為5時，容納的page是「a, b, f, d, e」，因為 c 不在裡面，如果接下來應用程式存取的記憶體是「c」那麼 5 個frame的效能反而更差

## CH9

### 硬碟名詞




### 硬碟的讀寫動作
1. 移動讀寫臂到要讀寫的該cylinder（seek time）
2. 等待轉盤持續旋轉，直到要讀取的sector剛好位於讀寫頭的位置（rotational delay）
3. 開始讀取
4. 傳輸資料到disk buffer （transfer time）
5. 從disk buffer傳輸資料到DRAM（transfer time）

### SMR
寫入密度提高，適用於儲存
對於「修改」的支援度變得很低
SMR 可壓縮拉近磁軌間距，以達到更高的磁錄密度。若磁軌有如屋瓦般彼此重疊，即可在相同空間中寫入更多資料。當新資料寫入時，硬碟機磁軌會縮小或疊起。



由於磁軌是互相重疊的，這就意味著覆蓋一個磁軌，也會影響鄰近的，會被一起重寫，因此如果我們隨機寫入一個磁軌，由於寫入磁頭的寬度比磁軌寬，因此寫入會影響到臨近磁軌；如果這個臨近磁軌有資料，這些資料就也需要重寫以免資料被破壞，依此類推。

### flash memory
最小讀、寫單位為page
最小抹除單位為block（比較大，以三星的為例，Page為16k，block為4M

#### wirte

#### erase



### out-of-place所造成的問題



會提供映射檔（藍色部分FTL)，會記錄block位置讓作業系統知道

### 混合式架構

### 階層式架構


### SSD scheduling（有NCQ）
SSD具有多個通道，可以同時驅動多個晶片
**目前控制器一次能從OS收到多個command，因此可以最大化SSD使用率**
- 以廣泛支援的native command queue而言，queue的長度為32

一次最多8個晶片同時作動，因此產能可達667MB/sec
- 相較於一次作動一個晶片，其產能只有83.4MB/sec

### disk scheduling

### 檔案分配方法

#### contiguous allocation

#### extents
從上面例子來看就是多加一塊連續的空間（不強制一定要連續，能連續最好），就可以放file1的延伸東西

#### linked allocation
開頭是4
標準的linked allocation進行隨機隨取時非常緩慢，因為要逐一的走訪（n-1）個block，才能找到第n個block。

##### linked allocation （FAT）

#### index allocation
系統為每一個檔案配置一個index block，這個index block紀錄這個檔案的data block散佈在storage的哪些位置

##### 如何擴增檔案的定址空間？
如同page table structure一樣index再index
當n層index時，存取某個data block，最多需要n+1次的storage access
假設「4」層index時，如果一個檔案就只有一個data block。那麼檔案系統的overhead非常大
- 檔案系統使用掉「4」個block做index，但只有一個data block
- 因此overhead為400%

### free space management

#### btrfs的做法

### 目錄的設計方法