码上讲进程线程调度

发表于 3年以前 | 总阅读数：355 次

进程线程调度

对于进程线程调度大家肯定都不陌生，都能够说上两句，比如什么进程是资源分配的基本单位，线程是调度的基本单位，进程有独立的地址空间，线程没有，线程与进程里面其他的线程共享资源，再有就是花样百出的调度策略。但是可能很多人对进程线程调度的内部情况还是不太清楚，只是说对这知识很熟悉，产生了理所当然的感觉。

本文就从一个简单的线程进程调度设计上来帮助大家理清进程线程的区别，缕清调度这条线。

一线程

我们先来看看线程，在POSIX定义的线程标准中，线程是这样创建的，函数原型如下：

第一个参数：thread，用来储存线程的id

第二个参数：attr，表示创建线程的类型，一般默认设为NULL就好

第三个参数：start_routine，是一个函数指针

第四个参数：arg，函数参数，传给上述函数指针指向的函数。因为只有这一个形参作为start_routine的参数，所以一般将参数封装成一个结构体再传过去。

私以为这四个参数的核心应该是后面两个参数，函数以及它的参数，有了它俩，线程才有意义对吧。从这儿其实就已经能够看出，线程也就是执行一个函数。只是这个“函数”有些特别，它可以单独上CPU运行，而不是像其他的普通函数只是附带地被能够上CPU的线程调用执行。

所以线程就像是一个载体，它能载着函数单独地上CPU。那是什么原因造成线程如此特别，任务同样是执行某个函数，为什么线程就能够被调度而单独上CPU呢？举个可能不太恰当的例子，一堆木头和一个木车有什么区别？就在于木车有特殊的结构组织，所以木车就可以单独地行驶，而木头呢？只能装在木车上然后被运到某个地方。同理呢，线程相较于函数就特殊在它有特殊的结构组织，比如PCB，栈，寄存器组等。

了解了线程的本质后，我们来具体设计一个很简单很简单的内核线程，看看线程内部的具体情况，从创建到运行经历了哪些过程，下面正式开始定义线程的一些数据结构：

1 PCB(task_struct)

PCB，Process Control Block，程序控制块，简单的一句话来说，PCB里面集合了一个进程/线程运行过程当中所有必要的信息，所以PCB就是进程/线程的标志，他们之间是一一对应的关系。

而在Linux里面进程线程的PCB都是用结构体 task_struct 来定义的，所以其实Linux里其实没有严格的进程和线程之分，线程也称为轻量级进程。

PCB里面会存放哪些信息呢？在这儿引用以下《操作系统精髓与设计原理》的内容，PCB里面会存放以下信息：

标识符：与进程相关的唯一标识符，用来区别正在执行的进程和其他进程。
状态：描述进程的状态，因为进程有挂起，阻塞，运行等好几个状态，所以都有个标识符来记录进程的执行状态。
优先级：如果有好几个进程正在执行，就涉及到进程被执行的先后顺序的问题，这和进程优先级这个标识符有关。
程序计数器：程序中即将被执行的下一条指令的地址。
内存指针：程序代码和进程相关数据的指针。
上下文数据：进程执行时处理器的寄存器中的数据。
I/O状态信息：包括显示的I/O请求，分配给进程的I/O设备和被进程使用的文件列表等。
记账信息：包括处理器的时间总和，记账号等等。

如今的Linux里面的 task_struct 结构体定义有好几百行代码，而且里面还包含了好多结构体，全部扩展开来的话都上千行了。而我们这里只定义几个元素，能弄清楚线程最基本的原理即可。第一版 task_struct 本定义如下：

我们定义了线程的栈，状态，名字。应该都好理解，线程也有自己的状态，状态定义如下：

本文里面用不到这么多状态，只会用到RUNNABLE和RUNNING。

然后用名字来标识线程，还有就是定义了一个栈，每个线程都有自己单独的栈，而且注意栈指针是线程PCB的第一个元素，这儿是有特殊用处的，后面会说，这儿只是提一句。

另外我们的PCB信息很少，只是示范性展示原理，栈也不用太大，所以直接将内核栈和PCB放在同一页，上面作为栈用，下面作为PCB。布局如下图所示：

2 栈的定义

前面定义了线程的PCB，比较简单，难就难在栈的定义，准确说来是线程创建时栈的区域划分。线程的创建跟运行是息息相关的，线程的运行可以分为两种情况：第一次运行和非第一运行。非第一次运行时线程所有的数据结构，资源等都是既在的，不需要我们手动去定义。而第一次运行需要的信息是要我们手动去设置的，为了一致性，我们创建时线程时应该模仿着非第一次运行的情况来创建结构信息。

那么非第一运行时线程的结构组织是怎样的呢？线程要上CPU，那肯定是发生了调度，谁又来触发调度呢？我们这儿只考虑时钟中断引起的调度。那么线程的内核栈结构组织应该很明确了，从上倒下应该是：中断栈帧，期间函数调用的参数返回地址，调度程序的上下文。目前感觉很模糊抽象没关系，有个大概印象，看完本文后会感觉豁然开朗。

中断栈帧

这就是中断栈帧，中断时上下文信息就保存在这儿，前文已经详细讲过中断，只是没说这些寄存器保存到哪，如今清楚了，保存到内核栈里面。这儿我们只是为了方便统一，所以把所有的寄存器全部定义了，实际上为了效率中断时只会压入必要的寄存器。不熟悉的可以翻翻前文，中断，时钟，键盘这三篇文章，在此就不赘述了。

参数地址

接下来定义第二部分，参数和地址，这可是线程能运行的关键。第二部分和线程第一次运行紧密相关，所以得先说说线程第一次怎么运行的。线程的运行就是执行函数，某个函数被执行说明执行流发生了变化，执行流发生了变化说明 cs:eip 的值发生了改变。而改变 cs:eip 的值就只有 call, ret, jmp 三种指令，一般的函数调用我们使用 call 指令，而这里为了与后面调度一致，运行函数我们使用 ret 指令。

来仔细了解一下 ret 指令，ret 指令其实等价于 popl %eip 所以过程分为两步：

修改eip，将栈顶的值存放到 eip 寄存器中。eip 中存放的是下条指令地址，所以使用 ret 指令的时候，栈顶一定会是条指令的地址，否则会出错，通常为主调函数 call 指令下一条指令地址。
esp 加 4。

因此我们可以模仿函数调用，自己在栈里设置好栈帧，把要执行的函数地址放到栈顶，然后 ret，就能返回执行函数了。

那函数调用时的栈帧什么样的？我们来复习复习，这与调用约定有关，c 语言默认的调用约定是 cdecl，举个简单的例子来看看c中怎么调用函数的，比如说函数 funcA 调用 funcB(param1, param2)，发生的过程如下:

而栈中情况如下：

所以综上所述：函数调用时要先从右至左压入被调用函数需要的参数，再留下主调函数的返回地址(call指令下一条指令的地址)，然后跳转去执行被调函数。函数执行完后返回，由主调函数来清理参数占用的栈空间。正是由于调用约定，被调函数就知到返回地址的上面就是参数，运行时就会去相应地方拿取参数然后执行。

这就是函数执行的过程，而我们的线程第一次运行就是要模拟这个过程。也就是说我们要在栈中先放好线程函数的参数，再留下一个哑地址，这是一个用不到的地址，只是占位用。前面说过，返回地址前就是参数，我们也得按照这个约定来，虽然用不上这个返回地址，但也得设置来形成正确的栈帧。随后再放置一个函数指针，ret 时它就是栈顶元素，然后就会去执行这个函数，线程就运行起来了。这儿一定要注意 ret 时栈顶是线程函数指针而不是我们设置的那个返回地址

线程一般传的函数原型为：

所以栈中第二部分需要定义的数据结构差不多也就明了了，定义如下：

这个结构体只有线程第一次运行会用，后面都不会再用，因为我们这是在模仿函数调用，而运行起来后是真的存在函数调用，不需要再用到这个结构，虽然结构可能不太一样，就在于比起函数调用多了一个元素——函数指针 eip。

调度程序上下文

终于来到了第三部分，这部分是要定义调度程序的上下文。为什么要定义这个，与调度相关。所以要提前说明以下调度，不管什么操作系统，调度程序做的事情都可以归结为两步：

选一个线程
切换线程

我们的调度程序为schedule()函数，切换函数为swtch(cur, next)。切换线程涉及到底层操作，直接使用汇编指令编写更加方便，而写汇编就是所有的指令都得亲历亲为，不像用高级语言编写程序，有编译器为你编译。编译器编译是要遵循一定规则编译的，例如上述所说的调用约定。我们写的切换函数会在c文件里面被调用，那么能够正确被调用要求我们自己写的汇编也得按照约定来。

这里我们就需要遵循一个规则，ABI，Application Binary Interface，程序二进制接口。不同于熟悉的API，它是更加底层的一套规则，是编译方面的约定。例如上述的调用约定就属于ABI。ABI里面规定了哪些为被调用者保存寄存器，有ebx, ebp, esi, edi, esp。意思是说这5个寄存器归主调函数所用，为了不破坏主调函数的寄存器结构，被调用函数需要将这些寄存器保存下来。

因此有了如下的上下文结构：

再这里我们只定义了 4 个寄存器，并没有 esp，这是因为 esp 会由调用约定来保证，再者 esp 还会保存到 kstack 里面，后面再详述。

到此终于把线程创建需要的结构定义好了，下面就来具体创建线程，伪码如下：

看个详细流程图帮助理解：

伪码配上流程图应该很清晰了，就不再解释说明了。

下面来看线程怎么运行，也就是thread_exec(thread)函数，其实这里面应该没这函数的，因为线程是要经过调度才能上CPU，才能运行的。这里只是先提前让大家看看我们的线程是怎么运行的，毕竟说了那么多次，线程第一次运行很特殊，靠返回运行，伪码如下：

先将线程内核栈的栈顶赋给esp寄存器，然后弹出context 里定义的 4 个寄存器，再 ret 就返回执行线程函数了。

ret 时栈顶元素是线程函数的地址，将其赋给 eip 之后就改变了执行流，执行线程函数。由于函数调用约定，线程函数知道目前的栈顶为返回地址，返回地址前面为参数。当然这是在刚运行函数的时候，通常函数里面有个pushl %ebp 的步骤，那栈顶就不是返回地址了。总之由于约定，函数能够找到自己需要的参数然后执行。不熟悉的可以再仔细看看32位机器函数调用方面的知识。

二调度

说完线程的创建运行，接下来说任务的调度，进程方面的问题放在后面，因为进程就是比线程多了一些东西，所以进程是可以在线程的基础上实现的。因此只要搞清楚了线程的执行和调度，进程也就好理解很多。

废话不多说，前面说过调度 schedule() 函数主要做两件事

选取下一个线程
调用切换线程函数switch(cur, next)

1 挑选一个线程

先说第一件事：挑选出一个线程。这又可以引发两个问题：

去哪儿挑选？
挑选的原则？

PCB就是线程的标识，它记录了线程所有需要的信息，如果我们把所有线程的PCB集合起来，不就有地方挑选了？这里我们采用队列的形式将所有线程的PCB串起来，将这个队列设为ready_queue。这需要在 task_struct 里添加一个队列结点。

挑选的原则就是调度策略了，我们用“带优先级的时间片轮转法”来举例。因为我感觉更像时间片轮转法，但优先级又会稍加影响，所以取这名字。这里需要向PCB中添加 priority 表示优先级，添加 ticks 表示还可以运行的时钟滴答数。

所以现在的PCB如下所示：

我们只来讨论时钟中断情况下触发的线程调度。时钟中断就不具体说了，不太熟悉的可以看看前文讲的时间管理大师一文。前文只简略说了一下时钟中断处理函数，本文来往里面添点料。

我们的调度策略如下：priority 表示每次线程上CPU时能够运行的滴答数，ticks 记录该线程还能继续运行的滴答数，每次时钟中断ticks减1，如果减到零了，调用调度程序。伪代码如下：

接下来就是 schedule 函数，先直接看伪码吧，我们的调度策略很简单，而且只讨论时间片用完的情况，直接看码差不多也就懂了

流程应该很清楚明了，只说两点，函数get_cur_thread() 和函数tag2thread()，这两个函数都是要得到task_struct，实现原理都是一样的。我们分配内存时都是一页一页4KB的分配，task_struct* 类型的元素是个地址值，它指向这一页内存的底部，所以它的低三位应该是为零的。

而我们的内核栈和task_struct是在一个页面内的，esp指向栈顶，也是个地址值，看到这有没有想到怎么获取当前线程结构体？很简单，直接将 esp 值的低3位变成0就是当前的task_struct* thread。tag转换成thread也是同理，有没有很巧妙？我当时看到这的时候惊讶了半天，太简单巧妙了，毕竟当时看xv6时获取当前进程懵逼了好久好久，这个就简单明了多了。

ready_queue，就绪队列，里面存放的全是task_struct里面的结点元素，以此来将所有的状态位RUNNABLE 的task_struct 串起来，这方面就是数据结构队列的简单应用，不再多说。这里面只出现了一个就绪队列，实际系统中应该会有多种队列，比如全部进程/线程的队列，根据调度策略不同可能还会有多级优先级队列等等。

2 swtch(cur, next)

还是先来看代码吧：

算是经典函数了，xv6里面也是这么实现的，几乎一模一样，我们来仔细分析一下，先来看看调用swtch时栈中的情况：

1、前两个 mov 指令 获取 cur, next 存到eax, edx寄存器中

2、**4 个 push 指令保存上下文，前文说过这是ABI的规则，需要被调用者保存这几个寄存器**

3、接着 movl %esp, (%eax) 保存当前线程的栈顶值，前文说过 esp 也是被调用者保存寄存器之一，除了调用约定保证之外，还有个保存地点就在这儿了，只是与其他4个寄存器保存方式不同而已。

仔细看看保存在哪？(%eax)，eax 里面存放的是线程 cur 的地址，而 task_struct 的第一个元素 kstack 的地址也是eax，那么(%eax)就应该指的是元素 kstack，也就是说栈顶值保存在 kstack 里，这也是 kstack 的意义所在，指向栈顶。另外这就是 kstack 为 task_struct 第一个元素的好处所在。

4、理解上面之后 movl (%edx), esp 也就理解了，(%edx) 是线程 next 的 kstack 的值，也就是 next 栈的栈顶值，然后将它赋给 esp 寄存器。这就是最为关键的的换栈步骤。

5、然后 4 个 popl 指令，弹出 next 执行调度时候的上下文，使得 esp 指向 next 栈中的返回地址，最后 ret 返回，至此线程就切换了。

注意重点标注的 next ，第四步过后栈已经切换了，弹出的所有东西都是 next 的。

这个过程是不是与前面的线程执行函数很像，前面一直提到的一致性就在这里体现，线程执行函数就是模仿 swtch 来写的，所以以后线程要运行，只要添加到就绪队列就行了，正式上CPU执行是靠调度程序调度来完成的。

再来看看内核栈的变化图仔细缕缕：

上述就是线程切换调度的全过程，这下可以解开线程第一次运行为什么要那么布局的问题，就是为了一致性方便操作。

