Algorithms for scheduling independent tasks on to the processors of a multi
processor system must trade-off processor load balance, memory locality, an
d scheduling overhead. Most existing algorithms, however, do not adequately
balance these conflicting factors. This paper introduces the Self-Adjustin
g Dynamic Scheduling (SADS) class of algorithms that use a unified cost mod
el to explicitly account for these factors at runtime. A dedicated processo
r performs scheduling in phases by maintaining a tree of partial schedules
and incrementally assigning tasks to the least-cost schedule. A scheduling
phase terminates whenever any processor becomes idle, at which time partial
schedules are distributed to the processors. An extension of the basic SAD
S algorithm, called DBSADS, controls the scheduling overhead by giving high
er priority to partial schedules with more task-to-processor assignments. T
hese algorithms are compared to two distributed scheduling algorithms withi
n a database application on an Intel Paragon distributed-memory multiproces
sor system.