第3章 并发控制-互斥与同步.ppt

《第3章 并发控制-互斥与同步.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章进程的并发控制——互斥与同步1进程的并发控制——互斥与同步3.1前趋图(PrecedenceGraph)3.2进程的同步与互斥3.3信号量和管程3.4进程通信2互斥与同步概念在多道程序环境中，由于进程合作和资源共享，使得并发执行的多个进程之间存在两种制约关系——同步与互斥3互斥与同步概念（1）同步，也称为直接相互制约，是指某些并发执行的进程为共同完成一个任务，需要相互合作、协同工作，这些合作的进程都是独立地以不可预知的速度推进，这就需要在一些关键点上互相等待，互通消息。4互斥与同步概念（2）互斥，也称间接相

2、互制约关系，是指多个进程同时竞争一个需要互斥使用的资源（如打印机等），当该资源已经分配给某个进程使用时，其它进程只能等待，直到该资源被释放。5互斥与同步概念可见，进程的同步是我们需要的，而互斥是被迫的。为了说明进程的同步，引入一个前趋图的概念63.1前趋图(PrecedenceGraph)前趋图(PrecedenceGraph)是一个有向无循环图，记为DAG(DirectedAcyclicGraph)，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示

3、两个结点之间存在的偏序(PartialOrder)或前趋关系78图3-3并发执行时的前趋图9图3-4四条语句的前趋关系103.2进程的同步与互斥进程互斥定义:所谓进程互斥是指当有若干进程都要使用某一共享资源时，最多允许一个进程使用，而其他要使用该资源的进程必须等待，直到占用该资源的进程释放了该资源为止。进程互斥是进程之间发生的一种间接性作用，一般是程序不希望的。两个进程不能同时进入临界区，否则就会导致数据的不一致，产生与时间有关的错误。113.2进程的同步与互斥临界资源定义:操作系统中将一次仅允许一个进程访问的资

4、源称为临界资源,如打印机、共享变量等。临界区定义:操作系统中把每个进程中访问临界资源的那段代码段称为临界区。123.2进程的同步与互斥如变量N是临界资源，程序A中有访问N的代码：…………….X=N;N++;…………….上面访问N的两句代码就是程序A的临界区。133.2进程的同步与互斥显然，若能保证每个进程互斥地进入自己的临界区，便可实现诸进程对临界资源的互斥访问143.2进程同步与互斥解决互斥问题应该满足互斥和公平两个原则，即任意时刻只能允许一个进程处于同一共享变量的临界区，而且不能让任一进程无限期地等待。15进

5、程同步机制的准则:①空闲让进：当无进程处于临界区时，必须让一个要求进入它的临界区的进程立即进入，以提高临界资源的利用率。②忙则等待：当已有进程处于临界区时，其他试图进入自己临界区的进程必须等待，以保证它们互斥地进入临界区。③让权等待：对于等待进入临界区的进程而言，它必须立即释放处理机，以避免进程"忙等"而降低CPU的效率。④有限等待：对要求进入临界区的进程，应在有限时间内进入，以免陷入"死等"。163.2进程的同步与互斥（续）进程同步概念:一般来说，一个进程对于其它的进程运行速度是不确定的。但是相互合作的几个进程

6、需要在某些确定点上协调它们的工作。所谓进程同步，是指多个相互合作的进程，在一些关键点上可能需要互相等待或互相交换信息，这种相互制约的关系称为进程同步。进程同步是进程之间直接的相互作用，是合作进程间有意识的行为。173.2进程同步与互斥进程同步实例1：典型的同步例子是公共汽车上司机与售票员的合作：只有当售票员关门之后司机才能启动车辆，只有司机停车之后售票员才能开车门。司机和售票员的行动需要一定的协调。同样地，两个进程之间有时也有这样的依赖关系，因此我们也要有一定的同步机制保证它们的执行次序。18进程同步实例2：系统

7、中有两个合作的进程，他们共用一个单缓冲区。这两个进程一个是计算进程，负责对数据进行计算；另一个为打印进程，负责对计算结果进行打印。当计算进程没有计算完毕，计算结果没有送到缓冲区的时候，打印进程就不能打印。一旦计算进程把计算结果送入缓冲区，就应该给打印进程发送一个信号，打印进程收到信号后就可以从缓冲区中取出计算结果进行打印。19进程同步实例2（续）：在打印进程尚未把缓冲区中的计算结果取出打印之前，计算进程也不能把下一次的计算结果送入缓冲区。只有在打印进程取出缓冲区中的内容，给计算进程发一个信号后，计算进程才能将下一

8、次的计算结果送入缓冲区。计算进程和打印进程就是通过这种互相发信号的方式实现同步的。203.3信号量和管程本章主要介绍以下两种同步和互斥机制：信号量管程213.3信号量和管程互斥问题可以用硬件方法，也可以用软件方法解决。“开关中断”称为硬件锁，是最简单的用硬件实现互斥的方法。223.3信号量和管程即在进程进入临界区之前，先执行“关中断”指令，即屏蔽所有中断，在进程执行自己的