在看文章前可以先看下這個，

吳海波：專欄的序。

先有個大概的認識會對閱讀有所幫助。

這一章來介紹下常用的存儲設備：硬碟。我們有如下問題：

現代硬碟驅動器如何存儲數據？硬碟對外提供的介面是什麼？數據實際上是如何分布和訪問的？如何提高磁碟調度的性能？

讓我們從理解現代磁碟驅動器的介面開始。所有現代硬碟設備的介面都很簡單。驅動器由大量扇區(512位元組塊)組成，每個扇區都可以讀寫。在有n個扇區的磁碟上，扇區編號從0到n?1。因此，我們可以將磁碟看作扇區數組；0到n?1是驅動器的地址空間。多扇區操作是可以的；事實上，許多文件系統一次讀寫4KB大小的數據(或更多)。然而，在操作磁碟時，驅動器製造商做的唯一保證是，單個512位元組的寫入是原子性的(也就是說，它要麼全部完成，要麼根本不完成)；因此，如果發生了意外的中斷，可能只有一小部分數據是真正完成的。

我們在使用磁碟的時候通常會有一些假設，但這些假設在設備的說明中其實並沒有直接規定；Schlosser和Ganger稱這是磁碟驅動器的「默認契約」。具體來說，人們通常可以假設訪問兩個相鄰塊的速度相對較快。通常還可以假設，連續的塊訪問速度比隨機訪問的速度要快。

下面我們一步一步的來說明磁碟的結構。我們從一個碟片開始，你可以想像它是一張cd的樣子，通過改變磁性來持久地存儲數據。磁碟可以有一個或多個碟片；每個盤有兩個面，每個面稱為表面(surface)。這些碟片通常由一些硬質材料(如鋁)製成，然後塗上一層薄薄的磁性層，使驅動器即使在電源關閉時也能持久地存儲信息（就像磁鐵的磁性可以保持很久一樣）。這些碟片都圍繞著主軸捆綁在一起，主軸連接到一個電機上，它以恆定(固定)的速度旋轉碟片。旋轉速度通常以每分鐘旋轉圈數(RPM)來衡量，現代磁碟的值在7，200 RPM到15，000 RPM範圍內。注意，我們通常會對單個旋轉的時間感興趣，例如，10，000 RPM的驅動器一次旋轉大約需要6毫秒。碟片上有一圈一圈的同心圓，我們把這樣的一個同心圓稱為磁軌。一個單一的表面（surface）包含成千上萬個磁軌，它們緊密的排列著，數百個磁軌才和人的頭髮一樣寬。為了從表面上讀和寫，我們需要一種機制，使我們能夠感知(即讀取)磁碟上的磁性，或者促使它們發生變化(即寫入)。這個讀寫過程是由磁碟磁頭完成的；驅動器的每個表面都有這樣的磁頭。磁碟頭連接到一個磁碟臂上，該臂在表面上移動以將磁頭定位於所需的軌道上。

假設我們有一個只有一個磁軌的硬碟(圖37.1)，看看它是怎麼工作的。這個軌道只有12個扇區，每個扇區的大小為512位元組，因此由數字0到11來處理。我們希望能夠讀或寫這些扇區，因此我們需要一個磁碟頭，連接到磁碟臂上，如我們現在所看到的(圖37.2)。在圖中，磁頭位於扇形6上方，磁軌逆時針旋轉。

先設想我們現在收到讀取塊0的請求。磁碟應該如何處理這個請求？在我們的簡單磁碟中，磁碟不需要做太多事情。它只需要等待所需扇區旋轉到磁頭下。這種等待在現代驅動器中經常發生，並且是I/O服務時間的重要組成部分，因此它有一個特殊的名稱：旋轉延遲。在示例中，如果旋轉一圈的延遲為R，則磁碟必須產生大約R/2的旋轉延遲，以等待塊0在磁頭下(如果我們從6開始)。在這條單軌上，最壞的情況是第5塊，因為幾乎要旋轉一圈才能去讀取。

到目前為止，我們的磁碟只有一個磁軌，這是不太現實的；現代磁碟有數百萬磁軌。因此，讓我們看一看一個更加真實的磁碟表面，這一個有三個軌道(圖37.3，左)。在圖中，磁頭目前位於最裡面的磁軌上(其中包含24至35扇區)；下一磁軌包含下一組扇區(12至23)，最外層磁軌包含第一組扇區(0至11)。

為了了解驅動器如何訪問給定的扇區，我們跟蹤一個訪問較遠扇區的例子，例如讀取扇區11。要進行這種讀取，驅動器首先將磁碟臂移動到正確的軌道(在本例中，是最外層的)，這一過程稱為尋道（seek）。與旋轉一樣，尋道是最昂貴的磁碟操作之一。需要注意的是，尋道分很多階段：首先是磁碟臂移動時的加速階段；然後是全速運動時的滑行階段，然後是減速時的減速階段；最後是磁頭在正確軌道上小心定位時的下沉階段。下沉階段的時間通常是相當重要的，大概在0.5到2ms，因為驅動器必須確定找到了正確的軌道(想像一下，如果它停在2個磁軌中間會怎麼樣。。。)，在尋道之後，磁碟臂已經將磁頭定位在正確的軌道上。圖37.3(右)描述了這個動作。正如我們所看到的，在尋道的過程中，磁頭被移動到了想要的軌道上，而磁碟當然也已經旋轉了，在這種情況下大約旋轉過了3個扇區。因此，第9扇區即將通過磁碟磁頭，我們必須忍受一個短暫的旋轉延遲才能傳輸數據。當扇區11通過磁碟磁頭下時，將發生I/O的最後階段，稱為傳輸（tranfer），其中數據要麼從表面讀取，要麼寫入表面。到這裡，我們有一個完整的I/O時間圖：首先是尋道，然後等待旋轉延遲，最後是傳輸。

這裡還有一些關於硬碟運行的有趣細節。許多驅動器使用磁軌的不對稱來確保順序讀取即使跨越磁軌也可以高效的進行。在我們的簡單示例磁碟中，如圖37.4所示。

當從一個磁軌切換到另一個磁軌時，磁碟需要時間來重新定位磁頭(甚至是鄰近的磁軌)。如果沒有這樣的不對稱，磁頭被移動到下一個軌道時，所需讀取的下一個塊已經過了磁頭，因此驅動器將不得不等待幾乎整個旋轉延遲才能訪問下一個塊。

任何現代磁碟驅動器的一個重要部分是它的緩存，由於歷史原因，有時被稱為track buffer。這個緩存只有很小的的內存大小(通常大約是8或16 MB)，驅動器可以用來保存從磁碟讀取或寫入磁碟的數據。例如，當從磁碟讀取一個扇區數據時，驅動器可能讀取該磁軌上的所有扇區的數據並將其緩存在內存中；這樣做可以使驅動器快速響應對同一磁軌的任何後續請求。在寫操作時，驅動器對寫動作的完成有2個不同的定義：當它將數據放入其內存中時，還是在實際寫入磁碟之後？前者被稱為寫回（write back ），後者則被稱為直寫（write through）。寫回有時會使驅動器看起來「更快」，但可能是危險的；如果文件系統或應用程序要求按一定順序將數據寫入磁碟以確保正確性，則寫回可能會導致問題(詳細信息可以看說日誌文件系統的那一章)。

現在我們有了磁碟的抽象模型，可以使用數據來做一些分析，使我們更好地理解磁碟性能。我們現在可以將I/O時間表示為三個主要組成部分的總和：

請注意，I/O的速率通常更容易用於驅動器之間的比較，並且速率可以很容易的計算出來。只需將傳輸的數據大小除以時間就可以了：

為了更好地理解I/O時間，讓我們執行以下計算。假設有兩個我們感興趣的工作負載。第一個稱為隨機工作負載，它對磁碟上的隨機位置進行小範圍(例如，4KB)讀取。在包括資料庫管理系統在內的許多重要應用程序中，隨機工作負載是常見的。第二個工作負載稱為順序工作負載，它簡單地從磁碟連續讀取大量扇區，而不會進行任意的跳轉。順序訪問模式非常常見，因此也很重要。為了理解隨機工作負載和順序工作負載之間的性能差異，我們首先需要對磁碟驅動器做一些假設。讓我們來看看希捷的幾個現代磁碟。第一個，被稱為Cheetah 15K.5，是一個高性能的SCSI驅動器。第二個，Barracuda，它的特點是容量特別大。有關這兩個硬碟的詳細信息，見圖37.5。

正如上圖所示，這些驅動器具有非常不同的特性，並且在許多方面很好地總結了磁碟驅動器市場的兩個重要組成部分。第一個是「高性能」驅動器市場，在這個市場上，驅動器被設計成儘可能快地旋轉，尋道時間少，並快速傳輸數據。第二個是「容量」市場，在這個市場中，每位元組的成本是最重要的考量；因此，雖然驅動器速度較慢，但可以將儘可能多的比特打包到可用的空間中。現在我們可以開始計算硬碟在上述兩個工作負載下的性能。讓我們從隨機工作負載開始。假設每個4KB的讀取發生在磁碟上的一個隨機位置，我們可以計算每次讀取所需的時間。在Cheetah上：

平均尋道時間(4毫秒)只是製造商報告的平均時間；需要注意，一個完整的尋道(從表面的一端到另一端)可能要花費兩到三倍的時間。可以直接由RPM來計算平均轉動延遲。15000 rpm等於250個rps(每秒旋轉)；因此，每個旋轉需要4ms。磁碟旋轉的平均值是半圈，因此，2ms是平均時間。最後，傳輸時間是在峰值傳輸速率下傳輸數據的值；這裡的傳輸時間非常小(30微秒；請注意，我們需要1000微秒才能得到1毫秒！)因此，根據我們上面的方程式，Cheetah的TI/O大約等於6毫秒。所以在隨機工作負載下,Cheetah的RI/O大約是0.66MB/s。對Barracuda的計算得出的TI/O約為13.2ms，因此RI/O約為0.31MB/s。現在讓我們看看順序工作負載。在這裡，我們可以假設在數據傳輸前有一個尋道和磁軌旋轉時間。為了簡單起見，假設傳輸的大小為100 MB。因此，Cheetah和Barracuda的TI/O分別約為800毫秒和950毫秒。因此，I/O的速率非常接近峰值傳輸速率，分別為125 MB/s和105 MB/s。圖37.6匯總了這些數字。這個數字向我們展示了一些重要的事情。首先，也是最重要的是，隨機工作負載和順序工作負載之間在性能上存在巨大差距，Cheetah是200倍左右，Barracuda超過300倍（已經不在一個數量級了，非常可怕的差距）。第二點：高端「性能」驅動器和低端「容量」驅動器在性能上有很大的差異。所以人們往往願意為前者支付最高的費用，而試圖以儘可能低的價格得到後者。

tip：平均尋道時間

下面來簡單說下平均尋道時間是怎麼算出來的。首先這個計算是根據磁軌間的距離來的。假設我們有0到N個磁軌。x，y是任意2個磁軌，它們之間的距離是絕對值x-y。為了計算平均尋道距離，我們首先計算下所有情況下的磁軌距離：

然後除以所有可能的情況數量:N*N.下面的式子使用了積分的形式

為了計算內部的積分，我們將絕對值打開

這個式子就是簡單的一元定積分了，求被積函數的原函數，得到的結果是這個：

將上下界帶入然後化簡得到：

現在我們來計算原來的二重積分的dx部分的積分：

又是一個簡單的定積分，求值後結果為：

最後將這個結果除以N*N,得到的結果就是n/3。所以平均尋道時間就是最大尋道時間除以3了。

因為I/O操作的高消耗，因此OS在決定I/O操作順序上扮演這很重要的角色。具體來說，給定一系列的I/O請求，硬碟調度器會判斷請求並且決定讓哪個請求接下來執行。不像job調度那樣，即job的運行時間無法確定，I/O請求的時間容易評估些，所以調度器的策略就儘可能按照SJF（shortest job first）策略進行。

早期的一個調度策略是SSTF（Shortest Seek Time First），SSTF按磁軌順序排列I/O請求隊列，選擇距離當前磁軌最近的請求執行。例如，假設磁頭的當前位置在內部磁軌上，並且我們有對第21扇區(中間磁軌)和第2扇區(外部磁軌)的請求，那麼會先完成對21扇區的請求再去完成對2扇區的請求(圖37.7)。

在本例中，SSTF運行良好，首先尋找中間磁軌，然後尋找外部磁軌。然而，SSTF並不是靈丹妙藥，原因如下。首先，主機操作系統無法使用驅動器內部結構；相反，它看到的只是一個個塊組成的數組。幸運的是，這個問題很容易解決。操作系統可以簡單地實現最近塊優先(NBF，nearest-block-first)，而不是sstf，前者對距離最近的塊優先進行訪問。

第二個問題更為根本：飢餓。在上面的例子中，想像下如果接下來的一系列請求都是對內部磁軌的，那麼對於外部磁軌的請求就會一直得不到完成。因此，問題的癥結在於：

