當前位置：首頁 > 运维知识 > windows >内容正文

windows

（操作系统题目题型总结）第三章：同步与互斥

發布時間：2025/3/15 windows 13 豆豆

生活随笔收集整理的這篇文章主要介紹了（操作系统题目题型总结）第三章：同步与互斥小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

費翔林課本習題

思考題

1.試述順序程序設計的特點以及采用順序程序設計的優缺點

【答案】

特點：

執行的順序性：一個程序在處理器上是嚴格按序執行的，每個操作必須在下一個操作開始前結束
環境的封閉性：運行程序獨占全機資源，資源狀態只能由此程序本身決定，也不受到外界環境因素影響
結果的確定性：程序在執行過程中允許1出現中斷，但是這種中斷不會對程序最終結果產生影響，也就是說程序執行結果與他的執行速度無關
過程的可再現性：程序針對同一個數據結構的執行過程在下一次執行時會重現，也即重復執行程序會獲得相同搞得執行過程和計算結果

優點是程序的編址和調試很方便，但缺點就是計算機系統效率低下

2.試述并發程序設計的特點以及采用并發程序設計的優缺點（★★★）

【答案】

特點：程序的執行不再是順序的，一個程序未執行完而另一個程序便已經開始執行，程序外部的順序特性消失，程序與計算不再一一對應

優點

若為單處理器系統，可以有效利用資源，讓處理器和設備,設備和設備同時工作，充分發揮硬部件的并行工作能力
若為多處理器系統，可以讓進程在不同處理器上物理地并行工作，加快計算速度
簡化程序設計任務，一般來說，編制并發的小程序進度快，容易保證正確性

缺點

可能會出現各種與時間有關的錯誤，例如結果唯一或永遠等待

3.解釋并發與并行（★★★）

【答案】

并行性是指兩個或多個事件在同一時刻發生
并發性是指兩個或多個事件在同一時間間隔發生

在多道程序環境下，并發性是指在一段時間內宏觀上有多個程序在同時運行，但在單處理機系統中，每一時刻卻僅能有一道程序執行，故微觀上這些程序只能是分時地交替執行

4.解釋可再入程序與可再用程序

可再入程序：又稱為可重入程序，是指能被多個程序同時調用的程序，是純代碼，在執行過程中不被修改
可再用程序：在調用過程中可以自身修改，在調用它的程序退出之前是不允許其他程序來調用的

5.解釋并發進程的無關性和交互性（★★★）

【答案】

無關性：無關的并發進程是指它們分別在不同的變量集合上操作，一個進程的執行與其他并發進程的進展無關，也即一個進程不會改變另一個與其并發執行進程的變量
交互性：交互的并發進程共享某些變量，一個進程的執行可能會影響其他進程的執行結果，交互的并發進程之間具有制約關系

6.解釋進程的競爭與協作關系

【答案】

競爭關系：批處理系統中建立多個批處理進程，分時系統中建立多個交互式進程，它們共享一套計算機系統資源，使得原本不存在邏輯關系的諸進程因共享資源而產生了交互和制約關系，這是間接制約關系，又叫做互斥關系，操作系統必須協調對共享資源的爭用
協作關系：一個作業可涉及一組并發進程，它們為了完成共同任務需要分工協作，由于每個進程都獨立地以不可預知的速度推進，在執行的先后次序上就要有約束，需要相互協作的進程在某些關鍵點上協調各自的工作。當其中一個進程到達關鍵點后，在尚未得到其伙伴進程發來的消息或信號之前應該阻塞自己，等待協作者發來信號或消息后方被喚醒并繼續執行。這種協作進程之間需要排定執行先后次序的協調關系是直接制約關系，稱為進程同步

7.試述進程的互斥與同步兩個概念之間的異同（★★★）

【答案】

進程同步：進程同步又叫做直接制約關系，它是指為完成某種任務而建立的兩個或多個進程，這些進程因為需要在某些位置上協調工作次序而產生一種制約關系
進程互斥：進程互斥叫做間接制約關系，它是指當一個進程訪問某臨界資源時，另一個想要訪問該臨界資源的進程必須等待。當前訪問臨界資源的進程訪問結束后，并釋放資源后，另一個進程才可以訪問

8.什么是臨界區和臨界資源？臨界區管理的基本原則是什么（★★★）

【答案】

臨界區：并發進程中與共享變量有關的程序段稱為臨界區
臨界資源：共享變量所代表的資源稱為臨界資源

四個原則

空閑讓進：臨界區空閑時，可以允許一個請求進入臨界區的進程立即進入臨界區
忙則等待：當已有進程進入臨界區時，其他試圖進入臨界區的進程必須等待
有限等待：對請求訪問的進程，應該保證能在有限時間內進入臨界區，也就是不能饑餓
讓權等待：當進程不能進入臨界區時，應該立即釋放處理機，防止進程處于忙等待狀態

11.試述Deek而算法實現臨界區互斥的原理

算法思想：該算法會設置一個布爾型的數組flag[]，用于標記各進程是否想要進入臨界區，比如"flag[0]=true"表示0號進程 $P_{0}$ 現在想要進入臨界區。每個進程在進入臨界區之前先檢查當前有沒有別的進程想進入臨界區，如果沒有則把自身對應的標志設置為true，之后開始訪問臨界區

具體實施：設置一個布爾型的數組flag[]，開始時均設置為flase，表示都不想進入臨界區，以分析 $P_{1}$ 為例

開始， $P_{1}$ 進程會檢查 $P_{0}$ 進程是否想要進入臨界區，如果flag[0]=true，那么 $P_{1}$ 就會被卡住
如果flag[0]=false，表示 $P_{1}$ 此時確認 $P_{0}$ 不想進入臨界區，那么它就不會被卡住。然后它進入臨界區之前，會被自己的flag[1]設置為true，向其他進程表明自己想要進入臨界區
臨界區訪問完畢之后，設置flag[1]=false

算法缺陷：違背了“忙則等待”原則。因為在這種算法下，兩個進程是并發的，并發導致異步，意味著兩個進程可能會同時訪問臨界區

10.試述Peterson算法實現臨界區互斥的原理

算法思想：為了防止兩個進程為了進入臨界區而無限期等待，又設置了一個變量turn，每個進程先設置自己的標志后再設置turn標志，再同時檢測另一個進程狀態標志和不允許進入標志，以保證兩個進程同時要求進入臨界區時，只允許一個進程進入臨界區

具體實施：以分析對于 $P_{1}$ 進程為例：

flag[1]=true表示 $P_{1}$ 想要進入臨界區，然后turn=0，是一種“謙讓操作”，表示可以優先讓 $P_{0}$ 進入臨界區
此時如果 $P_{0}$ 已經在臨界區，那么 $P_{1}$ while循環滿足，就會被卡住；如果 $P_{0}$ 不想進入臨界區，那么肯定有 $P_{0}$ 的flag[0]=flase, $P_{1}$ 就不會被卡住

算法優點：遵循了空閑讓進、忙則等待、有限等待這三個原則

算法缺陷：相較于前三種算法來說，是比較好的，但是還是有缺陷，未能遵循讓權等待的原則。因為在上面的那個例子中，即便 $P_{1}$ 不能進入臨界區，它還是會卡在while循環，不能釋放處理機，使處理機處于了忙等狀態

11.哪些硬件設施可以實現臨界區管理？簡述其用法

【答案】

①：中斷屏蔽方法
思想：當一個進程正在使用處理機執行它的臨界區代碼時，為了防止其他進程進入臨界區進行訪問的，直接“暴力的”禁止一切中斷發生，或稱之為屏蔽中斷、關中斷。因為CPU只在發生中斷時引起進程切換

優缺點

優點： 簡單、高效
缺點： 不適用于多處理機，限制了處理機交替執行程序的能力，因此執行的效率會明顯降低；且只適用于內核進程，不適用于用戶進程（因為開關中斷指令屬于特權指令）

②：TestAndSet指令(TSL)
思想：可以為每個臨界資源設置一個共享布爾變量lock，lock=true表示正在被占用，初值設為false。在進程訪問臨界資源之前，利用TestAndSet檢查和修改標志lock，如果有進程在臨界區，則重復檢查，直到進程退出。大致邏輯如下

while TestAndSet(&lock);//上鎖檢查 //臨界區代碼段 lock=false;//解鎖、退出區 //剩余區代碼段

TestAndSet指令：這是一個原子操作，執行過程中絕對不會被中斷，使用硬件實現。其功能是讀出指令標志后把該標志設為true。以下是功能描述

bool TestAndSet(bool* lock) {bool old;//用于存放*lock原來的值old=*lock;*lock=true;//無論是否加鎖，一律設為truereturn old;//返回lock原來的值 }

具體過程

如果剛開始lock=false，則TSL返回的old就是false，while條件不滿足，直接進入臨界區
如果剛開始lock=true，則TSL返回的old就是true,while條件滿足，會一直循環，直到當前訪問臨界區的進程在退出區進行解鎖

優缺點

優點： 相比軟件方法，TSL把上鎖和檢查操作使用硬件的方式編程了原子操作。所以實現簡單，不會像軟件實現那樣產生邏輯漏洞
缺點： 不滿足讓權等待 ，暫時無法進入臨界區的進程會占用CPU并循環執行TSL，使CPU忙等

③：swap指令（exchange）
能不能完成原子操作可以看其匯編指令，比如++i這就不是原子操作，因為它需要三條匯編指令，需要經過加載-運算-放回操作

思想：可以為每個臨界資源設置一個共享布爾變量lock，lock=true表示正在被占用，初值設為false；然后在每個進程中再設置一個局部變量key，用于和lock交換信息。在進入臨界區之前，先利用swap指令交換lock與key的內容，然后檢查key的狀態，有進程在臨界區時，重復交換和檢查過程，直到進程退出。大致邏輯如下

key=true; while(key!=false)swap(&lock,&key); //臨界區代碼段 lock=false; //剩余區代碼段

swap指令：該指令用于交換兩個字的內容，使用硬件實現。屬于原子操作，其對應的匯編指令如下

xchgb %al,mutex

王道書上給出了C語言描述，但是我覺得不好，這是原子性操作，那種代碼感覺似乎需要三個步驟一樣，直接看匯編即可。其中al和mutex是寄存器

具體過程

如果剛開始臨界區就已經被上鎖，那么先將其記錄在key上，也即key=true，那么此時while循環條件滿足，一直執行swap，直到此時處在臨界區的進程退出時將lock設為false，交換給key，然后結束循環
如果剛開始臨界區沒有被上鎖，那么先將其記錄在key上，也即key=false，那么此時while循環條件不滿足，直接進入臨界區

優缺點

優點：實現簡單，不會像軟件實現那樣產生邏輯漏洞，適用于多處理機環境
缺點：不滿足讓權等待 ，暫時無法進入臨界區的進程會占用CPU并循環執行TSL，使CPU忙等

12.什么是信號量？如何對其分類（★★★）

【答案】

1965年，荷蘭計算機科學家E. W. Djkstra提出新的同步工具一信號量和PV提作，他將交通管制中多種顏色的信號燈管理方法引人操作系統，讓多個進程通過特殊變
量展開交互。一個進程在某一關鍵點上被迫停止執行直至接收到對應的特殊變量值，通過這一措施，任何復雜的進程交互要求均可得到滿足，這種特殊變量就是信號量( semaphore)。為了通過信號量傳送信號,進程可利用P和V兩個特殊操作來發送和接收信號，如果協作進程的相應信號仍未送到，則進程被掛起直至信號到達為止。在操作系統中用信號量表示物理資源的實體，它是一個與隊列有關的整型變量。具體實現時，信號量是一種變量類型，用一個記錄型數據結構表示，有兩個分量：一個是信號量的值,另一個是信號量隊列指針。信號量在操作系統中主要用于封鎖臨界區、進程同步及維護資源計數。除了賦初值之外,信號量僅能由同步原語PV對其進行操作，不存在其他方法可以檢查或操作信號量,PV操作的不可分割性確保執行時的原子性及信號量值的完整性。Dijkstra 發明信號量操作原語:P和V操作(荷蘭語中“檢測”(Pro-beren)和“增量”( Verhogen)的首字母)，常用的符號還有up和down等。利用信號量和PV操作既可解決并發進程競爭問題，又可解決并發進程協作問題

按其用途分類：

公用信號量：聯系一組并發進程，相關進程均可在此信號量上執行PV操作，初值為1，用于實現進程互斥
私有信號量：聯系一組并發進程，僅允許信號量所用的進程執行P操作，而其他相關進程可在其上執行V操作，初值往往為0或正整數，多用于并發進程同步

按其取值分類：

二值信號量：僅允許取值為0或1，主要用于解決進程互斥問題
一般信號量：允許取大于1的數值，主要用于解決進程同步問題

PV操作

P操作（wait(S)原語）：這個操作會把信號量減去1，相減后如果信號量<0則表示資源已經被占用，進程需要阻塞；相減后如果信號量 $≥0\ge0$ ，則表明還有資源可以使用，進程可以正常執行
V操作（signal(S)原語）：這個操作會把信號量加上1，相加后如果信號量 $≤0\le0$ ，則表明當前有阻塞中的進程，于是會把該進程喚醒；相加后如果信號量>0，則表明當前沒有阻塞中的進程

13.為什么PV操作均為不可分割的原語操作

【答案】

因為他們被定義為了如下數據結構和不可中斷過程（以記錄型信號量為例）

typedef struct semaphore {int value;//信號量值struct pcb* list;//信號量隊列指針 }void P(semapore s) {s.value--;if(s.vaue < 0)sleep(s.list); } void V(semaphore s) {s.value++;if(s.value <= 0)wakeup(s.list); }

14.何為管程？它有哪些屬性（★★★）

【答案】

管程(Monitor)：它是一種特殊的軟件模塊，由以下部分組成

局部于管程的共享數據結構說明——可以理解為類的成員
對該數據結構進行操作的一組過程(函數)——可以理解為類的方法
對局部于管程的數據設置初始值的語句——可以理解為類的構造函數
管程有一個名字——可以理解為類名

所以，管程是一個代表共享資源的數據結構，進程對共享資源的申請、釋放等操作是通過過程來實現的（過程就是對這一數據結構的操作），這組過程還可以根據資源情況，或接受或阻塞進程的訪問，確保每次僅有一個進程使用共享資源，這樣就可以統一管理對共享資源的所有訪問，實現進程互斥，即：

monitor Test//定義了一個名稱為"Test"的管程 {Data Structure DS;//定義共享數據結構，對應系統中的某種共享資源Init_Code()//對共享數據結構初始化語言{DS=5;//初始資源數目為5}Take_Away()//過程1：申請一個資源{對共享數據結構的一系列操作DS--;//可用資源數目減一...}Give_Back()//過程2：歸還一個資源{對共享數據結構的一系列操作DS++;//可用資源數目加一...} }

管程基本特征：

共享性：管程中的移出過程可被所有要調用管程的過程的進程所共享
安全性：管程的局部變量只能由此管程的過程訪問，不允許進程或其他管程來直接訪問，一個管程的過程也不應該訪問任何非局部于它的變量
互斥性：在任一時刻，共享資源的進程可以訪問管程中的管理此資源的過程，但最多只有一個調用者能夠真正進入管程，其他調用者必須等待直至管程可用

15.試述管程中條件變量的含義和作用（★★★）

【答案】

當一個進程進入管程后被阻塞，直到阻塞的原因解除時，在此期間，如果該進程不釋放管程，那么其他進程無法進入管程，為此，將阻塞原因定義為條件變量condition

如果一個進程被阻塞的原因有多個，那么就設置多個條件變量，而每一個條件變量保存了一個等待隊列，用于記錄因該條件變量而阻塞的所有進程，對于條件變量的操作只有兩種：wait和signal

x.wait：當x對應的條件不滿足時，正在調用管程的進程調用x.wait將自己插入x條件的等待隊列，并釋放管程。此時其他進程可以使用該管程
x.signal：當x對應的條件發生了變化，則調用x.signal，喚醒一個因x條件而阻塞的進程

邏輯描述如下

monitor Test() {Data Structure DS;//定義共享數據結構，對應系統中的某種共享資源condition x;//定義了一個條件變量xInit_Code(){...}Take_Away(){if(DS<=0){x.wait();//資源不夠，在條件變量x上阻塞的大概}資源足夠，分配資源，做一系列相應處理}Give_Back(){歸還資源，做一系列相應處理if(進程在等待)x.sginal();//喚醒一個阻塞進程} }

可以看出：相較于信號量，條件變量或者管程把具體的同步互斥關系實現封裝了起來，只暴露兩個特別簡單的接口以供程序員調用，而這兩個接口其反應的本質問題就是資源是否存在，能否互斥訪問的問題，程序員不用關心復雜的同步互斥關系，只關心在相應的程序邏輯下資源數目的問題

16.試比較管程與進程

【答案】

管程所定義的是公用數據結構，而進程定義的是私有數據結構
管程把共享變量上的同步操作集中在一起統一管理，而臨界區卻分散在每個進程中
管程是為了解決進程共享資源的互斥而建立的，而進程是為了占有系統資源和實現系統并發性而引入的
管程被欲使用的共享資源的所有進程所調用，管程和調用它的進程不能并行工作；而進程之間可以并行工作
管程可以作為語言或操作系統部分，不必創建或撤銷；進程有其生命周期

17.為什么引入進程通信

【答案】

并發進程之間的交互必須滿足兩個基本要求:同步和通信。進程同步本質上是一種僅傳送信號的進程通信，通過修改信號量，進程之間可以建立聯系，相互協調運行和協同工作,但它缺乏傳遞數據的能力。在多任務系統中，可由多個進程分工協作完成同一任務,于是它們需要共享一些數據和相互交換信息，某些情況下交換的信息量很少，但在很多場合需要交換大批數據，可以通過通信機制來完成。進程之間互相交換信息的工作稱為進程通信( Inter - Process Communication,IPC) ,線程通信是從進程通信演變而來,由于可區分單線程結構進程和多線程結構進程,進程通信實質上就是進程中的線程之間的通信。通信方式有很多，包括信號(signal)通信機制，管道( pipeline)通信機

18.試述信件、信箱和間接通信原語

【答案】

19.什么是管道？如何通過管道機制實現進程間通信（★★★）

【答案】

管道是連接讀寫進程的一個特殊文件，允許按照FIFO方式傳送數據，也能使進程同步執行。管道是單向的，發送進程視管道文件為輸出文件，以字符流的形式把大量數據送入管道；接受進程視管道文件為輸入文件，從管道中接受數據，所以也稱為管道通信

20.試述進程的低級通信工具和高級通信工具（★★★）

【答案】

21.什么是死鎖（★★★）

【答案】

死鎖：所謂死鎖，是指多個進程因競爭資源而造成的一種互相等待的局面，若無外力作用，這些進程將無法向前推進

專業定義：如果一個進程集合中的每個進程都在等待只能由此集合中的其他進程才能引發的事件，而無限期陷入僵持的局面稱之為死鎖

生活中死鎖的例子：我拿了你房間的鑰匙，而我在自己的房間；你拿了我的房間的鑰匙，而你又在自己的房間。如果我要從自己的房間走出去，必須要拿到你手中的鑰匙，但是你要走出來又必須要拿到我手中的鑰匙，于是形成了死鎖

22.試述死鎖產生的必要條件

【答案】

①：互斥條件
互斥條件：是指只有對必須互斥使用的資源搶奪時才可能導致死鎖。比如打印機設備就可能導致互斥，但是像內存、揚聲器則不會

進程A已經獲得資源，進程B只能等待

②：不可剝奪條件

不可剝奪條件：是指進程所獲得的資源在未使用完之前，不能由其他進程強行奪走，只能主動釋放

③：持有并等待條件
持有并等待條件：是指進程已經至少保持了一個資源，但又提出了新的資源請求，但是該資源又被其他進程占有，此時請求進程被阻塞，但是對自己持有的資源保持不放

④：循環等待條件

循環剝奪條件：是指存在一種進程資源的循環等待鏈，鏈中的每一個進程已獲得的資源同時被下一個進程所請求

23.列舉死鎖的各種防止策略

【答案】

死鎖處理策略：主要分為以下三種

預防死鎖：破壞死鎖產生的四個必要條件中的一個或幾個
避免死鎖：用某種方法防止系統進入不安全狀態，從而避免死鎖。例如銀行家算法
死鎖的檢測和解除：允許死鎖產生，不過操作系統會負責檢測出死鎖的發生，然后采取某種措施解決死鎖

應用題

1.如何用信號量實現互斥操作

【答案】

思想：

1：分析并發進程的關鍵活動，劃定臨界區
2：設置互斥信號量mutex，初值1
3：在臨界區之前執行P操作
3：在臨界區之后執行V操作

具體描述：

可用如下描述大致邏輯，有兩個進程 $P_{1}$ 和 $P_{2}$

semaphore mutex=1;//互斥信號量 P1() {//其他代碼P(mutex);//進入臨界區前加鎖臨界區代碼V(mutex);//退出臨界區時要解鎖}P1() {//其他代碼P(mutex);//進入臨界區前加鎖臨界區代碼V(mutex);//退出臨界區時要解鎖}

進程 $P_{1}$ 在訪問臨界資源前，先執行了 $P$ 操作，由于信號量初值mutex=1，所以 $P_{1}$ 在執行完 $P$ 操作后mutex變為0， $P_{1}$ 訪問臨界資源
此時進程 $P_{2}$ 也想要訪問臨界資源，執行 $P$ 操作后，其mutex變為了-1，表明系統中已經沒有可以分配的資源，所以執行block原語，被阻塞
$P_{1}$ 訪問完臨界資源后，執行 $V$ 操作，信號量恢復，即mutex=0，然后使用wakeup原語喚醒阻塞中 $P_{2}$ ，并將資源分配給它
$P_{2}$ 訪問完成之后，執行 $V$ 操作，使信號量恢復至初值，即mutex=1

注意：
1：對不同的臨界資源需要設置不同的互斥信號量。例如 $P_{1}$ 和 $P_{2}$ 進程爭搶A這種資源，那么就可以設置互斥信號量為mutex1， $P_{3}$ 和 $P_{4}$ 進程爭搶B這種資源，那么就可以設置互斥信號量為mutex2

semaphore mutex1=1; semaphore mutex2=1;

2：一定注意P、V操作必須成對出現

缺少P操作： 不能保證臨界資源的互斥訪問
缺少V操作： 導致資源永遠不會釋放，繼而等待進程永遠不會被喚醒

2.如何用信號量實現同步操作

【答案】

思想：

1：分析什么地方需要實現同步關系，也即必須保證一前一后執行的兩個操作（或代碼）
2：設置同步信號量S，初值0
3：在必須要先執行的操作（代碼）之后執行V操作
4：在必須要后執行的操作（代碼）之前執行P操作

具體描述：

可用如下描述大致邏輯，有兩個進程 $P_{1}$ 和 $P_{2}$ 。其中代碼4要執行必須保證代碼1和代碼2先執行完畢，因此V操作在代碼1、2后面執行；同樣代碼1和代碼2執行完畢之后才能執行代碼4，因此P操作要在代碼4之前?？傮w上看 $P_{1}$ 一定要先于 $P_{2}$ 運行

semphore S=0;//同步信號量P1() {代碼1；代碼2V(S);代碼3; }P2() {P(S);代碼4；代碼5代碼6; }

如果先執行了P操作，那么表明此時 $P_{2}$ 先于 $P_{1}$ 執行（這不是我們期望的順序）。此時，由于S=0，P操作后S=-1，所以 $P_{2}$ 就會執行block原語進行阻塞。當 $P_{1}$ 的代碼2執行完之后，就會執行V操作，此時S++，所以S=0，所以 $P_{1}$ 就會執行wakeup原語，喚醒 $P_{2}$ 進程，這樣 $P_{2}$ 就可以繼續執行代碼4了。滿了同步
如果先執行了V操作，那么表明此時 $P_{1}$ 先于 $P_{2}$ 執行（這正是我們期望的順序），于是S++，S=1，當 $P_{2}$ 執行P操作時，由于S=1，也即有可用資源就會使S–，也即S=0，所以 $P_{2}$ 不會執行block原語，而是繼續向下執行代碼4

3.如何用信號量實現前驅關系

【答案】

所謂前驅關系就是要實現多組進程的同步關系，如下

$P_{1}$ 中有一句代碼S1
$P_{2}$ 中有一句代碼S2
$P_{3}$ 中有一句代碼S3
$P_{4}$ 中有一句代碼S4
$P_{5}$ 中有一句代碼S5
$P_{6}$ 中有一句代碼S6

這些代碼需要按照如下前驅圖所規定的順序執行

思想：

1：要為每一對前驅關系各設置一個同步變量
2：在必須要先執行的操作（代碼）之后對相應的同步變量執行V操作
3：在必須要后執行的操作（代碼）之前對相應的同步變量執行P操作

具體描述：

可用如下描述大致邏輯，有六個進程 $P_{1}$ ~ $P_{6}$ 。

P1() {...S1;V(a);V(b);... } P2() {...P(a);S2;V(c);V(d);... } P3() {...P(b);S3;V(g);... } P4() {...P(c);S4;V(e);... } P5() {...P(d);S5;V(f);... } P6() {...P(e);P(f);P(g);S6;... }

4.用信號量解決生產者與消費者問題

【答案】

實現同步

生產者：將產品放入緩沖區前需要執行P(empty)以消耗一個空閑緩沖區；放入緩沖區之后需要執行V(full)以增加一個產品數量
消費者：從緩沖區取出產品之前需要執行P(full)以消耗一個產品；從緩沖區取出產品之后需要執行V(empty)以增加一個空閑緩沖區

實現互斥

生產者：將產品放入緩沖區前需要執行P(mutex)；放入緩沖區之后需要執行V(mutex)
消費者：從緩沖區取出產品之前需要執行P(mutex)；從緩沖區取出產品之后V(mutex)

因此代碼如下

semaphore mutex=1;互斥信號量，實現對緩沖區的互斥訪問 semaphore empty=n;同步信號量，表示空閑緩沖區數量 semaphore full=0;同步信號量，表示非空閑緩沖區數量，也就是產品數量Producer() {while(1){//生產者生產數據p(empty);要用什么，P一下 //獲取空緩沖區p(mutex)：互斥夾緊//將數據放入緩沖區V(mutex)：互斥夾緊V(full)：提供什么，V一下 //產品數量增加} }Producer() {while(1){p(full);要用什么，P一下 //獲取產品p(mutex)：互斥夾緊//消費者取出產品V(mutex)：互斥夾緊V(empty)：提供什么，V一下 //空緩沖區增加//消費者使用數據}}

多生產者多消費者問題

【答案】

semaphore plate=1;//盤子中還可以放多少個水果 semaphore apple=0;//盤子中有幾個蘋果 semaphore orange=0;//盤子中有幾個句子dad() {while(1){準備一個蘋果；P(plate);//互斥放水果向盤子中放蘋果；V(apple);//可以取蘋果 } } mom() {while(1){準備一個橘子；P(plate);//互斥放水果向盤子中放橘子；V(orange);//允許取橘子 } }son() {while(1){P(orange);//互斥從盤子中取橘子取橘子V(plate);//取完歸還盤子吃橘子} }daughter() {while(1){P(apple);//互斥從盤子中取蘋果取蘋果V(plate);//取完歸還盤子吃蘋果} }

6.讀者寫者問題、

【答案】

關系分析：找出題目中描述的各個進程，分析它們之間的同步、互斥關系

互斥關系：寫進程與寫進程；寫進程與讀進程
同步關系：桌子上有組合一/二/三時，第一/二/三個抽煙者取走東西，這是三個同步關系；還有抽煙者抽完煙之后要發出完成信號，這是第四個同步關系

整理思路：根據各進程的操作流程確定P、V操作的大致順序

對于寫者來說，它與任何進程都是互斥的，因此可以設置一個互斥信號量rw，在寫者訪問共享文件前后分別執行P、V操作
對于讀者進程，如果它也像前面那樣，那么就不符合讀者進程可以同時訪問文件的要求了。既然各個讀進程需要同時訪問，而讀進程與寫進程又必須互斥訪問，所以我們可以讓第一個訪問文件的讀進程“加鎖”，也就是P操作，然后讓最后一個訪問完文件的讀進程進行解鎖，也就是V操作。所以可以設置一個整形變量count來記錄當前有幾個讀進程在訪問文件
對于讀進程來說，在某一時刻多個讀進程并發執行。而我們對count變量的判斷是無法實現原子性操作的，所以這里count就是一種臨界資源了，需要對其進行保護，可以設置互斥信號量mutex

設置信號量：設置需要的信號量，并根據題目條件確定信號量初值

設置信號量count為計數器，用于記錄當前讀者的數量，初值為0；
設置mutex為互斥信號量，用于保護更新count變量時的互斥；
設置互斥信號量rw，用于保證讀者和寫者的互斥訪問

int count=0; semaphore mutex=1; semaphore rw=1;

對于寫者，在寫文件之前進行P操作，寫完之后進行V操作，就可以實現寫者與其他進程的互斥

writer() {while(1){P(rw);//寫之前加鎖寫文件;V(rw);//寫之后解鎖} }

對于讀者，第一個讀者進入會加鎖，最后一個讀者退出時進行解鎖

reader() {while(1){P(mutex);//使用P操作保護count，防止多個讀進程對臨界資源的操作if(count==0)P(rw);//第一個讀進程count++;V(mutex);讀文件;P(mutex);count--;if(count==0)V(rw);//最后一個讀進程V(mutex);} }

但是上面代碼還存在一個bug：讀進程是優先，只要有讀進程在讀，寫進程就會一直被阻塞，寫進程餓死。

所以如果希望寫進程優先，也就是說當有讀進程在讀時，若有寫進程請求訪問，那么應該禁止后續讀進程請求，等到本次讀進程完畢之后，立即讓寫進程執行，只有在無寫進程的情況下才允許讀進程再次運行。因此可以再增設一個信號量w，用于實現寫優先

int count=0; semaphore mutex=1; semaphore rw=1; semaphore w=1;//用于實現寫優先writer() {while(1){P(w);P(rw);//寫之前加鎖寫文件;V(rw);//寫之后解鎖V(w);} }reader() {while(1){p(w);//在無寫進程的情況下進入P(mutex);//使用P操作保護count，防止多個讀進程對臨界資源的操作if(count==0)P(rw);//第一個讀進程count++;V(mutex);V(w);寫文件;P(mutex);count--;if(count==0)V(rw);//最后一個讀進程V(mutex);} }

7.吸煙者問題（單生產者多消費者問題）

【答案】

semaphore offer1=0;//組合一的數量 semaphore offer2=0;//組合二的數量 semaphore offer3=0;//組合三的數量 semaphore finish=0;//抽煙是否完成 int i=0;//用于實現輪流抽煙

對于生產者，其內部進行邏輯判斷，利用取余的方式輪流放置組合一、二和三，放置完成之后如果消費者不執行V(finish)，它將會在P(finish)處被阻塞

provider {while(1){if(i==0){組合一放桌子上V(offer1);}else if(i==1){組合二放桌子上V(offer2);}else if(i==2){組合三放桌子上V(offer3);}i=(i+1)%3;P(finish);} }

對于這三個消費者，他們各自在進入時首先會檢查是否有自己的組合，如果沒有將會被阻塞，如果有，執行完畢之后使用V(finish)通知生產者生產

smoker1() {while(1){P(Offer1);一系列卷煙、抽煙操作、拿走組合一V(finish);} } smoker2() {while(1){P(Offer2);一系列卷煙、抽煙操作、拿走組合二V(finish);} }smoker3() {while(1){P(Offer3);一系列卷煙、抽煙操作、拿走組合三V(finish);} }

8.哲學家進餐問題

【答案】

semaphore chopsticks[5]={1,1,1,1,1}; semaphore mutex=1;//取筷子信號量 P i()//i號哲學家進程 {while(1){P(mutex)：P(chopsticks[i]);//拿左P(chopsticks[i+1]%5);//拿右V(mutex);吃飯V(chopsticks[i]);//拿左V(chopsticks[i+1]%5);//拿右思考}}

【答案】

（1）解:在汽車行駛過程中,司機活動與售票員活動之間的同步關系為：售票員關車門后，向司機發開車信號,司機接到開車信號后啟動車輛,在汽車正常行駛過程中售票員售票,到站時司機停車,售票員在車停后開車門讓乘客.上下車。因此司機啟動車輛的動作必須與售票員關車門的動作取得同步；售票員開車門的動作也必須與司機停車取得同步

int s1=0;//表示是否允許司機啟動車輛 int s2=0;//表示是否允許售票員開門driver() {P(S1);啟動車輛正常行車到站停車V(S2); }Conductor() {關車門V(S1)售票 P(S2);開車門}

總結

以上是生活随笔為你收集整理的（操作系统题目题型总结）第三章：同步与互斥的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： mysqldump表损坏问题
下一篇： PHP-四种解析XML文件的方法