CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 6 of 7 · 3 min read

Measurements

Seeing the difference: parallelism and switching cost

In plain words: Two kernel threads can run at the same time on two processors. A test starts two threads that each count in a loop for a fixed amount of work and measures the elapsed time:

$ time ./m1                      (two processors available)
elapsed 0.86 s    user 1.705 s

$ time taskset -c 0 ./m1         (restricted to one processor)
elapsed 1.71 s    user 1.699 s

The work is the same, about 1.7 seconds of processor time in total (the user column). With two processors it finishes in 0.86 seconds, because the two threads ran at the same moment (1.705 divided by 2 is 0.85). Tied to one processor, the elapsed time is 1.71 seconds, because the threads took turns. This is parallelism (page 1), and a many-to-one library could never show it.

A second measurement compares the cost of switching between two kernel threads of one process with switching between two separate processes. Both use the same pipe ping-pong as Level 1, page 5, pinned to one processor. Five runs of each on the test machine:

Per switch (ns), five runs Average
Two processes 1316, 1265, 1256, 1250, 1281 about 1,274
Two threads 1230, 1211, 1278, 1201, 1186 about 1,221

The thread switch was about 4 per cent cheaper. That is a smaller gap than the textbook claim suggests, and the reason is that this test is dominated by the four system calls per round trip, and the tiny working set leaves almost no cache to lose. The saving from not changing the address space grows with programs that use a lot of memory, since the processor must then refill its caches and translation tables (Level 1, page 5). In short, a thread switch is cheaper, but on this simple test only slightly.

Interview angle

Answer in your head first, then open it.

What is the difference between user-level and kernel-level threads?

User-level threads are managed by a library and unknown to the kernel. Kernel-level threads are scheduled by the kernel.

Why does one blocking call stop all threads in a many-to-one model?

The kernel sees one line of execution and blocks the whole process.

Which model does Linux use?

One-to-one: each pthread is a kernel task created with clone.

How is a thread different from a process on Linux?

Both are tasks. A thread shares its address space and other resources with the thread that created it.

Check yourself: 1. What did the elapsed time do when the two threads were restricted to one processor, and why? 2. By how much was the thread switch cheaper in the test? 3. Why was the saving small?

Words you will meet

Word Meaning
User-level thread A thread run by a library, unknown to the kernel
Kernel-level thread A thread the kernel knows and schedules
Mapping model The rule linking user threads to kernel threads
Cooperative scheduling Each task keeps the processor until it yields
clone The Linux call that creates a task with chosen sharing
NPTL The Linux implementation of POSIX threads

Quick notes

  • A user-level thread is a thread whose creation, switching and scheduling are done by a thread library in user mode, so the kernel sees only the single process that contains it.
  • A threading model is the rule that maps a program's user-level threads to kernel-level threads.
  • clone is the Linux system call that creates a new task and lets the caller choose, by flags, which resources it shares with the new task, such as the address space, the open files and the signal handlers.