Scheduling for Performance
Ethan D. Bolker

My research in computer performance focuses on the use of queueing theory models to understand and predict system behavior. I have applied those tools in several areas: memory modeling, fair share and goal mode scheduling, understanding measured CPU queue lengths in Microsoft NT and Windows 2000 operating systems, Intel's hyper-threading architecture, and various virtualization disciplines. I like to build analytic models and validate them against measured data from real applications and from benchmarks I write.

Some of my work:

Some references:


Berkeley bibliographies
http://now.cs.berkeley.edu/Implicit/schedule.short-bib.html
http://now.cs.berkeley.edu/Implicit/schedule.long-bib.html
Andreas S. Schulz
http://web.mit.edu/schulz/www/publications.html
Maui scheduler
http://www.mhpcc.edu/maui/doc/
http://www.mhpcc.edu/research/mi97/97mi02.html
The original fair share papers
http://www.cs.su.oz.au/~piers/papers/Share/share.html
Limits -- A System for UNIX Resource Administration
http://www.c-side.com/c/papers/sc-89.html
Stride Scheduling: Deterministic Proportional-Share Resource Management
(1995)
(Correct) (35 citations)
Carl A. Waldspurger, William E. Weihl
Technical Memorandum MIT/LCS/TM-528 MIT Laboratory for Computer Science (lots of references here) http://citeseer.nj.nec.com/waldspurger95stride.html

Carl A. Waldspurger and William E. Weihl. Lottery Scheduling: Flexible Proportional-Share Resource Management, Proceedings of the First Symposium on Operating Systems Design and Implementation (OSDI '94), pages 1-11, Monterey, California, November 1994
http://www/waldspurger.org/carl/papers/lottery-osdi94.ps.gz

The thesis on which this is based:
Carl A. Waldspurger
Lottery and Stride Scheduling: Flexible Proportional-Share Resource Management
http://www.waldspurger.org/carl/papers/phd-mit-tr667.ps.gz
http://citeseer.nj.nec.com/cachedpage/139485/1

Berkeley talk outline:
Lottery Scheduling: Flexible Proportional-Share Resource Management
Carl A. Waldspurger and William E. Weihl, MIT LCS
http://www.cs.berkeley.edu/~gribble/osprelims/F95/summaries/lottery.html http://www.cs.berkeley.edu/~gribble/osprelims/summaries/lottery_sched.html

Waldspurger's publications: http://www.waldspurger.org/carl/papers.html


Hierarchical Loadable Schedulers
John Regehr
April 27, 1999
http://www.cs.virginia.edu/~jdr8d/holst/prop.html
(probably not relevant - this is a scheduler API specification - unless I really wanted to do some implementation)
Beschreibung des Fair-share Schedulers unter UNICOS
(custom software for a cray)
http://www.zib.de/zibdoc/zib/pvp/scheduler.html
Solaris Resource Manager 1.0: Controlling System Resources Effectively
(white paper)
http://www.sun.com/software/white-papers/wp-srm/

Modelling the Behavior of Solaris Resource Manager
(Batch workloads only - essentially Neil Gunther's earlier CMG paper, using his PDQ packaged M/M/1 formulas. See http://www.perfdynamics.com/ )
http://www.sun.com/blueprints/0899/solaris4.pdf


LSF Standard Edition (SGI product)
Dynamic Resource Sharing for Distributed Computing Environments
http://www.sgi.com/software/lsf/standard.html

Batch jobs are usually resource intensive. LSF Standard Edition allows you to manage the conflicting demands of users to ensure fair sharing of limited computing resources. You can configure shares for users and user groups, so users taking up fewer resources can get higher priority. Some jobs may even be suspended to make room for more urgent jobs.


What's in Store
Todd Walter
Teradata V2R3 brings new additions and enhancements that reflect the changing character of the data warehouse

Fair Share Scheduler. Teradata implements a priority-based fair share scheduler. Using a priority specified for users' sessions, CPU resources are allocated to grant each priority of work a fair share of the system. All work in all internal queues is managed by priority to expedite high-priority work. This facility is being enhanced in V2R3 to allow the definition of user classes and allocation of resources to these classes. It will be possible, for example, to specify that one group of users is confined to only 20 percent of the CPU resources of the system.

http://www.teradatareview.com/9801wltr.htm


http://lass.cs.umass.edu/~lass/papers/abs/TR00-22.abs.html

Surplus Fair Scheduling: A Proportional-Share CPU Scheduling Algorithm for Symmetric Multiprocessors

In this paper, we present surplus fair scheduling (SFS), a proportional-share CPU scheduler designed for symmetric multiprocessors. We first show that the infeasibility of certain weight assignments in multiprocessor environments results in unfairness or starvation in many existing proportional-share schedulers. We present a novel weight readjustment algorithm to translate infeasible weight assignments to a set of feasible weights. We show that weight readjustment enables existing proportional-share schedulers to significantly reduce, but not eliminate, the unfairness in their allocations. We then present surplus fair scheduling, a proportional-share scheduler that is designed explicitly for multiprocessor environments. We implement our scheduler in the Linux kernel and demonstrate its efficacy through an experimental evaluation. Our results show that SFS can achieve proportionate allocation, application isolation and good interactive performance, albeit at a slight increase in scheduling overhead. We conclude from our results that a proportional-share scheduler such as SFS is not only practical but also desirable for server operating systems.


SMART

The Design, Implementation and Evaluation of SMART: A Scheduler for Multimedia Applications, J. Nieh, M. S. Lam. Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles, Saint-Malo, France, October 1997.
http://www.cs.columbia.edu/~nieh/publications/sosp97_fordist.pdf
http://www.cs.columbia.edu/~nieh/publications/sosp97_cdrom/
A Fair Workload Allocation Policy for Heterogeneous Systems Leonidas Georgiadis, Christos Nikolaou, Alexander Thomasian