《进程互斥与同步课件》由会员分享，可在线阅读，更多相关《进程互斥与同步课件（32页珍藏版）》请在金锄头文库上搜索。
1、第三章 进程互斥与同步,互斥-信号量机制,1965年由荷兰的Dijkstra提出 信号量( semaphore ) 是一种软件不忙等待法 信号量机制的类型 经典信号量(忙等待) 记录型信号量(使用不当可能会造成死锁) 信号量集(资源利用率低),记录型信号量的定义,数据结构 typedef struct semaphore int value; PCB * P; S; /定义信号量的结构体及变量S,P-V操作原语,P(S)操作原语 void P( struct semaphore S ) S.value -; if ( S.value =0，则进程继续执行； 若相减结果0，则进程被封锁，并将它插
2、入到该信号灯的等待队列之中，然后转进程调度程序。,P-V操作原语,V(S)操作原语 void V( struct semaphore S ) S.value +; if ( S.value 0，则进程继续执行； 若相加结果=0，则从该信号灯的等待队列中移出一个进程，解除它的等待状态，然后返回本进程继续执行。,S.value的物理意义,S.value 用于表示资源数目或请求使用某一资源的进程个数的整形量. S是与临界区内所使用的公用资源有关的信号量。S.value0 表示可供并发进程使用的资源数。 P(S)操作时表示,表示进程请求分配一个该类资源,将对S.value减1,若S.value0 表示
3、资源已经分配完,此时|S.value|表示正在S.P队列中等待使用临界区的进程数 V(S)操作表示进程释放一个该类资源,S.value加1,若S.value=0表示S.P队列中有进程等待分配该类资源,应唤醒其中的一个进程,用信号量机制实现N进程间的互斥,为N个进程设置一个互斥的信号量mutex, mutex.value为1(实现互斥) 进程进入临界区前用P(mutex)操作申请资源 进程退出临界区后用V(mutext)操作释放资源,struct semaphore mutex; mutex.value=1; /初始化资源数量为1 cobegin void process1(void) whil
4、e( 1 ) P(mutex); .; /进程1访问临界资源 V(mutex); .;/非临界区代码 . void processN(void) while( 1 ) P(mutex); .; /进程N访问临界资源 V(mutex); .;/非临界区代码 coend,解决老问题,struct semaphore S = 1; / S.value = 1; P1: P( S ); R1=count; R1=R1+1; count=R1; V( S ); P2: P( S ); R2=count; R2=R2+1; count=R2; V( S );,进程同步,进程同步: 多个合作进程为了完成同一
5、个任务,在执行速度上必须相互协调。 进程同步的例子 计算与打印的同步关系,进程互斥与进程同步统称为进程同步 进程互斥实际上是进程同步的一种特殊情况,一个等待使资源的进程在得到占用资源的进程发出“释放资源”的信息后就可以使用该资源了。,互斥与同步的区别,互斥是进程间竞争共享资源的使用权,这种竞争无固定的必然关系。 同步是涉及共享资源的并发进程间有一种必然的依赖关系,即使没有进程在使用共享资源,尚未得到同步消息的进程仍不能去使用该资源。,用信号量机制解决进程同步,struct semaphore SC,SP=1,0; number x, y , buffer; cobegin void CP( v
6、oid ) /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,用信号量机制解决前趋图问题同步,方法： 若图中存在结点S1指向结点S2的有向边，表示进程P1中的程序段S1应该先执行，而进程P2中的程序段S2后执行。设置一个信号量s,初值为
7、0，将V(s)放在S1后面，而在S2前面先执行P(s)。 进程P1的语句序列为：S1; V(s) 进程P2的语句序列为：P(s); S2,S1,S2,s,具有8个结点的前趋图。图中的前趋图中共有有向边10条，可设10个信号量，初值均为0；有8个结点，可设计成8个并发进程，具体描述如下：,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(
8、g);S6;V(i) P(h);P(i);S7;V(j); P(j);S8; coend,用信号量机制解决经典进程同步问题,生产者-消费者问题(Producer-Consumer) 哲学家进餐问题 读者-写者问题 一个数据集（如文件）如果被几个并行进程所共享，有些进程只要求读数据集内容，它称读者，而另一些进程则要求修改数据集内容，它称写者，几个读者可以同时读些数据集，而不需要互斥，但一个写者不能和其它进程（不管是写者或读者）同时访问些数据集，它们之间必须互斥。,生产者-消费者问题Producer-Consumer Problem(1/5),生产者-消费者问题是最著名的同步问题，它描述一组生产者
9、（P1 Pk）向一组消费者（C1Cm）提供消息。它们共享一个有界缓冲池（bounded buffer pool）,生产者向其中投放消息，消费者从中取得消息，如下图所示。生产者-消费者问题是许多相互合作进程的一种抽象。,Producer-Consumer Problem(2/5),假定缓冲池中有n个缓冲区，每个缓冲区存放一个消息。由于缓冲池是临界资源，它只允许一个生产者投入消息，或者一个消费者从中取出消息。即生产者之间、生产者与消费者之间、消费者之间都必须互斥使用缓冲池。所以必须设置互斥信号量mutex，它代表缓冲池资源，它的数值为1。,Producer-Consumer Problem(3/5
10、),与计算打印两进程同步关系相同，生产者和消费者二类进程P和C之间应满足下列二个同步条件： 只有在缓冲池中至少有一个缓冲区已存入消息后，消费者才能从中提取消息，否则消费者必须等待。 只有缓冲池中至少有一个缓冲区是空时，生产者才能把消息放入缓冲区，否则生产者必须等待。 为了满足第一个同步条件，设置一个同步信号量full，它代表的资源是缓冲区满，它的初始值为0，它的值为n时整个缓冲池满。这个资源是消费者类进程C所拥有，C进程可以申请该资源，对它施加P操作，而C进程的合作进程生产者进程P对它施加V操作。 同样为了满足第二个同步条件，设置另一个同步信号量empty，它代表的资源是缓冲区空，它的初始值为
11、n，表示缓冲池中所有缓冲区空。,Producer-Consumer Problem(4/5),信号量 full表可用缓冲区数量 信号量 empty表空缓冲区数量 设置整型变量:存入指针in 和 取出指针out,1,0,0,互斥访问in的信号量s1 和互斥访问out的s2,Producer-Consumer Problem(5/5),struct semaphore s1,s2,empty,full=1,1,n,0; message buffern; int in , out = 0, 0 ; cobegin void produceri( void ) / i=1,2,.,k message
12、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 ; while ( 1 ) P( full ); P( s2 ); y = buffer out = ; out = ( out +1 ) mod n; V( s2 ); V( empty ) ; ConsumeMessage( y ); coend,哲学家进餐问题(1
13、/4),哲学家进餐问题是典型的同步问题，是由Dijkstra提出并解决的。 问题描述5个哲学家，他们的生活方式是交替的思考和进餐。哲学家们公用一张圆桌，分别坐在周围的5张椅子上，圆桌上有5个碗和5支叉子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的叉子，只有他拿到两只叉子时才能进餐，放下叉子又继续思考。 显然叉子是临界资源,哲学家进餐问题(2/4),一种解法 struct semaphore chopstick5=1,1,1,1,1; 第i个哲学家的并发程序为 while ( 1 ) think() ; P ( chopsticki ); /想拿左边的叉子 P ( chopsti
14、ck (i+1) mod 5 ); /想拿右边的叉子 eat () ; V ( chopsticki ); /放下左边的叉子 V ( chopstick (i+1) mod 5 ); /放下右边的叉子 ,思考: 当5个哲学家同时拿起其左边的叉子.,哲学家进餐问题(3/4),struct semaphore chopstick5=1,1,1,1,1; struct semaphore count = 4; /最多允许四个人申请叉子 第i个哲学家的并发程序为 while ( 1 ) think() ; P ( count ); P ( chopsticki ); /想拿左边的叉子 P ( chop
15、stick (i+1) mod 5 ); /想拿右边的叉子 eat () ; V ( chopsticki ); /放下左边的叉子 V ( chopstick (i+1) mod 5 ); /放下右边的叉子 V ( count ); ,哲学家进餐问题(4/4),其它解法 1 规定奇数号哲学家先申请拿他右边的叉子,然后现时申请拿左边的,而偶数号的则相反。 2 仅当哲学家左右两把叉子均可用时,才允许他拿叉子进餐,即左可两把叉子一起申请,而不是分两次申请,需要一个特殊的P操作。,读者-写者问题,一个文件可能被多个进程共享，为了保证读写的正确性和文件的一致性，系统要求，当有读者进程读文件时，不允许任何
16、写者进程写，但允许多读者同时读；当有写者进程写时，不允许任何其它写者进程写，也不允许任何读者进行读。,(读者优先),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 - - ; if ( readcount = 0 ) V ( wsem ); /最后一人,允许写 V ( x ); void writerj( void ) while ( 1 ) P ( wsem ); writi
