File SPSCQueue.h

↰ Parent directory (ADS/concurrent)

A bounded queue between one producer thread and one consumer thread, lock-free and wait-free, beyond the book: the circular vector of the queue of section 4.3.3 [see File ArrayQueue.h], whose head only the consumer writes and whose tail only the producer writes, so that each index is an atomic with the release and acquire orders and no lock is needed (the queue of Lamport).

Definition (ADS/concurrent/SPSCQueue.h)

Detailed Description

Each thread keeps a copy of the index of the other one, read again only when the queue looks full or empty, and the two indices and the two copies sit on four lines of cache of their own, grouped in pairs of lines so that a thread that spins on a full or empty queue, rewriting its copy, does not invalidate the line that the other one writes or reads (false sharing, also through the prefetch of the adjacent line); a consumer that finds the queue empty asks for the line of its next place before it reads the tail again, so that, when the item has come, the two lines travel together and a round trip between the threads costs one miss a side instead of two in a row; a consumer whose last pop took an item and that finds fewer than min( 64 , capacity / 2 ) new ones waits 64 pauses of the processor for a batch before it takes them (the backtracking of B-Queue), while after a pop that found nothing it takes at once what comes, so that a single item after a silence costs no wait; the places are raw memory with a line of padding at each end, so that the first and the last items share no line with other data. The capacity is a power of 2 and the indices are reduced by a mask.

The contracts [see File Contract.h]: the capacity is a power of 2, at least 2; only one thread calls push() and only one calls pop(). The operations are defined in SPSCQueue.tpp.

  1. Lamport, Specifying concurrent program modules, ACM Transactions on Programming Languages and Systems 5(2), 190-222, 1983, doi:10.1145/69624.357207

      1. Lee, T. Bu, G. Chandranmenon, A lock-free, cache-efficient multi-core synchronization mechanism for line-rate network traffic monitoring, IEEE International Symposium on Parallel and Distributed Processing (IPDPS), 1-12, 2010, doi:10.1109/IPDPS.2010.5470368 (the copies of the indices)

  1. Wang, K. Zhang, X. Tang, B. Hua, B-Queue: efficient and practical queuing for fast core-to-core communication, International Journal of Parallel Programming 41(1), 137-159, 2013, doi:10.1007/s10766-012-0213-x (the wait for a batch)

Intel 64 and IA-32 Architectures Optimization Reference Manual, the spatial prefetcher that fetches the pairs of lines of 128 bytes, https://www.intel.com/content/www/us/en/content-details/ 671488/intel-64-and-ia-32-architectures-optimization-reference- manual-volume-1.html

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes