UNIX for Advanced & Expert Users

I never understood what exactly it is that preempts a process in a preemptive multitasking system. For example, round-robin, SRTF, or preemptive priority-based algorithms. I understand how the algorithm works, but what exactly triggers the preemption? I know in the case of round-robin scheduling, there is a clock interrupt that preempts a process once its time slot runs out. How exactly does this work? As for SRTF and priority-based preemption, the only time a task would be preempted would be if another task enters the queue that has a higher priority and/or a shorter remaining execution time. So essentially, preemption only occurs in response to a fork() system call. So I would assume that fork() somehow triggers preemption, but I've looked at the algorithm for fork() as given in The Design of the Unix Operating System and it doesn't mention preemption. What is it that triggers a context switch, and how does this process interrupt mechanism work?

A timer. Hardware interrupts are happening all the time which gives a vector for the kernel to regain control without programs cooperatively giving it up. Keyboard or network (as just two examples) input being available cause interrupts so we can handle the data before buffers overflow. The timer does this too at regular intervals every few hz (Linux i386 once defaulted to 1000, MIPS to 100). I imagine that's when the scheduler decides who goes next. It's not just when fork() is called. we'd never regain control like that.

when there is no work to do, calling the interrupt handler alone keeps the CPU a little busy and wastes some power so modern kernels have dynamic ticks.

So the timer interrupt causes this context switch, how does it work depends on the arch I suppose. I know in MIPS there was a jump table of exception handlers created and stored at the beginning of memory. When the timer ticked, the Interrupt exception handler is called. That in turn checked a status register to know which interrupt. Then you'd exit that into the next program that deserved attention.

So does Unix do any preemption with fork(), or is it just round-robin scheduling with timer interrupts?

fork() pre-empts -- just like any and every other system call pre-empts. The calling process is forced to stop during any system call, while the kernel executes instead. This does not mean the new process is guaranteed to start before the parent restarts, however. UNIX gives no guarantees of scheduling order unless you specifically ask for it.

UNIX scheduling is more complicated than round robin. You can set priorities. The 'nice' command is related to this, it lets you run a process at reduced priority.

How the scheduler itself is built varies because there's way more than one kind of UNIX, but it's often credit-based -- i.e. processes which "behave" are run preferentially before ones which "misbehave". A polite process pre-empts by itself, from waiting on I/O or calling sleep(), etc. An impolite job, such as a CPU-intensive physics simulation, almost never pre-empts by itself and gets demerits when the kernel must force pre-emption instead.

This allows the scheduler to automatically prioritize interactive processes -- where waits might be noticed -- above batch jobs, which care much less.

Also see multilevel feedback queue.