第三章 进程互斥与同步.

Presentation on theme: "第三章 进程互斥与同步."— Presentation transcript:

1 第三章 进程互斥与同步

2 互斥-信号量机制 1965年由荷兰的Dijkstra提出 信号量( semaphore ) 是一种软件不忙等待法 信号量机制的类型
经典信号量(忙等待) 记录型信号量(使用不当可能会造成死锁) 信号量集(资源利用率低)

3 记录型信号量的定义 数据结构 typedef struct semaphore { int value; PCB * P;
} S; //定义信号量的结构体及变量S

4 P-V操作原语 P(S)操作原语 void P( struct semaphore S ) { S.value --;
if ( S.value < 0 ) block( S.P); //阻塞调用进程,在S.P中排队 } P操作的主要动作： ①s值减1； ②若相减结果>=0，则进程继续执行； ③若相减结果<0，则进程被封锁，并将它插入到该信号灯的等待队列之中，然后转进程调度程序。

5 P-V操作原语 V(S)操作原语 void V( struct semaphore S ) { S.value ++;
if ( S.value <= 0 ) wakeup( S.P); //唤醒S.P排队中某个进程 } V操作的主要动作： ①s值加1； ②若相加结果>0，则进程继续执行； ③若相加结果<=0，则从该信号灯的等待队列中移出一个进程，解除它的等待状态，然后返回本进程继续执行。

6 S.value的物理意义 S.value 用于表示资源数目或请求使用某一资源的进程个数的整形量.
S是与临界区内所使用的公用资源有关的信号量。S.value>0 表示可供并发进程使用的资源数。 P(S)操作时表示,表示进程请求分配一个该类资源,将对S.value减1,若S.value<0 表示资源已经分配完,此时|S.value|表示正在S.P队列中等待使用临界区的进程数 V(S)操作表示进程释放一个该类资源,S.value加1,若S.value<=0表示S.P队列中有进程等待分配该类资源,应唤醒其中的一个进程

7 用信号量机制实现N进程间的互斥 为N个进程设置一个互斥的信号量mutex, mutex.value为1(实现互斥)
进程进入临界区前用P(mutex)操作申请资源 进程退出临界区后用V(mutext)操作释放资源

8 struct semaphore mutex;
mutex.value=1; //初始化资源数量为1 cobegin void process1(void) { while( 1 ) { P(mutex); .....; //进程1访问临界资源 V(mutex); ......;//非临界区代码 } ...... void processN(void) .....; //进程N访问临界资源 coend

9 解决老问题 struct semaphore S = 1; // S.value = 1; P1: P( S ); R1=count;
R1=R1+1; count=R1; V( S ); P2: R2=count; R2=R2+1; count=R2;

10 进程同步 进程同步: 多个合作进程为了完成同一个任务,在执行速度上必须相互协调。 进程同步的例子 进程互斥与进程同步统称为进程同步
计算与打印的同步关系 Buffer C P 进程互斥与进程同步统称为进程同步 进程互斥实际上是进程同步的一种特殊情况,一个等待使资源的进程在得到占用资源的进程发出“释放资源”的信息后就可以使用该资源了。

11 互斥与同步的区别 互斥是进程间竞争共享资源的使用权,这种竞争无固定的必然关系。
同步是涉及共享资源的并发进程间有一种必然的依赖关系,即使没有进程在使用共享资源,尚未得到同步消息的进程仍不能去使用该资源。

12 用信号量机制解决进程同步 C P struct semaphore SC,SP=1,0; number x, y , buffer;
cobegin void CP( void ) //computer process { while ( 1 ){ x = computer(); //计算并将结果存于x P( SC ); //请求存数 buffer = x; V( SP ); //与打印进程同步 } void PP( void ) // print process { while( 1 ){ P( SP ); //请求取数 y=buffer; V( SC ); //与计算机进程同步 print y number; coend Buffer C P

13 用信号量机制解决前趋图问题[同步] 方法：
若图中存在结点S1指向结点S2的有向边，表示进程P1中的程序段S1应该先执行，而进程P2中的程序段S2后执行。设置一个信号量s,初值为0，将V(s)放在S1后面，而在S2前面先执行P(s)。 进程P1的语句序列为：S1; V(s) 进程P2的语句序列为：P(s); S2 S1 s S2

14 具有8个结点的前趋图。图中的前趋图中共有有向边10条，可设10个信号量，初值均为0；有8个结点，可设计成8个并发进程，具体描述如下：
S1 S2 S5 S6 S7 S8 a g e f b c d h i j S3 S4

15 Struct smaphore a,b,c,d,e,f,g,h,I,j=0,0,0,0,0,0,0,0,0,0
cobegin {S1; V(a); V(b); V(c);} {P(a); S2; V(d);} {P(b); S3; V(e); V(f);} {P(c); S4; V(g);} {P(d); P(e); S5; V(h);} {P(f); P(g); S6; V(i)} {P(h); P(i); S7; V(j);} {P(j); S8;} coend S1 S2 S5 S6 S7 S8 a g e f b c d h i j S3 S4

16 用信号量机制解决经典进程同步问题 生产者-消费者问题(Producer-Consumer) 哲学家进餐问题 读者-写者问题
一个数据集（如文件）如果被几个并行进程所共享，有些进程只要求读数据集内容，它称读者，而另一些进程则要求修改数据集内容，它称写者，几个读者可以同时读些数据集，而不需要互斥，但一个写者不能和其它进程（不管是写者或读者）同时访问些数据集，它们之间必须互斥。 … n-1 …. 2 1 P1 P2 P3 . Pk. C1 C2 C3 Cm

17 生产者-消费者问题 Producer-Consumer Problem(1/5)
生产者-消费者问题是最著名的同步问题，它描述一组生产者（P1 ……Pk）向一组消费者（C1……Cm）提供消息。它们共享一个有界缓冲池（bounded buffer pool）,生产者向其中投放消息，消费者从中取得消息，如下图所示。生产者-消费者问题是许多相互合作进程的一种抽象。 … n-1 …. 2 1 P1 P2 P3 . Pk. C1 C2 C3 Cm

18 Producer-Consumer Problem(2/5)
假定缓冲池中有n个缓冲区，每个缓冲区存放一个消息。由于缓冲池是临界资源，它只允许一个生产者投入消息，或者一个消费者从中取出消息。即生产者之间、生产者与消费者之间、消费者之间都必须互斥使用缓冲池。所以必须设置互斥信号量mutex，它代表缓冲池资源，它的数值为1。 … n-1 …. 2 1 P1 P2 P3 . Pk. C1 C2 C3 Cm

19 Producer-Consumer Problem(3/5)
与计算打印两进程同步关系相同，生产者和消费者二类进程P和C之间应满足下列二个同步条件： 只有在缓冲池中至少有一个缓冲区已存入消息后，消费者才能从中提取消息，否则消费者必须等待。 只有缓冲池中至少有一个缓冲区是空时，生产者才能把消息放入缓冲区，否则生产者必须等待。 为了满足第一个同步条件，设置一个同步信号量full，它代表的资源是缓冲区满，它的初始值为0，它的值为n时整个缓冲池满。这个资源是消费者类进程C所拥有，C进程可以申请该资源，对它施加P操作，而C进程的合作进程生产者进程P对它施加V操作。 同样为了满足第二个同步条件，设置另一个同步信号量empty，它代表的资源是缓冲区空，它的初始值为n，表示缓冲池中所有缓冲区空。

20 Producer-Consumer Problem(4/5)
信号量 full表可用缓冲区数量 信号量 empty表空缓冲区数量 设置整型变量:存入指针in 和 取出指针out in in in … n-1 …. 2 1 1 out out 互斥访问in的信号量s1 和互斥访问out的s2

21 Producer-Consumer Problem(5/5)
struct semaphore s1,s2,empty,full=1,1,n,0; message buffer[n]; int in , out = 0, 0 ; cobegin void produceri( void ) // i=1,2,...,k { message x ; while ( 1 ) { x = CreateNewMessage (); P( empty ); P( s1 ); buffer[ in ] = x; in = ( in +1 ) mod n; V( s1 ); V( full ) ; } } void consumerj( void ) // j=1,2,...,m { message y ; P( full ); P( s2 ); y = buffer[ out ] = ; out = ( out +1 ) mod n; V( s2 ); V( empty ) ; ConsumeMessage( y ); } coend

22 哲学家进餐问题(1/4) 哲学家进餐问题是典型的同步问题，是由Dijkstra提出并解决的。
问题描述5个哲学家，他们的生活方式是交替的思考和进餐。哲学家们公用一张圆桌，分别坐在周围的5张椅子上，圆桌上有5个碗和5支叉子，平时一个哲学家进行思考，饥饿时便试图取用其左、 右最靠近他的叉子，只有 他拿到两只叉子时才 能进餐，放下叉子又 继续思考。 显然叉子是临界资源

23 哲学家进餐问题(2/4) 思考: 当5个哲学家同时拿起其左边的叉子..... 一种解法
struct semaphore chopstick[5]={1,1,1,1,1}; 第i个哲学家的并发程序为 while ( 1 ){ think() ; P ( chopstick[i] ); //想拿左边的叉子 P ( chopstick[ (i+1) mod 5] ); //想拿右边的叉子 eat () ; V ( chopstick[i] ); //放下左边的叉子 V ( chopstick[ (i+1) mod 5] ); //放下右边的叉子 } 思考: 当5个哲学家同时拿起其左边的叉子.....

24 哲学家进餐问题(3/4) struct semaphore chopstick[5]={1,1,1,1,1};
struct semaphore count = 4; //最多允许四个人申请叉子 第i个哲学家的并发程序为 while ( 1 ){ think() ; P ( count ); P ( chopstick[i] ); //想拿左边的叉子 P ( chopstick[ (i+1) mod 5] ); //想拿右边的叉子 eat () ; V ( chopstick[i] ); //放下左边的叉子 V ( chopstick[ (i+1) mod 5] ); //放下右边的叉子 V ( count ); }

25 哲学家进餐问题(4/4) 其它解法 1 规定奇数号哲学家先申请拿他右边的叉子,然后现时申请拿左边的,而偶数号的则相反。
2 仅当哲学家左右两把叉子均可用时,才允许他拿叉子进餐,即左可两把叉子一起申请,而不是分两次申请,需要一个特殊的P操作。

26 读者-写者问题 一个文件可能被多个进程共享，为了保证读写的正确性和文件的一致性，系统要求，当有读者进程读文件时，不允许任何写者进程写，但允许多读者同时读；当有写者进程写时，不允许任何其它写者进程写，也不允许任何读者进行读。

27 struct semaphore x , wsem = 1,1; // x 实现readcount的互斥, wsem实现写/读的互斥
int readcout = 0; // 读者计数量 cobegin void readeri( void ) { while ( 1 ) { P( x ); if ( readcount == 0 ) P( wsem ); //仅我一人,禁止写 readcount ++; V ( x ); reading () ; P ( x ); readcount - - ; V ( wsem ); //最后一人,允许写 V ( x ); } } void writerj( void ) { while ( 1 ){ P ( wsem ); writing(); V ( wsem ); coend (读者优先) 写者挨饿现象

28 写者优先 只要有写者申请写操作,就不允许新的读者访问数据数据 增设变量 信号量rsem:在有写者操作时,禁止所有读者进行操作
变量writecount:用于控制信号量rsem的设置,当writecount为1时,做P(rsem)而当为0时作V(rsem) 信号量y:对写者共享的变量writecount进行互斥控制 信号量z:只允许rsem上有一个读者排队,其余读者在z上排队

29 作业-1 图书馆阅览室问题 问题描述：假定阅览室最多可同时容纳100个人阅读，读者进入时，必须在阅览室门口的一个登记表上登记，内容包括姓名、座号等，离开时要撤掉登记内容。用P、V操作描述读者进程的同步算法。

30 作业-2 理发师问题 问题描述：一个理发店由一个有几张椅子的等候室和一个放有一张理发椅的理发室组成。若没有要理发的顾客，则理发师就去睡觉；若一顾客走进理发店且所有的椅子都被占用了，则该顾客就离开理发店；若理发师正在为人理发，则该顾客就找一张空椅子坐下等待；若理发师在睡觉，则顾客就唤醒他，设计一个协调理发师和顾客的程序。

31 作业-3 吃水果问题 问题描述：桌上有一只盘子，每次只能放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放桔子，儿子专等吃盘里的桔子，女儿专等吃盘里的苹果。只要盘子空，则爸爸或妈妈可向盘中放水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出，请给出四人之间的同步关系，并用PV操作实现四人正确活动的程序。

32 作业4 某小型超市可容纳50个人同时购物,入口处备有篮子,每个购物者可拿一只篮子入内购物,在出口处结账,并归还篮子(出入口禁止多人同时通过)。试用P-V操作写出购物者的同步算法。