C++ boost::lockfree::queue
Description:
//atomic operation needed for queue
boost::atomic_int producer_count(0);
boost::atomic_int consumer_count(0);
boost::lockfree::queue<int> queue(128);
void producer(void)
{
for (int i = 0; i != 1000; ++i) {
int value = ++producer_count;
while (!queue.push(value))
;
}
}
boost::atomic<bool> done (false);
void consumer(void)
{
int value;
while (!done) {
while (queue.pop(value))
++consumer_count;
}
while (queue.pop(value))
++consumer_count;
}
int main()
{
using namespace std;
cout << "boost::lockfree::queue is ";
if (!queue.is_lock_free())
cout << "not ";
cout << "lockfree" << endl;
//creating producer and consumer thread
boost::thread_group thread1, thread2;
// we can observe that queue storage limit is 128
// but we are pushing the 1000 values
for (int i = 0; i != 4; ++i)
thread1.create_thread(producer);
for (int i = 0; i != 4; ++i)
thread2.create_thread(consumer);
thread1.join_all();
done = true;
thread2.join_all();
cout << "produced " << producer_count << " objects." << endl;
cout << "consumed " << consumer_count << " objects." << endl;
}
The boost :: lockfree concept is concurrent data structure (non-blocking structure) which is implemented with thread.
The data structure is lockfree when some concurrent operations are guaranteed to be finished in a finite number of
steps.But using lockfree program is difficult task in practical application .there are some restrictions ,the relevant aspects for the implementation of boost::lockfree are number of producer and consumer .apart from lockfree there
are other two concurrent data structure which are wait-free and obstruction free
explanation:
There are single or multiple producers and single or mulitple consumers.
Disadvantage : it cant be used in every circumstances it is risk taking .therefore for most of the use case it is not the best choice
Advantage: Lockfree data structure will be a better choice in order to optimize the latency of a system or to avoid
priority inversion which is necessary in real time application
header files:
1. <boost/lockfree/queue> : for a lockfree multi-producer/ multi-consumer queue
2.<boost/lockfree/stack>: for a lockfree multi-producer/ multi-consumer stack
3.<boost/lockfree/spsc_queue> : a wait free single- produce/single consumer queue .it is also known as ring buffer
Data structure boost parameters :
1.boost::lockfree::fixedsize : The internal nodes are stored inside an array and they are addressed by array indexing. This limits the possible size of the queue to the number of elements that can be addressed by the index type , but on platforms that lack double-width compare-and-exchange instructions, this is the best way to achieve lock-freedom
2.boost::lockfree::capacity : sets the capacity of a data structure at compile -time
3.boost::lockfree::allocator :Defines the allocator.
boost.lockfree supports stateful allocator and is compatible with Boost. Interprocess allocatorsSources or reasons for blocking behavior:
Atomic operations: some architectures do not provide atomic operations in natively in hardware there are also known as spinlocks
Memory allocations: allocating memory from operating system is not lock free .it uses a memory pool to allocate
the internal node ,if the memory is pool is exhausted then the new node is taken from operating system,then it create such situations
Exception handling: exception handling does not encourage the real time behavior so it is not encouraged with lockfree
Constructor:
queue(void): it constructs the queue
Member functions:
bool is_lock_free(void) const: it only checks the queue head or tail nodes and the freelist can be modified
in a lockfree manner ,it returns true if implementation is lockfreebool empty(void) const: to check that queue is empty or not ,it returns true is queue is empty
bool push(T const & t): it pushes the object t in the queue
bool pop(T & ret) : it pops the object t from the queue
Program:
//atomic operation needed for queue
boost::atomic_int producer_count(0);
boost::atomic_int consumer_count(0);
boost::lockfree::queue<int> queue(128);
void producer(void)
{
for (int i = 0; i != 1000; ++i) {
int value = ++producer_count;
while (!queue.push(value))
;
}
}
boost::atomic<bool> done (false);
void consumer(void)
{
int value;
while (!done) {
while (queue.pop(value))
++consumer_count;
}
while (queue.pop(value))
++consumer_count;
}
int main()
{
using namespace std;
cout << "boost::lockfree::queue is ";
if (!queue.is_lock_free())
cout << "not ";
cout << "lockfree" << endl;
//creating producer and consumer thread
boost::thread_group thread1, thread2;
// we can observe that queue storage limit is 128
// but we are pushing the 1000 values
for (int i = 0; i != 4; ++i)
thread1.create_thread(producer);
for (int i = 0; i != 4; ++i)
thread2.create_thread(consumer);
thread1.join_all();
done = true;
thread2.join_all();
cout << "produced " << producer_count << " objects." << endl;
cout << "consumed " << consumer_count << " objects." << endl;
}
output:
Real time examples:
Lamport's "Concurrent Reading and Writing"
-CACM 20(11), 1977, describes a non-blocking buffer
- limitations on number of concurrent writer
-lots of user-level music software uses lockfree data structures
Comments