第二章補(bǔ)充習(xí)題.doc

1、桌上有一只盤子，最多可容納兩個(gè)水果，每次只能放入或取出一個(gè)水果。爸爸專向盤中放蘋果，媽媽放專向盤中放桔子；兩個(gè)兒子專等吃盤子中的桔子，兩個(gè)女兒專等吃盤子中的蘋果。請(qǐng)用P、V操作來(lái)實(shí)現(xiàn)爸爸、媽媽、兒子、女兒之間的同步與互斥關(guān)系。答：本題中需設(shè)置4個(gè)信號(hào)量，其中empty表示還可以向盤中放幾個(gè)水果，其初值為2；apple對(duì)應(yīng)已放入盤中的蘋果，orange對(duì)應(yīng)已放入盤中的桔子，它們的初值均為0；mutex用來(lái)實(shí)現(xiàn)對(duì)盤子的互斥訪問(wèn)（包括放和?。?，其初值為1。相應(yīng)的進(jìn)程可描述為：father()while(1) P(empty); P(mutex); 向盤中放蘋果; V(mutex); V(apple);mother()while(1) P(empty); P(mutex); 向盤中放桔子; V(mutex); V(orange);son () /* 兩個(gè)兒子對(duì)應(yīng)同一段代碼 */while(1) P(orange); P(mutex); 從盤中取桔子; V(mutex); V(empty); 吃桔子;daughter() /* 兩個(gè)女兒對(duì)應(yīng)同一段代碼 */while(1) P(apple); P(mutex); 從盤中取蘋果; V(mutex); V(empty); 吃蘋果;2、某招待所有100個(gè)床位，住宿者住入要先登記（在登記表上填寫姓名及床位號(hào)），離去時(shí)要撤消登記（在登記表上刪去姓名和床位號(hào)）。請(qǐng)給出住宿登記及撤消登記過(guò)程的算法描述。答：本題中，被住宿者競(jìng)爭(zhēng)的資源主要有床位和住宿登記表兩種，可分別為它們?cè)O(shè)置初值為100的信號(hào)量bed及初值為1的信號(hào)量mutex。住宿登記過(guò)程的算法描述如下：P(bed);P(mutex);在登記表上填寫姓名及床位號(hào);v(mutex);撤消登記過(guò)程的算法描述如下：P(mutex);在登記表上刪去姓名和床位號(hào);V(mutex);V(bed);3、一閱覽室，讀者進(jìn)入閱覽室必須先在一張登記表（TB）上登記，該表為每一座位設(shè)一個(gè)表目，讀者離開時(shí)要消掉其登記信息，閱覽室共有100個(gè)座位。為了描述讀者的動(dòng)作，請(qǐng)用Pascal語(yǔ)言和P、V操作寫出進(jìn)程間的同步算法。約定：（1）flag的值：0座位空閑，1座位被占用。（2）用語(yǔ)句i=getflag（0）可搜索到一個(gè)空座位i，用語(yǔ)句i.falg=0或1可給標(biāo)志位賦值。（3）用i=getname（readername）可搜索到某讀者所登記的座位號(hào)i；用=0或=readername可給姓名字段賦值，0表示消除讀者姓名。（4）計(jì)數(shù)信號(hào)量用count，互斥信號(hào)量用mutex。 答：本題中，讀者要競(jìng)爭(zhēng)座位、登記表兩種資源，故可分別為它們?cè)O(shè)置初值為100的信號(hào)量count，以及初值為1的信號(hào)量mutex。讀者的動(dòng)作可描述為：reader() while(1)P(count); /* 申請(qǐng)一個(gè)座位 */P(mutex); /* 申請(qǐng)登記表 */i=getflag(0); /* 在登記表上搜索一個(gè)空座位 */i.flag=1; /* 登記該座位已被占用 */=readername; /* 登記讀者姓名 */V(mutex)； /* 釋放登記表 */進(jìn)入閱覽室，坐下并開始閱覽；P(mutex); /* 申請(qǐng)登記表 */i=getname(readername); /* 在登記表上搜索讀者登記的座位號(hào) */i.falg=0; /* 撤消登記信息 */=0;P(mutex); /* 釋放登記表 */V(count); /* 釋放座位 */離開閱覽室；4、某寺廟，有小和尚、老和尚若干。有一水缸，有小和尚提水入缸供老和尚飲用。水缸可容10桶水，水取自同一井中。水井徑窄，每次只能容一個(gè)桶取水。水桶總數(shù)為3個(gè)。每次入、取缸水僅為1桶，且不可同時(shí)進(jìn)行。試給出有關(guān)取水、入水的算法描述。 答：本題中需設(shè)置5個(gè)信號(hào)量：bucket對(duì)應(yīng)臨界資源水桶，初值為3；jar用來(lái)對(duì)水缸進(jìn)行互斥操作，初值為1；full表示水缸中可以使用的水，初值為0；empty表示缸中還可入水的容量，初值為10；well用來(lái)保證互斥地使用水井，初值為1。有關(guān)取水、入水的算法描述如下：semaphore bucket=3,jar=1,full=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. 如圖所示，三個(gè)合作進(jìn)程P1、P2、P3，它們都需通過(guò)同一輸入設(shè)備輸入各自的數(shù)據(jù)a、b、c，該輸入設(shè)備必須互斥地使用，而且其第一個(gè)數(shù)據(jù)必須由P1進(jìn)程讀取，第二個(gè)數(shù)據(jù)必須由P2進(jìn)程讀取，第三個(gè)數(shù)據(jù)則必須由P3進(jìn)程讀取。然后，三個(gè)進(jìn)程分別對(duì)輸入數(shù)據(jù)進(jìn)行下列計(jì)算：P1: x = a + bP2: y = a * bP3: z = y + c a最后，P1進(jìn)程通過(guò)所連的打印機(jī)將計(jì)算結(jié)果x、y、z的值打印出來(lái)。請(qǐng)用信號(hào)量實(shí)現(xiàn)它們的同步。P1P2P3Non-preemptive input deviceInput(a)Input(c)Input(b)圖 P1、P2、P3的工作示意圖答：為了控制三個(gè)進(jìn)程依次使用輸入設(shè)備進(jìn)行輸入，需分別設(shè)置三個(gè)信號(hào)量S1、S2、S3，其中S1的初值為1，S2和S3的初值為0。使用上述信號(hào)量后，三個(gè)進(jìn)程不會(huì)同時(shí)使用輸入設(shè)備，故不必再為輸入設(shè)備設(shè)置互斥信號(hào)量。另外，還需設(shè)置信號(hào)量Sb、Sy、Sz來(lái)分別表示數(shù)據(jù)b是否已經(jīng)輸入，以及y、z是否已計(jì)算完成，它們的初值均為0。三個(gè)進(jìn)程的動(dòng)作可描述為：P1：P(S1);從輸入設(shè)備輸入數(shù)據(jù)a；V(