libgenua
Basic Geometry, Numerical Algorithms and Interfaces
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Groups Pages
Public Member Functions | Static Public Member Functions | Private Member Functions | Private Attributes | Static Private Attributes | List of all members
TaskScheduler Class Reference

Detailed Description

Task-stealing thread pool.

(C++11)

This is a relatively simple task scheduler which creates one thread and one FunctionQueue per hardware thread, which start looking for work on creation. Since FunctionQueue stores objects of type std::function, each task creation typically implies at least one heap allocation in order to erase the type; furthermore, the compiler will not be able to inline the task bodies into the scheduler due to the indirect calls.

However, since the enqueing and fetching of task objects is performed with very little lock contention, this scheduler should be more suitable for problems which generate very many (thousands) tasks or where a very dynamic behavior (e.g. tasks creating variable numbers of new tasks of uneven cost).

When the task type for a specific problem is fixed and POD and the number of parallel jobs is known to be moderate, WorkStack or LockfreePool may be preferable.

See Also
FunctionQueue, parallel::invoke

#include <tasksystem.h>

Collaboration diagram for TaskScheduler:
[legend]

Public Member Functions

 TaskScheduler ()
 setup task system with one thread per logical processor core
 
 ~TaskScheduler ()
 mark all tasks as completed and join worker threads
 
template<typename F >
void enqueue (F &&f)
 Schedule f for asynchronuous execution. More...
 
size_t loadfactor () const
 returns the approximate (!) number of jobs waiting to be processed
 
void sweep ()
 erase all remaining unfinished tasks (running tasks are not touched)
 

Static Public Member Functions

static TaskSchedulerpool ()
 access the (centralized) system task pool
 

Private Member Functions

void run (unsigned i)
 Execute the next task in line. More...
 

Private Attributes

const uint m_ncores = std::thread::hardware_concurrency()
 number of threads and queues - must be a constant
 
std::atomic< uint > m_qindex
 holds the index of the task queue to feed next (mod m_count)
 
std::vector< std::thread > m_threads
 m_count threads, one per logical core
 
std::vector< FunctionQueuem_queues = std::vector<FunctionQueue>(m_ncores)
 one task queue per thread
 

Static Private Attributes

static TaskScheduler s_pool
 global system pool
 

Member Function Documentation

template<typename F >
void TaskScheduler::enqueue ( F &&  f)
inline

Schedule f for asynchronuous execution.

  1. Start the 'next' task queue, one past the one last tried
  2. Attempt to enqueue there; if it doesn't work (locked), go to the next
  3. Try each queue once if it still didn't succeed
  4. Only if all else fails, wait until queue tried first becomes unlocked

Any successfull push in any of the queues will notify one waiting thread (if there is any sleeping).

void TaskScheduler::run ( unsigned  i)
private

Execute the next task in line.

This is the function called by thread i; it first tries to pop off a new task from queue i. If that queue is locked or empty, cycle through the other queues a few times trying to steal a task there. If even that fails, waits for notification on queue i.

Todo:
Will only wake up when queue i is notified - hmm.

The documentation for this class was generated from the following files: