Reducing run queue contention in shared memory multiprocessors

A run queue is a critical data structure that can affect overall performance in shared memory multiprocessor systems. Both of the basic run queue organizations, centralized and distributed, present performance problems. Among the techniques that mitigate these problems, none is completely satisfactory. This article compares uniform-memory-access multiprocessors with nonuniform-memory-access multiprocessors and describes the two basic run queue organizations, citing their main drawbacks. A look at the techniques for improving performance in these basic organizations sets the stage for the introduction of the hierarchical run queue organization. The hierarchical organization inherits the best features of the centralized and the distributed organizations while avoiding their pitfalls. In the hierarchical organization, a set of task queues is organized as a tree, and the processors with their local queues are attached to the bottom level of the tree as leaf nodes. The tree branching factor and the transfer factor, which indicates the number of tasks transferred from a parent queue to a child queue in the hierarchy, are shown to be the key design issues. Average response time of the three organizations as a function of system utilization reveals that the hierarchical organization provides the best performance for all levels of system utilization. The article concludes that this run queue organization will prove to be a useful mechanism for building large-scale shared memory multiprocessor systems.