TR-95-21: Reducing Contention for Run Queue in Shared-Memory Multiprocessor Systems

Performance of parallel processing systems is sensitive to various hardware and software overheads and contention for hardware and software resources. Hardware resources such as interconnection network and memory introduce communication contention and memory contention that could seriously impact overall system performance. Software resources include critical data structures maintained by application software as well as by the system software.In process scheduling context, run queue is a critical data structure that could potentially affect the overall system performance. There are two basic run queue organizations: centralized and distributed. Many shared-memory multiprocessor systems use the centralized organization in which a single global run queue is shared by all processors in the system. We will first identify performance problems associated with these two organizations and then discuss some means to alleviate these problems. We then present a hierarchical task queue organization that incorporates the merits of these two queue organizations. Performance of the hierarchical organization is shown to inherit the good characteristics of the centralized and distributed organizations while avoiding the pitfalls associated with them. Thus, the hierarchical organization is useful in building large-scale multiprocessor systems.