Analysis of SRPT Scheduling: Investigating Unfairness

Abstract

The Shortest-Remaining-Processing-Time (SRPT) scheduling policy has long been known to be optimal for minimizing mean response time. Despite this fact, SRPT scheduling is rarely used in practice. It is believed that the performance improvements of SRPT over other scheduling policies with respect to mean response time stem from the fact that SRPT unfairly penalizes the large jobs in order to help the small jobs. This belief has caused people to instead adopt "fair" scheduling policies such as Processor-Sharing (PS), which produces the same expected slowdown for jobs of all sizes. This paper investigates formally via analysis the problem of unfairness in SRPT. The analysis assumes an M/G/1 model, but emphasizes heavy tailed job size distributions, as are characteristic of empirical workloads. We end with a trace-driven simulation experiment which agrees with the analysis, even though arrivals are no longer Poisson.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 2000
Accession Number
ADA382309

Entities

People

  • Mor Harchol-balter
  • Nikhil Bansal

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Materials and Manufacturing Processes
  • Space

DTIC Thesaurus Topics

  • Algorithms
  • Computer Science
  • Computers
  • Equations
  • Intervals
  • Law
  • Measurement
  • Network Protocols
  • Nutrition Disorders
  • Observation
  • Operating Systems
  • Operations Research
  • Probability
  • Probability Density Functions
  • Scheduling (Production)
  • Simulations
  • Workload

Fields of Study

  • Computer science

Readers

  • Mathematical Modeling and Probability Theory.
  • Parallel and Distributed Computing.
  • Regression Analysis.