Operating Systems Module 1 – Foundations: what an operating system does
The hardware an operating system manages
The cores, caches, memory and devices an operating system manages, with memory latency measured on a real machine and why it needs a timer and an MMU.
What you will learn
- Describe the CPU cores, memory hierarchy, buses and devices at the level an operating system needs
- Measure memory latency at growing working-set sizes and read the steps in the curve
- Calculate the average memory access time from each level's hit rate and access time
- Explain why a protected multitasking system needs a timer interrupt, a privileged mode and an MMU
- Explain why two cores writing the same cache line slow each other down
Before you start
What you’ll learn · Before you start
What you will learn
- Describe the CPU cores, memory hierarchy, buses and devices at the level an operating system needs
- Measure memory latency at growing working-set sizes and read the steps in the curve
- Calculate the average memory access time from each level's hit rate and access time
- Explain why a protected multitasking system needs a timer interrupt, a privileged mode and an MMU
- Explain why two cores writing the same cache line slow each other down
Before you start
On this page
On the machine that ran this lesson’s programs, one load from memory took under 2 nanoseconds while the data was small and about a hundred once it outgrew the caches: the same instruction, dozens of times slower. An operating system is built around facts like this one, because it decides where programs run and where their data lives.
This lesson walks through the hardware an operating system manages, at the depth the kernel needs it: the cores and their caches, memory and the steps in its speed, the devices and how they report back. It shows the three pieces of hardware without which no kernel could protect anything, and measures what it costs when two cores write the same cache line.
The parts of a computer an operating system manages
A computer gives the kernel a few kinds of things to share: cores to run instructions, memory to hold data, and
devices that store data or move it in and out. The program below asks the machine about itself, first through two
POSIX sysconf values that every Unix-like system answers, then through macOS’s sysctl interface for its caches:
#include <stdio.h>
#include <unistd.h>
#if defined(__APPLE__)
#include <sys/sysctl.h>
#endif
#if defined(__APPLE__)
static long long sysctl_number(const char *name) {
long long value = 0; // 4- or 8-byte values both fit (little-endian)
size_t size = sizeof value;
return sysctlbyname(name, &value, &size, NULL, 0) == 0 ? value : -1;
}
#endif
int main(void) {
printf("page size: %ld bytes\n", sysconf(_SC_PAGESIZE));
printf("processors online: %ld\n", sysconf(_SC_NPROCESSORS_ONLN));
#if defined(__APPLE__)
printf("cache line: %lld bytes\n", sysctl_number("hw.cachelinesize"));
long long levels = sysctl_number("hw.nperflevels");
for (long long level = 0; level < levels; level++) {
char key[64], name[32] = "?";
size_t size = sizeof name;
snprintf(key, sizeof key, "hw.perflevel%lld.name", level);
sysctlbyname(key, name, &size, NULL, 0);
snprintf(key, sizeof key, "hw.perflevel%lld.physicalcpu", level);
long long cores = sysctl_number(key);
snprintf(key, sizeof key, "hw.perflevel%lld.l1dcachesize", level);
long long l1 = sysctl_number(key) / 1024;
snprintf(key, sizeof key, "hw.perflevel%lld.l2cachesize", level);
long long l2 = sysctl_number(key) / (1024 * 1024);
snprintf(key, sizeof key, "hw.perflevel%lld.cpusperl2", level);
long long sharing = sysctl_number(key);
printf(
"%s cores: %lld, L1 data %lld KiB each, L2 %lld MiB per %lld cores\n",
name, cores, l1, l2, sharing);
}
#elif defined(_SC_LEVEL1_DCACHE_LINESIZE)
printf("cache line: %ld bytes\n",
sysconf(_SC_LEVEL1_DCACHE_LINESIZE));
#endif
return 0;
}Output
page size: 16384 bytes processors online: 18 cache line: 128 bytes Super cores: 6, L1 data 128 KiB each, L2 16 MiB per 6 cores Performance cores: 12, L1 data 64 KiB each, L2 8 MiB per 6 cores
Recorded with Apple clang version 21.0.0 (clang-2100.3.34.2) on macOS 26 arm64. To run it yourself: clang -std=c23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined machine_facts.c -o machine_facts && ./machine_facts
The machine has 18 cores of two kinds, which macOS names Super and Performance, each with first-level caches of its own and second-level caches shared by groups of six. Its memory is shared by all of them and handed out in A fixed-size block of memory, 16 KiB on the recorded machine, that the kernel maps into an address space as one unit. of 16 KiB. Here is how those parts connect:
The parts of the recorded machine an operating system manages
Text description of the diagram
The figure has six boxes in two columns, with the sizes that machine_facts.c printed on the recorded machine.
- Top left: 6 Super cores, each with a 128 KiB first-level data cache, sharing one 16 MiB second-level cache.
- Top right: 12 Performance cores, each with a 64 KiB first-level data cache; every group of 6 shares an 8 MiB second-level cache.
- Middle left: the main memory (DRAM), shared by all 18 cores and handed out in pages of 16 KiB. Arrows from both groups of cores to the memory stand for their loads and stores.
- Middle right: the timer and interrupt controller, with an arrow to the cores labelled interrupts: this is how a timer or a device stops a core and makes it run the kernel.
- Bottom left and right: the SSD controller and the network card. Each has an arrow to the memory labelled DMA: they copy data to and from memory themselves, without the cores.
Cores load and store through their caches into the shared memory. Each core has a memory management unit (MMU): The part of each core that translates every virtual address a program uses into a physical address, using page tables the kernel wrote, and refuses accesses those tables do not allow. that translates every address a program uses through page tables the kernel wrote. The SSD and the network card sit on an I/O bus and copy data to and from memory themselves. The timer and the interrupt controller can stop any core and make it run the kernel. The rest of this lesson takes these parts one at a time.
Checkpoint
Check: The parts of a computer an OS manages
Memory gets slower in steps as the data grows
A program’s working set: The data a program touches over a stretch of time. When it fits in a cache, loads are answered there; when it outgrows the caches, they wait for memory. is the data it touches over a stretch of time. To see how its size changes the cost of a load, the next program, in Rust, builds one random cycle through an array, so that each load gives the index of the next. No load can start before the one before it finishes, so the time per load is the time memory takes to answer. It repeats the measurement at sizes from 16 KiB to 64 MiB and keeps the best of three runs at each, because other programs on the machine can only ever slow a run down:
use std::hint::black_box;
use std::time::Instant;
const LOADS: usize = 1 << 20; // dependent loads timed in each run
const RUNS: usize = 3; // the best of 3 runs at each size: other programs can only slow a run
struct SplitMix64(u64);
impl SplitMix64 {
fn next(&mut self) -> u64 {
self.0 = self.0.wrapping_add(0x9e37_79b9_7f4a_7c15);
let mut z = self.0;
z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
z ^ (z >> 31)
}
}
/// Each load needs the result of the one before it, so the CPU cannot overlap them.
fn chase(next: &[u32], start: u32, loads: usize) -> u32 {
let mut i = start;
for _ in 0..loads {
i = next[i as usize];
}
i
}
fn main() {
let mut rng = SplitMix64(42); // a fixed seed, so every run uses the same order
println!("working set ns per load");
let mut kib = 16;
while kib <= 64 * 1024 {
let n = kib * 1024 / 4;
let mut next: Vec<u32> = (0..n as u32).collect();
for i in (1..n).rev() {
// Sattolo's shuffle: one cycle through every slot
let j = (rng.next() % i as u64) as usize;
next.swap(i, j);
}
let mut end = chase(&next, 0, LOADS); // warm up the caches and the TLB
let mut best = f64::MAX;
for _ in 0..RUNS {
let start = Instant::now();
end = black_box(chase(&next, end, LOADS));
best = best.min(start.elapsed().as_nanos() as f64 / LOADS as f64);
}
let size = if kib < 1024 {
format!("{kib} KiB")
} else {
format!("{} MiB", kib / 1024)
};
println!("{size:>11} {best:8.1}");
kib *= 4;
}
}Output
working set ns per load
16 KiB 1.5
64 KiB 1.3
256 KiB 4.3
1 MiB 8.8
4 MiB 16.5
16 MiB 92.5
64 MiB 122.8
This output changes from run to run: the times depend on the machine and on what else it is running; the sizes do not
Recorded with rustc 1.99.0 (b940084d7) on macOS 26 arm64. To run it yourself: rustc --edition 2024 -O pointer_chase.rs && ./pointer_chase
The times form plateaus, one for each level of the memory hierarchy: The levels a load can be answered from, small and fast near the core and large and slow further away: registers, first- and second-level caches, then main memory.. Up to 64 KiB the data fits in a core’s first-level cache and a load costs under 2 ns. At 256 KiB and 1 MiB it comes from the second-level cache, several times slower. At 16 and 64 MiB nearly every load goes to memory and costs around a hundred nanoseconds, with 4 MiB in between. The steps sit where machine_facts.c said the caches end, which is why the size of a working set often matters more than the number of instructions.
The average cost of an access follows from each level’s time and how often it hits. With a first-level cache that answers in t₁ and hits a share h₁ of the loads, in front of memory that answers in t₂:
In words: every access pays the cache’s time, and the share that misses also pays the memory’s. With t₁ = 1.7 ns, h₁ = 95 % and t₂ = 130 ns, AMAT = 1.7 + 0.05 × 130 = 8.2 ns: a miss rate of only 5 % makes the average almost five times the cost of a hit. More levels nest the same way, and the exercise at the end computes it for any number.
Checkpoint
Check: The memory hierarchy and average access time
Three pieces of hardware every protected system needs
The first lesson’s kernel took the CPU back after every slice. On real hardware it can only do that because of a timer interrupt: An interrupt raised by a hardware timer the kernel set. It stops the running program and makes the core enter the kernel, which can then give the CPU to another program.: the kernel sets a timer before it lets a program run, and when the time is up the timer interrupts the core, which jumps into the kernel whatever the program was doing. RISC-V’s privileged specification shows the mechanism in its plainest form: a machine timer interrupt becomes pending when the time register reaches the value of a compare register the kernel wrote. Step through it:
The drawing shows the whole scene; its 7 steps are listed below.
Every step as text
- Set the timer. Before it lets L run, the kernel programs the timer to interrupt after 3 ticks. Setting the timer is a privileged instruction, so only code in kernel mode can do it.
- Run L. The kernel switches to user mode and jumps into L, a loop that never ends and never calls the kernel.
- L loops. Ticks 0, 1 and 2 pass with L in its loop. L cannot switch the timer off or change it, because the CPU refuses those instructions in user mode.
- The interrupt. After tick 2 the timer raises an interrupt. The CPU stops L between two instructions, switches to kernel mode and jumps to the handler the kernel installed when it started.
- Save L, pick A. The handler saves L's registers in L's record and puts L at the back of the ready queue. It takes A from the front and sets the timer again.
- Resume A. The kernel returns to user mode, inside A. A runs ticks 3 to 5, and then the timer takes the CPU back from A in exactly the same way, for B.
- Everyone gets turns. Without the timer, L kept the CPU for all 16 ticks and A and B never ran. With it, B finished at tick 7 and A at tick 12, though L never cooperated. The timer, not the programs, decides when the kernel runs.
The model below runs three programs twice. L is a loop that never ends and never calls the kernel; A needs 5 steps and B needs 2. The first run has no timer, the second a timer every 3 ticks, and each run prints which program had the CPU at every tick:
Python 3.14 · main.py
from collections import deque
from dataclasses import dataclass
@dataclass
class Program:
name: str
steps: int | None # None: a loop that never ends and never gives the CPU back
done: int = 0
def run(timer: int | None, ticks: int) -> None:
programs = [Program("L", None), Program("A", 5), Program("B", 2)]
ready = deque(programs)
current: Program | None = None
ran = 0 # ticks the current program has run since it got the CPU
timeline = ""
for _ in range(ticks):
if current is not None and timer is not None and ran == timer and ready:
ready.append(current) # the timer interrupt hands the CPU to the kernel
current = None
if current is None and ready:
current, ran = ready.popleft(), 0
if current is None:
timeline += "."
continue
timeline += current.name
current.done += 1
ran += 1
if current.steps is not None and current.done == current.steps:
current = None # a program that finishes gives the CPU back
a, b = programs[1], programs[2]
print("no timer:" if timer is None else f"timer every {timer} ticks:")
print(f" CPU by tick: {timeline}")
print(f" A did {a.done} of {a.steps} steps, B did {b.done} of {b.steps}")
run(None, 16)
run(3, 16)In Python: None marks the endless loop's step count, and int | None in the type hint says so; deque is the ready queue.
Recorded with CPython 3.14.8 on macOS 26 arm64. It runs in your browser with Pyodide 314.0.7 (CPython 3.14.2). To run it yourself: python3 main.py
JavaScript Node 24 · main.mjs
// steps: null means a loop that never ends and never gives the CPU back
const makePrograms = () => [
{ name: "L", steps: null, done: 0 },
{ name: "A", steps: 5, done: 0 },
{ name: "B", steps: 2, done: 0 },
];
function run(timer, ticks) {
const programs = makePrograms();
const ready = [...programs];
let current = null;
let ran = 0; // ticks the current program has run since it got the CPU
let timeline = "";
for (let tick = 0; tick < ticks; tick++) {
if (current !== null && timer !== null && ran === timer && ready.length > 0) {
ready.push(current); // the timer interrupt hands the CPU to the kernel
current = null;
}
if (current === null && ready.length > 0) {
current = ready.shift();
ran = 0;
}
if (current === null) {
timeline += ".";
continue;
}
timeline += current.name;
current.done += 1;
ran += 1;
if (current.steps !== null && current.done === current.steps) {
current = null; // a program that finishes gives the CPU back
}
}
const [, a, b] = programs;
console.log(timer === null ? "no timer:" : `timer every ${timer} ticks:`);
console.log(` CPU by tick: ${timeline}`);
console.log(` A did ${a.done} of ${a.steps} steps, B did ${b.done} of ${b.steps}`);
}
run(null, 16);
run(3, 16);In JavaScript: null marks the endless loop, and the array destructuring [, a, b] skips the loop to name the two other programs.
Recorded with Node.js 24.21.0 LTS (V8 13.6) on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0). To run it yourself: node main.mjs
Java 25 LTS · Main.java
import java.util.ArrayDeque;
import java.util.List;
public class Main {
static final class Program {
final String name;
final Integer steps; // null: a loop that never ends and never gives the CPU back
int done;
Program(String name, Integer steps) {
this.name = name;
this.steps = steps;
}
}
static void run(Integer timer, int ticks) {
List<Program> programs =
List.of(new Program("L", null), new Program("A", 5), new Program("B", 2));
ArrayDeque<Program> ready = new ArrayDeque<>(programs);
Program current = null;
int ran = 0; // ticks the current program has run since it got the CPU
StringBuilder timeline = new StringBuilder();
for (int tick = 0; tick < ticks; tick++) {
if (current != null && timer != null && ran == timer && !ready.isEmpty()) {
ready.addLast(current); // the timer interrupt hands the CPU to the kernel
current = null;
}
if (current == null && !ready.isEmpty()) {
current = ready.removeFirst();
ran = 0;
}
if (current == null) {
timeline.append('.');
continue;
}
timeline.append(current.name);
current.done += 1;
ran += 1;
if (current.steps != null && current.done == current.steps) {
current = null; // a program that finishes gives the CPU back
}
}
Program a = programs.get(1);
Program b = programs.get(2);
System.out.println(timer == null ? "no timer:" : "timer every " + timer + " ticks:");
System.out.println(" CPU by tick: " + timeline);
System.out.println(
" A did " + a.done + " of " + a.steps + " steps, B did " + b.done + " of " + b.steps);
}
public static void main(String[] args) {
run(null, 16);
run(3, 16);
}
}In Java: The step count is an Integer, so it can be null for the endless loop; the null check comes before the comparison unboxes it.
Recorded with OpenJDK 25.0.4.1 LTS (Eclipse Temurin) on macOS 26 arm64. It runs in your browser with a TeaVM 0.16.0 build in QuickJS (quickjs-emscripten 0.32.0). To run it yourself: java Main.java
C++23 · main.cpp
#include <deque>
#include <optional>
#include <print>
#include <string>
#include <vector>
struct Program {
char name;
// no value: a loop that never ends and never gives the CPU back
std::optional<int> steps;
int done = 0;
};
void run(std::optional<int> timer, int ticks) {
std::vector<Program> programs = {{'L', std::nullopt}, {'A', 5}, {'B', 2}};
std::deque<Program *> ready;
for (auto &p : programs) {
ready.push_back(&p);
}
Program *current = nullptr;
int ran = 0; // ticks the current program has run since it got the CPU
std::string timeline;
for (int tick = 0; tick < ticks; tick++) {
if (current != nullptr && timer && ran == *timer && !ready.empty()) {
ready.push_back(
current); // the timer interrupt hands the CPU to the kernel
current = nullptr;
}
if (current == nullptr && !ready.empty()) {
current = ready.front();
ready.pop_front();
ran = 0;
}
if (current == nullptr) {
timeline += '.';
continue;
}
timeline += current->name;
current->done += 1;
ran += 1;
if (current->steps && current->done == *current->steps) {
current = nullptr; // a program that finishes gives the CPU back
}
}
const auto &a = programs[1];
const auto &b = programs[2];
if (timer) {
std::println("timer every {} ticks:", *timer);
} else {
std::println("no timer:");
}
std::println(" CPU by tick: {}", timeline);
std::println(" A did {} of {} steps, B did {} of {}", a.done, *a.steps,
b.done, *b.steps);
}
int main() {
run(std::nullopt, 16);
run(3, 16);
}In C++: std::optional<int> holds the step count, empty for the endless loop, and the timer is optional the same way.
Recorded with Apple clang 21.0.0 (C++23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang++ -std=c++23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.cpp -o main && ./main
C# 14 · .NET 10 · app.cs
using System.Globalization;
using System.Text;
CultureInfo.CurrentCulture = CultureInfo.InvariantCulture;
Run(null, 16);
Run(3, 16);
static void Run(int? timer, int ticks)
{
List<Job> programs = [new("L", null), new("A", 5), new("B", 2)];
var ready = new Queue<Job>(programs);
Job? current = null;
int ran = 0; // ticks the current program has run since it got the CPU
var timeline = new StringBuilder();
for (int tick = 0; tick < ticks; tick++)
{
if (current is not null && timer is not null && ran == timer && ready.Count > 0)
{
ready.Enqueue(current); // the timer interrupt hands the CPU to the kernel
current = null;
}
if (current is null && ready.Count > 0)
{
current = ready.Dequeue();
ran = 0;
}
if (current is null)
{
timeline.Append('.');
continue;
}
timeline.Append(current.Name);
current.Done += 1;
ran += 1;
if (current.Steps is not null && current.Done == current.Steps)
{
current = null; // a program that finishes gives the CPU back
}
}
var (a, b) = (programs[1], programs[2]);
Console.WriteLine(timer is null ? "no timer:" : $"timer every {timer} ticks:");
Console.WriteLine($" CPU by tick: {timeline}");
Console.WriteLine($" A did {a.Done} of {a.Steps} steps, B did {b.Done} of {b.Steps}");
}
// Steps is null for a loop that never ends and never gives the CPU back.
sealed class Job(string name, int? steps)
{
public string Name { get; } = name;
public int? Steps { get; } = steps;
public int Done { get; set; }
}In C#: A program's record is a class named Job, because top-level statements already create a class named Program. int? is null for the endless loop and for no timer.
Recorded with C# 14 on .NET 10.0.12 (SDK 10.0.401) on macOS 26 arm64. It runs in your browser with the .NET runtime for WebAssembly 10.0.12. To run it yourself: dotnet run app.cs
C23 · main.c
#include <stddef.h>
#include <stdio.h>
// steps of a loop that never ends and never gives the CPU back
enum { FOREVER = -1 };
typedef struct {
char name;
int steps;
int done;
} Program;
static void run(int timer, int ticks) { // timer 0: no timer interrupt
Program programs[] = {{'L', FOREVER, 0}, {'A', 5, 0}, {'B', 2, 0}};
Program *ready[64];
size_t head = 0;
size_t tail = 0;
for (size_t i = 0; i < 3; i++) {
ready[tail++] = &programs[i];
}
Program *current = NULL;
int ran = 0; // ticks the current program has run since it got the CPU
char timeline[64] = {0};
for (int tick = 0; tick < ticks; tick++) {
if (current != NULL && timer > 0 && ran == timer && head < tail) {
ready[tail++] =
current; // the timer interrupt hands the CPU to the kernel
current = NULL;
}
if (current == NULL && head < tail) {
current = ready[head++];
ran = 0;
}
if (current == NULL) {
timeline[tick] = '.';
continue;
}
timeline[tick] = current->name;
current->done += 1;
ran += 1;
if (current->steps != FOREVER && current->done == current->steps) {
current = NULL; // a program that finishes gives the CPU back
}
}
if (timer > 0) {
printf("timer every %d ticks:\n", timer);
} else {
printf("no timer:\n");
}
printf(" CPU by tick: %s\n", timeline);
printf(" A did %d of %d steps, B did %d of %d\n", programs[1].done,
programs[1].steps, programs[2].done, programs[2].steps);
}
int main(void) {
run(0, 16);
run(3, 16);
return 0;
}In C: C has no optional values, so FOREVER (−1) marks the endless loop and a timer of 0 means there is none.
Recorded with Apple clang 21.0.0 (C23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang -std=c23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.c -o main && ./main
PHP 8.5 · main.php
<?php
declare(strict_types=1);
final class Program
{
public int $done = 0;
/** @param ?int $steps null: a loop that never ends and never gives the CPU back */
public function __construct(
public readonly string $name,
public readonly ?int $steps,
) {}
}
function run(?int $timer, int $ticks): void
{
$programs = [new Program('L', null), new Program('A', 5), new Program('B', 2)];
$ready = new SplQueue();
foreach ($programs as $p) {
$ready->enqueue($p);
}
$current = null;
$ran = 0; // ticks the current program has run since it got the CPU
$timeline = '';
for ($tick = 0; $tick < $ticks; $tick++) {
if ($current !== null && $timer !== null && $ran === $timer && !$ready->isEmpty()) {
$ready->enqueue($current); // the timer interrupt hands the CPU to the kernel
$current = null;
}
if ($current === null && !$ready->isEmpty()) {
$current = $ready->dequeue();
$ran = 0;
}
if ($current === null) {
$timeline .= '.';
continue;
}
$timeline .= $current->name;
$current->done += 1;
$ran += 1;
if ($current->steps !== null && $current->done === $current->steps) {
$current = null; // a program that finishes gives the CPU back
}
}
[, $a, $b] = $programs;
echo $timer === null ? "no timer:\n" : "timer every {$timer} ticks:\n";
echo " CPU by tick: {$timeline}\n";
echo " A did {$a->done} of {$a->steps} steps, B did {$b->done} of {$b->steps}\n";
}
run(null, 16);
run(3, 16);In PHP: ?int lets the endless loop's step count be null; SplQueue is the ready queue.
Recorded with PHP 8.5.11 (CLI) on macOS 26 arm64. It runs in your browser with php-wasm 0.2.0 (PHP 8.5.2). To run it yourself: php main.php
Rust 1.99 · main.rs
use std::collections::VecDeque;
struct Program {
name: char,
steps: Option<u32>, // None: a loop that never ends and never gives the CPU back
done: u32,
}
fn run(timer: Option<u32>, ticks: u32) {
let mut programs = vec![
Program {
name: 'L',
steps: None,
done: 0,
},
Program {
name: 'A',
steps: Some(5),
done: 0,
},
Program {
name: 'B',
steps: Some(2),
done: 0,
},
];
let mut ready: VecDeque<usize> = (0..programs.len()).collect();
let mut current: Option<usize> = None;
let mut ran = 0; // ticks the current program has run since it got the CPU
let mut timeline = String::new();
for _ in 0..ticks {
if let (Some(i), Some(t)) = (current, timer) {
if ran == t && !ready.is_empty() {
ready.push_back(i); // the timer interrupt hands the CPU to the kernel
current = None;
}
}
if current.is_none() {
current = ready.pop_front();
ran = 0;
}
let Some(i) = current else {
timeline.push('.');
continue;
};
let p = &mut programs[i];
timeline.push(p.name);
p.done += 1;
ran += 1;
if p.steps == Some(p.done) {
current = None; // a program that finishes gives the CPU back
}
}
let (a, b) = (&programs[1], &programs[2]);
match timer {
Some(t) => println!("timer every {t} ticks:"),
None => println!("no timer:"),
}
println!(" CPU by tick: {timeline}");
let (a_steps, b_steps) = (a.steps.unwrap_or(0), b.steps.unwrap_or(0));
println!(
" A did {} of {a_steps} steps, B did {} of {b_steps}",
a.done, b.done
);
}
fn main() {
run(None, 16);
run(Some(3), 16);
}In Rust: Option<u32> marks the endless loop, and p.steps == Some(p.done) is true only when a program with a step count has finished.
Recorded with rustc 1.99.0 (edition 2024) on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: rustc --edition 2024 -O main.rs && ./main
TypeScript 6.0 · main.ts
interface Program {
name: string;
steps: number | null; // null: a loop that never ends and never gives the CPU back
done: number;
}
const makePrograms = (): Program[] => [
{ name: "L", steps: null, done: 0 },
{ name: "A", steps: 5, done: 0 },
{ name: "B", steps: 2, done: 0 },
];
function run(timer: number | null, ticks: number): void {
const programs = makePrograms();
const ready = [...programs];
let current: Program | undefined;
let ran = 0; // ticks the current program has run since it got the CPU
let timeline = "";
for (let tick = 0; tick < ticks; tick++) {
if (current !== undefined && timer !== null && ran === timer && ready.length > 0) {
ready.push(current); // the timer interrupt hands the CPU to the kernel
current = undefined;
}
if (current === undefined) {
current = ready.shift();
ran = 0;
}
if (current === undefined) {
timeline += ".";
continue;
}
timeline += current.name;
current.done += 1;
ran += 1;
if (current.steps !== null && current.done === current.steps) {
current = undefined; // a program that finishes gives the CPU back
}
}
const [, a, b] = programs;
console.log(timer === null ? "no timer:" : `timer every ${timer} ticks:`);
console.log(` CPU by tick: ${timeline}`);
console.log(` A did ${a.done} of ${a.steps} steps, B did ${b.done} of ${b.steps}`);
}
run(null, 16);
run(3, 16);In TypeScript: shift returns undefined when the queue is empty, so the current program is Program | undefined.
Recorded with TypeScript 6.0.3 (strict), run by Node.js 24.21.0 on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0) after Sucrase 3.35.1. To run it yourself: npx -p typescript@6.0.3 tsc --noEmit --strict main.ts && node main.ts
Go 1.27 · main.go
package main
import (
"fmt"
"strings"
)
const forever = -1 // steps of a loop that never ends and never gives the CPU back
type program struct {
name string
steps int
done int
}
func run(timer, ticks int) { // timer 0: no timer interrupt
programs := []*program{{"L", forever, 0}, {"A", 5, 0}, {"B", 2, 0}}
ready := append([]*program(nil), programs...)
var current *program
ran := 0 // ticks the current program has run since it got the CPU
var timeline strings.Builder
for range ticks {
if current != nil && timer > 0 && ran == timer && len(ready) > 0 {
ready = append(ready, current) // the timer interrupt hands the CPU to the kernel
current = nil
}
if current == nil && len(ready) > 0 {
current, ready, ran = ready[0], ready[1:], 0
}
if current == nil {
timeline.WriteByte('.')
continue
}
timeline.WriteString(current.name)
current.done++
ran++
if current.steps != forever && current.done == current.steps {
current = nil // a program that finishes gives the CPU back
}
}
a, b := programs[1], programs[2]
if timer > 0 {
fmt.Printf("timer every %d ticks:\n", timer)
} else {
fmt.Println("no timer:")
}
fmt.Println(" CPU by tick: " + timeline.String())
fmt.Printf(" A did %d of %d steps, B did %d of %d\n", a.done, a.steps, b.done, b.steps)
}
func main() {
run(0, 16)
run(3, 16)
}In Go: Go has no optional values, so forever (−1) marks the endless loop and a timer of 0 means there is none.
Recorded with Go 1.27.1 on macOS 26 arm64. It runs in your browser with the Go compiler in WebAssembly 1.27.1. To run it yourself: go run main.go
Swift 6.4 · main.swift
struct Program {
let name: Character
let steps: Int? // nil: a loop that never ends and never gives the CPU back
var done = 0
}
func run(timer: Int?, ticks: Int) {
var programs = [
Program(name: "L", steps: nil), Program(name: "A", steps: 5), Program(name: "B", steps: 2),
]
var ready = Array(programs.indices)
var current: Int?
var ran = 0 // ticks the current program has run since it got the CPU
var timeline = ""
for _ in 0..<ticks {
if let running = current, let timer, ran == timer, !ready.isEmpty {
ready.append(running) // the timer interrupt hands the CPU to the kernel
current = nil
}
if current == nil, !ready.isEmpty {
current = ready.removeFirst()
ran = 0
}
guard let i = current else {
timeline += "."
continue
}
timeline.append(programs[i].name)
programs[i].done += 1
ran += 1
if programs[i].steps == programs[i].done {
current = nil // a program that finishes gives the CPU back
}
}
let (a, b) = (programs[1], programs[2])
print(timer.map { "timer every \($0) ticks:" } ?? "no timer:")
print(" CPU by tick: \(timeline)")
print(" A did \(a.done) of \(a.steps ?? 0) steps, B did \(b.done) of \(b.steps ?? 0)")
}
run(timer: nil, ticks: 16)
run(timer: 3, ticks: 16)In Swift: Int? marks the endless loop, and if let takes the running program out of the optional before it goes back in the queue.
Recorded with Apple Swift 6.4 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: swiftc -O main.swift -o main && ./main
Ruby 4.0 · main.rb
# frozen_string_literal: true
# steps nil: a loop that never ends and never gives the CPU back
Program = Struct.new(:name, :steps, :done)
# The kernel's loop, one tick at a time.
class Scheduler
attr_reader :timeline
def initialize(programs, timer)
@ready = programs.dup
@timer = timer
@current = nil
@ran = 0 # ticks the current program has run since it got the CPU
@timeline = +''
end
def tick
preempt if preempt?
dispatch if @current.nil?
return @timeline << '.' if @current.nil?
run_current
end
private
def preempt? = @current && @timer && @ran == @timer && !@ready.empty?
def preempt
@ready.push(@current) # the timer interrupt hands the CPU to the kernel
@current = nil
end
def dispatch
@current = @ready.shift
@ran = 0
end
def run_current
@timeline << @current.name
@current.done += 1
@ran += 1
# a program that finishes gives the CPU back
@current = nil if @current.done == @current.steps
end
end
def run(timer, ticks)
programs = [Program.new('L', nil, 0), Program.new('A', 5, 0), Program.new('B', 2, 0)]
scheduler = Scheduler.new(programs, timer)
ticks.times { scheduler.tick }
puts timer.nil? ? 'no timer:' : "timer every #{timer} ticks:"
puts " CPU by tick: #{scheduler.timeline}"
a, b = programs[1..]
puts " A did #{a.done} of #{a.steps} steps, B did #{b.done} of #{b.steps}"
end
run(nil, 16)
run(3, 16)In Ruby: The loop is a small Scheduler class whose tick method runs one tick, which keeps each method short, as RuboCop asks.
Recorded with CRuby 4.0.7 on macOS 26 arm64. It runs in your browser with ruby.wasm 2.10.1 (Ruby 4.0.0). To run it yourself: ruby main.rb
Kotlin 2.4 · Main.kt
class Program(
val name: Char,
val steps: Int?, // null: a loop that never ends and never gives the CPU back
) {
var done = 0
}
fun run(
timer: Int?,
ticks: Int,
) {
val programs = listOf(Program('L', null), Program('A', 5), Program('B', 2))
val ready = ArrayDeque(programs)
var current: Program? = null
var ran = 0 // ticks the current program has run since it got the CPU
val timeline = StringBuilder()
repeat(ticks) {
val running = current
if (running != null && timer != null && ran == timer && ready.isNotEmpty()) {
ready.addLast(running) // the timer interrupt hands the CPU to the kernel
current = null
}
if (current == null && ready.isNotEmpty()) {
current = ready.removeFirst()
ran = 0
}
val p = current
if (p == null) {
timeline.append('.')
} else {
timeline.append(p.name)
p.done += 1
ran += 1
if (p.done == p.steps) {
current = null // a program that finishes gives the CPU back
}
}
}
val (a, b) = programs[1] to programs[2]
println(if (timer == null) "no timer:" else "timer every $timer ticks:")
println(" CPU by tick: $timeline")
println(" A did ${a.done} of ${a.steps} steps, B did ${b.done} of ${b.steps}")
}
fun main() {
run(null, 16)
run(3, 16)
}In Kotlin: repeat cannot continue a lambda, so an if and else take the place of the other versions' continue.
Recorded with Kotlin 2.4.20 on Java 25.0.4.1 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar
Dart 3.13 · main.dart
import 'dart:collection';
class Program {
Program(this.name, this.steps);
final String name;
final int? steps; // null: a loop that never ends and never gives the CPU back
int done = 0;
}
void run(int? timer, int ticks) {
final programs = [Program('L', null), Program('A', 5), Program('B', 2)];
final ready = Queue.of(programs);
Program? current;
var ran = 0; // ticks the current program has run since it got the CPU
final timeline = StringBuffer();
for (var tick = 0; tick < ticks; tick++) {
if (current != null && timer != null && ran == timer && ready.isNotEmpty) {
ready.addLast(current); // the timer interrupt hands the CPU to the kernel
current = null;
}
if (current == null && ready.isNotEmpty) {
current = ready.removeFirst();
ran = 0;
}
if (current == null) {
timeline.write('.');
continue;
}
timeline.write(current.name);
current.done += 1;
ran += 1;
if (current.done == current.steps) {
current = null; // a program that finishes gives the CPU back
}
}
final [_, a, b] = programs;
print(timer == null ? 'no timer:' : 'timer every $timer ticks:');
print(' CPU by tick: $timeline');
print(' A did ${a.done} of ${a.steps} steps, B did ${b.done} of ${b.steps}');
}
void main() {
run(null, 16);
run(3, 16);
}In Dart: int? marks the endless loop, and the list pattern [_, a, b] names the two programs that should finish.
Recorded with Dart 3.13.5 on macOS 26 arm64. It runs in your browser with a WebAssembly build by dart2wasm 3.13.5. To run it yourself: dart run main.dart
What every language printed
no timer: CPU by tick: LLLLLLLLLLLLLLLL A did 0 of 5 steps, B did 0 of 2 timer every 3 ticks: CPU by tick: LLLAAABBLLLAALLL A did 5 of 5 steps, B did 2 of 2
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads JavaScript (about 0.6 MB), which is kept for the next runs. Runs on this device: a JavaScript build of this program (about 11 KB), made when the page was built. The first run also downloads the JavaScript runner (about 0.6 MB), which is kept for the next runs. To change the code, copy it and run it with the command below. Runs on this device: a WebAssembly build of this program (about 152 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device: a .NET build of this program (about 3 KB), made when the page was built. The first run also downloads .NET (about 3.6 MB), which is kept for the next runs. Edit runs your changes in the browser: the first edited run downloads .NET (about 8.9 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads .NET (about 8.9 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 8 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads PHP (about 4.3 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 20 KB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device, in your browser. The first run downloads the JavaScript runner (about 0.9 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 718 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the Go compiler (about 18.7 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads the Go compiler (about 18.7 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 1.7 MB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device, in your browser. The first run downloads Ruby (about 10.2 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 186 KB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device: a WebAssembly build of this program (about 11 KB), made when the page was built. To change the code, copy it and run it with the command below.Your run, in this browser
Without a timer, L held the CPU for all 16 ticks and A and B did nothing at all. With the timer, the line
LLLAAABBLLLAALLL shows L stopped after every third tick, B finished at tick 7 and A at tick 12, although L never
cooperated. CS2023, the computing curriculum of the ACM, the IEEE Computer Society and AAAI, lists exactly this use:
timer interrupts to implement time slices.
The timer alone protects nothing if a program can switch it off, so the second piece is a privileged mode. The instructions that set the timer, mask interrupts or change the page tables work only in kernel mode; in user mode the processor refuses them (the next lesson shows the refusal). The third piece is the MMU, which checks every access against the page tables, so a program cannot even address the kernel’s memory or another program’s. Each piece needs the other two.
Key idea
A protected multitasking system needs a timer that hands the CPU back to the kernel, a privileged mode that only the kernel can use, and an MMU that checks every memory access.
Checkpoint
Check: Timer, privileged mode and MMU
Devices report back with interrupts and move data by DMA
Devices work at their own pace, which is slow next to a core’s: a disk or a network answers in far more time than the memory took in the chase above. The kernel does not wait for them. It starts the work, runs other programs, and lets the device report back with an interrupt: A signal from a device or timer that stops a core between two instructions and makes it run the kernel's handler. It arrives at any time, whatever the program was doing. More in “User mode, kernel mode and traps” when it is done. Most devices also move the data themselves, by direct memory access (DMA): A device copying data to or from memory itself, without a core moving each byte. The kernel tells the device where, and the device reports the end with an interrupt.: the Linux kernel’s DMA guide describes a device that performs DMA to read or write system memory. Step through one read:
The drawing shows the whole scene; its 6 steps are listed below.
Every step as text
- The read reaches the driver. A program asks to read a block of a file that is not in memory. Its read call ends up in the disk driver, which is part of the kernel.
- The command. The driver writes a command into the controller's registers, which block to read and which page frame to put it in. Then the kernel puts the reading program to sleep and runs another one.
- DMA. The controller reads the block and copies its bytes into frame 9 itself, by direct memory access. The CPU copies none of them; it is busy with other programs.
- The interrupt. When the copy is complete, the controller raises an interrupt. The CPU stops the program it was running and enters the kernel's handler for this device.
- Wake the reader. The handler checks the controller's status, marks frame 9 as holding block 7 and wakes the program that was waiting for it.
- The read returns. The program's read returns with the data. Without interrupts the kernel would have to ask the controller again and again whether it was done; without DMA a core would copy every byte itself.
The core’s work in that read was two short pieces of driver code: one to write the command, one to handle the interrupt. The waiting happened while the core ran other programs, and the copying was the controller’s. CS2023 puts it in the same terms: I/O interrupts let the kernel put blocked threads to sleep without polling. DMA also brings a duty: a device writes memory without going through any core’s MMU, so the kernel decides which addresses each device may use.
Checkpoint
Check: Interrupts and DMA
Cores that write the same cache line slow each other down
Caches keep copies, so the hardware must keep the copies of different cores consistent. It does this per
cache line: The block of memory that caches load, keep coherent and invalidate as one unit: 128 bytes on Apple silicon., 128 bytes on the recorded machine: before a core writes a line, every other
core’s copy of it is invalidated. When two cores write the same line over and over, the line travels back and forth
between them, even when each core writes a different variable in it. The Linux kernel’s documentation calls this
false sharing: Slowdown when cores write different variables that sit in the same cache line, so that the line moves between their caches on every write.. The program below measures it: two threads each add 1 to their own
counter 20 million times, first with both counters in one line, then with each in a line of its own. It is written
in Rust, whose #[repr(align(128))] places a struct at the start of a cache line:
use std::sync::atomic::{AtomicU64, Ordering};
use std::thread;
use std::time::Instant;
const ADDS: u64 = 20_000_000; // increments made by each of the two threads
#[repr(C, align(128))]
struct Near {
a: AtomicU64, // both counters in one 128-byte cache line
b: AtomicU64,
}
#[repr(C, align(128))]
struct OwnLine(AtomicU64); // a counter in a cache line of its own
fn add_many(counter: &AtomicU64) {
for _ in 0..ADDS {
counter.fetch_add(1, Ordering::Relaxed);
}
}
fn run_ms(x: &AtomicU64, y: &AtomicU64) -> f64 {
let start = Instant::now();
thread::scope(|s| {
s.spawn(|| add_many(x));
s.spawn(|| add_many(y));
});
start.elapsed().as_secs_f64() * 1e3
}
fn main() {
let near = Near {
a: AtomicU64::new(0),
b: AtomicU64::new(0),
};
let (a, b) = (OwnLine(AtomicU64::new(0)), OwnLine(AtomicU64::new(0)));
let same = run_ms(&near.a, &near.b);
let own = run_ms(&a.0, &b.0);
println!("same cache line: {same:6.0} ms");
println!("own cache lines: {own:6.0} ms");
println!("sharing a line was {:.1} times slower", same / own);
let total = near.a.load(Ordering::Relaxed) + near.b.load(Ordering::Relaxed);
let check = a.0.load(Ordering::Relaxed) + b.0.load(Ordering::Relaxed);
let same_count = if total == check { "yes" } else { "no" };
println!("each run counted {total} increments: {same_count}");
}Output
same cache line: 329 ms own cache lines: 50 ms sharing a line was 6.6 times slower each run counted 40000000 increments: yes
This output changes from run to run: the times depend on the machine, on which cores the threads ran and on what else was running; the counts do not
Recorded with rustc 1.99.0 (b940084d7) on macOS 26 arm64. To run it yourself: rustc --edition 2024 -O false_sharing.rs && ./false_sharing
The work was identical, 40 million increments in each run, yet sharing a line made it several times slower. Nothing was wrong with the program’s logic: the cost lives entirely in the hardware below it. The same effect shapes two later parts of this track. A lock is a word that many cores write, so a busy lock costs line transfers on every acquisition; and a thread that the scheduler moves to another core leaves its warm cache lines behind, so schedulers prefer to keep a thread where its data is.
Separate variables, shared line
volatile or a lock does not cure false sharing; the two counters are not shared, their line is. Give each
frequently written variable a line of its own, as OwnLine does with #[repr(align(128))] (in C, alignas(128)),
and use the line size your machine reports: 128 bytes here.
Checkpoint
Check: Cache coherence and false sharing
GATE CS
The GATE CS syllabus puts memory hierarchy, cache mapping, interrupts and DMA in its Computer Organization and Architecture section, not under Operating System. This lesson covers what the operating system needs from them; the average memory access time above is the kind of number the exam asks for.
Practise: work out the average memory access time
Write amat for any number of levels and run the sample tests. They include the lesson’s numbers, a level that
hits every time and a level that never does:
Exercise · Easy · Python
Work out the average memory access time
Write amat(levels) in amat.py. It returns the average time, in nanoseconds, that one memory access takes.
levelslists the memory levels in the order an access tries them, each as(hit_time_ns, hit_rate): for example the first-level cache, then the second-level cache, then main memory.- An access always pays the first level's hit time. A fraction
1 - hit_rateof accesses miss there and go on to the next level, where the same rule applies again. - The last level always has a hit rate of 1.0: main memory holds everything.
For example, a cache that answers in 1 ns and hits 95 % of accesses in front of memory that answers in 100 ns gives amat([(1, 0.95), (100, 1.0)]), which is 1 + 0.05 × 100 = 6.0.
Starter code · amat.py
def amat(levels):
"""Average time of one memory access, in ns, for [(hit_time_ns, hit_rate), ...]."""
# Replace this line with your code.
return 0.0The sample tests · test_amat.py
import math
from amat import amat
def test_one_cache_in_front_of_memory():
"""adds the misses' share of the memory time to the cache's own time"""
assert math.isclose(amat([(1, 0.95), (100, 1.0)]), 6.0)
assert math.isclose(amat([(1.7, 0.95), (130, 1.0)]), 8.2)
assert math.isclose(amat([(2, 0.5), (100, 1.0)]), 52.0)
def test_two_caches():
"""charges a second-level miss only to the accesses that already missed the first level"""
assert math.isclose(amat([(1, 0.9), (10, 0.8), (100, 1.0)]), 4.0)
assert math.isclose(amat([(1.5, 0.98), (12, 0.75), (130, 1.0)]), 2.39)
def test_memory_alone():
"""is the memory's own time when there is no cache"""
assert math.isclose(amat([(130, 1.0)]), 130.0)
def test_every_access_hits_the_first_level():
"""never reaches memory when the first level hits every time"""
assert math.isclose(amat([(2, 1.0), (100, 1.0)]), 2.0)
def test_a_level_that_never_hits():
"""passes every access on, and still charges its own time"""
assert math.isclose(amat([(1, 0.0), (10, 1.0)]), 11.0)
assert math.isclose(amat([(1, 0.0), (5, 0.0), (50, 1.0)]), 56.0)A hint
Work from the last level backwards: start with its hit time, then for each level before it compute hit_time + (1 - hit_rate) * time_of_the_levels_after_it. A loop over reversed(levels) does it in four lines.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Now test what stayed with you about caches, the timer and DMA, one question at a time:
Practice that adapts to you
Practise this lesson
12 questions about 5 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
Interview questions
Below, a warm-up with its complete answer. Two harder questions from this lesson wait in the module’s bank: a program that slows down as its data outgrows the caches, and two threads that slow each other down.
-
Fresher · Warm-up
Why does an operating system need a timer interrupt?
Without it, the kernel runs only when a program calls it, faults or exits, so a program stuck in a loop would keep the CPU for ever and every other program would stop. With a timer, the kernel sets a countdown before it lets a program run; when the time is up the timer interrupts the core, which jumps into the kernel whatever the program was doing. The kernel can then save that program's registers and run another one, which is how time slices, preemptive scheduling and timeouts work. A good answer adds why the timer has to be protected: setting it is a privileged instruction, so a program cannot switch it off. In the lesson's model, a loop without a timer kept the CPU for all 16 ticks; with a timer every 3 ticks, the two other programs finished by tick 12.
Model answers open with any pass: ₹79 for 1 week ($2.99), one payment that never renews.
-
Fresher to senior
A lookup routine does the same number of operations per query, but each query becomes about ten times slower when its table grows from 512 KiB to 64 MiB. Explain why, and how you would confirm it and fix it.
-
Mid to senior
Each of two threads updates its own counter in a struct, with no locks and no shared data, yet the program runs several times slower with two threads than with one. What is happening, how would you prove it, and how do you fix it?
Key takeaways
- The kernel manages cores with their caches, a shared memory handed out in pages (16 KiB on the recorded machine), and devices on an I/O bus that copy data by DMA and report back with interrupts.
- A load cost under 2 ns while the working set fitted the first-level cache, several times that in the second level and around a hundred nanoseconds from memory, so the size of the data that is touched matters as much as the instructions.
- The average access time is each level’s time plus the misses’ share of the levels below: 1.7 + 0.05 × 130 = 8.2 ns for one cache that hits 95 % of loads.
- A timer interrupt lets the kernel take the CPU back from a program that never stops; privileged mode stops programs from switching it off, and the MMU checks every access.
- Caches stay coherent per 128-byte line, so two threads writing different counters in one line ran several times slower than with a line each.
Terms in this lesson
- cache line
- The block of memory that caches load, keep coherent and invalidate as one unit: 128 bytes on Apple silicon.
- direct memory access (DMA)
- A device copying data to or from memory itself, without a core moving each byte. The kernel tells the device where, and the device reports the end with an interrupt.
- false sharing
- Slowdown when cores write different variables that sit in the same cache line, so that the line moves between their caches on every write.
- memory hierarchy
- The levels a load can be answered from, small and fast near the core and large and slow further away: registers, first- and second-level caches, then main memory.
- memory management unit (MMU)
- The part of each core that translates every virtual address a program uses into a physical address, using page tables the kernel wrote, and refuses accesses those tables do not allow.
- timer interrupt
- An interrupt raised by a hardware timer the kernel set. It stops the running program and makes the core enter the kernel, which can then give the CPU to another program.
- working set
- The data a program touches over a stretch of time. When it fits in a cache, loads are answered there; when it outgrows the caches, they wait for memory.
References
- sysconf(3): get configuration information at run time (Linux man-pages project (man7.org))
- sysconf: get configurable system variables (POSIX.1-2024) (The Open Group and IEEE)
- Memory management concepts overview (The Linux Kernel Organization)
- Dynamic DMA mapping guide (The Linux Kernel Organization)
- False sharing (The Linux Kernel Organization)
- The RISC-V Instruction Set Manual, Volume II: Privileged Architecture (machine timer registers) (RISC-V International)
- Computer Science Curricula 2023: Operating Systems knowledge area (Version Gamma) (ACM, IEEE Computer Society and AAAI (CS2023 Task Force))
- GATE 2027 syllabus for Computer Science and Information Technology (CS) (Indian Institute of Technology Madras (GATE 2027))
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress