1、-作者xxxx-日期xxxx第二章補充習題【精品文檔】1、桌上有一只盤子，最多可容納兩個水果，每次只能放入或取出一個水果。爸爸專向盤中放蘋果，媽媽放專向盤中放桔子；兩個兒子專等吃盤子中的桔子，兩個女兒專等吃盤子中的蘋果。請用P、V操作來實現爸爸、媽媽、兒子、女兒之間的同步與互斥關系。答：本題中需設置4個信號量，其中empty表示還可以向盤中放幾個水果，其初值為2；apple對應已放入盤中的蘋果，orange對應已放入盤中的桔子，它們的初值均為0；mutex用來實現對盤子的互斥訪問（包括放和取），其初值為1。相應的進程可描述為：father()while(1) P(empty); P(mutex

2、); 向盤中放蘋果; V(mutex); V(apple);mother()while(1) P(empty); P(mutex); 向盤中放桔子; V(mutex); V(orange);son () /* 兩個兒子對應同一段代碼 */while(1) P(orange); P(mutex); 從盤中取桔子; V(mutex); V(empty); 吃桔子;daughter() /* 兩個女兒對應同一段代碼 */while(1) P(apple); P(mutex); 從盤中取蘋果; V(mutex); V(empty); 吃蘋果;2、某招待所有100個床位，住宿者住入要先登記（在登記表上填

3、寫姓名及床位號），離去時要撤消登記（在登記表上刪去姓名和床位號）。請給出住宿登記及撤消登記過程的算法描述。答：本題中，被住宿者競爭的資源主要有床位和住宿登記表兩種，可分別為它們設置初值為100的信號量bed及初值為1的信號量mutex。住宿登記過程的算法描述如下：P(bed);P(mutex);在登記表上填寫姓名及床位號;v(mutex);撤消登記過程的算法描述如下：P(mutex);在登記表上刪去姓名和床位號;V(mutex);V(bed);3、一閱覽室，讀者進入閱覽室必須先在一張登記表（TB）上登記，該表為每一座位設一個表目，讀者離開時要消掉其登記信息，閱覽室共有100個座位。為了描述讀者

4、的動作，請用Pascal語言和P、V操作寫出進程間的同步算法。約定：（1）flag的值：0座位空閑，1座位被占用。（2）用語句i=getflag（0）可搜索到一個空座位i，用語句i.falg=0或1可給標志位賦值。（3）用i=getname（readername）可搜索到某讀者所登記的座位號i；用=0或=readername可給姓名字段賦值，0表示消除讀者姓名。（4）計數信號量用count，互斥信號量用mutex。 答：本題中，讀者要競爭座位、登記表兩種資源，故可分別為它們設置初值為100的信號量count，以及初值為1的信號量mutex。讀者的動作可描述為：reade

5、r() while(1)P(count); /* 申請一個座位 */P(mutex); /* 申請登記表 */i=getflag(0); /* 在登記表上搜索一個空座位 */i.flag=1; /* 登記該座位已被占用 */=readername; /* 登記讀者姓名 */V(mutex)； /* 釋放登記表 */進入閱覽室，坐下并開始閱覽；P(mutex); /* 申請登記表 */i=getname(readername); /* 在登記表上搜索讀者登記的座位號 */i.falg=0; /* 撤消登記信息 */=0;P(mutex); /* 釋放登記表 */V(cou

6、nt); /* 釋放座位 */離開閱覽室；4、某寺廟，有小和尚、老和尚若干。有一水缸，有小和尚提水入缸供老和尚飲用。水缸可容10桶水，水取自同一井中。水井徑窄，每次只能容一個桶取水。水桶總數為3個。每次入、取缸水僅為1桶，且不可同時進行。試給出有關取水、入水的算法描述。 答：本題中需設置5個信號量：bucket對應臨界資源水桶，初值為3；jar用來對水缸進行互斥操作，初值為1；full表示水缸中可以使用的水，初值為0；empty表示缸中還可入水的容量，初值為10；well用來保證互斥地使用水井，初值為1。有關取水、入水的算法描述如下：semaphore bucket=3,jar=1,full=

7、0,empty=10,well=1;little_monk() /* 小和尚入水算法 */while(1)P(empty);P(bucket);P(well);從水井中打水；V(well);P(jar); 倒水入缸；V(jar);V(full);V(bucket);old_monk() /*老和尚取水算法 */while(1)P(full);P(bucket);P(jar); 從缸中取水；V(jar);V(empty); 從桶中倒水飲用；V(bucket); 5. 如圖所示，三個合作進程P1、P2、P3，它們都需通過同一輸入設備輸入各自的數據a、b、c，該輸入設備必須互斥地使用，而且其第一個數

8、據必須由P1進程讀取，第二個數據必須由P2進程讀取，第三個數據則必須由P3進程讀取。然后，三個進程分別對輸入數據進行下列計算：P1: x = a + bP2: y = a * bP3: z = y + c a最后，P1進程通過所連的打印機將計算結果x、y、z的值打印出來。請用信號量實現它們的同步。P1P2P3Non-preemptive input deviceInput(a)Input(c)Input(b)圖 P1、P2、P3的工作示意圖答：為了控制三個進程依次使用輸入設備進行輸入，需分別設置三個信號量S1、S2、S3，其中S1的初值為1，S2和S3的初值為0。使用上述信號量后，三個進程不會同時使用輸入設備，故不必再為輸入設備設置互斥信號量。另外，還需設置信號量Sb、Sy、Sz來分別表示數據b是否已經輸入，以及y、z是否已計算完成，它們的初值均為0。三個進程的動作可描述為：P1：P(S1);從輸入設備輸入數據a；V(S2);