进程与线程

进程 Process

进程的状态

  • 运行状态（Running）：该时刻进程占用 CPU；
  • 就绪状态（Ready）：可运行，由于其他进程处于运行状态而暂时停止运行；
  • 阻塞状态（Blocked）：该进程正在等待某一事件发生（如等待输入/输出操作的完成）而暂时停止运行，这时，即使给它CPU控制权，它也无法运行；
  • 创建状态（new）：进程正在被创建时的状态；
  • 结束状态（Exit）：进程正在从系统中消失时的状态；

挂起状态：

  • 阻塞挂起状态：进程在外存（硬盘）并等待某个事件的出现；
  • 就绪挂起状态：进程在外存（硬盘），但只要进入内存，即刻立刻运行；

为什么挂起：

  1. 节省物理内存
  2. sleep让进程间歇挂起（定时器）
  3. 用户希望挂起一个程序的执行

PCB 进程控制块：进程存在的唯一标识。一般选择链表来组织。

CPU的上下文切换

CPU 上下文切换就是先把前一个任务的 CPU 上下文（CPU 寄存器和程序计数器）保存起来，然后加载新任务的上下文到这些寄存器和程序计数器，最后再跳转到程序计数器所指的新位置，运行新任务。

系统内核会存储保持下来的上下文信息，当此任务再次被分配给 CPU 运行时，CPU 会重新加载这些上下文，这样就能保证任务原来的状态不受影响，让任务看起来还是连续运行。

可分为：

  • 进程上下文切换
  • 线程上下文切换
  • 中断上下文切换

进程的上下文切换

一个进程切换到另一个进程运行，称为进程的上下文切换。发生在内核态。

进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的资源。

常见场景：

  • 为了保证所有进程可以得到公平调度，CPU 时间被划分为一段段的时间片，这些时间片再被轮流分配给各个进程。这样，当某个进程的时间片耗尽了，进程就从运行状态变为就绪状态，系统从就绪队列选择另外一个进程运行；
  • 进程在系统资源不足（比如内存不足）时，要等到资源满足后才可以运行，这个时候进程也会被挂起，并由系统调度其他进程运行；
  • 当进程通过睡眠函数 sleep 这样的方法将自己主动挂起时，自然也会重新调度；
  • 当有优先级更高的进程运行时，为了保证高优先级进程的运行，当前进程会被挂起，由高优先级进程来运行；
  • 发生硬件中断时，CPU 上的进程会被中断挂起，转而执行内核中的中断服务程序；

线程 Thread

进程中的一条执行流程

共享：同一个进程内多个线程之间可以共享代码段、数据段、打开的文件等资源。

独立：但每个线程各自都有一套独立的寄存器和栈，这样可以确保线程的控制流是相对独立的。

优点：

  • 一个进程中可以同时存在多个线程；
  • 各个线程之间可以并发执行；
  • 各个线程之间可以共享地址空间和文件等资源；

缺点：

  • 对C++来说，进程中的一个线程崩溃会导致其所属进程的所有进程都崩溃

线程的上下文切换

  • 当两个线程不是属于同一个进程，则切换的过程就跟进程上下文切换一样；
  • 当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据；

线程的实现方式

  • 用户级线程模型（User Thread）：在用户空间实现的线程，不是由内核管理的线程，是由用户态的线程库来完成线程的管理；
  • 内核级线程模型（Kernel Thread）：在内核中实现的线程，是由内核管理的线程；
  • 轻量级进程模型（LightWeight Process）：在内核中来支持用户线程；

用户线程与内核线程的对应关系：多对一，一对一，一对多

用户级线程模型

（多对一）

1.由应用程序所支持的线程实现, 内核意识不到用户级线程的实现。

用户线程是基于用户态的线程管理库来实现的，那么线程控制块（Thread Control Block, TCB） 也是在库里面来实现的，对于操作系统而言是看不到这个 TCB 的，它只能看到整个进程的 PCB。

所以，用户线程的整个线程管理和调度，操作系统是不直接参与的，而是由用户级线程库函数来完成线程的管理，包括线程的创建、终止、同步和调度等。

优点：

  • 每个进程都需要有它私有的线程控制块（TCB）列表，用来跟踪记录它各个线程状态信息（PC、栈指针、寄存器），TCB 由用户级线程库函数来维护，可用于不支持线程技术的操作系统；
  • 用户线程的切换也是由线程库函数来完成的，无需用户态与内核态的切换，所以速度特别快；、
  • （optional）允许每个进程定制自己的调度算法，线程管理比较灵活。这就是必须自己写管理程序，与内核线程的区别

缺点：

  • 由于操作系统不参与线程的调度，如果一个线程发起了系统调用而阻塞，那进程所包含的用户线程都不能执行了。
  • 当一个线程开始运行后，除非它主动地交出 CPU 的使用权，否则它所在的进程当中的其他线程无法运行，因为用户态的线程没法打断当前运行中的线程，它没有这个特权，只有操作系统才有，但是用户线程不是由操作系统管理的。
  • 由于时间片分配给进程，故与其他进程比，在多线程执行时，每个线程得到的时间片较少，执行会比较慢；

内核级线程模型

（一对一）

内核线程的优点：

  • 多处理器系统中，内核能够并行执行同一进程内的多个线程
  • 在一个进程当中，如果某个内核线程发起系统调用而被阻塞，并不会影响其他内核线程的运行/能够切换同一进程内的其他线程继续执行（用户级线程的一个缺点）；
  • 分配给线程，多线程的进程获得更多的 CPU 运行时间；

