Concurrency （并发性） Communication among processes

Presentation on theme: "Concurrency （并发性） Communication among processes"— Presentation transcript:

1 CHAPTER 5 Concurrency： Mutual Exclusion and Synchronization （并发性：互斥和同步）

2 Concurrency （并发性） Communication among processes
Sharing of and competing (竟争)for resources Synchronization of the activities of multiple processes Allocation of processor time to processer

3 Concurrency Multiple applications Structured application
Multiprogramming Structured application Application can be a set of concurrent processes Operating-system structure Operating system is a set of processes or threads

4 5.1 PRINCIPLES OF NCURRENCY (并发的原理)
Difficulties with Concurrency Sharing global resources Management of allocation of resources It become very difficult to locate a Programming errors

5 A Simple Example procedure echo; Var out,in:character; begin
input (in,keyboard); out: = in; output(out,display); end

6 A Simple Example Process P1 Process P2 . . Input(in,keyboard) .
Input(in,keyboard) . Input(in,keyboard) Out: = in out: = in Output(out,display) . Output(out,display)

7 Operating System Concerns （操作系统关注的问题）
Keep track of active processes:PCB Allocate and deallocate resources Processor time:scheduling Memory:virtual memory Files I/O devices Protect data and resources Result of process must be independent of the speed of execution of other concurrent processes（应保证进程执行的结果与速度无关）

8 Process Interaction Processes unaware of each other
- Competition - Mutual exclusion, Deadlock, Starvation Processes indirectly aware of each other - Cooperation by sharing - Mutual exclusion, Deadlock, Starvation, Data coherence(一致性) Process directly aware of each other - Cooperation by communication - Deadlock, Starvation

9 表5．1进程的交互 知道程度 关系 一个进程对其他进程的影响 潜在的控制问题 进程之间不知道对方 （进程间无工作联系） 竞争
1 一个进程的结果与其它进程的活动无关 2 进程的分时可能会受到影响 互斥 死锁（可复用的资源） 饿死 进程间接知道对方 （如共享对象） 通过共享合作 1. 一个进程的结果可能依赖于从其他进程获得的信息 2. 进程的分时可能会受到影响 数据一致性 进程直接知道对方 （它们有可用的通信原语） 通过通信合作 死锁（可消费的资源）

10 Competition Among Processes for Resources
Mutual Exclusion(互斥) Critical sections（临界区） Only one program at a time is allowed in its critical section (一次仅允许一个进程在临界区) Example only one process at a time is allowed to send command to the printer（critical resource）（例如一次仅允许一个进程发打印命令） Deadlock（死锁） Starvation

11 Competition Among Processes for Resources
Deadlock 例如，有两个进程P1、P2，竞争两个资源R1、R2。假设 占用：P1（R2） and P2（R1） 申请：P1（R1） and P2（R2） 结果：P1、P2永久等待（死锁）

12 Competition Among Processes for Resources
Starvation（饿死） 例如，有三个进程P1、P2、P3，竞争资源R假设 占用：P1（R） 申请：P2（R） and P3（R） 释放：P1（R） 占用：P2（R） 申请：P1（R） and P3（R） 释放：P2（R） 结果：P3（饿死）

13 Mutual Exclusion Mechanism 互斥机制
entry section critical section exit section （阅读P194，图5.1）

14 Cooperation Among Processes by Sharing （进程间由于共享合作）
Writing must be mutually exclusive （对写共享变量必须互斥） Critical sections are used to provide data integrity （确保数据完整性使用临界区） 例如：两个数据保持相等：A=B，初始值相等。 P1：A=A+1； B=B+1； P2：B=2*B； A=2*A 当P1和P2顺序执行，能保证一致。但并发执行，就可能出现A≠B，因此必须采用临界资源管理才能达到数据的一致性。

15 Cooperation Among Processes by Communication （进程间由于通信的合作）
Because nothing is shared between processes in the act of passing messages Mutual exclusion is not a control requirement for this sort of cooperation. Possible to have deadlock Each process waiting for a message from the other process Possible to have starvation Two processes sending message to each other while another process waits for a message

