磁碟管理(Disk Management)

[ Free space 管理 ]

1. bit vector
用一組 bits 來表示 block 已經被使用，或者為 free 的狀態。
優點：簡單、容易找到連續的 free space (就看有多少連續的0)
缺點：無法用來表示大型 disk

2. link list
在 disk 的各 free block 加入 link 指向下一個 free block
優點：增加、刪除 block 容易
缺點：效益不佳，在 search 時需要從頭開始找起。

3. combination (index)

取某個 block 記錄其他可用 block 的編號。

[ 空間配置方式 ]

1. contiguous allocation

OS 要在磁碟中找到 >= n 個連續的 free block 才能配置。
優點：支援 sequential access、random access、有效降低 seek time
缺點：會有外部碎裂、檔案大小無法任意增刪，建檔時要事先宣告大小。

2. link allocation

採用非連續配置，只要 OS 可以找到 >= n 個可用的 free block 就行。
這些 block 之間是以 link 方式相連。
優點：不會有外部碎裂、檔案可以任增刪空間、建檔時不用事先宣告大小。
缺點：不支援 random access、萬一 link 斷裂，則資料遺失。

FAT
是 Link Allocation 的變形，原本在各 block 間的 link 直接用表格儲存。
若在磁碟中有 n 個blocks 則 FAT 會有 n 個項目。

3. index allocation

如果 program 需要 n 個 blocks ，那麼就要去找出至少 n+1 個 blocks
因為其中 1 個 block 要拿來當 index block 使用。
優點：不會有外部碎裂，支援 random access，檔案大小可任意增刪。
缺點：index block 佔用額外空間，而且其大小設計亦是難題。

當 index block 太小，不足以容納檔案全部的 data block 時，解法有
(a) 利用 link 將多個 index blocks 串起來
(b) 使用 multilevel index 方法
(c) 混合法：像是 unix 的 I-node ，使用
- 12個 direct block pointer 指向 data block
- 1 個 single indirect block pointer 指向 single level index
- 1 個 double indirect block pointer 指向 two level index
- 1 個 triple indirect block pointer 指向 3-level index


[ Disk Access Time ]

磁碟存取時間由三個時間加總：seek time + latency time + transfer time
seek time: 將讀寫頭移到目標 track 上面 (最耗時)
latency time: 欲存取的 sector 轉到讀寫頭下方
transfer time: 資料在 disk 及 mem 傳輸需要的時間

[ 磁碟排班 ]

1. FCFS - simple, fair, 效率不佳
2. SSTF - shortest seek time first , 離目前讀寫頭最近的 track 先服務。
3. SCAN - 也稱為 elevator ，磁碟的讀寫頭會碰到盡頭，才折返。
4. LOOK - 不會碰到磁碟邊界