title: How to create an efficient multi-threaded task scheduler in C++?
body: <p>I'd like to create a very efficient task scheduler system in C++.</p>
  
  <p>The basic idea is this:</p>
  
  <pre><code>class Task {
      public:
          virtual void run() = 0;
  };
  
  class Scheduler {
      public:
          void add(Task &amp;task, double delayToRun);
  };
  </code></pre>
  
  <p>Behind <code>Scheduler</code>, there should be a fixed-size thread pool, which run the tasks (I don't want to create a thread for each task). <code>delayToRun</code> means that the <code>task</code> doesn't get executed immediately, but <code>delayToRun</code> seconds later (measuring from the point it was added into the <code>Scheduler</code>).</p>
  
  <p>(<code>delayToRun</code> means an "at-least" value, of course. If the system is loaded, or if we ask the impossible from the Scheduler, it won't be able to handle our request. But it should do the best it can)</p>
  
  <p>And here's my problem. How to implement <code>delayToRun</code> functionality efficiently? I'm trying to solve this problem with the use of mutexes and condition variables.</p>
  
  <p>I see two ways:</p>
  
  <h2>With manager thread</h2>
  
  <p>Scheduler contains two queues: <code>allTasksQueue</code>, and <code>tasksReadyToRunQueue</code>. A task gets added into <code>allTasksQueue</code> at <code>Scheduler::add</code>. There is a manager thread, which waits the smallest amount of time so it can put a task from <code>allTasksQueue</code> to <code>tasksReadyToRunQueue</code>. Worker threads wait for a task available in <code>tasksReadyToRunQueue</code>.</p>
  
  <p>If <code>Scheduler::add</code> adds a task in front of <code>allTasksQueue</code> (a task, which has a value of <code>delayToRun</code> so it should go before the current soonest-to-run task), then the manager task need to be woken up, so it can update the time of wait.</p>
  
  <p>This method can be considered inefficient, because it needs two queues, and it needs two condvar.signals to make a task run (one for <code>allTasksQueue</code>-><code>tasksReadyToRunQueue</code>, and one for signalling a worker thread to actually run the task)</p>
  
  <h2>Without manager thread</h2>
  
  <p>There is one queue in the scheduler. A task gets added into this queue at <code>Scheduler::add</code>. A worker thread checks the queue. If it is empty, it waits without a time constraint. If it is not empty, it waits for the soonest task.</p>
  
  <ol>
  <li><p>If there is only one condition variable for which the working threads waiting for: this method can be considered inefficient, because if a task added in front of the queue (front means, if there are N worker threads, then the task index &lt; N) then <strong>all</strong> the worker threads need to be woken up to update the time which they are waiting for.</p></li>
  <li><p>If there is a separate condition variable for each thread, then we can control which thread to wake up, so in this case we don't need to wake up all threads (we only need to wake up the thread which has the largest waiting time, so we need to manage this value). I'm currently thinking about implementing this, but working out the exact details are complex. Are there any recommendations/thoughts/document on this method?</p></li>
  </ol>
  
  <hr>
  
  <p>Is there any better solution for this problem? I'm trying to use standard C++ features, but I'm willing to use platform dependent (my main platform is linux) tools too (like pthreads), or even linux specific tools (like futexes), if they provide a better solution.</p>