《操作系统第5章并发性：互斥和同步.ppt》由会员分享，可在线阅读，更多相关《操作系统第5章并发性：互斥和同步.ppt（52页珍藏版）》请在三一办公上搜索。
1、1,第5章 并发性：互斥和同步,主要内容5.1 并发的原理5.2 互斥：硬件的支持5.3 信号量5.4 管程5.5 消息传递5.6 读者/写者问题,2,与并发相关的关键术语,原子操作保证指令序列要么作为一个组来执行，要么都不执行；临界区一段代码，在这段代码中进程将访问共享资源，当一个进程已经在这段代码中运行时，另外一个进程就不能在这段代码中执行；死锁两个或两个以上的进程因其中的每个进程都在等待其他进程做完某些事情而不能继续执行；活锁两个或两个以上进程为了响应其他进程中的变化而持续改变自己的状态但不做有用的工作；,3,与并发相关的关键术语,互斥当一个进程在临界区访问共享资源时，其他进程不能进入该
2、临界区访问任何共享资源；竞争条件多个线程或进程在读写一个共享数据时，结果依赖于它们执行的相对时间；饥饿一个可运行的进程被调度程序无限期地忽略，不能被调度执行的情形。,4,5.1 并发的原理,1、基本概念并发单处理器多道程序设计系统中，进程交替执行；并行多处理器系统中，不仅可以交替执行进程，还可以重叠执行进程。并发问题并发进程的相对执行速度是不可预测的，取决于其他进程的活动、操作系统处理中断的方式以及操作系统的调度策略。可能发生各种与时间有关的错误。,5,（结果不唯一）机票问题,/飞机票售票问题void T1()void T2()按旅客订票要求找到Aj;按旅客订票要求找到Aj;int X1=Aj
3、;int X2=Aj;if(X1=1)if(X2=1)X1-;X2-;Aj=X1;Aj=X2;输出一张票;输出一张票;else else 输出信息票已售完;输出信息票已售完;,6,T1、T2并发执行，可能出现如下交叉情况：T1:X1=Aj;/X1=mT2:X2=Aj;/X2=mT2:X2-;Aj=X2;输出一张票;/Aj=m-1T1:X1-;Aj=X1;输出一张票;/Aj=m-1同一张票卖给两位旅客（若只有一张余票）或者余票数不正确（若有多张余票）。,7,（永远等待）主存管理问题,申请和归还主存资源问题int X=memory;/memory为初始主存容量void borrow(int B)v
4、oid return(int B)while(BX)X=X+B;进程进入等待主存资源队列;修改主存分配表;X=X-B;释放等主存资源进程;修改主存分配表，进程获得主存资源;,8,若对borrow和return的并发执行不加限制将会导致错误，例如：Borrow:while(BX);Return:X=X+B;修改主存分配表;释放等待主存资源的进程；此时，因为borrow还没有进入等待队列，因此，return的释放操作是空操作，当borrow进入等待队列时，可能没有进程再来归还，处于永远等待状态。,9,2、操作系统关注的问题,并发带来的设计和管理问题：操作系统必须能跟踪不同的进程；操作系统必须为每个
5、活跃进程分配和释放各种资源；操作系统必须保护每个进程的数据和物理资源；一个进程的功能和执行结果必须与执行速度无关。,10,3、进程的交互,进程间的资源竞争互斥、死锁、饥饿进程间通过共享合作互斥、死锁、饥饿、数据一致性进程间通过通信合作死锁、饥饿,11,4、互斥的要求,必须强制实施互斥；一个在非临界区停止的进程不能干涉其他进程；不允许出现需要访问临界区的进程被无限延迟的情况；当没有进程在临界区时，任何需要进入临界区的进程必须能够立即进入；对相关进程的执行速度和处理器的数目没有任何要求和限制；一个进程驻留在临界区中的时间必须是有限的。,12,解决互斥问题的方法,软件方法由并发执行的进程担负解决问题
6、的责任；硬件方法中断禁用专用机器指令操作系统或程序设计语言中提供某种级别的支持信号量管程消息传递,13,5.2 互斥：硬件的支持,1、中断禁用while(true)/*禁用中断*/;/*临界区*/;/*启用中断*/;/*其余部分*/;问题：代价非常高；不能用于多处理器结构中。,14,2、专用机器指令,比较和交换指令int compare_and_swap(int*word,int testval,int newval)int oldval;oldval=*word;if(oldval=testval)*word=newval;return oldval;,15,交换指令,void exchan
7、ge(int register,int memory)int temp;temp=memory;memory=register;register=temp;,16,互斥协议,17,机器指令方法的优缺点,优点适用于在单处理器或共享内存的多处理器上的任何数目的进程；非常简单且易于证明；可用于支持多个临界区，每个临界区可以用它自己的变量定义。缺点忙等待；可能饥饿；可能死锁。,18,5.3 信号量,1965年提出了新的同步工具-信号量。基本原理两个或多个进程通过简单的信号进行合作，一个进程被迫在某一位置停止，直到它接收到一个特定的信号。任何复杂的合作需求都可以通过适当的信号结构得到满足。,19,信号量
8、,信号量是一个与队列有关的整型变量。可以初始化成非负数；semWait操作使信号量减1。若值为负数，则执行semWait的进程阻塞，否则继续执行；semSignal操作使信号量加1。若值小于或等于0，则被semWait操作阻塞的进程被解除阻塞。,20,信号量原语的定义,21,5.3.1 互斥,22,互斥的例子,23,5.3.2 生产者/消费者问题,问题描述：有一个或多个生产者生产某种类型的数据，并放置在缓冲区中；有一个消费者从缓冲区中取数据，每次取一项；系统保证避免对缓冲区的重复操作，即任何时候只有一个主体（生产者或消费者）可以访问缓冲区。缓存已满时，生产者不能继续添加数据；缓存已空时，消费者
9、不能继续移走数据。,24,1、无限缓冲区的生产者/消费者问题,producer:while(true)/*produce item v*/bin=v;in+;,consumer:while(true)while(in=out)/*do nothing*/;w=bout;out+;/*consume item w*/,25,无限缓冲区,26,使用信号量解决无限缓冲区生产者/消费者问题,27,2、有限缓冲缓冲区的生产者/消费者问题,producer:while(true)/*produce item v*/while(in+1)%n=out)/*do nothing*/;bin=v;in=(in+
10、1)%n,28,consumer:while(true)while(in=out)/*do nothing*/;w=bout;out=(out+1)%n;/*consume item w*/,29,有限缓冲区,30,使用信号量解决有限缓冲区生产者/消费者问题,31,5.6 读者/写者问题,问题定义有一个由多个进程共享的数据区，一些进程只读取这个数据区中的数据，一些进程只往数据区中写数据。并须满足以下条件：任意多的读进程可以同时读文件；一次只有一个写进程可以写文件；如果一个写进程正在写文件，那么禁止任何读进程读文件。,32,读者优先信号量,33,总结,信号量小结semWait和semSignal
11、操作小结针对信号量问题的补充练习,34,1、信号量小结,一个信号量可用于n个进程的同步互斥；且只能由semWait、semSignal操作修改。用于互斥时，S初值为1，取值为1-(n-1)（相当于临界区的通行证，实际上也是资源个数）S=1：临界区可用 S=0：已有一进程进入临界区 S=0 S=0:表示可用资源个数 S0:表示该资源的等待队列长度,35,2、semWait、semSignal操作小结,semWait(S)：请求分配一个资源。semSignal(S)：释放一个资源。semWait、semSignal操作必须成对出现。用于互斥时，位于同一进程内；用于同步时，交错出现于两个合作进程内。
12、多个semWait操作的次序不能颠倒，否则可能导致死锁。多个semSignal操作的次序可任意。,36,3、针对信号量问题的补充练习,桌子上有一个盘子，可以存放一个水果。父亲总是放苹果到盘子中，而母亲总是放香蕉到盘子中；儿子专等吃盘中的香蕉，而女儿专等吃盘中的苹果。,分析：生产者消费者问题的一种变形，生产者、消费者以及放入缓冲区的产品都有两类，但每类消费者只消费其中固定的一种产品。数据结构：semaphore dish，apple，banana;dish：表示盘子是否为空，初值为1apple：表示盘中是否有苹果，初值为0banana：表示盘中是否有香蕉，初值为0,37,process fath
13、er()semWait(dish);将苹果放到盘中；semSignal(apple);process mother()semWait(dish);将香蕉放到盘中；semSignal(banana);,process son()semWait(banana);从盘中取出香蕉；semSignal(dish);process daughter()semWait(apple);从盘中取出苹果；semSignal(dish);,38,在一个盒子里，混装了数量相等的黑白围棋子。现在用自动分拣系统把黑子、白子分开，设分拣系统有两个进程P1和P2，其中P1拣白子，P2拣黑子。规定每个进程每次拣一子，当一个进程
14、在拣时，不允许另一个进程去拣；当一个进程拣了一子时，必须让另一个进程去拣。试用信号量和P、V操作协调两个进程的并发执行。,分析：实际上就是两个进程的同步问题。数据结构：semaphore S1，S2;S1 和S2 分别表示可拣白子和黑子，不失一般性，若令先拣白子。初值，S1=1；S2=0；,39,process P1()while(true)semWait(S1);拣白子；semSignal(S2);,process P2()while(true)semWait(S2);拣黑子；semSignal(S1);,40,5.4 管程,管程是一个或多个过程、一个初始化序列和局部数据组成的软件模块，主要
15、特点如下：局部数据变量只能被管程的过程访问，任何外部过程都不能访问；一个进程通过调用管程的一个过程进入管程；在任何时候，只能有一个进程在管程中执行，调用管程的任何其他进程都被阻塞，以等待管程可用。管程通过条件变量提供对同步的支持。条件变量只有在管程中才能被访问。cwait(c)：调用管程的进程在条件c上阻塞。csignal(c)：恢复执行在cwait之后因为某些条件而阻塞的进程。,41,管程的结构,42,使用管程解决有界缓冲区的生产者/消费者问题,43,44,5.5 消息传递,消息传递：合作进程之间进行信息交换。消息传递原语send(destination,message)receive(so
16、urce,message),45,5.5.1 同步,阻塞send,阻塞receive发送者和接收者都被阻塞，直到完成信息的投递。无阻塞send,阻塞receive接收者阻塞，直到请求的信息到达。无阻塞send,无阻塞receive不要求任何一方等待。,46,5.5.2 寻址,直接寻址send原语包含目标进程的标识号；receive原语可显式地指定源进程，也可不指定。间接寻址发送者将消息发送到合适的信箱；接收者从信箱中获得消息。,47,5.5.3 消息格式,固定长度消息可变长度消息,消息头,消息体,48,5.5.4 排队原则,先进先出优先级,49,5.5.5 互斥,50,使用消息解决有界缓冲区生
17、产者/消费者问题,51,作业,1、写出信号量定义，semWait和semSignal原语，以及用信号量实现互斥的伪代码。2、假设一个阅览室有100个座位，没有座位时读者在阅览室外等待；每个读者进入阅览室时都必须在阅览室门口的一个登记本上登记座位号和姓名，然后阅览，离开阅览室时要去掉登记项。每次只允许一个人登记或去掉登记。用信号量操作描述读者的行为。,52,作业,3、设公共汽车上，司机和售票员活动如下：1）司机：启动汽车，正常行车，到站停车；2）售票员：关车门，售票，开门上下客。用信号量操作描述司机和售票员的同步。4、(选做)独木桥问题：东、西向汽车过独木桥。桥上无车时允许一方汽车过桥，待全部过完后才允许另一方汽车过桥。用信号量操作写出同步算法。(提示：参考读者优先的解法),
