- 论坛徽章:
- 0
|
本帖最后由 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]等
[数据类型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)
复制代码 [sched_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[1]和group[2]中
- cpu运行队列负载最高cpu的logical cpu id和相应运行队列的负载。
- 函数的返回值为group[2]和group[1]中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[2]
- i = 2,cpu = 7;
-
- 636-643:执行else语句,child为&group[2];
-
- 649-685:这里将执行if语句,即将调用函数cpu_search检查group[2].
- 650:group[2]中的cg_mask成员编码为00001111,CPU_NAND执行完后,
- cpumask的编码为11110000。
-
- 第二次for循环:调用函数cpu_search检查group[1].
- i = 1,cpu = 7.
- 636-643:执行else语句,child为&group[1];
-
- 649-685:这里将执行if语句,即将调用函数cpu_search检查group[1].
- 650:group[1]中的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[i - 1];
- 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[2]完成后:
-
- 686:递增total。
- 698-705:变量high指向的struct cpu_search对象包含了group[2]中运行队列负载最高cpu的
- logical cpu id及其运行队列的负载。
- 706-711:执行if语句前child为&group[2],i = 2,cpumask的编码为11110000
- 执行if语句后i = 1。
- 此时进行下一次for循环,将调用函数cpu_search检查group[1].
- cpu_search函数检查完group[1]完成后:
-
- 686:递增total。
- 698-705:变量high指向的struct cpu_search对象包含了group[1]和group[2]中运行队列负载最高cpu的
- logical cpu id及其运行队列的负载。
- 706-711:执行if语句前child为&group[2],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[2]:
- 参数描述:
- cg:&group[2]
- 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[1]:
- 参数描述:
- cg:&group[1]
- 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[2],当函数cpu_search返回时,high指向的struct cpu_search对象
- 中包含了group[2]中负载最高cpu的logical cpu id和相应运行队列的负载。
- 函数的返回值为group[2]中cpu运行队列的总负载。
- 检查group[1],当函数cpu_search返回时,high指向的struct cpu_search对象
- 中包含了group[1]中负载最高cpu的logical cpu id和相应运行队列的负载。
- 函数的返回值为group[1]中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[2]:
- cpumask:此时的编码为00001111.
- 检查group[1]:
- 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[2]:
- mp_maxid:
- Max CPU ID,初始化时被设置为mp_maxid = mp_ncpus - 1; 被初始化为7.
- 635-712:之间的for循环执行四次,检查child cpu_group,即group[2]中包含的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[2]没有child cpu_group,所以child为NULL。
- 637-638:跳过不属于group[2]中包含的cpu。
- 639-640:group[2]中的cpu已检查完毕,执行跳出for循环的操作。
- 649-685:这里将执行else语句,检查相应cpu运行队列的负载。
-
- 检查group[1]:
- mp_maxid:
- Max CPU ID,初始化时被设置为mp_maxid = mp_ncpus - 1; 被初始化为7.
- 635-712:之间的for循环执行四次,检查child cpu_group,即group[1]中包含的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[1]没有child cpu_group,所以child为NULL。
- 637-638:跳过不属于group[1]中包含的cpu。
- 639-640:group[1]中的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[i - 1];
- 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[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 }
复制代码 |
|