quantifying the cost of context switching

Paper: Quantifying the Cost of Context Switch by Chuanpeng Li, Chen Ding, and Kai Shen (ExpCS 2007).

Measuring the indirect cost of the context switch is a challenge. This paper does it in an experimental setup through synthetic workloads and also shows the impact of OS background interrupt handling on the measurement.

introduction #

Multitasking system: context switch is switching of the CPU from one thread to another. It makes multitasking possible but also causes system overhead.

direct cost #

• Process registers need to be saved and restored
• The OS kernel code (scheduler) needs to execute
• TLB entries need to be reloaded
• Process pipeline must be flushed

indirect cost #

• Cache sharing between multiple processes causes performance degradation
• Varies for different memory access patterns and workloads

measurement approach #

Ousterhout measured the direct cost using a benchmark with 2 processes communicating with 2 pipes. McVoy measured using lm-bench.

This paper uses pipe communication to implement frequent context switches between 2 processes.

• C1: direct cost of the context switch using Ousterhout method where the process makes no data access
• C2: total cost of context switch where each process allocates and accesses an array of floating point numbers
• Indirect cost = C2 - C1

direct cost measurement (C1) #

Two processes send single byte messages to each other via two pipes. During each round-trip, there are 2 context switches + one read and write syscall in each process. Measure the time cost of 10K round-trip communications (T1).

Single process simulating 2-process communication by sending a single byte message to itself via one pipe. Each round trip includes one read and one write syscall. Measure the time cost of 10K round-trip communications (T2).

Direct time cost per context switch: C1 = T1/20K - T2/10K

total cost measurement (C2) #

Same as before but with array access before writing message to the other process, then blocking on the next read operation.

• S1: execution time of 10K round-trip communications between two test processes
• S2: execution time of 10K simulated round-trip communications

Total time cost per context switch: C2 = S1/20K - S2/10K

Parameters changed during different runs: array size, access stride.

avoiding potential interference #

We need to avoid interference from other processes or background interrupt handling of the OS.

• Use a dual processor machine. Background handlers default to one processor, we use the other for experiments and simulations.
• Real-time scheduling with max priority. Linux syscalls sched_setaffinity() and sched_setscheduler() are used to effect the design.

time measurement #

High resolution timer that relies on a counting register in the CPU. It measures the time by counting the number of cycles the CPU has gone through since startup. We measure the cost of a large number of context switches and then report the average to offset the overhead of the timer itself.

experimental results #

Machine: IBM eServer with dual 2.0 GHz Intel Pentium Xeon CPUs. L2 cache: 512 KB, cache line size: 128 B. OS: Linux 2.6.17 kernel with Redhat 9. Compiler: gcc 3.2.2 (no optimization for compilation).

Average direct context switch cost (C1): 3.8 microseconds.

Total cost per context switch (C2): several microseconds to thousands.

effect of data size #

Each process sequentially traverses an array of size D between context switches. Each process does read, write or RMW on each array element.

Array size 1-200 KB: context switch 4.2 to 8.7 microseconds. The entire dataset combined between both processes fits in the L2 cache.

Array size 256-512 KB: context switch 38.9 to 203.2 microseconds. The dataset does not fit in the L2 cache for both processes but still fits for the simulated process. Upon each context switch, the process needs to refill the L2 cache with its own data. Additional costs also from frequent cache warmups. At array size 384 KB, the costs start to differ based on data access type.

Array size > 512 KB: context switch is even more. The dataset does not fit in the cache for both cases. We also get cache interference. There are cache misses. Interference manifests as cache warmups in the case of context switches. Non-linear effect of cache sharing.

effect of access stride #

Each process accesses an array of floating point numbers in a stride pattern and does RMW operation on each element.

Array size 32-128 KB: datasets fit in cache, no difference in context switch cost when we change the stride.

When the datasets don’t fit in the cache, there will be a cost of context switch with respect to stride:

• Stride 8 B: cost 44.1 - 183.9 microseconds
• Stride 128 B: cost 133.8 - 1496.1 microseconds

The data access pattern can affect the cost of context switch significantly. Stride affects the cache warmups.

effect of experimental environment #

• Dual processor: with the design of deploying the processes with real-time scheduling priority
• Single processor: same setup but with disabled multiprocessor support in Linux kernel

It was run on a quiet environment and external noisy environment. There was interference in the environment.

summary #

The indirect cost of context switches ranges from several microseconds to more than one thousand microseconds. When the data size is larger than the L2 cache, the cost of context switches increases monotonically with the data size and also based on access stride. The larger the stride, the more the cost.