Capricious Job Scheduling

May 30, 2014

Using a perfectly fair scheduler, I launch 5 processes with the following pattern:

IIIIIIIIICCCCCCCCCCCCIIIIIIIIIIIIIICCCCCCCCCCCCC

Where 'I' is one second of I/O intensive operation, and 'C' is one second of CPU intensive operation. The result of a perfectly fair scheduler is that there will be periods of high I/O contention and high CPU contention, as the 5 processes are "fairly" switched between, and each keeps the pace with the other.

Using a more "capricious" scheduler, where processes may "get lucky" for a while, my processes will be staggered

IIIIIIIIICCCCCCCCCCCCIIIIIIIIIIIIIICCCCCCCCCCCCC lucky (goes first)

IIIIIIIIICCCCCCCCCCCCIIIIIIIIIIIIIICCCCCCCCCCCCC unlucky (goes last)

IIIIIIIIICCCCCCCCCCCCIIIIIIIIIIIIIICCCCCCCCCCCCC

It's clear that "everyone wins" when this method is chosen.

My argument for "capricious" scheduling is that a system cannot know, in advance whether something will be an I or a C. Programs can be profiled over time (modern o/s systems don't do this... but probably should), but most program execution paths vary to the point where profiling may be impractical. Accordingly, a scheduler should be, to some extent, random.

erik’s Substack

Discussion about this post