In this project, we are to measure the cost of a context switch via a set of experiments. The objectives of this project are a few:

  1. We shall gain experience in reading and writing multiprocessed and multithreaded code as a user of an operating system.
  2. We shall gain insight into some principles of designing and implementing processes and threads in the operating system.
  3. The experience offers us a deeper appreciation of different thread models and their practical implications.
  4. Finally, the project provides experience in designing and documenting systems research experiment procedures, and in illustrating and interpreting systems research experimental results.

Project Description

You are to replicate selected experimental results in the following research paper, and then extend them to measure the cost of a thread switch:

Chuanpeng Li, Chen Ding, and Kai Shen. 2007. Quantifying the cost of context switch. In Proceedings of the 2007 Workshop on Experimental Computer Science (ExpCS ‘07). ACM, New York, NY, USA, Article 2. DOI: https://doi.org/10.1145/1281700.1281702 (Li et al., 2007)

The source code that the authors used in conducting their experiments is at:

https://github.com/cunychenhclass/contextswitchcost

This code will be automatically imported into the project repository upon your acceptance of the assignment described in Project Invitation.

Project Requirement

  • The project is open-ended. You are encouraged to design additional experiments and research questions.

  • The instructor provides an initial reference (Li et al., 2007). Although the paper provides an experimental means to quantify the cost of a context switch, you may have to explore the literature, consult the lecture notes, and discuss with the instructor to understand the paper. You will need to show a good grasp of the paper, including the research questions the authors sought to answer and the experimental approach used.

  • You will conduct a series of experiments to measure the cost of a context switch to replicate the results documented in the paper. To meet the requirement, you shall investigate at minimum the effect of one meaningful factor on the cost of a context switch. For instance, Figure 2 in Li et al. (Li et al., 2007) illustrates the cost of a context switch measured in the authors’ experiments in relation to two factors: array size and stride.

  • You will carry out the designed experiments and record the experiment results. As an empirical study, a single run is not evidence: you must run each configuration multiple times, report the mean and a measure of variability (standard deviation or standard error), and treat the comparisons as hypothesis tests, not as visual impressions (see Empirical Methodology).

  • You will extend the benchmark to measure the cost of a thread switch, and compare it to the cost of a process switch (see Extension: Thread Switch vs. Process Switch).

  • You shall complete a report that documents at minimum the following items. The report should be no more than 2 pages.

    • Explain what a context switch is and how it is important to processes and threads in operating systems.
    • Describe the following:
      1. the research question you are answering,
      2. the experiment and data collected to answer the research question,
      3. the answer to the research question, and
      4. present evidence visually using a graph and/or a table.
    • Compare process switching cost with thread switching cost, and explain what the comparison shows about the OS mechanism. Support the comparison with a hypothesis test, not just with the plotted means.
    • Provide necessary citations in the document.
    • Use either the ACM conference or IEEE conference proceedings template in writing the document. The ACM templates are at (ACM Conference Proceedings Template, n.d.), and the IEEE templates are at (IEEE Conference Publishing Templates, n.d.).

  • You shall prepare a deck of slides (no more than 5 slides, including the title and references) and make an oral presentation in class.

Direct Cost vs. Indirect Cost

A context switch has two kinds of cost.

  • Direct cost is what the kernel does during the switch: save the outgoing process’s registers and program counter, update its PCB, switch the page table, reload the incoming process’s registers and program counter, and update the TLB. This cost is paid by the kernel.

  • Indirect cost is what happens to the caches because of the switch. When the incoming process runs, its data is no longer in L1 or L2, because the outgoing process’s data was there. Every access after the switch misses, and each miss costs tens to hundreds of cycles. This cost is paid by the incoming process, as it executes, not by the kernel.

Li et al. (IEEE Conference Publishing Templates, n.d.)’s central finding is that on their machine, the indirect cost dominates. The direct cost is on the order of a microsecond or less, but the indirect cost, measured as the slowdown the incoming process experiences, is on the order of tens of microseconds when the working set is large enough to spill out of L1.

What does the benchmark measure? The benchmark times a loop of token passes and divides by the number of passes. That measurement includes both the direct cost and the indirect cost, because the incoming process’s cache misses happen during the loop. The benchmark does not isolate the direct cost; it measures the total cost per switch.

Why the working-set size matters. The working-set size determines which component dominates:

  • If the working set fits in L1, the indirect cost is small, and the measurement is close to the direct cost.
  • If the working set spills out of L1 but fits in L2, the measurement includes L1 misses.
  • If the working set spills out of all cache levels, the measurement is dominated by memory accesses, and the direct cost is a small fraction of the total.

The paper’s Figure 2 is a picture of this transition. That is why choosing working-set sizes relative to your own cache geometry is not optional: it determines what your measurement actually reflects.

Know Your Machine Before You Design the Experiment

