|
writtent by: gvim @ chinaunix /bsd
release under BSD license
在这一系列的小文里，我将从我自己的学习分析入手，尽量为大家展示一张清晰的进程相关机制与实现。后面的小文初步计划包括中断，时钟，系统调用框架，KSE，调度策略，等等有关进程的部分。有些部分已经有朋友实现了分析说明，我会在他们分析的基础上添加，修改，更新，使得这些东西可以形成一张体系网络。我不是专职作家或教育家，所以时间可能会比较长。当然，我不是神仙，我也会犯错。
作为开篇，我先详细分析调度机制。操作系统的心脏是调度器，并且这个心跳的脉搏是时钟。调度可以分为两个部分，一部分属于平台无关的调度策略，策略在[2]、[3]、[4]中已经有十分详尽的介绍；另一部分属于平台相关的调度机制，也就是本篇小文偏向的重点。时钟将在以后的小文中予以介绍(这部分[2]写得十分简略)。
既然调度机制是平台相关的，那为什么还需要分析它？我个人认为，首先自低向上的分析也是一种学习方式；只学习调度策略而不分析调度机制，对于调度器这个行为体来讲，是不完整的；另外，调度机制是与计算机体系紧密结合的，是软硬件之间交互的方式之一；最后，知道了实际的调度机制之后，我们可以在上层替换/修改调度策略，实现我们自己的调度器。分析的代码忽略SMP的相关内容，一些剖析(profiling)内容和其他与调度切换本身关系不大的相关代码(从前面的行号可以看出来省略部分，需要完整的话可以在下面的链接找到)。下面的代码都摘自 http://fxr.watson.org/fxr/source/i386/i386/swtch.s?v=RELENG60 ,因此保留行符便于查对。如果对汇编不熟悉的话，跳过相应代码而直接看解释应该没有太大问题。
本文的写法与[6]的任务切换部分的详细扩展。[6]中其余部分可以参见风雨兄的翻译【进程管理】之【FreeBSD内核如何在保护模式下管理IA32处理器（译）】
感谢雨丝风片@chinaunix/bsd和congli@chinaunix/bsd的审查、鼓励与支持 J
首先找到调度器调度机制的代码入口，该入口如下，在i386/i386/swtch.s中。
95 ENTRY(cpu_switch)
宏ENTRY在i386/include/asm.h中定义如下：
#define ENTRY(x) _ENTRY(x)
在相同的文件中我们可以看到如下的定义：
#define CNAME(csym) csym
#define _START_ENTRY .text; .p2align 2,0x90
#define _ENTRY(x) _START_ENTRY; \
.globl CNAME(x); .type CNAME(x),@function; CNAME(x):
这样ENTRY(cpu_switch)可以做如下替换
.text; .p2align 2,0x90; \
.globl cpu_switch; .type cpu_switch,@function; cpu_switch:
以上伪指令可以查看info gas中相关解释。
这段伪汇编代码的意思是告诉连接器，这部分数据是程序代码，.p2align 2,0x90; 告诉连接器这些指令以32bit也就是4字节长度(power(2,2))对齐，对齐时填充部分填入数值0x90，这个数值是NOP指令的机器代码。
.globl cpu_switch;声明cpu_switch是一个全局范围可见的符号。连接器可以使用这个符号。
.type cpu_switch,@function;声明这个符号是一个函数类型的符号。
cpu_switch: 标志符，告诉连接器从这里开始是代码部分的开始。
在正文段的开始，我们首先看看cpu_switch之前的代码注释。
注意！在FreeBSD 6.0 release 中man cpu_switch得到的是1996年的解释。(多谢风雨的开路性探索，使得我知道man手册跟不上步骤)
86 /*
87 * cpu_switch(old, new)
88 *
89 * Save the current thread state, then select the next thread to run
90 * and load its state.
91 * 0(%esp) = ret
92 * 4(%esp) = oldtd
93 * 8(%esp) = newtd
94 */
这部分注释告诉我们，cpu_switch取得两个参数，分别为old和new。这两个参数都是指向结构thread的指针（可以在sched_switch()[kern/sched_4bsd.c]等上层函数中找到对cpu_switch的调用）。函数调用栈桢的栈顶指针esp存放的是ret地址也就是返回地址(关于函数调用栈桢的相关概念可以参考[5])。下面紧接着的是切换之前的old线程结构指针，也就是cpu_switch的第一个参数，由于IA32上堆栈的生长方向和内存地址增长方向相反，因此这里是4(%esp)也就是%esp+4的意思，通过这样的语句我们可以得到old指针所指地址。4表示IA32上一个指针长度为4字节=32bit(不是吗？J)。old之后是new，也需要越过4字节，所以相对于esp栈顶来说是4+4=8。
为了将处理器的执行切换到new线程，我们必须首先保留old的线程上下文，以便当调度器在一次选择这个线程的时候可以恢复运行。所以，我们首先通过thread结构[sys/proc.h]的old指针取得old线程。
97 /* Switch to new thread. First, save context. */
98 movl 4(%esp),%ecx /* 现在ecx中存放的是old线程的thread指针 */
TD_PCB宏在i386/i386/genassym.c中定义为ASSYM(TD_PCB, offsetof(struct thread, td_pcb))，意义是：定义TD_PCB这个符号，它的值是thread结构中成员变量td_pcb的偏移量。其中的一系列宏替换我就不在这里罗嗦了。最后的实际宏行为体现在i386/compile/xxx/assym.s中的这一句：#define TD_PCB 0xfc，可见td_pcb成员在thread结构中是位于从0计数开始的0xfc字节处。td_pcb是一个pcb结构[i386/include/pcb.h]类型的实例变量。
105 movl TD_PCB(%ecx),%edx /* 取得old线程的进程控制块, 地址放在edx中*/
具体的保存工作在下面进行，第107行的(%esp)取得91行说明的ret地址，这个地址也就是调用cpu_switch之后的那句指令的地址。在汇编层面来说，就是call cpu_switch之后的指令地址。以前面说的上层函数sched_switch()为例，(%esp)放的是cpu_switch之后的紧接着的语句地址。
PCB_EIP等宏和上面105行出现的TD_PCB的解释相同，不再罗嗦。注意这里edx存放的是pcb结构的指针。首先保存IA32对外接口的几个(通用)寄存器：eip,ebx,esp,ebp,esi,edi,gs段描述符，和机器状态字。
107 movl (%esp),%eax /* Hardware registers */
108 movl %eax,PCB_EIP(%edx) /* 正如上面解释的，IP指向返回地址 */
109 movl %ebx,PCB_EBX(%edx) /* 保存当前线程的ebx */
110 movl %esp,PCB_ESP(%edx) /* 这里没有保存eax，它现在保存的是old 的EIP */
111 movl %ebp,PCB_EBP(%edx) /* 也没有保存ecx，它现在保存的是old thread */
112 movl %esi,PCB_ESI(%edx) /* 也没有保存edx，它现在保存的是old pcb */
113 movl %edi,PCB_EDI(%edx)
114 movl %gs,PCB_GS(%edx)
由于IA32指令集中没有直接取得处理器状态字的指令，所以我们需要间接使用堆栈及堆栈操作指令获得处理器状态字。
115 pushfl /* PSL ,取得当前状态字，并保存在pcb结构中*/
116 popl PCB_PSL(%edx) /* 的pcb_psl变量中。psl：process status long */
这里我还没有分析switchout，应该是kse概念内的东西，先放到这里不解释，以后再补充。
117 /* Check to see if we need to call a switchout function. */
118 movl PCB_SWITCHOUT(%edx),%eax
119 cmpl $0, %eax
120 je 1f
121 call *%eax
调试寄存器，需要保存就保存，不需要就跳过这段代码，DR(debug register)可以参看[7]。不了解这里问题也不大。
122 1:
123 /* Test if debug registers should be saved. */
124 testl $PCB_DBREGS,PCB_FLAGS(%edx)
125 jz 1f /* no, skip over */
126 movl %dr7,%eax /* yes, do the save */
127 movl %eax,PCB_DR7(%edx)
128 andl $0x0000fc00, %eax /* disable all watchpoints */
129 movl %eax,%dr7
130 movl %dr6,%eax
131 movl %eax,PCB_DR6(%edx)
132 movl %dr3,%eax
133 movl %eax,PCB_DR3(%edx)
134 movl %dr2,%eax
135 movl %eax,PCB_DR2(%edx)
136 movl %dr1,%eax
137 movl %eax,PCB_DR1(%edx)
138 movl %dr0,%eax
139 movl %eax,PCB_DR0(%edx)
140 1:
看看有没有使用287/387[i386/isa/npx.c]协处理器，当然，如果使用了我们也需要保存它的状态。
142 #ifdef DEV_NPX
143 /* have we used fp, and need a save? */
144 cmpl %ecx,PCPU(FPCURTHREAD)
145 jne 1f
146 addl $PCB_SAVEFPU,%edx /* h/w bugs make saving complicated */
147 pushl %edx
148 call npxsave /* do it in a big C function */
149 popl %eax
150 1:
151 #endif
与一个进程/线程相关的，除了上面需要保存的通用寄存器的各种状态之外，还有它的页表映射状态。这个页表的基地址是保存在CR3寄存器里的。现在的工作是保存old线程的地址映射关系，载入new的。因此，虽然old线程寄存器的各种状态我们已经保存好了，但是我们还必须改变old线程中的虚拟地址映射关系。这部分和虚拟内存有关，详细的分析可以参见风雨的文章及congli等众兄弟的实验和解答【内核相关】之【内存管理】。
153 /* Save is done. Now fire up new thread. Leave old vmspace. */
154 movl %ecx,%edi /* ecx还记得吗？从107行到这里一直没有变化 */
/* 到这里仍然代表old线程thread结构指针 */
/* 但是从现在开始edi代表old线程了 */
/* edi我们在113行保存过，所以现在可以使用 */
155 movl 8(%esp),%ecx /* New thread ,ecx现在代表new线程 */
160 movl TD_PCB(%ecx),%edx /* 获得new线程的pcb地址 */
161 movl PCPU(CPUID), %esi /* 展开之后是 movl %fs:PC_CPUID, %esi */
有关CR3的作用和使用，参见[7]。大致来说，CR3存放的是页表目录的基地址。整个使用过程如下：
[7]：图3-12
以4k页面为例，这里简单描述一下转换过程，熟悉得朋友可以跳过。首先，页目录Page Directory的基地址存放在CR3里面。线形地址的高[31：22]位作为对该目录的索引(为叙述方便，简写为IdxD: index directory)，取得一个目录项也就是图中左边Directory Entry。Page Directory有pow(2,10)=1024项，也就是说，页目录可以索引1024个页表。如果我们以C语言的形式来表达可以写成(CR3)[IdxD]。这个目录项也是一个基地址，它索引一个页表：Page Table。页表也有pow(2,10)=1024项。这些项由线形地址的[21:12](称之为IdxT: index Table)索引。每一个项可以表示一个4K(pow(2,12)，见下)大小的页面，用C语言数组方式表达为((CR3)[IdxD])[IdxT]。最后，线形地址低12位，也就是[11:0]作为页表的索引取得实际的物理地址，由表示的位数可以看出来，每张页表是4K。同样，C语言表示为(((CR3)[IdxD])[IdxT])[IdxP]。形象上说(或许不严谨)，地址的变换是一个三维数组的遍历过程。最后，我们可以看见，总的地址寻址空间是1024*1024*4096=4G字节。That’s right。
回到我们的cpu_switch中来说，可以看见，变换了CR3，也就变换了虚拟地址的映射关系。
163 /* switch address space */
164 movl PCB_CR3(%edx),%eax /* edx表示160行取得的new线程的pcb地址，
我们取出来new线程的CR3寄存器，放到eax里面
*/
168 cmpl %eax,IdlePTD /* Kernel address space? */
/* IdlePTD 在i386/i386/locore.S中定义 */
170 je sw1 /* 检查线程是否在内核态使用内核地址空间 */
171 movl %cr3,%ebx /* The same address space? */
172 cmpl %ebx,%eax
173 je sw1 /* 如原代码注释，检查是否处于相同地址空间 */
常识告诉我们，线程既可以在内核空间挂起(传统Unix在内核空间时不能被打断，但是不要忘了我们现在的FreeBSD6.0里)，也可以在用户空间挂起，所以存在如下的情况。
因为内核地址空间对所有进程是共享的，所以在内核空间时不需要转换CR3寄存器。
因为如果线程使用相同地址空间(废话，线程的存在就是为了共享地址空间嘛，也就是说这里检查的是old和new两个线程是否属于两个不同进程)，页目录基址也不需要变换，我们自然也不需要操作CR3寄存器。
但是现在检测到线程既不处于内核空间，也不使用相同的地址空间，所以需要做下面的工作。
否则直接跳过174-181行。
174 movl %eax,%cr3 /* new address space */
/* 我们开始使用164行得到的new线程的CR3
开始使用新的CR3，因此从现在开始地址映射关
系改变。
改变后不会影响下面的操作吗？因为下面还要访问内存阿？！不要忘了，我们在内核里，所有线程共享内核空间，下面的存储器访问，虽然CR3变了，但是从虚拟地址经过上述的三维数组遍历之后，仍然访问的相同的地址。概念上和C语言的指针alias很相似。[debug me]
*/
176 /* Release bit from old pmap->pm_active */
177 movl PCPU(CURPMAP), %ebx /* %fs:PC_CURPMAP = %fs:0x3c */
181 btrl %esi, PM_ACTIVE(%ebx) /* clear old */
/* esi在161行赋值 */
/* 清除活动位标志，由于old线程分配的虚存
* 在new线程活动期间不再需要，标志为不活动
* 可以让换页守护进程在存储空间不足时将之
* 交换出主存
*/
显然，我们弄死了一个，就要复活一个。我们下面需要设置new线程的虚拟页面为活动页面。
183 /* Set bit in new pmap->pm_active */
184 movl TD_PROC(%ecx),%eax /* newproc，取得new线程的进程结构 */
185 movl P_VMSPACE(%eax), %ebx /* 这是一个vmspace结构的指针 */
186 addl $VM_PMAP, %ebx /* 现在ebx代表new线程中pmap结构的首
地址vm/vm_map.h
*/
187 movl %ebx, PCPU(CURPMAP)
191 btsl %esi, PM_ACTIVE(%ebx) /* set new */
如下面194-197行的代码注释那样，我们现在已经切换了new线程的地址空间。
193 sw1:
194 /*
195 * At this point, we've switched address spaces and are ready
196 * to load up the rest of the next context.
197 */
pcb扩展，意思是每个进程有自己的TSS，反正都是TSS，因此是不是它自己的并不影响对线程切换行为的理解。差别不过是自己的TSS自己用，公用的TSS大家用。TSS: Task-State segment [7]:第6章
注意FreeBSD中并没有使用Intel硬件提供的任务切换机制（将在下面解释为什么还要出现TSS），所以暂时忽略这段代码的分析。
198 cmpl $0, PCB_EXT(%edx) /* has pcb extension? */
199 je 1f /* If not, use the default */
200 btsl %esi, private_tss /* mark use of private tss */
201 movl PCB_EXT(%edx), %edi /* new tss descriptor */
202 jmp 2f /* Load it up */
204 1: /*
205 * Use the common default TSS instead of our own.
206 * Set our stack pointer into the TSS, it's set to just
207 * below the PCB. In C, common_tss.tss_esp0 = &pcb - 16;
208 */
209 leal -16(%edx), %ebx /* leave space for vm86 */
210 movl %ebx, PCPU(COMMON_TSS) + TSS_ESP0
211
212 /*
213 * Test this CPU's bit in the bitmap to see if this
214 * CPU was using a private TSS.
215 */
216 btrl %esi, private_tss /* Already using the common? */
217 jae 3f /* if so, skip reloading */
218 PCPU_ADDR(COMMON_TSSD, %edi)
我们可以看见227行的ltr装载task register的操作。但是，FreeBSD是不依赖intel的硬件机制来实施任务切换。因此，上面保留的问题在这里回答。要回答这个问题，需要看看tss的大致结构：
[7]:图6-1
里面的各项域都是在使用intel硬件提供的任务切换时自动保存的。由于不使用TSS进行任务切换，我们忽略大部分域，只关心三个域(Stack Priv Level 0),( Stack Priv Level 1),( Stack Priv Level 2)，其时还有第四个域I/Omap，我还不熟悉，就不讲述I/O map的东西，希望有人可以补充下。
这三个域代表了处理器在0-2三个ring级别执行时的堆栈段及栈顶(SSx:ESPx，x代表ring级别)。还有一个ring3的堆栈，那自然在用户级大家经常看见的esp,ss就可以表示了。所以这里只需要记录四个ring级别中的三个。
由于80x86的处理器下降ring权限时，比如ring3（用户级）下降到0，或1，或2，（或者从ring2下降到0或1，等）处理器自动从TSS数据结构里面得相应ring级别找出堆栈。并在相应的级别中操作堆栈。为什么？因为我们不可以让低优先的东西使用高优先级堆栈，堆栈需要保护。所以我们可以看见下面的图示：
[7]:图5-4
图上半部是同级别的入栈操作，下面是跨级别的入栈。可以看出来，在ring下降(也就是优先级升高)的时候，很多东西都是记录在高优先级的堆栈中。(虽然这里是用的中断处理的图，但是抛开中断或是任务切换的表象，我们解释的是不同ring级别堆栈的使用。当然，从低优先级到高优先级的访问，也只有中断，异常等几种方式可以做到)。由于什么信息都已经记载，从高优先级退出时返回是很容易的。正是由于这个自动操作的存在，使得我们虽然不使用TSS这个东西，还是必须填充它，随任务切换时切换。
219 2:
220 /* Move correct tss descriptor into GDT slot, then reload tr. */
221 movl PCPU(TSS_GDT), %ebx /* entry in GDT */
222 movl 0(%edi), %eax
223 movl 4(%edi), %esi
224 movl %eax, 0(%ebx)
225 movl %esi, 4(%ebx)
226 movl $GPROC0_SEL*8, %esi /* GSEL(entry, SEL_KPL) */
227 ltr %si
228 3:
229
230 /* Copy the %fs and %gs selectors into this pcpu gdt */
231 leal PCB_FSD(%edx), %esi
232 movl PCPU(FSGS_GDT), %edi
233 movl 0(%esi), %eax /* %fs selector */
234 movl 4(%esi), %ebx
235 movl %eax, 0(%edi)
236 movl %ebx, 4(%edi)
237 movl 8(%esi), %eax /* %gs selector, comes straight after */
238 movl 12(%esi), %ebx
239 movl %eax, 8(%edi)
240 movl %ebx, 12(%edi)
恢复new线程的寄存器。是107-114行的逆过程
242 /* Restore context. */
243 movl PCB_EBX(%edx),%ebx
244 movl PCB_ESP(%edx),%esp
245 movl PCB_EBP(%edx),%ebp
246 movl PCB_ESI(%edx),%esi
247 movl PCB_EDI(%edx),%edi
248 movl PCB_EIP(%edx),%eax
249 movl %eax,(%esp)
250 pushl PCB_PSL(%edx)
251 popfl /* 恢复了很多寄存器，包括处理器状态字EFLAGS */
记录当前处理器的当前进程和当前线程。恩，平铺直叙的表达手法。
253 movl %edx, PCPU(CURPCB)
254 movl %ecx, PCPU(CURTHREAD) /* into next thread */
设置new线程的LDT描述符表，和GDT差不多，差别在于一个是公用的，一个是私有的。270行之下的USER_LDT在NetBSD中用来模拟windows，呵呵，我猜想FreeBSD也差不多吧，晕，猜想。。。。汗一个先。
256 /*
257 * Determine the LDT to use and load it if is the default one and
258 * that is not the current one.
259 */
260 movl TD_PROC(%ecx),%eax
261 cmpl $0,P_MD+MD_LDT(%eax)
262 jnz 1f
263 movl _default_ldt,%eax
264 cmpl PCPU(CURRENTLDT),%eax
265 je 2f
266 lldt _default_ldt
267 movl %eax,PCPU(CURRENTLDT)
268 jmp 2f
269 1:
270 /* Load the LDT when it is not the default one. */
271 pushl %edx /* Preserve pointer to pcb. */
272 addl $P_MD,%eax /* Pointer to mdproc is arg. */
273 pushl %eax
274 call set_user_ldt
275 addl $4,%esp
276 popl %edx
277 2:
278
279 /* This must be done after loading the user LDT. */
280 .globl cpu_switch_load_gs
281 cpu_switch_load_gs:
282 movl PCB_GS(%edx),%gs
恢复调试寄存器。
284 /* Test if debug registers should be restored. */
285 testl $PCB_DBREGS,PCB_FLAGS(%edx)
286 jz 1f
287
288 /*
289 * Restore debug registers. The special code for dr7 is to
290 * preserve the current values of its reserved bits.
291 */
292 movl PCB_DR6(%edx),%eax
293 movl %eax,%dr6
294 movl PCB_DR3(%edx),%eax
295 movl %eax,%dr3
296 movl PCB_DR2(%edx),%eax
297 movl %eax,%dr2
298 movl PCB_DR1(%edx),%eax
299 movl %eax,%dr1
300 movl PCB_DR0(%edx),%eax
301 movl %eax,%dr0
302 movl %dr7,%eax
303 andl $0x0000fc00,%eax
304 movl PCB_DR7(%edx),%ecx
305 andl $~0x0000fc00,%ecx
306 orl %ecx,%eax
307 movl %eax,%dr7
还记得249 movl %eax,(%esp)这句吗？我们在堆栈返回地址填充了new线程的eip，ret就返回到new线程上一次(因为它那个时候被剥夺了执行权)call cpu_switch之下的一条语句去执行。
308 1:
309 ret
310
Now, a new world, enjoy.
小结：
可以看出，FreeBSD的调度机制与策略分隔的十分明显，数据流参数全部包括在thread结构变量old,new中，也就是说，如果我们在上层替换掉调度策略的话，就可能提供一种新的调度器。
参考
[1] sys/i386/i386/swtch.s
[2] FreeBSD操作系统设计与实现
[3] ULE: A Modern Scheduler for FreeBSD
[4] Operation System concept(the six edition)
[5] Computer Systems: A Programmer's Perspective (CS:APP)
[6] A guide to how the FreeBSD kernel manages the IA32 processors in Protected Mode
[7] IA-32 Intel® ArchitectureSoftware Developer’s Manual
|
