Whenever two processes with the same absolute priority are ready to run,
the kernel has a decision to make, because only one can run at a time.
If the processes have absolute priority 0, the kernel makes this decision
as described in Traditional Scheduling. Otherwise, the decision
is as described in this section.
If two processes are ready to run but have different absolute priorities,
the decision is much simpler, and is described in Absolute Priority.
Each process has a scheduling policy. For processes with absolute
priority other than zero, there are two available:
First Come First Served
The most sensible case is where all the processes with a certain
absolute priority have the same scheduling policy. We'll discuss that
In Round Robin, processes share the CPU, each one running for a small
quantum of time (“time slice”) and then yielding to another in a
circular fashion. Of course, only processes that are ready to run and
have the same absolute priority are in this circle.
In First Come First Served, the process that has been waiting the
longest to run gets the CPU, and it keeps it until it voluntarily
relinquishes the CPU, runs out of things to do (blocks), or gets
preempted by a higher priority process.
First Come First Served, along with maximal absolute priority and
careful control of interrupts and page faults, is the one to use when a
process absolutely, positively has to run at full CPU speed or not at
Judicious use of sched_yield function invocations by processes
with First Come First Served scheduling policy forms a good compromise
between Round Robin and First Come First Served.
To understand how scheduling works when processes of different scheduling
policies occupy the same absolute priority, you have to know the nitty
gritty details of how processes enter and exit the ready to run list:
In both cases, the ready to run list is organized as a true queue, where
a process gets pushed onto the tail when it becomes ready to run and is
popped off the head when the scheduler decides to run it. Note that
ready to run and running are two mutually exclusive states. When the
scheduler runs a process, that process is no longer ready to run and no
longer in the ready to run list. When the process stops running, it
may go back to being ready to run again.
The only difference between a process that is assigned the Round Robin
scheduling policy and a process that is assigned First Come First Serve
is that in the former case, the process is automatically booted off the
CPU after a certain amount of time. When that happens, the process goes
back to being ready to run, which means it enters the queue at the tail.
The time quantum we're talking about is small. Really small. This is
not your father's timesharing. For example, with the Linux kernel, the
round robin time slice is a thousand times shorter than its typical
time slice for traditional scheduling.
A process begins life with the same scheduling policy as its parent process.
Functions described in Basic Scheduling Functions can change it.
Only a privileged process can set the scheduling policy of a process
that has absolute priority higher than 0.
Published under the terms of the GNU General Public License