不用互斥的队列读写操作.doc
文本预览下载声明
一种读写可并发进行的队列的实现方法 HYPERLINK JavaScript:d=document;t=d.selection?(d.selection.type!=None?d.selection.createRange().text:):(d.getSelection?d.getSelection():);void(saveit=window.open(/storeit.aspx?t=+escape(d.title)+u=+escape(d.location.href)+c=+escape(t),saveit,scrollbars=no,width=590,height=300,left=75,top=20,status=no,resizable=yes));saveit.focus();收藏
1 背景目前采用多线程的处理机制中，如下处理方式是比较常见的： 一个线程负责将上游数据放到一个公共队列中，另外一个线程从公共队列中取出数据进行处理。读取操作都需要共用一个互斥量来保证线程安全，这样写数据和取数据的操作实际上是串行的，有些时候，这个操作将对软件处理性能造成一定影响。如果我们能够实现一个队列，读取操作不需要任何互斥量保护就可以保证线程安全，那么读写线程的处理能力将得到明显提高。实际上就是保证队列的读取接口和写入接口之间不存在并发冲突，即一个线程只调用读取接口，一个线程只调用写入接口，这两个线程是不需要进行任何同步动作的；如果多个线程同时调用读取接口或者同时调用写入接口，那么读取接口和写入接口可以用不同的互斥量进行同步；最终达到我们的目的：多个线程中，读取速率不会影响写入的速率，反之亦然。除了读取操作外，很多地方可能还要知道队列的大小，比如内部调试信息，或者实现中需要限制队列的最大容量等，这在读写两个线程都可能用到的，也希望在任意处理线程中不用加锁就可以取到这个信息，这个接口和读写接口都不存在并发冲突的问题，从而提高执行效率。
1 实现方案
需要进行线程同步的操作都是因为大家需要修改（有的线程修改，也有的线程访问）公共资源造成的，只要我们能够保证忘列表中增加一个节点和删除一个节点都不需要都修改同一个资源，而且保证待访问的资源始终有效，那么就可以做到读取操作本身就是线程安全的。
下面是一个列表的简单实现。
struct ListNode
{
int data;
ListNode* next;
}
struct List
{
ListNode* beg;
ListNode* end;
List():beg(0),end(0){}
void push_back(int data)
{
if(!end)
beg = end = new ListNode(node);
else
{
end.next = new ListNode(node);
end = end-next;
}
}
void pop_front()
{
ListNode* top = beg;
beg = beg-next;
delete top;
if(!beg)
end = beg;
}
int front()
{
return beg-data;
}
}
上面的实现，因为增删操作都可能修改内部的beg,end变量，无法做到线程安全的。
如果push_back只修改end变量，pop_front只修改beg变量，那么这两个操作就可以做到线程安全的。如果列表为空的时候beg,end都以空指针来表示，就不可能做到这一点。如果列表为空的时候，beg,end也指向一个固定节点，那么就可能实现这个操作。如下所示：
struct List
{
ListNode* beg;
ListNode* end;
List():beg(new ListNode(0)),end(beg){}
…
}
当插入数据的时候都是用已有的end节点来保存数据，然后在生成一个新的表示结束的节点，如下
void push_back(int data)
{
end.data = data;
end.next = new ListNode(0);
end = end-next;
}
这样在插入数据的时候不需要修改beg变量了。在提取数据的时候也是做类似处理:
void pop_front()
{
if(!empty())
{
ListNode* oldBeg = beg;
beg = beg-next;
显示全部