|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r53231 - sandbox/task/libs/task/doc
From: oliver.kowalke_at_[hidden]
Date: 2009-05-24 16:35:54
Author: olli
Date: 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
New Revision: 53231
URL: http://svn.boost.org/trac/boost/changeset/53231
Log:
* documentation
Added:
sandbox/task/libs/task/doc/meta_functions.qbk (contents, props changed)
sandbox/task/libs/task/doc/scheduler.qbk (contents, props changed)
sandbox/task/libs/task/doc/shutdown.qbk (contents, props changed)
sandbox/task/libs/task/doc/static_pool.qbk (contents, props changed)
sandbox/task/libs/task/doc/utilities.qbk (contents, props changed)
sandbox/task/libs/task/doc/work_stealing.qbk (contents, props changed)
Removed:
sandbox/task/libs/task/doc/scheduling.qbk
sandbox/task/libs/task/doc/this_task.qbk
Text files modified:
sandbox/task/libs/task/doc/acknowledgements.qbk | 2
sandbox/task/libs/task/doc/appendices.qbk | 3
sandbox/task/libs/task/doc/as_sub_task.qbk | 2
sandbox/task/libs/task/doc/async_completion_token.qbk | 1
sandbox/task/libs/task/doc/async_executor.qbk | 1
sandbox/task/libs/task/doc/boost_task.qbk | 2
sandbox/task/libs/task/doc/channel.qbk | 19 +--
sandbox/task/libs/task/doc/description.qbk | 3
sandbox/task/libs/task/doc/forkjoin.qbk | 14 +-
sandbox/task/libs/task/doc/overview.qbk | 9 +
sandbox/task/libs/task/doc/pool.qbk | 193 ++++++++++++---------------------------
sandbox/task/libs/task/doc/rationale.qbk | 1
sandbox/task/libs/task/doc/reference.qbk | 26 ++--
sandbox/task/libs/task/doc/task.qbk | 4
14 files changed, 109 insertions(+), 171 deletions(-)
Modified: sandbox/task/libs/task/doc/acknowledgements.qbk
==============================================================================
--- sandbox/task/libs/task/doc/acknowledgements.qbk (original)
+++ sandbox/task/libs/task/doc/acknowledgements.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -7,6 +7,8 @@
[section:acknowledgements Appendix B: Acknowledgments]
+
I'd like to thank Vicente J. Botet Escriba for his comments on the implementation and Anthony Williams and Braddock Gaskill for their future libraries.
+
[endsect]
Modified: sandbox/task/libs/task/doc/appendices.qbk
==============================================================================
--- sandbox/task/libs/task/doc/appendices.qbk (original)
+++ sandbox/task/libs/task/doc/appendices.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -9,11 +9,10 @@
[section Appendices]
[include rationale.qbk]
-
[include acknowledgements.qbk]
-
[include todo.qbk]
+
[endsect]
Modified: sandbox/task/libs/task/doc/as_sub_task.qbk
==============================================================================
--- sandbox/task/libs/task/doc/as_sub_task.qbk (original)
+++ sandbox/task/libs/task/doc/as_sub_task.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -8,7 +8,7 @@
[section:as_sub_task __as_sub_task__]
-__as_sub_task__ is a conveniet way to execute a __sub_task__. If the parent task is executed inside a __thread_pool__ the __sub_task__ is put into the local-queue of the
+__as_sub_task__ is a convenient way to execute a __sub_task__. If the parent task is executed inside a __thread_pool__ the __sub_task__ is put into the local-queue of the
__worker_thread__ in the other case the __sub_task__ will be executed in a new thread.
Modified: sandbox/task/libs/task/doc/async_completion_token.qbk
==============================================================================
--- sandbox/task/libs/task/doc/async_completion_token.qbk (original)
+++ sandbox/task/libs/task/doc/async_completion_token.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -13,4 +13,5 @@
[include handle.qbk]
+
[endsect]
Modified: sandbox/task/libs/task/doc/async_executor.qbk
==============================================================================
--- sandbox/task/libs/task/doc/async_executor.qbk (original)
+++ sandbox/task/libs/task/doc/async_executor.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -18,4 +18,5 @@
[include pool.qbk]
[include as_sub_task.qbk]
+
[endsect]
Modified: sandbox/task/libs/task/doc/boost_task.qbk
==============================================================================
--- sandbox/task/libs/task/doc/boost_task.qbk (original)
+++ sandbox/task/libs/task/doc/boost_task.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -95,6 +95,8 @@
[def __thread_pools__ ['thread-pools]]
[def __sub_task__ ['sub-task]]
[def __sub_tasks__ ['sub-tasks]]
+[def __work_item__ ['work-item]]
+[def __work_items__ ['work-items]]
[def __work_stealing__ ['work-stealing]]
[def __worker_queue__ ['worker-queue]]
[def __worker_thread__ ['worker-thread]]
Modified: sandbox/task/libs/task/doc/channel.qbk
==============================================================================
--- sandbox/task/libs/task/doc/channel.qbk (original)
+++ sandbox/task/libs/task/doc/channel.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -1,21 +1,16 @@
[/
- (C) Copyright 2008 Oliver Kowalke.
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt).
+ Copyright Oliver Kowalke 2009.
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt
]
+
[section:channel Channel]
+
The channel synchronizes the access between application threads (producer threads) submitting __actions__ to the pool and __worker_threads__ (consumer threads). The scheduling of __actions__ queued into the channel depends on channels scheduling policy.
If the channel becomes empty all __worker_threads__ are set to sleep until a new __action__ is put in.
-[/
-[heading lockfree channel]
-
- class lockfree_channel
-
-Uses internaly a lockfree algorithm in order to get a fifo queue.
-]
[heading bounded channel]
@@ -29,10 +24,12 @@
If __lwm__ is less than __hwm__ all sleeping producer threads will be woken up if
the amount of pending tasks reaches __lwm__.
+
[heading unbounded channel]
template< typename SchedulingPolicy > class unbounded_channel
Contains a single lock in order to synchronize access to the queue. An unlimited number of __actions__ can be queued into this channel. The insertion of __actions__ will never block. If the channel becomes empty __worker_threads__ will be set to sleep until new __actions__ are inserted into the channel.
+
[endsect]
Modified: sandbox/task/libs/task/doc/description.qbk
==============================================================================
--- sandbox/task/libs/task/doc/description.qbk (original)
+++ sandbox/task/libs/task/doc/description.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -11,5 +11,8 @@
[include task.qbk]
[include async_completion_token.qbk]
[include async_executor.qbk]
+[include utilities.qbk]
+[include meta_functions.qbk]
+
[endsect]
Modified: sandbox/task/libs/task/doc/forkjoin.qbk
==============================================================================
--- sandbox/task/libs/task/doc/forkjoin.qbk (original)
+++ sandbox/task/libs/task/doc/forkjoin.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -1,11 +1,13 @@
-[/
- (C) Copyright 2008 Oliver Kowalke.
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt).
+/
+ Copyright Oliver Kowalke 2009.
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt
]
+
[section:forkjoin Fork/Join]
+
Fork/Join algorithms are recursive divide-and-conquer algorithms which repeatedly splitt __sub_actions__ until they become small enough to solve using simple, short sequential methods, so that they run in parallel on multiple cores.
The fork operation creates a new __sub_action__ (which can run in parallel) in the pool. The current __actions__ is not proceeded in the join operation until the forked __sub_actions__ have completed. In the meantime the __worker_thread__ executes other __actions__ from its local __worker_queue__.
@@ -99,4 +101,6 @@
return EXIT_FAILURE;
}
+
+
[endsect]
Added: sandbox/task/libs/task/doc/meta_functions.qbk
==============================================================================
--- (empty file)
+++ sandbox/task/libs/task/doc/meta_functions.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -0,0 +1,26 @@
+[/
+ Copyright Oliver Kowalke 2009.
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt
+]
+
+
+[section:meta_functions Meta functions]
+
+If the __threadpool__ supports priorities `boost::tp::has_priority< pool_type >` evaluates to `true`. The priority type is determined by `boost::tp::priority_type< pool_type >`.
+
+ typedef boost::tp::pool<
+ boost::tp::unbounded_channel< boost::tp::priority< int > >
+ > pool_type;
+
+ std::cout << std::boolalpha << boost::tp::has_priority< pool_type >::value << std::endl;
+ std::cout << typeid( boost::tp::priority_type< pool_type >::type).name() << std::endl;
+
+The support of fibers can be tested with meta-function `boost::tp::has_fibers< pool_type >`.
+
+ std::cout << std::boolalpha << boost::tp::has_fibers< pool_type >::value << std::endl;
+
+
+[endsect]
+
Modified: sandbox/task/libs/task/doc/overview.qbk
==============================================================================
--- sandbox/task/libs/task/doc/overview.qbk (original)
+++ sandbox/task/libs/task/doc/overview.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -56,10 +56,11 @@
[heading Tested Platforms]
__boost_task__ has been tested on the following platforms and compilers:
-* Debian GNU/Linux 2.6.29.2 (amd64), GCC 4.3.3
-* FreeBSD 7.2 (amd64), GCC 4.2.1
-* OpenSolaris 0811 (amd64), SUN
-* Windows XP Professional (i386), MSVC 9.0
+* Debian GNU/Linux 2.6.29.2 (x86_64), GCC 4.3.3
+* Ubuntu GNU/Linux 2.6.28.11 (x86), GCC 4.3.3
+* FreeBSD 7.2 (x86), GCC 4.2.1
+* OpenSolaris 0811 (x86_64), SunCC 5.10
+* Windows XP Professional (x86), MSVC 9.0
[heading How to build]
Modified: sandbox/task/libs/task/doc/pool.qbk
==============================================================================
--- sandbox/task/libs/task/doc/pool.qbk (original)
+++ sandbox/task/libs/task/doc/pool.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -1,148 +1,71 @@
[/
- (C) Copyright 2008 Oliver Kowalke.
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt).
+ Copyright Oliver Kowalke 2009.
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt
]
-[section:pool Pool]
-A __thread_pool__ maintains a queue (or queues) of work to be done, and a collection of __worker_threads__ which execute work from the queue(s).
+[section:pool Thread pool]
-Since a __sub_task__ is just a piece of a larger __task__, we don’t need to worry about execution order. We just need to execute these things quickly. One well-known strategy for fast execution of unordered work items is __work_stealing__.
+A __thread_pool__ maintains a queue (or queues) of __work_items__ to be done, and a pool of __worker_threads__ which execute __work_items__ from the queue(s).
+Instead of creating a new thread and quickly throwing it away after the task is done, the overhead related to thread creation and destruction can be avoided by running the __work_item__ on a __thread_pool__ (reusing an existing __worker__thread__ instead).
-[heading Work-Stealing]
+__boost_task__ provides __fn_async__ with support of
-The most important aspect of work-stealing is that it enables very fast enqueue and dequeue in the typical case, often requiring no synchronization at all. This virtually eliminates a large part of the overhead of QUWI, when working with child tasks. We still do need to allocate memory for the Task itself, and for the work-stealing queue, but like the improvements to the FIFO queue these data structures have been optimized for good GC performance. Parent tasks are fast; child tasks are much faster.
+``
+ std::string echo( std::string const& msg)
+ { return msg; }
+
+ void main()
+ {
+ boost::task::handle< std::string > h(
+ boost::task::async(
+ boost::task::default_pool(),
+ boost::task::make_task(
+ echo,
+ "Hello World!") ) );
+ std::cout << h.get() << std::endl;
+ }
+``
+
+executing a __task__ in __default_pool__ (using __fn_default_pool__)
+
+
+``
+ std::string echo( std::string const& msg)
+ { return msg; }
+
+ boost::task::static_pool<
+ boost::task::unbounded_channel<
+ boost::task::fifo
+ >
+ > pool( boost::task::poolsize( 5) );
+
+ void main()
+ {
+ boost::task::handle< std::string > h(
+ boost::task::async(
+ pool,
+ boost::task::make_task(
+ echo,
+ "Hello World!") ) );
+ std::cout << h.get() << std::endl;
+ }
+``
+
+and a custom __thread_pool__ (passing pool instance as an argument to __fn_async__).
+
+
+[include static_pool.qbk]
+[include channel.qbk]
+[include scheduler.qbk]
+[include shutdown.qbk]
+[include work_stealing.qbk]
+[include fork_join.qbk]
-Traditional thread pool do not scale because they use a single global queue protected by a global lock. The frequency at which __worker_threads__ aquire the global lock becomes a limiting factor for the throughput if:
-
-
-* the __tasks__ become smaller
-
-* more processors are added
-
-
-A work-stealing algorithm can be used to solve this problem. It uses a special kind of queue which has two ends, and allows lock-free pushes and pops from the ['private end] (accessed by the __worker_thread__ owning the queue), but requires synchronization from the ['public end] (accessed by the other __worker_threads__). Synchronization is necessary when the queue is sufficiently small that private and public operations could conflict.
-
-The pool contains one global queue (__bounded_channel__ or __unbounded_channel__) protected by a global lock and each __worker_thread__ has its own private worker queue. If work is enqueued by a __worker_thread__ the __action__ is stored in the worker queue. If the work is enqueued by a application thread it goes into the global queue. When __worker_threads__ are looking for work, they have following search order:
-
-
-* look into the private worker queue - __actions__ can be dequeued without locks
-
-* look in the global queue - locks are used for synchronization
-
-* check other worker queues ('stealing' __actions__ from private worker queues of other __worker_threads__) - requires locks
-
-
-For a lot of recursively queued __tasks__, the use of a worker queue per thread substantially reduces the synchronization necessary to complete the work. There are also fewer cache effects due to sharing of the global queue information.
-
-Operations on the private worker queue are executed in LIFO order and operations on worker queues of other __worker_threads__ in FIFO order (steals).
-
-
-* There are chances that memory is still hot in the cache, if the __actions__ are pushed in LIFO order into the private worker queue.
-
-* If a __worker_thread__ steals work in FIFO order, increases the chances that a larger 'chunk' of work will be stolen (the need for other steals will be possibly reduced). Because the __tasks__ are stored in LIFO order, the oldest items are closer to the ['public end] of the queue (forming a tree). Stealing such an older __task__ also steals a (probably) larger subtree of __tasks__ unfolded if the stolen work item get executed.
-
-
-[important Because of the work-stealing algorithm the execution order of __tasks__ may be not strict as in the global queue.]
-
-
-[heading Creation]
-
-The first template argument specifies the channel type and the scheduling policy.
-
- boost::tp::pool<
- boost::tp::unbounded_channel< boost::tp::fifo >
- > pool(
- boost::tp::poolsize( 6),
- boost::posix_time::posix_time::milliseconds( 50),
- boost::tp::scanns(10) );
-
-In the example above a __threadpool__ is created with a __unbounded_channel__, scheduling __actions__ in ['FIFO] order. The pool contains six __worker_threads__ going to sleep for 50 millisec after 10 iterations without geting an __action__ from the __global_queue__, from its local __worker_queue__ or local queues of other __worker_threads__.
-
- boost::tp::pool<
- boost::tp::bounded_channel< boost::tp::priority < int > >
- > pool(
- boost::tp::poolsize( 10),
- boost::tp::high_watermark( 10),
- boost::tp::low_watermark( 5) );
-
-This pool uses a __bounded_channel__ which schedules __actions__ by integer atrributes. A maximum of 10 __actions__ can be queued in the __global_queue__ without blocking the inserting thread.
-
-
-[heading Shutdown]
-
-If `boost::tp::pool< Channel >::shutdown()` is called - the the pool is set closed and all __worker_threads__ are joined until all pending __actions__ are processed. No futher __actions__ can be submitted by application threads.
-
-[note The deconstructor calls `boost::tp::pool< Channel >::shutdown()` if the pool was not shutdown yet.]
-
- boost::tp::pool<
- boost::tp::unbounded_channel< boost::tp::fifo >
- > pool( boost::tp::poolsize( 1) );
-
- boost::tp::task< int > t1(
- pool.submit(
- boost::bind(
- fibonacci_fn,
- 10) ) );
- boost::tp::task< int > t2(
- pool.submit(
- boost::bind(
- fibonacci_fn,
- 10) ) );
-
- pool.shutdown();
-
- std::cout << t1.result().get() << std::endl; // 55
- std::cout << t2.result().get() << std::endl; // 55
-
-[heading Shutdown immediatly]
-The function `boost::tp::pool< Channel >::shutdown_now()` closes the pool, interrupts and then joins all __worker_threads__. All pending (unprocessed) __actions__ will be returned.
-
-[important Pending __actions__ in the local __worker_queues__ are not returned if `boost::tp::pool< Channel >::shutdown_now()` was called.]
-
-
-[heading Default pool]
-
-The free function `boost::tp::get_default_pool()` returns a reference to the default __threadpool__ instance. The default __threadpool__ is
-of type `boost::tp::pool< boost::tp::unbounded_channel< boost::tp::fifo > >` and will contain as many __worker_threads__ as
-`boost::thread::hardware_concurrency()` returns.
-
-
-[heading Launch in pool]
-
-The free function `boost::tp::launch_in_pool( Act const& act)` submits the __action__ to the default pool and returns a task object.
-
-
-[heading Meta functions]
-
-If the __threadpool__ supports priorities `boost::tp::has_priority< pool_type >` evaluates to `true`. The priority type is determined by `boost::tp::priority_type< pool_type >`.
-
- typedef boost::tp::pool<
- boost::tp::unbounded_channel< boost::tp::priority< int > >
- > pool_type;
-
- std::cout << std::boolalpha << boost::tp::has_priority< pool_type >::value << std::endl;
- std::cout << typeid( boost::tp::priority_type< pool_type >::type).name() << std::endl;
-
-The support of fibers can be tested with meta-function `boost::tp::has_fibers< pool_type >`.
-
- std::cout << std::boolalpha << boost::tp::has_fibers< pool_type >::value << std::endl;
-
-
-[heading Processor binding]
-
-For some applications it is convenient to bind the worker threads of the pool to processors of the system. For this purpose BOOST_BIND_WORKER_TO_PROCESSORS must be defined. Without the poolsize in the construtor the __threadpool__ will contain as many
-__worker_threads__ as processors (== __hardware_concurrency__) are available and each __worker_thread__ is bound to one processor.
-
- boost::tp::pool<
- boost::tp::unbounded_channel< boost::tp::fifo >
- > pool;
-
-The code above will create a pool with two __worker_threads__ on a dual core system (each bound to one core).
[endsect]
Modified: sandbox/task/libs/task/doc/rationale.qbk
==============================================================================
--- sandbox/task/libs/task/doc/rationale.qbk (original)
+++ sandbox/task/libs/task/doc/rationale.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -20,4 +20,5 @@
* async : from mailing-list, execution of task in current thread, new thread in pool
+
[endsect]
Modified: sandbox/task/libs/task/doc/reference.qbk
==============================================================================
--- sandbox/task/libs/task/doc/reference.qbk (original)
+++ sandbox/task/libs/task/doc/reference.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -1,19 +1,21 @@
[/
- (C) Copyright 2008 Oliver Kowalke.
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt).
+ Copyright Oliver Kowalke 2009.
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt
]
+
[section:reference Reference]
-[include pool_ref.qbk]
-[include task_ref.qbk]
-[include this_task_ref.qbk]
-[include poolsize_ref.qbk]
-[include scanns_ref.qbk]
-[include watermark_ref.qbk]
-[include exceptions_ref.qbk]
-[include meta_ref.qbk]
+[include ref_async.qbk]
+[include ref_static_pool.qbk]
+[include ref_task.qbk]
+[include ref_handle.qbk]
+[include ref_utilities.qbk]
+[include ref_meta_functions.qbk]
+[include ref_exceptions.qbk]
+[include ref_watermark.qbk]
+
[endsect]
Added: sandbox/task/libs/task/doc/scheduler.qbk
==============================================================================
--- (empty file)
+++ sandbox/task/libs/task/doc/scheduler.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -0,0 +1,80 @@
+[/
+ Copyright Oliver Kowalke 2009.
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt
+]
+
+
+[section:scheduling Scheduling]
+
+The scheduling policy determines how __actions__ are scheduled inside the __channel__.
+
+
+[heading fifo]
+
+ struct fifo
+
+First inserted pending __action__ get taken first.
+
+
+[heading priority]
+
+ template< typename Attr, typename Ord = std::less< Attr > > struct priority
+
+Each pending task is associated with a priority attribute which is used for ordering __actions__.
+
+
+[heading smart]
+
+ template< typename Attr, typename Ord, typename Enq, typename Deq > struct smart
+
+Each pending __actions__ is associated with an attribute. The scheduler gets an put- and take-policy
+as template arguments. The corresponding policy get applied for each insertion and removal.
+
+__boost_threadpool__ provides ['boost::tp::replace_oldest] as put policy and ['boost::tp::take_oldest] as take
+policy. Both policies allow the replacement of old __actions__ in the scheduler by new ones.
+
+ // creates a pool with unbounded channel
+ // tasks are processed depending on the associated attributed
+ // oldest tasks with the same attributed pending in the channel
+ // will be replaced by the new task
+ // this example would execute add( 1, 2) and add( 5, 6)
+ // add( 2, 3) is removed (if pending when add( 5, 6) is submitted)
+ boost::tp::pool<
+ boost::tp::unbounded_channel<
+ boost::tp::smart<
+ int,
+ std::less< int >,
+ boost::tp::replace_oldest,
+ boost::tp::take_oldest
+ >
+ >
+ > pool( boost::tp::poolsize( 1) );
+
+ pool.submit(
+ boost::bind(
+ add_fn,
+ 1,
+ 2),
+ 0);
+
+ // replaced by later task with same attribute
+ // if still pending in pool
+ pool.submit(
+ boost::bind(
+ add_fn,
+ 3,
+ 4),
+ 1);
+
+ // will replace previous pending action
+ pool.submit(
+ boost::bind(
+ add_fn,
+ 5,
+ 6),
+ 1);
+
+
+[endsect]
Deleted: sandbox/task/libs/task/doc/scheduling.qbk
==============================================================================
--- sandbox/task/libs/task/doc/scheduling.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
+++ (empty file)
@@ -1,84 +0,0 @@
-[/
- (C) Copyright 2008 Oliver Kowalke.
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt).
-]
-
-[section:scheduling Scheduling]
-The scheduling policy determines how __actions__ are scheduled inside the __channel__.
-
-[heading fifo]
-
- struct fifo
-
-First inserted pending __action__ get taken first.
-
-
-[heading lifo]
-
- struct lifo
-
-Last inserted pending __action__ get taken first.
-
-
-[heading priority]
-
- template< typename Attr, typename Ord = std::less< Attr > > struct priority
-
-Each pending task is associated with a priority attribute which is used for ordering __actions__.
-
-
-[heading smart]
-
- template< typename Attr, typename Ord, typename Enq, typename Deq > struct smart
-
-Each pending __actions__ is associated with an attribute. The scheduler gets an put- and take-policy
-as template arguments. The corresponding policy get applied for each insertion and removal.
-
-__boost_threadpool__ provides ['boost::tp::replace_oldest] as put policy and ['boost::tp::take_oldest] as take
-policy. Both policies allow the replacement of old __actions__ in the scheduler by new ones.
-
- // creates a pool with unbounded channel
- // tasks are processed depending on the associated attributed
- // oldest tasks with the same attributed pending in the channel
- // will be replaced by the new task
- // this example would execute add( 1, 2) and add( 5, 6)
- // add( 2, 3) is removed (if pending when add( 5, 6) is submitted)
- boost::tp::pool<
- boost::tp::unbounded_channel<
- boost::tp::smart<
- int,
- std::less< int >,
- boost::tp::replace_oldest,
- boost::tp::take_oldest
- >
- >
- > pool( boost::tp::poolsize( 1) );
-
- pool.submit(
- boost::bind(
- add_fn,
- 1,
- 2),
- 0);
-
- // replaced by later task with same attribute
- // if still pending in pool
- pool.submit(
- boost::bind(
- add_fn,
- 3,
- 4),
- 1);
-
- // will replace previous pending action
- pool.submit(
- boost::bind(
- add_fn,
- 5,
- 6),
- 1);
-
-
-[endsect]
Added: sandbox/task/libs/task/doc/shutdown.qbk
==============================================================================
--- (empty file)
+++ sandbox/task/libs/task/doc/shutdown.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -0,0 +1,46 @@
+[/
+ Copyright Oliver Kowalke 2009.
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt
+]
+
+
+[section:static_pool Pool shutdown]
+
+[heading Shutdown]
+
+If `boost::tp::pool< Channel >::shutdown()` is called - the the pool is set closed and all __worker_threads__ are joined until all pending __actions__ are processed. No futher __actions__ can be submitted by application threads.
+
+[note The deconstructor calls `boost::tp::pool< Channel >::shutdown()` if the pool was not shutdown yet.]
+
+ boost::tp::pool<
+ boost::tp::unbounded_channel< boost::tp::fifo >
+ > pool( boost::tp::poolsize( 1) );
+
+ boost::tp::task< int > t1(
+ pool.submit(
+ boost::bind(
+ fibonacci_fn,
+ 10) ) );
+ boost::tp::task< int > t2(
+ pool.submit(
+ boost::bind(
+ fibonacci_fn,
+ 10) ) );
+
+ pool.shutdown();
+
+ std::cout << t1.result().get() << std::endl; // 55
+ std::cout << t2.result().get() << std::endl; // 55
+
+
+[heading Shutdown immediatly]
+
+The function `boost::tp::pool< Channel >::shutdown_now()` closes the pool, interrupts and then joins all __worker_threads__. All pending (unprocessed) __actions__ will be returned.
+
+[important Pending __actions__ in the local __worker_queues__ are not returned if `boost::tp::pool< Channel >::shutdown_now()` was called.]
+
+
+[endsect]
+
Added: sandbox/task/libs/task/doc/static_pool.qbk
==============================================================================
--- (empty file)
+++ sandbox/task/libs/task/doc/static_pool.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -0,0 +1,84 @@
+[/
+ Copyright Oliver Kowalke 2009.
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt
+]
+
+
+[section:static_pool __static_pool__]
+
+The first template argument specifies the channel type and the scheduling policy.
+
+ boost::tp::pool<
+ boost::tp::unbounded_channel< boost::tp::fifo >
+ > pool(
+ boost::tp::poolsize( 6),
+ boost::posix_time::posix_time::milliseconds( 50),
+ boost::tp::scanns(10) );
+
+In the example above a __threadpool__ is created with a __unbounded_channel__, scheduling __actions__ in ['FIFO] order. The pool contains six __worker_threads__ going to sleep for 50 millisec after 10 iterations without geting an __action__ from the __global_queue__, from its local __worker_queue__ or local queues of other __worker_threads__.
+
+ boost::tp::pool<
+ boost::tp::bounded_channel< boost::tp::priority < int > >
+ > pool(
+ boost::tp::poolsize( 10),
+ boost::tp::high_watermark( 10),
+ boost::tp::low_watermark( 5) );
+
+This pool uses a __bounded_channel__ which schedules __actions__ by integer atrributes. A maximum of 10 __actions__ can be queued in the __global_queue__ without blocking the inserting thread.
+
+
+[heading Shutdown]
+
+If `boost::tp::pool< Channel >::shutdown()` is called - the the pool is set closed and all __worker_threads__ are joined until all pending __actions__ are processed. No futher __actions__ can be submitted by application threads.
+
+[note The deconstructor calls `boost::tp::pool< Channel >::shutdown()` if the pool was not shutdown yet.]
+
+ boost::tp::pool<
+ boost::tp::unbounded_channel< boost::tp::fifo >
+ > pool( boost::tp::poolsize( 1) );
+
+ boost::tp::task< int > t1(
+ pool.submit(
+ boost::bind(
+ fibonacci_fn,
+ 10) ) );
+ boost::tp::task< int > t2(
+ pool.submit(
+ boost::bind(
+ fibonacci_fn,
+ 10) ) );
+
+ pool.shutdown();
+
+ std::cout << t1.result().get() << std::endl; // 55
+ std::cout << t2.result().get() << std::endl; // 55
+
+[heading Shutdown immediatly]
+The function `boost::tp::pool< Channel >::shutdown_now()` closes the pool, interrupts and then joins all __worker_threads__. All pending (unprocessed) __actions__ will be returned.
+
+[important Pending __actions__ in the local __worker_queues__ are not returned if `boost::tp::pool< Channel >::shutdown_now()` was called.]
+
+
+[heading Default pool]
+
+The free function `boost::tp::get_default_pool()` returns a reference to the default __threadpool__ instance. The default __threadpool__ is
+of type `boost::tp::pool< boost::tp::unbounded_channel< boost::tp::fifo > >` and will contain as many __worker_threads__ as
+`boost::thread::hardware_concurrency()` returns.
+
+
+[heading Processor binding]
+
+For some applications it is convenient to bind the worker threads of the pool to processors of the system. For this purpose BOOST_BIND_WORKER_TO_PROCESSORS must be defined. Without the poolsize in the construtor the __threadpool__ will contain as many
+__worker_threads__ as processors (== __hardware_concurrency__) are available and each __worker_thread__ is bound to one processor.
+
+ boost::tp::pool<
+ boost::tp::unbounded_channel< boost::tp::fifo >
+ > pool;
+
+The code above will create a pool with two __worker_threads__ on a dual core system (each bound to one core).
+
+
+[endsect]
+
Modified: sandbox/task/libs/task/doc/task.qbk
==============================================================================
--- sandbox/task/libs/task/doc/task.qbk (original)
+++ sandbox/task/libs/task/doc/task.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -56,6 +56,7 @@
boost::task::task< std::string > t( y);
``
+
[heading:cooperative Cooperative task amd interruption]
Sometimes it is desired to stop a running task if it is no longer needed. In this case the thread is not killed -
@@ -113,6 +114,7 @@
}
``
+
[heading:exceptions Exceptions]
Exceptions thrown by __task__ are transported by the __act__.
@@ -164,7 +166,7 @@
[heading:parent Parent-tasks]
Top-level tasks have no parent. A parent task can create child tasks when it creates another task by using __as_sub_task__ as __ae__. These children are implicitly treated as __sub_tasks__ of the larger task. It is assumed that that __sub_tasks__ can be executed in any order because only overall operation
-speed matters (enabling strategies for fast execution of unordered work-items as link_work_stealing[__work_stealing__]).
+speed matters (enabling strategies for fast execution of unordered __work_items__ as link_work_stealing[__work_stealing__]).
``
long serial_fib( long n)
Deleted: sandbox/task/libs/task/doc/this_task.qbk
==============================================================================
--- sandbox/task/libs/task/doc/this_task.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
+++ (empty file)
@@ -1,16 +0,0 @@
-[/
- (C) Copyright 2008 Oliver Kowalke.
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt).
-]
-
-[section:this_task Namespace this_task]
-In the function `boost::this_task::reschedule_until( Pred const&)` allows to synchronize the task with other
-asynchronous events without blocking the __worker_threads__ (bool Pred::operator()() must not block)
-The current task will be rescheduled until the passed predicate becomes true.
-The pool can be accessed via `boost::this_task::get_thread_pool< Pool >()` if the calling code is executed by a __worker_thread__.
-`boost::this_task::s_worker()` evaluates true if the current thread is __worker_thread__ and `boost::this_task::worker_id()`
-returns the thread id.
-
-[endsect]
Added: sandbox/task/libs/task/doc/utilities.qbk
==============================================================================
--- (empty file)
+++ sandbox/task/libs/task/doc/utilities.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -0,0 +1,19 @@
+[/
+ Copyright Oliver Kowalke 2009.
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt
+]
+
+
+[section:this_task Namespace this_task]
+
+In the function `boost::this_task::reschedule_until( Pred const&)` allows to synchronize the task with other
+asynchronous events without blocking the __worker_threads__ (bool Pred::operator()() must not block)
+The current task will be rescheduled until the passed predicate becomes true.
+The pool can be accessed via `boost::this_task::get_thread_pool< Pool >()` if the calling code is executed by a __worker_thread__.
+`boost::this_task::s_worker()` evaluates true if the current thread is __worker_thread__ and `boost::this_task::worker_id()`
+returns the thread id.
+
+
+[endsect]
Added: sandbox/task/libs/task/doc/work_stealing.qbk
==============================================================================
--- (empty file)
+++ sandbox/task/libs/task/doc/work_stealing.qbk 2009-05-24 16:35:50 EDT (Sun, 24 May 2009)
@@ -0,0 +1,41 @@
+[/
+ Copyright Oliver Kowalke 2009.
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt
+]
+
+
+[section:work_stealing Work-Stealing]
+
+The most important aspect of work-stealing is that it enables very fast enqueue and dequeue in the typical case, often requiring no synchronization at all. This virtually eliminates a large part of the overhead of QUWI, when working with child tasks. We still do need to allocate memory for the Task itself, and for the work-stealing queue, but like the improvements to the FIFO queue these data structures have been optimized for good GC performance. Parent tasks are fast; child tasks are much faster.
+
+Traditional thread pool do not scale because they use a single global queue protected by a global lock. The frequency at which __worker_threads__ aquire the global lock becomes a limiting factor for the throughput if:
+
+* the __tasks__ become smaller
+
+* more processors are added
+
+A work-stealing algorithm can be used to solve this problem. It uses a special kind of queue which has two ends, and allows lock-free pushes and pops from the ['private end] (accessed by the __worker_thread__ owning the queue), but requires synchronization from the ['public end] (accessed by the other __worker_threads__). Synchronization is necessary when the queue is sufficiently small that private and public operations could conflict.
+
+The pool contains one global queue (__bounded_channel__ or __unbounded_channel__) protected by a global lock and each __worker_thread__ has its own private worker queue. If work is enqueued by a __worker_thread__ the __action__ is stored in the worker queue. If the work is enqueued by a application thread it goes into the global queue. When __worker_threads__ are looking for work, they have following search order:
+
+* look into the private worker queue - __actions__ can be dequeued without locks
+
+* look in the global queue - locks are used for synchronization
+
+* check other worker queues ('stealing' __actions__ from private worker queues of other __worker_threads__) - requires locks
+
+For a lot of recursively queued __tasks__, the use of a worker queue per thread substantially reduces the synchronization necessary to complete the work. There are also fewer cache effects due to sharing of the global queue information.
+
+Operations on the private worker queue are executed in LIFO order and operations on worker queues of other __worker_threads__ in FIFO order (steals).
+
+* There are chances that memory is still hot in the cache, if the __actions__ are pushed in LIFO order into the private worker queue.
+
+* If a __worker_thread__ steals work in FIFO order, increases the chances that a larger 'chunk' of work will be stolen (the need for other steals will be possibly reduced). Because the __tasks__ are stored in LIFO order, the oldest items are closer to the ['public end] of the queue (forming a tree). Stealing such an older __task__ also steals a (probably) larger subtree of __tasks__ unfolded if the stolen work item get executed.
+
+Since a __sub_task__ is just a piece of a larger __task__, we don’t need to worry about execution order. We just need to execute these things quickly. One well-known strategy for fast execution of unordered work items is __work_stealing__.
+
+
+[endsect]
+
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk