Performance Analysis of Modified SRPT in Multiple-Processor Multitask Scheduling
share
In this paper we study the multiple-processor multitask scheduling problem in both deterministic and stochastic models. We consider and analyze Modified Shortest Remaining Processing Time (M-SRPT) scheduling algorithm, a simple modification of SRPT, which always schedules jobs according to SRPT whenever possible, while processes tasks in an arbitrary order. The M-SRPT algorithm is proved to achieve a competitive ratio of Θ(logα +β) for minimizing response time, where α denotes the ratio between maximum job workload and minimum job workload, β represents the ratio between maximum non-preemptive task workload and minimum job workload. In addition, the competitive ratio achieved is shown to be optimal (up to a constant factor), when there are constant number of machines. We further consider the problem under Poisson arrival and general workload distribution (, M/GI/N system), and show that M-SRPT achieves asymptotic optimal mean response time when the traffic intensity ρ approaches 1, if job size distribution has finite support. Beyond finite job workload, the asymptotic optimality of M-SRPT also holds for infinite job size distributions with certain probabilistic assumptions, for example, M/M/N system with finite task workload.
READ FULL TEXT