Lanchester Blog

Leave a leaf

0%

OS 线程

Posted on Edited on In

讲述了一些与进程管理相关的高级概念，这些概念在很多现代操作系统中都可以找到。首先这里所说的进程概念要比前面给出的更复杂、更精细。实际上，它包含了两个独立的概念：一个与资源所有权有关，一个与执行相关。这一区别使得许多操作系统中出现和发展了称为线程的结构。

进程和线程

在迄今为止的讨论中，进程具有如下两个特点：

  • 资源所有权：进程包括存放进程映像的虚拟地址空间；进程映像是程序、数据、栈和进程控制块中定义的属性集。进程总具有对资源的控制权或所有权，这些资源包括内存、IO 通道、IO 设备和文件等。操作系统提供预防进程间发生不必要资源冲突的保护功能。
  • 调度/执行：进程执行时采用一个或多程序的执行路径（轨迹），不同进程的执行过程会交替进行。因此，进程具有执行态（运行、就绪等）和分配给其的优先级，是可被操作系统调度和分派的实体。

这两个特点是独立的，因此操作系统应能分别处理它们。很多操作系统，特别是近期开发的操作系统已在这样做。为区分这两个特点，我们通常将分派的单位称为线程或轻量级进程（ Light Weight Process，LWP ），而将拥有资源所有权的单位称为进程（ process ）或任务（ task ）。

多线程

多线程是指操作系统在单个进程内支持多个并发执行路径的能力。MS-DOS 是支持单用户进程和单线程的操作系统例子。其他操作系统如各种版本的 UNIX，也支持多用户进程，但每个进程仅支持一个线程。

在多线程环境中，进程定义为资源分配单元和一个保护单元。与进程相关联的有：

  • 容纳进程映像的虚拟地址空间
  • 对处理器、其他进程（用于进程间通信）、文件和 IO 资源（设备和通道）的受保护访问

一个进程中可能有一个或多个线程，每个线程都有：

  • 一个线程执行状态（运行、就绪等）
  • 未运行时保存的线程上下文：线程可视为在进程内运行的一个独立程序计数器
  • 一个执行栈
  • 每个线程用于局部变量的一些静态存储空间
  • 与进程内其他线程共享的内存和资源的访问

下图从进程的管理角度说明了进程和线程的区别。

在单线程进程模型中（无明确的线程概念），进程的表示包括其进程控制块和用户地址空间，以及在进程执行中管理调用返回行为的用户栈和内核栈。进程正运行时，处理器寄存器由该进程控制；进程未运行时，将保存这些处理器寄存器中的内容。

在多线程环境中，进程仍然只有一个与之关联的进程控制块和用户地址空间，但每个线程现在会有许多单独的栈和一个单独的控制块，控制块中包含寄存器值、优先级和其他与线程相关的状态信息。因此，进程中的所有线程共享该进程的状态和资源，所有线程都驻留在同一块地址空间中，并可访问相同的数据。当某个线程改变了内存中的一个数据项时，其他线程在访问这一数据项时会看到这一变化。若一个线程以读权限打开一个文件，那么同一进程中的其他线程也能从这个文件中读取数据。

比较性能后会发现线程的如下优点：

  1. 在已有进程中创建一个新线程的时间，远少于创建一个全新进程的时间。Mach 开发人员的研究表明，线程创建要比在 UNIX 中创建进程快 10 倍。
  2. 终止线程要比终止进程所花的时间少。
  3. 同一进程内线程间切换的时间，要少于进程间切换的时间。
  4. 线程提高了不同执行程序间通信的效率。在多数操作系统中，独立进程间的通信需要内核介入，以提供保护和通信所需的机制。但是，由于同一进程中的多个线程共享内存和文件，因此它们无须调用内核就可互相通信。

因此，若将一个应用程序或函数实现为一组相关联的执行单元，则用一组线程要比用一组分离的进程更有效。

使用线程的一个应用程序示例是文件服务器。每个新文件请求到达时，文件管理程序会创建个新线程。服务器需要处理很多请求，因此会在短期内创建和销毁许多线程。服务器运行在多处理器机器上时，同一进程中的多个线程可以同时在不同处理器上执行。此外，由于文件服务中的进程或线程须共享文件数据，并据此协调它们的行为，因此使用线程和共享内存要比使用进程和消息传递的速度快。

在单处理器上使用线程结构，可简化逻辑上从事几种不同工作的程序的结构。下面给出了在单用户多处理系统中使用线程的 4 个例子：

  • 前台和后台工作：例如，在电子表格程序中，一个线程可以显示菜单并读取用户输入，而另一个线程执行用户命令并更新电子表格。这种方案允许程序在前一条命令完成前提示输入下一条命令，因而通常会使用户感到应用程序的响应速度有所提高。
  • 异步处理：程序中的异步元素可用线程来实现。例如，为避免掉电带来的损失，往往把文字处理程序设计成每隔 1 分钟就把随机存储内存（RAM）缓冲区中的数据写入磁盘。可以创建个任务是周期性地进行备份的线程，该线程由操作系统直接调度。这样，主程序中就不需要特别的代码来提供时间检査或协调输入和输出。
  • 执行速度：多线程进程在计算一批数据时，可通过设备读取下一批数据。在多处理器系统中，同一进程中的多个线程可同时执行。这样，既使一个线程在读取数据时被IO操作阻塞，另一个线程仍然可以继续运行。
  • 模块化程序结构：涉及多种活动或多种输入输出源和目的的程序，更容易使用线程来设计和实现。

在支持线程的操作系统中，调度和分派是在线程基础上完成的，因此大多数与执行相关的信息可以保存在线程级的数据结构中。但是，有些活动会影响进程中的所有线程，因此操作系统必须在进程级对它们进行管理。例如，挂起操作会把一个进程的地址空间换出内存，以便为其他进程的地址空间腾出位置。因为一个进程中的所有线程共享同一个地址空间，因此它们会同时被挂起。类似地，进程终止时会使得进程中的所有线程都终止。

线程的功能

线程状态

和进程一样，线程的主要状态有运行态、就绪态和阻塞态。一般来说，挂起态对线程没有意义，因此这类状态仅适用于进程。特别地，如果一个进程被换出，由于所有线程都共享该进程的地址空间，因此所有线程都须被换出。

有 4 种与线程状态改变相关的基本操作：

  • 派生：典型情况下，在派生一个新进程时，同时也会为该进程派生一个线程。随后，进程中的线程可在同一进程中派生另一个线程，并为新线程提供指令指针和参数；新线程拥有自己的寄存器上下文和栈空间，并放在就绪队列中。
  • 阻塞：线程需要等待一个事件时会被阻塞（保存线程的用户寄存器、程序计数器和栈指针），处理器转而执行另一个就绪线程。
  • 解除阻塞：发生阻塞一个线程的事件时，会将该线程转移到就绪队列中。
  • 结束：一个线程完成后，会释放其寄存器上下文和栈。

线程同步

一个进程中的所有线程共享同一个地址空间和诸如打开的文件之类的其他资源。一个线程对资源的任何修改都会影响同一进程中其他线程的环境，因此需要同步各种线程的活动，以便它们互不干扰且不破坏数据结构。例如，两个线程都试图同时往一个双向链表中增加一个元素时，可能会丢失一个元素或破坏链表结构。线程同步带来的问题和使用的技术通常与进程同步相同，在后面会详细讲解。

线程分类

用户级和内核级线程

线程分为两大类，即用户级线程（ User-Level Thread，ULT ）和内核级线程（ Kernel-Level Thread，KLT ），后者又称内核支持的线程或轻量级进程。

用户级线程

在纯 ULT 软件中，管理线程的所有工作都由应用程序完成，内核意识不到线程的存在。下图 a 说明了纯 ULT 方法。任何应用程序都可使用线程库设计成多线程程序。线程库是管理用户级线程的一个例程包，它含有创建和销毁线程的代码、在线程间传递消息和数据的代码、调度线程执行的代码，以及保存和恢复线程上下文的代码。

默认情况下，应用程序从单个线程开始，并在该线程中开始运行。这个应用程序及其线程将分配给一个由内核管理的进程。应用程序在运行（进程处于运行态）的任何时刻，都可派生一个在相同进程中运行的新线程。线程派生是通过调用线程库中的派生例程实现的。通过过程调用，控制权传递给派生例程。线程库为新线程创建一个数据结构，然后使用某种调度算法，把控制权传递给该进程中处于就绪态的一个线程。当控制权传递给线程库时，需要保存当前线程的上下文，然后在控制权从线程库中传递给一个线程时，恢复那个线程的上下文。上下文实际上包括用户寄存器的内容、程序计数器和栈指针。

上段描述的所有活动发生在用户空间中和一个进程内，内核并不知道这些活动。内核继续以进程为单位进行调度，并为进程指定一个执行状态（就绪态、运行态、阻塞态等）。下面的例子将阐述线程调度和进程调度的关系。假设进程 B 在其线程 2 中执行，进程和作为进程一部分的两个用户级线程的状态如下图 a 所示。此时可能会发生如下情况之一：

  1. 在线程 2 中执行的应用程序代码进行一个阻塞进程 B 的系统调用。例如，执行一次 IO 调用这会把控制权转交给内核，随后内核启动 IO 操作，把进程 B 置于阻塞态，并切换到另一个进程。在此期间，根据线程库维护的数据结构，进程 B 的线程 2 仍处于运行状态。注意，从在处理器上执行的角度来看，线程 2 实际上并不处于运行态，只是在线程库看来它处于运行态。相应的状态图如下图 b 所示。
  2. 时钟中断把控制权传递给内核，内核确定当前正运行的进程 B 已用完其时间片。内核把进程 B 置于就绪态并切换到另一个进程。同时，根据线程库维护的数据结构，进程 B 的线程 2 仍处于运行态。相应的状态图如下图 c 所示。
  3. 线程 2 运行到需要进程 B 的线程 1 执行某些动作的一个点。此时，线程 2 进入阻塞态，而线程 1 从就绪态转换到运行态。进程自身保留在运行态。相应的状态图如下图 d 所示。

上面三种情况中，每种情况都表明从上图 a 开始的一个替代事件，因此上图 b ~ d 所示的三种状态都是上图 a 状态的过渡。在第 1 种和第 2 种情况中（图 b c），当内核把控制权切换回进程 B 时，线程 2 会恢复执行。还要注意进程在执行线程库中的代码时可被中断，要么是其时间片已用完，要么是被一个更高优先级的进程抢占。因此在中断时，进程有可能处于线程切换的中间时刻，即正在从一个线程切换到另一个线程。当该进程被恢复时，线程库得以继续运行，完成线程切换，并把控制权转移给进程中的另一个线程。

使用 ULT 而非 KLT 的优点如下：

  1. 所有线程管理数据结构都在一个进程的用户地址空间中，线程切换不需要内核模式特权，因此进程不需要为了管理线程而切换到内核模式，进而节省了两次状态转换（从用户模式到内核模式，以及从内核模式返回用户模式）的开销。
  2. 调度因应用程序的不同而不同。一个应用程序可能更适合简单的轮转调度算法，而另一个应用程序可能更适合基于优先级的调度算法。为了不要乱底层的操作系统调度程序，可以做到为应用程序量身定做调度算法。
  3. ULT 可在任何操作系统中运行，不需要对底层内核进行修改以支持 ULT。线程库是供所有应用程序共享的一组应用级函数。

与 KLT 相比，ULT 也有两个明显的缺点：

  1. 在典型的操作系统中，许多系统调用都会引起阻塞。因此，在 ULT 执行一个系统调用时，不仅会阻塞这个线程，也会阻塞进程中的所有线程。
  2. 在纯 ULT 策略中，多线程应用程序不能利用多处理技术。内核一次只把一个进程分配给一个处理器，因此一个进程中只有一个线程可以执行，这相当于在一个进程内实现了应用级多道程序设计。虽然多道程序设计可明显提高应用程序的速度，但同时执行部分代码更会使某些应用程序受益。

现在已有解决这两个问题的方法，例如把应用程序写成一个多进程程序而非多线程程序。但是，这种方法消除了线程的主要优点：每次切换都变成进程间的切换而非线程间的切换，导致开销过大。另一种解决线程阻塞问题的方法是，使用一种称为“套管”（ jacketing ）的技术。“套管”的目标是把一个产生阻塞的系统调用转化为一个非阻塞的系统调用。例如，替代直接调用一个系统 IO 例程，让线程调用一个应用级的 IO 套管例程，这个套管例程中的代码用于检査并确定 IO 设备是否忙。如果忙，该线程进入阻塞态并把控制权传送给另一个线程。这个线程重新获得控制权后，套管例程会再次检査 IO 设备。

内核级线程

