What is the mechanism that allows the scheduler to switch which threads are executing?

Question

I understand that the cpu scheduler uses time slices and has a thread run for a specified amount of time and then switches threads, but what I don't understand is how the CPU knows to stop executing a thread and switch tasks. It can't check a clock repeatedly after every instruction right? That would take so much overhead it would be very wasteful. I don't think it uses some deterministic calculations on the thread to place an interrupt at some instruction where it assumes the time will have elapsed by the time it reaches that instruction, so then how does the context switch take place? How does the CPU stop execution without constantly checking a clock or something?

Answer 1

It's the timer interrupt.

Interrupts are one of those things that are beyond Turing-complete. A Turing-complete machine/language does not need to implement interrupts. But without interrupts you will have a hard time implementing a time-sliced or preemptive multitasking OS.

Without interrupts

It is still possible to implement a multitasking OS on a system without interrupts - you use Cooperative Multitasking. The old MacOS (before OSX) did just this. You just tell app developers that every now and then they must hand over execution to the OS by calling something like yield(). This "yield" function is actually the OS itself. Cooperative multitasking is not ideal of course - you can imagine a program crashing will cause the OS to never execute thus take down the entire machine. The advantage of cooperative multitasking is that you can do it on a very simple CPU with no interrupt support. It also typically requires a lot less RAM and CPU resources. And, as a programmer you have more control over the CPU - for example if you need to really use 100% of the CPU you can prevent the OS from taking any CPU time.

Interrupts

An interrupt is just a feature of the CPU where you can configure the CPU to call a function (called the interrupt handler) when something happens. For OS programmers, the most useful is the timer interrupt - where you can configure a timer to trigger an interrupt. The OS gets to run when the interrupt is triggered and at the end of execution the OS will simply schedule another timer interrupt - this is time-sliced multitasking.

Some OSes like Linux or Real-time Windows allow you to configure this timer. Linux call it jiffy, some OSes call it tick.

If you have done any javascript programming this will feel familiar to you - this is almost like how setTimeout() appears to behave to a programmer.

I/O

Another important type of interrupt is I/O interrupt. Your keyboard actually works with an I/O interrupt. A normal PC does not scan the keyboard at all. Instead the I/O controller (these days it's usually the USB controller) queries the keyboard and if there is a key press will send an interrupt signal to the CPU. This will trigger the OS and the OS will check which process the key belongs to and will switch to the process to allow it to receive the input - this is preemptive multitasking. Obviously, preemptive multitasking uses a time-slicer in the background in case there are long periods of no I/O activity.

Answer 2

"It can't check a clock repeatedly after every instruction - right?" CPU has special device - timer. It has a register which contains the time left for alarm and is decremented at every clock tick. As soon as it becomes zero, an interrupt is raised. Interrupt is implemented exactly as a procedure invocation, though the call to that procedure was not present in the currently executing program code. Interruption procedure can make some prescribed activities, set another timer value and return, then the currently executing program would not notice this invocation. Or it can decide to park current thread and let another thread to execute on this processor. In that case, the interruption procedure reloads special registers so that they point to that next thread and also makes return, and returns to a procedure which was executing on that another thread some time ago.

This way processor switches from one thread to another, and threads switch between active and passive states.