Question

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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top