生产者与消费者问题

哈尔滨师范大学学年论文题目生产者与消费者问题学生杨善明指导教师伦立军教授年级2008级专业计算机科学与技术系别计算机科学与技术系学院计算机科学与信息工程学院哈尔滨师范大学2011年6月1论文提要生产者—消费者问题（Producer_consumer）是一个经典的进程同步问题。它描述的是：有一群生产者进程在生产产品，并将此产品提供给消费者进程去消费。为使生产者进程和消费者进程能并发执行，在它们之间设置有个缓冲区的缓冲池，生产者进程可将它所生产的产品放入一个缓冲区中，消费者进程可从一个缓冲区取得一个产品消费。尽管所有的生产者进程和消费者进程都是以异步的方式运行的，但它们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个已装有消息尚未被取走产品的缓冲区投放产品。如下图所示：在中引入进程后，虽然提高了资源的利用率和系统的吞吐量，但由于进程的异步性，也会给系统造成混乱，尤其是在它们争用临界资源的时候。例如，当多个进程去争用一台打印机时，有可能使多个进程的输出结果交织在一起，难于区分；而当多个进程去争用共享变量，表格，链表时，有可能使数据处理出错。进程同步的主要任务就是使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。进程同步其优点在于能够让操作系统更加有效地对资源进行管理和调度，最大潜力地发挥处理机的性能。让系统的执行更加畅通无阻，尽可能地让系统少出现一些由于系统资源分配不合理所带来的死锁、死机之类的事情的发生。保持了处理机的高速运行之后从用户角度来说程序运行所花费的时间就会更短。从而保证了处理机在相同的时间内有更大的吞吐量。而把并发进程的同步和互斥问题一般化，就可以得到一个抽象的一般模型，即本次课程设计的任务：生产者—消费者问题。2生产者和消费者的问题杨善明摘要：在多道程序环境下，进程同步问题十分重要，也是一个相当有趣的问题，因而吸引了不少学者对它进行研究，并由此而产生了一系列经典的进程同步问题。其中比较有代表性的有“生产者—消费者问题”、“读者—写者问题”、“哲学家进餐问题”等等。通过对这些问题的研究和学习，可以帮助我们更好地理解进程同步概念及实现方法。关键词：操作系统进程同步生产者与消费者多线程本文讨论了多线程编程及其可行性，说明了在Windows环境下进行多线程编程的意义，并重点讨论了C++Builder平台下如何开发多线程应用程序这一问题，通过实现生产者－消费者问题这一著名的进程同步问题，比较清晰地反映了在Windows环境下进行多线程编程技术及其实现的作用和效果。一、设计思想我们把系统中使用某一类资源的进程称为该资源的消费者，而把释放同类资源的进程称为该资源的生产者。例如在计算进程与打印进程公用一个缓冲区时，计算进程把数据送入缓冲区，打印进程从缓冲区中取数据打印输出，因此，计算进程相当于数据资源的生产者，而打印进程相当于消费者，二者之间必须保持同步。基于这一问题，我们将使用生产者和消费者这一同步机制算法来处理该问题。二、解决方案首先，我们知道，生产者—消费者问题是一个同步问题。即生产者和消费者之间应满足如下条件：1)消费者想接收数据时，有界缓冲区中至少有一个单元是满的。2)生产者想发送数据时，有界缓冲区中至少有一个单元是空的。另外，由于有界缓冲区是临界资源，因此，各生产者进程和各消费者进程之间必须互斥。其次，我们还必须考虑面临的问题是属于进程互斥还是进程同步，或是互斥与同步的混合问题。然后根据共享资源的数量以及使用共享资源的规则正确的定义信号量及其初值。最后，还要对结果进行分析处理。若结果中生产和消费进程都已处理完时，但还可能出现以下两种情况：一是还有生产进程，但没有空缓冲，且消费进程暂时已完，所以此时，只能结束等待新的消费进程产生空缓冲。二是还有消费进程，但没有了满缓冲，且生产进程暂时已完，此时，只能结束等待新的生产进程来输入数据，产生新的满缓冲等。在程序中应能作出相应的判断和处理。三、程序的运行设置本程序的执行是在C++的环境中通过手动输入生产者和消费者线程的运行速度来控制3程序的运行的。为了实现生产者进程能把生产出来的产品正确的存入缓冲区，和消费者进程能够从缓冲区中取产品进行消费，防止因等待资源而出现死锁的现象，首先设置两个时间：生产者生产一个产品后等待的时间t1，和消费者消费一个产品后等待的时间t2，来控制生产者和消费者进程执行的速度。其函数原形是sleep(t1)和sleep(t2)其中t1、t2指定义挂起执行线程的时间，以毫秒为单位，取值为0时，该线程将余下的时间片交给处于就绪状态的同一优先级的其他线程。若没有处于就绪状态的同一优先级的其他线程，则函数立即返回。四、信号量机制的引用为了生产者进程送入缓冲池的消息能被消费者进程正确地取出消费,我们引入了信号量机制以避免进程在执行的过程中没有保持同步的情况发生。设置了信号量机制以后，生产者进程和消费者进程只能对缓冲区互斥地访问，也就是当生产者进程执行的时候消费者进程不能执行，反之奕然。其使用原理如下：一个进程在执行的时候它必需拥有信号量而且在执行的过程会一直占有信号量直到进程运行结束时释放信号量，这样就能保证多个进程的互斥执行。五、实验程序的结构图创建“生产者”线程缓冲区输入数据是否阻塞YN“生产者”等待，“消费者”取出缓冲区数据创建“消费者”线程缓冲区是否为空YN“消费者”阻塞“生产者”生产产品后被唤醒4六、运行结果与分析其中实验数据是：31P52P43P24C31321、在每个程序中坐须先做P(mutex)，后做V(mutex)，二者要成对出现。夹在二者中间的代码段就是该进程的临界区。2、对同步信号量full和empty的P，V操作同样必须成对出现，但它们分别位于不同的程序中。53、无论在生产者进程中还是在消费者进程中，两个P操作的次序不能颠倒:应先执行同步信号量的P操作，然后执行互斥信号量的P操作。否则可能造成进程死锁。七、结论通过这次实验了解到生产者-消费者问题是一个经典的进程同步问题，以及在其中使用信号量机制，生产者与消费者问题要求我们设计在同一个进程地址空间内执行的两个线程。生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费，而消费者线程从缓冲区中获得物品，然后释放缓冲区。当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放出一个空缓冲区，当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻塞，直到新的物品被生产出来。这次生产者和消费者问题的课程设计，不但加深了我对操作系统中多线程机制的理解和认识，更让我认识到知识的掌握，仅靠学习理论知识是远远不够的，要与实际动手操作相结合才能更好的理解和分析问题。八、结束语通过本次设计，我更近一步地了解了OS的进程机制和信号量实现生产者消费者问题的并发控制全过程，尤其是对多进程程序设计方法有了更深的理解。在书本上学习有关进程的同步的问题只是理论上的说法，并没有一个实际的东西，至少应是看得见的，对其含义也只是处于表面上的理解。这次实验我才体会到进程同步的真正涵义。最后，我还要感谢伦老师在实验过程中给予的指导和同学的帮助。特别是在实验开始时，我根本搞不懂是做什么，是伦老师给予引导才使我对此有了清晰的认识，从而完成本次课程设计。参考文献：【1】张尧学等编著，计算机操作系统教程，清华出版社。2008.6【2】汤子瀛等.计算机操作系统.西安电子科技大学出版社.2007年2月【3】严蔚敏，吴伟民编著，数据结构，清华大学出版社。2002【4】郑莉等编著，C++语言设计。北京：清华大学出版社.20006学年论文（设计）成绩表论文题目生产者与消费者问题作者杨善明指导教师伦立军职称教授指导教师评语指导教师签字等级