进程&线程

进程

操作系统为正在运行的程序提供的抽象，就是进程。简单来说，一个正在运行的程序就是一个进程。进程是资源分配的基本单位。

数据结构

在操作系统中，是用进程控制块（process control block，PCB）数据结构来描述进程的。

PCB 是进程存在的唯一标识，这意味着一个进程的存在，必然会有一个 PCB，如果进程消失了，那么 PCB 也会随之消失。所谓的创建进程和撤销进程，都是指对 PCB 的操作。

PCB 包含以下信息：

进程描述信息：

  • 进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符。
  • 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务；

进程控制和管理信息：

  • 进程当前状态，如 new、ready、running、waiting 或 blocked 等；
  • 进程优先级：进程抢占 CPU 时的优先级；

资源分配清单：

  • 有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的 I/O 设备信息。

CPU 相关信息：

  • CPU 中各个寄存器的值，当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中，以便进程重新执行时，能从断点处继续执行。

每个 PCB 是如何组织的呢？

通常是通过链表的方式进行组织，把具有相同状态的进程链在一起，组成各种队列。比如：

  • 将所有处于就绪状态的进程链在一起，称为就绪队列；
  • 把所有因等待某事件而处于等待状态的进程链在一起就组成各种阻塞队列；
  • 另外，对于运行队列在单核 CPU 系统中则只有一个运行指针了，因为单核 CPU 在某个时间，只能运行一个程序。

就绪队列和阻塞队列

除了链接的组织方式，还有索引方式，它的工作原理：将同一状态的进程组织在一个索引表中，索引表项指向相应的 PCB，不同状态对应不同的索引表。

一般会选择链表，因为可能面临进程创建，销毁等调度导致进程状态发生变化，所以链表能够更加灵活的插入和删除。

进程的控制

创建

操作系统允许一个进程创建另一个进程，而且允许子进程继承父进程所拥有的资源。

创建进程的过程如下：

  • 申请一个空白的 PCB，并向 PCB 中填写一些控制和管理进程的信息，比如进程的唯一标识等；
  • 为该进程分配运行时所必需的资源，比如内存资源；
  • 将 PCB 插入到就绪队列，等待被调度运行；

终止进程

进程可以有 3 种终止方式：正常结束、异常结束以及外界干预（信号 kill 掉）。

当子进程被终止时，其在父进程处继承的资源应当还给父进程。而当父进程被终止时，该父进程的子进程就变为孤儿进程，会被 1 号进程收养，并由 1 号进程对它们完成状态收集工作。

终止进程的过程如下：

  • 查找需要终止的进程的 PCB；
  • 如果处于执行状态，则立即终止该进程的执行，然后将 CPU 资源分配给其他进程；
  • 如果其还有子进程，则应将该进程的子进程交给 1 号进程接管；
  • 将该进程所拥有的全部资源都归还给操作系统；
  • 将其从 PCB 所在队列中删除；

阻塞进程

当进程需要等待某一事件完成时，它可以调用阻塞语句把自己阻塞等待。而一旦被阻塞等待，它只能由另一个进程唤醒。

阻塞进程的过程如下：

  • 找到将要被阻塞进程标识号对应的 PCB；
  • 如果该进程为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行；
  • 将该 PCB 插入到阻塞队列中去；

唤醒进程

进程由「运行」转变为「阻塞」状态是由于进程必须等待某一事件的完成，所以处于阻塞状态的进程是绝对不可能叫醒自己的。

如果某进程正在等待 I/O 事件，需由别的进程发消息给它，则只有当该进程所期待的事件出现时，才由发现者进程用唤醒语句叫醒它。

唤醒进程的过程如下：

  • 在该事件的阻塞队列中找到相应进程的 PCB；
  • 将其从阻塞队列中移出，并置其状态为就绪状态；
  • 把该 PCB 插入到就绪队列中，等待调度程序调度；

进程的状态

由上文可知，CPU 可以从一个进程切换到另外一个进程，在切换前必须要记录当前进程中运行的状态信息，以备下次切换回来的时候可以恢复执行。

