发送进程和接收进程的同步问题

1、BUF1BUFnBUF2 .Pb Pa1 1 发送进程和接收进程的同步问题发送进程和接收进程的同步问题 利用信号量可以解决合作进程之间的同利用信号量可以解决合作进程之间的同步。步。 例：设进程例：设进程Pa,PbPa,Pb通过缓冲区队列传送数通过缓冲区队列传送数据据 经典的进程同步问题经典的进程同步问题 发送和接送过程满足的条件是发送和接送过程满足的条件是： 1)1)在在PaPa至少送一块数据入一个缓冲区之至少送一块数据入一个缓冲区之前前,Pb,Pb不可能从缓冲区中取出数据不可能从缓冲区中取出数据 2)Pa2)Pa往缓冲队列发送数据时往缓冲队列发送数据时, ,至少有一个至少有一个缓冲区是空的缓

2、冲区是空的; ; 3) 3)由由PaPa发送的数据块在缓冲队列中按先发送的数据块在缓冲队列中按先进先出进先出(FIFO)(FIFO)方式排列方式排列. . 描述发送过程描述发送过程deposit (data)deposit (data)和接受过和接受过程程remove (data) .remove (data) .BUF1BUFnBUF2 .Pb Pa 1)1)BufemptyBufempty进程进程PaPa的私用信号量的私用信号量, , BuffullBuffull 进程进程PbPb的私用信号量的私用信号量; ; 2)Bufempty 2)Bufempty的初始值为的初始值为n(n n(n

3、为缓冲队列的缓冲区为缓冲队列的缓冲区个数个数),Buffull),Buffull的初始值为的初始值为0;0; 发送过程发送过程Deposit(data),Deposit(data),接送过程接送过程Remove(data),Remove(data),这这两个过程必须同步，因为两个过程必须同步，因为, ,因为过程因为过程deposit(data)deposit(data)的的执行结果是过程执行结果是过程remove(data)remove(data)的执行条件的执行条件, ,而当缓冲而当缓冲队列全部装满数据时队列全部装满数据时,remove(data),remove(data)的执行结果又是的执

4、行结果又是deposit(data)deposit(data)的执行条件。的执行条件。 BUF1BUFnBUF2 .Pb Pa Pa:deposit(data) Pb:remove(data) begin local x begin local x P(Bufempty) P(Buffull) 按按FIFO方式选择一个方式选择一个 按按FIFO方式选择一个方式选择一个 空缓冲空缓冲Buf(x); 装满数据的缓冲装满数据的缓冲Buf(x) Buf(x)-data data-Buf(x) Buf(x)置满标记置满标记 Buf(x)置空标记置空标记 V(Buffull) V(Bufempty) en

5、d end发送过程发送过程deposit (data)deposit (data)和接受过程和接受过程remove (data)remove (data)123 . nP1P2P3 .Pn.C1C2C3.Cn Dijkstra Dijkstra把同步问题抽象成一种生产者和消把同步问题抽象成一种生产者和消费者关系，计算机系统中的许多问题都可以被归费者关系，计算机系统中的许多问题都可以被归结为生产者和消费者关系，例如，生产者可以是结为生产者和消费者关系，例如，生产者可以是计算进程，消费者是打印进程，输入时输入进程计算进程，消费者是打印进程，输入时输入进程是生产者，计算进程是消费者。我们可以通过一是

6、生产者，计算进程是消费者。我们可以通过一个缓冲区把生产者和消费者联系起来个缓冲区把生产者和消费者联系起来2 2 生产者消费者生产者消费者的同步问题的同步问题(The Proceducer-(The Proceducer-Consumer Problem)Consumer Problem)举例：举例： 生产者把产品生产出来，送入仓库。给生产者把产品生产出来，送入仓库。给消费者发信号，消费者得到信号后，到仓库消费者发信号，消费者得到信号后，到仓库取产品，取走产品后给生产者发信号取产品，取走产品后给生产者发信号产品仓 库一个生产者一个消费者经典的进程同步问题经典的进程同步问题n生产者消费者问题是相互

7、合作进程关系的一种抽象n输入计算打印 生产者 消费者 生产者 消费者系统中使用资源的进程消费者系统中释放资源同类资源的进程生产者产品仓 库一个生产者一个消费者 1 想接收数据时，有界缓冲区中至少有一个单元是满的想接收数据时，有界缓冲区中至少有一个单元是满的 2 生产者想发送数据时，有界缓冲区中至少有一个单元是空的生产者想发送数据时，有界缓冲区中至少有一个单元是空的同步问题同步问题由于缓冲区是临界资源，所以生产者和消费者之间必须互斥的访问临界资源用信号量解题的关键步骤： 信号量的设置； 给信号量赋初值（常用的互斥和同步信号量值的大小）； P、V操作安排的位置（其中，P的顺序不能颠倒，V的顺序任意

8、） 要解决进程的同步问题要满足的条件要解决进程的同步问题要满足的条件设：公用信号量 mutex 表示缓冲区的个数 初值为1（消费者）私用信号量 full 表示有界缓冲区中非空单元数 初值为0 （生产者）私用信号量 avail 表示有界缓冲区中空的单元数 初值为ndeposit（data）： begin P(avail) 检查缓冲区中是否有空单元 执行后n-1 P(mutex) 检查缓冲区是否可用 执行后 mutex0 送数据入缓冲区 V(full) 执行后，非空单元数加1 0+11 V(mutex) 释放缓冲区中的资源 endRemove（data）： begin P(full) 检查缓冲区是

