第4讲、操作系统-经典的IPC问题

第二章进程与线程--经典的IPC问题

《操作系统》

四、读写者问题目录二、生产者消费者问题三、哲学家进餐问题一、信号量四、读写者问题目录二、生产者消费者问题三、哲学家进餐问题一、信号量Page

4三、进程间通信2.3进程间通信内容回顾：忙检测存在的问题。在用户空间通过标识位的方式实现互斥/同步操作，由于进程间的切换是由OS控制的，有可能会因为切换不当，引发错误。忙等的方式会浪费CPU的计算资源。方法：采用信号量的方式，由OS实现互斥/同步操作。Page

5三、进程间通信2.3进程间通信主要设计思想：如果当前进程无法进入临界区（当前不适合执行对共享资源的操作代码），则由OS帮助，进入阻塞状态，放弃CPU。两个通信原语：sleep与wakeupsleep:引起调用进程阻塞的系统调用wakeup：唤醒指定的进程通信原语的实现：信号量Page

6三、进程间通信2.3进程间通信信号量：由E.W.Dijkstra于1965年提出的方法。使用一个整型变量来累计唤醒次数。主要操作：down():检查其值是否大于0，如大于0,则减1并继续操作，否则，进程阻塞。Up():对信号量执行的值增加1，如果有进程在此信号量上睡眠，则唤醒一个进程。Page

7三、进程间通信2.3进程间通信信号量：要求：原子操作：一组相关联的操作要么都不间断的执行，要么都不执行。表示方法：P（）/V（），wait()/signal()问题：信号量如何实现？如何保证其操作的原子性？Page

8三、进程间通信2.3进程间通信互斥量：保证进程的串行化操作对于两个并发进程，互斥信号量的值域(?)若ＭＵＴＥＸ＝1表示没有进程进入临界区若ＭＵＴＥＸ＝0表示有一个进程进入临界区若ＭＵＴＥＸ＝-1表示一个进程进入临界区，另一个进程等待进入。Page

9信号量小结2.3进程间通信信号量：实现进程间的同步例如：先执行进程A，A结束后执行进程BSemaphoreSYN=0;ProcessA:Run();Up(SYN);ProcessB:Down(SYN);Run();Page

10信号量小结2.3进程间通信信号量：实现进程间的互斥例如：进程A与进程B同时想利用同一台打印机打印文件SemaphoreMUTEX=1;ProcessAorB:Down(&MUTEX);printFile();Up(&MUTEX);Page

11信号量小结2.3进程间通信信号量：主要用于进程间的控制交互的信息比较简单对用户不透明，信号量的使用错误可能会导致很严重的问题。想法：是否可以设计一种高级同步机制，来封装复杂的信号量机制，用户在编程时不用考虑它？Page

122.3进程间通信方法一：管程（monitor）是一个由过程、变量及数据结构等组成的一个集合，它们组成一个特殊的模块或软件包。进程可以在任可需要的时候调用管程中的过程。任一时刻管理中只能有一个活跃进程。进入管程的互斥是由编译器负责的。管程是通过编程语言实现的。管程是一种语言概念，而C语言并不支持它。请注意。三、进程间通信Page

13三、信号量小结2.3进程间通信方法二：消息机制与管程最大的区别是它是系统调用而不是语言成分，即是操作系统提供的功能。主要有两条通信原语实现：send(destination,&mesasage);receive(sourcde,&message);典型的实现方式socket网络通信。四、读写者问题目录二、生产者消费者问题三、哲学家进餐问题一、信号量Page

15一、生产者-消费者问题2.3.5信号量问题指环王下载进程播放进程本地数据缓冲区Page

16一、生产者-消费者问题2.3.5信号量基本类型一个有限空间的共享缓冲区，负责存放货物一个生产者向缓冲区中放物品，缓冲区满则不能放一个消费者从缓冲区中拿物品，缓冲区空则不能拿Page

17一、生产者-消费者问题2.3.5信号量问题分析生产者与消费者之间的同步操作，生产者放时，消息者不能拿，反之亦然。Page

18一、生产者-消费者问题2.3.5信号量Semaphoreempty=N,full=0;voidproducer(void){intitem;while(TRUE){item=produce_item();down(&empty);insert_item(item);up(&full);}}voidconsumer(void){intitem;while(TRUE){down(&full);item=get_item(item);up(&empty);consume_item(item);}}Page

19一、生产者-消费者问题2.3.5信号量扩展类型一个有限空间的共享缓冲区，负责存放货物多个生产者向缓冲区中放物品，缓冲区满则不能放多个消费者从缓冲区中拿物品，缓冲区空则不能拿Page

20一、生产者-消费者问题2.3.5信号量问题分析多个生产者放时，货物放在什么地方？多个消费者拿时，拿哪一个货物？办法：多个生产者，一个一个放。多个消费者，一个一个拿。Page

21一、生产者-消费者问题2.3.5信号量Semaphoreempty=N,full=0,mutex=1;voidproducer(void){intitem;while(TRUE){item=produce_item();down(&empty);down(&mutex);insert_item(item);up(&mutex);up(&full);}}voidconsumer(void){intitem;while(TRUE){down(&full);down(&mutex);item=get_item(item);down(&mutex);up(&empty);consume_item(item);}}Page

22一、生产者-消费者问题2.3.5信号量Semaphoreempty=N,full=0,mutex=1;voidproducer(void){intitem;while(TRUE){item=produce_item();down(&empty);down(&mutex);insert_item(item);up(&mutex);up(&full);}}voidconsumer(void){intitem;while(TRUE){down(&full);down(&mutex);item=insert_item(item);down(&mutex);up(&empty);consume_item(item);}}down(&empty)与down(&mutex)的顺序是否可以交换？Page

23一、生产者-消费者问题2.3.5信号量Semaphoreempty=N,full=0,mutex=1;voidproducer(void){intitem;while(TRUE){item=produce_item();down(&empty);down(&mutex);insert_item(item);up(&mutex);up(&full);}}voidconsumer(void){intitem;while(TRUE){down(&full);down(&mutex);item=insert_item(item);down(&mutex);up(&empty);consume_item(item);}}up(&empty)与up(&mutex)的顺序是否可以交换？Page

24一、生产者-消费者问题2.3.5信号量Semaphoreempty=N,full=0,mutex=1;voidproducer(void){intitem;while(TRUE){item=produce_item();down(&empty);down(&mutex);insert_item(item);up(&mutex);up(&full);}}voidconsumer(void){intitem;while(TRUE){down(&full);down(&mutex);item=insert_item(item);down(&mutex);up(&empty);consume_item(item);}}四、读写者问题目录二、生产者消费者问题三、哲学家进餐问题一、信号量Page

26二、哲学家就餐问题2.5.1信号量问题描述有五个哲学家围坐在一圆桌旁，每人面前有一盘通心粉，每两人之间放一只叉子。每个哲学家的行为是思考，感到饥饿，然后吃通心粉为了吃通心粉，每个哲学家必须拿到两只叉子，并且每个人只能直接从自己的左边或右边去取叉子Page

27二、哲学家就餐问题#defineN5voidphilosopher(inti){while(TRUE){think();take_fork(i);take_fork((i+1)%N);eat();put_fork(i);put_fork((i+1)%N);}}注：take_fork,put_fork,是对信号量操作;本算法有什么问题？2.5.1哲学家就餐问题Page

28二、哲学家就餐问题2.5.1哲学家就餐问题问题分析如果每个哲学家只拿到一把叉子，则会出现“饿死”的现象。解决办法：问题的根源在于并发执行引起的错误，可以把拿叉子的操作串行化。Page

29#defineN5semaphoremutex=1;voidphilosopher(inti){while(TRUE){think();

down(&mutex);take_fork(i);take_fork((i+1)%N);eat();put_fork(i);put_fork((i+1)%N);

