freebsd9.2-ULE线程调度-数据结构浅析

71v5

草图两张






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

[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. 
    
38.            flags kept in ts_flags
    
39. 
    
40.   ******************************/*/
    
41.    110  #define TSF_BOUND       0x0001          /* Thread can not migrate. */
    
42.    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. 
   
6.    td_rqindex:该值为对应的struct runq对象中rq_queues数组的索引。即将
   
7.               线程thread链接到链表rq_queues[td_rqindex]中。
   
8. 
   
9.    td_priority:线程的优先级，在将线程添加到cpu的运行队列中时，会使用
   
10.                该成员的值，函数sched_thread_priority会更新该成员的值。
    
11. 
    
12.    td_base_pri: 在函数sched_prio中更新。
    
13.               
    
14.    td_user_pri，td_base_user_pri：在函数sched_user_prio中设置。
    
15. ************************************/
    
16.               
    
17. 
    
18.    208                TAILQ_ENTRY(thread) td_runq;        /* (t) Run queue. */
    
19. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
    
20. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
    
21.    220                u_char                td_lend_user_pri; /* (t) Lend user pri. */
    
22. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
    
23. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
    
24.    276        
    
25.    277        /* Copied during fork1() or thread_sched_upcall(). */
    
26.    278        #define        td_startcopy td_endzero
    
27.    279                u_char                td_rqindex;        /* (t) Run queue index. */
    
28.    280                u_char                td_base_pri;        /* (t) Thread base kernel priority. */
    
29.    281                u_char                td_priority;        /* (t) Thread active priority. */
    
30.    282                u_char                td_pri_class;        /* (t) Scheduling class. */
    
31.    283                u_char                td_user_pri;        /* (t) User pri from estcpu and nice. */
    
32.    284                u_char                td_base_user_pri; /* (t) Base user pri */
    
33.    285        #define        td_endcopy td_pcb
    
34.    286        
    
35.    287        /*
    
36.    288         * Fields that must be manually set in fork1() or thread_sched_upcall()
    
37.    289         * or already have been set in the allocator, constructor, etc.
    
38.    290         */
    
39. /****************************************************************************
    
40. * td_pcb:该成员保存的是和thread相关联的struct pcb对象的虚拟线性基地址，
    
41.                           该对象保存在thread内核栈的顶部，之后访问struct pcb对象就
    
42.                           可以通过该成员来访问。创建进程时，在函数vm_forkproc中初始化。
    
43.    td_state:线程所处的状态。
    
44.    td_frame：指向一个类型为struct trapframe的数据对象，
    
45.              通过该对象可以访问保存在内核栈上的硬件上下文。
    
46.    td_kstack_obj：指向线程内核栈对应的struct vm_object对象。
    
47.    td_kstack：用来访问线程内核栈的起始虚拟线性地址。
    
48.    td_kstack_pages：线程内核栈的大小，单位为page。
    
49.    td_slpcallout：超时处理相关，创建进程时由函数thread_link初始化。
    
50.    td_sched：特定于调度程序的数据结构，该数据结构的类型为struct td_sched，
    
51.              选择不同的线程调度程序，该数据结构的类型不同，创建进程从
    
52.              thread_zone获取struct thread对象时，在函数thread_init中初始化
    
53.              该成员。
    
54. *******************************/
    
55.    291                struct pcb        *td_pcb;        /* (k) Kernel VA of pcb and kstack. */
    
56.    292                enum {
    
57.    293                        TDS_INACTIVE = 0x0,
    
58.    294                        TDS_INHIBITED,
    
59.    295                        TDS_CAN_RUN,
    
60.    296                        TDS_RUNQ,
    
61.    297                        TDS_RUNNING
    
62.    298                } td_state;                        /* (t) thread state */
    
63. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
    
64. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
    
65.    301                struct trapframe *td_frame;        /* (k) */
    
66.    302                struct vm_object *td_kstack_obj;/* (a) Kstack object. */
    
67.    303                vm_offset_t        td_kstack;        /* (a) Kernel VA of kstack. */
    
68.    304                int                td_kstack_pages; /* (a) Size of the kstack.  */
    
69. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
    
70. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
    
71.    307                struct td_sched        *td_sched;        /* (*) Scheduler-specific data. */
    
72. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
    
73. 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
    
74.    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. 
    
24.            typedef u_int32_t       rqb_word_t;
    
25.            #define        RQB_LEN     (2)    Number of priority status words.
    
26. 
    
27.            对于运行队列链表rq_queues，位图rqb_bits中的第i个bit位用来
    
28.            描述符运行队列链表rq_queues是否为空：
    
29.            第i个bit位为0：运行队列链表rq_queues为空
    
30.            第i个bit位非零：运行队列链表rq_queues非空
    
31. ****************************************/
    
32.     52        struct rqbits {
    
33.     53                rqb_word_t rqb_bits[RQB_LEN];
    
34.     54        };
    
35.     55     
    
36.    
    
37. /********************************************************************************
    
38. * Run queue structure.  Contains an array of run queues on which processes
    
39. * are placed, and a structure to maintain the status of each queue.
    
40. 
    
41.            #define RQ_NQS   (64)   Number of run queues.
    
42.            #define RQ_PPQ   (4)    Priorities per queue.
    
43. 
    
44.            rq_status：用来描述运行队列链表的状态。
    
45.            rq_queues：运行队列链表的数组，系统**有64个运行队列链表。
    
46. ************************/
    
47.     60        struct runq {
    
48.     61                struct        rqbits rq_status;
    
49.     62                struct        rqhead rq_queues[RQ_NQS];
    
50.     63        };
    
51. 
    
52. 
    
53. 
    
54. /******************************************************************************
    
55. * tdq - per processor runqs and statistics.  All fields are protected by the
    
56. * tdq_lock.  The load and lowpri may be accessed without to avoid excess
    
57. * locking in sched_pickcpu();
    
58.            对于SMP系统：
    
59.            每个cpu对应的一个struct tdq数据对象，数组tdq_cpu以cpu的logical id为索引。
    
60.            static struct tdq       tdq_cpu[MAXCPU];
    
61. 
    
62.            对于非SMP系统：
    
63.            系统中只定义了一个struct tdq数据对象。
    
64.            static struct tdq       tdq_cpu;
    
65. 
    
66.            该数据对象包含一些和调度程序相关的成员以及三个运行队列，分别为运行队列：
    
67.            tdq_realtime，tdq_timeshare，tdq_idle，在线程切换时，tdq_choose函数按照
    
68.            tdq_realtime，tdq_timeshare，tdq_idle这个顺序来选择一个thread：
    
69. 
    
70.            运行队列tdq_realtime：链接了td_priority小于PRI_MIN_BATCH的thread。
    
71.            运行队列tdq_timeshare：链接了td_priority在[PRI_MIN_BATCH，PRI_MAX_BATCH]
    
72.                                   之间的thread
    
73.            运行队列tdq_idle：链接了td_priority在[PRI_MIN_IDLE，PRI_MAX_IDLE]
    
74.                              之间的thread。
    
75.            tdq_lowpri：见tdq_add函数，当把线程td添加到对应的运行队列时，如果
    
76.                        td->td_priority < tdq->tdq_lowpri为真，就做下面的设置：
    
77.                        tdq->tdq_lowpri = td->td_priority，可见struct tdq对象
    
78.                        的tdq_lowpri成员保存了对应CPU运行队列中线程的最高优先级。
    
79. 
    
80.            tdq_transferable: 一个计数器，cpu的相应运行队列中可迁移线程的数目。在
    
81.                              函数tdq_runq_add中递增。
    
82. 
    
83.            tdq_ipipending:表示是否有挂起的处理器间中断(IPI)。
    
84. 
    
85.            tdq_load：对应cpu的负载，当把一个thread添加到struct tdq中三个运行
    
86.                      队列中的一个时，就会递增tdq_load成员，该成员同时也用来
    
87.                      选择负载最高和最低的CPU。
    
88. 
    
89.            tdq_switchcnt：一个计数器，记录相应cpu上发生线程切换的次数。
    
90. 
    
91.            tdq_ridx: 在函数tdq_choose中被使用，用法如下：
    
92.                      Set the mask for the first word so we ignore priorities
    
93.                      before 'tdq_ridx'.
    
94.                      mask = (rqb_word_t)-1 << (tdq_ridx & (RQB_BPW - 1));
    
95.                      即从rq_queues[tdq_ridx]开始的运行队列中选择一个可运行线程。
    
96.                      改成员的主要作用是防止在时间片轮转队列中的线程由于其优先级
    
97.                      而得不到运行，防止调度方面的饿死现象发生。
    
98.                      函数runq_choose_from会使用该成员作为一个参数。
    
99.   
    
100.            tdq_idx:当函数sched_add将一个thread添加到对应的运行队列时，将使用该
     
101.                    成员.
     
102.   
     
103.            tdq_cg：cpu logic id为i的cpu所属的group(即struct cpu_group对象的地址
     
104.                    或者对应数组group元素的地址)。
     
105. 
     
106.            tdq_name：字符数组保存的数据为"sched lock %d",这里的%d为cpu的logic id。
     
107. **********************************************************************************/
     
108.    225  struct tdq {
     
109.    226          /* Ordered to improve efficiency of cpu_search() and switch(). */
     
110.    227          struct mtx      tdq_lock;               /* run queue lock. */
     
111.    228          struct cpu_group *tdq_cg;               /* Pointer to cpu topology. */
     
112.    229          volatile int    tdq_load;               /* Aggregate load. */
     
113.    230          volatile int    tdq_cpu_idle;           /* cpu_idle() is active. */
     
114.    231          int             tdq_sysload;            /* For loadavg, !ITHD load. */
     
115.    232          int             tdq_transferable;       /* Transferable thread count. */
     
116.    233          short           tdq_switchcnt;          /* Switches this tick. */
     
117.    234          short           tdq_oldswitchcnt;       /* Switches last tick. */
     
118.    235          u_char          tdq_lowpri;             /* Lowest priority thread. */
     
119.    236          u_char          tdq_ipipending;         /* IPI pending. */
     
120.    237          u_char          tdq_idx;                /* Current insert index. */
     
121.    238          u_char          tdq_ridx;               /* Current removal index. */
     
122.    239          struct runq     tdq_realtime;           /* real-time run queue. */
     
123.    240          struct runq     tdq_timeshare;          /* timeshare run queue. */
     
124.    241          struct runq     tdq_idle;               /* Queue of IDLE threads. */
     
125. /************************************************************************************************
     
126. * #define  TDQ_NAME_LEN (sizeof("sched lock " + sizeof(__XSTRING(MAXCPU)))
     
127.    #define  TDQ_LOADNAME_LEN (sizeof("CPU " + sizeof(__XSTRING(MAXCPU)) - 1 + sizeof(" load")
     
128. ********************************/
     
129.    242          char            tdq_name[TDQ_NAME_LEN];
     
130.    243  #ifdef KTR
     
131.    244          char            tdq_loadname[TDQ_LOADNAME_LEN];
     
132.    245  #endif
     
133.    246  } __aligned(64);
     
134.    248  /* Idle thread states and config. */
     
135.    249  #define TDQ_RUNNING     1
     
136.    250  #define TDQ_IDLE        2
     

复制代码