__进程同步与通信(第三版)

1、 第二章 进程管理 -进程的同步与通信主要内容q 进程同步的概念q 用硬件方法解决互斥问题q 信号量机制q 经典进程同步问题q 进程通信并发有效地提高了系统资源的利用率但也带来了一些问题? ?例子：谁买面包？妈妈查看冰箱，面包没了去超市到达超市买好面包回家,把面包放入冰箱5:005:055:105:155:205:255:30爸爸查看冰箱，面包没了去超市到达超市买好面包回家,把面包放入冰箱噢,Too Much进程同步的概念n OS引入进程后，由于进程的异步性，可能会导致程序执行结果的不确定性，使程序执行时出现不可再现性。n 任务：对多个进程在执行次序上进行协调，使并发执行的进程有效地共享资源和

2、相互合作，使程序的执行具有可再现性。进程A进程B进程同步的概念输入计算打印buffer A bufferB等待这种关系是多个进程在共享资源中形成的。此时同步的任务是保证进程能互斥的访问临界资源。这种关系是多个进程在合作完成某种工作中形成的。此时进程的同步需要保证相互合作的进程在执行次序上的协调。通知间接相互制约关系直接相互制约关系打印机n 两种制约关系进程同步概念例：司机与售票员协同工作 司机 P1： 售票员 P2： REPEAT REPEAT 运行 售票 到站停 开门 UNTIL FALSE 关门 UNTIL FALSE进程同步概念(a) (b) (c) (d)n 临界资源一次仅允许一个进程

3、（互斥）访问的资源称为临界资源：如输入机、打印机，部分软资源( (如变量、表格等) )。a=n; /n为剩余的票数if(a1) a=a-1; /售出一张 n=a;a=n; /n为剩余的票数if(a1) a=a-1; /售出一张 n=a;临界资源处理不当n 临界区多个进程访问临界资源的代码称为临界区。 设计原则:q 每次至多允许一个进程处于临界区中;q 对于请求进入临界区的进程,在有限时间内只 允许一个进入;q 进程只在临界区停留有限的时间;临界区开始临界资源被访问？访问临界区退出临界区执行剩余操作未访问正访问repeatentry section;exit section;critical s

4、ection;remainder section;until false;临界区的访问流程访问临界资源的进程描述进入区临界区退出区剩余区同步机制应遵循的原则（实现互斥）q空闲让进：若临界资源处于空闲状态，允许 有进入请求进程立即进入临界区访问q忙则等待：若临界资源正被访问，其它进程 必须等待q有限等待：必须保证要求访问临界资源的进 程在有效的时间内进入临界区访问，以免“死 等”q让权等待：当进程不能进入临界区时，应释 放处理机，以免进程陷入“忙等”q 进程同步问题描述begin parbegin Pi: Pj: parendend并发进程并发进程用软件方法解决进程互斥问题用硬件方法解决进程互斥

5、问题 利用Test-and-Set指令Ts指令指令 function TS(var lock:boolean):boolean; begin TS:=lock; lock:=true; end lock=false时，资源空闲；lock=true时，表示资源正在使用。 while TS(lock) do no_op;lock:=false;remainder section;until false;critical section; TS指令实现互斥repeat用硬件方法解决进程互斥问题Ts指令指令 function TS(var lock:boolean):boolean; begin TS

6、:=lock; lock:=true; end Swap指令swap指令(交换指令) procedure Swap(var a,b:boolean) var temp:boolean; begin temp:=a; a:=b; b:=temp; end;用硬件方法解决进程互斥问题利用Swap指令实现进程互斥key:=true;repeat swap(lock,key);until key=false; lock:=false;repeat critical section;remainder section;until false;用硬件方法解决进程互斥问题练习： 我们为某临界区设置一把锁W，

