(3)--第3章 同步与通信操作系统原理.ppt

《(3)--第3章 同步与通信操作系统原理.ppt》由会员分享，可在线阅读，更多相关《(3)--第3章 同步与通信操作系统原理.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、本章目录3.1进程的同步与互斥3.2经典进程同步问题3.3管程3.4进程通信3.1 进程的同步与互斥3.1.1基本概念3.1.2硬件同步机制3.1.3信号量机制3.1.1 基本概念 1.临界资源凡是以互斥方式使用的共享资源都称为临界资源（Critical Resource）。临界资源具有一次只允许一个进程使用的属性。例如，计算机的许多硬件资源都被处理成临界资源，如打印机、磁带机等。如果打印机允许若干用户同时打印，那么打印结果会混淆在一起，不易分辨，给用户带来许多不便。系统中还有许多软资源，如内存中的公共数据结构、共享变量、表格、队列、栈等也被处理成临界资源，以避免多个进程对其访问时出现问题。3

2、.1.1 基本概念 2.临界区每个进程中，访问临界资源的那段代码称为临界区（Critical Section），简称CS。如果能保证各进程互斥地进入自己的临界区，便可实现各进程对临界资源的互斥访问。把申请进入临界区的那段代码称为进入区，如果可以进入，则设置“正在访问”标志。相应地，在临界区之后，用于退出对临界区访问的那段代码称为退出区，此时将临界区的标志恢复为“未被访问”。进程中，除上述进入区、临界区及退出区之外的那部分代码称为剩余区。3.1.1 基本概念 3.互斥准则（1）空闲让进。当没有进程在临界区时，任何需要进入临界区的进程都允许立即进入。（2）忙则等待。在共享同一对象的所有进程中，一次

