[This is still pretty weak, but I think that I have removed most or all of the inaccuracies that were in previous versions. Jim Wisner appears to have dropped from the face of the net, so I have not been able to get his help at making this chapter more meaningful. If anyone has a copy of the paper he wrote on the scheduler, please get in touch with me, as he promised me a copy, and I'd at least like to see what he had to say about the scheduler.]
[I'm not going to spend any further time on this until the new scheduler is added to Linux. The current one doesn't handle lots of tasks at once very well, and some day a new one will be put in.]
The scheduler is a function, schedule(), which is called at various times to determine whether or not to switch tasks, and if so, which task to switch to. The scheduler works in concert with the function do_timer(), which is called 100 times per second (on ), on each system timer interrupt, and with the system call handler part ret_from_sys_call() which is called on the return from system calls.
When a system call completes, or when a ``slow'' interrupt completes, ret_from_sys_call() is called. It does a bit of work, but all we care about are two lines:
These lines check the need_resched flag, and if it is set, schedule() is called, choosing a new process, and then after schedule() has chosen the new process, a little more magic in ret_from_sys_call() restores the environment for the chosen process (which may well be, and usually is, the process which is already running), and returns to user space. Returning to user space causes the new process which has been selected to run to be returned to.
In sched_init() in kernel/sched.c, request_irq() is used to get the timer interrupt. request_irq() sets up housekeeping before and after interrupts are serviced, as seen in <asm/irq.h>. However, interrupts that are serviced often and that must be serviced quickly, such as serial interrupts, do not call ret_from_sys_call() when done and do as little as possible, to keep the overhead down. In particular, they only save the registers that C would clobber, and assume that if the handler is going to use any others, the handler will deal with that. These ``fast'' interrupt handlers must be installed with the irqaction() function described in section .
The scheduler is significantly different from the schedulers in other unices, especially in its treatment of `nice level' priorities. Instead of scheduling processes with higher priority first, does round-robin scheduling, but lets higher priority processes run both sooner and longer. The standard scheduler instead uses queues of processes. Most implementations use two priority queues; a standard queue and a ``real time'' queue. Essentially, all processes on the ``real time'' queue get executed before processes on the standard queue, if they are not blocked, and within each queue, higher nice-level processes run before lower ones. The scheduler gives much better interactive performance at the expense of some ``throughput.''