Shortest remaining processing time
Shortest remaining processing time is a preemptive scheduling policy that serves the ready job with the least remaining service requirement.
Ideal model: one server, known service requirements and cost-free preempt-resume give SRPT its mean-response-time optimality; an estimated size or multiple servers changes the problem. Remaining work is not original size or elapsed wall time. [1]
The published web-server implementation approximated priorities with size bands and updated them as data was sent. Its Linux 2.2.16 network-bottleneck experiments are not SSD benchmarks. [2]
In a constructed three-job example, SRPT reduces mean response from 8 to 4 ms while one job rises from 8 to 10 ms. Lower mean latency therefore does not establish a per-request deadline. [3]
Relations
- related
- Request slowdown, Service time, Work-conserving scheduler, I/O scheduler, Semi-preemptible I/O
Citations
- Harchol-Balter and Scully. The most common queueing theory questions asked by computer systems practitioners. Sections 2.1 and 3.
- Harchol-Balter et al. Size-based Scheduling to Improve Web Performance. TOCS 2003; author manuscript, sections 2.2 and 3.1.
- Hesela: a finite SRPT trace and distinct slowdown denominators.
Sources & caveats
- Primary-source synthesis and an exact synthetic trace; no device or scheduler benchmark.
- Paper implementation and ideal policy are distinguished; no universal starvation or deadline guarantee is claimed.