我们正在开发一个基于C/S的网络应用程序,我们发现有太多的锁添加到std :: map,服务器的性能变差了.
我想知道是否有可能实现无锁地图,如果有,怎么样？那里有开源代码吗？
编辑:实际上我们使用std :: map来存储套接字信息,我们根据套接字文件描述进行了封装,以包含一些其他必要的信息,如ip地址,端口,套接字类型,tcp或udp等.
总结一下,我们有一张全球地图说它是
map<int fileDescriptor, socketInfor*> SocketsMap,
那么每个用于发送数据的线程都需要访问SocketsMap,并且他们必须在从SocketsMap读取或写入SocketsMap之前添加互斥锁,因此整个应用程序的并发级别会因为添加到SocketsMap的锁定而大大减少.
为了避免并发级问题,我们有两个解决方案:1.分别存储每个socketInfor*2.使用某种无锁映射.
我想找到某种无锁映射,因为此解决方案所需的代码更改远小于解决方案1所需的代码更改.
什么时候可以保证64位写入是原子的,在基于Intel x86的平台上用C编程时(特别是使用英特尔编译器运行MacOSX 10.4的基于Intel的Mac)？例如:
unsigned long long int y;
y = 0xfedcba87654321ULL;
/* ... a bunch of other time-consuming stuff happens... */
y = 0x12345678abcdefULL;
如果另一个线程在y的第一次赋值完成后检查y的值,我想确保它看到值0xfedcba87654321或值0x12345678abcdef,而不是它们的某些混合.我想这样做没有任何锁定,如果可能的话没有任何额外的代码.我希望在使用64位编译器(64位Intel编译器)时,在能够支持64位代码的操作系统(MacOSX 10.4)上,这些64位写入将是原子的.这总是如此吗？
在内核端很容易设置内存障碍:由于Linux内核头文件,宏mb,wmb,rmb等总是存在.
如何在用户端完成此操作？
x86和其他体系结构提供了特殊的原子指令(lock,cmpxchg等),允许您编写"无锁"数据结构.但随着越来越多的内核被添加,似乎这些指令实际上必须在幕后进行的工作将会增长(至少是为了保持缓存一致性？).如果原子添加在双核系统上今天需要大约100个周期,那么未来的80多个核心机器上可能需要更长的时间吗？如果您要将代码编写为最后一个,那么即使它们今天变慢,使用锁实际上是否更好？
我正在寻找一种方法来实现支持单个生产者和多个消费者的无锁队列数据结构.我看过Maged Michael和Michael Scott(1996)的经典方法,但他们的版本使用链表.我想要一个使用有界循环缓冲区的实现.什么东西使用原子变量？
另外,我不确定为什么这些经典方法是为需要大量动态内存管理的链表设计的.在多线程程序中,所有内存管理例程都是序列化的.我们不是通过将它们与动态数据结构结合使用来破坏无锁方法的好处吗？
我试图在英特尔64位架构上使用pthread库在C/C++中编写代码.
谢谢Shirish
我最近阅读了Paul McKenney的2010年白皮书"内存障碍:软件黑客的硬件视图".
我非常感谢关于下面给出的一小部分C代码的反馈/评论/指导,这些代码实现了M&S队列排队功能,特别是在内存和编译器障碍方面.
此代码使用指针计数器对来处理ABA,并且为了这篇文章,应该被认为是为x86/x64编写的.
对于这篇文章,内联评论现在都写完了,并且是这篇文章的一部分,因为它们表达了我现在的想法.
为简洁起见,我在结构中删除了断言代码和缓存行填充等.
目前,我认为代码很破碎,但我想确保我认为正确的原因.
#define PAC_SIZE 2
struct lfds_queue_element
{
struct lfds_queue_element
*volatile next[PAC_SIZE];
void
*user_data;
};
struct lfds_queue_state
{
struct lfds_queue_element
*volatile enqueue[PAC_SIZE];
struct lfds_queue_element
*volatile dequeue[PAC_SIZE];
atom_t volatile
aba_counter;
};
void lfds_queue_internal_dcas_pac_enqueue( struct lfds_queue_state *lqs, struct lfds_queue_element *lqe )
{
ALIGN(ALIGN_DOUBLE_POINTER) struct lfds_queue_element
*local_lqe[PAC_SIZE], *enqueue[PAC_SIZE], *next[PAC_SIZE];
unsigned char cas_result = 0;
unsigned int backoff_iteration = 1;
/* TRD : here we have been passed a new element to place
into the …我想知道是否有可能为任何"常见"架构(如x64或ARMv7/ARMv8)创建无锁,线程安全的共享指针.
在cppcon2014上关于无锁编程的讨论中,Herb Sutter提出了一个无锁定单链表的(部分)实现.实现看起来很简单,但它依赖于shared_ptr标准库中不存在或使用专用std::atomic...函数的原子实现.这一点尤为重要,因为单个push/pop调用可能会调用多个原子加载/存储和compare_exchange操作.
我看到的问题(我认为谈话中的一些问题是朝着相同的方向)是因为这是一个实际的无锁数据结构,那些原子操作本身就必须是无锁的.我不知道任何标准库实现std::atomic...的无锁功能 - 至少有一个简短的google/SO搜索 - 我也没有找到如何实现无锁专业化的建议std::atomic<std::shared_ptr>.
在我浪费时间之前,我想问:
std::atomic<std::shared_ptr>？对于所提到的队列,它尤其需要CAS操作.供参考,这里是来自Herb Sutter的代码(可能包含来自我的错别字):
template<class T>
class slist {
struct Node { T t; std::shared_ptr<Node> next; };
std::atomic<std::shared_ptr<Node>> head;
public:
class reference{
std::shared_ptr<Node> p;
public:
reference(std::shared_ptr<Node> p_){}
T& operator*(){ return p->t; }
T* operator->(){ return &p->t; }
};
auto find(T t) const {
auto p = head.load();
while …我正在为密集型网络应用程序实现无锁单生成器单个使用者队列.我有一堆工作线程在他们自己的队列中接收工作,然后他们出列并处理.
从这些队列中删除锁已经大大提高了高负载下的性能,但是当队列为空时它们不再阻塞,这反过来导致CPU使用率急剧上升.
如何有效地导致线程阻塞,直到它成功出列或被杀/中断为止？
我正在尝试编写一个无锁的单链表.最终的一致性不是问题(有人遍历可能包含不正确项目的列表).
我认为我得到了正确的添加项目(循环和Interlocked.CompareExchange).
但我无法弄清楚如何删除节点(列表中的任何位置),因为我必须得到前一个项目并将它们的Next字段设置为当前节点Next字段.
class Node
{
Node Next;
object Value;
}
class SinglyLinkedList
{
Root _root;
public void Add(object value)
{}
public void Remove(object value)
{}
}
即
a - > b - > c
至
a - > c
伪代码:
Node prev;
Node node = _root;
while (node.Value != nodeValue)
{
prev = node;
node = node.Next;
}
prev.Next = node.Next;
我如何使这成为一个原子操作(即确保prev.Next = node.Next调用没有next或prev被另一个线程删除)？
我可以使用ReaderWriterLockSlim,但我发现这个问题很有趣,因为我知道存在无锁链表.
我的担忧:
如果当前线程在循环和赋值之间挂起,则会发生以下情况:
prev 本身可能已被另一个线程删除. …是否存在实现IList的无锁且线程安全的数据结构？
当然,无锁是指一种实现,它不使用.NET中的锁定原语,而是使用互锁操作/原子操作来实现线程安全......没有一个,显然在并发数据结构下......
有没有人见过一个漂浮？
我见过一个用氨基-cbbs实现的java 文件,名为LockFreeVector但到目前为止还没有用于.NET.有任何想法吗？