操作系統(tǒng)設(shè)計與實現(xiàn)(第三章)

1、操作系統(tǒng)設(shè)計與實現(xiàn)第三章 輸入/輸出系統(tǒng) 操作系統(tǒng)的功能，很大的一部分是花費在I/O設(shè)備的控制和管理上，它負(fù)責(zé)對龐雜的外部設(shè)備提供一個通用的簡易接口。它對外部設(shè)備作了一個分層次的管理，解決了各設(shè)備間的交互及各自的輸入/輸出操作。 每個類型的操作系統(tǒng)都是在對I/O的管理基礎(chǔ)上搭建起來的。*發(fā)展歷史第一代用鍵盤和打印機(jī)第二代用鼠標(biāo)和調(diào)制解調(diào)器（俗稱“貓”） 第三代用手寫筆和掃描儀等另外，還有眾多的專業(yè)領(lǐng)域的設(shè)備。*外部設(shè)備分類1.按使用特性分 存儲型設(shè)備 輸入型設(shè)備（外設(shè)主機(jī)） 輸出型設(shè)備（主機(jī)外設(shè)） 輸入輸出型設(shè)備2.按數(shù)據(jù)組織分 塊設(shè)備 以數(shù)據(jù)塊為單位存儲、傳輸信息 字符設(shè)備 以字符為單位存儲

2、、傳輸信息3.按外部設(shè)備的從屬關(guān)系分 系統(tǒng)設(shè)備 指操作系統(tǒng)生成時，登記在系統(tǒng)中的標(biāo)準(zhǔn)設(shè)備 （如終端、打印機(jī)、磁盤機(jī)等） 用戶設(shè)備 指在系統(tǒng)生成時，未登記在系統(tǒng)中的非標(biāo)準(zhǔn)設(shè)備。對于這類設(shè)備的處理程序由用戶提供，并將其納入系統(tǒng)，由系統(tǒng)代替用戶實施管理。 （如A/D，D/A轉(zhuǎn)換器，CAD所用專用設(shè)備）4. 按資源分配角度分 獨占設(shè)備 在一段時間內(nèi)只能有一個進(jìn)程使用的設(shè)備，一般為低速I/O設(shè)備。（如打印機(jī)，磁帶等） 共享設(shè)備 在一段時間內(nèi)可有多個進(jìn)程共同使用的設(shè)備，多個進(jìn)程以交叉的方式來使用設(shè)備，其資源利用率高。（如硬盤）虛設(shè)備 在一類設(shè)備上模擬另一類設(shè)備，常用共享設(shè)備模擬獨占設(shè)備，用高速設(shè)備模擬低速

3、設(shè)備，被模擬的設(shè)備稱為虛設(shè)備 （將慢速的獨占設(shè)備改造成多個用戶可共享的設(shè)備，提高設(shè)備的利用率）（為了提高資源利用率，如SPOOLing技術(shù)就使用了虛設(shè)備技術(shù)用硬盤模擬輸入輸出設(shè)備。） SPOOLing技術(shù) 為解決獨立設(shè)備數(shù)量少，速度慢，不能滿足眾多進(jìn)程的要求，而且在進(jìn)程獨占設(shè)備期間，設(shè)備利用率比較低而提出的一種設(shè)備管理技術(shù)。5.從程序使用角度分 邏輯設(shè)備 物理設(shè)備* 設(shè)備管理的目的和任務(wù)1. 按照用戶的請求，控制設(shè)備的各種操作，完成I/O設(shè)備與內(nèi)存之間的數(shù)據(jù)交換（包括設(shè)備分配與回收；設(shè)備驅(qū)動程序；設(shè)備中斷處理；緩沖區(qū)管理），最終完成用戶的I/O請求(1) 選擇和分配I/O設(shè)備，以便進(jìn)行數(shù)據(jù)傳輸

4、操作(2) 控制I/O設(shè)備與內(nèi)存之間交換數(shù)據(jù)2.向用戶提供使用外部設(shè)備的方便接口，使用戶擺脫繁瑣的編程負(fù)擔(dān) 方便性 友好界面 透明性3.充分利用各種技術(shù)（通道，中斷，緩沖等）提高CPU與設(shè)備、設(shè)備與設(shè)備之間的并行工作能力，充分利用資源，提高資源利用率 并行性 均衡性（使設(shè)備充分忙碌）*I/O管理的重要性1. 沒有I/O設(shè)備的計算機(jī)就像一個沒有輪子的汽車2. I/O性能經(jīng)常成為系統(tǒng)性能的瓶頸 (1)CPU性能不等于系統(tǒng)性能，響應(yīng)時間也是一個重要因素 (2)CPU性能越高，與I/O差距越大； 彌補(bǔ)：更多的進(jìn)程 (3)進(jìn)程切換多，系統(tǒng)開銷大；3. 操作系統(tǒng)龐大復(fù)雜的原因之一是：資源多、雜，并發(fā)，均來

5、自I/O4 . 理解I/O的工作過程與結(jié)構(gòu)是理解操作系統(tǒng)的工作過程與結(jié)構(gòu)的關(guān)鍵。4. 保證在多道程序環(huán)境下，當(dāng)多個進(jìn)程競爭使用設(shè)備時，按一定策略分配和管理各種設(shè)備，使系統(tǒng)能有條不紊的工作5. 與設(shè)備無關(guān)性（設(shè)備獨立性） 用戶在編制程序時，使用邏輯設(shè)備名，由系統(tǒng)實現(xiàn)從邏輯設(shè)備到物理設(shè)備（實際設(shè)備）的轉(zhuǎn)換 用戶能獨立于具體物理設(shè)備而方便的使用設(shè)備 用戶申請使用設(shè)備時，只需要指定設(shè)備類型，而無須指定具體物理設(shè)備，系統(tǒng)根據(jù)當(dāng)前的請求，及設(shè)備分配的情況，在相同類別設(shè)備中，選擇一個空閑設(shè)備，并將其分配給一個申請進(jìn)程 統(tǒng)一性： 對不同的設(shè)備采取統(tǒng)一的操作方式，在用戶程序中使用的是邏輯設(shè)備優(yōu)點： 設(shè)備忙碌或設(shè)

