Contents

Work-conserving scheduler

Similarly, when referring to CPU scheduling, i.e. threads or processes scheduled over one or more available processorsorcores, a work-conserving scheduler^[3] ensures that processors/cores are not idle if there are processes/threads ready for execution.

Kleinrock's Conservation Law[edit]

Work-conserving schedulers are also notable for obeying Kleinrock's Conservation Law.^[4][5]

In the context where we have ${\displaystyle N}$ connections with Poisson-distributed arrival rates ${\displaystyle \lambda _{n}}$ packets per unit time each competing for scheduling time, Leonard Kleinrock established the following conservation law:

${\displaystyle \sum \limits _{n=1}^{N}\rho _{n}q_{n}=C}$ where ${\displaystyle \rho _{n}={\frac {\lambda _{n}}{\mu _{n}}}}$

• ${\displaystyle \lambda _{n}}$: The mean packet rate of connection ${\displaystyle n}$ in packets per unit time.
• ${\displaystyle \mu _{n}}$: The number of packets of connection ${\displaystyle 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.
• ${\displaystyle \rho _{n}}$: The link utilization contributed by a particular flow.
• ${\displaystyle q_{n}}$: The expected time a packet from connection ${\displaystyle n}$ sits in a buffer before the scheduler serves it in units of time.
• ${\displaystyle 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 ${\displaystyle \rho _{n}q_{n}={\frac {\lambda _{n}q_{n}}{\mu _{n}}}}$. Notice that ${\displaystyle \lambda _{n}q_{n}}$ is the expected number of buffered packets from flow ${\displaystyle n}$, and therefore the expected time to clear them from the buffer is this over the service rate ${\displaystyle \mu _{n}}$.

(Some sources use ${\displaystyle \mu _{n}}$ to mean the time to service a particular packet with units of unit time per packet, and use ${\displaystyle \rho _{n}=\lambda _{n}\mu _{n}}$. The equation is the same, the only difference being their ${\displaystyle \mu _{n}}$ is the reciprocal of the one presented above.)

Comparison to Non-Work Conserving Schedulers[edit]

Non-work conserving schedulers are sometimes useful to enhance predictability and reduce termination jitter for the activities carried out by a computing and communication system. In multi-processor systems they're useful to enhance performance in some scenarios.^{[6] [7]} Sometimes, a non-work conserving scheduler may be useful to enhance stability of a system; For example, a process scheduler may choose to keep processes off of the run queue if there were concern that the sum of the working sets of all of the runnable processes would exceed available memory and lead to non-linear page thrashing overhead. Limiting the run queue in this manner might lead to under-utilization of available processors (and hence be non-work conserving) with the goal of avoiding situations where the system is unusable due to thrashing.

References[edit]