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