OPERATING SYSTEMS

(CS C372)

LECTURE : CPU SCHEDULING

Linux Scheduling
 Linux 2.4 scheduler - goals
 Linux 2.4 scheduler provided soft real-time scheduling
capability coupled with a scheduler for non-real-time
processes

 Good interactive performance even during high load

 If the user types or clicks then the system must react

instantly and must execute the user tasks smoothly,

even during considerable background load.

 Fairness
 No process should stay without any timeslice for any
unreasonable amount of time.
 No process should get an unjustly high amount of
CPU time.
23 October 2024 3
 Linux 2.4 scheduler - goals
 Supports SMP: single runqueue, individual
scheduler
 SMP efficiency
 No CPU should stay idle if there is work to do.
 SMP affinity
 Processes which run on one CPU should stay
affine to that CPU.
 Processes should not bounce between CPUs too
frequently.

23 October 2024 4
The three Linux 2.4 scheduling classes
 RT process is scheduled according to one of
the following classes
 SCHED_FIFO: First-in-first-out real-time threads
 SCHED_RR: Round-robin real-time threads
 Non RT process (Conventional time shared process)
 SCHED_OTHER: Other, non-real-time threads

 Within each class, multiple priorities may be used, with

priorities in the real-time classes higher than the
priorities for the SCHED_OTHER class.

23 October 2024 5
SCHED_FIFO scheduling class
For FIFO threads, the following rules apply:
1. The system will not interrupt an executing FIFO thread
except in the following cases:
a. Another FIFO thread of higher priority becomes ready.
b. The executing FIFO thread is blocked for an I/O.
c. The executing FIFO thread voluntarily gives up the
processor.
2. When an executing FIFO thread is interrupted, it is placed
in the queue associated with its priority.
3. If more than one thread has that highest priority, the
thread that has been waiting the longest is chosen.

23 October 2024 6
SCHED_RR scheduling class

 The SCHED_RR policy is similar to the

SCHED_FIFO policy, except for the addition of a
timeslice associated with each thread.

 When a SCHED_RR thread has executed for its

timeslice, it is suspended and a real-time thread
of equal or higher priority is selected for running.

23 October 2024 7
Real time scheduling example in Linux
2.4

23 October 2024 8
Drawbacks of Linux 2.4 scheduler :
 Scheduler for the SCHED_OTHER class did
not scale well with increasing number of
processors and increasing number of
processes.

 The scheduler uses a single runqueue for all

processors in a symmetric multiprocessing
system (SMP) (good for load balancing but
bad for memory caches)

 Uses a single runqueue lock.

 Preemption is not possible.

23 October 2024 9
Linux Scheduling
O(1) scheduler
Evolution of Linux schedulers
Linux 2.4 scheduler Linux 2.6 O(1) scheduler
SMP with Single run queue, lacks SMP with individual run queue
scalability
Single run queue Two queues (active and expiry)
Selection takes O(N) time as it iterates Selection take constant time (O(1)) as
over every process from priority queue, dequeue the next
from active runqueue
Inefficient and weak for real time Much more efficient and much more
system scalable.
Priority of the process is fixed (Static Priority changes as per cpu usage.
priority) Static and dynamic priority.
Incorporated interactivity metrics with
numerous heuristics to determine
whether the process was I/O bound or
processor bound

23 October 2024 11
O(1) scheduler in Linux 2.6
 To correct these problems, Linux 2.6 uses
the O(1) scheduler.
 The scheduler is designed so that the time to
select the appropriate process and assign it
to a processor is constant,
 regardless of the load on the system or the
number of processors.

23 October 2024 12
O(1) scheduler in Linux 2.6
 Preemptive priority based round robin
scheduler
 Two separate priority ranges:
 Real time range : 0 to 99
 Nice value range: 100 to 139

 These two ranges map into global priority

scheme.
 Higher priority task : larger time quanta
 Lower priority task : smaller time quanta
23 October 2024 13
The Relationship Between
Priorities and Time-slice length

139

23 October 2024 14
Data structure
 The kernel maintains two scheduling data structure for
each processor in the system, of the following form

struct prio_array {
int nr_active; /* number of tasks in this array*/
unsigned long bitmap[BITMAP_SIZE]; /* priority bitmap */
struct list_head queue[MAX_PRIO]; /* priority queues */

 Two such structures are maintained:

 an active queues structure and

 an expired queues structure.

 A separate queue is maintained for each priority level.

23 October 2024 15
 List of Tasks Indexed According to
Prorities

[139 ] [139 ]

23 October 2024 16
23 October 2024 17
 O(1) scheduling algorithm in Linux 2.6
 Initially, both bitmaps are set to all zeroes and all queues
are empty.
 As a process becomes ready, it is assigned to the
appropriate priority queue in the active queues structure and
is assigned the appropriate timeslice.
 Possibilities:
 If the running process is preempted before its timeslice, it is returned
to an active queue.

 When a task completes its timeslice, it goes into the appropriate

queue in the expired queues structure and is assigned a new
timeslice.

 If the running process goes for I/O , priority (dynamic) is recomputed

and the process is added to the appropriate active queue.

23 October 2024 18
O(1) scheduling algorithm in Linux 2.6
contd..
 All scheduling is done from among tasks in the active
queues structure.
 When the active queues structure is empty, a simple
pointer assignment results in a switch of the active and
expired queues, and scheduling continues.
 On a given processor, the scheduler picks the highest-
priority nonempty queue. If multiple tasks are in that
queue, the tasks are scheduled in round-robin fashion.

23 October 2024 19
Calculating Priority of a process
 Each non-real-time task is assigned an initial priority in the range of
100 to 139, with a default of 120.This is the task’s static priority
and is specified by the user.

