FAQ Style Article

CFS and Periodic Scheduler (scheduler_tick())

In Linux Scheduler, Work In Progress on July 3, 2012 at 5:26 pm

This article explains scheduler_tick(), the periodic linux scheduler.

What is scheduler_tick()
It is function defined in sched.c which gets called by timer code with HZ frequency.
HZ is a preprocessor define, which can be set at compile time

What does it do?
Determine whether current task has to be scheduled out and new task has to be brought in

How does it do it?
If current task needs to be scheduled out, then TIF_NEED_RESCHED flag is set for it
Note that task itself will not be switched, just the flag is set
if flag is set, then task will be scheduled out when schedule() function is subsequently called.

What is schedule() function?
It implements the Main Scheduler. It is defined in kernel/sched.c
It is called from many points in the kernel to allocate the CPU to a process other than the currently active one
Usually called after returning from system calls, if TIF_NEED_RESCHED is set for current task

Which functions are called by scheduler_tick to do its job?
It mainly calls curr->sched_class->task_tick function.
If task is CFS task, then this will be task_tick_fair function.

What does task_tick_fair function do?
Nothing much, just ends up calling entity_tick() function, defined in sched_fair.c

What does entity_tick() do?
Does two main tasks
(a) Updates current task timing information by calling update_curr()
(b) If there are more than 1 tasks in current queue, calls check_preempt_tick() to check if current task has to be scheduled out.

What does check_preempt_tick() do?
First, it determines time slice for the current task
Second, it set resched flag on current task if either of two conditions are satisifed
(a) if current task has run beyond its time slice
(b) if current task vruntime exceeds next task vruntime by time slice, provided time run by current task is more than sysctl_sched_min_granularity

For both these operations, it uses many helper functions.

Which helper functions are used for determining time slice of current task?
sched_slice() provides time slice of current process.

How does sched_slice determine time slice?
It does using two steps
(a) Determines scheduler period, in which all runnable tasks should run at least once. It uses __sched_period helper function for this purpose.
(b) Determines share of current task in the scheduler period.
Shared is determined on the basis of ratio of current task weight to overall weight of CFS run queue.
In other words, share = scheduler period * (current_task.weight/cfs_rq.total.weight)

How does __sched_period find scheduler period?
if(number of runnable tasks(nr_running) < nr_latency)
period = sysctl_sched_latency;
period = sysctl_sched_min_granularity * nr_running;

Idea is to prevent period from going below sysctl_sched_min_granularity.

What helper function does check_preempt_tick() function use to set resched flag?
It uses resched_task() function, which is implemented in sched.c


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: