免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2663 | 回复: 0

[FreeBSD] freebsd9.2-ULE线程调度-数据结构浅析 [复制链接]

论坛徽章:
0
发表于 2014-06-24 20:53 |显示全部楼层
本帖最后由 71v5 于 2014-06-27 23:30 编辑

草图两张
02.jpg

05.jpg



下面数据结构成员的含义是结合源代码得出的,其中部分还没有明白其具体含义,以后会及时更新的,有错误的地方,望大家及时指出。

[struct td_sched数据对象]:
在线程创建过程中,thread_alloc函数为新线程分配struct thread对象,内核栈,同时还会分配struct td_sched类型的数据对象来描述线程调度方面的信息,
其实,struct td_sched类型的数据对象和struct thread类型的数据对象是一起从thread_zone标识的UMA区域中分配的,而且根据所选择的线程调度程序不同,
struct td_sched类型的数据对象定义也不同。

[ULE调度程序,对象大小为]:
  1.   2558  int
  2.   2559  sched_sizeof_thread(void)
  3.   2560  {
  4.   2561          return (sizeof(struct thread) + sizeof(struct td_sched));
  5.   2562  }
复制代码
[struct td_sched对象]:
  1. /********************************************************************
  2. * Thread scheduler specific section.  All fields are protected
  3. * by the thread lock.
  4.            ts_runq:指向相应的运行队列即struct runq数据对象
  5.            ts_slice:线程剩余的时间片
  6.            ts_slptime: 线程的睡眠时间
  7.            ts_runtime:线程的运行时间
  8.            ts_ltick:最近一次选择相应thread来运行时的时间戳
  9.            ts_cpu:和该struct td_sched对象相关联的thread将被添加到ts_cpu的
  10.                   运行队列中.
  11.            ts_rltick:当进行线程切换时,被替换线程相关的struct td_sched对象
  12.                       的ts_rlick成员被设置为ticks。
  13. ******************************************/
  14.     94  struct td_sched {      
  15.     95          struct runq     *ts_runq;       /* Run-queue we're queued on. */
  16.     96          short           ts_flags;       /* TSF_* flags. */
  17.     97          u_char          ts_cpu;         /* CPU that we have affinity for. */
  18.     98          int             ts_rltick;      /* Real last tick, for affinity. */
  19.     99          int             ts_slice;       /* Ticks of slice remaining. */
  20.    100          u_int           ts_slptime;     /* Number of ticks we vol. slept */
  21.    101          u_int           ts_runtime;     /* Number of ticks we were running */
  22.    102          int             ts_ltick;       /* Last tick that we were running on */
  23.    103          int             ts_ftick;       /* First tick that we were running on */
  24.    104          int             ts_ticks;       /* Tick count */
  25.    105  #ifdef KTR
  26.    106          char            ts_name[TS_NAME_LEN];
  27.    107  #endif
  28.    108  };
  29. /*****************************************************************************
  30.   * 下面两个标志要和struct thread对象的td_pinned成员结合来看:
  31.            td_pinned:如果该成员非零,那么该thread就不能被迁移到其它
  32.                       cpu的运行队列中,宏THREAD_CAN_MIGRATE会检查该
  33.                       成员的值。同时会设置和thread相关联的struct td_sched
  34.                       对象中的ts_flags成员中的标志:
  35.                       #define TSF_BOUND     0x0001 Thread can not migrate.
  36.                       #define TSF_XFERABLE  0x0002 Thread was added as transferable.

  37.            flags kept in ts_flags

  38.   ******************************/*/
  39.    110  #define TSF_BOUND       0x0001          /* Thread can not migrate. */
  40.    111  #define TSF_XFERABLE    0x0002          /* Thread was added as transferable. */
复制代码
无论内核使用的是4.4BSD调度程序还是ULE调度程序,uma_zalloc函数返回一个下面内存区间的起始地址:
  1.   -----------------------------------------------------------------------
  2.    |                                        |                                             |
  3.    | struct thread 对象          | struct td_sched对象            
  4.    -----------------------------------------------------------------------
  5.    ^                                       ^
  6.    |                                         |
  7.    td指向这里                    td_sched指向这里
复制代码
在struct thread对象中,和线程调度相关的成员如下:
  1.    204        struct thread {
  2. /**********************************************************************
  3. * td_runq:该成员用来将线程链接到对应的运行队列链表中,即对应的
  4.             struct runq对象的rq_queues数组元素中.

  5.    td_rqindex:该值为对应的struct runq对象中rq_queues数组的索引。即将
  6.               线程thread链接到链表rq_queues[td_rqindex]中。

  7.    td_priority:线程的优先级,在将线程添加到cpu的运行队列中时,会使用
  8.                该成员的值,函数sched_thread_priority会更新该成员的值。

  9.    td_base_pri: 在函数sched_prio中更新。
  10.               
  11.    td_user_pri,td_base_user_pri:在函数sched_user_prio中设置。
  12. ************************************/
  13.               

  14.    208                TAILQ_ENTRY(thread) td_runq;        /* (t) Run queue. */
  15. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  16. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  17.    220                u_char                td_lend_user_pri; /* (t) Lend user pri. */
  18. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  19. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  20.    276        
  21.    277        /* Copied during fork1() or thread_sched_upcall(). */
  22.    278        #define        td_startcopy td_endzero
  23.    279                u_char                td_rqindex;        /* (t) Run queue index. */
  24.    280                u_char                td_base_pri;        /* (t) Thread base kernel priority. */
  25.    281                u_char                td_priority;        /* (t) Thread active priority. */
  26.    282                u_char                td_pri_class;        /* (t) Scheduling class. */
  27.    283                u_char                td_user_pri;        /* (t) User pri from estcpu and nice. */
  28.    284                u_char                td_base_user_pri; /* (t) Base user pri */
  29.    285        #define        td_endcopy td_pcb
  30.    286        
  31.    287        /*
  32.    288         * Fields that must be manually set in fork1() or thread_sched_upcall()
  33.    289         * or already have been set in the allocator, constructor, etc.
  34.    290         */
  35. /****************************************************************************
  36. * td_pcb:该成员保存的是和thread相关联的struct pcb对象的虚拟线性基地址,
  37.                           该对象保存在thread内核栈的顶部,之后访问struct pcb对象就
  38.                           可以通过该成员来访问。创建进程时,在函数vm_forkproc中初始化。
  39.    td_state:线程所处的状态。
  40.    td_frame:指向一个类型为struct trapframe的数据对象,
  41.              通过该对象可以访问保存在内核栈上的硬件上下文。
  42.    td_kstack_obj:指向线程内核栈对应的struct vm_object对象。
  43.    td_kstack:用来访问线程内核栈的起始虚拟线性地址。
  44.    td_kstack_pages:线程内核栈的大小,单位为page。
  45.    td_slpcallout:超时处理相关,创建进程时由函数thread_link初始化。
  46.    td_sched:特定于调度程序的数据结构,该数据结构的类型为struct td_sched,
  47.              选择不同的线程调度程序,该数据结构的类型不同,创建进程从
  48.              thread_zone获取struct thread对象时,在函数thread_init中初始化
  49.              该成员。
  50. *******************************/
  51.    291                struct pcb        *td_pcb;        /* (k) Kernel VA of pcb and kstack. */
  52.    292                enum {
  53.    293                        TDS_INACTIVE = 0x0,
  54.    294                        TDS_INHIBITED,
  55.    295                        TDS_CAN_RUN,
  56.    296                        TDS_RUNQ,
  57.    297                        TDS_RUNNING
  58.    298                } td_state;                        /* (t) thread state */
  59. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  60. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  61.    301                struct trapframe *td_frame;        /* (k) */
  62.    302                struct vm_object *td_kstack_obj;/* (a) Kstack object. */
  63.    303                vm_offset_t        td_kstack;        /* (a) Kernel VA of kstack. */
  64.    304                int                td_kstack_pages; /* (a) Size of the kstack.  */
  65. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  66. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  67.    307                struct td_sched        *td_sched;        /* (*) Scheduler-specific data. */
  68. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  69. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  70.    320        };
复制代码
[运行队列数据结构]:

在freebsd中,线程优先级的范围为0-255,数字越小,优先级越高。如果使用256个不同的运行队列链表会大大增加确定下一个要执行线程
所花费的代价,所以freebsd使用64个运行队列链表,freebsd根据td_priority/4为线程选择一个运行队列链表, 而且每个运行队列链表
中的线程都不会根据它们的优先级再次排序。

运行队列最上层的数据结构由下面的结构体来描述:
  1.     36        /*
  2.     37         * Run queue parameters.
  3.     38         */
  4.     39        
  5.     40        #define        RQ_NQS                (64)                /* Number of run queues. */
  6.     41        #define        RQ_PPQ                (4)                /* Priorities per queue. */
  7.     42        
  8. /*****************************************************************
  9. * Head of run queues.
  10.            运行队列链表数组rq_queues的数据类型
  11.            宏TAILQ_HEAD展开后如下所示:
  12.            struct rqhead {                                                        
  13.              struct thread *tqh_first; /* first element */                    
  14.              struct thread **tqh_last; /* addr of last next element */        
  15.              TRACEBUF                                                      
  16.            };
  17. ******************************************************/
  18.     46        TAILQ_HEAD(rqhead, thread);
  19.       
  20. /*****************************************************************************
  21. * Bit array which maintains the status of a run queue.  When a queue is
  22. * non-empty the bit corresponding to the queue number will be set.

  23.            typedef u_int32_t       rqb_word_t;
  24.            #define        RQB_LEN     (2)    Number of priority status words.

  25.            对于运行队列链表rq_queues,位图rqb_bits中的第i个bit位用来
  26.            描述符运行队列链表rq_queues是否为空:
  27.            第i个bit位为0:运行队列链表rq_queues为空
  28.            第i个bit位非零:运行队列链表rq_queues非空
  29. ****************************************/
  30.     52        struct rqbits {
  31.     53                rqb_word_t rqb_bits[RQB_LEN];
  32.     54        };
  33.     55     
  34.    
  35. /********************************************************************************
  36. * Run queue structure.  Contains an array of run queues on which processes
  37. * are placed, and a structure to maintain the status of each queue.

  38.            #define RQ_NQS   (64)   Number of run queues.
  39.            #define RQ_PPQ   (4)    Priorities per queue.

  40.            rq_status:用来描述运行队列链表的状态。
  41.            rq_queues:运行队列链表的数组,系统**有64个运行队列链表。
  42. ************************/
  43.     60        struct runq {
  44.     61                struct        rqbits rq_status;
  45.     62                struct        rqhead rq_queues[RQ_NQS];
  46.     63        };



  47. /******************************************************************************
  48. * tdq - per processor runqs and statistics.  All fields are protected by the
  49. * tdq_lock.  The load and lowpri may be accessed without to avoid excess
  50. * locking in sched_pickcpu();
  51.            对于SMP系统:
  52.            每个cpu对应的一个struct tdq数据对象,数组tdq_cpu以cpu的logical id为索引。
  53.            static struct tdq       tdq_cpu[MAXCPU];

  54.            对于非SMP系统:
  55.            系统中只定义了一个struct tdq数据对象。
  56.            static struct tdq       tdq_cpu;

  57.            该数据对象包含一些和调度程序相关的成员以及三个运行队列,分别为运行队列:
  58.            tdq_realtime,tdq_timeshare,tdq_idle,在线程切换时,tdq_choose函数按照
  59.            tdq_realtime,tdq_timeshare,tdq_idle这个顺序来选择一个thread:

  60.            运行队列tdq_realtime:链接了td_priority小于PRI_MIN_BATCH的thread。
  61.            运行队列tdq_timeshare:链接了td_priority在[PRI_MIN_BATCH,PRI_MAX_BATCH]
  62.                                   之间的thread
  63.            运行队列tdq_idle:链接了td_priority在[PRI_MIN_IDLE,PRI_MAX_IDLE]
  64.                              之间的thread。
  65.            tdq_lowpri:见tdq_add函数,当把线程td添加到对应的运行队列时,如果
  66.                        td->td_priority < tdq->tdq_lowpri为真,就做下面的设置:
  67.                        tdq->tdq_lowpri = td->td_priority,可见struct tdq对象
  68.                        的tdq_lowpri成员保存了对应CPU运行队列中线程的最高优先级。

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

  71.            tdq_ipipending:表示是否有挂起的处理器间中断(IPI)。

  72.            tdq_load:对应cpu的负载,当把一个thread添加到struct tdq中三个运行
  73.                      队列中的一个时,就会递增tdq_load成员,该成员同时也用来
  74.                      选择负载最高和最低的CPU。

  75.            tdq_switchcnt:一个计数器,记录相应cpu上发生线程切换的次数。

  76.            tdq_ridx: 在函数tdq_choose中被使用,用法如下:
  77.                      Set the mask for the first word so we ignore priorities
  78.                      before 'tdq_ridx'.
  79.                      mask = (rqb_word_t)-1 << (tdq_ridx & (RQB_BPW - 1));
  80.                      即从rq_queues[tdq_ridx]开始的运行队列中选择一个可运行线程。
  81.                      改成员的主要作用是防止在时间片轮转队列中的线程由于其优先级
  82.                      而得不到运行,防止调度方面的饿死现象发生。
  83.                      函数runq_choose_from会使用该成员作为一个参数。
  84.   
  85.            tdq_idx:当函数sched_add将一个thread添加到对应的运行队列时,将使用该
  86.                    成员.
  87.   
  88.            tdq_cg:cpu logic id为i的cpu所属的group(即struct cpu_group对象的地址
  89.                    或者对应数组group元素的地址)。

  90.            tdq_name:字符数组保存的数据为"sched lock %d",这里的%d为cpu的logic id。
  91. **********************************************************************************/
  92.    225  struct tdq {
  93.    226          /* Ordered to improve efficiency of cpu_search() and switch(). */
  94.    227          struct mtx      tdq_lock;               /* run queue lock. */
  95.    228          struct cpu_group *tdq_cg;               /* Pointer to cpu topology. */
  96.    229          volatile int    tdq_load;               /* Aggregate load. */
  97.    230          volatile int    tdq_cpu_idle;           /* cpu_idle() is active. */
  98.    231          int             tdq_sysload;            /* For loadavg, !ITHD load. */
  99.    232          int             tdq_transferable;       /* Transferable thread count. */
  100.    233          short           tdq_switchcnt;          /* Switches this tick. */
  101.    234          short           tdq_oldswitchcnt;       /* Switches last tick. */
  102.    235          u_char          tdq_lowpri;             /* Lowest priority thread. */
  103.    236          u_char          tdq_ipipending;         /* IPI pending. */
  104.    237          u_char          tdq_idx;                /* Current insert index. */
  105.    238          u_char          tdq_ridx;               /* Current removal index. */
  106.    239          struct runq     tdq_realtime;           /* real-time run queue. */
  107.    240          struct runq     tdq_timeshare;          /* timeshare run queue. */
  108.    241          struct runq     tdq_idle;               /* Queue of IDLE threads. */
  109. /************************************************************************************************
  110. * #define  TDQ_NAME_LEN (sizeof("sched lock " + sizeof(__XSTRING(MAXCPU)))
  111.    #define  TDQ_LOADNAME_LEN (sizeof("CPU " + sizeof(__XSTRING(MAXCPU)) - 1 + sizeof(" load")
  112. ********************************/
  113.    242          char            tdq_name[TDQ_NAME_LEN];
  114.    243  #ifdef KTR
  115.    244          char            tdq_loadname[TDQ_LOADNAME_LEN];
  116.    245  #endif
  117.    246  } __aligned(64);
  118.    248  /* Idle thread states and config. */
  119.    249  #define TDQ_RUNNING     1
  120.    250  #define TDQ_IDLE        2
复制代码
01.jpg
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP