2022-10-21 09:06:41

将Mach 3.0升级为迁移线程模型

摘要

我们已经修改了Mach3.0，将跨域远程过程调用(RPC)视为一个单独的实体，而不是一系列消息传递操作。随着RPC的提升，我们通过更改线程模型来改进RPC期间的控制传输。与大多数操作系统一样，Mach将线程视为与单个任务静态关联的，RPC中涉及两个线程。另一种模型是迁移线程，在RPC期间，单个线程抽象在具有逻辑控制流的任务之间移动，并且“服务器”代码被被动地执行。我们兼容地用迁移线程替换了Mach的静态线程，试图将操作系统设计和实现的这方面隔离开来。
我们设计的关键元素是将线程抽象解耦为执行上下文和可调度的控制线程，这些线程由上下文链组成。我们实现的一个关键元素是，线程现在是基于内核的，并且通过向上调用临时地进入任务中。
新系统为线程操作和额外的控制操作提供了更精确的语义定义，允许调度和记帐属性跟随线程，简化了内核代码，并提高了RPC性能。为了向后兼容，我们保留了旧的线程和IPC接口，不需要对现有客户端程序进行更改，只需要对服务器进行最小的更改，这一点由一个功能强大的Unix单服务器和客户端所演示。关键RPC路径上的逻辑复杂性减少了9倍。
执行普通封送处理的本地RPC速度提高了1.7-3.4倍。我们得出结论，迁移线程模型优于静态模型，内核可见RPC是这种改进的先决条件，并且以这种方式改进现有的操作系统是可行的。

1.介绍和综述

我们首先定义和解释四个概念，这是本文的关键。它们是内核线程和用户线程、远程过程调用、静态线程和迁移线程。我们将解释内核线程在实现RPC时如何交互，以及使用静态线程和迁移线程实现RPC之间的区别。

线程：正如这个术语在大多数操作系统和线程包中使用一样，线程在概念上是一个连续的控制流。在传统Unix中，单个进程只包含单个内核提供的线程。Mach和许多其他现代操作系统支持每个进程多个线程，称为内核线程。它们与用户线程不同，用户级线程包提供的用户线程通过操作程序计数器和用户空间堆栈，在内核提供的线程之上实现多个控制线程。在本文的其余部分中，我们使用术语“线程”来指内核线程，除非经过限定。

在大多数操作系统中，线程不仅仅包含控制流，在Mach 3.0中，（1）线程也是一个可调度实体，具有优先级和调度策略属性（2）包含CPU累计时间等资源计费统计信息（3）包含计算的执行上下文——寄存器、程序计数器、堆栈指针的状态，以及对包含的任务和指定的异常处理程序的引用（4）提供线程控制点，通过线程控制端口对用户程序可见。

RPC：远程过程调用，顾名思义，对过程调用抽象进行建模。但是在不同的任务之间实现，控制流暂时移动到另一个位置，然后返回到原始点并继续，RPC可以在远程计算节点之间使用，但通常在同一节点上的任务之间使用:本地RPC。
在本文的其余部分，为了简洁起见，我们使用不限定的术语“RPC”仅指本地RPC(比通常使用的术语更受限制)。当客户机任务中的一个线程需要另一个任务提供的服务时，比如打开一个文件，它会打包一个数据包，其中包含服务提供者(在本例中是服务器，或者文件系统)处理请求所需的所有内容。这称为封送消息。然后客户端线程调用内核，将消息复制到服务器的地址空间中，并允许服务器开始处理它。一段时间后，服务器以另一条消息的形式将结果返回给客户机，允许客户机继续处理。

值得注意的是，尽管几乎所有的现代操作系统都在某种程度上提供了RPC抽象，但这种支持是连续的。一些操作系统支持RPC作为一个完全的内核可见实体，一些操作系统为RPC涉及的组合消息发送和接收提供了一个内核接口和特殊的优化，但从根本上只理解单向消息传递(Mach)，而一些操作系统仅通过在其他进程间通信(IPC)设施上分层的库(Unix)支持RPC。

静态线程：静态线程和迁移线程的区别在于客户机处理和服务器处理之间实现控制传输的方式。在基于静态线程的RPC中，涉及两个完全独立的线程:一个限于(或静态地)客户机任务，另一个限于服务器任务。当客户机调用内核来启动RPC时，内核不仅将客户机的消息复制到服务器中，而且还将客户机的线程置于睡眠状态，并唤醒服务器中的一个线程来处理消息。
这个线程称为服务线程，以前由服务器创建，唯一的目的是等待RPC请求并处理它们。当服务线程完成请求后，它调用内核，内核将使服务器线程重新进入睡眠状态，并再次唤醒客户机线程。在将控制从一个线程切换到另一个线程时，涉及到一个完整的上下文切换——地址映射、任务、线程、堆栈、寄存器、优先级等的更改，包括对内核调度器的调用
使用基于静态线程的RPC，服务器的计算资源(使用CPU的权利)用于向客户机提供服务。在面向对象的世界中，这被称为“活动对象”模型，因为服务器“对象”包含主动提供服务的线程。

迁移线程：如果RPC对内核是完全可见的，那么就可以实现另一种控制传输模型。迁移线程允许线程从一个任务“移动”到另一个任务，作为其正常功能的一部分，在这个模型中，在RPC期间，内核不会在其IPC内核调用时阻塞客户机线程，而是安排它在服务器代码中继续执行。内核不需要唤醒服务线程——相反，对于RPC而言，服务器只是一个被动的代码存储库，用于客户机线程执行代码。正是由于这个原因，在基于对象的世界中，这被称为“被动对象”模型。只涉及到部分上下文切换——内核切换地址空间和CPU寄存器的一些子集，如用户堆栈指针，但不切换线程或优先级，也从不涉及调度器，不需要恢复服务器线程状态(寄存器、堆栈)。客户机自己的计算资源(CPU的权限)用于为自己提供服务。注意，这个模型中的绑定与线程切换模型中的绑定非常相似，将在6.2节中详细介绍。
尽管大多数操作系统都支持使用静态线程模型的RPC，无论内核是否可见，但重要的是要注意，并不是所有的系统服务都是如此。所有使用“进程模型”来执行它们自己的内核代码的系统实际上在内核调用期间将用户的线程“迁移”到内核地址空间。没有上下文切换——只有堆栈和特权级别被更改——用户线程的资源被用来为自己提供服务。

静态vs迁移线程：实际上，这两种模型之间有一个连续统一体，例如，在一些系统(如QNX)中，某些客户端线程属性(如优先级)可以传递给(由)服务器线程。或者服务线程可能在客户机调用之间不保留任何状态，只提供用于执行的资源，就像在Peregrine RPC系统中一样。因此，不可能对每个线程和RPC实现进行精确分类。然而，大多数系统显然位于频谱的一端或另一端。

1.1 在Mach上提供迁移线程

Mach使用静态线程模型，线程包含上面线程段落中概述的所有属性，在我们的工作中，我们将线程抽象的这些语义方面解耦为两组，并添加了一个新的抽象，即激活堆栈，它记录由rpc产生的客户机-服务器关系。
一个线程现在仅仅是

控制的逻辑流，用任务中的一堆激活来表示
具有优先级和资源核算属性的可调度实体、

一个激活代表：

计算的执行上下文，包括正在执行其代码的任务、异常处理程序、程序计数器、寄存器和堆栈指针
用户可见的控制点

导出到用户代码的抽象与旧的线程抽象相对应，现在我们内部称之为激活，这不仅对用户程序的需求有意义，而且还提供了与原始Mach的兼容性。
上述定义的实际线程是可调度实体，不再隶属于任务。通过使RPC成为内核的单个可识别实体，并显式地记录激活堆栈(由RPC产生)中各个激活之间的关系，我们已经将RPC提升为一个对内核完全可见并得到内核支持的实体，而不是一系列消息传递操作。我们的线程抽象现在更紧密地建模了线程的原始概念基础:控制的逻辑流。事实证明，提升线程和RPC抽象也增强了可控制性，因为内核现在可以对单个激活或整个线程采取更精细和精确的操作。例如，它可以沿着激活链传播信息(“警报”)。向内核引入任务间RPC概念的另一个好处是，可以进行大量积极的IPC优化。这是我们最初的动机之一，但许多其他好处也随之而来。

1.2 概述目标和好处

我们对这个项目最初的目标有以下几点：

改变Mach3.0的线程模型为迁移线程模型
保持向后兼容性
通过RPC优化启用静态线程无法实现的性能改进。在设计和实现过程中，我们发现我们可以实现更多:
普通的基于消息(完全编组)的RPC变得快得多
线程可控性得到了增强
内核代码变得简单
实现了静态线程与迁移线程的苹果苹果比较

在本文的其余部分，我们将详细描述这项工作，我们首先讨论相关工作,然后覆盖迁移线程模型的优点,描述我们内核实现和接口,包括线程的讨论可控性问题,检查新系统RPC是如何工作的,并提到如何更改为更好地利用Unix服务器迁移线程，最后，介绍了本论文的实施现状和初步成果，并对今后的工作进行了概述，最后得出了本论文的结论。

2 相关工作

大多数操作系统使用静态线程模型，但也有一些例外。Sun的Spring操作系统支持的迁移线程模型与我们的非常相似。尽管使用了不同的术语。Spring的“梭子”对应我们的“thread”，而它们的“thread”对应我们的“activation”。Spring解决了可控性问题，但不需要考虑向后兼容性。Alpha可能是第一个完全采用迁移线程的系统。它面向实时约束，它的迁移线程抽象对于执行调度、异常处理和资源属性特别重要。在这两种系统中，线程都可以在分布式环境中跨节点迁移，实际上Alpha对于迁移线程的术语是“分布式线程”。Psyche是一个支持线程迁移的单地址空间系统。Taos上的轻量级RPC系统利用迁移线程(控制传输)作为其设计的关键部分，但重点关注高性能本地RPC，并包括额外的数据传输优化。这使得很难区分改进的控制转移带来的好处。面向对象系统传统上区分了“主动”和“被动”对象，对应于静态和迁移线程模型。Clouds是被动对象(迁移线程)模型的典型代表，而Emerald，正如我们所做的，同时提供了主动对象和被动对象——对两种执行方式的支持，Chorus只能在用户级任务之间进行线程切换，但是在内核保护域中运行的任务之间有“消息处理程序”，它在迁移线程模型中运行。
我们相信，许多迁移线程系统并没有完全解决随之而来的可控性问题——例如，没有完全支持调试或需要提供Unix信号语义。调度器激活是对用户级调度提供特殊支持的内核线程。调度器激活主要关注保护域中内核线程的行为，而我们的工作是处理跨保护域的线程行为，因此，这些工作在很大程度上是正交的，理论上可以结合在同一个系统中，但我们在这里不处理这个问题。除了Taos上的LEPC之外，所有支持迁移线程的现有系统从一开始就是以这种方式设计的。除了线程模型，它们在许多方面都与传统操作系统不同。据我们所知，到目前为止，线程模型问题本身还没有被分离出来并加以检验，比较所有的性能、功能和简化。我们的目标是通过比较同一操作系统中的两个线程模型来实现这一点，提供关注于线程模型的信息。通过在Mach 3.0上实现线程迁移，我们还演示了如何使带有静态线程的现有操作系统适应线程迁移

3.动机

迁移线程方法有几个优点，将在本节中概述。大部分的好处都与使用RPC有关，并首先进行描述。但是，在所有内核交互过程中，线程也有可控制的优势，在3.2节中概述了这些优势。在Alpha OS的上下文中，还讨论了迁移线程所提供的许多优点。

3.1 远程过程调用

