Abstract
Task scheduling is concerned with the sequence in which tasks entering a multiprocessor system are served. Task scheduling policies can be generally classified as eager scheduling and lazy scheduling. The former attempts to schedule the tasks whenever there are free processors available, while the latter delays the scheduling of some tasks so as to accommodate more appropriate tasks. In this paper we propose a topology-independent hybrid policy that combines the benefits of both. The new scheduling strategy, called the eager scheduling with lazy retry (ESLR) policy, tries to schedule a task eagerly upon its arrival. If the scheduling fails, then the task is rescheduled after a delay period. This delay in rescheduling gives tasks with different processor requests an equal opportunity to compete for free processors. The proposed scheduling policy is independent of the topology of the underlying multiprocessor. To study its performance, we simulated and compared several scheduling policies on hypercube multiprocessors. The results show that this ESLR policy can achieve a better system performance than previous approaches. We will study various considerations in implementing the ESLR policy and discuss their effects on the system performance.