How does Linux retain control of the CPU on a single-core machine?

In How does Linux “kill” a process? it is explained that Linux kills a process by returning its memory to the pool.

On a single-core machine, how does it actually do this? It must require CPU time to kill a process, and if that process is doing some extremely long running computation without yielding, how does Linux gain control of the processor for long enough to kill off that process?

Asked By: Adam Griffiths

||

The kernel gains control quite frequently in normal operations: whenever a process calls a system call, and whenever an interrupt occurs. Interrupts happen when hardware wants the CPU’s attention, or when the CPU wants the kernel’s attention, and one particular piece of hardware can be programmed to request attention periodically (the timer). Thus the kernel can ensure that, as long as the system doesn’t lock up so hard that interrupts are no longer generated, it will be invoked periodically.

As a result,

if that process is doing some extremely long running computation without yielding

isn’t a concern: Linux is a preemptive multitasking operating system, i.e. it multitasks without requiring running programs’ cooperation.

When it comes to killing processes, the kernel is involved anyway. If a process wants to kill another process, it has to call the kernel to do so, so the kernel is in control. If the kernel decides to kill a process (e.g. the OOM killer, or because the process tried to do something it’s not allowed to do, such as accessing unmapped memory), it’s also in control.

Note that the kernel can be configured to not control a subset of a system’s CPUs itself (using the deprecated isolcpus kernel parameter), or to not schedule tasks on certains CPUs itself (using cpusets without load balancing, which are fully integrated in cgroup v1 and cgroup v2); but at least one CPU in the system must always be fully managed by the kernel. It can also be configured to reduce the number of timer interrupts which are generated, depending on what a given CPU is being used for.

There’s also not much distinction between single-CPU (single-core, etc.) systems and multi-CPU systems, the same concerns apply to both as far as kernel control is concerned: each CPU needs to call into the kernel periodically if it is to be used for multitasking under kernel control.

Answered By: Stephen Kitt

Linux and most modern OSes use preemptive multitasking which means the kernel has complete control over the time each process is allowed to run and will preempt a process if it runs for too long, unlike cooperative multitasking where a process will pass control whenever it likes

Basically in preemptive multitasking the kernel will be fired periodically from a timer, and whenever the kernel is in control (when the timer interrupt happens or a system call is invoked) the kernel will save the current process’ context and then switch to the next process’ context if necessary. That’s called a context switch where the whole state of the process including all thread information, register values… are saved and restored to make the process continue to run from the exact point it was preempted without even knowing it hasn’t run continuously. Therefore lots of processes will appear to run simultaneously in a single CPU core, even though in reality only 1 process is being run at any moment. The kernel is also just a special process that does all the process and resource handling. It’s not run from a separate core just to monitor other processes

See also What does it mean to say “linux kernel is preemptive”?

Answered By: phuclv

To put it simply, the kernel is the absolute dictator* of the system. It controls when processes get resources (by being a preemptive multitasking kernel), and controls what resources it gets. (Processes ask for resources, and the kernel gives it to them if they are available. If they aren’t available, the resources are not given.)

Being the absolute dictator, the kernel can kill them if it thinks it needs to.

* There are always exceptions and edge cases.

Answered By: RonJohn

In some weird cases (embedded devices, perhaps RaspberryPi based) you could have a Linux kernel (see kernel.org & kernelnewbies.org for details) managing a very limited set of processes.

You could even write your own /sbin/init program

then you have control over the set of processes entirely.

(see init(1)) so that it fork(2)-s very few child processes and uses other syscalls(2).

This Operating System textbook should give you more insights, and you’ll learn a lot by compiling the Linux kernel from its source code. The first command to run is probably make menuconfig (after having the entire Linux kernel tree on your local disk). Read also Advanced Linux Programming and signal(7), time(7), vdso(7).

However, observe than in 2020 most processors for Linux have at least two cores. And many Linux systems are using systemd, whose source code is open source (and you are allowed to study it and improve it). Other Linux systems could use runit (also open source). With care and inspiration from existing init programs you could write your own.

You may want to see Linux From Scratch, and study the source code of your crt0 routines, and of GNU libc (it is free software, like GCC and GNU binutils and GNU bash are!) or musl-libc.

A related concept is that of continuations (a fancy name for reification of call stacks) and the call/cc primitive of Scheme. So read R5RS, ACM SIGPLAN conference proceedings (e.g. PLDI), Queinnec’s book Lisp In Small Pieces, and Pitrat’s book Artificial Beings and perhaps also this draft report (funded by CHARIOT). Be aware of Rice’s theorem.

If you use GCC, don’t forget to compile your foo.c code as gcc -Wall -Wextra -fverbose-asm -S foo.c then look inside foo.s

The OSDEV website also gives practical information about writing (and studying the source code of) operating system kernels. You could be interested by the Singularity software and FOSDEM and ACM SIGOPS conferences.

You may want to use /proc/ (see proc(5)) then you could observe that your Linux kernel is processing interrupts quite often (typically hundreds of interrupts per second). Each interrupt (e.g. those triggered by HPET) is an occasion (for the Linux kernel) to schedule some other process.

If your hardware don’t give hundreds of interrupts every second, you should discuss with the provider or designer of your hardware.

that process is doing some extremely long running computation without yielding

On Linux that never happens, unless your kernel or your hardware is buggy.

In user-space a process gets interrupted at least dozen of times per second (in 2020, on most hardware). Read about kernel preemption and context switch.

Observe that a context switch is changing the current continuation. At an abstract level, an interrupt is close to some call/cc in Scheme.

Answered By: Basile Starynkevitch
Categories: Answers Tags: ,
Answers are sorted by their score. The answer accepted by the question owner as the best is marked with
at the top-right corner.