|
|
Boost : |
From: Dan W. (danw_at_[hidden])
Date: 2003-12-29 19:55:01
Warning: un-tested. Might make a nice addition to the thread library. If
there's any interest in it, I could use some advice on how to test it properly.
In short, this is like a thread safe, alloc-free producer/consumer, shallow
but wide, two-way buffer. Should be very efficient and portable, since it does
not make use of locks or mutexes, and since it avoids
allocation/de-allocation by re-using the two same buffers. The buffer type
is generic (<T>).
Inherently portable, as it uses no platform specific threading mechanisms
whatsoever.
Usage: Create a class for the buffer type wanted, inheriting from abstract
buffer.
Call create_double_buffer<my_buff_t>( new my_buff_t, new my_buff_t ), to
allocate a double buffer on the heap. Optionally feed the returned address
to a smart pointer.
The producer can now call pmy_buff->checkout_buff(), and get a
shared_ptr<my_buff_t>. The producer can now write to this buffer via the
shared_ptr.
Once done, it simply lets the shared_ptr go out of scope. This triggers a
mechanism (via custom deleter calling double_buffer::operator()()) that moves
the buffer along from the producer checkout and makes it available to the
consumer.
The consumer uses an exactly symetrical function 'checkout_data'.
There are two buffers moving around a 6-position 'ring'.
Anyways, the comments get pretty graphic towards the bottom of the file.
Sorry to just paste the code below, I have no web-space readily available;
specially now when everybody here is on holidays. Read on...
#ifndef DOUBLE_BUFFER_HPP
#define DOUBLE_BUFFER_HPP
/*
Pattern "double buffer" is intended as a simple and
fast inter-thread data exchange solution. It allows
a producer and a consumer to exchange fixed-size data
buffers. Two such buffers are managed such that the
producer and consumer may simultaneously be working
to/from either buffer, or such that that one buffer
is being processed while the other waits, or such that
both buffers are in waiting --whether one waiting
for each thread, or the two waiting for one thread.
Its speed stems from the fact that thread safety is
achieved without the use of locks or mutexes, and
from the fact that the buffers are re-used, rather
than repeatedly allocated/de-allocated.
Finally, the fact that it uses no platform-specific
threading mechanisms, makes it inherently portable.
Note also that since only pointer variables to the
template type are instantiated, compiler optimization
should reduce generated template instances to a single
instance of the double_buffer class code.
The free function 'create_double_buffer' allocates the
instance on the heap and returns a pointer. This makes
it convenient for assigning that pointer to shared_ptr
objects held by the producer and consumer, such that
when they go out of scope, their commonly owned double
buffer is deallocated.
Note that, although we speak of 'producer'/'consumer',
the pattern is symmetrical: --i.e. the consumer can
just as well write to the buffers it receives before
returning them and the 'producer' may read them prior
to writing to them.
*/
#include <smart_ptr.hpp>
namespace boost
{
namespace dbf
{
/////////////////////////////////////////////////////////
//Class buffer allows polymorphic pointers to buffers;
//and prevents accidental deletion of the buffers by
//the delete shared_ptr<T>.get(). All you have to do is
//to derive your buffer from (abstract) buffer, e.g.:
// struct my_buff : public boost::dbf::buffer
// { char zzz[666];
// void erase(){ for(int i(666);i--;) zzz[i]=0; }
// }; //that's if you *want* to erase prior to producer
//checkout, each time; otherwise.. void erase(){}.
/////////////////////////////////////////////////////////
class buffer
{
buffer( buffer const &); //no copying
buffer & operator=( buffer const &);
protected:
~buffer(){}
public:
buffer(){}
void erase(){ erase_(); }
private:
virtual void erase_() = 0;
};
/////////////////////////////////////////////////////////
//Class double_buffer<T> is the main one here. T is the type of
//of your buffer class, e.g.: my_buff, as per example above.
//The two "checkout" public functions are what matters to ya...
//The producer checks-out buffers and releases data; the con-
//sumer checks-out data and releases a buffer. Data is short
//for 'buffer with valid data', while Buffer means plain, raw
//buffer. The functions return empty shared_ptr<T>'s if data or
//buffers aren't available, respectively, at time of call.
/////////////////////////////////////////////////////////
template< typename T >
class double_buffer
{
public:
typedef shared_ptr<buffer> pbuff_t;
~double_buffer(){}
pbuff_t checkout_data(){ return checkout_data_(); }
pbuff_t checkout_buff(){ return checkout_buff_(); }
private:
virtual pbuff_t checkout_data_() = 0;
virtual pbuff_t checkout_buff_() = 0;
};
/////////////////////////////////////////////////////////
//use this stand-alone function to create a double-buffer;
//you must allocate the buffers; double_buffer will delete
//them in its destructor.
/////////////////////////////////////////////////////////
template< typename T >
double_buffer<T> * create_double_buffer( T * pbuf1, T * pbuf2 );
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// DETAILS FOLLOW...
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//double_buffer's implementation:
template< typename T >
class db_impl : public double_buffer<T>
{
db_impl & operator=(db_impl const &);
db_impl(db_impl const &); db_impl();
public:
~db_impl();
db_impl( T * pbuf1, T * pbuf2 );
void operator()(T * released);
private:
void reset();
pbuff_t checkout_data_();
pbuff_t checkout_buff_();
T * volatile arr[6];
T * const pbuf1_;
T * const pbuf2_;
};
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
template< typename T > //free-standing create f'n
double_buffer<T> * create_double_buffer( T * pbuf1, T * pbuf2 )
{
return new db_impl<T>( pbuf1, pbuf2 );
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
template< typename T > //reset
void db_impl<T>::reset()
{
for(int i = 0; i < 6; ++i) arr[i] = 0;
pbuf2_->erase();
pbuf1_->erase();
arr[5] = pbuf2_;
arr[0] = pbuf1_;
if( arr[0] == 0 ) //see notes below
{
arr[0] = pbuf2_;
arr[5] = 0;
}
}
template< typename T > //ctor
db_impl<T>::db_impl
(
T * pbuf1,
T * pbuf2
)
: arr()
, pbuf1_(pbuf1)
, pbuf2_(pbuf2)
{
assert( pbuf1_ && pbuf2_ );
reset();
}
template< typename T > //dtor
db_impl<T>::~db_impl()
{
assert( arr[1]==0 && arr[4]==0 );
delete pbuf2_;
delete pbuf1_;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/* checkout_buff_(), checkout_data_(), and operator()()
constitute the core functionality and implement all
the thread-safety tricks. Two 'tokens' (pointers) are
moved around T * arr[6]: a ruby-shaped circuit where
two of the positions are checkout positions, and the
other four are 'waiting' positions, as follows:
[0] [5]
Buffer waiting Buffer waiting
[1] [4]
Producer checkout Consumer checkout
[2] [3]
Data waiting Data waiting
The tokens circulate counter-clock-wise. The producer
can copy a token from positions 0 or 5 to position 1,
and can clear positions 0 or 5, but not set them.
Once it has moved a token to position 1, it can use
the buffer it points to. When finished, the token in
1 is moved to 3, if 3 is clear, or to 2 otherwise.
The producer can set, but not clear, positions 2 and
and 3; unless 3 is free on second check. The consumer
can copy a token from positions 3 or 2 to position 4,
and can clear positions 3 or 2, but not set them.
Once it has moved a token to position 4, it can use
the data it points to. When finished, the token in
4 is moved to 0, if 0 is clear, or to 5 otherwise.
The consumer can set, but not clear, positions 5 and
and 0; unless 0 is free on second check, in which
rare case it will move 5 to 0 and clear 5, very, very
carefully... Some of the conditionals may appear to
be redundant; --they have to be so to be thread-safe.
Almost forgot, when consumer is done with data, it
first calls user function erase() on it.
Note that the checkout functions return shared_ptr<>
objects, which it initializes with "this" in ctor's
second argument...
When the client (producer or consumer) is done with
the buffer (shared_ptr<>'s go out of scope) the last
shared_ptr calls this->operator()(T*), like a custom
deleter. Operator()(), rather than free the memory,
simply moves the token along the circuit. At first it
does not know whether it's a return of a data-filled
buffer, or a used buffer. It finds out by comparing
the address released to those present in positions 1
and 4. This is safe to do.
*/
template< typename T > //producer checkout
double_buffer<T>::pbuff_t db_impl<T>::checkout_buff_()
{
T * the_buffer = 0;
assert( ! arr[1] );
if( ! arr[2] )
{
arr[1] = arr[0];
the_buffer = arr[1];
if( arr[0] && arr[5] )
{
arr[0] = arr[5];
arr[5] = 0;
}
else
{
arr[0] = 0;
}
}
return pbuff_t( the_buffer, this );
}
template< typename T > //consumer checkout
double_buffer<T>::pbuff_t db_impl<T>::checkout_data_()
{
T * the_buffer = 0;
assert( ! arr[4] );
if( ! arr[5] )
{
arr[4] = arr[3];
the_buffer = arr[4];
if( arr[3] && arr[2] )
{
arr[3] = arr[2];
arr[2] = 0;
}
else
{
arr[3] = 0;
}
}
return pbuff_t( the_buffer, this );
}
template< typename T > //"deleter" (moves token along)
void db_impl<T>::operator()(T * released)
{
assert( released );
if( released == arr[1] ) //if a producer release
{
if( arr[3] )
arr[2] = released;
else arr[3] = released;
if( !arr[3] && arr[2] )
{
arr[2] = 0;
arr[3] = released;
}
arr[1] = 0;
}
else //ought to be a consumer release (arr[4])
{
assert( released == arr[4] );
arr[4]->erase(); //clears buffer
if( arr[0] ) arr[5] = released;
else arr[0] = released;
if( !arr[0] && arr[5] )
{
arr[5] = 0;
arr[0] = released;
}
arr[4] = 0;
}
}
}
}
#endif
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk