1同步與互斥

同步就是先V後P，互斥就是先P後V。
三個進程P1，P2，P3互斥使用一個包含N（N>0）個單元的緩衝區。P1每次使用produce()生成一個正整數並用put()送入緩衝區某一空單元；P2每次用getodd()從該緩衝區中取出一個奇數並用countodd()統計奇數個數；P3每次用geteven()從該緩衝區中取出一個偶數並用conuteven()統計偶數個數。請用信號量機制實現這3個進程得同步與互斥活動，並說明所定義的信號量的含義。
首先本題中有兩個緩衝區，第二個緩衝區是P1,P2,P3互斥訪問的，因此信號量初值只能爲1。
此外進程P1,P2,P3還需要實現同步，就是說P1先生成數並放入緩衝區，P2或P3才能從緩衝區中取數，因爲同步是先V後P，因此信號量初值設置爲0。
綜合上述，標準答案是這樣的
做這種題有幾個要點，第一是信號量的設置要正確，是同步信號量還是互斥信號量要弄明白，二是題目中的函數要出現在代碼中。

semaphore mutex = 1;//緩衝區操作互斥信號量
semaphore odd = 0,even = 0;//奇數，偶數進程的同步信號量
semaphore empty = N;//空緩衝區單元個數信號量
cobegin{
 Process P1()
 while(True)
 {
  x = produce();//生成一個數
  P(empty);
  P(mutex);
  put();
  V(mutex);//釋放緩衝區
  if(x%2==0)
   V(even);//若是偶數，向P3發出信號
  else
   V(odd)；
 }
 Process P2()
 while(True)
 {
  P(odd);
  P(mutex);
  getodd();
  V(mutex);
  V(empty);
  countodd();
 }
 Process P3()
 while(True)
 {
  P(even);
  P(mutex);
  geteven();
  V(mutex);
  V(empty);
  counteven();
 }
}coend

2 在一個倉庫中可以存放A和B兩種產品，要求：

（1）每次只能存入一種產品。
（2）A產品數量-B產品數量<M。
（3）B產品數量-A產品數量<N。
其實這道題給我整懵逼了，設互斥信號量mutex我會，但A和B的信號量怎麼設置呢？
因爲A和B都是變量，兩個變量交互在一起，我感覺十分的頭大，這時候就要利用極限的思想。如果倉庫只存放A產品呢？如果倉庫只存放B產品呢？
如果倉庫只存放A產品，那麼它的最大值就是M-1，同理，只存放B產品，最大值就是N-1。因爲A和B之間有這種約束關係，所以它們應該是同步信號量。
在存入A產品的時候，首先進行P操作，看允不允許往倉庫中放入A，放完A之後，基於A和B之間的約束關係，相比於之前，B可以多放一個，大概就是
這樣的。

