【正文】 0000111333333331111111第4章 進(jìn)程的同步與通信（共享變量是否一定互斥使用）1. 了解多進(jìn)程環(huán)境下資源的概念、分類和特性。 　　// 對(duì)共享資源進(jìn)行寫入(不是讀寫，)操作 // 離開臨界區(qū)2. 什么是臨界區(qū)？每個(gè)進(jìn)程中訪問臨界資源的那段代碼稱為臨界區(qū)（Critical Section）（臨界資源是一次僅允許一個(gè)進(jìn)程使用的共享資源）請(qǐng)說明臨界區(qū)的代碼模式、同步原則。g_cs)。 　　 Sleep(1)。 　　 } 　 　UINT ThreadProc11(LPVOID pParam) 　　 { 　　// 進(jìn)入臨界區(qū) 　　 EnterCriticalSection(amp。 i++) 　　 { 　 　g_cArray[10 i 1] = b。 　　 return 0。 　　 AfxBeginThread(ThreadProc11, NULL)。 　 　}進(jìn)程進(jìn)入臨界區(qū)的調(diào)度原則是： 　　如果有若干進(jìn)程要求進(jìn)入空閑的臨界區(qū)，一次僅允許一個(gè)進(jìn)程進(jìn)入。 　　如果進(jìn)程不能進(jìn)入自己的臨界區(qū)，則應(yīng)讓出CPU，避免進(jìn)程出現(xiàn)“忙等”現(xiàn)象若不同進(jìn)程訪問相同臨界資源R1，它們?cè)L問臨界資源R1的代碼一定相同嗎？不一定，例如相同的循環(huán)，可以采用i++或者使用i它們控制進(jìn)入訪問臨界資源R1代碼區(qū)的同步代碼一定相同嗎？一定相同同步原則：忙碌等待（必須）：對(duì)已有進(jìn)程進(jìn)入臨界區(qū)時(shí)，其他試圖進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入臨界區(qū)。3. 請(qǐng)寫出利用1）禁止中斷結(jié)合共享標(biāo)志變量；2）多個(gè)共享標(biāo)志變量；3）硬件指令TS；4）硬件指令SWAP 等四種技術(shù)方案，實(shí)現(xiàn)臨界區(qū)同步的算法，并分別舉一例說明它們的應(yīng)用方法。Lock=false。While(flag[j]==trueamp?！瓆3）硬件指令TS:TS 功能描述：Boolean TS（boolean *lock）{Boolean old。}應(yīng)用（算法描述）：Lock=false。進(jìn)程的其他代碼；4）硬件指令SWAP功能描述：Swap(Boolean *a, boolean *b){Boolean temp。}應(yīng)用（算法描述）Pi/Pj(線程)：有全局變量lock Pi : 有局部變量key例子：P1：While(1){key=true。}用上面所列出的算法語(yǔ)句，沒有辦法實(shí)現(xiàn)【有限等待】和【讓權(quán)等待】，但通過改進(jìn)的方式和引入新的算法或許可以利用這四種方法實(shí)現(xiàn)【有限等待】和【讓權(quán)等待】4. 理解信號(hào)量的概念、定義和分類；理解具有睡眠等待機(jī)制的信號(hào)量實(shí)現(xiàn)算法。} semaphore。 } }void V (semaphore s) //signal(semaphore s) // V操作定義{ ++。 p(mutex)。=====================這部分是注解：semaphore mutex=1。 p(mutex)。用信號(hào)量解決基本同步問題：proc_A { while (1) { pute A1。 //wait for proc_B signal read(y)。 pute B1。 }}。 fork(proc_B,0)。 //緩沖池操作 here=obtain(empty) V(mutex)。 V(mutex)。 //緩沖池操作 Here=obtain(full) V(mutex)。 V(mutex)。 //互斥使用buffer semaphore full=0。 P(Fork[(i+1) mod 5)。for (i=0。按信息傳遞工作區(qū)的位置及組織方式不同,可將它進(jìn)一步分為:共享存儲(chǔ)區(qū)、管道和消息機(jī)制。(2)缺乏進(jìn)程間的同步協(xié)調(diào)的共享內(nèi)存區(qū)只是原始且低效的進(jìn)程間通信。由于進(jìn)程同步鎖交換的信息量較少且效率較低，因此稱之為低級(jí)的進(jìn)程通信方式，相應(yīng)的也將P、V原語(yǔ)稱為低級(jí)通信原語(yǔ)。 //發(fā)送者進(jìn)程標(biāo)識(shí) int size。 //消息隊(duì)列的首指針mutex 。msg_i)。 //把m復(fù)制到 msg_i = getpid()。msg_i)。void receive(int q, message * b) { j= getpid()。b)。組織結(jié)構(gòu)、主要核心模塊：隊(duì)列器（Enquener）。（這個(gè)沒法列出來，自己看看吧）4. 列舉描述可用于實(shí)時(shí)系統(tǒng)的調(diào)度算法。 進(jìn)程推進(jìn)的順序非法產(chǎn)生死鎖的必要條件：（1）互斥條件（Mutual exclusion）（2）請(qǐng)求和保存條件（保持了至少一個(gè)資源，又提出了新的請(qǐng)求）Hold and Wait（3）不可剝奪條件（No preemption）（4）環(huán)路等待條件（Circular waiting）一次性分配：在進(jìn)程運(yùn)行前，一次性的給進(jìn)程分配其所需的所有資源。數(shù)據(jù)結(jié)構(gòu)：實(shí)現(xiàn)算法：1:如果request ineed,則報(bào)錯(cuò)返回2：如果request iavailable ，則因系統(tǒng)暫無(wú)足夠資源返回3：假設(shè)進(jìn)程i的申請(qǐng)已獲批準(zhǔn)，于是修改系統(tǒng)狀態(tài)：Allocation=allocation i + request iNeed i=need –request i4:調(diào)用安全狀態(tài)算法5：若系統(tǒng)處于安全狀態(tài)，則將進(jìn)程i 申請(qǐng)的資源分配給進(jìn)程i，返回6：若系統(tǒng)處于不安全狀態(tài)，在恢復(fù)下列系統(tǒng)狀態(tài)后，系統(tǒng)不能保證安全，資源沒有分配而返回：Available=available+request iAllocation=allocation irequest iNeed i=need +request i安全性檢查：設(shè)Work（1:m）為臨時(shí)工作向量。輸入設(shè)備，指計(jì)算機(jī)“感受”外界的設(shè)備，包括鍵盤、鼠標(biāo)、掃描儀、數(shù)字化儀、觸摸屏……輸出設(shè)備：可計(jì)算機(jī)“影響”、“控制”外界的設(shè)備，如顯示器、各種CRT終端和各種硬拷貝設(shè)備類（打印機(jī)、繪圖儀……）按傳輸速率分類低速設(shè)備：幾個(gè)～幾百字節(jié)/S中速設(shè)備：比低速設(shè)備快3個(gè)兩級(jí)左右；高速設(shè)備：比低速設(shè)備快5個(gè)兩級(jí)左右；按信息交換單位分類字符設(shè)備(CHAR DEVICE)：信息存取以字節(jié)為單位、且不可尋址的中低速順序設(shè)備。232。地址識(shí)別：每個(gè)設(shè)備有一個(gè)地址；設(shè)備控制器中的接口寄存器也有地址。反之，當(dāng)用戶進(jìn)程需要向設(shè)備輸出數(shù)據(jù)時(shí)，也必須同樣發(fā)出啟動(dòng)命令啟動(dòng)設(shè)備輸出并等待輸出操作完成。以中斷驅(qū)動(dòng)控制I/O方式從設(shè)備讀數(shù)據(jù)介紹：在中斷方式下，數(shù)據(jù)的輸入按如下步驟操作: (1)首先，需要數(shù)據(jù)的進(jìn)程通過CPU發(fā)出啟動(dòng)指令啟動(dòng)外設(shè)輸入數(shù)據(jù)。 (3)當(dāng)輸入完成時(shí)，I/O控制器通過中斷請(qǐng)求線向CPU發(fā)出中斷信號(hào)。 (4)在以后的某個(gè)時(shí)刻，進(jìn)程調(diào)度程序選中提出請(qǐng)求輸入的進(jìn)程，該進(jìn)程從約定的內(nèi)存單元中取出數(shù)據(jù)做進(jìn)一步處理。另外，還要將中斷位和啟動(dòng)位置為1，以啟動(dòng)設(shè)備開始進(jìn)行數(shù)據(jù)輸入并允許中斷。特點(diǎn)：與中斷方式相比，DMA方式是在一批數(shù)據(jù)傳送完成后中斷CPU，從而大大減少了CPU進(jìn)行中斷處理的次數(shù)，且DMA方式下地?cái)?shù)據(jù)傳送是在DMA控制器控制下完成的。在通道控制方式下，CPU只需發(fā)出I/O指令，通道就能完成相應(yīng)的I/O操作，并在操作結(jié)束時(shí)向CPU發(fā)出中斷信號(hào)；同時(shí)一個(gè)通道還能控制多臺(tái)外設(shè)。(3)若數(shù)據(jù)傳送結(jié)束，則向CPU發(fā)出中斷請(qǐng)求。2）了解各種專用緩沖、公共緩沖池的作用機(jī)制和組織結(jié)構(gòu)。 雙緩沖可以提高處理機(jī)與設(shè)備的并行操作程度。只有當(dāng)兩個(gè)緩沖區(qū)都為空，進(jìn)程還要提取數(shù)據(jù)時(shí)，該進(jìn)程被迫等待。當(dāng)運(yùn)行進(jìn)程要數(shù)據(jù)時(shí)，從環(huán)形緩沖中取一個(gè)裝滿數(shù)據(jù)的緩沖區(qū)，并從此緩沖區(qū)中提取數(shù)據(jù)，out指針指向可以提取數(shù)據(jù)的第一個(gè)滿緩沖區(qū)。滿輸出數(shù)據(jù)緩沖區(qū)，所用這類緩沖區(qū)被鏈接在一起，構(gòu)成outq隊(duì)列。獨(dú)占設(shè)備定義：在申請(qǐng)?jiān)O(shè)備時(shí)，如果設(shè)備空閑，就將其獨(dú)占，不再允許其他進(jìn)程申請(qǐng)使用，一直等到該設(shè)備被釋放，才允許被其他進(jìn)程申請(qǐng)使用。分時(shí)式共享設(shè)備總能申請(qǐng)成功，只是通過I/O操作請(qǐng)求隊(duì)列將多進(jìn)程對(duì)同一設(shè)備的并發(fā)I/O操作請(qǐng)求順序化了。 每個(gè)設(shè)備驅(qū)動(dòng)程序只能處理一種設(shè)備或一類差別很小的兼容設(shè)備。 確定發(fā)什么。少數(shù)情況下，由于操作沒有任何延遲，驅(qū)動(dòng)程序無(wú)需阻塞。檢查‘排隊(duì)等候使用設(shè)備的I/O請(qǐng)求隊(duì)列’是否為空，如非空，則摘取等待隊(duì)列中的下一個(gè)I/O請(qǐng)求，并啟動(dòng)執(zhí)行之。進(jìn)行錯(cuò)誤檢查。向設(shè)備控制器寫入具體的I/O請(qǐng)求命令塊。通過規(guī)范它們的接口調(diào)用方式，上層（與設(shè)備無(wú)關(guān)I/O軟件）可調(diào)用這個(gè)容器中的子例程完成針對(duì)設(shè)備的各種I/O操作。5. 理解驅(qū)動(dòng)程序的主要作用、特性、功能和結(jié)構(gòu)模型。使用方法：在進(jìn)行寫打印機(jī)操作之前，必須以獨(dú)占方式申請(qǐng)打印機(jī)，否則如果有其他并發(fā)進(jìn)程使用同一打印機(jī)，打印紙上會(huì)交替出現(xiàn)不同打印文件的字符行，從而影響輸出效果。取自inq隊(duì)列、用于提取輸入數(shù)據(jù)的工作緩沖區(qū)(sin)。公共緩沖池： 三種類型緩沖區(qū)及隊(duì)列空閑緩沖區(qū)，所用這類緩沖區(qū)被鏈接在一起，構(gòu)成emq隊(duì)列。環(huán)形緩沖用于輸入/輸出時(shí)，還需要有兩個(gè)指針in和out。當(dāng)?shù)谝粋€(gè)緩沖區(qū)中的數(shù)據(jù)處理完后，若第二個(gè)緩沖區(qū)己填滿，則處理機(jī)又可以從第二個(gè)緩沖區(qū)中取出數(shù)據(jù)進(jìn)行處理，而輸入設(shè)備又可以裝填第一個(gè)緩沖區(qū)。設(shè)備和處理機(jī)交換數(shù)據(jù)時(shí)，先把被交換數(shù)據(jù)寫入緩沖區(qū)，然后，需要數(shù)據(jù)的設(shè)備或處理機(jī)從緩沖區(qū)取走數(shù)據(jù)。(4)在以后的某個(gè)時(shí)刻，存單元取出數(shù)據(jù)做進(jìn)一步處理進(jìn)程調(diào)度程序選中提出請(qǐng)求輸入的進(jìn)程，該進(jìn)程從指定的內(nèi)存單元取出數(shù)據(jù)做進(jìn)一步處理3. 1）簡(jiǎn)述設(shè)備緩沖的主要作用；設(shè)備緩沖是計(jì)算機(jī)系在各個(gè)層次都廣泛使用的一項(xiàng)技術(shù)，在設(shè)備管理時(shí)更是如此。通道控制方式的數(shù)據(jù)輸入過程如下:(1)當(dāng)進(jìn)程要求輸入數(shù)據(jù)時(shí)，CPU發(fā)出啟動(dòng)指令指明要進(jìn)行的I/O操作、所使用的設(shè)備號(hào)和對(duì)應(yīng)通道。通道控制方式：工作特點(diǎn)： I/O通道是一個(gè)特殊的專用CPU，能執(zhí)行與設(shè)備密切相關(guān)的指令，但通道沒有自己的內(nèi)存； 在設(shè)置通道后，CPU只需要向通道發(fā)出一條I/O指令，就可轉(zhuǎn)向其他任務(wù)。 (4) DMA控制器在傳送字節(jié)數(shù)完成時(shí)通過中斷請(qǐng)求線發(fā)出中斷信號(hào)，CPU收到中斷信號(hào)后轉(zhuǎn)中斷處理程序，喚醒等待輸入完成的進(jìn)程，并返回被中斷程序。但由于I/O控制器的數(shù)據(jù)緩沖寄存器裝滿數(shù)據(jù)后會(huì)發(fā)出中斷且數(shù)據(jù)緩沖寄存器通常較小，因此在一次數(shù)據(jù)傳送過程中發(fā)生中斷次數(shù)較多而好去大量CPU時(shí)間；如果系統(tǒng)配置的外設(shè)數(shù)目較多，切都以中斷方式進(jìn)行并行操作，則可能好去大量CPU時(shí)間或因CPU來不及處理而造成數(shù)據(jù)丟失。設(shè)備中斷處理程序?qū)⑤斎霐?shù)據(jù)寄存器中的數(shù)據(jù)傳送到某一特定內(nèi)存單元中，以便供要求輸入的進(jìn)程使用。 (2)在進(jìn)程發(fā)出指令啟動(dòng)設(shè)備之后，該進(jìn)程放棄處理機(jī)，等待輸入完成。但CPU和外設(shè)只能串行工作，且CPU的大部分時(shí)間處于循環(huán)測(cè)試狀態(tài)，是CPU的利用率大大降低；CPU在一段時(shí)間內(nèi)只能和一臺(tái)外設(shè)交換數(shù)據(jù)信息，從而不能設(shè)備間的并行工作；由于程序直接控制方式依靠測(cè)試設(shè)備狀態(tài)標(biāo)志來控制數(shù)據(jù)傳送，因此，無(wú)法發(fā)現(xiàn)和處理因設(shè)備和其他硬件所產(chǎn)生的錯(cuò)誤。程序直接I/O控制方式介紹：當(dāng)用戶進(jìn)程需要輸入數(shù)據(jù)時(shí)，有處理機(jī)向設(shè)備控制器發(fā)出一條I/O指令啟動(dòng)設(shè)備進(jìn)行輸入。232。按共享屬性分類獨(dú)享設(shè)備共享設(shè)備Spooling設(shè)備虛擬設(shè)備設(shè)備控制器的作用實(shí)現(xiàn)CPU對(duì)外設(shè)的寄存器接口級(jí)控制邏輯。原理：死鎖定理：S為死鎖狀態(tài)的充分條件是當(dāng)且僅當(dāng)資源分配圖是不可完全簡(jiǎn)化的方法：資源圖的化簡(jiǎn)（自行理解）主要思路：尋找最容易滿足，邊數(shù)較少的進(jìn)程，進(jìn)行化簡(jiǎn)；進(jìn)程化簡(jiǎ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)模型。有序資源分配：對(duì)又有的資源按類型進(jìn)行線性編號(hào)，進(jìn)程對(duì)資源的申請(qǐng)必須嚴(yán)格按資源序號(hào)提出，使得資源分配圖中不會(huì)出現(xiàn)環(huán)路，破壞了環(huán)路等待條件。產(chǎn)生死鎖原因：競(jìng)爭(zhēng)資源：（1）競(jìng)爭(zhēng)不可剝奪資源當(dāng)兩個(gè)或兩個(gè)以上進(jìn)程競(jìng)爭(zhēng)不可剝奪資源時(shí)，如進(jìn)程申請(qǐng)資源不止一種，而且不采用一次性分配方式時(shí)，容易造成死鎖。：分為主動(dòng)機(jī)制和被動(dòng)機(jī)制兩種（例如：合作式調(diào)度器、搶占式調(diào)度器、時(shí)間觸發(fā)、事件觸發(fā)）2. 了解1）CPU調(diào)度的主要類型及特點(diǎn)；2）衡量CPU調(diào)度效果的系統(tǒng)準(zhǔn)則和用戶準(zhǔn)則。 167。 //睡眠等待消息塊,可因超時(shí)退出 P()。