6、備故障時，用戶不必修改程序改善了系統(tǒng)的可適應(yīng)性和可擴(kuò)展性*設(shè)備管理的任務(wù)按用戶需求提出的要求接入外部設(shè)備，系統(tǒng)按一定算法分配和管理控制，而用戶不必關(guān)心設(shè)備的實際地址和控制指令.盡量提高輸入輸出設(shè)備的利用率，例如，發(fā)揮主機(jī)與外設(shè)以及外設(shè)與外設(shè)之間的真正并行工作能力.*設(shè)備管理的功能 設(shè)備分配與回收 記錄設(shè)備的狀態(tài) 根據(jù)用戶的請求和設(shè)備的類型，采用一定的分配算法，選擇一條數(shù)據(jù)通路 分配設(shè)備：按設(shè)備的不同類型和操作系統(tǒng)選用的算法分配。包括分配相應(yīng)的通道、設(shè)備控制器以及對未分配到的任務(wù)或怍業(yè)進(jìn)行排隊等；控制和實現(xiàn)真正的輸入輸出操作。包括通道程序控制、啟動設(shè)備、及時響應(yīng)及處理中斷訊號等；對輸入輸出緩沖區(qū)

7、進(jìn)行管理。例如邏輯名的管理，多個緩沖區(qū)的分時以及串并行操作，同類多個外部設(shè)備的均衡工作，避免“忙的忙”和“閑的閑”；在一些較大系統(tǒng)中實現(xiàn)虛擬設(shè)備技術(shù)（虛擬硬盤、虛擬內(nèi)存）。3.1 I/O硬件原理 I/O設(shè)備對不同的人有不同的理解，設(shè)計硬件的人員和對硬件編程的人員以及用戶都有不同的觀點和見解，我們主要分析如何對這些設(shè)備編程控制，更好地使設(shè)備之間協(xié)調(diào)工作，即主要從程序員的角度來分析它。3.1.1 I/O設(shè)備 對于Linux/UNIX來說，I/O設(shè)備主要分為兩類：塊設(shè)備（block device）和字符(character device)設(shè)備。 塊設(shè)備將信息存放在可尋址的固定大小的數(shù)據(jù)塊中，數(shù)據(jù)塊大

8、小的范圍常從512字節(jié)到32768字節(jié)。特征：能夠獨立地讀寫單個數(shù)據(jù)塊 - (涉及到了尋址操作) 字符設(shè)備可以接受或發(fā)送字符流，主要的設(shè)備有打印機(jī)、調(diào)制解調(diào)器等設(shè)備。這是種不合理的分法，比如 時鐘 無法尋址也無法發(fā)送接收字符流，但它可以把控制不同I/O設(shè)備的操作系統(tǒng)軟件成分隔離開來。 如文件系統(tǒng)主要負(fù)責(zé)磁盤相關(guān)的塊設(shè)備。3.1.2 設(shè)備控制器 I/O設(shè)備一般由機(jī)械和電子兩部分組成。把這兩部分分開處理，以提供更加模塊化，更加通用的設(shè)計： * 機(jī)械部分是設(shè)備本身； * 電子部分叫做設(shè)備控制器或適配器。 在小型和微型機(jī)中，它常采用印刷電路卡插入計算機(jī)中。 控制器卡上通常有一個插座，通過電纜與設(shè)備相連

9、； 控制器和設(shè)備之間的接口是一個標(biāo)準(zhǔn)接口，它符合ANSI、IEEE或ISO這樣的國際標(biāo)準(zhǔn)。 關(guān)注點：對該硬件如何進(jìn)行程序設(shè)計，不考慮設(shè)備內(nèi)部如何工作 程序員：軟件接口 即硬件所接受的命令，它所完成的功能，出錯信息等。 因此我們所關(guān)心的就是控制器，因為它和操作系統(tǒng)打交道，也就是我們要分析的重點。*設(shè)備接口 一次完整的I/O傳送過程，是由一系列信號組成，這些信號啟動設(shè)備所執(zhí)行的操作，并通過測試設(shè)備狀態(tài)來監(jiān)控設(shè)備操作的進(jìn)展 。 一個I/O過程由四步組成： * 準(zhǔn)備 * 啟動 * 測試和等待 * 結(jié)果檢查和錯誤處理 這個過程均是通過對設(shè)備接口寄存器組的讀寫來完成* 設(shè)備連接模式 指I/O設(shè)備與CPU之

10、間的連接方式，亦即將設(shè)備連接到一個計算機(jī)系統(tǒng)上的方式。在一個確定的連接模式下，從I/O設(shè)備到CPU間的所有連接成分構(gòu)成了一條I/O路徑（I/O鏈）。1.設(shè)備與主機(jī)間最基本的連接方式 四個要素： 設(shè)備接口形式 I/O指令形式 I/O地址空間分配及譯碼 連線問題CPU內(nèi)存(1)設(shè)備接口形式 * 端口地址譯碼 * 按照主機(jī)與設(shè)備的約定格式和過程接受或發(fā)送數(shù)據(jù)和信號 計算機(jī) 設(shè)備 設(shè)備 計算機(jī) * 將計算機(jī)的數(shù)字信號轉(zhuǎn)換為機(jī)械部分能識別的模擬信號，或反過來 (2) I/O指令形式與I/O地址是相互關(guān)聯(lián)的，主要有兩種形式： 內(nèi)存映像I/O模式 I/O專用指令要考慮的幾個問題：設(shè)備完成技術(shù)：系統(tǒng)如何知道設(shè)

