第三章进程的同步与通信 3.1进程互斥 并发执行的进程之间的关系 >并发引起的操作系统的改变 操作系统必须记住各种活跃的进程 须为每个进程分配和释放各种资源 根>进程的互斥与同步问题 保护每个进程的数据和物理资源 进程的结果必须与执行速度无关 >进程间的高级通信 程的同步与通信 进程间的制约 例1:两个进程对同一变量 count访问和修改, 自独立的速度向前推进。但由于资源共 及进程合作(即诸进程协同完成一项共 着 count=5。 P1: R1= coun 同的任务),因而产生了进程之间的相互 R1=R1+1 临界区 count= R1; 临界资源( Critical resource):一次 4 P2: R2=count 仅允许一个进程使用的资源。 R2=R2-1; 着顺序执行P1、P2,则 count:=5 Pl: RI= count: Pl: RI= count: 例2进程P、P2共同调用函数echo0。 2: R2= count R=R1+1; void echo o Pl: RI=RI+1 R2=R2 chin getchar( P2:R2=R2-1; count= R2 putchar(chou count=R2: Pl: count=RI 作系统|进程的 若执行顺序如上, 若执行顺序如上
1 操 作 系 统 | 进 程 的 同 步 与 通 信 1 CUIT 徐虹 第三章 进程的同步与通信 ¾并发执行的进程之间的关系 ¾进程的互斥与同步问题 ¾进程间的高级通信 操 作 系 统 | 进 程 的 同 步 与 通 信 2 CUIT 徐虹 3．1 进程互斥 ¾并发引起的操作系统的改变 ¾操作系统必须记住各种活跃的进程 ¾必须为每个进程分配和释放各种资源 ¾保护每个进程的数据和物理资源 ¾进程的结果必须与执行速度无关 操 作 系 统 | 进 程 的 同 步 与 通 信 3 CUIT 徐虹 ¾进程间的制约 系统中的诸进程可以共行执行，并以 各自独立的速度向前推进。但由于资源共 享及进程合作（即诸进程协同完成一项共 同的任务），因而产生了进程之间的相互 制约。 ¾临界区 ¾临界资源（Critical Resource）：一次 仅允许一个进程使用的资源。 操 作 系 统 | 进 程 的 同 步 与 通 信 4 CUIT 徐虹 例1：两个进程对同一变量count访问和修改， P1： count+=1; P2： count-=1; 若 count = 5。 P1： R1 = count; R1 = R1+1; count = R1; P2： R2 = count; R2 = R2 – 1 ; count = R2; 若顺序执行P1、P2，则count = 5。 操 作 系 统 | 进 程 的 同 步 与 通 信 5 CUIT 徐虹 P1： R1 = count; P1：R1 = count; P2： R2 = count; R1 = R1+1; P1： R1 = R1+1; P2：R2 = count; count = R1; R2 = R2 – 1; P2： R2 = R2 – 1; count = R2; count = R2; P1： count = R1; 若执行顺序如上， 若执行顺序如上， 则count = 4 则count = 6。 操 作 系 统 | 进 程 的 同 步 与 通 信 6 CUIT 徐虹 例2. 进程P1、P2共同调用函数echo() 。 void echo() { chin = getchar(); chout = chin; putchar(chout); }
729 一临界区:不允许多个并发进程交又执行的一段程序 Pr。 cess E1 Process P2 process lt begin w chin getchar oi chin getchar o Remainder of process 1: Goto LI 跳 chou=chin chin putchar(chou L2: C putchar(chou) Remainder of process 2: Goto L2 coend 互斥 互斥的软件实现 不允许两个以上的共事该资源的并 进程P,P共享临界资源R。Turn进程编号 发进程同时进入临界区称为互斥 算法1:共享一个公用整型变量 临界区调度原则 空闲让进 E while turn ei do no 忙则等待 有限等待 系统|程的同步 critical section 让权等待 remainder sectio 3→算法2:用数组代替算法一中的um var flag array [0... n of boolean=flase; 算法3 while flaglil do no op flag i: true critical section 作系统|进程的 fagi: =true while flagljl do no op; fagi: false remainder section remainder section until false;
2 操 作 系 统 | 进 程 的 同 步 与 通 信 7 CUIT 徐虹 Process P1 Process P2 . . chin = getchar(); . . chin = getchar(); chout = chin; . chout = chin; putchar(chout); . . putchar(chout); . . 操 作 系 统 | 进 程 的 同 步 与 通 信 8 CUIT 徐虹 ¾临界区：不允许多个并发进程交叉执行的一段程序。 cobegin process 1： begin L1：CS1; Remainder of process 1; Goto L1; end process 2：begin L2：CS2; Remainder of process 2; Goto L2; end coend 操 作 系 统 | 进 程 的 同 步 与 通 信 9 CUIT 徐虹 ¾互斥 ¾不允许两个以上的共享该资源的并 发进程同时进入临界区称为互斥。 ¾临界区调度原则 ¾空闲让进 ¾忙则等待 ¾有限等待 ¾让权等待 操 作 系 统 | 进 程 的 同 步 与 通 信 10 CUIT 徐虹 ¾互斥的软件实现 进程Pi，Pj共享临界资源R。Turn：进程编号。 ¾算法1：共享一个公用整型变量turn Pi :repeat while turn <> i do no_op; critical section turn := j; remainder section until false; 操 作 系 统 | 进 程 的 同 步 与 通 信 11 CUIT 徐虹 ¾算法2：用数组代替算法一中的turn var flag : array [0… n] of boolean = flase; repeat while flag[j] do no_op; flag[i] := true ; critical section flag[i] := false ; remainder section until false ; 操 作 系 统 | 进 程 的 同 步 与 通 信 12 CUIT 徐虹 ¾算法3： repeat flag[i] : = true ; while flag[j] do no_op; critical section flag[i] := false ; remainder section until false ;
算法5:对临界区S设置个变量状态W 算法4进程共享两个公用变量 W=0表示资源可用,W=1表示资源已被占用 N flag]: =true It lock W: CSI: Unlock w Remainder of process 1: while flaglil and turn=j)do no op: Goto LI fagi: =false remainder section until false 的同步与通信4 L2: lock W: CS2: Unlock w 关锁原语 开锁原语 lock WI if w=1 then unlock w if WLo NULL then begin block(n); remove(WL, q): insert(WL, n); q)=“ ready”; 的同步 insert(RL, ) 硬件实现进程互斥 利用 Test and set指令 利用TS指令实现互斥 begin while Ts (lock) do skip; TS: = lock critical section Lock:= true 作系统|进程的 maunder section Lock=true:资源被占用 Lock= false:资源可用
3 操 作 系 统 | 进 程 的 同 步 与 通 信 13 CUIT 徐虹 ¾算法4：进程共享两个公用变量 Pi: repeat flag[i] : = true ; turn := j ; while ( flag[j] and turn = j ) do no_op; critical section flag[i] := false ; remainder section until false ; 操 作 系 统 | 进 程 的 同 步 与 通 信 14 CUIT 徐虹 ¾算法5：对临界区S设置一个变量状态W， W=0表示资源可用，W=1表示资源已被占用。 例：Begin integer W = 0 ; Cogegin Begin L1：lock W; CS1; Unlock W; Remainder of process 1; Goto L1; End Begin L2：lock W; CS2; Unlock W; Remainder of process 2; Goto L2; End Coend End 操 作 系 统 | 进 程 的 同 步 与 通 信 15 CUIT 徐虹 ¾关锁原语 lock W： if W = 1 then begin block(n); insert(WL,n); scheduler; end else W = 1; 操 作 系 统 | 进 程 的 同 步 与 通 信 16 CUIT 徐虹 ¾开锁原语 unlock W： if WL<> NULL then begin remove(WL,q); status(q) = “ready”; insert(RL,q); end else W = 0; 操 作 系 统 | 进 程 的 同 步 与 通 信 17 CUIT 徐虹 ¾硬件实现进程互斥 ¾利用Test_and_Set 指令 function TS (var lock : boolean ) : boolean ; begin TS := lock ; Lock := true ; End Lock = true ：资源被占用 Lock = false ：资源可用 操 作 系 统 | 进 程 的 同 步 与 通 信 18 CUIT 徐虹 利用TS指令实现互斥： repeat while TS (lock) do skip ; critical section lock := false ; remainder section until false ;
一利用Swap指令实现进程互斥 初值lck= false表示资源可用。 s Procedure Swa key = true Var temp: boolean Swap(lock, key): Until key= false ritical section := b lock: = false remainder section until false 3.2信号量机制 wait(P)和 Signal(v)原语 整型信号量机制 wait(s)a Begin sem>=0:表示可供并发进程使用的资源实体的个歌 Lock out interrupts sem<0:表示正在等特使用帧界区的进程数。 If s<0 then Begin Sem的值只能由P、Ⅴ操作改变 Status(q)t =blocked; Pt wait( s 的同步 Unlock interrupts; Scheduler 按信号量数值分为二元信号和信号量 22 End sIgna原语 利用信号量实现互斥 Lock out interrupts; processIt Begin LIn wait (mutex): CsI; signal(mutex): Remainder of process If s<=0 then Begin Goto LI atus(R)I Insert(RL, R 作系统|进程的 Process2: Begin L2t wait(mutex ): CS2; Unlock interrupts: Coend
4 操 作 系 统 | 进 程 的 同 步 与 通 信 19 CUIT 徐虹 ¾利用Swap指令实现进程互斥 初值lock = false 表示资源可用。 Procedure Swap (var a,b : boolean) Var temp : boolean ; Begin Temp := a ; a := b ; b := temp ; End 操 作 系 统 | 进 程 的 同 步 与 通 信 20 CUIT 徐虹 repeat key := true ; repeat Swap(lock,key) ; Until key = false ; critical section lock := false ; remainder section until false ; 操 作 系 统 | 进 程 的 同 步 与 通 信 21 CUIT 徐虹 3． 2 信号量机制 ¾ 整型信号量机制 ¾ 信号量(sem) sem>=0: 表示可供并发进程使用的资源实体的个数 sem<0: 表示正在等待使用临界区的进程数。 Sem的值只能由P、V操作改变。 P：wait ( s ) V：signal (s ) 按信号量数值分为二元信号量和一般信号量。 操 作 系 统 | 进 程 的 同 步 与 通 信 22 CUIT 徐虹 ¾Wait（P）和signal（V）原语 ¾Wait(s) 原语 wait(s) ：Begin Lock out interrupts; s = s – 1; If s < 0 then Begin Status(q) ：= blocked; Insert(WL, q); Unlock interrupts; Scheduler; End Else unlock interrupts; End 操 作 系 统 | 进 程 的 同 步 与 通 信 23 CUIT 徐虹 ¾signal原语 signal(s) ：Begin Lock out interrupts; s = s + 1; If s < =0 then Begin Remove(WL，R); Status(R) ：= ready; Insert(RL，R); End Unlock interrupts; End 操 作 系 统 | 进 程 的 同 步 与 通 信 24 CUIT 徐虹 ¾利用信号量实现互斥 Begin integer mutex = 1; cobegin process1：Begin L1：wait (mutex);CS1; signal (mutex); Remainder of process 1; Goto L1; End Process2： Begin L2：wait (mutex);CS2; signal (mutex); Remainder of process 2; Goto L2; End Coend End
◆例、进程A、B、c依赖于D的結果 ■■■ Ready List ∏人∵ 程的同步与通信 Ready List 例:根据前趋图写出可并发执行的程序: 利用信号量描述前趋关系 var a, b, c, d, e, f, g, h: semaphore: =0,0,0,0,0,0,0,0 P2:S2 选则设置信号量s=0, a Pl: SI: signal(s) 的同步 P2: Wait(s): $2 begin SI; signal(a); signal(b); signal(c); end 记录型信号量机制 begin wait(a); S2; signal(d); end b type semaphore -=re begin wait(b); S3; signal(e), end 系统|遗程的 L: list of process begin wait(e), wait(f), S6; signal( h); end begin wait(g), wait(h); S7; end
5 操 作 系 统 | 进 程 的 同 步 与 通 信 25 CUIT 徐虹 例、进程A、B、C依赖于D的结果 操 作 系 统 | 进 程 的 同 步 与 通 信 26 CUIT 徐虹 操 作 系 统 | 进 程 的 同 步 与 通 信 27 CUIT 徐虹 ¾利用信号量描述前趋关系 P1：S1 P2：S2 S1——>S2 则设置信号量s=0， P1：S1；signal(s)； P2：Wait(s)；S2； 操 作 系 统 | 进 程 的 同 步 与 通 信 28 CUIT 徐虹 1 2 3 4 5 6 7 a b c d e f g h 例：根据前趋图写出可并发执行的程序： var a,b,c,d,e,f,g,h:semaphore := 0,0,0,0,0,0,0,0; 操 作 系 统 | 进 程 的 同 步 与 通 信 29 CUIT 徐虹 begin parbegin begin S1;signal(a); signal(b); signal(c); end begin wait(a); S2; signal(d); end begin wait(b); S3; signal(e); end begin wait(c); S4; signal(f); end begin wait(d); S5; signal(g); end begin wait(e); wait(f); S6 ; signal( h); end begin wait(g); wait(h); S7; end parend end 操 作 系 统 | 进 程 的 同 步 与 通 信 30 CUIT 徐虹 ¾记录型信号量机制 type semaphore = record value:integer; L:list of process; end