Scheduling

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.

Kernel Synchronization

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.

Process Scheduling

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 

        themselves.

Symmetric Multiprocessing

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.