内核线程的缺点：

  • 在支持内核线程的操作系统中，由内核来维护进程和线程的上下文信息，如 PCB 和 TCB；
  • 线程的创建、终止和切换都是通过系统调用的方式来进行，因此对于系统来说，系统开销比较大；

轻量级线程模型 LWP

内核支持的用户线程，一个进程可有一个或多个 LWP，每个 LWP 是跟内核线程一对一映射的，也就是 LWP 都是由一个内核线程支持，而且 LWP 是由内核管理并像普通进程一样被调度。

在大多数系统中，LWP与普通进程的区别也在于它只有一个最小的执行上下文和调度程序所需的统计信息。一般来说，一个进程代表程序的一个实例，而 LWP 代表程序的执行线程，因为一个执行线程不像进程那样需要那么多状态信息，所以 LWP 也不带有这样的信息。

基于内核线程。但也可以使用用户线程。

LWP与用户线程的对应关系

  • 1：1
  • N：1
  • M：N
  • 混搭

进程与线程的比较

  • 进程是资源（包括内存、打开的文件等）分配/拥有的基本单位，线程是 CPU 调度的基本单位；
  • 进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈；
  • 线程同样具有就绪、阻塞、执行三种基本状态，同样具有状态之间的转换关系；
  • 线程能减少并发执行的时间和空间开销；
  • 当进程只有一个线程时，可以认为进程就等于线程；
  • 当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源，这些资源在上下文切换时是不需要修改的；

线程能减少开销体现在：

  • 线程的创建时间比进程快，因为进程在创建的过程中，还需要资源管理信息，比如内存管理信息、文件管理信息，而线程在创建的过程中，不会涉及这些资源管理信息，而是共享它们；
  • 线程的终止时间比进程快，因为线程释放的资源相比进程少很多；
  • 同一个进程内的线程切换比进程切换快，因为线程具有相同的地址空间（虚拟内存共享），这意味着同一个进程的线程都具有同一个页表，那么在切换的时候不需要切换页表。而对于进程之间的切换，切换的时候要把页表给切换掉，而页表的切换过程开销是比较大的；
  • 由于同一进程的各线程间共享内存和文件资源，那么在线程之间数据传递的时候，就不需要经过内核了，这就使得线程之间的数据交互效率更高了；

进程调度算法

调度时机

  • 从就绪态 -> 运行态：当进程被创建时，会进入到就绪队列，操作系统会从就绪队列选择一个进程运行；
  • 从运行态 -> 阻塞态：当进程发生 I/O 事件而阻塞时，操作系统必须选择另外一个进程运行；
  • 从运行态 -> 结束态：当进程退出结束后，操作系统得从就绪队列选择另外一个进程运行；

调度原则

  • CPU 利用率：调度程序应确保 CPU 是始终匆忙的状态，这可提高 CPU 的利用率；
  • 系统吞吐量：吞吐量表示的是单位时间内 CPU 完成进程的数量，长作业的进程会占用较长的 CPU 资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量；
  • 周转时间：周转时间是进程运行+阻塞时间+等待时间的总和，一个进程的周转时间越小越好；
  • 等待时间：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意；
  • 响应时间：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。

调度算法

如果硬件时钟提供某个频率的周期性中断，那么可以根据如何处理时钟中断 ，把调度算法分为两类：

  • 非抢占式调度算法挑选一个进程，然后让该进程运行直到被阻塞，或者直到该进程退出，才会调用另外一个进程，也就是说不会理时钟中断这个事情。
  • 抢占式调度算法挑选一个进程，然后让该进程只运行某段时间，如果在该时段结束时，该进程仍然在运行时，则会把它挂起，接着调度程序从就绪队列挑选另外一个进程。这种抢占式调度处理，需要在时间间隔的末端发生时钟中断，以便把 CPU 控制返回给调度程序进行调度，也就是常说的时间片机制。
单核CPU

  • 先来先服务（First Come First Serve, FCFS)：适用于CPU繁忙型作业的系统，但不适用于I/O繁忙型作业的系统。

  • 最短作业优先（Shortest Job First, SJF)：有助于提高吞吐量，但会使长作业的周转时间变长或不会运行。

  • 高响应比优先（Highest Response Ratio Next)：理想型算法，现实中实现不了，因为无法预知要求服务时间。权衡短与长作业。优先权=（等待时间+要求服务时间）/要求服务时间。

  • 时间片轮转（Round Robin，PR）：众生平等，但有时间片

  • 最高优先级（Highest Priority First）：

    • 静态优先级和动态优先级
    • 非抢占式和抢占式

  • 多级反馈（Multilevel Feedback Queue)：时间片轮转和最高优先级的综和发展

    • 「多级」表示有多个队列（每个队列中有多个进程），每个队列优先级从高到低，同时优先级越高时间片越短。
    • 「反馈」表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列；
    • 设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短；
    • 新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果其在第一级队列规定的时间片内没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成；
    • 当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行；
多核CPU

Linux中每个CPU都有自己的运行队列（排序即为优先级）：

  1. dl_rq
  2. rt_rq
  3. cfs_rq：红黑树实现

各种调度器和调度策略

CFS（完全公平调度）：优先选择vruntime少的任务

vruntime = 实际运行时间delta_exec * NICE_0_LOAD/权重