CSched: Real-time disk scheduling with concurrent I/O requests

We present a new real-time disk scheduling algorithm, Concurrent Scheduler or CSched, which maximizes throughput for modern storage devices while providing real-time access guarantees, with computational costs of $O(\log n)$. To maximize performance it ensures request concurrency at the device and maximizes the depth of a new Limited Cyclical SCAN (L-CSCAN) queue that optimizes the request sequence sent to the device. For real-time requests there is an additional SCAN-EDF queue in front of the L-CSCAN queue to absorb bursts of real- time requests until they can be drained to the L-CSCAN queue. The real-time guarantees are provided by managing the worst-case latency at each stage of the pipeline: SCAN-EDF, L-CSCAN, and device. CSched is configured by the tuple {λ, σ, δ, τ(r), N}, where λ and σ are the minimal initial slack time and workload burstiness and are properties of the workload, and where δ, &tau(r);, and N are the device worst-case latency, worst-case throughput rate time for a request, and maximal number of concurrent requests, and are experimentally determined properties of the storage device. An experimental evaluation of CSched shows that given sufficient initial slack time, the system throughput performance costs of providing real-time guarantees are negligible.