三进程

上述的线程的创建，运行，切换已经说完，下面说说进程，进程咱们在这儿略讲，关于进程的知识还是很多的，包括特权级，内存布局，用户态等等，在这我们只是说说进程与线程有哪些实际上的区别。

1 单独的地址空间

根据大多书上的理论知识，目前我们应该很清楚，进程就是比线程多了一些东西，而最重要的应该是多了自己的虚拟地址空间。

线程拥有的资源很有限，只有个栈，然后在上面建立中断栈帧，运行必要的上下文等，也就是通常书上所说的寄存器资源。而进程拥有整个虚拟地址空间，整整 4 GB，它能在上面建立的东西可就太多了，堆栈，数据代码段等等，甚至还包括了线程所拥有的资源，这也就是为什么说线程要依赖于进程存在的原因。

所以可以说进程和线程最主要的区别就是有没有自己的地址空间，进程的其他特有的机制都是建立在地址空间之上的，而有没有地址空间就是有没有自己的页表，那么进程的task_struct可以如下定义：

前面说过，进程依据线程实现，所以进程线程用的是同一个任务结构体，只是进程的pgdir有实际的值，而线程的pgdir设为NULL。

2 特权级3用户态下工作

进程的另一特点就是运行在 3 特权级，进程的创建在内核态下实现，如果调度的是进程，需要从内核态返回用户态，高特权级转成低特权级。而CPU一般不会允许从高特权级转回低特权级，只有一种情况例外，中断返回。

线程运行是模仿函数调用然后返回执行的，而这里我们进入 3 特权级则是模仿中断然后返回到 3 特权级，实有异曲同工之妙。关于中断栈帧的结构体线程那一块已经定义，这里不再赘述，直接看进程的创建。

进程的创建

这里进程的创建，我们只说第一个进程也就是 init 进程的大致创建过程，因为后面所有的进程都是 init 进程的子进程，通过fork，exec等系统调用来实现的，涉及的内容挺多的，我后面单独写一篇关于创建新进程的文章。

init 进程的创建建立在线程之上，所以创建线程的步骤一个都不会少。而进程的 pgdir 是有实际值的，所以 thread_init 中得初始化 pgdir 。

剩下最大的不同在于填充中断栈帧，我们上述实现的线程只是在内核中运行，没有返回到用户态这一步，所以没有填充中断栈帧。而填充栈帧就像创建线程时填充函数指针，参数，返回地址一个道理，就是为了装的像，方便返回执行。这里我们将中断栈帧填充到中断栈，前面一直给中断预留的有空间，用处就在这。

但还有一个问题，我们的进程在线程之上实现，想想线程是怎么运行的？弹出调度程序的上下文后 ret 返回执行线程函数，如果我们不做改变，ret 后那么执行流都跑其他地方去了，根本没机会中断返回。所以这里需要将线程函数变为填充中断栈帧的函数，中断栈帧也是有 eip 的，我们将程序的入口地址放在这里。如此既保持了线程调度运行的一致性，又能填充中断栈帧然后中断返回，一举两得。

综上所述我们来缕缕创建进程需要的步骤：

创建线程，线程函数用来填充中断栈帧
创建进程需要的页表，调度时需要切换页表

有个认识之后，来看看具体的伪码：

再来看看流程图帮助理解，流程图只画了一部分，另一部分是线程创建流程图：

中断栈帧创建好后就可以中断返回了，这里我们是直接跳转到 intr_exit 去执行，这个函数前面的文章说过，它就是中断时压栈的逆过程。进程的创建就说到这儿，再来看看调度，需要做一些改变

改变得很少，进程有自己的页表，所以需要切换页表。而页表的切换就是将页目录地址加载到cr3寄存器，详细说明见前文的分页地址转换一文。

四设计说明

