湘潭大学 操作系统 第3章课件 ppt.ppt

（1）问题描述 有五位哲学家，用一生来思考和吃饭。他们围坐在一张圆桌旁边，桌子中央有一大碗米饭，桌上还有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，当某位哲学家进行思考时，他不与其它哲学家交互。当他感觉到饥饿时，便试图拿起与其左右最靠近他的筷子。满足： 一个哲学家每次只能拿起一只筷子，且他不能从其他哲学家手里拿筷子 只有在他拿到两只筷子时才能进餐 3.4.5 经典同步问题 * （2） 用信号量解决哲学家就餐问题 每一只筷子的使用都必须是互斥的，在某一时刻只允许一个哲学家使用 利用一个信号量表示一只筷子，五只筷子的信号量数组定义为semaphore chopstick[5] 3.4.5 经典同步问题 * 信号量解决哲学家就餐问题描述如下： semaphore chopstick[5] = {1,1,1,1,1}; int i; void philosopher (int i){ while(TRUE){ // think wait(chopstick[i]); wait(chopstick[(i+1) % 5]); // eat signal(chopstick[(i+1) % 5]); signal(chopstick[i]); } } void main(){ parbegain (philosopher(0), philosopher(1), philosopher(2), philosopher(3), philosopher(4));} * 可能出现死锁： 当五位哲学家都感到饥饿并都同时拿起了自己左边的筷子，又都伸手去拿右边的筷子的时，会发现右边的筷子都没有了。 一种解决方法是仅当哲学家左、右两边的筷子都能拿时才允许该哲学家拿起筷子就餐； 另一种解决方法是增加一位服务员，他最多只允许四位哲学家同时进入餐厅就餐，这就至少能保证有一位哲学家能同时拿起左、右两根筷子。 3.4.5 经典同步问题 * 补充：AND型信号量 前面我们所介绍的问题针对的是多个并发进程仅共享一个临界资源的情况。在有些应用场合，一个进程往往需要获得两个或两个以上的共享资源后方能继续执行。 AND型同步机制的基本思想：将进程在整个运行过程中所需要的所有资源一次性全部分配给进程，待进程使用完之后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。 3.4.5 经典同步问题 * 补充：AND型信号量 这样，对若干个临界资源的分配采取原子操作方式：要么，把它所请求的资源全部分配给进程；要么一个也不分配。 在wait操作中增加了一个“AND”条件，故称为AND同步，或称为同时wait操作。Swait(Simultaneous wait)定义为： 3.4.5 经典同步问题 * Swait(S1,S2,…,Sn) { while(TRUE) { if(Si=1 … Sn=1){ for(i=1; i=n; i++) break; } else{ place the process in the waiting queue associated with the first Si found with Si 1, and set the program count of this process to the beginning of Swait operation } } } * Ssignal(S1,S2,…,Sn) { while(TRUE) { for(i=1; i=n; i++){ Si++; Remove all the process waiting in the queue associated with Si into the ready queue } } } 利用AND信号量机制解决哲学家进餐问题，避免死锁 * semaphore chopstick chopstick[5] = {1,1,1,1,1}; do{ … //think …