freebsd9.2-ULE线程调度-保持cpu运行队列间的平衡-sched_balance函数

71v5

从帖子"freebsd9.2-何时调用mini_switch函数-线程时间片用完"的描述中可知，当statclock超时后，statclock_cnt函数
会调用调度程序相关的sched_clock函数进行相应的处理，sched_clock函数的一个任务就是检查是否需要调用函数
sched_balance在cpu的运行队列间迁移thread，以保持cpu运行队列间的平衡,这里再摘取相关的代码，这样就会更清晰:

1.   2174        /*
   
2.   2175         * Handle a stathz tick.  This is really only relevant for timeshare
   
3.   2176         * threads.
   
4.   2177         */
   
5.   2178        void
   
6.   2179        sched_clock(struct thread *td)
   
7.   2180        {
   
8.   2181                struct tdq *tdq;
   
9.   2182                struct td_sched *ts;
   
10.   2183                /* 2185：tdq指向当前cpu对应的struct tdq对象 */
    
11.   2184                THREAD_LOCK_ASSERT(td, MA_OWNED);
    
12.   2185                tdq = TDQ_SELF();
    
13.   2186        #ifdef SMP
    
14.   2187                /***********************************************************************
    
15.   2188                 * We run the long term load balancer infrequently on the first cpu.
    
16. 
    
17.                    static struct tdq       *balance_tdq;
    
18.                    static int balance_ticks;
    
19. 
    
20.                    2190-2193：
    
21.                    在ULE调度程序初始化阶段，BSP会将balance_tdq设置为BSP对应的struct tdq
    
22.                    数据对象的地址。
    
23.                   
    
24.                    balance_ticks为调用sched_balance函数在系统中cpu的运行队列间迁移线程
    
25.                    的周期，在ULE调度程序初始化阶段设置，具体值是多少应该没什么意义：
    
26.                    balance_interval默认值为128.
    
27.                    balance_ticks = max(balance_interval / 2, 1);
    
28.                    balance_ticks += random() % balance_interval;
    
29. 
    
30.                    当balance_ticks为零0时，函数sched_balance就要保持系统中cpu运行队列
    
31.                    间的平衡。
    
32. 
    
33.                    只在BSP上执行。
    
34.   2189                 *************/
    
35.   2190                if (balance_tdq == tdq) {
    
36.   2191                        if (balance_ticks && --balance_ticks == 0)
    
37.   2192                                sched_balance();
    
38.   2193                }
    
39. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
    
40. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
    
41.        }

复制代码

这里为了简化分析，做下面的假设：
1：系统中有两个物理cpu，每个cpu有4个物理核心，logical cpu id分别为0，1，2，3，4，5，6，7，后面就
以cpu0，cpu1，cpu2等等标识这些logical cpu，其对应的运行队列分别记为tdq_cpu[0]，tdq_cpu[1]，tdq_cpu[2]
，tdq_cpu[3]等等。

2：cpuset_t类型的大小为1字节，并且bit位以从左到右的顺序编号，那么：
   对于一个cpuset_t类型的cpumask变量，如果其编码为11111111， 如果某个bit位设置为1，那么该bit位对应的cpu
   就被检查，比如如果bit0被设置为1，就要检查cpu0。


这里先简要分析一下sched_lowest函数，大家可以参照sched_highest函数的分析看看sched_lowest函数到底怎么工作的。
[函数sched_lowest]：

1. /******************************************************************************************
   
2. * Find the cpu with the least load via the least loaded path that has a
   
3. * lowpri greater than pri  pri.  A pri of -1 indicates any priority is
   
4. * acceptable.
   
5. *
   
6.    参数描述：
   
7.    cg：所要检查的cpu_group。
   
8.    mask：将要检查的cpu集合。
   
9.    pri: 该参数可以忽略。
   
10.    maxload：该参数比较重要，一般设置为上一次调用函数sched_highest返回的cpu运行
    
11.             队列最高的cpu的的负载，在确定cpu运行队列负载最小的cpu时，只有当
    
12.             相应cpu运行队列的负载小于或者等于maxload才会被检查。
    
13.    prefer： 上一次调用函数sched_highest返回的cpu的logical cpu id，当所检查的
    
14.             cpu和prefer相同时，将prefer运行队列的负载减去一个常数。
    
15.    
    
16.    函数返回值：
    
17.    -1：表示期间创建了好多thread，这些thread被添加到了cpu的运行队列中，导致所检查的
    
18.        cpu运行队列的负载都比maxload高。
    
19. 
    
20.    非零：运行队列负载最低的cpu的logical cpu id。
    
21. 
    
22.    其实只要这些参数的含义弄明白，下来就是就是一些简单的分析过程了。
    
23. ************************************/
    
24.    744        static inline int
    
25.    745        sched_lowest(const struct cpu_group *cg, cpuset_t mask, int pri, int maxload,
    
26.    746            int prefer)
    
27.    747        {
    
28.    748                struct cpu_search low;
    
29.    749       
    
30.    750                low.cs_cpu = -1;
    
31.    751                low.cs_prefer = prefer;
    
32.    752                low.cs_mask = mask;
    
33.    753                low.cs_pri = pri;
    
34.    754                low.cs_limit = maxload;
    
35.    755                cpu_search_lowest(cg, &low);
    
36.    756                return low.cs_cpu;
    
37.    757        }
    
38.    716  /*
    
39.    717   * cpu_search instantiations must pass constants to maintain the inline
    
40.    718   * optimization.
    
41.    719   */
    
42.    720  int
    
43.    721  cpu_search_lowest(const struct cpu_group *cg, struct cpu_search *low)
    
44.    722  {
    
45.    723          return cpu_search(cg, low, NULL, CPU_SEARCH_LOWEST);
    
46.    724  }

复制代码

[ULE调度程序-sched_balance函数]：

1.    842        static void
   
2.    843        sched_balance(void)
   
3.    844        {
   
4.    845                struct tdq *tdq;
   
5.    846       
   
6.    847       
   
7.    848
   
8.    849
   
9.    850
   
10. /****************************************************************************************
    
11. * Select a random time between .5 * balance_interval and
    
12. * 1.5 * balance_interval.
    
13. *
    
14. * 变量reblance：表示是否要进行cpu运行队列间的再平衡，初始值为1，可以通过
    
15. * sysctl系统调用来更改。
    
16. * static int rebalance = 1;
    
17. 
    
18.    851-852：重新计算balance_ticks。
    
19.    
    
20.    853：如果不是SMP系统或者变量rebalance为0，就直接返回，因为没有必要进行
    
21.         cpu运行队列的再平衡操作。
    
22.    
    
23.    855：因为只有BSP执行sched_balance函数，而BSP的logical cpu id为0，所以
    
24.         这里tdq的值就为&tdq_cpu[0]。
    
25.    
    
26.    857：以参数cpu_top调用函数sched_balance_group
    
27.         参数cpu_top请参考帖子"freebsd9.2-ULE线程调度-创建数据结构来描述CPU拓扑信息"
    
28. **************************/
    
29.    851                balance_ticks = max(balance_interval / 2, 1);
    
30.    852                balance_ticks += random() % balance_interval;
    
31.    853                if (smp_started == 0 || rebalance == 0)
    
32.    854                        return;
    
33.    855                tdq = TDQ_SELF();
    
34.    856                TDQ_UNLOCK(tdq);
    
35.    857                sched_balance_group(cpu_top);
    
36.    858                TDQ_LOCK(tdq);
    
37.    859        }

复制代码

[函数sched_balance_group]：

1.    798        static void
   
2.    799        sched_balance_group(struct cpu_group *cg)
   
