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 实现临界区管理的硬件设施回顾订票问题和主存管理问题l订票问题:多个售票进程交叉访问了共享 变量Ajl主存管理问题:borrow和returrn共享了 表示主存物理资源的变量x因此，对于具有竞争关系的若干进程因此，对于具有竞争关系的若干进程 并发执行必须加以限制并发执行必须加以限制临界区的基本概念l临界区(Critical Section) ：并发进程中 与共享变量有关的程序段l临界资源(Critical Resource) ：共享变量 代表的资源，如独占型硬件，被共享的 数据结构和文件临界区管理的问题l主要问题：与同一变量有关的临界区分 散在各进程的程序段中，而各进程的执 行速度不可预知。 l必须加以管理和限制：保证进程在临 界区执行时，不让另一个进程进入临界区，就不会造成与时间有关的错误。（ 实现对共享变量的互斥访问）临界区调度的原则（1）一次至多有一个进程 进入临界区执行； （2）如果已经有进程在临界区中，试图进入此 临界区的其他进程应等待 （3）进入临界区内的进程应在有限时间内退出 ，以便让等待队列中的一个进程进入互斥使用，有空让进； 忙则等待，有限等待，让权等待； 择一而入，算法可行。3.2 临界区管理3.2.1 互斥与临界区 3.2.2 临界区管理的尝试 3.2.3 实现临界区管理的软件方法 3.2.4 实现临界区管理的硬件设施临界区管理的尝试引入进程标志，分别指示进程进入临 界区的情况 第一种尝试，先测试，后置位 不能保证同一时间只有一个进程进入临界 区 第二种尝试，先置位，后测试 会出现死循环的情况，永远等待临界区管理的尝试一inside1,inside2:Boolean inside1 := false; /* P1不在其临界区内 */ inside2 := false; /* P2不在其临界区内 */ cobegin process P1 Beginwhile inside2 do begin end;inside1 := true;临界区;inside1 := false;end;process P2Beginwhile inside1 do begin end;inside2 = true;临界区;inside2 := false;end; coend问题：P1和P2 有可能同时进 入临界区inside1,inside2:Boolean inside1 := false; /* P1不在其临界区内 */ inside2 := false; /* P2不在其临界区内 */ cobegin process P1 Begininside1 := true;while inside2 do begin end;临界区;inside1 := false;end;process P2Begininside2 = true;while inside1 do begin end;临界区;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算法的具体实现/ 变量定义及初始化 bool inside2 inside0=false;inside1=false; enum0,1 turn; cobegin process P0( ) inside0 = true; turn = 1; while (inside1 and turn = 1) ; 临界区; inside0 := false;process P1( ) inside1 := true; turn := 0; while (inside0 and turn = 0); 临界区; inside1 := false;coend.进入临界区的条件： 对方不在临界区或不 想进入临界区基本思想： 用对turn的置值和while语句来限制每次 只有一个进程进入临界区； 进程执行完临界区程序后，修改insidei状 态使等待进入临界区的进程可在有限时间 内进入。 算法满足临界区管理的三个条件。软件解法的缺点1. 忙等待（busy waiting） 2. 实现过于复杂，需要高的编程技巧回顾:l顺序程序设计有哪些特征?l什么是并发程序设计?l进程之间有哪些关系?什么是同步与互斥?l有关的进程如果不加控制,会出现哪些错误?l什么是临界区和临界资源?l临界区管理有哪些原则?3.2 临界区管理3.2.1 互斥与临界区 3.2.2 临界区管理的尝试 3.2.3 实现临界区管理的软件方法 3.2.4 实现临界区管理的硬件设施l临界区管理的前两个尝试之所以不能正 确管理临界区，问题在于：测试和上锁这两个动作分开了,因为执 行过程中可能被中断while inside2 do begin end; inside1 := true;inside1 := true; while inside2 do begin end; 关键点关键点: : 保证不被中断或者测试完立即上琐保证不被中断或者测试完立即上琐硬件方法l1. 关中断l2. 测试并建立指令l3. 对换指令1. 关中断l基本方法: 在进程进入临界区时关中断, 进程退出临界区时开中断(阻止进程交替 执行)l特点：简单，有效；不通用，关中断时间过长会影响系统性能；不适用于多处理器；2. 测试并建立指令l基本方法:借助于机器指令TS，TS指令 能使测试和上琐不分离 /TS指令的处理过程 bool TS(bool return true;else return false; /TS指令实现互斥 bool s=true; cobegin process Pi()while(!TS(s);临界区;s=true; coend3. 对换指令l基本方法 ：借助于对换指令SWAP/swap实现过程 void SWAP(bool a=b;b=temp; /对换指令实现进程互斥 bool lock=false; cobegin process Pi()bool keyi=true;do SWAP(keyi,lock);while(keyi); 临界区； SWAP(keyi,lock); coend总结l众多进程对于临界资源的访问必须互斥 进行l软件方法和硬件方法的共同缺点:“忙等待”，不能实现“让权等待”的原则