# Overview
* 作業系統屬於「軟體」，目的是使機器更容易地執行程式
* 讓程式們公平的使用資源
* 能與其他設備互動
* 提供api讓使用者能與系統資源互動
* Running a program = 執行一系列的指令

作業系統 = Processor + Memory + I/O interface

* Mechanism: 定義某個功能的概念
* Policy: 實作某個功能的演算法

# Process
作業系統具有以下api以控制Process
* Create
* Destroy
* Wait
* 其他控制(ex: 暫停、回復)
* 取得狀態

## Process 狀態
* New: 將相關資料從disk載入至memory
* Ready: 已準備好隨時被CPU執行
* Running: 正在被CPU執行
* Waiting(Blocked): 等待某個事件發生(ex: 等待輸入)
* terminated: 執行結束

### 創建 Process
一個Process在memory中所佔用空間的分配:
text: 決定要Fetch那些資料
data: 放全域變數
stack: 放置區域變數、函式回傳的address等
heap: 放動態配置的記憶體

## Process Control Block(PCB)
是一種作業系統用來追蹤Process的資料結構，其中儲存了以下資訊
* Register context: Process 被暫停後，register要暫時挪給其他Process用，故需要這個額外的空間將register的值暫時記住
* State: Process當前的狀態
* Program counter

## Dual-mode operation
Dual-mode指的是 kernal mode跟user mode，為了確保OS能掌握控制權，user Process 的某些操作(ex: 配置記憶體) 需要透過OS Process執行；換句話說，user Process的某些操作必須要間接透過System call，請OS Process 來執行

## Interrupt
當發生特定事件時，硬體或軟體可以通知CPU，使CPU暫時放下手邊執行的工作來處理這個Interrupt，並重新安排任務執行順序

Interrupt可以被硬體或軟體所觸發:
* hardware: I/O設備可以發送一個signal來實現Interrupt
* software: 通常是system call

### 流程

## CPU 判斷 I/O 完成的邏輯
1. Polling: CPU定期檢查I/O是否結束了沒
2. **Interrupt**: 當I/O結束時，I/O device(硬體) 會送一個signal通知CPU，接著OS會進入kernal mode，來決定接著要讓CPU執行哪個Process(I/O結束的那個或是正在執行的那個)

補充: 由軟體產生的Interrupt通常稱為trap或是System call

## OS 重新取得CPU控制權的方法
1. 等待System call
2. Timer interrupt: 定時觸發一個interrupt

### Context Switch
指的是作業系統在切換不同Process時，保存和恢復每個Process的狀態信息的過程，操作本身並不會對Process運算有任何進展

由dispacther執行

## Process scheduling
假設一個CPU要同時有多個Process要處理，為了最大化使用效率，在分配資源的時候，需要盡量滿足以下原則:
1. 希望盡量讓CPU無時無刻在做事
2. 希望每個Process 都能公平地被執行到

實作上是透過操作一系列的queue，分別用來放置狀態為New、Ready、Wait的process來實現的

(補充)
放置狀態為**New**之process的queue又被稱作**Job queue**
放置狀態為**Ready**之process的queue又被稱作**Ready queue**
放置狀態為**Wait**之process的queue又被稱作**Device queue**
除此之外，也可以根據用途來進一步的命名queue，例如I/O waiting queue

### scheduler 的種類
scheduler的目的是改變Process的狀態，可以分為
* Long-term scheduler (job scheduler)
* **選擇**要將那些Process 從Job queue 轉移至 ready queue 中(從 New 狀態變為 Ready 狀態)
* 不太常使用，甚至有些作業系統沒有
* 控制了multi-prigramming 的degree

* Short-term scheduler (CPU scheduler)
* **選擇**要將那些將Process 從ready queue 拿出來跑(從 Ready 狀態變為 run 狀態)

(補充)
根據process的性質，可以分成兩類:
* I/O bound process: 充滿I/O工作的process
* CPU bound process: 充滿計算的process

適當的混用這兩類process能提升CPU的使用率

(補充)
CPU–I/O Burst Cycle: 一個Process在執行的時候，通常處於"**交由CPU執行中**"跟"**等待I/O**"兩種狀態，burst time指的是等待時間

CPU burst time: Process交由CPU執行的等待時間

### Dispatcher
scheduler 選擇要轉移狀態的Process後，便會交由Dispatcher來**完成轉移的動作**

Dispatcher 的工作具體有:
* switching context: 保存當前Process並切換至新的Process
* switching to user mode: 控制執行user Progrem的權限以保護系統
* Jumping to the proper location in the user program to restart that program: 重啟先前暫停的Process時，能順利跳至上次暫停的位置繼續執行

重要概念:
Dispatch latency: Dispatcher暫停一個Process到執行另一個Process之間所需的時間，可以視作切換Process所需的時間成本

### 理想狀況下的scheduling Algorithm
定義一系列參數作為衡量標準
* **Turnaround time**
Turnaround time = process完成的時間 - process arrive的時間

* **Waiting time** (指的是Process在ready queue中的等待時間)
Waiting time = process完成的時間 - process arrive的時間 - process需要執行的時間(brust time)

* **response time**
response time = process第一次跑的時間 - process arrive的時間

1. First In, First Out
* 邏輯: 先arrive的Process先執行，直到執行完畢後再換下一個執行
* 缺點: 若不小心執行到CPU burst time過長的Process，會導致其他Process等待過久 (**Convoy effect**)
* 範例:

Average Turnaround time: (100+110+120)/3

2. Shortest Job First(SJF)
* 邏輯: 同樣是先arrive的Process先執行，直到執行完畢後再換下一個執行；若有多個Process同時arrive，則挑選CPU burst time短的Process先執行
* 缺點: 若先到的Process的CPU burst time過長，會導致其他Process等待過久 (**Convoy effect**)
* 範例:
Average Turnaround time: (10+20+120)/3
3. Preemptive SJF
* 邏輯: 無論何時都選擇**當前剩餘CPU burst time最短**的Process執行；Preemptive的意思是Process執行到一半允許被打斷
* 可以被證明這種scheduling的方法可以最佳化Turnaround time跟Waiting time(前提是已知每個Process的CPU burst time)
* 缺點: 現實中不能精準得知一個process要執行多久
* 範例:
Average Turnaround time: (120+10+20)/3

4. Approximate SJF:
* 邏輯: 跟類似，不過CPU burst time用猜的，使用exponential average來預測下一次的CPU brust time
* tn: 第n個Process 實際的CPU brust time
* τn+1: 下一次CPU brust time的預測值
* τn+1: 上一次CPU brust time的預測值
* α: 常數，通常為1/2
* 範例:

5. Round Robin (又稱為 RR 或 scheduling quantum )
* 邏輯: 每隔一定時間(Time slice)就從ready queue中公平的挑出一個Process執行，讓每個Process都能平均的被執行到，以降低response time
* 缺點: context switch成本高
* 範例:
Average Turnaround time: (13+14+15)/3
Average Response time: (1+1+1)/3

### Priority scheduling
現實狀況中，可能某些Process急著被執行，故為每個Process都設置一個Priority number，權限高的有被執行的優先權

* Starvation問題: 權限低的Process永遠不會被執行
* Aging解決方法: 每隔一段時間，便提升還未被執行的Process 2的權限

### Multilevel Queue Scheduling
現實狀況中，不同ready 狀態的Process可能有不同的工作性質，故將ready queue細分成不同的queue，並套用不同的scheduling algorithm，同樣為每個queue加上一個不同的權限

* Starvation問題: 權限低的queue永遠不會被執行
* Time Slice解決方法: 為每個queue都分配一定的時間可以使用CPU，例如權限高的queue執行5秒後換權限低的queue執行1秒

### Multi-Level Feedback Queue(MLFQ)
這個概念建立在作業系統中有數個priority不同的ready queue，是關於應該將Process分配至哪個ready queue中執行的演算法

該演算法執行結果類似SJF

假設A、B為兩個Process，Priority(A)指的是該Process處在的ready queue權限
規則:
1. 若Priority(A) > Priority(B)，則執行A
2. 若Priority(A) = Priority(B)，則A、B以Round Robin的方式執行
3. 當Process第一次轉成ready 狀態，會無條件的先進到權限最高的ready queue
4. 若一個Process 累計用光了該queue的Time Slice，則將該Process轉移至低一階的queue中 (避免gaming問題: 惡意使用99% 的Time Slice後，進入假I/O一下，再繼續占用CPU)
6. 每隔一段時間，便將所有的Process全部提升至權限最高的queue中 (避免Starvation問題、讓型態改變的Process有機會翻身)

ex:
* 第一個Process進入系統，分配到Q2
* 第一個Process用光了Q2 的Time Slice，掉到Q1
* 第一個Process用光了Q1 的Time Slice，掉到Q0
* 第二個Process進入系統，分配到Q2；因為Q2權限大於Q0，故先執行第二個Process
* 第二個Process用光了Q2 的Time Slice，掉到Q1；因為Q1權限大於Q0，故還是先執行第二個Process
* 第二個Process執行完畢，換第一個Process執行
* 第一個Process執行完畢

ex:
* 第一個Process進入系統，分配到Q2
* 第一個Process用光了Q2 的Time Slice，掉到Q1
* 第一個Process用光了Q1 的Time Slice，掉到Q0
* 第二個Process進入系統，分配到Q2；因為Q2權限大於Q0，故先執行第二個Process
* 第二個Process放棄CPU轉而等待I/O，換第一個Process執行
* 第二個Process I/O結束，因為第二個Process權限較高，故切換到第二個Process執行
* 如此反覆直到兩個Process執行結束

### Fair-share scheduling
* 目的是"真正的平等"，而非齊頭式平等
* 真的更重要的Process，便獲得更多的CPU time

1. Lottery scheduling
* 邏輯:
* 根據Process的重要度，分配不同數量的ticket給該Process；每次都抽出一張ticket，並執行對應的Process
* 至於要多少的ticket，則由user決定，再交由系統轉成global value(適當的比例)
* Process也可以根據需求暫時提升ticket數量
* 範例:

2. Stride scheduling
* 邏輯:
* 根據Process的重要度，分配不同數量的ticket給該Process；拿一個大數除以某個Process 的ticket，可以得到該Process的Stride(步數)
* 每次都從ready queue中挑出一個距離起點最近的Process執行，並將其與起點之距加上該Process的Stride
* 範例:
* 大數=10000, 各Process的ticket數量如圖所示
* 一開始，所有Process距離起點的距離皆相同，任意挑選A執行
* A距離起點的距離加100，接著挑B
* B距離起點的距離加200，接著挑C
* C距離起點的距離加40，還是距離起點最近，繼續挑C
* 以此類推，觀察可發現ticket越多的Process執行的越頻繁

3. Completely Fair Scheduling (CFS)
* 特性:
* time slice不固定，待處理的Process越多，time slice便會越短 (利用sched latency來控制，time slice=sched latency / Process 數量)
* 使用"nice value" 來控管Process的Priority，為每個Process都分配一個-20~19的數
* 使用Virtual runtime的概念來使權限高的Process能優先被執行，權限較高則Virtual runtime較少 (類似Stride scheduling的效果)
* 使用紅黑樹來實作ready queue，以提升搜尋、插入、刪除的效率
* 優點: 是Linux 預設使用的排程系統

# memory
為了因應Multiprogramming，不同Process可能需要互相切換，故引入了 memory virtualization的概念

* **memory virtualization**: 給每個Process一個假象，讓Process以為自己擁有獨立的記憶體空間；但實際上各個Process式共用同一個實體的記憶體空間
1* 優點: 很好實做

* free list: 是一個linked list，用於紀錄空的記憶體空間位址開頭

## Address Translation (單純使用base and bound)
* 分配給Process一段連續的物理記憶體，用來存放Stack、code、heap
* 使用virtual memory的概念來使實做更容易(virtual memory從0開始)
* 藉由base and bound機制實現virtual memory跟physical memory之間的轉換

* 左圖是virtual memory
* 右圖是physical memory
* 使用register存放一組base/bound
* virtual memory+base=physical memory
* bound 用來存放該Process的極限virtual memory大小

問題: 會有一堆空間沒辦法被指用
解決: 使用Segmentation

### Segmentation
是一個改善base and bound缺點的演算法

* 概念: 原本在base and bound中，分配給Process的物理記憶體是一段連續的空間；Segmentation允許存放Stack、code、heap的物理記憶體是非連續的 (virtual memory仍然要求是連續的)

ex:

Q: virtual address為100的一條指令(屬於Code區域)，其physical memory為?

* 因為Code區域的virtual memory是從0開始計算的，故直接使用base轉換即可
* physical memory = virtual memory + base
* 所求 = 100 + 32K

Q: virtual address為4200的動態配置變數(屬於heap區域)，其physical memory為?

* 因為Code區域的virtual memory不是從0開始計算的，故virtual memory要先扣掉heap區域的起點virtual memory位置，才能加上base以得出答案
* physical memory = (virtual memory - heap區域的起點virtual memory位置) + base
* 所求 = (4200-4096) + 34K

補充: 若嘗試存取超過heap virtual memory範圍的空間，則會出現Segmentation fault的錯誤

