【正文】 分條件是當(dāng)且僅當(dāng)資源分配圖是不可完全簡化的方法：資源圖的化簡（自行理解）主要思路：尋找最容易滿足，邊數(shù)較少的進(jìn)程，進(jìn)行化簡；進(jìn)程化簡之后釋放所占有的資源；重復(fù)如上過程，直到剩余的進(jìn)程出現(xiàn)死鎖或者所有的有向邊都已消去；第6章 設(shè)備管理1. 了解1）I/O系統(tǒng)的組織模型和硬件結(jié)構(gòu)模型；2）I/O設(shè)備的分類；3）設(shè)備控制器的作用和結(jié)構(gòu)模型。I/O系統(tǒng)的組織模型Hardware InterfaceDevice ControllerApplicationProcessFile ManagerDevice DriveCommandStatusDataAPIDevice Management Organization總線型I/O系統(tǒng)的結(jié)構(gòu)模型通道型I/O系統(tǒng)的結(jié)構(gòu)模型I/O設(shè)備的分類按使用特性分類存儲設(shè)備，包括磁盤、磁帶、光盤……等。輸入設(shè)備，指計(jì)算機(jī)“感受”外界的設(shè)備，包括鍵盤、鼠標(biāo)、掃描儀、數(shù)字化儀、觸摸屏……輸出設(shè)備：可計(jì)算機(jī)“影響”、“控制”外界的設(shè)備，如顯示器、各種CRT終端和各種硬拷貝設(shè)備類（打印機(jī)、繪圖儀……）按傳輸速率分類低速設(shè)備：幾個(gè)～幾百字節(jié)/S中速設(shè)備：比低速設(shè)備快3個(gè)兩級左右；高速設(shè)備：比低速設(shè)備快5個(gè)兩級左右；按信息交換單位分類字符設(shè)備(CHAR DEVICE)：信息存取以字節(jié)為單位、且不可尋址的中低速順序設(shè)備。塊設(shè)備(BLOCK DEVICE)： 信息存取以塊為單位的、快速且可尋址的設(shè)備。按共享屬性分類獨(dú)享設(shè)備共享設(shè)備Spooling設(shè)備虛擬設(shè)備設(shè)備控制器的作用實(shí)現(xiàn)CPU對外設(shè)的寄存器接口級控制邏輯。接收和識別命令數(shù)據(jù)交換與傳遞：CPU231。232?？刂破?31。232。設(shè)備； 設(shè)備到主機(jī)接口必須標(biāo)準(zhǔn)化，但控制器到設(shè)備的接口不需要標(biāo)準(zhǔn)化； 設(shè)備狀態(tài)報(bào)告。地址識別：每個(gè)設(shè)備有一個(gè)地址；設(shè)備控制器中的接口寄存器也有地址。設(shè)備控制器的結(jié)構(gòu)模型2. 理解程序直接控制、中斷控制、DMA控制和通道控制等I/O控制方式。程序直接I/O控制方式介紹：當(dāng)用戶進(jìn)程需要輸入數(shù)據(jù)時(shí)，有處理機(jī)向設(shè)備控制器發(fā)出一條I/O指令啟動設(shè)備進(jìn)行輸入。在設(shè)備輸入數(shù)據(jù)期間，處理機(jī)通過循環(huán)執(zhí)行測試指令不間斷地檢測設(shè)備狀態(tài)寄存器的值，當(dāng)設(shè)備狀態(tài)寄存器的值顯示設(shè)備輸入完成時(shí)，處理機(jī)將數(shù)據(jù)寄存器中的數(shù)據(jù)取出，送入內(nèi)存指定單元，然后再啟動設(shè)備去讀取下一個(gè)數(shù)據(jù)。反之，當(dāng)用戶進(jìn)程需要向設(shè)備輸出數(shù)據(jù)時(shí)，也必須同樣發(fā)出啟動命令啟動設(shè)備輸出并等待輸出操作完成。特點(diǎn)：優(yōu)點(diǎn)是控制簡單，也不需要多少硬件支持。但CPU和外設(shè)只能串行工作，且CPU的大部分時(shí)間處于循環(huán)測試狀態(tài)，是CPU的利用率大大降低；CPU在一段時(shí)間內(nèi)只能和一臺外設(shè)交換數(shù)據(jù)信息，從而不能設(shè)備間的并行工作；由于程序直接控制方式依靠測試設(shè)備狀態(tài)標(biāo)志來控制數(shù)據(jù)傳送，因此，無法發(fā)現(xiàn)和處理因設(shè)備和其他硬件所產(chǎn)生的錯(cuò)誤。所以，程序直接控制方式只適用于那些CPU執(zhí)行速度慢且外設(shè)較少的系統(tǒng)。以中斷驅(qū)動控制I/O方式從設(shè)備讀數(shù)據(jù)介紹：在中斷方式下，數(shù)據(jù)的輸入按如下步驟操作: (1)首先，需要數(shù)據(jù)的進(jìn)程通過CPU發(fā)出啟動指令啟動外設(shè)輸入數(shù)據(jù)。該指令同時(shí)還將狀態(tài)寄存器中的中斷允許位打開。 (2)在進(jìn)程發(fā)出指令啟動設(shè)備之后，該進(jìn)程放棄處理機(jī)，等待輸入完成。而進(jìn)程調(diào)度程序調(diào)度其他就緒進(jìn)程占據(jù)處理機(jī)。 (3)當(dāng)輸入完成時(shí)，I/O控制器通過中斷請求線向CPU發(fā)出中斷信號。CPU在接收到中斷信號之后，轉(zhuǎn)向設(shè)備中斷處理程序。設(shè)備中斷處理程序?qū)⑤斎霐?shù)據(jù)寄存器中的數(shù)據(jù)傳送到某一特定內(nèi)存單元中，以便供要求輸入的進(jìn)程使用。同時(shí)還把等待輸入完成的那個(gè)進(jìn)程喚醒，再返回到被中斷的進(jìn)程繼續(xù)執(zhí)行。 (4)在以后的某個(gè)時(shí)刻，進(jìn)程調(diào)度程序選中提出請求輸入的進(jìn)程，該進(jìn)程從約定的內(nèi)存單元中取出數(shù)據(jù)做進(jìn)一步處理。特點(diǎn)：優(yōu)點(diǎn)是能實(shí)現(xiàn)CPU與設(shè)備以及設(shè)備與設(shè)備間的并行操作，CPU的利用率較程序直接控制方式大大提高。但由于I/O控制器的數(shù)據(jù)緩沖寄存器裝滿數(shù)據(jù)后會發(fā)出中斷且數(shù)據(jù)緩沖寄存器通常較小，因此在一次數(shù)據(jù)傳送過程中發(fā)生中斷次數(shù)較多而好去大量CPU時(shí)間；如果系統(tǒng)配置的外設(shè)數(shù)目較多，切都以中斷方式進(jìn)行并行操作，則可能好去大量CPU時(shí)間或因CPU來不及處理而造成數(shù)據(jù)丟失。DMA控制器結(jié)構(gòu)及其工作處理的基本模型DMA工作特點(diǎn)： 數(shù)據(jù)傳送以塊為單位 CPU只在快傳送開始時(shí)設(shè)定DMA工作參數(shù)并啟動它，就可轉(zhuǎn)執(zhí)行其他任務(wù)； DMA工作雖然不需要CPU敢于，但需要與CPU分享總線（挪用1/4CPU周期） 塊傳送結(jié)束，DMA發(fā)出一個(gè)中斷通知CPU介紹：DMA控制方式下進(jìn)行數(shù)據(jù)輸入的過程如下: (1)當(dāng)進(jìn)程要求設(shè)備輸入一批數(shù)據(jù)時(shí)，CPU將準(zhǔn)備存放輸入數(shù)據(jù)的內(nèi)存始址以及要傳送的字節(jié)數(shù)分別送入DMA控制器中的內(nèi)存地址寄存器和傳送字節(jié)計(jì)數(shù)器。另外，還要將中斷位和啟動位置為1，以啟動設(shè)備開始進(jìn)行數(shù)據(jù)輸入并允許中斷。 (2)發(fā)出數(shù)據(jù)請求的進(jìn)程進(jìn)入等待狀態(tài)，進(jìn)程調(diào)度程序調(diào)度其他進(jìn)程占據(jù)CPU (3)輸入設(shè)備不斷地挪用CPU工作周期，將數(shù)據(jù)寄存器中的數(shù)據(jù)源源不斷地寫入內(nèi)存，直到所要求的字節(jié)全部傳送完畢。 (4) DMA控制器在傳送字節(jié)數(shù)完成時(shí)通過中斷請求線發(fā)出中斷信號，CPU收到中斷信號后轉(zhuǎn)中斷處理程序，喚醒等待輸入完成的進(jìn)程，并返回被中斷程序。 (5)在以后的某個(gè)時(shí)刻，進(jìn)程調(diào)度程序選中提出請求輸入的進(jìn)程，該進(jìn)程從指定的內(nèi)存單元取出數(shù)據(jù)并做進(jìn)一步處理。特點(diǎn)：與中斷方式相比，DMA方式是在一批數(shù)據(jù)傳送完成后中斷CPU，從而大大減少了CPU進(jìn)行中斷處理的次數(shù)，且DMA方式下地?cái)?shù)據(jù)傳送是在DMA控制器控制下完成的。但DMA方式仍有一定的局限，如對外設(shè)的管理和某些操作仍由CPU控制，多個(gè)DMA控制器的使用也不經(jīng)濟(jì)。通道控制方式：工作特點(diǎn)： I/O通道是一個(gè)特殊的專用CPU，能執(zhí)行與設(shè)備密切相關(guān)的指令，但通道沒有自己的內(nèi)存； 在設(shè)置通道后，CPU只需要向通道發(fā)出一條I/O指令，就可轉(zhuǎn)向其他任務(wù)。通道是一個(gè)專管輸入/輸出控制的處理機(jī)。在通道控制方式下，CPU只需發(fā)出I/O指令，通道就能完成相應(yīng)的I/O操作，并在操作結(jié)束時(shí)向CPU發(fā)出中斷信號；同時(shí)一個(gè)通道還能控制多臺外設(shè)。單絲，通道價(jià)格較高，從經(jīng)濟(jì)角度出發(fā)不宜過多使用。通道控制方式的數(shù)據(jù)輸入過程如下:(1)當(dāng)進(jìn)程要求輸入數(shù)據(jù)時(shí)，CPU發(fā)出啟動指令指明要進(jìn)行的I/O操作、所使用的設(shè)備號和對應(yīng)通道。(2)對應(yīng)通道接收到CPU發(fā)來的啟動指令之后，把存放在內(nèi)存中的通道程序讀出，并執(zhí)行通道程序，控制設(shè)備將數(shù)據(jù)傳送到內(nèi)存中指定的區(qū)域。(3)若數(shù)據(jù)傳送結(jié)束，則向CPU發(fā)出中斷請求。CPU收到中斷信號后轉(zhuǎn)中斷處理程序，喚醒等待輸入完成的進(jìn)程，并返回被中斷程序。(4)在以后的某個(gè)時(shí)刻，存單元取出數(shù)據(jù)做進(jìn)一步處理進(jìn)程調(diào)度程序選中提出請求輸入的進(jìn)程，該進(jìn)程從指定的內(nèi)存單元取出數(shù)據(jù)做進(jìn)一步處理3. 1）簡述設(shè)備緩沖的主要作用；設(shè)備緩沖是計(jì)算機(jī)系在各個(gè)層次都廣泛使用的一項(xiàng)技術(shù)，在設(shè)備管理時(shí)更是如此。作用：在設(shè)備管理中，引入設(shè)備緩沖，不僅可以有效提高CPU操作的速度，改善CPU與外設(shè)之間的速度不匹配的矛盾，而且可在需要重復(fù)對同一設(shè)備數(shù)據(jù)進(jìn)行I/O時(shí)，減少I/O次數(shù)。2）了解各種專用緩沖、公共緩沖池的作用機(jī)制和組織結(jié)構(gòu)。專用緩沖：分為單緩沖、雙緩沖和多緩沖（環(huán)形緩沖）三種 單緩沖是在設(shè)備和處理機(jī)之間設(shè)置一個(gè)緩沖區(qū)。設(shè)備和處理機(jī)交換數(shù)據(jù)時(shí)，先把被交換數(shù)據(jù)寫入緩沖區(qū)，然后，需要數(shù)據(jù)的設(shè)備或處理機(jī)從緩沖區(qū)取走數(shù)據(jù)。由于只設(shè)置了一個(gè)緩沖區(qū)，因而設(shè)備與處理機(jī)對緩沖區(qū)的操作是串行的。 雙緩沖可以提高處理機(jī)與設(shè)備的并行操作程度。在設(shè)備輸入時(shí)，輸入設(shè)備先將第一個(gè)緩沖區(qū)裝滿數(shù)據(jù)，在輸入設(shè)備裝填第二個(gè)緩沖區(qū)的同時(shí)，處理機(jī)可以從第一個(gè)緩沖區(qū)中取出數(shù)據(jù)供用戶進(jìn)程進(jìn)行處理。當(dāng)?shù)谝粋€(gè)緩沖區(qū)中的數(shù)據(jù)處理完后，若第二個(gè)緩沖區(qū)己填滿，則處理機(jī)又可以從第二個(gè)緩沖區(qū)中取出數(shù)據(jù)進(jìn)行處理，而輸入設(shè)備又可以裝填第一個(gè)緩沖區(qū)。顯然，雙緩沖的使用提高了處理機(jī)和輸入設(shè)備并行操作的程度。只有當(dāng)兩個(gè)緩沖區(qū)都為空，進(jìn)程還要提取數(shù)據(jù)時(shí)，該進(jìn)程被迫等待。 環(huán)形緩沖中包含多個(gè)大小相等的緩沖區(qū)，每個(gè)緩沖區(qū)中有一個(gè)鏈接指針指向下一個(gè)緩沖區(qū)，最后一個(gè)緩沖區(qū)指針指向第一個(gè)緩沖區(qū)，這樣多個(gè)緩沖區(qū)構(gòu)成一個(gè)環(huán)形。環(huán)形緩沖用于輸入/輸出時(shí)，還需要有兩個(gè)指針in和out。對于輸入而言，首先要從設(shè)備接收數(shù)據(jù)到緩沖區(qū)中，in指針指向可以輸入數(shù)據(jù)的第一個(gè)空緩沖區(qū)。當(dāng)運(yùn)行進(jìn)程要數(shù)據(jù)時(shí)，從環(huán)形緩沖中取一個(gè)裝滿數(shù)據(jù)的緩沖區(qū)，并從此緩沖區(qū)中提取數(shù)據(jù)，out指針指向可以提取數(shù)據(jù)的第一個(gè)滿緩沖區(qū)。顯然，對輸出而言正好相反，進(jìn)程將處理過的需要輸出的數(shù)據(jù)送到空緩沖區(qū)中，而當(dāng)設(shè)備空閑時(shí)，從滿緩沖區(qū)中取出數(shù)據(jù)由設(shè)備輸出。公共緩沖池： 三種類型緩沖區(qū)及隊(duì)列空閑緩沖區(qū)，所用這類緩沖區(qū)被鏈接在一起，構(gòu)成emq隊(duì)列。滿輸入數(shù)據(jù)緩沖區(qū)，所用這類緩沖區(qū)被鏈接在一起，構(gòu)成inq隊(duì)列。滿輸出數(shù)據(jù)緩沖區(qū)，所用這類緩沖區(qū)被鏈接在一起，構(gòu)成outq隊(duì)列。 四種工作緩沖區(qū)取自emq隊(duì)列、用于收容輸入數(shù)據(jù)的工作緩沖區(qū)(hin)。取自inq隊(duì)列、用于提取輸入數(shù)據(jù)的工作緩沖區(qū)(sin)。取自emq隊(duì)列、用于收容輸出數(shù)據(jù)的工作緩沖區(qū)(sout)取自outq隊(duì)列、用于提取輸出數(shù)據(jù)的工作緩沖區(qū)(hout)收容輸入的工作過程： 調(diào)用GetBuf（emq），從emq隊(duì)列首摘下一個(gè)空緩沖區(qū)，作為hin （設(shè)備驅(qū)動）將設(shè)備數(shù)據(jù)填入hin 再調(diào)AddBuf（inq，hin）提取輸入的工作過程： 調(diào)GetBuf（inq），從inq隊(duì)列首摘下一個(gè)空緩沖區(qū)，作為sin 用戶進(jìn)程使用sin 再調(diào)用AddBuf（emq，sin） 收容輸出工作過程 調(diào)GetBuf（emq），從emq隊(duì)列首摘下一個(gè)空緩沖區(qū)，作為sout 進(jìn)程數(shù)據(jù)填入sout 調(diào)用AddBuf（outq，sout） 提取輸出工作過程 調(diào)GetBuf（outq），從outq隊(duì)列首摘下一個(gè)空緩沖區(qū)，作為hout 進(jìn)程數(shù)據(jù)填入hout 調(diào)用AddBuf（emq，hout）4. 理解獨(dú)占設(shè)備、SPOOLING設(shè)備和分時(shí)共享設(shè)備的特點(diǎn)和使用方法。獨(dú)占設(shè)備定義：在申請?jiān)O(shè)備時(shí)，如果設(shè)備空閑，就將其獨(dú)占，不再允許其他進(jìn)程申請使用，一直等到該設(shè)備被釋放，才允許被其他進(jìn)程申請使用。特點(diǎn)：保證該進(jìn)程的操作不被其他進(jìn)程的針對同一外部設(shè)備資源的操作打擾，相當(dāng)于為外部設(shè)備加鎖，但設(shè)備利用率低。使用方法：在進(jìn)行寫打印機(jī)操作之前，必須以獨(dú)占方式申請打印機(jī)，否則如果有其他并發(fā)進(jìn)程使用同一打印機(jī)，打印紙上會交替出現(xiàn)不同打印文件的字符行，從而影響輸出效果。SPOOLING設(shè)備：特點(diǎn)：對I/O操作進(jìn)行批量處理，速度快使用方法：假脫機(jī)I/O方式由三部分組成:輸入井和輸出井，輸入緩沖區(qū)和輸出緩沖區(qū)，輸入進(jìn)程和輸出進(jìn)程分時(shí)共享設(shè)備：特點(diǎn)：分時(shí)共享是一種細(xì)粒度的分時(shí)使用設(shè)備，不同進(jìn)程的I/O操作請求以排隊(duì)方式分時(shí)的占用設(shè)備進(jìn)行I/O。分時(shí)式共享設(shè)備總能申請成功，只是通過I/O操作請求隊(duì)列將多進(jìn)程對同一設(shè)備的并發(fā)I/O操作請求順序化了。使用方法：將I/O操作請求排入隊(duì)列，設(shè)備驅(qū)動程序會依次按隊(duì)列中的請求啟動設(shè)備進(jìn)行I/O操作。5. 理解驅(qū)動程序的主要作用、特性、功能和結(jié)構(gòu)模型。定義：直接與（抽象）硬件打交道的軟件模塊，其任務(wù)是接受上層與設(shè)備無關(guān)的I/O軟件（設(shè)備獨(dú)立性軟件）的抽象請求，并進(jìn)行與設(shè)備相關(guān)的處理設(shè)備驅(qū)動程序的主要特性 封裝了與對應(yīng)設(shè)備相關(guān)的、所有或某方面的操作代碼，例如，OS中操縱/使用設(shè)備控制器的代碼肯定都已被集中到某個(gè)驅(qū)動程序中。 每個(gè)設(shè)備驅(qū)動程序只能處理一種設(shè)備或一類差別很小的兼容設(shè)備?？砂羊?qū)動程序看作是一個(gè)容器，其中包含了一組設(shè)備I/O操作子例程。通過規(guī)范它們的接口調(diào)用方式，上層（與設(shè)備無關(guān)I/O軟件）可調(diào)用這個(gè)容器中的子例程完成針對設(shè)備的各種I/O操作。設(shè)備驅(qū)動程序的主要功能 確定是否發(fā)請求。 確定發(fā)什么。 發(fā)布命令。向設(shè)備控制器寫入具體的I/O請求命令塊。 命令發(fā)出后處理，分兩種情況：大多數(shù)情況下，設(shè)備完成指定操作需要一定時(shí)間，驅(qū)動程序阻塞，直到驅(qū)動程序的中斷處理相關(guān)子例程解除其阻塞。少數(shù)情況下，由于操作沒有任何延遲，驅(qū)動程序無需阻塞。 設(shè)備操作完成中斷發(fā)生時(shí)，由被作為中斷處理程序的那部分驅(qū)動程序，完成如下的事后處理。進(jìn)行錯(cuò)誤檢查。檢查可能的喚醒。檢查‘排隊(duì)等候使用設(shè)備的I/O請求隊(duì)列’是否為空，如非空，則摘取等待隊(duì)列中的下一個(gè)I/O請求，并啟動執(zhí)行之。設(shè)備驅(qū)動程序的結(jié)構(gòu)1