RAID 5 示意圖。
這章比較重要的是各個 RAID 的設計，其他看過去有概念就可以了：）
2015.1.15 初版
2017.9.16 二版
一、Disk 簡介
Disk 結構：
- 磁區 (sector)
- 磁軌 (track)
- 磁柱 (cylinder) : 不同面之相同 tracks 形成之集合
- 讀寫頭 (Read/Write head)
描述磁碟幾何狀況 (C, H, S)
- C (cylinder) : 幾圈
- H (head) : 幾面(一片有兩面、最上最下面不算。)
- S (sector) : 一圈幾格
Disk access time 由下列 3 個時間加總：
- Seek time：將 Read/Write head 移到指定 track 上方所花的時間；三者中以 seek time 耗時最多，與 head 移動距離成正比，因為是機械動作。
- Latency (rotation) time：將欲存取的 sector 轉到 Read/Write head 下方所花的時間。
- Transfer time：資料在 disk 及 memory 之間的傳輸時間。
[例題1] Disk Capacity
若某硬碟有 10 個 disks，正反面皆可存資料但最上、最下一面不存。每一個表面上有 1024 條 tracks，每個 track 有 256 個 sectors。一個 sector 可存 512 byte 資料，則磁碟的容量為何？
Ans : (10×2 - 2) × 1024 × 256 × 512 Bytes = 18 × 2^7 MB
二、Disk Scheduling Algorithm
1. FCFS 演算法 (first-come, first-serve)：先到達的請求優先服務。
- 簡單、公平、效率不佳。
2. SSTF 演算法 (short-seek time first) ：距離目前 R/W Head 最近的 track 優先服務。
- 並非是最佳的 (平均移動的 track 總數量無法保証為最少)。
- 不公平，可能會發生 starvation。
3. SCAN 演算法：讀寫頭來回不停地掃描，若有 track 請求則服務。
- 提供雙向服務
- 遇到起頭與尾端的 track 才折返。
- 因為要碰到起頭或尾端才會折返，會有一些不必要的磁軌移動產生相對不公平，但不會發生 starvation。
4. C-SCAN 演算法：讀寫頭來回不停地掃描，若有 track 請求則服務。
- 提供單向服務
- 遇到 track 起頭與尾端才折返。
5. LOOK 演算法、C-LOOK 演算法：與 SCAN 極相似。唯一不同在於處理完某方向的最後一個 track 請求即折返，不需遇到 track 起頭與尾端才折返。
一些 disk scheduling algorithm 常識：
- Either SSTF or LOOK is a reasonable choice for the default algorithm.
- Disk scheduling problem is inherently NP-hard. There is no optimal solution! Heuristics may be taken.
- Modern disks impose nearly the same overheads on seek and rotation.
三、Disk Management
Low-level formatting (physical formatting)：
- Dividing a disk into sectors that the disk controller can read and write.
- Remapping bad tracks
- Zoned-bit encoding
- 原廠或完整格式化時使用 (防老化)。
Logical formatting (making a file system)：
- To use a disk to hold files, the operating system still needs to record its own data structures on the disk.
- Partition the disk into one or more groups of cylinders.
- 快速格式化，通常使用者格式化為此類，只寫掉檔案系統要用的表格。
Boot block initializes system：
- The bootstrap is stored in ROM.
- Bootstrap loader program.
- 傳統：bootstrap loader (ROM)，找 OS object code 載入 memory。
- 現在：simple bootstrap (ROM) => 完整 bootstrap (Disk) => OS object code (Disk) => 開機完成。
- 完整的 bootstrap loader 是存放在 Disk 中固定位置，稱為 boot blocks。
- 擁有 boot blocks 之 disk 稱為 boot disk 或 system disk。
四、RAID
獨立磁碟冗餘陣列 (RAID, Redundant Array of Independent Disks) 簡稱磁碟陣列，由多顆磁碟機組成一個陣列，將資料以分段 (striping) 的方式同時對不同的磁碟做讀寫的動作。 使用 RAID 有以下目的：
- 提升可靠度：provides reliability via redundancy.
- 增進效能：improving performance by means of parallelism.
RAID 把多個硬碟組合成為一個邏輯磁區，因此 OS 只會把它當作一個硬碟。RAID Level 高低不完全代表系統效能或可靠度的高低，端視管理員的需求。
將資料切割存放到多部硬碟中且不會重複存放。
- 優點：效能改善，可進行平行讀寫，適用於具有高效能需求的系統。理論上，硬碟越多效能就等於[單一硬碟效能]×[硬碟數]。事實上受限於匯流排I/O瓶頸及其它硬體因素的影響，RAID 效能會隨邊際遞減。
- 缺點：完全沒有容錯能力
必須由 2 個以上的硬碟所組成，有資料寫入時，直接同時寫入兩個硬碟，故內部資料是完全一樣的。
- 優點：系統可靠度很高，極佳的資料安全性，實作容易。
- 缺點：效率最差，且需花費兩倍的成本。
RAID 0+1：Mirror + Striping
結合了 RAID 0 與 RAID 1 兩種模式。至少要 4 顆以上的磁碟，且硬碟總數需為偶數。
- 優點：擁有 RAID 1 容錯力，以及 RAID 0 整體讀寫速度。
- 缺點：一次最少要用上 4 顆硬碟，且也要浪費一半的總容量，成本很高。
RAID 2：Hamming Code
加入了錯誤修正碼 (ECC, Error Correction Code)，不同的位元儲存在不同的硬碟中，具錯誤檢查與更正能力，當一部硬碟壞掉時，可由其它硬碟的內容來更正。例如：4 個 Bits 的資料需要 7 部硬碟來儲存，4 部存資料，3 部存Hamming Code。
RAID 3：Parallel with Parity
多利用一顆磁碟儲存同位元資訊達到容錯功能。當硬碟有問題，可由同位元檢測得知。所需的硬碟數較 RAID 2 節省。不是個好方法，因為全部的 disk 都不斷被寫 (Bit－interleaving)，效能低落。
[感覺] 同位元 Ap = A1 XOR A2 XOR A3，同位元 (parity) 是效能瓶頸所在。
RAID 4：Parallel with Parity (block)
跟 RAID 3 相同，不過其支援的資料交插是以 block 為單位計算的。P-disk 不斷被寫，效能瓶頸。
RAID 5：Striping with Rotating Parity
RAID 5 是一種儲存效能、資料安全和儲存成本兼顧的儲存解決方案，有較多的商業應用。與 RAID 4 雷同，但是 RAID 5 把同位元分散依序儲存於陣列中的每顆磁碟內，改善了 P-disk 不斷被寫的效能瓶頸。
RAID 6：Read Solomon Code
RAID 6 增加第 2 個獨立的奇偶校驗資訊塊。容許 2 個硬碟同時損壞，至少必須具備 4 或 4 個以上硬碟才能生效。RAID 6 在硬體磁碟陣列卡的功能中，也是最常見的磁碟陣列等級。
[例題] RAID-5 Reliability
Let the probability of 1-year up time of a disk be p
The probability of 1-year up time of a RAID-0 having 4 disks :
- p4 (~0.96 if p=0.99)
The probability of 1-year up time of a RAID-5 having 5 disks :
- p5+(5,1)(1-p)*p4 (~0.999 if p=0.99)
References
wiki - RAID
https://zh.wikipedia.org/wiki/RAID
my hebrew college - Raid and Server Technology Information
http://www.myhebrewcollege.com/raid-server-technology-information/
Abraham Silberschatz, Peter B. Galvin, Greg Gagne - Operating System Concepts 8th Edition
https://www.amazon.com/Operating-System-Concepts-Abraham-Silberschatz/dp/0470128720
聯合大學陳士杰教授課程教材
http://web.nuu.edu.tw/~sjchen/
洪逸 - 作業系統金寶典
http://m.sanmin.com.tw/product/index/001601057
發表文章
