Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2010538
  • 博文数量: 505
  • 博客积分: 1552
  • 博客等级: 上尉
  • 技术积分: 2524
  • 用 户 组: 普通用户
  • 注册时间: 2007-09-23 18:24
文章分类

全部博文(505)

文章存档

2019年(12)

2018年(15)

2017年(1)

2016年(17)

2015年(14)

2014年(93)

2013年(233)

2012年(108)

2011年(1)

2009年(11)

分类: C/C++

2013-05-28 08:45:27

首先来看看环形队列的算法(生产者、消费者模式,一个线程入队列,一个线程出队列)

环形队列结构
struct ring_queue
{
    atomic_t head;
    atomic_t tail;
    atomic_t flag;
    int size;
    struct data[size]; //环形队列的数据部分
} queue;
入队列(伪代码表示)
if queue->head == queue->tial && queue->flag == 1 //队列满
return
data[tail] = data
queue->tail = (queue->tail + 1) % queue->size
//设置队列flag
if queue->head == queue->tial
flag = 1  //队列满
队列(伪代码表示)
if queue->head == queue->tial && queue->flag == 0 //队列空
return
data[head] = data
queue->tail = (queue->head + 1) % queue->size
//设置队列flag
if queue->head == queue->tial
flag = 0  //队列空

分析其可能造成的错误(关键在flag)
当入队列线程在设置flag时 读取的 head == tail  且这时出队列也在设置flag 读取的 head == tail ,这时一个将flag置1,一个将flag置0
假设当前队列真实的情况是空,而最终的flag结果却是1 表示队列满, 那么在下一个循环出队列的时候,就认为队列是满的,可以出队列了,但出队列的数据时空的,会造成程序段错误!
假设队列真实情况是满,flag却为0 而在下一个入队列时,认为队列是空,会造成数据覆盖现象的数据丢失!

优化
去掉flag 和flag有关的部分,当head == tail 时,判断下队列中是否有数据, 有则认为满,无则认为空
入队列时 判断队列是否满(伪代码)
if queue->head == queue->tail && queue->data[ (queue->tail + 1) % queue->size] != NULL //判断为满
这里尽量用tail 因为只有入队列能改变tail
出队列 判断队列是否为空
if queue->head == queue->tail && queue->data[ (queue->head + 1) % queue->size] == NULL //判断为空
这里尽量用head 因为只有入队列能改变head
注意:判断队列数据是否为空时,不能判断tail 或者 head所指的内容,因为这里的内容可能正另一个线程修改(非原子操作),
判断下一个或者下下个内容是否为空。不过判断下一个也就够了,因为另一个线程不可能执行的那么快就改变下一个值,而本线程一句语句还没有时间执行。



阅读(829) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册