# Ch7 Disk
###### tags:`計算機組織`

## Disk introduction
### 原理
- disk 是 nonvolatile
- 讀寫頭基本上就是線圈，disk surface 會有磁場，而讀寫頭經過就會有感應電流。
- zone bit recording (ZBR)，磁碟的外圈可以 store 更多的資料量。
### componenet

- 由一堆 platter 組成，platter 通常是 double sided 可存 Data
- 每一個同心圓就是 track
- 扇形的區域就是 sector or disk block，而 sector 被 gap 分開。
- Cylinder 是上下所有 tracker 的集合


$10\times2\times2048\times16KB=$

### 存取步驟
- 將讀寫頭移到正確的 track。
- 將讀寫頭移動到正確的 sector，倒楣需要轉一整圈。
- 開始 transfer data。


electronics 裡面也有 processor 和 memory

## Capacity

- Recording density (bits/in): number of bits that can be squeezed into a 1 inch segment of a track.
- Track density (tracks/in): number of tracks that can be squeezed into a 1 inch radial segment.
- Areal density (bits/$\text{in}^2$): product of recording and track density.

## Average disk access time
- formula = seek time + rotational delay + data transfer + controller overhead + waiting time
- seek time : 讀寫頭移到正確 track 的時間
- 

- rotational delay(Latency Time or Rotation Time) :
- 在 track 內找到正確 sector 的時間
- $T_{\text{avg rotation}}$ = 1/2(因為平均找半圈) x 1/RPMs x 60 sec/1 min
- 轉速 rpm = rotations per minutes
- rpm / 60 second = 每秒鐘轉幾圈
- 倒數是轉一圈花的秒數
- 

- data transfer time (transfer time): $\frac{資料量}{\text{data transfer rate}}$
- data transfer rate = track 的資料量 $\times$ 每秒的轉幾圈(轉速 rotaional rate)
- 

- controller overhead : 把邏輯命令 $\rightarrow$ physical instruction
- waiting time : 等待其他 program 的時間。(通常題目都假設只有你在用，所以沒有 waiting time)
- Positioning Time = Seek Time + Rotational Latency
- 通常是 seek > transfer > rotate

## problem
- $\frac{15000}{60}= 250$
- 4 + 0.2 + $\frac{0.5}{250} + \frac{0.5K}{100M} = 6.2$

- $512\times 32\times 3600 = 58.9824$ MB/sec
- 12ms + $\frac{1}{60}$ + 1 ms = 29.67 ms
- 21.33 - 12 - 1 = 8.33
- $\frac{512\space bytes\times8}{R\times 512 \space bytes \times 32}+ \frac{0.5}{R} = 8.33$ ms
- R = 90.036

- disk Access Time = 12ms + $\frac{1}{2\times 60}$ + $\frac{512}{2^{20}\times 3.5}$ + 5.5= 25.97
- disk Access Time = 12ms + $\frac{1}{2\times 60}$ + $\frac{8\times 2^{10}}{2^{20}\times 3.5}$ + 5.5= 28.07
- 同 b

- 讀跟寫的位置一樣表示不需要 seek time
- 讀跟寫的位置不一樣 read time = write time

A:
- 70 RPS
- transfer rate = 20 MB/sec
- disk Access Time = 8 ms + $\frac{1}{2\times70}$+$\frac{4\times 2^{10}}{20 \times 2^{20}}$ + 2 ms = 14.17 ms
- 20 $\times 10^6$ $\div$ (400 $\times 10^6$ ) = 50 ms
- 2 $\times$ 14.17 + 50 = 78.34 ms
- 1000 ms / 78.34 = 12.76 次

## Review
- data transfer rate = ration rate $\times$ 1 tracker 的資料量(sector size $\times$ sectors per track)
- data transfer time = 資料量 $\div$ data transfer rate
- rotational delay = $\frac{1}{2}\div$rotation rate 轉半圈需要多少時間。
- 1 MB = $2^{20}$ B

## Nonvolatile memory devices

1. NVM：contorller + falsh NAND 晶片：沒有讀寫壁的移動，沒有 seek time 或是 rotational latency，電力消耗甚至更少。
2. flash-memory-based NVM：SSD、USB drive、DRAM stick
3. 容量較少，且比較貴。

## Disk Free Space Management(可用空間的管理)

1. bit vector(or bit map)
2. link list
3. grouping (2的變形)
4. counting (2的變形)

### bit vector(bit map) 位元向量/地圖

每一個 block 皆用 1 個 bit 表示 free 與否：
- 0 表 Free disk
- 1 表 allocated disk

有 n 個 blocks，則 bit vectors 大小 = n bits


優點：
1. 簡單 implement
2. 容易找到連續的 free blocks(即找連續的 0)

缺點：
1. 小型 disk 適用，但大型 disk 不適用，因為 blocks 數目龐大，造成 bit vector size 很大，很佔 momory 的 space，甚至被迫至於 disk 中。

### linked list

OS 直接在 Disk 上，將這些 Free Blocks 以 Linking 的方發串接，進行
管理


