忘记密码   免费注册 查看新帖 | 论坛精华区

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT 视频 徽章 文库 沙龙 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
查看: 11309 | 回复: 2

[FreeBSD] freebsd9.2-ULE线程调度-确定cpu运行队列负载最高的cpu-sched_highest函数 [复制链接]

论坛徽章:
0
发表于 2014-06-28 16:29 |显示全部楼层
本帖最后由 71v5 于 2014-06-29 22:44 编辑

[sched_highest函数]-确定系统中cpu运行队列负载最高的cpu,并返回该cpu的logical cpu id,继续以cpu拓扑图开始,因为检查cpu负载
的过程跟cpu拓扑图密切相关,这里为了简化分析,做下面的假设:
1:cpuset_t类型的大小为1字节,并且bit位以从左到右的顺序编号,那么:
   对于cpu_top中的cg_mask成员,其编码为11111111, 表示该group中包含的cpu的logical id为0,1,2,3,4,5,6,7。
   对于group[1]中的cg_mask成员,其编码为11110000,表示该group中包含的cpu的logical id为0,1,2,3。
   对于group[2]中的cg_mask成员,其编码为00001111,表示该group中包含的cpu的logical id为4,5,6,7。

2:因为不管是确定负载最高的cpu还是负载最低的cpu,最终都是通过函数cpu_search来操作的,所以在cpu_search函数中
   略去了一些不相关的操作,比如检查负载最高的cpu时,就略去了和检查负载最低的cpu相关的代码,略去的代码以下面
   的"。。。。。。。。。。。。。。。。。。。"标识。
   
3:cpu运行队列分别为tdq_cpu[0],tdq_cpu[1],tdq_cpu[2],tdq_cpu[3]等

07.jpg


[数据类型struct cpu_search]:
  1. /************************************************************************
  2. * struct cpu_search类型的数据对象在函数cpu_search中使用,用来保存
  3.    查找的结果。

  4.    cs_mask:一个cpu掩码位图,位图中设置为1的bit位对应的cpu将在
  5.             函数cpu_search中检查其负载。
  6.    cs_prefer:在检查cpu运行队列负载最低cpu的时候使用,一般设置为
  7.               上一次调用函数sched_highest返回的cpu的logical cpu id,当所
  8.               检查的cpu和cs_prefer相同时,将cs_prefer运行队列的负载减去
  9.               一个常数。
  10.    cs_limit:一个负载阈值。
  11.    cs_cpu:cpu运行队列负载最低或者最高的cpu对应的logical cpu id。
  12.    cs_load:相应的负载。
  13.    cs_pri:一般情况下,可以忽略。
  14. *********************************/
  15.    577        struct cpu_search {
  16.    578                cpuset_t cs_mask;
  17.    579                u_int        cs_prefer;
  18.    580                int        cs_pri;                /* Min priority for low. */
  19.    581                int        cs_limit;        /* Max load for low, min load for high. */
  20.    582                int        cs_cpu;
  21.    583                int        cs_load;
  22.    584        };
  23. /************************************************************
  24. * 传递给cpu_search函数的标志,含义如下:
  25.    CPU_SEARCH_LOWEST:只确定cpu运行队列负载最低的cpu。
  26.    CPU_SEARCH_HIGHEST:只确定cpu运行队列负载最高的cpu。
  27.    CPU_SEARCH_BOTH:同时确定cpu运行队列负载最高和最低的cpu。
  28. *****************************/
  29.    586        #define        CPU_SEARCH_LOWEST        0x1
  30.    587        #define        CPU_SEARCH_HIGHEST        0x2
  31.    588        #define        CPU_SEARCH_BOTH                (CPU_SEARCH_LOWEST|CPU_SEARCH_HIGHEST)
复制代码
[sched_highest函数]:
  1. /********************************************************************************************
  2. * Find the cpu with the highest load via the highest loaded path.
  3.    一般情况下,在确定系统中cpu运行队列负载最高的cpu时,会以下面的参数调用sched_highest函数:
  4.    cg:cpu_top。
  5.    mask:类型为cpuset_t的cpu位图,这里的编码为11111111,在随后从sched_balance_group函数中
  6.          的for循环中继续调用sched_highest函数时,mask的值会改变,不过mask中bit位为1的cpu
  7.          都要被检查。
  8.    minload:这里的值为1。

  9.    该函数实际上使用参数mask,minload初始化一个struct cpu_serach类型的数据对象,
  10.    然后再调用cpu_search_highest函数,该函数为函数cpu_search的简单封装。

  11.    函数sched_highest返回值如果为-1:在一般情况下,如果返回值为-1,就表示所检查cpu运行队列
  12.    中可迁移thread的数目为0.

  13.    函数sched_highest返回其它值:相应cpu的logical cpu id,该cpu运行队列中可迁移thread的数目
  14.    非零,并且负载最高。
  15. **************************************/
  16.    762        static inline int
  17.    763        sched_highest(const struct cpu_group *cg, cpuset_t mask, int minload)
  18.    764        {
  19.    765                struct cpu_search high;
  20.    766       
  21.    767                high.cs_cpu = -1;
  22.    768                high.cs_mask = mask;
  23.    769                high.cs_limit = minload;
  24.    770                cpu_search_highest(cg, &high);
  25.    771                return high.cs_cpu;
  26.    772        }
  27.    726        int
  28.    727        cpu_search_highest(const struct cpu_group *cg, struct cpu_search *high)
  29.    728        {
  30.    729                return cpu_search(cg, NULL, high, CPU_SEARCH_HIGHEST);
  31.    730        }
复制代码
[函数cpu_search]-该函数实际上是一个递归过程,根据之前的假定,递归深度为1,这里分检查cpu_top和检查child cpu_group两种情况来分析该函数,因为
这两种情况cpu_search函数的执行流程不一样。