9、否有数据 P(mutex) 访问缓冲区 取缓冲区中某单元数据 V(avail) 取走数据以后，有界缓冲区的空单元个数加1 V(mutex) 释放缓冲区 end deposit（data）： begin P(avail) P(mutex) 送数据入缓冲区 V(full) V(mutex) endRemove（data）： begin P(full) P(mutex) 取缓冲区中某单元数据 V(avail) V(mutex) end 公用信号量公用信号量, ,互斥时使用的信互斥时使用的信号量号量（二元信号量）：它仅允（二元信号量）：它仅允许取值为许取值为“”与与“”，用，用作互斥。它联系着一组共行

10、进作互斥。它联系着一组共行进程，初值为，每个进程均可程，初值为，每个进程均可对之施加、操作。对之施加、操作。 私用信号量：私用信号量：一般信号量一般信号量（资（资源信号量）：它联系着一组共源信号量）：它联系着一组共行进程，但其初值为，或为行进程，但其初值为，或为某个正整数，表示资源的数某个正整数，表示资源的数目，主要用于进程同步。目，主要用于进程同步。只允只允许拥有它的许拥有它的进程对之施加操进程对之施加操作，对作，对V操作没有限制操作没有限制 次序次序 次序次序（消费者）私用信号量 full 表示有界缓冲区中非空单元数 初值为0 （生产者）私用信号量 avail 表示有界缓冲区中空的单元数

11、初值为n几个经典的进程同步问题v生产者消费者问题v哲学家进餐问题v读者写者问题v图书馆阅览室问题v理发师问题 v吃水果问题v司机售票员问题v过河问题生产者消费者问题一个最著名的进程同步问题问题描述：一组生产者向一组消费者提供消息，它们共享一个有界缓冲池，生产者存入消息，消费者从中取得消息。 哲学家进餐问题n哲学家进餐问题是典型的同步问题，是由Dijkstra提出并解决的。n问题描述5个哲学家，他们的生活方式是交替的思考和进餐。哲学家们公用一张圆桌，分别坐在周围的5张椅子上，圆桌上有5个碗和5支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有他拿到两只筷子时才能进餐，放

12、下筷子又继续思考。例：例：利用信号量解决读者和写者问题利用信号量解决读者和写者问题 一个文件可能被多个进程共享，为了一个文件可能被多个进程共享，为了保证读写的正确性和文件的一致性，系统保证读写的正确性和文件的一致性，系统要求，当有读者进程读文件时，不允许任要求，当有读者进程读文件时，不允许任何写者进程写，但允许多读者同时读；当何写者进程写，但允许多读者同时读；当有写者进程写时，不允许任何其它写者进有写者进程写时，不允许任何其它写者进程写，也不允许任何读者进行读。程写，也不允许任何读者进行读。n为了解决读者和写者问题，需设置两个信为了解决读者和写者问题，需设置两个信号量：号量：n（1 1）读互斥

13、信号量）读互斥信号量rmutex,rmutex,用于使读者互用于使读者互斥地访问共享变量斥地访问共享变量readcount,readcount,这里这里readcountreadcount是记录有多少读者正在读是记录有多少读者正在读; ; n（2 2）写互斥信号量）写互斥信号量wmutex,wmutex,用于实现读写用于实现读写互斥。读者互斥。读者者问题进行如下描述：者问题进行如下描述：struct semapore rmutex,wmutexstruct semapore rmutex,wmutex=1,1;=1,1;int readcountint readcount:=0;:=0;cob

14、egincobeginvord readeri(vordvord readeri(vord)(i=1,2,)(i=1,2,k)k) while(true) while(true) p(rmutex p(rmutex) )； ifif readcount=0 then readcount=0 then p(wmutex p(wmutex); ); readcount:=readcount readcount:=readcount+1; +1; v(rmutex); v(rmutex); 读文件；读文件； p(rmutex p(rmutex) )； readcount:=readcount-1;r

15、eadcount:=readcount-1;ifif readcount=0 then readcount=0 thenv(wmutex);v(wmutex);v(rmutex);v(rmutex); vord writerj(vordvord writerj(vord)(j=1,2,)(j=1,2,m),m) while(true) while(true) p (wmutex p (wmutex);); 写文件；写文件； v(wmutex v(wmutex) )； CoendCoend 课后练习课后练习 图书馆阅览室问题问题描述：假定阅览室最多可同时容纳100个人阅读，读者进入时，必须在阅览室门口的一个登记表上登记，内容包括姓名、座号等，离开时要撤掉登记内容。用P、V操作描述读者进程的同步算法。 理发师问题问题描述：一个理发店由一个有几张椅子的等候室和一个放有一张理发椅的理发室组成。若没有要理发的顾客，则理发师就去睡觉；若一顾客走进理发店且所有的椅子都被占用了，则该顾客就离开理发店；若理发师正在为人理发，则该顾客就找一张空椅子坐下等待；若理发师在睡觉，则顾客就唤醒他，设计一个协调理发师和顾客的程序。 吃水果问题n问题描述：桌上有一只盘子，每次只能放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放桔子，儿子专等吃盘里的桔子，女儿专等吃盘里的苹果。只要盘子空，