所以，在一个进程的活动期间至少具备三种基本状态，即运行状态、就绪状态、阻塞状态。

img.png

上图中各个状态的意义：

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

当然，进程还有另外两个基本状态：

  • 创建状态（new）：进程正在被创建时的状态；
  • 结束状态（Exit）：进程正在从系统中消失时的状态；

于是，一个完整的进程状态的变迁如下图： img.png

  • NULL -> 创建状态：一个新进程被创建时的第一个状态；
  • 创建状态 -> 就绪状态：当进程被创建完成并初始化后，一切就绪准备运行时，变为就绪状态，这个过程是很快的；
  • 就绪态 -> 运行状态：处于就绪状态的进程被操作系统的进程调度器选中后，就分配给 CPU 正式运行该进程；
  • 运行状态 -> 结束状态：当进程已经运行完成或出错时，会被操作系统作结束状态处理；
  • 运行状态 -> 就绪状态：处于运行状态的进程在运行过程中，由于分配给它的运行时间片用完，操作系统会把该进程变为就绪态，接着从就绪态选中另外一个进程运行；
  • 运行状态 -> 阻塞状态：当进程请求某个事件且必须等待时，例如请求 I/O 事件；
  • 阻塞状态 -> 就绪状态：当进程要等待的事件完成时，它从阻塞状态变到就绪状态；

如果有大量处于阻塞状态的进程，进程可能会占用着物理内存空间（每个进程都会分配资源，如内存），显然不是我们所希望的，毕竟物理内存空间是有限的，被阻塞状态的进程占用着物理内存就一种浪费物理内存的行为。

所以，在虚拟内存管理的操作系统中，通常会把阻塞状态的进程的物理内存空间换出到硬盘，等需要再次运行的时候，再从硬盘换入到物理内存。

那么，就需要一个新的状态，来描述进程没有占用实际的物理内存空间的情况，这个状态就是挂起状态。

挂起一个进程可以释放系统资源，如 CPU、内存或 I/O，然后可以分配给其他活动进程。

它既可以是我们客户主动使得进程挂起，也可以是操作系统因为某些原因使得进程挂起。

这跟阻塞状态是不一样，阻塞状态是等待某个事件的返回。

另外，挂起状态可以分为两种：

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

这两种挂起状态加上前面的五种状态，就变成了七种状态变迁，见如下图： img.png 导致进程挂起的原因不只是因为进程所使用的内存空间不在物理内存，还包括如下情况：

  • 用户希望挂起一个程序的执行，比如在 Linux 中用 Ctrl+Z 挂起进程；
  • 负载调节的需要：有一些实时的任务非常重要，需要得到充足的内存空间，这个时候我们需要把非实时的任务进行挂起，优先使得实时任务执行。
  • 定时任务：一个进程可能会周期性的执行某个任务，那么在一次执行完毕后挂起而不是阻塞，这样可以节省内存。

阻塞和挂起状态的区别：

  • 挂起状态主要是为了节省内存资源，将进程从内存移出，虽然不占用CPU时间但需要操作系统显式地恢复。
  • 阻塞状态主要是因为进程在等待某个事件或资源，进程保留在内存中，等待条件满足时会自动恢复执行。

进程的上下文切换

任务是交给 CPU 运行的，那么在每个任务运行前，CPU 需要知道任务从哪里加载，又从哪里开始运行。

所以，操作系统需要事先帮 CPU 设置好 CPU 寄存器和程序计数器。

CPU 寄存器是 CPU 内部一个容量小，但是速度极快的内存（缓存）。程序计数器则是用来存储 CPU 正在执行的指令位置、或者即将执行的下一条指令位置。

CPU 寄存器和程序计数器是 CPU 在运行任何任务前，所必须依赖的环境，这些环境就叫做 CPU 上下文。

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

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

上面说到所谓的「任务」，主要包含进程、线程和中断。所以，可以根据任务的不同，把 CPU 上下文切换分成：进程上下文切换、线程上下文切换和中断上下文切换。

进程是由内核管理和调度的，所以进程的切换只能发生在内核态。

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

通常，会把交换的信息保存在进程的 PCB，当要运行另外一个进程的时候，我们需要从这个进程的 PCB 取出上下文，然后恢复到 CPU 中，这使得这个进程可以继续执行，如下图所示： img.png 进程的上下文开销是很关键的，我们希望它的开销越小越好，这样可以使得进程可以把更多时间花费在执行程序上，而不是耗费在上下文切换。

发生进程上下文切换有哪些常见场景？

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

线程

假设你要编写一个视频播放器软件，那么该软件功能的核心模块有三个：

  • 从视频文件当中读取数据；
  • 对读取的数据进行解压缩；
  • 把解压缩后的视频数据播放出来；

对于单进程的实现方式，我想大家都会是以下这个方式： img.png 对于单进程的这种方式，存在以下问题：

  • 播放出来的画面和声音会不连贯，因为当 CPU 能力不够强的时候，Read 的时候可能进程就等在这了，这样就会导致等半天才进行数据解压和播放；
  • 各个函数之间不是并发执行，影响资源的使用效率；

那改进成多进程的方式： img.png 对于多进程的这种方式，依然会存在问题：

  • 进程之间如何通信，共享数据？
  • 维护进程的系统开销较大，如创建进程时，分配资源、建立 PCB；终止进程时，回收资源、撤销 PCB；进程切换时，保存当前进程的状态信息；

那到底如何解决呢？需要有一种新的实体，满足以下特性：

  • 实体之间可以并发运行；
  • 实体之间共享相同的地址空间；

这个新的实体，就是线程( Thread )，线程之间可以并发运行且共享相同的地址空间。

什么是线程

线程是进程当中的一条执行流程。线程是独立调度的基本单位。

同一个进程内多个线程之间可以共享代码段、数据段、打开的文件等资源，但每个线程各自都有一套独立的寄存器和栈，这样可以确保线程的控制流是相对独立的。

当进程中的一个线程崩溃时，会导致其所属进程的所有线程崩溃（这里是针对 C/C++ 语言，Java语言中的线程奔溃不会造成进程崩溃）。

线程的上下文切换

线程与进程最大的区别在于：线程是调度的基本单位，而进程则是资源拥有的基本单位。

所以，所谓操作系统的任务调度，实际上的调度对象是线程，而进程只是给线程提供了虚拟内存、全局变量等资源。

对于线程和进程，我们可以这么理解：

  • 当进程只有一个线程时，可以认为进程就等于线程；
  • 当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源，这些资源在上下文切换时是不需要修改的；

另外，线程也有自己的私有数据，比如栈和寄存器等，这些在上下文切换时也是需要保存的。

线程上下文切换的是什么？

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

所以，线程的上下文切换相比进程，开销要小很多。

线程的实现

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

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

用户线程（协程）可以看做是一个内核线程的多个并发的任务，绑定在一个内核线程上，通过某种调度算法（程序自己实现的调度算法，而不是操作系统的调度）来持有这个线程的时间片从而来完成任务的运行。

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

用户级线程的模型是多对一的关系，即多个用户线程对应同一个内核线程，如下图所示： img.png 用户线程的优点：

  • 每个进程都需要有它私有的线程控制块（TCB）列表，用来跟踪记录它各个线程状态信息（PC、栈指针、寄存器），TCB 由用户级线程库函数来维护，可用于不支持线程技术的操作系统；
  • 用户线程的切换也是由线程库函数来完成的，无需用户态与内核态的切换，所以速度特别快；

用户线程的缺点：

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

内核线程是由操作系统管理的，内核线程对应的 TCB 自然是放在操作系统里的，这样内核线程的创建、终止和管理都是由操作系统负责。

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

进程和线程的区别

  • 进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。
  • 线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。
  • 由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。
  • 线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。

进程调度算法

这里的进程指只有主线程的进程，所以调度主线程就等于调度了整个进程。

调度时机

在进程的生命周期中，当进程从一个运行状态到另外一状态变化的时候，其实会触发一次调度。

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

因为，这些状态变化的时候，操作系统需要考虑是否要让新的进程给 CPU 运行，或者是否让当前进程从 CPU 上退出来而换另一个进程运行。

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

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

调度原则

原则一：如果运行的程序，发生了 I/O 事件的请求，那 CPU 使用率必然会很低，因为此时进程在阻塞等待硬盘的数据返回。这样的过程，势必会造成 CPU 突然的空闲。所以，为了提高 CPU 利用率，在这种发送 I/O 事件致使 CPU 空闲的情况下，调度程序需要从就绪队列中选择一个进程来运行。

原则二：有的程序执行某个任务花费的时间会比较长，如果这个程序一直占用着 CPU，会造成系统吞吐量（CPU 在单位时间内完成的进程数量）的降低。所以，要提高系统的吞吐率，调度程序要权衡长任务和短任务进程的运行完成数量。

原则三：从进程开始到结束的过程中，实际上是包含两个时间，分别是进程运行时间和进程等待时间，这两个时间总和就称为周转时间。进程的周转时间越小越好，如果进程的等待时间很长而运行时间很短，那周转时间就很长，这不是我们所期望的，调度程序应该避免这种情况发生。

原则四：处于就绪队列的进程，也不能等太久，当然希望这个等待的时间越短越好，这样可以使得进程更快的在 CPU 中执行。所以，就绪队列中进程的等待时间也是调度程序所需要考虑的原则。

原则五：对于鼠标、键盘这种交互式比较强的应用，我们当然希望它的响应时间越快越好，否则就会影响用户体验了。所以，对于交互式比较强的应用，响应时间也是调度程序需要考虑的原则。

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

调度算法

先进先出FIFO（先来先服务FCFS）：每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。

有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

适用于 CPU 繁忙型作业的系统，而不适用于 I/O 繁忙型作业的系统。

最短作业优先（Shortest Job First, SJF）调度算法同样也是顾名思义，它会优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。

长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

最短完成时间优先（STCF）：最短作业优先的抢占版，每当新进程来到，比较剩余进程剩余工作时间和新进程所有时间大小，优先调度小的一个进程。

时间片轮转（Round Robin, RR）调度算法：每个进程被分配一个时间段，称为时间片（Quantum），即允许该进程在该时间段中运行。

  • 如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配给另外一个进程；
  • 如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换；

另外，时间片的长度就是一个很关键的点：

  • 如果时间片设得太短会导致过多的进程上下文切换，降低了 CPU 效率；
  • 如果设得太长又可能引起对短作业进程的响应时间变长。

一般来说，时间片设为 20ms~50ms 通常是一个比较合理的折中值。

最高优先级（Highest Priority First，HPF）调度算法：希望调度程序能从就绪队列中选择最高优先级的进程进行运行。

进程的优先级可以分为，静态优先级和动态优先级：

  • 静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化；
  • 动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。

该算法也有两种处理优先级高的方法，非抢占式和抢占式：

  • 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
  • 抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。

调度算法提到的挂起指的是将当前正在运行的进程从CPU上移除，插入就绪队列中，而不是前文提到的进程挂起状态。

多级反馈队列（Multilevel Feedback Queue）调度算法是「时间片轮转算法」和「最高优先级算法」的综合和发展。

  • 「多级」表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
  • 「反馈」表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列；

img.png

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

如何提升优先级呢，系统有太多交互型（高优先级）任务，导致长工作（低优先级）无法得到 CPU ，就会有饥饿（starvation）问题。

  • 周期性提升所有工作（进程）优先级：经过一段时间 S （显然 S 的值很重要，太长饥饿问题无法避免，太短了则交互型任务得不到合适的 CPU 时间），将系统所有的工作全部加入最高优先级。
  • 为 MLFQ 的每层队列提供更加完善的 CPU 计时方式：调度程序应该记录一个进程在某一层中消耗的总时间，而不是在调度时重新计时。只要进程用完了自己的配额，就优先级降级。

可以发现，对于短作业可能可以在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也变更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。