迁移线程的许多优点源于它们与RPC的结合使用。与静态线程相比，迁移线程提供了更合适的底层抽象来构建RPC接口。静态线程的许多问题源于控制模型(单个控制线程中的过程调用抽象)和用于实现模型的机制(在不同任务中执行的两个线程)之间的语义差距，为RPC使用迁移线程在性能、功能和易于实现方面提供了好处。因为RPC使用得非常频繁，尤其是在更新的基于微内核的操作系统中，大多数内部系统交互都基于RPC，系统的这个方面在决定整个系统的性能和功能时非常重要。

调用效率

对于在静态线程模型中执行的rpc，两个线程(每个任务一个线程)必须在内核中同步。在操作期间需要两个线程到线程的上下文切换:一个是on call，一个是on return。然而，在迁移线程模型中，整个RPC可以由一个线程执行，该线程临时移动到服务器任务，执行请求的操作，然后返回到客户机任务，并获得结果。不需要进行同步、重新调度或全上下文切换。线程迁移也允许优化，例如那些在LRPC[3]和其他灵活结构或共享地址空间系统，例如Lipto[15]， FLEX[7]，和Mach内核服务器[22,17]。在这些系统中存在一定程度的域间内存共享或保护松弛，从而模糊了域边界。由从一个域迁移到另一个域的线程实现的RPC可以利用这种边界模糊，在参数传递和堆栈处理方面提供许多优化。在极限情况下，在迁移线程模型中实现的RPC可以专门化为一个简单的过程调用。
这些优点通常适用于任何服务调用机制，而不仅仅是通过RPC调用的大型服务器。例如，在基于对象的环境中，如果所有对象都必须是活动的，那么对相对细粒度对象的调用是非常有效的。对于被动对象，将类似的调用抽象应用于中等粒度和粗粒度对象更可行。
尽管基于静态线程的快速、高效的微内核的存在证明了在该模型中高性能是可能的，但这样的系统经常强加语义限制，使它们的实现向迁移线程模型扭曲。例如，商业实时操作系统QNX[20]，
仅支持非队列的、同步的、直接的进程到进程的消息传递和优先级继承;这种设计使其成为事实上的迁移线程系统。其他微内核，如L3[23]，保留了静态线程的完整语义，但是为了实现高性能，必须对调度的灵活性以及与RPC不直接相关的系统的其他方面施加严格的限制。

线程属性和实时服务

在静态线程模型中，当客户机任务执行RPC时，控制权被转移到完全不同的线程，该线程具有自己的调度参数(如执行优先级)以及其他属性(如资源限制)。除非采取特定的操作，否则服务器中的线程属性将为与客户端线程完全无关。当高优先级的客户机不公平地与访问同一服务器的低优先级客户机竞争时，这可能会导致典型的饥饿和优先级反转]问题。另一方面，如果客户机线程迁移到服务器来执行操作，那么所有这些属性都可以得到适当的维护，而不需要额外的工作。显然，这个问题对于提供实时服务的系统特别重要
一个相关的优势是资源核算，它可以更加精确，因为在服务器上代表客户端完成的工作可以自动地这样做。

在RPC中的中断

通常，由于异步条件，需要中断客户机被阻塞的RPC，无论是临时的还是永久的。要在静态线程模型中干净地完成此操作，仅仅中止消息发送/接收操作是不够的，因为服务器将继续处理请求，而不表明客户机不再希望完成请求。如果某个实体想要中止某个线程被阻塞的RPC，它必须找到RPC所指向的服务器，知道如何与该服务器进行足够的交互以向其发送中止RPC操作的请求，并向服务器提供某种标识，指定要中止的RPC。这通常被证明是一个复杂和困难的过程。此外，可以访问的每个服务器都必须支持这些中止操作。这在实践中很难保证，特别是如果任何用户模式任务可以将自己设置为“服务器”，并允许其他用户线程将rpc设置为它，Mach 3.0就允许这样做。另一方面，迁移线程提供了一个通道，通过这个通道可以传播中断的标准化请求。

服务器简化

“人格服务器”,模拟的整体操作系统如Unix或OS / 2,我们预计迁移线程来简化服务器,因为服务器是基于原来的操作系统可能会迁移线程模型,使用有限的线程“迁移”到单片内核系统调用。在personality server中维护这个模型可以实现更大的代码重用，并简化了系统调用中断、线程管理和Unix信号等控制机制的处理。
我们还希望迁移线程来简化服务器中的RPC服务，因为预期激活池的管理要比线程池简单，如第6.2节所述。

内核RPC路径简化

正如第8.5节的结果所示，迁移线程也大大简化了内核RPC路径。基于迁移线程的RPC路径往往很短而且很自然，而基于静态线程的优化RPC路径通常很长、复杂，并且包含无数的测试。

3.2 线程可控性和内核简化

迁移线程实现提供了与RPC无关的其他可控制性和简化优点。在静态线程模型中，线程通常是完全可控的资源。理想情况下，在这个模型中，任何具有适当特权的实体，例如Mach中持有\线程控制端口的程序，可以在任何时间任意地停止线程并修改其状态。从概念上讲，线程只执行用户模式指令，因此永远不会因为操作线程而破坏系统完整性。

不幸的是，这个模型以其最纯粹的形式不能在真实的操作系统中工作。线程必须能够调用内核级代码，以便与系统中的其他实体进行通信，如果它们要做任何超出纯计算的事情的话。由于执行未知内核代码的线程可能不会被任意操纵，因此完全可控性的模型必须在某种程度上发生变化:必须能够在必要时推迟或拒绝线程控制操作。

传统的操作系统有各种方法来解决这个问题，这些方法通常可以工作，但通常是复杂的、不一致的和不可预测的。例如，Mach 3.0提供了一个线程控制操作，它可以中止一个目标线程阻塞的系统调用，这样线程就可以被操纵了。然而，许多内核操作不能以透明的、可重新启动的方式中止，因此试图控制线程的实体可能必须等待任意长度的时间，或重试任意次数，然后才能安全地这样做。如果是这样，那么谁是真正被控制的——目标线程还是试图控制它的线程?

