无锁循环队列新实现：高性能多线程应用优化

需积分: 5 187 浏览量更新于2024-07-09 收藏 644KB PDF 举报

本文档探讨了"Yet Another Implementation of a Lock-Free Circular Array Queue"的主题，由Faustino Frechilla于2015年7月31日发布在CodeProject上。锁-free（无锁）编程是一种在多线程环境中追求高性能和避免死锁的重要技术。在这个特定的实现中，作者提出了一种基于循环数组的无锁队列，它显著减少了内存分配和避免了ABA问题。锁-free数据结构的关键在于设计原子操作，确保并发环境中的线程安全性和高效性。在这个案例中，作者的目标是创建一个队列，当新任务（请求）到来时，能够立即处理而无需等待锁的获取。这在需要高吞吐量和低延迟的应用场景中尤其有用，例如实时网络服务或大规模并发系统。该实现的特点包括： 1. **循环数组设计**：通过利用数组的连续存储空间，避免了传统锁机制中对单个元素的锁定，从而提高了并发性能。 2. **内存管理优化**：不进行堆内存分配，减少内存碎片和上下文切换的成本，有利于提高整体效率。 3. **ABA问题解决**：ABA问题是无锁数据结构中常见的问题，即两个线程可能认为对象状态发生了改变，但实际上只是顺序移动。作者通过某种机制消除了这种不确定性，确保正确性。文章提供了以下关键部分： - **介绍**：阐述了在现代高性能应用中采用多线程的原因，以及如何通过无锁算法提高并发性能。 - **核心原理**：详细介绍了队列的具体实现，包括原子操作的使用和ABA问题的避免策略。 - **代码下载**：读者可以下载包含实现代码的压缩包，以便于理解和测试此无锁队列的性能。阅读这篇文档有助于理解如何在多线程环境下设计和实现高效的无锁数据结构，这对于开发需要高并发性能的系统开发者来说是一项有价值的知识。通过学习本文，开发者可以提升其程序的并发性能，减少竞争条件带来的问题，并为他们的应用程序带来更高的吞吐量和响应速度。

2017/7/22 Yet another implementation of a lock-free circular array queue - CodeProject

https://www.codeproject.com/Articles/153898/Yet-another-implementation-of-a-lock-free-circular 4/19

}

void

queue_enqueue(Queue *q, gpointer data)

{

Node *node, *tail, *next;

node = g_slice_new(Node);

node->data = data;

node->next = NULL;

while (TRUE) {

tail = q->tail;

next = tail->next;

if (tail != q->tail)

continue;

if (next != NULL) {

CAS(&q->tail, tail, next);

continue;

}

if (CAS(&tail->next, null, node)

break;

}

CAS(&q->tail, tail, node);

}

gpointer

queue_dequeue(Queue *q)

{

Node *node, *tail, *next;

while (TRUE) {

head = q->head;

tail = q->tail;

next = head->next;

if (head != q->head)

continue;

if (next == NULL)

return NULL; // Empty

if (head == tail) {

CAS(&q->tail, tail, next);

continue;

}

data = next->data;

if (CAS(&q->head, head, next))

break;

}

g_slice_free(Node, head); // This isn't safe

return data;

}

In those programming languages which don't have a garbage collector (C++ is one of them) latest call to g_slice_free is not safe because of what is known as ABA

problem:

1. Thread T1 reads a value to dequeue and stops just before the first call to CAS in queue_dequeue

2. Thread T1 is preemtped. T2 attempts a CAS operation to remove the same node T1 was about to dequeue

3. It succedes and frees the memory allocated for that node

4. That same thread (or a new one, for instace T3) is going to enqueue a new node. the call to malloc returns the same address that was being used by the node

removed in step 2-3. It adds that node into the queue

5. T1 takes the processor again, the CAS operation succeds incorrectly since the address is the same, but it's not the same node. T1 removes the wrong node



The ABA problem can be fixed adding a reference counter to each node. This reference counter must be checked before assuming the CAS operation is right to avoid the

ABA problem. Good news is the queue this article is about doesn't suffer from the ABA problem, since it doesn't use dynamic memory allocation.

2.3 Dynamic memory allocation

In multithreaded systems, memory allocation must be seriously considered. The standard memory allocation mechanism blocks all the tasks that share the memory

space (all the threads of the process) from reserving memory on the heap when it is allocating space for one task. This is an easy way of doing things, and it works,

there's no way 2 threads can be given the same memory address because they can't be allocating space at the same time. It's quite slow though when threads allocate

memory quite often (and it must be noted that small things like inserting elements into standard queues or standard maps allocate memory on the heap)

There are some libraries out there that override the standard allocation mechanism to provide a lock-free memory allocation mechanism to reduce contention for the

heap, for example libhoard[6]. There are lots of different libraries of this kind, and they can have a great impact in your system if you switch from the standard C++

allocator to one of these lock-free based memory allocators. But sometimes they aren't just what the system needs, and software must go the extra mile and change its

synchronization mechanism. 

3. The circular array based lock-free queue

剩余18页未读，继续阅读

quietqq

粉丝: 1
资源: 77

无锁循环队列新实现：高性能多线程应用优化

APS013_The-Implementation-of-Two-Way-Ranging-with-the-DW1000_v2.3.pdf

lock-free circular array queue.

V.-(pp-25-28)--ABDUL-Manan_-Implementation-of-Ima_verilog image

Implementation-of-DVFS-on-Blackfin-Processor.rar_Task Scheduli

BP神经网络的matlab实现-matlab-implementation-of-BP-neural-networks.zipp

arcgis-pro-implementation-guide.pdf

SSA-BP网络的matlab实现_matlab-implementation-of-SSA-BP-network.zip

Implementation-of-OFDM-system-using-IFFT-and-FFT._OFDM FFT IFFT_

zk2013#The-design-and-implementation-of-a-64-bit-operating-syste

org.osgi.namespace.implementation-1.0.0.jar

最新资源