进程、线程和协程

进程 线程 协程
CPU 系统负责执行线程 一个进程含有多个线程,系统分配线程在不同的CPU上执行 线程上执行
内存 进程管理自己的内存区域 多线程共享进程的内存区域 同线程
系统负责在内存中分配调用栈,默认为 $8MB$ 用户程序在堆上分配栈,切换的时候修改 $SP$ 、$PC$ 、$BP$
切换方式 时间片耗尽后触发中断处理程序,内核负责切换线程 主动切换,让出CPU
切换内容 通用寄存器,$PC$ 寄存器,页表寄存器,TLBCPU缓存 通用寄存器,$PC$ 寄存器,CPU缓存 通用寄存器,$PC$ 寄存器
上下文 $task_-struct$ ,页表 $task_-struct$ ,页表 运行栈,寄存器

1. CPU和内存

        操作系统为进程分配了一个专门的数据结构称为进程控制块 ( $Process\ \ Control\ \ Block$ ,$PCB$ )。系统利用PCB来描述进程基本情况和运行状态,进而实现对进程的控制和管理。程序段、相关数据段和PCB构成了进程实体。PCB内的信息包括:

        线程的最直接理解就是轻量级进程,是CPU的基本执行单元,也是程序执行的最小单元,包括:

        线程是进程中的一个实体,是系统独立调度和分派的基本单位,只拥有一些运行中必不可少的资源,共享其所在线程的全部资源。在多线程操作系统中,进程的执行实际上是进程中的某个线程正在执行。Linux系统中进程和线程都使用 $task_-struct$ 结构描述,存储在一个双端循环列表中,列表存储在内核栈的末尾。
        线程的实现可以分为两类,用户级线程 ( $User-Level\ \ Thread$ ) 和内核级线程 ( $Kernel-Level\ \ Thread$ )。用户级线程中,有关线程管理的所有工作都交由应用程序完成;内核级线程中,线程管理的所有工作都交由内核完成,应用程序只有一个到内核级线程的编程接口,内核为进程及其内部的每个线程维护上下文信息。
        协程并不是一个新概念,它在 $1958$ 年就被提出。协程就是一个子任务,特点是非抢占式的调度。协程会自己判断运行状况,当满足一定条件就会主动让出CPU给其他协程,而进程或者线程的切换需要进入内核态交给内核处理。协程其实就是用户级线程。协程中的信息只包括运行栈和寄存器,后者决定了程序在代码中的执行位置。

2. 栈

        进程的内存空间中有一块栈区,PCB会存储栈区指针,表示用户空间栈。栈的初始化是由编译器和链接器计算出来的,但是栈的实时大小并不是固定的,栈也不是能无限增长的,一般为 $8MB$ 。对于主线程,其栈实际上就是进程栈。然而对于主线程生成的子线程来说,其栈是固定的,使用 $mmap(\ )$ 系统调用,也就是说不会动态增长,一旦用尽就没了。由于线程栈是从进程地址空间中 $mmap(\ )$ 映射的一块内存区域,原则上是线程私有的。
        在每一个进程的生命周期中,必然会通过系统调用陷入内核。在执行系统调用陷入内核之后,这些内核代码所使用的栈并不是原先进程用户空间中的栈,而是一个单独内核空间的栈,称作进程内核栈。进程内核栈通过 $slab$ 分配器从 $thread_-info_-cache$ 缓存池中分配出来,其大小为 $THREAD_-SIZE$ ,一般来说是一个页大小 ( $4K$ )。

union thread_union {
    struct thread_info thread_info;
    unsigned long stack[THREAD_SIZE/sizeof(long)];
}

        $thread_-union$ 进程内核栈和 $task_-struct$ 进程描述符有着紧密的联系,内核经常要访问 $task_-struct$ ,高效获取当前进程描述符是一个很重要的事。因此内核在进程内核栈头部存放了 $thread_-union$ ,从而记录了对应的进程描述符。
        进程陷入内核栈的时候,需要内核栈来支持内核函数调用,中断也是如此。当系统收到中断事件后,进行中断处理的时候,也需要中断栈来支持函数调用。由于系统中断的时候,系统当然是处于内核态的,所以中断栈是可以和内核栈共享的,具体是否共享,和处理器架构有关。
        协程可以被分为两类,一种是有栈协程,例如 $goroutine$ 和 $libco$ ,一种是无栈协程,例如C++。有栈和无栈的区别并不是运行的时候有没有栈,而是协程之间是否存在调用栈。
       很多地方又把协程称为 $subroutine$ ,也即函数,而 $coroutine$ 就是可以中断并恢复执行的 $subroutine$ 。如果把协程当作一个特殊的函数调用,那么有栈协程就是我们理想中的协程实现形式。把协程当作一个函数调用,难点在于如何切换函数,也即切换协程,最后还要切换回来。一种做法是在协程内部存储自身的上下文,并在需要的时候进行切换。上下文的本质是寄存器,所以保存上下文实际上就是把寄存器的值保存下来。在Go程序中,每个 $goroutine$ 都有自己的栈区,各个栈区隔离,初始大小为 $2KB$ ,可以按照需求增长和收缩,最大限制为 $1GB$ 。
        无栈协程的本质就是一个状态机,即所有协程本质都是同一个协程,而协程切换不过是寄存器状态的改变。从执行时栈的角度来看,所有协程共用一个系统栈,也就不必给协程分配栈。相比于有栈协程把局部变量放在新开的空间上,无栈协程直接使用系统栈,具有更好的局部性,而且中断和函数返回没有区别,更加高效。

