《经典IPC问题》PPT课件.ppt

2.3.4信号量（Semaphore）,1965年由著名的荷兰计算机科学家Dijkstra提出，其基本思路是用一种新的变量类型（semaphore）来记录当前可用资源的数量。有两种实现方式：1）semaphore的取值必须大于或等于0。0表示当前已没有空闲资源，而正数表示当前空闲资源的数量；2）semaphore的取值可正可负，负数的绝对值表示正在等待进入临界区的进程个数。信号量是由操作系统来维护的，用户进程只能通过初始化和两个标准原语（P、V原语）来访问。初始化可指定一个非负整数，即空闲资源总数。,P、V原语作为操作系统内核代码的一部分，是一种不可分割的原子操作（atomicaction），在其运行时，不会被时钟中断所打断；P、V原语包含有进程的阻塞和唤醒机制，因此在进程等待进入临界区时不会浪费CPU时间；,P原语：P是荷兰语Proberen（测试）的首字母。申请一个空闲资源（把信号量减1），若成功，则退出；若失败，则该进程被阻塞；V原语：V是荷兰语Verhogen（增加）的首字母。释放一个被占用的资源（把信号量加1），如果发现有被阻塞的进程，则选择一个唤醒之。,信号量和P、V原语的实现,Windows2000CreateSemaphore（创建信号量）WaitForSingleObject（P操作）ReleaseSemaphore（V操作）COS-IIosSemCreate（创建信号量）osSemPend（P操作）osSemPost（V操作）,利用信号量来实现进程互斥,intcount;/共享变量（临界资源）semaphoremutex；/互斥信号量，初始化为?,2.3.5进程的同步,进程间的同步是指多个进程中发生的事件存在某种时序关系，因此在各个进程之间必须协同合作，相互配合，使各个进程按一定的速度执行，以共同完成某一项任务。,同步：合作。互斥：竞争。只考虑基于信号量的同步问题。,如何实现A先执行，然后B执行？,信号量S初始值为？,while(1).A；V(S);.,进程P1,S初始值为1,while(1).P(S)；B;.,进程P2,【例子1】合作进程的执行次序用进程流图来描述各进程合作完成某一任务的次序，其规则如下：,用信号量及P、V操作来描述左图1、说明进程的同步关系进程P1、P2可并行执行，P3的执行必须等待P1、P2都完成后才能开始执行。几个同步关系？,2、设置信号量，说明含义、初值。S13=0表示进程P1尚未执行完成；S23=0表示进程P2尚未执行完成；,main()/均初始化为0semaphoreS13,S23;cobeginP1;P2;P3;coend,3.写出程序描述,【例子2】司机与售票员,while(上班时间)发动汽车；正常运行；到站停车；,while(上班时间)关闭车门；售票；打开车门；,公车司机,售票员,1、说明进程的同步关系只有关闭车门以后，才能启动汽车；只有停车以后，才能打开车门。,semaphoreS_DoorClose；/初始为0semaphoreS_Stop;/初始为0,2、设置信号量，说明含义、初值。,3.写出程序描述,【例子3】共享缓冲区的合作进程的同步,设有一个缓冲区buffer，大小为一个字节。Compute进程不断产生字符，送buffer，Print进程从buffer中取出字符打印。如不加控制，会出现多种打印结果，这取决于这两个进程运行的相对速度。在这众多的打印结果中，只有Compute和Print进程的运行刚好匹配的一种是正确的，其它均为错误。,while(计算未完成)得到一个计算结果;将数据送到缓冲区；,Compute,while(打印未完成)从缓冲区中取一数据；打印该数据；,Print,正确：“ABCD”错误：“BB”错误：“AA”,“ABCD”,1.问题分析，弄清楚同步关系：要保证打印结果的正确，Compute和Print进程必须遵循以下同步规则：当Compute把数据送入buffer后，Print才能从buffer中取，否则它必须等待（先存后取）；当Print从buffer取走数据后，Compute才能将新数据送buffer，否则也须等待（先取后存）,讨论,一个信号量是否可行？,semaphoreS_Buffer；/缓冲区是否有空间，初值1semaphoreS_Data;/是否有数据需打印，初值0,2.设置信号量，说明含义、初值。,2.4经典的IPC问题,生产者消费者问题哲学家就餐问题读者写者问题,用信号量来解决，主要问题：如何选择信号量，如何安排P、V原语的顺序。,2.4.1生产者消费者问题,两个进程（生产者和消费者）共享一个公有的、固定大小的缓冲区，生产者不断地制造产品，并把它放入缓冲区，而消费者不断地把产品取出来，并且使用它。要求这两个进程相互协调，正确地完成各自的工作。,问题描述,生产消费者问题,消费者,问题分析,对于生产者进程：制造一个产品，当要送入缓冲区时，要检查缓冲区是否有空位，若是，才可将产品送入缓冲区，并在必要时通知消费者；否则等待；对于消费者进程：当它去取产品时，先要检查缓冲区中是否有产品可取，若有，则取走一个，并在必要时通知生产者；否则等待。这种相互等待，并互通信息就是典型的进程同步。同时，缓冲区是个临界资源，因此，各个进程在使用缓冲区的时候，还有一个互斥的问题。,semaphoreS_Buffer_Num;/空闲的缓冲区个数，/初值为NsemaphoreS_Product_Num;/缓冲区当中的产品个/数，初值为0semaphoreS_Mutex;/用于互斥访问的信号/量，初值为1,信号量的定义,main()cobeginproducer();consumer();coend,voidproducer(void)intitem;while(TRUE)item=produce_item();/制造一个产品P(S_Buffer_Num);/是否有空闲缓冲区P(S_Mutex);/进入临界区insert_item(item);/产品放入缓冲区V(S_Mutex);/离开临界区V(S_Product_Num);/新增了一个产品,生产者进程,voidconsumer(void)intitem;while(TRUE)P(S_Product_Num);/缓冲区中有无产品P(S_Mutex);/进入临界区item=remove_item()/从缓冲区取产品V(S_Mutex);/离开临界区V(S_Buffer_Num);/新增一个空闲缓冲区consume_item(item);/使用该产品,消费者进程,Why互斥？,voidconsumer(void)intitem;while(TRUE)P(S_Product_Num);P(S_Mutex);item=remove_item()consume_item(item);V(S_Mutex);V(S_Buffer_Num);,消费者进程,voidproducer(void)intitem;while(TRUE)P(S_Buffer_Num);P(S_Mutex);item=produce_item();insert_item(item);V(S_Mutex);V(S_Product_Num);,生产者进程,2.4.2哲学家就餐问题,1965年，由Dijkstra提出并解决，后来逐渐成为该领域的一个经典问题，或者说，是一块试金石，用来试验新的进程同步方法的优劣。,五个哲学家围坐在一张圆桌旁，每个哲学家面前都摆着一大盘意大利面条，面条非常滑，所以每个哲学家都需要两把叉子才能进餐，在相邻两个盘子之间，只有一把叉子。桌面的布局见右图。,问题描述,本图摘自“ModernOperatingSystems”,0,1,2,3,4,0,1,2,3,4,每个哲学家的动作只有两种：进餐和思考。当一个哲学家感到饥饿时，他试图去获得他左边和右边的两把叉子（一次取一把，顺序无关），然后才能开始进餐。吃完以后，他需要把两把叉子放回原处，然后继续思考。问题是：如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐，也不出现有人永远拿不到叉子。,问题描述（续）,方案1,#defineN5/哲学家个数voidphilosopher(inti)/哲学家编号：04while(TRUE)think();/哲学家在思考take_fork(i);/去拿左边的叉子take_fork(i+1)%N);/去拿右边的叉子eat();/吃面条中.put_fork(i);/放下左边的叉子put_fork(i+1)%N);/放下右边的叉子,不正确，可能导致死锁。,方案2,while(1)/去拿两把叉子take_fork(i);/去拿左边的叉子if(fork(i+1)%N)/右边叉子还在吗take_fork(i+1)%N);/去拿右边的叉子break;/两把叉子均到手else/右边叉子已不在put_fork(i);/放下左边的叉子wait_some_time();/等待一会儿,对拿叉子的过程进行了改进，但仍不正确,方案3,while(1)/去拿两把叉子take_fork(i);/去拿左边的叉子if(fork(i+1)%N)/右边叉子还在吗take_fork(i+1)%N);/去拿右边的叉子break;/两把叉子均到手else/右边叉子已不在put_fork(i);/放下左边的叉子wait_random_time();/等待随机长时间,等待时间随机变化。可行，但非万全之策,方案4,semaphoremutex/互斥信号量，初值1voidphilosopher(inti)/哲学家编号i：04while(TRUE)think();/哲学家在思考P(mutex);/进入临界区take_fork(i);/去拿左边的叉子take_fork(i+1)%N);/去拿右边的叉子eat();/吃面条中.put_fork(i);/放下左边的叉子put_fork(i+1)%N);/放下右边的叉子V(mutex);/退出临界区,互斥访问。正确，但每次只允许一人进餐,方案4的缺点：它把就餐（而不是叉子）看成是必须互斥访问的临界资源，因此会造成（叉子）资源的浪费。从理论上说，如果有五把叉子，应允许两个不相邻的哲学家同时进餐。,S1思考中S2进入饥饿状态；S3如果左邻居或右邻居正在进餐，等待；否则转S4S4拿起两把叉子；S5吃面条S6放下左边的叉子；S7放下右边的叉子；S8新的一天又开始了，转S1,哲学家就餐问题的解答,指导原则：要么不拿，要么就拿两把叉子。,S1思考中S2进入饥饿状态；S3如果左邻居或右邻居正在进餐，进入阻塞状态；否则转S4S4拿起两把叉子；S5吃面条S6放下左边的叉子，看看左邻居现在能否进餐（饥饿状态、两把叉子都在），若能则唤醒之；S7放下右边的叉子，看看右邻居现在能否进餐，若能，唤醒之；S8新的一天又开始了，转S1,指导原则：不能浪费CPU时间；进程间相互通信。,必须有一个数据结构，来描述每个哲学家的当前状态；该数据结构是一个临界资源，各个哲学家对它的访问应该互斥地进行进程互斥；一个哲学家吃饱后，可能要唤醒它的左邻右舍，两者之间存在着同步关系进程同步；,数据结构的定义,#defineN5/哲学家个数#defineLEFT(i+N-1)%N/第i个哲学家的左邻居#defineRIGHT(i+1)%N/第i个哲学家的右邻居#defineTHINKING0/思考状态#defineHUNGRY1/饥饿状态#defineEATING2/进餐状态intstateN;/记录每个人的状态semaphoremutex;/互斥信号量，初值1semaphoresN;/每人一个信号量，0,voidphilosopher(inti)/i的取值：0到N1while(TRUE)/封闭式开发，一直循环think();/思考中take_forks(i);/拿到两把叉子或被阻塞eat();/吃面条中put_forks(i);/把两把叉子放回原处,函数philosopher的定义,/功能：要么拿到两把叉子，要么被阻塞起来。voidtake_forks(inti)/i的取值：0到N1P(mutex);/进入临界区statei=HUNGRY;/我饿了！test(i);/试图拿两把叉子V(mutex);/退出临界区P(si);/没有叉子便阻塞,函数take_forks的定义,voidtest(inti)/i的取值：0到N1if(statei=HUNGRY/第i人可以吃饭了,函数test的定义,/功能：把两把叉子放回原处，并在需要的时候，/去唤醒左邻右舍。voidput_forks(inti)/i的取值：0到N1P(mutex);/进入临界区statei=THINKING;/交出两把叉子test(LEFT);/看左邻居能否进餐test(RIGHT);/看右邻居能否进餐V(mutex);/退出临界区,函数put_forks的定义,2.4.3读者写者问题,在一个航空定票系统当中，有很多个竞争的进程想要访问（读、写）系统的数据库。访问规则是：在任何时候，可以允许多个进程同时来读，但如果有一个进程想要更新(写)该数据库，则其他的任何进程都不能访问，包括读者和写者。问题是：怎么样来编程实现读者和写者。,问题描述,问题分析,任何时候“写者”最多只允许一个，而“读者”可以有多个：“读写”是互斥的；“写写”是互斥的；“读读”是允许的；,基于读者优先策略的方法,假设读者来：1）若有其它读者在读，则不论是否有写者在等，新读者都可以读（读者优先）；2）若无读者、写者，则新读者也可以读；3）若无读者，且有写者在写，则新读者等待；假设写者来：1）若有读者，则新写者等待；2）若有其它写者，则新写者等待；3）若无读者和写者，则新写者可以写；,需要设置一个计数器rc，用来记录并发运行的读者个数；对于各个读者而言，该计数器是一个临界资源，对它的访问必须互斥进行，因此设置一个互斥信号量S_mutex；对于各个写者而言、写者与所有的读者而言，数据库是一个临界资源，对它的访问必须互斥地进行，因此设置一个互斥信号量S_db。,intrc=0;/并发读者的个数semaphoreS_mutex;/对rc的互斥信号量，初值1semaphoreS_db;/对数据库的信号量，初值1,读者写者问题的一个解答,voidwriter(void)while(TRUE)think_up_data();/生成数据，非临界区P(S_db);/希望访问数据库write_data_base();/更新数据库V(S_db);/退出临界区,voidreader(void)while(TRUE)P(S_mutex);/互斥地访问计数器rcrc+;/新增了一个读者if(rc=1)P(S_db);/如果是第一个读者V(S_mutex);/退出对rc的访问read_data_base();/读取数据库的内容P(S_mutex);/互斥地访问计数器rcrc-;/减少一个读者if(rc=0)V(S_db);/如果是最后一个读者V(S_mutex);/退出对rc的访问use_data_read();/使用数据，非临界区,对于基于读者优先策略的方法，只要有一个读者处于活动状态，后来的读者都会被接纳。如果读者源源不断地出现的话，那么写者就始终处于阻塞状态。,