操作系统4.2临界区管理.ppt

3 2临界区管理 3 2 1互斥与临界区3 2 2临界区管理的尝试3 2 3实现临界区管理的软件方法3 2 4实现临界区管理的硬件设施 3 2临界区管理 3 2 1互斥与临界区3 2 2临界区管理的尝试3 2 3实现临界区管理的软件方法3 2 4实现临界区管理的硬件设施 回顾订票问题和主存管理问题 订票问题 多个售票进程交叉访问了共享变量Aj主存管理问题 borrow和returrn共享了表示主存物理资源的变量x 因此 对于具有竞争关系的若干进程并发执行必须加以限制 临界区的基本概念 临界区 CriticalSection 并发进程中与共享变量有关的程序段临界资源 CriticalResource 共享变量代表的资源 如独占型硬件 被共享的数据结构和文件 临界区管理的问题 主要问题 与同一变量有关的临界区分散在各进程的程序段中 而各进程的执行速度不可预知 必须加以管理和限制 保证进程在临界区执行时 不让另一个进程进入临界区 就不会造成与时间有关的错误 实现对共享变量的互斥访问 临界区调度的原则 1 一次至多有一个进程进入临界区执行 2 如果已经有进程在临界区中 试图进入此临界区的其他进程应等待 3 进入临界区内的进程应在有限时间内退出 以便让等待队列中的一个进程进入 互斥使用 有空让进 忙则等待 有限等待 让权等待 择一而入 算法可行 3 2临界区管理 3 2 1互斥与临界区3 2 2临界区管理的尝试3 2 3实现临界区管理的软件方法3 2 4实现临界区管理的硬件设施 临界区管理的尝试 引入进程标志 分别指示进程进入临界区的情况第一种尝试 先测试 后置位不能保证同一时间只有一个进程进入临界区第二种尝试 先置位 后测试会出现死循环的情况 永远等待 临界区管理的尝试一 inside1 inside2 Booleaninside1 false P1不在其临界区内 inside2 false P2不在其临界区内 cobeginprocessP1Begin whileinside2dobeginend inside1 true 临界区 inside1 false end processP2Begin whileinside1dobeginend inside2 true 临界区 inside2 false end coend 问题 P1和P2有可能同时进入临界区 inside1 inside2 Booleaninside1 false P1不在其临界区内 inside2 false P2不在其临界区内 cobeginprocessP1Begin inside1 true whileinside2dobeginend 临界区 inside1 false end processP2Begin inside2 true whileinside1dobeginend 临界区 inside2 false end coend 临界区管理的尝试二 问题 P1和P2有可能永远进不了临界区 3 2临界区管理 3 2 1互斥与临界区3 2 2临界区管理的尝试3 2 3实现临界区管理的软件方法3 2 4实现临界区管理的硬件设施 实现临界区管理的软件算法 1 Dekker算法算法复杂难以理解 2 Peterson算法 Peterson算法的具体实现 变量定义及初始化boolinside 2 inside 0 false inside 1 false enum 0 1 turn cobegin processP0 inside 0 true turn 1 while inside 1 andturn 1 临界区 inside 0 false processP1 inside 1 true turn 0 while inside 0 andturn 0 临界区 inside 1 false coend 进入临界区的条件 对方不在临界区或不想进入临界区 基本思想 用对turn的置值和while语句来限制每次只有一个进程进入临界区 进程执行完临界区程序后 修改insidei状态使等待进入临界区的进程可在有限时间内进入 算法满足临界区管理的三个条件 软件解法的缺点 1 忙等待 busywaiting 2 实现过于复杂 需要高的编程技巧 回顾 顺序程序设计有哪些特征 什么是并发程序设计 进程之间有哪些关系 什么是同步与互斥 有关的进程如果不加控制 会出现哪些错误 什么是临界区和临界资源 临界区管理有哪些原则 3 2临界区管理 3 2 1互斥与临界区3 2 2临界区管理的尝试3 2 3实现临界区管理的软件方法3 2 4实现临界区管理的硬件设施 临界区管理的前两个尝试之所以不能正确管理临界区 问题在于 测试和上锁这两个动作分开了 因为执行过程中可能被中断 whileinside2dobeginend inside1 true inside1 true whileinside2dobeginend 关键点 保证不被中断或者测试完立即上琐 硬件方法 1 关中断2 测试并建立指令3 对换指令 1 关中断 基本方法 在进程进入临界区时关中断 进程退出临界区时开中断 阻止进程交替执行 特点 简单 有效 不通用 关中断时间过长会影响系统性能 不适用于多处理器 2 测试并建立指令 基本方法 借助于机器指令TS TS指令能使测试和上琐不分离 TS指令的处理过程boolTS bool TS指令实现互斥bools true cobeginprocessPi while TS s 临界区 s true coend 3 对换指令 基本方法 借助于对换指令SWAP swap实现过程voidSWAP bool 对换指令实现进程互斥boollock false cobeginproces