7、当W=1时，表示关锁；W=0时，表示锁已打开。写出开锁原语和关锁原语，并利用它们去实现互斥。critical section;进入区退出区while(W=1) do no_op;W:=1;W:=0;lock(w)unlock(w)下面是两个进程P0、P1互斥使用临界区的解决办法，能否达到目的？说明原因。设变量是flag0=flag1=0进程Pi：flagi=1;while (flag(i+1)%2=1); Pi的临界区代码；flagi=0;答案：如果执行flag0=1,flag1=1 此时while(flag0=1)成立，无限循环； while(flag1=1)成立，无限循环；思考：P0: f

8、lag0=1; while(flag1=1) P0的临界区代码；的临界区代码； flag0=0;P1: flag1=1; while(flag0=1) P1的临界区代码；的临界区代码； flag1=0;整型信号量机制wait(s): while s0 do no_op; s:=s-1;signal(s): s:=s+1;整型信号量是一个整形量，仅能通过原子操作来访问。这些操作被称为P、V操作(wait/signal)(源于荷兰文passeren /vrijgeven即通过/释放 )。整型机制中s 0时，时，会不断测试，违背“让权等待”。记录型信号量type semaphore = record

9、 Value:integer； L:list of process；endprocedure wait(s) 或或P(s) var s:semaphore; begin s.value=s.value-1； if s.value0 then block(s.L) endprocedure signal(s) 或或V(s) var s:semaphore; begin s.value:=s.value+1 if s.value0 then wakeup(s.L); end;L Value.入口入口(S)SS-1S0当前进程进入当前进程进入Q Q指向的等待队列指向的等待队列进程调度原语进程调度原语

10、返回返回P(S)入口入口(S)SS+1S0唤醒一个唤醒一个Q Q指向的指向的等待队列中的进程等待队列中的进程返回返回V(S)记录型信号量记录型信号量物理意义n s.value表示系统中可用的某类资源的数目；n 执行wait（即P）操作，意味着进程请求一个单位的资源；n 当s.value0时，表示资源已分配完毕，因而进程调用 block原语，进程自我阻塞，并插入信号量链表中。n s.value1时，记录型信号量，或s=1时，互斥信号量；swait(s,1,0)。s1时，允许多个进程进入某特定区；当s=0时，将阻止任何进程进入特定区。相当于可控开关。解决问题：需访问N个某类临界资源经典进程同步问题

11、 q生产者消费者问题q读者写者问题q哲学者就餐问题生产者消费者问题 123456Out Out inin满缓冲区空缓冲区N = 6 个缓冲区消费者将要取数据的位置生产者将要存放数据的位置354126Out Out in354126Out Out inin缓冲池问题分析：n 同步关系表现为：当所有缓冲区均装满产品时，生 产者必须等待消费者提供空缓冲区；当所有缓冲区 全为空时，消费者必须等待生产者提供满缓冲区。 n 互斥关系表现为：由于缓冲池是临界资源，所以任 何进程在对缓冲区进行存取操作时都必须和其他进 程互斥进行。 var mutex,empty,full:semaphore:=1,n,0;b

