PKUOS 第四章习题讲解 陈子文

 1. 以 Linux 为例，列举出进程状态转换的典型原因 和引起进程调度的因素。  Linux 进程状态有五种（ running/interruptible/uninteruptible/zombie/stoppe d ）  进程因等待输入而阻塞  调度程序选择另一个进程  输入可用  … PKUOS2

 2. 说明下列活动是属于哪种制约关系？ （ 1 ）若干同学去图书馆借书； （ 2 ）两队进行篮球比赛； （ 3 ）流水线生产中的各道工序； （ 4 ）商品生产和社会消费。 PKUOS3 互斥 同步

 3. 有 K 个进程共享一个临界区，对于下述情况， 请说明信号量的初值、含义，并用 P 、 V 操作写出 有关的互斥算法。  （ 1 ）一次只允许一个进程进入临界区； mutex ，初值为１，记录可进入临界区的进程数 ;  （ 2 ）一次允许 m 个进程进入临界区（ m<K ）。 mutex ，初值为 m ，记录可进入临界区的进程数 ; PKUOS4 互斥算法： P(mutex); 进入临界区； V(mutex); 结束；

 4. 假定一个阅览室最多可容纳 100 人，读者进入 和离开阅览室时都必须在阅览室门口的一个登记 表上标志（进入时登记，离开时去掉登记项）， 而且每次只允许一人登记或去掉登记，问：  （ 1 ）应编写几个程序完成此项工作，程序的主要 动作是些什么？应设置几个进程？进程与程序间的 对应关系如何？  （ 2 ）用 P ， V 操作写出这些进程的同步通信关系 PKUOS5

错误的答案  （ 1 ）  两个程序 登入：查看是否可入；可入的话在登记表上登记 登出：释放资源（位置资源）；去掉登机项  两个进程 PKUOS6 登入进程： { P(reader_count ） P(mutex) 登记表上登记 V(mutex) } 登出进程： { P(mutex) 去掉登记 V(reader_count) V(mutex) } Semaphore reader_count=100 ，控制可进入的读者数 Semaphore mutex=1 ，控制操作登记表

正确的答案  一个程序，根据读者数量有相应的进程数 PKUOS7 读者进程： { P(reader_count ） P(mutex) 登记表上登记 V(mutex) 看书 P(mutex) 去掉登记 V(reader_count) V(mutex) }

 5. 进程 A 1 ， A 2 ， … ， A n1 通过 m 个缓冲区向进程 B 1 ， B 2 ， … ， B n2 不断地发送消息，发送和接收工作 遵循如下规则： （ 1 ）每个发送进程每次发送一个消息，写入一个 缓冲区，缓冲区大小与消息长度一样； （ 2 ）对每一个消息， B 1 ， B 2 ， … ， B n2 都需要各接 收一次，读到各自的数据区内； （ 3 ） m 个缓冲区都满时，发送进程等待；没有可读 的消息时，接收进程等待。 试用 P ， V 操作组织正确的发送和接收操作 PKUOS8

分析  发送进程间的关系 — 互斥写 buffer  设置互斥信号量 mutex_cur  接收进程间的关系 — 共享读  发送进程和接收进程的关系 — 生产者与消费者  多个生产者，多个消费者，多个缓冲区  附加条件：广播 PKUOS9

10/32 参考答案 Semaphore mutex_count[m],mutex_cur,mutex_send[m] : (initial value = 1) Integer buffer_count[m]: (initial value = {0…0}) Semaphore mutex_receive[m] : (initial value = 0)

11/32 SENDER While true do begin P(mutex_cur); cur := (cur + 1 ) % m; V(mutex_cur); P(mutex_send[cur]); 写入 buffer[cur] V(mutex_receive[cur]); end RECEIVER While true do begin for I: = 0 to m do begin P(mutex_count[i]) buffer_count[i] := buffer_count[i] + 1; if Buffer_count[i] = 1 then P(mutex_receive[i]); V(mutex_count[i]); 从 buffer[i] 中读 P(mutex_count[i]); if Buffer_count[i] = n2 then do begin buffer_count[i] := 0; V(mutex_send[i]); end V(mutex_count[i]); end

PKUOS12 P1,P2,… ： i = 0;// 全局 while (true) { 生产产品 ; P(S1); P(mutex1); 往 Buffer [i] 放产品 ; i = (i+1) % n; V(mutex1); V(S2); } Q1,Q2,… ： j = 0;// 全局 while (true) { P(S2); P(mutex2); 从 Buffer[j] 取产品 ; j = (j+1) % n; V(mutex2); V(S1); 消费产品 ; } 只有当所有的消费者进程 接收到这个消息之后，才 能释放这个缓冲区资源。 因此引入一个数组，数组 大小与缓冲区大小一致

PKUOS13 Q1,Q2,… ： buffer_count[ 0..m-1] = 0 ； j = 0;// 每个消费者进程的局部变量 pid = getpid();// 获取该进程的进程号 while (true) { P(S2[j][pid]); P(mutex2); 从 Buffer[ j ] 取产品 ; If (++ buffer_count[ j ] == n2) // 所有的接收进程已经接到该消息 { buffer_count[ j ] = 0; V(S1); } j = (j+1) % m; V(mutex2); 消费产品 ; } P1,P2,… ： i = 0;// 全局 while (true) { 生产产品 ; P(S1); P(mutex1); 往 Buffer [i] 放产品 ; for(k=0..n2 - 1) V(S2[i][k]); i = (i+1) % m; V(mutex1); } 改为二维数组，考虑可 能某进程读得太快，会 绕过来读已经读过的 buffer ，因此多加了一 维用来标识进程

爱睡觉的理发师问题 [Dijkstra ， 1968]  6. 一个理发店有两间相连的屋子。一间是私室， 里面有一把理发椅，另一间是等候室，有一个滑 动门和 N 把椅子。理发师忙的时候，通向私室的 门被关闭，新来的顾客找一把空椅子坐下，如果 椅子都被占用了，则顾客只好离去。如果没有顾 客，则理发师在理发椅上睡觉，并打开通向私室 的门。理发师睡觉时，顾客可以叫醒他理发。请 编写理发师和顾客的程序，正确实现同步互斥问 题。 PKUOS14

15/32 参考答案 Integer waiting;(initial value = 0) Semaphore customer,barbers;(initial value = 0) Semaphore mutex:(initial value = 1) BARBER While(TRUE) do P(customers); P(mutex); waiting := waiting – 1; V(barbers); V(mutex); cut hair End do CUSTOMER P(mutex); if waiting < CHAIRS then do waiting := waiting + 1; V(customers); V(mutex); P(barbers); get haircut end do else then V(mutex);

 7. 在一间酒吧里有三个音乐爱好者，第一位音乐 爱好者只有随身听，第二位只有音乐 CD ，第三位 只有电池。而要听音乐就必须随身听、音乐 CD 和 电池这三种物品俱全。酒吧老板一次出借这三种 物品中的任意两种。当一名音乐爱好者得到这三 种物品并听完一首乐曲后，酒吧老板才能再一次 出借这三种物品中的任意两种。于是第二名音乐 爱好者得到这三种物品，并开始听乐曲。整个就 这样进行下去。 试用 P 、 V 操作正确解决这一过程。 PKUOS16

17/32 参考答案 semaphore mode1=0;// 缺少音乐 CD 和电池 semaphore mode2=0; semaphore mode3=0; semaphore musician=0;// 向老板借物品的音乐爱好者 semaphore wait = 0 ； Boss() { while(true) { p(musician);// 等候音乐爱好者来借 int prov=genprovide();// 出借三种物品中的任意两种； if(prov==1)// 如果是音乐 CD 和电池 v(mode1); else if(prov==2) v(mode2); else v(mode3); p(wait); // 等待某音乐爱好者归还物品 }

18/32 参考答案 musicLover(int i) { while(true) { v(musician);// 向老板要求接东西 if(i==1){// 如果只有随身听 p(mode1);// 向老板借其他两样物品 得到其他两样物品； 听音乐； } if(i==2){// 如果只有音乐 CD p(mode2); 得到其他两样物品； 听音乐； } if(i==3){// 如果只有电池 p(mode3); 得到其他两样物品； 听音乐； } v(wait); // 使得老板可以进行下一次借出 }

 8. 巴拿马运河建在太平洋和大西洋之间。由于太 平洋和大西洋水面高度不同，有巨大落差，所以 运河中修建有 T （ T>=2 ）级船闸，并且只能允许 单向通行。船闸依次编号为 1 ， 2 ， …… ， T 。由 大西洋来的船需经由船闸 T ， T-1 ， …… ， 2 ， 1 通 过运河到太平洋；由太平洋来的船需经由船闸 1 ， 2 ， …… ， T-1 ， T 通过运河到大西洋。 试用 P ， V 操作正确解决大西洋和太平洋的船只通 航问题。 PKUOS19

20/32 参考答案  PtoAcnt 整型，记录此船闸正由太平洋往大西洋 航行的船只 初值 0 。  AtoPcnt 整型，记录此船闸正由大西洋往太平洋 航行的船只 初值 0 。  MutexA 信号量，对 PtoAcount 互斥 初值 1  MutexB 信号量，对 AtoPcount 互斥 初值 1  Lock 信号量 初值 1

21/32 参考答案 P(mutexA); // 从太平洋至大西洋，方向雷同 PtoAcnt =PtoAcnt+1; if PtoAcnt = = 1 then P(Lock); V(mutexA); 过 P(mutexA) PtoAcnt=PtoAcnt-1; if PtoAcnt = = 0; then V(Lock); V(mutexA);

 9. 某银行有人民币储蓄业务，由 n 个柜员负责。 每个顾客进入银行后先取一个号，并且等着叫号 。当一个柜台人员空闲下来，就叫下一个号。试 用 P ， V 操作正确编写柜台人员和顾客进程的程 序。 PKUOS22

参考答案 PKUOS23 顾客进程： { // 取号码 P(MUTEX_CUSTOMER_NUM); int X = CUSTOMER_NUM; CUSTOMER_NUM++; V(MUTEX_CUSTOMER_NUM); // 等待叫号 V(CUSTOMER); P(COUNTER); ACTION_CUSTOMER(X); } 柜台人员进程： { int X; REPEAT // 叫号 P(CUSTOMER); P(MUTEX_COUNTER_NUM); int X = COUNTER_NUM; V(MUTEX_COUNTER_NUM); ACTION_COUNTER(X); V(COUNTER); UNTIL false; } Semaphore COUNTER=n ， 柜台工作人员数量 Semaphore CUSTOMER=0 ，顾客数量 互斥信号量： MUTEX_CUSTOMER_NUM 、 MUTEX_COUNTER_NUM

24/32 第四章习题  10. 某系统如此定义 P 、 V 操作： P （ S ） S = S – 1 ； 若 S ＜ 0 ，本进程进入 S 信号量等待队列的末尾；否则， 继续执行。 V （ S ） S ＝ S ＋ 1 ； 若 S≤0 ，释放等待队列中末尾的进程，否则继续运行。 （ 1 ）上面定义的 P 、 V 操作有什么问题？ （ 2 ）现有四个进程 P1 、 P2 、 P3 、 P4 竞争使用某一个互斥 资源（每个进程可能反复使用多次），试用上面定义的 P 、 V 操作正确解决 P1 、 P2 、 P3 、 P4 对该互斥资源的使用 问题。

25/32 第四章习题 （ 1 ）不合理：先进后出；可能 “ 无限等待 ” （ 2 ）思路：令每个信号量上的等待队列中始终只有 一个进程。 Semaphore S[n-1]; // S[i] 的初值为 i+1 Procedure_i () { int i; DO_PRE_JOB( ); for(i=n-2; i>=0; i--) P(S[i]); DO_JOB_IN_CRITICAL_SECTION; for(i=0;i<n － 1;i++) V(S[i]); …… } 注意释 放顺序

26/32 第四章习题  11. 试用 P 、 V 操作解决第二类读者写者问题。所 谓第二类读者写者问题是指写者优先，条件为： （ 1 ）多个读者可以同时进行读； （ 2 ）写者必须互斥（只允许一个写者写，同时也 不能读者、写者同时进行）； （ 3 ）写者优先于读者（一旦有写者来，则后续读 者必须等待，唤醒时优先考虑写者）

27 第四章习题 Integer readcount,writecount;(initial value = 0) Semaphore mutex1, mutex2, mutex3, w, r;(initial value = 1) READER P(mutex3); P(r); P(mutex1); readcount := readcount +1; if readcount = 1 then P(w); V(mutex1); V(r); V(mutex3); reading P(mutex1) readcount := readcount – 1; If readcount = 0 then V(w); V(mutex1); WRITER P(mutex2) writecount := writecount + 1; If writecount = 1 then P(r); V(mutex2); P(w); writing V(w); P(mutex2); writecount := writecount – 1; If writecount = 0 then V(r); V(mutex2);

28/32 第四章习题  12. 一家快餐店招有 4 种雇员 : （ 1 ）开票者，取顾 客的订单；（ 2 ）厨师，准备饭菜；（ 3 ）包装员 ，把食品塞入袋中；（ 4 ）出纳，一手收钱一手 交货。每位雇员可以看作一个在通信的顺序进程 。他们采用的是什么形式的进程间通信？

29/32 第四章习题  (1) 开票者 (2) 厨师 (3) 包装员 (4) 出纳  (1)->(2) 管道通信（文件）  (2)->(3) 信箱通信（间接）  (3)->(4) 消息缓冲（直接）

30/32 第四章习题  13. 请用进程通信的方法解决生产者消费者问题 void producer( ) { msgbuff mb; /*message buffer*/ while (1){ generate sth to send; receive(consumer, &mb); create_message(&mb); send(consumer,&mb); } void consumer( ) { int i; msgbuff mb; for(i=0 ; i<N; i++) send(producer, &mb); while(1) { receive(producer, &mb); extract message; send(producer, &mb); do sth }

31/32 第四章习题  14. 对某系统进行检测后表明平均每个进程在 I/O 阻塞之前的运行时间为 T 。一次进程切换需要的 时间为 S ，这里 S 实际上就是开销。对于采用时间 片长度为 Q 的时间片轮转法，请给出一下各种情 况的 CPU 利用率的计算公式。 （ 1 ） Q = ∞ （ 2 ） Q > T （ 3 ） S < Q < T （ 4 ） Q = S （ 5 ） Q 趋近于 0 分析：某个进程需要运行的 cpu 时间为 T

32/32 第四章习题 （ 1 ） Q = ∞ （ 2 ） Q > T （ 3 ） S < Q < T （ 4 ） Q = S 1/2 （ 5 ） Q 趋近于 0 0

33/32 第四章习题  16. 有 5 个待运行的进程，他们的估计运行时间分 别是 9 、 6 、 3 、 5 和 X 。采用哪种次序运行各进程 将得到最短的平均响应时间（答案依赖于 X ） ? 3659 X

PKUOS [Q&A] 34