優點：
1. 大型 Disk 適用(只需要紀錄 free block 的 pointer)
2. 插入/刪除 Free Block 方便

缺點：
1. 不夠迅速來找大量可用 block，因為在 disk 上讀取耗 link information 耗時(用 Grouping 法改善)
2. 不容易找到連續的 Free Blocks。(用 Couting 法改善)

### Grouping 法
是 Linked List 法之變型，在 Free Block 內除了記錄 Link Information 之外，另額外記錄其他 Free blocks 之 Number(Address)
優點：可快速找到大量的 Freee Blocks

### Counting 法
利用連續性配置及歸還之特性，改變 Linked List 記錄方式，Free Block 內除了記錄 Linking Information 以外，另外記錄在此 Free Block 之後的連續 Free blocks 之個數。


優點：適用於連續性配置，方便找到連續的 Free Blocks，且如果連續的 Free Blocks 很多，Linked List 長度也可大幅縮短。

## File Allocation Methods
1. contiguous allocation
2. linked allocation $\rightarrow$ FAT Method
3. Index allocation e.g. UNIX 的 I-Node Structure

### contiguous allocation
若 File 大小 = n 個 Blocks，則 OS 必須在 Disk 中找到 n 個連續的 Free Blocks，才能配置給它。此外，OS 在 Physical Directory 會記錄下列資訊：



優點：
1. 平均 Seek Time 較小，因為連續的 Blocks 大都落在同一條 Track 或鄰近 Tracks 上
2. 可支持 Random(direct) Access (任意存取 $i^{th}$ Block of the file)及 Sequential Access，即 $i^{th}$ Block = Start Number + i - 1
3. 可靠度較高(相對於 Linked Allocation)
4. 循序存取速度較快(相對於 Linked Allocation)
5. 容易實作

缺點：
1. 會有 external fragmentation。(Disk 用 Repack (磁碟重組)方式來解決，類似 Memory 的 compaction，兩者差別)
- fragmentation compation penalty 大
- 位置在 memory 或 Disk
2. 所有配置方法皆會有 internal fragmentation。
- 例：block size = 10 KB
- File = 44 KB
- 5 個 block
- interanl fragmentation = $5\times 10 -44 = 6KB$
3. File 大小不易動態擴充
4. 建檔之前需事先宣告大小

OS 現在使用 modified contiguous of space schema：空間不夠加入 extent
紀錄欄位新加入 link to the first block of the next extent

### Linked Allocation
若 File 大小為 n 個 Blocks，則 OS 只需在 Disk 中找到 n 個 Free Blocks(不需連續)即可配置，且 Allocated Blocks 之間以 Link 方式串連
physical directory的記錄：
1. File Name/Number (檔案識別)
2. Start Block Pointer (指向第一個區塊)
3. End Block Pointer (指向最後一個區塊)

| File Name/Number | Start Block Pointer | End Block Pointer |
| -------- | -------- | -------- |
| 2 | 3 | 4 |


優缺點與 Contiguous 相反

優點：
1. 沒有外部碎裂
2. File 大小容易動態擴充
3. 建立 File 之前，無需事先宣告大小

缺點
1. Seek Time 較長(因為不連續的 Blocks 可能散落在許多不同 Track 上)
2. 不支援 Random Access(direct access)
3. 可靠度差(因為萬一 Link 斷裂，Data Lost)
4. 需要連結空間(The space required for the pointer)
- 如果指標需要 4 out of a 512 byte block，則有 0.78 比例用來存放指標
- 解決方法 collect blocks into multiples, called cluster：原本是「Block 連接 Block」。使用了 Cluster 後，變成了「Cluster 連接 Cluster」。 這意味著：
- 減少指標數量：不需要每個 Block 都有指標，只需要每個 Cluster 有一個指標。
- 提升讀取速度：讀取一個 Cluster 就能連續獲得多個 Blocks 的資料，減少了磁頭移動 (Seek) 的頻率。
6. 循序存取速度慢(因為要在 Disk 上讀取 Link 資訊，才知道下一個 Block為何)

### FAT(File Allocation Table)方法

是 Linked Allocation 之變型，主要差異：Allocated Blocks 之間的 Linking Information 存於 OS Memory Area 中的一個表格，叫 FAT，而非存於 Disk 中


- 優點：想要加速 Random Access in the Linked Allocation，因為可以在 Memory 中的 FAT 迅速找到第 $i^{th}$ Block之 Number，然後再到 Disk Access $i^{th}$ Block 即可，不用在 Disk 中 traverse Linking Information
- MS-DOS 率先使用
- 實體目錄：紀錄 the block number of the first block of the file
- 需要 cached in memory

### Index Allocation(Linux)

若 File 大小為 n 個 Blocks，則 OS 除了配置 n 個 Blocks(無需連續)，另
需額外配置 Index Block，儲存所有 Data Blocks 之 Number(address)


優點：
1. 無 external fragmentation
2. 支援 Random Access 及 Sequential Access
3. File 大小容易動態擴充
4. 建立 File 之前，無需事先宣告大小

