Work-conserving scheduler
In computing and communication systems, a work-conserving scheduler is a scheduler that always tries to keep the scheduled resource(s) busy, if there are submitted jobs ready to be scheduled.
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computing and communication systems, a work-conserving scheduler is a scheduler that always tries to keep the scheduled resource(s) busy, if there are submitted jobs ready to be scheduled. In contrast, a non-work-conserving scheduler is a scheduler that, in some cases, may leave the scheduled resource(s) idle despite the presence of jobs ready to be scheduled.
For example, when dealing with networking and packet scheduling, a work-conserving scheduler leaves the channel idle only when there are no packets to transmit. In contrast, a non-work-conserving scheduler might leave the channel idle with packets still pending transmission.
Similarly, when referring to CPU scheduling, i.e. threads or processes scheduled over one or more available processors or cores, a work-conserving scheduler ensures that processors/cores are not idle if there are processes/threads ready for execution. \sum\limits_{n = 1}^N \rho_n q_n = C where \rho_n = \frac{\lambda_n}{\mu_n} \lambda_n : The mean packet rate of connection n in packets per unit time. \mu_n : The number of packets of connection n that the system overall could transmit per unit time, in units of packets. This can vary between flows if flows have differently sized packets. \rho_n : The link utilization contributed by a particular flow. q_n : The expected time a packet from connection n sits in a buffer before the scheduler serves it in units of time.
C : A constant - the expected time to clear out all buffered packets from all flows at any given point in time if they are transmitted at maximum service rate with no breaks. To understand why, observe that \rho_n q_n = \frac{\lambda_n q_n}{\mu_n} .
Notice that \lambda_n q_n is the expected number of buffered packets from flow n , and therefore the expected time to clear them from the buffer is this over the service rate \mu_n . (Some sources use \mu_n to mean the time to service a particular packet with units of unit time per packet, and use \rho_n = \lambda_n \mu_n . The equation is the same, the only difference being their \mu_n is the reciprocal of the one presented above.)
Text derived from https://en.wikipedia.org/w/index.php?oldid=1282436840 under CC BY-SA 4.0; modifications have been made.