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. 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[1][2] leaves the channel idle only when there are no packets to transmit, whereas 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[3] ensures that processors/cores are not idle if there are processes/threads ready for execution.

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.[4] [5] 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

  1. Padma Mundur, Improving QOS in IP Networks (course material for Multimedia Networking)
  2. Jon Crowcroft, Scheduling and queue management (course material for Digital Communications II)
  3. G. Buttazzo, G. Lipari, L. Abeni, M. Caccamo, Soft Real-Time Systems: Predictability vs. Efficiency, Springer 2005
  4. A. Fedorova, M. Seltzer and M.D. Smith, "A non-work-conserving operating system scheduler for SMT processors," in Proceedings of the Workshop on the Interaction between Operating Systems and Computer Architecture, in conjunction with ISCA 2006
  5. J. C. Sáez, J. I. Gomez and M. Prieto, "Improving Priority Enforcement via Non-Work-Conserving Scheduling," Parallel Processing, 2008. ICPP '08. 37th International Conference on, Portland, OR, 2008, pp. 99-106.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.