临界区管理.ppt

主要内容 互斥与临界区实现临界区管理的几种尝试实现临界区管理的软件算法实现临界区管理的硬件设施 3 2临界区管理 3 2 1互斥和临界区 飞机票售票系统之所以会产生错误 原因在于多个售票进程交叉访问了共享变量Aj 1 临界区 CriticalSection 与 临界资源 CriticalResource 并发进程中与共享变量有关的程序段叫 临界区 CriticalSection 共享变量代表的资源叫 临界资源 CriticalResource 飞机票售票系统中 进程T1的临界区为 X1 Aj if X1 1 X1 Aj X1 进程T2的临界区为 X1 Aj if X2 1 X2 Aj X2 与同一变量有关的临界区分散在各进程的程序段中 而各进程的执行速度不可预知 如果能保证进程在临界区执行时 不让另一个进程进入临界区 即各进程对共享变量的访问是互斥的 就不会造成与时间有关的错误 2 临界区的描述Dijkstra在1965年首先提出临界区的概念 可以用与一个共享变量相关的临界区的语句结构来书写交互的并发进程 sharedvariableregionvariabledostatement临界区的嵌套使用regionxdo regionydo regionydo regionxdo 一个进程执行到临界区的语句时 不管该进程目前是否正在运行 都说它是在临界区内 根据临界区语法重写的售票管理进程如下 sharedAjvoidTi 按旅客定票要求找到Aj regionAjdointXi Aj if Xi 1 Xi Aj Xi regionAj 输出一张票 else 输出票已售完 3 临界区的调度原则一次至多允许一个进程进入临界区内 一个进程不能无限地停留在临界区内 一个进程不能无限地等待进入临界区 临界区调度原则可总结成四句话 无空等待 有空让进 择一而入 算法可行 算法可行是指不能因为所选的调度策略造成进程饥饿甚至死锁 3 2 2实现临界区管理的几种尝试 首先讨论用软件方法实现互斥软件方法是为在具有一个处理器或共享主存的多处理器上执行的并发进程实现的 这种方法假定对主存中同一个单元的同时访问必定由存储器进行仲裁 使其串行化 下面的程序是采用标志方法实现互斥的一种尝试 进程进入临界区之后 设置自己的标志 进程进入临界区之前 先检查对方的临界区标志 只有对方不在临界区时 本进程才进入 boolinside1 false P1不在其临界区内 boolinside2 false P2不在其临界区内 cobeginprocessP1 while inside2 inside1 true 临界区 inside1 false processP2 while inside1 inside2 true 临界区 inside2 false coend这种方法是错误的 下面是一个说明错误的执行实例 全局共享变量 inside1 falseinside2 falseprocessP1 while inside2 此时inside2 false processP2 while inside1 此时inside2 false processP1 inside1 true 临界区 processP2 inside2 true 临界区 进程P1 P2同时进入了临界区 改进方案 进程一旦想进入临界区 即抢先把自己的标志设置为true 以防止对方再进入临界区 下面是第二个尝试 它会造成永远等待 boolinside1 false P1不在其临界区内 boolinside2 false P2不在其临界区内 cobeginprocessP1 inside1 true while inside2 临界区 inside1 false processP2 inside2 true while inside1 临界区 inside2 false coend 全局共享变量 inside1 falseinside2 falseprocessP1 inside1 true processP2 inside2 true processP1 while inside2 无限等待processP2 while inside1 无限等待 3 2 3实现临界区管理的软件方法 1 Peterson算法1981年 由Peterson提出 算法如下 boolinside 2 inside 0 false P0不在其临界区内 inside 1 false P1不在其临界区内 enum 0 1 turn 应该哪个进程进入临界区 cobeginprocessP0 inside 0 true turn 1 while inside 1 coend 算法分析与理解 两个进程同时执行时情况分析 全局共享变量 turn 1inside 0 falseinside 1 falseprocessP0processP1inside 0 true inside 1 true turn 1 turn 0 while inside 1 等待 临界区 inside 0 false while inside 0 andturn 0 不等待临界区 inside 1 false 一个进程单独执行时情况分析 全局共享变量 turn 1inside 0 falseinside 1 falseprocessP0inside 0 true turn 1 while inside 1 任何一个进程任何时候都可以自由连续多次进入临界区 而不需要通过两个进程交替执行才能进入临界区 进程P0只可能在while inside 1 处等待 在这里等待时 必定满足条件 inside 0 true且turn 0且inside 1 true 因为上述两组条件是互斥的 turn值不可能同时既为0又为1 不可能同时成立 因而两个进程P0 P1决不会同时等待 进入死锁状态 2 Dekker算法 选学 荷兰数学家T Dekker算法保证进程互斥地进入临界区 这是最早提出的一个软件互斥方法 Dekker算法用一个指示器turn来指示应该哪一个进程进入临界区 若turn 1则进程P1可以进入临界区 若turn 2则进程P2可以进入临界区 Dekker算法如下 boolinside 2 turn 1or2 inside 1 false inside 2 false cobegin processP1 inside 1 true whileinside 2 if turn 2 inside 1 false while turn 2 inside 1 true 临界区 turn 2 inside 1 false processP2begininside 2 true whileinside 1 if turn 1 inside 2 false while turn 1 inside 2 true 临界区 turn 1 inside 2 false end coend 下面是一个并发执行的实例分析 全局共享变量 turn 1 2 1inside 1 false true falseinside 2 false true false true falseprocessP1processP2inside 1 true inside 2 true While inside 2 if turn 2 不执行 inside 1 false 不执行While turn 2 不执行inside 1 true 不执行 不执行 processP1processP2whileinside 1 if turn 1 inside 2 false while turn 1 等待临界区 turn 2 while turn 1 inside 2 true 临界区 turn 1 inside 2 false inside 1 false end 两个进程P1 P2必须轮流进入临界区 一个进程单独执行时 最多只能进入临界区一次 进程P1只可能在while turn 2 处等待 在这里等待时 必定满足条件 turn 2且inside 1 false且inside 2 true 进程P2只可能在while turn 1 处等待 在这里等待时 必定满足条件 turn 1且inside 1 true且inside 2 false 因为上述两组条件是互斥的 不可能同时成立 因而两个进程P1 P2决不会同时等待 进入死锁状态 3 2 4实现临界区管理的硬件设施 在单处理器计算机中 并发进程只会交替执行 为了保持互斥 仅需要保证一个进程不被中断就可以了 管理临界区的软件尝试算法中用到了标志 在进入临界区之前需要首先测试标志 然后设置标志 这两个动作不能分开 否则 两个进程就可能同时进入临界区 用来实现互斥的硬件设施主要有 关中断 测试并建立指令 对换指令 1 关中断关中断是实现互斥的最简单方法之一 进程在测试标志之前 首先关中断 直到测试完并设置标志之后才开中断 进程在临界区执行期间 计算机系统不响应中断 因此 不会转向调度 也就不会引起进程或线程切换 正在执行标志测试和设置的进程或线程不会被打断 从而保证了互斥 关中断方法的缺点 滥用关中断权利可能导致严重后果 关中断时间过长会影响系统效率 限制处理器交叉执行程序的能力 关中断方法也不适用于多CPU系统 因为 在一个处理器上关中断 并不能防止进程在其他处理器上执行相同临界区代码 把关闭中断与否的权利赋予用户是很危险的 因为一旦用户没有打开中断 则系统可能因此终止工作 2 测试并建立指令硬件提供的测试并建立指令TS TestandSet 的执行过程如下 boolTS bool 用TS指令实现临界区管理 互斥 的算法如下 bools true 没有进程在临界区内cobeginprocessPi i 1 2 n while TS s 临界区 s true coend 3 对换指令对换 Swap 指令的功能是交换两个字的内容 处理过程