操作系统42临界区管理课件

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