Each process descriptor includes several fields related to scheduling:

When a new process is created, do_fork( ) sets the counter field of both current (the parent) and p (the child) processes in the following way:

p->counter = (current->counter + 1) >> 1; 
current->counter >>= 1; 
if (!current->counter) 
    current->need_resched = 1;

In other words, the number of ticks left to the parent is split in two halves: one for the parent and one for the child. This is done to prevent users from getting an unlimited amount of CPU time by using the following method: the parent process creates a child process that runs the same code and then kills itself; by properly adjusting the creation rate, the child process would always get a fresh quantum before the quantum of its parent expires. This programming trick does not work since the kernel does not reward forks. Similarly, a user cannot hog an unfair share of the processor by starting lots of background processes in a shell or by opening a lot of windows on a graphical desktop. More generally speaking, a process cannot hog resources (unless it has privileges to give itself a real-time policy) by forking multiple descendents.

Besides the fields included in each process descriptor, additional information is needed to describe what each CPU is doing. To that end, the scheduler can rely on the aligned_data array of NR_CPUS structures of type schedule_data. Each such structure consists of two fields:

Most of the time, any CPU accesses only its own array element; it is thus convenient to align the entries of the aligned_data array so that every element falls in a different cache line. In this way, the CPUs have a better chance to find their own element in the hardware cache.

The scheduler is invoked directly when the current process must be blocked right away because the resource it needs is not available. In this case, the kernel routine that wants to block it proceeds as follows:

As can be seen, the kernel routine checks repeatedly whether the resource needed by the process is available; if not, it yields the CPU to some other process by invoking schedule( ). Later, when the scheduler once again grants the CPU to the process, the availability of the resource is rechecked. These steps are similar to those performed by the sleep_on( ) and interruptible_sleep_on( ) functions described in Section 3.2.4.

The scheduler is also directly invoked by many device drivers that execute long iterative tasks. At each iteration cycle, the driver checks the value of the need_resched field and, if necessary, invokes schedule( ) to voluntarily relinquish the CPU.

The scheduler can also be invoked in a lazy way by setting the need_resched field of current to 1. Since a check on the value of this field is always made before resuming the execution of a User Mode process (see Section 4.8), schedule( ) will definitely be invoked at some time in the near future.

For instance, lazy invocation of the scheduler is performed in the following cases:

The goal of the schedule( ) function consists of replacing the currently executing process with another one. Thus, the key outcome of the function is to set a local variable called next so that it points to the descriptor of the process selected to replace current. If no runnable process in the system has priority greater than the priority of current, at the end, next coincides with current and no process switch takes place.

For efficiency reasons, the schedule( ) function starts by initializing a few local variables:

prev = current;
this_cpu = prev->processor;
sched_data = & aligned_data[this_cpu];

As you see, the pointer returned by current is saved in prev, the logical number of the executing CPU is saved in this_cpu, and the pointer to the aligned_data array element of the CPU is saved in sched_data.

Next, schedule( ) makes sure that prev doesn’t hold the global kernel lock or the global interrupt lock (see Section 5.5.2 and Section 5.3.10), and then reenables the local interrupts:

if (prev->lock_depth >= 0)
    spin_unlock(&kernel_flag);
release_irqlock(this_cpu);
_ _sti( );

Generally speaking, a process should never hold a lock across a process switch; otherwise, the system freezes as soon as another process tries to acquire the same lock.However, notice that schedule( ) doesn’t change the value of the lock_depth field; when prev resumes its execution, it reacquires the kernel_flag spin lock if the value of this field is not negative. Thus, the global kernel lock is automatically released and reacquired across a process switch. Conversely, the global interrupt lock is not automatically reacquired.

Before starting to look at the runnable processes, schedule( ) must disable the local interrupts and acquire the spin lock that protects the runqueue (see section Section 3.2.2.5):

spin_lock_irq(&runqueue_lock);

A check is then made to determine whether prev is a Round Robin real-time process (policy field set to SCHED_RR) that has exhausted its quantum. If so, schedule( ) assigns a new quantum to prev and puts it at the bottom of the runqueue list:

if (prev->policy == SCHED_RR && !prev->counter) {
    prev->counter = (20 - prev->nice) / 4 + 1;
    move_last_runqueue(prev);
}

