freebsd9.2-ULE线程调度-确定cpu运行队列负载最高的cpu-sched_highest函数
本帖最后由 71v5 于 2014-06-29 22:44 编辑-确定系统中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中的cg_mask成员，其编码为11110000，表示该group中包含的cpu的logical id为0，1，2，3。
对于group中的cg_mask成员，其编码为00001111，表示该group中包含的cpu的logical id为4，5，6，7。
2：因为不管是确定负载最高的cpu还是负载最低的cpu，最终都是通过函数cpu_search来操作的，所以在cpu_search函数中
略去了一些不相关的操作，比如检查负载最高的cpu时，就略去了和检查负载最低的cpu相关的代码，略去的代码以下面
的"。。。。。。。。。。。。。。。。。。。"标识。
3：cpu运行队列分别为tdq_cpu，tdq_cpu，tdq_cpu，tdq_cpu等
[数据类型struct cpu_search]：/************************************************************************
* struct cpu_search类型的数据对象在函数cpu_search中使用，用来保存
查找的结果。
cs_mask：一个cpu掩码位图，位图中设置为1的bit位对应的cpu将在
函数cpu_search中检查其负载。
cs_prefer：在检查cpu运行队列负载最低cpu的时候使用，一般设置为
上一次调用函数sched_highest返回的cpu的logical cpu id，当所
检查的cpu和cs_prefer相同时，将cs_prefer运行队列的负载减去
一个常数。
cs_limit：一个负载阈值。
cs_cpu：cpu运行队列负载最低或者最高的cpu对应的logical cpu id。
cs_load：相应的负载。
cs_pri：一般情况下，可以忽略。
*********************************/
577 struct cpu_search {
578 cpuset_t cs_mask;
579 u_int cs_prefer;
580 int cs_pri; /* Min priority for low. */
581 int cs_limit; /* Max load for low, min load for high. */
582 int cs_cpu;
583 int cs_load;
584 };
/************************************************************
* 传递给cpu_search函数的标志，含义如下：
CPU_SEARCH_LOWEST：只确定cpu运行队列负载最低的cpu。
CPU_SEARCH_HIGHEST：只确定cpu运行队列负载最高的cpu。
CPU_SEARCH_BOTH：同时确定cpu运行队列负载最高和最低的cpu。
*****************************/
586 #define CPU_SEARCH_LOWEST 0x1
587 #define CPU_SEARCH_HIGHEST 0x2
588 #define CPU_SEARCH_BOTH (CPU_SEARCH_LOWEST|CPU_SEARCH_HIGHEST)：/********************************************************************************************
* Find the cpu with the highest load via the highest loaded path.
一般情况下，在确定系统中cpu运行队列负载最高的cpu时，会以下面的参数调用sched_highest函数：
cg：cpu_top。
mask：类型为cpuset_t的cpu位图，这里的编码为11111111，在随后从sched_balance_group函数中
的for循环中继续调用sched_highest函数时，mask的值会改变，不过mask中bit位为1的cpu
都要被检查。
minload：这里的值为1。
该函数实际上使用参数mask，minload初始化一个struct cpu_serach类型的数据对象，
然后再调用cpu_search_highest函数，该函数为函数cpu_search的简单封装。
函数sched_highest返回值如果为-1：在一般情况下，如果返回值为-1，就表示所检查cpu运行队列
中可迁移thread的数目为0.
函数sched_highest返回其它值：相应cpu的logical cpu id，该cpu运行队列中可迁移thread的数目
非零，并且负载最高。
**************************************/
762 static inline int
763 sched_highest(const struct cpu_group *cg, cpuset_t mask, int minload)
764 {
765 struct cpu_search high;
766
767 high.cs_cpu = -1;
768 high.cs_mask = mask;
769 high.cs_limit = minload;
770 cpu_search_highest(cg, &high);
771 return high.cs_cpu;
772 }
726 int
727 cpu_search_highest(const struct cpu_group *cg, struct cpu_search *high)
728 {
729 return cpu_search(cg, NULL, high, CPU_SEARCH_HIGHEST);
730 }[函数cpu_search]-该函数实际上是一个递归过程，根据之前的假定，递归深度为1，这里分检查cpu_top和检查child cpu_group两种情况来分析该函数，因为
这两种情况cpu_search函数的执行流程不一样。
[检查cpu_top-调用函数cpu_search]：/***********************************************************************************************
* 参数描述:
cg：cpu_top
low：NULL。
high：类型为struct cpu_search的数据对象，各成员如下：
high.cs_cpu = -1;
high.cs_mask = mask; // 11111111
high.cs_limit = minload;// 1
match：CPU_SEARCH_HIGHEST
当函数cpu_search返回时，high指向的struct cpu_search对象中包含了group和group中
cpu运行队列负载最高cpu的logical cpu id和相应运行队列的负载。
函数的返回值为group和group中cpu运行队列的总负载。
******************************************/
612 static __inline int
613 cpu_search(const struct cpu_group *cg, struct cpu_search *low,
614 struct cpu_search *high, const int match)
615 {
/****************************************************************************
* 局部变量描述：
lgroup：检查负载最低的cpu时使用。
hgroup：检查负载最低的cpu时使用
cpumask：cpu位图。
child：指向child cpu_group。
tdq：指向相应cpu的运行队列。
cpu：相应cpu的logical cpu id。
i：child cpu_group的数目。
hload：cpu的最高负载。
load：
total：总负载。
rnd，*rndptr：一个随机数值，不明白其含义，但是不影响这里的分析，众会员
知道的话请及时联系啊。
*************************************/
616 struct cpu_search lgroup;
617 struct cpu_search hgroup;
618 cpuset_t cpumask;
619 struct cpu_group *child;
620 struct tdq *tdq;
621 int cpu, i, hload, lload, load, total, rnd, *rndptr;
622
/**************************************************************************
* cpumask：此时的编码为11111111.
*****************/
623 total = 0;
624 cpumask = cg->cg_mask;
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
629 if (match & CPU_SEARCH_HIGHEST) {
630 hload = INT_MIN;
631 hgroup = *high;
632 }
633
/***********************************************************************************
* mp_maxid：
Max CPU ID，初始化时被设置为mp_maxid = mp_ncpus - 1;被初始化为7.
635-712：之间的for循环执行两次，每次循环都检查一个child cpu_group。
第一次for循环：调用函数cpu_search检查group
i = 2，cpu = 7；
636-643：执行else语句，child为&group；
649-685：这里将执行if语句，即将调用函数cpu_search检查group.
650：group中的cg_mask成员编码为00001111，CPU_NAND执行完后，
cpumask的编码为11110000。
第二次for循环：调用函数cpu_search检查group.
i = 1，cpu = 7.
636-643：执行else语句，child为&group；
649-685：这里将执行if语句，即将调用函数cpu_search检查group.
650：group中的cg_mask成员编码为11110000，CPU_NAND执行完后，
cpumask的编码为00000000。
*************************************************/
634 /* Iterate through the child CPU groups and then remaining CPUs. */
635 for (i = cg->cg_children, cpu = mp_maxid; i >= 0; ) {
636 if (i == 0) {
637 while (cpu >= 0 && !CPU_ISSET(cpu, &cpumask))
638 cpu--;
639 if (cpu < 0)
640 break;
641 child = NULL;
642 } else
643 child = &cg->cg_child;
644
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
647 if (match & CPU_SEARCH_HIGHEST)
648 hgroup.cs_cpu = -1;
649 if (child) { /* Handle child CPU group. */
650 CPU_NAND(&cpumask, &child->cg_mask);
651 switch (match) {
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
655 case CPU_SEARCH_HIGHEST:
656 load = cpu_search_highest(child, &hgroup);
657 break;
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
661 }
662 } else { /* Handle child CPU. */
663 tdq = TDQ_CPU(cpu);
664 load = tdq->tdq_load * 256;
665 rndptr = DPCPU_PTR(randomval);
666 rnd = (*rndptr = *rndptr * 69069 + 5) >> 26;
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
678 if (match & CPU_SEARCH_HIGHEST)
679 if (tdq->tdq_load >= hgroup.cs_limit &&
680 tdq->tdq_transferable &&
681 CPU_ISSET(cpu, &hgroup.cs_mask)) {
682 hgroup.cs_cpu = cpu;
683 hgroup.cs_load = load - rnd;
684 }
685 }
/*************************************************************************************************
* cpu_search函数检查完group完成后：
686：递增total。
698-705：变量high指向的struct cpu_search对象包含了group中运行队列负载最高cpu的
logical cpu id及其运行队列的负载。
706-711：执行if语句前child为&group，i = 2，cpumask的编码为11110000
执行if语句后i = 1。
此时进行下一次for循环，将调用函数cpu_search检查group.
cpu_search函数检查完group完成后：
686：递增total。
698-705：变量high指向的struct cpu_search对象包含了group和group中运行队列负载最高cpu的
logical cpu id及其运行队列的负载。
706-711：执行if语句前child为&group，i = 1，cpumask的编码为00000000
执行if语句后i = 0。
此时708-709行就直接跳出了for循环。
************************************/
686 total += load;
687
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
698 if (match & CPU_SEARCH_HIGHEST)
699 if (hgroup.cs_cpu >= 0 &&
700 (load > hload ||
701 (load == hload && hgroup.cs_load > high->cs_load))) {
702 hload = load;
703 high->cs_cpu = hgroup.cs_cpu;
704 high->cs_load = hgroup.cs_load;
705 }
706 if (child) {
707 i--;
708 if (i == 0 && CPU_EMPTY(&cpumask))
709 break;
710 } else
711 cpu--;
712 }
713 return (total);
714 }
[检查child cpu_group-调用函数cpu_search]：/****************************************************************************
* 检查group：
参数描述:
cg：&group
low：NULL。
high：类型为struct cpu_search的数据对象，各成员如下：
high.cs_cpu = -1;
high.cs_mask = mask; // 11111111
high.cs_limit = minload;// 1
match：CPU_SEARCH_HIGHEST
检查group：
参数描述:
cg：&group
low：NULL。
high：类型为struct cpu_search的数据对象，各成员如下：
high.cs_cpu = -1;
high.cs_mask = mask; // 11111111
high.cs_limit = minload;// 1
match：CPU_SEARCH_HIGHEST
检查group，当函数cpu_search返回时，high指向的struct cpu_search对象
中包含了group中负载最高cpu的logical cpu id和相应运行队列的负载。
函数的返回值为group中cpu运行队列的总负载。
检查group，当函数cpu_search返回时，high指向的struct cpu_search对象
中包含了group中负载最高cpu的logical cpu id和相应运行队列的负载。
函数的返回值为group中cpu运行队列的总负载。
******************************************/
612 static __inline int
613 cpu_search(const struct cpu_group *cg, struct cpu_search *low,
614 struct cpu_search *high, const int match)
615 {
/****************************************************************************
* 局部变量描述：
lgroup：检查负载最低的cpu时使用。
hgroup：检查负载最低的cpu时使用
cpumask：cpu位图。
child：指向child cpu_group。
tdq：指向相应cpu的运行队列。
cpu：相应cpu的logical cpu id。
i：child cpu_group的数目。
hload：cpu的最高负载。
load：
total：总负载。
rnd，*rndptr：一个随机数值，不明白其含义，但是不影响这里的分析，众会员
知道的话请及时联系啊。
*************************************/
616 struct cpu_search lgroup;
617 struct cpu_search hgroup;
618 cpuset_t cpumask;
619 struct cpu_group *child;
620 struct tdq *tdq;
621 int cpu, i, hload, lload, load, total, rnd, *rndptr;
622
/**************************************************************************
* 检查group：
cpumask：此时的编码为00001111.
检查group：
cpumask：此时的编码为11110000.
*******************************************/
623 total = 0;
624 cpumask = cg->cg_mask;
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
629 if (match & CPU_SEARCH_HIGHEST) {
630 hload = INT_MIN;
631 hgroup = *high;
632 }
633
/***********************************************************************************
* 检查group：
mp_maxid：
Max CPU ID，初始化时被设置为mp_maxid = mp_ncpus - 1;被初始化为7.
635-712：之间的for循环执行四次，检查child cpu_group，即group中包含的cpu上运行
队列的负载。
第一次for循环：
i = 0，cpu = 7
第二次for循环：
i = 0，cpu = 6
第三次for循环：
i = 0，cpu = 5
第四次for循环：
i = 0，cpu = 4
636-643：执行if语句，因为group没有child cpu_group，所以child为NULL。
637-638：跳过不属于group中包含的cpu。
639-640：group中的cpu已检查完毕，执行跳出for循环的操作。
649-685：这里将执行else语句，检查相应cpu运行队列的负载。
检查group：
mp_maxid：
Max CPU ID，初始化时被设置为mp_maxid = mp_ncpus - 1;被初始化为7.
635-712：之间的for循环执行四次，检查child cpu_group，即group中包含的cpu上运行
队列的负载。
第一次for循环：
i = 0，cpu = 3
第二次for循环：
i = 0，cpu = 2
第三次for循环：
i = 0，cpu = 1
第四次for循环：
i = 0，cpu = 0
从上面可以看出，每个cpu_group中的cpu都要被检查，但是下面678-683之间的宏CPU_ISSET
会再次将cpu限制在一个特定的cpu集合中。
636-643：执行if语句，因为group没有child cpu_group，所以child为NULL。
637-638：跳过不属于group中包含的cpu。
639-640：group中的cpu已检查完毕，执行跳出for循环的操作。
649-685：这里将执行else语句，检查相应cpu运行队列的负载。
*************************************************/
634 /* Iterate through the child CPU groups and then remaining CPUs. */
635 for (i = cg->cg_children, cpu = mp_maxid; i >= 0; ) {
636 if (i == 0) {
637 while (cpu >= 0 && !CPU_ISSET(cpu, &cpumask))
638 cpu--;
639 if (cpu < 0)
640 break;
641 child = NULL;
642 } else
643 child = &cg->cg_child;
644
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
647 if (match & CPU_SEARCH_HIGHEST)
648 hgroup.cs_cpu = -1;
649 if (child) { /* Handle child CPU group. */
650 CPU_NAND(&cpumask, &child->cg_mask);
651 switch (match) {
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
655 case CPU_SEARCH_HIGHEST:
656 load = cpu_search_highest(child, &hgroup);
657 break;
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
661 }
662 } else {
/**********************************************************************************
* tdq_load：对应cpu运行队列的负载，当把一个thread添加到struct tdq中三个运行
队列中的一个时，就会递增tdq_load成员，该成员同时也用来
选择运行队列负载最高和最低的CPU。
tdq_transferable: 一个计数器，相应cpu运行队列中可迁移线程的数目。在函数
tdq_runq_add中递增。
663-684:检查相应cpu运行队列上的负载， Handle child CPU.
663：tdq为&tdq_cpu。
665-666:更新一个每cpu变量randomval。
678-684：将当前检查cpu运行队列的负载即logical cpu id保存到局部变量hgroup中。
从这里可以看出，上面636-641之间的while循环将cpu限定在相应的cpu_group中
，这里的CPU_ISSET宏再次将cpu限制在所要检查的特定cpu集合中。
在一般情况下，只有当相应cpu运行队列中可迁移的thread数目非零时，
变量hgroup中才包含有意义的值。
686：递增total。
***************************************/
663 tdq = TDQ_CPU(cpu);
664 load = tdq->tdq_load * 256;
665 rndptr = DPCPU_PTR(randomval);
666 rnd = (*rndptr = *rndptr * 69069 + 5) >> 26;
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
678 if (match & CPU_SEARCH_HIGHEST)
679 if (tdq->tdq_load >= hgroup.cs_limit &&
680 tdq->tdq_transferable &&
681 CPU_ISSET(cpu, &hgroup.cs_mask)) {
682 hgroup.cs_cpu = cpu;
683 hgroup.cs_load = load - rnd;
684 }
685 }
686 total += load;
687
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
/*********************************************************************************
* 698-705:
变量high指向的struct cpu_search对象始终包含的是当前cpu_group中运行队列负载
最高cpu的logical cpu id及其运行队列的负载。
**********************/
698 if (match & CPU_SEARCH_HIGHEST)
699 if (hgroup.cs_cpu >= 0 &&
700 (load > hload ||
701 (load == hload && hgroup.cs_load > high->cs_load))) {
702 hload = load;
703 high->cs_cpu = hgroup.cs_cpu;
704 high->cs_load = hgroup.cs_load;
705 }
/********************************************************************************
* 706-711：
这里将执行else语句，递减cpu.
***********************************/
706 if (child) {
707 i--;
708 if (i == 0 && CPU_EMPTY(&cpumask))
709 break;
710 } else
711 cpu--;
712 }
713 return (total);
714 } 太好了！对楼主赞一个 ！！！！！！！ 学习学习！
页:
[1]