第一篇：進程同步與互斥練習
進程同步與互斥
練習題
選擇題
1．任何兩個并發(fā)進程之間存在著（）的關系。
A．各自完全獨立
B．擁有共享變量
C．必須互斥
D．可能相互制約
2．并發(fā)進程執(zhí)行的相對速度是（）。
A．由進程的程序結(jié)構(gòu)決定的B．由進程自己來控制的C．在進程被創(chuàng)建時確定的D．與進程調(diào)度策略有關的3．并發(fā)進程執(zhí)行時可能會出現(xiàn)“與時間有關的錯誤”，這種錯誤是由于并發(fā)進程（）引起的。
A．使用共享資源
B．執(zhí)行的順序性
C．要求計算時間的長短
D．程序的長度
4．并發(fā)進程中與共享變量有關的程序段稱為（）。
A．共享子程序
B．臨界區(qū)
C．管理區(qū)
D．公共數(shù)據(jù)區(qū)
5．用來實現(xiàn)進程同步與互斥的PV操作實際上是由（）過程組成的。
A．一個可被中斷的B．一個不可被中斷的C．兩個可被中斷的D.兩個不可被中斷的6．進程從運行態(tài)變?yōu)榈却龖B(tài)可能由于（）。
A．執(zhí)行了V操作
B．執(zhí)行了P操作
C．時間片用完
D．有高優(yōu)先級進程就緒
7．用PV操作管理互斥使用的資源時，信號量的初值應定義為（）。
A．任意正整數(shù)
B．1
C．0
8.用P、V操作管理臨界區(qū)時，互斥信號量的初值應定義為()。
A．任意值
B．1
C．0
D．-
19．現(xiàn)有n個具有相關臨界區(qū)的并發(fā)進程，如果某進程調(diào)用P操作后變?yōu)榈却隣顟B(tài)，則調(diào)用P操作時信號量的值必定為（）。
A．≤0
B．1
C．n-1
D．n
10．用PV操作管理臨界區(qū)時把信號量的初值定義為1，現(xiàn)已有一個進程在臨界區(qū)，但有n個進程在等待進人臨界區(qū)，這時信號量的值為（）。
A．-1
B．1
C．-n
D．n
11．用V操作喚醒一個等待進程時，被喚醒進程的狀態(tài)應變成（）狀態(tài)。
A．執(zhí)行
B．就緒
C．運行
D．收容
12．進程間的同步是指進程間在邏輯上的相互()關系。
A．聯(lián)接B．制約
C．繼續(xù)D．調(diào)用
多項選擇題
1．有關并發(fā)進程的下列敘述中，（）是正確的。
A．任何時刻允許多個進程在同一CPU上運行
B．進程執(zhí)行的速度完全由進程自己控制
C．并發(fā)進程在訪問共享資源時可能出現(xiàn)與時間有關的錯誤
D．同步是指并發(fā)進程中存在的一種制約關系
E．各自獨立的并發(fā)進程在執(zhí)行時不會相互影響
2．一個正在運行的進程調(diào)用P(s)后，若S的值為（），則該進程可以繼續(xù)運行。
A．S＞0
B．S＜0
C．S≠0
E．S≤0
判斷題
1．有交往的并發(fā)進程一定共享某些資源。（）
2．如果不能控制并發(fā)進程執(zhí)行的相對速度，則它們在共享資源時一定會出現(xiàn)與時間有關的錯誤。（）
3．并發(fā)進程的執(zhí)行結(jié)果只取決于進程本身，不受外界影響。（）
4．多道程序設計必然導致進程的并發(fā)執(zhí)行。（）
有m個進程共享同一臨界資源，若使用信號量機制實現(xiàn)對資源的互斥訪問，則信號量值的變化范圍是________________。
對于兩個并發(fā)進程，設互斥信號量為mutex，若mutex=0，則________
A 表示沒有進程進入臨界區(qū)B 表示有一個進程進入臨界區(qū)
C表示有一個進程進入臨界區(qū)，另一個進程等待進入
D 表示有兩個進程進入臨界區(qū)
設系統(tǒng)中有n（n>2）進程，且當前不在執(zhí)行進程調(diào)度程序，試考慮下述4種情況哪種不能發(fā)生：
A沒有運行進程，有2個就緒進程，n-2個進程處于等待狀態(tài)。
B有1個運行進程，沒有就緒進程，n-1個進程處于等待狀
C有1個運行進程，有1個就緒進程，n-2個進程處于等待狀態(tài)
D有1個運行進程，有n-1個就緒進程，沒有進程處于等待狀態(tài)
設有一個作業(yè)由四個進程組成，這四個進程在運行時必須按圖所示的順序，用P、V原語操作表達四個進程的同步關系。
應用題
設系統(tǒng)中只有一臺打印機，有三個用戶的程序在執(zhí)行過程中都要使用打印機輸出計算結(jié)果。設每個用戶程序?qū)粋€進程。問：這三個進程間有什么樣的制約關系？試用P、V操作寫出這些進程使用打印機的算法。
判斷下面的同步問題的算法是否正確？若有錯，請指出錯誤原因并予以改正
（1）設A、B兩進程共用一個緩沖區(qū)Q，A向Q寫入信息，B則從Q讀出信息，算法框圖如圖所示。
設A、B為兩個并發(fā)進程，它們共享一臨界資源。其運行臨界區(qū)的算法框圖如圖所示。
某套裝服裝廠有甲乙兩個制作室和一個配套室。兩個制作室分別生產(chǎn)上衣和褲子，每制作一件上衣或褲子后制作室工人都要分別把它們送到配套室的衣架F1和褲架F2上，衣架F1上存放上衣，褲架F2上存放褲子，衣架最多能放50件上衣，褲架最多能放50條褲子。配套室工人每次從架上取一件上衣和一條褲子，然后將它們配成套裝，并進行包裝。為防止操作出錯，甲制作室工人及配套室工人對衣架F1的存取動作應互斥進行，乙制作室工人及配套室工人對褲架F2的存取動作應互斥進行。用P、V原語進行正確管理，分別描述甲制作室工人、乙制作室工人以及配套室工人的工作過程。
解：
（1）設公用信號量mutex1和mutex2控制進程對衣架和褲架的互斥操作
設私用信號量empty1和empty2分別表示衣架和褲架的空位數(shù)，full1表示衣架上的衣服數(shù)，full2表示褲架上的褲子數(shù)
（2）初始化mutex1=1，mutex2=1，empty1=50，empty2=50，full1=0，full2=0
（3）描述：
甲制作室工人工作過程：乙制作室工人工作過程：
L1：生產(chǎn)一件上衣L2：生產(chǎn)一條褲子
P(empty1)P(empty2)
P(mutex1)P(mutex2)
將上衣放到衣架上將褲子放到褲架上
V(mutex1)V(mutex2)
V(full1)V(full2)
Goto L1Goto L2
配套工人工作過程：
L3：P(full1)
P(full2)
P(mutex1)
P(mutex2)
分別取上衣和褲子進行配套
V(mutex1)
V(mutex2)
V(empty1)
V(empty2)
Goto L
3在一個盒子里，混裝了數(shù)量相等的黑白圍棋子。現(xiàn)在利用自動分揀系統(tǒng)把黑子、白子分開，設分揀系統(tǒng)有兩個進程P1和P2，其中進程P1揀白子；進程P2揀黑子。規(guī)定每個進程一次揀一子，當一個進程在揀時不允許另一個進程去揀，當一個進程揀了一子時，必須讓另一個進程去揀。試寫出進程P1和P2能夠正確并發(fā)執(zhí)行的程序。
設私有信號量S1=1；S2=0
P1(){P2(){
P(S1);P(S2);
揀白子;揀黑子;V(S2);}V(S1);}
有一個倉庫，可存放X、Y兩種產(chǎn)品，倉庫的存儲空間足夠大，但要求：(1)每次只能存入一種產(chǎn)品X或Y，(2)滿足-N 設互斥信號量mutex=1;私有信號量sx=M-1;sy=N-1; storeX(){storeY(){ P(sx);P(sy); P(mutex);P(mutex); 將X產(chǎn)品入庫；將X產(chǎn)品入庫； V(mutex);V(mutex); V(sy);}V(sx);} 答案 1.D 2.D 3.A 4.B 5.D 6.B 7.B 8.A 9.C 10.B 11.B 12.B 13.A 14.C 15.C 16.D 17.A 18.B 二、多項選擇題 1．[分析]任何一臺CPU在每一時刻只能解釋執(zhí)行一條指令，因而，不可能在同一時刻為多個進程服務。進程可同時執(zhí)行的含義是一個進程的工作沒有全部完成之前另一進程就可開始工作。所以，實際上多個進程是輪流占用CPU運行的。到底哪個進程能占用處理器不僅與進程自身有關，且受外界因素的影響；當多個進程競爭CPU時，必須由進程調(diào)度來決定當前哪個進程可以占用CPU；故每個進程都是走走停停的，進程執(zhí)行的速度不能完全由進程自己來控制。 并發(fā)進程相互之間可能是無關的，即它們是各自獨立的，這些進程中每一個進程的執(zhí)行既不依賴于其它進程也不會影響其它進程的執(zhí)行。但是，有些并發(fā)進程需使用共享資源，為保證進程執(zhí)行的正確性，對共享資源的使用必須加以限制。同步就是并發(fā)進程中的一種制約關系，一個進程能否使用共享資源取決于其它進程的消息，只有指定的消息到達才可使用共享資源。如果無約束地使用共享資源，則可能出現(xiàn)多個進程交替地訪問共享資源，于是就可能會出現(xiàn)與時間有關的錯誤。故本題的答案為C、D、E。 [題解]C、D、E。 2．[分析]根據(jù)P操作的定義，當調(diào)用P操作時, P操作把信號量S減去1，若結(jié)果小于0則調(diào)用者將等待信號量，否則可繼續(xù)運行。因而，若調(diào)用P(S）后S的值為＞=0則進程可以繼續(xù)運行，故應選擇A和D。要注意不能選擇C，因S<>0包含了S＞0和S＜0，當S＜0時進程將成為等待狀態(tài)而不能運行。[題解]A，D。 3．[題解]A，C，E。 4．[題解]A，B，C，D，E。 三、判斷題 1．[題解]是。2．［分析］如果不控制并發(fā)進程執(zhí)行的相對速度，則它們在共享資源時可能會出現(xiàn)兩種情況：一種是并發(fā)進程交替使用共享資源，這樣就可能會發(fā)生與時間有關的錯誤；另一種是并發(fā)執(zhí)行的速度沒有致使它們交替使用共享資源，這時就不會出現(xiàn)與時間有關的錯誤。因而，本題的結(jié)論“一定會出現(xiàn)與時間有關的錯誤”是不對的。[題解]否。 3．[分析]所謂防止死鎖是指采用了某種方法后系統(tǒng)一定不會發(fā)生死鎖。但是，使用PV操作不一定能防止死鎖，教材中的五個哲學家問題就是例證。所以, PV操作可以防止死鎖的說法是錯誤的。 [題解］否。 4.［分析]如果一個進程單獨執(zhí)行時，那么執(zhí)行結(jié)果只取決于進程本身，不受外界影響。但多個進程并發(fā)執(zhí)行時，無論是進程本身的原因還是外界的因素都會影響到進程的執(zhí)行速度。如果并發(fā)進程有共享變量且其執(zhí)行速度造成了它們交替訪問共享變量，那么進程的執(zhí)行結(jié)果可能不惟一。故本題的闡述不確切。[題解］否。 5．[題解］是。 6．[題解]是。 7．[分析］限制共享資源互斥使用后仍可能引起系統(tǒng)死鎖，可舉例說明。例如，教材中五個哲學家問題，采用了PV操作來保證共享資源的互斥使用，但還是發(fā)生了循環(huán)等待，且這種等待永遠不能結(jié)束，引起了死鎖。所以，資源的互斥使用不能保證系統(tǒng)不會死鎖。[題解]否。 8.[分析]若任何一個進程在申請新資源前總是先歸還已得到的資源，則任何進程都不會發(fā)生“占有且等待資源”的情況。也就是說，這種資源分配策略能破壞形成死鎖的四個必要條件中的第二個條件，故可防止死鎖。［題解］是。 四、填空題 1．封閉性，可再現(xiàn)性 2．并發(fā)進程 3．與時間有關的 4．臨界區(qū) 5．P, V 6．競爭（或互斥），協(xié)作（或同步） 7．P, V 8．等待信號量，就緒 9．[分析］因規(guī)定該資源只能互斥使用，因而信號量的初值應定義為1。當n個進程各調(diào)用一次P操作時將使信號量的值為最小。[題解]1，(1-n）或-(n-1)。 10．[分析]由于初值為10，因而調(diào)用了18次P操作后的值為（l0-18）=-8。再調(diào)用15次V操作的話則信號量的值為（－8＋15）=7?！割}解」7。 11．send（或發(fā)送），receive（或接收）12．發(fā)送者的信件，信箱 13．互斥使用資源，循環(huán)等待資源 14 死鎖防止，死鎖避免 15．防止 16．靜態(tài)分配，按序分配，剝奪式分配 17．不安全 18．銀行家 19．安全 20．處理器，主存儲器 21．循環(huán)等待資源 22．靜態(tài) 四、填空題 1．封閉性，可再現(xiàn)性 2．并發(fā)進程 3．與時間有關的 4．臨界區(qū) 5．P, V 6．競爭（或互斥），協(xié)作（或同步） 7．P, V 8．等待信號量，就緒 9．[分析］因規(guī)定該資源只能互斥使用，因而信號量的初值應定義為1。當n個進程各調(diào)用一次P操作時將使信號量的值為最小。[題解]1，(1-n）或-(n-1)。 10．[分析]由于初值為10，因而調(diào)用了18次P操作后的值為（l0-18）=-8。再調(diào)用15次V操作的話則信號量的值為（－8＋15）=7。「題解」7。 11．send（或發(fā)送），receive（或接收）12．發(fā)送者的信件，信箱 13．互斥使用資源，循環(huán)等待資源 14 死鎖防止，死鎖避免 15．防止 16．靜態(tài)分配，按序分配，剝奪式分配 17．不安全 18．銀行家 19．安全 20．處理器，主存儲器 21．循環(huán)等待資源 22．靜態(tài) 進程同步練習題 1.在公共汽車上，司機和售票員的工作流程如圖所示。為保證乘客的安全，司機和售票員應密切配合協(xié)調(diào)工作。請用信號量來實現(xiàn)司機與售票員之間的同步。 司機 售票員 啟動車輛 關車門 正常行車 售票 到站停車 開車門 圖 司機和售票員工作流程圖 ① 約束：怎么密切配合協(xié)調(diào)工作才能保證安全呢？ a)關車門之后再啟動車輛；利用前驅(qū)圖解釋 b)到站停車之后再開車門； ② 根據(jù)約束定義信號量； 關車門和啟動車輛需要一個信號量進行同步S1；到站停車和開車門之間需要一個信號量進行同步S2； ③ 建立幾個進程呢？ a)為司機建立一個進程Driver； b)為售票員建立一個進程Conductor； Driver： Repeat 啟動車輛； 正常行駛； 到站停車； Until false;Conductor： Repeat 關車門； 售票； 開車門； Until false; ④ 加入同步關系： Var s1,s2:semorphore=0,0; Driver： Repeat Wait(s1); 啟動車輛； 正常行駛； 到站停車； Signal(s2)Until false;Conductor： Repeat 關車門； Signal(s1); 售票； Wait(s2) 開車門； Until false;main(){ Driver(); Conductor();} 2.桌子上有一只盤子，盤子中只能放一只水果。爸爸專向盤子中放蘋果，媽媽專向盤子中放橘子，一個兒子專等吃盤子中的橘子，一個女兒專等吃盤子中的蘋果。用PV操作實現(xiàn)他們之間的同步機制。分析： ①約束： a)爸爸和媽媽競爭盤子，往盤子放水果，爸爸在放時，媽媽等待，或者相反； b)爸爸和女兒要同步，即爸爸放完蘋果之后通知女兒來吃；同時女兒吃完之后要通知盤子可用； c)媽媽和兒子要同步，即媽媽放完橘子之后通知兒子來吃；同時兒子吃完之后要通知盤子可用； ② 經(jīng)上述分析可知： 需要3個信號量：S1表示臨界資源盤子，初值1；爸爸和女兒需要一個信號量進行同步S2=0 媽媽和兒子需要一個信號量進行同步S3=0;③ 建立進程？ 爸爸： 媽媽： 女兒： 兒子： Repeat repeat repeat repeat 取一個蘋果； 取一個橘子； 從盤子取一個蘋果； 從盤子取一個橘子； 放入盤子； 放入盤子 吃蘋果； 吃橘子； Until false; Until false; Until false; Until false;④ 加入同步關系。 爸爸： 媽媽： 女兒： 兒子： Repeat repeat repeat repeat wait(S2); wait(S3);取一個蘋果； 取一個橘子； 從盤子取一個蘋果； 從盤子取一個橘子； Wait(S1); Wait(S1); signal(S1); signal(S1); 放入盤子； 放入盤子 吃蘋果； 吃橘子； Signal(S2); Signal(S3); Until false; Until false; Until false; Until false; 3.a，b兩點之間是一段東西向的單行車道，現(xiàn)要設計一個自動管理系統(tǒng)，管理規(guī)則如下：（1）當ab之間有車輛在行駛時同方向的車可以同時駛?cè)隺b段，但另一方向的車必須在ab段外等待； （2）當ab之間無車輛在行駛時，到達a點（或b點）的車輛可以進入ab段，但不能從a點和b點同時駛?cè)耄?/p> （3）當某方向在ab段行駛的車輛駛出了ab段且暫無車輛進入ab段時，應讓另一方向等待的車輛進入ab段行駛。 請用信號量為工具，對ab段實現(xiàn)正確管理以保證行駛安全。分析： ① 約束： a)ab兩點的單行車道是一種臨界資源；兩端的車輛對該資源進行競爭； b)同步關系：（1），（3）； ② 經(jīng)上述分析可知： 首先，設置互斥信號量Sab=1，用于a、b點的車輛互斥進入ab段； 然后，分別設置共享變量ab=0用于記錄當前ab段上由a點進入的車輛數(shù)量；共享變量ba=0用于記錄當前ab=段上由b點進入車輛的數(shù)量； 最后，設置互斥信號量S1=1用于ab段的車輛互斥訪問共享變量ab；設置互斥信號量S2=1用于ba段的車輛互斥訪問共享變量ba ③建立進程？ semaphore S1=1,S2=1,Sab=1;int ab=ba=0;Pab： pba： Repeat repeat Wait(S1) Wait(s2) abcount=abcount+1; bacount=bacount+1;if abcount==1 then wait(sab) if bacount==1 then wait(sab)signal(S1) signal(s2)進入車道行駛； 進入車道行駛； Wait(s1) Wait(s2)abcount=abcount-1; bacount=bacount-1;if abcount==0 then signal(sab) if bacount==0 then signal(sab)signal(s1) signal(s2); until false; until false;main(){ Pab(); Pba();} 5．一條河上架設了由若干個橋墩組成的一座橋。若一個橋墩只能站一個人，過河的人只能沿著橋向前走而不能向后退。過河時，只要對岸無人過，就可以過。但不允許河對岸的兩個人同時過，以防止出現(xiàn)死鎖。請給出兩個方向的人順利過河的同步算法。分析： ① 約束： a)橋?qū)儆谂R界資源，兩岸的人對該資源進行競爭； b)橋上的人數(shù)是有限制的，設這個橋由N個橋墩構(gòu)成，橋上同時只能有N個人過橋，其它人要進行等待。相當于共享資源數(shù)。 ② 設置信號量 信號量s：互斥使用橋，初值為1 變量count1：方向1上過河人計數(shù)器 變量count2：方向2上過河人計數(shù)器 信號量scount1：對方向1上過河人計數(shù)器count1的互斥使用，初值為1 信號量scount2：對方向2上過河人計數(shù)器count2的互斥使用，初值為1 信號量scount：代表橋上過河人的計數(shù)信號量，初值為橋墩個數(shù)N ③ 建立進程 Semaphore s, scount1, scount2, scount;int count1, count2;s=1;scount1=1;scount2=1;scount=N;count1=0;count2=0; void direct1(int i){ wait(scount1);count1++;if(count1==1) wait(s);signal(scount1); wait(scount); 上橋，過橋，下橋； signal(scount); wait(scount1);count1--;if(count1==0) signal(s);signal(scount1);} void direct2(int i){ wait(scount2);count2++;if(count2==1) wait(s);signal(scount2); wait(scount);上橋，過橋，下橋； signal(scount); wait(scount2);count2--;if(count2==0) signal(s);signal(scount2);} main(){ cobegin{ direct1(1); … direct1(n); direct2(1); … direct2(m); } } 6．有一個倉庫，可以存放A和B兩種產(chǎn)品，但要求：（1）每次只能存入一種產(chǎn)品（A或B）； （2）-N＜A產(chǎn)品數(shù)量－B產(chǎn)品數(shù)量＜M。其中，N和M是正整數(shù)。試用同步算法描述產(chǎn)品A與產(chǎn)品B的入庫過程。分析： ① 約束： a)倉庫是一種臨界資源，兩種產(chǎn)品為之競爭； b)A產(chǎn)品數(shù)量不能比B產(chǎn)品數(shù)量多M個以上即A產(chǎn)品數(shù)量比B產(chǎn)品數(shù)量最多多M-1個；A產(chǎn)品數(shù)量不能比B產(chǎn)品數(shù)量少N個以上即B產(chǎn)品數(shù)量比A產(chǎn)品最多多N-1個。② 設置信號量 設置互斥信號量mutex互斥使用倉庫； 設置兩個信號量來控制A、B產(chǎn)品的存放數(shù)量，sa表示當前允許A產(chǎn)品比B產(chǎn)品多入庫的數(shù)量（當前允許A產(chǎn)品入庫數(shù)量）； sb表示當前允許B產(chǎn)品比A產(chǎn)品多入庫的數(shù)量（當前允許B產(chǎn)品入庫數(shù)量）。 初始時，sa為M一1，sb為N一1。當往庫中存放入一個A產(chǎn)品時，則允許存入B產(chǎn)品的數(shù)量也增加1;當往庫中存放入一個B產(chǎn)品時，則允許存入A產(chǎn)品的數(shù)量也增加1。 ③ 建立進程 semaphore mutex=1，sa=M-1，sb=N-1;process puta(){ while(1) { 取一個產(chǎn)品； wait(sa);wait(mutex);將產(chǎn)品入庫； signal(mutex);signal(sb);} } process putb(){ while(1) { 取一個產(chǎn)品； wait(sb);wait(mutex);將產(chǎn)品入庫； signal(mutex);signal(sa); } } main(){ cobegin{ puta();putb();} } 4．將只讀數(shù)據(jù)的進程稱為“讀者”進程，而寫或修改數(shù)據(jù)的進程稱為“寫者”進程。允許多個“讀者”同時讀數(shù)據(jù)，但不允許“寫者”與其他“讀者”或“寫者”同時訪問數(shù)據(jù)。另外，要保證：一旦有“寫者”等待時，新到達的“讀者”必須等待，直到該“寫者”完成數(shù)據(jù)訪問為止。試用P、V操作正確實現(xiàn)“讀者”與“寫者”的同步。（第二類讀者寫者問題，信號量解決方法） 分析： ① 約束： a)寫者與寫者之間需要互斥訪問； b)讀者與寫者之間需要互斥；（有一個讀者在讀就讓寫者等待），因此，此時需要一個計數(shù)變量記錄讀者的數(shù)量。c)允許多個讀者同時讀數(shù)據(jù)； d)一旦有“寫者”等待時，新到達的“讀者”必須等待，直到該“寫者”完成數(shù)據(jù)訪問為止。 ② 建立進程 Write: Repeat 執(zhí)行讀操作 Until false;Read: Repeat 執(zhí)行寫操作； Until false;③ 設置信號量 a)設置互斥信號量mutex=1實現(xiàn)寫者與寫者之間的互斥訪問； Write: Repeat Wait(mutex) 執(zhí)行讀操作； Signal(mutex);Until false; b)實現(xiàn)讀者與寫者之間的互斥，設置整型變量readcount=0記錄讀者數(shù)量，if readcount==1 then wait(mutex)Read： Repeat readcount++;if(readcount==1)wait(mutex); 執(zhí)行讀操作； readcount--;if(readcount==0)signal(mutex); until false;由于readcount 是共享變量，所以讀者之間要互斥訪問，因此設置一個互斥信號量rmutex=1.Read： Repeat Wait(rmutex)readcount++;if(readcount==1)wait(mutex);signal(rmutex)執(zhí)行讀操作； Wait(rmutex)readcount--;if(readcount==0)signal(mutex);signal(rmutex)until false; c)要想實現(xiàn)d）的互斥，需讓讀者和寫者再共享一個互斥信號量s，因此設置互斥信號量s=1，一旦有寫者等待時，就wait（s）讓讀者等待。Write: Repeat wait(wmutex);writecount++;if(writecount==1)wait(s);signal(wmutex); Wait(mutex) 執(zhí)行讀操作； Signal(mutex); wait(wmutex);writecount--;if(writecount==0)signal(s);signal(wmutex); Until false;Read： Repeat Wait(s);Wait(rmutex)readcount++;if(readcount==1)wait(mutex);signal(rmutex)signal(s);執(zhí)行讀操作； Wait(rmutex)readcount--;if(readcount==0)signal(mutex);signal(rmutex)until false; ④ 完整代碼 Process reader(){ while(1) { wait(s);wait(rmutex);if(readcount==0)wait(mutex);readcount++;signal(rmutex);signal(s); perform read operation; wait(rmutex);readcount--;if(readcount==0)signal(mutex);signal(rmutex);} } Process writer(){ while(1) { wait(wmutex);writecount++; if(writecount==1)wait(s);signal(wmutex); wait(mutex);perform write operation;signal(mutex); wait(wmutex);writecount--;if(writecount==0)signal(s);signal(wmutex);} } Main(){ cobegin { reader(); writer(); } } 1、在公共汽車上，司機和售票員的工作流程如圖所示。為保證乘客的安全，司機和售票員應密切配合協(xié)調(diào)工作。請用信號量來實現(xiàn)司機與售票員之間的同步。 司機 售票員 啟動車輛 關車門 正常行車 售票 到站停車 開車門 圖 司機和售票員工作流程圖 【答案】 設置兩個資源信號量：S1、S2。S1表示是否允許司機啟動汽車，其初值為0；S2表示是否允許售票員開門，其初值為0.semaphoere S1=S2=0;void Driver(){ while(1) { wait(S1); 啟動車輛； 正常行車； 到站停車； signal(S2); } } void Busman(){ while(1) { 關車門； signal(S1)； 售票； wait(S2)； 開車門； } } main(){ cobegin{ Driver(); Busman(); } } 2.桌子上有一只盤子，盤子中只能放一只水果。爸爸專向盤子中放蘋果，媽媽專向盤子中放橘子，一個兒子專等吃盤子中的橘子，一個女兒專等吃盤子中的蘋果。用PV操作實現(xiàn)他們之間的同步機制。 【答案】 信號量S用來實現(xiàn)盤子的互斥訪問，S1表示盤子中蘋果個數(shù)，S2表示盤子中橘子的個數(shù)。 semaphore S=1,S1=S2=0;void father(){ while(1) { 準備蘋果; wait(S); 將蘋果放在盤子內(nèi)； signal(S1); } } void mother(){ while(1) { 準備橘子; wait(S); 將橘子放在盤子內(nèi)； signal(S2); } } void daughter(){ while(1) { wait(Sl); 從盤子里拿走蘋果； signal(S); 吃蘋果; } } void son(){ while(1) { wait(S2); 從盤子里拿走橘子； signal(S); 吃橘子; } } main(){ cobegin{ father(); mother(); daughter(); son(); } } 3.a，b兩點之間是一段東西向的單行車道，現(xiàn)要設計一個自動管理系統(tǒng)，管理規(guī)則如下：（1）當ab之間有車輛在行駛時同方向的車可以同時駛?cè)隺b段，但另一方向的車必須在ab段外等待； （2）當ab之間無車輛在行駛時，到達a點（或b點）的車輛可以進入ab段，但不能從a點和b點同時駛?cè)耄?/p> （3）當某方向在ab段行駛的車輛駛出了ab段且暫無車輛進入ab段時，應讓另一方向等待的車輛進入ab段行駛。 請用信號量為工具，對ab段實現(xiàn)正確管理以保證行駛安全?！敬鸢浮?/p> 此題是讀者-寫者問題的變形。設置3個信號量S1、S2和Sab，分別用于從a點進入的車互斥訪問共享變量ab（用于記錄當前ab段上由a點進入車輛的數(shù)量），從b點進入的車互斥訪問共享變量ba（用于記錄當前ab段上由b點進入車輛的數(shù)量）和a、b點的車輛互斥進入ab段。3個信號量的初值分別為1、1和1，兩個共享變量ab和ba的初值分別為0、0。 semaphore S1=1,S2=1,Sab=1;int ab=ba=0;void Pab(){ while(1) { wait(S1); if(ab==0) wait(Sab); ab=ab+1; signal(S1); 車輛從a點駛向b點; wait(S1); ab=ab-1; if(ab==0) signal(Sab); signal(S1); } } void Pba(){ while(1) { wait(S2); if(ba==0) wait(Sab); ba=ba+1; signal(S2); 車輛從b點駛向a點; wait(S2); ba=ba-1; if(ba==0) signal(Sab); signal(S2); } } main(){ cobegin{ Pab(); Pba(); } } 4.將只讀數(shù)據(jù)的進程稱為“讀者”進程，而寫或修改數(shù)據(jù)的進程稱為“寫者”進程。允許多個“讀者”同時讀數(shù)據(jù)，但不允許“寫者”與其他“讀者”或“寫者”同時訪問數(shù)據(jù)。另外，要保證：一旦有“寫者”等待時，新到達的“讀者”必須等待，直到該“寫者”完成數(shù)據(jù)訪問為止。試用P、V操作正確實現(xiàn)“讀者”與“寫者”的同步。（第二類讀者寫者問題，信號量解決方法） 【答案】 為了使寫者優(yōu)先，可在原來的讀優(yōu)先算法的基礎上增加一個互斥信號量s，初值為1，使得當至少有一個寫者準備訪問共享對象時，它可以使后續(xù)的讀者進程等待； 整型變量writecount，初值為0，用來對寫者進行計數(shù)； 互斥信號量wmutex，初值為1，用來實現(xiàn)多個寫者對writecount進行互斥訪問。Process reader(){ while(1) { wait(s);wait(rmutex);if(readcount==0)wait(mutex);readcount++;signal(rmutex);signal(s); perform read operation; wait(rmutex);readcount--;if(readcount==0)signal(mutex);signal(rmutex); } } Process writer(){ while(1) { wait(wmutex);if(writecount==0)wait(s);writecount++;signal(wmutex); wait(mutex);perform write operation;signal(mutex); wait(wmutex);writecount--;if(writecount==0)signal(s);signal(wmutex);} } Main(){ cobegin { reader(); writer(); } } 5.一條河上架設了由若干個橋墩組成的一座橋。若一個橋墩只能站一個人，過河的人只能沿著橋向前走而不能向后退。過河時，只要對岸無人過，就可以過。但不允許河對岸的兩個人同時過，以防止出現(xiàn)死鎖。請給出兩個方向的人順利過河的同步算法。 【答案】 信號量s：互斥使用橋，初值為1 信號量scount1：對方向1上過河人計數(shù)器count1的互斥使用，初值為1 信號量scount2：對方向2上過河人計數(shù)器count2的互斥使用，初值為1 信號量scount：代表橋上過河人的計數(shù)信號量，初值為橋墩個數(shù)N 變量count1：方向1上過河人計數(shù)器 變量count2：方向2上過河人計數(shù)器 Semaphore s, scount1, scount2, scount;int count1, count2;s=1;scount1=1;scount2=1;scount=N;count1=0;count2=0; void direct1(int i){ wait(scount1);if(count1==0) wait(s);count1++;signal(scount1); wait(scount); 上橋，過橋，下橋； signal(scount); wait(scount1);count1--;if(count1==0) signal(s);signal(scount1);} void direct2(int i){ wait(scount2);if(count2==0) wait(s);count2++;signal(scount2); wait(scount);上橋，過橋，下橋； signal(scount); wait(scount2);count2--;if(count2==0) signal(s);signal(scount2);} main(){ cobegin{ direct1(1); … direct1(n); direct2(1); … direct2(m); } } 6、有一個倉庫，可以存放A和B兩種產(chǎn)品，但要求：（1）每次只能存入一種產(chǎn)品（A或B）；（2）-N＜A產(chǎn)品數(shù)量－B產(chǎn)品數(shù)量＜M。其中，N和M是正整數(shù)。試用同步算法描述產(chǎn)品A與產(chǎn)品B的入庫過程。 【答案】 A產(chǎn)品的數(shù)量不能比B產(chǎn)品的數(shù)量少N個以上，A產(chǎn)品的數(shù)量不能比B產(chǎn)品的數(shù)量多M個以上． 設置兩個信號量來控制A、B產(chǎn)品的存放數(shù)量，sa表示當前允許A產(chǎn)品比B產(chǎn)品多入庫的數(shù)量（當前允許A產(chǎn)品入庫數(shù)量），即在當前庫存量和B產(chǎn)品不入庫的情況下，還可以允許sa個A產(chǎn)品入庫； sb表示當前允許B產(chǎn)品比A產(chǎn)品多入庫的數(shù)量（當前允許B產(chǎn)品入庫數(shù)量），即在當前庫存量和A產(chǎn)品不入庫的情況下，還可以允許sb個B產(chǎn)品入庫。 初始時，sa為M一1，sb為N一1。當往庫中存放入一個A產(chǎn)品時，則允許存入B產(chǎn)品的數(shù)量也增加1;當往庫中存放入一個B產(chǎn)品時，則允許存入A產(chǎn)品的數(shù)量也增加1。 semaphore mutex=1，sa=M-1，sb=N-1;process puta(){ while(1) { 取一個產(chǎn)品； wait(sa);wait(mutex);將產(chǎn)品入庫； signal(mutex);signal(sb);} } process putb(){ while(1) { 取一個產(chǎn)品； wait(sb);wait(mutex);將產(chǎn)品入庫； signal(mutex);signal(sa); } } main(){ cobegin{ puta();putb();} } 進程同步練習題 1.在公共汽車上，司機和售票員的工作流程如圖所示。為保證乘客的安全，司機和售票員應密切配合協(xié)調(diào)工作。請用信號量來實現(xiàn)司機與售票員之間的同步。 司機 售票員 啟動車輛 關車門 正常行車 售票 到站停車 開車門 圖 司機和售票員工作流程圖 2.桌子上有一只盤子，盤子中只能放一只水果。爸爸專向盤子中放蘋果，媽媽專向盤子中放橘子，一個兒子專等吃盤子中的橘子，一個女兒專等吃盤子中的蘋果。用PV操作實現(xiàn)他們之間的同步機制。 3.a，b兩點之間是一段東西向的單行車道，現(xiàn)要設計一個自動管理系統(tǒng)，管理規(guī)則如下：（1）當ab之間有車輛在行駛時同方向的車可以同時駛?cè)隺b段，但另一方向的車必須在ab段外等待； （2）當ab之間無車輛在行駛時，到達a點（或b點）的車輛可以進入ab段，但不能從a點和b點同時駛?cè)耄?/p> （3）當某方向在ab段行駛的車輛駛出了ab段且暫無車輛進入ab段時，應讓另一方向等待的車輛進入ab段行駛。 請用信號量為工具，對ab段實現(xiàn)正確管理以保證行駛安全。 4．將只讀數(shù)據(jù)的進程稱為“讀者”進程，而寫或修改數(shù)據(jù)的進程稱為“寫者”進程。允許多個“讀者”同時讀數(shù)據(jù)，但不允許“寫者”與其他“讀者”或“寫者”同時訪問數(shù)據(jù)。另外，要保證：一旦有“寫者”等待時，新到達的“讀者”必須等待，直到該“寫者”完成數(shù)據(jù)訪問為止。試用P、V操作正確實現(xiàn)“讀者”與“寫者”的同步。（第二類讀者寫者問題，信號量解決方法） 5．一條河上架設了由若干個橋墩組成的一座橋。若一個橋墩只能站一個人，過河的人只能沿著橋向前走而不能向后退。過河時，只要對岸無人過，就可以過。但不允許河對岸的兩個人同時過，以防止出現(xiàn)死鎖。請給出兩個方向的人順利過河的同步算法。6．有一個倉庫，可以存放A和B兩種產(chǎn)品，但要求：（1）每次只能存入一種產(chǎn)品（A或B）； （2）-N＜A產(chǎn)品數(shù)量－B產(chǎn)品數(shù)量＜M。其中，N和M是正整數(shù)。試用同步算法描述產(chǎn)品A與產(chǎn)品B的入庫過程。 1、在公共汽車上，司機和售票員的工作流程如圖所示。為保證乘客的安全，司機和售票員應密切配合協(xié)調(diào)工作。請用信號量來實現(xiàn)司機與售票員之間的同步。 司機 售票員 啟動車輛 關車門 正常行車 售票 到站停車 開車門 圖 司機和售票員工作流程圖 【答案】 設置兩個資源信號量：S1、S2。S1表示是否允許司機啟動汽車，其初值為0；S2表示是否允許售票員開門，其初值為0.semaphoere S1=S2=0;void Driver(){ while(1) { wait(S1); 啟動車輛； 正常行車； 到站停車； signal(S2); } } void Busman(){ while(1) { 關車門； signal(S1)； 售票； wait(S2)； 開車門； } } main(){ cobegin{ Driver(); Busman(); } } 2.桌子上有一只盤子，盤子中只能放一只水果。爸爸專向盤子中放蘋果，媽媽專向盤子中放橘子，一個兒子專等吃盤子中的橘子，一個女兒專等吃盤子中的蘋果。用PV操作實現(xiàn)他們之間的同步機制。 【答案】 信號量S用來實現(xiàn)盤子的互斥訪問，S1表示盤子中蘋果個數(shù)，S2表示盤子中橘子的個數(shù)。 semaphore S=1,S1=S2=0;void father(){ while(1) { 準備蘋果; wait(S); 將蘋果放在盤子內(nèi)； signal(S1); } } void mother(){ while(1) { 準備橘子; wait(S); 將橘子放在盤子內(nèi)； signal(S2); } } void daughter(){ while(1) { wait(Sl); 從盤子里拿走蘋果； signal(S); 吃蘋果; } } void son(){ while(1) { wait(S2); 從盤子里拿走橘子； signal(S); 吃橘子; } } main(){ cobegin{ father(); mother(); daughter(); son(); } } 3.a，b兩點之間是一段東西向的單行車道，現(xiàn)要設計一個自動管理系統(tǒng)，管理規(guī)則如下：（1）當ab之間有車輛在行駛時同方向的車可以同時駛?cè)隺b段，但另一方向的車必須在ab段外等待； （2）當ab之間無車輛在行駛時，到達a點（或b點）的車輛可以進入ab段，但不能從a點和b點同時駛?cè)耄?/p> （3）當某方向在ab段行駛的車輛駛出了ab段且暫無車輛進入ab段時，應讓另一方向等待的車輛進入ab段行駛。 請用信號量為工具，對ab段實現(xiàn)正確管理以保證行駛安全。【答案】 此題是讀者-寫者問題的變形。設置3個信號量S1、S2和Sab，分別用于從a點進入的車互斥訪問共享變量ab（用于記錄當前ab段上由a點進入車輛的數(shù)量），從b點進入的車互斥訪問共享變量ba（用于記錄當前ab段上由b點進入車輛的數(shù)量）和a、b點的車輛互斥進入ab段。3個信號量的初值分別為1、1和1，兩個共享變量ab和ba的初值分別為0、0。 semaphore S1=1,S2=1,Sab=1;int ab=ba=0;void Pab(){ while(1) { wait(S1); if(ab==0) wait(Sab); ab=ab+1; signal(S1); 車輛從a點駛向b點; wait(S1); ab=ab-1; if(ab==0) signal(Sab); signal(S1); } } void Pba(){ while(1) { wait(S2); if(ba==0) wait(Sab); ba=ba+1; signal(S2); 車輛從b點駛向a點; wait(S2); ba=ba-1; if(ba==0) signal(Sab); signal(S2); } } main(){ cobegin{ Pab(); Pba(); } } 4.將只讀數(shù)據(jù)的進程稱為“讀者”進程，而寫或修改數(shù)據(jù)的進程稱為“寫者”進程。允許多個“讀者”同時讀數(shù)據(jù)，但不允許“寫者”與其他“讀者”或“寫者”同時訪問數(shù)據(jù)。另外，要保證：一旦有“寫者”等待時，新到達的“讀者”必須等待，直到該“寫者”完成數(shù)據(jù)訪問為止。試用P、V操作正確實現(xiàn)“讀者”與“寫者”的同步。（第二類讀者寫者問題，信號量解決方法） 【答案】 為了使寫者優(yōu)先，可在原來的讀優(yōu)先算法的基礎上增加一個互斥信號量s，初值為1，使得當至少有一個寫者準備訪問共享對象時，它可以使后續(xù)的讀者進程等待； 整型變量writecount，初值為0，用來對寫者進行計數(shù)； 互斥信號量wmutex，初值為1，用來實現(xiàn)多個寫者對writecount進行互斥訪問。Process reader(){ while(1) { wait(s);wait(rmutex);if(readcount==0)wait(mutex);readcount++;signal(rmutex);signal(s); perform read operation; wait(rmutex);readcount--;if(readcount==0)signal(mutex);signal(rmutex);} } Process writer(){ while(1) { wait(wmutex);if(writecount==0)wait(s);writecount++;signal(wmutex); wait(mutex);perform write operation;signal(mutex); wait(wmutex);writecount--;if(writecount==0)signal(s);signal(wmutex);} } Main(){ cobegin { reader(); writer(); } } 5.一條河上架設了由若干個橋墩組成的一座橋。若一個橋墩只能站一個人，過河的人只能沿著橋向前走而不能向后退。過河時，只要對岸無人過，就可以過。但不允許河對岸的兩個人同時過，以防止出現(xiàn)死鎖。請給出兩個方向的人順利過河的同步算法。 【答案】 信號量s：互斥使用橋，初值為1 信號量scount1：對方向1上過河人計數(shù)器count1的互斥使用，初值為1 信號量scount2：對方向2上過河人計數(shù)器count2的互斥使用，初值為1 信號量scount：代表橋上過河人的計數(shù)信號量，初值為橋墩個數(shù)N 變量count1：方向1上過河人計數(shù)器 變量count2：方向2上過河人計數(shù)器 Semaphore s, scount1, scount2, scount;int count1, count2;s=1;scount1=1;scount2=1;scount=N;count1=0;count2=0; void direct1(int i){ wait(scount1);if(count1==0) wait(s);count1++;signal(scount1); wait(scount); 上橋，過橋，下橋； signal(scount); wait(scount1);count1--;if(count1==0) signal(s);signal(scount1);} void direct2(int i){ wait(scount2);if(count2==0) wait(s);count2++;signal(scount2); wait(scount);上橋，過橋，下橋； signal(scount);wait(scount2);count2--;if(count2==0) signal(s);signal(scount2);} main(){ cobegin{ direct1(1); … direct1(n); direct2(1); … direct2(m); } } 6、有一個倉庫，可以存放A和B兩種產(chǎn)品，但要求：（1）每次只能存入一種產(chǎn)品（A或B）；（2）-N＜A產(chǎn)品數(shù)量－B產(chǎn)品數(shù)量＜M。其中，N和M是正整數(shù)。試用同步算法描述產(chǎn)品A與產(chǎn)品B的入庫過程。 【答案】 A產(chǎn)品的數(shù)量不能比B產(chǎn)品的數(shù)量少N個以上，A產(chǎn)品的數(shù)量不能比B產(chǎn)品的數(shù)量多M個以上． 設置兩個信號量來控制A、B產(chǎn)品的存放數(shù)量，sa表示當前允許A產(chǎn)品比B產(chǎn)品多入庫的數(shù)量（當前允許A產(chǎn)品入庫數(shù)量），即在當前庫存量和B產(chǎn)品不入庫的情況下，還可以允許sa個A產(chǎn)品入庫； sb表示當前允許B產(chǎn)品比A產(chǎn)品多入庫的數(shù)量（當前允許B產(chǎn)品入庫數(shù)量），即在當前庫存量和A產(chǎn)品不入庫的情況下，還可以允許sb個B產(chǎn)品入庫。 初始時，sa為M一1，sb為N一1。當往庫中存放入一個A產(chǎn)品時，則允許存入B產(chǎn)品的數(shù)量也增加1;當往庫中存放入一個B產(chǎn)品時，則允許存入A產(chǎn)品的數(shù)量也增加1。 semaphore mutex=1，sa=M-1，sb=N-1;process puta(){ while(1) { 取一個產(chǎn)品； wait(sa);wait(mutex);將產(chǎn)品入庫； signal(mutex);signal(sb);} } process putb(){ while(1) { 取一個產(chǎn)品； wait(sb);wait(mutex);將產(chǎn)品入庫； signal(mutex);signal(sa); } } main(){ cobegin{ puta();putb();} } 案例4 對互斥事件的教學設計 [設計者] 房之華（江蘇省蘇州大學附屬中學） 設計符合現(xiàn)代教育理念和新課程標準的教學方案，是當前教育探討的熱門話題，而概率又是新增加的高中數(shù)學內(nèi)容，具有一定的難度，學生在學習中會產(chǎn)生許多困惑，為了讓學生能正確地理解并掌握，精心地設計教學方案顯得格外重要.筆者就概率中較難學習的一節(jié)內(nèi)容“互斥事件有一個發(fā)生的概率”給出教學方案的一個設計，供大家參考.[課題] 互斥事件有一個發(fā)生的概率 [教學目標] 通過探究式教學，使學生能正確地理解并掌握“互斥事件”、“彼此互斥”和“對立事件”等概念，理解并掌握當AB互斥時“事件A+B”的含義及其概率的求法，了解對立事件的概率的和為1的結(jié)論，會應用所學知識解決實際問題.通過探究式教學，引導學生學會學習“互斥事件有一個發(fā)生的概率”，學會如何觀察、推理和評價，潛移默化地激發(fā)學生的情感，使學生形成一種積極的態(tài)度和正確的人生價值觀.通過探究式教學，讓學生養(yǎng)成手、口、眼、耳、腦五官并用的良好習慣，強化動作技能的熟練.（點評：教學目標是對教學行動結(jié)果的預期.教學目標一般涉及三大領域：認知領域、情感領域和動作領域，認知領域的目標是現(xiàn)代學校教育最重要的領域，根據(jù)教學目標是重視學生的學習結(jié)果還是過程，教學目標又可分為行為目標和過程目標，我們在確定教學目標時應全方位地加以考慮.） [教學重點] 互斥事件的概念及其概率的求法 [教學難點] 對立事件與互斥事件的關系，事件A+B的概率的計算方法.[教學模式] 以探究為主導策略的教學模式，“幫助學生發(fā)展理智素養(yǎng)和理智技能”.（點評：在探究模式中，大部分時間由教師控制，但仍需要學生積極參與活動，教師的主要任務是為學生的探究活動去精心地創(chuàng)設問題情境，并對學生的探究結(jié)果給出客觀性的評價） [教學程序] 1、創(chuàng)設情境，讓學生的思維“動”起來 [問題1] 在一個盒子內(nèi)放有10個大小相同的小球，其中有7個紅球，2個綠球，1個黃球.若從盒中摸出1個紅球記為事件A，從盒中摸出1個綠球記為事件B，從盒中摸出1個黃球記為事件C，則事件A、B、C之間存在怎樣的關系（如圖1）？ 思考1：如果從盒中摸出1個是紅球，則說明事件A怎么樣？ 思考2：如果從盒中摸出的1個球是綠球，即事件B發(fā)生，則說明事件A又如何呢？ 思考3：通過對1、2的探究你發(fā)現(xiàn)了什么？ （點評：以上幾個思考題不能和盤托出，應逐個拋出，并留給學生思維的空間，讓學生的頭腦動起來.）學生展開思維活動，并將探索出來的結(jié)論加以歸納概括.[探究結(jié)論1] 事件A與B不可能同時發(fā)生，這種不可能同時發(fā)生的兩個事件叫做互斥事件.同理，事件B與C、事件A與C都是互斥事件.思考4：若事件A、B、C中任何兩個都是互斥事件，則就事件A、B、C彼此互斥，那么，三個以上的事件是否也能存在這樣的關系呢？若能，請你把它推廣到n個事件的情形.（點評：引導學生的思維向縱深發(fā)展，由特殊的情形去大膽地猜想一般的情形是否也存在，從而培養(yǎng)學生由特殊到一般的推理思維方式.） 2、廣泛聯(lián)想，讓學生的思維“活”起來 為了加深對概念的深刻理解，更清楚地認識事物的本質(zhì)屬性，迅速地建構(gòu)起知識的認知結(jié)構(gòu)，教師應引導學生展開廣泛的聯(lián)想.（點評：集合是數(shù)學中基本概念之一，是聯(lián)系中學數(shù)學中眾多不同知識的紐帶，當從集合的角度去認識排列、組合和概率時，求排列數(shù)、組合數(shù)和概率，都可看成一個全集下的某個子集到數(shù)的集合的不同的映射，這樣有助于揭示這些概念的本質(zhì)及其內(nèi)在聯(lián)系，可見廣泛的聯(lián)想能讓學生的思維活躍起來.） [設問1] 聯(lián)想集合的知識，想一想，能用集合的知識來解釋互斥事件的概念嗎？若能，請給出互斥事件的集合意義.[聯(lián)想與思考] 要求學生在聯(lián)想與獨立思考的基礎上開展小組討論，并歸納概括出建立在集合意義上的互斥事件的形象解釋.[探究結(jié)論3] 從集合的角度看，幾個事件彼此互斥，是指由各個事件所含的結(jié)果組成的集合彼此不相交，即交集是空集，如圖1所示.[設問3] 互斥事件與對立事件存在著怎樣的關系？ 學生思考、討論與概括可得如下的探究結(jié)論： [探究結(jié)論5] 一般地，兩個事件對立是兩個事件互斥的充分條件，但不是必要條件.[反饋訓練]判別下列每對事件是否是互斥事件： 從一堆產(chǎn)品（其中正品與次品都多于2個）中任取2件，其中：（1）恰有1件次品和恰有2件次品；（2）至少有1件正品和全是次品；（3）至少有1件正品和至少有1件次品；（4）至少有1件次品和全是正品； 先由學生獨立思考與求解，再請一名學生公布所做的答案，讓大家來評判與討論，直至得到正確答案.（點評：及時反饋是檢驗概念掌握情況的有效措施，通過練習來糾正學生對概念理解中的錯誤，從而強化概念的理解與掌握.） 3、變式教學，讓學生的思維“跳”起來 對問題不斷地進行變換，在變換中增加思維的難度，讓學生的思維“跳一跳”才能夠得著，以便培養(yǎng)學生探究與創(chuàng)新的能力.[變換1] 對上面的問題1稍作變形：“若從盒中摸出1個球，得到紅球或綠球的概率是多少？”（點評：經(jīng)變換后的問題，顯然增加了思維的難度，為了讓學生“跳一跳”能夠得著，有必要把問題加以分解，為問題的解決搭設思維的臺階，本題難在其事件的結(jié)果為若干個，而不是單一的.） 為了解答這個問題，我們可以設計系列思考題，從而降低問題的難度.思考1：滿足怎樣的條件，才表示這個事件發(fā)生？ 思考2：這個事件是否能分解為若干個基本事件？ 思考3：若把這個事件記作A+B，則A+B的概率如何求？ 引導學生思考與討論，可得出如下結(jié)論： 4、注重反思，讓學生的思維“深”下去 解決問題不能只追求得出一個答案，應注重解題后的反思，這樣才能從題海中解脫出來，達到舉一反 三、觸類旁通的功效，才能訓練學生思維的深刻性.例1 某地區(qū)的年降水量在下列范圍內(nèi)的概率如下表所示： 引導學生分析與探究，并讓學生登臺講解，然后引導學生反思，歸納求解的方法與步驟，以及應當注意的問題.[反思1] 設定義過的事件A、B、C、D是彼此互斥的事件組，要結(jié)合題意分析清楚互斥的原因；所求事件是關于互斥事件A、B、C、D中兩個或幾個的和的事件，不符合這兩點，就不能運用互斥事件的概率加法公式.[反思2] 解題步驟可歸結(jié)為如下四步： （1）用數(shù)學符號來表示問題中的有關事件；（2）判斷各事件間的互斥性；（3）應用概率加法公式進行計算；（4）寫出答案.例2 在20件產(chǎn)品中，有15件一級品，5件二級品，從中取3件，其中至少有1件為二級品的概率是多少？ 引導學生分析，求解與反思.[反思1] 當問題所涉及的事件包含若干個事件時，要注意進行合理的分類討論，如：“至少有1件為二級品”可分解為3個事件：示3件全是二級品的事件.[反思2] 在求某些稍復雜的事件的概率時，通常有兩種方法：一是將所求事件的概率化成一些彼此互斥的事件的概率的和，二是先去求此事件的對立事件的概率，前者是直接法，后者為逆向思維法，即間接法.5、學會建構(gòu)，讓學生的思維得以升華 零散的知識點，不易被人們所接受和記憶，教師要引導學生對所學的內(nèi)容給予高度的抽象和概括，建構(gòu)精煉的知識結(jié)構(gòu)的框架，便于記憶和應用.本教案的教學設計試圖依據(jù)新課程所倡導的教學理念，注重課程的發(fā)生和開發(fā)過程，注重師生交往、互動、共同發(fā)展的過程，關注學生的發(fā)展和情感體驗.參考文獻： 1.陳希平.實驗直觀 抽象 目標 評價 調(diào)控.數(shù)學通報.2002，6 表示恰有1件為二級品的事件，表示恰有2件為二級品的事件，表2.房之華.對互斥事件的教學設計.數(shù)學教學.2004，4 3.傅建明.課堂教學基本技能訓練.杭州大學出版社，1995，11 4.奚定華.數(shù)學教學設計.華東師范大學出版社，2001，1 5.徐英俊.教學設計，教育科學出版社，2001.9 6.王書臣，劉長華，蔣永晶.數(shù)學新課程教學設計，遼寧師范大學出版社，2002.5 7.張景斌.中學數(shù)學教學教程.科學出版社2000，12 計算機操作系統(tǒng)實驗報告 一、實驗名稱：售票員和汽車司機的進程同步問題 二、實驗內(nèi)容：創(chuàng)建兩個進程模擬售票員和汽車司機的同步行為。具體內(nèi)容如下： 1.司機的活動：啟動車輛，正常行車，到站停車。2.售票員活動：關車門，售票，開車門。 3.當發(fā)車時間到，售票員關好車門后，司機才能啟動車輛，售票員才開始售票。當?shù)秸緯r，司機停穩(wěn)車后，售票員才能打開車門，車上乘客先下車，然后站牌乘客上車。 三、問題分析與設計 分析：司機與售票員要協(xié)同工作:一方面只有售票員把門關好之后司機才可開車，因此售票員關好門之后要通知司機開車，然后售票；另一方面，也只有司機把車停下之后售票員才能開門讓乘客下車和上車，因此，此時司機應通知售票員。汽車當前正在始發(fā)站停車讓乘客讓乘客上車，因此，必須設置一定的信號量來實現(xiàn)他們之間的同步問題。 設計：設置司機與售票員的信號量為全局變量，并且客車的人數(shù)：現(xiàn)在人數(shù)、下車人數(shù)、上車人數(shù)為全局變量；設置司機與售票員的線程?？紤]到第一站和最后一站的問題，應單獨處理，故在各自的線程中分情況討論： 具體的思路是下面的圖示。其中S1是司機的信號量，S2是售票員的信號量。 程序的實現(xiàn)（代碼）： #include int Recent_num=0;//某一時刻的客車上的人數(shù) int Get_on_num;//上車的人數(shù) int Get_off_num;//下車的人數(shù) int pork=1;//客車到達路線的站數(shù) HANDLE Semaphore_driver;//Driver的信號量 HANDLE Semaphore_conductor;//Conductor的信號量 //產(chǎn)生一定范圍的隨機數(shù)，可避免下面程序的判斷是否超出客車的最大容量問題 int Get_random(int min,int max){ int a;srand((int)time(0));while(1){ a=rand()%(Total_num+1);if(a>=min && a<=max)return a;} } //Driver的線程 DWORD WINAPI Thread_Driver(LPVOID Driver){ while(pork<=Total_num){ if(pork==Total_pork){ WaitForSingleObject(Semaphore_driver,INFINITE);printf(“終點站到了,謝謝乘坐該公交車，祝您愉快!n”);printf(“到達終點站時汽車上還有 %d 人。n”,Recent_num);ReleaseSemaphore(Semaphore_conductor,1,NULL);return 0;} else { if(pork==1)printf(“發(fā)車時間到，現(xiàn)在是第 %d 站n”,pork);else printf(“ %d 站到了n”,pork);if(pork!=1)printf(“司機已停車。n”); ReleaseSemaphore(Semaphore_conductor,1,NULL);// 增加信號量 WaitForSingleObject(Semaphore_driver,INFINITE);printf(“已關門，汽車開始行使。n”);ReleaseSemaphore(Semaphore_conductor,1,NULL);} Sleep(1000);} return 0;} //Conductor的線程 DWORD WINAPI Thread_Conductor(LPVOID Conductor){ while(1){ if(pork < Total_pork){ WaitForSingleObject(Semaphore_conductor,INFINITE);if(pork==1){ Get_on_num=Get_random(0,Total_num-Recent_num);printf(“ %d 人已經(jīng)從該站上車。n”,Get_on_num);Recent_num+=Get_on_num;} else { printf(“售票員請開門讓乘客上下車！n”);Get_off_num=Get_random(0,Recent_num);printf(“%d人從第 %d 站下車。n”,Get_off_num,pork);Sleep(1000);//避免了時間的問題帶來的不是隨機數(shù)的現(xiàn)象 Recent_num-=Get_off_num;Get_on_num=Get_random(0,Total_num-Recent_num);printf(“%d人從該第 %d 站上車。n”,Get_on_num,pork);Recent_num+=Get_on_num;} printf(“此時車上共有：%d人n”,Recent_num);printf(“上車或下車完畢，售票員請關門！n”);ReleaseSemaphore(Semaphore_driver,1,NULL); WaitForSingleObject(Semaphore_conductor,INFINITE);printf(“現(xiàn)在售票員開始售票。n”);printf(“nnnn”);pork++;} if(pork==Total_pork){ ReleaseSemaphore(Semaphore_driver,1,NULL); WaitForSingleObject(Semaphore_conductor,INFINITE);printf(“售票員請開門讓乘客下車！n”);return 0;} Sleep(1000);} return 0;} //主函數(shù) int main(){ HANDLE Driver;HANDLE Conductor; Semaphore_driver=CreateSemaphore(NULL,0,1,“semaphore_driver”);//創(chuàng)建Driver的信號量 Semaphore_conductor=CreateSemaphore(NULL,0,1,“semaphore_conductor”);//創(chuàng)建Conductor的信號量 Driver=CreateThread(NULL,0,Thread_Driver,&Driver,0,NULL);//創(chuàng)建Driver的線程 Conductor=CreateThread(NULL,0,Thread_Conductor,&Conductor,0,NULL);//創(chuàng)建Conductor的線程 CloseHandle(Driver);//關閉Driver的線程 CloseHandle(Conductor);//關閉Conductor的線程 //GetLastError();while(1);system(“pause”);return 0;} 程序執(zhí)行結(jié)果： 實驗心得與反思： 通過本次實驗，加深了我們對進程同步與互斥的理解，而且懂WaitForSingleObject函數(shù)的作用，它相當于P操作；而ReleaseSemaphore函數(shù)相當于V操作，用這兩個函數(shù)來實現(xiàn)P,V操作，以改變信號量的值，從而實現(xiàn)進程同步。實驗過程中，我們發(fā)現(xiàn)以下是我們應該反思的： 1：線程的創(chuàng)建的函數(shù)的參數(shù)的理解還不太懂，主要是沒學過，對于其中的一些調(diào)用函數(shù)不太懂里面的意思。 2：線程的設計要考慮到各個情況，第一站和最后一戰(zhàn)，還有其中的全局的變量的運算的放到的是售票員的線程中，也就是其中的一些操作的位置問題，要考慮到同步的兩個線程之間的關系。3：關于信號量的問題，其要的是全局變量。 4：最最重要的是一些Win32 API 中的庫函數(shù)有關線程的創(chuàng)建等的理解，對其中的函數(shù)參量的理解有待進一步學習理解。 09信管（2）班 何美西 109253030212 樊麗彬 109253030215 孔娜 109253030218第二篇：進程同步典型例題(操作系統(tǒng))
第三篇：新版進程同步典型例題(操作系統(tǒng))
第四篇：互斥事件(示范教案)
第五篇：售票員和汽車司機的進程同步問題
點擊咨詢 