[SOLVED] How does the kernel scheduler maintain time quanta precision with timer interrupts?

Issue

From my reading there's a timer interrupt called by the hard ware that executes pretty often and transfers control back from a running process to the kernel/scheduler which is then able to determine if a running process has exceeded its time quanta and if so run another task.

This seems imprecise.

For example: If a timer interrupt was every 1 unit

And the scheduler algorithm determined a cpu bound process time quanta to be 1.5 units, it would actually get 2 units of CPU time.

Or does the scheduler only give time quanta's to processes in units of interrupt timers?

Solution

Linux's scheduler (CFS) allocates time slices to threads by first defining a time period in which every thread will run once. This time period is computed by the sched_slice() function and depends on the number of threads on the CPU, and 2 variables that can be set from user space (sysctl_sched_latency and sysctl_sched_min_granularity):

If the number of threads is greater than sysctl_sched_latency / sysctl_sched_min_granularity; then the period will be nr_threads * sysctl_sched_min_granularity; else the period will be sysctl_sched_latency.

For example, on my laptop, I have the following values:

    % cat /proc/sys/kernel/sched_latency_ns
    18000000
    % cat /proc/sys/kernel/sched_min_granularity_ns
    2250000

Therefore, sysctl_sched_latency / sysctl_sched_min_granularity = 8. Now, if I have less than 8 threads on a CPU, then each will be allocated 18.000.000 nanoseconds (ie. 18 milliseconds); else, each will be allocated 2.250.000 ns (2.25 ms).

Now, with those values in mind, if we look at the tick frequency (defined at compile time of the kernel) with this command:

    % zcat /proc/config.gz | grep CONFIG_HZ
    # CONFIG_HZ_PERIODIC is not set
    # CONFIG_HZ_100 is not set
    # CONFIG_HZ_250 is not set
    CONFIG_HZ_300=y
    # CONFIG_HZ_1000 is not set
    CONFIG_HZ=300

So, on my laptop, I have 300 ticks per second, which means a tick every 3 ms. Which means that in my case, with more than 8 threads on a CPU, I will loose a little bit of precision in my time slices (a thread that should run 2.25 ms will run 3 ms), but I could fix it by recompiling my kernel with more frequent ticks.

However, it should be noted that this is actually not a problem because, as indicated by its name, CFS (Completely Fair Scheduler) aims at being fair, which will be the case here.

Answered By - rgouicem