操作系统实现生产者消费者问题

操作系统实现生产者消费者问题-0-/13操作系统综合设计实现生产者消费者问题目录第一部分：实现生产者与消费者问题一、题目……………………………………………………………………………………………21、课程设计目的…………………………………………………………………………………22、课程设计要求…………………………………………………………………………………2二、设计内容………………………………………………………………………………………2三、开发环境………………………………………………………………………………………3四、分析设计………………………………………………………………………………………31、设计原理………………………………………………………………………………………32、涉及的数据结构………………………………………………………………………………53、流程图…………………………………………………………………………………………6五、运行示例及结果分析…………………………………………………………………………81、运行示例………………………………………………………………………………………82、运行结果分析：………………………………………………………………………………9六、个人体会………………………………………………………………………………………9七、附录（源程序）………………………………………………………………………………10第一部分：实现生产者与消费者问题一、题目：实现生产者与消费者问题操作系统实现生产者消费者问题-1-/13此问题是经典的进程同步互斥问题，问题描述参见教材第36页和第46页，要求编程实现，生产者放入产品的和消费者取走产品的速度可以调节。1、课程设计目的：在我们所学的《操作系统》这门课程中，关于经典进程的同步问题进行了一定的描述和探讨，介绍了几个经典的算法，需要我们在实践中学会熟练运用。在生产者与消费者问题中，需要我们了解进程同步的概念，理解信号量机制的原理，掌握运用信号量解决进程同步问题的方法，进而学会运用进程的同步与互斥解决生产者与消费者的冲突问题。2、课程设计要求：生产者与消费者问题可以算作是经典进程同步问题的典型代表。该课程设计要求运用基于单缓冲区和多缓冲区的生产者与消费者问题的多种实现机制,其中利用了数据结构中的循环队列和堆栈来模拟实现是一种比较容易实现的方法。这种思想能够帮助我们更好的理解所学内容，并加以锻炼我们的动手实践能力,实现它内在具有的超强的参考价值和实践意义。该课程设计通过了解进程间的两种制约关系，从而理解信号量机制；通过对实例的分析和讨论，理解信号量机制实现进程的同步及互斥的方法；通过对经典进程同步问题的剖析，初步掌握运用信号量解决进程同步问题的方法。二、设计内容在同一个进程地址空间内执行的两个线程。生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费。消费者线程从缓冲区中获得物品，然后释放缓冲区。当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放出一个空缓冲区。当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻塞，直到新的物品被生产出来，我的具体做法也是如此，建立缓冲区，生产者生产的产品放入，消费者从中取产品，如果没有产品，则等待。三、开发环境此程序的设计在WindowsXP操作系统下,基于MicrosoftVisualC++6.00环境下的一个关于实现生产者与消费者问题的程序。用C语言实现编程。操作系统实现生产者消费者问题-2-/13四、分析设计1、设计原理进程同步是指几个进程相互合作，一个进程到达某个点后，除非另一个进程已经完成某些操作，否则就不得不停下来，等待这些操作的结束，这就是进程同步的概念。生产者-消费者问题是一个经典的进程同步问题，该问题最早由Dijkstra提出，用以演示他提出的信号量机制。本作业要求设计在同一个进程地址空间内执行的两个线程。生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费。消费者线程从缓冲区中获得物品，然后释放缓冲区。当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放出一个空缓冲区。当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻塞，直到新的物品被生产出来。生产者—消费者问题是一种同步问题的抽象描述。计算机系统中的每个进程都可以消费或生产某类资源，当系统中某一进程使用某一资源时，可以看作是消耗，且该进程称为消费者。而当某个进程释放资源时，则它就相当一个生产者。通过一个有界缓冲区把生产者和消费者联系起来。假定生产者和消费者是相互等效的，只要缓冲区未满，生产者就可以将产品送入缓冲区，类似地，只要缓冲区未空，消费者就可以从缓冲区中去走物品并消费它。生产者和消费者的同步关系将禁止生产者向满的缓冲区输送产品，也禁止消费者从空的缓冲区中提取物品。在生产者—消费者问题中，信号灯具有两种功能。首先，它是跟踪资源的生产和消费的计数器；其次，它是协调资源的生产者和消费者之间的同步器。消费者通过再一指派给它的信号灯上做P操作来表示消耗资源，而生产者通过在同一信号灯上做V操作来表示生产资源。再这种信号灯的实施中，计数在每次P操作后减1，而在每次V操作中加1。个这一计数器的初始值是可利用的资源数目。当资源是不可利用时，将申请资源的进程放置在等待队列中。如果有一个资源释放，在等待队列中的第一个进程被唤醒并得到资源的控制权。为解决这一类生产者——消费者问题，设置了两个同步信号灯，一个说明空缓冲区的数目，用empty表示，其初值为有界缓冲区的大小n，另一个说明缓冲区的数目，用full表示，其初制值为0。由于有界缓冲区是一个零界资源，必须互斥使用，所以另外还需设置一个互斥信号灯mutex,起初值为1。假定在生产者和消费者之间的公用缓冲区中，具有n个缓冲区，这时可以利用互斥信号量mutex实现诸进程对缓冲池的互斥使用；利用信号量empty和full操作系统实现生产者消费者问题-3-/13分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者互相等效果，只要缓冲池未满，生产者便可以将消息送入缓冲池；只要缓冲池未空，消费者便可以从缓冲池中取走一个消息。在生产者---消费者问题中应注意：首先，在每个程序中用于互斥的wait(mutex)和signal(mutex)必须成对出现；其次，对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的程序中。生产者与消费者进程共享一个大小固定的缓冲区。其中，一个或多个生产者生产数据，并将生产的数据存入缓冲区，并有一个或多个消费者从缓冲区中取数据。假设缓冲区的大小为n（存储单元的个数），它可以被生产者和消费者循环使用。分别设置两个指针in和out，指向生产者将存放数据的存储单元和消费者将取出数据的存储单元，如图，指针in和out初始化指向缓冲区的第一个存储单元。生产者从第一个存储单元开始存放数据，一次存放一条数据一条数据且in指针向后移一个位置，当in指针指向第n个存储单元，下一次将指向第一个存储单元，如此循环反复使用缓冲区。消费者从缓冲区中逐条取走数据，一次取一条数据，相应的存储单元变为“空”，可以被生产者再次使用。每次取走一条数据，out指针向后移一个存储单元位置。试想，如果不控制生产者与消费者，将会产生什么结果？12345678n…………Inout12345678n…………Inout其中，in表示存数据位置，out表示取数据位置：：被占用单元：空存储单元图：生产者/消费者循环使用缓冲区首先，生产者和消费者可能同时进入缓冲区，甚至可能同时读/写一个存储单元，将导致执行结果不确定。这显然是不允许的。所以，必须使生产者和消费者互斥进入缓冲区。即某时刻只允许一个实体（生产者或消费者）访问缓冲区，操作系统实现生产者消费者问题-4-/13生产者互斥消费者和其他任何生产者。其次，生产者不能向满的缓冲区写数据，消费者也不能在空缓冲区中取数据，即生产者与消费者必须同步。当生产者产生出数据，需要将其存入缓冲区之前，首先检查缓冲区中是否有“空”存储单元，若缓冲区存储单元全部用完，则生产者必须阻塞等待，直到消费者取走一个存储单元的数据，唤醒它。若缓冲区内有“空”存储单元，生产者需要判断此时是否有别的生产者或消费者正在使用缓冲区，若是有，则阻塞等待，否则，获得缓冲区的使用权，将数据存入缓冲区，释放缓冲区的使用权。消费者取数据之前，首先检查缓冲区中是否存在装有数据的存储单元，若缓冲区为“空”，则阻塞等待，否则，判断缓冲区是否正在被使用，若正被使用，若正被使用，则阻塞等待，否则，获得缓冲区的使用权，进入缓冲区取数据，释放缓冲区的使用权。其执行流程如图所示，伪代码如图所示。2、涉及的数据结构①用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K，则表示系统中县有RJ类资源K个。②需求矩阵MAX。这是一个N*M的矩阵，它定义了系统中N个进程中的每一个进程对M类资源的最大需求。如果MAX[i,j]=K，则表示进程I需要RJ类资源的最大数目为K。③矩阵Allocation。这也是一个N*M的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得RJ类资源的数目为K。④矩阵Need。这也是一个N*M的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程I还需要RJ类资源K个，方能完成其任务。上述三个矩阵间存在下述关系：Need[i,j]=MAX[i,j]-Allocation[i,j]3、流程图生产一条数据等待资源，阻塞被唤醒操作系统实现生产者消费者问题-5-/13无有否是否可用存储单元是否可用被唤醒是否有数据单元操作系统实现生产者消费者问题-6-/13有否是五、运行示例及结果分析1、运行示例：是否可用空单元加1，唤醒一个生产者取走一条数据归还使用权消费数据等待资源，阻塞被唤醒等待使用权，阻塞被唤醒操作系统实现生产者消费者问题-7-/132、运行结果分析：此程序可自动输入生产者、消费者数目等条件，但程序执行过程中也进入了一种无限循环状态，若要得到较好的结果和界面需要加强编程练习。操作系统实现生产者消费者问题-8-/13六、个人体会经过快一个月的时间来弄这个大型作业。我当时真的有点力不从心。后来老师只要我们实现OS里面的一部分功能-----进程的控制和管理。就是比较有名的那两个进程算法。有于当时在实验室就对进程之间的运转有了一个全面的了解，虽然好多的细节部分还不是太了解，但是对一个进程的流向和执行过程还是有个大概的认识，所以这个大型作业做起来也不是那么的简单。那些东西的详细说明在我们的教材上是没有的。后来，我就在网上和图书馆大量的找资料。先对那些算法有一个大致全面的了解。经过两个多星期的查资料。我就开始对那两个算法的代码进行完善和修改，以达到我的要求。有经过了一个多星期的调试和运行终于达到了我的要求了。并把结果截取如下。在生产者与消费者问题的算法编写程序的时候要尽可能用全所学到的函数，因为这是检测我们用C语言进行程序设计的能力的重要方式。在编写程序的时候我们不可能一次就成功，往往一个图形要修改甚至是十几次数据才能得到预期的结果。因此在编写程序的时候一定不能急躁，要耐心地检测输入的数据和输出的结果，在没达到预期目的的情况下，要及时修改数据进行下一次的检测，只有这样才能成功地用C语言编写出需要的程序。编写程序是一个长期的过程，因此不能急躁，要坐的住。由于对C语言知识已经有些遗忘，所以我找出了以前的笔记，花了半天的时间去回忆和理解。对操作系统有关消费者---生产者问题的含义也已经有点模糊，我花了一天的时间看教材，还到图书馆借阅了相关的资料，才开始编程