随笔-3  评论-5  文章-13  trackbacks-0

--------------------------------------------------------------------------------
标题: 一读一写情况下,无锁队列如何实现?
作者: 叶飞虎
日期: 2009.03.09
--------------------------------------------------------------------------------

   一读一写情况下,无锁队列如何实现?其实并不难,先说说一读一写无锁队列的实际应
用吧。读写队列最大的应用是:一个线程收到事件或消息后直接加入到队列,而处理线程读
取队列中的事件或消息,并加以处理。在这个模式中,有一个线程负责写,多个处理线程读
自己的队列并处理。虽然看起来象是一写多读,其实不然,针对某一事件队列而言,只有一
个线程是写一个线程是读。

   此示例可以封装成一个Queue类,在KYLib中有TKYQueue类,其实现原理相同。代码示例
如下:

 

 1 // 链接数据项结构
 2 typedef struct TLinkItem
 3 {
 4    void*       Data;
 5    TLinkItem*  Next;
 6 *PLinkItem;
 7 
 8 TLinkItem*     FLinkHead;        // 队列头
 9 TLinkItem*     FLinkTail;        // 队列尾
10 
11 // 初始化队列
12 void InitQueue()
13 {
14    // 分配队列头项
15    FLinkTail = NULL;
16    FLinkHead = new TLinkItem;
17 
18    // 保证 Head 和 Tail 非空, 是一个线程读一个线程写的关键!
19    if (FLinkHead != NULL)
20    {
21       // 初始化队列头
22       FLinkHead->Data = NULL;
23       FLinkHead->Next = NULL;
24       FLinkTail       = FLinkHead;
25    }
26    else
27       throw;
28 }
29 
30 // 加入
31 bool Push(void* AData)
32 {
33    // 初始化
34    bool        result = false;
35    TLinkItem*  pItem  = new TLinkItem;
36 
37    // 加入队列
38    if (pItem != NULL)
39    {
40       // 写值
41       pItem->Data     = AData;
42       pItem->Next     = NULL;
43 
44       // 加到末尾
45       FLinkTail->Next = pItem;
46       FLinkTail       = pItem;
47 
48       // 返回结果
49       result = true;
50    }
51 
52    // 返回结果
53    return result;
54 }
55 
56 // 取出
57 void* Pop()
58 {
59    // 初始化
60    void* result = NULL;
61 
62    // 读取项
63    if (FLinkHead->Next != NULL)
64    {
65       // 取值
66       TLinkItem* pItem = FLinkHead;
67       FLinkHead        = FLinkHead->Next;
68       result           = FLinkHead->Data;
69 
70       // 释放项
71       delete pItem;
72    }
73 
74    // 返回结果
75    return result;
76 }
77 

 

posted on 2011-05-22 11:31 Kyee Ye 阅读(1528) 评论(3)  编辑 收藏 引用 所属分类: 技巧杂集

评论:
# re: 一读一写情况下,无锁队列如何实现? 2011-07-04 07:58 | jwchen
// 加到末尾
45 FLinkTail->Next = pItem;
46 FLinkTail = pItem;

你的队列不支持多线程同时enque 和deque的,当尾部指针被删除的时候,上面这句就报异常了。  回复  更多评论
  
# re: 一读一写情况下,无锁队列如何实现? 2011-07-04 08:25 | Kyee
一读一写无锁队列的前提是:push 时只能一个线程, 同时可以 pop 时另外一个线程。  回复  更多评论
  
# re: 一读一写情况下,无锁队列如何实现?[未登录] 2011-08-20 21:14 | 路人甲
一读一写如果是不同的线程,也是有问题的,你没考虑到中间的线程切换。所以这个代码发生bug的概率很小,但不表示不发生。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理