freebsd9.2-ULE线程调度-数据结构浅析
本帖最后由 71v5 于 2014-06-27 23:30 编辑草图两张:D
下面数据结构成员的含义是结合源代码得出的，其中部分还没有明白其具体含义，以后会及时更新的，有错误的地方，望大家及时指出。
：
在线程创建过程中，thread_alloc函数为新线程分配struct thread对象，内核栈，同时还会分配struct td_sched类型的数据对象来描述线程调度方面的信息，
其实，struct td_sched类型的数据对象和struct thread类型的数据对象是一起从thread_zone标识的UMA区域中分配的，而且根据所选择的线程调度程序不同，
struct td_sched类型的数据对象定义也不同。
：2558int
2559sched_sizeof_thread(void)
2560{
2561 return (sizeof(struct thread) + sizeof(struct td_sched));
2562}：/********************************************************************
* Thread scheduler specific section.All fields are protected
* by the thread lock.
ts_runq：指向相应的运行队列即struct runq数据对象
ts_slice：线程剩余的时间片
ts_slptime: 线程的睡眠时间
ts_runtime：线程的运行时间
ts_ltick:最近一次选择相应thread来运行时的时间戳
ts_cpu:和该struct td_sched对象相关联的thread将被添加到ts_cpu的
运行队列中.
ts_rltick：当进行线程切换时，被替换线程相关的struct td_sched对象
的ts_rlick成员被设置为ticks。
******************************************/
94struct td_sched {
95 struct runq *ts_runq; /* Run-queue we're queued on. */
96 short ts_flags; /* TSF_* flags. */
97 u_char ts_cpu; /* CPU that we have affinity for. */
98 int ts_rltick; /* Real last tick, for affinity. */
99 int ts_slice; /* Ticks of slice remaining. */
100 u_int ts_slptime; /* Number of ticks we vol. slept */
101 u_int ts_runtime; /* Number of ticks we were running */
102 int ts_ltick; /* Last tick that we were running on */
103 int ts_ftick; /* First tick that we were running on */
104 int ts_ticks; /* Tick count */
105#ifdef KTR
106 char ts_name;
107#endif
108};
/*****************************************************************************
* 下面两个标志要和struct thread对象的td_pinned成员结合来看：
td_pinned：如果该成员非零，那么该thread就不能被迁移到其它
cpu的运行队列中，宏THREAD_CAN_MIGRATE会检查该
成员的值。同时会设置和thread相关联的struct td_sched
对象中的ts_flags成员中的标志：
#define TSF_BOUND 0x0001 Thread can not migrate.
#define TSF_XFERABLE0x0002 Thread was added as transferable.
flags kept in ts_flags
******************************/*/
110#define TSF_BOUND 0x0001 /* Thread can not migrate. */
111#define TSF_XFERABLE 0x0002 /* Thread was added as transferable. */无论内核使用的是4.4BSD调度程序还是ULE调度程序，uma_zalloc函数返回一个下面内存区间的起始地址：-----------------------------------------------------------------------
| | |
| struct thread 对象 | struct td_sched对象
-----------------------------------------------------------------------
^ ^
| |
td指向这里 td_sched指向这里在struct thread对象中，和线程调度相关的成员如下： 204 struct thread {
/**********************************************************************
* td_runq：该成员用来将线程链接到对应的运行队列链表中，即对应的
struct runq对象的rq_queues数组元素中.
td_rqindex:该值为对应的struct runq对象中rq_queues数组的索引。即将
线程thread链接到链表rq_queues中。
td_priority:线程的优先级，在将线程添加到cpu的运行队列中时，会使用
该成员的值，函数sched_thread_priority会更新该成员的值。
td_base_pri: 在函数sched_prio中更新。
td_user_pri，td_base_user_pri：在函数sched_user_prio中设置。
************************************/
208 TAILQ_ENTRY(thread) td_runq; /* (t) Run queue. */
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
220 u_char td_lend_user_pri; /* (t) Lend user pri. */
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
276
277 /* Copied during fork1() or thread_sched_upcall(). */
278 #define td_startcopy td_endzero
279 u_char td_rqindex; /* (t) Run queue index. */
280 u_char td_base_pri; /* (t) Thread base kernel priority. */
281 u_char td_priority; /* (t) Thread active priority. */
282 u_char td_pri_class; /* (t) Scheduling class. */
283 u_char td_user_pri; /* (t) User pri from estcpu and nice. */
284 u_char td_base_user_pri; /* (t) Base user pri */
285 #define td_endcopy td_pcb
286
287 /*
288 * Fields that must be manually set in fork1() or thread_sched_upcall()
289 * or already have been set in the allocator, constructor, etc.
290 */
/****************************************************************************
* td_pcb:该成员保存的是和thread相关联的struct pcb对象的虚拟线性基地址，
该对象保存在thread内核栈的顶部，之后访问struct pcb对象就
可以通过该成员来访问。创建进程时，在函数vm_forkproc中初始化。
td_state:线程所处的状态。
td_frame：指向一个类型为struct trapframe的数据对象，
通过该对象可以访问保存在内核栈上的硬件上下文。
td_kstack_obj：指向线程内核栈对应的struct vm_object对象。
td_kstack：用来访问线程内核栈的起始虚拟线性地址。
td_kstack_pages：线程内核栈的大小，单位为page。
td_slpcallout：超时处理相关，创建进程时由函数thread_link初始化。
td_sched：特定于调度程序的数据结构，该数据结构的类型为struct td_sched，
选择不同的线程调度程序，该数据结构的类型不同，创建进程从
thread_zone获取struct thread对象时，在函数thread_init中初始化
该成员。
*******************************/
291 struct pcb *td_pcb; /* (k) Kernel VA of pcb and kstack. */
292 enum {
293 TDS_INACTIVE = 0x0,
294 TDS_INHIBITED,
295 TDS_CAN_RUN,
296 TDS_RUNQ,
297 TDS_RUNNING
298 } td_state; /* (t) thread state */
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
301 struct trapframe *td_frame; /* (k) */
302 struct vm_object *td_kstack_obj;/* (a) Kstack object. */
303 vm_offset_t td_kstack; /* (a) Kernel VA of kstack. */
304 int td_kstack_pages; /* (a) Size of the kstack.*/
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
307 struct td_sched *td_sched; /* (*) Scheduler-specific data. */
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
320 };[运行队列数据结构]：
在freebsd中，线程优先级的范围为0-255，数字越小，优先级越高。如果使用256个不同的运行队列链表会大大增加确定下一个要执行线程
所花费的代价，所以freebsd使用64个运行队列链表，freebsd根据td_priority/4为线程选择一个运行队列链表， 而且每个运行队列链表
中的线程都不会根据它们的优先级再次排序。
运行队列最上层的数据结构由下面的结构体来描述： 36 /*
37 * Run queue parameters.
38 */
39
40 #define RQ_NQS (64) /* Number of run queues. */
41 #define RQ_PPQ (4) /* Priorities per queue. */
42
/*****************************************************************
* Head of run queues.
运行队列链表数组rq_queues的数据类型
宏TAILQ_HEAD展开后如下所示：
struct rqhead {
struct thread *tqh_first; /* first element */
struct thread **tqh_last; /* addr of last next element */
TRACEBUF
};
******************************************************/
46 TAILQ_HEAD(rqhead, thread);
/*****************************************************************************
* Bit array which maintains the status of a run queue.When a queue is
* non-empty the bit corresponding to the queue number will be set.
typedef u_int32_t rqb_word_t;
#define RQB_LEN (2) Number of priority status words.
对于运行队列链表rq_queues，位图rqb_bits中的第i个bit位用来
描述符运行队列链表rq_queues是否为空：
第i个bit位为0：运行队列链表rq_queues为空
第i个bit位非零：运行队列链表rq_queues非空
****************************************/
52 struct rqbits {
53 rqb_word_t rqb_bits;
54 };
55
/********************************************************************************
* Run queue structure.Contains an array of run queues on which processes
* are placed, and a structure to maintain the status of each queue.
#define RQ_NQS (64) Number of run queues.
#define RQ_PPQ (4) Priorities per queue.
rq_status：用来描述运行队列链表的状态。
rq_queues：运行队列链表的数组，系统**有64个运行队列链表。
************************/
60 struct runq {
61 struct rqbits rq_status;
62 struct rqhead rq_queues;
63 };
/******************************************************************************
* tdq - per processor runqs and statistics.All fields are protected by the
* tdq_lock.The load and lowpri may be accessed without to avoid excess
* locking in sched_pickcpu();
对于SMP系统：
每个cpu对应的一个struct tdq数据对象，数组tdq_cpu以cpu的logical id为索引。
static struct tdq tdq_cpu;
对于非SMP系统：
系统中只定义了一个struct tdq数据对象。
static struct tdq tdq_cpu;
该数据对象包含一些和调度程序相关的成员以及三个运行队列，分别为运行队列：
tdq_realtime，tdq_timeshare，tdq_idle，在线程切换时，tdq_choose函数按照
tdq_realtime，tdq_timeshare，tdq_idle这个顺序来选择一个thread：
运行队列tdq_realtime：链接了td_priority小于PRI_MIN_BATCH的thread。
运行队列tdq_timeshare：链接了td_priority在
之间的thread
运行队列tdq_idle：链接了td_priority在
之间的thread。
tdq_lowpri：见tdq_add函数，当把线程td添加到对应的运行队列时，如果
td->td_priority < tdq->tdq_lowpri为真，就做下面的设置：
tdq->tdq_lowpri = td->td_priority，可见struct tdq对象
的tdq_lowpri成员保存了对应CPU运行队列中线程的最高优先级。
tdq_transferable: 一个计数器，cpu的相应运行队列中可迁移线程的数目。在
函数tdq_runq_add中递增。
tdq_ipipending:表示是否有挂起的处理器间中断(IPI)。
tdq_load：对应cpu的负载，当把一个thread添加到struct tdq中三个运行
队列中的一个时，就会递增tdq_load成员，该成员同时也用来
选择负载最高和最低的CPU。
tdq_switchcnt：一个计数器，记录相应cpu上发生线程切换的次数。
tdq_ridx: 在函数tdq_choose中被使用，用法如下：
Set the mask for the first word so we ignore priorities
before 'tdq_ridx'.
mask = (rqb_word_t)-1 << (tdq_ridx & (RQB_BPW - 1));
即从rq_queues开始的运行队列中选择一个可运行线程。
改成员的主要作用是防止在时间片轮转队列中的线程由于其优先级
而得不到运行，防止调度方面的饿死现象发生。
函数runq_choose_from会使用该成员作为一个参数。
tdq_idx:当函数sched_add将一个thread添加到对应的运行队列时，将使用该
成员.
tdq_cg：cpu logic id为i的cpu所属的group(即struct cpu_group对象的地址
或者对应数组group元素的地址)。
tdq_name：字符数组保存的数据为"sched lock %d",这里的%d为cpu的logic id。
**********************************************************************************/
225struct tdq {
226 /* Ordered to improve efficiency of cpu_search() and switch(). */
227 struct mtx tdq_lock; /* run queue lock. */
228 struct cpu_group *tdq_cg; /* Pointer to cpu topology. */
229 volatile int tdq_load; /* Aggregate load. */
230 volatile int tdq_cpu_idle; /* cpu_idle() is active. */
231 int tdq_sysload; /* For loadavg, !ITHD load. */
232 int tdq_transferable; /* Transferable thread count. */
233 short tdq_switchcnt; /* Switches this tick. */
234 short tdq_oldswitchcnt; /* Switches last tick. */
235 u_char tdq_lowpri; /* Lowest priority thread. */
236 u_char tdq_ipipending; /* IPI pending. */
237 u_char tdq_idx; /* Current insert index. */
238 u_char tdq_ridx; /* Current removal index. */
239 struct runq tdq_realtime; /* real-time run queue. */
240 struct runq tdq_timeshare; /* timeshare run queue. */
241 struct runq tdq_idle; /* Queue of IDLE threads. */
/************************************************************************************************
* #defineTDQ_NAME_LEN (sizeof("sched lock " + sizeof(__XSTRING(MAXCPU)))
#defineTDQ_LOADNAME_LEN (sizeof("CPU " + sizeof(__XSTRING(MAXCPU)) - 1 + sizeof(" load")
********************************/
242 char tdq_name;
243#ifdef KTR
244 char tdq_loadname;
245#endif
246} __aligned(64);
248/* Idle thread states and config. */
249#define TDQ_RUNNING 1
250#define TDQ_IDLE 2
页:
[1]