11、備的一次I/O操作是否完成？對CPU編程的I/O技術(shù)：CPU必須親自完成I/O的啟動與完成的處理，親自執(zhí)行所有數(shù)據(jù)在內(nèi)存和設(shè)備之間的實際物理傳送進(jìn)一步改善：*使CPU利用率盡可能不被I/O降低，使CPU脫離I/O的負(fù)擔(dān)* 提高I/O本身的絕對速度* 減少或緩解速度差距* 使CPU不等待I/O* 使CPU盡可能擺脫I/O* 提高設(shè)備利用率* 在設(shè)備與主機(jī)的硬連接上，引入總線，節(jié)省連線并提供配置擴(kuò)充與改變時的靈活性；引入控制器，擴(kuò)大設(shè)備與主機(jī)間的相互適用范圍- 總線的引入2.總線 將計算機(jī)系統(tǒng)中的各個子系統(tǒng)（CPU、內(nèi)存、外設(shè)等）相互連接，且連接是共享的。 好處：低成本（一線多用） 靈活性（易于增

12、加設(shè)備 便于兩個計算機(jī)系統(tǒng)之間共享外設(shè)）總線的缺點： 本身形成了通訊瓶頸，限制I/O吞吐量總線分類： 數(shù)據(jù)總線、地址總線、控制總線控制器，即設(shè)備的電子部分,完成設(shè)備與主機(jī)間的連接和通訊CPU與控制器間通訊： 單總線模型（微機(jī)、小型機(jī)） 多總線模型（中、大型機(jī)）-I/O通道控制器與設(shè)備的接口是一種低層次的接口：*比如從硬盤讀信息，讀出的是一個比特流，其中包括磁盤數(shù)據(jù)、扇區(qū)大小、校驗碼等信息，讀出來后由控制器對這些串行的比特流進(jìn)行轉(zhuǎn)換，并進(jìn)行校驗，最后裝入主存。*對顯示器的顯示，由CRT終端控制器從內(nèi)存中讀出要顯示的字符的字節(jié)流，然后產(chǎn)生來調(diào)制產(chǎn)生射線的信號，并最終將結(jié)果顯示出來?？刂破髋cCPU的

13、聯(lián)系每個控制器都有一些用來和CPU通信的寄存器，如果把這些寄存器放入內(nèi)存，即內(nèi)存映像I/O(這點在顯卡上尤為突出)。每個控制器還可以利用終端來通知CPU他們所承擔(dān)的任務(wù)的開始或結(jié)束。即固定設(shè)備中斷。(如網(wǎng)卡，ISA口的網(wǎng)卡)CPU通過向控制器的寄存器中寫入信息來控制這些設(shè)備工作。DMA（direct memory access） 數(shù)據(jù)在內(nèi)存與I/O設(shè)備間的直接成塊傳送 CPU在開始時向設(shè)備發(fā)“傳送一塊”命令，結(jié)束時進(jìn)行相應(yīng)處理，實際操作由DMA硬件直接完成 DMA需要附加的輔助硬件，且該DMA硬件屬于設(shè)備的電子部分的功能（由控制器實現(xiàn)）。許多控制器，尤其是塊設(shè)備控制器都支持DMA。 3.1.3

14、 存儲器直接存取例如：對磁盤進(jìn)行訪問 不用DMA時，磁盤如何讀：首先，控制器從磁盤驅(qū)動器串行地一位一位地讀一個塊，直到將整塊信息放入控制器的內(nèi)部緩沖區(qū)中。其次，它做個校驗計算，以核實沒有讀錯誤發(fā)生。然后控制器產(chǎn)生一個中斷。CPU響應(yīng)中斷，控制轉(zhuǎn)給操作系統(tǒng)。當(dāng)操作系統(tǒng)開始運(yùn)行時，它重復(fù)地從控制器緩沖區(qū)中一次一個字節(jié)或一個字地讀這個磁盤塊的信息，并將其送入內(nèi)存中 采用DMA方式時，允許DMA控制器接管地址線的控制權(quán)，直接控制DMA控制器與內(nèi)存的數(shù)據(jù)交換。從而使磁盤設(shè)備與存儲器之間的數(shù)據(jù)傳送不需要CPU介入，因而減輕了CPU負(fù)擔(dān)； 當(dāng)采用DMA時，除向控制器提供要讀數(shù)據(jù)塊的磁盤地址外，還要向控制器提

15、供兩個信息：數(shù)據(jù)塊送往內(nèi)存的起始地址和要傳送的字節(jié)數(shù)。 當(dāng)DMA硬件控制磁盤與存儲器之間進(jìn)行信息交換時，每當(dāng)磁盤把一個數(shù)據(jù)讀入控制器的數(shù)據(jù)緩沖區(qū)時，DMA控制器取代CPU，接管地址總線的控制權(quán)，并按照DMA控制器中的存儲器地址寄存器內(nèi)容把數(shù)據(jù)送入相應(yīng)的內(nèi)存單元中。然后，DMA硬件自動地把傳送字節(jié)計數(shù)器減1，把存儲器地址寄存器加1，DMA控制器對每一個傳送的數(shù)據(jù)重復(fù)上述過程，直到傳送字節(jié)計數(shù)器為“0”時，向CPU產(chǎn)生一個中斷信號。當(dāng)操作系統(tǒng)接管CPU控制權(quán)時，再無需做塊復(fù)制的工作了。CPU向控制器發(fā)出啟動DMA通知和有關(guān)參數(shù)控制器向內(nèi)存發(fā)出詢問請求訪問內(nèi)存（讀、寫）計數(shù)器減1結(jié)束否發(fā)中斷NYDM