16 Requirements for Mutual Exclusion （互斥的要求）
1. Only one process at a time is allowed in the critical section for a resource (一次仅允许一个进程进入临界区) 2. A process that halts in its non-critical section must do so without interfering with other processes(处于非临界区的进程不能干预其它进程) 3. No deadlock or starvation

17 Requirements for Mutual Exclusion （互斥的要求）
4. A process must not be delayed access to a critical section when there is no other process using it(当没有进程在临界区时应立即进入) 5. No assumptions are made about relative process speeds or number of processors(对相关进程的速度和处理机的数目没有任何要求和限制) 6. A process remains inside its critical section for a finite time only(一个进程驻留在它的临界区中的时间必须是有限的确)

18 Requirements for Mutual Exclusion （互斥的要求）
空闲让进 忙则等待 有限等待 让权等待

19 Approaches of Mutual Exclusion （互斥的方法）
Software Approaches（ 软件方法） Hardware Support Semaphores Monitors Message Passing

20 5.2 Software Approaches Memory access level
Access to the same location in main memory are serialized by some sort of memory arbiter Dekker’s Algorithm Peterson’s Algorithm

21 Dekker’s Algorithm : First Attempt
Busy Waiting Process is always checking to see if it can enter the critical section Process can do nothing productive until it gets permission to enter its critical section

22 Dekker’s Algorithm : First Attempt（第1种尝试） 图5.2“爱斯基摩人的小屋协议”（P198）
门和小屋很小，每次只能容纳一个人进入，小屋内有一个标志黑板 进程申请进入临界区，必须首先进入小屋并检查黑板标志是否是它 是，离开小屋，进入临界区，执行完毕，退出临界区， 并返回小屋，修改黑板标志为其他进程 否，反复进入小屋，检查黑板标志，直到标志是它自己

23 小黑版指示P1可进

24 保证了互斥，但存在问题：进程“忙等”进入临界区；若黑板标志修改失败，其他进程永久阻塞
var turn:0..1; {共享的全局变量} PROCESS PROCESS 1 … … while turn≠0 do {nothing}; while turn ≠ 1 do {nothing}; <critical section>; <critical section> turn:=1; turn:=0; 解析 保证了互斥，但存在问题：进程“忙等”进入临界区；若黑板标志修改失败，其他进程永久阻塞

25 Dekker’s Algorithm ★Second Attempt （第2种尝试）
Each process can examine the other’s status but cannot alter it When a process wants to enter the critical section, It checks the other processes first If no other process is in the critical section, it sets its status for the critical section

26 图5.3 每个人有一个自己的小屋 （P199） 每个人只能检查，但不能修改其他人的黑板标志 若某人申请进入临界区，首先检查对方黑板是否为“false” 是，修改自己小屋黑板值为“true”，进入临界区执行，完毕，恢复黑板值为“false” 否，反复进入小屋，检查黑板标志，直到标志是“false”

27

28 var flag : array [0..1] of boolean :false ; {共享全局变量}
PROCESS PROCESS 1 … … while flag[1] while flag[0] do {nothing}; do {nothing}; flag[0]:=true; flag[1]:=true; <critical section>; <critical section> flag[0]:=false; flag[1]:=false; … …

29 若进程执行完临界区，恢复自己标志为“false”失败，则其他进程永久阻塞。
This method does not guarantee mutual exclusion 分析以下执行顺序： P0：当flag[1]=false; 执行while flag[1]; P1：当flag[0]=false; 执行while flag[0]; P0：置flag[0]=true 执行<critical section>; P1：置flag[1]=true; 执行<critical section>;

30 Dekker’s Algorithm ★Third Attempt （第3种尝试）
Set flag to enter critical section before check other processes If another process is in the critical section when the flag is set, the process is blocked until the other process releases the critical section

31 var flag : array [0..1] of boolean :false ;
{共享的全局变量} PROCESS PROCESS 1 … … flag[0]:=true; flag[1]:=true; while flag[1] while flag[0] do {nothing}; do {nothing}; <critical section>; <critical section> flag[0]:=false; flag[1]:=false; … … 解析：如果两个进程在执行while之前都把flag设置成true，那么每个进程都会以为对方进入了临界区，使自己处于阻塞，从而导致死锁。 首先设标志

32 Dekker’s Algorithm ★Fourth Attempt （第4种尝试）
A process sets its flag to indicate its desire to enter its critical section but is prepared to reset the flag Other processes are checked. If they are in the critical region, the flag is reset and later set to indicate desire to enter the critical region. This is repeated until the process can enter the critical region.

33 重置标志 var flag : array [0..1] of boolean :false ; {共享的全局变量}
PROCESS PROCESS 1 … … flag[0]:=true; flag[1]:=true; while flag[1] do while flag[0] do begin begin flag[0] :=false; flag[1] :=false; <delay for a short time>; <delay for a short time>; end; end; <critical section>; <critical section> flag[0]:=false; flag[1]:=false; … … 重置标志

34 试按以下顺序执行： P0：置flag[0]=true;
P0：执行while flag[1]; P1：执行while flag[0]; P0：置flag[0]=false; P1：置flag[1]=false; P0：置flag[0]=true; … 解析：检查其它进程，然后重置，再检查，再重置…， 重置序列可以无线延伸，任何一个进程都不能进入自己的临界区。(这种现象称为:互斥礼让)

35 Dekker’s Algorithm : Correct Solution
该算法的主要思想是:需要两个变量: 1. turn:指出应该哪一个进入 the critical section turn=0 表示P0可以进入 turn=1 表示P1可以进入 2.Flag:指出当前哪一个在临界区 Flag=0 表示P0当前在临界区 Flag=1 表示P1当前在临界区 图5.4增加一个带准许进入临界区标志的小屋

36 指示P0可以进入临界区

37 代码描述（P203,图5.5） var flag： array[0..1] of boolean;
turn：0..1; //准许进入临界区标志变量 begin flag[0]：=false； flag[1]：= false; turn:＝1；//设P1进程在临界区 parbegin p0；p1; parend end

38 procedure P0； Begin repeat flag[0]:＝true； //初值为真， P0希望进入临界区。 while flag[1] do //查P1进程标志 if turn=1 then //turn为1，表明P1进程在临界区 begin flag[0]:=false; while turn=1 //当turn=0，表明P0进程可以进入临界区 do { nothing }； flag[0]：＝ true; //设标志为真，P0进入临界区 end; ＜critical section ＞ ; turn：=1； //指定P1进程可进临界区 flag[0]：＝ false; ＜remainder ＞ forever end

39 procedure P1; begin repeat flag[1]:=true； while flag[0] do if turn=0 then flag [1]:＝false; while turn＝0 do { nothing}； flag[1]:＝true end; <critical section ＞; turn：＝0; flag[1]：＝ false； <remainder> forever end

40 解析（分析P0的执行） 1. 置flag[0]:=true; 2. 执行while flag[1] 语句有两种情况:
(1)当flag[1] = false, P0进入临界区，执行完成，置turn:=1; flag[0]:=false ; (2)当flag[1] = true,检查turn的值, turn的值又有两种情况: ①turn = P0忙等 ②turn =0 P1已退出（但还未修改flag的值）， P0立即进入

41 Peterson’s Algorithm 提出简单的互斥方案：turn解决同时的冲突，Flag指示进程是否在临界区。对两参量同时控制，交替进入临界区执行。 代码描述（图5.6，P204） 解析： 分析P0的执行： 1.置flag[0]:=true;{阻止P1进入临界区} 2.执行while flag[1] 当flag[1]=false时,P0进入，执行完成，置flag[0]:=false; 当flag[1]=true时,P0阻塞，等待P1退出