Recall that the nice field of a process ranges between - 20 and + 19; therefore, schedule( ) replenishes the counter field with a number of ticks ranging from 11 to 1. The default value of the nice field is 0, so usually the process gets a new quantum of 6 ticks, roughly 60 ms.^[75]

Next, schedule( ) examines the state of prev. If it has nonblocked pending signals and its state is TASK_INTERRUPTIBLE, the function sets the process state to TASK_RUNNING. This action is not the same as assigning the processor to prev; it just gives prev a chance to be selected for execution:

if (prev->state == TASK_INTERRUPTIBLE && signal_pending(prev)) 
    prev->state = TASK_RUNNING;

If prev is not in the TASK_RUNNING state, schedule( ) was directly invoked by the process itself because it had to wait on some external resource; therefore, prev must be removed from the runqueue list:

if (prev->state != TASK_RUNNING) 
    del_from_runqueue(prev);

The function also resets the need_resched field of prev, just in case the scheduler was activated in the lazy way:

prev->need_resched = 0;

Now the time has come for schedule( ) to select the process to be executed in the next time quantum. To that end, the function scans the runqueue list. The objective is to store in next the process descriptor pointer of the highest priority process:

repeat_schedule:
    next = init_tasks[this_cpu];
    c = -1000;
    list_for_each(tmp, &runqueue_head) {
        p = list_entry(tmp, struct task_struct, run_list);
        if (p->cpus_runnable & p->cpus_allowed & (1 << this_cpu)) {
            int weight = goodness(p, this_cpu, prev->active_mm);
            if (weight > c)
                c = weight, next = p;
        }
    }

The function initializes next so it points to the process referenced by init_task[this_cpu]—that is, to the process (swapper) associated with the executing CPU; the c local variable is set to - 1000. As we shall see in the later section Section 11.2.2.5, the goodness( ) function returns an integer that denotes the priority of the process passed as parameter.

While scanning processes in the runqueue, schedule( ) considers only those that are both:

The loop selects the first process in the runqueue that has the maximum weight. Thus, at the end of the search, next points to the best candidate, and the c local variable contains its priority. It is possible that the runqueue list is empty; in this case, the cycle is not executed, and next points to the swapper kernel thread associated with the executing CPU. It is also possible that the best candidate turns out to be the old current process prev.

A particular case occurs when the local variable c is set to 0 at the exit of the loop. This happens only when all processes in the runqueue list that are runnable by the executing CPU have exhausted their quantum—i.e., all of them have a zero counter field. A new epoch must then begin, and schedule( ) assigns to all existing processes (not only to the TASK_RUNNING ones) a fresh quantum, whose duration is half the counter value plus an increment that depends on the value of nice:

if (!c) { 
    struct task_struct *p;
    spin_unlock_irq(&runqueue_lock);
    read_lock(&tasklist_lock);
    for_each_task(p)
        p->counter = (p->counter >> 1) + (20 - p->nice) / 4 + 1;
    read_unlock(&tasklist_lock);
    spin_lock_irq(&runqueue_lock);
    goto repeat_schedule;
}

In this way, suspended or stopped processes have their dynamic priorities periodically increased. As stated earlier, the rationale for increasing the counter value of suspended or stopped processes is to give preference to I/O-bound processes. However, no matter how often the quantum is increased, its value can never become greater than about 230 ms.^[76]

Let’s assume now that schedule( ) has selected its best candidate, and that next points to its process descriptor. The function updates the aligned_data array element of the executing CPU (this element is referenced by the sched_data local variable), writes the index of the executing CPU in next’s process descriptor, releases the runqueue list spin lock, and reenables local interrupts:

sched_data->curr = next;
next->processor = this_cpu;
next->cpus_runnable = 1UL << this_cpu;
spin_unlock_irq(&runqueue_lock);

Now schedule( ) is ready to proceed with the actual process switch. But wait a moment! If the next best candidate is the previously running process prev, schedule( ) can terminate:

if (prev == next) {
    prev->policy &= ~SCHED_YIELD;
    if (prev->lock_depth >= 0)
        spin_lock(&kernel_flag);
    return;        
}

Notice that schedule( ) reacquires the global kernel lock if the lock_depth field of the process is not negative, as we anticipated when we described the first actions of the function.

