利用信号量解决生产者消费者问题
操作系统课 程 设 计 任 务 书
一、设计题目
利用信号量解决生产者—消费者问题
二、主要内容
使用AND信号量解决生产者—消费者问题。
三、具体要求及应提交的材料
用C/C++语言编程实现上述内容，并按数学与计算机学院对课程设计说明书规范化要求，写出课程设计说明书，并提交下列材料：
1)课程设计说明书打印稿一份
2)课程设计说明书电子稿一份；
3)源程序电子文档一份。
四、主要技术路线提示
定义相应数据类型，使用AND信号量。
五、进度安排
按教学计划规定，数据结构课程设计为2周，其进度及时间大致分配如下：
序号
设计内容
天数
1
分析问题，给出数学模型，选择数据结构
2
2
设计算法，给出算法描述
1
3
给出源程序清单
2
4
编辑、编译、调试源程序
2
5
编写课程设计报告
3
总 计
10
六、推荐参考资料
[1] 汤子瀛，哲凤屏，汤小丹。计算机操作系统。西安电子科技大学出版社。2000年2月
[2] 黄祥喜。计算机操作系统实验教程。广州：中山大学出版社。1994
[3]史美林，张尧学。计算机操作系统教程。清华大学出版社。2000年8月
摘 要
生产者-消费者问题是最著名的同步问题，它描述一组生产者（P1 ……Pk）向一组消费者（C1……Cm）提供消息。它们共享一个有界缓冲池（bounded buffer pool）,生产者向其中投放消息，消费者从中取得消息。假定这些生产者和消费者互相等效，只要缓冲池未满，生产者可将消息送入缓冲池；只要缓冲池未空，消费者可从缓冲池取走一个消息。计算机系统中的每个进程都可以消费或生产某类资源。当系统中某一进程使用某一资源时，可以看作是消耗，且该进程称为消费者。而当某个进程释放资源时，则它就相当一个生产者。有界缓冲区内设有20个存储单元,放入/取出的数据项设定为1-20这20个整型数。每个生产者和消费者对有界缓冲区进行操作后，即时显示有界缓冲区的全部内容，当前指针位置和生产者/消费者线程的标识符。生产者和消费者各有两个以上以及多个生产者或多个消费者之间须有共享对缓冲区进行操作的函数代码。
关键词：生产者 消费者 AND信号量
1.设计思想
1.1生产者—消费者设计思想
通过一个有界缓冲区(用数组来实现，类似循环队列)把生产者和消费者联系起来。假定生产者和消费者的优先级是相同的，只要缓冲区未满，生产者就可以生产产品并将产品送入缓冲区。类似地，只要缓冲区未空，消费者就可以从缓冲区中去走产品并消费它。应该禁止生产者向满的缓冲区送入产品，同时也应该禁止消费者从空的缓冲区中取出产品，这一机制有生产者线程和消费者线程之间的互斥关系来实现。与计算打印两进程同步关系相同，生产者和消费者二类进程P和C之间应满足下列二个同步条件：
1.只有在缓冲池中至少有一个缓冲区已存入消息后，消费者才能从中提取消息，否则消费者必须等待。
2.只有缓冲池中至少有一个缓冲区是空时，生产者才能把消息放入缓冲区，否则生产者必须等待。
为了满足第一个同步条件，设置一个同步信号量full，它代表的资源是缓冲区满，它的初始值为0，它的值为n时整个缓冲池满。这个资源是消费者类进程C所拥有，C进程可以申请该资源，对它施加P操作，而C进程的合作进程生产者进程P对它施加V操作。同样为了满足第二个同步条件，设置另一个同步信号量empty，它代表的资源是缓冲区空，它的初始值为n，表示缓冲池中所有缓冲区空。信号量 full表可用缓冲区数量，信号量 empty表空缓冲区数量，设置整型变量：存入指针in 和 取出指针out 。
为解决生产者/消费者问题，应该设置两个资源信号量，其中一个表示空缓冲区的数目，用g_hFullSemaphore表示，其初始值为有界缓冲区的大小SIZE_OF_BUFFER；另一个表示缓冲区中产品的数目，用g_hEmptySemaphore表示，其初始值为0。另外，由于有界缓冲区是一个临界资源，必须互斥使用，所以还需要再设置一个互斥信号量g_hMutex，起初值为1。在生产者/消费者问题中，信号量实现两种功能。首先，它是生产产品和消费者199
利用信号量解决生产者消费者问题
产品的计数器，计数器的初始值是可利用的资源数目(有界缓冲区的长度)。其次，它是确保产品的生产者和消费者之间动作同步的同步器。生产者要生产一个产品时，首先对资源信号量g_hFullSemaphore和互斥信号量g_hMutex进行P操作，申请资源。如果可以通过的话，就生产一个产品，并把产品送入缓冲区。然后对互斥信号量g_hMutex和资源信号量g_hEmptySemaphore进行V操作，释放资源。
消费者要消费一个产品时，首先对资源信号量g_hEmptySemaphore和互斥信号量g_hMutex进行P操作，申请资源。如果可以通过的话，就从缓冲区取出一个产品并消费掉。然后对互斥信号量g_hMutex和资源信号量g_hFullSemaphore进行V操作，释放资源。如果缓冲区中已经没有可用资源，就把申请资源的进程添加到等待队列的队尾。如果有一个资源被释放，在等待队列中的第一个进程被唤醒并取得这个资源的使用权。
2.文件系统结构
2.1生产者—消费者系统结构
2.1.1 假定缓冲池中有n个缓冲区，每个缓冲区存放一个消息。由于缓冲池是临界资源，它只允许一个生产者投入消息，或者一个消费者从中取出消息。即生产者之间、生产者与消费者之间、消费者之间都必须互斥使用缓冲池。所以必须设置互斥信号量mutex，它代表缓冲池资源，它的数值为1。如下图所示：
图2.1.1生产者—消费者问题
2.1.2同步问题：
P进程不能往“满”的缓冲区中放产品，设置信号量为s_empty；
Q进程不能从“空”的缓冲区中取产品，设置信号量s_full。
先设置信号量：s_empty初值为1， s_full初值为0
P： Q：
while (true) while (true)
｛ ｛
生产一个产品; P(s_full);
P(s_empty); 从缓冲区取产品;
送产品到缓冲区; V(s_empty);
V(s_full); 消费产品;
}; };
以上算法可用下图来描述：若图片无法显示请联系QQ3710167
图2.1.2生产者—消费者单缓冲区
1.P原语操作的主要动作是：
（1）sem减1；
（2）若sem减1后仍大于或等于零，则进程继续执行；
（3）若sem减1后仍小于零，则该进程被阻塞后与该信号相对应的队列中，然后转进程调度。
P原语操作的功能框图如图1。
图1 P原语操作功能
2.V原语操作的主要动作是：若图片无法显示请联系QQ3710167
（1）sem加1；
（2）若相加结果大于零，则进程继续执行；
（3）若相加结果小于或等于零，则从该信号的等待队列中唤醒—等待进程，然后再返回原进程继续执行或转进程调度。
V原语操作的功能框图如图2。
图2 V原语操作功
2.2生产者—消费者存储结构
const unsigned short SIZE_OF_BUFFER = 10; //缓冲区长度
unsigned short ProductID = 0; //产品号
unsigned short ConsumeID = 0; //将被消耗的产品号
unsigned short in = 0; //产品进缓冲区时的缓冲区下标
unsigned short out = 0; //产品出缓冲区时的缓冲区下标
int g_buffer[SIZE_OF_BUFFER]; //缓冲区是个循环队列
bool g_continue = true; //控制程序结束
HANDLE g_hMutex; //用于线程间的互斥
HANDLE g_hFullSemaphore; //当缓冲区满时迫使生产者等待
HANDLE g_hEmptySemaphore; //当缓冲区空时迫使消费者等待
2.3生产者—消费者线程状态
DWORD WINAPI Producer(LPVOID); //生产者线程
DWORD WINAPI Consumer(LPVOID); //消费者线程
3.核心数据结构及算法说明
3.1数据定义
const unsigned short SIZE_OF_BUFFER = 10; //缓冲区长度
unsigned short ProductID = 0; //产品号
unsigned short ConsumeID = 0; //将被消耗的产品号
unsigned short in = 0; //产品进缓冲区时的缓冲区下标
unsigned short out = 0; //产品出缓冲区时的缓冲区下标
int g_buffer[SIZE_OF_BUFFER]; //缓冲区是个循环队列
bool g_continue = true; //控制程序结束
HANDLE g_hMutex; //用于线程间的互斥
HANDLE g_hFullSemaphore; //当缓冲区满时迫使生产者等待
HANDLE g_hEmptySemaphore; //当缓冲区空时迫使消费者等待
DWORD WINAPI Producer(LPVOID); //生产者线程
DWORD WINAPI Consumer(LPVOID); //消费者线程
3.2算法说明
用AND 型信号量解决生产者--消费者问题的算法说明如下：
semaphore mutex=1;
semaphore empty=n;
semaphore full=0;
item array[n];
int in=0;
int out=0;
producer()
{
while(ture)
{
produce an item in next_product;
Swaite(empty,mutex);
array[in]=next_product;
in=(in+1)%n;
Ssignal(mutex,full);
}
}
consumer()
{
while(ture)
{
利用信号量解决生产者消费者问题
Swaite(full,mutex);
next_consumer=array[out];
out=(out+1)%n;
Ssignal(mutex,empty);
consum the product in next_consumer;
}
}
4.算法流程图
一组生产者向一组消费者提供消息，它们共享一个有界缓冲池，生产者向其中投放消息，消费者从中取得消息。假定这些生产者和消费者互相等效，只要缓冲池未满，生产者可将消息送入缓冲池；只要缓冲池未空，消费者可从缓冲池取走一个消息。生产者与消费者问题算法实现的主要流程图如下图4.1和图4.2所示：若图片无法显示请联系QQ3710167
图4.1生产者与消费者主要流程图
图4.2生产者与消费者主要流程图
5.程序清单
5.1存储结构定义
5.1.1定义生产者—消费者的存储结构为：
利用信号量解决生产者消费者问题
const unsigned short SIZE_OF_BUFFER = 10; //缓冲区长度
unsigned short ProductID = 0; //产品号
unsigned short ConsumeID = 0; //将被消耗的产品号
unsigned short in = 0; //产品进缓冲区时的缓冲区下标
unsigned short out = 0; //产品出缓冲区时的缓冲区下标
int g_buffer[SIZE_OF_BUFFER]; //缓冲区是个循环队列
bool g_continue = true; //控制程序结束
HANDLE g_hMutex; //用于线程间的互斥
HANDLE g_hFullSemaphore; //当缓冲区满时迫使生产者等待
HANDLE g_hEmptySemaphore; //当缓冲区空时迫使消费者等待
DWORD WINAPI Producer(LPVOID); //生产者线程
DWORD WINAPI Consumer(LPVOID); //消费者线程
5.2算法相关的函数
5.2.1创建各个互斥信号以及生产者线程和消费者线程的函数在如下主函数里面所示：
int main()
{
//创建各个互斥信号
g_hMutex = CreateMutex(NULL,FALSE,NULL);
g_hFullSemaphore CreateSemaphore(NULL,SIZE_OF_BUFFER-1,SIZE_OF_BUFFER-1,NULL);
g_hEmptySemaphore = CreateSemaphore(NULL,0,SIZE_OF_BUFFER-1,NULL);
//调整下面的数值，可以发现，当生产者个数多于消费者个数时，
//生产速度快，生产者经常等待消费者；反之，消费者经常等待。
const unsigned short PRODUCERS_COUNT = 3; //生产者的个数
const unsigned short CONSUMERS_COUNT = 1; //消费者的个数
//总的线程数
const unsigned short THREADS_COUNT
PRODUCERS_COUNT+CONSUMERS_COUNT;
HANDLE hThreads[PRODUCERS_COUNT]; //各线程的handle
DWORD producerID[CONSUMERS_COUNT]; //生产者线程的标识符
DWORD consumerID[THREADS_COUNT]; //消费者线程的标识符
//创建生产者线程
for (int i=0;i
{
hThreads[i]=CreateThread(NULL,0,Producer,NULL,0,&producerID[i]);
if (hThreads[i]==NULL)
return -1;
}
//创建消费者线程
for ( i=0;i {
hThreads[PRODUCERS_COUNT+i]=CreateThread(NULL,0,Consumer,NULL,0
&consumerID[i]);
if (hThreads[i]==NULL)
return -1;
}
while(g_continue)
{
if(getchar())
{
//按回车后终止程序运行
g_continue = false;
}
}
return 0;
}
5.2.2生产者生产一个产品的函数：
//生产一个产品。简单模拟了一下，仅输出新产品的ID号
void Produce()
{
std::cerr << "Producing " << ++ProductID << " *** ";
std::cerr << "Succeed" << std::endl;
}
5.2.3把新生产的产品放入缓冲区的函数：
//把新生产的产品放入缓冲区
void Append()
{
std::cerr << "Appending a product *** ";
g_buffer[in] = ProductID;
in = (in+1)%SIZE_OF_BUFFER;
std::cerr << "Succeed" << std::endl;
}
5.2.4输出缓冲区当前的状态的函数：
//输出缓冲区当前的状态
for (int i=0;i {
std::cout << i <<": " << g_buffer[i];
if (i==in)
std::cout << " <-- 生产";
if (i==out)
std::cout << " <-- 消费";
std::cout << std::endl;
}
5.2.5从缓冲区中取出一个产品的函数：
//从缓冲区中取出一个产品
void Take()
{
std::cerr << "Taking a product *** ";
ConsumeID = g_buffer[out];
out = (out+1)%SIZE_OF_BUFFER;
利用信号量解决生产者消费者问题
std::cerr << "Succeed" << std::endl;
}
5.2.6输出缓冲区当前的状态的函数：
//输出缓冲区当前的状态
for (int i=0;i {
std::cout << i <<": " << g_buffer[i];
if (i==in)
std::cout << " <-- 生产";
if (i==out)
std::cout << " <-- 消费";
std::cout << std::endl;
}
}
5.2.7消耗一个产品的函数：
//消耗一个产品
void Consume()
{
std::cerr << "Consuming " << ConsumeID << " *** ";
std::cerr << "Succeed" << std::endl;
}
5.3生产者和消费者算法
5.3.1生产者算法：
//生产者
DWORD WINAPI Producer(LPVOID lpPara)
{
while(g_continue)
{
WaitForSingleObject(g_hFullSemaphore,INFINITE);
WaitForSingleObject(g_hMutex,INFINITE);
Produce();
Append();
Sleep(1500);
ReleaseMutex(g_hMutex);
ReleaseSemaphore(g_hEmptySemaphore,1,NULL);
}
return 0;
}
5.3.2消费者算法：
//消费者
DWORD WINAPI Consumer(LPVOID lpPara)
{
while(g_continue)
{
WaitForSingleObject(g_hEmptySemaphore,INFINITE);
WaitForSingleObject(g_hMutex,INFINITE);
Take();
Consume();
Sleep(1500);
ReleaseMutex(g_hMutex);
ReleaseSemaphore(g_hFullSemaphore,1,NULL);
}
return 0;
}
利用信号量解决生产者消费者问题
6.使用说明书
6.1本次设计是在Ｖisual C++里做的，具体使用过程按运行时候的提示进行操作。
进入运行界面，如下面图所示：若图片无法显示请联系QQ3710167
图6.1.4生产产品和消费产品
7.总结
通过这次课程设计,不但加深了对操作系统这们课程的认识,而且还了解了操作系统中使用AND信号量解决生产者—消费者问题算法的实现。比如：用AND信号量解决生产者—消费者问题时，可以通过一个有界缓冲区(用数组来实现，类似循环队列)把生产者和消费者联系起来。假定生产者和消费者的优先级是相同的，只要缓冲区未满，生产者就可以生产产品并将产品送入缓冲区。类似地，只要缓冲区未空，消费者就可以从缓冲区中去走产品并消费它。为了解决生产者/消费者问题，应该设置两个资源信号量，其中一个表示空缓冲区的数目，用g_hFullSemaphore表示，其初始值为有界缓冲区的大小SIZE_OF_BUFFER；另一个表示缓冲区中产品的数目，用g_hEmptySemaphore表示，其初始值为0。另外，由于有界缓冲区是一个临界资源，必须互斥使用，所以还需要再设置一个互斥信号量g_hMutex，起初值为1。在生产者/消费者问题中，信号量实现两种功能。首先，它是生产产品和消费产品的计数器，计数器的初始值是可利用的资源数目(有界缓冲区的长度)。其次，它是确保产品的生产者和消费者之间动作同步的同步器。 生产者要生产一个产品时，首先对资源信号量g_hFullSemaphore和互斥信号量g_hMutex进行P操作，申请资源。如果可以通过的话，就生产一个产品，并把产品送入缓冲区。然后对互斥信号量g_hMutex和资源信号量g_hEmptySemaphore进行V操作，释放资源。消费者要消费一个产品时，首先对资源信号量g_hEmptySemaphore和互斥信号量g_hMutex进行P操作，申请资源。如果可以通过的话，就从缓冲区取出一个产品并消费掉。然后对互斥信号量g_hMutex和资源信号量g_hFullSemaphore进行V操作，释放资源。
另外，使我体会最深的是：任何一门知识的掌握，仅靠学习理论知识是远远不够的，要与实际动手操作相结合才能达到功效。短短的课程设计就要结束了，不但对专业知识有了更深的理解，更使自己认识到实践的重要性，理论、实践相结合才能达到很好的学习效果，特别是程序语言的学习。
参考文献
[1] 张尧学等编著.计算机操作系统教程.清华大学出版社,2002.02
[2] 汤子瀛等编著.计算机操作系统.西安电子科技出版社,1996.12
[3] 陈向群编著.操作系统教程.北京大学出版社,2001.07
[4] 郑莉,傅仕星编著.C++语言设计. 北京: 清华大学版社.2000
[5] 严蔚敏,吴伟民编著.数据结构. 北京: 清华大学版社.2002
