IO設(shè)備管理課件

I/O設(shè)備管理

2I/O設(shè)備管理系統(tǒng)結(jié)構(gòu)圖設(shè)備管理概述操作系統(tǒng)I/O硬體管理I/O軟體管理上層用戶程式（應(yīng)用層）設(shè)備控制器命令寄存器底層硬體設(shè)備（物理層）中斷處理程式設(shè)備驅(qū)動程式設(shè)備無關(guān)程式用戶進程狀態(tài)寄存器數(shù)據(jù)寄存器3I/O設(shè)備的特點分析操作系統(tǒng)需要管理的最複雜的資源——I/O設(shè)備I/O設(shè)備種類繁多，工作模式各不相同I/O設(shè)備數(shù)據(jù)多樣，處理方式各不相同I/O設(shè)備性能參差，運行控制多種多樣最容易成為電腦系統(tǒng)的瓶頸——I/O設(shè)備很多I/O設(shè)備使用機械操作，導(dǎo)致其速度較CPU相差很大進程運行中的輸入輸出操作可能造成系統(tǒng)運行的性能瓶頸I/O管理：如何最大限度保證I/O設(shè)備與CPU的並行工作最實用、最體現(xiàn)操作系統(tǒng)特色的工作——I/O管理相容性：操作系統(tǒng)最難以完成的使命標(biāo)準(zhǔn)化：IT技術(shù)迅速普及發(fā)展的本質(zhì)高性能：I/O設(shè)備發(fā)展的主要目標(biāo)I/O硬體管理4I/O設(shè)備分類按照設(shè)備的功能特性劃分存儲型設(shè)備：保存各類數(shù)據(jù)（臨時或永久）輸入輸出型設(shè)備：提供人機交互手段數(shù)據(jù)通信型設(shè)備：實現(xiàn)電子數(shù)據(jù)交換按照數(shù)據(jù)的組織形式劃分塊設(shè)備：以數(shù)據(jù)塊為單位存儲、傳輸數(shù)據(jù)字元設(shè)備：以位元組為單位存儲、傳輸數(shù)據(jù)按照資源分配的形式劃分獨佔式設(shè)備：一個時刻只能由一個進程使用，一般為低速I/O設(shè)備共用式設(shè)備：一個時刻可由多個進程使用，資源利用率很高虛擬式設(shè)備：用高速設(shè)備模擬低速設(shè)備，用共用設(shè)備模擬獨佔設(shè)備按照程式使用的方式劃分邏輯設(shè)備：由操作系統(tǒng)維護，簡便用戶操作和控制的“設(shè)備結(jié)構(gòu)”物理設(shè)備：由硬體結(jié)構(gòu)組成，真實完成各類I/O設(shè)備操作I/O硬體管理5I/O設(shè)備的差別I/O設(shè)備的評價標(biāo)準(zhǔn)設(shè)備的數(shù)據(jù)傳輸單位和傳輸率設(shè)備的數(shù)據(jù)表示和應(yīng)用目標(biāo)設(shè)備的控制方式和出錯情況I/O硬體管理6I/O管理的任務(wù)和目標(biāo)根據(jù)用戶請求，控制各類I/O設(shè)備實現(xiàn)用戶的目標(biāo)控制設(shè)備操作，實現(xiàn)設(shè)備與記憶體的數(shù)據(jù)交換設(shè)備的分配與回收、設(shè)備驅(qū)動程式、設(shè)備中斷管理、各類緩衝區(qū)管理等向用戶提供方便的I/O設(shè)備介面，遮罩底層硬體細節(jié)差別虛擬機——邏輯設(shè)備的作用：用戶能夠簡單方便的使用I/O設(shè)備設(shè)備介面的方便性、友好性、透明性、設(shè)備無關(guān)性利用各種技術(shù)，提高I/O設(shè)備的運行效率設(shè)備與CPU之間、設(shè)備之間的並行設(shè)備負載的均衡：保持設(shè)備的充分忙碌實現(xiàn)對I/O設(shè)備的管理和保護設(shè)備的分配與回收：針對獨佔設(shè)備和共用設(shè)備，實現(xiàn)合理的資源分配設(shè)備的數(shù)據(jù)保護：不同設(shè)備之間的保護、設(shè)備內(nèi)部的保護I/O硬體管理7內(nèi)容提要

I/O設(shè)備管理概述

I/O硬體原理與軟體原理進程死鎖

I/O設(shè)備管理實例剖析內(nèi)容提要8I/O設(shè)備硬體組成I/O設(shè)備的硬體結(jié)構(gòu)機械部分（物理裝置）：由模擬信號驅(qū)動的各種機械裝置控制器/適配器（電子裝置）：實現(xiàn)與主機的連接和通信設(shè)備控制器的工作方式常以板卡的形式與主板的匯流排插槽連接通過設(shè)備的介面寄存器、緩衝區(qū)與CPU進行通信設(shè)備控制器的工作內(nèi)容地址解碼：實現(xiàn)對I/O地址空間的正確映射外部通信：接受或者發(fā)送數(shù)據(jù)/狀態(tài)信號執(zhí)行指令：將數(shù)位化指令轉(zhuǎn)化為機械裝置能夠理解的模擬信號性能增強：實現(xiàn)內(nèi)部硬體緩衝、完成數(shù)據(jù)加工等性能提升目標(biāo)I/O硬體管理9操作系統(tǒng)的硬體環(huán)境課程導(dǎo)論10I/O設(shè)備介面的工作流程I/O操作過程的細分準(zhǔn)備、啟動、測試和等待、結(jié)果檢查和錯誤處理I/O設(shè)備介面的作用介面寄存器：保存命令、狀態(tài)或者數(shù)據(jù)介面緩衝區(qū)：用來保存大量數(shù)據(jù)的緩衝區(qū)通過I/O設(shè)備介面，CPU可以設(shè)定指令或狀態(tài)、可以讀取狀態(tài)和結(jié)果I/O設(shè)備介面的工作方式設(shè)置命令寄存器和狀態(tài)寄存器：CPU通過匯流排與I/O介面通信I/O設(shè)備與CPU並行工作：控制器根據(jù)指令完成相應(yīng)I/O操作通過中斷向CPU發(fā)出信號：工作完成後通過硬體中斷通知CPUI/O硬體管理11I/O設(shè)備介面的工作流程（續(xù)）IBMPC的軟碟控制器可接受15條指令：READ、WRITE、SEEK、FORMAT等各條指令均可帶參數(shù)，指令和相關(guān)參數(shù)均被設(shè)置到介面寄存器中位串行工作機制：驅(qū)動器提供“位流”，控制器負責(zé)在緩衝區(qū)中將其組裝為位元組，並進行必要的校驗和糾錯顯示器的控制器位串行工作機制：從顯示緩衝區(qū)中讀取可供顯示的內(nèi)容，而後產(chǎn)生用來調(diào)製CRT電子束的信號I/O設(shè)備介面的價值遮罩底層硬體細節(jié)，降低應(yīng)用者的操作難度體現(xiàn)模組化的特點，適應(yīng)不同的應(yīng)用環(huán)境通過對I/O設(shè)備介面進行標(biāo)準(zhǔn)化，即可方便實現(xiàn)相容I/O硬體管理12電腦的系統(tǒng)結(jié)構(gòu)圖課程導(dǎo)論13I/O設(shè)備的連接與地址映射I/O設(shè)備的連接方式連接路徑：I/O設(shè)備與CPU建立連接時，所有有關(guān)組件構(gòu)成連接路徑I/O端口：I/O設(shè)備介面中有多個介面寄存器或緩衝區(qū)，每一個寄存器或緩衝區(qū)被稱為一個I/O端口I/O端口地址空間：實現(xiàn)對I/O介面寄存器/緩衝區(qū)的訪問I/O設(shè)備端口的編址方式I/O端口獨立編址：與記憶體空間完全獨立記憶體映射I/O地址：在內(nèi)存空間中劃分固定區(qū)域映射I/O端口I/O地址空間的編址方式和使用差別指令運行差別：訪問的地址空間不同系統(tǒng)資源消耗：所需要的資源數(shù)不同優(yōu)缺點權(quán)衡：匯流排規(guī)格、地址資訊傳輸與過濾、系統(tǒng)性能等因素I/O硬體管理14I/O端口獨立編址模式I/O地址與記憶體空間完全獨立使用專用的I/O指令對I/O端口進行操作優(yōu)缺點分析優(yōu)點1：I/O設(shè)備不佔用記憶體地址空間，減少系統(tǒng)資源消耗優(yōu)點2：技術(shù)實現(xiàn)複雜度低，易於區(qū)分I/O地址和記憶體地址缺點：由於地址空間獨立、狹小，導(dǎo)致指令類型少，只能使用簡單的組合語言編程I/O硬體管理15I/O端口的記憶體映射編址方式I/O端口地址空間和記憶體地址空間統(tǒng)一編址I/O端口地址也被作為物理地址空間的一部分進行存儲管理CPU訪問地址空間時，將對地址空間的範(fàn)圍進行判斷，然後選擇讀取記憶體空間或者訪問I/O端口記憶體映射編址的優(yōu)缺點分析優(yōu)點1：使得技術(shù)實現(xiàn)手段更加方便，可用C語言編寫驅(qū)動程式優(yōu)點2：不需要對I/O地址空間進行特殊保護，只需要利用現(xiàn)有的存儲保護機制（例如分頁式中的頁表項設(shè)置）優(yōu)點3：使得I/O端口的指令更加靈活多樣缺點1：記憶體映射方式中必須保證I/O端口的即時性（禁用高速緩存）缺點2：對於雙匯流排或者多匯流排結(jié)構(gòu)而言，I/O端口的地址映射將比較困難和麻煩I/O硬體管理16I/O端口地址的映射與訪問I/O硬體管理混合方案中，記憶體空間負責(zé)管理I/O端口，I/O獨立編址部分屬於數(shù)據(jù)緩衝區(qū)。例如Pentium就使用了這種方式17系統(tǒng)匯流排對I/O端口編址的影響I/O硬體管理18系統(tǒng)匯流排對I/O端口編址的影響I/O硬體管理19I/O設(shè)備的控制方式程式控制I/O（輪詢或忙等待模式）CPU直接與I/O設(shè)備進行通信，負責(zé)將用戶數(shù)據(jù)傳送到I/O端口用戶程式通過系統(tǒng)調(diào)用來使用I/O設(shè)備CPU需要不斷查詢I/O設(shè)備的端口狀態(tài)，性能較低中斷控制I/OCPU設(shè)定I/O設(shè)備的初始值，然後不再忙等待，運行其他進程，當(dāng)前進程阻塞I/O設(shè)備完成對當(dāng)前數(shù)據(jù)的處理後，向CPU發(fā)出中斷，I/O中斷處理程式將負責(zé)傳送剩餘數(shù)據(jù)中斷控制模式依然造成CPU時間的浪費，而且效率不高DMA控制I/O使用獨立的DMA控制器代替CPU的工作，I/O設(shè)備與DMA通信，DMA在傳輸完成一個數(shù)據(jù)緩衝區(qū)之後再向CPU發(fā)中斷DMA模式減少了中斷次數(shù)，同時又集成了程式控制和中斷控制的優(yōu)點I/O通道機制DMA機制過於簡單，有時未必能夠提高與CPU並行效率為此專門增加了I/O處理機，專門負責(zé)I/O設(shè)備的控制和操作，與CPU並行工作I/O硬體管理20程式控制I/O的工作流程I/O硬體管理由操作系統(tǒng)的“服務(wù)程式”負責(zé)將用戶數(shù)據(jù)傳送至印表機端口服務(wù)程式順序傳送列印數(shù)據(jù)，填滿介面緩衝區(qū)後就等待（空迴圈）每次迴圈中都檢查介面緩衝區(qū)是否可用，一旦可用就繼續(xù)傳送數(shù)據(jù)數(shù)據(jù)傳送完成後“服務(wù)程式”結(jié)束，用戶進程繼續(xù)運行缺點：靠CPU以“忙等待”的形式與印表機進行通信，浪費CPU資源21中斷控制I/O的工作流程I/O硬體管理“列印服務(wù)程式”只將最開始的數(shù)據(jù)傳送至印表機端口，然後阻塞CPU可繼續(xù)調(diào)度其他進程運行，不浪費CPU時間一旦列印緩衝區(qū)空後，印表機端口發(fā)出硬體中斷CPU回應(yīng)中斷，恢復(fù)“列印服務(wù)程式”運行，繼續(xù)傳送數(shù)據(jù)缺點：雖然節(jié)省了CPU資源，但是中斷回應(yīng)也消耗較大的系統(tǒng)資源22DMA控制I/O的工作流程I/O硬體管理用戶進程發(fā)出系統(tǒng)調(diào)用後進入阻塞態(tài)，CPU直接設(shè)置DMA端口CPU與DMA並行工作，DMA負責(zé)將用戶數(shù)據(jù)傳送給印表機當(dāng)DMA完成所有工作後，向CPU發(fā)出中斷，CPU回應(yīng)後喚醒用戶進程優(yōu)點：只有一次中斷、DMA與CPU並行提高了系統(tǒng)運行效率缺點：DMA速度較慢，如果CPU並不繁忙，那麼DMA機制並無太大意義23DMA工作方式的深入分析DMA內(nèi)部結(jié)構(gòu)的差異單路I/O連接：DMA中只有一組寄存器，只能連接一個I/O設(shè)備多路I/O連接：DMA中有多組寄存器，可同時連接多個I/O設(shè)備多路I/O連接模式下，DMA內(nèi)部也需要進行適當(dāng)?shù)恼{(diào)度（輪轉(zhuǎn)、優(yōu)先順序）DMA工作方式的差異數(shù)據(jù)匯流排的工作模式：塊模式和字元模式，傳輸數(shù)據(jù)的速率不同字元模式（週期竊?。篋MA竊取一個匯流排週期以傳輸一個字，造成CPU輕微延遲塊模式（突發(fā)模式）：DMA獲得匯流排控制權(quán)後連續(xù)發(fā)出多個請求，提高匯流排利用效率飛越模式：DMA內(nèi)部存在數(shù)據(jù)緩衝，設(shè)備將數(shù)據(jù)發(fā)送給DMA，DMA再進行轉(zhuǎn)發(fā)DMA模式的權(quán)衡與分析DMA保存的地址資訊：絕大多數(shù)情況下DMA保存的是物理地址，CPU負責(zé)將用戶地址轉(zhuǎn)換為物理地址，然後將其設(shè)置到DMA中DMA的數(shù)據(jù)緩衝：DMA內(nèi)部也會使用數(shù)據(jù)緩衝，這樣會大大提高I/O通信效率DMA的優(yōu)劣分析：DMA比CPU慢好多，簡單的應(yīng)用環(huán)境中，用CPU要比DMA好；只有存在頻繁的多道程序併發(fā)的情況下，DMA才會體現(xiàn)與CPU並行的作用I/O硬體管理24I/O通道機制的引入與實現(xiàn)I/O通道（Channel）的概念如何以高速、高效的方式控制I/O設(shè)備，是I/O管理的重要問題DMA速度很慢，而且結(jié)構(gòu)簡單，無法執(zhí)行相對複雜的程式引入I/O通道（專門的處理機），可以運行由通道指令組成的通道程式I/O通道的工作方式和分類分為位元組多路通道、選擇通道、成組多路通道三種I/O通道採取“竊取匯流排週期”的方式實現(xiàn)對I/O設(shè)備的控制和數(shù)據(jù)傳輸I/O通道就是一個小型的處理機，和CPU共用記憶體I/O通道接到CPU的指令後即啟動通道命令/程式，獨立於CPU控制I/O設(shè)備工作I/O通道的結(jié)構(gòu)組成CAW：通道地址寄存器，用於記錄通道程式在內(nèi)存中的地址CCW：通道命令寄存器，用於保存當(dāng)前正在運行的通道命令CSW：通道狀態(tài)寄存器，用於保存命令執(zhí)行後的結(jié)果CDW：通道數(shù)據(jù)寄存器，用於存放傳輸?shù)臄?shù)據(jù)（起到緩衝的作用）I/O硬體管理25不同類型的I/O通道I/O硬體管理26單通道與多通道I/O硬體管理27I/O軟體原理I/O軟體的設(shè)計需求有哪些？解決同步（阻塞）－非同步（傳輸）的問題。底層：如何傳送控制命令？如何傳輸數(shù)據(jù)？上層：如何向用戶遮罩此過程？如何調(diào)度I/O進程實現(xiàn)對設(shè)備訪問的錯誤處理。簡單情況：可在硬體底層解決的錯誤複雜情況：無法有效解決，只能通知高層的錯誤為便於人的使用，實現(xiàn)設(shè)備無關(guān)性——統(tǒng)一命名法。如何讓用戶無需考慮各種設(shè)備的差別，採用相同的習(xí)慣來使用？如何管理不同設(shè)備的統(tǒng)一命名？實現(xiàn)名稱與設(shè)備的映射？I/O設(shè)備的緩衝管理緩衝區(qū)的維護與使用；即時I/O設(shè)備中緩衝區(qū)的預(yù)存和即時性保持實現(xiàn)對專有設(shè)備的和共用設(shè)備的有效管理共用設(shè)備：如何記錄共用狀態(tài)？專有設(shè)備：如何實現(xiàn)對專有設(shè)備的互斥性訪問？I/O軟體管理28I/O軟體體系結(jié)構(gòu)I/O軟體管理中斷處理程式底層硬體設(shè)備設(shè)備驅(qū)動程式用戶I/O軟體設(shè)備無關(guān)軟體I/O請求I/O回應(yīng)提供系統(tǒng)庫調(diào)用，供人員使用；提供類似Spooling這樣的精靈守護進程管理共用設(shè)備命名、保護、阻塞、緩衝建立設(shè)備寄存器、解決錯誤處理中斷信號29中斷處理程式控制I/O設(shè)備的基本方法用戶發(fā)出系統(tǒng)調(diào)用或直接調(diào)用I/O設(shè)備，然後用戶進程阻塞設(shè)備驅(qū)動程式啟動I/O操作，然後自己阻塞I/O設(shè)備完成操作後產(chǎn)生中斷，對應(yīng)的中斷服務(wù)程式更新各種狀態(tài)資訊用戶進程恢復(fù)為就緒，繼續(xù)運行中斷處理程式的工作過程保存CPU現(xiàn)場資訊：各類寄存器（最重要的是PSW）為中斷服務(wù)程式設(shè)定CPU上下文：TLB、內(nèi)核堆疊等應(yīng)答中斷控制器：遮罩同類中斷、打開其他中斷恢復(fù)中斷服務(wù)進程的運行，完成對設(shè)備控制器介面的操作操作結(jié)束後進行調(diào)度，改變用戶進程狀態(tài)，選擇下一個運行程式用戶進程恢復(fù)正常運行，此時設(shè)備驅(qū)動程式無事可幹，又陷入阻塞I/O軟體管理30設(shè)備驅(qū)動程式設(shè)備驅(qū)動程式的特點用來控制設(shè)備控制器的代碼和指令，被稱為設(shè)備驅(qū)動程式目前的體系結(jié)構(gòu)中，設(shè)備驅(qū)動程式屬於操作系統(tǒng)的內(nèi)核部分操作系統(tǒng)實現(xiàn)過程中，需要提供標(biāo)準(zhǔn)化的介面函數(shù)，用於封裝設(shè)備驅(qū)動程式設(shè)備驅(qū)動的存在形式：與操作系統(tǒng)統(tǒng)一編譯，或者運行時動態(tài)鏈接設(shè)備驅(qū)動程式的工作過程接受上層用戶發(fā)送的各類參數(shù)，並對輸入?yún)?shù)進行檢查對硬體設(shè)備的可用性進行檢查，並接通或者啟動設(shè)備控制設(shè)備完成對應(yīng)的操作（通過設(shè)置介面寄存器實現(xiàn)）實現(xiàn)數(shù)據(jù)的I/O，同時返回操作的狀態(tài)結(jié)果。設(shè)備驅(qū)動工作過程中的特殊考慮設(shè)備驅(qū)動的工作方式：同步阻塞或持續(xù)運行同步阻塞模式下，必須考慮支持“中斷嵌套”的情況，將其設(shè)計為可重入熱插拔系統(tǒng)中，自動的適應(yīng)設(shè)備插入或者卸載I/O軟體管理31設(shè)備驅(qū)動程式的統(tǒng)一介面I/O軟體管理32緩衝機制的設(shè)計與實現(xiàn)I/O軟體管理33用戶空間的I/O軟體I/O操作相關(guān)的庫函數(shù)或工具包實現(xiàn)對OS內(nèi)核設(shè)備I/O管理機制的封裝向應(yīng)用層用戶提供規(guī)範(fàn)、簡潔的操作介面實現(xiàn)I/O管理底層機制與上層用戶的交互假脫機（Spooling）技術(shù)通過應(yīng)用軟體來實現(xiàn)對獨佔式I/O設(shè)備的管理緩衝＋封裝：用戶只需要管理“特殊I/O檔”守護進程（Daemon）：實現(xiàn)假脫機目錄利用應(yīng)用程式，將獨佔式I/O設(shè)備虛擬為共用設(shè)備I/O軟體管理34I/O設(shè)備管理小結(jié)I/O設(shè)備管理面對的各種衝突和矛盾“獨特性”與“相容性”——標(biāo)準(zhǔn)化環(huán)境下的發(fā)展選擇“高性能”與“友好性”——系統(tǒng)資源消耗的代價取捨硬體實現(xiàn)與軟體模擬——成本與性能之間的權(quán)衡I/O設(shè)備管理的思維方式統(tǒng)一、規(guī)範(fàn)的軟硬體平臺是一切技術(shù)發(fā)展的基礎(chǔ)性能穩(wěn)定和錯誤處理機制是一切應(yīng)用普及的前提系統(tǒng)觀：軟硬搭配、高低結(jié)合是複雜問題的解決思路未來趨勢：隨著硬體成本的降低，軟體的作用越來越大I/O設(shè)備管理35內(nèi)容提要

I/O設(shè)備管理概述

I/O硬體原理與軟體原理

進程死鎖

I/O設(shè)備管理實例剖析內(nèi)容提要36進程死鎖原理死鎖舉例進程A：獲得CD-ROM使用權(quán)，申請印表機進程B：獲得印表機使用權(quán)，申請CD-ROM死鎖：此時進程A、B均被阻塞，無法運行進程死鎖進程A進程B印表機CD-ROM37進程死鎖原理死鎖的定義進程死鎖若一個進程集合中的每一個進程都在等待只能由本集合中其他進程引發(fā)的事件。則這種情況為死鎖。死鎖發(fā)生的條件互斥條件：每一個資源或者空閒，或者被分配給一個進程保持和等待條件：已佔有某些資源的進程需申請新的資源後方可繼續(xù)運行非剝奪條件：被進程佔用的資源不可剝奪，只能被進程本身顯式釋放迴圈等待條件：系統(tǒng)必然存在一條由兩個或兩個以上進程組成的迴圈鏈，該迴圈鏈中每個進程都在等待臨近的進程釋放資源38如何理解死鎖概念基礎(chǔ)資源、可剝奪資源與不可剝奪資源可剝奪資源會造成死鎖嗎？（舉例）發(fā)生條件分析保持當(dāng)前資源，等待未分配資源存在迴圈的保持等待鏈，造成死鎖情況對比理解死鎖與互斥有哪些異同？操作系統(tǒng)為什麼要解決死鎖問題？在所有的操作系統(tǒng)中都會發(fā)生死鎖問題嗎？進程死鎖39死鎖的形式化描述基於有向圖描述死鎖條件進程死鎖40死鎖現(xiàn)象與死鎖過程產(chǎn)生死鎖的進程運行過程示例進程死鎖41死鎖現(xiàn)象與死鎖過程進程死鎖產(chǎn)生死鎖的進程運行過程示例42死鎖處理策略不理會死鎖原因：為什麼耗費大量的時間在小概率事件上呢？死鎖檢測與恢復(fù)目標(biāo)：檢測死鎖發(fā)生，通過撤銷進程恢復(fù)系統(tǒng)運行死鎖預(yù)防目標(biāo)：對進程加以適當(dāng)限制以防止死鎖情況發(fā)生死鎖避免目標(biāo)：不對進程加以限制，由操作系統(tǒng)完成死鎖預(yù)防進程死鎖43鴕鳥演算法核心思想：忽略死鎖問題原因：死鎖問題的發(fā)生是小概率事件策略分析方便性與正確性之間的選擇平均情況與最壞情況的選擇進程死鎖44死鎖檢測與恢復(fù)核心思想：將系統(tǒng)從死鎖中解脫方法動機：與其耗費大量時間來避免死鎖的發(fā)生，不如採取有效的手段解決死鎖死鎖檢測的解決方法每個類型的資源只有一個：基於圖和集合的演算法檢測是否有閉環(huán)每個類型的資源有多個：基於矩陣和向量比較方法檢測是否存在死鎖死鎖恢復(fù)的解決方法進行資源搶佔：將某個進程的資源強制性分配給其他進程利用回退恢復(fù)：設(shè)定檢查點，發(fā)現(xiàn)存在死鎖情況後則回退殺死進程恢復(fù)：直接殺掉佔用資源的進程，使得其他進程得以運行；最關(guān)鍵的問題是選擇殺死哪一個進程進程死鎖45死鎖檢測演算法簡介每個類型的資源只有一個建立資源分配圖結(jié)構(gòu)，記錄了所有的進程、資源和有向邊從任一結(jié)點開始進行深度優(yōu)先遍曆，如找到閉環(huán)則結(jié)束如某條遍曆路徑已經(jīng)到達終點，則回退至上一結(jié)點，繼續(xù)重複此過程每個類型的資源有多個建立現(xiàn)有資源標(biāo)量、可用資源標(biāo)量、當(dāng)前分配矩陣、請求矩陣等數(shù)據(jù)結(jié)構(gòu)對當(dāng)前分配矩陣，尋找可滿足資源需求的進程，對其標(biāo)記如果有進程沒有被標(biāo)記，說明該進程是死鎖進程進程死鎖46死鎖預(yù)防核心思想：對進程加以限制防止死鎖發(fā)生設(shè)計思路：針對四個死鎖條件，逐一避免具體解決方法互斥條件：使用Spooling技術(shù)來管理設(shè)備（保持和等待條件：資源可用性決定資源分配不可剝奪條件：由系統(tǒng)直接剝奪此類資源迴圈鏈條件：資源編號，按預(yù)定規(guī)則申請進程死鎖47死鎖避免核心思想：不對進程進行限制，預(yù)防死鎖設(shè)計思路：操作系統(tǒng)分析資源分配情況防止死鎖核心思想安全狀態(tài)：存在某種資源調(diào)度順序，保證所有進程正常運行完成，則稱該狀態(tài)為安全狀態(tài)不安全狀態(tài)：不存在可滿足所有進程正常運行的資源調(diào)度順序，則稱該狀態(tài)為不安全狀態(tài)具體實現(xiàn)方法資源軌跡圖：針對兩個進程的死鎖避免銀行家演算法：單種資源和多種資源的演算法進程死鎖48使用資源軌跡圖方法避免死鎖針對兩個進程、兩種資源的死鎖避免方法條件：兩個進程A和B，兩種資源“印表機”和“繪圖儀”根據(jù)指令運行過程來判斷是否發(fā)生死鎖進程A：P點啟動，I1~I3使用印表機，I2~I4使用繪圖儀；進程B：Q點啟動，I5~I7使用繪圖儀，I6~I8使用印表機；進程死鎖49使用資源軌跡圖方法避免死鎖進程死鎖50單種資源銀行家演算法核心思想記錄每個進程的已有資源和所需最大資源數(shù)對每一個資源請求進行檢查，判斷是否會造成不安全如果不安全則不分配，從而避免死鎖方法分析對任何資源請求，都尋找是否存在安全狀態(tài)序列不抱僥倖心理，防止任何死鎖情況的發(fā)生進程死鎖51單種資源銀行家演算法進程死鎖52多種資源銀行家演算法核心思想對單種資源銀行家演算法進行擴充基於向量操作來運行銀行家演算法進程死鎖53多種資源銀行家演算法處理步驟Step1：檢查“仍需資源矩陣”中的每一行，判斷是否存在一行，其所需資源總數(shù)小於向量A（剩餘資源總數(shù)），失敗則系統(tǒng)死鎖。Step2：如存在此行，則將所有資源分配給該行對應(yīng)向量，並將其狀態(tài)標(biāo)識為結(jié)束。Step3：重複1～2步，直至所有進程狀態(tài)為結(jié)束。如果所有進程狀態(tài)均可標(biāo)為結(jié)束，則狀態(tài)安全，否則會發(fā)生死鎖。進程死鎖54舉例：歷史考研題舉例北大1997年OS考研試題系統(tǒng)中有三種資源（A，B，C）和5個進程P1～P5資源總數(shù)為（17，5，20），T0時刻系統(tǒng)狀態(tài)如表所示，系統(tǒng)採用銀行家演算法實施死鎖避免策略進程死鎖最大資源需求量已分配資源量ABCABCP1559212P2536402P34011405P4425204P542431455舉例：歷史考研題舉例北大1997年OS考研試題請解答以下問題：（1）T0時刻是否為安全狀態(tài)？若是則給出安全序列（2）在T0時刻P2請求資源（0，3，4），是否能夠?qū)嵤┵Y源分配，為什麼？（3）在（2）的基礎(chǔ)上，若P4請求資源（2，0，1），是否能夠?qū)嵤┓峙?，為什麼？（4）在（3）的基礎(chǔ)上，若P1請求資源（0，2，0），是否能夠?qū)嵤┓峙?，為什麼？進程死鎖56內(nèi)容提要

I/O設(shè)備管理概述

I/O硬體原理與軟體原理進程死鎖

I/O設(shè)備管理實例剖析內(nèi)容提要57Minix中的I/O設(shè)備管理設(shè)備驅(qū)動方式（與Unix的本質(zhì)區(qū)別，與Linux類似方式）每一類設(shè)備均有單獨的設(shè)備驅(qū)動程式，其中硬體無關(guān)的內(nèi)容形成公共程式、硬體相關(guān)的內(nèi)容作為特定驅(qū)動。以模組化組織提高系統(tǒng)靈活性採用進程間通信的方式完成I/O設(shè)備的使用（Minix的進程式組織結(jié)構(gòu)）Unix採用過程調(diào)用的方式，用戶進程調(diào)用驅(qū)動程式，引發(fā)操作系統(tǒng)陷入，完成I/O操作後由中斷處理程式喚醒用戶進程設(shè)備管理方法設(shè)備驅(qū)動程式作為獨立進程存在，OS啟動時各個設(shè)備驅(qū)動進程完成基本初始化，而後等待消息（阻塞），直到用戶進程發(fā)送消息（使用I/O設(shè)備）將其喚醒與硬體相關(guān)的設(shè)備驅(qū)動部分作為過程被設(shè)備驅(qū)動程式調(diào)用，從而實現(xiàn)無關(guān)性封裝I/O軟體與死鎖處理Minix將所有與設(shè)備無關(guān)的I/O軟體封裝在檔系統(tǒng)模組中，所有的塊設(shè)備均作為一種特殊的檔用戶空間的I/O軟體主要是供用戶程式調(diào)用的函數(shù)庫Minix中對死鎖的處理採用“鴕鳥演算法”I/O管理實例58進程式OS與整體式OSI/O管理實例59Windows中的I/O設(shè)備管理I/O管理系統(tǒng)結(jié)構(gòu)I/O管理系統(tǒng)是一個獨立的系統(tǒng)組件，存在於NTOSKRNL.exe檔中I/O管理系統(tǒng)由多個執(zhí)行體組件和設(shè)備驅(qū)動程式組成，負責(zé)接受I/O請求，並針對性的將設(shè)備請求傳送到各類對應(yīng)的設(shè)備Windows中將所有的I/O操作均看作對虛擬檔的操作，所有的I/O數(shù)據(jù)傳輸都被看作“流數(shù)據(jù)”，由I/O管理系統(tǒng)負責(zé)將虛擬檔映射到對應(yīng)的物理設(shè)備上I/O管理系統(tǒng)組成I/O管理器：負責(zé)定義支撐設(shè)備驅(qū)動程式的基本架構(gòu)，直接回應(yīng)I/O請求設(shè)備驅(qū)動程式：負責(zé)定義並實現(xiàn)某一特定類型設(shè)備的I/O介面管理PnP管理器：與I/O管理器和匯流排驅(qū)動程式協(xié)同，檢測硬體資源的分配、設(shè)備的變更電源管理器：與I/O管理器協(xié)同工作來檢測整個系統(tǒng)和單個設(shè)備，完成電源狀態(tài)轉(zhuǎn)換WDMWMI：WDM的WMI支持例程，負責(zé)實現(xiàn)設(shè)備與WMI服務(wù)之間的通信註冊表：作為一個資料庫，存儲基本硬體描述資訊以及驅(qū)動程式的初始化和配置資訊硬體抽象層：將設(shè)備驅(qū)動程式實現(xiàn)為二進位可移植的形式，實現(xiàn)對硬體平臺的獨立Windows中的I/O系統(tǒng)數(shù)據(jù)結(jié)構(gòu)檔對象、驅(qū)動程式對象、設(shè)備對象、I/O請求包I/O管理實例60Windows中I/O系統(tǒng)組件I/O管理實例61Windows中的I/O數(shù)據(jù)結(jié)構(gòu)檔對象所有I/O設(shè)備被看作檔對象，用戶程式進行I/O操作時就像是對一個檔進行操作檔對象是可共用的、有設(shè)備無關(guān)命名的、受保護的、支持同步的結(jié)構(gòu)調(diào)用與實現(xiàn)過程：C庫函數(shù)——Win32DLL——NTDLL.DLL——NTOSKRNL.DLL驅(qū)動程式對象與設(shè)備對象驅(qū)動程式對象代表一個獨立的驅(qū)動程式，I/O管理器從驅(qū)動程式對象中獲得並且為I/O記錄每個驅(qū)動程式的入口點設(shè)備對象在OS中代表一個物理/邏輯/虛擬的設(shè)備，並描述設(shè)備的基本特徵當(dāng)驅(qū)動程式被加載時，I/O管理器將創(chuàng)建一個驅(qū)動程式對象，然後調(diào)用驅(qū)動程式的初始化例程，初始化例程將創(chuàng)建一個設(shè)備對象。設(shè)備對象接受I/O操作請求，驅(qū)動程式對象實現(xiàn)I/O操作請求I/O請求包由固定部分（標(biāo)題）和堆疊單元（數(shù)量不定）組成，包含了I/O請求的各類資訊IRP由I/O管理器構(gòu)造，保存了I/O請求的相關(guān)資訊，同時保存了調(diào)用者的相關(guān)資訊所有的IRP均保存在IRP佇列中，當(dāng)用戶程式終止後，I/O系統(tǒng)將清除未完成的IRPI/O管理實例62I/O請求涉及到的數(shù)據(jù)結(jié)構(gòu)I/O管理實例63Windows中設(shè)備驅(qū)動程式層次I/O管理實例64設(shè)備驅(qū)動程式的內(nèi)容組成I/O管理實例65Windows中的I/O處理簡述設(shè)備驅(qū)動程式的同步操作驅(qū)動程式在訪問相關(guān)數(shù)據(jù)時，必須實現(xiàn)“同步”操作，即以互斥的形式保護各類共用數(shù)據(jù)。在單CPU的機器上，通過同步例程實現(xiàn)；在多CPU的機器上，通過“自旋鎖”實現(xiàn)I/O處理的類型同步I/O和非同步I/O：絕大部分I/O操作是以同步方式實現(xiàn)的。但是也可以通過設(shè)定CreatFile的參數(shù)來使用非同步I/O，非同步I/O要求用戶程式在設(shè)計和實現(xiàn)時必須保證不訪問來自I/O操作的數(shù)據(jù)。在非同步方式下，用戶程式通過等待同步對象來實現(xiàn)與非同步I/O操作的“同步”快速I/O：允許I/O系統(tǒng)不產(chǎn)生IRP而直接使用驅(qū)動程式執(zhí)行I/O請求映射檔I/O和文件高速緩存映射檔I/O是將磁片中的MappingFile作為進程的虛擬記憶體一部分，直接把檔作為大的數(shù)組進行訪問Windows利用MappingFile可實現(xiàn)檔高速緩存和映象活動分散/集中式I/O：運行用戶程式從虛擬記憶體的多個緩衝區(qū)（映射檔）中讀寫數(shù)據(jù)到磁片檔（非高速緩存打開）的一個連續(xù)區(qū)域中。I/O管理實例66盤設(shè)備的管理描述盤的硬體組成及相關(guān)原理磁片：軟碟和硬碟，基於電磁原理存儲數(shù)據(jù)，盤面附著可磁化金屬氧化物，磁頭旋轉(zhuǎn)保持角速度一致即可只讀光碟：CD-ROM，基於光學(xué)原理，利用凹痕與