A scheduling policy for blocked programs in multiprogrammed shared-memory multiprocessors

Abstract

Shared memory multiprocessors are frequently used as compute servers with multiple parallel programs executing: at the same time. In such environments. an operating system switches the contexts of multiple processes. When the operating system switches contexts, in addition to the cost of saving the context of the process being swapped out and that of bringing in the context of the new process to be run, the cache performance nf processors also can be affected. The blocked algorithm improves cache performance by increasing the locality of memory references. In a blocked program using this algorithm, program performance can be significantly affected by the reuse of a block loaded into a cache memory. If frequent context switching replaces the block before it is completely reused, the cache locality in a blocked program cannot be successfully exploited. To address this problem, we propose a preemption-safe policy to utilize the cache locality of blocked programs in a multiprogrammed system. The proposed policy delays context switching until a block is fully reused within a program, but also compensates fbr the monopolized processor time on processor scheduling mechanisms. Our simulation results show that in a situation where blocked programs are nln on multiprogrammed shared-memory multiprocessors, the proposed policy improves the performance of these programs due to a decrease in cache misses. In such situations. it also has a beneficial impact on the overall system performance due to the enhanced processor utilization*.