10

I'm trying to understand the Completely Fair Scheduler (CFS). According to Robert Love in Linux Kernel Development, 3rd edition(italics his, bold mine):

Rather than assign each process a timeslice, CFS calculates how long a process should run as a function of the total number of runnable processes. Instead of using the nice value to calculate a timeslice, CFS uses the nice value to weight the proportion of processor a process is to receive: Higher valued (lower priority) processes receive a fractional weight relative to the default nice value, whereas lower valued (higher priority) processes receive a larger weight.

Each process then runs for a “timeslice” proportional to its weight divided by the total weight of all runnable threads. To calculate the actual timeslice, CFS sets a target for its approximation of the “infinitely small” scheduling duration in perfect multitasking. This target is called the targeted latency....Let’s assume the targeted latency is 20 milliseconds and we have two runnable tasks at the same priority. Regardless of those task’s priority, each will run for 10 milliseconds before preempting in favor of the other. If we have four tasks at the same priority, each will run for 5 milliseconds. If there are 20 tasks, each will run for 1 millisecond....

Now, let’s again consider the case of two runnable processes, except with dissimilar nice values—say, one with the default nice value (zero) and one with a nice value of 5. These nice values have dissimilar weights and thus our two processes receive different proportions of the processor’s time. In this case, the weights work out to about a 1/3 penalty for the nice-5 process. If our target latency is again 20 milliseconds, our two processes will receive 15 milliseconds and 5 milliseconds each of processor time, respectively.

The first bolded sentence says that tasks have the same timeslice regardless of priority, while the second says that the timeslice depends on nice value. Which is correct, or what am I missing?

2
  • 3
    He says "two runnable tasks at same priority" directly before the first bold sentence, so I would think he wants to say it does not matter which nice value the processes have, as long as they are all the same, not that they don't matter in general. But I'm not familiar with the CFS, so I may be wrong.
    – crater2150
    Sep 21, 2014 at 19:40
  • 2
    As far as I understand first sentence references the case with processes of equal nice value. The second paragraph further goes into the topic with processes of different nice value. Jul 27, 2017 at 8:38

1 Answer 1

1

The 2 sentences are just explaining 2 instances of how CFS could work - the former is when 2 tasks have the same nice value and the latter when the 2 tasks have different nice values. In general, the time slice calculated for each task boils down to this formula:

timeslice = (weight/total_weight)*target_latency

weight is the weight of the current task which is dependent on the nice value assigned to the task.

total_weight is the sum of the weights of all tasks in the run queue.

target_latency is the time interval that CFS will attempt to once schedule all tasks in the run queue by.

Going back to the original formula, when 2 tasks have the same nice value, they will also have the same weight value. By treating weight as a constant, our new formula is:

timeslice = (target_latency/total_weight)

As you see, the time slice of each task in the run queue is no longer dependent on its weight value and thus each task will receive the same time slice. This is the first case the book mentions.

The second case mentions the nice values differ, and thus the weight values will differ. Each task will receive its time slice accordingly.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .