南京大学：《操作系统》课程教学资源（PPT课件）第三章（3.2）临界区管理

临界区管理 互尽与临界区 实现临界区管理的几种尝谜 实现临界区管理的软件方法 实现临界区管理的硬件设施

临界区管理 ⚫ 互斥与临界区 ⚫ 实现临界区管理的几种尝试 ⚫ 实现临界区管理的软件方法 ⚫ 实现临界区管理的硬件设施

互斥与临界区 ●并发进程中与共亨变量有关的程序段 ●对临界区的三个要求 ◇一次至多允许一个选程停留在临界区內 ◇一个进程不能无限地停留在临界区內 ◇一个进程不能无限地等待进入临界区 ●临界区的描迷 shared variable region variable do statement ●临界区的嵌使用 region x do .. region y do.... region y do[…. region x do[……]

互斥与临界区 ⚫并发进程中与共享变量有关的程序段 ⚫对临界区的三个要求 一次至多允许一个进程停留在临界区内 一个进程不能无限地停留在临界区内 一个进程不能无限地等待进入临界区 ⚫临界区的描述 shared variable region variable do statement ⚫临界区的嵌套使用 region x do [ … region y do [ … ] …] region y do [ … region x do [ … ] …]

临界区管理 inside inside: boolean inside false /*P1不在其临界区内*/ inside2:= false;/*P2不在其临界区内*/ process P1 process P2 egIn begin while inside do [ ]i while inside do []; inside 1 true i nsi de2= true 临界区 临界区; ins de1 false: ins ide2 false; en en

临界区管理 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； 临界区; inside2 := false； end;

临界区管理 ins idel inside: boolean inside:= false /*P1不在其临界区内*/ ins ide2: false /*P2不在其临界区内*/ process P1 process P2 begin beg ins ide1 true ins de2 true while inside do []; while inside do[ 1 临界区; 临界区; ins ide1 fa ai se nside2: false: end 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 [ ]； 临界区; inside2 := false； end;

Dekker算法 o var inside array [1..2 of Boolean; ●Turn: integer; ●turn 1 or 2 o inside [1]:=false o inside 2: =false;

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[]:=true while inside do if turn=2 then begin inside[l]: =false while turn=2 do begin end inside[1]:=true end 临界区; turn inside[1]:=false end

⚫ 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 o begin inside[2]: =true while insidelll do if turn=1 then begin inside[2]: false; while turn=1 do begin end inside[2: =true en d 临界区; turn =1 inside[2]: false ●end; ● coend

⚫ 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算法 ins idel, inside: boolean. turn: integer tur n nsi de1 : false /*P1不在其临界区内*/ inside:= false /*P2不在其临界区内*/ process P1 process P2 begin begin inside . true inside:= true turn 2 turn while(ins ide2 and turn=2) while (ins ide1 and turn=1) do begin end do begin end; 临界区; 临界区; inside false: inside false: end: end:

Peterson算法 inside1,inside2:boolean; turn:integer; turn := 1; inside1 := false; /* P1 不在其临界区内 */ inside2 := false; /* P2 不在其临界区内 */ process P1 begin inside1 := true； turn := 2； while (inside2 and turn=2) do begin end； 临界区; inside1 := false； end; p rocess P2 begin inside2 := true； turn := 1； while (inside1 and turn=1) do begin end； 临界区; inside2 := false； end;

实现临界区管理的硬件设施 0关中断 测试并建立指令TS(x) 若 x=true, AUx: =false; return true 否则 return false ●对换指令sWap(a,b) temp: =a; a: =b; b: temp

实现临界区管理的硬件设施 ⚫ 关中断 ⚫ 测试并建立指令TS(x): 若x=true， 则x:=false; return true； 否则return false; ⚫ 对换指令swap (a,b) temp:=a; a:=b; b:=temp;

则试并建立指令 s: boolean true: process Pi /*i=1 929···9 n米 pi: boolean begin repeat pi =TS (s)until pi 临界区; s true: end

测试并建立指令 s : boolean; s := true; process Pi /* i = 1,2,…,n */ pi : boolean; begin repeat pi := TS(s) until pi； 临界区; s := true； end;