SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef CDSLIB_ALGO_FLAT_COMBINING_KERNEL_H
of a <i>publication list</i>. The publication list is a list of thread-local records
of a size proportional to the number of threads that are concurrently accessing the shared object.
- Each thread \p t accessing the structure to perform an invocation of some method \p m
+ Each thread \p t accessing the structure to perform an invocation of some method \p f()
on the shared object executes the following sequence of steps:
<ol>
- <li>Write the invocation opcode and parameters (if any) of the method \p m to be applied
+ <li>Write the invocation opcode and parameters (if any) of the method \p f() to be applied
sequentially to the shared object in the <i>request</i> field of your thread local publication
record (there is no need to use a load-store memory barrier). The <i>request</i> field will later
be used to receive the response. If your thread local publication record is marked as active
<li>Check if the global lock is taken. If so (another thread is an active combiner), spin on the <i>request</i>
field waiting for a response to the invocation (one can add a yield at this point to allow other threads
on the same core to run). Once in a while while spinning check if the lock is still taken and that your
- record is active. If your record is inactive proceed to step 5. Once the response is available,
- reset the request field to null and return the response.</li>
+ record is active (you may use any of \p wait_strategy instead of spinning). If your record is inactive proceed to step 5.
+ Once the response is available, reset the request field to null and return the response.</li>
<li>If the lock is not taken, attempt to acquire it and become a combiner. If you fail,
return to spinning in step 2.</li>
<li>Otherwise, you hold the lock and are a combiner.
<ul>
<li>Increment the combining pass count by one.</li>
<li>Execute a \p fc_apply() by traversing the publication list from the head,
- combining all nonnull method call invocations, setting the <i>age</i> of each of these records
+ combining all non-null method call invocations, setting the <i>age</i> of each of these records
to the current <i>count</i>, applying the combined method calls to the structure D, and returning
responses to all the invocations. This traversal is guaranteed to be wait-free.</li>
<li>If the <i>count</i> is such that a cleanup needs to be performed, traverse the publication
namespace cds { namespace algo { namespace flat_combining {
/// Wait strategies for \p flat_combining technique
+ /**
+ Wait strategy specifies how a thread waits until its request is performed by the combiner.
+ See \p wait_strategy::empty wait strategy to explain the interface.
+ */
namespace wait_strategy {
/// Empty wait strategy
+ /**
+ Empty wait strategy is just spinning on request field.
+ All functions are empty.
+ */
struct empty
{
- //@cond
+ /// Metafunction for defining a publication record for flat combining technique
+ /**
+ Any wait strategy may expand the publication record for storing
+ its own private data.
+ \p PublicationRecord is the type specified by \p flat_combining::kernel.
+ - If the strategy has no thread-private data, it should typedef \p PublicationRecord
+ as a return \p type of metafunction.
+ - Otherwise, if the strategy wants to store anything in thread-local data,
+ it should expand \p PublicationRecord, for example:
+ \code
+ template <typename PublicationRecord>
+ struct make_publication_record {
+ struct type: public PublicationRecord
+ {
+ int strategy_data;
+ };
+ };
+ \endcode
+ */
template <typename PublicationRecord>
struct make_publication_record {
- typedef PublicationRecord type;
+ typedef PublicationRecord type; ///< Metafunction result
};
+ /// Prepares the strategy
+ /**
+ This function is called before enter to waiting cycle.
+ Some strategies need to prepare its thread-local data in \p rec.
+
+ \p PublicationRecord is thread's publication record of type \p make_publication_record::type
+ */
template <typename PublicationRecord>
- void prepare( PublicationRecord& /*rec*/ )
- {}
+ void prepare( PublicationRecord& rec )
+ {
+ CDS_UNUSED( rec );
+ }
+
+ /// Waits for the combiner
+ /**
+ The thread calls this function to wait for the combiner process
+ the request.
+ The function returns \p true if the thread was waked up by the combiner,
+ otherwise it should return \p false.
+ \p FCKernel is a \p flat_combining::kernel object,
+ \p PublicationRecord is thread's publication record of type \p make_publication_record::type
+ */
template <typename FCKernel, typename PublicationRecord>
- bool wait( FCKernel& /*fc*/, PublicationRecord& /*rec*/ )
+ bool wait( FCKernel& fc, PublicationRecord& rec )
{
+ CDS_UNUSED( fc );
+ CDS_UNUSED( rec );
return false;
}
+ /// Wakes up the thread
+ /**
+ The combiner calls \p %notify() when it has been processed the request.
+
+ \p FCKernel is a \p flat_combining::kernel object,
+ \p PublicationRecord is thread's publication record of type \p make_publication_record::type
+ */
template <typename FCKernel, typename PublicationRecord>
- void notify( FCKernel& /*fc*/, PublicationRecord& /*rec*/ )
- {}
+ void notify( FCKernel& fc, PublicationRecord& rec )
+ {
+ CDS_UNUSED( fc );
+ CDS_UNUSED( rec );
+ }
+ /// Moves control to other thread
+ /**
+ This function is called when the thread becomes the combiner
+ but the request of the thread is already processed.
+ The strategy may call \p fc.wakeup_any() instructs the kernel
+ to wake up any pending thread.
+
+ \p FCKernel is a \p flat_combining::kernel object,
+ */
template <typename FCKernel>
- void wakeup( FCKernel& /*fc*/ )
- {}
- //@endcond
+ void wakeup( FCKernel& fc )
+ {
+ CDS_UNUSED( fc );
+ }
};
/// Back-off wait strategy
+ /**
+ Template argument \p Backoff specifies back-off strategy, default is cds::backoff::delay_of<2>
+ */
template <typename BackOff = cds::backoff::delay_of<2>>
struct backoff
{
- //@cond
- typedef BackOff back_off;
+ typedef BackOff back_off; ///< Back-off strategy
+ /// Incorporates back-off strategy into publication record
template <typename PublicationRecord>
- struct make_publication_record {
+ struct make_publication_record
+ {
+ //@cond
struct type: public PublicationRecord
{
back_off bkoff;
};
+ //@endcond
};
+ /// Resets back-off strategy in \p rec
template <typename PublicationRecord>
void prepare( PublicationRecord& rec )
{
rec.bkoff.reset();
}
+ /// Calls back-off strategy
template <typename FCKernel, typename PublicationRecord>
bool wait( FCKernel& /*fc*/, PublicationRecord& rec )
{
return false;
}
+ /// Does nothing
template <typename FCKernel, typename PublicationRecord>
void notify( FCKernel& /*fc*/, PublicationRecord& /*rec*/ )
{}
+ /// Does nothing
template <typename FCKernel>
void wakeup( FCKernel& )
{}
- //@endcond
};
/// Wait strategy based on the single mutex and the condition variable
std::condition_variable m_condvar;
typedef std::unique_lock< std::mutex > unique_lock;
+ //@endcond
public:
enum {
- c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds
+ c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds ///< Waiting duration
};
+ /// Empty metafunction
template <typename PublicationRecord>
struct make_publication_record {
- typedef PublicationRecord type;
+ typedef PublicationRecord type; ///< publication record type
};
+ /// Does nothing
template <typename PublicationRecord>
void prepare( PublicationRecord& /*rec*/ )
{}
+ /// Sleeps on condition variable waiting for notification from combiner
template <typename FCKernel, typename PublicationRecord>
bool wait( FCKernel& fc, PublicationRecord& rec )
{
return false;
}
+ /// Calls condition variable function \p notify_all()
template <typename FCKernel, typename PublicationRecord>
void notify( FCKernel& fc, PublicationRecord& rec )
{
m_condvar.notify_all();
}
+ /// Calls condition variable function \p notify_all()
template <typename FCKernel>
void wakeup( FCKernel& /*fc*/ )
{
m_condvar.notify_all();
}
- //@endcond
};
/// Wait strategy based on the single mutex and thread-local condition variables
std::mutex m_mutex;
typedef std::unique_lock< std::mutex > unique_lock;
+ //@endcond
public:
enum {
- c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds
+ c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds ///< Waiting duration
};
+ /// Incorporates a condition variable into \p PublicationRecord
template <typename PublicationRecord>
struct make_publication_record {
+ /// Metafunction result
struct type: public PublicationRecord
{
+ //@cond
std::condition_variable m_condvar;
+ //@endcond
};
};
+ /// Does nothing
template <typename PublicationRecord>
void prepare( PublicationRecord& /*rec*/ )
{}
+ /// Sleeps on condition variable waiting for notification from combiner
template <typename FCKernel, typename PublicationRecord>
bool wait( FCKernel& fc, PublicationRecord& rec )
{
return false;
}
+ /// Calls condition variable function \p notify_one()
template <typename FCKernel, typename PublicationRecord>
void notify( FCKernel& fc, PublicationRecord& rec )
{
rec.m_condvar.notify_one();
}
+ /// Calls \p fc.wakeup_any() to wake up any pending thread
template <typename FCKernel>
void wakeup( FCKernel& fc )
{
fc.wakeup_any();
}
- //@endcond
};
/// Wait strategy where each thread has a mutex and a condition variable
{
//@cond
typedef std::unique_lock< std::mutex > unique_lock;
-
+ //@endcond
public:
enum {
- c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds
+ c_nWaitMilliseconds = Milliseconds < 1 ? 1 : Milliseconds ///< Waiting duration
};
+ /// Incorporates a condition variable and a mutex into \p PublicationRecord
template <typename PublicationRecord>
struct make_publication_record {
+ /// Metafunction result
struct type: public PublicationRecord
{
+ //@cond
std::mutex m_mutex;
std::condition_variable m_condvar;
+ //@endcond
};
};
+ /// Does nothing
template <typename PublicationRecord>
void prepare( PublicationRecord& /*rec*/ )
{}
+ /// Sleeps on condition variable waiting for notification from combiner
template <typename FCKernel, typename PublicationRecord>
bool wait( FCKernel& fc, PublicationRecord& rec )
{
return false;
}
+ /// Calls condition variable function \p notify_one()
template <typename FCKernel, typename PublicationRecord>
void notify( FCKernel& /*fc*/, PublicationRecord& rec )
{
rec.m_condvar.notify_one();
}
+ /// Calls \p fc.wakeup_any() to wake up any pending thread
template <typename FCKernel>
void wakeup( FCKernel& fc )
{
fc.wakeup_any();
}
- //@endcond
};
} // namespace wait_strategy
projects / libcds.git / commitdiff