補充:
* Coarse-Grained: 指的是segment數量較少的切法(ex: 切成code, geap, stack)
* Fine-Grained: 指的是segment數量較多的切法(ex: 各個function切開)
補充:
* External fragmentation(外部碎片化): 指的是物理記憶體的總空間是夠的，但找不到大的連續空間以配置
* Internal fragmentation(內部碎片化): 指的是已被配置的記憶體中，有部分實際上並未被使用

## Free space management
能夠處理「不同記憶體大小的請求」
* 在分配空間時，除了分配使用者要求的空間以外，還需要額外的空間儲存size，紀錄本次共分配了多少記憶體(因為free function並不需要size參數)

* hptr由ptr - "header大小" 計算得出

### spliting概念
當一段可用的連續空間大於需要的空間時，將空間切成兩塊，一塊拿來使用，一塊繼續留在Free list中

### Coalescing概念
若有空間被使用完畢並返還後，需合併這些空間

### malloc 與free實作
有了上述觀念後，便可以實作出作業系統的malloc()跟free()函式 (不可以呼叫自己)

1. 初始化
1. 呼叫更底層的mmap函式，配置一塊固定為4096 bytes (1 chunk)的空間
2. 耗費8個byte存這塊空間header的相關資訊

2. 配置空間
1. 填上新空間所需的相關資訊(header的大小相同，不過未配置空間跟以配置空間的header定義不一致)
2. header移動到free space的最前端 (1,2步實作spliting)
3. 回傳ptr作為malloc的結果

3. 釋放空間
1. 用一個暫存的變數紀錄head指標原本指向的位置(16708)
2. head移動到 ptr - 8 的位置 (8代表header大小)
3. 使head->next指向剛剛紀錄的位置
4. 透過演算法掃過free list，Coalescing破碎的已釋放空間

### 分配空間策略
假設free list中有不只一塊free space可以拿來分配，根據選擇思路，可以分成以下四種方法 (假設需要配置大小為M的空間):
1. bast fit: 選大於等於M的空間中最小的那塊
* 缺點: spliting後剩的空間太小沒人要
2. worst space: 選所有空間中最大的那塊
3. first fit: 選第一個符合條件的空間
4. buddy system
* 將大空間分割成兩個小空間，兩個小空間互為Buddy
* 分配空間時，以上述規則不斷分割過大的空間，直到切出來的空間大小適合；最小空間圍32 bytes
* 維護Free list header，指向對應大小的剩餘空間
* 當釋放空間時，若該空間其Buddy也是空的，則合併之
* ex:

buddy system:
優點: Coalescing實作容易、能幫助allocater跟paging system
缺點: 檢查步驟導致performace稍低、即使空間連在一起，但不一定可以合併

## paging (single level)
External fragmentation問題:
若要求Process的物理address space須連續，可能會導致硬碟還有空間，但連續的空間不足，而導致無法回應請求

為解決上述問題，定義Process的物理address space可以是非連續的，並引入paging 機制管理free space

* paging 機制會將physical memory 切成多個大小固定的Page (本例的Page size為16 bytes)
* 可以將virtual address分成VPN 跟offset兩部分；offset的大小跟Page size有關(本例的Page size=2^4，故offset=4)
* 可以將physical address分成PFN 跟offset兩部分
* virtual address 會透過Page table的幫助轉成physical address；Page table就像一個hash table一樣 ( Page_table[VPN]=PFN )

* 這張圖說明了virtual address是如何透過Page table轉成physical address的

優點: 管理簡單、有彈性
缺點: paging table成本高(4MB)、需讀取很多次導致效率變差

paging table中一個entry除了存轉換所需資訊外，實務上還存了一些bit，稱為Common Flags of Page Table Entry (PTE)
* Vaild bit: 用於驗證特定的translation 是否有效
* Protection bit: 指出該Page table entry 是否可被讀取、寫入或執行
* Present bit: 指出該Page table entry 是否被swapping出去
* Dirty bit: 指出該Page table entry是否被修改過
* Reference(Accessed) bit: 指出該Page table entry是否被訪問過

### Translation Lookaside Buffer (TLB)
TLB 是一塊cathe，目的是改善paging 的速度

透過硬體的幫助，加入一塊名為translation lookaside buffers(TLBs)的特殊的快速查找快取來實現

透過spatial locality 來提升性能

* 先去TLB找看看答案(TLB存的是最近被使用的entry)，查找的過程是同時進行的
* 若找不到，則去page table中查entry

補充:
Temporal Locality: 最近使用的資料可能會在不久後再次使用

Spatial Locality: 在"最近使用的資料"旁邊的資料可能會在不久後再次使用

#### 處理TLB miss
* 在CISC 架構中，交由硬體直接處理TLB miss
* 在RISC 架構中，交由軟體處理TLB miss
* TLB miss -> raises exception -> 系統執行Trap handler code

#### TLB when context switch
* 每個Process 都有自己的Page table，但整個系統中的TLB只有一個；為了分辨出TLB中的某筆資料是屬於哪個Process的，新增一個欄位(ASID) 來記住Process ID

* 特殊情況: 兩個Process可能會共用同一個Page(即共享某塊physical memory)，以節省空間
* 以這個例子來說，因為PFN一樣，故

#### TLB replacement 邏輯 (重要)
* 使用LRU(Least recently used)邏輯，每次都剔除一個最久沒被用過的人

## Paging 優化: 使用Segments
進一步優化Paging 的方法，混和Segments跟Paging兩種機制

* 使用Seg 區域來標記
* 讓每個Seg 都有自己的page table

缺點: 只存Base and bound的方式，仍然可能會導致空間浪費(頭尾被使用中，但中間已被釋放)

## Paging 優化: Multi-level Page Tables
### 雙層 Page Tables
* 將Page table切成數個Page，並使用Page directory來做為搜尋的索引
* 使用Page directory來做為搜尋的索引
* 核心概念是"將page table 用page來管理"

* 左邊是舊版的Page table，右邊是新版
* 可發現右邊所需的記憶體空間較小
* 缺點: 要讀兩次memory(一次讀Page Directory，一次讀想要的Page內容)

* 把VPN分割成兩個區塊，分別作為Page Directory Index以及Page Table Index

### 三層 Page Tables
假設原Page table大小是2^21，想要切成一個node 大小2^7

2^21 / 2^7 =2^14，故Page directory所需大小為2^14，還可以再切

2^14 / 2^7 =2^7，故Page directory所需大小為2^14，總層數為三層

駐: 第一層是root還是leaf? root

## 其他 Page table
* Inverted Page Tables
* 所有Process共用一個Page table
* Hashed Page Table
* 透過hashing function的不斷hashing完成PFN的查找

## Swapping
Swapping 機制在memory 的空間不夠時，可以暫時把一個memory 中的一個Page放到disk中 (踢的是Page table所指向的記憶體空間)
* 簡單來說就是把disk當作是memory的延伸

在一個page table entry中使用額外的一個bit紀路該page是否在disk中
* **Page fault**: 當實體memory中找不到想要的資料時，需先將資料從disk中load回實體memory中
* Page replacement: 將某些page暫時轉移至disk中，以釋放空間給其他人
* Lazy approach: memory全滿了之後再執行Page replacement

1. 發現想要存取的Page不在實體memory中
2. 觸發trap，交由OS執行接下來的動作
3. OS去disk中找到要移到memory中的Page
4. OS將要移到memory中的Page載入至memory中
5. 重設Page table entry中的Present bit
6. 繼續執行指令

### 決定哪個Page要被暫時轉移到disk中
1. optimize
每次都移除一個最久才會被access 的page
* 要能預知未來會使用的Page順序才能使用該演算法
2. FIFO
* 先進的先被移除
3. Random
* 隨機挑一個移除
5. LRU
* 邏輯: Resulting Cache State 是一個queue，每次將使用過的page丟到queue的最右邊，並踢掉最左邊的page；
* 缺點: 時間成本高，每次操作O(n)
5. Clock algorithm
* 邏輯:
* 在有限的memory空間中，clock ptr輪流指向每個空間
* 每個空間中都會有一個Reference bit，初始化為0
* 當發生Page fault時，clock ptr會按順序跑過memory。若遇到Reference bit=0的空間，則將該空間作為victim取代之；若遇到Reference bit=1的空間，則將該空間的Reference bit變成0，接著繼續往下走
* 當hit時，clock ptr不動 (檢查hit是一瞬間發生的事，不須透過clock ptr)，hit位置的Reference bit變成1

* 優點: 犧牲一點效率的情況下，相較於LRU，空間成本大幅降低

6. 其他參考目標:
1. Considering Dirty Pages: 只讀沒有寫的那些page不需要重寫回disk，故選擇又舊又沒改過的較佳(設定一modified bit來實做)
2. prefetching: 系統預測將要被使用的PAGE，提前放進Page table 中
3. Clustering, Grouping: 收集數個要寫入disk中的資料後，再一次寫入

## Thrashing問題
Thrashing: 因為一次處理的Process太多，導致memory競爭激烈，效率反而變低

### Working-Set Model: 判斷Thrashing
利用page reference table (呼叫disk的歷史紀錄)來衡量

* WS(t): 在某時間點下的活躍Page的個數
* dleta: 常數，代表這個演算法要參考多少過去的紀錄

定義D= WS(t)中集合的個數

若D>M 便會發生Thrashing，此時會暫停處理某些Process
若D<M 便會增加同時處理的Process 數量以提升效率

## 其他技術
* Address Binding 的時機可以在編譯時、載入時、執行時

### Dynamic Loading

### Dynamic Linking and Shared Libraries

### Demand paging
當Process要跑第一條指令的時候，在將包含第一條指令的Page載入

### Copy-on-Write
Parent Process跟Child Process在未寫入的情況下共用同一塊記憶體空間，當某一方寫入時，在進行分支的動作

### Memory-Mapped File
直接將檔案映射至記憶體中，以節省I/O 速度
缺點: 占用記憶體資源

---期中考線---

# Lock
* 之所以需要lock，是因為在multithread的情況下，可能會出現Uncontrolled scheduling
* 例如兩個thread同時執行以下指令時，可能會因為交錯執行而導致錯誤

    counter = counter + 1

(某個thread先讀，但在寫入前又被另一個thread讀到)
* 這類型的指令所在區域又被稱為**Critical Section**
解決方案: 讓指令的執行具有atomicity的特性 -> 由Lock達成
* lock()提供的功能有
* 讓這個thread嘗試取得某個 critical Section 的lock
* 讓這個thread進入critical section (在 critical Section 的變數便受到 lock 保護)

## Spin Lock
### Test-And-Set (Atomic Exchange)
* 缺點: 不公平、單個CPU時表現極差

* 邏輯: lock->flag負責紀錄某個變數是否被鎖住
* 當 lock->flag 為 0 時，代表沒有人擁有某個變數的 lock，此時便會離開迴圈，並同時將lock->flag設成 1
* 當 lock->flag 為 1 時，代表有人擁有某個變數的 lock，此時便會繼續留在迴圈中等待
* TestAndSet是硬體指令(可以視為atomic的)，邏輯為**回傳傳入的 ptr 的值，並將ptr設成新的值**

### Compare-And-Swap (SPARC)
* 將TestAndSet 替換成 CompareAndSwap

* 邏輯與 Test-And-Set 等價

* Compare-And-Swap 是硬體指令(可以視為atomic的)，邏輯為
* 檢查當前ptr的值
* 若與 expect 相同，則將ptr設成新的值
* 若與 expect 不同，則不做事
* 回傳傳入的 ptr 的值

### Ticket Lock
* 本質上也是Spin Lock，但有些不同
* 具有公平性

* ticket 代表本次會抽出的號碼牌
* turn 代表當前輪到的號碼
* 邏輯:
* 每個Process都會先抽號碼牌 (ticket)，接著陷入迴圈循環等待，直到lock->turn = myturn (turn 輪到自己)時，便會離開迴圈進入 critical section
* 而當某個thread unlock變數時，會將 turn+1，代表換下一個人
* FetchAndAdd()是硬體指令(可以視為atomic的)，邏輯為**回傳當前ptr的值，並將ptr中的值加1**；Ticket Lock 透過這個函式實現 "抽號碼牌" 的 atomic 步驟

## Non spin lock
* 優點: 當thread數量跟
* 缺點: 不公平、單個CPU時表現極差
* m->guard: 負責保證操作queue時不會遇到race condition
* park(): 使當前的 thread 去睡覺 (睡覺不消耗系統資源)
* unpark(thread ID): 使指定的 thread 醒來

* 邏輯:
* lock(): 當某個變數沒人擁有時，直接使當前 thread 擁有這個變數；否則把自己加進 queue 中，接著睡覺等待
* unlock(): 當沒人在睡覺等待時，便不須做任何事；否則叫醒 queue 中的一個 thread
* 問題: 若 thread B 告訴別人自己要去睡覺了 (queue_add()) 但還沒真的睡 (呼叫 park())，此時 thread A 呼叫 unlock() 並把 thread B 叫醒，接著 thread B 才真的去睡覺 (呼叫 park())，此時便會導致 thread B 永遠不會被叫醒 (因為 thread B 睡著了但不在 queue 中)
* 解決方案: 新增 system call setpark()
* 邏輯: setpark() 代表這個 thread 進入"即將睡覺的狀態"，若此時有其他 thread 呼叫 unlock() 叫醒這個 thread 的話，使這個 thread 的 park() 直接回傳，不具有使當前 thread 睡覺的作用

