15.1-磁碟資料存取與管理算法

磁碟資料存取與管理算法#

磁碟資料存取與管理是計算機系統中關於硬碟（HDD）或固態硬碟（SSD）等存儲設備的基礎工作。這些算法主要關注如何有效地組織、讀取、寫入磁碟上的資料，並最大程度地提高存取效率。磁碟存取涉及許多操作，包括尋址、排程以及維護磁碟中的資料結構等。

1. 磁碟存取原理#

磁碟存取是指如何在磁碟中讀取或寫入資料。磁碟設備通常會將資料劃分為若干個扇區（sector），每個扇區的大小通常是512字節或4KB。資料存取的過程涉及磁頭移動到指定位置，並進行讀寫操作。這一過程受到物理和邏輯的限制，因此磁碟存取的效率對於系統性能至關重要。

磁碟的存取速度受限於： - 尋道時間（Seek Time）：磁頭從當前位置移動到目標位置所需的時間。 - 旋轉延遲（Rotational Latency）：等待目標扇區旋轉到磁頭下方所需的時間。 - 傳輸時間（Transfer Time）：從磁碟讀取或寫入資料所需的時間。

2. 磁碟存取算法#

為了有效地進行資料存取，設計了多種磁碟排程算法，這些算法用來決定磁頭的移動順序，以最小化總的存取時間。

(1) 先來先服務（FCFS: First-Come, First-Served）#

這是最簡單的磁碟排程算法，根據請求的到達順序依次執行。這種方法實現簡單，但可能導致較大的磁頭移動，效率不高。

優點：實現簡單，對用戶請求的順序保持尊重。
缺點：磁頭移動可能不均勻，導致較高的延遲。

(2) 最短尋道時間優先（SSTF: Shortest Seek Time First）#

SSTF算法選擇最接近當前磁頭位置的請求，這樣可以減少磁頭移動的距離，從而減少尋道時間。

優點：能減少尋道時間，效率較高。
缺點：可能會導致饑餓現象，即某些請求可能長時間無法被服務。

Python範例：

def sstf(requests, start):
    seek_count = 0
    distance = 0
    cur_track = 0
    left = []
    right = []

    # 分類請求
    for r in requests:
        if r < start:
            left.append(r)
        if r > start:
            right.append(r)

    # 排序
    left.sort(reverse=True)
    right.sort()

    # 處理右側的請求
    for r in right:
        distance = abs(r - start)
        seek_count += distance
        start = r

    # 處理左側的請求
    for r in left:
        distance = abs(r - start)
        seek_count += distance
        start = r

    return seek_count

requests = [34, 78, 12, 56, 90, 45, 67]
start = 50
seek_count = sstf(requests, start)
print("Total seek count:", seek_count)

(3) 扇區掃描（SCAN）#

SCAN算法也稱為電梯算法，磁頭沿著磁碟表面的一個方向移動，直到達到端點後，再反向移動。這種方法比FCFS更有效，因為它避免了磁頭在磁碟上來回跳躍。

優點：能夠保持較穩定的性能，避免磁頭來回移動。
缺點：磁頭到達邊界後會反向，可能會導致一些遠離當前磁頭位置的請求等待較長時間。

(4) 循環掃描（C-SCAN）#

C-SCAN是SCAN的變種，它只在一個方向上掃描磁碟，當到達最遠的一端時，會將磁頭返回起始位置，並繼續沿著同一方向掃描。這樣可以保持相對均衡的服務時間。

優點：較為均衡，不會出現反向掃描的問題。
缺點：如果大量的請求在磁碟的邊界附近，可能會有較長的等待時間。

(5) 最長等待時間優先（LOOK）#

LOOK算法和SCAN相似，不同之處在於LOOK在遇到請求無法繼續時會停止，而不是掃描到磁碟的邊界。這樣可以避免無謂的磁頭移動。

(6) C-LOOK#

C-LOOK是LOOK算法的變種，當磁頭達到邊界後，它會立即返回，而不是繼續掃描到邊界。這樣可以提高效率，避免過多的反向掃描。

3. 磁碟存儲管理算法#

除了排程算法，磁碟存儲的管理還涉及磁碟資料結構的管理，例如檔案系統和磁碟分配策略等。

(1) 磁碟分配策略#

磁碟的存儲空間需要有效的分配，常見的策略有：

連續分配（Contiguous Allocation）：資料以連續區域分配，這樣可以提高讀取性能，但可能會導致外部碎片問題。
鏈式分配（Linked Allocation）：每個區塊包含指向下一個區塊的指針，這樣可以解決碎片問題，但讀取性能較差。
索引分配（Indexed Allocation）：為每個檔案分配一個索引塊，索引塊中存儲檔案區塊的位置，這樣能高效地存取非連續資料。

(2) 磁碟快取策略#

磁碟快取的目的是通過將熱資料存儲在快速存儲設備（如RAM）中來減少磁碟I/O操作的次數。常見的快取策略包括：

最近最少使用（LRU: Least Recently Used）：將最久未使用的資料從快取中移除。
先進先出（FIFO: First In First Out）：按照資料進入快取的順序移除。
最少頻率使用（LFU: Least Frequently Used）：移除使用次數最少的資料。

總結#

磁碟資料存取與管理算法是提高磁碟效能的關鍵技術，常見的排程算法包括FCFS、SSTF、SCAN、C-SCAN、LOOK等。每種算法有其優缺點，適用於不同的應用場景。此外，磁碟分配策略和快取管理對於減少I/O延遲、提高系統效能也有重要影響。