Performance, under the hood · Start here · 1 of 10

Threads take turns

Your app runs dozens of threads, and so does every other app, on a phone that can run only a handful at once. Something has to decide who runs. Here's the kernel's turn-taking, the building block under every profiler chart in this course.

The problem

Your app has the main thread, the RenderThread, a few background threads and the runtime's own helpers: easily thirty threads. Every other app and system service has its own. The phone's processor can run about eight at a time. Thirty threads can't all run at once. So when your main thread "takes 120 ms" to do something, how much of that was it actually running?

See it

Two CPU cores each run one thread; three more ready threads wait in a run queue; the scheduler switches a running thread out so the next one gets a turn; a thread waiting for the disk leaves the queue and sleeps; when the data arrives the kernel wakes it and it queues again core 0core 1 A B C run queue B A D E preemption: A's turn is up E sleepswaiting for disk E wokenwoken: back in the queuewaits for a core
  1. Two CPU cores (phones have more). Each runs one thread at a time. Threads that are ready but have no core wait in the run queue.

    Step 1 of 4
  2. A's turn is up: the scheduler takes core 0 away and gives it to B, the next in line. A goes back in the queue. That's preemption.

    Step 2 of 4
  3. E needs a file from the disk. It isn't ready, so the kernel takes it off the queue: asleep, using no core. Predict: when the file arrives, does E run at once?

    Step 3 of 4
  4. No. The kernel wakes E: back in the run queue. It runs only when a core frees up.

    Step 4 of 4

The building block

A CPU core is one part of the processor that executes instructions, one after another. A core runs one thread at a time. A phone's processor has several cores, often eight, so at any moment at most eight threads are really running.

The scheduler is the part of the kernel that decides which thread runs on which core, and for how long. Threads that are ready to run, but have no core yet, wait in a run queue. When a core frees up, the scheduler gives it the next thread from the queue.

A thread doesn't keep a core until it's done. After a short stretch, or when a more urgent thread becomes ready, the scheduler can take the core away and put the thread back in the run queue. That's preemption: the thread didn't stop, it was paused so someone else could have a turn.

Some threads aren't ready at all. A thread that needs a lock another thread holds, or a file from the disk, or a message, has nothing to do until that arrives. The kernel takes it off the run queue: it's asleep and uses no core. When the thing arrives, the kernel wakes the thread: puts it back on a run queue. Woken isn't running yet: if every core is busy, it waits its turn.

So the time between a function's start and end, as a clock on the wall sees it, is made of three things: running on a core, waiting in the queue for one, and sleeping until something arrives. Only the first is your code being slow. The next puzzles show how a profiler tells them apart.

The analogy

Eight checkout counters in a supermarket and a crowd of shoppers. Shoppers with full baskets queue for a counter (the run queue). A cashier serves one at a time, and a manager (the scheduler) can wave someone aside to serve an urgent customer first (preemption). A shopper who forgot the milk leaves the queue to fetch it (asleep) and has to queue again when back (woken).

Check yourself

A phone has eight cores and twenty threads are ready to run. What happens to the other twelve?

Not quite. Leaving the queue is for threads waiting for something; ready threads queue.

Not quite. A core runs one thread at a time; the rest wait.

Right. Ready but no core means waiting in the queue.

A thread is waiting for a file from the disk. Where is it?

Not quite. Asleep it uses no core; the kernel wakes it when the data is there.

Not quite. It isn't ready yet; a sleeping thread takes no place in the queue.

Right. Waiting for something means asleep, not queued.

What's the difference between being woken and running?

Right. Woken is ready; running is on a core.

Not quite. That's the two swapped.

Sources

  • Perfetto: CPU Scheduling events ("Which threads were scheduled on which CPU core at any point in time, with nanosecond accuracy. The reason why a running thread got descheduled (e.g. pre-emption, blocked on a mutex, blocking syscall or any other wait queue)."; "Thread A suspends on the wait() it will enter the state S(sleeping) and get removed from the CPU run queue. When Thread B notifies the variable, the kernel will transition Thread A into the R(unnable) state. Thread A at that point is eligible to be put back on a run queue. However this might not happen for some time because, for instance: All CPUs might be busy running some other thread")

What you now know

A CPU core runs one thread at a time. The kernel's scheduler decides which ready thread runs on which core, and for how long; ready threads wait in a run queue, and a running thread can be switched out so others get a turn. A thread waiting for something (a lock, the disk, a message) leaves the queue entirely until the kernel wakes it. So a thread's elapsed time is its running time plus its waiting.