关于进程线程调度的一个简单设计到此也就结束了，这个设计思路主要来源于操作系统真象还原，融和了xv6，linux0.11的一些想法，以及自己的思考。这个设计思路应该算是最简单的了吧，虽然简单也足以让我们了解进程线程调度的本质。

1 栈方面的说明

关于这个设计私以为说的还是够清楚了，如果没看懂可以抓住栈，栈顶来看，不管看哪个系统源码，我认为，只要把其中栈的变化，栈顶的变化弄清楚了，问题就解决大半了。说到栈再多提几句：

kstack

这个设计的kstack元素，虽然我们的目的是让它指向栈顶，但要清楚这是我们定义在内存里面的一个变量，不可能时刻指向栈顶，只有esp寄存器才时刻指向栈顶，只有执行到修改kstack值的时候可能才会指向栈顶。主要是我自己在上面栽过跟头，说明一下警示自己和希望大家不要像我犯这种低级错误。

内核态转用户态时要保存内核栈栈顶值

主要是说在上述中断返回时需要将栈顶值记录在 tss 结构中的esp0位置处，上述的伪码中没有涉及，因为相关知识、细节需要说明的挺多，以后细说。在这简单解释一下，从用户态陷入内核态时需要换成内核栈，这个内核栈的栈顶值就保存在tss.esp0中，CPU会自动去取。

2 内核线程，轻量级进程，用户线程

我们上述创建的线程就属于内核线程，只运行在内核态，不受用户态影响。

轻量级进程是内核支持的用户线程，是内核线程的抽象，每个轻量级进程都会与一个内核线程相关联，以此来实现由内核支持的用户线程。这个关联现在是NPTL来做的，实现了对POSIX标准的兼容。

而用户线程从头至尾的一切工作如创建调度等等，都是独立于内核之外，仅在用户态下实现，内核并不支持。

所谓内核支持与否，可以根据我们上述的设计这样简单理解，创建线程之后能被加进内核的就绪队列然后被内核的调度器调度，那就说明内核是支持的。反之普通的用户线程，内核是看不到的，内核看到的就只是整个进程，也只会把进程加进就绪队列，调度进程之后用户态下的调度器再调度用户线程。

所以想要真正实现线程机制，内核线程是最基本的要求。内核支持的用户线程——轻量级进程与内核线程是单射关系，每个轻量级进程都有一个内核线程与之相对应，这就是常说的一对一模型。而普通用户线程的CPU调度实体还是进程，整个进程只对应的一个内核线程，即进程里面的多个用户线程也只对应一个内核线程，这就是多对一模型。

五总结

看完这个简单设计和说明，再来总结一番：线程就是运行某个函数，因为多了PCB，栈等结构组织所以可以被加进队列然后被调度运行。进程在线程之上实现，最主要的区别就是有自己的虚拟地址空间，也就是页表，然后是在3特权级用户态下运行。

1 常见问题说明

进程是资源分配的最小单位，而线程是调度的最小单位

进程有自己的虚拟地址空间，这个空间里面包括了各种资源，例如堆，栈，各种段，甚至包括线程的一些必要资源，它们其实都是虚拟地址空间的一块区域。所以说进程是资源分配的最小单位。

线程呢？线程就是一条执行流，用来执行某个函数，而且线程是依靠进程存在，因为上面说了，资源都是进程管理的。所以如果进程只有一条执行流，那么是可以看作线程的。如果里面有多个线程且为内核所支持，那么每个线程是可以被内核单独调度的。那如果是多个普通的用户线程呢？这个我认为看个人理解吧，从内核看调度的实体上的确是整个进程，从用户态看呢，调度的又是进程里面的某个线程。

关于普通用户线程仁者见仁，智者见智吧，不要太陷入理论。能够在脑海里面大概地模拟出进程线程是怎么创建的，怎么调度的就行了。而且现今的操作系统内核大都支持线程的。所以呢总的来说进程的确是资源分配的最小单位，而线程也是调度的最小单位。