The present invention provides a method, apparatus and article of manufacture for selecting commands to execute from a command queue in a data storage device. The present invention reduces maximum service times under random queued workloads by executing the oldest command in the queue at a constant and predetermined rate. This yields a minimal yet predictable performance penalty, while significantly reducing maximum service times.