up(&mutex);}}注：take_fork,put_fork,是对信号量操作;本算法有什么问题？二、哲学家就餐问题2.5.1哲学家就餐问题Page

30#defineN5semaphoremutex=N-1;voidphilosopher(inti){while(TRUE){think();down(&mutex);take_fork(i);take_fork((i+1)%N);eat();put_fork(i);put_fork((i+1)%N);up(&mutex);}}注：take_fork,put_fork,是对信号量操作;二、哲学家就餐问题2.5.1哲学家就餐问题本算法有什么问题？Page

31#defineN5#defineLEFT(i+N-1)%N#defineRIGHT(i+1)%N#defineTHINKING0#defineHUNGRY1#defineEATING2intstate[N];semaphores[N],mutex=1;voidphilosopher(inti){while(TRUE){think();take_forks(i);eat();put_forks(i);}}二、哲学家就餐问题voidtake_fork(inti){down(&mutex);state[i]=HUNGRY;test(i);up(&mutex);down(&s[i]);}voidput_fork(inti){down(&mutex);state[i]=THINKING;test(LEFT);test(RIGHT);up(&mutex);down(&s[i]);}voidtest(i){if(state[i]==HUNGRY&&state[LEFT]!=EATING&&state[RIGHT]!=EATING){state[i]=EATING;up(&s[i]);}}四、读写者问题目录二、生产者消费者问题三、哲学家进餐问题一、信号量Page

33问题来源1971年，由Courtois等人为数据库访问建立的模型多个进程可以同时读数据库中的数据。为了保持数据的一致性，当某一个进程在改写数据库时，其它进程不允许访问数据库。三、读写者问题2.5.2读写者问题Page

34问题描述对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个同时读三、读写者问题2.5.2读写者问题Page

35问题分析“读-写”互斥“写-写”互斥“读-读”允许三、读写者问题2.5.2读写者问题Page

36读-写者问题的信号量解法互斥关系分析读者和写者不能同时进入共享数据区多个写者不能同时进入共享数据区多个读者可以同时进入共享数据区同步关系分析读者进入缓冲区，写者必须等待写者进入缓冲区，读者必须等待三、读写者问题2.5.2读写者问题Page

37读-写者问题的信号量解法读者优先：一旦有读者进入，则后续读者均可进入写者优先：只要有写者等待，则后续读者必须等待合理顺序：读者在先来的写者之后三、读写者问题2.5.2读写者问题Page

38读者优先的信号量解法三、读写者问题2.5.2读写者问题Data读者读者写者读者Page

39三、读写者问题2.5.2读写者问题semaphorewrt=1,mutex=1;readcount=0;writer(){wait(wrt);//Writingisdonesignal(wrt);}reader(){ wait(mutex); readcount++; if(readcount==1) { wait(wrt); } signal(mutex); //Dothereading wait(mutex); readcount--; if(readcount==0) { signal(wrt); } signal(mutex);}请问上述算法有什么问题？Page

40读者优先的信号量解法当读者的读取时间及到达速率较快且是一个平滑的流时，有可能会出现写者“饿死”的情况。如：读者平均操作时间为2秒，平均1秒到达一个，写者平均操作时间为5秒。三、读写者问题2.5.2读写者问题Page

41写者优先的信号量解法三、读写者问题2.5.2读写者问题Data写者读者写者读者Page

42三、读写者问题intreadcount=0,writecount=0;semaphoremutex_1=1,mutex_2=1,mutex_3=1,w=1,r=1;WRITERP(mutex_2);writecount=writecount+1;if(writecount==1){P(r)；}V(mutex_2);P(w);writingisperformed;V(w);P(mutex_2);writecount=writecount-1;if(writecount==0){V(r)；}V(mutex_2);READERP(mutex_3);P(r);P(mutex_1);readcount=readcount+1;if(readcount==1){P(W);}V(mutex_1);V(r);