| We begin by studying optimal scheduling policies in a single-server system and optimal dispatching policies in systems with multiple parallel queues and servers. With different assumptions of system characteristics (e.g. workload patterns) and performance requirements (e.g. mean response time and mean slowdown), the optimal scheduling policies differ vastly. As an example, in a system with a single queue, we show that a scheduling policy can be the best scheduling policy for one kind of service-time distributions and at the same time the worst for another, and that a scheduling policy can be the best policy in terms of mean slowdown but the worst in terms of mean response time.; Since there is no such thing as ubiquitous optimality, we put our efforts into two directions. First, inspired by the observation that the variability of service time is a dominant factor on the optimality of scheduling policies, we set constraints on service-time variability and investigate the best and worst scenarios in terms of mean response time for several scheduling policies on a single-server queue. Second, we propose a configurable policy that can be tuned with a parameter. This configurable policy is not only analyzed in both deterministic and stochastic configurations, but also implemented in Linux as a kernel scheduler. We justify by experiments our claim that the ubiquitous optimality can now be achieved by configurability. |
