操作系统第4讲

1、操作系统概念第四讲 进程互斥与同步上章回顾进程与程序的区别？什么是PCB？与进程上下文的区别？本课总体纲要进程互斥（ Mutual Exclusion on Processes）临界区准则（Critical Section Rule)加锁实现互斥(Mutual Exclusion)信号量实现互斥（semaphore）两种互斥方式的区别进程同步(Synchronization)P,V原语实现同步生产者消费者问题读写问题哲学家就餐问题进程互斥互斥：一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。不允许两个以上的共享该资源的进程同时进入临界区临界区：

2、 （Critical Section)把不允许多个并发进程交叉执行的一段程序称作临界区。并发进程互斥协调准则不能假设各并发程序的相对执行速度，各并发进程享有平等、独立的竞争公共资源的权利并发进程中某个进程不在临界区时，它不阻止其他进程进入临界区并发进程中的若干各进程申请进入临界区时，只能允许一个进程进入并发进程中某个进程申请进入临界区，应该在有限的时间内进入本课总体纲要进程互斥（ Mutual Exclusion on Processes）临界区准则（Critical Section Rule)加锁实现互斥(Mutual Exclusion)信号量实现互斥（semaphore）两种互斥方式的区

3、别进程同步(Synchronization)P,V原语实现同步生产者消费者问题读写问题哲学家就餐问题加锁实现互斥(1)单标志法P0:While turn!=0 donothingTurn:=1P1:While turn!=1 donothingTurn:=0加锁实现互斥（2）双标志法P0:While flag1 donothingFlag0:=true;Flag0:=false;P1:While flag0 donothingFlag1:=true;Flag1:=false;加锁实现互斥（3）双标志法改进版P0:Flag0:=true;While flag1 donothingFlag0:=f

4、alse;P1:Flag1:=true;While flag0 donothingFlag1:=false;加锁实现互斥（4）双标志法改进版P0:Flag0:=true;While Flag1 doFlag0:=false;Flag0:=true;Flag0:=false;P1:Flag1:=true;While Flag0 doFlag1:=false;Flag1:=true;Flag1:=false;本课总体纲要进程互斥（ Mutual Exclusion on Processes）临界区准则（Critical Section Rule)加锁实现互斥(Mutual Exclusion)信号

5、量实现互斥（semaphore）两种互斥方式的区别进程同步(Synchronization)P,V原语实现同步生产者消费者问题读写问题哲学家就餐问题信号量（semaphore)P0:A:lock(w)Unlock(w)Goto AP1:A:lock(w)Unlock(w)Goto A信号量(sem):在操作系统中，信号量一般是一整数，当sem=0:可供并发进程使用的资源实体数。当sem=0调用进程入等待队列转进程调度返回入口sem=sem+1sem=0唤醒等待队列中的进程转进程调度返回是否是否P,V原语实现进程互斥描述P0,P1并发进程互斥：设sem取值（1，0，1）Sem=1表示p0,p1都

6、未进入临界区sem=0表示p0或p1进入临界区Sem=1表示在p0和p1进程中，一个进程已经进入临界区，另一个处于等待进入临界区状态。P0:P(sem)V(sem)P1:P(sem)V(sem)本课总体纲要进程互斥（ Mutual Exclusion on Processes）临界区准则（Critical Section Rule)加锁实现互斥(Mutual Exclusion)信号量实现互斥（semaphore）两种互斥方式的区别进程同步(Synchronization)P,V原语实现同步生产者消费者问题读写问题哲学家就餐问题加锁法与信号量法的区别加锁法信号量法1、加锁过程可以中断采用P、V

7、原语2、循环检测锁，系统开销大，系统开销小3、未进入临界区的进程无排队等待机制未进入临界区的进程必须在等待队列中等待本课总体纲要进程互斥（ Mutual Exclusion on Processes）临界区准则（Critical Section Rule)加锁实现互斥(Mutual Exclusion)信号量实现互斥（semaphore）两种互斥方式的区别进程同步(Synchronization)P,V原语实现同步生产者消费者问题读写问题哲学家就餐问题进程同步进程同步：把异步环境下的一组并发进程，因直接制约并互相发送消息而进行的相互合作、相互等待，并使进程按照一定的顺序和速度执行的过程。合作进

8、程：具有同步关系的一组进程消息：合作进程互相发送的信号。则可使用以下过程：Wait(消息名):表示进程等待合作进程发来消息Signal(消息名)：表示向合作进程发送消息。信号量分类私用信号量：也可以把各进程之间发送的消息作为信号量看待。公用信号量：互斥时使用的信号量称为公用信号量本课总体纲要进程互斥（ Mutual Exclusion on Processes）临界区准则（Critical Section Rule)加锁实现互斥(Mutual Exclusion)信号量实现互斥（semaphore）两种互斥方式的区别进程同步(Synchronization)P,V原语实现同步生产者消费者问题读

9、写问题哲学家就餐问题生产者消费者问题生产者和消费者之间满足的条件：消费者接收数据时，有界缓冲区中至少有一个是满的生产者发送数据时，有界缓冲区中至少有一个是空的生产者进程与消费者进程必须互斥P,V原语实现同步Producer(data)BeginP(available)P(mutex)送数据进入缓冲区某单元V(full)V(mutex)EndConsumer(data)BeginP(full)P(mutex)送数据进入缓冲区某单元V(available)V(mutex)End公用信号量：mutex生产者私用信号量：available,消费者私用信号量：full读者写者问题读者写者问题必须保证一个

10、写者与其他进程互斥的访问共享数据的同步问题。加锁实现同步信号量实现同步同步问题有一个50座的阅览室，读者进入阅览室时，必须在登记簿上查找是否有空座，如果有，则登记姓名并进入阅读，当读者离开阅览室时，需要注销座位和姓名。采用P、V操作完成读者操作的同步算法。哲学家就餐问题就餐条件：哲学家想吃饭，先提出吃饭要求提出吃饭要求后，并拿到两双筷子后，方可吃饭。如果筷子被他人获得，则必须等待此人吃完后，才能获取筷子对于已经申请吃饭的任一个哲学家在自己未拿到两只筷子吃饭之前，不放下自己的筷子刚开始就餐时，只允许两个哲学家请求吃饭不相邻的哲学家同时要求吃饭信号量Si来互斥两两相邻哲学家的吃饭请求。信号量chopsticki来互斥筷子的使用 i (i+4)%5 (i+1)%5 (i+3)%5 (i+2)%5总结进程互斥（ Mutual Exclusion on Proce