Take the 2-minute tour ×

I implemented a scheduler task delegation scheduler instead of a task stealing scheduler. So the basic idea of this method is each thread has its own private local queue. Whenever a task is produced, before the task gets enqueued to the local queues, a search operation is done among the queues and minimum size queue is found by comparing each size of the queues. Each time this minimum size queue is used to enqueue the task. This is a way of diverting the pressure of the work from a busy thread's queue and delegate the jobs to the least busy thread's queue.

The problem in this scheduling technique is, we dont know how much time each tasks takes to complete. ie. the queue may have a minimal count, but the task may be still operating, on the other hand the queue may have higher value counter, but the tasks may be completed very soon. any ideas to solve this problem?

I am working on linux, C++ programming language in our own multithreading library implementing a multi-rate synchronous data flow paradigm .

share|improve this question
Sounds like the wrong strategy to me if the task completion times can vary so wildly. Do you have to do it this way? –  jlew Feb 13 '13 at 13:37
@jlew Usually are all the tasks execution time are almost equivalent (or) it will vary wildly. what is general thing prevelant –  Dev Feb 13 '13 at 13:42
@jlewIs the question clear? –  Dev Feb 13 '13 at 14:09
It seems insoluble without more metadata about each task's run time, hence task-stealing and simple shared-queue pools. –  Martin James Feb 13 '13 at 14:56

2 Answers 2

It seems that your scheduling policy doesn't fit the job at hand. Usually this type of naive-scheduling which ignores task completion times is only relevant when tasks are relatively equal in execution time. I'd recommend doing some research. A good place to start would be Wikipedia's Scheduling article but that is of course just the tip of the iceberg. I'd also give a second (and third) thought to the task-delegation requirement since timeslicing task operations allows you to fine grain queue management by considering the task's "history". However, if clients are designed so that each client consistently sends the same "type" of task, then you can achieve similar results with this knowledge.

share|improve this answer

As far as I remember from my Queueing Theory class the fairest (of them all;) system is the one which has a single queue and multiple servers. Using such system ensures the lowest expected average execution time for all tasks and the largest utilization factor (% of time it works, I'm not sure the term is correct).

In other words, unless you have some priority tasks, please reconsider your task delegation scheduler implementation.

share|improve this answer

Your Answer


