Department of Software Engineering
Mehran University of Engineering and Technology, Jamshoro
Course: SWE211 – Operating System Concepts
Instructor Asadullah Channar Practical/Lab No. 15
Date CLOs 3
Signature Assessment Score
Topic Case Study
Objectives - To enable students to understand CPU scheduling in Linux
Lab Discussion: Theoretical concepts and Procedural steps
CPU Scheduling in Linux
Scheduling is the job of allocating CPU time to different tasks within an operating
system. Linux, like all UNIX systems, supports preemptive multitasking. In such a
system, the process scheduler decides which process runs and when.
Making these decisions in a way that balances fairness and performance across
many different workloads is one of the more complicated challenges in modern
operating systems.
Process Scheduling
Linux has two separate process-scheduling algorithms. One is a time-sharing
algorithm for fair, preemptive scheduling among multiple processes. The other is
designed for real-time tasks, where absolute priorities are more important than
fairness.
1. Time Sharing Scheduling
The scheduling algorithm used for routine time-sharing tasks received a major
overhaul with version 2.6 of the kernel. Earlier versions ran a variation of the
traditional UNIX scheduling algorithm. This algorithm does not provide adequate
support for SMP systems, does not scale well as the number of tasks on the
system grows, and does not maintain fairness among interactive tasks,
particularly on systems such as desktops and mobile devices. The process
scheduler was first overhauled with version 2.5 of the kernel. Version 2.5
implemented a scheduling algorithm that selects which task to run in constant
time—known as O(1)— regardless of the number of tasks or processors in the
system. The new scheduler also provided increased support for SMP, including
processor affinity and load balancing. These changes, while improving scalability,
did not improve interactive performance or fairness—and, in fact, made these
problems worse under certain workloads. Consequently, the process scheduler
was overhauled a second time, with Linux kernel version 2.6. This version
ushered in the Completely Fair Scheduler (CFS).
The Linux scheduler is a preemptive, priority-based algorithm with two separate
priority ranges: a real-time range from 0 to 99 and a nice value ranging from −20
to 19. Smaller nice values indicate higher priorities. Thus, by increasing the nice
value, you are decreasing your priority and being “nice” to the rest of the system.
CFS is a significant departure from the traditional UNIX process scheduler. In the
latter, the core variables in the scheduling algorithm are priority and time slice.
The time slice is the length of time—the slice of the processor— that a process is
afforded. Traditional UNIX systems give processes a fixed time slice, perhaps
with a boost or penalty for high- or low-priority processes, respectively. A
process may run for the length of its time slice, and higher-priority processes run
before lower-priority processes. It is a simple algorithm that many non-UNIX
systems employ. Such simplicity worked well for early time-sharing systems but
has proved incapable of delivering good interactive performance and fairness on
today’s modern desktops and mobile devices.
CFS introduced a new scheduling algorithm called fair scheduling that eliminates
time slices in the traditional sense. Instead of time slices, all processes are
allotted a proportion of the processor’s time. CFS calculates how long a process
should run as a function of the total number of runnable processes. To start, CFS
says that if there are N runnable processes, then each should be afforded 1/N of
the processor’s time. CFS then adjusts this allotment by weighting each process’s
allotment by its nice value. Processes with the default nice value have a weight of
1—their priority is unchanged. Processes with a smaller nice value (higher
priority) receive a higher weight, while processes with a larger nice value (lower
priority) receive a lower weight. CFS then runs each process for a “time slice”
proportional to the process’s weight divided by the total weight of all runnable
processes.
To calculate the actual length of time a process runs, CFS relies on a configurable
variable called target latency, which is the interval of time during which every
runnable task should run at least once. For example, assume that the target
latency is 10 milliseconds. Further assume that we have two runnable processes
of the same priority. Each of these processes has the same weight and therefore
receives the same proportion of the processor’s time. In this case, with a target
latency of 10 milliseconds, the first process runs for 5 milliseconds, then the
other process runs for 5 milliseconds, then the first process runs for 5
milliseconds again, and so forth. If we have 10 runnable processes, then CFS will
run each for a millisecond before repeating.
But what if we had, say, 1, 000 processes? Each process would run for 1
microsecond if we followed the procedure just described. Due to switching costs,
scheduling processes for such short lengths of time is inefficient. CFS consequently
relies on a second configurable variable, the minimum granularity, which is a
minimum length of time any process is allotted the processor. All processes,
regardless of the target latency, will run for at least the minimum granularity. In this
manner, CFS ensures that switching costs do not grow unacceptably large when the
number of runnable processes grows too large. In doing so, it violates its attempts at
fairness. In the usual case, however, the number of runnable processes remains
reasonable, and both fairness and switching costs are maximized.
With the switch to fair scheduling, CFS behaves differently from traditional UNIX
process schedulers in several ways. Most notably, as we have seen, CFS eliminates
the concept of a static time slice. Instead, each process receives a proportion of the
processor’s time. How long that allotment is depends on how many other processes
are runnable. This approach solves several problems in mapping priorities to time
slices inherent in preemptive, priority-based scheduling algorithms. It is possible, of
course, to solve these problems in other ways without abandoning the classic UNIX
scheduler. CFS, however, solves the problems with a simple algorithm that performs
well on interactive workloads such as mobile devices without compromising
throughput performance on the largest of servers.
2. Real-Time Scheduling
Linux’s real-time scheduling algorithm is significantly simpler than the fair
scheduling employed for standard time-sharing processes. Linux implements the
two real-time scheduling classes required by POSIX.1b: first-come, first-served
(FCFS) and round-robin. In both cases, each process has a priority in addition to
its scheduling class. The scheduler always runs the process with the highest
priority. Among processes of equal priority, it runs the process that has been
waiting longest. The only difference between FCFS and round-robin scheduling is
that FCFS processes continue to run until they either exit or block, whereas a
round-robin process will be preempted after a while and will be moved to the
end of the scheduling queue, so round-robin processes of equal priority will
automatically time-share among themselves.
Linux’s real-time scheduling is soft—rather than hard—real time. The scheduler
offers strict guarantees about the relative priorities of real-time processes, but
the kernel does not offer any guarantees about how quickly a real-time process
will be scheduled once that process becomes runnable. In contrast, a hard real-
time system can guarantee a minimum latency between when a process becomes
runnable and when it actually runs.
Lab Tasks
1. How does Linux’s Completely Fair Scheduler (CFS) provide improved
fairness over a traditional UNIX process scheduler? When is the fairness
guaranteed?
2. What are the two configurable variables of the Completely Fair Scheduler
(CFS)? What are the pros and cons of setting each of them to very small
and very large values?
