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

内容进程同步的基本概念信号量机制经典进程同步问题管程机制进程通信信号量举例第三章进程的同步与通信目的及要求理解临界资源和临界区的概念，初步领会进程同步机制应遵循的准则；理解和掌握整型信号量和记录型信号量机制；熟练掌握利用信号量机制解决经典进程同步问题；领会管程的基本概念，掌握利用管程解决经典进程同步问题；了解进程通信的类型，理解消息传递系统中的发送和接受原语。第三章进程的同步与通信重点临界资源和临界区的概念；记录型信号量机制；利用信号量机制解决经典进程同步问题；管程的基本概念；利用管程解决经典进程同步问题。难点利用软件方法解决进程互斥问题；利用信号量机制解决经典进程同步问题；管程的概念。第三章进程的同步与通信资源共享关系 （CooperationAmongProcessesbySharing）

多进程共享资源，例如各进程争用一台打印机，这时各进程使用这台打印机时有一定的限制。每次只允许一个进程使用一段时间打印机，等该进程使用完毕后再将打印机分配给其它进程。这种使用原则称为互斥使用。相互合作关系 （CooperationAmongProcessesbyCommunication）

在某些进程之间还存在合作关系，例如一个程序的输入、计算、打印三个程序段作为三个进程并发执行，由于这三个进程间存在着相互合作的关系，即先输入再计算、最后再打印的关系，所以这三个进程在并发执行时推进序列受到限制，要保证其合作关系正确，进程间这种关系称为同步关系3.1

进程同步的基本概念3.1.1

临界资源3.1.2临界区3.1.3利用软件方法解决进程互斥问题3.1.4利用硬件方法解决进程互斥问题3.1

进程同步的基本概念象打印机这类资源一次只允许一个进程使用的资源称为临界资源。属于临界资源有硬件打印机、磁带机等，软件在消息缓冲队列、变量、数组、缓冲区等。当然还有一类象磁盘等资源，它允许进程间共享，即可交替使用，所以它称为共享资源，而临界资源又称独享资源。 进程在并发执行时为了保证结果的可再现性，各进程执行序列必须加以限制以保证互斥地使用临界资源，相互合作完成任务。3.1.1

临界资源(CriticalResources)3.1.2

临界区(criticalsections)临界区的定义与进入临界区(criticalsection)：进程中访问临界资源的一段代码。进入区(entrysection)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应“正在访问临界区”标志退出区(exitsection)：用于将“正在访问临界区”标志清除。剩余区(remaindersection)：代码中的其余部分。同步机制应遵循的准则

用于保证多个进程在执行次序上的协调关系的相应机制称为进程同步机制。空闲让进当无进程进入临界区时，相应的临界资源处于空闲状态，因而允许一个请求进入临界区的进程立即进入自己的临界区。忙则等待当已有进程进入自己的临界区时，即相应的临界资源正被访问，因而其它试图进入临界区的进程必须等待，以保证进程互斥地访问临界资源。3.1.2

临界区(criticalsections)有限等待对要求访问临界资源的进程，应保证进程能在有限时间进入临界区，以免陷入“饥饿”状态。让权等待当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等。3.1.2

临界区(criticalsections)3.1.3

利用软件方法解决进程互斥问题问题：有二个进程Pi和Pj互斥共享临界资源R，beginparbegin Pi; Pj;parendend3.1.3

利用软件方法解决进程互斥问题算法1：单标志

设置一个公用整型变量turn，用于指示被允许进入临界区的进程的编号，即若turn=i，表示允许进程Pi进入临界区。Pi进程:Pj进程:

repeatrepeatwhileturn≠idonoop;

whileturn≠jdonoop;CriticalsectionCriticalsectionturn:=j;turn:=i;RemainSectionRemainSectionuntilfalseuntilfalse3.1.3

利用软件方法解决进程互斥问题该算法可确保每次只允许一个进程进入临界区。但是，强制两个进程轮流地进入临界区，很容易造成资源利用不充分。例如，当进程只退出临界区后将turn置为j，以便允许Pj进入临界区。但如果进程Pj暂时并未要求访问该临界资源，而Pi又想再次访问该资源，但它却无法进入临界区。可见，此算法不能保证实现“空闲让进”的准则l。3.1.3

利用软件方法解决进程互斥问题算法2：双标志先检查 算法2的基本思想是：在每一个进程访问临界资源之前，先去查看一下临界资源是否正被访问。若正被访问，该进程需等待；否则才进人自己的临界区。为此，设置了一个数组，使其中每个元素的初值为false，表示所有进程都未进入临界区；而当其中的第i个元素值true时，即若flag[i]=true时，表示进程Pi正在临界区内执行。

Pi: Pj： repeatrepeat whileflag[j]dono_op; whileflag[i]dono_op; flag[i]:=true; flag[j]:=true; critical_section; critical_section; flag[i]:=false; flag[j]:=false; remaindersection; remaindersection; untilfalseuntilfalse3.1.3

利用软件方法解决进程互斥问题算法3：双标志、后检查

为了解决这一问题，在算法3中仍然使用了数flag[n]，但令flag[i]=true表示进程Pi希望进入临界区，即每当进程Pi要进入临界区前，先将flag[i]置为ture，表示进程Pi已要求进入临界区。然后再去查看Pj的标志。若此时flag[j]=true，则pi等待；否则，Pi进入临界区。换言之，算法3是使要进入临界区的进程先设置其要求进入的标志，然后，再去查看其它进程的标志。3.1.3

利用软件方法解决进程互斥问题Pi: Pj:repeatrepeat flag[i]:=true; flag[j]:=true;

whileflag[j]dono_op;

whileflag[i]dono_op; critical_section;critical_section; flag[i]:=false;flag[j]:=false; remaindersection;remaindersection;untilfalseuntilfalse3.1.3

利用软件方法解决进程互斥问题算法4：先修改、后检查、后修改者等待该算法是组合了算法1和算法3中的关键概念而形成的新算法为每个进程设置了相应的标志位flag[i]，当flag[i]=true时，表示进程Pi要求进入临界区。此外，还设置了一个turn变量，用于指示允许进入临界区的进程编号。进程Pi为了进入临界区先置flag[i]为true，并置turn为j，表示应轮到进程j进入临界区。接下去再判别flag[j]andturn=j的条件是否满足。若未满足即false，则可进入临界区；否则等待。或者说，当flag[j]=false或者turn=i时，进程pi可以进入临界区。前者表示pj未要求进入临界区，后者表示仅允许Pi进入临界区。

3.1.3

利用软件方法解决进程互斥问题Pi:repeatflag[i]:=true;turn:=j;while(flag[j]andturn=j)dono_op;critical_section;flag[i]:=false;remaindersection;untilfalse

Pj:repeatflag[j]:=true;turn:=i;while(flag[i]andturn=i)dono_op;critical_section;flag[j]:=false;remaindersection;untilfalse

3.1.3

利用软件方法解决进程互斥问题假如过程Pi和Pj几乎同时要求进入临界区，它们将分别将标志flag[i]和flag[j]置为true。Pi先将turn置j，当它去执行While语句时，flag[j]andturn=j条件成立，故又等待；但立即Pj又将turn置成I；这样，Pi便可进入临界区，而进程PJ执行while语句时，flag[i]andturn=i条件成立，使Pj等待；当Pi退出临界区时，将flag[i]置为false后，将使flag[i]andturn=j条件不再成立，从而使Pj进入临界区。这样，既保证了“忙则等待”，又实现了“有空让进”。3.1.4

利用硬件方法解决进程互斥问题

完全利用软件方法来解决诸进程互斥进入临界区的问题，有一定难度，且有很大局限性，因而现代已很少采用此方法。 针对这一点，现在有许多计算机已提供了一些特殊的硬件指令，这些指令允许对一个字中的内容进行检测和修正，或交换两个字的内容等。可利用这些特殊的指令来解决临界区问题。 下面介绍两条特殊硬件指令，以及利用它们来解决临界区问题的方法。3.1.4

利用硬件方法解决进程互斥问题利用Test－and－Set指令实现互斥Test－and－Set指令在许多机器中都有这样的指令，不同机器的相应指令的功能是相同的，因而我们不局限于某特定的机器去定义Test－and－set指令为functionTS（varlock：boolean）：boolean；

beginTS:=lock；

lock:=true；

end其中，lock有两种状态：当lock=false时，表示该资源空闲；当lock=true时，表示该资源正在被使用。3.1.4

利用硬件方法解决进程互斥问题利用TS实现进程互斥

为了实现诸进程对临界资源的互斥访问，可为每个临界资源设置一个布尔变量lock，并赋予其初值为false，以表示资源空闲。 利用TS指令实现互斥的Pi进程可描述为：

repeatwhileTS(lock)dono－loop；

criticalsection;lock:=false;remaindersectionuntilfalse；3.1.4

利用硬件方法解决进程互斥问题利用Swap指令实现进程互斥Swap指令

该指令称为交换指令。在微型机中该指令又称为XCHG指令，用于交换两个字的内容，可描述如下：

ProcedureSwap（vara,b：boolean）

vartemp：boolean；

begintemp:=a；

a:=b；

b:=temp；

end3.1.4

利用硬件方法解决进程互斥问题利用Swap实现进程互斥 在利用Swap实现进程互斥时，可为临界资源设置一个全局布尔变量lock，其初值为false(表示可用)，在每个进程中再利用一个局部布尔变量key。利用Swap指令实现进程互斥的Pi进程可描述为：repeatkey:=true;repeat Swap(lock,key);untilkey=false;criticalsection;lock:=false;remaindersectionuntilfalse；利用硬件指令能有效地实现过程互斥，但它却不能满足“让权等待”的准则，造成处理机时间的浪费，而且也很难将它用于解决较复杂的进程同步问题。

1965年，荷兰学者Dijkstra提出的信号量机制是一种卓有成效的进程同步工具。在长期且广泛的应用中，信号量机制又得到了很大的发展，它从整型信号量经记录型信号量，进而发展为“信号量集”机制。现在信号量机制已被广泛地应用于单处理机和多处理机系统，以及计算机网络中。3.2.1整型信号量机制3.2.2记录型信号量机制3.2.3信号量集机制3.2

信号量机制

整型信号量最初信号量S是一个整型变量，除初始化外，对信号量仅能执行两个原子操作，即wait(s)和signal(s),这两个原子操作以前多称为P（s）和V(s)操作。wait(s){ whiles<=0dono-loop s:=s-1;}signal(s){ s:=s+1;}3.2.1

整型信号量机制

利用信号量实现互斥

进程P1 进程P2 ┊ ┊

wait（mutex）； wait（mutex）；

criticalsection

criticalsection

signal（mutex）； signal（mutex）； remaindersection remaindersection

┊ ┊ 信号量mutex的初值为1，每个进程在进入临界区时对信号量执行wait操作，待临界区执行完后执行signal操作。3.2.1

整型信号量机制

利用信号量来描述前趋关系 信号量s的初值为0，当进程P2先执行必定阻塞，只有在P1执行完S1；signal(s)，P2才被唤醒。

进程P1 进程P2 ┊ ┊ S1; wait(s) signal(s)

S2;

┊

┊3.2.1

整型信号量机制

3.2.1

整型信号量机制

S1S2S4S6S5S3abcdefgvara,b,c,d,e,f,g:semaphore=0;beginparbeginbegins1；signal(a)；signal(b)；end；beginwait(a)；s2；signal(c)；signal(d)；end；beginwait(b)；s3；signal(e)；end；beginwait(c)；s4；signal(f)；end；beginwait(d)；s5；signal(g)；end；beginwait(e)；wait(f)；wait(g)；s6；end；parendend

习题（P94-8）：我们为某临界区设置一把锁W，当W=1时，表示关锁；W=0表示锁已打开。试写出开锁原语和关锁原语，并利用它们去实现互斥。3.2.1

整型信号量机制

解： 开锁原语

unlock(W): W:=0;

关锁原语

lock(W): whileW=1dono_op;

W=1;

利用开关锁原语实现互斥:

varW:semaphore:=0;

begin

parbegin

process:

begin

repeat

lock(W);

criticalsection

unlock(W);

remaindersection

untilfalse;

3.2.1

整型信号量机制

每个信号量s除一个整数值s.count（计数）外，还有一个进程等待队列s.queue，其中是阻塞在该信号量的各个进程的标识s.count初始化指定一个非负整数值，表示系统中某类资源的数目（又称为“资源信号量“）若为非负值，表示当前的空闲资源数若为负值，其绝对值表示当前等待临界区的进程数typesemaphore=record count:integer;

queue:listofprocess:endvars:semaphore;3.2.2

记录型信号量机制procedurewait(s)begins.count:=s.count-1;ifs.count<0thenBlock(s.queue)endproceduresignal(s)begins.count:=s.count+1;ifs.count<=0thenWakeup(s.queue);end3.2.2

记录型信号量机制ifs.count<0thenWakeup(s.queue);s.count:=s.count+1;AND型信号量集机制上述的进程的互斥问题，是针对进程间共享一个临界资源。但在某些应用场合，进程需要共享两个或更多的临界资源。例如，两个进程A和B共享临界资源D和E，则设置两个互斥信号量Dmutex和Emutex，初值为1。 ProcessA ProcessB wait(Dmutex) wait(Emutex) wait(Emutex) wait(Dmutex)

若进程A和B按下列次序交替wait操作：

ProcessA：wait(Dmutex)－>Dmutex=0 ProcessB:wait(Emutex)－>Emutex=0 ProcessA：wait(Emutex)－>Emutex=-1堵塞 ProcessB:wait(Dmutex)－>Dmutex=-1堵塞3.2.3

信号量集机制

最后进程A和B处在僵持状态，在无外力作用下，无法解脱，即死锁状态。AND同步机制基本思想：在一个原语中，对多个临界资源的分配采用原子操作方式，要么全部分配给它，要么一个都不分配。称为Swait(SimultaneousWait)。AND型信号量集用于同时需要多种资源且每种占用一个时的信号量操作；3.2.3

信号量集机制

Swait(s1,s2,....sn) if（s1＞=1ands2＞=1and....andsn＞=1） fori:=1tondo Si:=Si-1; endfor else

把调用P操作的进程置为等待状态，并插入到 第一次满足si<1的信号量的等待队列中；设置程序计数器指向Swait。

endif；3.2.3

信号量集机制

Ssignal(s1,s2,....sn)fori:=1tondoSi:=Si+1;

从等待队列Si.queue中取出进程P,进入就绪队列;endfor；3.2.3

信号量集机制

一般“信号量集”机制

一般信号量集用于同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的处理；一次需要N个某类临界资源时，就要进行N次wait操作－－低效又可能死锁基本思想在AND型信号量集的基础上进行扩充进程对信号量Si的测试值为ti，用于信号量的判断，即Si>=ti，表示资源数量低于ti时，便不予分配占用值为di，用于信号量的增减，即Si=Si-di和Si=Si+diSwait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);3.2.3

信号量集机制

Swait(s1,t1,d1;s2,t2,d2;....sn,tn,dn)

if（s1＞=t1ands2＞=t2and....andsn＞=tn）

fori:=1tondo si=si-di; endforelse 把调用P操作的进程置为等待状态，并插入到第一次满足 si<ti的信号量的等待队列中；

endif；Ssignal(s1,d1;s2,d2;....sn,dn)

fori:=1tondo si=si+di; 从si等待队列中取出进程，转为就绪状态； endfor；3.2.3

信号量集机制一般“信号量集”的几种特定情况：Swait(S,d,d) 表示每次申请d个资源，当少于d个时，便不分配；Swait(S,1,1)S>1 蜕化为记录型信号量；S=1 蜕化为互斥信号量；Swait(S,1,0) 作为一个可控开关当S>=1时，允许任何进程进入临界区；当S=0时，禁止任何进程进入临界区；3.2.3

信号量集机制

3.3

经典进程同步问题

3.3.1生产者－消费者问题

(theproducer-consumerproblem)3.3.2读者－写者问题 (thereaders-writersproblem)3.3.3哲学家进餐问题(thediningphilosophersproblem)

3.3.1生产者－消费者问题

问题描述：生产者-消费者问题是最著名的同步问题。若干进程通过有限的共享缓冲区交换数据。其中，“生产者”进程不断写入，而“消费者”进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对公用缓冲池进行操作。3.3.1生产者－消费者问题

利用记录型信号量解决生产者-消费者问题任何时刻只能有一个进程可对公用缓冲池进行操作。

互斥信号量mutex用于互斥访问公用缓冲池，初值是1资源信号量full表示“满”缓冲区的数目，初值为0，资源信号量empty表示"空"缓冲区的数目，初值为N。full+empty=N varmutex,empty,full:semaphore:1,n,0;3.3.1生产者－消费者问题

varmutex,empty,full:semaphore:1,n,0;buffer:array[0,…,n-1]ofitem;in,out:integer:=0,0;beginparbegin producer:begin repeat produceaniteminnextp;

wait(empty); wait(mutex); buffer[in]:=nextp; in:=(in+l)modn; signal(mutex); signal(full); untilfalse; end3.3.1生产者－消费者问题

consumer:begin repeat wait(full); wait(mutex); nextc:=buffer(out); out:=(out+l)modn; signal(mutex); signal(empty); consumeaniteminnextc; untilfalse; end parendend3.3.1生产者－消费者问题

在进程同步时管理一个共享资源可能要设二个信号量，而在进程互斥管理时只要设一个信号量；每个程序中的互斥信号量mutex的wait与signal操作必须成对出现；资源信号量的wait与signal操作，也成对出现，但分别出现在不同的程序中；每个程序中的wait操作不能颠倒，必须先执行对资源信号量的wait操作，然后执行互斥信号量的wait操作，否则可能引起进程死锁;3.3.1生产者－消费者问题

利用AND信号集解决生产者-消费者问题Swait(empty,mutex)wait(empty);wait(mutex);Ssignal(mutex,full) signal(mutex);signal(full);

Swait(full,mutex)wait(full);wait(mutex);Ssignal(mutex,empty)signal(mutex);signal(empty);3.3.1生产者－消费者问题

varmutex,empty,full:semaphore:1,n,0;buffer:array[0,…,n-1]ofitem;in,out:integer:=0,0;beginparbegin producer:begin repeat produceaniteminnextp; Swait(empty,mutex); buffer[in]:=nextp; in:=(in+l)modn; Ssignal(mutex,full); untilfalse; end3.3.1生产者－消费者问题

consumer:begin repeat Swait(full,mutex); nextc:=buffer(out); out:=(out+l)modn; Ssignal(mutex,empty); consumeaniteminnextc; untilfalse; end parendend3.3.1生产者－消费者问题

习题（P94-6): 在生产者－消费者问题中，如果缺少了signal(full)或signal(empty),对执行结果会有何影响?解：生产者－消费者问题可描述如下:

wait(empty); wait(full);

wait(mutex); wait(mutex);

buffer(in):=nextp; nextc:=buffer(out);

in:=(in+1)modn; out:=(out+1)modn;

signal(mutex); signal(mutex);

signal(empty);3.3.1生产者－消费者问题

wait(empty); wait(full);

wait(mutex); wait(mutex);

buffer(in):=nextp; nextc:=buffer(out);

in:=(in+1)modn; out:=(out+1)modn;

signal(mutex); signal(mutex);

signal(full); 3.3.1生产者－消费者问题

习题（P94-7): 在生产者－消费者问题中，如果将两个wait操作即wait(full)和wait(mutex)互换位置；或者是将signal(mutex)与signal(full)互换位置结果会如何?解：生产者－消费者问题可描述如下:

wait(empty); wait(mutex);

wait(mutex); wait(full);

buffer(in):=nextp; nextc:=buffer(out);

in:=(in+1)modn; out:=(out+1)modn;

