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

1、Silberschatz, Galvin and Gagne 2013Operating System Concepts 9th EditionChapter 5: Process Synchronization进进程同步程同步习题课习题课5.2Silberschatz, Galvin and Gagne 2013Operating System Concepts 9th Edition最简单的情况如何进行分析呢？本章作业2经典的生产者和消费者问题一个生产者 V.S. 一个消费者5.3Silberschatz, Galvin and Gagne 2013Operating System Con

2、cepts 9th EditionProducerwhile(1) produce ； wait(empty); put in buffer; signal(full);semaphore empty=1,full=0;Consumerwhile(1) wait(full); take out from buffer; signal(empty); consume5.4Silberschatz, Galvin and Gagne 2013Operating System Concepts 9th Edition一个生产者 V.S. 一个消费者 但缓冲区有n个复杂一些的情况如何进行分析呢？ 本章

3、作业35.5Silberschatz, Galvin and Gagne 2013Operating System Concepts 9th EditionProducerwhile(1) produce; wait(empty); put; signal(full); in=(in+1)%n;semaphore empty=n,full=0;Consumerwhile(1) wait(full); take; signal(empty); consume； out = （out+1)%n;Buffer bufn； int in=0,out=0;%使用循环缓冲级数5.6Silberschatz

4、, Galvin and Gagne 2013Operating System Concepts 9th Edition多个生产者 V.S. 多个消费者 n个缓冲区更为复杂的情况如何进行分析呢？本章作业35.7Silberschatz, Galvin and Gagne 2013Operating System Concepts 9th EditionProducerwhile(1) produce; wait(empty); wait（mutex1） put; in=(in+1)%n; signal（mutex1） signal(full); semaphore empty=n,full=0

5、，mutex1=1， mutex2=1;Consumerwhile(1) wait(full); wait（mutex2） take; out = （out+1)%n; signal（mutex2） signal(empty); consume；Buffer bufn； int in=0,out=0;%使用循环缓冲级数5.8Silberschatz, Galvin and Gagne 2013Operating System Concepts 9th EditionProcess Synchronization Example进进程同步例子程同步例子 作作业业4司机进程：REPEAT启动车辆正

6、常驾驶到站停车UNTIL 售票员进程：REPEAT关门售票开门UNTIL 同步要求：先关门，后开车 先停车，后开门5.9Silberschatz, Galvin and Gagne 2013Operating System Concepts 9th Edition解：解：nSemaphore close=0，open=0；driver( )/*司机司机*/ while(True) P(close);启启动车辆动车辆;正常行正常行车车;到站停到站停车车;V(open);Conductor( ) /*售票售票员员*/ while(True) 关关车门车门； ；V(close);售票售票;P(ope

7、n);开开车门车门;上下乘客上下乘客; 5.10Silberschatz, Galvin and Gagne 2013Operating System Concepts 9th Edition作作业业5n设有两个优先级相同的进程p1和p2如下。信号量S1和S2的初值均为0，试问P1和P2并发执行结束后，x、y、z的值各位多少？进进程程P1y = 1； ；y = y+2;V(S1);z = y+1;P(S2);y = z + y;进进程程P2x = 1;x = x +1;P(S1);x = x+y;V(S2);z=x+z;5.11Silberschatz, Galvin and Gagne 20

8、13Operating System Concepts 9th Edition作作业业5n设有两个优先级相同的进程p1和p2如下。信号量S1和S2的初值均为0，试问P1和P2并发执行结束后，x、y、z的值各位多少？进进程程P1y = 1； ；y = y+2;V(S1);z = y+1;P(S2);y = z + y;进进程程P2x = 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的最终值是： 9Y的最终值取决于P1和P2最后一行的执行顺序： 如果P2先执行完，则Y=12；如果P1先执行完，则Y=7；5.12Sil

9、berschatz, Galvin and Gagne 2013Operating System Concepts 9th Edition作作业业6 假定系统有3个并发进程get 、copy 和put共享缓冲器B1和B2。进程get负责从输入设备上读信息，每读出一条记录后放到B1中。进程copy从缓冲器B1中取出一条记录拷贝后存入B2。进程put取出B2中的记录打印输出。B1和B2每次只能存放一条记录。要求3个进程协调完成任务，使打印出来的与读入的记录个数、次序完全一样。请用记录型信号量写出并发程序。（北大1990年试题）解题思路：这是同步还是互斥呢？2个资源； 每个资源对应两个事件（空、满）

10、；5.13Silberschatz, Galvin and Gagne 2013Operating System Concepts 9th Edition 设置4个信号量，其中empty1对应空闲的缓冲区1，其初值为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(em

11、pty2);将取出的记录 存入缓冲区2 ；V(full2); put( ) while(1) P(full2);从缓冲区2中 取出一条记录; V(empty2);将取出的记录 打印出来； 5.14Silberschatz, Galvin and Gagne 2013Operating System Concepts 9th Edition公平的公平的读读写写问题问题（作（作业业7） ）n读读者者优优先的先的读读写写问题问题中，当有中，当有读读者不断到来者不断到来时时，写者可能会，写者可能会饥饿饥饿。 。n修改：修改：进进程的程的执执行行顺顺序按照到达序按照到达顺顺序序进进行操作行操作l即一个即

12、一个读读者者试图进试图进行行读读操作操作时时，如果有写者正在等待，如果有写者正在等待进进行写操作，行写操作，后后续读续读者需要等待先到达的写者完成写操作后才能开始者需要等待先到达的写者完成写操作后才能开始读读操作。操作。n思路：思路：读读者和写者的排者和写者的排队队模型模型n排队模型是：读者和写者竞争n在排队过程中所有的进程都不可以加塞；只能按顺序排队；n但是队列中两个写者进程之间的读者进程可以一起进入到临界区5.15Silberschatz, Galvin and Gagne 2013Operating System Concepts 9th Edition初始初始值值： ： semapho

13、re rmutex = 1, wrt = 1; int readcount = 0Reader Processwait(rmutex);readcount+;if (readcount = 1)wait(wrt);signal(rmutex); reading is performed wait(rmutex);readcount-;if (readcount = 0)signal(wrt);signal(rmutex):Writer Processwait(wrt); writing is performed signal(wrt);5.16Silberschatz, Galvin and

14、Gagne 2013Operating System Concepts 9th EditionThe Readers-Writers Problem读读者写者者写者问题问题 - 读读者者优优先先nWhat is the Readers-Writers problem? nA data set is shared among a number of concurrent processeslReaders only read the data set; they do not perform any updates;lWriters can both read and write.nProble

15、m allow multiple readers to read at the same time. Only one single writer can access the shared data at the same time.nShared datasemaphore mutex, wrt;Initiallymutex = 1, wrt = 1, readcount = 05.17Silberschatz, Galvin and Gagne 2013Operating System Concepts 9th Edition初始初始值值： ：mutex = 1, wrt = 1, re

16、adcount = 0Reader Processwait(mutex);readcount+;if (readcount = 1)wait(wrt);signal(mutex); reading is performed wait(mutex);readcount-;if (readcount = 0)signal(wrt);signal(mutex):Writer Processwait(wrt); writing is performed signal(wrt);5.18Silberschatz, Galvin and Gagne 2013Operating System Concept

17、s 9th Edition更更为为复复杂杂的的读读者写者者写者问题问题n写者写者优优先的先的读读者写者者写者问题问题n课课后作后作业业8：写者：写者优优先的先的读读者写者者写者问题问题的同步机的同步机制制实现实现。 。5.19Silberschatz, Galvin and Gagne 2013Operating System Concepts 9th Edition初始初始值值： ： semaphore wrt= 1, S=1; semaphore wmutex = 1, rmutex=1; int readcount = 0,writecount=0;Writer() while(1) P(wmutex); writecoun