How does the kernel scheduler know how to pre-empt a process?

Question

As far as I understand, the kernel is not a process, but rather a set of handlers that can be invoked from the runtime of another progress (or by the kernel itself via a timer or something similar?)

If a program hits some exception handler that requires long-running synchronous processing before it can start running again (e.g. hits a page fault that requires a disk read), how does the kernel identify that the context should be switched? In order to achieve this, it would seem another process would need to run?

Does the kernel spawn a process that takes care of this by intermittently checking for processes in this state? Does the process that invokes the long-running synchronous handler let the kernel know that it should switch contexts until the handler is complete (e.g. the disk read completes)?

Answer 1

1. "The kernel is not a process."

   This is pure terminology. (Terminology is important.) The kernel is not a process because by definition processes exist in userland. But the kernel does have threads.

2. "If a program hits some exception handler that requires long-running synchronous processing before it can start running again (e.g. hits a page fault that requires a disk read)".

   If a userland process executes a machine instruction which references an unmapped memory page then:

   • The processor generates a trap and transitions to ring 0/supervisor mode. (This happens in hardware.)

   • The trap handler is part of the kernel. Assuming that indeed the memory page must be paged in from disk, it will put the process in the state of uninterruptible sleep (this means it saves the process CPU state in the process table and it modifies status field in the process entry in the table of processes), finds a victim memory page, initiates the I/O to page out the victim and page in the requested page, and invokes the scheduler (another part of the kernel) to switch userland context to another process which is ready to run.

   • Eventually, the I/O completes. This generates an interrupt. In response to the interrupt, the processor invokes a handler and transitions to ring 0/supervisor mode. (This happens in hardware.)

   • The interrupt handler is part of the kernel. It clears the waiting for I/O state of the process which was waiting for the memory page and marks it ready to run. It then invokes the scheduler to switch userland context to a process which is ready to run.

In general, the kernel runs:

• In response to a hardware trap or interrupt; this includes timer interrupts.

• In response to an explicit system call from a user process.

Most of the time, the processor is at ring 3/user mode and executes instructions from some userland process. It transitions to ring 0/supervisor mode (where the kernel lives) when an userland process makes a syscall (for example, because it wants to do some input/output operation) or when the hardware generates a trap (invalid memory access, division by zero, and so on) or when an interrupt request is received from the hardware (I/O completion, timer interrupt, mouse move, packet arrived on the network interface, etc.)

To answer the question in the title, "how does the kernel scheduler know how to pre-empt a process": the kernel handles timer interrupts. If, when a timer interrupt arrives, the schduler notices that the currently running userland process has exhausted its quantum then the process is put at the end of the running queue and another process is resumed. (In general, the scheduler takes care to ensure that all userland processes which are ready to run receive processor time fairly.)

Answer 2

If a program hits some exception handler that requires long-running synchronous processing before it can start running again (e.g. hits a page fault that requires a disk read), how does the kernel identify that the context should be switched? In order to achieve this, it would seem another process would need to run?

The kernel page fault handler calls the kernel scheduler, if the page fault required a disk read.

https://elixir.bootlin.com/linux/v4.17/source/mm/filemap.c#L2470

filemap_fault()
wait_on_page_locked() - usually via __lock_page_or_retry()
wait_on_page_bit()
wait_on_page_bit_common()
io_schedule()
schedule()

---

I haven't quite worked out what you mean by these questions, but I think the answer to the second one is "no, it doesn't need to".

Ignoring optimizations, the kernel will always switch the context immediately after queuing the read. (I.e. this happens before filemap_fault() calls __lock_page_or_retry(). The logic there is a bit more convoluted, but you can click through it without too much difficulty).

If there are no other runnable processes, the kernel will switch the CPU to its idle task. (The Linux kernel has per-cpu idle threads. You don't see them e.g. in top though, unlike the Windows "System Idle Process").