For both schedulers I have found the definition, that no processor stays idle, if there is more work it can do.

However, I found two different upper bounds on the computation time of $T$. For the following equations $T_{\infty}$ is the computation time on infinite processors and $T_1$ is the duration on one processor.

[1] Greedy Schduler (Theorem 1): $T = T_1/m + T_\infty$

[2] Work-Conserving Scheduler (Theorem 1): $T = (T_1-T_\infty)/m + T_\infty$

Both consider the scheduling of directed acyclic graphs where each vertex $v$ represents a task with a certain execution time and the edges represent precendence constraints between the tasks. I.e. task $v_i$ has to execute before task $v_j$ if there exists an edge $(v_i,v_j)$ between those two tasks. I have x threads that can execute those tasks. However, I am not 100% sure if [2] considers preemptive scheduling for their upper bound, but it does seem to be the case for their theorem 1.

In this presentation (page 41) I have found both equations for an upper bounds of the greedy scheduler.

Is there by definition any difference between the two schedulers?


1 Answer 1


If I understand well, it is the same scheduling method with different names. I think Work-conserving Scheduler is the more "official" one. "greedy" can indeed qualify many aspects of the problem and one should always precise which. greedy algorithm is a paradigm not a specific method for a specific problem.

Anyway about the upper-bound, the presentation of your last link says that it is:

$T < (T_1-T_\infty) / m + T_\infty$

but that a simpler one is generally used:

$T < T_1 / m + T_\infty$

Of course the latter is greater than the former but both are true. Also note that they are both equivalent to $T_\infty$ when $m$ tends to $+\infty$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.