操作系統(tǒng) 課件 第7、8章 設(shè)備管理、進(jìn)程同步機(jī)制與死鎖

第7章設(shè)備管理學(xué)習(xí)目標(biāo)<2

>1．掌握輸入輸出設(shè)備管理的基本概念2．掌握輸入輸出設(shè)備硬件的組成及其控制方式3．理解輸入輸出設(shè)備驅(qū)動(dòng)軟件的組成、設(shè)備獨(dú)立性的概念及設(shè)備驅(qū)動(dòng)的層次結(jié)構(gòu)4．掌握輸入輸出設(shè)備的分配與回收、各種不同類(lèi)型設(shè)備的分配算法5．理解磁盤(pán)驅(qū)動(dòng)調(diào)度及信息優(yōu)化分布的概念6．掌握虛擬設(shè)備和緩沖技術(shù)的應(yīng)用學(xué)時(shí)：8本章內(nèi)容導(dǎo)讀<3

>1．本章是操作系統(tǒng)設(shè)備管理的內(nèi)容，闡述輸入輸出設(shè)備在計(jì)算機(jī)系統(tǒng)中的功能和作用2．輸入輸出設(shè)備種類(lèi)繁多，傳輸速度、接口方式、功能性能存在較大的差異3．設(shè)備的驅(qū)動(dòng)程序與操作系統(tǒng)內(nèi)核之間配合的模式和信息的交流方式7.1設(shè)備管理的基本概念7.2設(shè)備硬件和設(shè)備管理軟件的組成7.3I/O設(shè)備的控制方式7.4設(shè)備分配與回收7.5磁盤(pán)驅(qū)動(dòng)調(diào)度7.6緩沖技術(shù)7.7虛擬設(shè)備技術(shù)7.8本章小結(jié)目錄CONTENTSPART7.1設(shè)備管理的基本概念輸入輸出設(shè)備的定義<6

>輸入輸出設(shè)備（I/O設(shè)備）也稱(chēng)為外部設(shè)備（peripheral），包括計(jì)算機(jī)系統(tǒng)中除CPU和內(nèi)存儲(chǔ)器以外的所有的硬件設(shè)備和裝置廣義的輸入輸出設(shè)備即上述定義，狹義的輸入輸出設(shè)備不包括外存儲(chǔ)設(shè)備輸入設(shè)備（鍵盤(pán)）輸入設(shè)備（鼠標(biāo)）輸出設(shè)備（顯示器）輸出設(shè)備（打印機(jī)）處理器內(nèi)存計(jì)算機(jī)系統(tǒng)計(jì)算機(jī)系統(tǒng)與輸入輸出設(shè)備關(guān)系示意圖<7

>設(shè)備管理的地位和意義設(shè)備管理在操作系統(tǒng)中具有十分重要的地位，它是操作系統(tǒng)總體性能的重要決定因素和重要表現(xiàn)指標(biāo)輸入輸出設(shè)備的多樣性用戶(hù)要求和CPU進(jìn)程調(diào)度的多樣性性能存在較大差異輸入輸出設(shè)備與處理器的性能鴻溝導(dǎo)致并發(fā)技術(shù)產(chǎn)生的直接原因設(shè)備形態(tài)和應(yīng)用多樣是操作系統(tǒng)所管理的資源龐雜的主要原因之一用戶(hù)要求、CPU進(jìn)程調(diào)度的多樣性，導(dǎo)致了操作系統(tǒng)的設(shè)備管理相關(guān)的數(shù)據(jù)結(jié)構(gòu)與算法的多樣性操作系統(tǒng)主要通過(guò)緩沖技術(shù)、中斷技術(shù)和虛擬技術(shù)來(lái)解決輸入輸出設(shè)備性能同CPU性能不匹配問(wèn)題<8

>設(shè)備管理的任務(wù)設(shè)備管理的任務(wù)主要表現(xiàn)在以下方面：解決輸入輸出設(shè)備的性能瓶頸方便用戶(hù)對(duì)設(shè)備的管理操作系統(tǒng)需要在設(shè)備管理和系統(tǒng)的其它部分之間提供簡(jiǎn)單易用的訪問(wèn)接口保障用戶(hù)使用設(shè)備的安全由設(shè)備傳送或管理的數(shù)據(jù)不應(yīng)破壞或泄露；多用戶(hù)多任務(wù)環(huán)境中的設(shè)備使用應(yīng)該通過(guò)協(xié)調(diào)而避免沖突<9

>輸入輸出設(shè)備的分類(lèi)按設(shè)備的使用特性分類(lèi)計(jì)算機(jī)用以“感受”或“接觸”外部信息的設(shè)備，如鍵盤(pán)、鼠標(biāo)輸入設(shè)備計(jì)算機(jī)用來(lái)保存信息的裝置，記錄介質(zhì)必須具有可寫(xiě)入性、可讀出性、可保存性等特征，如磁介質(zhì)的光盤(pán)等存儲(chǔ)設(shè)備計(jì)算機(jī)用以產(chǎn)生普通人可感知的信息或輸出用以“影響”或“控制”其他外部裝置的設(shè)備，如打印機(jī)、顯示器輸出設(shè)備交互式設(shè)備用于與計(jì)算機(jī)進(jìn)行交流的一類(lèi)設(shè)備，至少包含輸入設(shè)備和輸出設(shè)備，如鼠標(biāo)、手寫(xiě)輸入設(shè)備<10

>輸入輸出設(shè)備的分類(lèi)按設(shè)備的信息組織方式分類(lèi)以字符為單位組織和處理信息的設(shè)備被稱(chēng)為字符設(shè)備傳遞或接收一連串的字符不尋址，并且沒(méi)有查找操作如鍵盤(pán)、終端、打印機(jī)等字符設(shè)備（CharacterDevice）以信息塊為單位組織和處理信息的設(shè)備被稱(chēng)為塊設(shè)備能夠隨時(shí)讀寫(xiě)設(shè)備中的任何一塊存儲(chǔ)塊如磁盤(pán)、磁帶等塊設(shè)備（BlockDevice）<11

>輸入輸出設(shè)備的分類(lèi)按設(shè)備使用時(shí)可共享性分類(lèi)獨(dú)占設(shè)備指在一個(gè)程序（作業(yè)，用戶(hù)）的整個(gè)運(yùn)行期間都必須由單個(gè)程序（作業(yè)、用戶(hù)）獨(dú)占直至該程序（作業(yè)）完成的設(shè)備獨(dú)占設(shè)備虛擬設(shè)備是指在一類(lèi)設(shè)備上模擬另一類(lèi)設(shè)備，被模擬的設(shè)備稱(chēng)為虛擬設(shè)備通常用共享設(shè)備模擬獨(dú)占設(shè)備，用高速設(shè)備模擬低速設(shè)備虛擬設(shè)備共享設(shè)備是指能夠同時(shí)讓許多程序（作業(yè)、用戶(hù)）使用的設(shè)備共享設(shè)備設(shè)備管理與文件管理的關(guān)系<12

>區(qū)別：設(shè)備管理是對(duì)計(jì)算機(jī)系統(tǒng)中所有輸入輸出設(shè)備硬件的管理，為用戶(hù)提供標(biāo)準(zhǔn)的接口來(lái)使用設(shè)備文件管理對(duì)設(shè)備里面存儲(chǔ)的數(shù)據(jù)和信息，提供一整套管理規(guī)則，以文件及其配套概念來(lái)具體實(shí)施聯(lián)系：將物理的設(shè)備資源抽象為邏輯的文件資源，使得用戶(hù)可以用統(tǒng)一、透明的方式訪問(wèn)物理設(shè)備和設(shè)備上的數(shù)據(jù)和信息在UNIX系統(tǒng)中將所有的設(shè)備都當(dāng)作文件對(duì)象來(lái)管理，通過(guò)提供給用戶(hù)一個(gè)簡(jiǎn)單易用的接口平臺(tái)，提高設(shè)備利用率，降低設(shè)備使用難度背景-2：北京大學(xué)圖書(shū)館PART7.2設(shè)備硬件和設(shè)備管理軟件的組成設(shè)備硬件的組成<14

>從硬件的角度看，設(shè)備由物理設(shè)備和電子部件兩部分組成——操作系統(tǒng)而言更注重的是其電子部件的控制方式典型的計(jì)算機(jī)系統(tǒng)其硬件結(jié)構(gòu)如圖所示：中央部分是CPU和主存，通過(guò)總線(xiàn)與第二層的接口（適配器）部件相連，第三層是各種外部設(shè)備控制器，最外層是外部設(shè)備每一種外部設(shè)備在它自己的設(shè)備控制器（一種電子部件）的控制下工作，而設(shè)備控制器則通過(guò)適配器和主機(jī)連接一種計(jì)算機(jī)外部設(shè)備硬件系統(tǒng)組織結(jié)構(gòu)圖<15

>設(shè)備控制器的組成每個(gè)設(shè)備控制器都有若干個(gè)寄存器用來(lái)與CPU進(jìn)行通信，包括控制寄存器、狀態(tài)寄存器和數(shù)據(jù)寄存器寫(xiě)入控制寄存器，操作系統(tǒng)可以控制設(shè)備發(fā)送數(shù)據(jù)、接收數(shù)據(jù)、開(kāi)啟或關(guān)閉讀取狀態(tài)寄存器，操作系統(tǒng)可以獲悉設(shè)備的狀態(tài)，如是否準(zhǔn)備好接收新的數(shù)據(jù)數(shù)據(jù)寄存器通常作為操作系統(tǒng)發(fā)出或接收數(shù)據(jù)的緩沖區(qū)控制寄存器狀態(tài)寄存器數(shù)據(jù)寄存器I/O端口地址及其編址方式<16

>為了使CPU能夠訪問(wèn)設(shè)備控制器中的寄存器，必須為每個(gè)寄存器分配唯一的地址，該地址稱(chēng)為I/O端口地址或I/O端口號(hào)I/O端口地址主要有兩種編址方式：內(nèi)存映射編址和I/O獨(dú)立編址內(nèi)存映射編址是分配給系統(tǒng)中所有端口的地址空間與內(nèi)存地址空間統(tǒng)一編址，對(duì)I/O的讀寫(xiě)操作等同于對(duì)存儲(chǔ)器的操作，這樣的系統(tǒng)稱(chēng)為內(nèi)存映射I/O（memory-mappedI/O），大部分處理器采用內(nèi)存映射I/OI/O獨(dú)立編址是分配給系統(tǒng)中所有端口的地址空間與內(nèi)存地址空間是完全獨(dú)立的操作系統(tǒng)通過(guò)對(duì)設(shè)備控制器中的寄存器進(jìn)行讀寫(xiě)操作來(lái)完成與設(shè)備的數(shù)據(jù)交換輸入輸出設(shè)備對(duì)設(shè)備控制器中的控制方式有程序直接控制方式、中斷控制方式、DMA方式和通道控制方式設(shè)備管理軟件（I/O軟件）的組成<17

>基本思想：把設(shè)備管理軟件組織成為一系列層次，較低的層處理與硬件有關(guān)的細(xì)節(jié)，并將硬件的特征與較高的層隔離；而較高的層則向用戶(hù)提供一個(gè)友好的、清晰而規(guī)整的程序接口結(jié)構(gòu)分為四層：中斷處理程序、設(shè)備驅(qū)動(dòng)程序、設(shè)備獨(dú)立的操作系統(tǒng)軟件和用戶(hù)級(jí)軟件從功能上看，設(shè)備獨(dú)立層是I/O軟件的主要部分；從代碼量上看，設(shè)備驅(qū)動(dòng)層是I/O軟件的主要部分設(shè)備管理軟件的組成設(shè)備管理軟件（I/O軟件）的組成<18

>中斷處理程序負(fù)責(zé)控制輸入輸出設(shè)備和內(nèi)存與CPU之間的數(shù)據(jù)傳送設(shè)備獨(dú)立層起到承上啟下的作用：將種類(lèi)繁多的輸入輸出設(shè)備的驅(qū)動(dòng)屏蔽起來(lái)，對(duì)用戶(hù)呈現(xiàn)出一個(gè)標(biāo)準(zhǔn)的調(diào)用接口將用戶(hù)使用輸入輸出設(shè)備的需求按照設(shè)備驅(qū)動(dòng)的要求配置參數(shù)并傳遞數(shù)據(jù)大部分I/O軟件都包含在操作系統(tǒng)中，但是用戶(hù)層軟件仍有部分是與庫(kù)函數(shù)連接在一起的，甚至還有在內(nèi)核之外運(yùn)行的程序構(gòu)成設(shè)備管理軟件的組成設(shè)備獨(dú)立性<19

>設(shè)計(jì)I/O軟件的一個(gè)最關(guān)鍵的目標(biāo)是設(shè)備獨(dú)立性（deviceindependence），即除了直接與設(shè)備硬件打交道的低層軟件之外，其他部分的軟件并不依賴(lài)于硬件右圖所示為常見(jiàn)的設(shè)備獨(dú)立層軟件實(shí)現(xiàn)的一些功能設(shè)備需要的I/O軟件功能可以在與設(shè)備獨(dú)立的軟件中實(shí)現(xiàn)，這類(lèi)軟件面向用戶(hù)應(yīng)用層并提供一個(gè)統(tǒng)一的接口與設(shè)備無(wú)關(guān)I/O軟件的功能<20

>設(shè)備獨(dú)立層軟件實(shí)現(xiàn)的功能123設(shè)備命名設(shè)備保護(hù)提供一個(gè)與設(shè)備無(wú)關(guān)的邏輯快設(shè)備獨(dú)立層的軟件負(fù)責(zé)把設(shè)備的符號(hào)名映射到相應(yīng)的設(shè)備驅(qū)動(dòng)程序上對(duì)設(shè)備進(jìn)行必要的保護(hù)，防止無(wú)授權(quán)的應(yīng)用或用戶(hù)的非法使用向上層提供統(tǒng)一大小的邏輯塊尺寸4緩沖對(duì)于常見(jiàn)的塊設(shè)備和字符設(shè)備，都使用到緩沖區(qū)567存儲(chǔ)設(shè)備的塊分配獨(dú)占設(shè)備的分配和釋放錯(cuò)誤處理

操作系統(tǒng)需要為每個(gè)磁盤(pán)設(shè)置一張空閑塊表或位圖一些設(shè)備在某一時(shí)刻只能被單個(gè)進(jìn)程使用，這就要求操作系統(tǒng)對(duì)設(shè)備使用請(qǐng)求進(jìn)行檢查一些典型的錯(cuò)誤不是輸入輸出設(shè)備的錯(cuò)誤造成的，如何處理這個(gè)錯(cuò)誤就與設(shè)備無(wú)關(guān)背景-2：北京大學(xué)圖書(shū)館PART7.3I/O設(shè)備的控制方式<22

>I/O設(shè)備的控制方式I/O設(shè)備的控制方式取決于I/O設(shè)備硬件與處理器和內(nèi)存的聯(lián)結(jié)方式以及其相應(yīng)的設(shè)備驅(qū)動(dòng)程序，主要有以下四種方式：123程序控制方式中斷控制方式DMA控制方式4通道控制方式程序控制方式<23

>程序控制方式也稱(chēng)為PIO（ProgrammedI/O，程控I/O）方式，是指由用戶(hù)進(jìn)程直接控制處理器進(jìn)行內(nèi)存和外部設(shè)備之間信息傳送的方式，如圖所示優(yōu)點(diǎn)：CPU和外設(shè)的操作能通過(guò)狀態(tài)信息得到同步，而且硬件結(jié)構(gòu)比較簡(jiǎn)單缺點(diǎn)：CPU效率較低，傳輸完全在CPU控制下完成，對(duì)外部出現(xiàn)的異常事件無(wú)實(shí)時(shí)響應(yīng)能力只適用于那些CPU執(zhí)行速度較慢，而且外部設(shè)備較少的系統(tǒng)，如單片機(jī)系統(tǒng)程序直接控制方式的傳送結(jié)構(gòu)中斷控制方式<24

>中斷是一種在發(fā)生了一個(gè)異常事件時(shí)，調(diào)用相應(yīng)處理程序（通常稱(chēng)為中斷服務(wù)程序）進(jìn)行服務(wù)的過(guò)程中斷服務(wù)程序與中斷時(shí)CPU正在執(zhí)行的進(jìn)程是相互獨(dú)立的，相互不傳遞數(shù)據(jù)采用中斷控制方式的優(yōu)點(diǎn)：CPU與外設(shè)在大部分時(shí)間內(nèi)并行工作，有效地提高了計(jì)算機(jī)的效率具有實(shí)時(shí)響應(yīng)能力，可適用于實(shí)時(shí)控制場(chǎng)合及時(shí)處理異常情況，提高計(jì)算機(jī)的可靠性如要采用中斷方式進(jìn)行數(shù)據(jù)傳送，則CPU和設(shè)備控制器就應(yīng)具備中斷機(jī)構(gòu)中斷控制方式<25

>程序中斷控制方式的處理過(guò)程如下：在CPU上運(yùn)行的進(jìn)程通過(guò)總線(xiàn)發(fā)出命令請(qǐng)求，啟動(dòng)外設(shè)工作，當(dāng)前進(jìn)程阻塞，調(diào)度程序調(diào)度其他進(jìn)程外設(shè)數(shù)據(jù)準(zhǔn)備好，置位中斷請(qǐng)求觸發(fā)器若此時(shí)中斷屏蔽觸發(fā)器狀態(tài)為非屏蔽狀態(tài)，則I/O接口向CPU發(fā)中斷請(qǐng)求（IR）CPU接受中斷請(qǐng)求，且中斷為允許中斷狀態(tài)，則中斷判優(yōu)電路工作中斷判優(yōu)電路對(duì)到達(dá)的優(yōu)先級(jí)最高的中斷請(qǐng)求給予響應(yīng)（INTA），CPU中斷正在執(zhí)行的其他進(jìn)程，轉(zhuǎn)而執(zhí)行中斷服務(wù)程序中斷控制方式的傳送結(jié)構(gòu)DMA控制方式<26

>DMA是直接內(nèi)存訪問(wèn)（DirectMemoryAccess）的縮寫(xiě)，它是一種完全由硬件執(zhí)行I/O數(shù)據(jù)交換的工作方式DMA控制器（DMAController，DMAC）從CPU完全接管對(duì)總線(xiàn)的控制，數(shù)據(jù)交換不經(jīng)過(guò)CPU，而直接在內(nèi)存和外部設(shè)備之間進(jìn)行由DMA控制器占用系統(tǒng)總線(xiàn)并向內(nèi)存發(fā)出地址和控制信號(hào)，對(duì)傳送信息的個(gè)數(shù)計(jì)數(shù)，并且以中斷方式向CPU報(bào)告?zhèn)魉筒僮鞯慕Y(jié)束DMA方式的傳送結(jié)構(gòu)如圖所示，可分為三個(gè)階段：傳送前預(yù)處理、數(shù)據(jù)傳送、傳送后處理DMA方式一般用于高速傳送成組的數(shù)據(jù)DMA方式的傳送結(jié)構(gòu)通道控制方式<27

>通道（channel）是一個(gè)特殊功能的處理器，它有自己的指令和程序，可以實(shí)現(xiàn)對(duì)外部設(shè)備的統(tǒng)一管理和外部設(shè)備與內(nèi)存之間的數(shù)據(jù)傳送與DMA方式相比，通道方式增加了CPU與通道操作的并行能力；增加了通道之間以及同一通道內(nèi)各設(shè)備之間的并行操作能力；為用戶(hù)提供了靈活增加外設(shè)的可能性按照信息交換方式的不同，一個(gè)系統(tǒng)中可以設(shè)立三種類(lèi)型的通道：選擇通道，優(yōu)點(diǎn)是以數(shù)據(jù)塊為單位進(jìn)行傳輸，傳輸率高；缺點(diǎn)是通道利用率低數(shù)組多路通道，優(yōu)點(diǎn)是同選擇通道一樣，以數(shù)據(jù)塊為單位進(jìn)行傳輸，傳輸率高，又具有多路并行操作的能力，通道利用率高，缺點(diǎn)是控制復(fù)雜字節(jié)多路通道，各設(shè)備與通道之間的數(shù)據(jù)傳送是以字節(jié)為單位交替進(jìn)行的，各設(shè)備輪流占用一個(gè)很短的時(shí)間片，多路并行操作能力與數(shù)組多路通道相同通道具有的功能<28

>接受CPU的指令，按指令與外部設(shè)備進(jìn)行通信從內(nèi)存讀取通道指令，執(zhí)行通道程序，向設(shè)備控制器和設(shè)備發(fā)送各種命令組織外部設(shè)備和內(nèi)存之間進(jìn)行數(shù)據(jù)傳送，并根據(jù)需要提供數(shù)據(jù)緩存的空間從外部設(shè)備得到設(shè)備的狀態(tài)信息，形成并保存通道本身的狀態(tài)信息，根據(jù)要求將這些狀態(tài)信息送到內(nèi)存的指定單元，供CPU使用將外部設(shè)備的中斷請(qǐng)求和通道本身的中斷請(qǐng)求按序及時(shí)報(bào)告CPU通道方式的數(shù)據(jù)傳送結(jié)構(gòu)背景-2：北京大學(xué)圖書(shū)館PART7.4設(shè)備分配與回收<30

>I/O設(shè)備的控制方式假定：即每一個(gè)準(zhǔn)備傳送數(shù)據(jù)的進(jìn)程都已申請(qǐng)到了它所需要的外部設(shè)備和控制器事實(shí)：由于設(shè)備和控制器資源的有限性，不是每一個(gè)進(jìn)程隨時(shí)隨地都能得到這些資源，如果申請(qǐng)進(jìn)程得不到它所申請(qǐng)的資源，將被放入資源等待隊(duì)列中等待，直到所需要的資源被釋放為了合理、高效、安全地分配和回收設(shè)備，我們從以下四個(gè)方面進(jìn)行分析123數(shù)據(jù)結(jié)構(gòu)分配原則分配策略4分配算法數(shù)據(jù)結(jié)構(gòu)<31

>1.數(shù)據(jù)結(jié)構(gòu)為了記錄系統(tǒng)內(nèi)所有設(shè)備的情況，以便對(duì)它們進(jìn)行有效的管理，引入了一些表結(jié)構(gòu)常采用的數(shù)據(jù)結(jié)構(gòu)主要含四張表（如圖所示）：系統(tǒng)設(shè)備表（SystemDeviceTable）設(shè)備控制表（DeviceControlTable）控制器控制表（COntrolerControlTable）和通道控制表（CHannelControlTable）設(shè)備（通道、控制器）等待隊(duì)列也是與設(shè)備分配有關(guān)的數(shù)據(jù)結(jié)構(gòu)，組織方式可以按照先來(lái)先服務(wù)（FIFO）的順序，也可以按照優(yōu)先級(jí)順序與設(shè)備分配有關(guān)的數(shù)據(jù)結(jié)構(gòu)分配原則<32

>2.分配原則設(shè)備分配的總原則是：要充分發(fā)揮設(shè)備的使用效率，又要避免由于不合理的分配造成進(jìn)程死鎖要做到把用戶(hù)程序和具體物理設(shè)備隔離開(kāi)來(lái)，即用戶(hù)程序面對(duì)的是邏輯設(shè)備，而分配程序?qū)⒃谙到y(tǒng)把邏輯設(shè)備轉(zhuǎn)換成物理設(shè)備之后，再根據(jù)要求的物理設(shè)備號(hào)進(jìn)行分配，設(shè)備分配方式有兩種：靜態(tài)分配，靜態(tài)分配方式不會(huì)出現(xiàn)死鎖，但設(shè)備的使用效率低，不符合分配的總原則動(dòng)態(tài)分配，動(dòng)態(tài)分配方式有利于提高設(shè)備的利用率，但如果分配算法使用不當(dāng)，則有可能造成進(jìn)程死鎖獨(dú)占設(shè)備的分配<33

>3.獨(dú)占設(shè)備的分配計(jì)算機(jī)系統(tǒng)中大量的設(shè)備是獨(dú)占設(shè)備，不能采取并發(fā)的方式使用，只能交替地使用，為此，在設(shè)備分配中采用如下的方法：設(shè)備的絕對(duì)號(hào)與相對(duì)號(hào)：為了對(duì)計(jì)算機(jī)系統(tǒng)中配置的各種不同類(lèi)型的外部設(shè)備進(jìn)行管理，系統(tǒng)為每一臺(tái)設(shè)備確定一個(gè)編號(hào)，這個(gè)確定的編號(hào)稱(chēng)為設(shè)備的“絕對(duì)號(hào)”；有時(shí)用戶(hù)可能要求同時(shí)使用幾臺(tái)同類(lèi)設(shè)備，為了避免使用時(shí)的混亂，用戶(hù)可以把自己要求使用的若干臺(tái)類(lèi)設(shè)備給出編號(hào)，由用戶(hù)在程序中定義的設(shè)備編號(hào)稱(chēng)設(shè)備的“相對(duì)號(hào)”，用戶(hù)使用“設(shè)備類(lèi)、相對(duì)號(hào)”來(lái)提出使用設(shè)備的要求設(shè)備的指定方式：用戶(hù)在申請(qǐng)獨(dú)占設(shè)備時(shí)，指定需要什么設(shè)備，指定設(shè)備的方式可以有兩種，一種是指定設(shè)備的絕對(duì)號(hào)，另一種是指定設(shè)備類(lèi)、相對(duì)號(hào)獨(dú)占設(shè)備的分配<34

