Zohar's blog

操作系统 - 进程、线程与协程基本概念

ComputerProcessThreadCoroutineOperationg SystemComputer

操作系统中最核心的概念是进程,这是对正在运行程序的一个抽象,是计算机中最古老以及最重要的抽象概念之一。进程、线程、协程三者并非相互取代,也没有孰优孰劣,三者是协同的关系,只有三者联合工作才能使操作系统发挥最大的能效。

进程

{进程}(Process)是计算机中的程序关于某数据集合上的一次运行活动,是系统进行资源分配和调度的基本单位,是操作系统结构的基础。

特征

  • 动态性:从程序的角度,进程是程序在多道程序系统中的一次执行过程,拥有自己的生命周期,从被启动再到主动退出或者被杀死,因此进程具有动态性。

  • 并发性:对于单个 CPU,在任一瞬间都只能运行一个进程,但在一段时间内可以交替运行多个进程,这种交替运行使得多个程序共同执行的方式称为{并发}(concurrence)。任何进程都可以同其他进程一起并发执行,因此进程具有并发性。

  • 独立性:进程是能够独立运行和接受调度的独立单位,也是操作系统分配资源的基本单位,因此进程具有独立性。每一个进程都可以独立抽出到 CPU 中执行,因此进程是一个能独立运行的基本单位。操作系统必须默认程序都是贪婪且富有攻击性的,每个进程只能使用自己已分配的资源以防止其他程序或操作系统遭受破坏,因此进程是系统分配资源的独立单位。

  • 异步性:由于操作系统调度的时间是不确定的,进程随时可能主动退出 CPU,也可能抢占其他进程所需要的资源阻塞其他进程执行,因此进程按不可预知的速度向前推进,具有异步性。

结构

进程的结构由程序、资源和进程控制块组成。进程是一个动态性的概念,其动态性由{进程控制块}(Process Control Block)(PCB)所维护,该数据结构维护了进程运行时的各项动态信息。

同一段时间有多个进程存在,CPU 在各进程间来回切换,因此系统必需维护一张{进程表}(process table),以维护当前所有进程的信息。PCB 就是进程表中的表项。

PCB 中需要维护的信息有:

进程管理 存储管理 文件管理
寄存器、程序计数器、程序状态字、堆栈指针、进程状态、优先级、调度参数、进程 ID、父进程、进程组、信号、进程开始时间、使用的 CPU 时间、子进程 CPU 时间、下次定时器时间 正文段指针、数据段指针、堆栈段指针 根目录、工作目录、文件描述符、用户 ID、组 ID

状态

进程存在三种状态:

  1. 就绪态:进程在逻辑上能够正常运行,但接收操作系统调度在等待 CPU。

  2. 运行态:进程正在使用 CPU 运行。

  3. 阻塞态:进程逻辑上无法继续运行,必需等待满足运行条件后才能运行。如进程正在等待键盘输入或进程所需要的资源正在被其他进程使用等。

进程不存在创建、消亡这些状态,因为内核不会保存死去的进程也不会提前创建空进程给待创建的进程,进程永远都是直接创建和直接释放的。

进程状态间的转换:

进程状态切换 -- Zohar Yip

进程在就绪态和运行态来回切换是由调度程序引起的,而只有运行才能被阻塞,阻塞结束之后,进程会重新回到就绪态,如果此时调度程序刚好让进程运行,进程又会马上运行。调度程序是内核的一部分,其工作内容主要为两部分:

  1. 保证公平性:保证各个进程享有的 CPU 时间片相同。内核通过接收时钟中断周期性地得知时间,PCB 中记录着进程已使用的 CPU 时间,调度程序如果发现进程执行时间过长,调度程序会切换其他进程执行。

  2. 提高效率:执行中的进程进行系统调用如果发生阻塞,由于执行系统调用的是内核,当内核发现发生阻塞时,会切换当前阻塞的进程,调度其他就绪进程执行。

进程的创建

新进程的创建都是由一个已存在的进程执行一个用于创建进程的系统调用创建的。这个系统调用通知操作系统创建一个进程,并直接或间接地指定该进程中要运行的程序。

Unix 和类 Unix 系统中使用 fork 系统调用创建新进程,这个系统调用会创建一个与运行进程相同的副本。这两个进程互为父子关系,拥有同样的存储映像、同样的上下文和相同的打开文件,不同之处仅在于进程号和父进程号。通常子进程会执行一个 execve 系统调用,以修改其系统镜像并运行一个新的程序。之所以要分为两步创建进程,是为了在 fork 之后允许子进程处理其文件描述符,这样可以完成对标准输入、标准输出和标准出错的重定向。

Windows 中 CreateProcess 调用既处理进程的创建,又负责把正确的程序装入新的进程。

无论是任何系统,进程创建之后,父子进程拥有各自不同的地址空间。Unix 中子进程的地址空间也是父进程的副本,除了不可写的内存区可以共享之外,其他内存区域都是互不可见的。不可写的内存共享区是 fork 出来的父子进程中的程序正文部分,因为在未装入新程序时,父子进程所运行的代码是一样的。但是内存外的其他资源,有一部分确实可以在父子进程间进行共享,比如父进程已打开的文件。

进程的退出

多数进程是因为完成自身的工作正常退出,在 Linux 中,程序调用 exit 系统调用主动退出,在 Windows 中程序调用 ExitProcess 主动退出。进程也可以在执行出错时捕获自身的异常,在处理异常时选择退出,此时程序通常会进行日志记录或警告操作。正常退出和异常退出都是程序自行选择的结果,属于主动退出。

如果程序发生严重错误且程序无法捕获该错误,此时由操作系统强制终止该进程的执行,属于被动退出。典型的例子像内存越界问题,这属于对其他进程严重的攻击行为,操作系统会强制停止当前程序的执行。

被动退出的另一种情况是其他进程主动杀死目标进程,如 kill 命令,在 Windows 中为 TerminateProcess,典型的使用像 windows 的任务管理器。杀手进程必需获得特殊权限才能执行该动作。

进程的层次结构

由于进程都是由父进程创建的,因此如果子进程再创建子进程,进程之间会形成一种分层的结构。

Unix 中进程及其后裔共同组成一个进程组。当用户从键盘发出一个信号时,该信号会被与当前键盘相关的进程组中的所有成员接收,每个进程都可以捕获和忽略该信号。Unix 系统在启动时,会创建一个 init 进程作为所有进程的祖先,因此 Unix 中的进程结构仿佛是一棵多叉树。

而 Windows 中没有进程层次的概念,所有进程地位相同。父进程在创建子进程的时候可以获得一个对于该子进程有效的句柄,即一块特殊的令牌,使用该令牌可以控制子进程。但父进程可以选择将句柄交给其他进程,因此 Windows 中没有固定的进程层级之分。

线程

{线程}(Thread)是系统运算调度的最小单位。它被包含在进程之中,是进程中的实际运作单位,是系统中独立运行的基本单位。

作为资源分配的基本单位使得线程的切换较为繁重,同时我们希望多个程序能同时使用相同的资源以提高效率,且保证这些程序可以相互友好合作,不会发生攻击行为。线程的存在就是为了解决这样的需求。

线程是实际使用 CPU 的对象,虽然 CPU 实际上运行的是线程的指令,但线程不能看作是独立的运行程序,因为线程没有独有的数据,它的数据是进程内共享的,它仅仅只是一个接受调度、独立运行的基本单位而已。之所以能够保证各线程不会相互攻击,是因为进程才是独立的程序,程序的开发者不可能会让自己程序内的代码相互攻击,使用线程的目的就是为了提高程序的工作效率而不是加速程序的死亡。

特征

  • 轻量级:由于线程间共享进程的资源,因此在管理和调度线程的时候,不需要像进程切换一样保留中断、定时器和上下文等等数据,只需要为线程保留代码执行时的必要信息即可。轻量级带来的效果是线程的切换速度较进程快一两个数量级。

  • 调度的基本单位:在多线程 OS 中,线程的运行独占 CPU,因此线程是运行的基本单位,也是接受调度的基本单位。

  • 并发性:同一进程中的线程可以并发执行,对于多核 CPU 甚至可以并行执行。

  • 共享进程资源:同一进程内的线程共享进程的所有资源和地址空间。因为同进程内线程可以访问同一个文件,因此线程之间的通信无需通过内核,大大减少通信的消耗。