由于完全的可控性模型无论如何都是不现实的，因此减少模型的野心，以允许线程迁移，为线程操作提供更精确定义的语义。实际上，通过强制显式地定义可控性边界，并记录任务间的控制流，内核可以提供额外的线程控制机制，如跨域“警报”。定义控件的边界还可以简化所有控件机制的实现，如第8.5节所示。

4.内核实现

在本节中，我们将描述Mach 3.0微内核中迁移线程实现的底层结构。我们使用的许多技术也可以类似地应用于其他传统的多线程操作系统，如单片Unix内核。

4.1 线程的实现

从概念上讲，传统的Mach 3.0用户线程开始执行特定的任务，偶尔会陷入在内核中与“外部”实体通信。内核随后从系统调用中返回并恢复了用户代码。线程的初始位置和正常位置都在用户空间中，线程只是偶尔“访问”内核，以请求服务。

在我们的迁移线程实现中，情况在某种意义上是相反的。线程开始作为纯粹的内核模式实体执行，然后向用户空间进行向上调用以运行用户代码。从概念上讲，内核是所有线程的“home base”:执行用户级代码的唯一时间是在进入任务的“临时中断”期间。在用户模式下执行的线程与当前运行的任务相关联，但在内核中运行的线程与任何用户级任务没有紧密关联。

虽然内核中的线程现在可以向用户空间进行向上调用，但传统的内核/用户界面仍然保留。一旦线程在用户空间中执行，它就可以以陷阱和异常的形式回调内核。或者，内核可以进一步向上调用相同或不同的用户任务。这种对内核/用户界面的重新定义是我们实现中支持迁移线程的主要机制。

应该区分“内核”代码和我们所说的“粘合”代码。内核在概念上是一个保护域，很像用户级任务，线程可以在其中执行、等待、迁入和迁出等等;它的主要区别是它具有特权并提供基本的系统控制服务。粘合代码是低级的、高度依赖于系统的代码，它在所有保护域(包括用户域和内核域)之间进行转换。内核代码和粘接代码之间的区别经常被忽略，因为这两种代码通常在管理器模式下执行，并且经常在单个二进制映像中链接在一起。然而，这并不一定是事实;例如，在QNX中，7K“微内核”基本上只包含胶合代码，而“内核本身”被放置在一个特殊的特权但其他方面都很普通的进程中。在后面的部分中，我们将会清楚地看到，即使内核代码和粘合代码仍然可以放在一起，但是在迁移线程的情况下，它们之间的区别变得极其重要。

4.2 控制抽象和机制

即使在静态线程模型中，线程的完全可控性在实践中也不能完全实现。虽然线程位于内核中的情况在某种程度上可以作为一种特殊情况来解决，但随着迁移线程的增加，必须更仔细地考虑可控性问题。现在，内核不仅“超出”了线程控制的范围，而且为了维护任务之间的保护，迁移到其他保护域的线程也可能是不可控制的。例如，如果客户机中的一个线程迁移到用于RPC的服务器上，则不允许同一客户机中的另一个线程在执行服务器代码时停止或操作第一个线程的CPU状态。

为了同时提供可控性和保护，我们将“线程”的概念分为两部分:调度程序使用的部分和提供显式控制的部分。第一个线程(我们仍然将其称为“线程”)在任务之间迁移，并进入和离开内核。第二种是用户模式调用或激活，它始终固定在特定任务上。任意控制只允许在特定的激活中进行，而不允许在整个线程中进行。

每当一个线程迁移到一个任务中时(包括内核在线程创建时的初始向上调用)，一个激活就会被添加到线程的“激活堆栈”的顶部。当线程从迁移中返回时，相应的激活将从激活堆栈中弹出。这个新的内核可见的抽象，栈或激活链，有助于提供可控性。

激活要么在线程创建期间隐式地创建，要么由希望接收传入的迁移线程的服务器显式地创建。显式创建的激活在线程迁移到该任务并“激活”它之前是未被占用的。

在内核中，对激活的控制主要是通过异步过程调用(APCs)实现的，类似于单片内核中的异步陷阱(ast)。当从内核返回到激活时，胶水代码检查附加到激活的apc，如果存在，调用它们。例如，为了挂起一个激活，APC被附加到该激活，该激活将被阻塞直到恢复。在此之前，Mach将线程挂起作为调度程序的一部分来处理，给它已经很复杂的状态机增加了更多的复杂性;现在调度程序对一个线程挂起另一个线程一无所知。相反，使用的是内核的普通阻塞机制，其中线程只“挂起”自己。

4.3 内核堆栈管理

由于激活链在任何时候都可能中断，所以激活之间的所有链接信息都存储在激活本身中，单个内核堆栈就足以满足整个线程的需要。为了能够跨分布式系统中的节点进行任务迁移，这也是必需的，因为内核堆栈上保存的状态不容易封装以进行传输。这种显式的状态保存通常被称为使用延续，尽管我们的实现与过去Mach中使用延续的方式有很大不同。特别地，我们将延续限制为纯粹的“粘合”(转换)代码;所有高级内核代码都使用普通的进程模型。

5 可控性：语义、接口和实现

在本节中，我们将描述线程控制操作的语义、这些操作的接口以及实现的某些方面。我们相信我们的方法同样可以应用于其他传统的多线程操作系统。

5.1 线程控制接口

在原始Mach内核中，线程以线程控制端口的形式导出到用户模式程序中，通过线程控制端口可以调用控制操作。在我们的系统中，当线程仍然存在时，呈现给用户级代码的控制抽象是激活控制端口。这可以工作，因为导出给用户的旧线程执行抽象被绑定到单个任务，就像现在的激活一样。我们通过使用激活控制端口直接替换二进制级的线程端口来维护与现有Mach代码的兼容性——所有先前预期或返回的线程端口现在都使用激活端口。为了在源代码级别上兼容，提供了适当的同义词。

Alerts

