Capricious Job Scheduling
Posted 12:16 PM

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

 IIIIIIIIICCCCCCCCCCCCIIIIIIIIIIIIIICCCCCCCCCCCCC
 IIIIIIIIICCCCCCCCCCCCIIIIIIIIIIIIIICCCCCCCCCCCCC
 IIIIIIIIICCCCCCCCCCCCIIIIIIIIIIIIIICCCCCCCCCCCCC
 IIIIIIIIICCCCCCCCCCCCIIIIIIIIIIIIIICCCCCCCCCCCCC
 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
   IIIIIIIIICCCCCCCCCCCCIIIIIIIIIIIIIICCCCCCCCCCCCC
  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.

[View/Post Comments] [Digg] [Del.icio.us] [Stumble]