第2章進(jìn)程管理-3

互斥與同步解決方法之三：

信號(hào)量方法軟件方法和硬件方法都存在"忙等"問(wèn)題,浪費(fèi)了處理機(jī)時(shí)間。而信號(hào)量方法能夠?qū)崿F(xiàn)進(jìn)程的互斥和同步,而不必"忙等"。實(shí)例交通信號(hào)燈:紅燈停,綠燈行整型信號(hào)量最初由Dijkstra把整型信號(hào)量定義為一個(gè)用于表示資源數(shù)目的整型量S，它與一般整型量不同，除初始化外，僅能通過(guò)兩個(gè)標(biāo)準(zhǔn)的原子操作(AtomicOperation)wait(S)和signal(S)來(lái)訪(fǎng)問(wèn)。很長(zhǎng)時(shí)間以來(lái)，這兩個(gè)操作一直被分別稱(chēng)為P、V操作。Wait(S)和signal(S)操作可描述為：

wait(S)：while S<=0dono-op；

S:=S-1；

signal(S)： S:=S+1；記錄型信號(hào)量的基本原理兩個(gè)或多個(gè)進(jìn)程可以通過(guò)傳遞信號(hào)進(jìn)行合作,可以迫使進(jìn)程在某個(gè)位置暫時(shí)停止執(zhí)行(阻塞等待),直到它收到一個(gè)可以"向前推進(jìn)"的信號(hào)為止(被喚醒)。相應(yīng)地,記錄型信號(hào)量應(yīng)該包括兩個(gè)域:一個(gè)整型域,表示資源的數(shù)目,另外一個(gè)域?yàn)殛?duì)列,其元素為等待該信號(hào)量而阻塞的進(jìn)程。記錄型信號(hào)量的定義typesemaphore=record

value:integer；

L:listofprocess；

end相應(yīng)地，wait(S)和signal(S)操作可描述為：procedurewait(S)

varS：semaphore；

begin

S.value:=S.value-1；

ifS.value<0thenblock(S.L)；

endproceduresignal(S)

varS:semaphore；

begin

S.value:=S.value+1；

ifS.value<=0thenwakeup(S.L)；

endwait和signal的應(yīng)用進(jìn)程進(jìn)入臨界區(qū)之前,首先執(zhí)行wait(S)原語(yǔ),如果S.value<0則進(jìn)程調(diào)用阻塞原語(yǔ),將自己阻塞,并插入到S.L隊(duì)列中等待。注意,阻塞進(jìn)程不會(huì)占用處理機(jī)時(shí)間,不是忙等.直到某個(gè)從臨界區(qū)退出的進(jìn)程執(zhí)行signal(S)原語(yǔ),喚醒它。一旦其它某個(gè)進(jìn)程執(zhí)行了原語(yǔ)signal(S),S.value值加1,如果S.value<=0,即阻塞隊(duì)列中還有被阻塞進(jìn)程,則調(diào)用喚醒原語(yǔ),把S.L中的第一個(gè)進(jìn)程的狀態(tài)修改為就緒狀態(tài),并插入到就緒隊(duì)列中,準(zhǔn)備執(zhí)行臨界區(qū)代碼.信號(hào)量類(lèi)型信號(hào)量分為:互斥信號(hào)量和資源信號(hào)量?；コ庑盘?hào)量用于申請(qǐng)或釋放資源的使用權(quán),常初始化為1。資源信號(hào)量用于申請(qǐng)或歸還資源，可以初始化為大于1的正整數(shù)，表示系統(tǒng)中某類(lèi)資源的可用個(gè)數(shù)。wait操作用于申請(qǐng)資源（或使用權(quán)），進(jìn)程執(zhí)行wait原語(yǔ)時(shí)，可能會(huì)阻塞自己。signal操作用于釋放資源（或歸還資源使用權(quán)），進(jìn)城執(zhí)行signal原語(yǔ)時(shí)，有責(zé)任喚醒一個(gè)阻塞進(jìn)程。信號(hào)量類(lèi)型的物理意義S.value>0表示還可執(zhí)行wait(S)而不會(huì)阻塞的進(jìn)程數(shù)(可用資源數(shù))。每執(zhí)行一次wait(S)操作，就意味著請(qǐng)求分配一個(gè)單位的資源。當(dāng)S.value<=0時(shí)，表示無(wú)資源可用，因此請(qǐng)求該資源的進(jìn)程被阻塞。此時(shí)S.value絕對(duì)值等于該信號(hào)量阻塞隊(duì)列中的等待進(jìn)程數(shù)。執(zhí)行一次signal操作，就意味著釋放一個(gè)單位的資源。若S.value<0,表示S.L隊(duì)列中還有被阻塞的進(jìn)程，需要喚醒該隊(duì)列中的第一個(gè)進(jìn)程，將它轉(zhuǎn)移到就緒隊(duì)列中。S.value的取值范圍當(dāng)僅有兩個(gè)并發(fā)進(jìn)程共享臨界資源時(shí)，互斥信號(hào)量?jī)H能取之0，1，-1，其中，

-S.value=1,表示無(wú)進(jìn)程進(jìn)入臨界區(qū)-S.value=0,表示已經(jīng)有一個(gè)進(jìn)程進(jìn)入臨界區(qū)-S.value=-1,表示已有一個(gè)進(jìn)程正在等待進(jìn)入臨界區(qū)當(dāng)用S來(lái)實(shí)現(xiàn)n個(gè)進(jìn)程的互斥時(shí)，S.value的取值范圍為1-(n-1)AND型信號(hào)量上述的進(jìn)程互斥問(wèn)題，是針對(duì)各進(jìn)程之間只共享一個(gè)臨界資源而言的。在有些應(yīng)用場(chǎng)合，是一個(gè)進(jìn)程需要先獲得兩個(gè)或更多的共享資源后方能執(zhí)行其任務(wù)。假定現(xiàn)有兩個(gè)進(jìn)程A和B，他們都要求訪(fǎng)問(wèn)共享數(shù)據(jù)D和E。當(dāng)然，共享數(shù)據(jù)都應(yīng)作為臨界資源。為此，可為這兩個(gè)數(shù)據(jù)分別設(shè)置用于互斥的信號(hào)量Dmutex和Emutex，并令它們的初值都是1。相應(yīng)地，在兩個(gè)進(jìn)程中都要包含兩個(gè)對(duì)Dmutex和Emutex的操作，即processA:

processB:wait(Dmutex)；wait(Emutex)；wait(Emutex)；wait(Dmutex)；AND型信號(hào)量若進(jìn)程A和B按下述次序交替執(zhí)行wait操作：

processA:wait(Dmutex)；于是Dmutex=0

processB:wait(Emutex)；于是Emutex=0

processA:wait(Emutex)；于是Emutex=-1A阻塞

processB:wait(Dmutex)；于是Dmutex=-1B阻塞最后，進(jìn)程A和B處于僵持狀態(tài)。在無(wú)外力作用下，兩者都將無(wú)法從僵持狀態(tài)中解脫出來(lái)。我們稱(chēng)此時(shí)的進(jìn)程A和B已進(jìn)入死鎖狀態(tài)。顯然，當(dāng)進(jìn)程同時(shí)要求的共享資源愈多時(shí)，發(fā)生進(jìn)程死鎖的可能性也就愈大。AND型信號(hào)量

AND同步機(jī)制的基本思想是：將進(jìn)程在整個(gè)運(yùn)行過(guò)程中需要的所有資源，一次性全部地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放?！窗阉?qǐng)求的資源全部分配到進(jìn)程，要么一個(gè)也不分配。方法：在wait操作中，增加了一個(gè)“AND”條件，故稱(chēng)為AND同步，或稱(chēng)為同時(shí)wait操作，即Swait(Simultaneouswait)定義如下:Swait(S1，S2，…，Sn)

ifSi>=1and…andSn>=1then

fori:=1tondo

Si:=Si-1；

endfor

else

placetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi<1，andsettheprogramcountofthisprocesstothebeginningofSwaitoperation

endifSsignal(S1，S2，…，Sn)fori:=1tondo

Si:=Si+1；RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue.endfor；信號(hào)量集在記錄型信號(hào)量機(jī)制中,wait(S)和signal(S)僅能對(duì)信號(hào)量進(jìn)行加1和減1操作，意味著每次只能獲得和釋放一個(gè)單位的臨界資源。而當(dāng)一次需要N個(gè)某類(lèi)的臨界資源時(shí)，便要進(jìn)行N次wait(S)操作，顯然是低效的。此外，在有些情況下，當(dāng)資源量低于某一下限時(shí)，便不予分配。因而，在每次分配前，都必須測(cè)試該資源量的數(shù)量，看其是否大于其下限值?；谝陨蟽牲c(diǎn)，可以對(duì)AND信號(hào)機(jī)制加以擴(kuò)充，形成一般的“信號(hào)量集”。Swait和Ssignal操作描述如下：Swait(S1，t1，d1，…，Sn，tn，dn)

ifSi>=t1and…andSn>=dnthen

fori:=1tondo

Si:=Si-di；

endfor

else

placetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi<ti，andsettheprogramcountofthisprocesstothebeginningofSwaitoperation

endifSsignal(S1，d1，…，Sn，dn)fori:=1tondo

Si:=Si+di；RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue.endfor；信號(hào)量集幾種特殊的情況(1)Swait(S,d,d)：此時(shí)在信號(hào)量集中只有一個(gè)信號(hào)量S，但允許它每次申請(qǐng)d個(gè)資源，當(dāng)現(xiàn)有資源少于d時(shí)，不予分配；(2)Swait(S,1,1)：此時(shí)信號(hào)量集蛻化為一般的記錄型信號(hào)量(S>1)或互斥型信號(hào)量(S=1);(3)Swait(S,1,0)：這是一種特殊且很有用的信號(hào)量操作。當(dāng)S>=1時(shí)，允許多個(gè)進(jìn)程進(jìn)入特定區(qū)；當(dāng)S變?yōu)?時(shí)，將阻止任何進(jìn)程進(jìn)入特定區(qū)。換言之，它相當(dāng)于一個(gè)可控開(kāi)關(guān)。使用信號(hào)量解決問(wèn)題的關(guān)鍵步驟：1）信號(hào)量的設(shè)置；2）給信號(hào)量賦初值（常用的互斥和同步信號(hào)量值的大?。?；3）P、V操作安排的位置。注意：1）若有多個(gè)信號(hào)量，信號(hào)量的P操作的順序不能任意，通常先對(duì)資源信號(hào)量執(zhí)行P操作，然后對(duì)互斥信號(hào)量進(jìn)行P操作，而V操作的順序可以任意；2）互斥信號(hào)量其P和V操作通常在同一個(gè)進(jìn)程內(nèi)；而資源信號(hào)量的P和V操作通常分布在不同的進(jìn)程內(nèi)。利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥Varmutex:semaphore:=1；

begin

parbegin

process1:process2:parendprocess1、2:begin

repeat

wait(mutex)；

criticalsection

signal(mutex)；

remaindersection

untilfalse；

end

利用信號(hào)量實(shí)現(xiàn)進(jìn)程的同步P

Q

Buffer1假設(shè)有一個(gè)輸入進(jìn)程P和一個(gè)計(jì)算進(jìn)程Q,共享一個(gè)緩沖區(qū),輸入進(jìn)程輸入數(shù)據(jù),計(jì)算進(jìn)程處理數(shù)據(jù),如何實(shí)現(xiàn)二者的同步。Varempty,full:semaphore:=1,0；P:wait(empty);Q:wait(full);

輸入數(shù)據(jù)；處理數(shù)據(jù);

signal(full);

signal(empty);利用信號(hào)量實(shí)現(xiàn)進(jìn)程的同步(擴(kuò)展1)假設(shè)有一個(gè)輸入進(jìn)程P可以接收兩種數(shù)據(jù)：奇數(shù)和偶數(shù)，計(jì)算進(jìn)程Q1負(fù)責(zé)處理奇數(shù)數(shù)據(jù)，計(jì)算進(jìn)程Q2負(fù)責(zé)處理偶數(shù)數(shù)據(jù)。Varempty,full1，full2:semaphore:=1,0,0；P:wait(empty);Q1:wait(full1);Q2:wait(full2);

輸入數(shù)據(jù)；處理奇數(shù);處理偶數(shù);

if(是奇數(shù))

signal(empty);

signal(empty);

signal(full1);elsesignal(full2);Buffer1PQ1Q2利用信號(hào)量實(shí)現(xiàn)進(jìn)程的同步(擴(kuò)展2)假設(shè)有有兩個(gè)輸入進(jìn)程P1和P2分別接收奇數(shù)和偶數(shù)，計(jì)算進(jìn)程Q1和Q2分別負(fù)責(zé)處理奇數(shù)和偶數(shù)數(shù)據(jù)。Varempty,full1，full2:semaphore:=1,0,0；P1:wait(empty);P2:wait(empty);Q1:wait(full1);Q2:wait(full2);

輸入奇數(shù)；輸入偶數(shù)；處理奇數(shù)處理偶數(shù)

signal(full1);

signal(full2);signal(empty);

signal(empty);Buffer1P1Q1Q2P2利用信號(hào)量實(shí)現(xiàn)進(jìn)程的同步(擴(kuò)展3)Buffer1假設(shè)進(jìn)程P負(fù)責(zé)數(shù)據(jù)的輸入，進(jìn)程K負(fù)責(zé)數(shù)據(jù)的加工，進(jìn)程Q負(fù)責(zé)數(shù)據(jù)的打印。PQKVarempty,full1，full2:semaphore:=1,0,0；P:wait(empty);K:wait(full1);Q:wait(full2);

輸入數(shù)據(jù)；取數(shù)據(jù)打印數(shù)據(jù);

signal(full1);數(shù)據(jù)加工;

signal(empty);

signal(full2);

利用信號(hào)量實(shí)現(xiàn)進(jìn)程的同步(練習(xí))吃水果問(wèn)題：假設(shè)桌上有一個(gè)空盤(pán)子，一次僅允許放一個(gè)水果，利用信號(hào)量的P，V操作解決下列同步問(wèn)題：1）父親負(fù)責(zé)放水果，兒子負(fù)責(zé)吃水果；2）父親負(fù)責(zé)水果（蘋(píng)果或桔子），兒子吃蘋(píng)果，女兒吃桔子；3）父親負(fù)責(zé)放蘋(píng)果，母親負(fù)責(zé)放桔子，兒子吃蘋(píng)果，女兒吃桔子；4）父親負(fù)責(zé)放蘋(píng)果，母親負(fù)責(zé)削皮，兒子負(fù)責(zé)吃蘋(píng)果。思考思考:有三個(gè)進(jìn)程:進(jìn)程get：從輸入設(shè)備上不斷讀數(shù)據(jù)，并存入緩沖區(qū)Buffer1；進(jìn)程copy：不斷將緩沖區(qū)Buffer1的內(nèi)容復(fù)制到緩沖區(qū)Buffer2；進(jìn)程put：則不斷將Buffer2的內(nèi)容在打印機(jī)上輸出，get

copy

put

Buffer1Buffer23個(gè)進(jìn)程的協(xié)同工作

為了使三個(gè)進(jìn)程并發(fā)工作以大大加快執(zhí)行速度，又保證打印結(jié)果和輸入結(jié)果一致，三個(gè)進(jìn)程之間必須協(xié)調(diào)工作?！镌O(shè)四個(gè)信號(hào)量S1、S2、S3、S4，令：

S1：初值為1，表示緩沖區(qū)Buffer1空閑的單元數(shù)；

S2：初值為0，表示緩沖區(qū)Buffer1數(shù)據(jù)的個(gè)數(shù)；

S3：初值為1，表示緩沖區(qū)Buffer2空閑的單元數(shù)；

S4：初值為0，表示緩沖區(qū)Buffer2中數(shù)據(jù)個(gè)數(shù)。進(jìn)程get

進(jìn)程copy

進(jìn)程putP（S1）；P（S2）；P（S4）；從輸入設(shè)備向P（S3）；將緩沖區(qū)Buffer2緩沖區(qū)Buffer1將Buffer1內(nèi)容內(nèi)容在打印機(jī)上輸出；中寫(xiě)數(shù)據(jù)；復(fù)制到Buffer2V（S3）；V（S2）；V（S1）；

V（S4）；………………3個(gè)進(jìn)程之間的同步信號(hào)量的應(yīng)用

-實(shí)現(xiàn)前趨關(guān)系方法：若圖中存在結(jié)點(diǎn)S1指向結(jié)點(diǎn)S2的有向邊，表示進(jìn)程P1中的程序段S1應(yīng)該先執(zhí)行，而進(jìn)程P2中的程序段S2后執(zhí)行。設(shè)置一個(gè)信號(hào)量s,初值為0，將signal(s)放在S1后面，而在S2前面先執(zhí)行wait(s)。進(jìn)程P1的語(yǔ)句序列為：S1;signal(s)進(jìn)程P2的語(yǔ)句序列為：wait(s);S2

S1S2s信號(hào)量的應(yīng)用

-實(shí)現(xiàn)前趨關(guān)系要點(diǎn)1）信號(hào)量的個(gè)數(shù)=有向邊的個(gè)數(shù)2）每一個(gè)進(jìn)程對(duì)應(yīng)的語(yǔ)句結(jié)點(diǎn)的入邊和出邊分別處理：對(duì)于入邊的信號(hào)量執(zhí)行P操作，并放置在該語(yǔ)句的前面；對(duì)于出邊的信號(hào)量執(zhí)行V操作，并放置在該語(yǔ)句的后面；Vara,b,c,d,e,f,g：semaphore:=0,0,0,0,0,0,0；

begin

parbegin

beginS1；

signal(a)；

signal(b)；

end；

beginwait(a)；

S2；

signal(c)；

signal(d)；

end；

beginwait(b)；

S3；

signal(e)；

end；

beginwait(c)；

S4；

signal(f)；

end；

beginwait(d)；

S5；

signal(g)；

end；

beginwait(e)；

wait(f)；

wait(g)；

S6；

end；

parend

end信號(hào)量的使用要點(diǎn)

信號(hào)量的物理含義：-S>0表示有S個(gè)資源可用-S<0則|S|表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù)必須置一次且只能置一次初值初值不能為負(fù)數(shù)只能執(zhí)行wait、signal操作必須成對(duì)使用wait和signal原語(yǔ)：-遺漏P原語(yǔ)則不能保證互斥訪(fǎng)問(wèn)-遺漏V原語(yǔ)則不能在使用臨界資源之后將其釋放（給其他等待的進(jìn)程）-P、V原語(yǔ)不能次序錯(cuò)誤、重復(fù)或遺漏2.4經(jīng)典進(jìn)程的同步問(wèn)題生產(chǎn)者-消費(fèi)者問(wèn)題生產(chǎn)者與消費(fèi)者是一個(gè)廣義的概念,可以代表一類(lèi)具有相同屬性的進(jìn)程。生產(chǎn)者和消費(fèi)者進(jìn)程共享一個(gè)大小固定的緩沖區(qū)，其中，一個(gè)或多個(gè)生產(chǎn)者生產(chǎn)數(shù)據(jù)，并將生產(chǎn)的數(shù)據(jù)存入緩沖區(qū)，并有一個(gè)消費(fèi)者從緩沖區(qū)中取數(shù)據(jù)。假設(shè)緩沖區(qū)的大小為n(存儲(chǔ)單元的個(gè)數(shù))，它可以被生產(chǎn)者和消費(fèi)者循環(huán)使用。分別設(shè)置兩個(gè)指針in，out，指向生產(chǎn)者將存放數(shù)據(jù)的存儲(chǔ)單元和消費(fèi)者將取數(shù)據(jù)的存儲(chǔ)單元。生產(chǎn)者/消費(fèi)者必須互斥生產(chǎn)者和消費(fèi)者可能同時(shí)進(jìn)入緩沖區(qū)，甚至可能同時(shí)讀/寫(xiě)一個(gè)存儲(chǔ)單元，將導(dǎo)致執(zhí)行結(jié)果的不確定性。這顯然是不允許的，必須使生產(chǎn)者和消費(fèi)者互斥進(jìn)入緩沖區(qū)，即，某時(shí)刻只允許一個(gè)進(jìn)程（生產(chǎn)者或消費(fèi)者）訪(fǎng)問(wèn)緩沖區(qū)，生產(chǎn)者互斥消費(fèi)者和其他任何生產(chǎn)者。生產(chǎn)者/消費(fèi)者必須同步生產(chǎn)者不能向滿(mǎn)緩沖區(qū)寫(xiě)數(shù)據(jù)，消費(fèi)者也不能在空緩沖區(qū)中取數(shù)據(jù)，即生產(chǎn)者和消費(fèi)者必須同步。Varmutex:semaphore(:=1);/*互斥信號(hào)量*/

empty:semaphore(:=n);/*資源信號(hào)量，空存儲(chǔ)單元*/

full:semaphore(:=0);/*資源信號(hào)量，數(shù)據(jù)單元*/

buffer:array[0，…，n-1]ofitem；in,out:integer:=0，0；procedureproducer;procedureconsumer;beginbeginrepeatrepeatproduceranitemnexttp;wait(full);wait(empty);wait(mutex);wait(mutex);nextc:=buffer(out);buffer(in):=nextp;out=(out+1)modn;in=(in+1)modn;signal(mutex);signal(mutex);signal(empty);signal(full);consumertheiteminnextc;untilfalse;untilfalse;endendbeginparbeginproducer;consumer;parendend注意進(jìn)程應(yīng)該先申請(qǐng)資源信號(hào)量，再申請(qǐng)互斥信號(hào)量，順序不能顛倒，否則可能引起進(jìn)程的死鎖；對(duì)任何信號(hào)量的wait與signal操作必須配對(duì)；同一信號(hào)量的wait與signal可以在不同的進(jìn)程中；讀者-寫(xiě)者問(wèn)題該問(wèn)題描述為多個(gè)進(jìn)程訪(fǎng)問(wèn)一個(gè)共享數(shù)據(jù)區(qū)，如數(shù)據(jù)庫(kù)，文件，內(nèi)存區(qū)及一組寄存器等的數(shù)據(jù)問(wèn)題建立一個(gè)通用模型，其中若干個(gè)讀進(jìn)程只能讀數(shù)據(jù)，若干寫(xiě)進(jìn)程只能寫(xiě)數(shù)據(jù)。例如，一個(gè)聯(lián)網(wǎng)售票系統(tǒng)，數(shù)據(jù)的查詢(xún)和更新非常頻繁，不可避免會(huì)出現(xiàn)多個(gè)進(jìn)程試圖查詢(xún)或修改其中某一條數(shù)據(jù)的情形，多個(gè)進(jìn)程同時(shí)讀一條記錄是可以的，但如果一個(gè)進(jìn)程正在更新數(shù)據(jù)庫(kù)的某條記錄，則所有其他進(jìn)程不能訪(fǎng)問(wèn)（讀或?qū)懀┰撚涗?，否則可能將同一個(gè)座位銷(xiāo)售多次。讀者-寫(xiě)者進(jìn)程滿(mǎn)足的條件允許多個(gè)讀者進(jìn)程同時(shí)讀數(shù)據(jù)；不允許多個(gè)寫(xiě)者進(jìn)程同時(shí)寫(xiě)數(shù)據(jù)，即只能互斥寫(xiě)數(shù)據(jù)；若有寫(xiě)者進(jìn)程正在寫(xiě)數(shù)據(jù)，則不允許讀者進(jìn)程讀數(shù)據(jù)。讀者優(yōu)先當(dāng)一個(gè)讀者正在讀數(shù)據(jù)時(shí)，另一個(gè)讀者也需要讀數(shù)據(jù)，應(yīng)允許第二個(gè)讀者進(jìn)入，同理第三個(gè)及隨后更多的讀者都被允許進(jìn)入；現(xiàn)在假設(shè)一個(gè)寫(xiě)者到來(lái)，由于寫(xiě)操作是排他的，所以他不能訪(fǎng)問(wèn)數(shù)據(jù)，需要阻塞等待。如果一直都有新的讀者陸續(xù)到來(lái)，寫(xiě)者的寫(xiě)操作被嚴(yán)重推遲；該方法稱(chēng)為“讀者優(yōu)先”，即，一旦讀者正在讀數(shù)據(jù)，允許多個(gè)讀者同時(shí)讀數(shù)據(jù)，只有當(dāng)全部讀者退出，才允許寫(xiě)者進(jìn)入寫(xiě)數(shù)據(jù)。Varrmutex，wmutex:semaphore:=1,1；/*互斥信號(hào)量*/

