The impact of operating system scheduling policies and synchronization methods of performance of parallel applications

Shared-memory multiprocessors are frequently used as compute servers with multiple parallel applications executing at the same time. In such environments, the efficiency of a parrdlel ap-plication can be significantly affected by the operating system scheduling policy. In this paper, we use detailed simulation stud-ies to evaluate the performance of several different scheduling strategies, These include regular priority scheduling, coschedul-ing or gang scheduling, process control with processor partition-ing, handoff scheduling, and affinity-based scheduling. We also explore tradeoffs between the use of busy-waiting and block-ing synchronization primitives and their interactions with the scheduling strategies. Since effective use of caches is essential to achieving high performance, a key focus is on the impact of the scheduling strategies on the caching behavior of the applica-tions. Our results show that in situations where the number of pro-cesses exceeds the number of processors, regular priority-based scheduling in conjunction with busy-waiting synchronization primitives results in extremely poor processor utilization. In such situations, use of blocking synchronization primitives can signif-icantly improve performance. Process control and gang schedul-ing strategies are shown to offer the highest performance, and their performance is relatively independent of the synchroniza-tion method used. However, for applications that have sizable working sets that fit into the cache, process control performs better than gang scheduling. For the applications considered, the performance gains due to handoff scheduling and processor affinity are shown to be small. 1