1.. _Concurrent_Queue_Classes:
2
3Concurrent Queue Classes
4========================
5
6
7Template class ``concurrent_queue<T,Alloc>`` implements a concurrent
8queue with values of type ``T``. Multiple threads may simultaneously
9push and pop elements from the queue. The queue is unbounded and has no
10blocking operations. The fundamental operations on it are ``push`` and
11``try_pop``. The ``push`` operation works just like ``push`` for a
12std::queue. The operation ``try_pop`` pops an item if it is available.
13The check and popping have to be done in a single operation for sake of
14thread safety.
15
16
17For example, consider the following serial code:
18
19
20::
21
22
23           extern std::queue<T> MySerialQueue;
24           T item;
25           if( !MySerialQueue.empty() ) {
26               item = MySerialQueue.front();
27               MySerialQueue.pop_front();
28               ... process item...
29           }
30
31
32Even if each std::queue method were implemented in a thread-safe manner,
33the composition of those methods as shown in the example would not be
34thread safe if there were other threads also popping from the same
35queue. For example, ``MySerialQueue.empty()`` might return true just
36before another thread snatches the last item from ``MySerialQueue``.
37
38
39The equivalent thread-safe |full_name| code is:
40
41
42::
43
44
45           extern concurrent_queue<T> MyQueue;
46           T item;
47           if( MyQueue.try_pop(item) ) {
48               ...process item...
49           }
50
51
52In a single-threaded program, a queue is a first-in first-out structure.
53But if multiple threads are pushing and popping concurrently, the
54definition of "first" is uncertain. Use of ``concurrent_queue``
55guarantees that if a thread pushes two values, and another thread pops
56those two values, they will be popped in the same order that they were
57pushed.
58
59
60Template class ``concurrent_queue`` is unbounded and has no methods that
61wait. It is up to the user to provide synchronization to avoid overflow,
62or to wait for the queue to become non-empty. Typically this is
63appropriate when the synchronization has to be done at a higher level.
64
65
66Template class ``concurrent_bounded_queue<T,Alloc>`` is a variant that
67adds blocking operations and the ability to specify a capacity. The
68methods of particular interest on it are:
69
70
71-  ``pop(item)`` waits until it can succeed.
72
73
74-  ``push(item)`` waits until it can succeed without exceeding the
75   queue's capacity.
76
77
78-  ``try_push(item)`` pushes ``item`` only if it would not exceed the
79   queue's capacity.
80
81
82-  size() returns a *signed* integer.
83
84
85The value of concurrent_queue::size() is defined as the number of push
86operations started minus the number of pop operations started. If pops
87outnumber pushes, ``size()`` becomes negative. For example, if a
88``concurrent_queue`` is empty, and there are ``n`` pending pop
89operations, ``size()`` returns -\ ``n``. This provides an easy way for
90producers to know how many consumers are waiting on the queue. Method
91``empty()`` is defined to be true if and only if ``size()`` is not
92positive.
93
94
95By default, a ``concurrent_bounded_queue`` is unbounded. It may hold any
96number of values, until memory runs out. It can be bounded by setting
97the queue capacity with method ``set_capacity``.Setting the capacity
98causes ``push`` to block until there is room in the queue. Bounded
99queues are slower than unbounded queues, so if there is a constraint
100elsewhere in your program that prevents the queue from becoming too
101large, it is better not to set the capacity. If you do not need the
102bounds or the blocking pop, consider using ``concurrent_queue`` instead.
103
104.. toctree::
105   :maxdepth: 4
106
107   ../tbb_userguide/Iterating_Over_a_Concurrent_Queue_for_Debugging
108   ../tbb_userguide/When_Not_to_Use_Queues