互斥和同步練習題解析課件

互斥和同步練習題互斥和同步練習題1例1.在一個僅允許單向行駛的單排車道十字路口，只允許車輛從南向北和從西向東行駛，如圖8.1所示；為了安全起見，每次僅允許一輛汽車通過十字路口；當有車輛通過路口時其它車輛必須等待，當無車輛在路口行駛時則一次僅允許一輛汽車通過。請用P、V原語及信號量實現(xiàn)十字路口的交通控制系統(tǒng)，并描述具體的控制算法。北東圖1允許單向行駛的單排車道十字路口例1.在一個僅允許單向行駛的單排車道十字路口，只允許車輛從南2設(shè)一信號量sem表示是否允許汽車通過，初值為1，表示允許汽車通過。設(shè)入口檢測進程procedurein,出口檢測進程procedureout，它們的描述如下：procedurein（）beginL1:檢測到有一輛車要進入路口P(sem)允許進入路口gotoL1endprocedureout（）beginL2:檢測到有一輛車駛出路口V(sem)gotoL2end設(shè)一信號量sem表示是否允許汽車通過，初值為1，表示允許汽車3例2：設(shè)存在三個過程get、copy和put分別對緩沖區(qū)S和T進行操作，其中g(shù)et負責將數(shù)據(jù)塊存入緩沖區(qū)S，copy負責從緩沖區(qū)S讀出數(shù)據(jù)并復制到緩沖區(qū)T中，put負責從緩沖區(qū)T中讀出數(shù)據(jù)并打印，如圖2所示。請用P、V操作描述上述三個過程。getcopyput緩沖區(qū)S緩沖區(qū)T圖2輸入—緩沖—輸出問題解：設(shè)信號量SGC表示緩沖區(qū)S是否允許放數(shù)據(jù)，值為1時表示允許，初值為1；信號量SCG表示緩沖區(qū)S是否允許取數(shù)據(jù)，值為1時表示允許，初值為0；信號量SCP表示緩沖區(qū)T是否允許放數(shù)據(jù)，值為1時表示允許，初值為1；信號量SPC表示緩沖區(qū)T是否允許取數(shù)據(jù)，值為1時表示允許，初值為0。例2：設(shè)存在三個過程get、copy和put分別對緩沖區(qū)S和4get（）beginL1：取存入緩沖區(qū)S的數(shù)據(jù)xP（SGC）把數(shù)據(jù)x存入緩沖區(qū)S中V（SCG）gotoL1endcopy（）beginL2：P（SCG）把緩沖區(qū)S的數(shù)據(jù)存入x中V（SGC）P（SCP）把數(shù)據(jù)x要存入緩沖區(qū)T中V（SPC）gotoL2endput（）beginL3：P（SPC）把緩沖區(qū)T的數(shù)據(jù)存入x中V（SCP）打印數(shù)據(jù)xgotoL3endget（）copy（）put（）5例3：試用信號燈與PV操作實現(xiàn)司機與售票員之間的同步問題。設(shè)公共汽車上有一個司機和一個售票員，司機負責駕駛汽車，售票員負責開關(guān)車門，他們之間必須協(xié)同工作。一方面售票員關(guān)好車門并通知司機后，司機才能開車；另一方面，司機將車停穩(wěn)并通知售票員后，售票員才能打開車門上下乘客。例3：試用信號燈與PV操作實現(xiàn)司機與售票員之間的同步問題。設(shè)6互斥和同步練習題解析課件7例4：公交車上司機負責駕駛汽車，而售票員負責開關(guān)車門，他們之間必須協(xié)同工作。一方面售票員關(guān)好車門并通知司機后，司機才能開車；另一方面，司機將車停穩(wěn)并通知售票員后，售票員才能打開車門上下乘客。假設(shè)某輛公交車上有一名司機和兩名售票員，每個售票員各負責一個車門，請設(shè)適當?shù)男盘柫?，并用P、V原語描述他們的同步過程。例4：公交車上司機負責駕駛汽車，而售票員負責開關(guān)車門，他們之8例4：公交車上司機負責駕駛汽車，而售票員負責開關(guān)車門，他們之間必須協(xié)同工作。一方面售票員關(guān)好車門并通知司機后，司機才能開車；另一方面，司機將車停穩(wěn)并通知售票員后，售票員才能打開車門上下乘客。假設(shè)某輛公交車上有一名司機和兩名售票員，每個售票員各負責一個車門，請設(shè)適當?shù)男盘柫?，并用P、V原語描述他們的同步過程。解：設(shè)信號量dooropen表示是否允許開門，值為1時表示是允許開門，初值為0；doorclose1表示前們是否關(guān)上；值為1時表示已關(guān)上，初值為1；doorclose2表示后們是否關(guān)上；值為1時表示已關(guān)上，初值為1；

例4：公交車上司機負責駕駛汽車，而售票員負責開關(guān)車門，他們之9driver()beginL1:開車停車V（dooropen）等待P（doorclose1）P（doorclose2）啟動車輛gotoL1end司機和兩名售票員所對應的進程描述如下：tackiter1()beginL2:售票P（dooropen）等待乘客上車關(guān)車門V（doorclose1）gotoL2endtackiter2()beginL3:售票P（dooropen）等待乘客上車關(guān)車門V（doorclose2）gotoL3enddriver()司機和兩名售票員所tackiter1()ta10互斥和同步練習題解析課件11互斥和同步練習題解析課件12互斥和同步練習題解析課件13例6：設(shè)一個理發(fā)店內(nèi)有n張椅子和一個理發(fā)師（及其理發(fā)椅和理發(fā)工具）。當一個顧客走進理發(fā)店時，若供等候的椅子已坐滿人，則離開。若有空座位則進入理發(fā)店，此時若理發(fā)師正在為他人理發(fā)，則他就找一個空座位坐下；若理發(fā)師空閑則就要求理發(fā)師為他理發(fā)。請給出此問題的同步算法。例6：設(shè)一個理發(fā)店內(nèi)有n張椅子和一個理發(fā)師（及其理發(fā)椅和理發(fā)14設(shè)信號量chair椅子是否有和有多少把椅子空閑，初值為n表示有n把椅子可以空閑；hairdresser理發(fā)師是否正在為他人理發(fā)，值為1時表示正在為他人理發(fā)，初值為0；顧客進程描述如下：customer()beginL1:走進理發(fā)店P(guān)(chair)P(hairdresser)V(chair)讓理發(fā)師為他理發(fā)V(hairdresser)gotoL1end設(shè)信號量chair椅子是否有和有多少把椅子空閑，初值為n15例題7：A、B兩人共同使用一個報箱，該報箱每次僅能容納一份報紙。A訂閱《生活報》，B訂閱《晚報》，分別由投遞員C和D投遞。請用P、V操作描述他們的同步程序.例題7：A、B兩人共同使用一個報箱，該報箱每次僅能容納一份報16答；設(shè)信號量SP，表示信箱是否允許放報紙，值為1時表示允許放報紙，初值為1；信號量SA，表示信箱中是否有生活報，值為1時表示有，初值為0；信號量SB，表示信箱中是否有晚報，值為1時表示有，初值為0。例題：A、B兩人共同使用一個報箱，該報箱每次僅能容納一份報紙。A訂閱《生活報》，B訂閱《晚報》，分別由投遞員C和D投遞。請用P、V操作描述他們的同步程序。例題：A、B兩人共同使用一個報箱，該報箱每次僅能容納一份報紙17A（）beginL3：P(SA)取《生活報》V（SP）gotoL3EndC（）beginL1：P(SP)把《生活報》放入報箱V（SA）gotoL1end投遞員C、D和A、B兩人的進程描述如下：B（）beginL4：P(SB)取《晚報》V（SP）gotoL4endD（）beginL2：P(SP)把《晚報》放入報箱V（SB）gotoL2endA（）C（）投遞員C、D和A、B兩人的進程描述如下：B（）D18互斥和同步練習題互斥和同步練習題19例1.在一個僅允許單向行駛的單排車道十字路口，只允許車輛從南向北和從西向東行駛，如圖8.1所示；為了安全起見，每次僅允許一輛汽車通過十字路口；當有車輛通過路口時其它車輛必須等待，當無車輛在路口行駛時則一次僅允許一輛汽車通過。請用P、V原語及信號量實現(xiàn)十字路口的交通控制系統(tǒng)，并描述具體的控制算法。北東圖1允許單向行駛的單排車道十字路口例1.在一個僅允許單向行駛的單排車道十字路口，只允許車輛從南20設(shè)一信號量sem表示是否允許汽車通過，初值為1，表示允許汽車通過。設(shè)入口檢測進程procedurein,出口檢測進程procedureout，它們的描述如下：procedurein（）beginL1:檢測到有一輛車要進入路口P(sem)允許進入路口gotoL1endprocedureout（）beginL2:檢測到有一輛車駛出路口V(sem)gotoL2end設(shè)一信號量sem表示是否允許汽車通過，初值為1，表示允許汽車21例2：設(shè)存在三個過程get、copy和put分別對緩沖區(qū)S和T進行操作，其中g(shù)et負責將數(shù)據(jù)塊存入緩沖區(qū)S，copy負責從緩沖區(qū)S讀出數(shù)據(jù)并復制到緩沖區(qū)T中，put負責從緩沖區(qū)T中讀出數(shù)據(jù)并打印，如圖2所示。請用P、V操作描述上述三個過程。getcopyput緩沖區(qū)S緩沖區(qū)T圖2輸入—緩沖—輸出問題解：設(shè)信號量SGC表示緩沖區(qū)S是否允許放數(shù)據(jù)，值為1時表示允許，初值為1；信號量SCG表示緩沖區(qū)S是否允許取數(shù)據(jù)，值為1時表示允許，初值為0；信號量SCP表示緩沖區(qū)T是否允許放數(shù)據(jù)，值為1時表示允許，初值為1；信號量SPC表示緩沖區(qū)T是否允許取數(shù)據(jù)，值為1時表示允許，初值為0。例2：設(shè)存在三個過程get、copy和put分別對緩沖區(qū)S和22get（）beginL1：取存入緩沖區(qū)S的數(shù)據(jù)xP（SGC）把數(shù)據(jù)x存入緩沖區(qū)S中V（SCG）gotoL1endcopy（）beginL2：P（SCG）把緩沖區(qū)S的數(shù)據(jù)存入x中V（SGC）P（SCP）把數(shù)據(jù)x要存入緩沖區(qū)T中V（SPC）gotoL2endput（）beginL3：P（SPC）把緩沖區(qū)T的數(shù)據(jù)存入x中V（SCP）打印數(shù)據(jù)xgotoL3endget（）copy（）put（）23例3：試用信號燈與PV操作實現(xiàn)司機與售票員之間的同步問題。設(shè)公共汽車上有一個司機和一個售票員，司機負責駕駛汽車，售票員負責開關(guān)車門，他們之間必須協(xié)同工作。一方面售票員關(guān)好車門并通知司機后，司機才能開車；另一方面，司機將車停穩(wěn)并通知售票員后，售票員才能打開車門上下乘客。例3：試用信號燈與PV操作實現(xiàn)司機與售票員之間的同步問題。設(shè)24互斥和同步練習題解析課件25例4：公交車上司機負責駕駛汽車，而售票員負責開關(guān)車門，他們之間必須協(xié)同工作。一方面售票員關(guān)好車門并通知司機后，司機才能開車；另一方面，司機將車停穩(wěn)并通知售票員后，售票員才能打開車門上下乘客。假設(shè)某輛公交車上有一名司機和兩名售票員，每個售票員各負責一個車門，請設(shè)適當?shù)男盘柫?，并用P、V原語描述他們的同步過程。例4：公交車上司機負責駕駛汽車，而售票員負責開關(guān)車門，他們之26例4：公交車上司機負責駕駛汽車，而售票員負責開關(guān)車門，他們之間必須協(xié)同工作。一方面售票員關(guān)好車門并通知司機后，司機才能開車；另一方面，司機將車停穩(wěn)并通知售票員后，售票員才能打開車門上下乘客。假設(shè)某輛公交車上有一名司機和兩名售票員，每個售票員各負責一個車門，請設(shè)適當?shù)男盘柫浚⒂肞、V原語描述他們的同步過程。解：設(shè)信號量dooropen表示是否允許開門，值為1時表示是允許開門，初值為0；doorclose1表示前們是否關(guān)上；值為1時表示已關(guān)上，初值為1；doorclose2表示后們是否關(guān)上；值為1時表示已關(guān)上，初值為1；

例4：公交車上司機負責駕駛汽車，而售票員負責開關(guān)車門，他們之27driver()beginL1:開車停車V（dooropen）等待P（doorclose1）P（doorclose2）啟動車輛gotoL1end司機和兩名售票員所對應的進程描述如下：tackiter1()beginL2:售票P（dooropen）等待乘客上車關(guān)車門V（doorclose1）gotoL2endtackiter2()beginL3:售票P（dooropen）等待乘客上車關(guān)車門V（doorclose2）gotoL3enddriver()司機和兩名售票員所tackiter1()ta28互斥和同步練習題解析課件29互斥和同步練習題解析課件30互斥和同步練習題解析課件31例6：設(shè)一個理發(fā)店內(nèi)有n張椅子和一個理發(fā)師（及其理發(fā)椅和理發(fā)工具）。當一個顧客走進理發(fā)店時，若供等候的椅子已坐滿人，則離開。若有空座位則進入理發(fā)店，此時若理發(fā)師正在為他人理發(fā)，則他就找一個空座位坐下；若理發(fā)師空閑則就要求理發(fā)師為他理發(fā)。請給出此問題的同步算法。例6：設(shè)一個理發(fā)店內(nèi)有n張椅子和一個理發(fā)師（及其理發(fā)椅和理發(fā)32設(shè)信號量chair椅子是否有和有多少把椅子空閑，初值為n表示有n把椅子可以空閑；hairdresser理發(fā)師是否正在為他人理發(fā)，值為1時表示正在為他人理發(fā)，初值為0；顧客進程描述如下：customer()beginL1:走進理發(fā)店P(guān)(chair)P(hairdresser)