[检查cpu_top-调用函数cpu_search]:
  1. /***********************************************************************************************
  2. * 参数描述:
  3.    cg:cpu_top

  4.    low:NULL。

  5.    high:类型为struct cpu_search的数据对象,各成员如下:
  6.          high.cs_cpu = -1;
  7.          high.cs_mask = mask; // 11111111
  8.          high.cs_limit = minload;// 1

  9.    match:CPU_SEARCH_HIGHEST

  10.    当函数cpu_search返回时,high指向的struct cpu_search对象中包含了group[1]和group[2]中
  11.    cpu运行队列负载最高cpu的logical cpu id和相应运行队列的负载。

  12.    函数的返回值为group[2]和group[1]中cpu运行队列的总负载。
  13. ******************************************/
  14.    612        static __inline int
  15.    613        cpu_search(const struct cpu_group *cg, struct cpu_search *low,
  16.    614            struct cpu_search *high, const int match)
  17.    615        {
  18. /****************************************************************************
  19. * 局部变量描述:
  20.    lgroup:检查负载最低的cpu时使用。
  21.    hgroup:检查负载最低的cpu时使用
  22.    cpumask:cpu位图。
  23.    child:指向child cpu_group。
  24.    tdq:指向相应cpu的运行队列。
  25.    cpu:相应cpu的logical cpu id。
  26.    i:child cpu_group的数目。
  27.    hload:cpu的最高负载。
  28.    load:
  29.    total:总负载。
  30.    rnd,*rndptr:一个随机数值,不明白其含义,但是不影响这里的分析,众会员
  31.                  知道的话请及时联系啊。
  32. *************************************/
  33.    616                struct cpu_search lgroup;
  34.    617                struct cpu_search hgroup;
  35.    618                cpuset_t cpumask;
  36.    619                struct cpu_group *child;
  37.    620                struct tdq *tdq;
  38.    621                int cpu, i, hload, lload, load, total, rnd, *rndptr;
  39.    622       
  40. /**************************************************************************
  41. * cpumask:此时的编码为11111111.
  42.    
  43. *****************/
  44.    623                total = 0;
  45.    624                cpumask = cg->cg_mask;
  46. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  47.    629                if (match & CPU_SEARCH_HIGHEST) {
  48.    630                        hload = INT_MIN;
  49.    631                        hgroup = *high;
  50.    632                }
  51.    633
  52. /***********************************************************************************
  53. * mp_maxid:
  54.    Max CPU ID,初始化时被设置为mp_maxid = mp_ncpus - 1;  被初始化为7.

  55.    635-712:之间的for循环执行两次,每次循环都检查一个child cpu_group。

  56.    第一次for循环:调用函数cpu_search检查group[2]
  57.    i = 2,cpu = 7;
  58.    
  59.    636-643:执行else语句,child为&group[2];
  60.    
  61.    649-685:这里将执行if语句,即将调用函数cpu_search检查group[2].

  62.    650:group[2]中的cg_mask成员编码为00001111,CPU_NAND执行完后,
  63.         cpumask的编码为11110000。

  64.    
  65.    第二次for循环:调用函数cpu_search检查group[1].
  66.    i = 1,cpu = 7.

  67.    636-643:执行else语句,child为&group[1];
  68.    
  69.    649-685:这里将执行if语句,即将调用函数cpu_search检查group[1].

  70.    650:group[1]中的cg_mask成员编码为11110000,CPU_NAND执行完后,
  71.         cpumask的编码为00000000。   

  72. *************************************************/         
  73.    634                /* Iterate through the child CPU groups and then remaining CPUs. */
  74.    635                for (i = cg->cg_children, cpu = mp_maxid; i >= 0; ) {
  75.    636                        if (i == 0) {
  76.    637                                while (cpu >= 0 && !CPU_ISSET(cpu, &cpumask))
  77.    638                                        cpu--;
  78.    639                                if (cpu < 0)
  79.    640                                        break;
  80.    641                                child = NULL;
  81.    642                        } else
  82.    643                                child = &cg->cg_child[i - 1];
  83.    644       
  84. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  85.    647                        if (match & CPU_SEARCH_HIGHEST)
  86.    648                                hgroup.cs_cpu = -1;
  87.    649                        if (child) {                        /* Handle child CPU group. */
  88.    650                                CPU_NAND(&cpumask, &child->cg_mask);
  89.    651                                switch (match) {
  90. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  91.    655                                case CPU_SEARCH_HIGHEST:
  92.    656                                        load = cpu_search_highest(child, &hgroup);
  93.    657                                        break;
  94. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  95.    661                                }
  96.    662                        } else {                        /* Handle child CPU. */
  97.    663                                tdq = TDQ_CPU(cpu);
  98.    664                                load = tdq->tdq_load * 256;
  99.    665                                rndptr = DPCPU_PTR(randomval);
  100.    666                                rnd = (*rndptr = *rndptr * 69069 + 5) >> 26;
  101. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  102.    678                                if (match & CPU_SEARCH_HIGHEST)
  103.    679                                        if (tdq->tdq_load >= hgroup.cs_limit &&
  104.    680                                            tdq->tdq_transferable &&
  105.    681                                            CPU_ISSET(cpu, &hgroup.cs_mask)) {
  106.    682                                                hgroup.cs_cpu = cpu;
  107.    683                                                hgroup.cs_load = load - rnd;
  108.    684                                        }
  109.    685                        }
  110. /*************************************************************************************************
  111. * cpu_search函数检查完group[2]完成后:
  112.   
  113.    686:递增total。

  114.    698-705:变量high指向的struct cpu_search对象包含了group[2]中运行队列负载最高cpu的
  115.             logical cpu id及其运行队列的负载。

  116.    706-711:执行if语句前child为&group[2],i = 2,cpumask的编码为11110000
  117.             执行if语句后i = 1。

  118.    此时进行下一次for循环,将调用函数cpu_search检查group[1].


  119.    cpu_search函数检查完group[1]完成后:
  120.   
  121.    686:递增total。

  122.    698-705:变量high指向的struct cpu_search对象包含了group[1]和group[2]中运行队列负载最高cpu的
  123.             logical cpu id及其运行队列的负载。

  124.    706-711:执行if语句前child为&group[2],i = 1,cpumask的编码为00000000
  125.             执行if语句后i = 0。

  126.    此时708-709行就直接跳出了for循环。
  127. ************************************/
  128.    686                        total += load;
  129.    687       
  130. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  131.    698                        if (match & CPU_SEARCH_HIGHEST)
  132.    699                                if (hgroup.cs_cpu >= 0 &&
  133.    700                                    (load > hload ||
  134.    701                                     (load == hload && hgroup.cs_load > high->cs_load))) {
  135.    702                                        hload = load;
  136.    703                                        high->cs_cpu = hgroup.cs_cpu;
  137.    704                                        high->cs_load = hgroup.cs_load;
  138.    705                                }
  139.    706                        if (child) {
  140.    707                                i--;
  141.    708                                if (i == 0 && CPU_EMPTY(&cpumask))
  142.    709                                        break;
  143.    710                        } else
  144.    711                                cpu--;
  145.    712                }
  146.    713                return (total);
  147.    714        }
