临界区管理
互斥与临界区
实现临界区管理的几种尝试
实现临界区管理的软件方法
实现临界区管理的硬件设施互斥与临界区
并发进程中与共享变量有关的程序段
对临界区的三个要求
一次至多允许一个进程停留在临界区内
一个进程不能无限地停留在临界区内
一个进程不能无限地等待进入临界区
临界区的描述
shared variable
region variable do statement
临界区的嵌套使用
region x do [ … region y do [ … ] … ]
region y do [ … region x do [ … ] … ]
临界区管理
inside1,inside2:boolean;
inside1,= false; /* P1 不在其临界区内 */
inside2,= false; /* P2 不在其临界区内 */
process P1
begin
w h i l e i n s i d e 2 d o [ ] ；
inside1,= true ；
临界区 ;
inside1,= false ；
end;
process P2
begin
w h i l e i n s i d e 1 d o [ ] ；
inside2 = true ；
临界区 ;
insi de2,= false ；
end;
临界区管理
inside1,inside2:boolean;
inside1,= false; /* P1 不在其临界区内 */
inside2,= false; /* P2 不在其临界区内 */
process P1
begin
inside1,= true ；
w h i l e i n s i d e 2 d o [ ] ；
临界区 ;
inside1,= false ；
end;
process P2
begin
inside2,= true ；
w h i l e i n s i d e 1 d o [ ] ；
临界区 ;
ins ide2,= false ；
end;
Dekker算法
var inside,array[1..2] of Boolean;
Turn,integer;
turn,= 1 or 2;
inside[1]:=false;
inside[2]:=false;
cobegin
process P1
begin
inside[1]:=true;
while inside[2] do if turn=2 then
begin
inside[1]:=false;
while turn=2 do begin end;
inside[1]:=true;
end
临界区 ;
turn = 2；
inside[1]:=false;
end;
process P2
begin
inside[2]:=true;
while inside[1] do if turn=1 then
begin
inside[2]:=false;
while turn=1 do begin end;
inside[2]:=true;
end
临界区 ;
turn = 1；
inside[2]:=false;
end;
coend
Peterson算法
inside1,inside2:boolean;
turn:integer;
turn,= 1;
inside1,= false; /* P1 不在其临界区内 */
inside2,= false; /* P2 不在其临界区内 */
process P1
begin
inside1,= true ；
turn,= 2 ；
w h i l e ( i n s i d e 2 a n d t u r n = 2 )
do begin end ；
临界区 ;
inside1,= false ；
end;
pr ocess P2
begin
inside2,= true ；
turn,= 1 ；
w h i l e ( i n s i d e 1 a n d t u r n = 1 )
do begin end ；
临界区 ;
inside2,= false ；
end;
实现临界区管理的硬件设施
关中断
测试并建立指令 TS(x):
若 x=true，
则 x:=false; return true；
否则 return false;
对换指令 swap (a,b)
temp:=a; a:=b; b:=temp;
测试并建立指令
s,boolean;
s,= true;
process Pi /* i = 1,2,…,n */
pi,boolean;
begin
repeat pi,= TS(s) until pi；
临界区 ;
s,= true；
end;
对换指令
lock,boolean;
lock,= false;
process Pi /* i = 1,2,…,n*/
pi,boolean;
begin
pi,= true;
repeat swap(lock,pi) until pi = false；
临界区 ;
lock,= false；
end;