signal(mutex); signal(mutex);

signal(full); signal(empty);

3.3.1生产者－消费者问题

wait(mutex); wait(full);

wait(empty); wait(mutex);

buffer(in):=nextp; nextc:=buffer(out);

in:=(in+1)modn; out:=(out+1)modn;

signal(mutex); signal(mutex);

signal(full); signal(empty);

3.3.1生产者－消费者问题

wait(empty); wait(full);

wait(mutex); wait(mutex);

buffer(in):=nextp; nextc:=buffer(out);

in:=(in+1)modn; out:=(out+1)modn;

signal(full); signal(mutex);

signal(mutex); signal(empty);3.3.1生产者－消费者问题

wait(empty); wait(full);

wait(mutex); wait(mutex);

buffer(in):=nextp; nextc:=buffer(out);

in:=(in+1)modn; out:=(out+1)modn;

signal(mutex); signal(empty);

signal(full); signal(mutex);

3.3.2

读者－写者问题

问题描述：有一数据区为多个进程所共享。假设一些进程只能对该数据区完成读操作（读者），而另一些进程只能对其完成写操作（写者），读者和写者要遵守以下约束：允许多个读者同时从数据区中读数据；任何时候只允许一个写者向数据区中写数据；当有读者正在读数据时，不允许写者写数据；若有写者正在写数据区，不允许读者读数据。3.3.2

读者－写者问题

利用记录型信号量解决读者－写者问题互斥信号量wmutex：初值是1。公共变量readcount：表示“正在读”的进程数，初值是0；互斥信号量rmutex：表示对readcount的互斥操作，初值是1。3.3.2

读者－写者问题Varrmutex,wmutex:semaphore:=1,1;readcount:integer:=0;beginparbeginreader:begin ／*读者进程*／ repeat wait(rmutex)； ifreadcount=0thenwait(wmutex); readcunt：=readcount+1; signal(rmutex); ReadText wait(rmutex); readcount=readcount-1; ifreadcount=0thensignal(wmutex); signal(rmutex); untilfalse;end

3.3.2

读者－写者问题

writer:begin repeat wait(wmutex);／*写者进程*／ WriteText; signal(wmutex); untilfalse endparendend3.3.2

读者－写者问题

讨论信号量WRmutex用于读者和写者、写者和写者之间互斥访问数据区。允许多个读者同时访问数据区。第一个读者进入时要用信号量Wmutex与写者互斥。变量readcount用于记录正在读数据区的读者数量。由于该变量能够被多个进程共享，也属于临界资源，所以使用信号量Rmutex对其实施互斥访问。允许多个读者同时读数据区，当至少有一个读者正在读时，其他读者无须等待就可以读数据。在本例中，一旦有一个读者开始访问数据区，其后，只要至少有一个读者正在访问数据区，读者将一直保持对数据区的控制权，这样可能会造成写者的饿死。3.3.2

读者－写者问题

利用信号量集机制解决读者－写者问题L,mx:semaphore:=RN,1;

/*规定最多只能有RN个读者同时读*/beginparbeginreader:begin ／*读者进程*／ repeat Swait(L,1,1);/*L>=1表示读者数不满RN个，本读者可读*/ Swait(mx,1,0);/*mx=1表示无写者在写，本读者可读*/ performreadoperation Ssignal(L,1); untilfalse;end3.3.2

读者－写者问题writer:begin ／*写者进程*／repeatSwait(mx,1,1,L,RN,0);/*mx=1表示无写者在写，同时L=RN表示无读者在读*/performwriteoperationSsignal(mx,1); untilfalse;endparendend3.3.3哲学家进餐问题

问题描述：5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起左边和右边的两支筷子，思考时同时将两支筷子放回原处3.3.3哲学家进餐问题利用记录型信号量解决哲学家进餐问题varchopstick：array[0,…,4]ofsemaphore:=(1,1,1,1,1)第i个哲学家的活动可描述为：repeat wait(chopstick[i]); wait(chopstick[(i+1)mod5]; eat; signal(chopstick[i]); signal(chopstick[(i+1)mod5]; think;untilfalse；3.3.3哲学家进餐问题

若五个哲学家同时饥饿，而各自拿起左边的筷子，则造成死锁。其解决方法：至多只允许四个哲学家同时进餐仅当哲学家的左、右两支筷子均可用时，才允许拿起筷子进餐规定奇数号的哲学家先拿左边的筷子，再拿右边的筷子，而偶数号的哲学家先拿右边的筷子，再拿左边的筷子；3.3.3哲学家进餐问题利用AND信号量解决哲学家进餐问题

varchopstick：array[0,…,4]ofsemaphore:=(1,1,1,1,1)第i个哲学家的活动可描述为：

repeat think; Swait（chopstick[i]，chopstick[（i+1）mod5]）; eat; Ssignal（chopstick[i]，chopstick[（i+1）mod5]）;untilfalse；3.4

管程机制

用信号量可实现进程间的同步，但由于信号量的控制分布在整个程序中，其正确性分析很困难。管程是管理进程间同步的机制，它保证进程互斥地访问共享变量，并方便地阻塞和唤醒进程。管程可以函数库的形式实现。相比之下，管程比信号量好控制。3.4.1管程的引入3.4.2管程的基本概念3.4.3利用管程解决生产者――消费者问题3.4.4利用管程解决读者-写者问题3.4.1管程的引入

信号量同步的缺点同步操作分散 信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（如P、V操作的次序错误、重复或遗漏）易读性差 要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序；管程的引入 1973年，Hoare和Hanson所提出；其基本思想是把信号量及其操作原语封装在一个对象内部。即：将共享变量以及对共享变量能够进行的所有操作集中在一个模块中。3.4.2

管程的基本概念

管程的定义 管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。管程的主要特性模块化 一个管程是一个基本程序单位，可以单独编译；抽象数据类型 管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码信息封装 管程中的外部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的；3.4.2

管程的基本概念

管程的的组成名称：为每个共享资源设立一个管程数据结构说明：一组局部于管程的控制变量操作原语：对控制变量和临界资源进行操作的一组原语过程（程序代码），是访问该管程的唯一途径。这些原语本身是互斥的，任一时刻只允许一个进程去调用，其余需要访问的进程就等待。初始化代码：对控制变量进行初始化的代码3.4.2

管程的基本概念

条件变量(condition)

管程提供了一种可以允许多进程安全有效地共享抽象数据类型的机制，管程实现同步机制由“条件结构”（conditionconstruct）所提供。 为实现进程互斥同步，必须定义一些条件变量，（例如：varnotempty，notfull：condition）。这些条件变量是只能被wait和signal操作所访问。

3.4.2

管程的基本概念

notfull.wait操作意味着调用该操作的进程将被挂起，另至直一个进程执行；

notfull.signal操作仅仅是启动一个被堵塞的进程，如无堵塞进程则notfull.signal操作相当于空操作，不改变notfull状态，这不同于v操作。 若Q堵塞，P执行notfulll.Signal,执行管程中的唤醒切换方法：P等待Q继续，直到Q等待或退出；Q等待P继续，直到P等待或退出；3.4.3利用管程解决生产者―消费者问题

建立一个管程PC，它包括两个过程put（item）和get（item），它们分别执行将生产的消息放入缓冲池和从缓冲池取出消息的操作，设置一变量count表示缓冲池已存消息数目。TypePC=monitorvarin,out,count:integer;buffer:array[0,…,n-1]ofitem;notfull,notempty:condition;procedureentryput(item)beginifcount>=nthennotfull.wait;beffer(in):=nextp;in:=(in+1)modn;count=count+1;ifnotempty.queuethennotempty.signal;end3.4.3利用管程解决生产者―消费者问题procedureentryget(item)beginifcount<=0thennotempty.wait;nextc:=buffer(out);out:=(out+1)modn;count:=count-1;ifnotfull.queuethennotfull.signal;endbeginin:=out:=0;count:=0;end

3.4.3利用管程解决生产者―消费者问题生产者和消费者程序为：producer:beginrepeatproduceaniteminnextp;PC.put(item);untilfalse;endconsumer:beginrepeatPC.get(item);consumetheiteminnextc;untilfalse;end3.4.3利用管程解决生产者―消费者问题3.4.4

利用管程解决读者-写者问题信号量的C++描述

classSemaphoreClass{public: SemaphoreClass(LONGcInitialValue); voidP(void); voidV(void);private: HANDLEhSemaphore; LONGcMax;};3.4.4

利用管程解决读者-写者问

管程的C++描述classMonitorClass{public: MonitorClass(void); voidMonitorEnter(void); voidMonitorLeave(void); voidMonitorWait(SemaphoreClass hSemCondition, int*lpConditionCount); voidMonitorSignal(SemaphoreClass hSemCondition, int*lpConditionCount);

private: SemaphoreClassMonitorMutex;//Initialvalueis1. SemaphoreClassMonitorUrgent;//Initialvalueis0. int UrgentCount; //Monitorurgentsemaphorecounter.};3.4.4

利用管程解决读者-写者问

MonitorClass::MonitorClass(void):MonitorMutex(1),MonitorUrgent(0){ UrgentCount=0;}voidMonitorClass::MonitorEnter(void){ MonitorMutex.P();}3.4.4

利用管程解决读者-写者问题voidMonitorClass::MonitorLeave(void){ if(UrgentCount>0) { UrgentCount--; MonitorUrgent.V(); } else { MonitorMutex.V(); }}3.4.4

利用管程解决读者-写者问题voidMonitorClass::MonitorWait( SemaphoreClasshSemCondition, int*lpConditionCount){(*lpConditionCount)++;if(UrgentCount>0){ UrgentCount--; MonitorUrgent.V();}else{ MonitorMutex.V();}hSemCondition.P();}3.4.4

利用管程解决读者-写者问题voidMonitorClass::MonitorSignal( SemaphoreClasshSemCondition, int*lpConditionCount){if((*lpConditionCount)>0){ (*lpConditionCount)--; UrgentCount++; hSemCondition.V(); MonitorUrgent.P();}}3.4.4

利用管程解决读者-写者问

读者-写者问题

classReaderWriterClass{public: voidStartReader(void); voidFinishReader(void); voidStartWriter(void); voidFinishWriter(void); ReaderWriterClass(void);private: MonitorClass ReaderWriterMonitor; SemaphoreClass rq,wq; //读写等待队列

intr_count,w_count; //读写等待计数

intreading_count,write_count;};3.4.4

利用管程解决读者-写者问

ReaderWriterClass::ReaderWriterClass(void):ReaderWriterMonitor(),rq(0),wq(0){reading_count=0;write_count=0;r_count=0;w_count=0;}3.4.4

利用管程解决读者-写者问

voidReaderWriterClass::StartReader(void){ ReaderWriterMonitor.MonitorEnter(); if(write_count>0) { ReaderWriterMonitor.MonitorWait(rq, &r_count); } reading_count++; ReaderWriterMonitor.MonitorSignal(rq, &r_count); ReaderWriterMonitor.MonitorLeave();}3.4.4

利用管程解决读者-写者问

voidReaderWriterClass::FinishReader(void){ ReaderWriterMonitor.MonitorEnter(); reading_count--;if(reading_count==0) { ReaderWriterMonitor.MonitorSignal(wq, &w_count); } ReaderWriterMonitor.MonitorLeave();}3.4.4

利用管程解决读者-写者问

voidReaderWriterClass::StartWriter(void){ ReaderWriterMonitor.MonitorEnter(); write_count++;if((write_count>1)||(reading_count>0)) { ReaderWriterMonitor.MonitorWait(wq, &w_count); } ReaderWriterMonitor.MonitorLeave();}3.4.4

利用管程解决读者-写者问

voidReaderWriterClass::FinishWriter(void){ReaderWriterMonitor.MonitorEnter();write_count--;if(write_count>0) { ReaderWriterMonitor.MonitorSignal(wq, &w_count); } else { ReaderWriterMonitor.MonitorSignal(rq, &r_count); }ReaderWriterMonitor.MonitorLeave();}3.4.4

利用管程解决读者-写者问

读者的活动：r_and_w.StartReader();读操作；r_and_w.FinishReader();写者的活动：r_and_w.StartWriter();写操作；r_and_w.FinishWriter();3.5

进程通信

3.5.1进程通信的类型3.5.2共享存储器系统3.5.3消息传递系统3.5.4管道通信3.5.1进程通信的类型

低级通信和高级通信低级通信：只能传递状态和整数值（控制信息），包括进程互斥和同步所采用的信号量和管程机制。优点是速度快。缺点是：传送信息量小：效率低，每次通信传递的信息量固定，若传递较多信息则需要进行多次通信。编程复杂：用户直接实现通信的细节，编程复杂，容易出错。高级通信：能够传送任意数量的数据，包括三类：共享存储器系统，消息传送系统和管道通信系统。3.5.1进程通信的类型

直接通信和间接通信直接通信：信息直接传递给接收方，如管道。在发送时，指定接收方的地址或标识，也可以指定多个接收方或广播式地址；在接收时，允许接收来自任意发送方的消息，并在读出消息的同时获取发送方的地址。间接通信：借助于收发双方进程之外的共享数据结构作为通信中转，如消息队列。通常收方和发方的数目可以是任意的。3.5.1进程通信的类型

高级通信的特征通信链路(communicationlink)：显式/隐式点对点/多点/广播单向/双向有容量（链路带缓冲区）/无容量（发送方和接收方需自备缓冲区）数据格式：字节流(bytestream)：各次发送之间的分界，在接收时不被保留，没有格式；报文(datagram/message)：各次发送之间的分界，在接收时被保留，通常有格式（如表示类型），定长/不定长报文，可靠报文/不可靠报文。收发操作的同步方式发送进程阻塞、接收进程阻塞发送进程不阻塞、接收进程阻塞发送进程不阻塞、接收进程不阻塞3.5.2

共享存储器系统

基于共享数据结构的通信方式在这种通信方式中，要求诸进程公用某个数据结构，进程通过它们交换信息。如在生产者-消费者问题中，就是把缓冲池（有界缓冲区）这种数据结构用来作通信的。这种通信方式是低效的，只适用传送少量的数据。基于共享存储区的通信方式

为了传送大量的数据，在存储器划分出一块共享存储区，各进程可以通过对共享存储区中的数据，进行读写来进行通信3.5.2

共享存储器系统

UNIX的共享存储区 共享存储区是UNIX系统V中通信速度最高的一种通信机制，它包含在进程通信软件包IPC中。创建或打开共享存储区(shmget)： 依据用户给出的整数值key，创建新区或打开现有区，返回一个共享存储区ID。连接共享存储区(shmat) 连接共享存储区到本进程的地址空间，可以指定虚拟地址或由系统分配，返回共享存储区首地址。父进程已连接的共享存储区可被fork创建的子进程继承。拆除共享存储区连接(shmdt) 拆除共享存储区与本进程地址空间的连接。共享存储区控制(shmctl) 对共享存储区进行控制。如：共享存储区的删除需要显式调用shmctl(shmid,IPC_RMID,0)；

3.5.2

共享存储器系统

进程A进程B

虚空间内存空间虚空间

A正文A数据

A栈

共享存储器

B正文

B数据

B栈3.5.2

共享存储器系统

UNIX的文件映射mmap：建立进程地址空间到文件或共享存储区对象的映射，将文件偏移off起的len字节映射到进程地址addr处

caddr_tmmap(caddr_taddr,size_tlen,intprot,intflags,intfildes,off_toff);munmap：拆除映射

intmunmap(void*addr,size_tlen);优点： 提高效率（消除不必要的数据拷贝）、 降低复杂性（直接读写操作而不必管理缓冲区）、 可直接将内存的数据类型记录在文件上（如指针）3.5.2

共享存储器系统

WindowsNT的文件映射采用文件映射(filemapping)机制：可以将整个文件映射为进程虚拟地址空间的一部分来加以访问。在CreateFileMapping和OpenFileMapping时可以指定对象名称。CreateFileMapping为指定文件创建一个文件映射对象，返回对象指针；OpenFileMapping打开一个命名的文件映射对象，返回对象指针；MapViewOfFile把文件映射到本进程的地址空间，返回映射地址空间的首地址；这时可利用首地址进行读写；FlushViewOfFile可把映射地址空间的内容写到物理文件中；UnmapViewOfFile拆除文件映射与本进程地址空间间映射关系；随后，可利用CloseHandle关闭文件映射对象；3.5.2

共享存储器系统

3.5.3

消息传递系统

消息传递系统分为直接通信方式和间接通信方式两种。直接通信方式

这是指发送进程利用OS提供的发送命令直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上。接收进程利用OS提供的接收命令直接从消息缓冲队列中取得消息。此时要求发送进程和接收进程都以显示的方式提供对方的标识符，通常系统提供下述两条通信原语：

Send(Receiver,message)；Receive(Sender,message)；或(Receive(message))；

直接通信的实例-消息缓冲队列通信机制。3.5.3

消息传递系统

消息缓冲队列通信机制，首先由美国的Hansan提出，并在RC4O00系统上实现，后来被广泛应用于本地进程之间的通信中。在这种通信机制中，发送进程利用send原语，将消息直接发送给接收进程；接收进程则利用Receive原语接收消息。消息缓冲队列通信机制中的数据结构消息缓冲区 在消息缓冲通信方式中，主要利用的数据结构是消息缓冲区。它可描述为：typemessagebuffer=record sender； 发送者进程标识符 size； 消息长度 text； 消息正文 next； 指向下一个消息缓区的指针 end3.5.3

消息传递系统

PCB中有关通信的数据项在利用消息缓冲队列通信机制时，在PCB中应增加的数据项可描述如下：typeprocesscontrolblock＝record ┊ mq； 消息队列队前指针 mutex； 消息队列互斥信号量 sm； 消息队列资源信号量

┊ end3.5.3

消息传递系统

发送原语procduresend（receiver,a）

begingetbuf(a.size,i);i.sender:=a.sender:i.size:=a.size;i.text:=a.text;i.next:=();getid(PCBset,receiver.j);wait(j.mutex);insert(j.mq,i);signal(j.mutex);signal(j.sm);end3.5.3

消息传递系统

接收原语procedurereceive(b)beginj:=internalname:wait(j.sm);wait(j.mutex);remove(j.mq,i);signal(j.mutex);b.sender:=i.sender:b.size:=i.size;b.text:=i.text:end3.5.3

消息传递系统3.5.3

消息传递系统.

mutexsmmq

………...send(B,a);sender:Asize:13text:Howareyou?Nextsend:Asize:13text:Howareyou?Next:sender:Asize:5text:HelloNext:

sender:Asize:13text:Howareyou?Next:0sender:Asize:5text:HelloNext:..receive(b);sender:Asize:5text:Hello 系统管理的－组缓冲区进程A进程BPCB进程B3.5.3

消息传递系统

UNIX系统消息机制 UNIX系统V的进程通信软件包IPC提供了消息机制。消息机制的数据结构

UNIX系统将消息分为消息首部和消息数据两部分。消息首部 在消息首部中记录有消息的类型、大小、指向消息数据区的指针、消息队列的链接指针等。消息队列头表 消息队列头表的每一表项是作为一个消息队列的消息头。在消息头中包含了指向消息队列中第一个消息的指针和指向最后一个消息指针，队列中消息的数目、队列中消息数据的总字节数等。3.5.3

消息传递系统

UNIX消息队列APImsgget依据用户给出的整数值key，创建新消息队列或打开现有消息队列，返回一个消息队列ID；msgsnd发送消息；msgrcv接收消息，可以指定消息类型；没有消息时，返回-1；msgctl对消息队列进行控制，如删除消息队列；3.5.3

消息传递系统

队列0..队列i消息首部msgh0消息缓冲区0消息首部msgh8消息缓冲区8消息首部msgh