16、A的實現(xiàn)流程使用DMA的優(yōu)點: 通過讓控制器進(jìn)行數(shù)據(jù)的第一步收集校驗，可以緩解設(shè)備之間對總線的控制權(quán)的爭奪，因為，一旦不用DMA這種方式，當(dāng)開始傳輸時，總線的控制權(quán)必須長時間被此控制器所獲得，而長時間的占用會使大量其他任務(wù)阻塞；而他們本身也會因為傳送和讀取的速度的差異，會使本身的結(jié)構(gòu)設(shè)計復(fù)雜化。通過這種內(nèi)部的緩沖機(jī)制，使得在啟動DMA傳送前完全不使用總線，而自己本身的設(shè)計也就自然簡化起來。類共享區(qū)域的管理-磁盤塊的交叉編址 當(dāng)數(shù)據(jù)從控制器被傳到內(nèi)存時，控制器本身也正在讀扇區(qū)上的信息時，控制器就可以被認(rèn)為是一個共享的區(qū)域，而這時就會出現(xiàn)競爭。此時只能滿足一方要求，即要么數(shù)據(jù)從磁盤到控制器，要么數(shù)

17、據(jù)從控制器到內(nèi)存。 如果數(shù)據(jù)從控制器到內(nèi)存，而數(shù)據(jù)仍需要被讀取，則必然會發(fā)生數(shù)據(jù)丟失的情況，需要用一些方法來避免-即隔一個數(shù)據(jù)塊讀一個（因為硬盤是連續(xù)轉(zhuǎn)動的，不可能停止）或幾個的方案。 對于a圖進(jìn)行編址，控制器只能做到隔一個塊讀取一個的速度，則讀完全部的信息需要磁盤旋轉(zhuǎn)8周，此時b圖只需要2周，對于c圖，主要是針對從控制器向內(nèi)存?zhèn)鲾?shù)據(jù)比從硬盤向控制器傳數(shù)據(jù)慢的情況。未編碼單交叉編碼雙交叉編碼有關(guān)技術(shù) 通道技術(shù)： 定義：通道是獨立于CPU的專門負(fù)責(zé)數(shù)據(jù)輸入/輸出傳輸工作的處理機(jī)，對外部設(shè)備實現(xiàn)統(tǒng)一管理，代替CPU對輸入/輸出操作進(jìn)行控制，從而使輸入，輸出操作可與CPU并行操作。 引入通道的目的：

18、 為了使CPU從I/O事務(wù)中解脫出來，同時為了提高CPU與設(shè)備，設(shè)備與設(shè)備之間的并行工作能力。分類1) 字節(jié)多路通道 字節(jié)多路通道以字節(jié)為單位傳輸信息，它可以分時地執(zhí)行多個通道程序。當(dāng)一個通道程序控制某臺設(shè)備傳送一個字節(jié)后，通道硬件將控制轉(zhuǎn)去執(zhí)行另一個通道程序，控制另一臺設(shè)備傳送信息。 主要連接以字節(jié)為單位的低速I/O設(shè)備。如打印機(jī)，終端。 以字節(jié)為單位交叉?zhèn)鬏?，?dāng)一臺傳送一個字節(jié)后，立即轉(zhuǎn)去為另一臺傳送字節(jié)。 2)選擇通道 選擇通道是以成組方式工作的，即每次傳送一批數(shù)據(jù)，故傳送速度很高。選擇通道在一段時間內(nèi)只能執(zhí)行一個通道程序，只允許一臺設(shè)備進(jìn)行數(shù)據(jù)傳輸。 當(dāng)這臺設(shè)備數(shù)據(jù)傳輸完成后，再選擇與

19、通道連接的另一臺設(shè)備，執(zhí)行它的相應(yīng)的通道程序。 主要連接磁盤，磁帶等高速I/O設(shè)備。選擇通道 3)成組多路通道 它結(jié)合了選擇通道傳送速度高和字節(jié)多路通道能進(jìn)行分時并行操作的優(yōu)點。它先為一臺設(shè)備執(zhí)行一條通道指令，然后自動轉(zhuǎn)接，為另一臺設(shè)備執(zhí)行一條通道指令。 主要連接高速設(shè)備 這樣，對于連接多臺磁盤機(jī)的數(shù)組多路通道，它可以啟動它們同時執(zhí)行移臂定位操作，然后，按序交叉地傳輸一批批數(shù)據(jù)。數(shù)據(jù)多路通道實際上是對通道程序采用多道程序設(shè)計的硬件實現(xiàn)。3.2 I/O軟件原理 IO軟件的基本思想是按分層的思想構(gòu)成，較低層軟件要使較高層軟件獨立于硬件的特性，較高層軟件則要向用戶提供一個友好的、清晰的、簡單的、功能

20、更強(qiáng)的接口。 3.2.1 I/O軟件的目標(biāo) 在設(shè)計IO軟件時的一個關(guān)鍵概念是設(shè)備獨立性。用戶在編寫使用軟盤或硬盤上文件的程序時，無需考慮設(shè)備類型和特性。*設(shè)備無關(guān)性： 與設(shè)備獨立性密切相關(guān)的是統(tǒng)一命名(uniform naming)這一目標(biāo)。一個文件或一個設(shè)備的名字只應(yīng)是一個簡單的字符串或一個整數(shù)，不應(yīng)依賴于設(shè)備. 如簡單的輸入： sort output 此時操作系統(tǒng)能夠從各種設(shè)備上獲得輸入，也可以做同樣的輸出。設(shè)備的驅(qū)動和設(shè)備間的差異性均由操作系統(tǒng)本身來處理。* 錯誤處理 出錯處理是I/O軟件的另一個目標(biāo)。一般來說，數(shù)據(jù)傳輸中的錯誤應(yīng)盡可能地在接近硬件層上處理。由控制器盡可能地處理它所遇到的

21、問題，如果它真的處理不了，再交給設(shè)備的驅(qū)動程序，去再進(jìn)行一次重復(fù)操作。如對磁盤的讀取。 盡量把錯誤交給底層的軟件來處理，只有底層軟件處理不了的時候再交給較高一層的軟件來處理。* 異步同步問題 大多數(shù)物理I/O是異步傳輸，即CPU在啟動傳輸后便轉(zhuǎn)向其他工作。如何在系統(tǒng)中實現(xiàn)異步，需要實現(xiàn)阻塞和喚醒機(jī)制，操作系統(tǒng)中需要有此模擬，是通過中斷來實現(xiàn)的，利用中斷來實現(xiàn)阻塞和喚醒，實現(xiàn)符合硬件的異步傳輸。 *獨占與共享 由于一些設(shè)備是獨占設(shè)備(打印機(jī))，有些設(shè)備是共享設(shè)備(磁盤)，故操作系統(tǒng)需要能夠同時處理這些設(shè)備。 針對以上目標(biāo)，通常將I/O軟件組織成如下的幾個層次，使操作系統(tǒng)能夠合理高效地實現(xiàn)上述目標(biāo)

22、。 1. 中斷處理程序（底層）； 2. 設(shè)備驅(qū)動程序； 3. 與設(shè)備無關(guān)的操作系統(tǒng)軟件； 4. 用戶層軟件（高層）。3.2.2 中斷處理程序 *每個進(jìn)程在啟動一個I/O操作后阻塞； *直到I/O操作完成并產(chǎn)生一個中斷； *由操作系統(tǒng)接管CPU后喚醒該進(jìn)程為止。為了將中斷放入底層，需要做一定的隱藏，如進(jìn)行I/O操作的進(jìn)程將自己掛起，等到I/O操作完成后進(jìn)行中斷。掛起的方法常見的有：執(zhí)行信號量的DOWN操作、條件變量的WAIT操作，或者消息的RECEIVE操作。中斷發(fā)生時，中斷處理程序解除進(jìn)程的阻塞狀態(tài)。3.2.3 設(shè)備驅(qū)動程序 與設(shè)備密切相關(guān)的代碼放在設(shè)備驅(qū)動程序中，每個設(shè)備驅(qū)動程序處理一種設(shè)備

23、類型。 每一個控制器都設(shè)有一個或多個設(shè)備寄存器，用來存放向設(shè)備發(fā)送的命令和參數(shù)。設(shè)備驅(qū)動程序負(fù)責(zé)發(fā)出這些命令，并監(jiān)督它們正確執(zhí)行。 一般，設(shè)備驅(qū)動程序的任務(wù)是接收來自與設(shè)備無關(guān)的上層軟件的抽象請求，并執(zhí)行這個請求。 在設(shè)備驅(qū)動程序的進(jìn)程發(fā)出一條或多條命令后，系統(tǒng)有兩種處理方式，多數(shù)情況下，執(zhí)行設(shè)備驅(qū)動程序的進(jìn)程必須等待命令完成。 這樣，在命令開始執(zhí)行后，它阻塞自已，直到中斷處理時將它解除阻塞為止（此時，一般驅(qū)動程序需要等待控制器完成一定的操作，故阻塞自己）。而在其它情況下，命令執(zhí)行不必延遲就很快完成，所以驅(qū)動程序不需要阻塞（如在一些圖形卡上滾動屏幕只需要寫少許字節(jié)到控制器的寄存器中，由于不需要

24、機(jī)械運(yùn)行，所以整個操作能在幾微秒內(nèi)完成。）。 3.2.4 與設(shè)備無關(guān)的I/O軟件 雖然I/O軟件中一部分是設(shè)備專用的，但大部分軟件是與設(shè)備無關(guān)的。設(shè)備驅(qū)動程序與設(shè)備獨立軟件之間的確切界限是依賴于具體系統(tǒng)的。 1.獨立于設(shè)備的軟件的基本任務(wù)是實現(xiàn)所有設(shè)備都需要的功能，并且向用戶級軟件提供一個統(tǒng)一的接口。 2.如何給文件和設(shè)備這樣的對象命名是操作系統(tǒng)中的一個主要課題。獨立于設(shè)備的軟件負(fù)責(zé)把設(shè)備的符號名映射到正確的設(shè)備驅(qū)動上。3.設(shè)備保護(hù) 系統(tǒng)如何防止無權(quán)存取設(shè)備的用戶存取設(shè)備呢？ 對設(shè)備文件的rwx進(jìn)行控制，但一般的系統(tǒng)中都不允許訪問。 4.不同的磁盤可以采用不同的扇區(qū)尺寸。向較高層軟件掩蓋這一事

25、實并提供大小統(tǒng)一的塊尺寸，這正是設(shè)備獨立軟件的一個任務(wù)。它可將若干扇區(qū)合成一個邏輯塊。這樣，較高層的軟件只與抽象設(shè)備打交道，獨立于物理扇區(qū)的尺寸而使用等長的邏輯塊。 5.緩沖技術(shù) 6.設(shè)備分配 7.出錯處理 3.2.5 用戶空間的I/O軟件 盡管大部分I/O軟件都包含在操作系統(tǒng)中，但仍有一小部分是由與用戶程序連接在一起的庫過程，甚至完全由運(yùn)行于核外的程序構(gòu)成。系統(tǒng)調(diào)用，包括I/O系統(tǒng)調(diào)用，通常由庫過程實現(xiàn)。 這些過程所做的工作只是將系統(tǒng)調(diào)用時所用的參數(shù)放在合適的位置，由其它的I/O過程實現(xiàn)真正的操作。（1）用戶進(jìn)程層執(zhí)行輸入輸出系統(tǒng)調(diào)用，對I/O數(shù)據(jù)進(jìn)行格式化，為假脫機(jī)輸入輸出作準(zhǔn)備；（2）獨

26、立于設(shè)備的軟件實現(xiàn)設(shè)備的命名、設(shè)備的保護(hù)、成塊處理、緩沖技術(shù)和設(shè)備分配；（3）設(shè)備驅(qū)動程序設(shè)置設(shè)備寄存器、檢查設(shè)備的執(zhí)行狀態(tài)；（4）中斷處理程序負(fù)責(zé)IO完成時，喚醒設(shè)備驅(qū)動程序進(jìn)程，進(jìn)行中斷處理；（5）硬件層實現(xiàn)物理IO的操作。3.3 死鎖死鎖的現(xiàn)象*死鎖的定義： 一組進(jìn)程中，每個進(jìn)程都無限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無法得到資源，這種現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程。死鎖（Deadlock）饑餓（Starvation）*關(guān)于死鎖的一些結(jié)論： 參與死鎖的進(jìn)程最少是兩個； （兩個以上進(jìn)程才會出現(xiàn)死鎖） 參與死鎖的進(jìn)程至少有兩個已經(jīng)占有資源； 參與死鎖的所有進(jìn)程都在等待

27、資源；注： 如果死鎖發(fā)生，會浪費大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。3.3.1資源 資源是在任何時刻只能被單個進(jìn)程使用的對象 可剝奪式資源 不可剝奪式資源 對于打印的過程（可剝奪式資源是存儲器，不可剝奪式資源是打印機(jī)） 對于任一個資源，它本身必存在一個固定的模式。“被申請被分配被使用被釋放”模式。 對于可剝奪式資源： 可以將可能存在死鎖的情況避免，比如說直接剝奪它本身已經(jīng)占有的資源，故，這種潛在威脅是可以在一定程度上獲通過某些手段來避免；對于不可剝奪式資源，由于無法在尚未導(dǎo)致失敗的情況下剝奪其資源，如果強(qiáng)行剝奪資源，則會使當(dāng)前的任務(wù)出現(xiàn)混亂。而死鎖的發(fā)生也正是直接與不可剝奪式資源相關(guān)，故需要分析處

28、理的是不可剝奪式資源可能導(dǎo)致的潛在死鎖。3.3.2 死鎖的原理一般來說，死鎖時，沒有一個進(jìn)程可以觸發(fā)那個能夠喚醒本集合中另一個進(jìn)程的時間，所以所有的進(jìn)程都將永遠(yuǎn)等待下去。*發(fā)生死鎖的四個必要條件：1 .互斥使用，每一資源或者已被分配給一個進(jìn)程，或者空閑；（資源獨占）2 .保持和等待，一個進(jìn)程在申請新的資源的同時保持對原有資源的占有； （只有這樣才是動態(tài)申請，動態(tài)分配）3 .不可強(qiáng)占,資源申請者不能強(qiáng)行的從資源占有者手中奪取資源，資源只能由占有者自愿釋放；4 .循環(huán)等待，即必然有一條由兩個或多個進(jìn)程組成的循環(huán)鏈，鏈中每個進(jìn)程都在等待相鄰進(jìn)程占用的資源。 存在一個進(jìn)程等待隊列 P1 , P2 ,

29、, Pn, 其中P1等待P2占有的資源，P2等待P3占有的資源，Pn等待P1占有的資源，形成一個進(jìn)程等待環(huán)路。*死鎖模型-有向圖a：表示，進(jìn)程A已經(jīng)占有了資源R;b：表示進(jìn)程B在申請資源S;c：表示進(jìn)程D在獲得了資源T后，再申請資源U，而此時進(jìn)程C也在獲得了資源U后，正在申請資源T。*死鎖模型-資源圖單個或分開執(zhí)行操作系統(tǒng)不分配資源給B進(jìn)程，這樣就會避免死鎖。* 死鎖的解決方案1. 產(chǎn)生死鎖的例子 申請不同類型資源產(chǎn)生死鎖 P1：申請打印機(jī)申請掃描儀使用釋放打印機(jī)釋放掃描儀P2：申請掃描儀申請打印機(jī)使用釋放打印機(jī)釋放掃描儀申請同類資源產(chǎn)生死鎖（如內(nèi)存） 設(shè)有資源R，R有m個分配單位，由n個進(jìn)程

