2月 16, 2011

磁碟管理(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 - 不會碰到磁碟邊界

1 則留言:

  1. BetSoft secures new market position with - SmFS.info
    The Malta-based gambling brand is leading the way in online gambling 카지노사이트 with an innovative brand, Betsoft's first mobile 바카라사이트 platform, BetSoft,

    回覆刪除