...making Linux just a little more fun!
The Linux Scheduler
By Vinayak Hegde

Why the Design of Scheduler is critical

Two of the most critical parts of a kernel are the memory subsystem and the scheduler. This is because they influence the design and affect the performance of almost every other part of the kernel and the OS. That is also why you would want to get them absolutely right and optimize their performance. The Linux kernel is used right from small embedded devices, scaling up to large mainframes. Designing is scheduler is at best a black art. No matter how good the design is, some people will always feel that some categories of processes have got a raw deal.

In the article that follows, I have purposely tried to skip quoting any reference code because one can easily get it from the net (see the references). The article also looks the challenges developers found when they redesigned the scheduler, how those challenges were met, and what could be the the future direction the scheduler is likely to follow. Having said that, there's nothing like reading the source code to get an understanding of what's going on under the hood. You will find the implementation of the scheduler in kernel/sched.c if you have the kernel source installed.

Scheduling Objectives

The Linux scheduler strives to meet several objectives :

  1. Fairness :

    The scheduler should give a fair amount of CPU share to every process. Quite a fair amount of work has been done in the new kernel to ensure fair sharing of CPU time among processes.

  2. Throughput and CPU utilization :

    The scheduler should try to maximize both throughput and CPU utilization. The usual method of increasing CPU utilization is by increasing the amount of multi-programming. But this is only beneficial up to a point after which it becomes counterproductive and thrashing starts.

  3. Minimal Overhead :

    A scheduler itself should run for as small time as possible. The scheduler latency should be minimal. But this is the tricky part. It is generally seen that scheduling itself is not useful work (??) . But if the scheduling is done right even after expending some more time, it may be worth the effort. But how do we decide which is the optimal point? Most scheduler solve this problem by using some heuristic policies.

  4. Enforce priority-based scheduling :

    Priority scheduling means that some processes get more preference over others. At the very least the scheduler must differentiate between I/O-bound processes and CPU-bound processes. Moreover, some kind of aging must be be implemented so that starvation of processes does not take place. Linux does enforce priorities as well as differentiates between different categories of processes. The Linux kernel differentiates between batch scheduled jobs and interactive. They get a share of the CPU according to their priorities. Probably some people have used the nice command to change the priority of a process.

  5. Turnaround time, waiting time :

    Turnaround time is the sum of the service time and amount of time wasted waiting in the ready queue. The scheduler tries to reduce both.

  6. Response time and Variance :

    The response from a program should be as fast as possible. Also another important factor which is often ignored is the variance between the response times. It is not acceptable if the average response time is low but some user occasionally experiences say, a 10-second delay from an interactive program.

  7. Miscellaneous :

    The scheduler also tries to meet some other goals such as predictability. The behavior of the scheduler should be predictable for a given set of process with assigned priorities. The scheduler performance must degrade gracefully under heavy loads. This is particularly important because the Linux is very popular in the server market, and servers tend to get overloaded during peak traffic hours.

Improvements in the scheduler



[BIO] Vinayak is currently pursuing the APGDST course at NCST. His areas of interest are networking, parallel computing systems and programming languages. He believes that Linux will do to the software industry what the invention of printing press did to the world of science and literature. In his non-existent free time he likes listening to music and reading books. He is currently working on Project LIberatioN-UX where he makes affordable computing on Linux accessible for academia/corporates by configuring remote boot stations (Thin Clients).

Copyright © 2003, Vinayak Hegde. Copying license
Published in Issue 89 of Linux Gazette, April 2003