3、只能有一个进程进入临界区。其它要求进入临界区的进程只能等待。（3）有限等待。任何一个进程经有限时间等待后都能进入临界区，以免陷入“死等”状态。（4）让权等待。当一个进程不能进入临界区时要立即阻塞自己，释放处理机让其它进程使用，避免“忙等”。3.1.2 硬件同步机制1.测试与设置指令booleanTest_and_Set(inti)if（i=0）i=1;returntrue;elsereturnfalse;3.1.2 硬件同步机制设lock为全局变量，初始值为0，表示无人进入。利用Test_and_Set指令，即可实现对临界区的加锁与解锁。dowhile(!Test_and_Set(lock)d

4、oskip;/循环等待；entrysectioncriticalsection;lock=false;/exitsectionremaindersection;while(true);3.1.2 硬件同步机制2.交换指令voidExchange（intregister,intmemory）inttemp；temp=memory；memory=register；register=temp；3.1.2 硬件同步机制设lock为全局变量（初值为0，表示无人进入），每个进程设一个局部变量key。利用Exchange指令，可实现对临界区的加锁与解锁。dointkey=1;while(key=1)Exch

5、ange(key,lock);criticalsection;Exchange(key,lock)remainersection;while(true);3.1.2 硬件同步机制3.机器指令方法的优缺点使用专门的机器指令实施互斥有以下优点：（1）适用于在单处理机或共享内存的多处理机上的任何数目的进程。（2）非常简单且易于证明。（3）可用于支持多临界区，每个临界区可以用其自己的变量定义。同样也存在一些严重的缺点：（1）使用了忙等待。（2）可能饥饿。（3）可能死锁。3.1.3 信号量机制著名的荷兰计算机学者Dijkstra经过长期的操作系统研究与设计，于1965年提出了一种同步机制信号量机制。该机

6、制由一个称为信号量（Semaphore，也译为“信号灯”）的特殊变量和两个被命名为P、V操作的原语（分别对应wait（）和signal（）组成。1.整型信号量最初由Dijkstra把信号量定义为一个整型量，代表资源数目或可同时使用该资源的进程个数。信号量的初值为非负数，除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问和修改。wait（S）和signal（S）操作可描述为：semaphoreS；wait(S):whileS0donoopS=S1;signal(S):S=S+1;在该信号量机制的wait操作中，只要信号量S0，就会不断地测试，直到S0。因此，该机制并未

7、遵循“让权等待”的准则，而是使进程一直处于“忙等”状态。2.记录型信号量该信号量机制，是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量count外，还应增加一个进程链表指针queue，用于链接上述所有等待进程。此信号量定义如下：typedefstructintcount；queueType*queue；semaphore；2.记录型信号量wait（S）操作可描述为：semaphoreS；voidwait(S)S.count；if(S.count0)block(S.qu

8、eue)；/阻塞该进程链接到S.queue队列；signal（S）操作可描述为：voidsignal(S)S.count+；if(S.count=0)wakeup(S.queue);3.信号量的使用（1）用于实现互斥：例如，用于n个进程的临界区之间互斥，设n个进程共享一个信号量mutex，初值为1。为了实现进程互斥地进入临界区，只需把临界区CS置于wait(mutex)和signal(mutex)之间。任一进程Pi的框架为：voidPi（）semaphoremutex=1；/信号量初值为1；dowait(mutex);criticalsection;signal(mutex);remainde

9、rsection;while(true);3.信号量的使用（2）用于实现同步：例如，有两个并发进程P1、P2，共享一个公共信号量s，初值为0。P1执行的程序中有一条S1语句，P2执行的程序中有一条S2语句。而且，只有当P1执行完S1语句后，P2才能开始执行S2语句。对这种简单的同步问题，可以很容易地用信号量机制解决。进程间的同步控制描述如下：semaphoreS=0；/信号量初值为0；进程P1程序框架如下：voidP1（）S1;signal（S）;voidmain（）parbegin（P1(),P2()）;进程P2程序框架如下：voidP2（）wait（S）;S2;3.2 经典进程同步问题3.

10、2.1生产者消费者问题3.2.2读者写者问题3.2.3哲学家就餐问题3.2.1 生产者-消费者问题生产者消费者(producerconsumer)问题是一个著名的进程同步问题。它描述的是：有若干生产者进程，假设k（k0）个，在生产产品，并将这些产品提供给m（m0）个消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池（假设组织成环形），生产者进程将它所生产的产品放入缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步。假定它们的约束条件是：（1）当缓冲池中有空缓冲区时，允许

11、任一生产者进程把它的产品放入。（2）当缓冲池中无空缓冲区时，则试图将产品放入缓冲池的任何生产者进程必须等待。（3）当缓冲池中有产品时，允许任一个消费者进程把其中的一个产品取走消费。（4）当缓冲池中没有产品时，试图从该池内取出产品的任何消费者进程必须等待。3.2.1 生产者-消费者问题对所有生产者和消费者进程来说，把缓冲池看成一个整体，因此缓冲池是临界资源，即任何一个进程在对池中某个缓冲区进行“放”或“取”操作时须和其他进程互斥执行。首先定义信号量如下：（1）信号量mutex，初值为1，用于控制互斥地访问缓冲池。（2）信号量full，初值为0，用于资源计数。full值表示当前缓冲池中“满”缓冲区

12、的个数。（3）信号量empty，初值为n，用于资源计数。empty值表示当前缓冲池中“空”缓冲区的个数。3.2.1 生产者-消费者问题/*programproducerconsumer*/constintn；/buffersizeintin，out=0/缓冲区首空、首满指针semaphoreempty=n;full=0;mutex=1；voidproducer()while(true)生产一个产品；wait(empty);wait(mutex);将产品放入缓冲区；in=(in+1)%n;signal(mutex);signal(full);3.2.1 生产者-消费者问题voidconsumer

13、()while(ture)wait(full);wait(mutex);从缓冲区中取产品；out=(out+1)%n;signal(mutex);signal(empty);消费该产品；voidmain()parbegin(producer(),consumer();3.2.2 读者-写者问题读者写者问题描述如下：有一个数据区（数据区可以是一个文件、一块内存空间或一组寄存器）被多个用户共享，其中一部分用户是读者，另一部分是写者。我们规定：读者对数据区是只读的，而且允许多个读者同时读；写者对数据区是只写的，当一个写者正在向数据区写信息的时候，不允许其他用户使用，无论是读者还是写者。即保证一个写者

14、进程必须与其他进程互斥地访问共享对象。也就是说，解决该问题必须满足的条件如下：（1）任意多个读者可以同时读；（2）任一时刻只能有一个写者可以写；（3）如果写者正在写，那么读者就不能读。3.2.2 读者-写者问题读者优先的解决方案：首先，使用一个互斥信号量wmutex，实现读者与写者、写者与写者之间的互斥。由于读者可以同时访问数据区，因此我们让第一个准备进入临界区的读者，通过wait（wmutex）强占临界资源，以便排斥写者访问。当最后一个读者离开临界区时，通过signal（wmutex）将临界资源释放，以便其它用户使用。其次，设计一个专为读者共享的变量readcounter，用来记录读数据区的

15、人数。readcounter应视为临界资源，故应有一个互斥信号量，定义为rmutex。3.2.2 读者-写者问题读者优先/*programreadersandwriters*/intreadcounter;semaphorewmutex=1;semaphorermutex=1;/对readcounter的互斥访问voidreader()while(true)wait(rmutex);readcounter+;if(readcounter=1)wait(wmutex);signal(rmutex);readunit();wait(rmutex);readcounter；if(readcount=

16、0)signal(wmutex);signal(rmutex);3.2.2 读者-写者问题读者优先voidwriter()while(true)wait(wmutex);writeunit();signal(wmutex);voidmain()readcounter=0;parbegin(reader(),writer();3.2.2 读者-写者问题写者优先/*programreadersandwriters*/intreadcount,writecount;semaphorex=1,y=1,z=1,wsem=1,rsem=1;voidreader()while(true)wait(z);wa

17、it(rsem);wait(x);readcount+;if(readcount=1)wait(wsem)；signal(x);signal(rsem);signal(z);readunit();wait(x);readcount;if(readcount=0)signal(wsem)；signal(x);3.2.2 读者-写者问题写者优先voidwriter()while(true)wait(y);writecount+;if(writecount=1)wait(rsem);signal(y);wait(wsem);writeunit();signal(wsem);wait(y);write

18、count;if(writecount=0)signal(rsem);signal(y);voidmain()readcount=writecount=0;parbegin(reader(),writer();3.2.3 哲学家就餐问题Dijkstra于1965年首先提出并解决了哲学家就餐问题，该问题也是大量并发控制问题中的一个典型例子。有5位哲学家，他们倾注毕生精力用于思考问题和吃饭。设想他们共同坐在一张放有5把椅子的餐桌前用餐，用餐过后开始思考问题。他们的生活方式可描述为一个单调的循环：思考饥饿用餐再思考。已知餐桌上摆的是面条，桌上放着五根筷子，任意两个哲学家之间有一根，如图32所示。哲学

19、家在思考问题时，并不影响他人。只有当哲学家饥饿的时候，他才试图拿起左、右筷子（一根一根地拿起）。如果筷子已在他人手中，则需等待。饥饿的哲学家只有左右手各拿到一根筷子才可以开始进餐。而且，也只有当他吃完饭后才放下筷子，重新开始思考问题。3.2.3 哲学家就餐问题显然，筷子是一种临界资源。设i号筷子的互斥信号量为chopsticki(i=0,1,2,3,4），初值均为1。3.2.3 哲学家就餐问题semaphorechopstick5=1,1,1,1,1;inti;voidPhilosophers(inti)while(true)think();wait(chopsticki);wait(chop

20、stick(i+1)mod5);eat();signal(chopsticki);signal(chopstick(i+1)mod5);voidmain()parbegin(Philosophers(0),Philosophers(1),Philosopher(2),Philosopher(3),Philosopher(4);3.2.3 哲学家就餐问题显然，上述解决方案可保证不会有两个相邻的哲学家同时进餐，但有可能引起死锁。假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0；当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待。对于这样的死锁问题，可

21、采取如下两种解决方法：（1）规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，0、1号哲学家竞争1号筷子；2、3号哲学家竞争3号筷子。（2）至多有4个哲学家同时拿筷子。3.2.3 哲学家就餐问题解决方法1voidPhilosophers(inti)while(true)think();if(i%2=0)wait(chopsticki);wait(chopstick(i+1)mod5);elsewait(chopstick(i+1)mod5);wait(chopsticki);eat();signal(chopsticki);signal(chopstick

22、(i+1)mod5);3.2.3 哲学家就餐问题解决方法2inti;semaphorechopstick5=1,1,1,1,1;semaphoreroom=4;/用于控制同时进餐的哲学家位数 voidPhilosophers(inti)while(true)think();wait(room);wait(chopsticki);wait(chopstick(i+1)mod5);eat();signal(chopsticki);signal(chopstick(i+1)mod5);signal(room);voidmain()parbegin(Philosophers(0),Philosophe

23、rs(1),Philosopher(2),Philosopher(3),Philosopher(4);3.3 管程3.3.1管程的基本概念3.3.2用管程解决生产者消费者问题3.3.1 管程的基本概念1.管程的引入信号量机制是一种既方便又有效的进程同步机制，但采用信号量机制来编写并发程序，对临界区的执行会分散在各个进程中，其缺点如下：（1）易读性差。因为要了解对于一组共享变量及信号量的操作是否正确，就必须通读整个系统或者并发程序。（2）不利于修改和维护。因为程序的局部性很差，所以任一组变量或一段代码的修改都可能影响大局。（3）正确性难以保证。因为操作系统或并发程序通常很大，要保证这样一个复杂的

24、系统没有逻辑错误是很难的。这不仅给系统的管理带来了麻烦，而且还会因同步操作的使用不当而导致系统死锁。为了解决这一问题，著名学者Hoare于1974年提出了一种具有面向对象程序设计思想的同步机制管程。3.3.1 管程的基本概念2.管程的概念 管程是一种并发性的结构，是由一个或多个过程、一个初始化序列和局部数据组成的软件模块。如图33所示，其主要由4部分组成：（1）管程名；（2）局部于管程的共享变量说明；（3）对该数据结构进行操作的一组过程/函数；（4）对局部于管程的数据设置初始值的语句。图3-3 管程的示意图一组操作过程初始化代码条件(不忙)队列共享数据进入队列3.3.1 管程的基本概念管程最主

25、要的特点如下：（1）只能通过管程中的过程而不能用其他外部过程访问其局部数据变量。（2）进程通过调用管程的过程而进入管程。（3）每一时刻只能有一个进程在管程中执行，任何其他调用管程的进程将被挂起直至管程可用为止。3.3.1 管程的基本概念3.条件变量管程在任一时刻只允许一个进程调用，这样就具有实现互斥的能力，任一时刻管程中的局部数据也只能被一个进程访问。因此，一个共享的数据结构可以放在管程中加以保护，如果管程中的数据代表某种资源，那么管程就支持对这种资源访问的互斥。为了将管程用于并发进程中，管程必须拥有同步手段。例如，假设一个进程调用了管程，当它在执行过程中发现条件不满足时，应将该进程阻塞。这就

26、需要一种机制，使得该进程不仅被阻塞，而且能释放这个管程，以便其它进程可以进入。以后，当条件满足并且管程再次可用时，需要恢复该进程并允许它在中断点重新进入管程。为了区分阻塞的原因，引入了局部于管程的条件变量，即condtionc。3.3.1 管程的基本概念3.条件变量管程在任一时刻只允许一个进程调用，这样就具有实现互斥的能力，任一时刻管程中的局部数据也只能被一个进程访问。因此，一个共享的数据结构可以放在管程中加以保护，如果管程中的数据代表某种资源，那么管程就支持对这种资源访问的互斥。为了将管程用于并发进程中，管程必须拥有同步手段。例如，假设一个进程调用了管程，当它在执行过程中发现条件不满足时，应

27、将该进程阻塞。这就需要一种机制，使得该进程不仅被阻塞，而且能释放这个管程，以便其它进程可以进入。以后，当条件满足并且管程再次可用时，需要恢复该进程并允许它在中断点重新进入管程。为了区分阻塞的原因，引入了局部于管程的条件变量，即condtionc。3.3.1 管程的基本概念3.条件变量管程可使用条件变量支持同步，这些变量保存在管程中并且只能在管程内部访问。用以下两个原语操作条件变量。c.wait()：用来将执行进程排在与条件变量c相应的等待队列上。c.signal()：用来唤醒与c相应的等待队列上的一个进程。若没有等待进程，则c.signal()不起任何作用，什么都不做。3.3.2 用管程解决生

28、产者-消费者问题在利用管程方法来解决生产者消费者问题时，首先便是为它们建立一个管程，并命名为ProducerConsumer,简称为PC。（1）管程中有两个条件变量：notfull：缓冲区未全满即缓冲区中还有空位置时，变量值为true；notempty：缓冲区未全空即缓冲区中至少有一个产品存在，则变量值为true。（2）为该管程定义两个函数（假设缓冲区中的产品是字符）：放产品：append(charx)取产品：take(charx)3.3.2 用管程解决生产者-消费者问题/*programproducerconsumer*/monitorPC;/管程名charbufferN;intnextin

29、,nextout;intcount;/局部变量condtionnotfull,notempty;/条件变量voidappend(charx)if(count=N)notfull.wait();buffernextin=x;nextin=(nextin+1)%N;count+;notempty.signal();voidtake(charx)if(count=0)notempty.wait();x=buffernextout;nextout=(nextout+1)%N;count;notfull.signal();3.3.2 用管程解决生产者-消费者问题nextin=0;nextout=0;co

30、unt=0;/局部变量初始化voidproducer()charx;while(true)produce(x);append(x);voidconsumer()charx;while(true)take(x);consume(x);voidmain()parbegin(producer(),consumer();3.4 进程通信3.4.1共享存储器系统3.4.2管道通信系统3.4.3消息传递系统3.4.1 共享存储器系统共享存储器系统（SharedMemorySystem）需要在内存中开辟一个共享的存储空间，供进程之间进行数据传递。两个需要互相交换信息的进程通过对同一共享数据区（sharedm

31、emory）的操作来达到互相通信的目的，而这个共享数据区是每个互相通信进程的一个组成部分。3.4.2 管道通信系统所谓“管道”，是指用于连接一个读进程和一个写进程以实现他们之间数据通信的一个共享文件，又名pipe文件。又由于写进程和读进程是利用管道进行通信的，所以这种通信方式被称为管道通信。在该方式中，向管道提供输入的发送进程(即写进程)，以字符流的形式将大量的数据写入管道；而接收管道输出的接收进程(即读进程)，则从管道中读取数据。最简单的一种管道，可能是批处理命令中使用管道符号“|”建立的那种。例如：who|sortwho的输出数据经管道传递给sort作为输入。这样，一个管道连接了两个命令，

32、形成了一个管道行，数据流从左向右呈单向流动。3.4.3 消息传递系统不论是单机系统、多机系统，还是计算机网络，消息传递机制都是用得最广泛的一种进程间通信机制。在消息传递系统中，进程间的数据交换是以格式化的消息(message)为单位的；在计算机网络中，message又称为报文。消息传递中的管理机制由操作系统提供，程序员可以直接利用系统提供的一组通信原语进行通信。主要有以下两个原语：发送原语：send(destination,message)，其中，destination为消息的目的地（接收进程名）。该原语表示发送消息到进程destination。接收原语：receive(source,mess

33、age)，其中，source是消息发出地（发送进程名）。该原语表示从进程source接收消息。1.直接通信方式这是指发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。此时，要求发送进程和接收进程都以显式方式提供对方的标识符。通常，系统提供下述两条通信命令(原语)：Send(Receiver,message);发送一个消息给接收进程；Receive(Sender,message);接收Sender发来的消息；利用直接通信原语解决生产者-消费者问题可以利用直接通信原语，来解决生产者消费者问题。当生产者生产出一个产品(消息)后，便用Send原语将消息发送给消费者进程；而消费者进程则利用Re

34、ceive原语来得到一个消息。如果消息尚未生产出来，消费者必须等待，直至生产者进程将消息发送过来。生产者消费者的通信过程可分别描述如下：voidproducer()doproduceaniteminnextp；send(consumer,nextp)；while(true);voidconsumer()doreceive(producer,nextc);consumetheiteminnextc;while(true);2.间接通信方式该方式指的是进程间的通信，需要通过共享的数据结构作为中间实体来暂存发送进程发送给目标进程的消息。该中间实体称为信箱，接收进程从中取出对方发送给自己的消息。消息可

35、以在信箱中安全地保存，所以利用信箱既可实现实时通信，也可实现非实时通信。系统提供了若干条原语用于信箱通信，如下所示：（1）信箱的创建和撤消。（2）消息的发送和接收。Send(mailbox,message)：将一个消息发送到指定信箱；Receive(mailbox,message)：从指定信箱中接收一个消息；具体可以使用两个信箱producemail、consumemail，信箱中的消息组织成消息队列，容量由全局变量capacity决定。produceemail中存放空消息（可以理解为放产品的空位置），能取到空消息，则表示生产者可以生产，每生产一个产品，里面的空消息（空位置）数减1。信箱pro

36、ducemail最初填满了空消息（空位置），其数量等于信箱的容量。consumemail中存放消息(产品)，有消息(产品)，则表示消费者能消费，每消费一个产品，里面的消息（产品）数就减1。consumemail中最初没有消息（产品）。利用信箱解决生产者-消费者问题生产者：从producemail中接收空消息。若接收到，则生产产品（消息），并将它发送到信箱consumemail中。每生产一次，mayproduce中空消息就减少一个。消费者：从consumemail中接收消息。有消息，说明能消费，取走消息消费后，发送空消息到信箱producemail中。生产者消费者的通信过程可分别描述如下：con

37、stintcapacity=/*bufferingcapacity*/null=/*emptymessage*/inti;voidproducer()messagepmsg;while(true)receive(producemail,null);pmsg=produce();send(consumemail,pmsg);利用信箱解决生产者-消费者问题voidconsumer()messagecmsg;while(true)receive(consumemail,cmsg);consume(cmsg);send(producemail,null);voidmain()create_mailbo

38、x(producemail);create_mailbox(consumemail);for(inti=1;i=capacity;i+)send(producemail,null)parbegin(producer(),consumer();利用信箱解决生产者-消费者问题3.消息缓冲队列通信示例消息缓冲队列通信机制是由Hansen在1973年提出的一种进程通信方式，如图35所示。其基本思想是：当发送进程要发送消息时，先根据发送的消息长度来向系统申请一个消息缓冲区，接着把发送的消息写入到消息缓冲区中。然后将其挂在接收进程PCB所指示的消息队列的队尾。接收进程在适当的时候从其消息队列中摘下消息缓冲

39、区，读取消息，然后再将缓冲区作为空闲缓冲区归还给系统。3.消息缓冲队列通信示例（1）消息缓冲队列通信机制中的数据结构消息缓冲区structmessage intsender;/发送者进程标识符inttype;/消息类型intsize;/消息长度char*text/消息正文（含接收者标识符）structmessage*next/指向消息队列中下一个消息缓冲区的指针;3.消息缓冲队列通信示例PCB结构中有关进程同步的信息利用消息缓冲队列通信机制时，在设置消息缓冲队列的同时，还应增加用于对消息队列进行操作和实现同步的信号量，并将它们记录在进程的PCB中，如下所示：structPCBstructmes

40、sage*head;/指向该进程接收到的消息队列队首指针semaphoremutex;/消息队列是临界资源，该信号量用于它的互斥semaphoremnum；/同步信号量，其值表示消息队列中的消息数;3.消息缓冲队列通信示例（2）利用通信原语进行通信发送原语voidsend(Q,m)根据消息m的长度size向系统申请一个消息缓冲区；找到接收进程的PCB；wait(mutex);将准备发送的消息m复制到新申请的消息缓冲区；将消息缓冲区挂在接收进程消息队列的队尾；signal(mutex);signal(mnum);接收原语voidreceive(n)wait(mnum);wait(mutex);从

41、head指向的消息队列中摘下第一个消息缓冲区；将消息缓冲区中的信息n取出;释放消息缓冲区；signal(mutex);3.消息缓冲队列通信示例小结现代操作系统的中心问题是多道程序设计，而实现多道程序设计的基础是并发。并发执行的多个进程间免不了形成各种各样的关系，最具代表性的关系就是同步和互斥。同步是指进程之间通过在执行时序上的某种限制而达到相互合作的约束关系，是一种直接制约关系。互斥是指进程之间彼此本无关，但是由于竞争使用同一共享资源而产生相互制约的关系，是一种间接制约关系。实现进程的同步和互斥可以使用P、V操作。本章通过三个典型例子生产者消费者问题、读者写者问题及哲学家就餐问题进行了讨论。进程之间要进行大量数据的通信，可以采取共享存储器通信、管道通信和消息传递通信的方式。