Analysis of task migration in shared-memory multiprocessor scheduling
- 2 April 1991
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 19 (1), 143-155
- https://doi.org/10.1145/107972.107987
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 an 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 illustrate 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.Keywords
This publication has 15 references indexed in Scilit:
- Adaptive load sharing in heterogeneous distributed systemsJournal of Parallel and Distributed Computing, 1990
- Analysis of the effects of delays on load sharingIEEE Transactions on Computers, 1989
- A comparison of receiver-initiated and sender-initiated adaptive load sharingPerformance Evaluation, 1986
- A comparison of priority-based decentralized load balancing policiesPublished by Association for Computing Machinery (ACM) ,1986
- Load-balancing heuristics and process behaviorPublished by Association for Computing Machinery (ACM) ,1986
- A distributed load‐balancing policy for a multicomputerSoftware: Practice and Experience, 1985
- Optimal static load balancing in distributed computer systemsJournal of the ACM, 1985
- Load Sharing in Distributed SystemsIEEE Transactions on Computers, 1985
- Dual Processor Scheduling with Dynamic ReassignmentIEEE Transactions on Software Engineering, 1979
- A Proof for the Queuing Formula: L = λWOperations Research, 1961