生产者与消费者算法实现.doc

标准文档课程设计说明书题目: 生产者与消费者算法模拟 院 系： 计算机科学与工程 专业班级： 信息安全(xxxx)班 学 号： 201130xxxx 学生姓名： xxxx 指导教师： xxxx 2013年 xx月 xx 日 xxxx大学课程设计（论文）任务书 计算机 院系 计算机 教研室学 号20113xxxxx学生姓名xxxx专业（班级）xxxxx设计题目生产者与消费者算法模拟设计技术参数（1）系统作业或进程的数目；（2）系统资源的种类和数目；（3）系统作业或进程的对每类资源的最大需求数目；（4）系统作业或进程已分配的资源数目。设计要求（1）检查系统安全状态：根据系统作业或进程的对每类资源的最大需求数目、已分配的资源数目等计算是否存在安全序列。（2）检查系统是否可以继续某个进程资源分配请求。工作量 要求设计说明书的字数在3000字以上。工作计划2012.11.25-11.26 根据课程设计的要求，查找相关资料，完成需求分析；2012.11.26-11.27 进行系统的概要设计；2012.11.27-11.28 进行系统的详细设计和源代码的书写；2013.11.29-11.30 对系统进行调试分析，写出课程设计报告。参考资料1 Cay S.Horstmann,Gary Cornell编著.JAVA核心技术 卷 I.北京：机械工业出版社,2008.2 郑莉编著.Java语言程序设计（第二版）.北京：清华大学出版社,2011.3 吕国英等编著.算法设计与分析.北京：清华大学出版社，2009.4 马小军等编.软件工程项目案例与实践指导. 北京：清华大学出版社，2013.5 汤子瀛等编著. 计算机操作系统.西安：西安电子科技大学出版社,2011.指导教师签字教研室主任签字2012年xx月xx日指导教师评语：成绩： 指导教师： 年 月 日xxxx大学课程设计（论文）成绩评定表实用文案目录1.问题描述11.1目的11.2设计要求12.需求分析13. 概要设计13.1程序流程图14. 详细设计24.1程序框架24.1.1生产者与消费者的父类24.1.2 生产者类54.1.3 消费者类64.1.4 主程序入口64.2基本算法分析74.2.1 wait(mutex)与signal()数值信号74.2.2 isBufferEmpty()与isBufferFull()信号74.2.3 produce()存数方法与consume()取数方法85. 调试分析105.1不启动生产者线程测试结果分析105.2不启动消费者线程测试结果分析116. 用户手册117. 测试结果128. 设计体会13参考文献13附录13实用文案1.问题描述1.1目的掌握信号的使用方法和P、V操作的定义，掌握使用P、V操作实现进程之间同步与互斥的方法，加深对进程同步互斥概念的理解。1.2设计要求设计一程序，由一个进程创建三个子进程，三个子进程一个是生产者进程，两个是消费者进程，且要求：l 父子进程都使用父进程创建的共享存储区进行通信，由生产者进程将一个数组中的十个数值发送到由5个缓冲区组成的共享内存中；l 两个消费者进程轮流接收并输出这十个数值，同时将两个消费者进程读出的数值进行累加求各和。l 考虑生产者进程生产的速度和消费者进程速度。2.需求分析生产者-消费者问题是一个著名的进程同步问题。既然有进程间的同步，也就必将涉及到进程之间的互斥与通信问题，对于这个问题的解决有着很强的现实意义。它的现实意义在于可以类比到计算机中对于临界资源的互斥共享。生产者与消费者就好比是对计算机临界资源访问的程序或用户，而临界资源如打印机、磁带机等设备。3. 概要设计3.1程序流程图说明：图3.1 程序流程图所示，首先生产者与消费者线程创建，便就去访问缓冲区。对于生产者若缓冲区没有被其他线程访问，且缓冲区未满则生产数据存放到缓冲区，若其中有一条件没有满足则生产者线程进入阻塞状态。而对于消费者同样也需要缓冲区没有被其他线程访问，但同时要求缓冲区未空才能从缓冲区取数据，若其中有一个条件为满足则同样进入阻塞状态。“生产者”线程创建“消费者”阻塞“生产者”向缓冲区放入数据否是否有线程访问缓冲区否是是“消费者”或“生产者”阻塞缓冲区是否满否是否有线程访问缓冲区是缓冲区是否空否“消费者”线程创建“生产者”阻塞“消费者”从缓冲区中取数图3.1 程序流程图4. 详细设计4.1程序框架4.1.1生产者与消费者的父类public class SuperThread extends JPanel/定义缓冲区的读写锁private Lock bufferLock;/ 共享缓冲区public static IntBuffer buffer = IntBuffer.allocate(5);/生产者数组public int array = 1,5,6,9,8,11,13,10,7,3;/生产者执行的次数public static int count = 0;/两个生产者取出数据的累加public static int consumerSum = 0;/记录消费者取数次数public static int consumerCount = 0;/存放从缓冲区中取得的数据private static int consumerData;/定义线程名public String nameString;/线程互斥信号，值为 0 表示生产者进程，值为 1 表示消费者进程public static int mutex = 0;/* 构造函数 */public SuperThread(String name)/主要完成一些变量的初始化/* 获得线程名 */public String getNameString() return nameString;/* 设置线程名 */public void setNameString(String nameString) this.nameString = nameString;/* 获得互斥信号 */public static int getMutex() return mutex;/* 设置互斥信号 */public static void setMutex(int mutex) SuperThread.mutex = mutex;/* 判断是否有线程访问缓冲区，没有则对线程进行加锁 */public boolean wait(int mutex)if (mutex = 1) return false;else return true;/* 释放进程操作完成信号，其实本质就是修改mutex的信号值 */public static void signal()mutex = 0;/* 判断缓冲区是否为空 */public boolean isBufferEmpty()/根据缓冲区中是否有0存在来判断是否为空/若0的个数为5则为空，反之则不为空/* 判断缓冲区是否为满 */public boolean isBufferFull()/根据缓冲区中是否有0存在来判断是否为空/若0的个数为0则为满，反之则不满/* 消费数，即在缓冲区中取数 */public void consume()if (wait(mutex) & !isBufferEmpty() /判断是否访问缓冲区/加锁bufferLock.lock();try /设置互斥信号/从缓冲区取数/将取数后的缓冲区置0/释放互斥信号finally/解锁bufferLock.unlock();/* 消费者取得缓冲区数据*/public int getBufferData(int index)/完成取数操作return data;/* 生产数，即向缓冲区中存数*/public void produce()if (wait(mutex) & !isBufferFull() /判断是否访问缓冲区bufferLock.lock();/加锁try/设置互斥信号/向缓冲区存数/释放互斥信号finally/解锁bufferLock.unlock();/* 生产者向公共缓冲区放数据*/public void putBufferData(int index)/完成想缓冲区存数操作4.1.2 生产者类public class Producer extends SuperThread implements Runnable/ 生产者休眠时间private int producerDelay;/* 生产者构造函数 */public Producer(String name) super(name);/* 获得生产者休眠时间 */public int getProducerDelay() return producerDelay;/* 设置生产者休眠时间*/public void setProducerDelay(int producerDelay) this.producerDelay = producerDelay;/* 线程中的run函数，线程启动时默认调用的函数*/Overridepublic void run() /线程启动后向缓冲区存数操作4.1.3 消费者类public class Consumer extends SuperThread implements Runnable /* 消费者休眠时间 */private int consumerDelay;/* 消费者构造函数 */public Consumer(String name) super(name);/* 获得消费者休眠时间 */public int getConsumerDelay() return consumerDelay;/* 设置消费者休眠时间 */public void setConsumerDelay(int consumerDelay) this.consumerDelay = consumerDelay;/* 线程中的run函数，线程启动时默认调用的函数 */Overridepublic void run() while (true) /线程启动后向缓冲区取数操作4.1.4 主程序入口主函数 main(String args) /生产者与消费者对象定义producer、consumer1、consumer2 /设置休眠参数,如1000、2000、2500/创建线程producerThread、consumer1Thread、consumer2Thread /启动线程producerThread.start()、consumer1Thread.start()、/consumer2Thread.start();4.2基本算法分析4.2.1 wait(mutex)与signal()数值信号数值信号wait(mutex)主要是通过整型值mutex的设置来表示缓冲区是否已被访问，具体过程为：当有线程需要访问缓冲区时，先确定wait(mutex)信号值，若mutex的值为1则wait(mutex)为真，便可进行下一步操作，若mutex的值为0则wait(mutex)为不为真，该线程阻塞。当线程完成对缓冲区的访问后需要调用signal()信号对信号值mutex进行释放，释放后mutex的值为1，以便其他线程能够访问缓冲区。wait(mutex)与signal()的主要代码如下：public boolean wait(int mutex)/wait(mutex)信号if (mutex = 1) return false;else return true;public static void signal()/signal()信号mutex = 0;4.2.2 isBufferEmpty()与isBufferFull()信号对于以上所述的wait(mutex)信号还不足以控制线程之间的同步与互斥，还必须使用到isBufferEmpty()与isBufferFull()两个信号。对于生产者要用到信号isBufferFull()来判断缓冲区是否为满，当wait(mutex)型号值为真且isBufferFull()信号值不为真时，生产者线程才能对缓冲区进行存数操作，否则就阻塞等待机会。而对于消费者同样也要用到辅助信号isBufferEmpty()来判断缓冲区是否为空，只有缓冲区不为空且wait(mutex)为真是，消费者才能对缓冲区进行取数操作。isBufferEmpty()与isBufferFull()的主要代码如下：public boolean isBufferEmpty()/判断缓冲区是否为空int count = 0;for (int i = 0; i buffer.capacity(); i+) if (buffer.get(i) = 0) /根据缓冲区中的0的个数来判断，若缓/区0的个数为5（缓冲区容量为5），则为空/反之不为空count +;if (count = 5) return true;else return false;public boolean isBufferFull()/判断缓冲区是否为满int count = 0;for (int i = 0; i buffer.capacity(); i+) if (buffer.get(i) != 0) /根据缓冲区中不为0的个数来判断，若缓/区不为0的个数小于5（缓冲区容量为5），/则不为满，反之为满count +;if (count 5) return false;else return true;4.2.3 produce()存数方法与consume()取数方法produce()方法由生产者使用，在条件满足的情况下对缓冲区进行存数操作，而这个条件就是wait(mutex)=true & ! isBufferFull()=true。对于消费者调用consume()方法同样也要满足这样一个条件：wait(mutex)=true & ! isBufferEmpty()=true。produce()与consume()方法的主要代码如下：/* 生产数，即向缓冲区中存数*/public void produce()if (wait(mutex) & !isBufferFull() bufferLock.lock();/对该程序段加锁，防止其他线程访问缓冲区trysetMutex(1);/将线程互斥信号值mutex设置为1，使之互斥int index = 0;for (int i = 0; i buffer.capacity(); i+)/寻找存数的位置if (buffer.get(i) = 0) index = i;break;putBufferData(index);/向缓冲区中存入数据signal();/释放互斥信号，将mutex设置为0finallybufferLock.unlock();/解锁/* 消费数，即在缓冲区中取数 */public void consume()if (wait(mutex) & !isBufferEmpty() bufferLock.lock();/对该程序段加锁，防止其他线程访问缓冲区try setMutex(1);/将线程互斥信号值mutex设置为1，使之互斥int index = 0;/存放顺序查找第一个为0的数的下摆int i;for (i = 0; i 0)/缓冲区为满的情况index = 5;consumerData = getBufferData(index-1);/取数据consumerCount +;if (consumerCount = 2 ) consumerSum = consumerSum + consumerData;/计算两次取数/之和if (consumerCount = 2) System.out.println(消费者取数之和为：+consumerSum);consumerSum = 0;consumerCount = 0;buffer.put(index-1, 0);/将已取过数的缓冲区重新置0consumerPrintBufferData();/输出取数后的缓冲区signal();/释放互斥信号，将mutex设置为0finallybufferLock.unlock();/解锁5. 调试分析5.1不启动生产者线程测试结果分析由于没有启动生产者线程，所以缓冲区为空，从而导致isBufferEmpty()信号为真，所以消费者线程不可访问缓冲区取数。测试结果如图5.1：图5.1不启动生产者线程测试结果5.2不启动消费者线程测试结果分析因为没启动“消费者”而只启动了“生产者”，所以在缓冲区未满前“生产者”一直向缓冲区“生产”数据直到缓冲区满为止。由于没有“消费者”消费数据，所以缓冲区满后“生产者”不能再向缓冲区生产数据。测试结果如图5.2：图5.2不启动消费者线程测试结果6. 用户手册编写语言：JAVA运行环境：Windows XP/7/8 + MyElipse + JDK1.77. 测试结果根据分别只启动生产者线程和只启动消费者线程的分析结果，以及正确结果的得出可知生产者-消费者算法模拟成功。下面给出了完整代码的运行结果的部分图片，如图7.1、7.2、7.3：图7.1图7.2图7.38. 设计体会无论是在操作系统这门课程，还是在其它的课程中只要讲到线程就必定会提到“生产者与消费者”问题。因为就这个问题能够很好地模拟线程间的同步、异步以及线程间的通信，而且易于学生理解线程关系与联系。在本次课程设计中通过自己编写代码实现“生产者-消费者”算法，其中主要的算法思想体现在如何通过信号函数来控制线程的执行。在算法的编写过程中遇到了许多的小问题，但在不断的调试和查阅资料得到了解决，这让我对线程有了更深的了解，明白了操作系统是如何通过各种机制来实现线程之间有条不紊的执行。最后我还想说，进入大学后每个学期都有课程设计，大家都以分组的方式来完成课程设计题目。对于设计过程中出现的问题，组员之间的交流和讨论时很有效的，能及时的将问题解决，我想这一点不论是在今后的生活还是工作中都会有很大的帮助参考文献1 Cay S.Horstmann,Gary Cornell编著.JAVA核心技术 卷 I.北京：机械工业出版社,2008.2 郑莉编著.Java语言程序设计（第二版）.北京：清华大学出版社,2011.3 吕国英等编著.算法设计与分析.北京：清华大学出版社，2009.4 马小军等编.软件工程项目案例与实践指导. 北京：清华大学出版社，2013.5 汤子瀛等编著. 计算机操作系统.西安：西安电子科技大学出版社,2011.附录实用文案