Performance of hierarchical processor scheduling in shared-memory multiprocessor systems

Processor scheduling policies for multiprocessor systems can be broadly div ided into space-sharing and time-sharing policies. Space-sharing policies d ivide the system processors into a number of partitions and each partition is exclusively allocated to a single job. In time-sharing policies, process ors are temporally shared by jobs. Several space-sharing and time-sharing p olicies have been proposed for small-scale shared-memory systems and requir e a central run queue and/or central scheduler. The central queue/scheduler poses serious scalability problems for large-scale multiprocessor systems. Furthermore, space-sharing and time-sharing policies have their advantages and disadvantages. In this paper, we propose a new multiprocessor scheduli ng policy that eliminates contention for the central queue/scheduler. Our h ierarchical scheduling policy (HSP) is a self-scheduling policy and uses a hierarchical run queue organization to facilitate processor allocation to j abs. We show that the HSP policy is considerably better than purely space-s haring and purely time-sharing policies over a wide range of system and wor kload parameters of interest.