缺點：
1. Index Block 佔用額外空間
2. Linking Space 浪費(overhead)比Linked Allocation 大許多
3. 若 File 很大，則單一個 Index Block 可能無法容納(保存) File 的所有 Data Block Number，此問題需被解決

#### 解決單一 Index Block 不夠存放所有 Data Blocks Number 之問題

1. 法一：使用多個 Index Blocks，且彼此以 Link 方式串聯，例：Assume 一個 Index Block 可存 5 個 Number)，
- 不適那麼純粹的支援 direct access
- 缺點在於 Random Access of $i^{th}$ Block 之平均 IO 次數大幅增加。
- 
2. 法二：使用 multilevel Index Structure
- 
- 優點：
- Radom Access of $i^{th}$ Block 之 IO 次數是固定值 2 level 就需要 3 次 IO。(level 1 index block + level 2 index block + file block)
- 適用於大型檔案
- 缺點：對小型檔案及不適合，因為 Index Blocks 太佔空間，甚至可能多於 Data Blocks 數目。

3. 法三：混合法(UNIX 的 I-Node 結構)
- 
- 優點：小型、大型 file 皆適合

#### 例題


### 小結


## Disk Scheduling Algorithm

1. FCFS
2. SSTF
3. SCAN
4. C-SCAN(C:circular)
5. Look
6. C-Look

Disk Scheduling 法則：既無最佳也無最差。

### FCFS(First Come First Service)

1. 最早到達的 Track Request 優先服務
2. 列如 ： Disk 有 200 軌，編號 0~199，Head 目前停在第53軌，剛剛服務完第40軌，現在 Disk Queue 中有下列 Track Request 依序為：98,183,37,122,14,124,65,67，求 Tracks 移動總數？
3. 分析
- 公平(No Starvation)
- 排班效果不是很好，Track 移動數較多，seek time 較長(SSD 多採用此法)

### SSTF(Shortest Seek Time Track First)

1. 距離 Head 目前位置最近的 Track Request，優先服務
2. 
3. 分析
- 不公平，可能有 starvation
- 排班效果不錯，Track 移動較少 seek time 小，但並非是 Optimal

### SCAN 法則
1. Head 來回雙向移動掃瞄，遇有 Track Request，即行服務，Head 遇到 Track 開端或盡頭時，才折返提供服務
2. 例子：假設磁碟有 200 個柱面（0–199），磁碟臂目前在柱面 50，請求的柱面如下：請求序列：95, 180, 34, 119, 11, 123, 62, 64，起始位置：50，方向向外（往 199）
1. 先處理：62 → 64 → 95 → 119 → 123 → 180（往外）
2. 到達最外圈（199），方向反轉
3. 回頭處理：34 → 11（往內）

3. 分析：
1. 排班效能可接受，適用於大量負載之情況，因為 Track Request 有較均勻一致之等待時間(Look 也是)
2. 在某些時刻，對某些，似乎不盡公平例：(用 C-Scan 改善)
3. Head 需要遇到 Track 開端或盡頭才折返，此舉耗費不必要的 Seek Time(用 look 解決)

### C-SCAN

1. 是 SCAN 變型；差別只是提供單向服務，折返回程不提供服務

### Look

是 SCAN 之變形；差別：Head 服務完該方向之最後一個 Track Request 後，即可折返提供回程服務

### C-Look

look 之變形；差別：只提供單向服務


### NVM(non-volatile memory) scheduling

沒有移動的 disk heads，通常使用 simple FCFS policy

- NVM device 的行為模式，在服務 reads 動作時間是 uniform，但是 write service time is not uniform.(因為 flash memory 天生特性)
- 有些 SSD 依據這個特性，只 merge only adjacent write reuqests，但是 read 請求的服務是 FCFS order
- 例子：Linux NOOP scheduler uses an FCFS policy，做一些修改，將 adjacent requests 合併

### 各教科書的名詞比較


## Formatting
1. physical format(low-level Format)
1. 工廠生產 Disk System 時執行
2. 主要劃分出 Disk Controller 可以存取的 sector
3. 偵測有無 BAD sectors
2. logical format：user 在使用 Disk 之前必須做兩件事
- partition：切割分區，即 logical drive(e.g.C,D,E 磁碟機) separate device
- logical format：OS製作(寫入) File Management System 所需之資料結構
- Free Space 管理：(ex:Bit Vector)
- allocated space (FAT, I-Node)
- 空的 physical directory
- 有時候，為了增加效能，多數的 file systems 會將依些 blocks 聚集起來形成一個較大的 chunks, 通常較做 clusters
3. “Disk formatted by a file system which the logical block size is 1024 bytes
- 檔案系統把磁碟切成一塊一塊的「邏輯區塊（logical block）」。
- 每一塊是 1024 bytes
- 這些區塊是檔案配置（allocation）的最小單位。
- 因此，即使 file 只有 1 bytes，系統也會配置 1024 bytes

## RAW-IO

## Boostrap Loader

## BAD Sector 之處理方式

## SWAP Space Management

## 提升 Disk Data Access Performance 之技術
[RAID](https://hackmd.io/@k_6HWCPmRYypmdRKmNab6g/S1eyUl0kgg)