Time Accounting

All process schedulers must account for the time that a process runs.

In general Unix systems, each process is given a time slice which is decremented by each tick of the system clock. when the time slice reaches zero, the process is preempted in favor of another process with non-zero time slice.

Scheduler Entity Structure

CFS does not have the notion of a time slice. CFS uses the scheduler entity structure, struct sched_entity defined in <linux/sched.h>, to keep track of process accounting:

struct sched_entity {
  struct load_weight load;
  struct rb_node     run_node;
  struct list_head   group_node;
  unsigned int       on_rq;
  u64                exec_start;
  u64                sum_exec_runtime;
  u64                vruntime;
  u64                prev_sum_exec_runtime;
  u64                last_wakeup;
  u64                avg_overlap;
  u64                nr_migrations;
  u64                start_runtime;
  u64                avg_wakeup;

};

This sched_entity structure is within the process descriptor task_struct

The vruntime variable stores the virtual runtime of the process, which is the actual run time weighted by the number of runnable processes. CFS uses vruntime to account for how long a process has run, and how long more it should run.

The function update_curr() defined in kernel/sched_fair.c manages this accounting of vruntime

update_curr() is called periodically by the system timer, and also whenever a process becomes runnnable or unrunnable.