同步和互斥.pptVIP

进程互斥和同步 1 互斥算法 2 信号量(semaphore) 3 经典进程同步问题 4 管程(monitor) 5 进程互斥和同步举例 互斥算法 1临界资源 2临界区的访问过程 3同步机制应遵循的准则 4进程互斥的软件方法 5进程互斥的硬件方法 临界资源 进程间资源访问冲突 共享变量的修改冲突 操作顺序冲突 进程间的制约关系 间接制约：进行竞争－－独占分配到的部分或全部共享资源，“互斥” 直接制约：进行协作－－等待来自其他进程的信息，“同步” 临界区的访问过程 临界区(critical section)：进程中访问临界资源的一段代码。 进入区(entry section)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应正在访问临界区标志 退出区(exit section)：用于将正在访问临界区标志清除。 剩余区(remainder section)：代码中的其余部分。 同步机制应遵循的准则 空闲则入：其他进程均不处于临界区； 忙则等待：已有进程处于其临界区； 有限等待：等待进入临界区的进程不能死等； 让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态） 进程互斥的软件方法 有两个进程Pi, Pj，其中的Pi 缺点：强制轮流进入临界区，没有考虑进程的实际需要。容易造成资源利用不充分：在Pi出让临界区之后，Pj使用临界区之前，Pi不可能再次使用临界区； 算法2：双标志、先检查 设立一个标志数组flag[]：描述进程是否在临界区，初值均为FALSE。 先检查，后修改：在进入区检查另一个进程是否在临界区，不在时修改本进程在临界区的标志； 在退出区修改本进程在临界区的标志； 优点：不用交替进入，可连续使用； 缺点：Pi和Pj可能同时进入临界区。按下面序列执行时，会同时进入：Pia Pja Pib Pjb。即在检查对方flag之后和切换自己flag之前有一段时间，结果都检查通过。这里的问题出在检查和修改操作不能连续进行。 算法3：双标志、后检查 类似于算法2，与互斥算法2的区别在于先修改后检查。可防止两个进程同时进入临界区。 缺点：Pi和Pj可能都进入不了临界区。按下面序列执行时，会都进不了临界区：Pia Pja Pib Pjb。即在切换自己flag之后和检查对方flag之前有一段时间，结果都切换flag，都检查不通过。 算法4(Peterson’s Algorithm)：先修改、后检查、后修改者等待 结合算法1和算法3，是正确的算法 turn=j;描述可进入的进程（同时修改标志时） 在进入区先修改后检查，并检查并发修改的先后： 检查对方flag，如果不在临界区则自己进入－－空闲则入 否则再检查turn：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入－－先到先入，后到等待 进程互斥的硬件方法 完全利用软件方法，有很大局限性（如不适于多进程），现在已很少采用。 可以利用某些硬件指令－－其读写操作由一条指令完成，因而保证读操作与写操作不被打断； 互斥算法（TS指令） 利用TS实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE 在进入区利用TS进行检查：有进程在临界区时，重复检查；直到其它进程退出时，检查通过； Swap指令（或Exchange指令） 互斥算法（Swap指令） 利用Swap实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE。每个进程设置一个私有布尔变量key 硬件方法的优点 适用于任意数目的进程，在单处理器或多处理器上 简单，容易验证其正确性 可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量 硬件方法的缺点 等待要耗费CPU时间，不能实现让权等待 可能饥饿：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上 可能死锁 2信号量和P、V原语 1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)），是一种卓有成效的进程同步机制。 信号量只能通过初始化和两个标准的原语来访问－－作为OS核心代码执行，不受进程调度的打断 初始化指定一个非负整数值，表示空闲资源总数（又称为资源信号量）－－若为非负值表示当前的空闲资源数，若为负值其绝对值表示当前等待临界区的进程数 二进制信号量(binary semaphore)：只允许信号量取0或1值 P，V操作的实现 依进程等待方式不同，P操作的执行方式也不同。 忙等待：当进程必须等待时，如果预计等待时间不长，则在多机系统中，为了减少进程状态转换所引起的开销，可采用忙等待方式。 阻塞等待：当进程必须在信号量S上等待时，将进程变为等待状态（blockeda），插入与信号量S有关的等待队列，让出C