进程同步经典习题.doc

1. 某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请用PV操作实现管理。解：定义一个信号量S，初值为20parbegin process pl(l=1,2,)beginwait(S);进入售票厅；购票；退出；signal(S)end2. 桌上有一空盘，允许存放一个水果，爸爸可向盘内放苹果，妈妈可向盘内放桔子，儿子专等吃盘内的桔子，女儿专等吃盘中的苹果，请用P、V 操作实现爸爸、妈妈、儿子、女儿四个并发进程的同步与互斥。int S=1;int Sa=0;int Sb=0;main()cobeginfather();mather();son();daughter();coendfather()mather()while(1) while(1)p(S); p(S) ;将一个苹果放入盘中将一个桔子放入盘中V(Sa); V(Sb);son()daughter() while(1) while(1)p(Sb); p(Sa);从盘中取出桔子从盘中取出苹果V(S);吃桔子； V(S);吃苹果；3. 生产围棋的工人不小心把相等数量的黑子和白子混装在一个盒子里，现在要用自动分拣系统把黑子和白子分开，该系统由两个并发执行的进程PA和PB组成，系统功能如下：（1）PA专拣黑子，PB专拣白子；（2）每个进程每次只拣一个子，当一个进程拣子时，不允许另一个进程去拣子；（3）当一个进程拣一个子（黑或白）后，必须让另一个进程去拣一个子（白或黑）请回答：这两个并发进程之间的关系是同步还是互斥写出PV操作管理时应定义的信号量及其初值。根据定义的信号量，写出用PV操作管理两个并发进程的程序答：两个进程之间是同步关系定义两个信号量S1和S2，初值为1和0process PA process PA begin begin repeat repeat wait(S1) wait(S2) 拣黑子 拣白子 signal(S2) signal(S1) until false until false end end4. 有一阅览室，读者进入时必须先在一张登记表上登记，该表为每一座位列出一个表目，包括座号、姓名，读者离开时要注销登记信息；假若阅览室共有100个座位。试用信号量和PV操作来实现用户进程的同步算法。解：设置如下3个信号量seat：表示阅览室中空座位数，其初值为100.readers：记录阅览室中的读者数，其初值为0.mutex：互斥信号量（对于读者而言，阅览室是一个临界资源，任何时刻最多只有一位读者填写登记表或撤销登记表），初值为1.对应的算法描述如下：semaphore seats=100；semaphore readers=0；semaphore mutex=1；main（）cobegin 读者进入阅览室进程readerini(i=1,2,n) while(true) p(seats); /递减空座位数 p(mutex); 填写登记表 进入阅览室； v(mutex); /允许其他读者访问阅览室 v(readers); /递增读者数 读者离开阅览室进程readerouti (i=1,2, ,n)while(true) p(readers); p(mutex); 撤销登记；离开阅览室；v(mutex);v(seats);coend解法二：解：var name:array1.100of AA=record number:integer; name:string;endfor i:=1 to 100 do Ai.number:=i;A:=null;mutex,seatcount:semaphore;mutex:=1;seacount:=100;cobegin process readeri(var readername:string)(i=1,2) begin p(seatcount); p(mutex); for i:=1 to 100 do i+ if A=null then A:= readername; reader get the seat number=i; v(mutex); 进入阅览室座位号i,坐下读书； p(mutex); A:=null; V(mutex); V(seatcount); 离开阅览室; endcoend5. 三个进程P1、P2、P3互斥使用一个包含N（N0）个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用geteven()从缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。2009年全国考研试题解：缓冲区是一互斥信号量，因此设互斥信号量mutexP1、P2因为奇数的设置与取用而同步，设同步信号量odd；P1、P3因为偶数的设置与取用而同步，设同步信号量even；P1、P2、P3因为共享缓冲区，设同步信号量empty。semaphore mutex=1; /缓冲区互斥信号量semaphore odd=0, even=0 ; /奇数、偶数进程的同步信号量semaphore empty=N ; /空缓冲区单元个数信号量main( )cobeginprocess P1 while(true) number=produce(); p(empty); /递减空缓冲区的单元个数p(mutex); /互斥访问缓冲区put( );v(mutex); /恢复访问缓冲区if number%2=0 v(even); /为偶数允许取偶数else v(odd); /为奇数允许取奇数process P2 process P3 while(true) while(true) p(odd); /互斥奇数p(even);p(mu