On fair size-based scheduling

By executing jobs serially rather than in parallel, size-based scheduling policies can shorten time needed to complete jobs; however, major obstacles to their applicability are fairness guarantees and the fact that job sizes are rarely known exactly a-priori. Here, we introduce the Pri family of size-based scheduling policies; Pri simulates any reference scheduler and executes jobs in the order of their simulated completion: we show that these schedulers give strong fairness guarantees, since no job completes later in Pri than in the reference policy. In addition, we introduce PSBS, a practical implementation of such a scheduler: it works online (i.e., without needing knowledge of jobs submitted in the future), it has an efficient O(log n) implementation and it allows setting priorities to jobs. Most importantly, unlike earlier size-based policies, the performance of PSBS degrades gracefully with errors, leading to performances that are close to optimal in a variety of realistic use cases.