Operating Systems - Massive Storage System

發表於2025-09-17|更新於2026-09-17|作業系統

|總字數:6.3k|閱讀時間:26分鐘|瀏覽量:

Massive Storage System

這章主要探討：

Hard Disk Structure
Disk Access Time
Free-Space Management
File Allocation Methods
Disk Scheduling
Formatting
Bootstrap Loader
Bad Sectors
Swap Space Management
RAID
File Directory Structure
File Access Control
Consistency Semantics
Storage Attachment

Hard Disk Drive

HDD 基本結構

一顆 HDD 由多個 disk platter 組成。

每片 platter 通常有兩個可以儲存資料的：

Surface

每個 surface 又會分成很多同心圓：

Track

每個 track 再切成：

Sector

而不同 platter 上，相同位置的 tracks 集合稱為：

Cylinder

關係

Surface → Track → Sector

而：

不同 Surface 上相同半徑的 Track
→ 組成一個 Cylinder

HDD Structure

名稱	意義
Platter	磁碟片
Surface	磁碟片的一面
Track	Surface 上的同心圓磁軌
Sector	Track 再切割出的區域
Cylinder	不同 Surface 上相同位置 Track 的集合
Head	負責讀寫資料
Arm	移動 Head
Spindle	帶動 Platter 旋轉

Sector

每個 sector 為固定大小，是 HDD 傳輸資料的基本區域。

傳統：

512 Bytes / Sector

現在常見：

4 KB / Sector

RPM

RPM（Rotations Per Minute）

表示：

磁碟每分鐘旋轉幾圈

常見：

5,400 RPM
7,200 RPM
10,000 RPM
15,000 RPM

RPM 越高，通常等待 sector 轉到 head 下方的時間越短。

Disk Access Time(計算)

Disk Access Time 主要由三部分組成：

$$
Disk\ Access\ Time=Seek\ Time+Rotational\ Latency+Transfer\ Time
$$

時間	意義
Seek Time	Head 移動到目標 Track / Cylinder
Rotational Latency	等待目標 Sector 旋轉到 Head 下方
Transfer Time	HDD 與 Memory 傳輸資料

通常：

Seek Time 佔最大的比例

Seek Time

將讀寫 Head 移動到欲存取的 Track / Cylinder所需要的時間。

Rotational Latency

Head 已經到達正確 Track 後，還必須等：

目標 Sector 旋轉到 Head 下方。

平均旋轉延遲通常取：

$$
Average\ Latency

\frac{1}{2}
\times
Rotation\ Time
$$

Transfer Time

資料真正從：

HDD ↔ Main Memory

傳輸的時間。

Transfer Time 與：

Transfer Rate 成反比。

Disk Access Time 考題

假設：

10 disks
每個 disk 有 2 surfaces
每個 surface 有 4096 tracks
每個 track 有 2048 sectors
每 sector = 8 KB
Rotation Speed = 6000 RPM
Average Seek Time = 10 ms

① Disk Capacity

$$
10
\times
2
\times
4096
\times
2048
\times
8KB
$$

得到：

1280 GB

② Average Rotational Latency

6000 RPM：

$$
\frac{6000}{60}

100\ rotations/sec
$$

所以轉一圈：

$$
\frac{1}{100}

0.01s

10ms
$$

平均只需要等半圈：

$$
Average\ Latency

\frac{10}{2}

5ms
$$

③ Read File 所需時間

基本觀念：

$$
Read\ Time

Seek\ Time
+
Rotational\ Latency
+
Transfer\ Time
$$

例如讀取 4 MB：

Seek Time = 10 ms
Rotational Latency = 5 ms
再加上 4 MB 的 Transfer Time。

你照片中的例題最後得到約：

15.125 ms

Non-Volatile Memory Devices

NVM：

Non-Volatile Memory

即使斷電：

資料仍然可以保存。

Flash-memory-based NVM 常用在：

SSD
USB Drive
Flash Drive

通常由：

Controller
NAND Flash

組成。

NVM vs HDD

NVM / SSD	HDD
沒有移動磁頭	有機械式磁頭
沒有 Seek Time	有 Seek Time
沒有 Rotational Latency	有 Rotational Latency
較快	較慢
較可靠	機械元件可能損壞
較省電	較耗電
較昂貴	較便宜
容量通常較小	大容量較容易

Free-Space Management(少考)

OS 必須知道 Disk 中：

哪些 Blocks 是 Free
哪些 Blocks 已經 Allocated

Free-Space Management 主要有四種：

方法
Bit Vector / Bitmap
Linked List
Grouping
Counting

Free-Space Management 的基本單位是 Block。

Bit Vector / Bitmap

Disk 中的每一個 Block 使用：

1 bit

表示 Free / Allocated。

例如：

1 = Free
0 = Allocated

也可以反過來定義。

優點

結構簡單
容易找第一個 Free Block
容易找：

N 個連續 Free Blocks

因此對需要連續空間的配置方式相當方便。

缺點

Bitmap 最好：

完整保存在 Main Memory

否則尋找 Free Block 時效率會降低。

因此：

對小型 Disk System 比較適合。

Linked List — Free Space

將所有：

Free Blocks

使用 Linked List 串起來。

只需要保存：

Pointer → 第一個 Free Block

優點

結構簡單，而且適合：

大型 Disk System。

缺點

如果需要大量 Free Blocks：

必須 Traverse Linked List。

因此會產生大量：

Disk I/O

所以不容易快速找到大量 Free Blocks。

尤其不利於：

Contiguous Allocation。

Grouping

Grouping 是 Free List 的變形。

假設一個 Free Block 可以存：

N 個 Block Addresses

則：

前 N-1 個：記錄其他 Free Blocks
最後一個：指向下一個包含 N 個 Free Block Addresses 的 Block

因此：

一次可以取得很多 Free Blocks。

Grouping 優點

解決普通 Linked List：

無法快速取得大量 Free Blocks

的問題。

Counting

如果 Free Blocks 經常是：

一整段連續出現

則可以記錄：

Starting Block + Count

例如：

Block 5 開始，後面共有 3 個連續 Free Blocks

可記：

Start	Count
5	3

而不需要：

5 → 6 → 7

逐個紀錄。

Counting 優點

如果連續 Free Blocks 很多：

可以大幅縮短 Free List。

File Allocation Methods (三顆星)

OS 配置 File Blocks 的方式主要分為：

Contiguous Allocation
Linked Allocation
Indexed Allocation

另外：

Linked Allocation 的變形：FAT(File Allocation Table)

Indexed Allocation 的著名方法：UNIX i-Node

Contiguous Allocation

如果 File 大小為：

N Blocks

OS 必須找到：

N 個連續的 Free Blocks

配置給 File。

Directory 要記什麼？

Physical Directory 只需要記：

Starting Block
Length

例如：

File	Start Block	Length
File1	10	3

代表：

File1 = Block 10、11、12

找第 i 個 Block

如果：

i < Length

則：

$$
Block\ Number

Start\ Block+i
$$

所以 Direct Access 非常容易。

Contiguous Allocation 優點

1. Seek Time 較短

因為連續 Blocks 通常位於：

相同或相鄰 Track。

2. Sequential Access 很快

直接：

Block 10 → 11 → 12 → 13

3. Random / Direct Access 很快

知道：

Start Block + Offset

即可。

4. 容易實作

Contiguous Allocation 缺點

1. 不容易找到連續的 Free Blocks

即使 Disk 還有很多 Free Blocks：

也可能散落在不同地方。

2. External Fragmentation

可能變成：

Free、Used、Free、Used、Free……

雖然 Free Space 總量夠：

卻找不到夠大的連續區域。

3. File 不容易成長

建立 File 前必須先預估：

File Size。

如果 File 後來變大：

後面可能已經被其他 File 使用。

Modified Contiguous Allocation

現代 OS 可以使用：

Extent

一開始：

分配一個 Contiguous Chunk。

不夠時：

再分配另外一個 Contiguous Chunk。

Directory 需要紀錄：

Starting Block
Block Count
Link to Next Extent

目的：

改善 File 不容易擴充的問題。

Linked Allocation

如果 File 需要：

N Blocks

只需要在 Disk 找：

任意 N 個 Free Blocks

不需要連續。

Blocks 之間利用：

Pointer

串成 Linked List。

例如：

3 → 5 → 14 → EOF

Linked Allocation 優點

1. No External Fragmentation

Blocks 不需要連續。

2. File 很容易成長

只要還有 Free Block：

就能繼續加入。

3. 建立 File 前不用先知道大小

Linked Allocation 缺點

1. Direct Access 效率差

假設要找：

File 的第 i 個 Block

必須：

從第一個 Block 開始一路走 Pointer。

所以：

Linked Allocation 適合 Sequential Access
不適合 Direct Access。

2. Pointer Overhead

每個 Data Block 都要額外存：

Pointer。

例如：

Block = 512 Bytes
Pointer = 4 Bytes

則：

$$
\frac{4}{512}
\approx
0.78%
$$

空間拿去存 Pointer。

解法之一：

將多個 Blocks 組成 Cluster

再以 Cluster 為配置單位。

3. Lower Reliability

如果中間某個 Pointer：

損壞 / Lost

後面的 Blocks 就可能：

無法找到。

4. Seek Time 較長

因為 Blocks：

可能分散在不同 Tracks。

FAT — File Allocation Table

FAT 是：

Linked Allocation 的變形。

全名：

File Allocation Table

核心概念

假設 Disk 有：

N Blocks

FAT 就有：

N 個 Entries。

每一個 Entry 對應一個 Block。

Entry 裡存：

Next Block Number

例如：

Block	FAT Entry
3	5
5	14
14	EOF

代表：

File = 3 → 5 → 14 → EOF

Directory 只需要記：

First Block = 3

特殊值

最後一個 Block：

EOF

Free Block：

0

FAT 的優點

相較普通 Linked Allocation：

Random Access 效率較好。

因為 Pointer：

不存在每個 Disk Data Block 裡

而集中在：

FAT Table。

FAT 的重要條件

FAT 必須：

Cached in Memory

否則如果每查一個 FAT Entry 都要存取 Disk：

會產生大量 Disk Head Seeks。

Indexed Allocation

如果 File 大小為：

N Blocks

除了配置 N 個 Data Blocks 外：

還會再配置一個 Index Block

Index Block 用來記錄：

File 各 Data Blocks 的 Block Number / Address。

Entry	Data Block
0	3
1	7
2	15

Indexed Allocation 優點

支援 Direct Access
支援 Sequential Access
No External Fragmentation
File 容易擴充
建立 File 前不需要先知道大小

Indexed Allocation 缺點

1. Index Block 空間浪費

例如：

Index Block 可以存 100 個 Block Numbers

但 File 只有：

5 Blocks

那剩下：

95 Entries = NULL

仍然浪費 Index Block 空間。

2. 大型 File

如果 File 太大：

一個 Index Block 可能放不下所有 Data Block Addresses。

因此需要其他方法。

解決大型 Indexed Allocation

主要有：

Linked Scheme
Multilevel Index
Combined Scheme / UNIX i-Node

Linked Scheme

使用：

多個 Index Blocks

並且將 Index Blocks：

Linked List 串起來。

缺點

如果 File 的 Data Block 在後面的 Index Block：

必須先讀前面的 Index Block。

所以存取第 i 個 Block 的平均 I/O 次數：

會增加。

因此：

不是真正乾淨的 Direct Access。

Multilevel Index

建立：

多層 Index。

例如 Two-Level Index：

第一層：

指向第二層 Index Blocks

第二層：

指向真正 Data Blocks

概念：

Level 1 Index
↓
Level 2 Index
↓
Data Block

例子

假設：

Block Size = 4 KB
Block Address = 4 Bytes

一個 Index Block 可以存：

$$
\frac{4KB}{4Bytes}

1024

2^{10}
$$

個 Block Addresses。

兩層 Index：

$$
2^{10}\times2^{10}

2^{20}
$$

個 Data Blocks。

最大 File Size：

$$
2^{20}\times4KB

4GB
$$

存取一次 Data Block

Two-Level Index：

Read Level-1 Index Block
Read Level-2 Index Block
Read Data Block

所以：

3 次 Disk I/O

Multilevel Index 優缺點

優點	缺點
適合大型 File	小 File 不划算
Direct Access 次數固定	可能產生很多 Index Blocks
容易繼續增加層數	很多 Entries 可能為 NULL

Combined Scheme — UNIX i-Node

UNIX File System 常使用：

i-Node

投影片的例子有：

15 Pointers

其中：

Pointer	功能
1～12	Direct Blocks
13	Single Indirect
14	Double Indirect
15	Triple Indirect

Direct Blocks

前 12 個 Pointer：

直接指向 Data Blocks。

Single Indirect

第 13 個 Pointer：

指向一個 Index Block

Index Block 再：

指向 Data Blocks。

Double Indirect

第 14 個 Pointer：

Index → Index → Data

Triple Indirect

第 15 個 Pointer：

Index → Index → Index → Data

i-Node 最大 File Size 基本公式

假設：

一個 Index Block 可以存 N 個 Block Addresses

則可表示的 Data Blocks：

$$
12+N+N^2+N^3
$$

因此：

$$
Max\ File\ Size

(12+N+N^2+N^3)
\times Block\ Size
$$

注意：考題可能會自己指定 i-Node Entry 數量。

例如你照片中的另一題是：

12 Entries = 9 Direct + Single + Double + Triple

這時不能直接套 12 個 Direct Blocks，要依題目條件計算。

HDD Scheduling

主要演算法：

Algorithm
FCFS
SSTF
SCAN
C-SCAN
LOOK
C-LOOK

目標主要是降低：

Disk Head Movement / Seek Time。

FCFS Scheduling

FCFS：

First Come First Served

也就是：

最早到達的 Request 先處理。

優點

簡單
公平
No Starvation

缺點

Head 可能：

大幅來回移動

所以通常：

效能不是最好。

FCFS 範例

Queue：

98, 183, 37, 122, 14, 124, 65, 67

初始 Head：

53

順序：

53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67

Total Head Movement：

640 Cylinders

SSTF

SSTF：

Shortest Seek-Time First

每次選擇：

距離目前 Head 最近的 Request。

範例

Head：

53

Requests：

98, 183, 37, 122, 14, 124, 65, 67

順序：

53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183

Total Track Movement：

236

SSTF 優點

通常：

效能很好。

因為一直選最近 Request。

SSTF 缺點

可能產生：

Starvation

如果某個遠端 Request 一直存在，而附近不斷有新 Request：

遠端 Request 可能很久都輪不到。

另外：

SSTF 並沒有被證明一定 Optimal。

SCAN Algorithm

SCAN 又稱：

Elevator Algorithm

Head 先往固定方向移動。

途中遇到 Request：

就 Service。

到達 Disk：

邊界 / 軌道盡頭

再：

反方向移動。

SCAN 優點

平均 Head Movement 不錯
Response Time 比較 Uniform
適合 Heavy Loading

SCAN 缺點

即使後面已經沒有 Request：

Head 還是必須走到 Disk 邊界才折返。

因此：

會產生不必要的 Track Movement。

這也是 LOOK 要改善的問題。

C-SCAN

C-SCAN：

Circular SCAN

只提供：

單一方向的 Service。

例如：

往右服務 → 到最右端 → 回到最左端 → 再繼續往右服務

回程：

不提供 Service

C-SCAN 優點

相較 SCAN：

Wait Time 更 Uniform。

考題注意

計算 Head Movement 時：

回到起點的 Movement 要不要計算

必須：

依照題目定義。

LOOK

LOOK 是 SCAN 的變形。

差別：

不需要走到 Disk 邊界。

只要移動到：

該方向最後一個 Request

就：

直接折返。

因此可以：

避免不必要的 Track Movement。

C-LOOK

C-LOOK 是：

LOOK + Circular

只提供單向服務。

到達：

最後一個 Request

直接跳到另一側：

最前面的 Request

再繼續同方向服務。

Disk Scheduling 比較

方法	核心想法	Starvation
FCFS	按到達順序	No
SSTF	最近 Request 優先	Yes
SCAN	來回掃描到邊界	較不容易
C-SCAN	單向服務，到底再返回	較 Uniform
LOOK	SCAN，但只走到最後 Request	較不容易
C-LOOK	LOOK + 單向服務	較 Uniform

FCFS 最簡單、公平，但效能較差。

SSTF 效能很好，但是有 Starvation。

SCAN / C-SCAN / LOOK / C-LOOK 適合 Disk Heavy Loading。

NVM Scheduling

NVM / SSD：

沒有移動 Disk Head。

因此通常不需要：

傳統 HDD 為了減少 Seek Time 所做的複雜 Scheduling。

常使用：

Simple FCFS Policy

例如：

Linux NOOP Scheduler。

NOOP

Linux NOOP：

使用 FCFS

但會做部分修改，例如：

Merge Adjacent Requests。

Read Service Time 較 Uniform
Write Service Time 不一定 Uniform

有些 SSD：

只 Merge Adjacent Write Requests

Read Requests：

選 :

維持 FCFS Order。

Formatting

Disk 在真正存放 File 前，需要經過 Formatting。

Low-Level Formatting

又稱：

Physical Formatting

把 Disk：

劃分成很多 Sectors。

每個 Sector 具有：

Header
Data Area
Trailer

Header / Trailer

包含 Controller 所需資訊，例如：

Sector / Page Number
Error Detection Code
Error Correction Code

通常 Low-Level Formatting：

HDD 在工廠製造時就已經完成。

Partition

接下來 OS 會將 Drive：

切成一個或多個 Partition。

每個 Partition：

是 Blocks 的集合。

OS 可以把每個 Partition：

視為一個 Separate Device。

Logical Formatting

Logical Formatting：

建立 File System。

OS 需要把：

Initial File-System Data Structures

寫進 Disk。

例如：

Free Space Map
Allocated Space Map
FAT
Initial Empty Directory

Cluster

File System 有時會將：

多個 Blocks 聚集

形成：

Cluster

Device I/O：

仍以 Block 為單位

File-System I/O：

可以 Cluster 為單位

藉此增加：

Sequential Access

並降低：

Random Access。

Raw I/O

如果 Partition：

沒有 File System

可以把它視為：

一個大型 Logical Block Array。

這種 Disk 又稱：

Raw Disk

在上面的 I/O：

Raw I/O

Raw I/O 用途

例如：

Swap Space
Database Systems

Database 喜歡 Raw I/O 的原因之一：

可以自行控制 Database Record 的實體位置。

Raw I/O 優點

沒有 File-System Services，例如：

Buffer Cache
File Locking
Prefetching
Space Allocation
File Names
Directories

所以：

可以更 Efficient。

缺點

對：

一般 User
Application Programmer

而言：

很難直接使用。

Bootstrap Loader

電腦開機時：

必須有一個 Initial Program

負責把：

OS Object Code

從 Disk：

Load 到 Main Memory。

這個程式稱為：

Bootstrap Loader

開機流程

Step 1

Power On。

Step 2

執行儲存在：

NVM / Firmware (ROM)

中的：

Tiny Bootstrap Loader。

Step 3

Tiny Bootstrap Loader：

從 Disk 固定位置載入 Full Bootstrap Program。

Step 4

Full Bootstrap Program：

從 Disk 找到 OS Object Code。

Step 5

將 OS：

Load 到 RAM。

Step 6

開始執行 OS。

Boot Block

Full Bootstrap Program 通常存放在 Disk 的固定區域：

Boot Blocks

包含 Boot Partition Blocks 的 Disk：

Boot Disk / System Disk。

Bad Blocks / Sectors

Sector 可能因為：

工廠生產時就壞掉
長期使用後損壞

因此 OS / Disk Controller：

必須處理 Bad Sectors。

方法一：Mark Bad Sector

將壞掉的 Block：

標示為 Unusable

之後 File System：

不再配置它。

例如：

Linux badblocks
DOS chkdsk

方法二：Sector Sparing / Forwarding

Low-Level Formatting 時：

預留一些 Spare Sectors。

這些 Spare Sectors：

OS 看不到，也不能直接配置。

如果某 Sector 壞掉：

Controller 將它重新導向到 Spare Sector。

重點

OS 仍然認為：

自己在存取原本的 Sector。

實際上：

Disk Controller 已經 Redirect 到 Spare Sector。

缺點

Redirect 之後可能破壞：

Disk Scheduling Optimization。

所以通常會讓 Spare Sectors：

分散在各 Cylinder / Track 附近

讓 Bad Sector 優先使用：

同一或鄰近 Cylinder 的 Spare Sector。

方法三: Sector Slipping

另一種方法：

Sector Slipping

假設：

Sector 17 壞掉

第一個 Spare Sector：

203

則不是單純：

17 → 203

而是把中間 Sector 的資料：

一個一個往後移。

例如：

202 → 203
201 → 202
…
18 → 19

最後：

Sector 17 使用原本 Sector 18 的位置。

缺點

需要：

大量 Disk I/O。

Swap Space Management

早期 Swapping：

當 Main Memory 不足時：

Medium-Term Scheduler

可以將 Process：

Swap Out 到 Disk。

釋放：

Memory Space。

現代 OS

目前很少：

整個 Process Swap Out。

通常配合：

Virtual Memory。

主要 Swap：

Pages

而不是：

整個 Process。

Swap Space

Virtual Memory 使用：

Secondary Storage

作為 Main Memory 的延伸。

但是：

Disk Access 比 Memory Access 慢非常多。

因此 Swap Space 管理：

對 System Performance 很重要。

Swap Space Use

不同 OS：

使用 Swap Space 的方式不同。

可以存：

Entire Process Image
Swapped-Out Pages

Swap 大小

Overestimate 比 Underestimate 安全。

因為如果 Swap Space 不夠：

OS 可能必須強制終止 Processes

甚至：

System Crash。

Multiple Swap Spaces

例如 Linux：

可以同時使用多個 Swap Spaces。

包含：

Swap Files
Dedicated Swap Partitions

如果放在：

Separate Storage Devices

還能平衡：

I/O Bandwidth。

Swap-Space Location (申論)

Swap Space 可以放在兩種地方：

Normal File System
Separate Partition / Raw I/O

Normal File System

優點

容易：

Create
Name
Allocate

可以直接使用：

Normal File-System Routine。

缺點

較沒效率。

而且：

可能有 Fragmentation。

Separate Raw Partition

不放：

File System
Directory Structure

所以：

效率較高。

缺點

可能增加：

Internal Fragmentation。

另外 Partition：

大小固定。

如果未來需要更多 Swap：

可能需要 Repartition

或：

再增加其他 Swap Space。

RAID

RAID：

Redundant Arrays of Independent Disks

目的主要有：

提升 Reliability
提升 Performance

RAID 兩個核心技術

① Redundancy

增加可靠度。

主要：

Mirroring
Parity Check

② Parallelism

增加效能。

主要：

Data Striping

將資料分散到：

多個 Physical Disks

讓多個 Disk：

平行存取。

Striping

分成：

Bit-Level Striping
Block-Level Striping

目的：

增加 Throughput
降低大型 Access 的 Response Time

RAID 0

RAID 0：

Block-Level Striping Only

沒有：

Mirroring
Parity
Redundancy

RAID 0

特性	結果
Performance	高
Reliability	沒有提升
Fault Tolerance	無
Space Overhead	最小

適合：

Performance 很重要，但 Data Loss 不重要的情況。

RAID 1

RAID 1：

Mirroring

每一份 Data：

都有一份完整 Mirror。

Disk 數量

假設需要：

N 個 Data Disks

則 RAID 1：

需要 2N 個 Disks。

例如：

4 個 Data Disks

4 個 Mirror Disks
= 8 Disks

實際容量：

