第三章进程的同步与通信 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
procedure wait(s) var s:semaphore S. value-1: n block(S, L); 选 procedure signal(s) S value:=S value+1 IfS value <=0 then wakeup(S, L); 我的步与通信2 信号量集机制 AND型信号量集机制 A、B交替执行 向引入 process A: wait(Mutex) JuDmutex=0 进程A、B讨问共事据D和E s process B: wait(Mutex); JUEmutex=0 信号量 Mutex=1, Mute 则I process A process: wait(Mute);则 Mutex=1,阻嘉 wait(Mutex) wait(Mutex) 的发生死锁 wait(Mutex): AND同步机制的思想 Swait(s1S2,…Sn) Signal(s1, S2,...,Sn) For i=l to n do Endfor 将所有等待Si资源的进程移到就绪队列。 ndfor 将进程插入第i(Sik1)个管待队列 作系统|进程的 设该进程的程序计撒器到Swai操作的开始
6 操 作 系 统 | 进 程 的 同 步 与 通 信 31 CUIT 徐虹 procedure wait(s) var s:semaphore; begin S.value := S.value – 1; If S.value =1 and S2>=1 and … and Sn>=1 then For i:=1 to n do Si := Si – 1; Endfor Else 将进程插入第i（Si<1）个等待队列。 设置该进程的程序计数器到Swait操作的开始。 Endif 操 作 系 统 | 进 程 的 同 步 与 通 信 36 CUIT 徐虹 Ssignal(S1,S2,…,Sn) For i:=1 to n do Si := Si + 1; 将所有等待Si资源的进程移到就绪队列。 Endfor
一般“僧号量”机制 If si>=tI and s2>=t2 andand Sn>stn then For i:=l to n d 将所有等待Si资源的进程移到就绪队列。 将执行进程插入第i(Siti)个等待队列。 设置该进程的程序计数器到Swai操作的开始 3.3经典进程同步问题 个信号量,可每次 申请d个资源 同步的概念 Swait(S,1,1):记录型信号量(S1) 算进程和打印进程使用同一缓冲区Buf 或互斥信号量(S=1) 0):当S>=1,允许多个进 ocal PBuf 程进入某临界区;当S=0后,阻止任 的同步 At ComputerfChuf: Br While (Buf : NULL) 何进程进入临界区 Print(PBuft 异步环境 生产者消费者问题 进程都能以各自独立的,不可预知的 问题描述 速度向前推进 作系统|进程的 通过由n个环形缓冲区构成的 进程同步 缓冲池,把生产者P1,P2,… 相互合作的进程之间需要交换一定的 PM和一群消贵者Cl,C2, 信息,当某进程未获得其合作进程发来的 CK联系起来 信息之前,该进程等待,宜到该信息到来 算法描述 时才被唤继续执行,从而保证诸进程的 协调运行
7 操 作 系 统 | 进 程 的 同 步 与 通 信 37 CUIT 徐虹 ¾一般“信号量”机制 Swait(S1,t1,d1;…;Sn,tn,dn) If S1>=t1 and S2>=t2 and … and Sn>=tn then For i:=1 to n do Si := Si – di; Endfor Else 将执行进程插入第i（Si1） 或互斥信号量（S=1）； ¾ Swait(S,1,0)：当S>=1，允许多个进 程进入某临界区；当S=0后，阻止任 何进程进入临界区。 操 作 系 统 | 进 程 的 同 步 与 通 信 40 CUIT 徐虹 3．3 经典进程同步问题 ¾同步的概念 例：计算进程和打印进程使用同一缓冲区Buf。 Pc： …… Pp： …… local Cbuf local PBuf A： Computer(Cbuf); B： While (Buf != NULL) While (CBuf!= NULL) Buf——> PBuf CBuf ——>Buf Print(PBuf)； Goto A; Goto B; 操 作 系 统 | 进 程 的 同 步 与 通 信 41 CUIT 徐虹 ¾异步环境 相互合作的一组并发进程，其中每 一进程都能以各自独立的，不可预知的 速度向前推进。 ¾进程同步 相互合作的进程之间需要交换一定的 信息，当某进程未获得其合作进程发来的 信息之前，该进程等待，直到该信息到来 时才被唤醒继续执行，从而保证诸进程的 协调运行。 操 作 系 统 | 进 程 的 同 步 与 通 信 42 CUIT 徐虹 ¾生产者—消费者问题 ¾问题描述 通过由n个环形缓冲区构成的 缓冲池，把生产者P1，P2，……， PM和一群消费者C1，C2，……， CK联系起来。 ¾算法描述
b11121b3国4 buffer:array O,..., n-1 of item; --…- in, out:integer: =0.0; 我的同步与通信4 producer: begin repeat wait(full) next product; wait(mutex) ait(empty); out: =(out+1)mod n: signal(empty); in :=(in+1)mod n 的同步 signal(mutex) 46 wait(empty) wait(full empty>=0则数据送入级冲区 full>=0则从级冲区取走数据 empty 被阻(瀹 ful0 empty<=0释放一个空缓冲区,唤腹一个 作系统|进程的 full<=0数据装入缓冲区,唤一个 阻塞的生产者进程 阻塞的消费者进程
8 操 作 系 统 | 进 程 的 同 步 与 通 信 43 CUIT 徐虹 操 作 系 统 | 进 程 的 同 步 与 通 信 44 CUIT 徐虹 变量定义： begin Var mutex,empty,full:semaphore:=1,n,0; buffer:array[0,…,n-1] of item; in,out:integer := 0,0; 操 作 系 统 | 进 程 的 同 步 与 通 信 45 CUIT 徐虹 parbegin producer: begin repeat produce next product ; wait (empty); wait (mutex); buffer(in):=nextp ; in := (in+1) mod n ; signal (full); signal (mutex); until false ; end 操 作 系 统 | 进 程 的 同 步 与 通 信 46 CUIT 徐虹 consumer: begin repeat wait (full); wait (mutex); nextc := buffer(out); out := (out+1) mod n; signal (empty); signal (mutex); consume the item in nextc; until false ; end parend end 操 作 系 统 | 进 程 的 同 步 与 通 信 47 CUIT 徐虹 wait(empty) empty >= 0 则数据送入缓冲区 empty 0 empty = 0 则从缓冲区取走数据 full 0 full <= 0 数据装入缓冲区，唤醒一个 阻塞的消费者进程
≯注意 >读者—写者问题 互斥和同步信号量的原语必须成对 读者进程 siga操作的次序无关紧要,但wait 写者进程(互斥的存取共享对象 操作的次序不能顺倒,否则会造成 系解决读写问题导致饥饿现象 死 class readersandwriters t 用AND信号量解决生产者消 贵者问题 int headcount: 的同多与通信0 semaphore x=new semaphore(1); semaphore wsem= new semaphore(1); ,xe public void reader i hile(true) wait(x); ublic void writer i headcount++: while(true)i wait(wsem); WRITEUNTO signal(x); signal(wsem READUNITO 的同步 public static void main(String args)i f(headcount==0) =0; signal(wsem) parbegin(reader, writer signal(x):) 1 哲学家进餐问题 public class diningphilosophers i semaphore fork=new semaphore 5(1) int 1: 作系统|进程的
9 操 作 系 统 | 进 程 的 同 步 与 通 信 49 CUIT 徐虹 ¾注意： ¾互斥和同步信号量的原语必须成对 出现。 ¾signal操作的次序无关紧要，但wait 操作的次序不能颠倒，否则会造成 死锁。 ¾用AND信号量解决生产者——消 费者问题 操 作 系 统 | 进 程 的 同 步 与 通 信 50 CUIT 徐虹 ¾读者——写者问题 读者进程 写者进程(互斥的存取共享对象) 解决读写问题,导致饥饿现象 public class readersandwriters { int readcount; semaphore x = new semaphore(1); semaphore wsem = new semaphore(1); 操 作 系 统 | 进 程 的 同 步 与 通 信 51 CUIT 徐虹 public void reader() { while (true) { wait (x); readcount++; if (readcount == 1) wait (wsem); signal (x); READUNIT(); wait (x); readcount--; if (readcount == 0) signal (wsem); signal (x); } } 操 作 系 统 | 进 程 的 同 步 与 通 信 52 CUIT 徐虹 public void writer() { while (true) { wait (wsem); WRITEUNIT(); signal (wsem); } } public static void main (String args[]) { readcount = 0; parbegin (reader, writer); } 操 作 系 统 | 进 程 的 同 步 与 通 信 53 CUIT 徐虹 ¾哲学家进餐问题 操 作 系 统 | 进 程 的 同 步 与 通 信 54 CUIT 徐虹 public class diningphilosophers { semaphore [] fork = new semaphore[5](1); int i;
public void philosopher(int i)i parbegin(philosopher(0), wait(fork) wait(fork (i+1)%5); eato: 程的同步与通信 philosopher(4)); signal(fork [(i+1)%5D; signal(fork) 解决死锁的方法: 3.4 管程机制 至多允许四个哲学家同时进餐 仅当哲学家的左右两支叉子均可用时 管程的引入 进餐。(用AND信号量机制解决哲 学家进餐问题。) 管程的基本概念 奇数号哲学家先拿左边的叉子,偶数 >管程的定义 哲学家先拿右边的叉子。 条件变量 >利用管程解决生产者—消费者 问题 >利用管程解决哲学家进餐问题 final static int LEFT=(i-1)mod N; final static int RIGHT=(i+1)mod N; aa final static int THINKING=0 final static int EATING=2
10 操 作 系 统 | 进 程 的 同 步 与 通 信 55 CUIT 徐虹 public void philosopher (int i) { while (true) { think(); wait (fork[i]); wait (fork [(i+1) % 5]); eat(); signal(fork [(i+1) % 5]); signal(fork[i]); } } 操 作 系 统 | 进 程 的 同 步 与 通 信 56 CUIT 徐虹 public static void main() { parbegin (philosopher (0), philosopher (1), philosopher (2), philosopher (3), philosopher (4)); } } 操 作 系 统 | 进 程 的 同 步 与 通 信 57 CUIT 徐虹 ¾解决死锁的方法： ¾至多允许四个哲学家同时进餐。 ¾仅当哲学家的左右两支叉子均可用时， 才进餐。（用AND信号量机制解决哲 学家进餐问题。） ¾奇数号哲学家先拿左边的叉子，偶数 号哲学家先拿右边的叉子。 操 作 系 统 | 进 程 的 同 步 与 通 信 58 CUIT 徐虹 3 . 4 管程机制 ¾管程的引入 ¾管程的基本概念 ¾管程的定义 ¾条件变量 ¾利用管程解决生产者——消费者 问题 操 作 系 统 | 进 程 的 同 步 与 通 信 59 CUIT 徐虹 操 作 系 统 | 进 程 的 同 步 与 通 信 60 CUIT 徐虹 ¾利用管程解决哲学家进餐问题 Monitor forks; final static int N = 5; final static int LEFT = (i-1) mod N; final static int RIGHT = (i+1) mod N; final static int THINKING = 0; final static int HUNGRY = 1; final static int EATING = 2;