Affinity scheduling of unbalanced workloads

Shared memory multiprocessor systems are becoming increasingly important and common. Multiprocessor environments are significantly different from uniproces­sor environments, raising new scheduling issues that need to be considered. A funda­mental scheduling issue arises in situations in which a unit of work may be processed more efficiently on one processor than on any other, due to factors such as the rate at which the required data can be accessed from the given processor. The unit of work is said to have an "affinity" for the given processor, in such a case. The scheduling issue that has to be considered is the trade off between the goals of respecting proces­sor affinities (so as to obtain improved efficiencies in execution) and of dynamically assigning each unit of work to whichever processor happens to be, at the time, least loaded (so as to obtain better load balance and decreased processor idle times). A specific context in which the above scheduling issue arises is that of shared memory multiprocessors with large, per-processor caches or cached main memories. The shared-memory programming paradigm of such machines permits the dynamic scheduling of work. The data required by a unit of work may, however, often reside' mostly in the cache of one particular processor, to which that unit of work thus has affinity. In this thesis, the design of "affinity scheduling" algorithms, in which both affinity and load balancing considerations play major roles in the scheduling policy, is explored. Two new affinity scheduling algorithms are proposed for a context in which the units of work have widely varying execution times. An experimental study of these algorithms finds them to be superior to the previously proposed algorithms 'in this context.