 As the task executes, a dynamic priority is calculated as a function

of the task’s static priority and its execution behavior.

 The Linux scheduler is designed to favor I/O-bound tasks over

processor-bound tasks. This preference tends to provide good
interactive response.

 The technique used by Linux to determine the dynamic priority is to

keep a running tab on how much time a process sleeps (waiting for
an event) versus how much time the process runs.

 In essence, a task that spends most of its time sleeping is given a

higher priority.

23 October 2024 20
Calculating Static Priority of a process
from Nice value
 nice() or setpriority() system calls
 Changes the static priority of the process

 /*Convert user-nice values [ -20 ... 0 ... 19 ] to

static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
and back */

 #define NICE_TO_PRIO(nice)
(MAX_RT_PRIO + (nice) + 20)

 #define PRIO_TO_NICE(prio)
((prio) - MAX_RT_PRIO - 20)
23 October 2024 21
Calculating Time slice of a process
 Time slices are assigned in the range of 10 ms to
200 ms.
 In general, higher priority tasks are assigned
larger time slices.
 A new process will always inherit the static priority
of its parent.
 User can change the static priority of the process
by nice() or setpriority() system calls

23 October 2024 22
Calculating Time slice from static priority
 Static priority determines the base time quantum of
a process
 Base time quantum (in milliseconds)
 (140 – static priority) X 20 if static priority <120
 (140 – static priority) X 5 if static priority >=120
 The higher the static priority (lower value), the longer the
base time quantum
 Example
Description static priority base time quantum
Highest static priority 100 800ms
Default static priority 120 100ms
Lowest static priority 139 5ms
23 October 2024 23
Dynamic priority
 In Linux, process priority is dynamic.
 The scheduler keeps track of what processes
are doing and adjusts their priorities periodically.
 DP is recalculated when q expires and process
is moved to expired array, also when process
sleeps
 In this way, processes that have been denied
the use of the CPU for a long time interval are
boosted by dynamically increasing their priority.
 Correspondingly, processes running for a long
time are penalized by decreasing their priority.
23 October 2024 24
 Average Sleep Time Bonus Granularity

Greater than or equal to 0 but smaller than 100ms 0 5120

Greater than or equal to 100ms but smaller than 200ms 1 2560

Greater than or equal to 200ms but smaller than 300ms 2 1280

Greater than or equal to 300ms but smaller than 400ms 3 640

Greater than or equal to 400ms but smaller than 500ms 4 320

Greater than or equal to 500ms but smaller than 600ms 5 160

Greater than or equal to 600ms but smaller than 700ms 6 80

Greater than or equal to 700ms but smaller than 800ms 7 40

Greater than or equal to 800ms but smaller than 900ms 8 20

Greater than or equal to 900ms but smaller than 1000ms 9 10

1 second 10 10

23 October 2024 25
 Calculating Dynamic Priority based on avg sleep time
 Dynamic priority value ranges from 100 (highest
priority) to 139 (lowest priority)
 Dynamic priority is the one scheduler looks at when
selecting a new process to run
 Dynamic priority =
max (100, min(static priority – bonus + 5, 139))
 Bonus is ranging from 0 to 10
 Less than 5 (is a penalty that) lowers dynamic priority
 Greater than 5 raises dynamic priority
 Value of bonus depends on the past history of the
process (related to average sleep time of the process)
 Average sleep time reduces when process is running
 Average sleep can never become larger than 1 second
 Average sleep time increases when process is in I/O

23 October 2024 26
Relationship to Real-Time Tasks
The following considerations apply:
1. All real-time tasks have only a static priority;
no dynamic priority changes are made.
2. SCHED_FIFO tasks do not have assigned timeslices.
Such tasks are scheduled in FIFO discipline.
If a SCHED_FIFO task is blocked, it returns to the same priority
queue in the active queue list when it becomes unblocked.
3. Although SCHED_RR tasks do have assigned timeslices, they
also are never moved to the expired queue list.
 When a SCHED_RR task exhaust its timeslice, it is returned to its
priority queue with the same timeslice value.
 Timeslice values are never changed.
 The effect of these rules is that the switch between the active queue
list and the expired queue list only happens when there are no ready
real-time tasks waiting to execute.
23 October 2024 27
 A real time process is replaced by another only
when one of the following events occur
 Process is preempted by a higher real time priority
process
 Process performs blocking operation (TASK_
INTERRUPTABLE or TASK_UNINTERRUPTABLE)
 Process is stopped (TASK_STOPPED or
TASK_TRACED)
 Process is killed (EXIT_ZOMBIE or EXIT_DEAD)
 Process voluntarily relinquishes the CPU by invoking
sched_yield() system call
 The process is Round Robin real time (SCHED_RR)
and it has exhausted its time quantum

23 October 2024 28
 System Calls Related to Scheduling
 nice( ) Change the priority of a conventional process.
 getpriority( ) Get the maximum priority of a group of conventional processes.
 setpriority( ) 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.

23 October 2024 29
Exercise
Process Nice Execution Sleep Real Time Sched policy
Time(ms) time(ms) Priority
A 8 50 0 - SCHED_OTHER
B -15 800 0 - SCHED_OTHER
C -5 600 - 30 SCHED_RR
D 0 100 - 30 SCHED_FCFS

 A Linux OS supporting O(1) Scheduler has this snapshot at time t. Assume that the
order of arrival of processes to the system is Process A to Process D. Process
A and B are Conventional processes and Process C and D are Real Time
Processes.
 Find Static Priority for all the processes.
 Find Quantum time for all the processes.
 Find Dynamic priority for all Conventional processes.
 Find the resultant schedule and represent it as Gantt chart

23 October 2024 30