结构

线程的实体包括程序、数据和线程控制块。线程是动态概念,它的动态特性由{线程控制块}(Thread Control Block)(TCB)描述。TCB包括以下信息:

  • 线程状态。

  • 用于指示被执行指令序列的程序计数器、保留局部变量、少数状态参数和返回地址等的一组寄存器和堆栈。

  • 存放每个线程的局部变量主存区。

  • 访问同一个进程中的主存和其它资源。

CPU 在各线程间来回切换,因此要实现多线程必需维护一张{线程表}(thread table),以维护当前所有进程的信息。TCB 就是进程表中的表项。

状态

任何多线程模型都必须包含这三种状态:运行、阻塞、就绪,这三种状态可运行单位接受调度必须会拥有的三种状态,与进程的状态一致。多线程的实现不一定要操作系统的支持,不同系统所实现的方式也是不同的,因此不同系统不同程序线程的状态在运行、阻塞和就绪的基础上可能增加其他状态:如 Linux 会对死亡的线程予以回收,在创建的时候直接更换 TCB 内容即可投入使用,因此线程增加了死亡的状态。

多线程与内核

由于多线程的实现并不一定要内核的支持,程序可以自行实现多线程的功能,因此支持多线程的应用可以在不支持多线程的操作系统中运行。即使操作系统支持多线程,应用也可以选择不使用操作系统提供的线程包改用自行开发的线程包,甚至是两者混用都是可行的。内核支持的线程称为内核级线程,用户实现的线程称为用户级线程。

多线程与内核 -- Internet

用户级线程

由于是程序自行实现的线程,内核对于线程的存在一无所知,因此即使系统不支持线程,用户级线程也可以工作。

程序必须在用户空间内实现线程表来跟踪进程中的线程和自行实现一套线程的调度方法。由于是用户级线程,对于线程的启动、切换、消灭全部都不需要陷入内核,因此用户级线程的切换速度极快。同时,用户级线程可以实现一套独有的适用于自身的线程调度算法,使程序不必担心线程在不该切换的地方切换,在不该执行的地方执行。但由于没有内核的支持,用户级线程存在较多限制:

  1. 线程无法并行执行。在多核 CPU 中,由于是用户级线程,内核以一整个进程进行调度,同一个进程只能走一个 CPU,所有线程只能在同一 CPU 中并发执行而不能在多个 CPU 中并行执行。

  2. 进程被切换之后,所有线程都无法执行。线程的调度工作由进程决定,进程只有在运行态才能让自己的线程运行。

  3. 内核并不知道线程的存在,任何一个线程使用自陷后如果发生阻塞,内核都会阻塞整个进程的执行,所有线程都无法执行,这种情况下多线程就失去了意义。如果线程是因为过程调用而阻塞,程序可以自行切换线程执行,因为这个阻塞是程序设置的,程序自行可控。但程序运行的过程中系统调用无可避免且非常多,因为某个线程进行系统调用产生阻塞而阻塞所有线程,是用户级线程面临的最大问题。

  4. 与第三点类似的问题是页面故障问题。进程发生页面故障时,内核需要到磁盘中取回丢失的指令,此时线程阻塞。内核无法得知是哪个线程引发页面故障,只能阻塞整个进程。

  5. 在用户线程中,一个线程会持续占用 CPU 导致其他线程长时间无法运行。因为进程内部没有时钟中断,所以对线程无法使用轮转调度,同时由于进程中永远只能运行着一条线程,进程中无法设置守护线程管理其他线程。