在我们的迁移线程实现中，我们提供了Mach 3.0的thread_abort调用的功能，它中止正在进行的内核操作，并将控制权返回给用户代码。但是，我们提供了一种更简洁、更通用的形式。警报是一种异步消息形式，从客户机传递给它所调用的内核或服务器，请求被调用方终止请求的操作，并尽快将控制权返回给客户机。
警报主要是内核以统一的方式支持的一种信息传递机制。它们本身并不提供对线程的控制，因为它们没有强制功能:警报只是“请求”，而不是“要求”。我们目前仅为服务器实现一个轮询接口来发现警报，但将来可能还会提供一个异常接口。警报与Spring中的警报非常相似，Taos的“Alert”和“TestAlert”功能类似，但显然不能跨域操作。

默认情况下，添加到线程堆栈的新激活会阻塞警报，以防止干扰不小心的服务器的功能。内核已经能够处理大多数警报，并且可以设计用于迁移线程的新服务器来处理这些警报。实际上，我们提供了一个通用的中断请求机制，它在迁移rpc和内核调用中都统一工作。
我们还提供了另一个操作，该操作首先在目标激活时生成警报，然后断开链，立即将控制权返回给客户端。这很像下面讨论的终止

挂起

在Mach 3.0线程语义中，挂起一个线程的基本目的是防止它执行更多的用户模式指令，直到它被恢复。因此，挂起任务的线程将该任务转换为“被动实体”，允许检查或修改其地址空间和其他状态，而不受其线程的干扰。只要计算没有隐式引用线程的任务，就不需要立即停止线程的所有计算。例如，可以允许在线程挂起时执行显式的设备I/O，但是内核copyin和copyout操作(这将隐式地影响任务的地址空间)不能执行。

我们当前的实现允许这样的内核活动继续进行。我们不期望这在实践中成为一个问题，但在任何情况下，它都应该作为相关工作的副作用来解决。在这项工作中，我们进一步将内核代码与“粘合”代码(前面描述过)分离开来。当激活被挂起时，内核确保用户模式或glue指令都不会在该激活中执行。如果线程正在其他地方执行，它将不会受到影响，直到它试图返回挂起的激活。

为了在这个模型中保持正确的挂起语义，内核系统调用对调用者任务的隐式引用必须被限制在粘合代码中。这在Mach中相对容易做到，因为大多数内核调用都是作为对内核对象的通用RPC实现的:只有低级RPC代码需要遵守控制语义，而不是实现内核调用的实际代码

终止

我们实现中的终止机制如图1所示。如果一个不在线程激活堆栈顶部的激活被终止，或者此时线程正在内核调用中，那么该线程将分裂为两个具有相同调度参数的独立线程。一个线程保留激活堆栈的顶部部分，位于终止的激活之上，而另一个线程保留底部部分。具有上段的线程继续在最顶层的服务器上不间断地执行，确保线程终止不会违反保护，警报通过这个线程自动向上传播，提示正在完成的工作可能不再有价值。给定激活堆栈底部部分的线程返回到它现在的顶部激活，并带有适当的错误代码。这本质上与Spring中使用的终止机制相同。

在我们的系统中，不仅当线程在用户模式下以比终止激活更近的激活运行时，而且当线程代表终止激活在内核中执行时，线程也可以被分割。以前，试图终止一个线程可能会阻塞一段时间，而调用者会等待受害者离开内核或到达一个“干净点”。在新的模型中，终止激活总是一个立即的操作:如果终止的激活恰巧调用了内核，那么它就会留下来完成它正在执行的任何操作，然后悄悄地自毁。粘合操作和内核操作隐式地影响线程的任务的问题在“挂起”一节中进行了处理。

我们的终止机制需要仔细规划内核数据结构和锁定机制;特别是，必须精确地定义内核和粘合代码之间的线。然而，一旦解决了这个问题，这种技术不仅增加了额外的可控性，而且大大简化了内核中控制机制的实现，正如我们在第8.5节中所展示的那样。

CPU状态

最初的Mach 3.0设计提供了线程操作，在“理想的”完全可控模型中，可以随时保存、恢复、检查和修改线程的整个CPU状态。所有的CPU状态操作都是由两个原语thread_get_state和thread_set_state提供的，它们被定义为仅在目标线程挂起时才产生一致的结果。然而，由于完全可控模型的问题，CPU状态控制机制通常被认为是有用的许多东西，实际上在Mach 3.0[18]中无法在有界时间内可靠地实现。
例如，将任务的状态封装为检查点或传输到另一个节点，可能需要控制线程等待任意长时间，或者需要中止内核操作，从而可能产生不准确的状态。

因为现有的CPU状态控制操作已经有问题,它会很难达到完整的向后兼容性,我们选择结构这些操作在我们的迁移线程实现适合当前使用这些操作:特别是那些由Unix服务器和模拟器,通过应用程序创建自己的线程以直接方式和控制它们。

Mach 3.0要求线程在检查或设置其状态之前调用thread_abort，除非该线程刚刚创建。否则，状态操作将使用“陈旧的”信息，产生无用的结果。在迁移线程中，在操作其状态之前中止激活并不是严格要求的。如果没有这样做，CPU状态操作将耐心等待，直到线程处于目标激活状态，而不会干扰其功能。因此，我们放松了对这些操作的限制，同时保持了它们在最初Mach 3.0中唯一有效使用的向后兼容性。

调度参数

Mach 3.0最终的线程控制操作必须映射到激活操作，这些操作管理线程调度参数，如优先级、调度策略和CPU使用统计数据。与上面描述的操作不同，这些操作在概念上仍然是在线程上执行的，而不是在激活中执行的。然而，最初的Mach 3.0线程控制端口已经变成了激活端口，这就提出了如何处理这些操作的接口的问题。

因为每个激活都被附加到一个线程上，所以在我们当前的实现中，我们将线程操作导出为对激活的操作，并且在内核中，将操作重定向到附加的线程上。然而，这就产生了一个保护问题，因为线程中的任何激活都可以修改全局调度状态。例如，服务器在处理RPC时可以降低线程的最大优先级(在没有特殊权限的情况下不能引发该优先级)，在客户机返回时留下一个“瘫痪的”线程。在我们的初始实现中，这在实践中不是问题，因为Unix服务器受到所有客户机的信任。更好的解决方案是提供一个激活操作，该操作禁止堆栈中更高位置的后续激活更改全局线程状态。线程状态仍然可以从激活或更低的级别被操纵(假设它在更低的级别上也没有被禁止)。