在纯 KLT 软件中，管理线程的所有工作均由内核完成。应用级没有线程管理代码，只有一个到内核线程设施的应用编程接口（API，Windows 是这种方法的一个例子）。

上图 b 显示了纯 KLT 方法。内核为进程及进程内的每个线程维护上下文信息。调度由内核基于线程完成。这种方法克服了 ULT 方法的两个缺点。首先，内核可以同时把同一个进程中的多个线程调度到多个处理器中；其次，进程中的一个线程被阻塞时，内核可以调度同一个进程中的另一个线程。KLT 方法的另一个优点是，内核例程自身也可是多线程的。

与 ULT 方法相比，KLT 方法的主要缺点是：在把控制权从一个线程传送到同一个进程内的另一个线程时，需要切换到内核模式。为说明两种方法的区别，下表给出了在单处理器 VAX 机上运行类 UNIX 操作系统的测量结果。表中进行了两个基准测试，即 Null Fork 和 Signa-Wait，前者测量创建、调度、执行和完成一个调用空过程的进程线程的时间（即派生一个进程线程的开销），后者测量进程线程给正在等待的进程线程发信号，然后在某个条件上等待所需要的时间（即两个进程线程的同步时间）。可以看出，ULT 和 KLT 之间、KLT 和进程之间都有一个数量级以上的性能差距。

从表中可以看出，虽然使用 KLT 多线程技术与使用单线程的进程相比，速度明显提升，但使用 ULT 与使用 KLT 相比，速度再次得以提升。速度的再次提升是否能实现，取决于应用程序的性质。应用程序中的大多数线程切换都需要内核模式访问时，基于 ULT 的方案不见得会比基于 KLT 的方案好。

混合方法

有些操作系统提供混合 ULT 和 KLT 的方法（如下图 c）。

在混合系统中，线程创建完全在用户空间中完成，线程的调度和同步也在应用程序中进行。一个应用程序中的多个用户级线程会被映射到一些（小于等于用户级线程数）内核级线程上。为使整体性能最佳，程序员可为特定应用程序和处理器调节 KLT 的数量。

在混合方法中，同一个应用程序中的多个线程可在多个处理器上并行地运行，某个会引起阻塞的系统调用不会阻塞整个进程。设计正确时，这种方法可结合纯 ULT 方法和纯 KLT 方法的优点，并克服它们的缺点。

Solaris 操作系统是使用混合方法的很好例子。最新版的 Solaris 将 ULT/KLT 关系限制为 1:1。

其他方案

如前所述，资源分配和分派单元的概念一直体现在单个进程的概念中，即线程和进程的关系是 1:1。近年来的研究热点是，在一个进程中提供多个线程。这是一种多对一的关系。此外，还有两种组合，即多对多的关系和一对多的关系。下图介绍了线程与进程的关系。

多对多的关系

实验性操作系统 TRIX 研究了线程和进程间的多对多关系。TRIX 操作系统中有域和线程的概念。域是一个静态实体，它包含一个地址空间和一些发送接收消息的端口；线程是一个执行路径，它含有执行栈、处理器状态和调度信息。

类似于前述多线程方法，多个线程可在一个域中执行，且带来的效益也类似于前者。但是，单个用户的活动或应用程序也可能在多个域中执行，此时线程要从一个域移动到另一个域。

在多个域中使用一个线程目的，最初是为了给程序员提供结构化的工具。例如，我们考虑一个使用 IO 子程序的程序。在允许用户派生进程的多道程序设计环境中，主程序可能产生一个新进程去处理 IO，然后继续执行。但在主程序后面的步骤取决于 IO 操作的结果时，主程序就须等待其他 IO 程序结束。实现这一应用有以下几种方法：

  1. 整个程序作为单个进程来实现。这是一种简单且合理的解决方案，但内存管理有些问题。整个进程要有效地执行，可能需要相当大的内存空间，而 IO 子程序缓冲 IO 并处理少量程序代码所需的地址空间相对较小。由于 IO 程序在大程序的地址空间中执行，因此在 IO 操作期间整个进程必须驻留在内存中，或经过 IO 操作交换出去。把主程序和 IO 子程序作为同一个地址空间中的两个线程来实现时，这种存储管理的影响仍然存在。
  2. 主程序和 IO 子程序可作为两个独立的进程实现。这会带来创建辅助程序的开销。IO 活动频繁时，要么使每个辅助进程处于活跃状态（消耗管理资源），要么频繁地创建和销毁该子程序（低效）。
  3. 把主程序和 IO 子程序当作由单个线程实现的单个活动，但为主程序和 IO 子程序分别创建地址空间（域）。因此，在执行过程中，这个线程可在两个地址空间之间移动，操作系统可以分别管理这两个地址空间，而不会带来任何创建进程的开销。此外，IO 子程序使用的地址空间可共享给其他相似的 IO 程序。