解决第三点系统调用发生阻塞引发全体阻塞的问题,有两种方案:

  1. 将所有系统调用改为非阻塞调用。像读取网卡缓冲区中的数据流,如果为空则马上返回零而不必等待缓冲区数据填满或达到要求。这种方式需要修改内核,用户级线程的目标之一是在不动内核的条件下实现多线程,所以修改内核可能性太小。

  2. 进程在系统调用前判断该调用是否会阻塞,会则让出 CPU,不会则进行该系统调用。内核提供了一种称为{包装器}(Wrapper)的工具可以在执行系统调用前进行检查并返回结果。select 系统调用就是包装器的一种,可以预先判断将要执行的系统调用是否会阻塞并通知用户线程,线程得知会发生阻塞时就主动让出 CPU 给其他线程。

解决第五点线程调度的问题,有两种方案:

  1. 让所有线程按周期地向内核请求一次时钟信号,以此作为线程运行时间的依据,当线程判断自己运行时间与其他线程运行时间不对等,则主动让出 CPU 运行其他线程。但不可能总是高频率地请求时钟信号,即使可能开销也非常大。

  2. 在开发过程中,各线程之间相互协商约定,各个线程在运行到自身承诺的某条件下时,主动让出 CPU 给其他线程或者是主动唤醒其他特定地线程。这种协作的方式需要开发者进行保证,线程对于 CPU 的时间片是主动放弃的,是和程序内其他线程相互协作而产生的调度行为。如果程序是由多人开发的,可能会发生某个人开发的线程没有与其他线程合作,永久占用 CPU 时间的情况。

直指用户级线程的问题是:我们使用多线程的目的是在单条线程阻塞的时候通过运行其他线程来提高整个系统的吞吐量。如果一个系统是经常发生阻塞的,即使是使用 select 来知晓阻塞去运行其他线程,其他线程也会发生阻塞,会发生阻塞的线程一定会运行,这样导致的结果是基本上整个应用程序都处于进程阻塞的状态,这样的话用户级线程没有解决任何问题。而对于一台极少发生阻塞的服务器而言,使用多线程的意义并不大。

内核级线程

内核实现的线程,所有对线程的管理工作都交由内核实现,用户程序只需要调用内核提供的系统调用即可创建、使用和销毁线程,线程的调度工作由内核负责。内核会为所有线程在内核中维护一张线程表。TCB 中保存了每个线程的寄存器、状态和其他信息。TCB 中存有所属进程的指针,但整体上线程表和进程表之间没有关联关系,同时进程间的相互影响变小。

多个 CPU 间同一个进程的线程可以并行执行。线程被切换或阻塞时,内核可以根据其选择运行同一个进程中的其他线程,也可以运行其他进程中的线程,切换成其他进程需要进行上下文切换。能够产生阻塞的系统调用转化为线程级别,线程的阻塞并不会影响到同一个进程中的其他线程;同时,线程发生页面故障时,只会阻塞当前进程去获取指令,而不会阻塞其他线程。

内核级线程解决了用户级线程的大多数问题,但是所做出的牺牲是创建、撤销和切换线程的代价比用户级线程多出非常多数量级,内核级线程的切换速度远不如用户级线程。由于创建和撤销线程的代价较大,系统采用回收线程的方式处理死亡的线程:当线程需要撤销时,将它标志为不可运行的状态,随后在需要创建线程的时候,重新启动该线程并切换其工作内容,从而节省开销。

内核线程与用户线程混合实现

内核级线程和用户级线程组合使用的方式,可以解决两者自身的一部分缺陷,同时利用两者各自都有的优点,使程序并发执行的速度更快。不过此时用户级线程或许应该称为线程中的线程。采用这种方式,开发者可以自行决定在多个内核级线程上设置多个用户级线程,将内核级线程多路复用起来以带来最大的灵活度。

由于依靠与内核线程进行多路复用的方式,用户线程可以并行执行,也可以与其它程序的进程同时工作。当某个用户级线程发生系统调用时,阻塞的仅仅所绑定的内核线程,其他内核线程依旧可以运行,所阻塞的内核线程中的用户线程也可以绑定到其他可运行的内核线程上;同理,发生页面故障的用户线程也可以这么做。内核的调度单位依旧是内核线程,因此对于用户线程的调度机制必须由用户程序自行实现,这种方式大大减少了单进程中用户线程的弊端,交由用户程序自行处理用户线程的调度是一种更自由更灵活的方式。

构造服务器的三种模式

模型 并行性 系统调用 中断
单线程进程 × 阻塞 ×
多线程 阻塞 ×
有限状态机 非阻塞

通过对比单线程、线程构造服务器的模式,可以非常直观地看出单线程与多线程之间的差异。服务器最基本的功能在于接收请求,并响应请求,响应请求可能会用到内存中的资源或者不需要任何资源,此时直接返回即可。也可能会用到磁盘中的资源,此时需要进行系统调用并发生阻塞。由于以前多线程与单线程的区别,现如今设计和保留了三种服务器构造模型:

单线程进程模型

由单个进程监听请求,接收请求后获取并处理资源,资源准备好后再响应到客户端处。在执行单个请求的时候,无法执行其他请求,其他请求要么阻塞要么丢弃。如果在获取资源时被阻塞,这该进程将被挂起直至系统调用完毕。

多线程模型

在单个服务器进程中,由单个分派线程监听请求,接收请求后在多个睡眠中的工作线程中随机唤醒一个工作线程,将请求递交给工作线程之后,响应工作由工作线程负责,分派线程继续执行监听。单个工作线程的阻塞并不会影响其他请求的执行。

有限状态机

前两种的工作模式都是顺序执行的。如果要解决单线程进程的阻塞问题,让系统在阻塞时可以响应其他请求,则需要打破这种顺序执行的工作模式。

对于一个系统,如果该系统接收的事件是有限的,且所有输入该系统的事件在计算后的状态都会被保存起来,这个系统就是一个有限状态机

有限状态机的概念被广泛应用在计算机科学中,对于上面所构造的服务器,我们可以使用有限状态机的设计,将服务器设置为响应不同事件的状态机。所输入的事件合集为:请求到达、发生阻塞、阻塞处理完毕。事件以软件中断的方式触发系统的处理程序,系统不必对事件进行专门的监听,系统针对各事件的状态转化为:

  • 请求到达时,请求列表存储元素加一,保存当前请求信息处理信息,并对请求进行处理。

  • 系统调用发生阻塞时,更新并保存当前阻塞请求的处理信息。处理其他事件进入空闲等待。

  • 系统调用阻塞结束时,如果当前没有请求正在处理,取出该阻塞对应的请求,获取系统调用结果并继续处理该请求;如果当前正在处理请求,更新并保存当前请求处理信息。切换到系统调用所对应请求进行处理。

在单线程的模式可以通过有限状态机解决无法并发处理和阻塞的问题,但实际上有限状态机最终的效果就是模拟了多线程的堆栈处理,而这一模拟过程需要耗费开发人员非常多的精力。

调度程序激活机制

{调度程序激活}(Scheduler Activation)机制的目标是模拟内核级线程的功能,并且为线程包提供在用户级线程才能实现的性能和灵活性。调度程序激活机制所注重的点是:如果用户级线程使用某种系统调用时是安全的,那么就不应该进行专门的非阻塞调用实现或者使用包装器进行提前检查。同时,如果线程阻塞在某个系统调用上或者页面故障上,只要同一进程中有其他就绪的线程,就可以运行其他线程。调度程序激活机制由于避免不必要的自陷操作和切换发生阻塞的线程提高了效率。

使用调度程序激活机制时,内核会给每个进程安排一定数量的虚拟处理器,并且让运行时系统将线程分配到处理器上,这些虚拟处理器由内核予以支持。当内核了解到某个线程被阻塞之后,内核会通知该进程的运行时系统,并且在堆栈中以参数的形式传递发生特殊事件的线程编号和事件描述。内核在一个已知的起始地址主动启动运行时系统,从而向运行时系统发出通知,这是对 UNIX 中信号的一种粗略模拟。这个机制被称为{上行调用}(UpCall),即底层系统主动调用高层服务,这是一种违反分层次系统内在结构的概念,因为分层次系统中,只存在高层对底层的调用。

运行时系统一旦被激活,就把内核通知的线程标记为阻塞线程并取出一个就绪线程进行启动。当内核知道被阻塞的线程可以运行之后,内核再次使用上行调用激活运行时系统,通知运行时系统可以调度使用该阻塞线程。此时运行时系统将该线程的阻塞标志去掉并放入就绪队列中,根据自己的意愿选择是否运行线程。

在某个用户线程运行时如果发生了一个硬件中断,被中断的虚拟 CPU 会切换进入内核态。如果被中断的进程对该事件不感兴趣,在中断处理程序运行之后会把被中断的线程恢复到中断时的状态。如果对该事件感兴趣,那么在中断处理程序执行后运行时系统就不再启动该被中断线程,而是将它挂起同时启动该线程对应的 CPU,此时被中断的线程状态保存在堆栈中。运行时系统执行决定在该 CPU 上调度哪个线程:被中断的线程、新就绪的线程或其他选择。

协程

{协程}(coroutine)是程序中的一种组件,它允许在设置多个入口点和中断位置,将子程序泛化为非抢占式的多任务处理模式,是用户级线程的一种实现。

特征

  • 编译器级:与内核态无关,在用户态完成创建、切换和销毁。

    协程是编译器级的,也就是用户级,与内核无关。在程序编译期间就将子例程中多个入口和多个中断予以实现,使得协程在运行时可以根据不同中断执行不同的策略而不需要陷入内核,如创建、唤醒其他协程或者是退出当前协程。

  • 协同:通过协同调度而非抢占的方式来切换执行。

    编译器级意味着协程的管理依靠程序自身实现,不依靠操作系统进行管理调度。协程是主动调度的调度方式,因此是非抢占的,一个协程不会也没有办法与其他协程抢夺 CPU 时间片。在协程进入阻塞的时候,会主动让出 CPU 时间片给约定好的协程或者是交由协程调度器自行决定。正是由于这种事先约定好的协作方式,Coroutine 才被称之为“协程”。

    如果依靠协程自身让出 CPU,则需要使用包装器提前判断是否会进入阻塞,这依旧很不优雅,发生页面故障时也无法让出 CPU 。因此协程的调度通常使用专用调度器管理的方式实现,专用的调度器运行在另一条内核级线程之上用于检测其他协程的状态,当发现协程进入阻塞的时候调度器会将阻塞的协程切换为就绪的协程,但这种方式无法在不支持多线程的内核上运行。

  • N:M 模式:N 个协程可以在 M 个线程上运行。

    由于如今的操作系统基本上都支持内核级线程,当应用程序开发中使用到协程和线程时,程序运行之后就是一个混合使用内核级线程和用户级线程的运行时系统,只不过这时不叫用户级线程,而称之为协程。协程有 1:N 模式,即多个协程绑定在同一个线程上;也有 N:M 模式,多个线程与多个协程相互分离,通过管理机制将协程在多个线程之间切换,这样可以解决线程中由于某个协程发生阻塞而导致线程内所有协程阻塞的问题。而 1:N 模式本来就是 N:M 模式的一种特例。

    主动调度的方式是上文用户级线程中调度问题的第二种解决方案,通过主动让出 CPU 时间片的方式进行调度。通常的实现是线程中实现一个协程池,协程池里面设置调度器,但是这个调度器是被动调度的,它没有也不会去监控协程的执行和调度协程。当一个协程发生阻塞的时候,协程会通知调度器,根据实现协调好的调度算法调用最合适的协程执行,直到新的协程主动让出 CPU 时间片,否则该协程将一直执行下去。

结构

协程的实体包括程序、数据和协程控制体,因为协程与线程一样同享程序资源,而且协程没有太多控制信息,只需要保存程序计数器、栈指针、DX寄存器等运行状态的信息,所以协程要保存和恢复的东西很少。

通常协程的实现通常是在线程中实现一个协程池,在协程池里面设置调度器,这个调度器可以是主动调度也可以是被动调度。主动调度时,调度器需要作为独立线程监控其他协程的运行状态,当协程运行完毕或者发生阻塞时,就将该阻塞的协程切换为其他就绪协程运行。被动调度时,由协程主动通知调度器进行调度。