5.2 任务控制端口

大多数任务控制操作在迁移线程下的工作方式与最初的Mach设计相同。其他的则以简单的方式进行修改，以匹配新的线程模型。特别地，task_threads调用现在返回任务的激活端口列表，而不是线程端口。当一个任务被挂起、恢复或终止时，它内部的所有激活(而不是线程)都以类似的方式挂起、恢复或终止。

6.RPC迁移

支持迁移线程的基本内核机制就绪之后，还需要演示它对RPC性能和复杂性的影响。因为我们在这一点上的重点主要是在RPC期间的控制传输，我们的初始实现基于用户模式存根完成的封送和解封送，保留了原始Mach数据传输接口。在本节中，我们将描述这个RPC系统，以及为使服务器支持迁移RPC所需要的更改。因为内核本身几乎是完全向后兼容的，所以在使用传统RPC时不需要做任何更改

6.1 客户端

从客户机的角度来看，RPC语义(包括绑定)是未修改的。支持具有正常mach msg调用的现有二进制文件:内核检查消息选项，以确保它们指定一个真正的RPC，并检查目标端口，以确保服务器能够处理迁移的RPC。
在实践中，几乎所有MIG生成的mach msg调用都满足这些需求，因此大多数客户机都会自动使用迁移RPC。请注意，数据仍然可以包含端口权限和超限内存。

6.2 服务端

初始化支持迁移RPC的服务器与只支持线程交换RPC的服务器的方式几乎相同。在完成绑定的主要部分时，服务器将发送权限导出到客户机，与之前完全一样。
此外，服务器必须创建一个或多个未被占用的激活，每个激活都在其自己的地址空间中包含一个指向堆栈的指针，并在绑定的最后一部分，即其正常分派函数的入口点。向内核提供这些信息可以封装在一个函数中，例如在cthreads包中。

仍然自动支持传统的静态线程RPC。不再需要大量的服务器线程池，但至少仍必须存在一个服务器线程池来处理偶尔的异步消息，因为在当前实现中，当无法使用迁移RPC时，这被用作后备机制。

当将一个迁移RPC放入服务器中时，内核从服务器池中分配一个未被占用的激活，将传入的消息复制到服务器堆栈，并向分派例程向服务器任务发出upcall。这个米格生成的例程与用于分派传统消息的例程相同，只是它通过一个特殊的内核入口点返回。在返回时，内核不需要做任何安全检查或端口操作，并且在mach_msg调用中由客户机提供的应答端口根本不会被使用。

如果尝试迁移RPC，并且内核发现当前没有可用的激活，那么在我们的初始实现中，内核将退回到正常消息路径，从而导致正常消息被排队到端口。这并不理想，我们计划检测最后一个可用的激活何时将用于迁移RPC，而不是立即创建请求的RPC，而是临时“侧道”并向服务器发出一个特殊的通知upcall。此时，如果服务器认为需要的话，它可以创建更多的激活。如果它这样做了，它将它们返回到内核，原始RPC就可以继续进行。否则，它立即返回和RPC阻塞，直到堆栈被释放。

在实现这一点时，激活池的服务器管理应该比线程池的管理简单得多，原因有几个。资源将根据需要由客户端线程自己分配，而不是由服务器提前预测资源需求。服务器可以使用一些简单的衰减函数来释放激活(与内核线程相比，它们只是被动的数据结构，因此内核管理激活的成本很低)。相反，使用线程池时，服务器被内核“墙”与客户机的请求分隔开——如果服务器线程数量不足，客户机消息就会在服务器不知情的情况下在队列中堆积起来。服务器有一个更复杂的工作,它必须跟踪等待消息的线程数、在服务器上运行的线程数以及在传出的rpc或内核调用上被阻塞的线程数。。最后一个方面特别尴尬，因为它需要用唤醒和管理服务器线程的操作来围绕每个这样的阻塞调用。如果不这样做，就会导致死锁。最后，大量的复杂性是由于在内核线程上复用cthreads造成的，这是迁移线程无法完成的。但是，如果发现有必要限制特定服务器上执行的线程总数，以避免由于过度的内核上下文切换而导致的饱和，那么这种简化就不会出现。

6.3 用户级线程问题

迁移RPC最重要的问题是在Mach上使用最广泛的用户级线程和同步包cthreads在迁移RPC时有很大的限制。

服务器线程管理

cthreads库给正在迁移的RPC的服务器带来了一个严重的问题。服务器使用cthreads在内核线程之上实现用户线程的多路复用，尽可能用更快的用户级上下文切换替换内核模式上下文切换。然而，用户级线程包所做的一个主要假设是，它运行用户级线程的所有内核线程都是可互换的，因此一个内核线程可以和另一个内核线程一样用于某个操作。该假设在静态线程模型中是可以满足的，但在此过程中对服务器线程进行了实时监控。

然而，在迁移线程模型中，从客户机迁移进来的内核线程是不可互换的——它们可能具有不同的优先级和其他属性。即使忽略这一点，在处理RPC后返回到内核必须在RPC进入的同一内核线程上完成。一般来说，尝试以这种方式实现多线程会失去我们设计的主要优势之一:提供一个内核实体(激活堆栈)，它代表正在进行的特定工作，即整个控制逻辑线程。因此，将服务器的用户级线程复用于传入的内核线程之上是不合适的。在cthreads中，可以通过“连接”用户级线程轻松地避免多路复用。