仍只有 4 個 Disk。

RAID 1

優點：

High Reliability
Recovery 快速

缺點：

Storage Cost 高。

RAID 2

使用類似 Memory：

Error-Correcting Code（ECC）

的技術。

投影片例子：

4 個 Data Disks + 3 個 Parity Disks

目前：

幾乎沒有實際產品。

RAID 3

使用：

Bit-Level Striping

搭配：

Parity Check。

例如：

4 Data Disks + 1 Parity Disk

總共：

5 Disks。

RAID 4

使用：

Block-Level Striping + Dedicated Parity Disk。

例如：

4 Data Disks + 1 Parity Disk。

RAID 4 Read

多個 Data Disks 可以：

Parallel Read

所以 Large Read：

Transfer Rate 很高。

RAID 4 Write

更新一小塊資料時：

必須更新：

Data Block
Parity Block

使用：

Read-Modify-Write Cycle

一個 Single Write：

Read Old Data
Read Old Parity
Write New Data
Write New Parity

因此：

4 次 Drive Accesses

RAID 4 問題

Dedicated Parity Disk：

可能變成 Bottleneck。

Small Independent Writes：

不容易 Parallel 執行。

RAID 5

RAID 5：

Block-Interleaved Striping + Parity Check

與 RAID 4 最大差異：

Parity Blocks 分散在所有 Disks

而不是：

集中在一個 Parity Disk。

因此可以避免：

單一 Parity Disk 過度使用。

RAID 5

是非常常用的 Parity RAID。

RAID 6

RAID 6 又稱：

P + Q Redundancy

相較 RAID 5：

保存更多 Redundant Information。

可以防止：

Multiple Drive Failures。

照片中的重點：

最多可以同時壞兩顆 Disk

而：

RAID 3、4、5 最多允許一顆 Disk 壞掉。

RAID Levels 比較

RAID	技術	Fault Tolerance
RAID 0	Striping	無
RAID 1	Mirroring	有
RAID 3	Bit Striping + Parity	1 Disk
RAID 4	Block Striping + Dedicated Parity	1 Disk
RAID 5	Block Striping + Distributed Parity	1 Disk
RAID 6	Dual Parity P+Q	2 Disks

RAID 0+1

先：

Striping

再：

將整組 Stripe Mirror。

也就是：

Stripe → Mirror

RAID 1+0

又稱 RAID 10。

先：

每兩顆 Disk 做 Mirror

再：

對這些 Mirror Pairs 做 Striping。

也就是：

Mirror → Stripe

RAID 0+1 vs RAID 1+0

RAID 0+1	RAID 1+0
先 Striping	先 Mirroring
再 Mirror 整組	再 Stripe
一個 Disk 壞可能使整組 Stripe 無法使用	可利用該 Disk 的 Mirror 繼續
Reliability 較差	Reliability 較好

如何選 RAID

RAID 1

適合：

High Reliability + Fast Recovery

RAID 0

適合：

High Performance，但 Data Loss 不重要。

RAID 0+1 / RAID 1+0

適合：

Performance 與 Reliability 都重要

例如：

Small Databases。

RAID 5

常使用在：

Moderate Volume of Data

例如：

中大型 Database。

RAID 6

適合：

需要 Good Performance + Protection

且不希望：

Space Overhead 太大。

File Directory Structure (一次)

主要 Directory Structures：

Single-Level Directory
Two-Level Directory
Tree-Structured Directory
Acyclic Graph Directory
General Graph Directory

Tree-Structured Directory

目前常見的 Directory Structure。

每個 File：

從 Root 到 File 只有唯一一條 Path。

Directory 中可以包含：

Files
Subdirectories

Path Name

分為：

Absolute Path

從：

Root

開始。

Relative Path

從：

Current Directory

開始。

Tree Structure 特性

File / Subdirectory：

無法在不同 Directory 共享。

如果想讓同一 File 出現在兩個地方：

必須複製一份。

Acyclic-Graph Directory

Acyclic：

沒有 Cycle

但是允許：

不同 Directory 共享 File / Subdirectory。

所以：

同一個實體 File

可以出現在：

多個 Directory。

特性

同一個 File 可以：

有很多 Absolute Path Names。

不同 File Names：

可能 Refer to Same File。

Shared File 的刪除問題

假設：

A、B 都指向同一個 File。

如果 A：

Delete File

那到底要不要：

回收 File Storage？

如果直接回收：

B 可能產生 Dangling Pointer。

解法：Reference Count

記錄：

有多少 References 指向這個 File。

新增 Link：

$$
Reference\ Count+1
$$

刪除 Link：

$$
Reference\ Count-1
$$

只有當：

$$
Reference\ Count=0
$$

才：

真正回收 File Space。

Symbolic Link

Shared File 也可以透過：

Symbolic Link

建立。

刪除 Link

刪掉 Symbolic Link：

不影響 Original File。

刪除 Original File

如果 Original File 被刪除：

Symbolic Link 可能變成 Dangling Link。

之後使用 Link 時：

才發現 Target 已不存在。

General Graph Directory

General Graph：

允許 Cycle。

例如：

A → B → C → A

問題一：Infinite Search

搜尋 Directory 時：

可能一直繞 Cycle。

因此必須避免：

重複搜尋同一 Directory。

問題二：File 無法回收

即使外部已經：

沒有人使用 File

Cycle 中的 References：

仍然可能互相指向

導致：

Reference Count 不會變成 0。

因此形成：

Garbage。

Garbage Collection

解決方式：

Traverse Entire File System。

Step 1

對所有可以從 Root 到達的 File：

Mark。

Step 2

沒有被 Mark 的 File：

視為 Garbage。

Step 3

回收：

Storage Space。

缺點

Disk-Based File System：

執行 Garbage Collection 非常耗時。

Directory Structures 比較

Structure	Share	Cycle	主要問題
Tree	✗	✗	無法共享
Acyclic Graph	✓	✗	Shared File 刪除問題
General Graph	✓	✓	Infinite Search、Garbage Collection

File Access Control

UNIX 將 File User 分成三類：

Owner
Group
Other

Owner

建立此 File 的：

User。

Group

由 Owner 指定：

可以共享 File 的一組 Users。

Other

不屬於：

Owner / Group

的其他 Users。

Access Rights

主要有三種：

權限	意義	數字
R	Read	4
W	Write	2
X	Execute	1

命令：

chmod

chmod 例子

例如：

chmod 751 file

拆成：

Owner = 7

$$
4+2+1=7
$$

rwx

Group = 5

$$
4+1=5
$$

r-x

Other = 1

--x

所以：

751 = rwx r-x --x

Consistency Semantics (近幾年)

Consistency Semantics：

描述多個 Users 同時存取 Shared File 時，修改內容如何被其他 Users 看到。

投影片分為三種：

UNIX Semantic
Session Semantic
Immutable Semantic

UNIX Semantic

某個 User 修改 File：

其他 Users 立即看到修改。

也就是：

Visible Immediately。

特性

只有：

Single Physical Image。

所有 Users：

存取同一份內容。

因此需要：

Exclusive Access

來確保正確性。

可能造成：

User Processes Delay。

Session Semantic

使用者對 Open File：

修改內容。

其他 Users：

不會立即看到。

通常等到：

File Close

之後：

後來開啟 File 的 User 才看到修改。

已經 Open File 的 User

如果另一個 User：

已經把 File Open

則：

不一定看到新的修改。

Session Semantic 特性

某一時間點：

File 可能有多個不同 Images。

多個 Users 可以：

同時 Read / Write 自己的 Image。

因此：

不需要立即同步。

例子：

OpenAFS。

Immutable Shared-File Semantic

Immutable：

不可修改。

File 建立完成後：

不能再修改。

只能：

Read-Only。

要求

File Name 不可以重複
File Content 不可以改變

三種 Consistency Semantics

Semantic	修改後其他 User 何時看到
UNIX	Immediately
Session	File Close 後
Immutable	根本不能修改

UNIX：大家看到同一份內容

Session：一個 Session 一份 View

Immutable：建立後不能改

Storage Attachment

Computer 存取 Secondary Storage 主要有四種方式：

Host-Attached Storage
NAS
SAN
Cloud Storage

Host-Attached Storage

直接透過：

Local I/O Ports

連接 Storage。

例如：

SATA

High-End Workstation / Server 也可能使用：

Fibre Channel（FC）

NAS

NAS：

Network-Attached Storage

透過：

Network

存取 Storage。

NAS Protocol

Clients 透過 RPC 存取 NAS。

例如：

OS	Protocol
UNIX / Linux	NFS
Windows	CIFS

NAS 缺點

Storage I/O：

會消耗一般 Data Network Bandwidth。

因此：

增加 Network Latency / Traffic。

SAN

SAN：

Storage-Area Network

是一個：

Private Network。

主要使用：

Storage Protocols

而不是一般 Network Protocols。

SAN 優點

Flexibility

多個 Hosts：

可以連接相同 Storage Arrays。

Storage：

也可以動態配置給 Hosts。

Storage I/O 不佔一般 Network Bandwidth

架構大致：

Client
↓
LAN / WAN
↓
Server
↓
SAN
↓
Storage Array

所以：

Storage I/O 有自己的 Storage Network。

NAS vs SAN

NAS	SAN
經一般 Network	Private Storage Network
常以 File 為主	Storage / Block 為主
NFS / CIFS	Storage Protocol
會使用一般 Network Bandwidth	Storage I/O 不佔一般 Network Bandwidth

Cloud Storage

Cloud Storage 與 NAS 類似：

都透過 Network 存取 Storage。

差別：

