操作系统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,因此，对于具有竞争关系的若干进程并发执行必须加以限制,临界区的基本概念,临界区(Critical Section)：并发进程中与共享变量有关的程序段临界资源(Critical Resource)：共享变量代表的资源，如独占型硬件，被共享的数据结构和文件,临界区管理的问题,主要问题：与同一变量有关的临界区分散在各进程的程序段中，而各进程的执行速度不可预知。必须加以管理和限制：保证进程在临界区执行时，不让另一个进程进入临界区，就不会造成与时间有关的错误。（实现对共享变量的互斥访问）,临界区调度的原则,（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不在其临界区内*/cobeginprocess P1Begin while inside2 do begin end;inside1:=true;临界区;inside1:=false;end;process P2 Begin while inside1 do begin end;inside2=true;临界区;inside2:=false;end;coend,问题：P1和P2有可能同时进入临界区,inside1,inside2:Booleaninside1:=false;/*P1不在其临界区内*/inside2:=false;/*P2不在其临界区内*/cobeginprocess P1Begin inside1:=true;while inside2 do begin end;临界区;inside1:=false;end;process P2 Begin inside2=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 inside2inside0=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.实现过于复杂，需要高的编程技巧,回顾:,顺序程序设计有哪些特征?什么是并发程序设计?进程之间有哪些关系?什么是同步与互斥?有关的进程如果不加控制,会出现哪些错误?什么是临界区和临界资源?临界区管理有哪些原则?,3.2 临界区管理,3.2.1 互斥与临界区3.2.2 临界区管理的尝试3.2.3 实现临界区管理的软件方法3.2.4 实现临界区管理的硬件设施,临界区管理的前两个尝试之所以不能正确管理临界区，问题在于：测试和上锁这两个动作分开了,因为执行过程中可能被中断,while inside2 do begin end;inside1:=true;,inside1:=true;while inside2 do begin end;,关键点:保证不被中断或者测试完立即上琐,硬件方法,1.关中断2.测试并建立指令3.对换指令,1.关中断,基本方法:在进程进入临界区时关中断,进程退出临界区时开中断(阻止进程交替执行)特点：简单，有效；不通用，关中断时间过长会影响系统性能；不适用于多处理器；,2.测试并建立指令,基本方法:借助于机器指令TS，TS指令能使测试和上琐不分离,/TS指令的处理过程bool TS(bool,/TS指令实现互斥bool s=true;cobeginprocess Pi()while(!TS(s);临界区;s=true;coend,3.对换指令,基本方法：借助于对换指令SWAP,/swap实现过程void SWAP(bool,/对换指令实现进程互斥bool lock=false;cobeginprocess Pi()bool keyi=true;do SWAP(keyi,lock);while(keyi);临界区；SWAP(keyi,lock);coend,总结,众多进程对于临界资源的访问必须互斥进行软件方法和硬件方法的共同缺点:“忙等待”，不能实现“让权等待”的原则,
