The job of allocating CPU time to different tasks within an operating system.
While scheduling is normally thought of as the running and interrupting of processes, in Linux, scheduling also includes the running of the various kernel tasks.
Running kernel tasks encompasses both tasks that are requested by a running process and tasks that execute internally on behalf of a device driver.
A request for kernel-mode execution can occur in two ways:
1. A running program may request an operating system service, either explicitly via a system call,
or implicitly, for example, when a page fault occurs.
2. A device driver may deliver a hardware interrupt that causes the CPU to start executing a
kernel-defined handler for that interrupt.
Kernel synchronization requires a framework that will allow the kernelís critical sections to run without interruption by another critical section.
Linux uses two techniques to protect critical sections:
1. Normal kernel code is non-preemptible
when a time interrupt is received while a process is executing a kernel system service routine, the kernelís need reached flag is set so that the scheduler will run once the system call has completed and control is about to be returned to user mode.
2. The second technique applies to critical sections that occur in an interrupt service routines.
By using the processorís interrupt control hardware to disable interrupts during a critical section, the kernel guarantees that it can proceed without the risk of concurrent access of shared data structures.
To avoid performance penalties, Linuxís kernel uses a synchronization architecture that allows long critical sections to run without having interrupts disabled for the critical sectionís entire duration.
Interrupt service routines are separated into a top half and a bottom half.
1. The top half is a normal interrupt service routine, and runs with recursive interrupts disabled.
2. The bottom half is run, with all interrupts enabled, by a miniature scheduler that ensures that
bottom halves never interrupt themselves.
3. This architecture is completed by a mechanism for disabling selected bottom halves while
executing normal, foreground kernel code.
Interrupt Protection Levels
Each level may be interrupted by code running at a higher level, but will never be interrupted by code running at the same or a lower level.
User processes can always be preempted by another process when a time-sharing scheduling interrupt occurs.
Linux uses two process-scheduling algorithms:
1. A time-sharing algorithm for fair preemptive scheduling between multiple processes
2. A real-time algorithm for tasks where absolute priorities are more important than fairness
A processís scheduling class defines which algorithm to apply.
For time-sharing processes, Linux uses a prioritized, credit based algorithm.
1. The crediting rule factors in both the processís history and its priority.
2. This crediting system automatically prioritizes interactive or I/O-bound processes.
credits : = credits + priority
Linux implements the FIFO and round-robin real-time scheduling classes; in both cases, each process has a priority in addition to its scheduling class.
1. The scheduler runs the process with the highest priority; for equal-priority processes, it runs
the longest-waiting one
2. FIFO processes continue to run until they either exit or block
3. A round-robin process will be preempted after a while and moved to the end of the scheduling
queue, so that round robin processes of equal priority automatically time-share between
Linux 2.0 was the first Linux kernel to support SMP hardware; separate processes or threads can execute in parallel on separate processors.
To preserve the kernelís nonpre-emptible synchronization requirements, SMP imposes the restriction, via a single kernel spin lock, that only one processor at a time may execute kernel-mode code.