os-3

操作

系

统

|

进程的同步与通信1CUIT 徐虹第三章进程的同步与通信

¾

并发执行的进程之间的关系¾进程的互斥与同步问题¾进程间的高级通信操作系统|进程的同步与通信2CUIT 徐虹3．1进程互斥¾并发引起的操作系统的改变¾操作系统必须记住各种活跃的进程¾必须为每个进程分配和释放各种资源¾保护每个进程的数据和物理资源¾进程的结果必须与执行速度无关操作

系

统

|

进程的同步与通信3CUIT 徐虹¾进程间的制约系统中的诸进程可以共行执行，并以各自独立的速度向前推进。但由于资源共享及进程合作（即诸进程协同完成一项共同的任务），因而产生了进程之间的相互制约。¾临界区¾临界资源（Critical Resource）：一次仅允许一个进程使用的资源。操作系统|进程的同步与通信4CUIT 徐虹例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。操作

系

统

|

进程的同步与通信5CUIT 徐虹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。操作系统|进程的同步与通信6CUIT 徐虹例2. 进程P1、P2共同调用函数echo()。void echo(){chin =getchar();chout= chin;putchar(chout); }操作

系

统

|

进程的同步与通信7CUIT 徐虹Process P1Process P2..chin =getchar();..chin =getchar();chout= chin;. chout

= chin;putchar(chout);..putchar(chout);..操作系统|进程的同步与通信8CUIT 徐虹¾临界区：不允许多个并发进程交叉执行的一段程序。cobeginprocess 1：beginL1：CS1;Remainder of process 1;GotoL1;endprocess 2：beginL2：CS2;Remainder of process 2;GotoL2;endcoend

操作系统|进程的同步与通信9CUIT 徐虹¾互斥¾不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。¾临界区调度原则¾空闲让进¾忙则等待¾有限等待¾让权等待操作系统|进程的同步与通信10CUIT 徐虹¾互斥的软件实现进程Pi，Pj共享临界资源R。Turn：进程编号。¾算法1：共享一个公用整型变量turnPi :repeatwhile turn <> i do no_op;critical sectionturn := j;remainder sectionuntil false;

操作系统|进程的同步与通信11CUIT 徐虹¾算法2：用数组代替算法一中的turnvar flag : array [0…n] ofboolean=flase;repeatwhile flag[j] do no_op;flag[i] := true ;critical sectionflag[i] := false ;remainder sectionuntil false ;操作系统|进程的同步与通信12CUIT 徐虹¾算法3：repeatflag[i] : = true ;while flag[j] do no_op;critical sectionflag[i] := false ;remainder sectionuntil false ;操作

系

统

|

进程的同步与通信13CUIT 徐虹¾算法4：进程共享两个公用变量Pi: repeatflag[i] : = true ;turn := j ;while ( flag[j] and turn = j ) do no_op;critical sectionflag[i] := false ;remainder sectionuntil false ;操作系统|进程的同步与通信14CUIT 徐虹¾算法5：对临界区S设置一个变量状态W，W=0表示资源可用，W=1表示资源已被占用。例：Begin integer W = 0 ;CogeginBeginL1：lock W;CS1;Unlock W;Remainder of process 1;Goto L1;EndBeginL2：lock W;CS2;Unlock W;Remainder of process 2;Goto L2;EndCoendEnd

操作系统|进程的同步与通信15CUIT 徐虹¾关锁原语lock W：if W = 1 thenbeginblock(n);insert(WL,n);scheduler;endelseW = 1;操作系统|进程的同步与通信16CUIT 徐虹¾开锁原语unlock W：if WL<> NULL thenbeginremove(WL,q);status(q) = “ready”;insert(RL,q);endelseW = 0;

操作系统|

进

程的同步与通信17CUIT 徐虹¾硬件实现进程互斥¾利用Test_and_Set 指令function TS (varlock :boolean) :boolean;beginTS := lock ; Lock := true ;EndLock = true ：资源被占用Lock = false ：资源可用操作系统|进程的同步与通信18CUIT 徐虹利用TS指令实现互斥：repeatwhile TS (lock) do skip ;critical sectionlock := false ;remainder sectionuntil false ;操作

系

统

|

进程的同步与通信19CUIT 徐虹¾利用Swap指令实现进程互斥初值lock = false 表示资源可用。Procedure Swap (vara,b :boolean)Var temp :boolean;BeginTemp := a ;

a := b ;b := temp ;End操作系统|进程的同步与通信20CUIT 徐虹repeatkey := true ;repeatSwap(lock,key) ;Until key = false ;critical sectionlock := false ;remainder sectionuntil false ;操作

系

统

|

进程的同步与通信21CUIT 徐虹3．2信号量机制¾整型信号量机制¾信号量(sem)sem>=0: 表示可供并发进程使用的资源实体的个数sem<0: 表示正在等待使用临界区的进程数。Sem的值只能由P、V操作改变。P：wait ( s )V：signal (s )按信号量数值分为二元信号量和一般信号量。操作系统|进程的同步与通信22CUIT 徐虹¾Wait（P）和signal（V）原语¾Wait(s) 原语wait(s) ：BeginLock out interrupts;s = s –1;If s < 0 thenBeginStatus(q) ：= blocked;Insert(WL, q);Unlock interrupts; Scheduler;EndElseunlock interrupts;End

操作系统|进程的同步与通信

23CUIT 徐虹¾signal原语signal(s) ：BeginLock out interrupts;s = s + 1;If s < =0 thenBeginRemove(WL，R);Status(R) ：= ready;Insert(RL，R);EndUnlock interrupts;

End操作系统|进程的同步与通信24CUIT 徐虹¾利用信号量实现互斥Begin integermutex= 1;cobeginprocess1：BeginL1：wait (mutex);CS1;signal (mutex);Remainder of process 1;Goto L1;EndProcess2：BeginL2：wait (mutex);CS2;signal (mutex);Remainder of process 2;Goto L2;EndCoendEnd操作

系

统

|

进程的同步与通信25CUIT 徐虹例、进程A、B、C依赖于D的结果操作系统|进程的同步与通信26CUIT 徐虹操作

系

统

|

进程的同步与通信27CUIT 徐虹¾利用信号量描述前趋关系P1：S1P2：S2S1——>S2则设置信号量s=0，P1：S1；signal(s)；P2：Wait(s)；S2；操作系统|进程的同步与通信28CUIT 徐虹1234567abcdefgh例：根据前趋图写出可并发执行的程序：var a,b,c,d,e,f,g,h:semaphore := 0,0,0,0,0,0,0,0;

操作系统|进程的同步与通信29CUIT 徐虹beginparbeginbegin S1;signal(a); signal(b); signal(c); endbegin wait(a); S2; signal(d); endbegin wait(b); S3; signal(e); endbegin wait(c); S4; signal(f); endbegin wait(d); S5; signal(g); endbegin wait(e); wait(f); S6 ; signal( h); endbegin wait(g); wait(h); S7; endparendend操作系统|进程的同步与通信30CUIT 徐虹¾记录型信号量机制type semaphore = recordvalue:integer;L:list of process;end操作

系

统

|

进程的同步与通信31CUIT 徐虹procedure wait(s)vars:semaphore;beginS.value := S.value –1;If S.value < 0 then block(S,L);

endprocedure signal(s)vars:semaphore;beginS.value := S.value + 1;If S.value < = 0 then wakeup(S,L);end操作系统|进程的同步与通信32CUIT 徐虹-1-2-1操作

系

统

|

进程的同步与通信33CUIT 徐虹¾信号量集机制¾AND型信号量集机制¾问题引入进程A、B访问共享数据D和E信号量Dmutex=1，Emutex=1process A :wait(Dmutex) ;wait(Emutex) ;process B :wait(Emutex) ;wait(Dmutex) ;操作系统|进程的同步与通信34CUIT 徐虹A、B交替执行：process A :wait(Dmutex) ;则Dmutex= 0process B : wait(Emutex) ; 则Emutex= 0process A :wait(Emutex) ; 则Emutex= -1，阻塞process B :wait(Dmutex) ; 则Dmutex= -1，阻塞发生死锁。操