复制代码
[检查child cpu_group-调用函数cpu_search]:
  1. /****************************************************************************
  2. * 检查group[2]:
  3.    参数描述:
  4.    cg:&group[2]

  5.    low:NULL。

  6.    high:类型为struct cpu_search的数据对象,各成员如下:
  7.          high.cs_cpu = -1;
  8.          high.cs_mask = mask; // 11111111
  9.          high.cs_limit = minload;// 1

  10.    match:CPU_SEARCH_HIGHEST


  11.    检查group[1]:
  12.    参数描述:
  13.    cg:&group[1]

  14.    low:NULL。

  15.    high:类型为struct cpu_search的数据对象,各成员如下:
  16.          high.cs_cpu = -1;
  17.          high.cs_mask = mask; // 11111111
  18.          high.cs_limit = minload;// 1

  19.    match:CPU_SEARCH_HIGHEST

  20.    检查group[2],当函数cpu_search返回时,high指向的struct cpu_search对象
  21.    中包含了group[2]中负载最高cpu的logical cpu id和相应运行队列的负载。
  22.    函数的返回值为group[2]中cpu运行队列的总负载。


  23.    检查group[1],当函数cpu_search返回时,high指向的struct cpu_search对象
  24.    中包含了group[1]中负载最高cpu的logical cpu id和相应运行队列的负载。
  25.    函数的返回值为group[1]中cpu运行队列的总负载。
  26. ******************************************/
  27.    612        static __inline int
  28.    613        cpu_search(const struct cpu_group *cg, struct cpu_search *low,
  29.    614            struct cpu_search *high, const int match)
  30.    615        {
  31. /****************************************************************************
  32. * 局部变量描述:
  33.    lgroup:检查负载最低的cpu时使用。
  34.    hgroup:检查负载最低的cpu时使用
  35.    cpumask:cpu位图。
  36.    child:指向child cpu_group。
  37.    tdq:指向相应cpu的运行队列。
  38.    cpu:相应cpu的logical cpu id。
  39.    i:child cpu_group的数目。
  40.    hload:cpu的最高负载。
  41.    load:
  42.    total:总负载。
  43.    rnd,*rndptr:一个随机数值,不明白其含义,但是不影响这里的分析,众会员
  44.                  知道的话请及时联系啊。
  45. *************************************/
  46.    616                struct cpu_search lgroup;
  47.    617                struct cpu_search hgroup;
  48.    618                cpuset_t cpumask;
  49.    619                struct cpu_group *child;
  50.    620                struct tdq *tdq;
  51.    621                int cpu, i, hload, lload, load, total, rnd, *rndptr;
  52.    622       
  53. /**************************************************************************
  54. * 检查group[2]:
  55.    cpumask:此时的编码为00001111.

  56.    检查group[1]:
  57.    cpumask:此时的编码为11110000.   
  58. *******************************************/
  59.    623                total = 0;
  60.    624                cpumask = cg->cg_mask;
  61. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  62.    629                if (match & CPU_SEARCH_HIGHEST) {
  63.    630                        hload = INT_MIN;
  64.    631                        hgroup = *high;
  65.    632                }
  66.    633
  67. /***********************************************************************************
  68. * 检查group[2]:  
  69.    mp_maxid:
  70.    Max CPU ID,初始化时被设置为mp_maxid = mp_ncpus - 1;  被初始化为7.

  71.    635-712:之间的for循环执行四次,检查child cpu_group,即group[2]中包含的cpu上运行
  72.             队列的负载。

  73.    第一次for循环:
  74.    i = 0,cpu = 7
  75.    
  76.    第二次for循环:
  77.    i = 0,cpu = 6

  78.    第三次for循环:
  79.    i = 0,cpu = 5

  80.    第四次for循环:
  81.    i = 0,cpu = 4

  82.    636-643:执行if语句,因为group[2]没有child cpu_group,所以child为NULL。

  83.    637-638:跳过不属于group[2]中包含的cpu。

  84.    639-640:group[2]中的cpu已检查完毕,执行跳出for循环的操作。

  85.    649-685:这里将执行else语句,检查相应cpu运行队列的负载。

  86.    
  87.    检查group[1]:  
  88.    mp_maxid:
  89.    Max CPU ID,初始化时被设置为mp_maxid = mp_ncpus - 1;  被初始化为7.

  90.    635-712:之间的for循环执行四次,检查child cpu_group,即group[1]中包含的cpu上运行
  91.             队列的负载。

  92.    第一次for循环:
  93.    i = 0,cpu = 3
  94.    
  95.    第二次for循环:
  96.    i = 0,cpu = 2

  97.    第三次for循环:
  98.    i = 0,cpu = 1

  99.    第四次for循环:
  100.    i = 0,cpu = 0

  101.    从上面可以看出,每个cpu_group中的cpu都要被检查,但是下面678-683之间的宏CPU_ISSET
  102.    会再次将cpu限制在一个特定的cpu集合中。

  103.    636-643:执行if语句,因为group[1]没有child cpu_group,所以child为NULL。

  104.    637-638:跳过不属于group[1]中包含的cpu。

  105.    639-640:group[1]中的cpu已检查完毕,执行跳出for循环的操作。

  106.    649-685:这里将执行else语句,检查相应cpu运行队列的负载。
  107.    
  108. *************************************************/         
  109.    634                /* Iterate through the child CPU groups and then remaining CPUs. */
  110.    635                for (i = cg->cg_children, cpu = mp_maxid; i >= 0; ) {
  111.    636                        if (i == 0) {
  112.    637                                while (cpu >= 0 && !CPU_ISSET(cpu, &cpumask))
  113.    638                                        cpu--;
  114.    639                                if (cpu < 0)
  115.    640                                        break;
  116.    641                                child = NULL;
  117.    642                        } else
  118.    643                                child = &cg->cg_child[i - 1];
  119.    644       
  120. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  121.    647                        if (match & CPU_SEARCH_HIGHEST)
  122.    648                                hgroup.cs_cpu = -1;
  123.    649                        if (child) {                        /* Handle child CPU group. */
  124.    650                                CPU_NAND(&cpumask, &child->cg_mask);
  125.    651                                switch (match) {
  126. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  127.    655                                case CPU_SEARCH_HIGHEST:
  128.    656                                        load = cpu_search_highest(child, &hgroup);
  129.    657                                        break;
  130. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  131.    661                                }
  132.    662                        } else {
  133. /**********************************************************************************
  134. * tdq_load:对应cpu运行队列的负载,当把一个thread添加到struct tdq中三个运行
  135.              队列中的一个时,就会递增tdq_load成员,该成员同时也用来
  136.              选择运行队列负载最高和最低的CPU。

  137.    tdq_transferable: 一个计数器,相应cpu运行队列中可迁移线程的数目。在函数
  138.                      tdq_runq_add中递增。

  139.    663-684:检查相应cpu运行队列上的负载, Handle child CPU.
  140.    
  141.    663:tdq为&tdq_cpu[cpu]。

  142.    665-666:更新一个每cpu变量randomval。

  143.    678-684:将当前检查cpu运行队列的负载即logical cpu id保存到局部变量hgroup中。
  144.             从这里可以看出,上面636-641之间的while循环将cpu限定在相应的cpu_group中
  145.             ,这里的CPU_ISSET宏再次将cpu限制在所要检查的特定cpu集合中。
  146.             在一般情况下,只有当相应cpu运行队列中可迁移的thread数目非零时,
  147.             变量hgroup中才包含有意义的值。

  148.    686:递增total。
  149. ***************************************/
  150.    663                                tdq = TDQ_CPU(cpu);
  151.    664                                load = tdq->tdq_load * 256;
  152.    665                                rndptr = DPCPU_PTR(randomval);
  153.    666                                rnd = (*rndptr = *rndptr * 69069 + 5) >> 26;
  154. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  155.    678                                if (match & CPU_SEARCH_HIGHEST)
  156.    679                                        if (tdq->tdq_load >= hgroup.cs_limit &&
  157.    680                                            tdq->tdq_transferable &&
  158.    681                                            CPU_ISSET(cpu, &hgroup.cs_mask)) {
  159.    682                                                hgroup.cs_cpu = cpu;
  160.    683                                                hgroup.cs_load = load - rnd;
  161.    684                                        }
  162.    685                        }
  163.    686                        total += load;
  164.    687       
  165. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  166. /*********************************************************************************
  167. * 698-705:
  168.    变量high指向的struct cpu_search对象始终包含的是当前cpu_group中运行队列负载
  169.    最高cpu的logical cpu id及其运行队列的负载。
  170. **********************/
  171.    698                        if (match & CPU_SEARCH_HIGHEST)
  172.    699                                if (hgroup.cs_cpu >= 0 &&
  173.    700                                    (load > hload ||
  174.    701                                     (load == hload && hgroup.cs_load > high->cs_load))) {
  175.    702                                        hload = load;
  176.    703                                        high->cs_cpu = hgroup.cs_cpu;
  177.    704                                        high->cs_load = hgroup.cs_load;
  178.    705                                }
  179. /********************************************************************************
  180. * 706-711:
  181.    这里将执行else语句,递减cpu.
  182. ***********************************/
  183.    706                        if (child) {
  184.    707                                i--;
  185.    708                                if (i == 0 && CPU_EMPTY(&cpumask))
  186.    709                                        break;
  187.    710                        } else
  188.    711                                cpu--;
  189.    712                }
  190.    713                return (total);
  191.    714        }
复制代码

论坛徽章:
0
发表于 2015-04-17 12:42 |显示全部楼层
太好了!对楼主赞一个 !!!!!!!

论坛徽章:
0
发表于 2015-04-28 20:07 |显示全部楼层
学习学习!               
您需要登录后才可以回帖 登录 | 注册

本版积分规则

久等啦!10张门票开启你的DTCC2017之旅

2017中国数据库技术大会将于2017年5月11-13日如约而至,本届大会以“数据驱动•价值发现”为主题,共设定2大主场和21个技术专场,云集海内外120+位技术大牛,共同探讨Oracle、MySQL、NoSQL、云端数据库、区块链、深度学习等领域的前瞻性热点话题。
即日起,填写DTCC2017会前调查问卷,即有机会赢取价值2600元的大会门票1张!仅限10张!
----------------------------------------
活动截止时间:2017年5月5日统一公布

问卷入口>>
  

北京皓辰网域网络信息技术有限公司. 版权所有 京ICP证:060528号 北京市公安局海淀分局网监中心备案编号:1101082001
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP