Server scheduling to balance priorities, fairness, and average quality of service

Abstract

Often server systems do not implement the best known algorithms for optimizing average Quality of Service (QoS) out of concern that these algorithms may be insufficiently fair to individual jobs. The standard method for balancing average QoS and fairness is to optimize the ℓp norm, 1 < p < ∞. Thus we consider server scheduling strategies to optimize the ℓp norms of the standard QoS measures, flow and stretch. We first show that there is no no(1)-competitive online algorithm for the ℓp norms of either flow or stretch. We then show that the standard clairvoyant algorithms for optimizing average QoS, Shortest Job First (S.JF), and Shortest Remaining Processing Time (SRPT), are scalable for the ℓp norms of flow and stretch. We then show that the standard nonclairvoyant algorithm for optimizing average QoS, Shortest Elapsed Time First (SETF), is also scalable for the ℓp norms of flow. We then show that the online algorithm, Highest Density First (HDF), and the nonclairvoyant algorithm, Weighted Shortest Elapsed Time First (WSETF), are scalable for the weighted ℓp norms of flow. These results suggest that the concern that these standard algorithms may unnecessarily starve jobs is unfounded. In contrast, we show that the Round Robin, or Processor Sharing, algorithm, which is sometimes adopted because of its seeming fairness properties, is not O(1 + ∈)-speed, no(1)-competitive for sufficiently small ∈. © 2010 Society for Industrial and Applied Mathematics.