2、用户级线程与内核级线程实现.md

# 用户级线程

用户级线程与内核级线程

* 线程就是要在一个地址空间下启动并交替执行的多个执行序列
* 执行序列就是一段执行中的程序，这多段程序完全可以只出现在用户态程序中，即操作系统完全不知道这些线程的存在，这样的线程被称为 用户级线程。
* 和用户级线程概念相对应的是内核级线程，能在同一地址空间中交替执行并交由操作系统管理的执行序列就是内核级线程。





总的来说

* 创建一个用户级线程就是创建出来一个可以让 CPU 切换进去的初始样子
* 线程栈有自己私有的栈（所谓的私有是指每个线程在堆栈段都有自己对立的 ESP，这样的目的是为了防止线程切换带来的混乱），其每个栈帧里还包含一个 EIP。

![在这里插入图片描述](https://img-blog.csdnimg.cn/20210121001124329.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70)






创建：thread_create（核心是构造栈帧，因为要符合 ret 指令执行时的规则）

* 实现（func 无参数）

  ```c
  thread_create(void * func)
  {
      long *stack = malloc(SIZE_OF_USERSTACK) + SOME_SIZE;
      TCB *p = malloc(SIZE_OF_TCB);
      *stack = func;
      *(stack--) = eax; //初始化执行现场，可以全是 0
      ······
      p->esp = stack;
  }
  ```

* 实现（func 有参数）

  * 通过每个线程的栈进行传参
    * 即：在栈中依次放入第二个参数、第一个参数、返回地址，并且将 ESP 寄存器设置指向存放返回地址的那个内存单元。
  * 线程创建时适当地初始化栈，使得跳入函数 func 执行时，ESP 指向将来 func 函数返回时要跳转的地址，ESP+4 处放置第一个参数，ESP+8 处放置第二个参数等等
    * 因为不能移动 ESP，但是为了读取这些参数通常会使用 EBP ，把 EBP 保存之后，将 ESP 的值赋给 EBP ，然后用 EBP 相对寻址（即“ n(%ebp)” 的操作数形式）来获取操作数

  ```c
  thread_create(void * func, void* arg1)
  {
      long *stack = malloc(SIZE_OF_USERSTACK) + SOME_SIZE;;
      TCB *p = malloc(SIZE_OF_TCB);
      *stack = arg1;
      *(stack–-) = thread_exit; //func 完成后执行线程退出系统调用
      *(stack–-) = func;
      *(stack--) = eax; //初始化执行现场，可以全是 0
      ······
      p->esp = stack;
  }
  ```

  

  


切换：Yeild

  * Yield() 也只是一个普通的用户态函数，由用户自己编写

  * Yield() 函数只要完成线程 TCB 的切换和栈切换即可

    * 不用去改变 EIP ，因为每个函数执行完都会弹栈，然后执行栈顶的函数（即把 EIP 值改为栈顶栈 SS:ESP 单元里的值，该过程由 ret 指令完成，同样把返回地址压栈也是由 call 指令完成）

    ```c
    Yield()
    {
        next = FindNext();
        push %eax
        push %ebx
        ······
        mov %esp, TCB[current].esp
        mov TCB[current].esp, %esp
        ······
        push %ebx
        push %eax
    }
    ```



# 内核级线程

## 优势

原因

* 如果一个用户级线程在内核中阻塞，则这个进程的所有用户级线程将全部阻塞。这就限制了用户级线程的并发程度，从而限制了由并发性而引起的计算机硬件工作效率提升。
* 因为在进程调度的时候，需要阻塞的这些操作（比如 读写磁盘，或者使用其他 IO 设备）都需要执行内核的程序，所以就会不给这个进程再分配时间片，然后加入阻塞队列，直到 IO 完成被中断程序进行唤醒。



区别

* 用户级线程是完全在用户态内存中制造的一个指令执行序列，即用户级线程的 TCB、栈等内容都是创建在用户态中的，操作系统完全不知道（即线程的创建、调度对操作系统都不可见）。
* 内核级线程是内核态内存和用户态内存合作制造一个指令执行序列，内核级线程的 TCB 等信息是创建在操作系统内核中的，操作系统通过这些数据结构可以感知和操纵内核级线程（即线程的创建、调度，都对操作系统可见）

* 结论：内核级线程较用户级线程而言具有更好的并发性，硬件工作效率也会更高一些



内核级线程如何提高硬件使用效率（以双核处理器为例）

![在这里插入图片描述](https://img-blog.csdnimg.cn/20210121001223137.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70)


* 如果计算机系统中有两个用户级线程，由于操作系统并不知道存在两个指令执行序列，所以只能利用到处理器中的一个核来执行其中的一个执行序列
  * 即使调用 Yield 切换到下一个执行序列，仍然只是利用一个核，双核处理器中的另一个核一直空闲
* 而如果计算机系统中创建了两个内核级线程，此时操作系统能操纵两个指令执行序列，会将核 1 分配给第一个执行序列，核 2 分配给第二个执行序列，两个核可以同时“取指 执行”，硬件工作效率得到显著提升。



内核线程比进程的优势

* 如果计算机系统中有两个进程，虽然两个进程对应的两个执行序列都可以被操作系统感知，但对应在两个进程上的两个执行序列并不适合并行地放在多核处理器中的多个核上。
  * 因为多核处理器中的多个核通常要共享 MMU（Memory Management Unit，内存管理单元）以及一些缓存等，为了避免进程之间的影响，进程之间要实现地址隔离，即每个进程要使用自己的地址空间和地址映射表，硬件 MMU 就是用来查找地址映射表的硬件，而某些缓存就用来缓存一些最近的地址映射结果。
  * 如果将两个进程并行地放在一个多核处理器的两个核上，虽然表面上可以让两个执行序列同时向前执行，但是共享 MMU 不可能同时去查两个不同的表，而且缓存也不能发挥作用了，因为进程 1 程序中地址 100 对应物理内存单元1100，而进程 2 程序中的地址 100 却对应物理内存单元 2100。
* 而两个内核级线程使用的是同一个地址空间，MMU、缓存本身都是可以共享的。所以内核级线程非常适合于多核处理器结构，而多核处理器是现代处理器设计中的一种主流技术，因此绝大多数现代操作系统都支持内核级线程。



优势总结

* 内核级线程有其优点：可以提高并发性、可以有效的支持多核处理器等等；
* 进程也有其优点：以进程为单位来分配计算机资源，方便管理，进程之间互相分离，安全性高、可靠性好等等；
* 当然用户级线程也有其优点：用户在应用程序中随意创建，创建代价小、灵活性大、同时具有一定的并发性等等。
* 因此在操作系统中，这三个概念往往是同时存在并实现的。



三者的内在关系

* （1）引出进程的目标是为了管理 CPU，即通过执行程序来使用 CPU。进程、内核级线程、用户级线程都是要执行一个指令序列，**没有本质区别，都属于 CPU 管理范畴（为了高效利用 CPU）**；
* （2）要执行一个指令序列，除了通过分配栈、创建数据结构记录以执行位置等以外，还要分配内存（显然要分配内存并将指令序列读入内存以后，程序才能被“取指 执行”）等资源，这就是进程的概念；
* （3）将进程中的资源和执行序列分离以后引出了线程概念，**进程必须在操作系统内核中创建，因为进程创建要涉及到计算机硬件资源的分配**。因此**进程中的那个执行序列实际上就是一个内核级线程**
* （4）内核级线程是操作系统在一套进程资源下创建的可以并发执行的多个执行序列，操作系统为每个这样的执行序列创建了相应的数据结构来实现对这些内核级线程控制，如切换、调度等；
* （5）同样的，上层应用程序也可以创建并交替执行多个指令执行序列，因为执行程序所需要的资源已经在创建进程时分配好了。此时启动多个执行序列所需要的 TCB 和用户栈等信息完全可以由应用程序自己编程实现，由应用程序负责操控这多个执行序列，对操作系统而言完全透明。



## 切换

对比用户级线程

* 相同
  * 用户级线程的切换，主要分为三步：TCB 的切换、根据 TCB 中存储的栈指针完成用户栈切换、根据用户栈中压入函数返回地址完成 PC 指针切换。
  * 内核级线程的切换也要完成“切换 TCB、切换栈、切换 PC 指针”这三件事
* 区别
  * 第一个重要区别：内核级线程的 TCB 存储操作系统内核中，因此完成 TCB 切换的程序应该执行在操作系统内核中
    * 即用户级线程通过调用用户态函数 Yield() 完成切换，而内核级线程必须进入内核才能引起切换。
    * 内核级线程间切换从进入内核---中断开始，因为中断是从用户态进入内核态的唯一方式。
  * 第二个重要区别：需要一个内核栈来控制指令执行位置的跳转，即切换栈要同时切换用户栈和内核栈
* 综上
  * 用户级线程切换的核心是根据存放在用户程序中的 TCB 找到用户栈，通过用户栈切换完成用户级线程的切换，整个切换过程通过调用 Yiled()函数引发。
  * 内核级线程切换的核心是首先进入操作系统内核并在内核中找到线程 TCB，进而根据 TCB 找到线程的内核栈，通过内核栈切换完成内核级线程切换，整个切换过程由中断引发。







“int/iret”时栈发生的变化（int 指令会自动压栈，压入当前的 SS:ESP；iret 指令也会同样的弹栈然后返回)

* “int”指令执行时，会**找到当前进程的内核栈**，然后将用户态执行的一些重要信息，如当前程序执行位置 CS:EIP、当前用户栈栈顶位置 SS:ESP 以及标志寄存器 EFLAGS 压到内核栈中。

  * 实际上，所有外部中断，比如时钟中断、键盘中断、磁盘读写完成中断等，都会引起上述动作。
  * 至于返回用户态还是内核态，要看中断时的段寄存器值

  ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210121001240374.png)