The paper was published in 2007, and the machine the authors used is likely much slower and less advanced than yours. But “slower” is not a useful statement on its own. What matters for this experiment is the size of the memory hierarchy: the L1, L2, and L3 cache sizes, the cache line size, and the number of cores. These determine which working-set sizes are interesting, and which are too small or too large to show a cache effect.

Before designing your experiment, determine the cache geometry of the machine you will run on. For example, on Linux:

lscpu
getconf -a | grep CACHE
cat /sys/devices/system/cpu/cpu0/cache/index*/size
cat /sys/devices/system/cpu/cpu0/cache/index*/level
cat /sys/devices/system/cpu/cpu0/cache/index*/type

lscpu gives a summary; getconf -a | grep CACHE gives the POSIX-reported cache sizes; the /sys/devices/system/cpu/cpu0/cache/ files give the per-level geometry. Record the following in your report:

  • L1 data cache size and line size,
  • L2 cache size,
  • L3 cache size (if present),
  • number of physical cores and logical CPUs.

Then choose your working-set sizes relative to those sizes. A working set of 4 KB is interesting on any machine. A working set of 256 KB is interesting on a machine whose L2 is 256 KB or smaller, but may be entirely within L3 on a machine with a large L3, in which case it will not produce the effect the paper reports. The paper’s working-set sizes were chosen for the paper’s machine; you must choose yours for yours.

Empirical Methodology

A single run of the benchmark is not evidence. The cost of a context switch varies from run to run because of cache state, interrupt activity, frequency scaling, and scheduling noise. The following are required:

  1. Repeat each configuration. Run each (mode, working-set size, stride) configuration at least 30 times. Report the mean and the standard deviation (or the standard error of the mean) for each configuration. Plot the mean with error bars.

  2. Report the distribution, not just the mean. Two configurations can have the same mean and very different spreads. A box plot or a violin plot, in addition to the mean-with-error-bars plot, is acceptable and often more informative.

  3. Use a hypothesis test for the thread-vs-process comparison. You are comparing two paired conditions: for each configuration, the process-mode cost and the thread-mode cost are measured on the same machine under the same conditions. Use the Wilcoxon signed-rank test to test whether the two modes differ significantly. Report the test statistic, the p-value, and the effect size, and state the null and alternative hypotheses. Do not report “thread is faster” on the basis of the plotted means alone.

  4. State your assumptions and their limits. The Wilcoxon signed-rank test assumes paired observations and does not assume normality, but it does assume that the differences are symmetrically distributed. If your data violates that assumption, say so and interpret the result accordingly. If you have reason to prefer a different test, justify the choice.

  5. Report negative results. If the thread-vs-process difference is not statistically significant at some working-set sizes, report that. A small, non-significant difference is a finding, not a failure — it tells you that at those working-set sizes, the mechanism difference is not the dominant cost.

Special Considerations: VirtualBox VMs

  1. This project requires accurate measurement of time. There have been reports that time measurements on virtual machines are sometimes erratic, especially when measuring short lengths of time. Consider this when running experiments on VirtualBox VMs and when interpreting the results.
  2. The cache geometry reported by the VM may not match the cache geometry of the host. If you run in a VM, determine the cache geometry of the host, and note in your report that the VM’s reported geometry may differ. This is one reason measurements in a VM can be noisy.

Extension: Thread Switch vs. Process Switch

The paper measures process switches. A natural extension is to measure thread switches and compare.

Hypothesis

A thread switch should be cheaper than a process switch, because the kernel does not switch page tables or flush the TLB when switching between threads of the same process. The mechanism difference is real: a process switch saves and restores more state than a thread switch.

State this as a testable hypothesis: for a given working-set size and stride, the mean per-switch cost in thread mode is lower than in process mode. The null hypothesis is that the two modes have the same distribution of per-switch costs.

Experiment

Modify the benchmark so that it can run in two modes:

  • Process mode: two processes pass a token through a pipe, as in the paper.
  • Thread mode: two threads in the same process pass a token through a pipe.

Use the same trigger in both modes. A pipe works for both: a blocking read() on an empty pipe suspends only the calling thread, so Thread B’s read() yields the CPU while Thread A runs and writes the token, and the kernel wakes Thread B when the write completes. Using the same trigger in both modes ensures that the only difference you measure is the switch mechanism (page table and TLB vs. registers only), not the trigger.

Run both modes with the same working-set sizes and strides. For each configuration, collect at least 30 paired measurements, and apply the Wilcoxon signed-rank test as described in Empirical Methodology. Plot the per-switch cost for both modes on the same axes, with error bars.

What to Expect, and What to Be Careful About

The mechanism difference is real: a thread switch saves and restores fewer things than a process switch. But the measured difference may be small, because on modern hardware the dominant cost of a switch is cache pollution, not the register save/restore, and both modes suffer cache pollution.

