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

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

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

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

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

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

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

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

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

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

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

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

>設(shè)備控制器的組成每個設(shè)備控制器都有若干個寄存器用來與CPU進行通信，包括控制寄存器、狀態(tài)寄存器和數(shù)據(jù)寄存器寫入控制寄存器，操作系統(tǒng)可以控制設(shè)備發(fā)送數(shù)據(jù)、接收數(shù)據(jù)、開啟或關(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能夠訪問設(shè)備控制器中的寄存器，必須為每個寄存器分配唯一的地址，該地址稱為I/O端口地址或I/O端口號I/O端口地址主要有兩種編址方式：內(nèi)存映射編址和I/O獨立編址內(nèi)存映射編址是分配給系統(tǒng)中所有端口的地址空間與內(nèi)存地址空間統(tǒng)一編址，對I/O的讀寫操作等同于對存儲器的操作，這樣的系統(tǒng)稱為內(nèi)存映射I/O（memory-mappedI/O），大部分處理器采用內(nèi)存映射I/OI/O獨立編址是分配給系統(tǒng)中所有端口的地址空間與內(nèi)存地址空間是完全獨立的操作系統(tǒng)通過對設(shè)備控制器中的寄存器進行讀寫操作來完成與設(shè)備的數(shù)據(jù)交換輸入輸出設(shè)備對設(shè)備控制器中的控制方式有程序直接控制方式、中斷控制方式、DMA方式和通道控制方式設(shè)備管理軟件（I/O軟件）的組成<17

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

序號

柱面號

磁頭號

扇區(qū)號

①

9

6

3

②

7

5

6

③

15

20

6

④

9

4

4

⑤

20

9

5

⑥

7

15

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

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

扇區(qū)號

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

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

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

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

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

目錄CONTENTSPART8.1進程（線程）的同步與互斥8.1進程（線程）的同步與互斥<89

>

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

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

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

>

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

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

>

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

>

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

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

>

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

當(dāng)某個售票處有旅客買票時，進程如程序8-2訂票過程8.1.1與時間有關(guān)的錯誤<94

>

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

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

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

>

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

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

>

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

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

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

8.1.2進程同步與進程互斥<97

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

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

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

>臨界資源的正確訪問過程分成如圖8-2所示的四個部分：

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

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

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

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

8.1.2進程同步與進程互斥<100

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

>

1．進程互斥的軟件方法

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

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

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

8.1.2進程同步與進程互斥<102

>

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

8.1.2進程同步與進程互斥<103

>

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

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

8.1.2進程同步與進程互斥<104

>

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

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

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

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

8.1.2進程同步與進程互斥<106

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

8.1.2進程同步與進程互斥<107

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

>

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

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

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

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

硬件方法的主要缺點包括：

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

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

>

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

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

>

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

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

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

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

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

8.1.3信號量（semaphore）和P、V原語<111

>

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

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

8.1.3信號量（semaphore）和P、V原語<112

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

>

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

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

>

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

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

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

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

>8.2.1