多进程同步方法解决生产者-消费者问题

课程设计报告课程名称：操作系统实验题目：用多进程同步方法解决生产者-消费者问题院系：计算机科学与工程学院班级：姓名：学号：指导老师：一、概述：1、问题描述：用多进程同步方法解决生产者-消费者问题设计目的:通过研究Linux的进程机制和信号量实现生产者消费者问题的并发控制.说明:有界缓冲区内设有20个存储单元,放入/取出的数据项设定为1-20这20个整型数.设计要求:1)每个生产者和消费者对有界缓冲区进行操作后,即时显示有界缓冲区的全部内容,当前指针位置和生产者/消费者线程的标识符.2)生产者和消费者各有两个以上.3)多个生产者或多个消费者之间须有共享对缓冲区进行操作的函数代码.2、程序设计基本思想:生产者—消费者问题是一种同步问题的抽象描述。计算机系统中的每个进程都可以消费或生产某类资源。当系统中某一进程使用某一资源时，可以看作是消耗，且该进程称为消费者。而当某个进程释放资源时，则它就相当一个生产者。一个有限空间的共享缓冲区，负责存放货物。生产者向缓冲区中放物品，缓冲区满则不能放。消费者从缓冲区中拿物品，缓冲区空则不能拿。因为有多个缓冲区，所以生产者线程没有必要在生成新的数据之前等待最后一个数据被消费者线程处理完毕。同样，消费者线程并不一定每次只能处理一个数据。在多缓冲区机制下，线程之间不必互相等待形成死锁，因而提高了效率。多个缓冲区就好像使用一条传送带替代托架，传送带上一次可以放多个产品。生产者在缓冲区尾加入数据，而消费者则在缓冲区头读取数据。当缓冲区满的时候，缓冲区就上锁并等待消费者线程读取数据；每一个生产或消费动作使得传送带向前移动一个单位，因而，消费者线程读取数据的顺序和数据产生顺序是相同的。可以引入一个count计数器来表示已经被使用的缓冲区数量。用Producer和Consumer来同步生产者和消费者线程。每当生产者线程发现缓冲区满（count=BufferSize），它就等待Consumer事件。同样，当消费者线程发现缓冲区空，它就开始等待Producer。生产者线程写入一个新的数据之后，就立刻发出Consumer来唤醒正在等待的消费者线程；消费者线程在读取一个数据之后，就发出Producer来唤醒正在等待的生产者线程。通过一个有界缓冲区(用数组来实现，类似循环队列)把生产者和消费者联系起来。假定生产者和消费者的优先级是相同的，只要缓冲区未满，生产者就可以生产产品并将产品送入缓冲区。类似地，只要缓冲区未空，消费者就可以从缓冲区中去走产品并消费它。应该禁止生产者向满的缓冲区送入产品，同时也应该禁止消费者从空的缓冲区中取出产品，这一机制有生产者线程和消费者线程之间的互斥关系来实现。二、图形描述及算法：m个生产者、k个消费者、共享n个单元缓冲区基本算法如下：三、程序流程图：4.1、生产者流程结构：-varB:array[0..n-1]ofinteger;Empty:g_hFullSemaphore:=SIZE_OF_BUFFER;/*可以使用的空缓冲区数*/Full:g_hEmptySemaphore:=0;/*缓冲区内可以使用的产品数*/Mutex:semaphore:=1;in,out:integer:=0;/*放入/取出缓冲区指针*/cobeginprocessproducer_I(I=1,2,…,m)processconsumer_j(j=1,2,…,k)BeginbeginL1:produceaproduct;L2:P(Full);//对资源信号量与互斥信号量//P操作生产消耗一个缓冲区P操作，申请资源P(Empty);P(Mutex);P(Mutex);Product:=B[out];B[in]:=product;out:=(out+1)modn;in:=(in+1)modn;V(Mutex);V(Mutex);V(Empty);V(Full);Consumeaproduct;GotoL1;GotoL2;end;end;Coend4.2消费者流程结构：生产者线程开始资源信号量P操作互斥信号量P操作生产一个产品把产品送入缓冲区互斥信号量V操作资源信号量V操作等待队列中有消费者线程等待队列中有消费者线程线程自我阻塞添加到等待队列线程自我阻塞添加到等待队列未通过未通过通过通过唤醒对头的消费者线程唤醒对头的消费者线程生产者线程结束YYNN四、数据结构及部分函数描述a)用一个整型数组Buffer_NUM来代表缓冲区。生产产品及对已有产品消费都需要访问该组缓冲区。缓冲区的大小和结构体：structBuffer{intproduct[BUFFER_NUM];//缓冲区消费者线程开始资源信号量P操作互斥信号量P操作从缓冲区取出一个产品消费一个产品互斥信号量V操作资源信号量V操作等待队列中有生产者线程等待队列中有生产者线程线程自我阻塞添加到等待队列线程自我阻塞添加到等待队列未通过未通过通过通过唤醒对头的生产者线程唤醒对头的生产者线程消费者线程结束YYNNintstart,end;//两个指针相当于教材中的inout指针}g_buf;b)在实现本程序的消费生产模型时，具体地通过如下同步对象实现互斥：i.设一个互斥量Mutex，以实现生产者在查询和保留缓冲区内的下一个空位置时进行互斥。ii.每一个生产者用一个信号量与其消费者同步，通过设置Full实现，该组信号量用于表示相应产品已生产。同时用一个表示空缓冲区数目的信号量Empty进行类似的同步，指示缓冲区中是否存在空位置，以便开始生产下一个产品。c)定义Windows下的P操作#defineP(S)WaitForSingleObject(S,INFINITE)说明：WaitForSingleObject函数用来检测hHandle事件的信号状态，在某一线程中调用该函数时，线程暂时挂起，如果在挂起的dwMilliseconds毫秒内，线程所等待的对象变为有信号状态，则该函数立即返回；如果超时时间已经到达dwMilliseconds毫秒，但hHandle所指向的对象还没有变成有信号状态，函数照样返回。参数dwMilliseconds有两个具有特殊意义的值：0和INFINITE。若为0，则该函数立即返回；若为INFINITE，则线程一直被挂起，直到hHandle所指向的对象变为有信号状态时为止。d)定义Windows下的V操作#defineV(S)ReleaseSemaphore(S,1,NULL)说明ReleaseSemaphore函数用于对指定的信号量增加指定的值e)生产者线程代码：DWORDWINAPIProducer(LPVOIDpara){inti=*(int*)para-CONSUMER_NUM;intptr;intdata;//产品intj=0;while(j++4){data=rand()%8;printf(生产者%01d:生产出:%s!\n,i,thing[data]);//等待存放空间P(Empty);//有地方，先锁住缓冲区P(Mutex);//记录消费的物品ptr=g_buf.end;c)消费者线程代码：DWORDWINAPIConsumer(LPVOIDpara){//i表示第i个消费者inti=*(int*)para;//利用para传入当前消费者的编号intptr;//待消费的内容的指针printf(消费者%1d:需要资源\n,i);intj=0;while(j++4){//等待产品P(Full);//有产品，先锁住缓冲区P(Mutex);//记录消费的物品ptr=g_buf.start;//再移动缓冲区指针g_buf.start=(g_buf.start+1)%BUFFER_NUM;//让其他消费者或生产者使用printf(消费者%01d:我需要buf[%d]=%s\n,i,ptr,thing[g_buf.product[ptr]]);//消费完毕，并释放一个缓冲printf(消费者%01d:我消费完毕%s\n,i,thing[g_buf.product[ptr]]);V(Mutex);V(Empty);Sleep(rate*rand()%10+110);}return0;}//再移动缓冲区指针g_buf.end=(g_buf.end+1)%BUFFER_NUM;printf(生产者%01d:放到缓冲区buf[%d]=%s\n,i,ptr,thing[data]);g_buf.product[ptr]=data;//放好了完毕，释放一个产品//让其他消费者或生产者使用V(Mutex);V(Full);Sleep(rate/2*rand()%10+110);}return0;}五、调试过程：为解决生产者/消费者问题，应该设置两个资源信号量，其中一个表示空缓冲区的数目，用Full表示，其初始值为有界缓冲区的大小BUFFER_NUM；另一个表示缓冲区中产品的数目，用Empty表示，其初始值为0。另外，由于有界缓冲区是一个临界资源，必须互斥使用，所以还需要再设置一个互斥信号量Mutex，起初值为1。在生产者/消费者问题中，信号量实现两种功能。首先，它是生产产品和消费产品的计数器，计数器的初始值是可利用的资源数目(有界缓冲区的长度)。其次，它是确保产品的生产者和消费者之间动作同步的同步器。生产者要生产一个产品时，首先对资源信号量Full和互斥信号量Mutex进行P操作，申请资源。如果可以通过的话，就生产一个产品，并把产品送入缓冲区。然后对互斥信号量Mutex和资源信号量Empty进行V操作，释放资源。消费者要消费一个产品时，首先对资源信号量Empty和互斥信号量Mutex进行P操作，申请资源。如果可以通过的话，就从缓冲区取出一个产品并消费掉。然后对互斥信号量Mutex和资源信号量Full进行V操作，释放资源。如果缓冲区中已经没有可用资源，就把申请资源的进程添加到等待队列的队尾。如果有一个资源被释放，在等待队列中的第一个进程被唤醒并取得这个资源的使用权。六、程序运行结果：在程序中设置了两个消费者，三个生产者，为便于描述出生产-消费的过程，我用食物代表被缓冲区消费的资源。在实验结果中我们可以看到几个生产者生产的食物放在缓冲区中，消费者需求的话就去缓冲区去取。在同一个时间点上不必生产者生产一个消费者就消费一个，消费者某个时间消费的资源有可能是上一个生产者所生产的。由于按题目要求设置的缓冲区为20，所以缓冲区没有溢出到等待消费者消费的情况。七、课程设计总结：本次课程设计通过模拟计算机操作系统中经典的“生产者—消费者问题”，巩固了我在操作系统原理课上所学的知识，加深了对操作系统中进程同步和互斥等问题，完成了多进程同步方法解决生产者－消费者问题全部过程，结果满足设计要求。设计过程中遇到不少困难，在反复研究老师的PPT及课本的原理后才逐渐明晰怎样将代码实现，虽然这学期学过Java，但java不是很熟悉，因此还是选择C++语言。以前学习C++没有深入了解到线程这个概念，在学习Java的时候才知道有专门的线程类。所以我在网上也参考了其他人用C++编写尤其是关于多进程程序的设计实现。在代码的实现过程中，我是主要定义了两个函数DWORDWINAPIConsumer(LPVOIDpara)和DWORDWINAPIProducer(LPVOIDpara)，在这两个函数中实现PV操作。通过本次设计，我较好地掌握了通过研究Linux的进程机制和信号量实现生产者消费者问题的并发控制全过程，尤其是对多进程程序设计方法有了更深的理解，开拓了思路，锻炼了实践动手能手。但是我觉得课程设计的时间有点短，中间又夹杂着好几场考试，所以没能做出界面以便于直观的观察出详细过程，只是用代码实现了要描述的功能且达到了要求，所以改进的空间还比较大。参考文献[1]计算机操作系统教程.孙钟秀等编著.高等教育出版社,2010年8月出版[2]数据结构教程.李春葆等编著清华大学出版社.2009年4月[3]面向对象程序设计与VisualC++6.0教程陈天华编著清华大学出版社.2009年7月附源代码：#i