1、第二章进程管理32.8 进程的同步2.8.1 进程同步的基本概念一进程同步的任务1.引例 - 反映“不可再现性” “与时间有关的错误”示例2.1 的例3Var N: Integer BeginN := 0;Parbegin Program A: Program B: Begin Begin repeat repeat a1: N := N+1; b1：Print (N) until false b2：N:= 0； End until false EndParend End进程A,B执行时共享变量N，若执行顺序为: a1 b1 b2或b1 b2 a1执行结果不同，有可能使数据出错也就是进程并发运
2、行呈现出“不可再现性” 即，产生“与时间有关的错误”。2进程同步的任务 (1) 使多个进程并发运行具有可再现性(2) 使多个进程可以进行通信（IPC）。多个进程合作一个任务(多个进程并发运行以提高速度)，但每个进程只能访问本进程的内存空间，多个进程如何进行通信？例问题:。一个进程如何向另一进程传送信息（数据）。如何保证两个或多个进程在共享资源时不会彼此影响。如何为存在依赖关系的进程进行适当地定序二、同步和互斥的概念1间接制约（资源共享引起）互斥使用临界资源，如两个或多个进程互斥使用打印机。2直接制约（互相合作关系）同步A， B进程共享缓冲区，它们不是一种简单地互斥使用缓冲区的关系: A，B进程
3、在执行次序上应该协调，它们互相之间制约关系为：当缓冲区放满数据时，A进程不能再向缓冲区放数据当缓冲区数据已全部取走（缓冲区空），B进程不能再打印 “同步”是指进程在执行次序上有互相的制约关系，互斥是同步的特例。三、临界区临界资源：一次仅允许一个进程使用的资源临界区：进程中访问临界资源的那段代码（注: 临界区是代码，不是数据区）并发执行示例用Parbegin和Parend把并发执行的程序括起来BeginVar N:integer 临界资源N := 0；Parbegin Program A： Begin Repeat al: N := N+1临界区until falseEnd ParendProg
4、ram B: BeginRepeat bl:Print(N); b2:N:=0; 临界区 until false EndEnd例：两个进程共享一个变量count，执行顺序不同结果不同BeginVar count:integer := 0 临界资源Parbegin P1:begin a1: R1=count; a2: R1:=R1+1; 临界区 a3: count:=R1; endP2:begin b1: R2:=count;b2: R2:=R2-1; 临界区b3: count:=R2 endparendend若count当前值为5，按如下几种不同运行顺序，结果不同：a1,a2,a3,b1,b2
5、,b3或b1,b2 b3,a1,a2,a3,count的值为5a1,a2,b1 b2,a3,b3,结果为4a1,b1,a2,b2,a3,b3:count的值为4OS应提供同步机制以避免出现上述现象,使得进程P1使用临界资源期间(在临界区中运行)，进程P2不能使用临界资源2.8.2 进程的同步机制要求一、进入区和退出区的设置为了保证对临界资源的正确使用，将程序对临界资源的访问过程分成三个部分： 程序P1: 检查是否可进入临界区，并设置“正在访问”标志，使其它进程不可以进入临界区 临界区 将“正在访问”标志清除，使其它进程可以进入临界区 其它代码二、同步机制的准则(P64)1空闲让进2忙则等待3有
6、限等待4让权（CPU运行权）等待 2.8.3 用软件方法解决互斥问题 用户在程序中设置逻辑变量，用于要进入临界区进程的测试，OS不提供任何支持方法一、设置“令牌”,输流进入临界区用变量turn指示被允许进入的进程编号，初值为i表示允许Pi 进程进入临界区改错P65 第5行 应为turn =iPi :repeat While turni do no-op 进入区（测试）turn:= j， 退出区其它代码untile falsePj : repeat While turnj do no-opturn:=i;其它代码untile false分析：turn相当“令牌”,输流使用不会同时进入临界区,不会
7、同时都不能进入，符合“空闲让进”“忙则等待”Pi和Pj必须输流进入临界区缺点: Pi退出后(turn:=j)，若因某种原因Pj不能进入临区，那么Pi也不能再进入临区 方法二、每个进程设置自己是否在临界区的标志flagflag0,1nof boolean；n个进程标志，初值为false不在临界区每个进程Pi在进入临界区前先检查其它一进程是否在临界区，如不在，表示则Pi可进入，并在进入前首先修改本进程标志flagi:=true,表示“本进程在临界区，其它进程不能进入临界区”忙则等待var flag0,1n of booleanPi repeata1:while flagj do no-op 检查其
8、它进程是否在临界区flagi:=true修改标志，表示Pi要进入临区临界区flayi:false其它代码until falsePj: repat b1:while flayi do no-opb2:flayj:=true临界区flayj:=false其他代码until false若判断和设置标志的动作连续完成，则可顺利实现“互斥进入”。若Pi,Pj几乎同时要求进入临界区，如顺序为：a1,b1则测试条件都满足（都不在临区）则Pi,Pj同时进入临区（不能互斥）违背“忙则等待”。方法三、先设置标志（表示要进入临区），再测试Pi: repeata1:flayi:=truea2:while flayj
9、do no-op临界区flayi:=false其它代码until falsePj:repeatb1:flayj:=true;b2:while flayido no-op临界区flayj:=false其它代码until false若顺序为:a1,b1,a2,b2, 则Pi,Pj都进不了临区，违背“有空让进”2.8.4 用硬件方法解决同步问题软件方法解决互斥的缺点程序中在进入临区之前用两条语句分别进行测试和锁住，如果测试和锁住两条语句不能连续执行(例如上述进程Pi,Pj几种特殊切换),就会产生不符合同步机制准则的结果。下面用硬件方法解决同步问题。一、Test-and-Set指令（TS指令）锁Loc
10、k=false 可进入临界区（锁开着） Lock=true 不可进入临界区（锁关着）设置硬件测试锁的指令Test and Set，把测试和关锁两个操作结合在一条指令中，不会被打断，保证互斥进入临界区，该指令功能如下：Function TS(Var Lock:boolean):Boolean Begin TS:=Lock Lock:=true;End二、利用TS实现进程互斥repeatWhile TS(Lock)do skip;-反复测试，直至TS为false(等待CPU运行其它进程，其它进程把Lock=false) 临界区lock:=false; 其它代码until false缺点: Whil
11、e Ts(Lock)do skip 当TS=true时需要反复测试(违背让权（CPU运行权）等待)三、Swap指令（类似TS指令） P68自学思考用Swap指令为什么可实现互斥2.6.5 信号量机制一条硬件指令执行时不会被打断，原语也是“不会被打断”的操作一、 整型信号量的原语操作整型信号量S: 0 可以进入临界区 0不可进入临界区Wait(S): /* 也称P操作 */While S0 do no-op S:= S 1 Wait原语类似于Test-and-Set指令，把测试和设置(S:= S 1)两个操作在一条原语中实现SignaL(S): /*也称V操作 */S:=S+1; SignaL原
12、语相当于Lock=false(开锁)可利用整型信号量实现互斥，程序如下：Var mutex:semaphone:=1 /* 信号量置初值 */ BeginParbeginProcess1:begin Repeat Wait(mutex); 临界区signal(mutex); 其它代码 until false; endProcess2:begin Repeat Wait(mutex);临界区Signal(mutex);其它代码until false;endparendend 缺点: Wait(S):While S0 do no-op 当S0时需要反复测试(违背让权（CPU运行权）等待)二、 记录
13、型信号量机制Type semaphone=record value: integer; /*信号量的整型值 */ L: list of process; /* 设置等待该信号量的进程阻塞队列 */ End相应地，Wait(S)和Signal(S)操作可描述为：Procedure wait(S) - P操作 Var S:semaphone; Begin S.value:=S.value-1; if S.value 0 then block(S.L) Endblock(S.L)为阻塞原语, 若S.value 0则调用Wait(S)的进程自我阻塞(等待其它进程用signal(S)唤醒)注意。此处用i
14、f 测试而不是While测试，这样不必“忙等”。Procedure signal(S) - V操作 Var S:semaphone; Begin S.value:=S.value+1; if S.value0 then wakeup(S.L); Endwakeup(S.L) 为唤醒原语三、整型信号量和记录型信号量的不同整型 记录型While测试 用if测试（不必反复测试）wait(S)中 先While S0 wait(S)中 先S.value:=S.value-1 后S:= S 1 后 if S.value0时，S.value的值为该类资源当前可用的数量S.Value0时，其绝对值为请求使用该
15、资源（要想进入临区对资源操作）的进程数（在阻塞队列中等待该信号量的进程数）。例： 五个进程共享3台打印机 S.value初值为3 若五个进程几乎同时申请进入临区使用打印机，那么：第一个进程申请进入：S.value:3-1=2第二个进程申请进入：S.value:2-1=1 申请成功进入临区第三个进程申请进入：S.value:1-1=0上述三个进程在临区使用打印机未结束，第四,第五个进程也申请进入临区使用打印机，则：第四个进程申请进入：S.value:0-1= -1阻塞第五个进程申请进入：S.value:-1-1= -2阻塞该信号量整型值S.Value的变化范围为3 -2五、利用信号量实现互斥Va
16、r mutex:semaphone:=1 Begin Parbegin Process1:begin Repeat Wait(mutex);临界区signal(mutex);其它代码until false;endProcess2:begin Repeat Wait(mutex); 临界区 signal(mutex); 其它代码 until false;endParend End注。阻塞进程被唤醒后不需再用Wait测试，直接进入临区六、利用信号量同步例一、生产者消费者问题1.单缓冲区，单生产者、单消费者CP IOP同步问题：生产者将产品一件（批）一次放入缓冲区，消费者从缓冲区取出一件（批）产品。
17、同步要求：当缓冲区有产品时，生产者不能再放产品到缓冲区，当缓冲区为空时，消费者进程不能从缓冲区取产品。信号量设置：empty: 初值为1（为空），表示有1个缓冲区，用来表示缓冲区是否为空当生产者进程向缓冲区放产品之前，用Wait操作,测试empty的值是否1,若是，则可放产品。当消费者进程从缓冲区取产品后，用Signal(empty)操作释放缓冲区(表示缓冲区已空)full：初值为0，表示缓冲区是否为满（有产品），初值0表示没有产品。当消费者进程从缓冲区取产品之前，用Wait操作测试 full的值是否1，若是，可取产品。当生产者进程向缓冲区放产品时，用signal(full)操作释放full表
18、示缓冲区已满。程序如下：var empty,full:semaphore:=1,0beginParbeginproducer: consumer:begin beginrepeat repeat 生产产品wait(empty); wait(full);把产品放入缓冲区 从缓冲区取出产品signal(full); signal(empty); until false until falseParendend注意。此处对信号量empty,full的wait, signal操作设置的位置思考题：如果用一个互斥信号量mutex, 一个条件变量可以实现吗？2. 多缓冲区、单生产者、单消费者多缓冲区可使生
19、产者、消费者进程不是必须输流使用缓冲区 5 0 4 1 3 2同步要求：缓冲池满了，生产者不能再放产品 缓冲池空了，消费者不能再取产品缓冲池中各缓冲区编号，0，1，n-1（ n个缓冲区）,缓冲区循环编号，例：6=（5+1）mod 6 =0缓冲池用buffer数组表示 下标从0到n-1信号量empty初值为n，（表示有n个空缓冲区） 信号量full初值为0，（表示缓冲区都空）生产者放产品时必须指定缓冲区编号，用in表示，初值为0 消费者取产品时用out指定缓冲区编号，初值为0程序如下：var empty,full semaphore:=n,0; buffer:array0,n-1 of item
20、; in,out:=0,0;begin parbegin producer: consumer: begin repeat begin repeat 生产产品wait(empty); wait(full);bufferin:=产品 产品：=buffer(out)in:=(in+1)mod n out:=(out+1)mod nsignal(full); signal(empty);until false; until falseparendend思考题： （1）in和out值的变化范围？（2）当in和out的值为多少的表示缓冲池放满了产品。 当in和out的值为多少时表示缓冲池没有产品。3多个
21、缓冲区，多个生产者，多个消费者与上述 (2.) 不同点：多个生产者共享缓冲池指针in，必须互斥使用in多个消费者共享缓冲池指针out，必须互斥使用out简单方法：设置一互斥信号量mutec，使得无论生产者还是消费者，只能有一个进程进入缓冲池程序如下，P73Var mutex , empty, full: semaphone:=1, n, 0; Buffer: array0,n-1 of item; in, out: integer:=0,0;Begin Parbegin Producer: consumer: begin begin repeat repeat producer an item
22、 in nextp wait(full);wait(empty); wait(mutex);wait(mutex); nextc:=buffer(out);buffer(in):=nextp; out:=(out+1)mod n;in:=(in+1)mod n; signal(mutex);signal(mutex); signal(empty);signa(full); consume the item in nextc; until false; until false;end end parendend讨论 1多个wait操作的不同顺序问题（1）正确顺序Producer: consume
23、r: a1:wait(empty); b1:wait(full) a2:wait(mutex); b2:wait(mutex); 若缓冲已满，生产者进程阻塞，未执行wait(mutex)，消费者进程可以运行（2）错误顺序如果将上述多个wait操作顺序颠倒如下：- a1:wait(mutex); b1:wait(mutex); a2:wait(empty); b2:wait(full)若缓冲已满，生产者进程运行：先执行wait(mutex)，通过，再执行wait(empty)，生产者进程阻塞(等待empty)，但不释放互斥信号量mutex，轮到消费者进程运行：阻塞(等待mutex)，这样两个进程
24、都阻塞结论：一般先对资源同步信号量作wait操作，再执行对互斥信号量的wait操作2对互斥信号量mutex的wait操作和signal操作在同一个进程中必须成对出现。3对资源同步信号量的wait和signal操作分别处子不同的进程中P：wait (empty); c: wait (full) Signal (full ) signal ( empty )例2：利用信号量控制程序（或语句）的执行顺序 程序前驱图 程序前驱图中的信号量设置 a b c d e f gVar a, b, c, d, e, f, g: semaphore:0,0,0,0,0,0,0BeginParbeginS1 beg
25、in s1; sighal(a); signal(b); end;S2 begin wait(a); s2; signal(c); signal(d) end;S3 begin wait(b); s3; signal(e) end;S4 begin wait(c); s4; signal(f); end;S5 begin wait(d); wait(e); s5; signal(g); end;S6 begin wait(f); wait(g); s6；end;ParendEnd思考：是否可以用一个信号量代替a,b两个信号量,，程序改为:S1 begin s1; signal(a)e nd;S
26、2 begin wait(a); s2; S3 begin wait(a); s3; 例3：读者写者问题 多个读者进程可以同时读文件,但排斥写者进程；写者进程写文件时排斥其它任何进程同步要求：读者可以同时读，不需互斥读者与写者之间互斥写者与读者，写者互斥信号量设计：:互斥信号量wmutex，用于：第一个读者与写者互斥 写者与其它读写者互斥对wmutex的操作：第一个读者进入临区时，用wait(wmutex)测试并排斥其它写者。最后一个读者退出临区时，用signal(wmutex)释放资源设置读者计数器readcount，初值为0，用于对读者序号的统计，以确定“第一”和“最后一个”在临区的读者。
27、设置信号量rmutex，以使读者互斥使用计数器（注意：不是互斥使用要读的文件）利用记录型信号量解决读者-写者问题程序：var rmutex, wmutex; semaphone:=1,1; readcount:integer:=0;beginparbeginReader:Begin RepeatWait(rmutex);互斥使用readcount计数器If readcount=o then wait(wmutex);第一个读者负责测试可否进入临区readcount:=readcount+1;Signal(rmutex);释放计数器执行读操作wait (rmutex);readcount:=re
28、adcount-1;if readcount=0 then signal(wmutex); 最后一个出临区的读者负责释放资源。Signal(rmutex);Until false;EndWriter: 写者进程只需用wmutex信号量互斥使用临区Begin Repeat Wait(wmutxe); Perform write operation;临界区 Signal(wmutex);Until false; EndParendEnd思考题：（1）在读者进程中对rmutex的互斥操作做了两次，是否可以改为一次，结果有何不同。信号量应用小结：1互斥信号的初值为同类可用资源的个数。例 定义时置，mutex:=1表示有1个资源若var mutex:semaphore:=5表示有5个同类资源，最多允许5个进程同时使用2对互斥信号量的操作，在同一程序中测试(wait)和释放(signal)：wait (mutex)临界区signal(mutex)3资源信号量（用作同步），初值为同类
