操作系统第4讲课件

操作系统概念

第四讲进程互斥与同步OperatingSystemConceptionDavidfu上章回顾进程与程序的区别？什么是PCB？与进程上下文的区别？OperatingSystemConceptionDavidfu本课总体纲要进程互斥（MutualExclusiononProcesses）临界区准则（CriticalSectionRule)加锁实现互斥(MutualExclusion)信号量实现互斥（semaphore）两种互斥方式的区别进程同步(Synchronization)P,V原语实现同步生产者消费者问题读－写问题哲学家就餐问题OperatingSystemConceptionDavidfu并发进程互斥协调准则不能假设各并发程序的相对执行速度，各并发进程享有平等、独立的竞争公共资源的权利并发进程中某个进程不在临界区时，它不阻止其他进程进入临界区并发进程中的若干各进程申请进入临界区时，只能允许一个进程进入并发进程中某个进程申请进入临界区，应该在有限的时间内进入OperatingSystemConceptionDavidfu本课总体纲要进程互斥（MutualExclusiononProcesses）临界区准则（CriticalSectionRule)加锁实现互斥(MutualExclusion)信号量实现互斥（semaphore）两种互斥方式的区别进程同步(Synchronization)P,V原语实现同步生产者消费者问题读－写问题哲学家就餐问题OperatingSystemConceptionDavidfu加锁实现互斥(1)－单标志法P0:Whileturn!=0do{nothing}<临界区>Turn:=1P1:Whileturn!=1do{nothing}<临界区>Turn:=0OperatingSystemConceptionDavidfu加锁实现互斥（3）－双标志法改进版P0:Flag[0]:=true;Whileflag[1]do{nothing}<临界区>Flag[0]:=false;P1:Flag[1]:=true;Whileflag[0]do{nothing}<临界区>Flag[1]:=false;OperatingSystemConceptionDavidfu加锁实现互斥（4）－双标志法改进版P0:Flag[0]:=true;WhileFlag[1]do{Flag[0]:=false;<延迟一段时间>Flag[0]:=true;}<临界区>Flag[0]:=false;P1:Flag[1]:=true;WhileFlag[0]do{Flag[1]:=false;<延迟一段时间>Flag[1]:=true;}<临界区>Flag[1]:=false;OperatingSystemConceptionDavidfu本课总体纲要进程互斥（MutualExclusiononProcesses）临界区准则（CriticalSectionRule)加锁实现互斥(MutualExclusion)信号量实现互斥（semaphore）两种互斥方式的区别进程同步(Synchronization)P,V原语实现同步生产者消费者问题读－写问题哲学家就餐问题OperatingSystemConceptionDavidfuP,V原语P原语操作V原语操作入口sem=sem－1sem>=0调用进程入等待队列转进程调度返回入口sem=sem+1sem<=0唤醒等待队列中的进程转进程调度返回是否是否OperatingSystemConceptionDavidfuP,V原语实现进程互斥描述P0,P1并发进程互斥：设sem取值（1，0，－1）Sem=1表示p0,p1都未进入临界区sem=0表示p0或p1进入临界区Sem=－1表示在p0和p1进程中，一个进程已经进入临界区，另一个处于等待进入临界区状态。P0:P(sem)<CS>V(sem)P1:P(sem)<CS>V(sem)…OperatingSystemConceptionDavidfu本课总体纲要进程互斥（MutualExclusiononProcesses）临界区准则（CriticalSectionRule)加锁实现互斥(MutualExclusion)信号量实现互斥（semaphore）两种互斥方式的区别进程同步(Synchronization)P,V原语实现同步生产者消费者问题读－写问题哲学家就餐问题OperatingSystemConceptionDavidfu本课总体纲要进程互斥（MutualExclusiononProcesses）临界区准则（CriticalSectionRule)加锁实现互斥(MutualExclusion)信号量实现互斥（semaphore）两种互斥方式的区别进程同步(Synchronization)P,V原语实现同步生产者消费者问题读－写问题哲学家就餐问题OperatingSystemConceptionDavidfu进程同步进程同步：把异步环境下的一组并发进程，因直接制约并互相发送消息而进行的相互合作、相互等待，并使进程按照一定的顺序和速度执行的过程。合作进程：具有同步关系的一组进程消息：合作进程互相发送的信号。则可使用以下过程：Wait(消息名):表示进程等待合作进程发来消息Signal(消息名)：表示向合作进程发送消息。OperatingSystemConceptionDavidfu信号量分类私用信号量：也可以把各进程之间发送的消息作为信号量看待。公用信号量：互斥时使用的信号量称为公用信号量OperatingSystemConceptionDavidfu生产者消费者问题

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

读者－写者问题必须保证一个写者与其他进程互斥的访问共享数据的同步问题。加锁实现同步信号量实现同步OperatingSystemConceptionDavidfu哲学家就餐问题

就餐条件：哲学家想吃饭，先提出吃饭要求提出吃饭要求后，并拿到两双筷子后，方可吃饭。如果筷子被他人获得，则必须等待此人吃完后，才能获取筷子对于已经申请吃饭的任一个哲学家在自己未拿到两只筷子吃饭之前，不放下自己的筷子刚开始就餐时，只允许两个哲学家请求吃饭OperatingSystemConceptionDavidfu不相邻的哲学家同时要求吃饭信号量S[i]来互斥两两相邻哲学家的吃饭请求。信号量chopstick[i]来互斥筷子的使