TRIX 开发人员的经验表明，第三种方法优点甚多，对某些应用程序来说可能是最有效的解决方案。

一对多的关系

在分布式操作系统（用于控制分布式计算机系统）领域，人们对把线程当作一个可在地址空间中移动的实体兴趣浓厚。这种研究的一个著名例子是内核称为 Ra 的 Clouds 操作系统，另一个例子是 Emerald 系统。

从用户的角度来看，Clouds 中的线程是一个活动单元。进程是一个带有相关进程控制块的虚地址空间。线程创建后，会通过调用该进程中一个程序的入口点，开始在进程中执行。线程可从一个地址空间转移到另一个地址空间，甚至横跨机器边界（即从一台计算机移到另一台计算机）。线程移动时，它须携带自身的某些信息，如控制终端、全局参数和调度指导信息（如优先级）。

Clouds 方法提供了一种隔离用户、程序员与详细分布式环境的有效方法。用户的活动可表示成线程，线程在计算机间的移动由操作系统根据各种与系统相关的因素控制，如对远程资源进行访问的需要、负载平衡等。

多核和多线程

多核系统的软件性能

多核组织结构带来的性能提升，取决于应用程序有效利用并行资源的能力。我们首先介绍运行在多核系统上的单个应用程序。 Amdahl 定律声称

该定律假设程序执行时间的(1-f)分之一所涉及的代码本质上是串行的，其余 f 分之一所涉及的代码是无限并行的，并且没有调度开销。

该定律看上去使得多核组织结构的前景很迷人。然而，如下图 a 所示，即使是一小部分串行代码也会显著影响性能。假设只有 10% 的代码本质上是串行的（ 即 f = 0.9 ），那么在一个 8 处理器的多核系统上运行该程序也仅有 4.7 倍的性能提升。另外，多处理器任务调度和通信以及高速缓存一致性维护都会给软件带来额外的开销。这就使得性能曲线达到峰值后便开始下降。下图 b 是一个有代表性的例子。

尽管如此，软件工程师们一直在努力解决这个问题，而且发现大量应用程序可以有效利用多核系统。研究了一系列数据库应用程序，这些程序采取了很多措施来降低硬件组织结构、操作系统、中间件和数据库应用软件本身的串行部分比例。从下图中可以看出，数据库管理系统和数据库应用程序能有效地使用多核系统。还有许多不同类型的服务器程序能够有效使用并行化的多核组织结构，因为服务器程序通常会并行地处理许多相对独立的事务。

除通用服务器软件外，其他类型的应用程序也可从多核系统中直接获益，因为它们的吞吐量能随着处理器核心的数量伸缩。给出如下示例：

  • 原生多线程应用程序：多线程应用程序的特征是具有少数几个高度线程化的进程。线程化应用程序的例子包括 Lotus Domino 和 Siebel CRM（客户关系管理）。
  • 多进程应用程序：多进程应用程序的特征是具有多个单线程的进程。多进程应用程序的例子包括 Oracle 数据库、SAP 和 PeopleSoft。
  • Java应用程序：Java 从根本上支持线程的概念。不仅 Java 语言本身能够很方便地支持多线程应用程序开发，Java 虚拟机也是一个多线程进程，它为 Java 应用程序提供调度机制和内存管理。能够直接从多核系统资源中获益的 Jav a应用程序包括 Sun 公司的 Java 应用服务器、BEA 公司的 WebLogic、IBM 公司的 WebSphere 和开源的 Tomcat 应用服务器。基于 J2EE 开发的所有应用程序也可直接从多核技术中获益。
  • 多实例应用程序：即使个别应用程序未利用大量的线程来达到伸缩性，仍然可以通过并行运行多个应用程序的实例来从多核组织结构中获益。多个应用程序实例需要一定程度上的隔离性时，可使用虚拟化技术（虚拟出支撑操作系统的硬件）为每个实例提供独立、安全的环境。