操作系统第5章并发性：互斥和同步

《操作系统第5章并发性：互斥和同步》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章并发性：互斥和同步主要内容5.1并发的原理5.2互斥：硬件的支持5.3信号量5.4管程5.5消息传递5.6读者/写者问题1与并发相关的关键术语原子操作保证指令序列要么作为一个组来执行，要么都不执行；临界区一段代码，在这段代码中进程将访问共享资源，当一个进程已经在这段代码中运行时，另外一个进程就不能在这段代码中执行；死锁两个或两个以上的进程因其中的每个进程都在等待其他进程做完某些事情而不能继续执行；活锁两个或两个以上进程为了响应其他进程中的变化而持续改变自己的状态但不做有用的工作；2与并发相关的

2、关键术语互斥当一个进程在临界区访问共享资源时，其他进程不能进入该临界区访问任何共享资源；竞争条件多个线程或进程在读写一个共享数据时，结果依赖于它们执行的相对时间；饥饿一个可运行的进程被调度程序无限期地忽略，不能被调度执行的情形。35.1并发的原理1、基本概念并发单处理器多道程序设计系统中，进程交替执行；并行多处理器系统中，不仅可以交替执行进程，还可以重叠执行进程。并发问题并发进程的相对执行速度是不可预测的，取决于其他进程的活动、操作系统处理中断的方式以及操作系统的调度策略。可能发生各种与时间有关的错

3、误。4（结果不唯一）机票问题//飞机票售票问题voidT1(){voidT2(){{按旅客订票要求找到Aj};{按旅客订票要求找到Aj};intX1=Aj;intX2=Aj;if(X1>=1){if(X2>=1){X1--;X2--;Aj=X1;Aj=X2;{输出一张票};{输出一张票};}}elseelse{输出信息"票已售完"};{输出信息"票已售完"};}}5T1、T2并发执行，可能出现如下交叉情况：T1:X1=Aj;//X1=mT2:X2=Aj;//X2=mT2:X2--;Aj=X2;{输出

4、一张票};//Aj=m-1T1:X1--;Aj=X1;{输出一张票};//Aj=m-1同一张票卖给两位旅客（若只有一张余票）或者余票数不正确（若有多张余票）。6（永远等待）主存管理问题申请和归还主存资源问题intX=memory;//memory为初始主存容量voidborrow(intB){voidreturn(intB){while(B>X)X=X+B;{进程进入等待主存资源队列};{修改主存分配表};X=X-B;{释放等主存资源进程};{修改主存分配表，进程获得主存资源};}}7若对borro

5、w和return的并发执行不加限制将会导致错误，例如：Borrow:while(B>X);Return:X=X+B;{修改主存分配表};{释放等待主存资源的进程}；此时，因为borrow还没有进入等待队列，因此，return的释放操作是空操作，当borrow进入等待队列时，可能没有进程再来归还，处于永远等待状态。82、操作系统关注的问题并发带来的设计和管理问题：操作系统必须能跟踪不同的进程；操作系统必须为每个活跃进程分配和释放各种资源；操作系统必须保护每个进程的数据和物理资源；一个进程的功能和执行结

6、果必须与执行速度无关。93、进程的交互进程间的资源竞争互斥、死锁、饥饿进程间通过共享合作互斥、死锁、饥饿、数据一致性进程间通过通信合作死锁、饥饿104、互斥的要求必须强制实施互斥；一个在非临界区停止的进程不能干涉其他进程；不允许出现需要访问临界区的进程被无限延迟的情况；当没有进程在临界区时，任何需要进入临界区的进程必须能够立即进入；对相关进程的执行速度和处理器的数目没有任何要求和限制；一个进程驻留在临界区中的时间必须是有限的。11解决互斥问题的方法软件方法由并发执行的进程担负解决问题的责任；硬件方法

7、中断禁用专用机器指令操作系统或程序设计语言中提供某种级别的支持信号量管程消息传递125.2互斥：硬件的支持1、中断禁用while(true){/*禁用中断*/;/*临界区*/;/*启用中断*/;/*其余部分*/;}问题：代价非常高；不能用于多处理器结构中。132、专用机器指令比较和交换指令intcompare_and_swap(int*word,inttestval,intnewval){intoldval;oldval=*word;if(oldval==testval)*word=newval;r

8、eturnoldval;}14交换指令voidexchange(intregister,intmemory){inttemp;temp=memory;memory=register;register=temp;}15互斥协议16机器指令方法的优缺点优点适用于在单处理器或共享内存的多处理器上的任何数目的进程；非常简单且易于证明；可用于支持多个临界区，每个临界区可以用它自己的变量定义。缺点忙等待；可能饥饿；可能死锁。175.3信号量1965年E.W.Dijkstra提出了