我們如何實現類似SSTF的調度而避免飢餓？

針對這個問題的解決方法在很多年前就已經有了方案，並且說起來也相對簡單。該演算法最初被稱為掃描（SCAN），這個策略就是來回掃描磁軌，並且按照這個順序來完成對應磁軌的請求（還記得電梯調度演算法嗎，沒錯，就是這個）。我們稱對磁碟的一次從裡到外或者從外到里的訪問稱為sweep。因此，如果一個請求對應的磁軌已經在這次sweep中服務過了，則不會立即處理它，而是排隊直到下一個掃描(在另一個方向)。

掃描有許多變體，但是仍然有問題，特別是這個演算法根本沒有去考慮磁碟的旋轉延遲問題，所以我們接下來的問題就是：

如何通過同時考慮尋道和旋轉延遲來實現更接近SJF的演算法？

在討論最短定位時間優先(shortest positioning time first，SPTF)調度(有時也稱為最短訪問時間優先(shortest access time first，SATF)之前，讓我們通過一個例子來更加深入的理解我們面臨的問題。圖37.8給出了一個示例。

在示例中，磁頭當前位於內部磁軌的扇區30上。因此，調度程序必須決定：對於扇區16和扇區8的請求，應該選擇哪個來完成？答案是「視情況而定」。在工程學中，「視情況而定」幾乎總是答案，反映出權衡是工程師生活的一部分；這樣的格言在緊要關頭也是有意義的。例如，當你不知道老闆問題的答案時，你就可以這麼說（。。。當然也要視你的老闆性格而定）。最關鍵的在於，我們要知道為什麼要「視情況而定」，我們究竟要根據哪些因素來討論最終的方案。在現在的磁碟問題上，我們討論的就是尋道時間和旋轉時間，哪個佔據的比重更大。如果在我們的示例中，尋道時間比旋轉延遲要高得多，那麼SSTF(和變體)就很好了。然而，想像一下，如果尋道比旋轉要快得多呢。在我們的示例中，對外部磁軌的扇區8服務比扇區16效率要更高，因為要訪問扇區16，要旋轉幾乎一圈，這個旋轉延遲要大於尋道時間。

在現代驅動器上，正如我們上面所看到的，尋道和旋轉大致是等價的(當然，取決於確切的請求)，因此SPTF是有用的，並且提高了性能。然而，在操作系統中實現則非常困難，因為操作系統通常不清楚磁軌邊界在哪裡或磁頭當前在哪裡。因此，SPTF通常在驅動器內執行，如下所述。

在對基本磁碟操作、調度和相關主題的簡要描述中，我們沒有討論許多其他問題。其中一個問題是：在現代系統上，磁碟調度在哪裡執行？在舊系統中，所有的調度都是由操作系統完成的；在查看一組掛起的請求之後，操作系統將選擇最好的請求，並將其發送到磁碟。當該請求完成後，將選擇下一個請求，依此類推。磁碟也是這樣。

在現代系統中，磁碟可以容納多個未執行的請求，並且具有複雜的內部調度程序(它可以精確地實現SPTF；在磁碟控制器內部，所有的相關的細節都是可用的，包括精確的磁頭位置)。因此，操作系統調度程序通常選擇它認為最好的幾個請求(例如16個)，並將它們全部發送到磁碟；然後，磁碟使用其對頭部位置的內部數據和詳細的磁軌布局信息，以最佳的(SPTF)順序處理所述請求。

磁碟調度程序的另一個重要任務是I/O合併。例如，設想有一系列讀取塊33，8，34的請求，如圖37.8所示。在這種情況下，調度程序應該將對塊33和塊34的請求合併為一個單一的請求。合併在操作系統級別尤為重要，因為它減少了發送到磁碟的請求數量，從而降低了開銷。現代調度程序解決的最後一個問題是：系統應該等待多長時間才向磁碟發出I/O？人們可能天真地認為，一旦有了一個I/O，就應該立即向驅動器發出請求；這樣會產生work-conserving，也就是說如果有i/o請求，磁碟就永遠不會空閑。然而，相關研究已經表明，稍微等待一會再執行i/o操作也許會更好。通過等待，一個新的「更好」的請求可能到達磁碟，從而提高總體效率。當然，決定等待的時間可能會很棘手；詳細信息請參閱研究論文，或者查看Linux內核實現，以了解這些想法是如何轉化為實踐的(如果你是那種雄心勃勃的人，我相信你是的)。

推薦閱讀：

相关文章