Transcript Linux scheduling (PPT slides)

Operating Systems, fall 2002
SCHEDULING
in Linux
Lior Amar,
David Breitgand
(recitation)
www.cs.huji.ac.il/~os
Scheduling in Unix
• The scheduling algorithm must fulfill several
conflicting objectives:
–
–
–
–
fast process response time;
good throughput for background jobs;
avoidance of process starvation;
Preferential treatment of low- and high-priority
processes.
• The set of rules used to determine when and how
selecting a new process to run is called scheduling
policy.
Linux
• Unix clone for PC by Tornvald Linus;
– Originally for x386 family;
• Scheduling is based on the time-sharing:
– Several processes are allowed to run "concurrently“;
– Which means that the CPU time is roughly divided into
"slices“, one for each runnable process;
– If a currently running process is not terminated when its time
slice (quantum) expires, a process switch may take place;
– Time-sharing relies on timer interrupts and is transparent to
processes;
– No additional code needs to be inserted in the programs in
order to ensure CPU time-sharing.
– CPU sharing policies can be controlled to a certain extent.
Process Classification
I/O-bound:
• make heavy use of I/O devices and spend much time
waiting for I/O operations to complete.
CPU-bound:
• number-crunching applications that require a lot of CPU
time.
Alternative Process Classification
Interactive processes:
• interact constantly with their users;
• spend a lot of time waiting for key presses
and mouse operations;
• when input is received, the process must be
woken up quickly, or the user will find the
system to be unresponsive;
• typically, the average delay must fall
between 50 and 150 ms.
• the variance of such delay must also be
bounded, or the user will find the system to be
erratic;
Alternative Process Classification
Batch processes:
• Do not need user interaction;
• Often run in the background;
• Do not need to be very responsive;
• Typical batch programs data-mining engines, file
transfers, compilers
Real-time processes:
• Have very strong scheduling requirements;
• Should have a short response time and a minimum variance;
• Often require a guaranteed sequence of execution;
• Often require a guaranteed timing (deadlines).
Real Time Processes
• Hard real time processes:
– Nuclear power plant control;
– Airplane control.
• Soft real time processes:
– Video/audio streaming;
– On-line gaming/conferencing.
Classifications are largely
independent
• Batch programs may be I/O bound and CPU
bound
• Real Time programs maybe I/O bound and
CPU bound.
• Can interactive programs be CPU bound?
…and in Linux
• Soft real-time processes are explicitly recognized:
– There are two types of user processes in Linux: real
time, and conventional.
• No way explicitly to distinguish among
conventional batch and interactive processes:
– Linux (as all UNIXs) prefers I/O processes
– Is this always OK?
Linux Scheduling Policy
• Based on priorities;
• Priority is a measure of worthiness of choosing a
certain process to run among the processes being ready
to run;
• In Linux there are two types of priorities:
– Static :
• stay fixed throughout the process life
• for soft real time processes
– Dynamic :
• for conventional processes (adjusted by the scheduler based on
process history)
Why not Hard Real Time?
• Two reasons:
– Linux kernel is non-preemptive (as in classic
Unix),
• you will appreciate why in this week lecture.
– Linux user-level process is preemptive.
Preempted vs Suspended
• Preempted process is logically in the
READY state, it just does not use CPU
• Suspended process waits for some event
completion (e.g., I/O completion, timer
event, other event – can you give an
example?), thus it is not runnable.
Quantum
• Time sharing is possible since each process
occupies CPU for a finite time slice aka quantum;
• How long should it be?
– If too long - FCFS
– If too short – switching overhead is too high
– Question: if switching takes up 10 ms, and quantum is
10 ms, what is switching overhead?
• Statement: long quantum always degrades
response time of interactive applications.
– Is this false or true?
Quantum (II)
• The statement from the previous slide is FALSE in
general;
• In particular, this is not true in Linux;
• This actually depends on whether the scheduler gives
higher priority to the I/O bound process (interactive
programs are always I/O bound);
• In Linux previously suspended I/O process will very
quickly preempt currently running CPU-bound process
upon wakeup when SUSPENDED ->READY state
transition takes place
Quantum (III)
• However, in some cases when quantum is too long
responsiveness may be degraded
• Example:
– Two commands are invoked simultaneously by two users.
One is CPU bound, another one is interactive
– Shells of users fork two process. If initially these two have the
same dynamic priority, and the CPU bound is selected first,
then the I/O bound suffers.
The rule of thumb adopted by Linux is:
choose quantum duration as long as possible, while keeping good
system response time.
The actual value is 210 ms.
Linux Scheduling Algorithm
• Linux uses a variant of multilevel queue with feedback;
• CPU time is divided into epochs;
– In a single epoch, every process has a specified quantum
whose duration is computed when the epoch begins;
• Different processes may have different quanta;
• Quantum value is the maximum CPU time portion assigned to the
process in that epoch;
• Process is preempted when:
– it finishes up its quantum;
– a previously suspended process with higher priority is awaken;
– process voluntarily relinquish CPU either by calling a
blocking system call, or by calling sched_yeild() syscall;
– process voluntarily decreases/increases its priority through
calling setpriority()
– Real time process is ready to run.
Linux Scheduling Algorithm
(continued)
• Priority of a conventional process in Linux equals
unused time from the process’s quantum;
– The more time left, the higher priority;
• Static priorities: 1-99 are never changed by the scheduler
• Different priority queues can be handled through two
policies: FCFS and RR.
• An epoch terminates when all runnable processes
exhaust their quantum.
• When a new epoch begin each runnable process is
assigned a new quantum:
base priority + time left from the last epoch
More on priorities (I)
• When a process forks a child process the priority for the
child is set as follows:
current->counter >>= 1; //counter counts ticks left
p->counter = current->counter;
• What is the effect of this? Why this is needed?
• In PC one clock tick usually happens every 0.01
sec.
• Base quantum (=base priority) is 20 ticks (defined
in /usr/include/sched.h)
More on Priorities (II)
• When a new epoch begins every process
(i.e., also the suspended ones) obtain new
priorities:
p->priority += p->counter >> 1;
• Thus suspended processes (I/O bound)
increase their priority;
• What is the maximum priority a process may
get ever?
• Why is it good to recalculate all priorities
once per epoch, and not all the time?
Let’s check ourselves
• What type of processes will be favored by
Linux scheduler?
• Can starvation occur if only conventional
processes execute?
• Can starvation occur if both real time and
conventional processes execute?
• Can starvation occur if only real time
processes execute?
• Why relatively long quantum does not hurt
interactive processes in Linux?
• Can a single epoch be infinite?
System Call Description
nice( )
getpriority( )
setpriority( )
Change the priority of a conventional process.
Get the maximum priority of a group of conventional
processes.
Set the priority of a group of conventional processes.
sched_getscheduler( )
Get the scheduling policy of a process.
sched_setscheduler( )
Set the scheduling policy and priority of a process.
sched_getparam( )
Get the scheduling priority of a process.
sched_setparam( )
Set the priority of a process.
sched_yield( )
Relinquish the processor voluntarily without blocking.
sched_get_ priority_min( )
Get the minimum priority value for a policy.
sched_get_ priority_max( )
Get the maximum priority value for a policy.
sched_rr_get_interval( )
Get the time quantum value for the Round Robin policy.