How Linux really gives a process CPU

Runnable does not mean running

If a process or thread has work to do and is not waiting on I/O, a lock or a timer, it can be in the runnable state.

Roughly speaking:

runnable -> running

running means the task is currently executing instructions on a CPU.

runnable means:

it is ready to execute,
but it may still be waiting for a processor

That distinction matters.

On a single logical CPU, only one task can execute at any given moment.

If we have:

CPU 0

task A - running
task B - runnable
task C - runnable

then B and C are ready to work, but they have to wait until the scheduler gives them a CPU.

The scheduler picks the next task

Linux keeps per-CPU scheduler structures holding the tasks that are ready to execute.

A simplified picture:

CPU 0

running:
    A

runnable:
    B
    C
    D

After a while the scheduler may decide:

A -> B

The state then changes roughly like this:

A: running  -> runnable
B: runnable -> running

A context switch happens and the CPU starts executing process B's code.

Later C may be picked, then A again, and so on.

A -> B -> C -> A -> D -> ...

That is how many processes can share a single processor.

CPU time

If a process executed for 10 ms, it used about 10 ms of CPU time.

That is independent of how much time passed on the clock.

Example:

0 ms      process becomes runnable
0-20 ms   waits for CPU
20-30 ms  executes
30 ms     finishes its work

Wall-clock time:

30 ms

CPU time:

10 ms

For the remaining 20 ms the process was ready to execute but did not get a processor.

This is a very important distinction:

wall-clock time != CPU time

CPU time measures the time spent actually executing code on a processor.

What happens when there are more processes than CPUs

Assume one logical CPU and two processes:

A
B

Both are CPU-bound and always have work.

Each of them would like to execute without interruption.

That is not possible, because only one CPU is available.

So the scheduler has to divide processor time:

time ------------------------------------------------>

CPU:
| A | B | A | B | A | B | A | B |

Each process is running for part of the time and runnable for another part.

Over a longer window they may each receive roughly half of the CPU time.

If we observe a one-second window:

A CPU time ~ 500 ms
B CPU time ~ 500 ms

That does not mean each one got "half of a physical core".

They got alternating slices of execution time on the same logical CPU.

And what if we have several CPUs?

On a multiprocessor machine several tasks can execute in parallel.

Example:

CPU 0 -> task A
CPU 1 -> task B
CPU 2 -> task C
CPU 3 -> task D

If a fifth runnable task appears:

task E

it cannot execute in parallel with the other four.

It has to wait until the scheduler makes one of the CPUs available to it.

So with four logical CPUs:

4 runnable tasks  -> all can be running
5 runnable tasks  -> at least one has to wait
20 runnable tasks -> most will be waiting at any moment

The mere fact that a process is runnable does not guarantee immediate execution.

Threads are scheduled separately

The scheduler does not look at a process only as a whole.

In practice tasks are what gets scheduled, so a multithreaded process can execute several threads at once.

A process:

app
├── thread A
├── thread B
├── thread C
└── thread D

On four CPUs we can have:

CPU 0 -> thread A
CPU 1 -> thread B
CPU 2 -> thread C
CPU 3 -> thread D

Such a process can consume roughly:

4 CPU-seconds

in a single second, because four of its threads executed in parallel for that second.

That is why a value like:

400% CPU

is nothing strange for a multithreaded process in tools that treat 100% as full utilisation of one logical CPU.

The scheduler does not "start a process once"

A process does not get a CPU once and for all.

The scheduler keeps making decisions continuously.

A typical CPU-bound task may look like this:

running
   |
   v
runnable
   |
   v
running
   |
   v
runnable
   |
   v
running

The task is repeatedly taken off the CPU and let back onto it.

From the application's point of view execution looks continuous.

From the kernel's point of view it is a series of CPU-time fragments handed out among many tasks.

The most important mental model

The mechanism boils down to:

task has work
    |
    v
runnable
    |
    v
scheduler picks the task
    |
    v
running
    |
    v
task consumes CPU time

If there are more available CPUs than runnable tasks, a task can usually run quickly.

If there are more runnable tasks than available CPU, some of them have to wait.

And this is the foundation of the whole discussion about CPU:

a process does not own a processor

a process gets time slices from the scheduler
in which it may execute instructions

Every higher layer of CPU control is built on top of this mechanism.