作業系統學習筆記-I/O管理和磁盤排程

前言

正在學習作業系統，記錄筆記。

參考資料：

《作業系統（精髓與設計原理 第8版） 》

第十一章：I/O管理和磁盤排程

I/O裝置

I/O裝置大體上可以分為如下三類：

• 人可讀：顧名思義就是其面向的使用者群體是人，具體有：
  • 列印機
  • 終端（包含：顯示器、鍵盤、滑鼠等）
• 機器可讀：面向電子裝置通信，具體有：
  • 磁盤、錄音帶驅動器
  • 傳感器
  • 控制器
• 通信：适用于與遠端裝置通信，如：
  • 數字線路驅動器
  • 數據機

資料傳送速率：不同類型的I/O裝置，資料傳送速率可能會相差幾個數量級，如下圖：

用途：裝置用途對作業系統及其支撐設施中的軟體和政策都有影響。

• 用于存儲檔案的磁盤需要檔案管理軟體的支援
• 虛拟記憶體需要特殊硬體軟體支援
• 終端既可被普通使用者使用，也可被系統管理者使用。

控制的複雜性：例如，列印機僅需要一個相對簡單的控制接口，而磁盤的控制接口則要複雜得多。

傳送機關：資料可按位元組流或字元流的形式傳送（如終端I/O），也可按更大的塊傳送（如磁盤I/O）。

錯誤條件：随着裝置的不同，錯誤的性質、報告錯誤的方式、錯誤造成的後果及有效的響應範圍，都各不相同。

以上的差異使得不管是從作業系統的角度，還是從使用者程序的角度，都很難找到一種統一的、一緻的I/O解決方法。

I/O功能的組織

有三種執行I/O的技術（具體可以看第一章的内容，這裡不過多介紹）：

• 可程式設計I/O：處理器代表一個程序給I/O子產品發送一個I/O指令；該程序進入忙等待，直到操作完成才能繼續執行。

  缺點：當執行I/O操作時，處理器容易進入忙等待狀态（空閑），造成處理器資源浪費。

• 中斷驅動I/O：處理器代表程序向I/O子產品發出一個I/O指令。有兩種可能性：
  • 若來自程序的I/O指令是非阻塞的，則處理器繼續執行發出I/O指令的程序的後續指令。

  • 若I/O指令是阻塞的，則處理器執行的下一條指令來自作業系統，它将目前的程序設定為阻塞态并排程其他程序。

    引入中斷機制。

    缺點：雖然緩解了忙等待狀況，但是最後資料在I/O裝置與主存之間傳輸的過程要依賴于處理器。

• 直接存儲器通路（Direct Memory Access，DMA）：一個DMA子產品（作為“代理CPU”）控制記憶體和I/O子產品之間的資料交換。為傳送一塊資料，處理器給DMA子產品發請求，且隻有在整個資料塊傳送結束後，它才被中斷。

  資料在I/O裝置與主存之間傳輸的整個過程隻産生兩次中斷：

  • 在調用I/O裝置前，處理器向I/O裝置發出指令
  • 資料傳輸完之後，DMA子產品向I/O裝置發出中斷（告知“資料傳輸完畢”）
  優勢：資料在I/O裝置與主存之間傳輸不依賴于處理器。

小結I/O執行技術

無中斷	使用中斷
通過處理器實作I/O和記憶體間的傳送	可程式設計I/O	中斷驅動I/O
I/O和記憶體間直接傳送	直接存儲器通路（DMA）

I/O功能的發展

1. 處理器直接控制外圍裝置：這在簡單的微處理器控制裝置中可以見到。

2. 增加了控制器或I/O子產品：引入無中斷的可程式設計I/O。

   從該階段開始，處理器無需處理外部裝置的細節。

3. 同上一階段基本相同，但是采用了中斷的方式：處理器無須費時間等待執行一次I/O操作，因而提高了效率。
4. DMA子產品的引入：資料塊在I/O裝置和記憶體中移動無需處理器參與，僅在傳送開始和結束時才需要用到處理器。

5. I/O子產品有一個獨立處理器：有專門為I/O設計的指令集，中央處理器指導I/O處理器執行記憶體中的一個I/O程式。I/O處理器在沒有中央處理器幹涉的情況下取指令并執行這些指令。這就使得中央處理器可以指定一系列的I/O活動，且僅在整個序列執行完成後中央處理器才被中斷。

   該階段的I/O子產品通常稱為：I/O channel (I/O通道)

6. I/O子產品有自己的局部存儲器，事實上其本身就是一台計算機：
   • 使用這種體系結構可以控制許多I/O裝置，并使需要中央處理器參與的部分降到最小
   • 這種結構通常用于控制與互動終端的通信，I/O處理器負責大多數控制終端的任務
   該階段的I/O子產品通常稱為：I/O processor (I/O處理器)

直接存儲器通路（DMA）

下圖是典型的DMA框圖

說明：

• Data Count：儲存此次傳輸的資料的位元組數
• Data Register：存放正在傳輸的資料
• Address Register：基址寄存器
• Control Logic：其他的一些功能

DMA工作流程：

1. 處理器和DMA子產品之間有讀寫控制線，基于此處理器可以向DMA子產品發送指令（請求I/O）
2. DMA子產品直接負責I/O裝置到記憶體之間的資料傳輸（不需要處理器）
3. 在資料傳輸完之後，DMA子產品向處理器發送一個中斷信号

DMA機制的配置：

• 所有子產品共享同一個系統總線：

• DMA子產品充當代理處理器
• 同一時刻隻允許一個I/O裝置和主存進行互動，否則會出現資料沖突
• 同一個時間段可以有多台I/O裝置和主存進行互動——分時複用
• 排隊的情況很嚴重，雖然這樣的設計開銷不大，但是效率很低

• 內建DMA和I/O：

• 減少了I/O對DMA子產品的競争

  在DMA子產品和一個或多個I/O子產品之間還存在一條不包含系統總線的路徑。DMA邏輯實際上可能就是I/O子產品的一部分，或可能是控制一個或多個I/0子產品的一個單獨子產品。

• 增加I/O局部總線：

• DMA子產品中I/O接口的數量減少到1
• 易擴充

第二、三種方式：DMA和I/O子產品之間的資料交換是脫離系統總線完成的。

作業系統設計問題

設計目标

在設計I/O機制時，最重要的兩個目标就是：效率（Efficiency）、通用性（Generality）。

• 效率：

  • I/O操作通常是計算機系統的瓶頸。

    之前也提到過，大多數I/O裝置都是機械運動，而處理器是電信号的處理，二者的速度差距在幾個數量級。

  • 解決上述問題的一種方式是引入多道程式設計。這樣可以緩解，但不能徹底解決問題。我們想象一種極端情況：在并發度達到最大時，所有的程序都在等待I/O裝置，那麼這時也會出現CPU空閑狀态，效率并不能有效提高。
  • 于是引入交換技術。用于将額外的就緒程序加載進記憶體，進而使處理器處于工作狀态。（這本身就是一個I/O操作）

• 通用性：處于簡單和避免錯誤的考慮，希望能用一種統一的方式處理所有裝置。

  注：有些版本将“通用性”翻譯為“裝置的獨立性”。

  • 處理器看待I/O裝置的方式統一。

  • 作業系統管理I/O裝置和IVO操作的方式統一。

    由于裝置特性的多樣性，在實際中很難真正實作通用性。

    目前所能做的就是用一種階層化、子產品化的方法設計I/O功能。這種方法隐藏了大部分I/O裝置低層例程中的細節，使得使用者程序和作業系統高層可以通過如讀、寫、打開、關閉、加鎖和解鎖等通用的函數來操作I/O裝置。

I/O功能的邏輯結構

分層的原理是：作業系統的功能可以根據其複雜性、特征時間尺度和抽象層次來分開。

将分層原理應用于I/O機制，具體如下圖：

說明：

• 邏輯I/O（Logical I/O）：邏輯I/O子產品把裝置當作一個邏輯資源來處理，它并不關心實際控制裝置的細節。
• 裝置I/O（Device I/O）：請求的操作和資料（緩沖的資料、記錄等）被轉換為适當的I/O指令序列、通道指令和控制器指令。
• 排程和控制（Scheduling & control）：I/O操作的排隊、排程實際上發生在這一層。
• 目錄管理（Directory management）：在這一層，符号檔案被轉換為辨別符，采用辨別符時可通過檔案描述符表或索引表直接或間接地通路檔案。
• 檔案系統（File system）：這一層處理檔案的邏輯結構及使用者指定的操作，如打開、關閉、讀、寫等。這一層還管理通路權限。
• 實體組織（Physical organization）：考慮到輔存裝置的實體磁道和扇區結構，對于檔案和記錄的邏輯通路必須轉換為實體外存位址。輔助存儲空間和記憶體緩沖區的配置設定通常也在這一層處理。

I/O緩沖

緩存（buffering）的原因：

• 處理器在I/O完成之前必須等待
• 在頁交換的過程中，某些頁必須駐留記憶體

緩存（buffer）：記憶體當中預留的一個區域，用來暫存I/O通訊的資料。

舉例：

• printf函數：可能有時候會出現明明在程式中寫了printf，但是并沒有如期望般那樣得到輸出結果。這是因為printf是一個帶緩沖的輸出列印。printf本身會調用一個系統調用，會産生程序切換，如果僅為了列印一句“Hello World”就使用程序切換，可以認為這是沒必要的。是以會當緩沖區滿了的時候再一次性列印出來。（如果必要，我們也可以用fflush去強制清除緩存，将其列印出來）
• 列印機：在使用列印機的時候可以看到計算機螢幕上顯示進度條（完成一頁、兩頁…），待到進度條完成之後，列印機才開始工作。進度條展示的其實就是将資料存儲到緩沖區的進度，當執行完成後，處理器就可以完成其他的任務去了，接下來才是列印機去通路緩沖區，将資料真實地列印出來。

優點：

• 可以讓CPU和I/O并行操作
• 減少中斷次數
• 提高CPU效率

緩沖的定義：在輸入請求發出前就開始執行輸入傳送，并且在輸出請求發出一段時間之後才開始執行輸出傳送。

光看定義可能有些不知所雲，往下看，慢慢體會。

在讨論各種緩沖方法之前，首先要區分兩類I/O裝置：

• 面向塊（Block-oriented）的I/O裝置：
  • 将資訊儲存到固定大小的塊中
  • 傳送過程中一次傳輸一塊
  • 通常可以通過塊号通路資料
  • 舉例：磁盤、錄音帶、USB智能卡
• 面向流（Stream-oriented）的I/O裝置：
  • 以位元組流的方式輸入\輸出資料
  • 舉例：終端、列印機、通信端口、滑鼠和其他訓示裝置及其他大多數非輔存裝置

單緩沖

• I/O裝置先将傳送的資料移入到系統緩沖區中（I/O → 記憶體）
• 上一步傳輸完成時，程序把該塊移動到使用者空間（記憶體 → 記憶體）
• 緊接着，根據局部性原理，會預先請求另一個資料塊，将其移入緩沖區（預讀；或預先輸入）

優點：

• 使用者程序可在下一資料塊讀取的同時，處理已讀入的資料塊
• 輸入發生在系統記憶體而非使用者程序記憶體，是以作業系統可以将該程序換出

缺點：

• 作業系統必須記錄給使用者程序配置設定系統緩沖區的情況

  作業系統維護使用者程序系統緩沖區。

• 交換邏輯也受到影響

  I/O操作所涉及的磁盤和用于交換的磁盤是同一個磁盤時，磁盤寫操作排隊等待将程序換出到同一個裝置上是沒有任何意義的。若試圖換出程序并釋放記憶體，則要在I/O操作完成後才能開始，而在這時，把程序換出到磁盤已經不再合适。

面向流的單緩沖：

• 每次傳送一行的方式或每次傳送一位元組的方式
• 使用者在終端每次輸入一行，用回車表示到達行尾
• 輸出到終端時也是類似地每次輸出一行

雙緩沖

• 在記憶體中為作業系統配置設定兩個系統緩沖區

• 輸入輸出交替使用

  在一個程序向一個緩沖區中傳送資料（從這個緩沖區中取資料）的同時，作業系統正在清空（或填充）另一個緩沖區，這種技術稱為雙緩沖（double buffering）或緩沖交換（buffer swapping）。

循環緩沖

• 記憶體中有兩個以上的緩沖區
• 每個單緩沖區是循環緩沖器的一個單元
• 平滑I/O操作和程序之間的資料流

磁盤排程

磁盤性能

磁盤的内部結構如下圖：

說明：為了讀或寫，磁頭必須定位于指定的磁道和該磁道中指定扇區的開始處。

磁盤性能參數：

• 尋道時間（Seek time ）：磁頭定位到磁道所需要的時間稱為尋道時間。
• 旋轉延遲（Rotational delay ）：磁頭到達扇區開始位置的時間稱為旋轉延遲。
• 傳輸時間（transfer time）：磁頭定位完成就開始讀操作或寫操作，這就是資料傳輸，傳輸的時間就是傳輸時間。

磁盤排程（重點）：

上圖為磁盤I/O傳送的一般時序圖：

等待I/O裝置 → 等待通道 → 尋道（确定磁道） → 旋轉延遲（确定扇區） → 資料傳輸延遲

相關計算：

傳輸時間：

T=brNT = \frac{b}{rN} T=rNb​

• T：傳輸時間
• b：要傳送的位元組數
• N：一個磁道中的位元組數
• r：旋轉速度（機關：轉/秒）

總平均存取時間：

Ta=Ts+12r+brNT_a = T_s + \frac{1}{2r} +\frac{b}{rN} Ta​=Ts​+2r1​+rNb​

• Ts：平均尋道時間

磁盤排程政策

不同磁盤排程的性能差異的原因可以追溯到尋道時間。是以為了提高性能，需要減少花費在尋道上的時間。

考慮多道程式環境中的一種典型情況：即作業系統為每個I/O裝置維護一個請求隊列。

• 對于一個磁盤來說，隊列中可能有來自多個程序的許多I/O請求（讀和寫）
• 随機排程（random scheduling）：随機通路磁道。該種方法性能最差，可用于評估其他技術。

下面我們将會介紹八種磁盤排程政策，在介紹時會統一以一個例子進行：

例子：

假設磁盤有200個磁道，磁盤請求隊列中是一些随機請求。被請求的磁道，按照磁盤排程程式的接收順序分别為：

55、58、39、18、90、160、150、38、184

說明：

假設以磁道号為100處開始尋道。

具體以折線圖的形式展示：縱軸表示磁盤上的磁道；橫軸表示時間（或跨越磁道的數量）。

優先級（Priority，PRI）

• 此方法不會優化磁盤的使用率
• 通常較短的批作業和互動作業的優先級較高
• 可以提供較好的互動響應時間

先進先出（First-in First-out，FIFO）

處理請求的順序（如下圖）：

55、58、39、18、90、160、150、38、184

• 這是最簡單的排程政策
• 按照收到請求的順序進行處理
• 優點：公平對待每個請求
• 缺點：并未對磁頭的通路有任何優化，效率最差。在多程序環境中，性能接近随機排程。

後進先出（Last-in First-out，LIFO）

處理請求的順序：

184、38、150、160、90、18、39、58、55

• 考慮到了局部性原理

  在事物處理系統中，由于順序讀取檔案的緣故，把裝置配置設定給最後到來的使用者，可減少磁臂的運動，甚至沒有磁臂運動。

• 缺點：可能會産生饑餓

  假設隊列中不停地有新的請求，那麼最先進入隊列的請求很可能饑餓。

最短服務時間優先（Shortest Service Time First ，SSTF）

處理請求的順序（如下圖）：

90、58、55、39、38、18、150、160、184

• 政策：選擇使磁頭臂從目前位置開始移動最少的磁盤I/O請求（如果兩個距離相等，随機選擇方向）

• 總是選擇最小尋道時間的請求

  考慮的名額太單一，并不能保證平均尋道時間最小

• 可能會産生饑餓

  如果不停有新的請求，該請求距離磁頭很近，那麼距離磁頭較遠的請求可能饑餓。

SCAN（掃描，電梯算法）

處理請求的順序（如下圖）：

55、58、39、18、90、160、150、38、184

• 政策：磁頭臂僅沿一個方向移動，并在途中滿足所有未完成的請求，直到它達到這個方向上的最後一個磁道，或者在這個方向上沒有其他請求為止，反轉掃描方向。

  考慮了局部性原理

  這種定向移動的形式類似于電梯，是以也被稱為“電梯算法”。

• 可以解決饑餓
• 問題：基于該例假設，假設在處理完184号磁道請求之後，磁頭反向掃描，這時又有新的185号磁道通路請求，那麼磁頭會掃描一輪之後再回來處理，顯然是不合理的。

C-SCAN（循環掃描）

處理請求的順序（如下圖）：

55、58、39、18、90、160、150、38、184

• 政策：将掃描方向固定。當通路到沿某個方向的最後一個磁道時，磁頭臂傳回到磁道相反方向末端的磁道。
• 可以解決SCAN的問題。減少了新請求的最大延遲。

N-step-SCAN

• 将磁盤請求隊列劃分為長度為N的n個子隊列
• 對于n個子隊列采取FIFO算法
• 對于子隊列中的N個請求，采取SCAN算法
• 如果有新的請求，将其添加到新的隊列中去

FSCAN

• 使用兩個子隊列
• 掃描開始時，所有請求都在一個隊列中，另一個隊列為空。
• 在掃描過程中，所有新到的請求都放入另一個隊列。

磁盤排程算法比較

比較FIFO、SSTF、SCANF、C-SCAN算法，如下圖：

注意：計算平均尋道時間時，注意分母的取值。

以FIFO為例

• 從磁道100處開始：

AVE = \frac{45+3+19+21+72+70+10+112+146}{9} = 55.3

• 從磁道55處開始：AVE = \frac{0+3+19+21+72+70+10+112+146}{9-1} = 56.625

注意磁頭開始的位置

RAID

受限于技術，磁盤存儲器的大小并不能無限擴大，雖然技術在不斷進步，其大小也在逐漸增大，但要意識到一個問題，現實中我們對于磁盤存儲的需求可能要遠遠大于其實際容量。

設計人員認識到這個問題，并提出了并行使用多個磁盤的方案。

獨立磁盤備援陣列（Redundant Array of Independent Disks，RAID）：

• 實體上通過多個磁盤組成一個磁盤組，在邏輯上這是一個大容量的磁盤
• 使用備援磁盤容量儲存奇偶檢驗資訊，保證在一個磁盤失效時，資料具有可恢複性

RAID包含0~6共七個級别，這裡僅介紹RAID0、RAID1、RAID5

RAID0

• 實作高資料傳送能力
• 實作告訴I/O請求率

RAID1

• 讀請求可由包含被請求資料的任何一個磁盤提供服務，而不管哪個磁盤擁有最小尋道時間和旋轉延遲。
• 寫請求需要對兩個響應的條帶進行更新，但這可并行完成。
• 從失效中恢複很簡單：當一個驅動器失效時，仍然可以從第二個驅動器通路到資料。

RAID5

• 把奇偶校驗條帶分布在所有磁盤中。

後記

本篇已完結

（如有修改或補充歡迎評論）