Analysis of task migration in shared-memory multiprocessor scheduling

Abstract

In shared-memory multiprocessor systems it may be more efficient to schedule a task on one processor than on mother, Due to the inevitability of idle processors in these environments, there exists en important tradeoff between keeping the workload balanced and scheduling tasks where they run most efficiently. The purpose of an adaptive task migration policy is to determine the appropriate balance between the extremes of this load sharing tradeoff. We make the observation that there are considerable differences between this load sharing problem in distributed and shared-memory multiprocessor systems, and we formulate a queueing theoretic model of task migration to study the problem. A detailed mathematical analysis of the model is developed, which includes the effects of increased contention for system resources induced by the task migration policy. Our objective is to provide a better understanding of task migration in shared-memory multiprocessor environments. In particular, we illus tratc the potential for significant improvements in system performance, and we show that even when migration costs are large it may still be beneficial to migrate waiting tasks to idle processors. We further demonstrate the potential for unstable behavior under migratory scheduling policies, and we provide optimal policy thresholds that yield the best performance and avoid this form of processor thrashing.