The Susceptibility of Programs to Context Switching

Modern memory systems are composed of several levels of caching. Design of these levels is largely an empirical practice. One highly-effective empirical method is the single-pass method wherein all caches in a broad design space are evaluated in one pass over the trace. Multiprogramming degrades memory system performance since (process) context switching reduces the effectiveness of cache memories. Few single-pass methods exist which account for multiprogramming effects. This paper uses a general model of single-pass algorithms, the recurrence/conflict model, and extends the model for recording the effects due to both voluntary context switches (e.g., system calls) and involuntary context switches (e.g., time quantum expiration). Involuntary context switches are modeled using the distribution of lengths between a reference to an address and the re-reference to the same address. The paper makes the assumptions that involunary context switches are equally likely to occur between each reference, and that one can independently estimate, fcs, the fraction of a cache’s contents flushed between context switches. The case where fcs= 1 is used to measure the effect of worst-case context switch penalty (the susceptibility) of several members of the SPEC89 benchmark set to context switching. Some empirical results of fcs are presented to illustrate the case where fcs< 1. The model is validated against its assumptions by comparing its results with more-restrictive methods.