Each type of process scheduler has benefits and drawbacks. Normally, when designing an operating system, we evaluate the criteria in order to pick the best scheduling strategy. The algorithms presented here are rather basic, and it is important to note that in a real system, it is common to employ a mixture or these strategies to create an appriopriate scheduler.

The Linux scheduler uses a preemptive, priority-based algorithm with two separate priority factors: a real-time range from 0 to 99, and a nice factor ranging from 100 to 140. Numerically lower values indicate higher priorities.

Unlike other operating systems, the Linux scheduler also assigns a variable time quanta to processes, based on priority. A higher-priority task will get a longer time quanta to run, while lower-priority tasks get shorter time quanta.

A runnable task can execute as long as it has time remaining in its time slice. If a task exhausts its time slice, it is considered to be expires and will not be eligible for execution again until all other tasks have also exhausted their time quanta.

Linux kernels prior to version 2.5 ran a variation of the traditional UNIX scheduling algorithm, which did not provide sufficient support for Symmetric Multi-Processing (SMP) and did not scale well as the number of tasks grew. Since version 2.5, however, the scheduler was re-written, and the algorithm now runs in constant time, O(1), regardless of the number of tasks. The scheduler now also provides better support for multi-processor systems, including features for load balancing.

The kernel maintains a list of all runnable tasks in a runqueue. Because of its support for SMP, each processor maintains its own runqueue and schedules itself independently. Each runqueue also contains two priority arrays - and active and expired array. The active array contains tasks with time remaining in their time slices. The expired array stores tasks which have expired. Once the active array is empty, the two arrays are swapped, and the process repeats.

Solaris uses priority-based thread scheduling. It defines four levels of scheduling, which are Real Time, System, Time sharing, and Interactive.

Each level, or class, has different priorities and employ different algorithms. The default class for normal processes is time sharing.

In the time sharing class, there is an inverse relationship between priorities and time slices: The higher the priority the smaller the time slice; the lower the priority the higher the time slice. This policy gives good response time for interactive processes (which have a higher priority) and good throughput for CPU-bound processes (which have lower priorities).

The interactive class uses the same scheduling policy as the time sharing class, but gives windowing applications higher priority for better performance.

Even though each scheduling class includes its own set of priorities, the scheduler converts these to global priorities and selects the thread with the next highest global priority. The selected thread runs on the CPU until it blocks, finished its time slice, or is preempted by a higher-priority thread. If multiple threads have the same priority, the scheduler uses a round-robin queue.

The Windows XP scheduler schedules threads using a priority, preemptive algorithm. It ensures that the highest priority thread will always run. A thread selected to run by the scheduler will continue to run until it is preempted by a higher-priority thread, until it terminates, until its time quantum ends, or until a blocking system call causes the thread to wait (such as on I/O).

Similar to Solaris, priorities are divided into two classes. The variable class contains threads having priorities from 1 to 15, and the real-time class contains threads ranging from 16 to 31. (The thread running at priority 0 is a special thread used for memory management.) The scheduler uses a queue for each scheduling priority and traverses the queues from highest to lowest until it finds a thread that is ready to run. If no ready thread can be found, the scheduler will execute a special thread called the idle thread.

The Win32 API provides several priority classes, which include (together with their base priority values):

• REALTIME_PRIORITY = 24
• HIGH_PRIORITY = 13
• ABOVE_NORMAL_PRIORITY = 10
• NORMAL_PRIORITY = 8
• BELOW_NORMAL_PRIORITY = 6
• IDLE_PRIORITY = 4

Priorities in all classes except the REALTIME_PRIORITY class are variable. Within each of the priority classes is a relative priority, that is based on a similar priority segregation - TIME_CRITICAL, HIGHEST, ABOVE_NORMAL, NORMAL, BELOW_NORMAL, LOWEST, IDLE.

Thus, the global priority of each thread is based on its priority class, and also its relative priority within that class.

When a thread exhausts its time quanta, it is interrupted. If the thread is in a variable-priority class, its priority is lowered, although a priority is never lowered below its base priority value. When a thread is released from a wait operation, the scheduler boosts its priority. The amount of boost depends on what the thread was waiting for. A thread waiting for keyboard input would get a large boost, whereas a thread waiting for a disk operation would get a lower boost. This strategy gives good response times to interactive threads, and also enables the I/O-bound threads to keep the I/O devices busy. This strategy is used by several operating systems, including UNIX. In addition, the windows which the user is currently interacting with receives a priority boost to enhance its response time.