13

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?

43

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.

  • Could you please add some links regarding the kernel relinquishing control of CPUs? – Roman Odaisky Nov 27 '20 at 19:02
  • @RomanOdaisky Also curious about this. I would imagine (complete guess) that if the system designer wished to enable some type of realtime guarantees for a portion of the system, they could have the kernel relinquish preemptive control of a core and let a (somewhat) realtime application run on said core. – Zee2 Nov 28 '20 at 7:33
  • @Roman I’ve added some information, thanks for askin. – Stephen Kitt Nov 28 '20 at 8:52
  • @Zee2 that’s one common use case, see details in relation to RHEL for RT for example. – Stephen Kitt Nov 28 '20 at 8:53
11

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. 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”?

  • 9
    A couple of minor quibbles. The kernel doesn’t necessarily change processes when it returns to user space; it returns to whichever process is the one chosen to run next, and that could be the same as before. “Preemptive” has somewhat different meanings in “preemptive multitasking” and “preemptive kernel” — in the former, processes are preempted; in the latter, the kernel is preempted. Linux has always used preemptive multitasking, but the kernel itself has been preemptive only since 2.5.4 (I suspect you know that but it’s not clear from your answer that there’s a difference). – Stephen Kitt Nov 25 '20 at 16:27
1

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.

0

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.

  • Re: "exceptions and edge cases" - provided a kernel is running (and without a hypervisor), when is the kernel not the BDFL of a computer system? User-code doesn't run in Ring 0. – Dai Nov 26 '20 at 22:08
  • 1
    Really the CPU is the dictator and the kernel is the dictator's buddy who the dictator always gives special favours to. – user253751 Nov 27 '20 at 17:43
  • 1
    Code can't do anything. Code is just instructions that tell the CPU what to do, and the operating system is just code. The question is, when the CPU is executing the instructions of some application program, and the instructions of the application program tell the CPU to keep going 'round an infinite loop, what could ever cause the CPU to suddenly stop following those instructions, and start executing operating system instructions instead? The answer is, interrupts – Solomon Slow Nov 28 '20 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.