>3.獨(dú)占型設(shè)備的分配和釋放操作系統(tǒng)設(shè)置“設(shè)備分配表”用來(lái)記錄計(jì)算機(jī)系統(tǒng)所配置的獨(dú)占設(shè)備類(lèi)型、臺(tái)數(shù)以及分配情況等設(shè)備分配表可由“設(shè)備類(lèi)表”和“設(shè)備表”兩部分組成“設(shè)備類(lèi)表”記錄系統(tǒng)中的各類(lèi)設(shè)備每一臺(tái)設(shè)備在“設(shè)備表”中占一個(gè)登記項(xiàng)當(dāng)設(shè)備分配給某作業(yè)后則需指出占用設(shè)備的作業(yè)名，以及用戶(hù)定義的相對(duì)號(hào)，如下圖所示獨(dú)占設(shè)備的分配<35

>3.獨(dú)占型設(shè)備的分配和釋放用戶(hù)作業(yè)申請(qǐng)某類(lèi)外部設(shè)備的過(guò)程如下：（1）用戶(hù)作業(yè)提出某類(lèi)外部設(shè)備申請(qǐng)（2）系統(tǒng)檢查“設(shè)備類(lèi)表”，如果該類(lèi)設(shè)備的現(xiàn)存臺(tái)數(shù)可以滿(mǎn)足申請(qǐng)要求，則取得該類(lèi)設(shè)備的“設(shè)備表”始址，如該類(lèi)設(shè)備的現(xiàn)存臺(tái)數(shù)不能滿(mǎn)足申請(qǐng)要求，則用戶(hù)作業(yè)進(jìn)入等待隊(duì)列（3）系統(tǒng)通過(guò)該類(lèi)設(shè)備的“設(shè)備表”始址，進(jìn)入該類(lèi)設(shè)備的“設(shè)備表”，開(kāi)始依次檢查該類(lèi)設(shè)備在設(shè)備表中的登記項(xiàng)獨(dú)占設(shè)備的分配<36

>3.獨(dú)占型設(shè)備的分配和釋放（4）在該類(lèi)設(shè)備表中的登記項(xiàng)找出“設(shè)備完好狀態(tài)”為“好”而且“分配狀態(tài)”是“未分配”的設(shè)備（5）進(jìn)行設(shè)備分配，在“設(shè)備類(lèi)表”和“設(shè)備表”中進(jìn)行如下的修改：①修改“設(shè)備類(lèi)表”中該類(lèi)設(shè)備的現(xiàn)存臺(tái)數(shù)；②把該臺(tái)設(shè)備在“設(shè)備表”中的“分配狀態(tài)”標(biāo)志改成“已分配”；③在該“設(shè)備表”中填上擬占用該設(shè)備的作業(yè)名和作業(yè)程序中定義的該設(shè)備相對(duì)號(hào)獨(dú)占設(shè)備的分配<37

>3.獨(dú)占型設(shè)備的分配和釋放（6）把已分配的該設(shè)備的絕對(duì)號(hào)與相對(duì)號(hào)的對(duì)應(yīng)關(guān)系通知用戶(hù)程序，以便用戶(hù)在分配到的設(shè)備上進(jìn)行相關(guān)的操作以右圖所示舉例舉例：一個(gè)用戶(hù)J3要申請(qǐng)1臺(tái)打印機(jī)，系統(tǒng)先查“設(shè)備類(lèi)表”，發(fā)現(xiàn)現(xiàn)存臺(tái)數(shù)為2，可以滿(mǎn)足申請(qǐng)要求，則從該類(lèi)設(shè)備的“設(shè)備表”始址開(kāi)始依次檢查該類(lèi)設(shè)備在設(shè)備表中的登記項(xiàng)“設(shè)備表”始址指向的第一臺(tái)打印機(jī)，絕對(duì)號(hào)為002p，標(biāo)志為“已分配”獨(dú)占設(shè)備的分配獨(dú)占設(shè)備的分配<38

>3.獨(dú)占型設(shè)備的分配和釋放再檢查第二臺(tái)打印機(jī)，即絕對(duì)號(hào)為003p的設(shè)備，設(shè)備狀態(tài)是“好”的，且標(biāo)志為“未分配”，于是可以把這臺(tái)絕對(duì)號(hào)為003p的打印機(jī)設(shè)備，分配給該用戶(hù)，參見(jiàn)右圖（a）分配后要修改設(shè)備類(lèi)表中打印機(jī)現(xiàn)存臺(tái)數(shù)，從2臺(tái)改為1臺(tái)，把003p設(shè)備標(biāo)志改成“已分配”，且填上占用該設(shè)備的作業(yè)名J3和作業(yè)程序中定義的相對(duì)號(hào)001，參考圖（b）當(dāng)作業(yè)J3執(zhí)行時(shí)，系統(tǒng)通過(guò)相關(guān)的作業(yè)名和相對(duì)號(hào)，就可以從設(shè)備表中的登記項(xiàng)得到設(shè)備的絕對(duì)號(hào)，最后啟動(dòng)該設(shè)備進(jìn)行需要的打印作業(yè)獨(dú)占設(shè)備的分配獨(dú)占設(shè)備的分配<39

>3.獨(dú)占型設(shè)備的分配和釋放在用戶(hù)作業(yè)使用完某臺(tái)外部設(shè)備，會(huì)發(fā)出釋放設(shè)備的命令，把設(shè)備歸還給系統(tǒng)系統(tǒng)收回設(shè)備時(shí)，需要對(duì)該臺(tái)設(shè)備的“設(shè)備表”中有關(guān)的登記項(xiàng)進(jìn)行相應(yīng)的修改，即把該臺(tái)設(shè)備在“設(shè)備表”中的“分配狀態(tài)”標(biāo)志改成“未分配”，同時(shí)在該“設(shè)備表”中撤銷(xiāo)占用該設(shè)備的作業(yè)名和設(shè)備相對(duì)號(hào)最后，在該類(lèi)設(shè)備的“設(shè)備類(lèi)表”中，把該類(lèi)設(shè)備的現(xiàn)存臺(tái)數(shù)增加1臺(tái)獨(dú)占設(shè)備的分配共享設(shè)備的分配<40

>4.共享設(shè)備的分配共享設(shè)備可被多個(gè)進(jìn)程所共享，但在每個(gè)I/O傳輸?shù)膯挝粫r(shí)間內(nèi)只由一個(gè)進(jìn)程所占有在每一個(gè)使用命令之前都隱含有一個(gè)申請(qǐng)命令，在每一個(gè)使用命令之后都隱含有一個(gè)釋放命令共享設(shè)備使用的具體方法如下：申請(qǐng)?jiān)O(shè)備：如設(shè)備被占用，進(jìn)入設(shè)備等待隊(duì)列，否則分配設(shè)備啟動(dòng)設(shè)備：I/O傳輸釋放設(shè)備：當(dāng)設(shè)備結(jié)束，發(fā)出中斷信號(hào)時(shí)，系統(tǒng)喚醒一個(gè)等待設(shè)備的進(jìn)程由于獨(dú)占設(shè)備的分配和回收必須遵守“獨(dú)占”的要求，設(shè)備利用率低，死鎖幾率增大，不利于調(diào)度，使用能將獨(dú)占設(shè)備轉(zhuǎn)變?yōu)楣蚕碓O(shè)備的技術(shù)稱(chēng)為“SPOOLing”系統(tǒng)可有效解決這個(gè)問(wèn)題背景-2：北京大學(xué)圖書(shū)館PART7.5磁盤(pán)驅(qū)動(dòng)調(diào)度磁盤(pán)驅(qū)動(dòng)調(diào)度<42

>本節(jié)討論磁盤(pán)驅(qū)動(dòng)的調(diào)度策略幾乎所有計(jì)算機(jī)都使用磁盤(pán)來(lái)存儲(chǔ)信息從存儲(chǔ)角度看，與內(nèi)存相比，磁盤(pán)有三個(gè)主要的優(yōu)點(diǎn)：可用的存儲(chǔ)容量非常大每位的價(jià)格非常低電源關(guān)掉后信息不會(huì)丟失磁盤(pán)的結(jié)構(gòu)決定了對(duì)磁盤(pán)的訪問(wèn)需要通過(guò)移動(dòng)磁頭所在的磁臂，驅(qū)動(dòng)磁盤(pán)旋轉(zhuǎn)以及選擇適當(dāng)磁頭來(lái)確定數(shù)據(jù)存放在磁盤(pán)面上的空間位置如何快速找到上述位置便是磁盤(pán)驅(qū)動(dòng)調(diào)度要做的工作信息傳輸時(shí)間<43

>一、信息傳輸時(shí)間啟動(dòng)磁盤(pán)執(zhí)行輸入輸出操作時(shí)，要把磁臂移動(dòng)到指定的磁道（柱面），再等待需要訪問(wèn)的扇區(qū)旋轉(zhuǎn)到磁頭位置下，然后讓指定的磁頭進(jìn)行讀寫(xiě)完成信息傳送執(zhí)行一次輸入輸出所花的時(shí)間有：尋道時(shí)間――磁頭在磁臂帶動(dòng)下移動(dòng)到指定磁道（柱面）所花的時(shí)間延遲時(shí)間――需要訪問(wèn)的扇區(qū)旋轉(zhuǎn)到磁頭下所需的時(shí)間傳送時(shí)間――由磁頭進(jìn)行讀寫(xiě)完成信息傳送的時(shí)間其中傳送信息所花的時(shí)間是在硬件設(shè)計(jì)就固定的；而尋道時(shí)間和延遲時(shí)間是與信息在磁盤(pán)上的位置有關(guān)右圖是訪問(wèn)磁盤(pán)的操作時(shí)間示意圖訪問(wèn)磁盤(pán)的操作時(shí)間信息傳輸時(shí)間<44

>為了減少移動(dòng)磁臂所花費(fèi)的時(shí)間，是按磁道（柱面）存放同一磁道（柱面）上的各磁道被放滿(mǎn)信息后，再放到下一個(gè)柱面上例如單張磁盤(pán)有上下二個(gè)面對(duì)應(yīng)二個(gè)磁頭：當(dāng)尋道到目標(biāo)磁道位置，上下二個(gè)磁頭同時(shí)讀取所在的磁道并緩存，再通過(guò)選擇器依次選擇相應(yīng)的緩沖區(qū)內(nèi)的數(shù)據(jù)寫(xiě)入數(shù)據(jù)時(shí)，先對(duì)緩沖區(qū)填入數(shù)據(jù)，然后只允許相應(yīng)磁頭進(jìn)行寫(xiě)操作，其他磁頭不進(jìn)行寫(xiě)入所以各磁盤(pán)存儲(chǔ)塊的編號(hào)按相同磁道（柱面）的磁頭（盤(pán)面）順序（從0號(hào)開(kāi)始編址），其次是相同磁道（柱面）的扇區(qū)順序，最后是磁道（柱面）號(hào)進(jìn)行排序在訪問(wèn)時(shí)是反過(guò)來(lái)進(jìn)行尋址，即先尋道，再等待扇區(qū)，最后選擇磁頭信息傳輸時(shí)間<45

>假定用t表示每個(gè)磁道（柱面）上的磁頭總數(shù)（或者稱(chēng)為一個(gè)柱面上的總磁道數(shù)），用s表示每個(gè)磁道（柱面）上的扇區(qū)數(shù)，則第i磁道，j磁頭，k扇區(qū)所對(duì)應(yīng)的塊b由如下公式確定：b＝k＋s×（j＋i×t）同樣根據(jù)塊號(hào)也可確定該塊在磁盤(pán)上的位置，在上述的假定下，每個(gè)柱面上有s×t個(gè)磁盤(pán)塊，為了計(jì)算第p塊在磁盤(pán)上位置，可以令：d＝s×tm＝[p/d]n=pmodd于是，第p塊在磁盤(pán)上位置為：柱面號(hào)＝m磁頭號(hào)＝[n/s]扇區(qū)號(hào)＝nmods移臂調(diào)度及調(diào)度算法<46

>二、移臂調(diào)度及調(diào)度算法在一系列訪問(wèn)的讀寫(xiě)請(qǐng)求來(lái)到時(shí)，應(yīng)該采用一定的調(diào)度策略來(lái)決定各等待訪問(wèn)的執(zhí)行次序，使尋找和延遲時(shí)間都盡可能小的那個(gè)訪問(wèn)者可以?xún)?yōu)先得到服務(wù)根據(jù)訪問(wèn)者指定的柱面位置來(lái)決定執(zhí)行次序的調(diào)度，稱(chēng)為“移臂調(diào)度”移臂調(diào)度的目的是盡可能地減少操作中的尋找時(shí)間在磁盤(pán)盤(pán)面上，0磁道在盤(pán)面的外部；號(hào)數(shù)越大，磁道越靠近盤(pán)片的中心磁盤(pán)在關(guān)機(jī)時(shí)，硬盤(pán)磁頭停放在最內(nèi)圈柱面常用的移臂調(diào)度算法有先來(lái)先服務(wù)算法、最短尋找時(shí)間優(yōu)先算法、電梯調(diào)度算法和單向掃描算法先來(lái)先服務(wù)調(diào)度算法<47

>1．先來(lái)先服務(wù)調(diào)度算法最簡(jiǎn)單的移臂調(diào)度算法是“先來(lái)先服務(wù)”調(diào)度算法，這個(gè)算法實(shí)際上不考慮訪問(wèn)者要求訪問(wèn)的物理位置，而只是考慮訪問(wèn)者提出訪問(wèn)請(qǐng)求的先后次序采用先來(lái)先服務(wù)算法決定等待訪問(wèn)者執(zhí)行輸入輸出操作的次序時(shí)磁臂來(lái)回地移動(dòng)先來(lái)先服務(wù)算法花費(fèi)的尋找時(shí)間較長(zhǎng)，執(zhí)行輸入輸出操作的總時(shí)間也很長(zhǎng)先來(lái)先服務(wù)調(diào)度算法最短尋找時(shí)間優(yōu)先調(diào)度算法<48

>2．最短尋找時(shí)間優(yōu)先調(diào)度算法最短尋找時(shí)間優(yōu)先調(diào)度算法總是從等待訪問(wèn)者中挑選尋找時(shí)間最短的那個(gè)請(qǐng)求先執(zhí)行的，而不管訪問(wèn)者到來(lái)的先后次序采用最短尋找時(shí)間優(yōu)先算法決定等待訪問(wèn)者執(zhí)行操作的次序時(shí)，讀寫(xiě)磁頭總共移動(dòng)了200多個(gè)柱面的距離，與先來(lái)先服務(wù)算法比較，大幅度地減少了尋找時(shí)間，因而縮短了為各訪問(wèn)者請(qǐng)求服務(wù)的平均時(shí)間，也就提高了系統(tǒng)效率最短尋找時(shí)間優(yōu)先調(diào)度算法電梯調(diào)度算法<49

>3．電梯調(diào)度算法“電梯調(diào)度”算法是從磁臂當(dāng)前位置開(kāi)始沿著臂的移動(dòng)方向去選擇離當(dāng)前磁臂最近的那個(gè)柱訪問(wèn)者，如果沿臂的移動(dòng)方向無(wú)請(qǐng)求訪問(wèn)時(shí)，就改變臂的移動(dòng)方向再選擇前述的同一例子來(lái)討論采用“電梯調(diào)度”算法的情況，由于磁臂的初始方向有兩個(gè)，而該算法是與磁臂的方向有關(guān)，所以分成兩種情況來(lái)討論：（1）磁臂由里向外移動(dòng)（2）磁臂由外向里移動(dòng)電梯調(diào)度算法<50

>3．電梯調(diào)度算法（舉例說(shuō)明）（1）磁臂由里向外移動(dòng)開(kāi)始時(shí)，在50號(hào)柱面執(zhí)行操作的讀寫(xiě)磁頭的磁臂方向是由里向外，趨向32號(hào)柱面的位置當(dāng)訪問(wèn)50號(hào)柱面的操作結(jié)束后，沿臂移動(dòng)方向最近的柱面是32號(hào)柱面，所以應(yīng)先為32號(hào)柱面的訪問(wèn)者服務(wù)，然后是為15號(hào)柱面的訪問(wèn)者服務(wù)由于在向外移方向已無(wú)訪問(wèn)等待者，故改變磁臂的方向，由外向里依次為各訪問(wèn)者服務(wù)這種情況下為等待訪問(wèn)者服務(wù)的次序是61，99，130，148，159，199磁臂由里向外的電梯調(diào)度

電梯調(diào)度算法<51

>3．電梯調(diào)度算法（舉例說(shuō)明）（2）磁臂由外向里移動(dòng)開(kāi)始時(shí)，正在50號(hào)柱面執(zhí)行操作的讀寫(xiě)磁頭的磁臂是由外向里（即向柱面號(hào)增大的內(nèi)圈方向）趨向61號(hào)柱面的位置當(dāng)訪問(wèn)50號(hào)柱面的操作結(jié)束后，沿臂移動(dòng)方向最近的柱面是61號(hào)柱面，所以應(yīng)先為61號(hào)柱面服務(wù)，然后按磁臂由外向里移動(dòng)的方向，依次為99，130，148，159，199柱面的訪問(wèn)者服務(wù)當(dāng)201號(hào)柱面的操作結(jié)束后，向里移動(dòng)的方向已經(jīng)無(wú)訪問(wèn)等待者，所以改變磁臂的前進(jìn)方向，由里向外依次為32、15柱面的訪問(wèn)者服務(wù)磁臂由外向里的電梯調(diào)度

電梯調(diào)度算法<52

>3．電梯調(diào)度算法“電梯調(diào)度”與“最短尋找時(shí)間優(yōu)先”都是要盡量減少磁臂移動(dòng)時(shí)所花的時(shí)間區(qū)別：“最短尋找時(shí)間優(yōu)先”不考慮磁臂的移動(dòng)方向，總是選擇離當(dāng)前讀寫(xiě)磁頭最近的那個(gè)柱面，這種選擇可能導(dǎo)致磁臂來(lái)回改變移動(dòng)方向“電梯調(diào)度”是沿著磁臂的移動(dòng)方向去選擇離當(dāng)前讀寫(xiě)磁頭最近的那個(gè)柱面的訪問(wèn)者，僅當(dāng)沿磁臂的前進(jìn)移動(dòng)方向無(wú)訪問(wèn)等待者時(shí)，才改變磁臂的前進(jìn)方向，由于磁臂改變方向是機(jī)械動(dòng)作，速度相對(duì)較慢因此，電梯調(diào)度算法是一種簡(jiǎn)單、實(shí)用且高效的調(diào)度算法但是，“電梯調(diào)度”算法在實(shí)現(xiàn)時(shí)，不僅要記住讀寫(xiě)磁頭的當(dāng)前位置，還必須記住磁臂的當(dāng)前前進(jìn)方向

單向掃描調(diào)度算法<53

>4．單向掃描調(diào)度算法不考慮訪問(wèn)者等待的先后次序，總是從0號(hào)柱面開(kāi)始向里道掃描按照各自所要訪問(wèn)的柱面位置的次序去選擇訪問(wèn)者，在磁臂到達(dá)最后一個(gè)柱面后，立即快速返回到0號(hào)柱面，返回時(shí)不為任何的訪問(wèn)者等待服務(wù)在返回到0號(hào)柱面后，再次進(jìn)行掃描單向掃描調(diào)度算法

移臂調(diào)度及調(diào)度算法<54

>除了“先來(lái)先服務(wù)”調(diào)度算法外，其余三種調(diào)度算法都是根據(jù)欲訪問(wèn)的柱面位置來(lái)進(jìn)行調(diào)度的在調(diào)度過(guò)程中可能有新的請(qǐng)求訪問(wèn)者加入，新的請(qǐng)求訪問(wèn)者加入時(shí)如果讀寫(xiě)已經(jīng)超過(guò)了它們所要訪問(wèn)的柱面位置則只能在以后的調(diào)度中被選擇執(zhí)行在多道程序設(shè)計(jì)系統(tǒng)中，在等待訪問(wèn)磁盤(pán)的多個(gè)訪問(wèn)者請(qǐng)求中，可能要求訪問(wèn)的柱面號(hào)相同但在不同磁道或不同扇區(qū)，因此在進(jìn)行移臂調(diào)度時(shí)，在按照某種算法把磁臂定位到某個(gè)柱面后，應(yīng)該在等待訪問(wèn)這個(gè)柱面的各個(gè)訪問(wèn)者的輸入輸出操作都完成之后再改變磁臂的位置旋轉(zhuǎn)調(diào)度優(yōu)化<55

>三、旋轉(zhuǎn)調(diào)度優(yōu)化在磁臂定位后有若干個(gè)訪問(wèn)者等待訪問(wèn)該柱面的情況下，若從減少輸入輸出操作總時(shí)間為目標(biāo)出發(fā)，顯然應(yīng)該優(yōu)先選擇延遲時(shí)間最短的訪問(wèn)者去執(zhí)行根據(jù)延遲時(shí)間來(lái)決定執(zhí)行次序的調(diào)度稱(chēng)為“旋轉(zhuǎn)調(diào)度”進(jìn)行旋轉(zhuǎn)調(diào)度時(shí)應(yīng)分析下列情況：若干訪問(wèn)等待者請(qǐng)求訪問(wèn)同一柱面上的不同扇區(qū)若干訪問(wèn)等待者請(qǐng)求訪問(wèn)不同柱面上的不同編號(hào)的扇區(qū)若干訪問(wèn)等待者請(qǐng)求訪問(wèn)不同柱面上的、具有相同編號(hào)的扇區(qū)旋轉(zhuǎn)調(diào)度優(yōu)化<56

>三、旋轉(zhuǎn)調(diào)度優(yōu)化（舉例）有4個(gè)訪問(wèn)第88號(hào)柱面的請(qǐng)求訪問(wèn)者，它們的訪問(wèn)要求如下圖所示，在圖中得4個(gè)訪問(wèn)的執(zhí)行次序有兩種可能：①、②、④、③，或①、③、④、②，在圖中可以看到，③和②兩個(gè)請(qǐng)求都是訪問(wèn)6號(hào)扇區(qū)，但是每一時(shí)刻只允許一個(gè)讀寫(xiě)磁頭進(jìn)行操作，所以當(dāng)6號(hào)扇區(qū)旋轉(zhuǎn)到磁頭位置下時(shí)，只有其中的一個(gè)請(qǐng)求可執(zhí)行，另一個(gè)請(qǐng)求必須等磁盤(pán)下一次把6號(hào)扇區(qū)旋轉(zhuǎn)到讀寫(xiě)磁頭位置下時(shí)才能得到服務(wù)如果按照①、②的執(zhí)行次序，在6號(hào)扇區(qū)執(zhí)行結(jié)束之后應(yīng)該訪問(wèn)8號(hào)扇區(qū)，即執(zhí)行④的請(qǐng)求，在這一圈執(zhí)行完畢之后的下一圈，再執(zhí)行另一個(gè)6號(hào)扇區(qū)的訪問(wèn)，即③的請(qǐng)求，所以整個(gè)執(zhí)行次序是①、②、④、③如果在①的請(qǐng)求執(zhí)行之后執(zhí)行③的請(qǐng)求，類(lèi)似地，后面應(yīng)該去訪問(wèn)8號(hào)扇區(qū)，即執(zhí)行④的請(qǐng)求，而在這一圈執(zhí)行完畢之后的下一圈，再執(zhí)行另一個(gè)6號(hào)扇區(qū)的訪問(wèn)，即②的請(qǐng)求。所以整個(gè)執(zhí)行次序是①、③、④、②旋轉(zhuǎn)調(diào)度示例信息的優(yōu)化分布<57

>四、信息的優(yōu)化分布記錄在磁道上的排列方式也會(huì)影響磁盤(pán)的輸入輸出操作的時(shí)間舉例：假設(shè)某個(gè)系統(tǒng)在磁盤(pán)初始化時(shí)把磁盤(pán)的盤(pán)面分成8個(gè)扇區(qū)，今有8個(gè)邏輯記錄被存放在同一個(gè)磁道上的這8個(gè)扇區(qū)中，供處理程序使用，處理程序要求順序處理這8個(gè)記錄，從1至8，每次處理程序請(qǐng)求從磁盤(pán)上讀出一個(gè)邏輯記錄，然后程序?qū)γ總€(gè)讀出的記錄花費(fèi)10毫秒的時(shí)間進(jìn)行運(yùn)算處理，接著再讀出下一個(gè)記錄進(jìn)行類(lèi)似的處理，直至這8個(gè)記錄都處理結(jié)束，假定磁盤(pán)轉(zhuǎn)速為40毫秒/周，8個(gè)邏輯記錄依次存放在磁道上，如圖（a）所示磁盤(pán)信息的優(yōu)化分布

信息的優(yōu)化分布<58

>四、信息的優(yōu)化分布由磁盤(pán)轉(zhuǎn)速可知，讀一個(gè)記錄要花5毫秒的時(shí)間。當(dāng)花了5毫秒的時(shí)間讀出第1個(gè)記錄，并花費(fèi)10毫秒時(shí)間進(jìn)行處理后，第4個(gè)記錄的位置已經(jīng)轉(zhuǎn)到讀寫(xiě)磁頭下面為了順序處理第2個(gè)記錄，必須等待磁盤(pán)把第2個(gè)記錄旋轉(zhuǎn)到讀寫(xiě)磁頭位置下面，即要30毫秒的延遲時(shí)間于是，處理這8個(gè)記錄所要花時(shí)間為：8×（5+10）+7×30＝330（ms）

如果我們把上述8個(gè)邏輯記錄在磁道上的位置重新進(jìn)行優(yōu)化安排，使得當(dāng)讀出一個(gè)記錄并對(duì)之處理完畢之后，讀寫(xiě)磁頭正好處于需要讀出的下一個(gè)記錄位置上，于是可立即讀出該記錄磁盤(pán)信息的優(yōu)化分布

信息的優(yōu)化分布<59

>四、信息的優(yōu)化分布在圖中，是對(duì)這8個(gè)邏輯記錄進(jìn)行的最優(yōu)分布處理后的示意圖，按圖（b）的安排，程序處理這8個(gè)記錄所要花費(fèi)的時(shí)間變?yōu)椋?×（5＋10）=120（ms）

這個(gè)結(jié)果說(shuō)明，在對(duì)磁盤(pán)上信息分布進(jìn)行優(yōu)化分布之后，整個(gè)程序的處理時(shí)間從330毫秒降低為120毫秒，可見(jiàn)優(yōu)化分布有利于減少延遲時(shí)間，從而縮短了整個(gè)輸入輸出操作的時(shí)間對(duì)于一些能預(yù)知處理要求的信息在磁盤(pán)上的記錄位置，采用優(yōu)化分布可以提高系統(tǒng)的效率磁盤(pán)信息的優(yōu)化分布

背景-3：西門(mén)華表緩沖技術(shù)PART7.6緩沖的引入<61

>1.緩沖的引入中斷、DMA和通道控制技術(shù)使得系統(tǒng)中各I/O設(shè)備之間、I/O設(shè)備和CPU之間可以并行工作但I(xiàn)/O設(shè)備和CPU的處理速度不匹配的問(wèn)題是客觀存在的中斷方式時(shí)容易造成數(shù)據(jù)丟失引入緩沖區(qū)的作用：解決I/O設(shè)備與處理機(jī)速度不匹配的問(wèn)題減少中斷次數(shù)緩沖的引入<62

>1.緩沖的引入為了匹配I/O設(shè)備與CPU之間的處理速度，減少外部中斷的次數(shù)和CPU進(jìn)行中斷處理所花費(fèi)時(shí)間，并且解決DMA或通道方式中可能出現(xiàn)的瓶頸問(wèn)題，通常都需要在設(shè)備管理中引入用來(lái)暫存數(shù)據(jù)的緩沖技術(shù)根據(jù)I/O控制方式的不同，實(shí)現(xiàn)緩沖區(qū)的方法有兩種采用專(zhuān)用的硬件設(shè)置數(shù)據(jù)緩沖區(qū)——這種方法常常應(yīng)用在外部設(shè)備的I/O控制器中，在現(xiàn)代的外部設(shè)備中，無(wú)論是噴墨打印機(jī)、激光打印機(jī)還是普通的鍵盤(pán)中，都設(shè)有采用專(zhuān)用硬件的數(shù)據(jù)緩沖區(qū)在內(nèi)存劃出一定容量的專(zhuān)用數(shù)據(jù)緩沖區(qū)，以便存放輸入／輸出的數(shù)據(jù)——這種設(shè)置在內(nèi)存的緩沖區(qū)又稱(chēng)為“軟件緩沖”緩沖的種類(lèi)<63

>2.緩沖的種類(lèi)根據(jù)系統(tǒng)設(shè)置的緩沖區(qū)的個(gè)數(shù)，緩沖技術(shù)分為單緩沖、雙緩沖和多緩沖以及緩沖池等幾種單緩沖：在I/O設(shè)備和處理機(jī)之間設(shè)置一個(gè)緩沖區(qū)，但是I/O設(shè)備和I/O設(shè)備之間仍不能通過(guò)單緩沖實(shí)現(xiàn)并行操作雙緩沖只是一種說(shuō)明設(shè)備和設(shè)備、CPU和設(shè)備并行操作的簡(jiǎn)單模型，并不能用于實(shí)際系統(tǒng)現(xiàn)代計(jì)算機(jī)系統(tǒng)中一般使用多緩沖或緩沖池結(jié)構(gòu)多緩沖是指具有多個(gè)緩沖區(qū)，其中一部分緩沖區(qū)專(zhuān)門(mén)用于輸入，另一部分緩沖區(qū)專(zhuān)門(mén)用于輸出的緩沖結(jié)構(gòu)而緩沖池則是把多個(gè)緩沖區(qū)連接起來(lái)統(tǒng)一管理，在緩沖池中的每個(gè)緩沖區(qū)既可用于輸入又可用于輸出的一種緩沖結(jié)構(gòu)緩沖池管理<64

>3.緩沖池管理緩沖池由多個(gè)緩沖區(qū)組成，而一個(gè)緩沖區(qū)由兩部分組成：一部分是用來(lái)標(biāo)識(shí)和管理該緩沖器的緩沖首部，另一部分是用于存放數(shù)據(jù)的緩沖體，系統(tǒng)把各緩沖區(qū)按其使用狀況連成三種隊(duì)列：空閑緩沖隊(duì)列em，其隊(duì)首指針為F（em），隊(duì)尾指針為L(zhǎng)（em）裝滿(mǎn)輸入數(shù)據(jù)的輸入緩沖隊(duì)列in，其隊(duì)首指針為F（in），隊(duì)尾指針為L(zhǎng)（in）裝滿(mǎn)輸出數(shù)據(jù)的輸出緩沖隊(duì)列out，其隊(duì)首指針為F（out），隊(duì)尾指針為L(zhǎng)（out）系統(tǒng)（或用戶(hù)進(jìn)程）從這三種隊(duì)列中申請(qǐng)和取出緩沖區(qū)，并用申請(qǐng)得到的緩沖區(qū)進(jìn)行存數(shù)、取數(shù)操作，在存數(shù)、取數(shù)操作結(jié)束后，再將緩沖區(qū)放入相應(yīng)的隊(duì)列，這些緩沖區(qū)被稱(chēng)為工作緩沖區(qū)，在緩沖池中，有四種工作緩沖區(qū)：用于收容設(shè)備輸入數(shù)據(jù)的收容輸入緩沖區(qū)hin用于提取設(shè)備輸入數(shù)據(jù)的提取輸入緩沖區(qū)sin用于收容CPU輸出數(shù)據(jù)的收容輸出緩沖區(qū)hout用于提取CPU輸出數(shù)據(jù)的提取輸出緩沖區(qū)sout緩沖池管理<65

>3.緩沖池管理對(duì)緩沖池的管理由如下幾個(gè)操作組成：從三種緩沖區(qū)隊(duì)列中按一定的選取規(guī)則取出一個(gè)緩沖區(qū)的過(guò)程take_buf（type）把緩沖區(qū)按一定的選取規(guī)則插入相應(yīng)的緩沖區(qū)隊(duì)列的過(guò)程add_buf（type，number）供進(jìn)程申請(qǐng)緩沖區(qū)用的過(guò)程get_buf（type，number）供進(jìn)程將緩沖區(qū)放入相應(yīng)緩沖區(qū)隊(duì)列的過(guò)程put_buf（type，work_buf）其中，參數(shù)type表示緩沖隊(duì)列類(lèi)型，number為緩沖區(qū)號(hào)，而work_buf則表示工作緩沖區(qū)類(lèi)型緩沖池的工作緩沖區(qū)如圖所示緩沖池管理<66

>3.緩沖池管理使用這幾個(gè)操作，緩沖池的工作過(guò)程可描述如下：對(duì)于輸入進(jìn)程而言，首先調(diào)用過(guò)程get_buf（em，number）從空白緩沖區(qū)隊(duì)列中取出一個(gè)緩沖號(hào)為number的空白緩沖區(qū)，將其作為收容輸入緩沖區(qū)hin，當(dāng)hin中裝滿(mǎn)了由輸入設(shè)備輸入的數(shù)據(jù)之后，系統(tǒng)調(diào)用過(guò)程put_buf（in，hin）將該緩沖區(qū)插入輸入緩沖區(qū)隊(duì)列in中對(duì)于輸出進(jìn)程而言，先調(diào)用過(guò)程get_buf（em，number）從空白緩沖區(qū)隊(duì)列中取出一個(gè)編號(hào)為number的空白緩沖區(qū)作為收容輸出緩沖區(qū)hout，待hout中裝滿(mǎn)輸出數(shù)據(jù)之后，系統(tǒng)再調(diào)用過(guò)程put_buf（out，hout）將該緩沖區(qū)插入輸出緩沖區(qū)隊(duì)列out緩沖池管理<67

>3.緩沖池管理對(duì)緩沖區(qū)的輸入數(shù)據(jù)和輸出數(shù)據(jù)的提取也是由過(guò)程get_buf和put_buf實(shí)現(xiàn)的get_buf（out，number）從輸出緩沖隊(duì)列中提取裝滿(mǎn)輸出數(shù)據(jù)的第number號(hào)緩沖區(qū)，將其作為sout，當(dāng)sout中數(shù)據(jù)輸出完畢時(shí)，系統(tǒng)調(diào)用過(guò)程put_buf（em，sout）將該緩沖區(qū)插入空白緩沖隊(duì)列g(shù)et_buf（in，number）則從輸入緩沖隊(duì)列中取出裝滿(mǎn)輸入數(shù)據(jù)的第number號(hào)緩沖區(qū)作為輸入緩沖區(qū)sin，當(dāng)CPU從中提取完所需數(shù)據(jù)之后系統(tǒng)調(diào)用過(guò)程put_buf（em，sin）將該緩沖區(qū)釋放，并插入空白緩沖隊(duì)列em中緩沖池管理<68

>3.緩沖池管理對(duì)于各緩沖區(qū)的排列以及每次取出和插入緩沖隊(duì)列的順序都應(yīng)有一定的規(guī)則最簡(jiǎn)單的方法是FIFO，即先進(jìn)先出的排列方法，采用FIFO方法也省略了對(duì)緩沖隊(duì)列的搜索時(shí)間背景-3：西門(mén)華表虛擬設(shè)備技術(shù)PART7.7虛擬設(shè)備技術(shù)<70

>虛擬設(shè)備技術(shù)，又稱(chēng)為SPOOLing技術(shù)，全稱(chēng)為SimultaneousPeripheralOperationsOn-Line，其含義是同時(shí)的外部設(shè)備聯(lián)機(jī)操作，也稱(chēng)假脫機(jī)技術(shù)是多道程序設(shè)計(jì)系統(tǒng)中處理獨(dú)占外部設(shè)備的一種方法可以提高設(shè)備利用率并縮短單個(gè)程序的響應(yīng)時(shí)間SPOOLing技術(shù)之所以被稱(chēng)為虛擬設(shè)備技術(shù)，是因?yàn)樗梢允惯M(jìn)程在所需的外部設(shè)備不存在或被占用的情況下使用該設(shè)備虛擬設(shè)備技術(shù)的實(shí)現(xiàn)原理<71