Readcount:integer:=0；procedurereader;procedurewriter;

beginbegin

repeatrepeat

wait(rmutex)；waite(wmutex);

ifreadcount=0thenwait(wmutex)；寫(xiě)數(shù)據(jù)；

Readcount:=Readcount+1；signal(wmutex);

signal(rmutex)；untilfalse;讀數(shù)據(jù)；end

wait(rmutex)；Readcount:=Readcount-1；

ifReadcount=0thensignal(wmutex)；

signal(rmutex)；

untilfalse；endbeginparbeginreader;writer;parendend信號(hào)量集機(jī)制這里增加一個(gè)限制，即最多只允許RN個(gè)讀者同時(shí)讀。為此，又引入一個(gè)信號(hào)量L，并賦予其初值為RN，通過(guò)執(zhí)行Swait(L,1,1)操作，來(lái)控制讀者的數(shù)目。每當(dāng)有一個(gè)讀者進(jìn)入時(shí)，執(zhí)行Swait(L,1,1),使L的值減1，當(dāng)RN個(gè)讀者進(jìn)入讀后，L便減為0，當(dāng)?shù)赗N+1個(gè)讀者進(jìn)入讀時(shí)，必然會(huì)因Swait(L,1,1)操作失敗而阻塞。VarL，mx=RN,1；/*互斥信號(hào)量*/procedurereader;procedurewriter;

beginbegin

repeatrepeatSwait(L,1,1)；Swaite(mx,1,1;L,RN,0);Swait(mx,1,0);寫(xiě)數(shù)據(jù)讀數(shù)據(jù)；Ssignal(mx,1);Ssignal(L,1)；untilfalse;

untilfalse；endendbeginparbeginreader;writer;parendend注意Swait(mx,1,0)起到開(kāi)關(guān)作用，只要無(wú)寫(xiě)進(jìn)程進(jìn)入寫(xiě)，任何讀進(jìn)程都可以讀，否則，任何讀進(jìn)程都無(wú)發(fā)進(jìn)入讀；Swait(mx,1,1;L,RN,0)表示僅當(dāng)無(wú)寫(xiě)進(jìn)程進(jìn)入寫(xiě)，又無(wú)讀進(jìn)程在讀，寫(xiě)進(jìn)程才能進(jìn)入寫(xiě)。寫(xiě)者優(yōu)先為了防止“讀者優(yōu)先”可能導(dǎo)致寫(xiě)者饑餓，可以考慮寫(xiě)者優(yōu)先；即，當(dāng)共享數(shù)據(jù)區(qū)被讀者占用時(shí)，后續(xù)緊鄰到達(dá)的讀者可以繼續(xù)進(jìn)入，若這時(shí)有一個(gè)寫(xiě)者到來(lái)且阻塞等待，則寫(xiě)者后面到達(dá)的若干讀者全部阻塞等待。換句話(huà)，只要有一個(gè)寫(xiě)者申請(qǐng)寫(xiě)數(shù)據(jù)，則不允許新的讀者進(jìn)入讀數(shù)據(jù)，這樣，寫(xiě)者只需等待優(yōu)先于它到來(lái)的讀者完成其獨(dú)數(shù)據(jù)任務(wù)，而不用等待起后到來(lái)的讀者。這種方案解決了寫(xiě)者饑餓問(wèn)題，但降低了并發(fā)程度，使系統(tǒng)的性能較差。哲學(xué)家進(jìn)餐問(wèn)題問(wèn)題描述：（由Dijkstra首先提出并解決）5個(gè)哲學(xué)家圍繞一張圓桌而坐，桌子上放著5支筷子，每?jī)蓚€(gè)哲學(xué)家之間放一支；每個(gè)哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉進(jìn)餐時(shí)需要同時(shí)拿起他左邊和右邊的兩支筷子，并且每個(gè)人只能直接從自己的左邊或右邊去取筷子。吃完思考時(shí)則同時(shí)將兩支筷子放回原處。ABCDE12345

Varchopstick:array[0，…，4]ofsemaphore；所有信號(hào)量均被初始化為1，第i位哲學(xué)家的活動(dòng)可描述為：

repeat

wait(chopstick[i])；

wait(chopstick[(i+1)mod5])；

eat；

signal(chopstick[i])；

signal(chopstick[(i+1)mod5])；

think；

untilfalse；………資源競(jìng)爭(zhēng)導(dǎo)致僵持的解決方法：

(1)至多只允許有四位哲學(xué)家同時(shí)去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進(jìn)餐，并在用畢時(shí)能釋放出他用過(guò)的兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐。

(2)僅當(dāng)哲學(xué)家的左、右兩只筷子均可用時(shí)，才允許他拿起筷子進(jìn)餐。

(3)規(guī)定奇數(shù)號(hào)哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子，而偶數(shù)號(hào)哲學(xué)家則相反。按此規(guī)定，將是1、2號(hào)哲學(xué)家競(jìng)爭(zhēng)1號(hào)筷子；3、4號(hào)哲學(xué)家競(jìng)爭(zhēng)3號(hào)筷子。即五位哲學(xué)家都先競(jìng)爭(zhēng)奇數(shù)號(hào)筷子，獲得后，再去競(jìng)爭(zhēng)偶數(shù)號(hào)筷子，最后總會(huì)有一位哲學(xué)家能獲得兩只筷子而進(jìn)餐?！締?wèn)題1】

要求寫(xiě)一個(gè)函數(shù)或方法,能顯示出一個(gè)int類(lèi)型數(shù)組的元素個(gè)數(shù)及元素的內(nèi)容.

【解決方法1】

調(diào)用一個(gè)顯示數(shù)組元素個(gè)數(shù)和元素內(nèi)容的函數(shù)時(shí)，將數(shù)組與說(shuō)明此數(shù)組元素個(gè)數(shù)一并作為參數(shù)傳遞過(guò)去。

#include<iostream.h>voidshowArray(intArray[],intLen){inti;for(i=0;i<Len;i++)/*顯示數(shù)組元素的內(nèi)容*/cout<<Array[i]<<"";}voidmain(){intArray[10];/*這就是要顯示的數(shù)組,設(shè)置了10個(gè)元素*/intLen=10;/*用一個(gè)int類(lèi)型變量記錄此數(shù)組的元素個(gè)數(shù)*/inti;cout<<"請(qǐng)輸入10個(gè)整數(shù)：";for(i=0;i<Len;i++)/*初始化數(shù)組*/cin>>Array[i];showArray(Array,Len);/*調(diào)用顯示數(shù)組元素個(gè)數(shù)及內(nèi)容的函數(shù)*/}【問(wèn)題1】

要求寫(xiě)一個(gè)函數(shù)或方法,能顯示出一個(gè)int類(lèi)型數(shù)組的元素個(gè)數(shù)及元素的內(nèi)容.

【解決方法2】

將數(shù)組和描述它元素個(gè)數(shù)的數(shù)值通過(guò)結(jié)構(gòu)體放在了一起.structintArray/*定義一個(gè)intArray結(jié)構(gòu)體*/{intLen;/*這是本結(jié)構(gòu)體表示的數(shù)組的元素個(gè)數(shù)*/inta[10];};#include"iostream.h"structintArray/*定義一個(gè)intArray結(jié)構(gòu)體*/{intLen;/*這是本結(jié)構(gòu)體表示的數(shù)組的元素個(gè)數(shù)*/inta[10];};voidshowArray(structintArrayp){inti;for(i=0;i<p.Len;i++)cout<<p.a[i]<<"";}voidmain(){structintArrayp;inti;

p.Len=10;/*為這個(gè)結(jié)構(gòu)體的元素個(gè)數(shù)準(zhǔn)確賦值*/ cout<<"請(qǐng)輸入10個(gè)整數(shù)：";

for(i=0;i<p.Len;i++)cin>>p.a[i];showArray(p);}這樣傳遞給函數(shù)showArray()時(shí),就只是一個(gè)參數(shù)。

但這個(gè)方案比第一個(gè)方案多增加了一結(jié)構(gòu)體的概念,而且結(jié)構(gòu)體中的數(shù)組int

a[10],它的元素個(gè)數(shù)也是固定的,p.Len的值只能是10,當(dāng)p.Len為其他的值時(shí)就會(huì)出錯(cuò)。

注意：使用結(jié)構(gòu)體，代碼里就已經(jīng)有了一點(diǎn)面向?qū)ο蟮幕靖拍盍耍皇遣⒉皇智逦??！締?wèn)題1】

要求寫(xiě)一個(gè)函數(shù)或方法,能顯示出一個(gè)int類(lèi)型數(shù)組的元素個(gè)數(shù)及元素的內(nèi)容.

【解決方法3】

使用動(dòng)態(tài)分配內(nèi)存的方法,使數(shù)組的元素個(gè)數(shù)隨意分配.#include"iostream.h"structintArray{intLen;

int*a;};voidshowArray(structintArrayp){inti;for(i=0;i<p.Len;i++)cout<<p.a[i]<<"";}voidmain(){structintArrayp;inti;p.Len=5;/*隨意給這個(gè)數(shù)組分配n個(gè)元素*/

p.a=newint[p.Len];/*在內(nèi)存中開(kāi)辟了一個(gè)n個(gè)int類(lèi)型的內(nèi)存塊,并返回其地址*/for(i=0;i<p.Len;i++)cin>>p.a[i];showArray(p);

delete[]p.a;/*不要忘了釋放開(kāi)辟的內(nèi)存空間*/ }通過(guò)動(dòng)態(tài)分配的方法,實(shí)現(xiàn)了數(shù)組元素個(gè)數(shù)的任意分配,并且其數(shù)組個(gè)數(shù)的屬性L(fǎng)en如實(shí)地表達(dá)出了數(shù)組的個(gè)數(shù),而不需要我們操心.該解決方法要比前兩個(gè)解決方法都要進(jìn)步,但是做的工作也多了一點(diǎn),這里就涉及到了一個(gè)動(dòng)態(tài)分配的概念,而且一定要使用delete這個(gè)函數(shù)來(lái)釋放掉動(dòng)態(tài)分配的內(nèi)存,否則會(huì)造成內(nèi)存泄露,顯然,多增加了一些代碼編寫(xiě)的風(fēng)險(xiǎn).

此問(wèn)題如何方便有效地得到解決的?

其解決問(wèn)題的思路,與這個(gè)方法是一樣的,就是使數(shù)組被封裝進(jìn)一個(gè)類(lèi)中，使之成為一個(gè)對(duì)象來(lái)考慮.一個(gè)類(lèi)就是一個(gè)擴(kuò)展的struct。除了定義數(shù)據(jù)成員，你還可以為其添加成員函數(shù)。

注意：

通過(guò)對(duì)問(wèn)題1的演示與一步一步的改善方法，我們已經(jīng)初步轉(zhuǎn)向了面向?qū)ο蟮乃季S方式。

【問(wèn)題1】

要求寫(xiě)一個(gè)函數(shù)或方法,能顯示出一個(gè)int類(lèi)型數(shù)組的元素個(gè)數(shù)及元素的內(nèi)容.

【解決方法4】

使用C++的面向?qū)ο蠓椒ā?/p>

#include<iostream.h>classintArray{private: intLen;int*a;public:intArray(intsize)//進(jìn)行內(nèi)存分配并初始化賦值{Len=size;a=newint[Len];//開(kāi)辟內(nèi)存inti; cout<<"請(qǐng)輸入"<<Len<<"個(gè)整數(shù)：";for(i=0;i<Len;i++)cin>>a[i];}voidshowArray(){inti; cout<<"數(shù)組元素有：";for(i=0;i<Len;i++)cout<<a[i]<<"";}~intArray(){delete[]a;//釋放內(nèi)存}};voidmain(){/*創(chuàng)建intArray類(lèi)型的對(duì)象實(shí)例p，并指定其數(shù)組元素為5個(gè)*/

intArrayp(5);/*直接調(diào)用此實(shí)例的方法來(lái)顯示其內(nèi)容，這里，我們不給這個(gè)函數(shù)傳遞參數(shù)，因?yàn)檫@個(gè)函數(shù)要顯示的，是它自身對(duì)象的內(nèi)容*/

p.showArray();}

對(duì)于一個(gè)封裝好的類(lèi),我們只是將此類(lèi)intArray實(shí)例化并初始化,然后調(diào)用它的顯示方法就完成了上面我們所做的很多工作.只要設(shè)計(jì)并封裝好類(lèi),對(duì)于類(lèi)的內(nèi)部細(xì)節(jié)我們做好后就不必去關(guān)心,事實(shí)上,如果你把你的類(lèi)提供給另外一個(gè)人,他只要寫(xiě)2行代碼就能解決這個(gè)問(wèn)題.而像上面的那3個(gè)解決方法,你可以數(shù)一下,在別人使用你提供的函數(shù)后,他究竟要寫(xiě)多少行代碼,要關(guān)心多少個(gè)細(xì)節(jié)問(wèn)題才能不出錯(cuò)?

同步操作分散：信號(hào)量機(jī)制中，同步操作分散在各個(gè)進(jìn)程中，使用不當(dāng)就可能導(dǎo)致各進(jìn)程死鎖（如P、V操作的次序錯(cuò)誤、重復(fù)或遺漏）易讀性差：要了解對(duì)于一組共享變量及信號(hào)量的操作是否正確，必須通讀整個(gè)系統(tǒng)或者并發(fā)程序用戶(hù)負(fù)擔(dān)：由用戶(hù)自己編寫(xiě)控制代碼，加重用戶(hù)負(fù)擔(dān)互斥與同步解決方法之四：

管程方法管程的引入1973年，Hoare和Hanson所提出；其基本思想是把信號(hào)量及其操作原語(yǔ)封裝在一個(gè)對(duì)象內(nèi)部即：將共享變量以及對(duì)共享變量能夠進(jìn)行的所有操作集中在一個(gè)模塊中管程的定義：管程是關(guān)于共享資源的數(shù)據(jù)結(jié)構(gòu)及一組針對(duì)該資源的操作過(guò)程所構(gòu)成的軟件模塊。管程的組成由上述的定義可知，管程由四部分組成：①管程的名稱(chēng)；②局部于管程內(nèi)部的共享數(shù)據(jù)結(jié)構(gòu)說(shuō)明；③對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過(guò)程；④對(duì)局部于管程內(nèi)部的共享數(shù)據(jù)設(shè)置初始值的語(yǔ)句。type<管程名>=MONITOR；<管程變量說(shuō)明>；procedure<過(guò)程名>(<形式參數(shù)表>)；begin

<過(guò)程體>end;procedure<過(guò)程名>(<形式參數(shù)表>)；begin

<過(guò)程體>end;begin<