第二章补充习题.doc

1、桌上有一只盘子，最多可容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘中放苹果，妈妈放专向盘中放桔子；两个儿子专等吃盘子中的桔子，两个女儿专等吃盘子中的苹果。请用P、V操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。答：本题中需设置4个信号量，其中empty表示还可以向盘中放几个水果，其初值为2；apple对应已放入盘中的苹果，orange对应已放入盘中的桔子，它们的初值均为0；mutex用来实现对盘子的互斥访问（包括放和取），其初值为1。相应的进程可描述为：father()while(1) P(empty); P(mutex); 向盘中放苹果; 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个床位，住宿者住入要先登记（在登记表上填写姓名及床位号），离去时要撤消登记（在登记表上删去姓名和床位号）。请给出住宿登记及撤消登记过程的算法描述。答：本题中，被住宿者竞争的资源主要有床位和住宿登记表两种，可分别为它们设置初值为100的信号量bed及初值为1的信号量mutex。住宿登记过程的算法描述如下：P(bed);P(mutex);在登记表上填写姓名及床位号;v(mutex);撤消登记过程的算法描述如下：P(mutex);在登记表上删去姓名和床位号;V(mutex);V(bed);3、一阅览室，读者进入阅览室必须先在一张登记表（TB）上登记，该表为每一座位设一个表目，读者离开时要消掉其登记信息，阅览室共有100个座位。为了描述读者的动作，请用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。读者的动作可描述为：reader() 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(count); /* 释放座位 */离开阅览室；4、某寺庙，有小和尚、老和尚若干。有一水缸，有小和尚提水入缸供老和尚饮用。水缸可容10桶水，水取自同一井中。水井径窄，每次只能容一个桶取水。水桶总数为3个。每次入、取缸水仅为1桶，且不可同时进行。试给出有关取水、入水的算法描述。 答：本题中需设置5个信号量：bucket对应临界资源水桶，初值为3；jar用来对水缸进行互斥操作，初值为1；full表示水缸中可以使用的水，初值为0；empty表示缸中还可入水的容量，初值为10；well用来保证互斥地使用水井，初值为1。有关取水、入水的算法描述如下：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. 如图所示，三个合作进程P1、P2、P3，它们都需通过同一输入设备输入各自的数据a、b、c，该输入设备必须互斥地使用，而且其第一个数据必须由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(