Shulou(Shulou.com)06/03 Report--

This series is called simple UNIX, but it also includes the details of various kinds of UNIX systems. This series of articles are sorted out from my study notes over the past few years, focusing on the analysis of the implementation ideas and insights of each UNIX, class UNIX.

This article is short and is just an analysis of one detail of the Linux CFS scheduler.

When a process is looking for the next process to be run, is it just the process in the lower left corner of the red-black tree? In fact, this is the simplest implementation, but considering optimization, it is not so simple. Consider the utilization of the CPU cache, that is, if a process A preempts process B, does pick next choose process B or the lower-left corner of the red-black tree in the context of process A? In addition, if process A has just been awakened in an attempt to preempt process B, but does not succeed, then the next is to choose the lower left corner of the red-black tree process or choose process A? Yes, these are all problems.

Let's look at the implementation of pick next:

Static struct sched_entity * pick_next_entity (struct cfs_rq * cfs_rq) {struct sched_entity * se = _ _ pick_next_entity (cfs_rq); struct sched_entity * left = se; if (cfs_rq- > next & & wakeup_preempt_entity (cfs_rq- > next, left)

Next; / * Prefer last buddy, try to return the CPU to a preempted task. * / if (cfs_rq- > last & & wakeup_preempt_entity (cfs_rq- > last, left)

Last; clear_buddies (cfs_rq, se); return se;}

Obviously, to compare the process in the lower left corner of the red-black tree with the other two processes, next and last, next is the process of preemption failure, while last is the process that is preempted after preemption success. Which of these three processes is the best next process? The decision conditions of Linux CFS implementation are:

1. Try to meet the need for newly awakened processes to preempt other processes

two。 Minimize the impact of cache flushing caused by the above preemption.

How does the Linux CFS implementation do that? Linux saves two variables, namely, the process that preemption fails and the process that is preempted after preemption success. When weighing, the priority is as follows:

The process of preemption after success > the process of preemption failure > the process in the lower left corner of the red-black tree

Whether you can choose the first two processes or not is determined by the wakeup_preempt_entity function. Too much code is useless. Just look at the following diagram:

The details of this CFS were not implemented when Linux 2.6.23 first implemented CFS. Therefore, from the most simple time, you can gradually understand the details of the context, it is good to see Changelog. I have to say, reading history is wise.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.