操作系统综合设计
实现生产者消费者问题
目 录
第一部分：实现生产者与消费者问题
一、题目……………………………………………………………………………………………2 1、课程设计目的…………………………………………………………………………………2 2、课程设计要求…………………………………………………………………………………2 二、设计内容………………………………………………………………………………………2 三、开发环境………………………………………………………………………………………3 四、分析设计………………………………………………………………………………………3 1、设计原理………………………………………………………………………………………3 2、涉及的数据结构………………………………………………………………………………5 3、流程图…………………………………………………………………………………………6 五、运行示例及结果分析…………………………………………………………………………8 1、运行示例………………………………………………………………………………………8 2、运行结果分析：………………………………………………………………………………9 六、个人体会………………………………………………………………………………………9 七、附录（源程序）………………………………………………………………………………10
第一部分：实现生产者与消费者问题
一、题目：实现生产者与消费者问题
此问题是经典的进程同步互斥问题，问题描述参见教材第36页和第46页，要求编程实现，生产者放入产品的和消费者取走产品的速度可以调节。 1、课程设计目的：
在我们所学的《操作系统》这门课程中，关于经典进程的同步问题进行了一定的描述和探讨，介绍了几个经典的算法，需要我们在实践中学会熟练运用。在生产者与消费者问题中，需要我们了解进程同步的概念，理解信号量机制的原理，掌握运用信号量解决进程同步问题的方法，进而学会运用进程的同步与互斥解决生产者与消费者的冲突问题。 2、课程设计要求：
生产者与消费者问题可以算作是经典进程同步问题的典型代表。该课程设计要求运用基于单缓冲区和多缓冲区的生产者与消费者问题的多种实现机制,其中利用了数据结构中的循环队列和堆栈来模拟实现是一种比较容易实现的方法。这种思想能够帮助我们更好的理解所学内容，并加以锻炼我们的动手实践能力,实现它内在具有的超强的参考价值和实践意义。
该课程设计通过了解进程间的两种制约关系，从而理解信号量机制；通过对实例的分析和讨论，理解信号量机制实现进程的同步及互斥的方法；通过对经典进程同步问题的剖析，初步掌握运用信号量解决进程同步问题的方法。
二、设计内容
在同一个进程地址空间内执行的两个线程。生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费。消费者线程从缓冲区中获得物品，然后释放缓冲区。当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放出一个空缓冲区。当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻塞，直到新的物品被生产出来，我的具体做法也是如此，建立缓冲区，生产者生产的产品放入，消费者从中取产品，如果没有产品，则等待。
三、开发环境
此程序的设计在Windows XP操作系统下,基于Microsoft Visual C++6.00环境下的一个关于实现生产者与消费者问题的程序。用C语言实现编程。
四、分析设计
1、设计原理
进程同步是指几个进程相互合作，一个进程到达某个点后，除非另一个进程已经完成某些操作，否则就不得不停下来，等待这些操作的结束，这就是进程同步的概念。
生产者-消费者问题是一个经典的进程同步问题，该问题最早由Dijkstra提出，用以演示他提出的信号量机制。本作业要求设计在同一个进程地址空间内执行的两个线程。生产者线程生产物品，然后将物品放置在一个空缓冲区中供消费者线程消费。消费者线程从缓冲区中获得物品，然后释放缓冲区。当生产者线程生产物品时，如果没有空缓冲区可用，那么生产者线程必须等待消费者线程释放出一个空缓冲区。当消费者线程消费物品时，如果没有满的缓冲区，那么消费者线程将被阻塞，直到新的物品被生产出来。
生产者—消费者问题是一种同步问题的抽象描述。计算机系统中的每个进程都可以消费或生产某类资源，当系统中某一进程使用某一资源时，可以看作是消耗，且该进程称为消费者。而当某个进程释放资源时，则它就相当一个生产者。 通过一个有界缓冲区把生产者和消费者联系起来。假定生产者和消费者是相互等效的，只要缓冲区未满，生产者就可以将产品送入缓冲区，类似地，只要缓冲区未空，消费者就可以从缓冲区中去走物品并消费它。生产者和消费者的同步关系将禁止生产者向满的缓冲区输送产品，也禁止消费者从空的缓冲区中提取物品。
在生产者—消费者问题中，信号灯具有两种功能。首先，它是跟踪资源的生产和消费的计数器；其次，它是协调资源的生产者和消费者之间的同步器。消费者通过再一指派给它的信号灯上做P操作来表示消耗资源，而生产者通过在同一信号灯上做V操作来表示生产资源。再这种信号灯的实施中，计数在每次P操作后减1，而在每次V操作中加1。个这一计数器的初始值是可利用的资源数目。当资源是不可利用时，将申请资源的进程放置在等待队列中。如果有一个资源释放，在等待队列中的第一个进程被唤醒并得到资源的控制权。
为解决这一类生产者——消费者问题，设置了两个同步信号灯，一个说明空缓冲区的数目，用empty表示，其初值为有界缓冲区的大小n，另一个说明缓冲区的数目，用full表示，其初制值为0。由于有界缓冲区是一个零界资源，必须互斥使用，所以另外还需设置一个互斥信号灯mutex,起初值为1。
假定在生产者和消费者之间的公用缓冲区中，具有n个缓冲区，这时可以利用互斥信号量mutex实现诸进程对缓冲池的互斥使用；利用信号量empty和full
分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者互相等效果，只要缓冲池未满，生产者便可以将消息送入缓冲池；只要缓冲池未空，消费者便可以从缓冲池中取走一个消息。
在生产者---消费者问题中应注意：首先，在每个程序中用于互斥的wait(mutex)和signal(mutex)必须成对出现；其次，对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的程序中。
生产者与消费者进程共享一个大小固定的缓冲区。其中，一个或多个生产者生产数据，并将生产的数据存入缓冲区，并有一个或多个消费者从缓冲区中取数据。
假设缓冲区的大小为n（存储单元的个数），它可以被生产者和消费者循环使用。分别设置两个指针in和out，指向生产者将存放数据的存储单元和消费者将取出数据的存储单元，如图，指针in和out初始化指向缓冲区的第一个存储单元。生产者从第一个存储单元开始存放数据，一次存放一条数据一条数据且in指针向后移一个位置，当in 指针指向第n个存储单元，下一次将指向第一个存储单元，如此循环反复使用缓冲区。消费者从缓冲区中逐条取走数据，一次取一条数据，相应的存储单元变为“空”，可以被生产者再次使用。每次取走一条数据，out指针向后移一个存储单元位置。试想，如果不控制生产者与消费者，将会产生什么结果？
1 2 3 4 5 6 7 8 n In out
1 2 3 4 5 6 7 8 n In out
其中，in表示存数据位置，out表示取数据位置
： ：被占用单元 ：空存储单元 图：生产者/消费者循环使用缓冲区
首先，生产者和消费者可能同时进入缓冲区，甚至可能同时读/写一个存储单元，将导致执行结果不确定。这显然是不允许的。所以，必须使生产者和消费者互斥进入缓冲区。即某时刻只允许一个实体（生产者或消费者）访问缓冲区，
………… ………… 生产者互斥消费者和其他任何生产者。
其次，生产者不能向满的缓冲区写数据，消费者也不能在空缓冲区中取数据，即生产者与消费者必须同步。当生产者产生出数据，需要将其存入缓冲区之前，首先检查缓冲区中是否有“空”存储单元，若缓冲区存储单元全部用完，则生产者必须阻塞等待，直到消费者取走一个存储单元的数据，唤醒它。若缓冲区内有“空”存储单元，生产者需要判断此时是否有别的生产者或消费者正在使用缓冲区，若是有，则阻塞等待，否则，获得缓冲区的使用权，将数据存入缓冲区，释放缓冲区的使用权。消费者取数据之前，首先检查缓冲区中是否存在装有数据的存储单元，若缓冲区为“空”，则阻塞等待，否则，判断缓冲区是否正在被使用，若正被使用，若正被使用，则阻塞等待，否则，获得缓冲区的使用权，进入缓冲区取数据，释放缓冲区的使用权。其执行流程如图所示，伪代码如图所示。 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、流程图
生产一条数据 等待资源，阻塞
操作系统实现生产者消费者问题讲课讲稿