然而，在消除用户级线程多路复用的过程中会损失一些速度，因为现在服务器中的同步操作有时需要内核级上下文切换，而不是用户级上下文切换。测量实际的应用程序(包括多处理器上的应用程序)是必要的，这样我们才能确保更好的RPC性能带来的好处不会被这个额外的成本所抵消。我们相信，在典型的RPC服务器中，用户级上下文切换的速度优势并不像在计算密集型应用程序中那样显著，计算密集型应用程序是线程实现的传统基准。在提供“系统”功能的精心设计的服务器中，我们认为内部争用可以最小化，这样RPC速度的重要性就超过了上下文切换速度。我们指出，在许多基于商业微内核的系统中，包括QNX[20]、Chorus[26]和KeyKOS[6]，操作系统服务器通常不会在多个内核线程上复用用户级线程。相反，这些系统要么提供纯内核线程的多线程，要么它们的函数被及时分解，以便每个服务器可以基于单个内核线程，不需要内部同步。然而，在对使用迁移RPC的服务器进行更广泛的性能分析之前，在为RPC服务时丢失用户级线程仍然是一个问题。

注意，只有当“来宾”线程从其他任务迁移进来时，用户级线程多路复用才有问题;服务器本机线程仍然可以使用某种用户级线程系统，甚至可以使用专门的多路复用机制，如调度程序激活。

一个更合适的同步系统

由于cthreads不能在服务器的内核线程上复用用户级线程，所以应该用一个更好的同步库来替换它，以便在内核线程上提供同步。此外，内核可见的同步对于完全实现优先级继承是必要的，正如我们在一篇更长的论文[18]中讨论的那样。我们正在计划替换cthreads，它在用户级库中提供同步原语，但要与内核合作。

7 unix服务器

要使用传统RPC在新内核上运行，不需要对OSF/1单个服务器和模拟器或它们使用的库进行更改。为了支持迁移RPC，需要做一些更改。最初，我们选择了对现有代码影响最小的方法，但从长远来看，可以提供更好、更干净的机制。服务器被修改为调用cthreads库中的新setup函数并连接传入的cthreads。现有的复杂的服务器线程池管理，虽然基本上不再使用，但仍然保留了下来。我们没有对模拟器进行任何修改。因为我们为线程操作提供了向后兼容的语义，所以不需要对处理Unix信号的现有复杂代码进行修改。

即使对我们的实现进行了调优，我们也不期望在单个服务器上有很大的性能改进，这在很大程度上是因为它是在RPC非常昂贵的假设下编写的。因此，服务器尽量避免RPC，而是求助于其他方法，如共享内存页，迁移RPC并不能提高其性能。然而，我们的最初目标主要不是展示性能改进，而是演示迁移线程在简化性和整洁性方面所带来的好处，以及如何在现有操作系统中以向后兼容的方式实现迁移线程。

理想的修改

我们预期Unix服务器可以通过使用迁移线程的两种修改来简化。其中一种是在Mach下模拟Unix信号。另一个原因是Mach 3.0没有提供将abort请求传播到rpc的标准方法，Unix服务器必须手动处理所有Unix系统调用中断，比如那些由挂起的信号引起的中断。通过利用现在由内核提供的传播中止操作，应该可以大大简化它。这也会使中断语义自然地扩展到系统中的其他服务器，比如运行在Unix下的mach特定应用程序安装的服务器。

8.结果

8.1 状态

我们完成了本文所描述的系统的核心实现。一个未经修改的基于仿真器的Unix服务器使用传统的线程交换RPC在新的微内核上正常运行。修改为提供激活的服务器可以运行多用户，从而使用迁移RPC。Unix信号，包括^C和Z，正在工作。

8.2 实验环境

所有的时间收集在一个单HP9000/730 64mb RAM上。这台机器有67 Mhz PARISC 1.1处理器，128K offchip Icache, 256K offchip Dcache, 96入口ITLB和96入口DTLB，页面大小为4K。缓存是直接映射和虚拟寻址的，缓存丢失的代价约为14个周期。RPC测试时间是通过读取PA的时钟寄存器(每个周期递增)来收集的，并且可以在用户模式下读取。其他时间则从Unix服务器获取。系统软件是Mach 3.0内核的移植版本NMK14.4，以及基于模拟器的OSF/1单服务器版本1.0.4b1。编译器是GCC 2.4.5。完全优化的u5。

8.3 RPC路径分解和分析

为了分析下一节介绍的空RPC 3.6倍的加速，我们沿着内核的空RPC路径手动计算指令数。这些计数在表1中按处理类型进行了分类，并在每个类别中给出了相对(旧/新比率)和绝对(指令数)改进。12%的改进是由于倒置的服务器-内核接口:因为内核现在正在调用服务器，而不是相反，内核不再需要在每个RPC上保存和恢复服务器的寄存器。21%的结果来自内核对RPC的“第一手”知识:它不再需要创建、翻译和使用应答端口来匹配响应请求。41%直接来自迁移线程的优化控制传输:切换激活比切换线程简单得多。20%的改进是由于更简单的数据管理，特别是由于从源到目的地的直接复制，消除了在内核地址空间中维护临时消息缓冲区的需要。这个方面是否与线程迁移有关还有待商榷。

有趣的是，现在迁移RPC的近一半的成本都位于内核-客户端边界上(如果通过内存操作来衡量，则超过一半——参见下面)。因此，对内核RPC路径其他部分的进一步改进可能只会带来最小的总体加速。相比之下，向上调用(尤其是在内存操作中)是如此便宜，这可能会对支持线程迁移的系统结构产生影响。

表1的最后两列显示了每个阶段的改进(通过负载/存储操作的数量衡量)，由于内存子系统的成本，这些操作对整个周期的贡献不成比例。我们观察到，对于RPC的每个阶段，指令计数和内存操作的改进百分比大致相等。这表明指令计数是每个阶段对总体性能增益的相对贡献的有效度量。

对旧的优化RPC路径中的上下文切换代码的检查可以解释它的大部分成本:内核实际上执行了特别手工编写的内联调度程序的一部分。必须满足许多约束:新线程和旧线程必须处于正确的状态，必须正确维护运行和等待队列，必须以正确的顺序获取和释放端口、线程、IPC空间和其他数据结构上的锁，以避免死锁;计时器是操纵;中断级别被改变;必须仔细地跟踪沿途获取的资源，以确保如果由于某种原因，计算偏离了优化路径，就有可能展开所有内容。

表2显示了每个路径的指令组合，分为三类:总指令、加载/存储和分支。迁移路径具有更高的负载和存储百分比(56% vs. 43%)，这可能是由于IPC|寄存器保存和恢复、内存复制和数据结构遍历|的基本内存密集型方面较少被计算开销所掩盖。然而，分支指令的相对发生率要低得多(10% vs 17%)。再加上分支指令总数减少了九倍，这就降低了迁移路径的逻辑复杂性。

一般来说，我们希望我们在RPC路径上的结果能够扩展到PA-RISC之外的其他体系结构。虽然有时dicult，但大多数架构可以在日期连续时实现单个直接复制，例如通过临时映射[23]。改变中断优先级(IPL)在切换路径上做了四次，由于调度程序的介入，但在迁移路径上没有任何改变;IPL更改在PA-RISC上很便宜，但在其他一些架构[28]上却非常昂贵，这使得迁移线程在这些架构上特别重要。在某些架构中，地址空间切换不可避免的成本要高得多，这将导致较低的改进率，但即便如此，我们预计收益也是相当可观的。

8.4 微观和宏观基准测试结果

表3给出了跨任务迁移和传统切换RPC的成本度量。左边的列只包括RPC的内核开销，而右边的列同时包括内核和用户(封送)开销，这是在另一组运行中获得的。在这台机器上，一个空的本地RPC现在在内核中花费的时间少于10微秒。迁移线程的加速随参数大小而变化，对于null RPC是3.4倍，对于1K的数据是2.0倍，对于长内联编组数据是1.7倍。之所以选择1.7是因为数据在切换路径上复制了三次——一次是在编组过程中，两次是在内核|中，但在整个迁移路径上只复制了两次。

一个有趣的观察是，每条指令的循环数(CPI)在迁移路径上(3:0 = 648=213)比在原始路径上(2:1 = 2318=1128)要差得多。我们认为，部分或全部原因是两个因素:如上所述，load/store指令的百分比更高，以及手工编写的迁移路径上的指令没有像C编译器对大部分旧路径所做的那样进行仔细的调度和优化。因此，对迁移RPC路径进行更仔细的编码可能会在一定程度上降低CPI。有必要对CPI差异进行更多的调查。

32K迁移RPC的内核时间的测量显示了HP730的直接映射缓存的严重副作用。在顶部是我们最初的测量结果，一个可疑的低时间导致了相当令人难以置信的4:0速度改进。下面是稍微移动消息缓冲区后采取的相同度量，这样缓存线就会发生冲突，从而导致1:6的改进，低于我们预期的因子2，因为数据被复制了一次而不是两次。这说明了缓存效应在数据传输中的重要性，值得进一步研究。

作为对整体性能影响的初步测试，我们测量了gas组装程序的“制作”时间。在迁移线程的情况下，耗时从109秒增加到107秒，提高了约2%。连接阶段大约需要3秒。一个更大的程序的链接(惠普链接器本身)，从14秒提高到12秒，提高了14%。我们相信这个更大的改进是由于ld有更高的系统调用与计算的比率。

我们放慢速度的一个地方是在内核的rpc中。它们目前还没有迁移，因为我们还没有更改内核以在其端口上提供激活。我们不认为这样做会很困难。完成此操作后，所有原本使用优化路径的消息(真正的rpc)都应该进行迁移。

我们希望一个调优的实现能够实现更多的总体加速，如果执行了迁移线程所启用的其他RPC优化，那么速度会显著提高。

8.5 内核代码简化

在可控性：使线程独立于任务，并且在用户模式之外不受控制，这大大降低了许多方面的代码复杂性。包含大多数线程控制操作的源文件减少了一半以上，从72K减少到32K。在新的支持激活的18K源文件中，对控制操作的支持只占大约10K。这种简化主要是由于线程暂停、恢复和终止的更清晰的管理。最初的Mach 3.0线程控制机制必须针对特殊情况进行大量测试，比如一个线程操纵自己，或者两个线程试图同时控制对方，这可能会导致内核死锁。既然可控性被限制在定义良好的边界内(必须支持迁移线程)，这些棘手的情况就不会发生，因为内核代码总是“越界”的。

由于类似的原因，任务管理代码从38K减少到20K:更干净的模型简化了锁定，消除了许多特殊情况，如线程终止自己的任务。

RPC迁移：在最初的切换路径上，端口转换和上下文切换代码大多是用与机器无关的C代码编写的，而其他类别则是特定于pa的汇编语言。在迁移RPC路径上，与机器无关的部分变得如此微不足道，以至于将它们内联到汇编语言路径中要比与高级语言进行接口更容易。整个1350行复杂的C代码(包括优化的RPC路径和大约400条手工编写的汇编指令)被大约220条汇编指令所取代。从第8.3节的图中可以明显地看出，在逻辑复杂性(9倍)方面所得到的简化。

8.6 内存使用

在最初的微内核中，由于采用了延续机制[14]，通常每个处理器只需要几个内核堆栈(每个8K)。在这个项目的开始，为了简化我们的工作，我们禁用了延续;这立即将内核内存使用量提高到每个线程一个内核堆栈。但是，随着线程迁移，现在系统中的线程要少得多，而且内核堆栈仍然与线程相关联，而不是与激活相关联。在运行我们的多用户基准测试时，我们观察到内核的物理内存使用最多比原始系统多300K。然而，我们正处于在新模式下重新实行延期的过程中，因此，即使是这种增加也应该是暂时的。

关于服务器虚拟内存的使用，在写这篇文章的时候，我们静态地分配了大量的激活(40个)，而旧的线程池仍然保留在服务器中。因此,大约三倍的VM使用前(2.6 MB vs。8 MB)当我们删除线程池,服务器虚拟机使用应该是一样的在旧系统中,因为在大多数情况下每台服务器线程/用户堆栈成为服务器激活/用户堆栈。当然，客户机不受影响，因为它们没有被修改。