12、uffer:array0n-1 of item;in,out:integer:=0,0;说明：mutex ：互斥信号量Empty ：空缓冲区数量full：满缓冲区数量生产者消费者问题 outin满空(in+1)mod n(out+1)mod nconsumer: begin repeat wait(full); /阻塞消费进程 wait(mutex); 取出产品 out:=(out+1) mod n; signal(mutex); signal(empty); /唤醒生产进程 消费产品 until false; end;producer: begin repeat 生产一个产品 wait(em

13、pty); /可分配一个空缓冲区 wait(mutex); /关闭缓冲区 将产品放入缓冲区 in:=(in+1) mod n; /输入指针后移 signal(mutex); /打开缓冲区 signal(full); /唤醒消费进程 until false; end;思考：q 如果少了signal(full)或signal(empty)， 会怎样？q 将两个wait(full)和wait(mutex)互换位 置，或将signal(full)与signal(mutex)互 换，结果怎样？q 如果缺少了signal(full)，则消费者进程在wait(full）处阻 塞，并一直处于阻塞状态；如果少了

14、signal(empty)，则生 产者进程在产生n个数据后，即缓冲区满时，产生阻塞， 无法生产数据。【分析】q consumer:wait(mutex) mutex:=0; wait(full) full:=-1 阻塞 producer: wait(empty) empty0 wait(mutex) 阻塞若互换signal(full)和signal(mutex)不会引起死锁，只使得临界资源的释放推迟一点。生产者消费者问题 【注意】q wait(mutex)和signal(mutex)必须成对出现。q empty和full 的P、V操作也需要成对出现，但 它们处于不同的程序中。q 进程中的多个w

15、ait操作不能颠倒，先执行对资 源信号量的 wait操作，然后执行对互斥信号量 的wait操作，否则引起死锁。读者写者问题 共享资源可被写进程和读进程共享。要求：多个读进程可同时读一个共享对象，不允许写进程和其它读进程或写进程同时访问共享对象。var rmutex,wmutex：semaphore:=1,1;readcount :integer:=0;writer: begin repeat wait(wmutex); 写 signal(wmutex); until false; end;reader: begin repeat wait(rmutex); if readcount=0 the

16、n wait(wmutex); readcount:=readcount+1; signal(rmutex); 读 wait(rmutex); readcount:=readcount-1; if readcount=0 then signal(wmutex); signal(rmutex); until false; end;无读者时，判断是否有写者操作无读者时，允许写者操作读者写者问题 rmutex是控制读者互斥地访问readcountwmutex是控制读或写的互斥用信号量集机制解决读写者问题 var RN: integer; /最多允许RN个读者同时读L,mx:semaphore:=RN

17、,1;reader: begin repeat Swait (L,1,1); Swait (mx,1,0); 读 Ssignal (L,1); until false; endwriter: begin repeat Swait (mx,1,1;L,RN,0); 写 Ssignal (mx,1); until false; endq Swait(L,1,1)：有读者进入时，使L值减1，L为0时，阻止读者读q Swait(mx,1,0)：起开关作用。mx=1时表明无写者，读进程可以进入读。 mx=0，任何reader进程就都无法进入读。q Swait(mx,1,1；L,RN,0) ：表示仅当即无

18、writer进程在写（mx=1），又无 reader进程在读（L=RN）时，writer进程才能进入临界区写。哲学家进餐问题 五个哲学家共用一张圆桌，平时思考问题，饥饿时拿其左、右最靠近他的筷子，只有两支筷子都拿到时才能进餐。进餐毕，放下筷子继续思考问题。01234var chopstick:array0,4 of semaphore:=(1,1,1,1,1);哲学家哲学家i: repeat wait(chopsticki); wait(chopstick(i+1) mod 5; eat; signal(chopsticki); signal(chopstick(i+1) mod 5; thi

19、nk; until false;解决方法：q至多只允许四个哲学家同时进餐，以保证至少有一个哲学家能进餐。q仅当哲学家的左、右两支筷子均可用时，才允许他拿起筷子进餐。q规定奇数哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数 哲学家则相反。按此规定，将是1,2号哲学家竞争1号筷子；3,4号哲 学家竞争3号筷子。即五个哲学家都先竞争奇数号筷子，获得后，再 去竞争偶数号筷子，最后总会有一个哲学家获得两支筷子进餐。哲学家进餐问题 若五个哲学家都成功持有左边的筷子时，系统产生死锁：var chopstick : array0,4 of semaphore :=(1,1,1,1,1);process

20、i: repeat think; Swait(chopstick(i+1) mod 5,chopsticki); eat; Ssignal(chopstick(i+1) mod 5,chopsticki); until false;：var sm:semaphore:=4; repeat wait(sm); wait(chopsticki); wait(chopstick(i+1) mod 5); eat; signal (chopsticki); signal (chopstick(i+1) mod 5); signal(sm); think; until false;哲学家进餐问题 012

21、34philosopher i:repeatif(i%2=0) wait(chopstick(i+1) mod 5); wait(chopsticki); eat; signal (chopstick(i+1) mod 5); signal (chopsticki); think;else wait(chopsticki); wait(chopstick(i+1) mod 5); eat; signal (chopsticki); signal (chopstick(i+1) mod 5); think;until false;哲学家进餐问题 【练习【练习】1.若信号量S的初值为10，当前值为

22、-3，则表示有_个等待进程。 A. 0 B. 3 C.7 D. 92.设有10个进程共享同一互斥段，若最多允许有4个进程进入互斥段，则所用的互斥信号量的初值为_。 A. 4 B. 10 C. 7 D. 13.信号量的值具有明确的物理意义，其值大于等于0时，其值表示_ _；其值小于0时，其绝对值表示 _。等待信号的进程数目可用资源数目【例1】：公共汽车上，司机和售票员各行其职，司机负责开车和到站停车；售票员负责售票和开、关门，当售票员关好车门后，驾驶员才能开车行驶。用P、V操作实现司机与售票员间的同步。司机和售票员的信号量分别为var S1,S2:semaphore:=0,0司机： repeat

23、 开车； 停车； V(S2); P(S1); until false; 售票员：repeat 售票； P(S2); 开车门； 关车门； V(S1); until false;【例2】：用信号量实现4*100接力赛的同步过程 P操作:表示等待某个信号的到来。V操作:表示发出一个信号。 运动员运动员1 运动员运动员2 运动员运动员3 运动员运动员4S1(0)S2(0)S3(0)parbegin athlete1: begin athlete2: begin run； P(S1); V(S1); run; end; V(S2); end; athlete3: begin athlete4: begi

24、n P(S2); P(S3); run; run; V(S3); end; end;parend;【例3】：假设有3个并发进程P、Q、R。其中P负责从输入设备读入信息并传送给Q；Q将信息加后传送给R；R则负责将信息打印输出。进程P、Q共享一个由m个缓冲区组成的缓冲池；进程Q、R共享另一个n个缓冲区组成的缓冲池。写出并发程序。 PQRvar mutex1,mutex2,S1,S2,S3,S4:semaphore:=1,1,m,0,n,0;S1/S2S3/S4P: Q: R: 读信息；读信息； P(S2); P(S4); P(S1); P(mutex1); P(mutex2); P(mutex1)

25、; 取数据取数据; 打印数据；打印数据； 放入数据；放入数据； V(mutex1); V(mutex2); V(mutex1); V(S1); V(S3); V(S2); 数据处理；数据处理； P(S3); P(mutex2); 处理后的数据放入缓冲区；处理后的数据放入缓冲区； V(mutex2); V(S4);【作业】1.有一阅览室，共有100个座位。读者进入时必须先在一张 登记表上登记，该表为每一座位列一表目，包括座号和读 者姓名。读者离开时要注销掉登记内容。用P、V操作描述 读者进程的同步结构。2.计算进程计算进程打印进程打印进程单缓冲区能用从信号量的两种不同角度去解决以上问题吗？提示：

26、q S1:计算进程把计算结果放入缓冲区，然后通知打印进 程取走结果，并使自己处于等待状态，等待计算进程将 结果取走； S2:打印进程取走结果，并向计算进程发送信号，使之 继续计算。q 从资源角度理解：sempty:计算进程申请空的缓冲区;打 印进程申请带数据的缓冲区，即sfull。1.var mutex,s:semaphore:=1,100; process readeri: begin P(s); P(mutex); 登记； V(mutex); 阅读； P(mutex); 删除登记项； V(mutex); V(s); end;【答案】 2. 第一种方法： var S1,S2:semaphor

27、e:=0,0; 计算进程： repeat 计算； 将结果放入缓冲区； V(S1); P(S2); until false; 打印进程： repeat P(S1); 从缓冲区中取出数据； V(S2); 打印； until false;第二种方法： var Sempty,Sfull:semaphore:=1,0; 计算进程计算进程： repeat 计算 P(Sempty);将结果放入缓冲区； V(Sfull); until false; 打印进程打印进程： repeat P(Sfull); 从缓冲区中取出数据； V(Sempty); 打印； until false;管程引入 采用PV同步机制来编写

28、并发程序，对于共享变量及信号量变量的操作将被分散于各个进程中。缺点：n 可读性差：要了解对于一组共享变量及信号量的操作 是否正确，必须通读整个并发程序。n 不利于修改和维护：任一组变量或一段代码的修改都 可能影响全局。n 正确性难以保证：因为操作系统或并发程序通常很 大，要保证这样一个复杂的系统没有逻辑错误是很难 的。管程概念 系统中的软硬件资源都可用数据结构加以抽象地描述，即用少量信息和对该资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。 管程定义了一个数据结构(资源)和能为并发进程所执行的一组操作(资源管理)。它包括四部分：管程名称；局部于管程的共享数据结构说明；对数据结构进

29、行操作的过程；共享数据的初始化序列。 集中式同步机制，它的基本思想是将共享变量以及对共享变量能够进行的所有操作集中在一个模块中，并发程序由若干个这样的模块所构成，由于一个模块通常较短，模块之间关系清晰，提高了可读性，便于修改和维护且正确性易于保证。type monitor-name=monitor 定义，指定名称 variable declarations 共享变量说明 procedure (); 操作定义 begin end; function ():值类型; begin end; begin Initialization code; 初始化序列 end;n局部于管程的数据结构，仅能被管程的

30、过程访问；n进程通过调用管程的过程进入管程；n每次仅允许一个进程进入管程(互斥访问)。管程定义 管程是互斥进入的，当一个进程试图进入一个已被占用的管程时它应当在管程的入口处等待，因此在管程的入口处应当有一个进程等待队列，称作入口等待队列。 如果进程P唤醒进程Q，则P等待Q继续，而进程Q在执行又唤醒进程R，则Q等待R继续，因此，在管程内部，由于执行唤醒操作，可能会出现多个等待进程，因而还需要有一个进程等待队列，这个等待队列被称为紧急等待队列。它的优先级应当高于入口等待队列的优先级。 管程【问题】：多个进程出现在管程中 当一个管程中的进程执行等待操作时，它应当释放管程的互斥权；当一个进入管程的进程

31、执行唤醒操作时（如P唤醒Q），管程中便存在两个同时处于活动状态的进程。处理方法：n P等待Q继续，直到Q退出或等待n Q等待P继续，直到P等待或退出管程条件变量 利用管程实现进程同步时，必须设置同步操作原语wait和signal，当进入管程的进程因资源被占用等原因不能继续运行时，调用wait使其等待。当另一进程访问完并释放后，调用signal唤醒等待进程。为了描述不同的等待原因引入条件变量condition。 var x,y:condition; 定义条件变量x.wait：表示正在调用管程的进程因x条件需要被阻塞或挂起，并插 入x条件的等待队列中。x.signal：表示正在调用管程的进程发现x

32、条件变化，重新启动因x而 阻塞或挂起的进程。区分两种signal操作：n 管程的signal操作，启动一个阻塞进程，若没有进程阻塞，则不做 任何事情；n 信号量signal操作，若无阻塞进程，总要执行s:=s+1；管程解决生产者消费者问题 type producer-consumer=monitor var in,out,count:integer; buffer:array0n-1 of item; notfull,notempty:condition; procedure entry put(item) begin if countn then notfull.wait; buffer(i

33、n):=nextp; in:=(in+1) mod n; count:=count+1; if notempty.queue then notempty.signal; end;procedure entry get(item) begin if count0 then notempty.wait; nextc:=buffer(out); out:=(out+1) mod n; count:=count-1; if notfull.queue then notfull.signal; end;begin in:=out:=0;count:=0;end producer:begin repeat

34、 produce an item in nextp; PC.put(item); until false; end;consumer:begin repeat PC.get(item); consumer the item in nextc; until false; end;管程解决生产者消费者问题管程解决哲学家进餐问题Type dining-philosophers=monitor var state:array04 of (thinking,hungry,eating); var self:array04 of condition; Procedure entry pickup(i:04

35、) begin statei:=hungry; test(i); if statei eating then selfi.wait end; Procedure entry putdown(i:04) begin statei:=thinking; test(i+4 mod 5); test(i+1 mod 5); end; Procedure test(k:04) begin if statek+4 mod 5 eating and statek=hungry and statek+1 mod 5 eating then begin statek:=eating; selfk.signal;

36、 end; end; Begin for i:=0 to 4 do statei:=thinking; End;Philosopher i:dining-philosophers.pickup(i)；eating;dining-philosophers.putdown(i);pickup(i:04)：若某哲学家处于饥饿，且他的左、右哲学家未进餐时，便允许这位哲学家进餐。否则，执行self(i).wait推迟进餐。putdown(i:04):当哲学家进餐毕，若其左、右的哲学家都在饥饿且都未用餐时，可让他们进餐。test(i:04)：测试哲学家是否已具备进餐条件。管程 VS 进程：n 设置目的不同

37、：管程是对共享资源进行管理；进程是资 源分配和执行的基本单位。 n 数据结构不同：管程定义公用数据结构（队列）；进程 定义私有数据结构（PCB）。 n 存在方式不同：管程是操作系统固有的部分，没有生命 周期；进程有生命周期。n 执行方式不同：管程被进程调用，没有并发性；进程具 有并发执行性。 说一说说一说进程通信n 低级通信： 如P、V操作 只能传递简单的信号，不能传递交换大量信息，效率低。 对用户不透明。n 高级通信： 利用操作系统提供的一组操作命令，传送数据量大。 对用户透明。进程通信类型（高级通信）n共享存储器系统（共享数据结构、共享存 储区）n消息传递系统（直接通信、间接通信）n管道通

38、信消息传递通信的实现方法n直接通信方式Send(receiver,message); Receive(sender,message);n间接通信方式信箱发送进程接收进程管道通信管道机制的协调能力：n 互斥：进程互斥地读、写pipe。n 同步：写进程把数据写入pipe后，便去睡眠 等待，直到读进程把数据取走才被唤醒。n 对方是否存在：确定对方存在时，才能通信。pipe写进程读进程消息缓冲队列通信机制（美.Hansan) 消息缓冲区 PCB相关数据项Type message buffer=record Sender :发送者进程标识符 Size :消息长度 Text :消息正文 Next :指向下

39、一个消息缓冲区的指针Type processcontrol block=record mq : 消息队列队首指针 mutex:消息队列互斥信号量 sm : 消息队列资源信号量PCB(B)发发送送区区接接收收区区消息缓冲区消息缓冲区Procedure send(receiver,a)begin getbuf(a.size,i);/根据a.size申请一个缓冲区i i.sender:=a.sender; i.size:=a.size; / 将发送区a中的消息 i.text:=a.text; 复制到消息缓冲区i中 i.next:=0; getid(PCB set,receiver,j); /获得接收

40、进程的内部标识符j wait(j.mutex); insert(j.mq,i); /将i挂在j.mq上 signal(j.mutex); signal(j.sm); end;Procedure receive(b) begin j:=internal name; wait(j.sm); wait(j.mutex); remove(j.mq,i); /从mq队列中摘下缓冲区i signal(j.mutex); b.sender:=i.sender; b.size:=i.size; 数据复制到以b为首址的消息接 收区内 b.text:=i.text; end;进程进程A A进程进程B B本章小结桌

41、上有一空盘，只允许放入一个水果，爸爸专向盘中放苹果，妈妈专向盘中放桔子，女儿专等着吃盘中的苹果，儿子专等着吃盘中的桔子。试用P、V操作实现爸爸、妈妈、儿子、女儿间的同步。分析：盘子中一次只能放入一个水果，当盘子为空时，爸爸可以放入苹果，或者妈妈放入桔子。若放入苹果，则允许女儿吃，若是桔子，则允许儿子吃。n 爸爸：放苹果n 妈妈：放桔子n 儿子：取桔子、吃桔子n 女儿：取苹果、吃苹果作业Var mutex,S1,S2,S3,S4:semaphore:=1,0,0,0,0;ParbeginFather: Son: repeat repeat P(mutex); P(S4); 将苹果放入果盘； P(

42、mutex); V(mutex); 取桔子； V(S3); V(mutex); P(S1); V(S1); until false; 吃桔子； until false;Mother: Daughter: repeat repeat P(mutex); P(S3); 将桔子放入果盘； P(mutex); V(mutex); 取苹果; V(S4); V(mutex); P(S2); V(S2); until false; 吃苹果； until false;Parend若按以下顺序执行：Father: P(mutex)； 放苹果； V(mutex);Mother:P(mutex); 放桔子； V(m

43、utex);情况会怎样？错误分析Var Sempty,Sapple,Sorange:semaphore:=1,0,0;ParbeginFather: Son: begin begin repeat repeat P(Sempty); P(Sorange); 将苹果放入果盘； 取桔子； V(Sapple); V(Sempty) V(Sempty); 吃桔子； until false; until false; end endMother: Daughter: begin begin repeat repeat P(Sempty); P(Sapple); 将桔子放入果盘； 取苹果； V(Soran

44、ge); V(Sempty); V(Sempty); 吃苹果； until false; until false; end endParend若V(Sempty)由Father或Mother自己来完成，会出现什么情况呢？Father: P(Sempty); 放苹果； V(Sapple); V(Sempty);Mother: P(Sempty); 放桔子； V(Sorange); 错误分析var Sempty,S1,S2,S3,S4:semaphore:=1,0,0,0,0;ParbeginFather: Son: repeat repeat P(Sempty); P(S3); 将苹果放入果盘；

45、 取桔子； V(S1); V(S4); P(S2); V(Sempty); until false; 吃桔子；吃桔子； until false;Mother: Daughter: repeat repeat P(Sempty); P(S1); 将桔子放入果盘； 取苹果； V(S3); V(S2); P(S4); V(empty); until false; 吃苹果； until false;Parendvar Sempty,Sapple,Sorange:semaphore:=1,0,0;ParbeginFather: Son: repeat repeat P(Sempty); P(Sorang

46、e); 将苹果放入果盘； 取桔子； V(Sapple); V(Sempty); until false; 吃桔子； until false;Mother: Daughter: repeat repeat P(Sempty); P(Sapple); 将桔子放入果盘； 取苹果； V(Sorange); V(Sempty); until false; 吃苹果； until false;Parend注意 n P(mutex)、V(mutex)在同一程序成对出现。而且放于访问临界资源代码前后。 如:p(mutex) reader:=reader+1 V(mutex)n 一般信号量P操作、V操作也成对出现

47、，但出现在不同的 进程中。n 信号量必须初始化，且其初值不同，其实现过程也有差别。n 出现连续两个P操作，先后顺序要注意。 理发店有几位理发师，一把理发椅和n把供等候理发的顾客坐的椅子，如果没有顾客，理发师便在理发椅上睡觉。当顾客到来时，必须先唤醒一个理发师。如果理发师正在理发时又有顾客到来，则如果有空椅子坐，顾客就坐下来等，否则，离开。思考：Var Customers，barbers，mutex:semaphore:=0,0,1Var waiting:integer:=0理发师：Begin P(customers) P(mutex) waiting:=waiting-1 V(mutex) V(barbers) 理发End 顾客： Begin P(mutex) If waitingn then Begin waiting:=waiting+1 V(mutex) V(customer) P(barbers) 允许理发 End Else V(mutex) End进程(60年代)拥有资源的独立单位独立调度和分派单位线程(80年代)创建撤消切换线程的引入缺点：时间空间开销大，限制并发度的提高。目的：减小上下文切换开销；提高并