### Peterson’s Solution
* 只靠純軟體便可以解決，能夠保證兩個Process間不會有race condition
* 前提是load 跟 store 指令是atomic的

* flag[i]=true 表示 Process i已經準備好(想要)進critical section
* turn: 現在誰有權限進入critical section
* turn = j: 禮讓給對方先做 (為了避免某方無止盡等待的情況)
* 邏輯: 當對方不想進入 critical section，或是對方禮讓我方時，我方便可以進入 critical section
### Bakery algorithm
* 此演算法適用於n process

* num[i] = max(num[0 to n-1])+1: process i 抽取號碼牌 (此步驟並不是 atomic 的，故仍然可能會有兩個 process 同時抽到同個號碼)
* while(choosing[j]): 不斷等待，直到確認想要比較的那個人已抽完號碼牌便離開迴圈
* while((num[j]!=0) && (num[j],j)<(num[i],i)): 不斷等待，直到想要比較的那個人(j)不想進入critical section(num[j]==0)，或是想要比較的那個人比自己晚生成(透過號碼牌來判斷)時，便離開迴圈

# condition
希望一個thread能等待某個條件的發生，並在條件滿足時被通知繼續執行

api實做:

int done = 0; // 用來確認是否操作是否做完的flag
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER; // 初始化一個互斥鎖，用於保護共享資源的存取
pthread_cond_t c = PTHREAD_COND_INITIALIZER; // 初始化一個條件變數

void thr_exit() {
    Pthread_mutex_lock(&m); // 將操作用lock保護起來，以確定其中的操作是atomic的
    done = 1;
    Pthread_cond_signal(&c); // 發送條件變數的信號，通知等待的執行緒
    Pthread_mutex_unlock(&m); //解鎖
}

void thr_join() {
    Pthread_mutex_lock(&m); // 鎖定互斥鎖，開始進行臨界區域的操作
    while (done == 0) // 檢查標誌，如果條件未滿足
        Pthread_cond_wait(&c, &m); // 釋放鎖，進入等待狀態，等待信號的到來
    Pthread_mutex_unlock(&m); // 解鎖互斥鎖，結束臨界區域的操作
}

使用方式 (在這個例子中，parent thread 會等待 child thread 結束，而 child thread 結束時通知 parent thread)

void *child(void *arg) {
    printf("child\n"); // 在子執行緒中顯示消息
    thr_exit(); // 呼叫退出函數，設置標誌，發送信號
    return NULL; // 子執行緒結束
}

int main(int argc, char *argv[]) {
    printf("parent: begin\n"); // 顯示父執行緒開始的消息
    pthread_t p; // 宣告一個執行緒識別符號 p
    Pthread_create(&p, NULL, child, NULL); // 創建一個新的執行緒 p，執行 child 函數
    thr_join(); // 等待子執行緒的結束
    printf("parent: end\n"); // 顯示父執行緒結束的消息
    return 0; // 主程式結束
}

## 應用場景: producer-Consumer model
* producer
* 負責將request放入queue中 (put)
* 一次可能會收到很多的request (loop)，但一次只會放一個，放到滿(=1) 為止
* **希望在被叫醒時request前queue已經為空**
* Consumer
* 負責回應queue中的request (get)
* 一次可能會被要求處理很多的request (loop)，但一次只會處理一個，拿到空為止
* **希望在被叫醒時request前queue不為空**
* 可能有許多producer跟Consumer

錯誤版:
* 問題: 在一個 producer、兩個 consumer 的情況下，producer 放入一個 request 後去睡覺，並叫醒 consumer 1； comsumer 1 順利消耗一個 request 後去睡覺，但**consumer 2 卻沒有 request 可以消耗** (假設 consumer 2 一直醒著，只是沒機會被執行到)
* 解決方法: 將 producer 的第 8 行跟 consumer 的第 20 行改成 while 迴圈，如此一來被叫醒後便會再次確認當前情況
* 在上面的狀況下，輪到 consumer 2 時會再次確認是否有 request 可以被消耗，接著發現沒有，便會繼續回去睡覺
* 問題: 在一個 producer、兩個 consumer 的情況下，consumer 1 在處理完 request 後，去睡覺並叫別人起來，但叫的是 consumer 2 而非 producer，接著consumer 2 醒來後發現沒有 request 可以消耗，又回去睡覺；至此，所有人都在睡覺，發生非預期情況
* 解決方法: 上述問題發生的主要原因是因為 consumer 叫醒的是 另一個 consumer，只要讓producer 跟 consumer 使用不同的 condition variable，能保證不回叫醒與自己同類型的 process，問題得以解決

最終正確版:

註: 某個 process 去睡覺，其實就是進入 ready queue 中，而 Pthread_cond_signal() 的功能便是叫醒一個在 ready queue 中的人

補充:
**Mesa semantics**: 某個thread被叫起來後，不保證會馬上執行 (大部分的系統架構)
**Hoare semantics**: 某個thread被叫起來後，會馬上執行

# Semaphore
* 是一個更高階的工具，可以被視為一個用來處理同步問題的物件
* 可以拿來取代 lock 及 condition variable
* 具有以下幾個 api 可以使用
* sem_init(&s, 0, 1)
* 第二個參數設成 0，代表這個物件只能在同一個 process 的不同 thread 間共用
* 第三個參數決定了這個物件的初始值
* 設成 1 的時候可以實作 lock
* 設成 0 的時候可以實作 condition variable
* sem_wait(&s)
* 進入 critical section 前呼叫
* 無論如何，先將這個物件的值減 1
* 接著檢查該物件的值，若 <0 則會卡住睡覺，否則離開
* sem_post(&s)
* 離開 critical section 前呼叫
* 無論如何，先將這個物件的值加 1
* 若有其他 thread 正在睡覺，則叫醒其中一個 thread

## 實作 lock

## 實作 condition variable

## 實作 Reader-Writer Locks
* 若一個讀取資料的 process 拿到 Reader-Writer Locks，其他讀取資料的 process 仍可以通行無阻的讀資料，但想要寫資料的 process 會被擋下
* 缺點: 公平性問題

* sem_eait(&rw->lock): 確保 rw->readers++ 的動作是 atomic 的
* 只有第一個想要讀取資料的 process 會取得禁止別人寫入的鎖 (第 5 行)
* 其他想要讀取資料的 process 不會進到第四行的 if，故可以直接進入 critical section