This is why knowing your cache geometry matters. If you choose working-set sizes that are all well within L1, you will see the mechanism difference clearly, because cache effects are minimal. If you choose working-set sizes that exceed L3, you will see cache effects dominate, and the two modes may look statistically indistinguishable. The interesting working-set sizes are those that straddle the cache boundaries: sizes just below and just above each level’s capacity.

If you measure a small, non-significant gap at some working-set sizes, that is not evidence that the mechanism difference does not exist. It is evidence that the mechanism difference is not the dominant cost at those sizes. Report both the significant and non-significant results, and explain the pattern in terms of the cache geometry.

Practical Notes

  1. Use a pipe in both modes. You could pass the token through a shared variable in thread mode, but that introduces two problems: the compiler may cache the value in a register (you would need volatile or a compiler barrier), and the two threads may spin rather than alternate. The pipe avoids both problems: the read()/write() pair provides the synchronization, and the kernel handles the handoff.

  2. Pin both execution contexts to the same core. If the two threads run on different cores, they may run in parallel rather than switch, and the benchmark will not measure what you intend. Use sched_setaffinity() (or taskset) to pin both execution contexts to the same core. This applies to both process mode and thread mode.

  3. Keep the pipe ends open until the benchmark is done. In thread mode, the two threads share the file descriptor table. Do not close the pipe ends in one thread while the other is still using them.

  4. Use a small token. The atomicity guarantee for pipe writes applies to writes of at most PIPE_BUF bytes (at least 512, and typically 4096 on Linux). A single-byte or single-word token is well within this limit, so a write is never partially observed by the reader.

Report

Add a section to your report comparing the two modes. Include:

  • the plot of mean per-switch cost with error bars, for both modes, on the same axes;
  • the result of the Wilcoxon signed-rank test for each working-set size, with the test statistic, p-value, and effect size;
  • a discussion of at what working-set sizes the difference is statistically significant, and whether the difference grows or shrinks as the working set crosses each cache boundary;
  • an explanation in terms of the mechanism (page tables, TLB, cache) and the measurement (which effects dominate at which scale).

Project Invitation

The project invitation will be distributed via CUNY’s Learning Management System, Brightspace.

Submission

Submit your work via the git repository hosted on GitHub.

  • In the project repository, create a directory called doc.
  • In the doc directory, add your project report (no more than 2 pages).
  • In the doc directory, add your presentation slides (no more than 5 slides).
  • Push your local repository to the remote repository on GitHub.
  • Make sure you observe the deadline posted at the class website.
  • Make an oral presentation in class (on a designated date).

Further Reading

In addition to (Li et al., 2007), here are a few readings for those who are interested in further exploration. You may share with the instructor and the class any additional articles that you believe are worth exploring.

  1. Mitigating context switching in densely packed Linux clusters (Isstaif et al., 2025) — shows what context-switch costs look like under realistic serverless colocation, where costs can reach 20 µs. (This is a 2025 arXiv working paper from the Cambridge Systems Research Group, not a peer-reviewed publication. It is included because it provides a recent, production-scale measurement of context-switch costs that complements the 2007 paper you are replicating. Treat its numbers as indicative, not authoritative.)
  2. ghOSt (Humphries et al., 2021) — what you build when the kernel scheduler’s cost becomes the bottleneck. Moves scheduling to user space and reports sub-microsecond commit latencies.
  3. Skyloft (Jia et al., 2024) — measures Linux thread-switching costs (about 1.1 µs for runnable threads) and explores user-level scheduling.

References

  1. Li, C., Ding, C., & Shen, K. (2007). Quantifying the Cost of Context Switch. Proceedings of the 2007 Workshop on Experimental Computer Science. https://doi.org/10.1145/1281700.1281702
  2. ACM Conference Proceedings Template. https://www.acm.org/publications/proceedings-template
  3. IEEE Conference Publishing Templates. https://www.ieee.org/conferences/publishing/templates.html
  4. Isstaif, A. A. T., Kalyvianaki, E., & Mortier, R. (2025). Mitigating context switching in densely packed Linux clusters with Latency-Aware Group Scheduling. ArXiv Preprint ArXiv:2508.15703. https://arxiv.org/abs/2508.15703
  5. Humphries, J. T., Natu, N., Chaugule, A., Weisse, O., Rhoden, B., Don, J., Rizzo, L., Rombakh, O., Turner, P., & Kozyrakis, C. (2021). ghOSt: Fast & Flexible User-Space Delegation of Linux Scheduling. SOSP ’21: ACM SIGOPS 28th Symposium on Operating Systems Principles, 588–604. https://doi.org/10.1145/3477132.3483542
  6. Jia, Y., Tian, K., You, Y., Chen, Y., & Chen, K. (2024). Skyloft: A General High-Efficient Scheduling Framework in User Space. Proceedings of the ACM Symposium on Operating Systems Principles (SOSP), 265–279. https://doi.org/10.1145/3694715