Linux线程编程之生产者消费者问题_linux生产者消费者问题 - CSDN文库

生产者消费者问题

87 浏览量更新于2023-03-03 评论收藏 497KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

Linux线程编程之生产者消费者问题线程编程之生产者消费者问题

　　前言

　　本文基于顺序循环队列，给出Linux生产者/消费者问题的多线程示例，并讨论编程时需要注意的事项。文中涉及的代码运

行环境如下：

　　本文假定读者已具备线程同步的基础知识。

　　一顺序表循环队列

　　1.1 顺序循环队列定义

　　队列是一种运算受限的先进先出线性表，仅允许在队尾插入(入队)，在队首删除(出队)。新元素入队后成为新的队尾元

素，元素出队后其后继元素成为队首元素。

　　队列的顺序存储结构使用一个数组和两个整型变量实现，其结构如下：

　　1 struct Queue{

　　2 ElemType elem[MaxSize];

　　3 int head， tail;

　　4 };

　　即利用数组elem顺序存储队列中的所有元素，利用整型变量head和tail分别存储队首元素和队尾(或队尾下一个)元素的下

标位置，分别称为队首指针和队尾指针。MaxSize指定顺序存储队列的大长度，即队列中多能够存储的元素个数。当队列的顺

序存储空间静态分配时，MaxSize通常为宏定义；若动态分配时，还可为全局或局部变量。

　　单向顺序队列存在“假溢出”问题，即多次入队和出队操作后，队首空余许多位置而队尾指针指向队列中后一个元素位置，

从而无法使新的数据元素入队。假溢出本质在于队首和队尾指针值不能由所定义数组下界值自动转为数组上界值，解决办法是

将顺序队列构造成一个逻辑上首尾相连的循环表。当队列的第MaxSize-1个位置被占用后，只要队首还有可用空间，则把新的

数据元素插入队列第0号位置。因此，顺序队列通常都采用顺序循环队列结构。

　　下图所示为MaxSize=4的循环队列三种状态图：

　　其中，为区分队空与队满，在入队时少用一个数据(图中下标为3的位置)。本文约定队首指针head指向队首元素，队尾指

针tail指向队尾元素的下一个元素，以队尾指针加1等于队首指针判断队满，即：

　　初始化：head = tail = 0；

　　队列空：head == tail；

　　队列满：(tail + 1) % MaxSize == head；

　　元素数：num = (tail – head + MaxSize) % MaxSize

　　%为取模运算符，循环队列利用数学上的取模运算将首尾巧妙相连。

　　当约定head指向队首前一个元素，tail指向队尾元素时，元素数目仍满足上面的公式。当约定head指向队首元素，tail指向

队尾元素时，元素数目为(tail – head + 1 + MaxSize) % MaxSize。

　　此外，也可另设一个标志以区别队空和队满。该标志可为布尔型空满标志位，也可为队列中元素个数。

　　通过队首元素位置和队列中元素个数，可计算出队尾元素所在位置。亦即，可用队列中元素个数代替队尾指针(或队首指

针)。此时，队列满足：

　　队列空：num == 0；

　　队列满：num == MaxSize；

　　队尾位置：tail = (head + num + MaxSize) % MaxSize

　　1.2 顺序循环队列实现

　　本节将采用C语言实现一个简单但却标准的顺序循环队列函数集。

　　首先定义循环队列结构如下：

　　1 #define QUEUE_SIZE 5 //队列大容纳QUEUE_SIZE-1个元素

　　2 typedef struct{

　　3 int aData[QUEUE_SIZE]; //队列元素

　　4 int dwHead; //指向队首元素

　　5 int dwTail; //指向队尾元素的下一个元素

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余7页未读，立即下载

评论0

weixin_38516386

粉丝: 5
资源: 899

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