* sem_eait(&rw->lock): 確保 rw->readers-- 的動作是 atomic 的
* 最後想要讀取資料的 process 結束讀取資料之後，才會釋放禁止別人寫入的鎖 (第 5 行)

# Monitor
* Monitor可以視作一個物件，可以解決特定情況下的 deadlock 問題
* 被 Monitor 保護的變數及函式可以被許多 thread 使用，但 Monitor 保證同一時間只有一個 thread 能使用
* 內含 condition variable 以便在各個 thread 之間溝通
* 同一時間只會有一個 thread 使用 Monitor 中的 function

# 常見concurrency 問題總結
## non-deadlock bug
### Atomic violation
需要 Atomic 的程式被中斷，導致非預期的情況發生

ex: 兩個thread 都對某個變數做修改，導致被overwritten

* 解法: 使用 lock 保護變數，確保中間不會被插手

### Order violation
程式執行的順序非預期

ex: Consumer 在 Producer 執行前便先執行了
ex: 存取變數的 thread 比 建立變數的 thread 早執行

* 解法: 使用 cndition variable
* Producer產生出東西後，才通知 Consumer
* Consumer被通知後，才會進行下一步動作

## deadlock bug
* 兩個 thread 同時需要兩個資源，但各自都只擁有一個不放棄，導致卡死

* deadlock 發生四大要件
* Mutual exclusion: 資源同時只能被一個 thread 使用
* Prevention 解法: 把 lock 拿掉，使用硬體指令維護 atomic
* Hold-and-wait: thread 會在拿到部分資源的同時，等待其他資源釋放
* Prevention 解法: 新增條件: 當 thread 可以全拿到所需 instance 時，才選擇拿
* No preemption: thread 拿到某個資源後，別個 thread 便不能強佔
* Prevention 解法: 讓資源允許被強佔
* Cicular wait: 等待的 flow 形成 cycle
* Prevention 解法: 嚴謹的定義 thread 拿鎖的順序

補充: Livelock: 兩個人不斷互相禮讓，導致系統有在運作，但進度沒有前進
解法:

### Resource-Allocation Graph
用於協助可視化資源的使用情況，並系統係的定義 dead lock 的發生情況

* 圖形意義解釋
* 圓形代表 process
* 長方形代表 Resourse
* 長方形中的點代表 Resourse 的 instance；擁有一個 resourse 中的任意 instance 便可以使用該 resourse
* 結論
* 若圖中沒有cycle，則不可能有 dead lock
* 若圖中有cycle，且參與cycle的所有 resourse 都只包含一個 instanse，則必會發生 dead lock
* 若圖中有cycle，且參與cycle的所有 resourse 可能包含不只一個 instance，則可能發生 dead lock

## 解決 deadlock bug
### Prevention algorithm
直接去除 deadlock 發生的四要素之一

### Aviodance algorithm
確保下一步不會發生 dead lock

#### single instance (每個 resourse 都只有一個 instance)
* 基於上面提到的 Resource-Allocation Graph
* 演算法:
* 定義 chaim edge 代表 "可能發生的情況"，以虛線表示
*
#### multiple instance --- Banker’s Algorithm
* 概念是判斷是否能找到一個順序，使程式能安全執行
* 演算法:
* 在分配資源之前，先使用 safety algorithm 確認 "在分配資源後，系統是否是安全的"
* 若確認是安全的，才會執行分配資源的動作

ex:
給定 Allocation / Max Required
| | A | B | C | A | B | C |
| --- | --- | --- | --- | --- | --- | --- |
| P1 | 0 | 1 | 0 | 7 | 5 | 3 |
| P2 | 2 | 0 | 0 | 3 | 1 | 2 |
| P3 | 3 | 0 | 2 | 9 | 0 | 2 |
| P4 | 2 | 1 | 1 | 2 | 2 | 1 |
| P5 | 0 | 0 | 2 | 5 | 3 | 3 |

給定 Available
| A | B | C |
| -------- | -------- | -------- |
| 3 | 3 | 2 |

求是否可以分配給 P1 (0, 2, 0)

解法:
1. 先分配資源下去

Allocation / Max Required (new)
| | A | B | C | A | B | C |
| --- | --- | --- | --- | --- | --- | --- |
| P1 | 0 | **3** | 0 | 7 | 5 | 3 |
| P2 | 2 | 0 | 0 | 3 | 1 | 2 |
| P3 | 3 | 0 | 2 | 9 | 0 | 2 |
| P4 | 2 | 1 | 1 | 2 | 2 | 1 |
| P5 | 0 | 0 | 2 | 5 | 3 | 3 |

Available (new)
| A | B | C |
| -------- | -------- | -------- |
| 3 | **1** | 2 |

2. 計算出 Need matrix (Max Required - Allocation)

| | A | B | C |
| --- | --- | --- | --- |
| P1 | 7 | 2 | 3 |
| P2 | 1 | 1 | 2 |
| P3 | 6 | 0 | 0 |
| P4 | 0 | 1 | 0 |
| P5 | 5 | 3 | 1 |

3. 若某個 Process 所需資源 (Need) 都小於 Available，則
* 先做該 Process
* 釋放該 process 的資源至 Allocation 中

Available (new)
| A | B | C | |
| --- | --- | --- | ---- |
| 3 | 1 | 2 | 初始情況 |
| 5 | 1 | 2 | 選P2 |
| 7 | 2 | 3 | 選P4 |
| 7 | 5 | 3 | 選P1 |
| 10 | 5 | 5 | 選P3 |
| 10 | 5 | 7 | 選P5 |

safety path: P2 -> P4 -> P1 -> P3 -> P5
4. 若能找到 safety path，代表可以分配給 P1 (0, 2, 0)

### 讓dead lock 發生，並即時檢測
主要著重在檢測 dead lock 上

#### single instance
* 若存在環，則會發生 deadlock

#### multiple instance
* 若能找到一組Safe sequence，則當前沒有 dead lock

#### 解決當前的 deadlock
探討當檢測到 dead lock時，如何解決

1. 強制終止所有 Process
2. 不斷一個個拿掉 Process，直到 dead lock 問題解決

# I/O device
--- 斷片 ---

## DMA (Direct Memory Access)

## IDE Device Driver (設備驅動程式)
* 讓電腦的作業系統與硬體設備進行溝通
* 提供 api 給上層應用程式
* 負責控制IDE 硬碟中的各種 register

# Hard disk drive
## 硬碟基本結構
* Spindle: 讓 platter 旋轉的軸心
* Disk arm: 讀寫臂
* arm assembly: 讀寫臂集合，同一時間讀寫臂的位置是同步的
* read write head: 讀寫頭
* Platter: 磁盤，存放資料的地方
* Platter上有一圈圈的 track
* 每個 track 可以再細分成 許多 sector
* 數個 sector 可以組成 cluster
* 不同盤中的相同位置稱為 Cylinder

