操作系统第五章同步互斥作业.ppt

1、Chapter 5: Process Synchronization进程同步习题课,最简单的情况 如何进行分析呢？ 本章作业2,经典的生产者和消费者问题 一个生产者 V.S. 一个消费者,Producer while(1) produce ； wait(empty); put in buffer; signal(full); ,semaphore empty=1,full=0;,Consumer while(1) wait(full); take out from buffer; signal(empty); consume ,一个生产者 V.S. 一个消费者 但缓冲区有n个,复杂一些的情况

2、如何进行分析呢？ 本章作业3,Producer while(1) produce; wait(empty); put; signal(full); in=(in+1)%n; ,semaphore empty=n,full=0;,Consumer while(1) wait(full); take; signal(empty); consume； out = （out+1)%n; ,Buffer bufn； int in=0,out=0; %使用循环缓冲级数,多个生产者 V.S. 多个消费者 n个缓冲区,更为复杂的情况 如何进行分析呢？ 本章作业3,Producer while(1) produ

3、ce; wait(empty); wait（mutex1） put; in=(in+1)%n; signal（mutex1） signal(full); ,semaphore empty=n,full=0，mutex1=1， mutex2=1;,Consumer while(1) wait(full); wait（mutex2） take; out = （out+1)%n; signal（mutex2） signal(empty); consume； ,Buffer bufn； int in=0,out=0; %使用循环缓冲级数,Process Synchronization Example进

4、程同步例子 作业4,同步要求：先关门，后开车,先停车，后开门,解：,Semaphore close=0，open=0； driver( ) /*司机*/ while(True) P(close); 启动车辆; 正常行车; 到站停车; V(open); ,Conductor( ) /*售票员*/ while(True) 关车门； V(close); 售票;P(open); 开车门; 上下乘客; ,作业5,设有两个优先级相同的进程p1和p2如下。信号量S1和S2的初值均为0，试问P1和P2并发执行结束后，x、y、z的值各位多少？,进程P1 y = 1； y = y+2; V(S1); z = y+

5、1; P(S2); y = z + y;,进程P2 x = 1; x = x +1; P(S1); x = x+y; V(S2); z=x+z;,作业5,设有两个优先级相同的进程p1和p2如下。信号量S1和S2的初值均为0，试问P1和P2并发执行结束后，x、y、z的值各位多少？,进程P1 y = 1； y = y+2; V(S1); z = y+1; P(S2); y = z + y;,进程P2 x = 1; x = x +1; P(S1); x = x+y; V(S2); z=x+z;,y=3,X=2,X=5,Z=4,X的最终值是5; Z的最终值是： 9,Y的最终值取决于P1和P2最后一行的

6、执行顺序： 如果P2先执行完，则Y=12； 如果P1先执行完，则Y=7；,作业6,假定系统有3个并发进程get 、copy 和put共享缓冲器B1和B2。进程get负责从输入设备上读信息，每读出一条记录后放到B1中。进程copy从缓冲器B1中取出一条记录拷贝后存入B2。进程put取出B2中的记录打印输出。B1和B2每次只能存放一条记录。要求3个进程协调完成任务，使打印出来的与读入的记录个数、次序完全一样。请用记录型信号量写出并发程序。（北大1990年试题）,解题思路：这是同步还是互斥呢？ 2个资源； 每个资源对应两个事件（空、满）；,设置4个信号量，其中empty1对应空闲的缓冲区1，其初值为

7、1；full1对应缓冲区1中的记录，其初值为0； empty2对应空闲的缓冲区2，其初值为1；full2对应缓冲区2中的记录，其初值为0。相应进程描述为：,get( ) while(1) 从输入设备 读入一条记录; P(empty1); 将记录存入 缓冲区1； V(full1); ,copy( ) while(1) P(full1); 从缓冲区1中 取出一条记录; V(empty1); P(empty2); 将取出的记录 存入缓冲区2 ； V(full2); ,put( ) while(1) P(full2); 从缓冲区2中 取出一条记录; V(empty2); 将取出的记录 打印出来； ,公

8、平的读写问题（作业7）,读者优先的读写问题中，当有读者不断到来时，写者可能会饥饿。 修改：进程的执行顺序按照到达顺序进行操作 即一个读者试图进行读操作时，如果有写者正在等待进行写操作，后续读者需要等待先到达的写者完成写操作后才能开始读操作。 思路：读者和写者的排队模型 排队模型是：读者和写者竞争 在排队过程中所有的进程都不可以加塞；只能按顺序排队； 但是队列中两个写者进程之间的读者进程可以一起进入到临界区,初始值： semaphore rmutex = 1, wrt = 1; int readcount = 0,Reader Process wait(rmutex); readcount+;

9、if (readcount = 1) wait(wrt); signal(rmutex); reading is performed wait(rmutex); readcount-; if (readcount = 0) signal(wrt); signal(rmutex):,Writer Process wait(wrt); writing is performed signal(wrt);,The Readers-Writers Problem读者写者问题 - 读者优先,What is the Readers-Writers problem? A data set is shared

10、among a number of concurrent processes Readers only read the data set; they do not perform any updates; Writers can both read and write. Problem allow multiple readers to read at the same time. Only one single writer can access the shared data at the same time. Shared datasemaphore mutex, wrt;Initia

11、llymutex = 1, wrt = 1, readcount = 0,初始值：mutex = 1, wrt = 1, readcount = 0,Reader Process wait(mutex); readcount+; if (readcount = 1) wait(wrt); signal(mutex); reading is performed wait(mutex); readcount-; if (readcount = 0) signal(wrt); signal(mutex):,Writer Process wait(wrt); writing is performed signal(wrt);,更为复杂的读者写者问题,写者优先的读者写者问题 课后作业8：写者优先的读者写者问题的同步机制实现。,初始值： semaphore wrt= 1, S=1; semaphore wmutex = 1, rmutex=1; int readcount = 0,writecount=0;,Writer() while(1) P(wmutex); writecount+; If(writecount=1) P(S); V(wmutex); P(wrt); 写文件； V(wrt); P(wmutex); writecount-; i