OPERATING SYSTEMS CS F372
BIJU K RAVEENDRAN & TEAM
LECT #24: CPU SCHEDULING
Completely Fair Scheduler
• Introduced in Linux kernel 2.6.23
• Aim
– Maximize overall CPU utilization and interactive performance
• Uses Red-black tree data structure [using the spent processor time
as a key] instead of run queues
– Picks the process that has used the least amount of time
– If a task spends a lot of its time sleeping, the spent time value
will be low
– Order of complexity is log(N) where N is the number of nodes
in read-black tree
Monday, February 24, 2025 Biju K Raveendran @ BITS Pilani Goa 2
• Source files
– sched.c, sched.h and sched_fair.c
• Uses nanosecond granularity accounting, the atomic
units by which an individual process' share of the CPU
was allocated: minimum 1msec
• Processes given a fair amount of the processor
• CFS maintains virtual runtime - time provided to a
given task
• smaller a task's virtual runtime, smaller the amount of
time the task has been permitted access to the
processor – higher need for processor
Monday, February 24, 2025 Biju K Raveendran @ BITS Pilani Goa 3
Completely Fair Scheduler
• CFS maintains a time-ordered red-black tree – not run queues like
previous kernel versions
• Tree Properties:
– Self Balancing - no path in the tree will ever be more than
twice as long as any other
– Operations on the tree occur in O(log n) time – quick insertion,
deletion
• Tasks with the lowest virtual runtimes stored toward the left side
of the tree, tasks with highest virtual runtimes stored toward the
right
• Scheduler picks left-most node of the red-black tree to schedule
next – O(1)
Monday, February 24, 2025 Biju K Raveendran @ BITS Pilani Goa 4
Completely Fair Scheduler
• Task accounts for its time with the CPU - adds execution time to
virtual runtime and is then inserted back into the tree if runnable
Monday, February 24, 2025 Biju K Raveendran @ BITS Pilani Goa 5
Completely Fair Scheduler
• CFS needs to have the following:
– A mechanism to calculate what the fair CPU share is
per process.
• A clock per task, virtual run time is used for the same
• Approximated average is used to initialize the clock for the
new tasks
• Group scheduling to decide virtual run time
– A mechanism to keep track of the time for which
each process was waiting while the CPU was
assigned to the currently running task
Monday, February 24, 2025 Biju K Raveendran @ BITS Pilani Goa 6
Time Slice Calculation
timeslice = scheduling period * (task's
weight/total weight of tasks in the run queue)
– The task's weight depends on the task's nice level
and the scheduling policy. Minimum task weight for
a SCHED_OTHER task is 15, corresponding to nice 19.
The maximum task weight is 88761, corresponding
to nice -20
– Time slices become smaller as the load increases.
Monday, February 24, 2025 Biju K Raveendran @ BITS Pilani Goa 7
CFS – Process Selection, Process Add
• Selection Process
– Pick process with smallest vruntime (leftmost leaf)
– Red-black tree (rbtree) - self balancing BST
– __pick_next_task()
• Cached value of leftmost leaf (rb_leftmost)
• Add process
– Enqueue_entity function
– Update stats
– __enqueue_entity function
– Insert in correct place
– Update colors with balancing
Monday, February 24, 2025 Biju K Raveendran @ BITS Pilani Goa 8
CFS – Process Remove
• Remove process (when process blocks or
terminates)
– Dequeue_entity()
• Update stats
– __dequeue_entity()
• Rbtree implementation provides rb_erase()
• Rest of the function updates rb_leftmost
Monday, February 24, 2025 Biju K Raveendran @ BITS Pilani Goa 9
Real-time CPU Scheduling
• Soft real-time systems – Critical real-time tasks have the highest
priority, but no guarantee as to when tasks will be scheduled
• Hard real-time systems – task must be serviced by its deadline
• Event latency – the amount of time that
elapses from when an event occurs to
when it is serviced.
• Two types of latencies affect performance
1. Interrupt latency – time from arrival
of interrupt to start of routine that
services interrupt
2. Dispatch latency – time for schedule
to take current process off CPU and
switch to another
Monday, February 24, 2025 Biju K Raveendran @ BITS Pilani Goa 10
Priority based Scheduling
• Tasks
– Hard RT and Soft RT
– Periodic, Aperiodic, Sporadic
• Schedulers
– Rate Monotonic / Deadline Monotonic
– Earliest Deadline First
– Least Laxity First
Monday, February 24, 2025 Biju K Raveendran @ BITS Pilani Goa 11
• T1 = (4,1), T2 = (5,2), T3 = (20,5)
• T1(2,0.8), T2(5, 1.5), T3(5.1,1.5)
Monday, February 24, 2025 Biju K Raveendran @ BITS Pilani Goa 12