3.    800        {
   
4. /********************************************************************************
   
5. * 局部变量描述：
   
6.    hamsk：在调用函数sched_highest检查运行队列负载最高的cpu时使用，该变量是一个
   
7.           cpu位图的集合，设置为1的bit位对应的cpu都会被检查。
   
8. 
   
9.    lmask：类似于hamsk，在检查运行队列负载最低的cpu时使用。
   
10. 
    
11.    high：运行队列负载最高的cpu的logical cpu id。
    
12.    low：运行队列负载最低的cpu的logical cpu id。
    
13. **************************************/
    
14.    801                cpuset_t hmask, lmask;
    
15.    802                int high, low, anylow;
    
16.    803       
    
17. /***************************************************************************************************
    
18. * 804：for循环前，将变量hmask的bit位全设置为1，表示检查系统中全部的cpu。
    
19. 
    
20.    805-839：一个无限for循环，当下面任何一个条件满足时，中止for循环：
    
21.    条件1：函数sched_highest返回值为-1，在一般情况下，如果返回值为-1，就表示所
    
22.           检查cpu运行队列中可迁移thread的数目为0。
    
23. 
    
24.    条件2：变量lmask中的bit位全部为0，表示没有要检查的cpu。
    
25. 
    
26.    条件3：anylow变量为1，并且函数sched_lowest返回值为-1。
    
27. 
    
28.    810：如果执行到这里，就表示函数sched_highest执行成功，这里假设函数sched_highest
    
29.         返回值为6(high值为6)，即cpu6的运行队列tdq_cpu[6]的负载最高，宏CPU_CLR将变量hmask中的bit6
    
30.         清零，这就意味着下一次调用sched_highest函数时将不会检查cpu6。
    
31. 
    
32.    811：将更新后的hmask变量copy到lmask变量中，函数sched_lowest将检查lmask变量中包含
    
33.         的cpu运行队列的负载，选择一个负载最低的cpu。
    
34. 
    
35.    813-815：当变量lmask为空时，即变量lmask中的bit位全为零，表示没有要检查的cpu，此时
    
36.             调用函数sched_lowest没有意义，跳出for循环。
    
37. 
    
38.    817-818：调用函数sched_lowest确定cpu运行队列负载最低的cpu，这里假设函数sched_lowest的返回值
    
39.             为2(low值为2)，即cpu2的运行队列tdq_cpu[2]的负载最低。
    
40. 
    
41.    820-821：对应上面的条件3。
    
42.   
    
43.    823-824：当函数sched_lowest返回-1时，此时继续for循环，如果期间一些thread意外终止或者
    
44.             主动执行了exit操作，那么下一次检查时，sched_lowest函数有可能返回有意义的值。
    
45. 
    
46.    825-828：执行到这里话，high为负载最高的cpu，low为负载最低的cpu，此时函数
    
47.             sched_balance_pair执行一个将thread从运行队列tdq_cpu[6]迁移到运行队列tdq_cpu[2]
    
48.             中的操作，以下面的形式调用函数：
    
49.             sched_balance_pair(&tdq_cpu[6], &tdq_cpu[2])；  
    
50.    
    
51.    826-828：如果函数sched_balance_pair返回1，将变量hmask中的bit2清零，这意味着下次for循环时将
    
52.             不会检查cpu6和cpu2。
    
53. 
    
54.    830-837：如果函数sched_balance_pair返回0，此时将变量lmask中的bit2清零，同时将变量anylow
    
55.             设置为0，跳转到nextlow处继续执行，继续确定下一个运行队列负载最低的cpu。
    
56. ***********************/
    
57.    804                CPU_FILL(&hmask);
    
58.    805                for (;;) {
    
59.    806                        high = sched_highest(cg, hmask, 1);
    
60.    807                        /* Stop if there is no more CPU with transferrable threads. */
    
61.    808                        if (high == -1)
    
62.    809                                break;
    
63.    810                        CPU_CLR(high, &hmask);
    
64.    811                        CPU_COPY(&hmask, &lmask);
    
65.    812                        /* Stop if there is no more CPU left for low. */
    
66.    813                        if (CPU_EMPTY(&lmask))
    
67.    814                                break;
    
68.    815                        anylow = 1;
    
69.    816        nextlow:
    
70.    817                        low = sched_lowest(cg, lmask, -1,
    
71.    818                            TDQ_CPU(high)->tdq_load - 1, high);
    
72.    819                        /* Stop if we looked well and found no less loaded CPU. */
    
73.    820                        if (anylow && low == -1)
    
74.    821                                break;
    
75.    822                        /* Go to next high if we found no less loaded CPU. */
    
76.    823                        if (low == -1)
    
77.    824                                continue;
    
78.    825                        /* Transfer thread from high to low. */
    
79.    826                        if (sched_balance_pair(TDQ_CPU(high), TDQ_CPU(low))) {
    
80.    827                                /* CPU that got thread can no longer be a donor. */
    
81.    828                                CPU_CLR(low, &hmask);
    
82.    829                        } else {
    
83.    830                                /*
    
84.    831                                 * If failed, then there is no threads on high
    
85.    832                                 * that can run on this low. Drop low from low
    
86.    833                                 * mask and look for different one.
    
87.    834                                 */
    
88.    835                                CPU_CLR(low, &lmask);
    
89.    836                                anylow = 0;
    
90.    837                                goto nextlow;
    
91.    838                        }
    
92.    839                }
    
93.    840        }

复制代码

[函数sched_balance_pair]-负责在两个运行队列间迁移thread：

1. /********************************************************************
   
2. * Transfer load between two imbalanced thread queues.
   
3. *
   
4.    参数描述:
   
5.    high：负载最高的运行队列，这里为tdq_cpu[6]。
   
6.    low： 负载最低的运行队列，这里为tdq_cpu[2]。
   
7. 
   
8.    sched_balance_pair函数返回值的含义请参考一下下面对tdq_move函数
   
9.    返回值的分析。
   
10. ****************************/
    
11.    889        static int
    
12.    890        sched_balance_pair(struct tdq *high, struct tdq *low)
    
13.    891        {
    
14. /*********************************************************************************
    
15. * 局部变量描述：
    
16.    moved：可以迁移的thread的数目。
    
17.    cpu：运行队列low对应的cpu的logical cpu id。
    
18. 
    
19.    901-912：再次检查迁移条件是否满足，tdq_move函数见下面的分析。
    
20.   
    
21.    一般情况下if语句的前两个条件都满足，此时：
    
22. 
    
23.    在函数tdq_move返回1时，检查是否需要向运行队列low对应的cpu发出一个处理器间
    
24.    中断(IPI),后续有时间的话，将和大家分享一下处理器间中断的发送过程以及相关
    
25.    的处理。
    
26. *******************************************/  
    
27.    892                int moved;
    
28.    893                int cpu;
    
29.    894       
    
30.    895                tdq_lock_pair(high, low);
    
31.    896                moved = 0;
    
32.    897                /*
    
33.    898                 * Determine what the imbalance is and then adjust that to how many
    
34.    899                 * threads we actually have to give up (transferable).
    
35.    900                 */
    
36.    901                if (high->tdq_transferable != 0 && high->tdq_load > low->tdq_load &&
    
37.    902                    (moved = tdq_move(high, low)) > 0) {
    
38.    903                        /*
    
39.    904                         * In case the target isn't the current cpu IPI it to force a
    
40.    905                         * reschedule with the new workload.
    
41.    906                         */
    
42.    907                        cpu = TDQ_ID(low);
    
43.    908                        sched_pin();
    
44.    909                        if (cpu != PCPU_GET(cpuid))
    
45.    910                                ipi_cpu(cpu, IPI_PREEMPT);
    
46.    911                        sched_unpin();
    
47.    912                }
    
48.    913                tdq_unlock_pair(high, low);
    
49.    914                return (moved);
    
50.    915        }

复制代码

[函数tdq_move]：

1. /*****************************************************************
   
2. * Move a thread from one thread queue to another.
   
3. *
   
4.    参数描述：
   
5.    from：线程将要从运行队列from中移除。
   
6.    to：线程将要添加到运行队列to中。
   
7. 
   
8.    根据函数的描述，tdq_move一次将只迁移一个thread，太可怜了吧，
   
9.    之前看linux-2.6.18线程调度这块实现时，都可以迁移一定数目的
   
10.    thread了，不过bsd开发者可能有他们自己的想法，这里就是简要
    
11.    的点评一下。
    
12. 
    
13.    下面简要的分析一下tdq_move函数，后续有时间将和大家分享一下
    
14.    如何将一个thread添加到运行队列中，以及如何将一个thread从一个
    
15.    运行队列中移除。
    
16. 
    
17.    这里只需要明白返回值的含义：
    
18.    
    
19.    0：运行队列from中的thread不能迁移到运行队列to中。
    
20. 
    
21.    1：成功将一个thread从运行队列from迁移到运行队列to中。
    
22. 
    
23. ************************/
    
24.    920        static int
    
25.    921        tdq_move(struct tdq *from, struct tdq *to)
    
26.    922        {
    
27.    923                struct td_sched *ts;
    
28.    924                struct thread *td;
    
29.    925                struct tdq *tdq;
    
30.    926                int cpu;
    
31.    927       
    
32.    928                TDQ_LOCK_ASSERT(from, MA_OWNED);
    
33.    929                TDQ_LOCK_ASSERT(to, MA_OWNED);
    
34.    930       
    
35. /******************************************************************
    
36. * cpu：运行队列to对应的cpu的logical cpu id。
    
37. 
    
38.    描述thread的struct thread对象有下面一个成员：
    
39.    td_cpuset：cpu掩码的集合，即CPU affinity sets，一般情况下
    
40.               该字段的值从父进程继承，除非调用cpuset系统调用
    
41.               进行修改，即线程thread只能在在td_cpuset中的cpu
    
42.               上运行或者说成线程thread只能被添加到td_cpuset中的cpu
    
43.               的运行队列中。
    
44.    函数tdq_steal依次检查tdq_realtime，tdq_timeshare，tdq_idle
    
45.    队列中的全部thread，如果描述每个thread的struct thread对象
    
46.    中的td_cpuset成员标识的cpu集合中都不包括运行队列to对应的cpu，
    
47.    那么函数tdq_steal将返回NULL,此时tdq_move函数返回0.
    
48.    否则函数tdq_steal将返回描述一个线程的struct thread对象，此时
    
49.    此时tdq_move函数返回1.
    
50. 
    
51.    941-947：将线程td从运行队列from中移除，同时将线程td添加到
    
52.             运行队列to中，以及更新线程td对应的struct thread对象
    
53.             中的相关成员。  
    
54. ******************************/   
    
55.    931                tdq = from;
    
56.    932                cpu = TDQ_ID(to);
    
57.    933                td = tdq_steal(tdq, cpu);
    
58.    934                if (td == NULL)
    
59.    935                        return (0);
    
60.    936                ts = td->td_sched;
    
61.    937                /*
    
62.    938                 * Although the run queue is locked the thread may be blocked.  Lock
    
63.    939                 * it to clear this and acquire the run-queue lock.
    
64.    940                 */
    
65.    941                thread_lock(td);
    
66.    942                /* Drop recursive lock on from acquired via thread_lock(). */
    
67.    943                TDQ_UNLOCK(from);
    
68.    944                sched_rem(td);
    
69.    945                ts->ts_cpu = cpu;
    
70.    946                td->td_lock = TDQ_LOCKPTR(to);
    
71.    947                tdq_add(to, td, SRQ_YIELDING);
    
72.    948                return (1);
    
73.    949        }

复制代码

freshkkalice

支持一下辛苦的楼主~顶了！

lei06264

我老妈很喜欢李宇春呢。。。。。。

keitse

林子大了什么鸟没有啊？祝踩的死全家！！！！