码上讲进程线程调度
进程线程调度
对于进程线程调度大家肯定都不陌生，都能够说上两句，比如什么进程是资源分配的基本单位，线程是调度的基本单位，进程有独立的地址空间，线程没有，线程与进程里面其他的线程共享资源，再有就是花样百出的调度策略。但是可能很多人对进程线程调度的内部情况还是不太清楚，只是说对这知识很熟悉，产生了理所当然的感觉。
本文就从一个简单的线程进程调度设计上来帮助大家理清进程线程的区别，缕清调度这条线。
一 线程
我们先来看看线程，在POSIX定义的线程标准中，线程是这样创建的，函数原型如下：
第二个参数：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 本定义如下：
然后用名字来标识线程，还有就是定义了一个栈，每个线程都有自己单独的栈，而且注意栈指针是线程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)，发生的过程如下:
这就是函数执行的过程，而我们的线程第一次运行就是要模拟这个过程。也就是说我们要在栈中先放好线程函数的参数，再留下一个哑地址，这是一个用不到的地址，只是占位用。前面说过，返回地址前就是参数，我们也得按照这个约定来，虽然用不上这个返回地址，但也得设置来形成正确的栈帧。随后再放置一个函数指针，ret 时它就是栈顶元素，然后就会去执行这个函数，线程就运行起来了。这儿一定要注意 ret 时栈顶是线程函数指针而不是我们设置的那个返回地址
线程一般传的函数原型为：
调度程序上下文
终于来到了第三部分，这部分是要定义调度程序的上下文。为什么要定义这个，与调度相关。所以要提前说明以下调度，不管什么操作系统，调度程序做的事情都可以归结为两步：
- 选一个线程
- 切换线程
我们的调度程序为schedule()函数，切换函数为swtch(cur, next)。切换线程涉及到底层操作，直接使用汇编指令编写更加方便，而写汇编就是所有的指令都得亲历亲为，不像用高级语言编写程序，有编译器为你编译。编译器编译是要遵循一定规则编译的，例如上述所说的调用约定。我们写的切换函数会在c文件里面被调用，那么能够正确被调用要求我们自己写的汇编也得按照约定来。
这里我们就需要遵循一个规则，ABI，Application Binary Interface，程序二进制接口。不同于熟悉的API，它是更加底层的一套规则，是编译方面的约定。例如上述的调用约定就属于ABI。ABI里面规定了哪些为被调用者保存寄存器，有ebx, ebp, esi, edi, esp。意思是说这5个寄存器归主调函数所用，为了不破坏主调函数的寄存器结构，被调用函数需要将这些寄存器保存下来。
因此有了如下的上下文结构：
到此终于把线程创建需要的结构定义好了，下面就来具体创建线程，伪码如下：
下面来看线程怎么运行，也就是thread_exec(thread)函数，其实这里面应该没这函数的，因为线程是要经过调度才能上CPU，才能运行的。这里只是先提前让大家看看我们的线程是怎么运行的，毕竟说了那么多次，线程第一次运行很特殊，靠返回运行，伪码如下：
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，如果减到零了，调用调度程序。伪代码如下：
而我们的内核栈和task_struct是在一个页面内的，esp指向栈顶，也是个地址值，看到这有没有想到怎么获取当前线程结构体？很简单，直接将 esp 值的低3位变成0就是当前的task_struct* thread。tag转换成thread也是同理，有没有很巧妙？我当时看到这的时候惊讶了半天，太简单巧妙了，毕竟当时看xv6时获取当前进程懵逼了好久好久，这个就简单明了多了。
ready_queue，就绪队列，里面存放的全是task_struct里面的结点元素，以此来将所有的状态位RUNNABLE 的task_struct 串起来，这方面就是数据结构队列的简单应用，不再多说。这里面只出现了一个就绪队列，实际系统中应该会有多种队列，比如全部进程/线程的队列，根据调度策略不同可能还会有多级优先级队列等等。
2 swtch(cur, next)
还是先来看代码吧：
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可以如下定义：
2 特权级3用户态下工作
进程的另一特点就是运行在 3 特权级，进程的创建在内核态下实现，如果调度的是进程，需要从内核态返回用户态，高特权级转成低特权级。而CPU一般不会允许从高特权级转回低特权级，只有一种情况例外，中断返回。
线程运行是模仿函数调用然后返回执行的，而这里我们进入 3 特权级则是模仿中断然后返回到 3 特权级，实有异曲同工之妙。关于中断栈帧的结构体线程那一块已经定义，这里不再赘述，直接看进程的创建。
进程的创建
这里进程的创建，我们只说第一个进程也就是 init 进程的大致创建过程，因为后面所有的进程都是 init 进程的子进程，通过fork，exec等系统调用来实现的，涉及的内容挺多的，我后面单独写一篇关于创建新进程的文章。
init 进程的创建建立在线程之上，所以创建线程的步骤一个都不会少。而进程的 pgdir 是有实际值的，所以 thread_init 中得初始化 pgdir 。
剩下最大的不同在于填充中断栈帧，我们上述实现的线程只是在内核中运行，没有返回到用户态这一步，所以没有填充中断栈帧。而填充栈帧就像创建线程时填充函数指针，参数，返回地址一个道理，就是为了装的像，方便返回执行。这里我们将中断栈帧填充到中断栈，前面一直给中断预留的有空间，用处就在这。
但还有一个问题，我们的进程在线程之上实现，想想线程是怎么运行的？弹出调度程序的上下文后 ret 返回执行线程函数，如果我们不做改变，ret 后那么执行流都跑其他地方去了，根本没机会中断返回。所以这里需要将线程函数变为填充中断栈帧的函数，中断栈帧也是有 eip 的，我们将程序的入口地址放在这里。如此既保持了线程调度运行的一致性，又能填充中断栈帧然后中断返回，一举两得。
综上所述我们来缕缕创建进程需要的步骤：
- 创建线程，线程函数用来填充中断栈帧
- 创建进程需要的页表，调度时需要切换页表
有个认识之后，来看看具体的伪码：
四 设计说明
关于进程线程调度的一个简单设计到此也就结束了，这个设计思路主要来源于操作系统真象还原，融和了xv6，linux0.11的一些想法，以及自己的思考。这个设计思路应该算是最简单的了吧，虽然简单也足以让我们了解进程线程调度的本质。
1 栈方面的说明
关于这个设计私以为说的还是够清楚了，如果没看懂可以抓住栈，栈顶来看，不管看哪个系统源码，我认为，只要把其中栈的变化，栈顶的变化弄清楚了，问题就解决大半了。说到栈再多提几句：
kstack
这个设计的kstack元素，虽然我们的目的是让它指向栈顶，但要清楚这是我们定义在内存里面的一个变量，不可能时刻指向栈顶，只有esp寄存器才时刻指向栈顶，只有执行到修改kstack值的时候可能才会指向栈顶。主要是我自己在上面栽过跟头，说明一下警示自己和希望大家不要像我犯这种低级错误。
内核态转用户态时要保存内核栈栈顶值
主要是说在上述中断返回时需要将栈顶值记录在 tss 结构中的esp0位置处，上述的伪码中没有涉及，因为相关知识、细节需要说明的挺多，以后细说。在这简单解释一下，从用户态陷入内核态时需要换成内核栈，这个内核栈的栈顶值就保存在tss.esp0中，CPU会自动去取。
2 内核线程，轻量级进程，用户线程
我们上述创建的线程就属于内核线程，只运行在内核态，不受用户态影响。
轻量级进程是内核支持的用户线程，是内核线程的抽象，每个轻量级进程都会与一个内核线程相关联，以此来实现由内核支持的用户线程。这个关联现在是NPTL来做的，实现了对POSIX标准的兼容。
而用户线程从头至尾的一切工作如创建调度等等，都是独立于内核之外，仅在用户态下实现，内核并不支持。
所谓内核支持与否，可以根据我们上述的设计这样简单理解，创建线程之后能被加进内核的就绪队列然后被内核的调度器调度，那就说明内核是支持的。反之普通的用户线程，内核是看不到的，内核看到的就只是整个进程，也只会把进程加进就绪队列，调度进程之后用户态下的调度器再调度用户线程。
所以想要真正实现线程机制，内核线程是最基本的要求。内核支持的用户线程——轻量级进程与内核线程是单射关系，每个轻量级进程都有一个内核线程与之相对应，这就是常说的一对一模型。而普通用户线程的CPU调度实体还是进程，整个进程只对应的一个内核线程，即进程里面的多个用户线程也只对应一个内核线程，这就是多对一模型。
五 总结
看完这个简单设计和说明，再来总结一番：线程就是运行某个函数，因为多了PCB，栈等结构组织所以可以被加进队列然后被调度运行。进程在线程之上实现，最主要的区别就是有自己的虚拟地址空间，也就是页表，然后是在3特权级用户态下运行。
1 常见问题说明
进程是资源分配的最小单位，而线程是调度的最小单位
进程有自己的虚拟地址空间，这个空间里面包括了各种资源，例如堆，栈，各种段，甚至包括线程的一些必要资源，它们其实都是虚拟地址空间的一块区域。所以说进程是资源分配的最小单位。
线程呢？线程就是一条执行流，用来执行某个函数，而且线程是依靠进程存在，因为上面说了，资源都是进程管理的。所以如果进程只有一条执行流，那么是可以看作线程的。如果里面有多个线程且为内核所支持，那么每个线程是可以被内核单独调度的。那如果是多个普通的用户线程呢？这个我认为看个人理解吧，从内核看调度的实体上的确是整个进程，从用户态看呢，调度的又是进程里面的某个线程。
关于普通用户线程仁者见仁，智者见智吧，不要太陷入理论。能够在脑海里面大概地模拟出进程线程是怎么创建的，怎么调度的就行了。而且现今的操作系统内核大都支持线程的。所以呢总的来说进程的确是资源分配的最小单位，而线程也是调度的最小单位。
线程提速
线程能给程序运行提速的原理就在于，多个线程能够并行执行，如果只有一个CPU，那就是伪并行，也是能提速的。
举个例子来说明：有A B两个进程，A有三个线程，a，b，c，B只有它自己一个执行流。所以调度时，就绪队列上 A 有三个结点能被调度，而B只有一个，这样算下来 A 运行的速度肯定比 B 快。
但要清楚如果只有一个CPU的情况下，由于线程切换的开销，多线程进程运行的总时间应该是多于单线程进程的。只是说开了多个线程就能够去抢占更多的时间片资源，运行的效率会更高。
使用多线程还有一点能够提速，就是遇到阻塞的情况，比如说 A 进程的 a 如果阻塞，bc两个线程还能正常运行。而如果是 B 运行到某个地方阻塞的话，B整个进程就阻塞了。当然这也是讨论内核支持的用户线程，如果是普通的用户线程，某个线程阻塞也会导致整个进程阻塞，因为内核是感觉不到多个线程。
2 最后总结
进程线程调度的问题如果只在上层研究，就比如操作系统课上学习的东西，应该还是比较好理解的。但是可能会觉得模糊抽象，要不就是知识点非常熟悉之后产生的理所当然的感觉。而要想真正有个清晰的认识还是得去看看码，看看是怎么设计的。
设计也不是那么简单呐，需要考虑到方方面面，前前后后的逻辑联系，就比如说本文这个设计的线程第一次运行的方式，进入 3 特权级的方式，都是模仿相应结构来设计，使系统的前后保持一致。
而本文呢就相当于是对前辈大佬们的设计再做了精简的处理，隐去了许多的细节，某些地方也不太规范妥当，还望见谅。比如汇编跟c混写，虽然的确有内联汇编形式的支持但没用，就完全当作伪代码吧。进程线程调度算是三大块息息相关的内容，不可能七千多字就能讲述清楚的，但我想最基本的原理应该说的还是比较清楚的。
好啦本文就到这里，如果哪有错或不足，还请大家批评指正；此号没有留言功能，欢迎大家私信或加我微信与我交流。