## I/O time, I/O rate
* Seek time: 移動讀寫頭，使其找到正確 track 的時間 (讀寫頭在 track 間移動的時間)
* Rotation time: 旋轉 platter 使其轉到正確位置所需的時間
* Transfer time: 實際改變 platter 磁場狀態所需時間

I/O time = Seek time + Rotation time + Transfer time
I/O rate(每秒讀寫的資料量) = $\frac{Transfer 的資料大小}{I/O time}$

計算範例 (4KB Random write，假設一個 section 大小為 4KB):
**Seek time**: 4ms
**Rotation time**: 15000 RPM(rotation per minute) = 250 RPS(rotation per second) = 轉一圈需 4ms
-> 平均而言，找到資料需要轉半圈，故 Rotation time 為 2ms
**Transfer time**: 4KB / 125MB =30µs

故 I/O time = 4ms + 2ms + 30µs = 約為6ms
I/O rate = 4KB / 6ms = 0.66MB/s

計算範例 (100MB sequential write，假設一個 section 大小為 4KB):
**Seek time**: 4ms (只需要找一次)
**Rotation time**: 15000 RPM(rotation per minute) = 250 RPS(rotation per second) = 轉一圈需 4ms
-> 平均而言，找到資料需要轉半圈，故 Rotation time 為 2ms (只需要找一次)
**Transfer time**: 100MB / 125MB = 800ms

故 I/O time = 4ms + 2ms + 800ms = 806ms
I/O rate = 100MB / 806ms = 125MB/s

## 優化技術
1. Track skew: 當資料需存放在不同的 track 上時，考慮到 Seek time，調整其資料的擺放位置，以避免 platter 需要多轉一圈才能讀到資料
* 觀察 22~25
2. Multi-zoned (又稱為 Zoned bit recording, ZBR): 使外圈的 track 能存放的 sector 數更多
* 將硬碟分成許多 zone， 每個 zone 中的 track 其 sector 數量一樣，但外圈的 zone 其 sector 數量比內圈的 zone 多
3. 硬碟的Cache (Track byffer)
* 暫存硬碟讀到的資料，等待 OS 讀取
* 將常讀的資料放置於此，以增進效率
* 暫存要寫的資料，並在真正寫入之前便先回覆給 OS 已寫入 (write-Back)，若確認寫入後才回傳，則稱為 write-through
* 暫存 request queue並重新排序優先度，等有時間再慢慢消化

## Disk scheduling
這些 scheduling algorithm 可以在 OS 或 Disk 中做

## FCFS (First Come Fist Serve)
概念: 先到的 request 先服務

## SSTF (Shortest Seek Time First)
概念: 每次都找 queue 中距離當前讀寫頭最近的 request 服務，已減少 seek time

缺點: 會造成 starvation

## SCAN (elevator algorithm)
概念: 選定起始位置及初始方向，走到底後再往反方向走，不斷往返並一路服務路上的 request

適用於硬碟 loading 很重的時候

## C-SCAN
提供了一個比 SCAN 演算法更公平的方法
概念: 選定起始位置，往同一個方向走並一路服務路上的 request，接著**直接跳回頭**後繼續往同一個方向走

適用於硬碟 loading 很重的時候

## C-LOOK
概念: 選定起始位置，往同一個方向走到"**當前 queue 中最後一個 request 的位置**"，並一路服務路上的 request，接著直接跳回"**當前 queue 中第一個 request 的位置**"後繼續往同一個方向走

* 備註: SCAN algorithm 也有 LOOK 版本，跟 C_LOOK 差在反方向走回去的時候也會服務 request
* 結論: SCAN 有許多變形，透過不同個關鍵字來區別
* C: 直接跳回頭
* LOOK: 不要走到底

## 加速技巧
I/O merging: OS 將連續的 request merge 起來，變成新的 sequential request，再將這個 request 送給硬碟處理

## RAID
Redundant Arrays of Independent Disks
將多個獨立硬碟組合成一個邏輯單元

重點: Level 0,1,4,5

### RAID Level 0
* 多設置幾顆硬碟以增加可使用總容量
* 將連續的資料分割成不同區塊，並平均分配到不同硬碟中，如此一來便能同時讀取不同硬碟中的資料以加速
* 分割的區塊大小越大，平行度可能越差，但可以減少硬碟的 position time(磁頭移動到資料所在處所需的時間)


### RAID Level 1
* 讓多顆硬碟存兩兩一組放完全一樣的資料，以提升讀取速度及可靠性


### RAID Level 2

### RAID Level 3
多設置一顆硬碟，以 bit 為單位儲存硬碟資料的 parity

### RAID Level 4
* 多設置一顆硬碟，以 block 為單位儲存硬碟資料的 parity
* 能容忍任何一顆硬碟壞掉
* Full-stripe write: 若要改到同一排的所有 bit，便不需要依序把舊資料讀出來 XOR，直接計算出新的 parity 寫入即可


計算 parity 的方法範例

更新 parity 方法:
* 拿舊的資料跟新的資料 XOR，再跟舊的 parity XOR
* Random write 的性能瓶頸被 parity disk 所限制

### RAID Level 5
* 與 RAID Level 4 一樣以 block 為單位儲存硬碟資料的 parity，但 parity 相關資料分散儲存於各硬碟中，不額外使用其他硬碟
* 如此一來便能分散 parity disk 的性能瓶頸

### 結論
* RAID Level 4 Random write 速度受 parity disk 所限制

# File system 使用
* 檔案所附帶的屬性
* Name
* identifier
* type
* location
* size
* protection

* 能對檔案進行的操作
* create
* write
* read
* seek
* delete
* open
* close
## File
### opening files
* Open-file table: 管理已開啟的檔案
* 同時也會管理該檔案的 file pointer
* File-open count: 用來記錄某檔案同時被多少人開啟
* 目的: 當最後一個人關掉某檔案時，能將該檔案從 Open-file table 中移除
### Access Methods
* Sequential access: 只能依序存取
* read next:
* write next
* reset: 跳回檔案開頭
* Direct access: 可以隨意跳至想要讀寫的位置
### Removing Files
* 以 unix 為例，rm 指令會呼叫 unlink()
* unlink()
* 確認該檔案的 inode number
* 移除 link
* inode number--，若減至0，則真正釋放檔案占用的空間

## Directory
* 硬碟可以被分成需多區(partitions)，根據用途又可以分成
* raw partition: 跟檔案系統無關的空間，例如儲存 database
* Formatted partition(volume): 格式化的區域(包含檔案系統)，file 便儲存至這些區域中
* Directories 便是用來管那些格式化的區域

