进程同步问题分析--生产者和消费者问题
一、 讨论课名称：
计算机操作系统中进程同步与互斥问题分析
二、 讨论课目的：
1．熟悉临界资源、信号量及PV操作的定义与物理意义；
2．掌握进程互斥与进程同步的相关知识；
3．掌握用信号量机制解决进程之间的同步与互斥问题；
4．实现生产者－消费者问题，深刻理解进程同步问题。
三、讨论课内容：
1．进程同步的基本概念
在多道程序环境下，系统中可能存在许多的进程，在这些进程之间必定存在一些制约关系，这种制约关系表现为以下两种形式：
①资源共享关系。进程之间不知道其他进程的存在，而这些进程又处在同一个系统中，对系统资源必须共享使用，而有些资源不允许进程同时访问，例如打印机。系统只能保证进程间互斥地使用这种临界资源，称这种资源共享关系叫做互斥；
②相互合作关系。在某些进程间还存在一种相互合作的关系。例如在某个系统中存在两个进程，输入进程A和计算进程B，A负责向B提供数据，当缓冲区空时，B进程因不能获得所需数据而等待。当A把数据送入缓冲区后，并向B发送一个信号将B唤醒，B才能取走数据。同样，当B没有提取数据，也就是说缓冲区满时，进程A也无法向其中投入数据而等待。这就是一种相互合作关系，称之为进程间的同步关系。
2．信号量机制实现进程同步
本文分析的生产者-消费者问题就是一种相互合作问题的代表，对进程同步问题的解决，早在1965年，荷兰科学家Dijkstra就提出信号量机制是一种卓有成效的进程同步工具。
在信号量机制中，信号量仅能通过两个标准的原子操作wait（s）和singnal（s）来访问。这两个操作被称为P,V操作。
在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述为：
type semaphore=record
value:integer;
L:list of process;
End
相应地，wait（s）和singal（s）操作可描述为：
Procedure wait（s）
var s:semaphore;
Begin
S.value:=S.value-1;
If S.value
End
Procedure signal(s)
var S:semaphore;
BeginS.value:=S.value+1;
If S.value
End
每次的wait操作，意味着进程请求一个单位的资源，因此描述为S.value:=S.value-1;当S.value
3.利用信号量解决生产者—消费者问题
3.1一个buffer，一个生产者，一个消费者
（1）规则
只有buffer为空才能生产者才能进行put操作，只有buffer有数据消费者才能进行get操作。利用信号量机制实现消费者和生产者的协同工作，其中信号量s1代表的缓冲区这种资源，初值为1，代表有1个buffer。s2代表buffer是否有数据，初值为0，所以也称这种信号量叫做资源信号量。
（2）实现流程
p（s1）"判断buffer是否为空"
put放入数据
v（s2）"设置buffer有数据的标志，给消费者发一个有数据的信号"
p（s2）"判断buffer是否有数据"
get取走数据
v（s1）"设置buffer为空标志"
3.2一个buffer，多个生产者，多个消费者
（1）规则
只有buffer为空才能put；只有buffer中有数据才能get;不允许多个put操作同时进行；不允许多个get操作同时进行。这时buffer变成了临界资源，消费者之间需要互斥地使用，生产者之间也需要互斥地使用，消费者和生产者之间也需要互斥地使用，这时设置两个信号量s1，s2实现同步，例外设置S信号，代表buffer这种临界资源，用于互斥，称之为互斥信号量。
（2）实现流程
p（s1）"判断buffer是否空"
p（s）"是否可进行put，是否有其他进程占用buffer"
put
v（s）"释放buffer，让其他进程可以使用"
v（s2）"给消费者进程释放一个buffer中有数据的信号"
p（s2）"判断是否有数据"
p（s）"是否可进行get，是否有其他进程占用"
get
v（s）"释放buffer，让其他进程可以使用"
v（s1）"给生产者释放一个buffer为空的信号"
通过3个信号量，实现了消费者和生产者之间同步关系，也保证了在某个时刻只有一个进程使用临界资源buffer。
3.3多个生产者，多个消费者，N个buffer
（1）规则
任一时刻只允许一个进程操作buffer。在生产者和消费者之间的公共缓冲池中，有n个缓冲区，可利用互斥信号量spg使诸进程实现对缓冲池的互斥使用。利用资源信号量s1,s2分别代表缓冲池中的空缓冲区的数量，假定只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲区为空，消费者便可从缓冲池中取走一个数据。
（2）实现流程
Var spg,s1.s2;semaphore:1,n,0;
｛p（s1）;
p（spg）;
put
v（spg）;
v（s2）;｝
｛p（s2）;
p（spg）;
get
v（spg）;
v（s1）;｝
在生产者-消费者问题中应注意：
（1）在每个程序中用于实现互斥的wait（spg）和signal（spg）必须成对出现。
（2）对资源信号量s1和s2的p和v操作，同样需要成对地出现，但它们是分别处于不同的程序中。
（3）在每个程序中的多个p操作顺序不能颠倒。应先执行对资源信号量的p操作，然后在执行对互斥信号量的p操作，否则可能引起进程死锁。
四、讨论课总结
计算机操作系统中引入了进程后，极大地改善了系统资源的利用率和提高了系统的吞吐量，但是由于多道环境中同时存在多个进程，它们共享系统资源，各自按照各自的方式运行，给系统造成了混乱，所以系统必须提供一种机制管理进程，使这些并发执行的进程之间能有条不紊地运行，能有效地共享资源和相互合作，使得程序的执行具
有可再现性，这就是进程同步的主要任务，本文结合信号量机制分析了经典的进程同步的例子———生产者-消费者问题，并给出了相应的实现流程。