* iret 指令正好是 int 指令的逆过程。



第二步：调用 schedule，引起 TCB 切换

* 在中断处理程序中，如果发现当前线程了启动了磁盘读写等操作，即发现当前线程应该让出 CPU 时，系统内核就会调用 schedule() 函数来完成 TCB 的切换
  * 具体做法很简单，例如在向磁盘发出读写指令以后，将当前线程（可以定义一个内核全局变量 current 来指向当前线程的 TCB）的状态修改为阻塞，具体代码实现为 current->state = 阻塞，并将 current 添加到一个等待某个磁盘块读写完成的等待队列链表上。接下来调用函数 schedule() 实现 TCB 切换。
* 为了完成 TCB 的切换，schedule() 函数首先从就绪队列中选取出下一个要执行线程的 TCB。
* 找到下一个 TCB 以后，此处用 next 指针指向这个 TCB，利用current 和next 指针指向的信息就可以开始内核级线程切换的第三阶段了。



第三步：内核栈的切换（也是schedule() 中执行）

* 将当前的 ESP寄存器存放在 current 指向的 TCB 中，再从 next 指向的 TCB 中取出 esp 字段赋值给 ESP 寄存器。
* 由于现在执行在内核态，所以当前寄存器 ESP 指向的就是当前线程的内核栈，而放在 TCB 中的 esp 也是线程的内核栈地址，所以这样的切换是内核栈切换



第四步：中断返回准备

* 为内核级线程切换的最后一段 用户栈切换做准备，同时也和内核级线程切换的第一段 中断进入相对应。

* 在这一阶段中，要将存放在下一个线程的内核栈（因为内核栈已经切换完成）中的用户态程序执行现场恢复出来，这个现场是这个线程在切换出去时由中断入口程序保存的。

* 以system_call 为例，此时要用 pop 将压到内核栈中的寄存器恢复出来，即：

  ```assembly
  popl %ebx
  popl %ecx
  popl %edx
  pop %fs
  pop %es
  pop %ds
  ```

  * 用户级线程没有恢复寄存器现场这个步骤，因为用户级线程都是一个进程内的，都是共用这些的



最后一步：用户栈切换

* 实际上就是切换用户态程序 PC 指针以及相应的用户栈，即需要将 CS:EIP 寄存器设置为当前用户程序执行地址，将 SS:ESP 寄存器设置为当前用户栈地址就可以
* 这两个信息现在就在这下一个线程的内核栈中，只要执行一句 iret 指令就可以完成这个切换了（因为 iret 指令的设定就是弹栈得到 CS:EIP 和 SS:ESP）



![在这里插入图片描述](https://img-blog.csdnimg.cn/20210121001842483.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70)

## 创建

创建内核级线程的关键：初始化 TCB、内核栈和用户栈 

* （1）创建一个 TCB，主要存放内核栈的 esp 指针；
  * 只要申请一段内核态内存作为内核栈，并在初始化内核栈内容后将栈顶位置填写到新申请的 TCB 中即可
* （2）分配一个内核栈，其中主要存放用户态程序的PC 指针、用户栈地址以及执行现场；
* （3）分配用户栈，主要存放进入用户态函数时用到的参数等内容。
  * 和前面用户级线程中讨论过的参数处理没有任何区别
  * 内核栈和用户栈不用刻意建立关联，用户态的代码执行时，一定有一个相对应的内核栈地址保存在 current



内核栈的初始化

* 核心也是构造栈帧，要符合 iret 指令执行时的规则，因为时钟中断在调用schedule 切换 pcb 时就是改变一下 esp，然后 iret，完成pcb 的切换

* 假定指针变量 krnstack 指向新申请的内核栈，则要完成内核栈初始化的第一部分代码就是（栈顶是内存地址最小的）：

  ```c
  /**
   * 和 iret 指令对应
   */
  /**
   * 对于内核线程的话，那么 ss 跟进程相同即可，只需改变 sp，因为共享地址空间
   * 对于新创建的进程，那么 ss 要换位给这个进程分配的地址空间
   */
  *krnstack = 用户栈的段选择子（即 ss）; //例如是 0x17
  *(krnstack-4) = 用户栈的偏移; //是新申请的用户栈地址
  *(krnstack-8) = eflags; //不是重点，可以随意设置
  /**
   * 对于内核线程的话，那么 cs 跟进程相同即可，只需改变 ip，因为共享地址空间
   * 对于新创建的进程，那么 cs 要换位给这个进程分配的地址空间
   */
  *(krnstack-12) = 用户代码段的段选择子（即 cs）; //例如就是 0x0f
  *(krnstack-16) = 用户程序入口地址; //如线程用户态函数地址 A()
  ```

* 内核栈中下一部分要存放的信息应该是回到用户态程序执行时的执行现场

  * 即如果在首次执行用户态程序时需要让某些通用寄存器取特定数值时，就应该将这些数值初始化在内核栈中
  * 比如该线程对应的用户程序入口函数 A 在首次执行时需要让 eax=0，此部分就应该有初始化语句：*(krnstack-20) = 0;

* 当 schedule 执行完内核栈切换，在要进行返回的时候，那么对于全新开辟的栈帧，里面没有正确的返回地址，而是返回到了上面 SS 栈顶 krnstack-20（即初始化的地方） ，但那个并不是返回后要继续执行的地方

  * 执行完栈的切换就到了上面说的第四阶段，所以改为 first_return_from_kernel（就是那段 pop 恢复寄存器现场的程序）的地址即可

    ```
    *(krnstack-24) = first_return_from_kernel; 
    ```