If a process other than prev is selected, a process switch must take place. The current value of the Time Stamp Counter, fetched by means of the rdtsc assembly language instruction, is stored in the last_schedule field of the aligned_data array element of the executing CPU:

asm volatile("rdtsc" : "=A" (sched_data->last_schedule));

The context_swtch field of kstat is also increased by 1 to update the statistics maintained by the kernel:

kstat.context_swtch++;

It is also crucial to set up the address space of next properly. We know from Chapter 8 that the active_mm field of the process descriptor points to the memory descriptor that is effectively used by the process, while the mm field points to the memory descriptor owned by the process. For normal processes, the two fields hold the same address; however, a kernel thread does not have its own address space and its mm field is always set to NULL. The schedule( ) function ensures that if next is a kernel thread, then it uses the address space used by prev:

if (!next->mm) {
    next->active_mm = prev->active_mm;
    atomic_inc(&prev->active_mm->mm_count);
    cpu_tlbstate[this_cpu].state == TLBSTATE_LAZY;
}

In earlier versions of Linux, kernel threads had their own address space. That design choice was suboptimal when the scheduler selected a kernel thread as a new process to run because changing the Page Tables was useless; since any kernel thread runs in Kernel Mode, it uses only the fourth gigabyte of the linear address space, whose mapping is the same for all processes in the system. Even worse, writing into the cr3 register invalidates all TLB entries (see Section 2.4.8), which leads to a significant performance penalty. Linux 2.4 is much more efficient because Page Tables aren’t touched at all if next is a kernel thread. As further optimization, if next is a kernel thread, the schedule( ) function sets the process into lazy TLB mode (see Section 2.4.8).

Conversely, if next is a regular process, the schedule( ) function replaces the address space of prev with the one of next:

if (next->mm)
    switch_mm(prev->active_mm, next->mm, next, this_cpu);

If prev is a kernel thread, the schedule( ) function releases the address space used by prev and resets prev->active_mm:

if (!prev->mm) {
    mmdrop(prev->active_mm);
    prev->active_mm = NULL;
}

Recall that mmdrop( ) decrements the usage counter of the memory descriptor; if the counter reaches 0, it also frees the descriptor together with the associated Page Tables and virtual memory regions.

Now schedule( ) can finally invoke switch_to( ) to perform the process switch between prev and next (see Section 3.3.3):

switch_to(prev, next, prev);

The instructions of the schedule( ) function following the switch_to macro invocation will not be performed right away by the next process, but at a later time by prev when the scheduler selects it again for execution. However, at that moment, the prev local variable does not point to our original process that was to be replaced when we started the description of schedule( ), but rather to the process that was replaced by our original prev when it was scheduled again. (If you are confused, go back and read Section 3.3.3.)

The last instructions of the schedule( ) function are:

_ _schedule_tail(prev);
if (current->lock_depth >= 0)
    spin_lock(&kernel_flag);
if (current->need_resched)
    goto need_resched_back;
return;

As you see, schedule( ) invokes _ _schedule_tail( ) (described next), reacquires the global kernel lock if necessary, and checks whether some other process has set the need_resched field of prev while it was not running. In this case, the whole schedule( ) function is reexecuted from the beginning; otherwise, the function terminates.

In uniprocessor systems, the _ _schedule_tail( ) function limits itself to clear the SCHED_YIELD flag of the policy field of prev. Conversely, in multiprocessor systems, the function executes code that is essentially equivalent to the following fragment:

policy = prev->policy;
prev->policy = policy & ~SCHED_YIELD;
wmb( );
spin_lock(&prev->alloc_lock);
prev->cpus_runnable = ~0UL;
spin_lock_irqsave(&runqueue_lock, flags);
if (prev->state == TASK_RUNNING && prev != init_task[smp_processor_id( )]
       && prev->cpus_runnable == ~0UL && !(policy & SCHED_YIELD))
    reschedule_idle(prev);
spin_unlock_irqrestore(&runqueue_lock, flags); 
spin_unlock(&prev->alloc_lock);

The wmb( ) memory barrier is used to make sure that the processor won’t reshuffle the assembly language instructions that modify the policy field with those that acquire the alloc_lock spin lock (see Section 5.3.2).

As you may notice, the role of _ _schedule_tail( ) is far more important in multiprocessor systems because this function checks whether the process that was replaced can be rescheduled on some other CPU. This attempt is performed only if the following conditions are satisfied:

To check whether the priority of prev is high enough to replace the current process of some other CPU, _ _schedule_tail( ) invokes reschedule_idle( ). This is the same function invoked by wake_up_process( ) and is described in the later section Section 11.2.2.6.

The next two sections complete the analysis of the scheduler. They describe, respectively, the goodness( ) and reschedule_idle( ) functions.

The heart of the scheduling algorithm includes identifying the best candidate among all processes in the runqueue list. This is what the goodness( ) function does. It receives as input parameters:

The integer value weight returned by goodness( ) measures the “goodness” of p and has the following meanings:

With respect to earlier versions, the Linux 2.4 scheduling algorithm has been improved to enhance its performance on multiprocessor systems. It was also simplified, which is a great improvement by itself.

As we have seen, each processor runs the schedule( ) function on its own to replace the process that is currently in execution. However, processors are able to exchange information to boost system performance. In particular, right after a process switch, any processor usually checks whether the just replaced process should be executed on some other CPU running a lower priority process. This check is performed by reschedule_idle( ).

The reschedule_idle( ) function looks for some other CPU to run the process p passed as parameter and uses interprocessor interrupts to force other CPUs to perform scheduling. The function performs a series of tests in a fixed order. If one of them is successful, the function sends a RESCHEDULE_VECTOR interprocessor interrupt to the selected CPU (see Section 4.6.2) and returns. If all tests fail, the function returns without forcing a rescheduling. The tests are performed in the following order:

If the number of existing processes is very large, it is inefficient to recompute all dynamic priorities at once.

In old traditional Unix kernels, the dynamic priorities were recomputed every second, so the problem was even worse. Linux tries instead to minimize the overhead of the scheduler. Priorities are recomputed only when all runnable processes have exhausted their time quantum. Therefore, when the number of processes is large, the recomputation phase is more expensive but executed less frequently.

This simple approach has a disadvantage: when the number of runnable processes is very large, I/O-bound processes are seldom boosted, and therefore, interactive applications have a longer response time.

The system responsiveness experienced by users depends heavily on the system load , which is the average number of processes that are runnable and thus waiting for CPU time.^[77]

As mentioned before, system responsiveness also depends on the average time-quantum duration of the runnable processes. In Linux, the predefined time quantum appears to be too large for high-end machines that have a very high expected system load.

The preference for I/O-bound processes is a good strategy to ensure a short response time for interactive programs, but it is not perfect. Indeed, some batch programs with almost no user interaction are I/O-bound. For instance, consider a database search engine that must typically read lots of data from the hard disk, or a network application that must collect data from a remote host on a slow link. Even if these kinds of processes do not need a short response time, they are boosted by the scheduling algorithm. On the other hand, interactive programs that are also CPU-bound may appear unresponsive to the users, since the increment of dynamic priority due to I/O blocking operations may not compensate for the decrement due to CPU usage.

As stated in the first chapter, nonpreemptive kernels are not well suited for real-time applications, since processes may spend several milliseconds in Kernel Mode while handling an interrupt or exception. During this time, a real-time process that becomes runnable cannot be resumed. This is unacceptable for real-time applications, which require predictable and low response times.^[78]

Future versions of Linux might address this problem, by either implementing SVR4’s “fixed preemption points” or making the kernel fully preemptive. It remains questionable, however, whether these design choices are appropriate for a general-purpose operating systems such as Linux.

Kernel preemption, in fact, is just one of several necessary conditions for implementing an effective real-time scheduler. Several other issues must be considered. For instance, real-time processes often must use resources that are also needed by conventional processes. A real-time process may thus end up waiting until a lower-priority process releases some resource. This phenomenon is called priority inversion . Moreover, a real-time process could require a kernel service that is granted on behalf of another lower-priority process (for example, a kernel thread). This phenomenon is called hidden scheduling . An effective real-time scheduler should address and resolve such problems.

Luckily, all these shortcomings have been fixed in the brand new scheduler developed by Ingo Molnar that is included in the Linux 2.5 current development version. This scheduler is so efficient that it has been back-ported to Linux 2.4 and adopted by some commercial distributions of the GNU/Linux system.