第六章 进程间互斥、同步与通信(操作系统原理)

第六章进程间互斥、同步与通信授课教师：付勇智[e-mail]西南林学院基础部数理教研室问题纲要►间接制约和直接制约是什么？►什么是临界区？►什么是信号量？►什么是同步、互斥？►如何应用信号量实现同步和互斥？►信号量在Windows编程中是如何实现的？进程并发运行所带来的问题►由于系统资源的共享性，并发进程的执行结果失去了封闭性和可再现性。►满足Bernstein条件的并发进程能够保持封闭性，但是Bernstein条件限制太过严格，不符合大多数实际环境的需要。►因而，OS需要寻求一种机制，满足进程间共享资源的需要。进程间通信IPC►在两个或多个进程间传递信息或共享数据的机制，称之为进程间通信（Inter-ProcessCommunication）►UNIX操作系统中的管道技术（Pipe）就是一种IPC►在IPC的过程中，主要要解决两类问题：互斥和同步互斥的需要voidSendPrint(){1if((in+1)%N==out)2exit(0);3else4in=(in+1)%N;5file[in]=printfile;6return;}ProcessA(){……SendPrint()}ProcessB(){……SendPrint()}临界区（CriticalSection)►临界资源：一次仅允许一个进程使用的资源称为临界资源。►临界区：进程中对于临界资源访问的程序段称为临界区。►间接制约：由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象，称为由共享公有资源造成的并发进程执行速度的间接制约，简称间接制约。►互斥：一组并发进程中的一个或多个程序段，因共享某一公有资源而导致他们不能同时进入临界区称为互斥。互斥（MutualExclusion）互斥方案应满足的4个条件►任何两个进程不能同时处于临界区►不应对CPU的数目和速度做任何假设►临界区外的进程不得阻塞其他进程►不得使进程在临界区外无休止地等待互斥的实现方案►关中断►锁变量►严格轮换法►Peterson方案►TSL硬件指令（Intel平台为BTS指令）►信号量►管程►消息传递关中断►处理机的调度都是由中断所引起的（主要是定时器中断）►如果进入临界区前将所有外部中断屏蔽，则在运行临界区时将不会响应所有外部中断事件，也就不可能发生进程切换，待进程执行完临界区后再开中断。►缺点：交由用户进程管理中断的开关是非常不安全的，一旦用户程序关中断后忘记打开，则整个系统将无法响应外部事件而崩溃；另外，在多处理器系统中，关中断也仅屏蔽本处理器的中断响应，对其他处理器中运行的进程无法屏蔽。►因而通常中断屏蔽都由OS进行管理，由OS使用它来保证一些核心操作的不可中断性。锁变量intlock=0;//初始情况下没有进程进入临界区Processi(){while(lock==1);//当其他进程在临界区工作时，忙等待lock=1;//设置锁变量，防止其他进程进入critical_section();//进行临界区相关操作lock=0;//退出临界区后解锁，使其他进程可以进入non_critical_section();}严格轮转法Peterson方案TSL指令（测试与设置指令）IntelCPU中对应的TSL指令汇编指令码为BTS信号量(semaphore)►信号量使E.W.Dijkstra在1965年提出的一种方法，他建议引入一个新的变量类型，称作信号量。信号量是一个整数，其值可以为0或某个正整数，分别表示不可进入临界区以及能够进入的进程数目。►信号量：是一个仅能由同步原语对其进行操作的整型变量。►原语（原子操作）：操作过程不可中断，必须以一个整体进行执行地系统基本操作►对于信号量操作的原语只有两个：UP和DOWNDOWN原语（P操作）►(1)若信号量S大于0，则将S减1，P操作返回，该进程继续执行►(2)若信号量S等于0，则将进程挂入S的等待队列，将进程设置为阻塞状态，并转调度程序P原语S0S=S-1返回调用进程进入等待队列转进程调度是否UP原语（V操作）►(1)若信号量S的等待队列中有等待进程，则取队首进程，将其置为就绪状态并返回。►(2)否则信号量S加1，并放回V原语是否有等待进程S=S+1返回取队首进程置为就绪态否是生产者－消费者问题►问题描述：两个进程共享一个公共的固定大小的缓冲区。其中的一个，生产者，将信息放入缓冲区；另一个，消费者，从缓冲区中取出信息。►当缓冲区已满，而此时生产者还想向其中放入一个新的信息则让生产者睡眠，待消费者从缓冲区取走一个或多个信息时再唤醒它。►当消费者试图从缓冲区中取信息而发现缓冲区为空时，它就睡眠，直到生产者向其中放入一些消息再将其唤醒。生产者过程消费者过程直接制约与同步►一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程称为并发进程间的直接制约。►异步环境下的一组并发进程，因直接制约而互相发送消息而进行相互合作、相互等待，使得各进程按一定的速度执行的过程称为进程间的同步。生产者－消费者问题信号量定义#defineN100semaphoremutex=1;//互斥信号量semaphoreempty=N;//开始时候可用的消息缓冲区数为Nsemaphorefull=0;//开始时候可用的消息为0生产者进程voidproducer(){intitem;while(true){produce-item(&item);//产生消息down(empty);//获得一个消息缓冲块down(mutex);//对消息的缓冲要互斥enter-item(item);//将消息送入缓冲区up(mutex);//互斥结束up(full);//增加一个可用消息}}消费者进程voidconsumer(){intitem;while(true){down(full);//获得一可用消息down(mutex);//互斥访问消息缓冲区get-item(&item);//取得消息并从队列删除up(mutex);//结束互斥up(empty);//增加一个空缓冲区}}哲学家进餐问题►五个哲学家围坐在一张圆桌周围，每个哲学家面前都有一盘通心粉，由于通心粉很滑，所以要两把叉子才能夹住。相邻两盘子之间有一把叉子，餐具摆放如右图所示哲学家生活的过程►哲学家的生活包括两种活动：即吃饭和思考。当一个哲学家觉得饿时，他就试图分两次去取他左边和右边的叉子，每次得到一把，并且不分次序。如果成功的获得两把叉子，他就开始吃饭，吃完以后放下叉子继续思考。►问题：为每一个哲学家写一段程序来描述其行为，要求不能死锁。不正确解法#defineN5voidphilosopher(inti){while(true){think();take-fork(i);take-fork((i+1)%N);eat();put-fork(i);put-fork((i+1)%N);}}低效率的互斥可行解法#defineN5semaphormutex=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);}}经典解法#defineN5#defineLEFT(i-1)%N#defineRIGHT(i+1)%N#defineTHINKING0#defineHUNGRY1#defineEATING2intstate[N]semaphoremutex=1semaphores[N]={0,0,...,0}哲学家过程voidphilosopher(inti){while(true){think();take-forks(i);eat();put-forks(i);}}voidtest(i){if(state[i]==HUNGRY&&state[LEFT]!=EATING&&state[RIGHT]!=EATING){state[i]=EATING;up(s[i]);}}哲学家的两个主要动作voidtake-forks(inti){down(&mutex);state[i]=HUNGRY;test(i);up(mutex);down(s[i]);}voidput-forks(inti){down(mutex);state[i]=THINKING;test(LEFT);test(RIGHT);up(mutex);}读者－写者问题►设想一个飞机订票系统，其中有许多竞争的进程试图读写其中的数据。多个进程同时读是可以接受的，但一个进程正在更新数据库，则所有其他进程都不能访问数据库，即使读操作也不行。►问题：如何对读者和写者编写线程？semaphoremutex=1;semaphoredb=1;intrc=0;voidreader(){while(true){down(mutex);rc+=1;if(rc==1)down(db);up(mutex);read-data-base();down(mutex);rc=rc-1;if(rc==0)up(db);up(mutex);use-data-read();}}写者过程voidwriter(){while(true){think-up-data();down(db);write-data-base();up(db);}}理发师睡觉问题►理发店里有一位理发师、一把理发椅和n把供等候理发顾客坐的椅子。如果没有顾客，则理发师便在理发椅上睡觉。►当一个顾客到来时，他必须叫醒理发师；如果一个顾客到来时理发师正在理发，则如果有空椅子可以坐，他们就坐下来等待；如果没有空椅子，他们就离开。►问题：为理发师和顾客各编写一段程序，描述他们的行为，要求不能带有竞争条件。信号量定义#defineCHAIRS5//椅子数目semaphorecustomers=0;//顾客数目semaphorebarbers=0;//等候顾客的理发师数目semaphoremutex=1;//等待队列互斥信号量intwaiting=0;//等待队列voidbarber(){while(true){down(customers);down(mutex);waiting--;up(barbers);up(mutex);cut-hair();}}voidcustomer(){down(mutex);if(waitingCHAIRS){waiting++;up(customers);up(mutex);down(barbers);get-haircut();}elseup(mutex);}司机－售票员问题►一辆公共汽车上有一名司机和一名售票员，司机的工作是不停的循环执行如下步骤：“开车－正常行车－到站停车”，售票员的工作是不停的执行如下工作：“开车门－等候乘客上车－关车门－售票”►售票员必须等车到站停车后才能开车门；司机也必须等售票员关车门以后才能开车►问题：试写两段程序，分别描述司机和售票员的工作过程。司机、售票员问题到站停车开车开车门关车门售票正常行车。。。。。。。售票员司机semaphoredriving=0;semaphoredoor=1;voiddriver(){while(true){down(driving);开车();正常行车();到站停车();up(door);}}voidticket-seller(){while(true){down(door);开门();等待乘客上车();关门();up(driving);售票();}}两学校交通问题►在南开大学和天津大学之间有一条弯曲的小路，其中从S到T一段路每次只允许一辆自行车通过，但中间有一个小的“安全岛”M，可供两辆自行车在从两端进入小路的情况下错车使用，如下图所示，试设计一个算法使来往的自行车均可顺利通过。学校交通图示M天津大学南开大学SKTLsemaphoreS2T=1;semaphoreT2S=1;s