Scalable scheduling of parallel servers

With the increasing use of distributed systems, designing effective task scheduling policies becomes increasingly crucial. We study scheduling for tightly coupled server systems (a single queue for all servers) and loosely coupled server systems (a system of several identical servers in parallel, where a routing decision must be made immediately upon a task's arrival). For a loosely coupled server system, when task processing times are known upon arrival and follow a discrete distribution, we propose to use multi-layered round robin routing followed by shortest remaining processing time (SRPT) local scheduling at each server. We show that this policy has the same heavy traffic limit as an optimal scheduling policy for a tightly coupled server system. We also design a policy with modified multi-layered round robin routing and SRPT local scheduling, which provides optimal performance in both heavy and light traffic. For a continuous task processing time distribution, we propose to use a preemptive priority queue to approximate SRPT, and demonstrate that its performance is superior to other size based policies. When task processing times are unknown upon arrival and follow a distribution with decreasing hazard rate, we suggest the use of foreground background processing sharing (FBPS) as the local scheduling policy.; If the servers are not identical (the service rate at each server is different), we can use the insights developed for policies for homogeneous server systems to design policies which achieve good system performance. Taking SRPT as the local scheduling policy and using a heavy traffic approximation, we derive policies which perform the same as an SRPT single super server system where the service rate is the sum of the service rates at each server.