How does preemption on x86 architecture work?

Question

I'm struggling to understand one thing about preemption. Citing Wikipedia:

In computing, preemption (more correctly pre-emption) is the act of temporarily interrupting a task being carried out by a computer system, without requiring its cooperation, and with the intention of resuming the task at a later time. Such a change is known as a context switch. It is normally carried out by a privileged task or part of the system known as a preemptive scheduler, which has the power to preempt, or interrupt, and later resume, other tasks in the system.

So, basically, they say the scheduler can interrupt the current running task. How is that even possible? CPU is running the code of this task at the moment, not the code of scheduler. So how a scheduler can do anything?

My guess is that there must be some kind of a hardware timer which physically interrupts CPU after some time has passed and give control back to scheduler. Is this correct? Is there any documentation where I can read about it in more detail?

Any answers will be highly appreciated.

Chrysanthemum

Answer 1

Indeed. The x86 architecture has a concept known as interrupts. Some interrupts are triggered by the hardware (and others can be triggered from software).

The kernel registers "handlers" that take care of this. If you're into kernel design, here's a tutorial that may help: http://www.osdever.net/bkerndev/Docs/gettingstarted.htm (note: some of this stuff can be pretty hard and covers some topics that are not strictly part of your question)

When an interrupt is triggered, the code that is currently being executed is stopped. The CPU will instead execute the handler and, once the handler is done, go back to the code that was being executed before the interrupt was triggered. For the application, it's as if the interrupt never happened at all.

We can combine interrupt handling with, say, a hardware clock(such as the PIT chip) to get the result you want.

You can also check http://wiki.osdev.org/PIT (again, be aware that some of this stuff can be complicated if you're just getting started on the topic).

Using the IRQ for Preemptive Multitasking

The timer IRQ can also be used to perform preemptive multitasking. To give the currently running task some time to run, set a threshold, for example of 3 ticks. Use a global variable like the one before but go up from 0, and when that variable hits 3, switch tasks. How you do so is up to you.

So:

1. The kernel says "When the time expires, I want this code to be executed" by registering the adequate interrupt handler.
2. The timer expires, triggering an interrupt. The code that the kernel registered is then executed.
3. The kernel takes over, saves all the required data (such as the state of registers and the the address of the code that was being executed) from the stopped process, and gives control to a different process.
4. Later, when the kernel wants the first process to continue, it uses all the saved data to restore the process to its former state. Then, it tells the CPU to continue executing the code from where it stopped.

Tenor

Big thanks. So this timer exists and is called PIT. BTW, this site and you guys are amazing. Not even 5 minutes and I get satisfying answer for my question. Wow! – Chrysanthemum

Answer 2

Your guess is correct. In most operating systems, there is a timer interrupt that runs privileged code in the kernel on some fixed frequency. This privileged code can decide to either (a) return to the originally running code, or (b) save the context and start running some other code.

There are other conditions which can cause a context switch, such as a request to read from I/O where the process would have to wait for the I/O be ready. The kernel will probably switch to some other task while the first is waiting.

You may also be interested in reading about the so-called tickless kernel.

Antares