>一、虛擬設(shè)備的實(shí)現(xiàn)原理—SPOOLing系統(tǒng)工作原理SPOOLing系統(tǒng)主要包括輸入程序模塊、輸出程序模塊、作業(yè)調(diào)度程序三部分，其工作原理是：利用SPOOLing系統(tǒng)中的輸入程序模塊，在作業(yè)執(zhí)行前就利用慢速設(shè)備將作業(yè)預(yù)先輸入到后援存儲(chǔ)器（如磁盤(pán)、磁鼓，此時(shí)，這些磁盤(pán)、磁鼓稱(chēng)為輸入井）中去，稱(chēng)為預(yù)輸入，作業(yè)進(jìn)入內(nèi)存運(yùn)行后，使用數(shù)據(jù)時(shí)，直接從輸入井中取出另外，作業(yè)執(zhí)行時(shí)不必直接啟動(dòng)外部設(shè)備輸出數(shù)據(jù)，只需將這些數(shù)據(jù)寫(xiě)入輸出井（專(zhuān)門(mén)用于存放將要輸出信息的磁盤(pán)、磁鼓）中去，稱(chēng)為緩輸出，待作業(yè)全部運(yùn)行完畢，再由外部設(shè)備輸出全部數(shù)據(jù)和信息按照上述工作方式，就實(shí)現(xiàn)了對(duì)作業(yè)的輸入、組織調(diào)度和輸出管理的統(tǒng)一進(jìn)行外部設(shè)備在CPU直接控制下，又與CPU并行工作（故稱(chēng)為假脫機(jī)）SPOOLing系統(tǒng)的組成<72

>二、SPOOLing的組成和實(shí)現(xiàn)1．SPOOLing系統(tǒng)的組成（見(jiàn)右圖所示）輸入裝置和輸出裝置為獨(dú)占的I/O設(shè)備，通過(guò)通道連接到外部設(shè)備，這個(gè)外部設(shè)備通常是一個(gè)外存儲(chǔ)設(shè)備其中劃分了許多輸入井和輸出井，每一個(gè)獨(dú)占設(shè)備對(duì)應(yīng)一個(gè)井（也是一個(gè)存儲(chǔ)塊）外存儲(chǔ)設(shè)備通過(guò)通道連接到主機(jī)系統(tǒng)中，因?yàn)榇疟P(pán)可以作為共享設(shè)備使用，所以所有的獨(dú)占設(shè)備被映射到輸入井或輸出井上被當(dāng)作共享設(shè)備使用其中輸入管理模塊和輸出管理模塊是二個(gè)位于主機(jī)中的軟件程序，當(dāng)輸入井或輸出井發(fā)出中斷請(qǐng)求時(shí)進(jìn)行響應(yīng)，并服務(wù)相應(yīng)的用戶(hù)進(jìn)程，從而完成輸入輸出任務(wù)SPOOLing系統(tǒng)SPOOLing系統(tǒng)的實(shí)現(xiàn)<73

>2．SPOOLing系統(tǒng)的實(shí)現(xiàn)—打印機(jī)的值班進(jìn)程SPOOLing系統(tǒng)通常分為輸入SPOOLing和輸出SPOOLing，二者工作原理類(lèi)似以常見(jiàn)的打印機(jī)共享為例，說(shuō)明輸出SPOOLing的基本原理打印機(jī)是一種典型的獨(dú)占設(shè)備，引入SPOOLing技術(shù)后，用戶(hù)的打印請(qǐng)求傳遞給SPOOLing系統(tǒng)，而并不是真正把打印機(jī)分配給用戶(hù)SPOOLing系統(tǒng)的輸出管理模塊在磁盤(pán)上申請(qǐng)一個(gè)空閑區(qū)，把需要打印的數(shù)據(jù)傳送到里面，再把用戶(hù)的打印請(qǐng)求掛到打印隊(duì)列上如果打印機(jī)空閑，后臺(tái)打印程序就會(huì)從打印隊(duì)列中取出一個(gè)請(qǐng)求，再?gòu)拇疟P(pán)上的對(duì)應(yīng)輸出井取出數(shù)據(jù)，執(zhí)行打印操作由于磁盤(pán)是共享的，SPOOLing系統(tǒng)可以隨時(shí)響應(yīng)打印請(qǐng)求并把數(shù)據(jù)緩存起來(lái)獨(dú)占設(shè)備改造成了共享設(shè)備，從而提高了設(shè)備的利用率和系統(tǒng)效率背景-3：西門(mén)華表本章小結(jié)PART7.8本章小結(jié)<75

>本章首先總述設(shè)備管理工作的重要性，然后敘述輸入輸出設(shè)備的分類(lèi)——I/O設(shè)備由物理設(shè)備和電子部件兩部分組成系統(tǒng)對(duì)輸入輸出設(shè)備的控制模式有程序查詢(xún)方式，程序中斷方式，DMA方式和通道方式查詢(xún)方式定時(shí)對(duì)各種設(shè)備輪流詢(xún)問(wèn)一遍有無(wú)處理要求，有要求的則加以處理，在處理完I/O設(shè)備要求之后，處理機(jī)返回繼續(xù)工作，查詢(xún)占據(jù)了CPU部分處理時(shí)間，效率較低為了提高整體效率，支持多道程序和I/O設(shè)備的并行操作，采用了中斷方式控制I/O設(shè)備和內(nèi)存與CPU之間的數(shù)據(jù)傳送，DMA技術(shù)是指數(shù)據(jù)在內(nèi)存與I/O設(shè)備間直接進(jìn)行成塊傳輸DMA方式與中斷方式的主要區(qū)別：中斷方式是在數(shù)據(jù)緩沖寄存器滿(mǎn)后發(fā)出中斷，而DMA方式則在數(shù)據(jù)塊全部傳送結(jié)束時(shí)要求中斷處理，減少了中斷次數(shù)中斷方式的數(shù)據(jù)傳送是在中斷處理時(shí)由CPU控制完成的，而DMA方式則是在DMA控制器的控制下，不經(jīng)過(guò)CPU控制完成的，DMA技術(shù)提高了I/O效率，減輕了CPU負(fù)擔(dān)輸入/輸出通道是一個(gè)獨(dú)立于CPU的、專(zhuān)門(mén)管理I/O的處理機(jī)，它控制設(shè)備與內(nèi)存直接進(jìn)行數(shù)據(jù)交換本章小結(jié)<76

>I/O軟件的設(shè)計(jì)目標(biāo)是提供設(shè)備的獨(dú)立性以及對(duì)設(shè)備的統(tǒng)一命名設(shè)備分配的原則是，充分發(fā)揮設(shè)備的使用效率，但要避免死鎖為了對(duì)外部設(shè)備進(jìn)行管理，系統(tǒng)為每一臺(tái)設(shè)備確定一個(gè)編號(hào)，即設(shè)備的“絕對(duì)號(hào)”用戶(hù)對(duì)在程序中定義的、要求使用的若干設(shè)備給出的編號(hào)稱(chēng)為設(shè)備的“相對(duì)號(hào)”操作系統(tǒng)設(shè)置“設(shè)備類(lèi)表”和“設(shè)備表”記錄計(jì)算機(jī)系統(tǒng)所配置的獨(dú)占設(shè)備類(lèi)型、臺(tái)數(shù)以及分配情況共享設(shè)備可被多個(gè)進(jìn)程所共享，但在每個(gè)I/O傳輸?shù)膯挝粫r(shí)間內(nèi)只由一個(gè)進(jìn)程所占有用戶(hù)在使用共享型設(shè)備時(shí)沒(méi)有明顯的設(shè)備申請(qǐng)與設(shè)備釋放活動(dòng)，在每一個(gè)使用命令之前都隱含有一個(gè)申請(qǐng)命令，在每一個(gè)使用命令之后都隱含有一個(gè)釋放命令，在此隱含的申請(qǐng)命令和隱含的釋放命令之間，執(zhí)行了一次I/O傳輸本章小結(jié)<77

>啟動(dòng)磁盤(pán)時(shí)，要把磁臂移動(dòng)到指定的柱面，再等待指定的扇區(qū)旋轉(zhuǎn)到磁頭位置下，然后讓指定的磁頭進(jìn)行讀寫(xiě)，完成信息傳送，執(zhí)行一次輸入輸出所花的時(shí)間有：尋道時(shí)間、延遲時(shí)間和傳送時(shí)間磁盤(pán)驅(qū)動(dòng)調(diào)度由“移臂調(diào)度”和“旋轉(zhuǎn)調(diào)度”兩部分組成；常用的移臂調(diào)度算法有先來(lái)先服務(wù)、最短尋找時(shí)間優(yōu)先、電梯調(diào)度和單向掃描算法為了匹配I/O設(shè)備與CPU間的處理速度，減少外部中斷的次數(shù)和CPU中斷處理所花費(fèi)時(shí)間，并解決DMA或通道方式中可能出現(xiàn)的瓶頸，需要使用緩沖技術(shù)實(shí)現(xiàn)緩沖區(qū)的方法有兩種，采用專(zhuān)用的硬件設(shè)置數(shù)據(jù)緩沖區(qū)和在內(nèi)存劃出專(zhuān)用數(shù)據(jù)緩沖區(qū)即“軟件緩沖”緩沖區(qū)有單緩沖、雙緩沖和多緩沖以及緩沖池等幾種虛設(shè)備技術(shù)，稱(chēng)為SPOOLing技術(shù)，是多道程序設(shè)計(jì)系統(tǒng)中處理獨(dú)占I/O設(shè)備的一種方法SPOOLing包括輸入程序模塊、輸出程序模塊、作業(yè)調(diào)度程序三部分SPOOLing提高了設(shè)備利用率，縮短了用戶(hù)程序執(zhí)行時(shí)間，但并不提高CPU利用率背景-3：西門(mén)華表思考與練習(xí)PART7.9思考與練習(xí)<79

>1．設(shè)備管理的目標(biāo)和功能是什么？2．解釋設(shè)備的絕對(duì)號(hào)與相對(duì)號(hào)。3．用戶(hù)程序中采用“設(shè)備類(lèi)、相對(duì)號(hào)”的方式來(lái)使用設(shè)備有什么優(yōu)點(diǎn)？4．為什么提出“設(shè)備的獨(dú)立性”的概念？實(shí)現(xiàn)設(shè)備獨(dú)立性的好處是什么？5．什么是設(shè)備的靜態(tài)分配方式？什么是設(shè)備的動(dòng)態(tài)分配方式？各有什么特點(diǎn)？6．CPU與外部設(shè)備之間有幾種輸入/輸出控制方式？它們各自的特點(diǎn)是什么？7．啟動(dòng)磁盤(pán)執(zhí)行一次輸入輸出操作花費(fèi)時(shí)間由哪幾部分組成？8．什么是移臂調(diào)度？什么是旋轉(zhuǎn)調(diào)度？各有哪些主要的調(diào)度算法？思考與練習(xí)<80

>9．假設(shè)一個(gè)活動(dòng)頭磁盤(pán)有200道，編號(hào)從0~199。當(dāng)前磁頭正在54道上服務(wù)，并且剛剛完成了39道的請(qǐng)求?，F(xiàn)有如下訪盤(pán)請(qǐng)求序列（磁道號(hào)）：86，147，91，173，95，148，101，26，169，80，129，22試給出采用下列算法后磁頭移動(dòng)的順序和移動(dòng)總量（總磁道數(shù)）。（1）最短尋道時(shí)間優(yōu)先磁盤(pán)調(diào)度算法。（2）掃描法磁盤(pán)調(diào)度算法（假設(shè)沿磁頭移動(dòng)方向不再有訪問(wèn)請(qǐng)求時(shí)，磁頭沿相反方向移動(dòng)。）10．假設(shè)磁盤(pán)的磁臂現(xiàn)在第8號(hào)柱面上，有6個(gè)訪盤(pán)請(qǐng)求在等待，如下所示。請(qǐng)給出最省時(shí)間的響應(yīng)次序。

序號(hào)

柱面號(hào)

磁頭號(hào)

扇區(qū)號(hào)

①

9

6

3

②

7

5

6

③

15

20

6

④

9

4

4

⑤

20

9

5

⑥

7

15

2思考與練習(xí)<81

>11．假定某磁盤(pán)的旋轉(zhuǎn)速度是每圈20毫秒，格式化后每個(gè)盤(pán)面被分成10個(gè)扇區(qū)，現(xiàn)有10個(gè)邏輯記錄存放在同一磁道上，安排如下所示。

扇區(qū)號(hào)

邏輯記錄1A2B3C4D5E6F7G8H9I10J處理程序要順序處理這些記錄，每讀出一個(gè)記錄后處理程序要花4毫秒的時(shí)間進(jìn)行處理，然后再順序讀下一個(gè)記錄并處理，直到處理完這些記錄，回答：（1）順序處理完這10個(gè)記錄總共花費(fèi)了多少時(shí)間？（2）請(qǐng)給出一種記錄優(yōu)化分布的方案，使處理程序能在最短時(shí)間內(nèi)處理完這10個(gè)記錄，并計(jì)算優(yōu)化分布時(shí)需要花費(fèi)的時(shí)間。思考與練習(xí)<82

>12．假定有一個(gè)磁盤(pán)組共有100個(gè)柱面，每個(gè)柱面上有8個(gè)磁道，每個(gè)盤(pán)面被分成8個(gè)扇區(qū)，現(xiàn)有一個(gè)含有6400個(gè)邏輯記錄的文件，邏輯記錄的大小與扇區(qū)大小一致，該文件以順序結(jié)構(gòu)的形式被存放到磁盤(pán)上，柱面、磁道、扇區(qū)的編號(hào)均從“0”開(kāi)始，邏輯記錄的編號(hào)也從“0”開(kāi)始，文件信息從0柱面、0磁道、0扇區(qū)開(kāi)始存放，試問(wèn)：（1）該文件的第3680個(gè)邏輯記錄應(yīng)存放在哪個(gè)柱面的第幾磁道的第幾個(gè)扇區(qū)？（2）第78柱面的第6磁道的第6扇區(qū)中存放了該文件的第幾個(gè)邏輯記錄？13．為什么引入通道？有哪幾類(lèi)通道？它們各自的特點(diǎn)是什么？14．解釋通道命令、通道程序、地址字和通道狀態(tài)字。15．中央處理器與通道之間是怎樣配合工作的？16．設(shè)備驅(qū)動(dòng)程序的主要功能是什么？17．請(qǐng)說(shuō)明SPOOLing技術(shù)的基本思想，SPOOLing系統(tǒng)由哪些部分組成？簡(jiǎn)述它們的功能。18．SPOOLing系統(tǒng)中輸入井和輸出井的作用是什么？19．實(shí)現(xiàn)虛擬設(shè)備的主要條件是什么？20．為什么說(shuō)SPOOLing技術(shù)實(shí)現(xiàn)了虛擬設(shè)備？SPOOLing系統(tǒng)為什么能提高獨(dú)占設(shè)備的利用率？21．在什么條件下要使用緩沖技術(shù)？22．為什么相比較單緩沖，采用雙緩沖可以提高I/O的性能？23．DMA技術(shù)和通道技術(shù)的共同點(diǎn)和不同點(diǎn)是什么？感謝大家聆聽(tīng)THANKSFORTHECAREFULGUIDANCE第8章

進(jìn)程同步機(jī)制與死鎖學(xué)習(xí)目標(biāo)<85

>1．理解進(jìn)程間的相互作用及臨界區(qū)的概念和使用準(zhǔn)則2．掌握進(jìn)程同步、進(jìn)程互斥的概念和實(shí)例3．掌握信號(hào)量及Ｐ、Ｖ操作4．掌握經(jīng)典的進(jìn)程同步、進(jìn)程互斥問(wèn)題的解決方案5．掌握死鎖的基本概念、死鎖的定義6．掌握死鎖發(fā)生的原因和四個(gè)必要條件7．掌握死鎖檢測(cè)與解除方法、死鎖避免及死鎖預(yù)防的各種方法教師導(dǎo)讀<86

>1．本章內(nèi)容是關(guān)于進(jìn)程同步與進(jìn)程互斥問(wèn)題產(chǎn)生及解決方法2．信號(hào)量及Ｐ、Ｖ操作是同步互斥機(jī)制之一，可以解決各種同步互斥問(wèn)題3．生產(chǎn)者消費(fèi)者問(wèn)題和讀者寫(xiě)者問(wèn)題是典型的進(jìn)程同步互斥模型4．死鎖隨著操作系統(tǒng)的復(fù)雜度增加而產(chǎn)生，并隨著技術(shù)的發(fā)展而發(fā)展5．在應(yīng)對(duì)死鎖的策略中，平衡系統(tǒng)運(yùn)行效率、資源利用率與發(fā)生死鎖的風(fēng)險(xiǎn)是關(guān)鍵8.1進(jìn)程（線(xiàn)程）的同步與互斥8.2經(jīng)典的進(jìn)程同步問(wèn)題8.3死鎖8.4哲學(xué)家就餐問(wèn)題8.5本章小結(jié)

目錄CONTENTSPART8.1進(jìn)程（線(xiàn)程）的同步與互斥8.1進(jìn)程（線(xiàn)程）的同步與互斥<89

>

多道程序系統(tǒng)中并發(fā)進(jìn)程通常有多個(gè)。在邏輯上具有某種聯(lián)系的進(jìn)程稱(chēng)為相關(guān)進(jìn)程

如果一個(gè)進(jìn)程的執(zhí)行不影響其他進(jìn)程的執(zhí)行，且不受其他進(jìn)程的影響，則這些并發(fā)進(jìn)程相互之間是無(wú)關(guān)的

如果一個(gè)進(jìn)程的執(zhí)行影響到其他進(jìn)程的執(zhí)行，或者受其他進(jìn)程的影響，則這些并發(fā)進(jìn)程是相關(guān)的8.1.1與時(shí)間有關(guān)的錯(cuò)誤<90

>

一個(gè)進(jìn)程由于各種原因而可能被中斷，且斷點(diǎn)是不固定的。進(jìn)程被中斷后，哪個(gè)進(jìn)程可以得到運(yùn)行，而被中斷的那個(gè)進(jìn)程在什么時(shí)候再去占用處理器等等問(wèn)題，則與進(jìn)程調(diào)度策略有關(guān)

進(jìn)程執(zhí)行的速度是不能由進(jìn)程自身控制的。若干相關(guān)并發(fā)進(jìn)程共享資源，形成交替使用共享資源的情形8.1.1與時(shí)間有關(guān)的錯(cuò)誤<91

>

例如，兩個(gè)并發(fā)程序A和B共享一個(gè)公共變量n，程序A每執(zhí)行一次循環(huán)都要作n=n+1操作，程序B則在每一次循環(huán)中打印出n的值并將n重新置0。程序描述如程序8-1。8.1.1與時(shí)間有關(guān)的錯(cuò)誤<92

>

由于程序A和B的執(zhí)行都以各自獨(dú)立的速度向前推進(jìn)，它們的語(yǔ)句在時(shí)間上可任意穿插或交叉執(zhí)行，故程序A的①n=n+1操作可能在程序B的②print（n）和③n=0操作之前，也可能在它們之后或它們之間（即①出現(xiàn)在②之后，而在③之前），設(shè)在開(kāi)始某個(gè)循環(huán)之前n的值為5，則對(duì)于上面三種情形，執(zhí)行完一個(gè)循環(huán)后，打印機(jī)印出的值可以分別為6、5和5，而執(zhí)行后的n值分別為0，1，0。相同的程序可能產(chǎn)生三組不同的結(jié)果，顯然，這不是我們所希望的

產(chǎn)生了這種情形的根本原因在于：在相關(guān)并發(fā)程序中共享了公共變量，使得程序的計(jì)算結(jié)果與并發(fā)程序執(zhí)行的時(shí)間有關(guān)（如上例中的三種情形，其結(jié)果時(shí)對(duì)時(shí)錯(cuò)），所以，把它稱(chēng)為“與時(shí)間有關(guān)的錯(cuò)誤”8.1.1與時(shí)間有關(guān)的錯(cuò)誤<93

>

另一個(gè)售票系統(tǒng)例子：假設(shè)一個(gè)售票系統(tǒng)有n個(gè)售票處（或者有n個(gè)網(wǎng)絡(luò)客戶(hù)端）。在售票系統(tǒng)的公共數(shù)據(jù)庫(kù)存放著某月某日某次車(chē)次的票額，這些票額用單元Aj（j=1,2,3,…）代表。每個(gè)客戶(hù)端訪問(wèn)系統(tǒng)的公共數(shù)據(jù)庫(kù)。用P1，P2，…Pn表示各訂票的處理進(jìn)程；而R1，R2，…，Rn為各進(jìn)程執(zhí)行時(shí)所使用的存儲(chǔ)單元

當(dāng)某個(gè)售票處有旅客買(mǎi)票時(shí)，進(jìn)程如程序8-2訂票過(guò)程8.1.1與時(shí)間有關(guān)的錯(cuò)誤<94

>

由于訂票進(jìn)程執(zhí)行的時(shí)間以及要求購(gòu)買(mǎi)的車(chē)票日期和車(chē)次是隨機(jī)的，因此存在著有若干個(gè)旅客幾乎在相同的時(shí)刻、不同的終端要求購(gòu)買(mǎi)同一天同一車(chē)次的可能。于是，若干個(gè)進(jìn)程都要訪問(wèn)同一個(gè)Aj，進(jìn)程并發(fā)執(zhí)行時(shí)可能出現(xiàn)如圖8-1中所示的情況。

在圖8-1中，進(jìn)程Pi讀出的Aj值與進(jìn)程Pk讀出的Aj值相同，當(dāng)Aj≥1時(shí)，這兩個(gè)進(jìn)程Pi和Pk都認(rèn)為有票可售給旅客。于是，進(jìn)程繼續(xù)執(zhí)行，各自對(duì)余票數(shù)減1，然后把剩余的余票數(shù)存回Aj。這樣售票系統(tǒng)的公共數(shù)據(jù)庫(kù)中的票額記錄就出錯(cuò)了

如果在這些進(jìn)程處理之前，Aj=1，即剛好只剩下一張票，那么這一張票就賣(mài)給了兩個(gè)旅客，甚至是多個(gè)旅客8.1.1與時(shí)間有關(guān)的錯(cuò)誤<95

>

顯然，這也是與時(shí)間有關(guān)的錯(cuò)誤

并發(fā)執(zhí)行的進(jìn)程競(jìng)爭(zhēng)資源就是互斥關(guān)系，使用其他進(jìn)程的數(shù)據(jù)就是同步關(guān)系8.1.2進(jìn)程同步與進(jìn)程互斥<96

>

解決進(jìn)程同步與互斥的做法有兩種：一是由競(jìng)爭(zhēng)各方平等協(xié)商；二是引入進(jìn)程管理者

臨界資源是指計(jì)算機(jī)系統(tǒng)中的需要互斥使用的硬件或軟件資源，如外設(shè)、共享代碼段、共享數(shù)據(jù)結(jié)構(gòu)等。多個(gè)進(jìn)程在對(duì)臨界資源進(jìn)行寫(xiě)入或修改操作時(shí)，必須互斥地進(jìn)行

計(jì)算機(jī)系統(tǒng)中也有一些可以同時(shí)訪問(wèn)的共享資源不是臨界資源，如只讀數(shù)據(jù)

8.1.2進(jìn)程同步與進(jìn)程互斥<97

>進(jìn)程間的相互制約關(guān)系按相互感知程度分為如表8-1所列的三種類(lèi)型。資源共享的程度分成三個(gè)層次：互斥（mutualexclusion）、死鎖（deadlock）和饑餓（starvation）

保證資源的互斥使用是指多個(gè)進(jìn)程不同時(shí)使用同一個(gè)資源。避免死鎖是指避免多個(gè)進(jìn)程互不相讓而得不到足夠的資源的情況出現(xiàn)。避免饑餓是指避免某些進(jìn)程一直得不到資源8.1.2進(jìn)程同步與進(jìn)程互斥<98

>相互感知的程度交互關(guān)系一個(gè)進(jìn)程對(duì)其他進(jìn)程的影響潛在的控制問(wèn)題相互不感知（完全不了解其他進(jìn)程的存在)競(jìng)爭(zhēng)（competition）一個(gè)進(jìn)程的操作對(duì)其他進(jìn)程的結(jié)果無(wú)影響互斥，死鎖，饑餓間接感知（雙方都與第三方交互，如共享資源）通過(guò)共享進(jìn)行協(xié)作一個(gè)進(jìn)程的結(jié)果依賴(lài)于從其他進(jìn)程獲得的信息互斥，死鎖，饑餓直接感知（雙方直接交互，如通信）通過(guò)通信進(jìn)行協(xié)作一個(gè)進(jìn)程的結(jié)果依賴(lài)于從其他進(jìn)程獲得的信息死鎖，饑餓表8-1進(jìn)程間的相互制約關(guān)系8.1.2進(jìn)程同步與進(jìn)程互斥<99

>臨界資源的正確訪問(wèn)過(guò)程分成如圖8-2所示的四個(gè)部分：

1）進(jìn)入?yún)^(qū)（entrysection）：在進(jìn)入?yún)^(qū)設(shè)置相應(yīng)的“正在訪問(wèn)臨界區(qū)”標(biāo)志，檢查可否進(jìn)入臨界區(qū)；以防止其他進(jìn)程同時(shí)進(jìn)入臨界區(qū)

2）臨界區(qū)（criticalsection）：進(jìn)程中訪問(wèn)臨界資源的一段代碼

3）退出區(qū)（exitsection）：將“正在訪問(wèn)臨界區(qū)”的標(biāo)志清除