Cloud 通常經 Internet / WAN 連到遠端 Data Center。

Protocol 差異

NAS 可以：

NFS / CIFS → File System
iSCSI → Raw Block Device

Cloud Storage 則通常：

API Based

Application：

使用 API 存取 Storage。

Cloud Storage 例子

Amazon S3
Dropbox
Microsoft OneDrive
Apple iCloud

Cloud Storage 連線

NAS 通常：

使用 LAN

所以 Latency 較低。

Cloud：

經 Internet / WAN

連線失敗：

相對比較常見。

因此 Application：

可能暫停 Storage Access，等待重新連線。

最後總整理

Free Space Management

方法	重點
Bitmap	1 Bit / Block
Linked List	Free Blocks 串起來
Grouping	一次記很多 Free Blocks
Counting	Start Block + Count

File Allocation

方法	Direct Access	External Fragmentation	Grow
Contiguous	✅ 很快	✅ 有	❌ 困難
Linked	❌ 慢	❌ 無	✅ 容易
FAT	✅ 比 Linked 好	❌ 無	✅
Indexed	✅	❌ 無	✅

Disk Scheduling

Algorithm	記憶方式
FCFS	誰先來誰先做
SSTF	最近的先做
SCAN	電梯來回到底
C-SCAN	只服務一個方向
LOOK	不走到底，看最後一個 Request
C-LOOK	LOOK + 單向

RAID

RAID	一句話
RAID 0	Striping，沒備份
RAID 1	Mirror
RAID 3	Bit Striping + Parity
RAID 4	Block Striping + 單一 Parity Disk
RAID 5	Block Striping + 分散 Parity
RAID 6	Dual Parity，可壞兩顆
RAID 0+1	Stripe → Mirror
RAID 1+0	Mirror → Stripe

Directory	重點
Tree	不共享、無 Cycle
Acyclic Graph	可共享、無 Cycle
General Graph	可共享、可有 Cycle

Consistency

類型	核心
UNIX	修改立即可見
Session	Close 後才可見
Immutable	建立後不可修改

Storage Attachment

類型	核心
Host-Attached	直接連本機
NAS	Network File Storage
SAN	Private Storage Network
Cloud	Internet / WAN + API

這一章考試最容易混的四組：

① Contiguous / Linked / Indexed
② Bitmap / Linked List / Grouping / Counting
③ FCFS / SSTF / SCAN / C-SCAN / LOOK / C-LOOK
④ RAID 0 / 1 / 4 / 5 / 6 / 0+1 / 1+0

文章作者: YowDesert

文章連結: https://yowdesert.github.io/posts/16471629.html

作業系統

Massive Storage System

Hard Disk Drive

HDD 基本結構

關係

HDD Structure

Sector

RPM

Disk Access Time(計算)

Seek Time

Rotational Latency

$$ Average\ Latency

Transfer Time

Disk Access Time 考題

① Disk Capacity

② Average Rotational Latency

$$ \frac{6000}{60}

$$ \frac{1}{100}

0.01s

$$ Average\ Latency

\frac{10}{2}

③ Read File 所需時間

$$ Read\ Time

Non-Volatile Memory Devices

NVM vs HDD

Free-Space Management(少考)

Bit Vector / Bitmap

優點

缺點

Linked List — Free Space

優點

缺點

Grouping

Grouping 優點

Counting

Counting 優點

File Allocation Methods (三顆星)

Contiguous Allocation

Directory 要記什麼？

找第 i 個 Block

$$ Block\ Number

Contiguous Allocation 優點

1. Seek Time 較短

2. Sequential Access 很快

3. Random / Direct Access 很快

4. 容易實作

Contiguous Allocation 缺點

1. 不容易找到連續的 Free Blocks

2. External Fragmentation

3. File 不容易成長

Modified Contiguous Allocation

Linked Allocation

Directory

Linked Allocation 優點

1. No External Fragmentation

2. File 很容易成長

3. 建立 File 前不用先知道大小

Linked Allocation 缺點

1. Direct Access 效率差

2. Pointer Overhead

3. Lower Reliability

4. Seek Time 較長

FAT — File Allocation Table

核心概念

特殊值

FAT 的優點

FAT 的重要條件

Indexed Allocation

Directory

Indexed Allocation 優點

Indexed Allocation 缺點

1. Index Block 空間浪費

2. 大型 File

解決大型 Indexed Allocation

Linked Scheme

缺點

Multilevel Index

例子

$$ \frac{4KB}{4Bytes}

1024

$$ 2^{10}\times2^{10}

$$
Average\ Latency

$$
\frac{6000}{60}

$$
\frac{1}{100}

$$
Average\ Latency

$$
Read\ Time

$$
Block\ Number

$$
\frac{4KB}{4Bytes}

$$
2^{10}\times2^{10}

$$
2^{20}\times4KB

$$
Max\ File\ Size