Linux进程调度CFS算法实现分析

Myth丶恋晨 2022-06-18 03:52 273阅读 0赞

网上讲CFS的文章很多，可能版本不一，理解不尽相同。我以问题追溯方式，跟踪源码写下我对CFS的理解，有的问题我也还没理解透，欢迎对内核有兴趣的朋友一起交流学习，源码版本是与LKD3配套的Linux2.6.34

背景知识：

(1) Linux的调度器类主要实现两类进程调度算法：实时调度算法和完全公平调度算法(CFS)，实时调度算法SCHED\_FIFO和SCHED\_RR，按优先级执行，一般不会被抢占。直到实时进程执行完，才会执行普通进程。而大多数的普通进程，用的就是CFS算法。

(2) 进程调度的时机：

①进程状态转换时刻：进程终止、进程睡眠；

②当前进程的”时间片”用完；

③主动让出处理器，用户调用sleep()或者内核调用schedule()；

④从中断，系统调用或异常返回时；

(3) 每个进程task\_struct中都有一个struct sched\_entity se成员，这就是调度器的实体结构，进程调度算法实际上就是管理所有进程的这个se。

点击(此处)折叠或打开

1.  struct task\_struct \{   
    
2.      volatile long state;    /\* \-1 unrunnable, 0 runnable, >0 stopped \*/  
    
3.      void \*stack;  
    
4.      atomic\_t usage;  
    
5.      unsigned int flags;    /\* per process flags, defined below \*/  
    
6.      unsigned int ptrace;  
    
7.    
    
8.      int lock\_depth;        /\* BKL lock depth \*/  
    
9.    
    
10. \#ifdef CONFIG\_SMP  
    
11. \#ifdef \_\_ARCH\_WANT\_UNLOCKED\_CTXSW  
    
12.     int oncpu;  
    
13. \#endif  
    
14. \#endif  
    
15.   
    
16.     int prio, static\_prio, normal\_prio;  
    
17.     unsigned int rt\_priority;  
    
18.     const struct sched\_class \*sched\_class;  
    
19.     struct sched\_entity se; //进程调度实体
20.     struct sched\_rt\_entity rt;  
    
21.     …  
    
22. \}

CFS基于一个简单的理念：所有任务都应该公平的分配处理器。理想情况下，n个进程的调度系统中，每个进程获得1/n处理器时间，所有进程的vruntime也是相同的。

CFS完全抛弃了时间片的概念，而是分配一个处理器使用比来度量。

每个进程一个调度周期内分配的时间(类似于传统的“时间片”)跟三个因素有关：进程总数，优先级，调度周期  
  
其他进程调度详细基础知识参见上篇博文：[http://blog.chinaunix.net/uid-24708340-id-3778555.html][http_blog.chinaunix.net_uid-24708340-id-3778555.html]

1.理解CFS的首先要理解vruntime的含义

简单说vruntime就是该进程的运行时间，但这个时间是通过优先级和系统负载等加权过的时间，而非物理时钟时间，按字面理解为虚拟运行时间，也很恰当。

每个进程的调度实体se都保存着本进程的虚拟运行时间。

点击(此处)折叠或打开

1.  struct sched\_entity \{   
    
2.      struct load\_weight    load;        /\* for load\-balancing \*/  
    
3.      struct rb\_node        run\_node;  
    
4.      struct list\_head    group\_node;  
    
5.      unsigned int        on\_rq;  
    
6.    
    
7.      u64            exec\_start;  
    
8.      u64            sum\_exec\_runtime;  
    
9.      u64            vruntime; //虚拟运行时间  
    
10.     u64            prev\_sum\_exec\_runtime;  
    
11. …  
    
12. \}

而进程相关的调度方法如下

点击(此处)折叠或打开

1.  static const struct sched\_class fair\_sched\_class = \{   
    
2.      .next            = &idle\_sched\_class,  
    
3.      .enqueue\_task        = enqueue\_task\_fair,  
    
4.      .dequeue\_task        = dequeue\_task\_fair,  
    
5.      .yield\_task        = yield\_task\_fair,  
    
6.    
    
7.      .check\_preempt\_curr    = check\_preempt\_wakeup,  
    
8.    
    
9.      .pick\_next\_task        = pick\_next\_task\_fair,  
    
10.     .put\_prev\_task        = put\_prev\_task\_fair,  
    
11.   
    
12. \#ifdef CONFIG\_SMP  
    
13.     .select\_task\_rq        = select\_task\_rq\_fair,  
    
14.   
    
15.     .rq\_online        = rq\_online\_fair,  
    
16.     .rq\_offline        = rq\_offline\_fair,  
    
17.   
    
18.     .task\_waking        = task\_waking\_fair,  
    
19. \#endif  
    
20.   
    
21.     .set\_curr\_task = set\_curr\_task\_fair,  
    
22.     .task\_tick        = task\_tick\_fair,  
    
23.     .task\_fork        = task\_fork\_fair,  
    
24.   
    
25.     .prio\_changed        = prio\_changed\_fair,  
    
26.     .switched\_to        = switched\_to\_fair,  
    
27.   
    
28.     .get\_rr\_interval    = get\_rr\_interval\_fair,  
    
29.   
    
30. \#ifdef CONFIG\_FAIR\_GROUP\_SCHED  
    
31.     .task\_move\_group    = task\_move\_group\_fair,  
    
32. \#endif  
    
33. \};

2.vruntime的值如何跟新？

时钟中断产生时，会依次调用tick\_periodic()-> update\_process\_times()->scheduler\_tick()

点击(此处)折叠或打开

1.  void scheduler\_tick(void)  
    
2.  \{   
    
3.  …  
    
4.      raw\_spin\_lock(&rq\->lock);  
    
5.      update\_rq\_clock(rq);  
    
6.      update\_cpu\_load(rq);  
    
7.      curr\->sched\_class\->task\_tick(rq, curr, 0); //执行调度器tick，更新进程vruntime  
    
8.      raw\_spin\_unlock(&rq\->lock);  
    
9.  …  
    
10. \}  
    
11. task\_tick\_fair ()调用entity\_tick()如下：  
    
12. static void entity\_tick(struct cfs\_rq \*cfs\_rq, struct sched\_entity \*curr, int queued)  
    
13. \{   
    
14.     update\_curr(cfs\_rq);  
    
15. …  
    
16.     if (cfs\_rq\->nr\_running > 1 || !sched\_feat(WAKEUP\_PREEMPT))  
    
17.         check\_preempt\_tick(cfs\_rq, curr); //检查当前进程是否需要调度  
    
18. \}

这里分析两个重要函数update\_curr()和check\_preempt\_tick()

点击(此处)折叠或打开

1.  static void update\_curr(struct cfs\_rq \*cfs\_rq)  
    
2.  \{   
    
3.      struct sched\_entity \*curr = cfs\_rq\->curr;  
    
4.      u64 now = rq\_of(cfs\_rq)\->clock;  
    
5.      unsigned long delta\_exec;  
    
6.    
    
7.      if (unlikely(!curr))  
    
8.          return;  
    
9.    
    
10. // delta\_exec获得最后一次修改后，当前进程所运行的实际时间  
    
11.     delta\_exec = (unsigned long)(now \- curr\->exec\_start);  
    
12.     if (!delta\_exec)  
    
13.         return;  
    
14.   
    
15.     \_\_update\_curr(cfs\_rq, curr, delta\_exec);  
    
16.     curr\->exec\_start = now; //运行时间已保存，更新起始执行时间  
    
17.   
    
18.     if (entity\_is\_task(curr)) \{   
    
19.         struct task\_struct \*curtask = task\_of(curr);  
    
20.   
    
21.         trace\_sched\_stat\_runtime(curtask, delta\_exec, curr\->vruntime);  
    
22.         cpuacct\_charge(curtask, delta\_exec);  
    
23.         account\_group\_exec\_runtime(curtask, delta\_exec);  
    
24.     \}  
    
25. \}

主要关心\_\_update\_curr()函数

点击(此处)折叠或打开

1.  static inline void \_\_update\_curr(struct cfs\_rq \*cfs\_rq, struct sched\_entity \*curr, unsigned long delta\_exec)  
    
2.  \{   
    
3.      unsigned long delta\_exec\_weighted;  
    
4.    
    
5.      schedstat\_set(curr\->exec\_max, max((u64)delta\_exec, curr\->exec\_max));  
    
6.    
    
7.      curr\->sum\_exec\_runtime \+= delta\_exec;//累计实际运行时间  
    
8.      schedstat\_add(cfs\_rq, exec\_clock, delta\_exec);  
    
9.      delta\_exec\_weighted = calc\_delta\_fair(delta\_exec, curr);//对delta\_exec加权  
    
10.   
    
11.     curr\->vruntime \+= delta\_exec\_weighted;//累计入vruntime  
    
12.     update\_min\_vruntime(cfs\_rq); //更新cfs\_rq最小vruntime(保存所有进程中的最小vruntime)  
    
13. \}

关注calc\_delta\_fair()加权函数如何实现

点击(此处)折叠或打开

1.  /\*  
    
2.   \* delta /= w  
    
3.   \*/  
    
4.  static inline unsigned long  
    
5.  calc\_delta\_fair(unsigned long delta, struct sched\_entity \*se)  
    
6.  \{   
    
7.      if (unlikely(se\->load.weight != NICE\_0\_LOAD))  
    
8.          delta = calc\_delta\_mine(delta, NICE\_0\_LOAD, &se\->load);  
    
9.    
    
10.     return delta;  
    
11. \}

若当前进程nice为0，直接返回实际运行时间，其他所有nice值的加权都是以0nice值为参考增加或减少的。

点击(此处)折叠或打开

1.  /\*  
    
2.   \* delta \*= weight / lw  
    
3.   \*/  
    
4.  static unsigned long  
    
5.  calc\_delta\_mine(unsigned long delta\_exec, unsigned long weight,  
    
6.          struct load\_weight \*lw)  
    
7.  \{   
    
8.      u64 tmp;  
    
9.    
    
10.     if (!lw\->inv\_weight) \{   
    
11.         if (BITS\_PER\_LONG > 32 && unlikely(lw\->weight >= WMULT\_CONST))  
    
12.             lw\->inv\_weight = 1;  
    
13.         else  
    
14.             lw\->inv\_weight = 1 \+ (WMULT\_CONST\-lw\->weight/2)  
    
15.                 / (lw\->weight\+1);//这公式没弄明白  
    
16.     \}  
    
17.   
    
18.     tmp = (u64)delta\_exec \* weight;  
    
19.     /\*  
    
20.      \* Check whether we'd overflow the 64\-bit multiplication:  
    
21.      \*/  
    
22.     if (unlikely(tmp > WMULT\_CONST))  
    
23.         tmp = SRR(SRR(tmp, WMULT\_SHIFT/2) \* lw\->inv\_weight,  
    
24.             WMULT\_SHIFT/2);  
    
25.     else  
    
26.         tmp = SRR(tmp \* lw\->inv\_weight, WMULT\_SHIFT);//做四舍五入  
    
27.   
    
28.     return (unsigned long)min(tmp, (u64)(unsigned long)LONG\_MAX);  
    
29. \}

当nice!=0时，实际是按公式delta \*= weight / lw来计算的weight=1024是nice0的权重，lw是当前进程的权重，该lw和nice值的换算后面介绍，上面还书的lw计算公式没弄明白，总之这个函数就是把实际运行时间加权为进程调度里的虚拟运行时间，从而更新vruntime。  
  
更新完vruntime之后，会检查是否需要进程调度

点击(此处)折叠或打开

1.  回到static void entity\_tick(struct cfs\_rq \*cfs\_rq, struct sched\_entity \*curr, int queued)  
    
2.  \{   
    
3.      update\_curr(cfs\_rq);  
    
4.  …  
    
5.      if (cfs\_rq\->nr\_running > 1 || !sched\_feat(WAKEUP\_PREEMPT))  
    
6.          check\_preempt\_tick(cfs\_rq, curr); //检查当前进程是否需要调度  
    
7.  \}

更新完cfs\_rq之后，会检查当前进程是否已经用完自己的“时间片”

点击(此处)折叠或打开

1.  /\*  
    
2.   \* Preempt the current task with a newly woken task if needed:  
    
3.   \*/  
    
4.  static void  
    
5.  check\_preempt\_tick(struct cfs\_rq \*cfs\_rq, struct sched\_entity \*curr)  
    
6.  \{   
    
7.      unsigned long ideal\_runtime, delta\_exec;  
    
8.    
    
9.      ideal\_runtime = sched\_slice(cfs\_rq, curr);//ideal\_runtime是理论上的处理器运行时间片    
10.     delta\_exec = curr\->sum\_exec\_runtime \- curr\->prev\_sum\_exec\_runtime;//该进程本轮调度累计运行时间  
    
11.     if (delta\_exec > ideal\_runtime) \{ // 假如实际运行超过调度器分配的时间，就标记调度标志  
    
12.         resched\_task(rq\_of(cfs\_rq)\->curr);  
    
13.         /\*  
    
14.          \* The current task ran long enough, ensure it doesn't get  
    
15.          \* re\-elected due to buddy favours.  
    
16.          \*/  
    
17.         clear\_buddies(cfs\_rq, curr);  
    
18.         return;  
    
19.     \}  
    
20.   
    
21.     /\*  
    
22.      \* Ensure that a task that missed wakeup preemption by a  
    
23.      \* narrow margin doesn't have to wait for a full slice.  
    
24.      \* This also mitigates buddy induced latencies under load.  
    
25.      \*/  
    
26.     if (!sched\_feat(WAKEUP\_PREEMPT))  
    
27.         return;  
    
28.   
    
29.     if (delta\_exec < sysctl\_sched\_min\_granularity)  
    
30.         return;  
    
31.   
    
32.     if (cfs\_rq\->nr\_running > 1) \{   
    
33.         struct sched\_entity \*se = \_\_pick\_next\_entity(cfs\_rq);  
    
34.         s64 delta = curr\->vruntime \- se\->vruntime;  
    
35.   
    
36.         if (delta > ideal\_runtime)  
    
37.             resched\_task(rq\_of(cfs\_rq)\->curr);  
    
38.     \}  
    
39. \}

当该进程运行时间超过实际分配的“时间片”，就标记调度标志resched\_task(rq\_of(cfs\_rq)->curr);，否则本进程继续执行。中断退出，调度函数schedule()会检查此标记，以选取新的进程来抢占当前进程。

3.如何选择下一个可执行进程

CFS选择具有最小vruntime值的进程作为下一个可执行进程，CFS用红黑树来组织调度实体，而键值就是vruntime。那么CFS只要查找选择最左叶子节点作为下一个可执行进程即可。实际上CFS缓存了最左叶子，可以直接选取left\_most叶子。

上面代码跟踪到timer tick中断退出，若“ideal\_runtime”已经用完，就会调用schedule()函数选中新进程并且完成切换。

点击(此处)折叠或打开

1.  asmlinkage void \_\_sched schedule(void)  
    
2.  \{   
    
3.      if (prev\->state && !(preempt\_count() & PREEMPT\_ACTIVE)) \{   
    
4.          if (unlikely(signal\_pending\_state(prev\->state, prev)))  
    
5.              prev\->state = TASK\_RUNNING;  
    
6.          else  
    
7.              deactivate\_task(rq, prev, 1);//如果状态已经不可运行，将其移除运行队列  
    
8.          switch\_count = &prev\->nvcsw;  
    
9.      \}  
    
10.   
    
11.     pre\_schedule(rq, prev);  
    
12.   
    
13.     if (unlikely(!rq\->nr\_running))  
    
14.         idle\_balance(cpu, rq);  
    
15.   
    
16.     put\_prev\_task(rq, prev); //处理上一个进程  
    
17.     next = pick\_next\_task(rq);//选出下一个进程  
    
18. …  
    
19.     context\_switch(rq, prev, next); /\* unlocks the rq \*///完成进程切换  
    
20. …  
    
21. \}

如果进程状态已经不是可运行，那么会将该进程移出可运行队列，如果继续可运行

put\_prev\_task()会依次调用put\_prev\_task\_fair()->put\_prev\_entity()

点击(此处)折叠或打开

1.  static void put\_prev\_entity(struct cfs\_rq \*cfs\_rq, struct sched\_entity \*prev)  
    
2.  \{   
    
3.      /\*  
    
4.       \* If still on the runqueue then deactivate\_task()  
    
5.       \* was not called and update\_curr() has to be done:  
    
6.       \*/  
    
7.      if (prev\->on\_rq)  
    
8.          update\_curr(cfs\_rq);  
    
9.    
    
10.     check\_spread(cfs\_rq, prev);  
    
11.     if (prev\->on\_rq) \{   
    
12.         update\_stats\_wait\_start(cfs\_rq, prev);  
    
13.         /\* Put 'current' back into the tree. \*/  
    
14.         \_\_enqueue\_entity(cfs\_rq, prev);  
    
15.     \}  
    
16.     cfs\_rq\->curr = NULL;  
    
17. \}

\_\_enqueue\_entity(cfs\_rq, prev) 将上一个进程重新插入红黑树(注意，当前运行进程是不在红黑树中的)

pick\_next\_task()会依次调用pick\_next\_task\_fair()

点击(此处)折叠或打开

1.  static struct task\_struct \*pick\_next\_task\_fair(struct rq \*rq)  
    
2.  \{   
    
3.      struct task\_struct \*p;  
    
4.      struct cfs\_rq \*cfs\_rq = &rq\->cfs;  
    
5.      struct sched\_entity \*se;  
    
6.    
    
7.      if (!cfs\_rq\->nr\_running)  
    
8.          return NULL;  
    
9.    
    
10.     do \{   
    
11.         se = pick\_next\_entity(cfs\_rq);//选出下一个可执行进程  
    
12.         set\_next\_entity(cfs\_rq, se); //把选中的进程(left\_most叶子)从红黑树移除，更新红黑树  
    
13.         cfs\_rq = group\_cfs\_rq(se);  
    
14.     \} while (cfs\_rq);  
    
15.   
    
16.     p = task\_of(se);  
    
17.     hrtick\_start\_fair(rq, p);  
    
18.   
    
19.     return p;  
    
20. \}

set\_next\_entity()函数会调用\_\_dequeue\_entity(cfs\_rq, se)把选中的下一个进程即最左叶子移出红黑树。

最后context\_switch()完成进程的切换。

4.何时更新rbtree

①上一个进程执行完ideal\_time，还可继续执行时，会插入红黑树；

②下一个进程被选中移出rbtree红黑树时；

③新建进程；

④进程由睡眠态被激活，变为可运行态时；

⑤调整优先级时也会更新rbtree；

5.新建进程如何加入红黑树

新建进程会做一系列复杂的工作，这里我们只关心与红黑树有关部分

Linux使用fork，clone或者vfork等系统调用创建进程，最终都会到do\_fork函数实现，如果没有设置CLONE\_STOPPED，do\_fork会执行两个与红黑树相关的函数: copy\_process()和wake\_up\_new\_task()

(1) copy\_process()->sched\_fork()->task\_fork()

点击(此处)折叠或打开

1.  static void place\_entity(struct cfs\_rq \*cfs\_rq, struct sched\_entity \*se, int initial)  
    
2.  \{   
    
3.      u64 vruntime = cfs\_rq\->min\_vruntime;//以cfs的最小vruntime为基准  
    
4.    
    
5.      /\*  
    
6.       \* The 'current' period is already promised to the current tasks,  
    
7.       \* however the extra weight of the new task will slow them down a  
    
8.       \* little, place the new task so that it fits in the slot that  
    
9.       \* stays open at the end.  
    
10.      \*/  
    
11.     if (initial && sched\_feat(START\_DEBIT))  
    
12.         vruntime \+= sched\_vslice(cfs\_rq, se);// 加上一个调度周期内的"时间片"  
    
13.   
    
14.     /\* sleeps up to a single latency don't count. \*/  
    
15.     if (!initial && sched\_feat(FAIR\_SLEEPERS)) \{   
    
16.         unsigned long thresh = sysctl\_sched\_latency;  
    
17.   
    
18.         /\*  
    
19.          \* Convert the sleeper threshold into virtual time.  
    
20.          \* SCHED\_IDLE is a special sub\-class. We care about  
    
21.          \* fairness only relative to other SCHED\_IDLE tasks,  
    
22.          \* all of which have the same weight.  
    
23.          \*/  
    
24.         if (sched\_feat(NORMALIZED\_SLEEPER) && (!entity\_is\_task(se) ||  
    
25.                  task\_of(se)\->policy != SCHED\_IDLE))  
    
26.             thresh = calc\_delta\_fair(thresh, se);  
    
27.   
    
28.         /\*  
    
29.          \* Halve their sleep time's effect, to allow  
    
30.          \* for a gentler effect of sleepers:  
    
31.          \*/  
    
32.         if (sched\_feat(GENTLE\_FAIR\_SLEEPERS))  
    
33.             thresh >>= 1;  
    
34.   
    
35.         vruntime \-= thresh;  
    
36.     \}  
    
37.   
    
38.     /\* ensure we never gain time by being placed backwards. \*/  
    
39.     vruntime = max\_vruntime(se\->vruntime, vruntime);  
    
40.   
    
41.     se\->vruntime = vruntime;  
    
42. \}

计算新进程的vruntime值，加上一个“平均时间片”表示刚执行完，避免新建进程立马抢占CPU。

(2)调用wake\_up\_new\_task函数

点击(此处)折叠或打开

1.  void wake\_up\_new\_task(struct task\_struct \*p, unsigned long clone\_flags)  
    
2.  \{   
    
3.  …  
    
4.      rq = task\_rq\_lock(p, &flags);  
    
5.      update\_rq\_clock(rq);  
    
6.      activate\_task(rq, p, 0);//激活当前进程，添加入红黑树  
    
7.  check\_preempt\_curr(rq, p, WF\_FORK);//确认是否需要抢占  
    
8.      …  
    
9.  \}

更新时钟，激活新建的进程activate\_task()会调用

点击(此处)折叠或打开

1.  static void enqueue\_task(struct rq \*rq, struct task\_struct \*p, int wakeup, bool head)  
    
2.  \{   
    
3.      if (wakeup)  
    
4.          p\->se.start\_runtime = p\->se.sum\_exec\_runtime;  
    
5.    
    
6.      sched\_info\_queued(p);  
    
7.      p\->sched\_class\->enqueue\_task(rq, p, wakeup, head);  
    
8.      p\->se.on\_rq = 1;  
    
9.  \}

将新建的进程加入rbtree；

6.唤醒进程 调用try\_to\_wake\_up()->activate\_task()->enqueue\_task\_fair()->enqueue\_entity()

注意enqueue\_entity 函数调用place\_entity对进程vruntime做补偿计算，再次考察place\_entity(cfs\_rq, se, 0)

点击(此处)折叠或打开

1.  static void place\_entity(struct cfs\_rq \*cfs\_rq, struct sched\_entity \*se, int initial)  
    
2.  \{   
    
3.      u64 vruntime = cfs\_rq\->min\_vruntime;//以cfs的最小vruntime为基准  
    
4.    
    
5.      /\*  
    
6.       \* The 'current' period is already promised to the current tasks,  
    
7.       \* however the extra weight of the new task will slow them down a  
    
8.       \* little, place the new task so that it fits in the slot that  
    
9.       \* stays open at the end.  
    
10.      \*/  
    
11.     if (initial && sched\_feat(START\_DEBIT))  
    
12.         vruntime \+= sched\_vslice(cfs\_rq, se);//一个调度周期内的"时间片"  
    
13.   
    
14.     /\* sleeps up to a single latency don't count. \*/  
    
15.     if (!initial && sched\_feat(FAIR\_SLEEPERS)) \{   
    
16.         unsigned long thresh = sysctl\_sched\_latency;  
    
17.   
    
18.         /\*  
    
19.          \* Convert the sleeper threshold into virtual time.  
    
20.          \* SCHED\_IDLE is a special sub\-class. We care about  
    
21.          \* fairness only relative to other SCHED\_IDLE tasks,  
    
22.          \* all of which have the same weight.  
    
23.          \*/  
    
24.         if (sched\_feat(NORMALIZED\_SLEEPER) && (!entity\_is\_task(se) ||  
    
25.                  task\_of(se)\->policy != SCHED\_IDLE))  
    
26.             thresh = calc\_delta\_fair(thresh, se);  
    
27.   
    
28.         /\*  
    
29.          \* Halve their sleep time's effect, to allow  
    
30.          \* for a gentler effect of sleepers:  
    
31.          \*/  
    
32.         if (sched\_feat(GENTLE\_FAIR\_SLEEPERS))  
    
33.             thresh >>= 1;  
    
34.   
    
35.         vruntime \-= thresh;//对于睡眠进程唤醒，给予vruntime补偿  
    
36.     \}  
    
37.   
    
38.     /\* ensure we never gain time by being placed backwards. \*/  
    
39.     vruntime = max\_vruntime(se\->vruntime, vruntime);//避免通过睡眠来获得运行时间  
    
40.   
    
41.     se\->vruntime = vruntime;  
    
42. \}

当initial=1时，新建进程vruntime=cfs最小vruntime值\+时间片，放入红黑树最右端。

当initial=0时，表示唤醒进程，vruntime要减去一个thresh.这个thresh由调度周期sysctl\_sched\_latency加权得到虚拟时间，这样做可以对睡眠进程做一个补偿，唤醒时会得到一个较小的vruntime, 使它可以尽快抢占CPU(可以快速响应I/O消耗型进程)。

注意注释/\* ensure we never gain time by being placed backwards. \*/

这个设计是为了给睡眠较长时间的进程做时间补偿的，既使其可以快速抢占，又避免因太小的vruntime值而长期占用CPU。但有些进程只是短时间睡眠，这样唤醒时自身vruntime还是大于min\_vruntime的，为了不让进程通过睡眠获得额外运行时间补偿，最后vruntime取计算出的补偿时间和进程本身的vruntime较大者。从这可以看出，虽然CFS不再区分I/O消耗型，CPU消耗型进程，但是CFS模型对IO消耗型天然的提供了快速的响应。

7.改变进程优先级，如何调整rbtree

Linux中改变进程优先级会调用底层的set\_user\_nice()

点击(此处)折叠或打开

1.  void set\_user\_nice(struct task\_struct \*p, long nice)  
    
2.  \{   
    
3.  …  
    
4.      dequeue\_task(rq, p, 0); //把进程从红黑树中取出  
    
5.  …  
    
6.      p\->static\_prio = NICE\_TO\_PRIO(nice);//将nice(\-20~19)值映射到100~139,0~99是实时进程优先级  
    
7.      set\_load\_weight(p);  
    
8.  …  
    
9.      enqueue\_task(rq, p, 0, false);  
    
10. \}

set\_user\_nice把进程从红黑树取出，调整优先级(nice值对应权重)，再重新加入红黑树.

set\_load\_weight()函数是设置nice值对应的权重，

点击(此处)折叠或打开

1.  static void set\_load\_weight(struct task\_struct \*p)  
    
2.  \{   
    
3.      if (task\_has\_rt\_policy(p)) \{   
    
4.          p\->se.load.weight = 0;  
    
5.          p\->se.load.inv\_weight = WMULT\_CONST;  
    
6.          return;  
    
7.      \}  
    
8.    
    
9.      /\*  
    
10.      \* SCHED\_IDLE tasks get minimal weight:  
    
11.      \*/  
    
12.     if (p\->policy == SCHED\_IDLE) \{   
    
13.         p\->se.load.weight = WEIGHT\_IDLEPRIO;  
    
14.         p\->se.load.inv\_weight = WMULT\_IDLEPRIO;  
    
15.         return;  
    
16.     \}  
    
17.   
    
18.     p\->se.load.weight = prio\_to\_weight\[p\->static\_prio \- MAX\_RT\_PRIO\];  
    
19.     p\->se.load.inv\_weight = prio\_to\_wmult\[p\->static\_prio \- MAX\_RT\_PRIO\];  
    
20. \}

数组prio\_to\_weight\[\]是将nice值(-20~19)转化为以nici 0(1024)值为基准的加权值,根据内核注释每一个nice差值，权重相差10%，即在负载一定的条件下，每增加或减少一个nice值，获得的CPU时间相应增加或减少10%

点击(此处)折叠或打开

1.  static const int prio\_to\_weight\[40\] = \{   
    
2.   /\* \-20 \*/ 88761, 71755, 56483, 46273, 36291,  
    
3.   /\* \-15 \*/ 29154, 23254, 18705, 14949, 11916,  
    
4.   /\* \-10 \*/ 9548, 7620, 6100, 4904, 3906,  
    
5.   /\* \-5 \*/ 3121, 2501, 1991, 1586, 1277,  
    
6.   /\* 0 \*/ 1024, 820, 655, 526, 423,  
    
7.   /\* 5 \*/ 335, 272, 215, 172, 137,  
    
8.   /\* 10 \*/ 110, 87, 70, 56, 45,  
    
9.   /\* 15 \*/ 36, 29, 23, 18, 15,  
    
10. \};

上面 calc\_delta\_mine()函数用到这个数组加权值 ，这个 转化过程还没弄明白，有明白的朋友，指点一二，不胜感激

点击(此处)折叠或打开

1.  /\*  
    
2.   \* Inverse (2^32/x) values of the prio\_to\_weight\[\] array, precalculated.  
    
3.   \*  
    
4.   \* In cases where the weight does not change often, we can use the  
    
5.   \* precalculated inverse to speed up arithmetics by turning divisions  
    
6.   \* into multiplications:  
    
7.   \*/  
    
8.  static const u32 prio\_to\_wmult\[40\] = \{   
    
9.   /\* \-20 \*/ 48388, 59856, 76040, 92818, 118348,  
    
10.  /\* \-15 \*/ 147320, 184698, 229616, 287308, 360437,  
    
11.  /\* \-10 \*/ 449829, 563644, 704093, 875809, 1099582,  
    
12.  /\* \-5 \*/ 1376151, 1717300, 2157191, 2708050, 3363326,  
    
13.  /\* 0 \*/ 4194304, 5237765, 6557202, 8165337, 10153587,  
    
14.  /\* 5 \*/ 12820798, 15790321, 19976592, 24970740, 31350126,  
    
15.  /\* 10 \*/ 39045157, 49367440, 61356676, 76695844, 95443717,  
    
16.  /\* 15 \*/ 119304647, 148102320, 186737708, 238609294, 286331153,  
    
17. \};

最后，说下对CFS “完全公平” 的理解：  
①不再区分进程类型，所有进程公平对待  
 ②对I/O消耗型进程，仍然会提供快速响应(对睡眠进程做时间补偿)  
 ③ 优先级高的进程，获得CPU时间更多(vruntime增长的更慢)  
  
可见CFS的完全公平，并不是说所有进程绝对的平等，占用CPU时间完全相同，而是体现在vruntime数值上，所有进程都用虚拟时间来度量，总是让vruntime最小的进程抢占，这样看起来是完全公平的，但实际上vruntime的更新，增长速度，不同进程是不尽一样的。CFS利用这么个简单的vruntime机制，实现了以往需要相当复杂算法实现的进度调度需求，高明！

阅读(6042) | 评论(7) | 转发(13) |

上一篇：Linux内核设计与实现(5)---进程调度

下一篇：Linux内核设计与实现(6)---系统调用