【正文】 :integer。 begin P(S)。 x:=0。 t:=0。 If x1 then t:=t+2。V(S)。 u:=t。 EndCoend 消息緩沖通信機(jī)制有什么好處？試述消息緩沖通信的過程。解 消息緩沖通信機(jī)制不僅能較好地解決進(jìn)程間的同步互斥問題，還能交換大量信息，是理想的進(jìn)程通信工具，而且操作系統(tǒng)隱藏了進(jìn)程通信的實(shí)現(xiàn)細(xì)節(jié)，即通信過程對(duì)用戶是透明的，這樣就大大地簡化了通信程序編制上的復(fù)雜性。消息緩沖通信的過程如下：當(dāng)某個(gè)進(jìn)程需要向另一個(gè)進(jìn)程發(fā)送消息時(shí)，便向系統(tǒng)申請(qǐng)一個(gè)消息緩沖區(qū)，并把要發(fā)送的數(shù)據(jù)送到消息緩沖區(qū)，然后把該消息緩沖區(qū)插入到接受進(jìn)程的消息隊(duì)列中。接受進(jìn)程在接受消息時(shí)，只要從本進(jìn)程的消息隊(duì)列中摘下該消息緩沖區(qū)，即可從中取下所需的信息，然后把該消息緩沖區(qū)交還給系統(tǒng)。 讀者和寫者問題。有一數(shù)據(jù)區(qū)可為多個(gè)進(jìn)程共享。假設(shè)一些進(jìn)程只能對(duì)數(shù)據(jù)區(qū)進(jìn)行讀操作（讀者），而另一些進(jìn)程只能進(jìn)行寫操作（寫者），讀者和寫者需要遵守如下規(guī)則：(1) 多個(gè)讀者可以同時(shí)從數(shù)據(jù)區(qū)取數(shù)據(jù)；(2) 讀、寫操作不能同時(shí)進(jìn)行；(3) 寫操作不能同時(shí)進(jìn)行。 解 這是一個(gè)經(jīng)典的問題，該問題首先在1971年由Courtois等人解決。根據(jù)規(guī)則可知，寫操作與寫操作是互斥的，寫操作與所有的讀操作是互斥的，讀操作與讀操作之間是可以同時(shí)進(jìn)行的。（1）讀寫進(jìn)程操作的流程如下：〈寫進(jìn)程〉是否有讀進(jìn)程讀數(shù)據(jù)？有，則等待；是否有寫進(jìn)程寫數(shù)據(jù)？有，則等待；寫數(shù)據(jù)；設(shè)立可寫標(biāo)志；設(shè)立可讀標(biāo)志?！醋x進(jìn)程〉是否有寫進(jìn)程寫數(shù)據(jù)？有，則等待；讀數(shù)據(jù)；設(shè)立可寫標(biāo)志（2）信號(hào)量及其含義 根據(jù)上述的流程，可以得出需要3個(gè)信號(hào)量：WRM是讀寫互斥，用于讀進(jìn)程與寫進(jìn)程之間的互斥，表示是否沒有讀寫操作，可否進(jìn)行讀寫操作；WM是用于寫進(jìn)程與寫進(jìn)程之間的互斥，表示是否沒有寫操作，是否可以進(jìn)行寫操作；countM是用于讀進(jìn)程互斥操作讀進(jìn)程個(gè)數(shù)變變量readcount，其含義為readcount是否可操作。這里關(guān)鍵問題是即要實(shí)現(xiàn)讀寫互斥，又要實(shí)現(xiàn)并發(fā)的讀操作。為此引入一個(gè)變量readcount，來記錄當(dāng)前需要進(jìn)行讀操作進(jìn)程的個(gè)數(shù)，當(dāng)readcount0時(shí)，表示有讀操作進(jìn)程，readcount=0時(shí)表示沒有讀操作進(jìn)程。因此，當(dāng)readcount開始大于0時(shí)，即readcount=1時(shí)，開始讀進(jìn)程開始讀寫互斥，readcount=0時(shí)，讀進(jìn)程撤消讀寫互斥。這樣就把每個(gè)讀進(jìn)程與寫進(jìn)程的互斥轉(zhuǎn)化為整個(gè)讀操作與寫操作的互斥。 （3）P、V操作的確定 〈寫進(jìn)程〉P(WRM)P(WM)寫數(shù)據(jù)V(WRM)V(WM)〈讀進(jìn)程〉P(countM)Readcount= Readcount+1If Readcount=1 then P(WRM)。V(countM)讀數(shù)據(jù)P(countM)Readcount= Readcount1If Readcount=0 then V(WRM)。V(countM)以上的解法是讀進(jìn)程優(yōu)先的，也就是說一旦一個(gè)讀進(jìn)程開始讀操作，只要還有需要進(jìn)行讀操作的進(jìn)程，那么，就要保持讀操作的獨(dú)占，直到?jīng)]有讀進(jìn)程操作的時(shí)候，即讀進(jìn)程記數(shù)Readcount=0時(shí)，才能允許寫進(jìn)程進(jìn)行操作。這里可以將WRM和WM合并成一個(gè)信號(hào)量，現(xiàn)在這樣做可以更容易理解些。 （4）信號(hào)量的初值 WRM=1；WM=1；countM=0。 桌上有一空盤，只允許存放一個(gè)水果。爸爸可向盤中放蘋果，也可向盤中放桔子。兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當(dāng)盤中空時(shí)一次只能放一只水果供吃者取用，請(qǐng)用P、V原語實(shí)現(xiàn)爸爸、兒子、女兒三個(gè)并發(fā)進(jìn)程的同步。分析 在本題中，爸爸、兒子、女兒共用一個(gè)盤子，且盤中一次只能放一個(gè)水果。當(dāng)盤子為空時(shí)，爸爸可將一個(gè)水果放入果盤中。若放入果盤中的是蘋果，則允許女兒吃，兒子必須等待；若放入果盤中的是桔子，則允許兒子吃，女兒必須等待。本題實(shí)際上是生產(chǎn)者消費(fèi)者問題的一種變形。這里，生產(chǎn)者放入緩沖區(qū)的產(chǎn)品有兩類，消費(fèi)者也有兩類，每類消費(fèi)者只消費(fèi)其中固定的一類產(chǎn)品。解 在本題中，應(yīng)設(shè)置三個(gè)信號(hào)量S、So、Sa，信號(hào)量S表示盤子是否為空，其初值為1；信號(hào)量So表示盤中是否有桔子，其初值為0；信號(hào)量Sa表示盤中是否有蘋果，其初值為0。同步描述如下：int S=1。int Sa=0。int So=0。main( ){ cobeginfather()。son()。daughter()。coend}father(){ while(1){ P(S )。將水果放入盤中；if （放入的是桔子） V(So)。else V(Sa)。}}son( ){ while(1){ P(So)。從盤中取出桔子；V(S)。吃桔子；} }daughter( ){ while(1){P(Sa)。從盤中取出蘋果；V(S)。吃蘋果；}} 習(xí)題 選擇最合適的答案1. 用P、V操作管理臨界區(qū)時(shí)，信號(hào)量的初值一般應(yīng)定義為（ ）。A.–1 2. 有m個(gè)進(jìn)程共享同一臨界資源，若使用信號(hào)量機(jī)制實(shí)現(xiàn)對(duì)一臨界資源的互斥訪問，則信號(hào)量的變化范圍是（ ）。 –(m1) –m 3. 在下面的敘述中，正確的是（ ）。 4. 對(duì)進(jìn)程間互斥地使用臨界資源，進(jìn)程可以（ ） 5. 設(shè)兩個(gè)進(jìn)程共用一個(gè)臨界資源的互斥信號(hào)量mutex，當(dāng)mutex＝1時(shí)表示（ ）。，另一個(gè)進(jìn)程等待 6. 設(shè)兩個(gè)進(jìn)程共用一個(gè)臨界資源的互斥信號(hào)量mutex，當(dāng)mutex＝1時(shí)表示（ ）。，另一個(gè)進(jìn)程等待 7．當(dāng)一進(jìn)程因在記錄型信號(hào)量S上執(zhí)行P(S)操作而被阻塞后，S的值為（ ）。 A.0 B.0 C.≥0 D.≤08．當(dāng)一進(jìn)程因在記錄型信號(hào)量S上執(zhí)行V(S)操作而導(dǎo)致喚醒另一進(jìn)程后，S的值為（ ）。 A.0 B.0 C.≥0 D.≤09．如果信號(hào)量的當(dāng)前值為4，則表示系統(tǒng)中在該信號(hào)量上有（ ）個(gè)進(jìn)程等待。 10．若有4個(gè)進(jìn)程共享同一程序段，而且每次最多允許3個(gè)進(jìn)程進(jìn)入該程序段，則信號(hào)量的變化范圍是（ ）。A. 3，2，1，0 B. 3，2，1，0，1C. 4，3，2，1，0 D. 2，1，0，1，211．若信號(hào)S的初值為2，當(dāng)前值為1，則表示有( )個(gè)等待進(jìn)程？ 12．如果有三個(gè)進(jìn)程共享同一互斥段，而且每次最多允許兩個(gè)進(jìn)程進(jìn)入該互斥段，則信號(hào)量的初值應(yīng)設(shè)置為（ ）。A. 3 B. 1 C. 2 D. 013．并發(fā)進(jìn)程之間（ ） 14．在操作系統(tǒng)中，有一組進(jìn)程，進(jìn)程之間具有直接相互制約性。這組并發(fā)進(jìn)程之間（ ）。 15. （ ）操作不是P操作可完成的。 選擇所有正確的答案1. 有關(guān)進(jìn)程的描述中，（ ）是正確的。. V操作可以交換大量信息，不可能出現(xiàn)與時(shí)間有關(guān)的錯(cuò)誤2. 下列資源中，( ) 是臨界資源。 3. 進(jìn)程從執(zhí)行狀態(tài)轉(zhuǎn)換到阻塞狀態(tài)的可能原因是( ). 4. 進(jìn)程從阻塞狀態(tài)轉(zhuǎn)換到就緒狀態(tài)的可能原因是( ).A. 時(shí)間片完 B. 其它進(jìn)程執(zhí)行了喚醒原語C. 執(zhí)行了V操作 D. 執(zhí)行了P操作，設(shè)系統(tǒng)中有n個(gè)進(jìn)程（n2）,且當(dāng)前處理機(jī)沒有執(zhí)行進(jìn)程調(diào)度程序，下述情況哪些可能發(fā)生（ ）。，有2個(gè)進(jìn)程處于就緒狀態(tài)，n個(gè)進(jìn)程處于等待狀態(tài)。 ，n1個(gè)進(jìn)程處于等待狀態(tài)。C. 一個(gè)進(jìn)程處于運(yùn)行狀態(tài)，1個(gè)進(jìn)程處于就緒狀態(tài)，n2個(gè)進(jìn)程處于等待狀態(tài)。D. 一個(gè)進(jìn)程處于運(yùn)行狀態(tài)，n1個(gè)進(jìn)程處于就緒狀態(tài)，沒有進(jìn)程處于等待狀態(tài) 判斷正誤，錯(cuò)誤的簡要說明理由1．一個(gè)臨界資源可以對(duì)應(yīng)多個(gè)臨界區(qū)。2．互斥地使用臨界資源是通過互斥地進(jìn)入臨界區(qū)實(shí)現(xiàn)的。3．同步信號(hào)量的初值一般為1。4．引入管程是為了讓系統(tǒng)自動(dòng)處理臨界資源的互斥使用問題。5．生產(chǎn)者－消費(fèi)者問題是一個(gè)既有同步又有互斥的問題。6．用管程實(shí)現(xiàn)進(jìn)程同步時(shí)，管程中的過程是不可中斷的。7．進(jìn)程A、B共享變量x，需要互斥執(zhí)行；進(jìn)程B、C共享變量y，B、C也需要互斥執(zhí)行，因此，進(jìn)程A、C必須互斥執(zhí)行。8. 單道程序系統(tǒng)中程序的執(zhí)行也需要同步和互斥。 簡答題1．為什么說互斥也是一種同步？2．為什么說進(jìn)程同步問題關(guān)系到OS的成?。?．同步機(jī)制應(yīng)遵循的準(zhǔn)則是什么？4．進(jìn)程通信有哪三種基本類型？5．簡述解互斥問題的軟、硬件方法的異同。6．什么是原語？它與廣義指令有什么區(qū)別？7．對(duì)臨界區(qū)管理的要求是什么？8．設(shè)有n個(gè)進(jìn)程共享一個(gè)互斥段，對(duì)于如下兩種情況使用信號(hào)量，信號(hào)量的值的變化怎樣？(1) 如果每次只允許一個(gè)進(jìn)程進(jìn)入互斥段；(2) 如果每次最多允許m個(gè)進(jìn)程（mn）同時(shí)進(jìn)入互斥段。1．在信號(hào)量機(jī)制中，若P(S)操作是可中斷的，則會(huì)有什么問題？2．試述引起多道程序系統(tǒng)程序執(zhí)行不確定性的內(nèi)部原因？3. 何謂臨界區(qū)？下面給出的兩個(gè)進(jìn)程互斥的算法是安全的嗎？為什么？define true。define false。int flag[2]。flag[1]=flag[2]=false。entercrtsec(i)int i。{while (flag[1i])flag[i]=true。}leavecrtsec(i)int i。{flag[i]=false。}process i:…entercrtsec(i)。In critical section。Leavecrtsec(i)。4．如何理解原語的原子性，在單機(jī)環(huán)境下如何實(shí)現(xiàn)原語的原子性，實(shí)現(xiàn)時(shí)應(yīng)注意哪些問題？5．當(dāng)進(jìn)程X和進(jìn)程Y共享某個(gè)資源r，進(jìn)程并發(fā)執(zhí)行時(shí)的程序如下：begin S:semaphore:=1。Cobegin Process X Begin L1:P(S)。 使用資源r。 V(S)。 Goto L1。 End。 Process Y Begin L2:P(S)。 使用資源r。 V(S)。 Goto L2。 End。Coend。End。請(qǐng)回答：(1) 兩個(gè)進(jìn)程并發(fā)執(zhí)行時(shí)，能否保證互斥地使用資源？為什么？(2) 如果要使兩個(gè)進(jìn)程交替使用資源，若仍使用P、V操作來進(jìn)行管理，寫出應(yīng)定義的信號(hào)量及其初值。(3) 修改上述程序，使兩個(gè)進(jìn)程能交替使用資源r。6．某車站售票廳，任何時(shí)刻最多可容納20名購票者進(jìn)入，當(dāng)售票廳中少于20購票者時(shí)，則廳外的購票者可立即進(jìn)入，否則需在外面等待。若把一個(gè)購票者看作一個(gè)進(jìn)程，請(qǐng)回答下列問題：(1) 用P、V操作管理這些并發(fā)進(jìn)程時(shí)，應(yīng)怎樣定義信號(hào)量？寫出信號(hào)量的初值以及信號(hào)量各種取值的含義。(2) 根據(jù)所定義的信號(hào)量，把應(yīng)執(zhí)行的P、V操作填入下述程序中，以保證進(jìn)程能夠正確地并發(fā)執(zhí)行。COBEGIN PROCESS Pi (i=1,2,…..) Begin 。 進(jìn)入售票廳 ； 購票； ； 退出； End。COEND（3）若欲購票者最多為n個(gè)人，寫出信號(hào)量可能的變化范圍（最大值和最小值）。7． 進(jìn)程之間存在哪幾種相互制約關(guān)系？各是什么原因引起的？下列活動(dòng)分別屬于哪種制約關(guān)系？（1）若干同學(xué)去圖書館借書；（2）兩隊(duì)舉行籃球比賽；（3）流水線生產(chǎn)的各道工序；（4）商品生產(chǎn)和社會(huì)消費(fèi)。8．設(shè)有兩個(gè)優(yōu)先級(jí)相同的進(jìn)程P1和P2如下。信號(hào)量S1和S2的初值均為0，試問PP2并發(fā)執(zhí)行結(jié)束后，x=?，y=?，z=?〈進(jìn)程P1〉 〈進(jìn)程P2〉 y:=1。 x:=1。y:=y+2。 x:=x+1。V(S1)。 P(S1)