Intel® oneAPI Threading Building Blocks
Ask questions and share information about adding parallelism to your applications when using this threading library.

Approximating FIFO scheduling?


Does anyone have suggestions for how I can use TBB to solve the following problem?

I'm working on a soft-realtime simulator which will generate lots and lots of small tasks.  I.e., tasks which would be good candidates for modeling with TBB::task.  Each task has a timestamp, indicating when in simualtion-time its results are (ideally) available.  These tasks are submitted to my code over time as the simulator executes.  I need to ultimately ensure that, one way or another, these tasks are executed in approxitmately the order of their associated timestamps.  Each of these tasks is independent of the others, as far as dependencies.

One key detail is that the application needs the freedom to upgrade the urgency of a task after submitting it to my code. 

So my solution *was* going to be:

  • My code maintains a priority queue of tasks which the app has sent me, but which I haven't yet passed on to TBB for execution.
  • If the app wants to change a task's priority, it can only do so if my code hasn't yet submitted the task to TBB. 
  • I let the user specify how many tasks are concurrently submitted at one time by my code to TBB.  This represents the tradeoff between maximizing parallelism, and maximizing the app's ability to modify task priorities after the tasks have been first submitted.

The main problem I'm running into is, how do I ensure lack of starvation of a given task?  For example, suppose the user has specified that 10 tasks may be concurrently in flight with TBB.  If one of those tasks completes execution, I'll immediately pull the next task out of my priority queue and submit it to TBB.  However, this raises the possibility that one of those other 9, already in-flight tasks will be starved.  This would be a problem, because it would mean the simulation-timestamp deadline of that starving task wasn't being respected.

I've considered using a sepate task group for each of those (in this case) 10 slots, and if some slot's task seemed to be taking too long, bump up that task group's priority until the group's task completed.  But that was so elaborate that I had to wonder if I'm re-inventing the wheel. 

0 Kudos
1 Reply
Valued Contributor III

If tasks are (finite and) enqueued, starvation would already seem to be avoided? It is also perfectly valid for a tbb::task to be a generic execution engine for a (non-TBB) task popped just in time from a concurrent_priority_queue. And perhaps you might merge the now strictly hierarchical priority and timestamp, by ordering on the sum of a priority-related delta and the original timestamp.

0 Kudos