生产者与消费者算法实现.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.问题描述 1
1.1目的 1
1.2设计要求 1
2.需求分析 1
3. 概要设计 1
3.1程序流程图 1
4. 详细设计 2
4.1程序框架 2
4.1.1生产者与消费者的父类 2
4.1.2 生产者类 5
4.1.3 消费者类 6
4.1.4 主程序入口 6
4.2基本算法分析 7
4.2.1 wait(mutex)与signal()数值信号 7
4.2.2 isBufferEmpty()与isBufferFull()信号 7
4.2.3 produce()存数方法与consume()取数方法 8
5. 调试分析 10
5.1不启动生产者线程测试结果分析 10
5.2不启动消费者线程测试结果分析 11
6. 用户手册 11
7. 测试结果 12
8. 设计体会 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函数，线程启动时默认调用的函数*/
@Override
public 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函数，线程启动时默认调用的函数 */
@Override
public 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();//对该程序段加锁，防止其他线程访问缓冲区
try{
setMutex(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设置为0
}finally{
bufferLock.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 < buffer.capacity(); i++) {//顺序查找第一个为 //0的数
if (buffer.get(i) == 0) {
index = i;
break;
}else if(buffer.get(4) > 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);//将已取过数的缓冲区重新置0
consumerPrintBufferData();//输出取数后的缓冲区
signal();//释放互斥信号，将mutex设置为0
}finally{
bufferLock.unlock();//解锁
}
}
}
5. 调试分析
5.1不启动生产者线程测试结果分析
由于没有启动生产者线程，所以缓冲区为空，从而导致isBufferEmpty()信号为真，所以消费者线程不可访问缓冲区取数。测试结果如图5.1：
图5.1不启动生产者线程测试结果
5.2不启动消费者线程测试结果分析
因为没启动“消费者”而只启动了“生产者”，所以在缓冲区未满前“生产者”一直向缓冲区“生产”数据直到缓冲区满为止。由于没有“消费者”消费数据，所以缓冲区满后“生产者”不能再向缓冲区生产数据。测试结果如图5.2：

图5.2不启动消费者线程测试结果
6. 用户手册
编写语言：JAVA
运行环境：Windows XP/7/8 + MyElipse + JDK1.7
7. 测试结果
根据分别只启动生产者线程和只启动消费者线程的分析结果，以及正确结果的得出可知生产者--消费者算法模拟成功。下面给出了完整代码的运行结果的部分图片，如图7.1、7.2、7.3：

图7.1

图7.2

图7.3
8. 设计体会
无论是在操作系统这门课程，还是在其它的课程中只要讲到线程就必定会提到“生产者与消费者”问题。因为就这个问题能够很好地模拟线程间的同步、异步以及线程间的通信，而且易于学生理解线程关系与联系。
在本次课程设计中通过自己编写代码实现“生产者--消费者”算法，其中主要的算法思想体现在如何通过信号函数来控制线程的执行。在算法的编写过程中遇到了许多的小问题，但在不断的调试和查阅资料得到了解决，这让我对线程有了更深的了解，明白了操作系统是如何通过各种机制来实现线程之间有条不紊的执行。
最后我还想说，进入大学后每个学期都有课程设计，大家都以分组的方式来完成课程设计题目。对于设计过程中出现的问题，组员之间的交流和讨论时很有效的，能及时的将问题解决，我想这一点不论是在今后的生活还是工作中都会有很大的帮助
参考文献
[1] Cay S.Horstmann,Gary Cornell编著.JAVA核心技术 卷 I.北京：机械工业出版社,2008.
[2] 郑莉编著.Java语言程序设计（第二版）.北京：清华大学出版社,2011.
[3] 吕国英等编著.算法设计与分析.北京：清华大学出版社，2009.
[4] 马小军等编.软件工程项目案例与实践指导. 北京：清华大学出版社，2013.
[5] 汤子瀛等编著. 计算机操作系统.西安：西安电子科技大学出版社,2011.
附录

实用文案