42 var flag：array[ 0. 1]of boolean； turn：0
var flag：array[ 0..1]of boolean； turn：0..1; begin flag[0]:＝false; flag[1]:＝false; turn:=1; //假设P1进程可先进临界区 parbegin P0;P1; //见下页 parend end Figure5.6 Peterson’s Algorithm for Two Processes

43 procedure P0; begin repeat flag[0]:=true; //P0进程希望进临界区 turn：＝1； while flag[1] and turn＝1 do { nothing}； ＜critical section＞； flag[0]：=false; <remainder> forever end；

44 procedure P1； begin repeat flag[1]:=true; turn:＝0; while flag[0] and turn=0 do { nothing }； < critical section >； flag[1]:=false； ＜ remainder ＞ forever end；

45 Approaches of Mutual Exclusion
Software Approaches Hardware Support Semaphores Monitors Message Passing

46 5.3 Mutual Exclusion: Hardware Support （互斥：硬件支持）
Interrupt Disabling（中断屏蔽） A process runs until it invokes an operating-system service or until it is interrupted （进程运行到它调用系统服务或被中断为止） Disabling interrupts guarantees mutual exclusion（屏蔽中断以确保互斥） Multiprocessor(在多处理机中) disabling interrupts on one processor will not guarantee mutual exclusion

47 实现互斥的过程 While (true ) { <disable interrupts> /* 屏蔽中断 */ <critical section> /* 临界区 */ <enable interrupt> /* 启用中断 */ <remainder> /* 其余部分 */ }

48 Special Machine Instructions (专门的机器指令 )
在一个多处理器配置中，几个处理器共享访问一个公共的主存。在这种情况下，不存在主／从关系，处理器的间行为是无关的，表现出一种对等关系，处理器之间没有支持互斥的中断机制。处理器的设计者提出了一些机器指令，用于保证两个动作的原子性。 如在一个取指令周期中对一个存储器单元的读和写，或者读和测试。由于这些动作在一个指令周期中执行，它们不会受到其他指令的干扰。

49 两种最常见的指令描述如下： function testset ( var i:integer ) : boolean ; begin
1. Test and Set Instruction function testset ( var i:integer ) : boolean ; begin if i = 0 then i := 1; testset := true; end else testset :=false; end. 例如：Figure5.7 a (p206)

50 program mutualexclusion; const n＝. ;(. number of processes
program mutualexclusion; const n＝...;(*number of processes* ）； var bolt：integer； procedure PO(i:integer）； begin repeat repeat { nothing } until testset(bolt) ；当bolt为0时，进入临界区， < critical section >; bolt:＝ 0; < remainder> forever end; begin（* main program*） bolt:=0; parbegin P(1)； P(2)； ... P(n); parend end (a)Test and Set Instruction

51 2. Exchange Instruction var temp; begin temp := m; m := r; r := temp;
procedure exchange ( var r :register; var m :memory ); var temp; begin temp := m; m := r; r := temp; end. 例如：Figure5.7 b (p206)

52 program mutualexclusion； const n=. ; (
program mutualexclusion； const n=...; (*number of processes）; var bolt： integer； procedure P（i：integer）; var keyi：integer; begin repeat keyi：＝1; repeat exchange（keyi，bolt） until keyi=0; ＜critical section ＞ ; exchange(keyi，bolt）； ＜remainder ＞ forever end； begin（*main program*) bolt：＝ 0; parbegin P(1)； P(2）； ... P(n); parend end. (b)Exchange Intruction

53 ●Advantages of Machine Instructions
(机器指令的优点) Applicable to any number of processes on either a single processor or multiple processors sharing main memory （可应用于单处理机或多处理机中多进程共享存储器） It is simple and therefore easy to verify （非常简单且易于证明） It can be used to support multiple critical sections；each critical section can be defined by its own varible. （可支持多个临界区，每个临界区可用自己的变量定义）

54 (机器指令的缺点) ●Disadvantages of Machine Instructions
Busy-waiting consumes processor time Starvation is possible when a process leaves a critical section and more than one process is waiting. Deadlock If a low priority process P1 has the critical region a higher priority process P2 needs , the higher priority process P2 will obtain the critical region P1 to wait for the critical region If P2 now attempts to use same resource as P1

55 Approaches of Mutual Exclusion
Software Approaches Hardware Support Semaphores Monitors Message Passing

56 5.4 Semaphores Special variable called a semaphore. (信号量是一个特殊的变量)
Semaphore is a variable that has an integer value May be initialized （初始化）to a nonnegative number To transmit a signal via semaphore s，a process executers the primitive signal(s). （为了经信号量传出一信号，进程执行signal（s）原语） To receive a signal via semaphore s，a process executes the primitive wait(s); （为了经信号量接收一信号，进程执行wait（s）原语）

57 ●Wait operation decrements the semaphore value
- wait(s)：s－1 - wait操作:申请资源且可能阻塞自己(s＜0) ●Signal operation increments semaphore value - signal(s)：s＋1 - signal操作:释放资源并唤醒阻塞进程(s≤0) ●Wait and signal operations cannot be interrupted （ Wait and signal 操作不能被中断） ●Queue is used to hold processes waiting on the semaphore（建立信号量相关的进程等待队列）

58 Types of Semaphores General Semaphore(通用信号量）,原语定义见P209，图5.8
- 通用信号量是记录型，其中一个域为整型，另一个域为队列，队列中的元素为等待该信号量的阻塞进程（FIFO） Binary Semaphore(二进制信号量）,原语定义见P209，图5.9

59 Type semaphore=record count: integer； queue: list of process end; void s:semaphore; Wait(s): s.count:=s.count-1； if s.count ＜0 then begin place this process in s.queue； block this process end signal（s）: s.count:=s.count+1； if s.count ≤0） remove a process P from s.queue; place process P on ready list； end ; 图5．8 信号量原语的定义

60 typebinary semaphore=record value:(0,1)； queue: list of process; end Var s:binary semaphore; waitB(s): if s.value=1 then s．value ＝ 0; else begin place this process in s.queue； block this process； end; signalB（s）: if s.queue is empty s．Value: ＝ 1; else begin remove a process P from s．queue； place process P on ready list ; 图5.9 二进制信号量原语的定义

61 Mutual Exclusion:Semaphores
Solution to the mutual exclusion problem using a semaphore (解决互斥的问题使用信号量) （图5.10， P210,见下页） 信号量的意义 互斥信号量：申请/释放使用权，常初始化为1

62 Program mutualexclusion; Const n=…
Program mutualexclusion; Const n=….;(进程数） Var s:semaphore (:=1); Procedure P(I:integer); Begin Repeat Wait(s); <critical section>; Signal(s); <remainder> Forever end Begin (* main program*) Parbegin P(1); p(2);….p(n); parend; End Figure 5.10 使用信号量互斥

63 2.资源信号量：申请/归还资源，资源信号量可以初始化为一个正整数（表示系统中某类资源的可用个数），s.count的意义为：
s.count≥0：表示还可执行wait(s)而不会阻塞的进程数（可用资源数） s.count﹤0：表示s.queue队列中阻塞进程的个数（被阻塞进程数）

64 Producer/Consumer Problem (生产者和消费者问题)
One or more producers are generating data and placing these in a buffer One or more consumer is taking items out of the buffer one at time Only one producer or consumer may access the buffer at any one time (但一次仅一个生产者或消费者访问缓冲区)

65 Producer/Consumer Problem
任务及要求 buffer不能并行操作（必须互斥），即某时刻只允许一个实体（producer or consumer）访问buffer 控制producer and consumer协调（同步）地读/写buffer，即不能向满buffer写数据；不能在空buffer中取数据

66 Infinite Buffer

67 缓冲区无限的生产者和消费者问题 producer: repeat produce item v; b[in] := v;
in := in + 1； forever; consumer ： repeat while in≤out do {nothing};//无产品 w := b[out]; out := out + 1； consume item w;

68 Solution to the Infinite Buffer Using Binary Semaphore
Try to implement this system using binary semaphores （Fig 5.13, P213, 见下页) - n = in – out；(n为可取的产品数) - ‘s’ is used to enforce mutual exclusion (s为互斥使用信号量) - ‘delay’ is used to force the consumer to wait if the buffer is empty (用delay信号量实现,当缓冲区空时,消费者等待)

69 program mutualexclusion; var n:integer ; s:(. binary
program mutualexclusion; var n:integer ; s:(*binary*)semaphore (:=1); delay:(*binary*)semaphore(:=0); procedure producer; begin repeat produce; waitB(s); append; n:=n+1; if n≥1 then signalB(delay); signalB(s); forever end;

70 procedure consumer; begin waitB(delay); repeat waitB(s); take; n:=n-1; signalB(s); consume; if n=0 then waitB(delay) forever end; begin (* main program*) n:=0; Parbegin producer;consumer parend; end Figure 5.13 使用二元信号量解决在无限缓冲区时 生产者与消费者问题

71 上述程序执行的可能情况如下表所示：(P214)）
消费不存在的产品

72 在考虑无限缓冲时 解决“消费不存在产品”的方法
1. 增加一个辅助变量m，参见图5.14（P215） 2.用general semaphores解决producer/ consumer问题（图5.15，P216） 在考虑有限缓冲时 解决“生产者和消费者”的问题 ●循环使用缓冲区解决“生产者和消费者”的方法:

73

74 producer: Repeat produce item v while((in+1)mod n=out)do{nothing}; b[in] = v; in = (in + 1) mod n Forever; consumer: Repeat while (in = out)do {nothing}; w = b[out]; out = (out + 1) mod n; consume item w

75 Solution to the Finite Buffer
用通用信号量解决Producer and Consumer访问有限buffer问题 （参见图5.17，P218）

76 Summary of Mutual Exclusion
利用wait、signal原语对Semaphore互斥操作实现:powerful and flexible 可用软件方法实现互斥，如Dekker 算法、Peterson算法等（但增加处理负荷） 可用硬件或测试指令的方法实现互斥，如屏蔽中断(8259)、Test and Set指令等 （属于可接受的忙等）

77 Approaches of Mutual Exclusion
Software Approaches Hardware Support Semaphores Monitors Message Passing

78 Monitor（管程） ——面向对象方法 虽然信号量机制是一种既方便、又有效的进程同步机制，但每个要访问临界资源的进程都必须自备同步操作wait（S）和signal（s）。这就使大量的同步操作分散在各个进程中。这不仅给系统的管理带来了麻烦，而且还会因同步操作的使用不当而导致系统死锁。这样，在解决上述问题的过程中，便产生了一种新的进程同步工具——管程 .

79 当共享资源用共享数据结构表示时，资源管理程序可用对该数据结构进行操作的一组过程来表示(例如，资源的请求和释放过程request和release)，我们把这样一组相关的数据结构和过程一并称为管程。
Hansan为管程所下的定义是：“一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据”。

80 管程由三部分组成： ①局部于管程的共享变量说明； ②对该数据结构进行操作的一组过程； ③对局部于管程的数据设置初始值的语句。 前两个特点让人联想到面向对象软件中对象的特点。的确，面向对象操作系统或程序设计语言可以很容易地把管程作为一种具有特殊特征的对象来实现。

81 Chief characteristics（主要特点）
Local data variables are accessible only by the monitor（局部数据变量只能被管程的过程访问，任何外部过程都不能访问）。 Process enters monitor by invoking one of its procedures（一个进程通过调用管程的一个过程进入管程）。 Only one process may be executing in the monitor at a time（在任何时候，只能有一个进程在管程中执行，调用管程的任何其他进程都被挂起，以等待管程变成可用的）。

82 为进行并发处理，管程必须包含同步工具。 例如，假设一个进程调用了管程，它在管程中时，须被挂起，直到满足某些条件时才恢复。这就需要一种机制，使得该进程不仅被挂起，而且能释放这个管程，以便某些别的进程可以进入。以后，当条件满足并且管程再次可用时，需要恢复该进程并允许它在挂起点重新进入管程。 管程通过使用条件变量提供对同步的支持，这些条件变量包含在管程中，并且只有在管程中才能被访问。有两个函数可以操作条件变量： ①cwait(c)：调用进程的执行在条件c上挂起，管程现在可被另一个进程使用。 ②csignal(c)：恢复在cwait之后为某些条件而挂起的进程的执行。如果有多个这样的进程，选择其中一个；如果没有这样的进程，什么也不做。

83 图5．21给出了一个管程的结构。尽管一个进程可以通过调用管程的任何一个过程进入管程，我们仍可以把管程想像成具有一个入口点，并保证一次只有一个进程可以进入。其他试图进入管程的进程，加入到挂起等待管程可用的进程队列中。当一个进程在管程中时，它可能会通过发送cwait(x)把自己暂时挂起在条件x上，随后它被放入等待条件改变以重新进入管程的进程队列中。

84

85 例如，使用管程的方法解决生产者和消费者的问题。（参见图5.23 P227）
/* program producerconsumer */ monitor boundedbuffer; buffer:array[0..N]of char; //space for N items nextin,nextout:integer; //buffer pointers count:integer; //number of items in buffer notfull, notempty:condition; //for synchronization

86 procedure append（x：char); begin if count = N then cwait(notfull); //buffer is full; avoid overflow buffer[nextin]:=x; nextin:=nextin+1 mod N； count:=count＋1; //one more item in buffer csignal(notempty); //resume any waiting consumer end;

87 procedure take（x ：char）； begin if count=0 then cwait(notempty)； //buffer is empty; avoid underflow x:=buffer[nextout]; nextout:=（nextout ＋ 1）mod N; count:= count-1; //one fewer item in buffer csignal（notfull）； //resume any waiting producer end; begin //monitor body nextin:=0;nextout:=0; count:=0; //buffer initially empty end

88 procedure preducer； var x：char; begin repeat produce(x); append(x); forever end; procedure consumer; var x:char; take(x); consume(x); end

89 begin (*main program*) parbegin producer; consumer parend end figure5.23 A Solution to to the Bounded-Buffer Producer/Consumer Problem Using a Monitor

90 Monitor is a software module。
管程是用并发pascal、pascal plus、Modula-2、Modula-3等语言编写的程序，现在已形成了许多库函数。管程可以锁定任何对象，如链表或链表的元素等。 用管程实现互斥比用信号量实现互斥，更简单、更方便、更安全。

91 Approaches of Mutual Exclusion
Software Approaches Hardware Support Semaphores Monitors Message Passing

92 5.6 Message Passing 当进程互相交互时，必须满足两个基本要求：同步和通信。 为实施互斥，进程间需要同步；
为了合作，进程间需要交换信息； 提供这些功能的一种方法是消息传递。消息传递的实际功能以一对原语的形式提供： send (destination, message) receive (source, message) 消息传递还有一个优点: 它有助于在分布式系统以及共享存储器的多处理器系统和单处理器系统中的实现。

93 为了进程间通信和同步，消息系统的设计特点 :

94 Synchronization(同步) 当发送进程调用执行send原语时，有两种处理方式： 1、发送者进程被阻塞，直到这个消息被接收到为止。
2、发送者进程不阻塞，继续执行。 当接收进程调用执行receive原语时，有两种处理方式： 1、如果消息在执行receive原语之前发送，则该消息能被接收。 2、如果receive原语没有接收到消息，则选择下列一种方式执行： ①该进程被阻塞直到一个消息到达 ②该进程放弃接收，继续执行

95 发送者和接受者按阻塞和非阻塞有三种不同的组合： 1、Blocking send, blocking receive
（进程间紧密同步时，采用阻塞发送和阻塞接收） Both sender and receiver are blocked until message is delivered（发送者和接受者都被阻塞，直到完成信息的传送） Called a rendezvous(称为会合) 2、Nonblocking send, nonblocking receive Neither party is required to wait（不需要任何一方等待续）

96 3、Nonblocking send, blocking receive
（最常用的一种方法：非阻塞发送，阻塞接收） Sender may continue on，Receiver is blocked until the requested message arrives. (发送者继续执行,接收者被阻塞直到请求的消息到达) It allows a process to send one or more messages to a variety of destinations as quickly as possible.(允许进程发送一个或多个消息尽快的给各种目标进程) 例如,一个服务进程给其它进程提供服务或资源. 采用此种方式存在的问题: ①由于无阻塞发送:当收不到应答,会引起多次重发 ②由于阻塞接收,当收不到消息时,会引起死等.

97 Addressing(寻址) 寻址分为：直接寻址和间接寻址。 Direct addressing(直接寻址)
send primitive includes a specific identifier of the destination process（发送原语包含目标进程的具体标识符） 接收原语有两种处理方式： ①receive primitive could know ahead of time which process a message is expected（接收进程知道接受哪一个进程的消息） ②In other cases，it is impossible to specify the anticipated source message （另一种情况指定所希望的源进程是不可能）.receive primitive could use source parameter to return a value when the receive operation has been performed（仅能当接收操作执行完之后返回源参数,接收原语能使用该源参数）

98 Indirect addressing(间接寻址)
Messages are not send directly from sender to receiver but rather are sent to a shared data structure consisting of queues that can temporarily hold message.(消息是不能从发送者直接到接收者,而是将消息送到共享的数据结构组成的队列中暂存消息) queues are called mailboxes one process sends a message to the mailbox and the other process picks up the message from the mailbox

99

100 Message Format(消息格式)

101 Queuing Discipline(排队原则)
FIFO 优先级 Mutual Exclusion(互斥) 若采用Nonblocking send, blocking receive 多个进程共享邮箱mutex。若进程申请进入临界区，首先申请从mutex邮箱中接收一条消息。若邮箱空，则该进程阻塞；若进程收到邮箱中的消息，则进入临界区，执行完毕退出，释放邮箱mutex。 参见 figure5.26(P235）

102 program mutualexclusion; const n=. ;(. number of processes
program mutualexclusion; const n=...;(*number of processes*）； procedure P（i：integer）； var meg : message； begin repeat receive(mutex， msg）； <critical section ＞; send（mutex，msg); <remainder） forever end ; begin(*main program *) create_mailbox（muteX）； send（mutex,null）； parbegin P(1）; P(2); ... P(n) parend end Figure5.26 Mutual Exclusion Using Messages

103 Message Passing (Producer/Consumer Problem)
解决有限buffer Producer/Consumer Problem （图5.27，P236） 两个邮箱： Mayconsume： Producer存放数据，供Consumer取走（即buffer数据区） Mayproduce：存放空消息的buffer空间 

104 5.7 Readers/Writers Problem
Any number of readers may simultaneously read the file Only one writer at a time may write to the file If a writer is writing to the file, no reader may read it

105 Readers/Writers Problem
可用于解决多个进程共享一个数据区（文件、内存区、一组寄存器等），其中若干读进程只能读数据，若干写进程只能写数据等实际问题。

106 Readers/Writers Problem （Readers have priority）
- Writers are subject to starvation - 参见图5.28，P238 ,其中 wsem：互斥信号量，用于Writers互斥Writers和Readers，以及第一个Reader互斥Writers readcount：统计同时读数据的Readers个数 x：对变量readcount互斥算术加减1操作

107 Readers/Writers Problem （Writers have priority）
Writers have priority:指只要有一个writer申请写数据，则不再允许新的reader进入读数据 参见图5.29 ，P240，其中为写者增加以下变量： rsem：信号量，当至少有一个写者申请写数据时互斥新的读者进入读数据（阻塞1个读者） writecount：用于控制rsem信号量 y：信号量，控制对writecount的互斥加减操作 z：信号量，用于阻塞被rsem阻塞的读者（1个）后的后继若干读者