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

ChinaUnix.net

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

[FreeBSD] freebsd9.2-ULE线程调度-保持cpu运行队列间的平衡-sched_balance函数 [复制链接]

论坛徽章:
0
发表于 2014-06-29 23:02 |显示全部楼层
本帖最后由 71v5 于 2014-06-30 01:33 编辑

从帖子"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.                    static struct tdq       *balance_tdq;
  17.                    static int balance_ticks;

  18.                    2190-2193:
  19.                    在ULE调度程序初始化阶段,BSP会将balance_tdq设置为BSP对应的struct tdq
  20.                    数据对象的地址。
  21.                   
  22.                    balance_ticks为调用sched_balance函数在系统中cpu的运行队列间迁移线程
  23.                    的周期,在ULE调度程序初始化阶段设置,具体值是多少应该没什么意义:
  24.                    balance_interval默认值为128.
  25.                    balance_ticks = max(balance_interval / 2, 1);
  26.                    balance_ticks += random() % balance_interval;

  27.                    当balance_ticks为零0时,函数sched_balance就要保持系统中cpu运行队列
  28.                    间的平衡。

  29.                    只在BSP上执行。
  30.   2189                 *************/
  31.   2190                if (balance_tdq == tdq) {
  32.   2191                        if (balance_ticks && --balance_ticks == 0)
  33.   2192                                sched_balance();
  34.   2193                }
  35. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  36. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  37.        }
复制代码
这里为了简化分析,做下面的假设:
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.    非零:运行队列负载最低的cpu的logical cpu id。

  20.    其实只要这些参数的含义弄明白,下来就是就是一些简单的分析过程了。
  21. ************************************/
  22.    744        static inline int
  23.    745        sched_lowest(const struct cpu_group *cg, cpuset_t mask, int pri, int maxload,
  24.    746            int prefer)
  25.    747        {
  26.    748                struct cpu_search low;
  27.    749       
  28.    750                low.cs_cpu = -1;
  29.    751                low.cs_prefer = prefer;
  30.    752                low.cs_mask = mask;
  31.    753                low.cs_pri = pri;
  32.    754                low.cs_limit = maxload;
  33.    755                cpu_search_lowest(cg, &low);
  34.    756                return low.cs_cpu;
  35.    757        }
  36.    716  /*
  37.    717   * cpu_search instantiations must pass constants to maintain the inline
  38.    718   * optimization.
  39.    719   */
  40.    720  int
  41.    721  cpu_search_lowest(const struct cpu_group *cg, struct cpu_search *low)
  42.    722  {
  43.    723          return cpu_search(cg, low, NULL, CPU_SEARCH_LOWEST);
  44.    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.    851-852:重新计算balance_ticks。
  18.    
  19.    853:如果不是SMP系统或者变量rebalance为0,就直接返回,因为没有必要进行
  20.         cpu运行队列的再平衡操作。
  21.    
  22.    855:因为只有BSP执行sched_balance函数,而BSP的logical cpu id为0,所以
  23.         这里tdq的值就为&tdq_cpu[0]。
  24.    
  25.    857:以参数cpu_top调用函数sched_balance_group
  26.         参数cpu_top请参考帖子"freebsd9.2-ULE线程调度-创建数据结构来描述CPU拓扑信息"
  27. **************************/
  28.    851                balance_ticks = max(balance_interval / 2, 1);
  29.    852                balance_ticks += random() % balance_interval;
  30.    853                if (smp_started == 0 || rebalance == 0)
  31.    854                        return;
  32.    855                tdq = TDQ_SELF();
  33.    856                TDQ_UNLOCK(tdq);
  34.    857                sched_balance_group(cpu_top);
  35.    858                TDQ_LOCK(tdq);
  36.    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.    lmask:类似于hamsk,在检查运行队列负载最低的cpu时使用。

  9.    high:运行队列负载最高的cpu的logical cpu id。
  10.    low:运行队列负载最低的cpu的logical cpu id。
  11. **************************************/
  12.    801                cpuset_t hmask, lmask;
  13.    802                int high, low, anylow;
  14.    803       
  15. /***************************************************************************************************
  16. * 804:for循环前,将变量hmask的bit位全设置为1,表示检查系统中全部的cpu。

  17.    805-839:一个无限for循环,当下面任何一个条件满足时,中止for循环:
  18.    条件1:函数sched_highest返回值为-1,在一般情况下,如果返回值为-1,就表示所
  19.           检查cpu运行队列中可迁移thread的数目为0。

  20.    条件2:变量lmask中的bit位全部为0,表示没有要检查的cpu。

  21.    条件3:anylow变量为1,并且函数sched_lowest返回值为-1。

  22.    810:如果执行到这里,就表示函数sched_highest执行成功,这里假设函数sched_highest
  23.         返回值为6(high值为6),即cpu6的运行队列tdq_cpu[6]的负载最高,宏CPU_CLR将变量hmask中的bit6
  24.         清零,这就意味着下一次调用sched_highest函数时将不会检查cpu6。

  25.    811:将更新后的hmask变量copy到lmask变量中,函数sched_lowest将检查lmask变量中包含
  26.         的cpu运行队列的负载,选择一个负载最低的cpu。

  27.    813-815:当变量lmask为空时,即变量lmask中的bit位全为零,表示没有要检查的cpu,此时
  28.             调用函数sched_lowest没有意义,跳出for循环。

  29.    817-818:调用函数sched_lowest确定cpu运行队列负载最低的cpu,这里假设函数sched_lowest的返回值
  30.             为2(low值为2),即cpu2的运行队列tdq_cpu[2]的负载最低。

  31.    820-821:对应上面的条件3。
  32.   
  33.    823-824:当函数sched_lowest返回-1时,此时继续for循环,如果期间一些thread意外终止或者
  34.             主动执行了exit操作,那么下一次检查时,sched_lowest函数有可能返回有意义的值。

  35.    825-828:执行到这里话,high为负载最高的cpu,low为负载最低的cpu,此时函数
  36.             sched_balance_pair执行一个将thread从运行队列tdq_cpu[6]迁移到运行队列tdq_cpu[2]
  37.             中的操作,以下面的形式调用函数:
  38.             sched_balance_pair(&tdq_cpu[6], &tdq_cpu[2]);  
  39.    
  40.    826-828:如果函数sched_balance_pair返回1,将变量hmask中的bit2清零,这意味着下次for循环时将
  41.             不会检查cpu6和cpu2。

  42.    830-837:如果函数sched_balance_pair返回0,此时将变量lmask中的bit2清零,同时将变量anylow
  43.             设置为0,跳转到nextlow处继续执行,继续确定下一个运行队列负载最低的cpu。
  44. ***********************/
  45.    804                CPU_FILL(&hmask);
  46.    805                for (;;) {
  47.    806                        high = sched_highest(cg, hmask, 1);
  48.    807                        /* Stop if there is no more CPU with transferrable threads. */
  49.    808                        if (high == -1)
  50.    809                                break;
  51.    810                        CPU_CLR(high, &hmask);
  52.    811                        CPU_COPY(&hmask, &lmask);
  53.    812                        /* Stop if there is no more CPU left for low. */
  54.    813                        if (CPU_EMPTY(&lmask))
  55.    814                                break;
  56.    815                        anylow = 1;
  57.    816        nextlow:
  58.    817                        low = sched_lowest(cg, lmask, -1,
  59.    818                            TDQ_CPU(high)->tdq_load - 1, high);
  60.    819                        /* Stop if we looked well and found no less loaded CPU. */
  61.    820                        if (anylow && low == -1)
  62.    821                                break;
  63.    822                        /* Go to next high if we found no less loaded CPU. */
  64.    823                        if (low == -1)
  65.    824                                continue;
  66.    825                        /* Transfer thread from high to low. */
  67.    826                        if (sched_balance_pair(TDQ_CPU(high), TDQ_CPU(low))) {
  68.    827                                /* CPU that got thread can no longer be a donor. */
  69.    828                                CPU_CLR(low, &hmask);
  70.    829                        } else {
  71.    830                                /*
  72.    831                                 * If failed, then there is no threads on high
  73.    832                                 * that can run on this low. Drop low from low
  74.    833                                 * mask and look for different one.
  75.    834                                 */
  76.    835                                CPU_CLR(low, &lmask);
  77.    836                                anylow = 0;
  78.    837                                goto nextlow;
  79.    838                        }
  80.    839                }
  81.    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.    sched_balance_pair函数返回值的含义请参考一下下面对tdq_move函数
  8.    返回值的分析。
  9. ****************************/
  10.    889        static int
  11.    890        sched_balance_pair(struct tdq *high, struct tdq *low)
  12.    891        {
  13. /*********************************************************************************
  14. * 局部变量描述:
  15.    moved:可以迁移的thread的数目。
  16.    cpu:运行队列low对应的cpu的logical cpu id。

  17.    901-912:再次检查迁移条件是否满足,tdq_move函数见下面的分析。
  18.   
  19.    一般情况下if语句的前两个条件都满足,此时:

  20.    在函数tdq_move返回1时,检查是否需要向运行队列low对应的cpu发出一个处理器间
  21.    中断(IPI),后续有时间的话,将和大家分享一下处理器间中断的发送过程以及相关
  22.    的处理。
  23. *******************************************/  
  24.    892                int moved;
  25.    893                int cpu;
  26.    894       
  27.    895                tdq_lock_pair(high, low);
  28.    896                moved = 0;
  29.    897                /*
  30.    898                 * Determine what the imbalance is and then adjust that to how many
  31.    899                 * threads we actually have to give up (transferable).
  32.    900                 */
  33.    901                if (high->tdq_transferable != 0 && high->tdq_load > low->tdq_load &&
  34.    902                    (moved = tdq_move(high, low)) > 0) {
  35.    903                        /*
  36.    904                         * In case the target isn't the current cpu IPI it to force a
  37.    905                         * reschedule with the new workload.
  38.    906                         */
  39.    907                        cpu = TDQ_ID(low);
  40.    908                        sched_pin();
  41.    909                        if (cpu != PCPU_GET(cpuid))
  42.    910                                ipi_cpu(cpu, IPI_PREEMPT);
  43.    911                        sched_unpin();
  44.    912                }
  45.    913                tdq_unlock_pair(high, low);
  46.    914                return (moved);
  47.    915        }
复制代码
[函数tdq_move]:
  1. /*****************************************************************
  2. * Move a thread from one thread queue to another.
  3. *
  4.    参数描述:
  5.    from:线程将要从运行队列from中移除。
  6.    to:线程将要添加到运行队列to中。

  7.    根据函数的描述,tdq_move一次将只迁移一个thread,太可怜了吧,
  8.    之前看linux-2.6.18线程调度这块实现时,都可以迁移一定数目的
  9.    thread了,不过bsd开发者可能有他们自己的想法,这里就是简要
  10.    的点评一下。

  11.    下面简要的分析一下tdq_move函数,后续有时间将和大家分享一下
  12.    如何将一个thread添加到运行队列中,以及如何将一个thread从一个
  13.    运行队列中移除。

  14.    这里只需要明白返回值的含义:
  15.    
  16.    0:运行队列from中的thread不能迁移到运行队列to中。

  17.    1:成功将一个thread从运行队列from迁移到运行队列to中。

  18. ************************/
  19.    920        static int
  20.    921        tdq_move(struct tdq *from, struct tdq *to)
  21.    922        {
  22.    923                struct td_sched *ts;
  23.    924                struct thread *td;
  24.    925                struct tdq *tdq;
  25.    926                int cpu;
  26.    927       
  27.    928                TDQ_LOCK_ASSERT(from, MA_OWNED);
  28.    929                TDQ_LOCK_ASSERT(to, MA_OWNED);
  29.    930       
  30. /******************************************************************
  31. * cpu:运行队列to对应的cpu的logical cpu id。

  32.    描述thread的struct thread对象有下面一个成员:
  33.    td_cpuset:cpu掩码的集合,即CPU affinity sets,一般情况下
  34.               该字段的值从父进程继承,除非调用cpuset系统调用
  35.               进行修改,即线程thread只能在在td_cpuset中的cpu
  36.               上运行或者说成线程thread只能被添加到td_cpuset中的cpu
  37.               的运行队列中。
  38.    函数tdq_steal依次检查tdq_realtime,tdq_timeshare,tdq_idle
  39.    队列中的全部thread,如果描述每个thread的struct thread对象
  40.    中的td_cpuset成员标识的cpu集合中都不包括运行队列to对应的cpu,
  41.    那么函数tdq_steal将返回NULL,此时tdq_move函数返回0.
  42.    否则函数tdq_steal将返回描述一个线程的struct thread对象,此时
  43.    此时tdq_move函数返回1.

  44.    941-947:将线程td从运行队列from中移除,同时将线程td添加到
  45.             运行队列to中,以及更新线程td对应的struct thread对象
  46.             中的相关成员。  
  47. ******************************/   
  48.    931                tdq = from;
  49.    932                cpu = TDQ_ID(to);
  50.    933                td = tdq_steal(tdq, cpu);
  51.    934                if (td == NULL)
  52.    935                        return (0);
  53.    936                ts = td->td_sched;
  54.    937                /*
  55.    938                 * Although the run queue is locked the thread may be blocked.  Lock
  56.    939                 * it to clear this and acquire the run-queue lock.
  57.    940                 */
  58.    941                thread_lock(td);
  59.    942                /* Drop recursive lock on from acquired via thread_lock(). */
  60.    943                TDQ_UNLOCK(from);
  61.    944                sched_rem(td);
  62.    945                ts->ts_cpu = cpu;
  63.    946                td->td_lock = TDQ_LOCKPTR(to);
  64.    947                tdq_add(to, td, SRQ_YIELDING);
  65.    948                return (1);
  66.    949        }
复制代码

论坛徽章:
0
发表于 2015-04-13 18:31 |显示全部楼层
支持一下辛苦的楼主~顶了!

论坛徽章:
0
发表于 2015-04-25 15:34 |显示全部楼层
我老妈很喜欢李宇春呢。。。。。。

论坛徽章:
0
发表于 2015-04-30 17:03 |显示全部楼层
林子大了什么鸟没有啊?祝踩的死全家!!!!
您需要登录后才可以回帖 登录 | 注册

本版积分规则

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP