网络安全参考 | UNIX参考 | GPS参考 | 无线参考 | 在线手册 | OSBUG.ORG | SUNNY-NETWORK.COM
天线制作 GPS 地标
网站地图 RSS订阅
高级搜索 收藏本站
Home | 业界动态 | Open source | GNU | Linux | BSD | Solaris | AIX | HP-UX | IRIX | Mac OS X | Minix | Tru64 | SCO UNIX | Network | Security | X-Window | Database | 应用服务 | Programming | 经典著作 | 永远的纪念 | 杂项
 当前位置: Home > BSD > FreeBSD > Kernel > 文章  
FreeBSD6.0中cpu_switch调度机制分析
文章来源: bbs.chinaunix.net 文章作者: gvim 发布时间: 2006-08-14   字体: [ ]  
 

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/bsdcongli@chinaunix/bsd的审查、鼓励与支持 J

 

首先找到调度器调度机制的代码入口,该入口如下,在i386/i386/swtch.s中。

95 ENTRY(cpu_switch)

ENTRYi386/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取得两个参数,分别为oldnew。这两个参数都是指向结构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变量中。pslprocess 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里面。线形地址的高[3122]位作为对该目录的索引(为叙述方便,简写为IdxD: index directory),取得一个目录项也就是图中左边Directory EntryPage Directorypow(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寄存器。

 

因为如果线程使用相同地址空间(废话,线程的存在就是为了共享地址空间嘛,也就是说这里检查的是oldnew两个线程是否属于两个不同进程),页目录基址也不需要变换,我们自然也不需要操作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 */

                                                    /* esi161行赋值 */

                                             /* 清除活动位标志,由于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:ESPxx代表ring级别)。还有一个ring3的堆栈,那自然在用户级大家经常看见的esp,ss就可以表示了。所以这里只需要记录四个ring级别中的三个。

 

由于80x86的处理器下降ring权限时,比如ring3(用户级)下降到0,或1,或2,(或者从ring2下降到01,等)处理器自动从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_LDTNetBSD中用来模拟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线程的eipret就返回到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

 
推荐文章
·教你制作软盘上运行的FreeBSD系
·教你定制自己的压缩的FreeBSD内
 
 
↑返回顶部   打印本页   关闭窗口↓  

Google
 
Web oldhand.org unixreference.net meshmea.org
相关分类
热点文章
·教你制作软盘上运行的Fr
·教你定制自己的压缩的Fr
相关文章
·初学者入门:FreeBSD服
·FreeBSD服务器的安装与
·制作软盘上运行的FreeBS
·配置基于ADSL的防火墙
·在FreeBSD中安装双网卡
·FreeBSD,实实在在的选
·教你制作软盘上运行的Fr
·FreeBSD系统安装与配置
更多...
 
 

Copyright(c) 2001-2009 OLDHAND ORGANIZATION, All Rights reserved.
Power by DedeCms 织梦内容管理系统