30、P1,P2,Pn（n m）共享。假設(shè)每個進(jìn)程對R的申請和釋放符合下列原則： * 一次只能申請一個單位 * 滿足總申請后才能使用 * 使用完后一次性釋放申請同類資源產(chǎn)生死鎖（如內(nèi)存）m=2，n=3資源分配不當(dāng)導(dǎo)致死鎖產(chǎn)生* 處理死鎖的方法1 .忽略死鎖的發(fā)生；2 .檢測死鎖并恢復(fù)；3 .謹(jǐn)慎對資源進(jìn)行動態(tài)分配，避免死鎖；4 .通過破壞上述四個必要條件來預(yù)防死鎖的發(fā)生。3.3.3 鴕鳥算法 最簡單的方法就是鴕鳥算法：把頭埋到沙子里，假裝根本沒有問題發(fā)生。對死鎖問題的看法：1. 數(shù)學(xué)家們認(rèn)為不管花多大代價也要徹底防止死鎖的發(fā)生 ；2. 工程師們則想要了解死鎖發(fā)生的頻率、系統(tǒng)因各種原因崩潰的頻率以及死

31、鎖的嚴(yán)重程度。 解決死鎖問題通常要花很大代價，而且會給進(jìn)程帶來許多不便的限制。 一般來說，死鎖發(fā)生的概率是很小的。3.3.4 死鎖的檢測和恢復(fù) 主要監(jiān)測資源的申請和釋放，并根據(jù)當(dāng)前的資源使用情況來判斷此時系統(tǒng)中是否存在環(huán)路，如果存在，就取消掉其中的一個進(jìn)程，如果不存在則繼續(xù)。 或者更簡單，不去維護(hù)資源，而是去判斷進(jìn)程是否連續(xù)阻塞超過了預(yù)定的時間，如果有這樣的進(jìn)程，就將它取消。 3.3.5 死鎖預(yù)防定義： 在系統(tǒng)設(shè)計時確定資源分配算法，保證不發(fā)生死鎖。具體的做法是破壞產(chǎn)生死鎖的四個必要條件之一。破壞“互斥使用”條件 對于打印機(jī)這類設(shè)備，利用假脫機(jī)等技術(shù)來避免進(jìn)程之間的資源競爭。破壞“請求和保持”

32、條件 要求每個進(jìn)程在運(yùn)行前必須一次性申請它所要求的所有資源，且僅當(dāng)該進(jìn)程所要資源均可滿足時才給予一次性分配。 另一方案，當(dāng)進(jìn)程申請時，先釋放掉自己的資源再進(jìn)行申請，當(dāng)申請成功后再收回剛才自己的資源。問題： 對于第一種方案，資源數(shù)目的判斷只有在運(yùn)行時才知道，而且效率無法提高。破壞“循環(huán)等待”條件 采用資源有序分配法： 把系統(tǒng)中所有資源編號，進(jìn)程在申請資源時必須嚴(yán)格按資源編號的遞增次序進(jìn)行，否則操作系統(tǒng)不予分配。破壞“不可剝奪”條件 在允許進(jìn)程動態(tài)申請資源前提下規(guī)定，一個進(jìn)程在申請新的資源不能立即得到滿足而變?yōu)榈却隣顟B(tài)之前，必須釋放已占有的全部資源，若需要再重新申請。此時進(jìn)程A、B分別占有資源i、

33、j，如果死鎖，即只有當(dāng)構(gòu)成環(huán)路時才會有，即A申請j，B申請i，但是如果有了編號，規(guī)定了進(jìn)程申請資源必須按照編號的順序，則會；ij，不允許A申請；ij，不允許B申請，這樣就避免了死鎖。死鎖預(yù)防的方法：3.3.6 死鎖避免定義： 在系統(tǒng)運(yùn)行過程中，對進(jìn)程發(fā)出的每一個資源申請進(jìn)行動態(tài)檢查，并根據(jù)檢查結(jié)果決定是否分配資源，若分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配。安全狀態(tài)與不安全狀態(tài)安全狀態(tài)： 如果存在一個由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，Pn，則系統(tǒng)處于安全狀態(tài)。安全序列： 一個進(jìn)程序列P1，Pn是安全的，如果對于每一個進(jìn)程Pi(1in），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所

34、有進(jìn)程Pj (j i )當(dāng)前占有資源量之和，系統(tǒng)處于安全狀態(tài)。 (安全狀態(tài)一定是沒有死鎖發(fā)生的)安全狀態(tài)與不安全狀態(tài)不安全狀態(tài):不存在一個安全序列，不安全狀態(tài)一定導(dǎo)致死鎖* 資源軌跡圖pqI1I2I3I4ArtI5I6I7I8Bs打印機(jī)繪圖儀繪圖儀打印機(jī) u 兩進(jìn)程均結(jié)束Dijkstra（1965）提出了一種能夠避免死鎖的調(diào)度算法，稱為銀行家算法。它的模型基于一個小城鎮(zhèn)的銀行家，他向一群客戶分別承諾了一定的貸款額度。銀行家不必為了能在同一時間借給每一個客戶滿額的貸款而在手頭上保存足夠的現(xiàn)金。銀行家算法銀行家算法(單種資源)問題描述：基本思想：在每個資源請求發(fā)出時對這個請求進(jìn)行考察，檢查滿足這一

35、請求時是否會達(dá)到安全狀態(tài)。如果能達(dá)到，那么就滿足該請求；如果不能達(dá)到，那么就推遲這一請求。為了判斷狀態(tài)是否安全，銀行家看他是否有足夠的資源來滿足某一個客戶。如果有，那么這筆貸款被認(rèn)為是能夠收回的，并且最接近最大限額的客戶將被檢查，依次類推。如果所有的貸款最終都被收回，那么該狀態(tài)是安全的，最初的請求可以批準(zhǔn)。銀行家算法銀行家算法當(dāng)進(jìn)程pi提出資源申請時，系統(tǒng)執(zhí)行下列步驟：（1）若RequestiNeedi,轉(zhuǎn)（2）； 否則錯誤返回（2）若RequestiAvailable, 轉(zhuǎn)（3）；否則進(jìn)程等待(3）假設(shè)系統(tǒng)分配了資源，則有：Available:=Available-Requesti;Allo

36、cationi:= Allocationi+Requesti;Needi:=Needi-Requesti若系統(tǒng)新狀態(tài)是安全的，則分配完成若系統(tǒng)新狀態(tài)是不安全的，則恢復(fù)原狀態(tài)，進(jìn)程等待銀行家算法為進(jìn)行安全性檢查，定義數(shù)據(jù)結(jié)構(gòu)：Work: integer;Finish:ARRAY1.n of Boolean;銀行家算法安全性檢查的步驟：(1) Work:=Available; Finish:=false;(2) 尋找滿足條件的i： a.Finishi=false; b.NeediWork;如果不存在，則轉(zhuǎn)(4)銀行家算法(3) Work:=Work+Allocationi; Finishi:=tr

37、ue; 轉(zhuǎn)(1)(4) 若對所有i,Finishi=true,則系統(tǒng)處于安全狀態(tài)，否則處于不安全狀態(tài)R1R2R3R4A3011B0100C1110D1101E0000R1R2R3R4A1100B0112C3100D0010E2110 E=(6,3,4,2) 總資源 P=(5,3,2,2) 已分配資源 A=(1,0,2,0) 剩余資源多種資源檢查一個狀態(tài)是否安全的算法描述如下：查找右邊矩陣中是否有一行，其未被滿足的資源數(shù)均小于或等于A。如果不存在這樣的行，則系統(tǒng)將死鎖，因為任何進(jìn)程都無法運(yùn)行結(jié)束。若找到這樣一行，則可以假設(shè)它獲得所需的資源并運(yùn)行結(jié)束，將該進(jìn)程標(biāo)記為結(jié)束，并將資源加到向量A上。重復(fù)

38、以上兩步，直到所有的進(jìn)程都標(biāo)記為結(jié)束。若能達(dá)到這種狀態(tài)，則初始狀態(tài)是安全的；或者直到發(fā)生死鎖，則初始狀態(tài)是不安全的?！咀鳂I(yè)：】 已分配的資源最大需求量 A BCABCP10 10753P2200322P3302902P4211222P5002433剩余資源ABC 33 2問題:此狀態(tài)是否為安全狀態(tài)，如果 是, 則找出安全序列在此基礎(chǔ)上P2 申請（1，0，2）能否分配？為什么？P5 申請（3，3，0）能否分配？為什么？P1 申請（0，2，0）能否分配？為什么？3.4 MINIX 3 中的I/O概述3.4.1 MINIX 3 中的中斷處理器和I/O訪問 許多設(shè)備驅(qū)動程序在啟動I/O設(shè)備后阻塞，等待

39、某種消息到達(dá)。這種消息往往由該設(shè)備的中斷處理器產(chǎn)生。 在MINIX3中，大多數(shù)I/O通常是命令設(shè)備執(zhí)行某個操作，然后等待該操作結(jié)束。大部分工作由磁盤控制器完成，而需要中斷處理器做的工作很少。 有時低層中斷處理器需要做更多的事情，如時鐘中斷處理器。 在MINIX3 中，時鐘中斷處理器是獨特的，因為時鐘是唯一運(yùn)行在內(nèi)核空間的中斷驅(qū)動設(shè)備。只有當(dāng)前進(jìn)程的時間片用完或者定時器到期時才會向時鐘任務(wù)發(fā)送消息。用戶空間的設(shè)備驅(qū)動程序可能需要若干不同層次的I/O訪問 1. 驅(qū)動程序可能需要訪問其正常數(shù)據(jù)空間以外的內(nèi)存。如管理RAM盤的內(nèi)存驅(qū)動。 2. 驅(qū)動程序可能需要讀寫I/O端口。如硬盤驅(qū)動程序就需要這種訪

40、問。 3. 驅(qū)動程序可能需要響應(yīng)可預(yù)測中斷。比如，硬盤驅(qū)動程序向磁盤控制器發(fā)送命令，這將導(dǎo)致在需要的操作完成后發(fā)生中斷。 4. 驅(qū)動程序可能需要響應(yīng)不可預(yù)測中斷，鍵盤驅(qū)動程序?qū)儆谶@一類。3.4.2 MINIX 3 的設(shè)備驅(qū)動程序 每一類I/O設(shè)備都有一個單獨的I/O設(shè)備驅(qū)動程序。這些驅(qū)動程序是完整的進(jìn)程，每個都有其自己的狀態(tài)、寄存器、堆棧等。 一個簡單的設(shè)備驅(qū)動程序放在一個單獨的源文件里。對于RAM盤、硬盤、軟盤都各自有一個源文件來支持每種類型的設(shè)備，而支持所有塊設(shè)備類型的通用例程則放在drive.c和drvlib.c中。 對于磁盤和終端這樣的設(shè)備組，不僅有源文件，同時還有頭文件。Drive.h支持所有的塊設(shè)備驅(qū)動程序，tty.h提供對所有串口設(shè)備的通用定義。 MINIX3的設(shè)計原則是將完全獨立的用戶空間的進(jìn)程來運(yùn)行操作系統(tǒng)的組件。這種設(shè)計原則是高度模塊化和相當(dāng)有效率的。這也是MINIX3和UNIX在本質(zhì)上的少數(shù)區(qū)別之一。 在MINIX3中，進(jìn)程通過向文件系統(tǒng)進(jìn)程發(fā)送消息來讀取一個文件，而文件系統(tǒng)則向磁盤驅(qū)動程序發(fā)送一條消息來