4）剩余區(qū)（remaindersection）：代碼中的其余部分

8.1.2進(jìn)程同步與進(jìn)程互斥<100

>同步機(jī)制應(yīng)遵循以下4條準(zhǔn)則1）空閑則入：任何時(shí)刻最多只有一個(gè)進(jìn)程位于臨界區(qū)。當(dāng)有進(jìn)程位于臨界區(qū)時(shí)，其他進(jìn)程不能進(jìn)入臨界區(qū)2）忙則等待：當(dāng)已有進(jìn)程處于臨界區(qū)時(shí)，后到達(dá)的進(jìn)程只能在進(jìn)入?yún)^(qū)等待3）有限等待：等待進(jìn)入臨界區(qū)的進(jìn)程不能無(wú)限期地“死等”4）讓權(quán)等待：因在進(jìn)入?yún)^(qū)等待而不能進(jìn)入臨界區(qū)的進(jìn)程，應(yīng)釋放處理機(jī)，轉(zhuǎn)換到阻塞狀態(tài)8.1.2進(jìn)程同步與進(jìn)程互斥<101

>

1．進(jìn)程互斥的軟件方法

通過(guò)平等協(xié)商方式實(shí)現(xiàn)進(jìn)程互斥的最初方法是軟件方法。其基本思路是在進(jìn)入?yún)^(qū)檢查和設(shè)置一些標(biāo)志，如果已有進(jìn)程在臨界區(qū)，則在進(jìn)入?yún)^(qū)通過(guò)循環(huán)檢查進(jìn)行等待；在退出區(qū)修改標(biāo)志

皮特遜算法（Peterson’sAlgorithm）是一種軟件實(shí)現(xiàn)的臨界區(qū)訪問(wèn)算法，其做法是：先修改臨界區(qū)標(biāo)識(shí)、后檢查、后修改者等待

以?xún)蓚€(gè)進(jìn)程為例，假設(shè)有兩個(gè)進(jìn)程Pi和Pj，其中一個(gè)公用整型變量為turn，描述允許進(jìn)入臨界區(qū)的進(jìn)程標(biāo)識(shí)；turn為i時(shí)，進(jìn)程Pi可進(jìn)入，否則不可進(jìn)入；標(biāo)志flag[i]表示進(jìn)程i想進(jìn)入臨界區(qū)，若flag[i]為T(mén)RUE，則進(jìn)程i準(zhǔn)備進(jìn)入臨界區(qū)，反之則不想進(jìn)入

8.1.2進(jìn)程同步與進(jìn)程互斥<102

>

皮特遜算法的基本思想是：每個(gè)進(jìn)程都在進(jìn)入?yún)^(qū)先將flag修改為本進(jìn)程為T(mén)RUE，而將turn設(shè)為另一個(gè)進(jìn)程，所以當(dāng)另一個(gè)進(jìn)程想進(jìn)臨界區(qū)時(shí)就可以進(jìn)入。如果兩個(gè)進(jìn)程同時(shí)希望進(jìn)入臨界區(qū)，那么turn會(huì)在幾乎同時(shí)被設(shè)成i和j，但是只有后一個(gè)賦值語(yǔ)句的結(jié)果會(huì)被保持，因此turn的最終值決定了先到的（先賦值的）進(jìn)程能進(jìn)入臨界區(qū)。圖8-3為進(jìn)程Pi的代碼

8.1.2進(jìn)程同步與進(jìn)程互斥<103

>

皮特遜算法可實(shí)現(xiàn)四條準(zhǔn)則中的前二條：空閑則入和忙則等待。但Pi和Pj會(huì)形成乒乓效應(yīng)，也就是當(dāng)Pi希望進(jìn)入臨界區(qū)而Pj無(wú)響應(yīng)時(shí)，Pi會(huì)出現(xiàn)“饑餓”現(xiàn)象。另外對(duì)于三個(gè)以上進(jìn)程間的互斥其標(biāo)識(shí)設(shè)計(jì)更為復(fù)雜

這里的根本問(wèn)題就是修改標(biāo)志和檢查標(biāo)志不能作為一個(gè)整體來(lái)執(zhí)行

8.1.2進(jìn)程同步與進(jìn)程互斥<104

>

2．進(jìn)程互斥的硬件方法軟件方法實(shí)現(xiàn)進(jìn)程互斥不適用于數(shù)目很多的進(jìn)程間的互斥

利用硬件方法的主要思路是用一條指令完成讀和寫(xiě)兩個(gè)操作，因而保證讀操作與寫(xiě)操作不被打斷。依據(jù)所采用的指令的不同硬件方法分成TS指令和Swap指令兩種

（1）Test-and-Set指令TS指令的功能是讀出指定標(biāo)志后把該標(biāo)志設(shè)置為T(mén)RUE。TS指令的功能可描述成程序8-38.1.2進(jìn)程同步與進(jìn)程互斥<105

>TS指令互斥算法是，每個(gè)臨界資源設(shè)置一個(gè)公共布爾變量lock，表示資源的兩種狀態(tài)：TRUE表示正被占用，F(xiàn)ALSE表示空閑。初值為FALSE。在進(jìn)入?yún)^(qū)利用TS進(jìn)行檢查和修改標(biāo)志lock。有進(jìn)程在臨界區(qū)時(shí)，重復(fù)檢查；直到其他進(jìn)程退出時(shí)，檢查通過(guò)。如圖8-4所示，所有要訪問(wèn)臨界資源的進(jìn)程的進(jìn)入?yún)^(qū)和退出區(qū)代碼是相同的

8.1.2進(jìn)程同步與進(jìn)程互斥<106

>（2）Swap指令（或Exchange指令）Swap指令的功能是交換兩個(gè)字（字節(jié)）的內(nèi)容。我們可用程序8-4的函數(shù)描述Swap指令的功能

8.1.2進(jìn)程同步與進(jìn)程互斥<107

>Swap指令互斥算法是，每個(gè)臨界資源設(shè)置一個(gè)公共布爾變量lock，初值為FALSE；每個(gè)進(jìn)程設(shè)置一個(gè)私有布爾變量key，用于與lock間的信息交換。在進(jìn)入?yún)^(qū)利用Swap指令交換lock與key的內(nèi)容，然后檢查key的狀態(tài)；有進(jìn)程在臨界區(qū)時(shí)，重復(fù)交換和檢查過(guò)程，直到其他進(jìn)程退出時(shí)，檢查通過(guò)。圖8-5所有要訪問(wèn)臨界資源的進(jìn)程的相關(guān)代碼8.1.2進(jìn)程同步與進(jìn)程互斥<108

>

硬件方法把修改和檢查操作合成為整體而具有明顯的優(yōu)點(diǎn)，體現(xiàn)在以下幾個(gè)方面：

1）適用范圍廣：硬件方法適用于任意數(shù)目的進(jìn)程，在單處理器和多處理器環(huán)境中完全相同

2）簡(jiǎn)單：硬件方法的標(biāo)志設(shè)置簡(jiǎn)單，含義明確，容易驗(yàn)證其正確性

3）支持多個(gè)臨界區(qū)：在一個(gè)進(jìn)程內(nèi)有多個(gè)臨界區(qū)時(shí)，只需為每個(gè)臨界區(qū)設(shè)立一個(gè)布爾變量

硬件方法的主要缺點(diǎn)包括：

1）進(jìn)程在等待進(jìn)入臨界區(qū)時(shí)，處理機(jī)為“忙等”，不能實(shí)現(xiàn)“讓權(quán)等待”

2）進(jìn)入臨界區(qū)的進(jìn)程是從等待進(jìn)程中隨機(jī)選擇的，可能導(dǎo)致“饑餓”8.1.3信號(hào)量（semaphore）和P、V原語(yǔ)<109

>

平等進(jìn)程間的協(xié)商機(jī)制存在有些問(wèn)題是平等協(xié)商無(wú)法解決的，需要引入一個(gè)地位高于進(jìn)程的管理者來(lái)解決公有資源的使用問(wèn)題

操作系統(tǒng)可以從進(jìn)程管理者的角度來(lái)處理互斥的問(wèn)題，信號(hào)量就是由操作系統(tǒng)提供的管理公有資源的有效手段8.1.3信號(hào)量（semaphore）和P、V原語(yǔ)<110

>

信號(hào)量是荷蘭學(xué)者Dijkstra于1965年提出的一種卓有成效的進(jìn)程同步機(jī)制

信號(hào)量機(jī)制所使用的P、V原語(yǔ)就來(lái)自荷蘭語(yǔ)的test（proberen）和increment（verhogen）所謂“原語(yǔ)”即指執(zhí)行中不受進(jìn)程調(diào)度和執(zhí)行的打斷，恰如一條指令

每個(gè)信號(hào)量s除一個(gè)整數(shù)值s.count（計(jì)數(shù)）外，還有一個(gè)進(jìn)程等待隊(duì)列s.queue，其中存放的是阻塞在該信號(hào)量的各個(gè)進(jìn)程的標(biāo)識(shí)

信號(hào)量只能通過(guò)初始化和兩個(gè)標(biāo)準(zhǔn)的原語(yǔ)即P原語(yǔ)和V原語(yǔ)來(lái)訪問(wèn)。P、V原語(yǔ)的執(zhí)行很好地解決了操作的整體性

信號(hào)量的初始化可指定一個(gè)非負(fù)整數(shù)值，表示空閑資源總數(shù)。若信號(hào)量為非負(fù)整數(shù)值，表示當(dāng)前的空閑資源數(shù)；若為負(fù)值，其絕對(duì)值表示當(dāng)前等待臨界區(qū)的進(jìn)程數(shù)

8.1.3信號(hào)量（semaphore）和P、V原語(yǔ)<111

>

信號(hào)量機(jī)制中P原語(yǔ)相當(dāng)于進(jìn)入?yún)^(qū)操作，V原語(yǔ)相當(dāng)于退出區(qū)操作

P原語(yǔ)所執(zhí)行的操作可用下面函數(shù)wait(s)來(lái)描述。見(jiàn)程序8-5

8.1.3信號(hào)量（semaphore）和P、V原語(yǔ)<112

>V原語(yǔ)所執(zhí)行的操作可用下面函數(shù)signal(s)來(lái)描述。見(jiàn)程序8-68.1.3信號(hào)量（semaphore）和P、V原語(yǔ)<113

>

信號(hào)量機(jī)制可實(shí)現(xiàn)臨界資源的互斥訪問(wèn)。如圖8-6所示，mutex（MUTualExclusion）為互斥信號(hào)量，其初值為1；臨界區(qū)代碼置于P(mutex)和V(mutex)原語(yǔ)之間

在使用信號(hào)量時(shí)，必須成對(duì)使用P和V原語(yǔ)。遺漏P原語(yǔ)則不能保證互斥訪問(wèn)，遺漏V原語(yǔ)則不能在使用臨界資源之后將其釋放給其他等待的進(jìn)程。P、V原語(yǔ)的使用不能次序錯(cuò)誤、重復(fù)或遺漏8.1.3信號(hào)量（semaphore）和P、V原語(yǔ)<114

>

信號(hào)量機(jī)制可實(shí)現(xiàn)進(jìn)程間的同步。如圖8-7所示前趨關(guān)系是指并發(fā)執(zhí)行的進(jìn)程P1和P2中，分別有代碼C1和C2，要求C1在C2開(kāi)始前完成執(zhí)行。我們可設(shè)置一個(gè)互斥信號(hào)量S12，其初值為0。這樣，只有在P1執(zhí)行到V(S12)后，P2才會(huì)結(jié)束P(S12)的執(zhí)行

背景-2：北京大學(xué)圖書(shū)館PART8.2經(jīng)典的進(jìn)程同步問(wèn)題<116

>8.2經(jīng)典的進(jìn)程同步問(wèn)題Dijkstra把同步問(wèn)題抽象成一種“生產(chǎn)者-消費(fèi)者關(guān)系”

生產(chǎn)者-消費(fèi)者問(wèn)題是計(jì)算機(jī)中各種實(shí)際的同步、互斥問(wèn)題的一個(gè)抽象模型。計(jì)算機(jī)系統(tǒng)中的許多問(wèn)題都可被歸結(jié)為生產(chǎn)者和消費(fèi)者關(guān)系，例如，處理并生成數(shù)據(jù)是生產(chǎn)者進(jìn)程，打印結(jié)果是消費(fèi)者進(jìn)程；在輸入時(shí)輸入進(jìn)程是生產(chǎn)者進(jìn)程，處理并生成數(shù)據(jù)是消費(fèi)者進(jìn)程<117

>8.2.1