3. 调度

        通常进程的创建、撤销以及要求系统设备完成I/O操作都是利用系统调用进入内核模式,再由内核中相应的处理程序完成的。进程切换也是内核模式下完成的,过程为:

  1. 保存处理机上下文,包括程序计数器和寄存器;
  2. 更新PCB
  3. PCB移入相应的就绪队列或者事件的阻塞队列;
  4. 找到下一个要执行的进程,更新PCB
  5. 更新内存管理的数据结构;
  6. 恢复处理机上下文。

        线程只持有一些必不可少的资源,包括线程ID、程序计数器、寄存器集合和堆栈。在进行线程切换时,只需要保存和设置少量寄存器内容即可。由于Linux中线程和进程使用相同的结构,因此在Linux中,线程和进程调度算法相同。
        Linux系统使用了一种叫做CFS ( $Completely\ \ Fair\ \ Scheduler$ ) 的可抢占支持优先级时间片动态轮转调度算法。首先会根据CPU的负载状况确定一个调度的时间区间,然后将这个区间根据各个可运行进程的静态优先级 划分给每个进程一个时间片,这个时间片即动态优先级,跟虚拟运行时间有关 ( 虚拟运行时间 = 实际运行时间 $\times$ $NICE_-0_-LOAD$ / 权重 ,其中 $NICE_-0_-LOAD = \frac{1024}{1.25^{nice}}$ )。然后将所有进程按照时间片的大小构建成一颗红黑树,每次调度时取红黑树中边上时间片最多的进程 ( 也即虚拟运行时间最少的进程 ) 运行,直到红黑树所有节点都用完了时间片就会触发下一轮调度。基本思路就是让虚拟运行时间最少的进程运行,所以叫做基本公平调度算法。
        $goroutine$ 就是协程,不同的是Go在运行时、系统调用等多方面对 $goroutine$ 调度进行了封装和处理,当遇到长时间执行或者进行系统调用时,会主动把当前 $goroutine$ 的CPU转让出去,让其他 $goroutine$ 能被调度执行。在内部实现上,进程内维护了一组数据结构和 $n$ 个线程,协程执行的代码在一个待执行队列中,由 $n$ 个线程消费。GoI/O函数进行封装,内部使用异步I/O模式,在异步I/O执行的过程中,将现有执行序列入栈,让另一个协程执行。
        Go协程使用了M-P-G模型。$M$ 为 $Machine$ ,即一个底层的操作系统线程;$G$ 即 $goroutine$ ,也就是协程;$P$ 为 $Processor$ ,是协程的管理者,Go抽象的一个处理器,通常数量等于CPU数量,运行时会绑定一个 $M$ ,当 $M$ 不可运行,比如陷入的时候,会转移到其他 $M$ 中。$P$ 中存在一个协程队列,$M$ 会消费这个队列,中途出现阻塞或者占用时间片过久都会触发协程调度。
        Go协程采用了一种无优先级可抢占FIFO时间片轮转调度算法,调度本质是给绑定在 $P$ 的 $M$ 选择下一个可以运行的 $G$ 。$P$ 中的队列会被 $M$ 按照顺序消费,同时Go启动一个特殊的不绑定 $P$ 的线程 $sysmon$ ( $System\ \ Monitor$ ),会遍历所有 $P$ ,将在 $P$ 上运行超过 $10ms$ 的协程标记为可抢占。被标记为可抢占的协程在函数调用时会触发抢占调度,重新回到队列中。当 $P$ 的队列消费完毕,就会尝试去全局的协程队列中寻找任务,如果还是没有,就会从其他 $P$ 中窃取一半任务到当前队列上。

进程、线程和协程