【正文】 ? 如中斷、信號(hào)（ signals)、消。 ? 這樣進(jìn)程 P P2都會(huì)因?yàn)榈却龑?duì)方占用的資源而阻塞，出現(xiàn)死鎖。 ? 假設(shè)這時(shí)，表格 T2被進(jìn)程 P2占用且鎖定，則進(jìn)程P1阻塞等待。 ? 如處理機(jī)、 I/O通道和設(shè)備、內(nèi) /外存儲(chǔ)器、諸如文件、數(shù)據(jù)庫和信號(hào)量之類的數(shù)據(jù)結(jié)構(gòu)等。 ? 系統(tǒng)中的資源大體可以分為兩類：可重用資源和可消耗資源。當(dāng)然，如果能提前預(yù)防和避免死鎖的出現(xiàn)，將能提高系統(tǒng)的運(yùn)行效率。 交通中的死鎖現(xiàn)象 進(jìn)程競爭資源可能引起死鎖 Process P … Get A , Get B , Release A , Release B , Process Q … Get B … Get A … Release B … Release A … 進(jìn)程競爭資源且推進(jìn)順序不當(dāng)可能產(chǎn)生死鎖 修改進(jìn)程 P,Q代碼 Process P … Get A , Release A , Get B , Release B , Process Q … Get B … Release B … Get A … Release A … 死鎖的定義 ? 死鎖 (deadlock)概念可以描述為，多個(gè)進(jìn)程因?yàn)楦偁庂Y源，或執(zhí)行時(shí)推進(jìn)的順序不當(dāng)，或相互通信而永久阻塞現(xiàn)象，如果沒有外力作用，這種現(xiàn)象將永遠(yuǎn)保持下去。 ? 一旦出現(xiàn)進(jìn)程死鎖，相應(yīng)的進(jìn)程將無法向前推進(jìn)。 ? 如果消費(fèi)者消費(fèi)數(shù)據(jù)的速度更快，則消費(fèi)者將因?yàn)榻邮詹坏健皵?shù)據(jù)”消息而阻塞，直到生產(chǎn)者生產(chǎn)并發(fā)送來一條“數(shù)據(jù)”消息。 ? 通過這種方式進(jìn)行數(shù)據(jù)傳遞，系統(tǒng)中的總消息數(shù)保持不變，所以，消息可以存入在預(yù)知數(shù)量的內(nèi)存中。 利用消息傳遞解決生產(chǎn)者－消費(fèi)者問題 ? 共使用了 capacity條消息，類似于共享內(nèi)存緩沖區(qū)中的 capacity個(gè)存儲(chǔ)單元。 ? 可見，控制進(jìn)程互斥進(jìn)入臨界區(qū)的這條消息本身可以不含任何有用的內(nèi)容，它僅被當(dāng)作進(jìn)程能否進(jìn)入臨界區(qū)的一種憑證，或令牌。這時(shí)，郵箱 mutex變?yōu)椤翱铡?，即沒有消息．其后執(zhí)行receive(mutex,msg)語句希望進(jìn)入臨界區(qū)的進(jìn)程被阻塞。 … P(n) parend 注意 ? “空”消息：代表一條消息體為“空”，但具有消息頭的“真正”的一條消息，不是沒有消息。 /*創(chuàng)建郵箱 */ Send(mutex_null)。 send(mutex,msg)。 Begin repeat receive(mutex,msg)。 /* 進(jìn)程數(shù) */ Procedure P(I:integer)。 ? 如果一個(gè)進(jìn)程希望進(jìn)入臨界區(qū)，首先必須申請(qǐng)從mutex郵箱中接收一條消息．若郵箱為“空”，則該進(jìn)程阻塞（接收）；若進(jìn)程收到郵箱中的一條消息，則進(jìn)入臨界區(qū)，執(zhí)行完畢以后，退出臨界區(qū)，并將該消息發(fā)送回郵箱 mutex中。 利用消息傳遞實(shí)現(xiàn)互斥 ? 采用“不阻塞發(fā)送，阻塞接收”方式。 ? 發(fā)送進(jìn)程將消息發(fā)送到指定的郵箱中，接收進(jìn)程從郵箱中接收消息。 ?接收進(jìn)程可以不必指定接收哪個(gè)進(jìn)程的消息。 ? 若采用直接尋址， send原語中必須指定目標(biāo)進(jìn)程的具體標(biāo)識(shí)號(hào)。 ? 如果采用“不阻塞接收”方式，則可能因?yàn)榻邮辗降木壒?，丟失消息。 ? 設(shè)計(jì)并發(fā)程序時(shí)，若采用“不阻塞發(fā)送”方式，就必須在程序中考慮讓接收進(jìn)程發(fā)回應(yīng)答消息，證實(shí)其是否收到消息，這將增加程序設(shè)計(jì)的難度。 “不阻塞發(fā)送” ? 例如，當(dāng)進(jìn)程執(zhí)行過程中需要打印輸出，通常讓打印任務(wù)排隊(duì)等待，而請(qǐng)求打印的進(jìn)程無須阻塞等待打印完成，即，每當(dāng)進(jìn)程需要打印時(shí)，都可以以消息形式發(fā)出請(qǐng)求，然后繼續(xù)執(zhí)行。 ? 不阻塞發(fā)送，阻塞接收；常用于服務(wù)進(jìn)程為其它進(jìn)程提供服務(wù)。 ? 即，當(dāng)發(fā)送進(jìn)程調(diào)用 Send原語發(fā)送消息時(shí)，若沒有空閑的消息緩沖區(qū)，則發(fā)送進(jìn)程阻塞；當(dāng)接收進(jìn)程調(diào)用 Receive原語接收消息時(shí)，如果沒有消息可接收，由接收進(jìn)程阻塞，直到一條消息到達(dá)。然后，申請(qǐng)進(jìn)程把獲得的共享存儲(chǔ)分區(qū)連接到本進(jìn)程上，此后便可象讀 /寫普通存儲(chǔ)器一樣地讀 /寫共享存儲(chǔ)分區(qū)，該方式下，通信進(jìn)程之間的同步與互斥訪問共享存儲(chǔ)區(qū)可以由操作系統(tǒng)實(shí)現(xiàn)。 ? 由操作系統(tǒng)在內(nèi)存中劃分出一塊區(qū)域作為共享存儲(chǔ)區(qū) 。 ？如何通過共享存儲(chǔ)區(qū)通信 ? 通過程序設(shè)計(jì)來實(shí)現(xiàn) 。 ? 這里的共享數(shù)據(jù)區(qū)屬于每個(gè)互相通信進(jìn)程的組成部分，這種通信方式不要求數(shù)據(jù)移動(dòng)，一般用于本地通信。 ? 進(jìn)程之間同步與互斥是一種低級(jí)通信，用來控制進(jìn)程執(zhí)行速度。 ? 低級(jí)通信 ：進(jìn)程之間交換控制信息的過程。當(dāng)某進(jìn)程釋放出一個(gè)臨界資源以后，將用 signal原語喚醒等待在該臨界資源上的一個(gè)阻塞過進(jìn)程。 ? 由于進(jìn)程阻塞等待的原因有多種，為了區(qū)別阻塞等待進(jìn)程和不同的阻塞隊(duì)列，管程中設(shè)置了不同的條件變量，將因?yàn)椴煌录枞倪M(jìn)程組織在不同的隊(duì)列中。信號(hào)量具有累加功能，當(dāng)信號(hào)量為負(fù)數(shù)時(shí)，其絕對(duì)值表示等待在該信號(hào)量上的阻塞進(jìn)程數(shù)。 用管程實(shí)現(xiàn)同步 ? 用管程實(shí)現(xiàn)進(jìn)程同步，是指在管程中要設(shè)置一對(duì)同步操作原語，例如， wait(或 block)和 signal(或wakeup）。 ? 典型地，當(dāng)一個(gè)進(jìn)程調(diào)用管程中的過程時(shí)，若先檢查管程中是否有其他的活躍進(jìn)程，如果有，則阻塞調(diào)用進(jìn)程、直到管程內(nèi)的進(jìn)程離開管程。 Begin /*初始化語句 */ End。 … Procedure Pn(x)。 Procedure P2(x)。 Procedure P1(x)。 Type name=monitor /*管程命名 */ Var i:integer。 管程的使用 ? 管程本身被作為一種臨界區(qū)，因此，實(shí)現(xiàn)管程時(shí)，需要考慮互斥、同步和控制變量等問題。典型的管程包括三個(gè)部分： (1)對(duì)局部于管程的共享數(shù)據(jù)結(jié)構(gòu)的說明； (2)對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程； (3)對(duì)該數(shù)據(jù)結(jié)構(gòu)初始化的語句。 ? 利用管程可以鎖定任何對(duì)象，尤其是鏈表型數(shù)據(jù)結(jié)構(gòu)，可以鎖定整個(gè)鏈表，或鏈表中的某個(gè)元素。 parend end. 管程 ? 管程是一種在 程序設(shè)計(jì)級(jí) 控制進(jìn)程互斥與同步的機(jī)制，具有信號(hào)量的功能，且更容易使用和控制。 writecount:=0。 If writecount=0 then signal(rsem) Signal(y) Forever End。 Wait(y)。 寫數(shù)據(jù) 。 signal(y)。 writecount:=writecount+1。 Signal(x)。 Readcount::=readcount1。 Signal(z)。 Signal(x)。 readcount:=readcount+1。 wait(rsem)。 Var x,y,z,rsem,wsem。 ? 這種方案解決了寫者饑餓問題，但降低了并發(fā)程序，使系統(tǒng)的性能較差。 ? 換句話說，只要有一個(gè)寫者申請(qǐng)寫數(shù)據(jù)，則不再允許新的讀者進(jìn)入讀數(shù)據(jù)。 parend End. 寫者優(yōu)先 ? 為了防止“讀者優(yōu)先”可能導(dǎo)致寫者饑餓，可以考慮寫者優(yōu)先。 parbegin reader。 forever End。 Procedure write: Begin repeat wait(wsem)。 signal(x)。 readcount:=readcount1。 signal(x)。 readcount:=readcount+1。 /*統(tǒng)計(jì)讀者的個(gè)數(shù) */ Var x,wsem:semaphore(:=1)。 Program readers_writers。 ? 現(xiàn)在假設(shè)一個(gè)寫者到來，由于寫操作是排他的，所以它不能訪問數(shù)據(jù)，需要阻塞等待，如果一直都有新的讀者陸續(xù)到來，寫者的寫操作將被嚴(yán)重推遲。 ? 如果一個(gè)寫者進(jìn)程正在修改數(shù)據(jù)，別的寫者以及任何讀者都不能訪問該數(shù)據(jù)。 如何控制讀者和寫者 ? 如果采用生產(chǎn)者 /消費(fèi)者問題解決方法，嚴(yán)格互斥任何讀者和寫者進(jìn)程，可以保證數(shù)據(jù)更新操作的正確性。 ? 例如，一個(gè)聯(lián)網(wǎng)售票系統(tǒng)，數(shù)據(jù)的查詢和更新非常頻繁，不可避免會(huì)出現(xiàn)多個(gè)進(jìn)程試圖查詢或修改（讀 /寫）其中某一條數(shù)據(jù)的情形，多個(gè)進(jìn)程同時(shí)讀一條記錄是可以的，但如果一個(gè)進(jìn)程正在更新數(shù)據(jù)庫中的某條記錄，則所有其他進(jìn)程都不能訪問（讀或?qū)懀┑挠涗?，否則可能會(huì)將同一個(gè)座位銷售多次。 End。 V(S1)。 開車門 。 Begin Loop: 售票 。 End。 P(S1)。 到站停車 。S2:=0。 司機(jī)和售票員間的同步關(guān)系如下圖所示： 司機(jī) 正常行車 到站停車 開車 售票 關(guān)車門 開車門 售票員 解析： ? 設(shè)置兩個(gè)信號(hào)量 S S2，分別表示司機(jī)和售票員的私用信號(hào)量，其初值均為 0。售票員負(fù)責(zé)售票和開、關(guān)門，當(dāng)售票員關(guān)好車門后，駕駛員才能開車行駛。 End。 V(Soq)。 P(mutex_2)。 End。 V(mutex_2)。 P(mutex_2)。 數(shù)據(jù)處理 。 從緩沖區(qū)中取出數(shù)據(jù) V(mutex_1)。 Process Q Begin Loop: P(Siq)。 Goto loop。 V(Siq)。 P(mutex_1)。 Process P Begin Loop: 讀入信息 。 題解 ? 設(shè)有兩個(gè)信號(hào)量 mutex_ mutex_2分別用來實(shí)施對(duì)緩沖區(qū)的互斥訪問，且其初值都為了 1；設(shè)置私有信號(hào)量 Sip、 Siq用于進(jìn)程 P和 Q之間的同步；設(shè)置私有信號(hào)量 Soq、Sor用于進(jìn)程 Q和 R之間的同步。 分析 ? 這是一個(gè)典型的生產(chǎn)者與消費(fèi)者問題，本題中Q既作消費(fèi)者又作為生產(chǎn)者。進(jìn)程 P、 Q共享一個(gè)由 m個(gè)緩沖區(qū)組成的緩沖池；進(jìn)程 Q、 R共享一個(gè)由 n個(gè)緩沖區(qū)組成的緩沖池（假設(shè)緩沖區(qū)足夠大，進(jìn)程間每次傳輸信息的單位均小于等于緩沖區(qū)長度）。 例題 ? 假設(shè)有 3個(gè)并發(fā)進(jìn)程 P、 Q、 R。 END Parend。 Process PD Begin P(SD)。 從緩沖區(qū)中取數(shù)求累和 V(Sempty)。 End。 Process PB Begin P(SB)。 num放入緩沖區(qū) 。 Parbegin Process PA Begin P(Sempty)。 題解 ? 程序如下： Begin Sempty,SB,SC,SD:Semaphore=1:0,0,0。請(qǐng)用 P、 V操作寫出能夠正確的執(zhí)行的程序。 2022下半年軟件設(shè)計(jì)師考試上午試題 ? 進(jìn)程 P P P3和 P4的前趨圖如下： P1 P4 P3 P2 p1 a P1執(zhí)行 p2 b V(S3) P2執(zhí)行 p3 c V(S4) P3執(zhí)行 p4 d P4執(zhí)行 若用 PV操作控制這幾個(gè)進(jìn)程的并發(fā)執(zhí)行過程，則需要設(shè)置 4個(gè)信號(hào)量 S S S3和 S4，且信號(hào)量初值都等于零。 ? 對(duì)任何信號(hào)量的 wait與 signal操作必須配對(duì)，同一進(jìn)程中的多對(duì) wait與 signal語句只能嵌套，不能交叉。 注意 ? 進(jìn)程應(yīng)該先申請(qǐng)資源信號(hào)量，再申請(qǐng)互斥信號(hào)量，順序不能顛倒。 signal(e)。 wait(s)。 /*資源信號(hào)量 n，數(shù)據(jù)單元，初始化為 0 */ e:semaphore(:=sizeofbuffer)。 /* 緩沖區(qū)的大小 */ Var s:semaphore(:=1)。 Program producer_consumer。 signal(n)。 存入一條數(shù)據(jù) 。 /*資源信號(hào)量 e，空存儲(chǔ)單元 */ Procedure producer: Begin repeat 生產(chǎn)一條數(shù)據(jù)； wait(e)。 /*互斥信號(hào)量 s,初始化為 1 */ n:semaphore(:=0)。 Const sizeofbuffer=…。 Begin /*主程序