Semaphore Sa=M-1,Sb=N-1;//分別代表產品A和B還可容納的數量差，以及B和A的數量差。
Semaphore mutex = 1;//訪問倉庫的互斥信號量
rocess_A()
{
 while(True){
  	P(Sa);
  	P(mutex);
  	A產品入庫;
  	V(mutex);
  	V(Sb);
}
process_B()
{
 while(True){
  	P(Sb);
  	P(mutex);
  	B產品入庫;
  	V(mutex);
  	V(Sa);
}

3麪包師有很多面包，由n名銷售人員推銷。每名顧客進店後取一個號，並且等待叫號，當一名銷售人員空閒後，就叫下一個號。試設計一個使銷售人員和顧客同步的算法。

int i=0,j=0;
semaphore mutex_i=1;mutex_j=1;
Consumer(){
 進入麪包店;
 P(mutex_i);
 取號i;
 i++;
 V(mutex_i);
 等待叫號i併購買麪包;
}
Seller()
{
	while(True){
  		P(mutex_j);
  		if(j<=i){
  			叫號j;
   			j++；
   			V(mutex_j);
   			銷售麪包;
   		}
  		else{
  			V(mutex_j);
  			休息片刻;
  			}
  		}
}

4某博物館最多可容納500人同時參觀，有一個出入口，該出入口一次僅允許一人通過。參觀者的活動描述如下：

cobegin
	參觀者進程i;
	{
		…………
		進門;
		…………
		參觀;
		…………
		出門;
		……………
	}
coend

請添加必要的信號量和P，V[或wait(),aignal()]操作，以實現上述過程中的互斥與同步。
要求寫出完整的過程，說明信號量的含義並賦初值。

出入口一次僅允許一個人通過，設置互斥信號量mutex，初值爲1.博物館最多可同時容納500人，因此設置信號量empty，初值爲500。

Semaphore empty = 500;//博物館可以容納的最多人數
Semaphore mutex = 1;//用於出入口資源的控制
cobegin
參觀者進程i:
{
	……
	P(empty);//可容納人數-1
	P(mutex);//互斥使用門
	進門;
	V(mutex);
	參觀;
	P(mutex);//互斥使用門
	出門;
	V(mutex);
	V(empty);//可容納人數+1
	……
}

5某工廠有兩個生產車間和一個裝配車間，兩個生產車間分別生產A,B兩種零件，裝配車間的任務是把A，B兩種零件組裝成產品。兩個車間每生產一個零件後，都要分別把它們送到專配車間的貨架F1，F2上。F1存放零件A，F2存放零件B，F1和F2的容量均可存放10個零件。裝配工人每次從貨架上取一個零件A和一個零件B後組裝成產品。用PV操作正確管理。

我發現做這種題，最重要的就是找準約束關係
（1）F1和F2的容量爲10
（2）必須先放零件再取零件
這是我之前發現的約束關係，但我還忘了一個
生產車間要訪問貨架，裝配工人也要訪問貨架，他倆總不能同時訪問貨架吧，他倆得互斥訪問，我錯就錯在這個地方。

本題需要設置6個信號量：
empty1對應貨架F1上的空閒空間，初值爲10，empty2對應貨架F2上的空閒空間，初值爲10；
full1對應貨架F1上的A產品，初值爲0，full2對應貨架F2上的B產品，初值爲0；
mutex1用於互斥地訪問貨架F1，mutex2用於互斥地訪問貨架F2。
process_A
while(True){
	生產一個產品A;
	P(empty1);//判斷貨架F1是否有空
	P(mutex1);//互斥訪問貨架F1
	將產品A存放到貨架F1上;
	V(mutex1);
	V(full1);
}
process_B
while(True){
	生產一個產品B;
 	P(empty2);//判斷貨架F2是否有空
 	P(mutex2);//互斥訪問貨架F2
 	將產品B存放到貨架F2上;
 	V(mutex2);
 	V(full2);
 }
 assemble
 while(True){
 	P(full1);//判斷貨架F1上是否有產品A
 	P(mutex1);//互斥訪問貨架F1
 	從貨架F1上取一個A產品;
 	V(mutex1);//釋放貨架F1
 	V(empty1);貨架F1上的空閒空間數+1
 	P(full2);//判斷貨架F2上是否有產品B
	P(mutex2);//互斥訪問貨架F2
  	從貨架F2上取一個B產品;
  	V(mutex2);//釋放貨架F2
  	V(empty2);貨架F2上的空閒空間數+1
  	將取得的A產品和B產品組裝成產品
}

6某寺廟有小和尚，老和尚若干，有一水缸，由老和尚提水入缸供老和尚飲用。水缸可容10桶水，水取自同一井中。水井徑窄，每次只能容納一個桶取水。水桶總數爲3個。每次入缸取水僅爲1桶水，且不可同時進行。試給出有關從缸取水，入水的算法描述。

在本題中我忽略了一個限制關係，那就是老和尚取水的時候，缸裏沒水怎麼辦？所以要多設置一個信號量表示缸中水的數量。

從井中取水並放入水缸是一個連續的動作，可視爲一個進程；從缸中取水可視爲另一個進程。設水井和水缸爲臨界資源，引入mutex1和mutex2；三個水桶無論是從井中取水還是將水倒入水缸都是一次一個，應該給他們一個信號量empty1，搶不到水桶的進程只好等待。水缸滿時，不可以再放水，設置empty2信號量來控制入水量；水缸空時，不可以取水，設置empty3信號量來控制。

semaphore mutex1 = 1;//用於互斥地訪問水井
semaphore mutex2 = 1;//用於互斥的訪問水缸
semaphore empty2 = 10;//用於表示水缸中剩餘空間能容納的水的桶數
semaphore empty1 = 3;//表示有多少個水桶可用，初值爲3
semaphore empty3 = 0;//表示水缸中水的桶數
//小和尚
while(True)
{
	P(mutex1);//互斥訪問水井
	P(empty2);//申請使用一個水桶
	從井中打一桶水;
	V(mutex1);
	P(mutex2);//互斥訪問水缸
	P(empty2);
	將水倒入水缸中;
	V(mutex2);
	V(empty1);
	V(empty3);
}
//老和尚
while(True)
{
	P(empty3);//申請從水缸中取水
	P(mutex2);//互斥訪問水缸
	P(empty1);//申請使用一個水桶
	從水缸中打一桶水;
	V(mutex2);
	V(empty2);
	喝水;
	V(empty1);//釋放一個水桶
}
這種題很需要加註釋。

7如下圖所示，三個合作進程P1，P2，P3，它們都需要通過同一設備輸入各自的數據a,b,c，該輸入設備必須互斥的使用，而且其第一個數據必須由P1進程讀取，第二個數據必須由P2進程讀取，第三個數據必須由p3進程讀取。然後，三個進程分別對輸入數據進行下列計算：

P1:x=a+b;
P2:y=a*b;
P3:z=y+c-a；
最後，P1進程通過所連接的打印機將計算結果x，y，z的值打印出來，請用信號量實現它們的同步。

這種題很少見，因爲它居然沒有mutex，就是隻考了同步，我覺得真是太妙了。而且最後還要由進程P1把結果輸出，這又是一個同步。另外這種有多個進程的還是要分開寫。這題實在是太精妙了。

爲了控制三個進程依次使用輸入設備進行輸入，需分別設置三個信號量S1,S2,S3，其中S1的初值爲1，S2和S3的初值均爲0.使用上述信號量後，三個進程不會同時使用輸入設備，因此不必再爲輸入設備設置互斥信號量。另外，還需要設置信號量Sb，Sy，Sz來表示數據b是否已經輸入，以及y，z是否已計算完成，他們的初值均爲0。

semaphore S1=1，S2=0，S3=0；
semaphore Sb=0，Sy=0，Sz=0；
P1(){
	P(S1);
	從輸入設備輸入數據a;
	V(S2);
	P(Sb);
	x=a+b;
	P(Sy);
	P(Sz);
	使用打印機打印出x,y,z的結果;
}
P2(){
	P(S2);
	從輸入設備輸入數據b;
	V(S3);
	V(Sb);
	y=a+b;
	V(Sy);
}
P3(){
	P(S3);
	從輸入設備輸入數據c;
	P(Sy);
	z=y+c-a;
	V(Sz);
}

8

cobegin
semaphore seat = 10;//供顧客等待的座位，初始值爲10
semaphore costomer = 0;//銀行內在座位上等待的顧客數，初始爲0
semaphore mutex = 1;//用於取號機的互斥訪問
semaphore service =0;總歸是營業員先叫號，然後顧客再離開座位去接受服務，這裏又有一重同步關係，所以要設一個service。

{
	process顧客i；
	{	
		P(seat);
		P(mutex);
		從取號機獲取一個號碼;
		V(mutex);
		V(costomer);
		P(service);
		等待叫號;
		獲取服務;
	}
	process 營業員
	{
		while(true)
		{
			P(costomer);//有顧客等待才叫號，沒有顧客等待就不叫號			
			叫號;
			V(service);			
			爲顧客服務;
			V(seat);//顧客接受服務完走了，空閒座位+1
		}
	}
}

9有橋如下圖所示，車流方向如箭頭所示，回答下列問題：

（1）假設橋上每次只能有一輛車行駛，試用信號燈的P，V操作實現交通管理。4
（2）假設橋上不允許兩車交會，但允許同方向多輛車一次通過（即橋上可有多輛同方向行駛的車）。試用信號燈的P，V操作實現橋上的交通管理。

過橋錯誤答案

我說寫着寫着怎麼一直感覺不對勁，原來是這裏是要分成兩個進程來寫，分別是從北邊往南走和從南邊往北走。

semaphore bridge = 1;//用於互斥的訪問橋
NtoS(){
	P(bridge);
	通過橋;
	V(brisge);
}
StoN(){
	P(bridge);
	通過橋;
	V(brisge);
}

(2)遇到這種沒有給定具體數量的題目，得用count和if了
橋上可以同方向多車行駛，需要設置bridge，還需要對同方向車輛計數。爲了防止同方向計數中同時申請bridge造成同方向不可同時行車的問題，要對計數過程加以保護，因爲設置信號量mutexSN，mutexNS。

int countSN = 0;
int countNS = 0;
semaphore mutexSN = 1;
semaphore mutexNS = 1;
semaphore bridge = 1;
StoN(){
	P(mutexSN);
	if(countSN==0)
		P(bridge);
	countSN++;
	V(mutexSN);
	過橋;
	P(mutexSN);
	countSN--;
	if(countSN==0)
		V(bridge);
	V(mutexSN);
}
NtoS(){
	P(mutexNS);
	if(countNS==0)
		P(bridge);
	countNS++;
	V(mutexNS);
	過橋;
	P(mutexNS);
	countNS--;
	if(countNS==0);
		V(bridge);
	V(mutexNS);
}

10假設有兩個線程（編號爲0和1）需要去訪問同一個共享資源，爲避免競爭狀態的問題，我們必須實現一種互斥機制，使得在任何時候只能有一個線程訪問這個資源。假如有如下一段代碼：

bool flag[2];//flag數組，初始化爲FALSE
Enter_Critical_Section(int my_thread_id,int other_thread_id){
	while(flag[other_thread_id]==TRUE);
	flag[my_thread_id]=TRUE;
}
Exit_Critical_Section(int my_thread_id,int other_thread_id){
	flag[my_thread_id]=FALSE;
}

當一個線程想要訪問臨界資源時，就調用上述的這兩個函數。例如，線程0的代碼可能是這樣的：
Enter_Critical_Section(0,1);
使用這個資源;
Exit_Critical_Section（0,1）;
做其他的事情；
試問：
（1）上述的這種機制能夠實現資源互斥訪問嗎？爲什麼？
（2）若把Enter_Critical_Section（）函數中的兩條語句互換一下位置，結果會如何？
一開始都是FALSE，線程1是TRUE的時候，線程0陷入忙等狀態，直到線程1是FALSE的時候，才跳出死循環，去執行線程0，因此可以實現互斥訪問。

啥玩意還要時鐘中斷，還要考慮原子性，我看408的題目咋沒說原子性，我真是服氣。好像真的考慮原子性，要不就是線程1執行完，線程0才能進行實現這種同步。

不能實現互斥訪問。考慮如下情形：
（1）初始化時，flag數組的兩個元素值均爲FALSE。
（2）線程0先執行，執行while循環語句時，由於flag[1]爲FALSE，所以順利結束，不會被卡住。假設這時來了一個時鐘中斷，打斷了它的運行。
（3）線程1去執行，執行while循環語句時，由於flag[0]爲FALSE，所以順利結束，不會被卡住，然後進入臨界區。
（4）後來當線程0再執行時，也進入臨界區，這樣就同時有兩個線程在臨界區。
總結：不能成功的根本原因是無法保證Enter_Critical_Section函數執行的原子性。我們從上面的軟件實現方法中可以看出，對於兩個進程互斥，最主要的問題是標誌的檢查和修改不能作爲一個整體來執行，因此容易導致無法保證互斥訪問的問題。
如果兩條語句換一下位置，那麼無論線程1是什麼狀態，線程0都會區執行，這就無法實現互斥訪問，會陷入死鎖狀態。

11同步與死鎖

semaphore empty = N;
semaphore frame = 0;
semaphore wheel = 0;
semaphore s1 = N-2;
semaphore s2 = N-1;
工人1活動:
do{
	加工一個車架;
	P(s1);
	P(empty);
	車架放入箱中;
	V(frame);
}while(1);
工人2活動:
do{
	加工一個車輪;
	P(s2);
	P(empty);
	車輪放入箱中;
	V(wheel);
}while(1)
工人3活動:
do{
	P(frame);
	箱中取一車架;
	V(empty);
	V(s1);
	P(wheel);
	P(wheel);
	箱中取兩個車輪;
	V(empty);
	V(empty);
	V(s2);
	V(s2);
	組裝爲一臺車;
}while(1)

12設P，Q，R共享一個緩衝區，P，Q構成一對生產者-消費者，R既爲生產者又爲消費者。使用P，V操作使其同步。

其實本題的難點就在於如何理解這個R進程。R既爲消費者又爲生產者，因此必須在執行前判斷狀態，若empty=1，則執行生產者功能，若full=1，則執行消費者功能。

semaphore full = 0;//表示緩衝區的產品
semaphore empty = 1;//表示緩衝區的空位
semaphore mutex = 1;//互斥信號量
Procedure P
{
	while(True){
		P(empty);
		P(mutex);
		Product one;
		V(mutex);
		V(full);
		}
}
Procedure Q
{
	while(True){
		P(full);
		P(mutex);
		Consume one;
		V(mutex);
		V(empty);
		}
}
Procedure R
{
	if(empty==1){
		P(empty);
		P(mutex);
		produce one;
		V(mutex);
		V(full);
	}
	if(full==1){
		P(full);
		P(mutex);
		Consume one;
		V(mutex);
		V(empty);
	}
}

13理髮店裏有一位理髮師，一把理髮椅和n把供等候理髮的顧客坐的椅子。若沒有顧客，理髮師便在理髮椅上睡覺，一位顧客到來時，顧客必須叫醒理髮師，若理髮師正在理髮時又有顧客到來，若有空椅子可坐，則坐下來等待，否則就離開。試用P，V操作實現，並說明信號量的定義和初值。

'''控制變量waiting用來記錄等待理髮的顧客數，初值爲0，進來一個顧客時，waiting加1，一個顧客理髮時，waiting減1。
信號量coustomers用來記錄等候理髮的顧客數，並用作阻塞理髮師進程，初值爲0。
信號量baebers用來記錄正在等候顧客的理髮師數，並用作阻塞理髮師進程，初值爲0。
信號量mutex用於互斥，信號量爲1。
int waiting = 0;//等候理髮的顧客數
int chairs = n;//爲顧客準備的椅子數
semaphore cuotomers=0,barbers=0,mutex=1;
barber(){
	while(True){
		P(customers);//若無顧客，理髮師睡眠
		P(mutex);//進程互斥
		waiting = waiting-1;//等候顧客數少1個
		V(barbers);//理髮師爲一個顧客理髮
		V(mutex);
		Cut_hair();
		}
}
customer(){
	P(mutex);
	if(waiting<chairs){
		waiting=waiting+1;//等待顧客數加1
		V(customers);
		P(mutex);
		P(barbers);//無理髮師，顧客坐着
		get_hair_cut();
		}
	else
		V(mutex);//人滿，顧客離開
}

14 有錄像廳和觀衆兩個主體。

限制條件1：只有3種錄像片
限制條件2：看其他錄像片的觀衆不允許進入

這一題犯的錯誤是明明有三種想看電影的人，但我卻把他們統一處理了。

16設公共汽車上駕駛員和售票員的活動分別如下圖所示。駕駛員的活動：啓動車輛，正常行駛，到站停車；售票員的活動：關車門，售票，開車門。在汽車不斷地到站，停車，行駛的過程中，這兩個活動有什麼同步關係？用信號量和P，V操作實現它們的同步。

在汽車行駛過程中，駕駛員活動與售票員活動之間的同步關係爲：售票員關閉車門後，向駕駛員發開車信號，駕駛員接到開車信號後啓動車輛，在汽車正常行駛過程中售票員售票，到站時駕駛員離車，售票員在車停後開門讓乘客上下車。因此，駕駛員啓動車輛的動作必須和售票員關車門的動作同步；售票員開車門的動作也必須與駕駛員停車同步。應設置兩個信號量S1，S2，S1表示是否允許駕駛員啓動汽車，初值爲0；S2表示是否允許售票員開門（初值爲0）

semaphore S1=S2=0;
Procedure driver
{
	P(S1);
	Start;
	Driving;
	Stop;
	V(S2);
}
Procedure Conductor
{
	while(1)
	{
		關車門;
		V(S1);
		售票;
		P(S2);
		開車門;
		上下乘客;
	}
}

17信箱辯論

很nice，這種類型的題目我差不多已經掌握了。

18某進程中有3個併發執行的線程thread1，thread2和thread3，其僞代碼如下所示：

//複數的結構類型定義
typedef struct
{	
	float a;
	float b;
} cnum;
cnum x,y,z;//全局變量

//計算兩個複數之和
cunm add (cnump,cnumq)
{
	cnum s;
	s.a=p.a+q.a;
	s.b=p.b+q.b;
	return s;
}

}