### Single-Level Directory
所有檔案都在同一層

* 檔案不可以有重複的名字
* 無法分群

### two-Level Directory
多了一層使用者的 level


* 對於每個使用者來說仍然是 Single-Level

### Tree-Structured Directories
使用樹狀的格式儲存


#### Making Directories
使用 mkdir()

#### Reading Directories
使用 readdir()

#### Deleting Directories
使用 rmdir()

注意: 在移除 Directory 之前，須確保該 Directory 為空

### Hard link
> ln file file2
* 使file2 跟 file 共用同一個 inode
* inode number 存的便是有幾個 hard link 指向該檔案

### Symbolic Links (soft link)
> ln –s file file2
* file2 存的是 file 的檔案路徑
* 概念像是桌面中的捷徑

### File System Mounting
將某個檔案系統掛載到另一個檔案系統上，需指定欲掛載的位置(mounting point)

# File system 實作
## Allocation Methods
將硬碟切成許多 blocks，接著進行編號

### Contiguous Allocation
概念:
* 找一段連續的 block 空間儲存檔案
* 如此一來便只需存**開頭的 block 編號**及**占用的 block 數**即可

缺點: 若要分配的空間過大，可能會發生 external fragmetation


### Linked
概念:
* 每個檔案由 blocks 組成的link listed 組成
* 每個 link listed 的 node 可以是一或多個 block，靈活調整以適應系統需求

缺點:
1. 若其中一個 node 受損，便無法找到後面的內容
2. 搜尋時間久


### Indexed
概念:
* 為了解決 linked list 斷掉導致檔案丟失的問題
* 使用 index table 依序紀錄某檔案用到的 block 有哪些


## 簡單的檔案系統 (VSFS)
* 假設這個硬碟共有 64 個 block
* 其中 8 個用來管理檔案
* l: 用來存放 inode (固定大小這顆硬碟能儲存的最多檔案數取決於 inode 的最大數量)
* i: inode 的 bitmap，用來追蹤某個 inode 是否正在被使用中
* d: data block 的 bitmap，用來追蹤某個 data block 是否正在被使用中
* s: super block: 用來存放整個檔案系統的基本資料 (掛載檔案系統時會用到)
* 剩下的 56 個 block 用來存放資料

缺點: 沒有考慮到 locatity 的特性，同一份檔案可能會放置在硬碟中離很遠的位置，導致 performance 降低

### inode 內部結構 (也就是上面的 l)
* direct blocks: 存放多個連結到真實資料所在處的指標
* single indirect: 為了能處理大檔案，故使用多層的形式紀錄
* 下面的 indirect 區域同理，能處理更大的檔案

### 開檔與讀檔
* 開檔的部分
* 讀取根目錄的 inode
* 透過根目錄的 inode 讀取根目錄的 data
* 透過根目錄的 data 讀取 foo 的 inode
* 透過 foo 的 inode 讀取 foo 的 data
* 透過 foo 的 data 讀取 bar 的 inode
* 透過 bar 的 inode 找到欲開啟的檔案
* 讀檔的部分
* 讀取 bar 的 inode
* 透過 bar 的 inode 讀取 bar 中的 data
* 更新 bar 的 inode 的資訊 (access time)

### 創建檔案與寫檔
* 創建檔案的部分 (在 foo 目錄下創建一個名為 bar 的檔案)
* 先開啟 foo 的 data
* 讀取 inode bitmap，並分配檔案所需的空間
* 在 foo 的 data 中寫入新建檔案的相關資訊
* 對 bar 的 inode 進行讀寫 (寫入 create time 等資訊)

* 寫入檔案的部分
* 從 data bitmap 中找到一段可用的空間，並配置出去
* 寫入真正的資料到 bar 中
* 更新 bar 的 inode 資訊
## FFS
考慮到硬碟架構，將相關的檔案放在一起

原則:
1. 將不同的 directory放在不同的 group 中
2. 將相同目錄下的檔案放在同一個 group 中
* 但對於大檔案，將其分割後，放置於不同 group 中 (因為大檔案可能會占用太多 group 中的空間，導致其他同目錄下的檔案放不進去)
* 決定分割後一個區塊大小時，會希望 positioning time 跟 transfer time 消耗的時間相同
* 所求為 average positioning time * Transfer rate

ex:

### 其他優化
Sub-block: 將 block 進一步細分，以解決 internal fragmentation
parameterization: block 排放的方式設定一點小 delay，以配合操作 FFS 的耗時

## Crash recovry
### FSCK (file system checker)
* 概念: 查看 file system 的狀態，嘗試找到不合理之處，並修復成合理的狀態

缺點: 仍無法完整復原寫入的資料

### Data Journaling (Write-Ahead Logging)
* 概念: 透過維護額外的一個空間(journal area)，來記錄寫入的資訊(含 data 、metadata)，以在系統發生非預期的情況時(ex: 斷電)，能夠追蹤發生了甚麼事

* 
* TxB: 某筆 transaction 的開頭
* 中間的白色區域: 某筆 transaction 的 data 、metadata
* TxE: 某筆 transaction 的結尾，透過 commit 寫入

* 詳細步驟:
* 同時開始寫入資料到 TxB、Journal contents 中
* 上面兩者全部完成後，進行 Journal commit (寫入 TxE)
* 將 matadata、 data 寫入至 file system 中 (checkpoints)
* 刪除 Journal 中的該筆 transaction

* 復原資料的方法: crash後，replay 仍留存在 Journal 的那些 transaction (若資料確定寫入硬碟的話，便不會存在於 Journal 中)

### Metadata Journaling
* Journaling 會將完整資料寫進 Journal 中，效率過低
* Metadata Journaling 只寫入關於檔案的 metadata，以加速寫入
* 詳細步驟:
* 同時開始寫入資料到 TxB、Journal contents、Data
* 上面三者全部完成後，進行 Journal commit (寫入 TxE)
* 將真正的 Metadata 寫進硬碟中 (checkpoints)
* 刪除 Journal 中的該筆 transaction

Tricky case:
1. 某個 transaction 刪除某個 directory (視為 matadata)
2. 下一個 transaction 建立某個 directory並寫下一些檔案內容，使用了同一個空間
3. 這兩筆 transaction checkpoints 前，發生斷電
4. 斷電恢復後，replay 這兩筆 transaction
5. 第二筆 transaction 寫入的檔案內容被刪除!

解決方法:
1. 在確定 checkpoints 前，不使用該空間
2. 在刪除硬碟中的檔案時，順便 revoke(撤銷) journal 中對應的 transaction