ACM通信
研究突出了
高效的系统强制的确定性并行
信贷:英伟达
确定性执行为调试、容错和安全性提供了许多好处。当前执行方法平行然而，程序确定性地常常招致高成本，允许行为错误的软件破坏可重复性，并将依赖时间的竞争转换为依赖输入或路径的竞争，而没有消除它们。我们引入了一个新的并行编程模型来解决这些问题，并使用Determinator这个概念证明操作系统来证明模型的实用性。Determinator的微内核应用程序编程接口(API)只提供了“无共享”的地址空间和确定性的进程间通信原语，以使所有非特权代码的执行行为良好或不可精确重复。在这个微内核之上，Determinator的用户级运行时提供了一个私人空间为线程级和进程级并行编程建模。该模型避免了引入读/写数据竞争，并将写/写竞争转换为可靠检测的冲突。粗粒度的并行基准测试在多核pc和分布式集群中的跨节点上的性能和规模与非确定性系统相当。
1.简介
多核革命使并行编程变得普遍且不可避免，但构建可靠的并行软件是困难的，而且容易出错。主流的并行编程模型引入了普遍的时间依赖风险比赛，导致不确定的“海森堡”。轻微的同步错误通常会导致访问共享内存的线程之间不确定的竞争。2，20.，21在共享文件系统中传递消息或访问文件时，并发进程也会发生类似的竞争，不仅会产生错误，还会产生安全漏洞。25
我们通常更喜欢运行软件确定性，因此，对于给定的输入，它总是产生相同的输出。20.除了方便的考虑，确定性执行也是一种基本的虚拟化工具:实现重放调试所需的基础，19容错,11和问责机制。16入侵分析方法12以及定时通道控制4进一步要求系统执行决定论，即使是那些被设计来逃避分析的恶意代码。
用于并行确定执行的用户空间技术8，22有希望，但有局限性。首先，依靠一个确定性调度程序驻留在应用程序进程中，它们允许有缺陷或恶意的应用程序通过干扰调度器来破坏确定性。其次，确定性调度器通过合成一个可重复但任意的线程间交互调度来模拟传统的api，通常使用指令计数器作为人工时间度量。因此，数据竞争仍然存在，但它们的表现形式微妙地取决于输入和代码路径长度，而不是“实时”时间。第三，隔离和调度线程的内存访问所需的用户级插装可能会招致相当大的开销，即使对于很少同步的粗粒度代码也是如此。
为了应对无处不在的并行性带来的挑战，我们可能需要重新考虑标准的非确定性并行编程模型，而不是仅仅将它们硬塞到人工执行调度中。为此，我们提出限定词这是一个概念验证操作系统，旨在让决定论成为常态，20.避免在任何内存访问的数据竞争21或者更高的语义级别。2由于它的操作系统级方法，Determinator支持现有的语言，不仅可以对单个进程执行确定性，还可以对交互进程组执行确定性，并且可以防止恶意的用户级代码破坏内核对确定性的保证。为了自由地探索设计空间，Determinator采用了一种“全新”的方法，只提供与基本Unix进程、线程和文件api的有限兼容性。为了改进向后兼容性，可以在“沙箱”中实现Determinator的环境，扩展遗留内核。9
Determinator的内核拒绝用户代码直接访问可能产生不确定性行为的硬件资源，包括实时时钟、周期计数器和可写共享内存。用户代码运行在单线程、类进程的层次结构中空间，每个都运行在一个私有的虚拟地址空间，并且只能与它的直接父结点和子结点通信。潜在的有用的不确定性来源，例如内核表示为I/O设备的计时器，只能通过与更有特权的空间的显式通信，由非特权空间访问。因此，监控空间可以协调所有影响非特权空间子树的非确定性输入，记录真实的非确定性事件，以便将来重播，或者合成人工事件。
在这个内核API之上，Determinator的用户级运行时模拟了我们熟悉的共享资源编程抽象。运行时使用文件复制和版本控制24为应用程序提供一个通过Unix文件API访问的逻辑共享文件系统，并采用分布式共享内存技术1模拟多线程应用程序的共享内存。由于这种模拟是在用户空间中实现的，应用程序可以自由地定制它，并且运行时bug不会损害内核对确定性的保证。
而不是模拟传统的并行内存模型，Determinator探索了一个私人空间模型。3.在这个模型中，每个线程保持一个私有的所有共享内存和文件系统状态的虚拟副本;普通读写访问和修改这个工作副本。线程只在程序定义的同步点协调它们的更改，就像开发人员使用版本控制系统一样。这个模型消除了读/写数据竞争，因为读只能看到原因之前在显式同步图中写入，写/写竞赛变成冲突，运行时可以独立于任何(真实的或合成的)执行计划可靠地检测和报告。
使用通用并行基准测试的实验表明，与非确定性环境相比，Determinator可以确定性地运行粗粒度并行应用程序，性能和可伸缩性都很好。但是，确定性在细粒度的并行应用程序上带来了很高的成本，因为Determinator使用虚拟内存来隔离线程。对于几乎不需要线程间通信的“令人尴尬的并行”应用程序，Determinator可以在集群的各个节点上对应用程序透明地分配计算，从而保持可用的性能和可伸缩性。在未来的工作中，该原型仍然有许多限制需要解决，例如受限的空间层次结构、有限的文件系统大小、没有持久存储以及低效的跨节点通信。
2.确定性编程模型
Determinator的目标是提供一个编程模型自然而且普遍确定性．是自然的确定性，模型的基本抽象应该首先避免引入数据竞争或其他不确定性行为，而不仅仅是提供控制、检测或重现竞争的方法。是普遍确定性，模型应该在所有抽象级别上具有确定性的行为:例如，用于共享内存访问、线程间同步、文件系统访问、进程间通信、外部设备或网络访问以及线程/进程调度。
许多中间设计点可能会产生有用的权衡:例如，只在同步上而不是内存访问上强制确定性可以提高效率。22然而，就目前而言，我们探讨的是对普遍决定论采用“纯粹主义”方法的可行性。为了实现这一目标，我们发现我们必须解决当前系统中至少四个不确定性来源:应用程序操作可能需要的不确定性输入;共享状态，如内存和文件系统;线程和进程用来协调的同步api;以及应用程序使用和管理系统资源的名称空间。
2.1.明确不确定性输入
许多应用程序使用不确定性输入，例如Web服务器的传入消息、交互式应用程序的计时器和加密算法的随机数。我们不寻求消除这种不确定性输入，而是使相关输入明确和可控。
并行调试机制，19容错,11问责制,16和入侵分析12所有这些都依赖于重放以指令换指令的计算指令的能力，以复制、验证或分析程序的执行历史。当只需要记录I/O时，重放是有效的，例如对于单处理器虚拟机，12但是如果内部由于并行性而产生的不确定性来源也必须重新播放。13
Determinator将有用的不确定性来源转换为显式的I/O，应用程序通过可控的通道访问它，并且只消除了由于并行性导致的内部不确定性。如果应用程序调用gettime-ofday ()例如，一个监督进程可以拦截这个I/O来记录、回放或合成这些时间“输入”。
2.2.共享状态的无种族模型
传统的系统允许线程并发访问多种形式的共享状态，例如共享内存和文件系统，如果线程没有正确同步，就会产生数据竞争和heisenbugs。20.，21重播调试器19和确定性调度程序8，22一旦数据竞争出现，就使其可重现，但不要更改开发人员编写应用程序时使用的固有的易于竞争的模型。
Determinator将标准的并发访问模型替换为私人空间模型中,3.这就避免了数据竞争。该模型为每个线程提供所有逻辑共享状态的私有虚拟副本，包括共享内存和文件系统状态。线程的正常读写操作只影响其私有工作状态，不与其他线程直接交互。相反，Determinator累积每个线程对共享状态的更改，然后相这些线程间的更改仅发生在程序定义的同步点。这个模型与早期的并行Fortran系统有关，6复制的文件系统,24分布式版本控制系统，15以及数据库中的快照隔离。7然而，据我们所知，Determinator是第一个为普遍存在的线程级和进程级决定论引入这种模型的操作系统。
如果一个线程执行赋值x＝y"当另一个并发执行时"y＝x，例如，这些分配在传统模型中竞争，但在Determinator下是没有竞争的，并且总是交换x与y．每个线程读取x或y总是看到该变量的“旧”版本，在最后一次显式同步点保存在线程的私有工作区中。
图1举例说明一个更现实的游戏或模拟器的例子，它使用一组“参与者”(玩家，粒子等)来表示一些逻辑上的“宇宙”，并在每个时间步并行更新所有参与者。为了更新actor，主线程为每个actor派生一个子线程，然后通过连接所有子线程进行同步。更新每个参与者的子线程代码“内联”在主要()函数，Unix的一个便利fork ()决定符扩展到共享内存线程。
每个子线程读取数组中任何或所有参与者的“先前”状态，然后就地更新其分配的参与者的状态，不需要显式复制或额外的同步。对于标准线程，这段代码有一个读/写竞赛:每个子线程在检查数组中的其他角色时，可能会看到“旧”和“新”状态的任意混合。然而，在Determinator下，这个代码是正确的，并且没有种族问题。每个子线程只读取它的actors数组的私有工作副本，除了子线程本身之外，它是不动的，因为主线程派生了该子线程。当主线程重新连接所有的子线程时，Determinator将每个子线程的actor数组更新合并回主线程的工作副本中，以便在下一个时间步骤中使用。
传统的写/写竞赛变得冲突在这个模型中。例如，如果两个子线程并发写入同一个actor数组元素，则Determinator检测到这个冲突，并在主线程试图加入第二个冲突的子线程时发出运行时异常信号。相比之下，在传统的模型中，任何一个线程都可能“赢得”这个依赖于时间的竞赛，在整个计算过程中默默地传播一个可能错误的值。在传统的确定性调度器下运行这段代码会导致根据合成的、可重现的时间度量(例如，指令计数)而不是实时时间来决定“获胜者”，但竞争仍然存在，并且仍然可能因为输入或指令路径长度的微小变化而显示或消失。
2.3.一个无竞争的同步API
即使在没有内存访问竞争的正确锁定的程序中，标准线程的行为也可能是非确定性的。例如，两个线程可以以任何顺序获得锁，从而导致高级数据竞争。2这种不确定性是锁抽象所固有的:我们可以记录、回放或合成一个锁获取时间表，22但这样的时间表对开发人员来说仍然是随意和不可预测的。
幸运的是，许多同步抽象都是自然确定的，例如fork/join、barrier和future。确定性抽象的关键属性是，当线程同步时，程序逻辑就确定发生同步的线程执行路径中的点，以及所涉及的线程。例如，在fork/join同步中，父进程的同步thread_join（t)手术和孩子的thread_exit()确定各自的同步点，父函数显式地指示线程t加入。锁无法通过此测试，因为有一个线程的解锁()将锁传递给任意的后续线程锁()。如果只有一个线程可以访问队列的每一端，那么像信号量和管道这样的队列抽象就是确定的18但不确定的是，多个线程是否可以在任意一端竞相插入或删除元素。
由于多核革命还很年轻，而且大多数应用程序代码还没有被并行化，我们仍然可以选择使用什么同步抽象。因此，尽管它可以通过确定调度来模拟不确定的原语，但从本质上讲，它只支持无竞争的同步原语。
2.4.Race-free系统名称空间
当前的操作系统api经常通过公开锁隐式同步的共享名称空间而无意中引入不确定性。函数返回的指针受执行时间的影响malloc ()或mmap ()返回的文件编号open ()返回的进程idfork ()返回的文件名mktemp ()在单线程的过程。即使只有一个线程实际使用给定的内存块、文件、进程ID或临时文件，从共享名称空间分配这些名称本质上是不确定的。
Determinator的API避免使用系统选择的名称创建共享名称空间，而是使用应用程序选择的名称创建线程私有的名称空间。应用程序(而不是系统)为分配的内存选择虚拟地址，为子进程选择进程id。这一原则确保了在命名资源时，除了应用程序本身提供的信息外，不会显示任何共享状态信息。由于隐式共享名称空间经常导致多处理器争用，因此设计避免这种隐式共享的系统api可以与最近的多核可伸缩性工作协同工作。10
3.限定词内核
现在我们简要概述Determinator内核的设计和API。应用程序通常不直接使用这个API，而是使用第4节中描述的用户级运行时。
3.1.空间
决定符在层次结构中执行应用程序代码空间,见图2．每个空间由单个控制流的CPU寄存器状态、一个包含代码和工作数据的虚拟地址空间以及一个可选的快照此地址空间先前版本的。确定符空间类似于单线程的Unix进程，有重要的区别;我们使用术语“空间”来强调这些区别，并避免与Determinator在用户级模拟的“进程”和“线程”抽象相混淆。
决定符空间不能比它的父空间活得长，并且空间可以直接交互只有通过下面描述的三次系统调用调用它的直系父节点和子节点。内核不提供文件系统、可写共享内存或其他隐含全局共享状态的抽象。
只有根空间可以通过I/O设备直接访问不确定的输入，例如控制台输入或时钟。其他空间只能通过父/子交互或根空间委托的特权间接访问I/O设备。因此，父空间可以将所有不确定的输入控制到任何非特权空间子树中，例如，记录输入以便将来重播。这种空间层次结构还为I/ o限制的应用程序造成了性能瓶颈，这是我们留给未来工作解决的设计限制。
3.2.系统调用的API
确定符空间仅作为处理器陷阱和三个系统调用sput、Get和Ret的结果进行交互，如表1．参数允许在一个系统调用中组合多个相关操作。例如，Put调用可以初始化子进程的寄存器，将虚拟内存范围复制到子进程中，设置目标范围的权限，快照子进程的地址空间，并启动子进程执行。
每个空间都有一个子空间的命名空间。用户级代码管理此名称空间，在Get或Put中指定任何子编号;如果这个子进程不存在，内核会创建它。如果子进程确实存在并且正在运行，内核会阻塞父进程，直到子进程通过Ret或陷阱停止。这些协作的“会合”语义确保空间只在两个空间执行中定义良好的点上同步。
用户级代码可以在Get或Put调用中指定Copy选项，以在调用空间和子内存之间复制一段虚拟内存。内核使用写时复制(copy-on-write)来优化大型副本，并避免物理复制只读页面。Snap选项同样使用写时复制(copy-on-write)来保存子空间的整个虚拟地址空间的引用快照。
Put调用还支持Merge选项，它类似于Copy，只不过内核只复制那些字节不同在子空间的当前快照和父空间的引用快照之间，不影响父空间中的其他字节。内核还检测冲突:如果一个字节在这两个自快照以来的子空间和父空间，内核会生成一个异常，将冲突视为编程错误，如非法内存访问或除零。Determinator的用户级运行时使用Merge给多线程进程一种共享内存的假象，稍后将对此进行描述。
最后，Ret系统调用停止调用空间，将控制权返回给空间的父空间。除零之类的异常也会导致隐式Ret，为父进程提供一个状态码，表明子进程停止的原因。
为了方便调试或防止子程序循环，父程序可以用指令限制，强制子进程在执行特定数量的指令后返回到父进程。计数指令而不是“实时”保留了确定性，同时允许空间“量化”子进程的执行，以实现用户级别的确定性调度。8
3.3.空间迁移分布
空间层次结构不仅可以跨越多处理器/多核系统中的多个cpu，还可以跨越同构集群中的多个节点。虽然分发对应用程序在语义上是透明的，但应用程序在设计时可能必须考虑到分发，以获得良好的性能。
为了支持分布，内核将每个空间的子名称空间中的高阶位解释为节点号。当一个空间调用Put或Get时，内核首先将调用空间的状态和控制流迁移到子编号参数中指定的节点，然后在剩余子编号位中指定的节点上创建子节点或与子节点交互。图3说明了两个节点之间的空间迁移以及在每个节点上管理子节点。
当内核迁移一个空间时，它首先只向接收内核传输该空间的寄存器状态和地址空间元数据。当空间在新节点上访问内存页时，接收内核按需请求空间的内存页。在一般情况下，当一个空间在几个节点之间重复迁移时，例如，当一个空间在几个节点的每个节点上启动子节点，然后稍后返回收集它们的结果时，每个节点的内核都避免了冗余的跨节点页复制。对于只读页面(如程序代码)，每当空间返回到该节点时，每个节点的内核都会重用这些页面的缓存副本。
4.高级并行抽象
Determinator的内核API消除了许多方便和熟悉的抽象，但是我们可以在用户空间中确定性地重现这些抽象，但需要做一些重要的权衡。本节描述Determinator的用户级运行时基础设施如何模拟传统的Unix进程、文件系统、线程和同步。
4.1.流程和叉/执行/等
我们不打算精确地复制Unix进程语义，而是希望模拟传统的进程语义叉/执行/等足以支持可编写脚本的shell中的常见用途，构建工具如使，以及多进程应用程序(如编译器)。
餐叉:一个基本的Unixfork ()只需要一个Put系统调用，就可以将父进程的整个内存状态复制到子进程空间中，设置子进程的寄存器，并启动子进程。困难在于Unix的全局进程ID (PID)命名空间，这是2.4节中讨论的不确定性的来源。因为大多数应用程序使用返回的pidfork ()仅仅是作为一个不透明的论点waitpid ()，我们的运行时将pid设置为每个进程本地的。每个进程分配自己的pid，这些pid与其他进程的pid无关，并且可能在数值上与其他进程的pid冲突。这种改变会破坏在进程之间传递pid的Unix应用程序，并意味着类似的命令“ps”必须内置到shell中的原因与“cd”已经是。但是，这种方法适用于遵循典型的fork/wait模式的面向计算的应用程序。
执行:Unix的用户级实现exec ()必须构造新程序的内存映像，用来替换旧程序，同时仍然执行旧程序的运行时库代码。我们的运行时将新程序加载到从未被使用过的“保留”子空间中fork ()，然后调用Get将子程序的整个内存复制到(正在运行的)父程序之上:这个Get因此“返回”到新程序中。运行时还将一些Unix进程状态(例如后面描述的PID名称空间和文件系统状态)从旧程序转移到新程序。
等待:当应用程序调用waitpid ()为了等待特定的子进程，运行时调用Get与子进程的Ret进行同步，并获取子进程的退出状态。子进程可以在终止前返回到父进程进行I/O请求;父节点的运行时服务I/O请求并恢复waitpid ()对应用程序透明。
Unix的wait ()等待有问题吗任何(“第一个”)孩子终止，违反了章节2.3中讨论的决定论。内核不能在不损害决定论的情况下提供“等待任何子系统”调用，所以我们的运行时只等待最早派生的子系统。
这种行为不会影响产生多个子进程然后等待所有子进程完成的应用程序，但会影响到的两种常见用法wait ()．首先，交互式Unix shell使用wait ()当后台进程完成时报告;在Determinator下运行的交互式shell需要特殊的“非确定性I/O特权”来提供这种功能(以及交互作业控制等相关功能)。其次，我们的运行时行为可能会对使用的程序的性能产生负面影响wait ()实现用户空间的动态调度或负载均衡。
考虑一个平行使无论运行时是否限制并发子进程的数量。一个普通的“让- j。”允许无限的孩子，把日程安排留给系统。在Unix或Determinator下，内核的调度器将任务分配给可用的cpu，如图4 (a)及(b)．如果用户运行“让j2,”然而,然后使最初只启动任务1和2，然后等待一个任务完成后才开始任务3。在Unix中,wait ()当短任务2完成时返回，启用使立即开始任务3图4 (c)．限定词,wait ()仅当(确定性选择的)任务1完成时返回，导致在的非最优调度图4 (d):决定论阻止运行时学习任务1和任务2中哪一个先完成。由于无法获得用于通知用户级调度决策的时间信息，因此建议将调度留给在确定性环境(例如:“让- j”而不是“j2”）.
4.2.共享文件系统
Unix的文件系统提供了方便的命名空间和存储库，用于暂存程序输入、存储输出和保存中间结果(如临时文件)。因为我们的内核不允许物理状态共享，所以用户级代码必须模拟共享状态抽象。Determinator的“无共享”空间层次结构类似于仅由单处理器机器组成的分布式系统，因此我们的用户级运行时借鉴了分布式文件系统原则，为应用程序提供了共享文件系统抽象。
由于我们当前的重点是模拟熟悉的抽象，而不是开发存储系统，因此目前Determinator的文件系统不提供持久性:它实际上只充当临时文件系统。
我们的运行时模拟了一个弱一致性的复制文件系统，24通过在每个进程的地址空间中维护一个完整的文件系统副本，如图5．当一个进程通过fork ()，子文件系统除了继承父文件的打开文件描述符外，还继承父文件系统的一个副本。个人打开/关闭/读/写进程中的操作只使用该进程的文件系统副本，因此当不同进程的副本同时修改文件时，它们可能会产生分歧。当一个子进程终止，而它的父进程通过wait ()，父进程的运行时使用文件版本控制将子进程的更改传播到父进程。
如果一个平行使fork多个编译器进程，例如，每个子进程写入其输出．o文件到它自己的文件系统副本。父类的运行时合并这些．o作为父文件系统的文件wait ()S在每个子结点上。由于内核的写时复制优化，这种复制和协调并不像看起来那样低效。在许多空间中复制文件系统映像不会复制物理页面，直到用户级代码修改它们，因此相同文件的所有副本只使用一组页面。
在任何弱一致性的文件系统中，对同一个文件执行非同步的并发写操作可能会导致冲突．当我们的运行时检测到一个冲突，它简单地丢弃一个副本，并在文件上设置一个冲突标志;后来的努力open ()该文件导致错误。此行为适用于冲突表明存在错误的批计算应用程序，其解决方案是修复错误并重新运行作业。交互式使用需要一种避免数据丢失的策略。用户级运行时可以实现更强的一致性，并以更高的同步成本避免非同步的并发写入。
4.3.输入/输出和日志记录
由于非特权空间只能通过空间层次结构中的父/子交互间接地访问外部I/O设备，所以我们的用户级运行时将I/O视为文件系统同步的特殊情况。除了常规文件外，进程的文件系统还包含特殊文件I / O文件，例如控制台输入和输出文件。与Unix设备特殊文件不同，Determinator的I/O文件实际上保存了进程文件系统映像中的数据:例如，控制台输入文件积累了进程从控制台接收到的所有字符，而控制台输出文件保存了写入控制台的所有字符。在当前的原型中，控制台或日志文件最终可能会“填满”并变得不可用，尽管合适的垃圾收集机制可以解决这个缺陷。
当进程执行控制台时read ()时，C库首先返回进程本地控制台输入文件中已经存在的未读数据。当没有更多的数据可用时，进程不会返回文件结束条件，而是调用Ret与其父进程同步，等待更多的控制台输入(或原则上任何其他形式的新输入)可用。当父进程执行wait ()或者以其他方式与子进程同步，它将任何新输入传播给子进程。当父进程没有任何正在等待的子进程的新输入时，它将所有子进程的输入请求转发给父进程，并最终通过根进程发送给内核。
当进程执行控制台时write ()，运行时将新数据追加到其内部控制台输出文件，就像追加到常规文件一样。下一次进程与父进程同步时，文件系统协调将这些写操作传播到根进程，根进程将它们转发到内核的I/O设备。进程可以通过显式调用请求立即输出传播fsync ()．
和解处理“仅追加”写入与其他写入不同，使对控制台或日志文件的并发写入不会产生冲突。在和解过程中，如果父进程和子进程都对同一个文件进行了仅追加写操作，则和解将子进程的最新写操作追加到父进程的文件副本中，反之亦然。因此，每个进程的副本积累了所有进程的并发写操作，尽管不同的进程可能会以不同的顺序观察这些写操作。与Unix不同，从相同的输入重新运行并行计算，无论是否使用输出重定向，都会产生逐字节相同的控制台和日志文件输出。
4.4.共享内存多线程
尽管存在非确定性，但共享内存多线程仍然很受欢迎，部分原因是并行代码不需要打包和解包消息:线程只是在共享变量和结构上“就地”计算。由于Determinator除了通过写时复制的只读共享之外，并没有为用户空间提供物理上的共享内存，因此模拟共享内存涉及到分布式共享内存技术。将第2.2节的私有工作区模型调整为线程级共享内存重用了早期并行Fortran机器的思想6和发布一致的DSM系统，1虽然这些先前的设计不提供决定论。
我们的运行时使用内核的Snap和Merge操作(章节3.2)来模拟私有工作区模型中的共享内存，使用fork/join同步。要派生一个子线程，父线程调用带有Copy、Snap、Regs和Start选项的Put来将其内存的共享部分复制到子空间中，在子空间中保存该内存状态的快照，并启动子空间运行，如图所示图6．主线程可以通过这种方式派生出多个子线程。为了与子进程同步并收集其结果，父进程调用带有Merge选项的Get，该选项将子进程对共享内存所做的所有更改合并回父进程，因为它的快照已经被捕获。如果父进程和子进程，或者父进程收集的子进程和其他子进程在快照之后并发地修改了相同的字节，内核会检测并报告这个冲突。
我们的运行时还支持障碍，这是OpenMP等数据并行编程模型的基础。23当组中的每个线程到达一个屏障时，它调用Ret停止并等待管理组的父线程。父线程在barrier之前调用Get with Merge来收集每个子线程的更改，然后调用Put with Copy和Snap来用一个包含所有线程之前结果的新共享内存快照恢复每个子线程。虽然私有工作空间模型在概念上扩展到非层次同步，3.我们的原型严格的空间层次结构目前限制了同步的灵活性，我们打算在未来解决这个问题。任何但是，如下一节所述，模拟同步抽象可能需要一些成本。
应用程序可以选择其地址空间的哪些部分共享，哪些部分保持线程私有。通过将线程堆栈放置在共享区域之外，所有线程都可以重用相同的堆栈区域，内核不会浪费任何精力来合并堆栈数据。线程私有堆栈使子线程能够继承父线程的堆栈，并在与父线程相同的C/ c++函数中“内联”运行，如图1．但是，如果线程希望向堆栈分配的结构传递指针，那么它们可能会将堆栈定位在不相交的共享区域。类似地，如果文件系统区域是共享的，那么线程就像在Unix中一样共享一个公共的文件描述符名称空间。将文件系统区域排除在共享空间之外，并使用普通的文件系统协调(章节4.2)来同步它，将产生线程私有的文件表。
4.5.模拟遗留线程api
对于已经使用非确定性同步并行化的遗留代码，Determinator的运行时可以通过确定性调度模拟标准的pthreads API。8在这种情况下，过程是初始的掌握空间永远不要直接运行应用程序代码，而是充当调度程序，监督每个应用程序线程的一个子空间。调度器使用内核的指令限制特性(章节3.2)来数字转换每个线程的执行。在允许每个线程独立运行一个量子之后，调度器使用Merge来收集线程的共享内存更改，然后从合并状态重新启动另一个量子的线程。
要模拟pthreads同步，线程可以提前结束其量子，以便与调度器交互。例如，无论互斥锁是否被锁定，每个互斥锁总是有一个“所有者”线程。所有者可以在没有调度器交互的情况下锁定和解锁互斥锁，但是需要互斥锁的另一个线程必须调用调度器来获得所有权。在当前所有者的下一个量程中，如果互斥锁被解锁，调度器“窃取”互斥锁的所有权，否则将锁线程放在互斥锁的队列上，一旦互斥锁可用，就会被唤醒。
虽然确定性调度提供了与遗留代码的兼容性，但它也有缺点。除非执行量程很大，否则序列化同步操作所需的主空间可能会限制可伸缩性。然而，大量程可能会增加线程等待与另一个线程交互的时间浪费，例如窃取一个未锁定的互斥锁。
此外，由于确定性调度器可能抢占线程并在应用程序代码中的任何点传播共享内存更改，因此编程模型仍然是不确定的。与我们的私有工作区模型相比，如果一个线程运行x＝y“另一个人在跑”y＝x“在确定性调度器下，结果可能是可重复的，但对程序员来说并不比以前更可预测。重新运行程序时使用完全相同的输入将产生相同的结果，如果输入更改或代码重新编译影响任何指令序列的长度，这种更改可能会级联到不同的执行时间表，并触发与时间表相关(如果不是与时间相关)的错误。
5.评价
本节首先非正式地评估Determinator原型，然后分析单节点和分布式并行处理的性能，最后是代码的大小。
Determinator是用C语言编写的，带有小的汇编片段，目前运行在32位的x86架构上。由于我们的重点是并行计算绑定的应用程序，Determinator的I/O能力目前仅限于基于文本的控制台I/O和一个简单的基于以太网的空间迁移协议(章节3.3)。该原型没有持久的磁盘存储:运行时的共享文件系统抽象目前仅在物理内存中运行。
5.1.系统使用经验
我们发现确定性编程模型简化了应用程序和用户级运行时代码的调试，因为用户空间的错误总是可重现的。相反，当我们确实观察到不确定行为时，它只能由内核(或硬件)bug导致，立即限制了搜索空间。
因为Determinator的文件系统保存一个进程的输出，直到下一次同步事件发生(通常是进程的终止)，所以即使该进程与其他生成输出的进程并行执行，每个进程的输出也会作为一个单元出现。此外，不同进程的输出在运行期间以一致的顺序出现，就像按顺序运行一样。
虽然种族检测工具存在，21我们发现，在“正常情况”执行下，Determinator检测冲突是很方便的，不需要特殊的工具。决定者模型使冲突检测成为标准的检测除以零或非法内存访问。
Determinator的子集加倍为警务信息员“并行教学操作系统”，在过去两年的耶鲁操作系统课程中使用。14虽然确定性不是一个主要的课程主题，但我们发现，由于Determinator/PIOS的简单设计和最小的内核API，它是多核时代操作系统教学的一个有用的工具。部分源自JOS并受到其启发，17PIOS包括一个教学框架，学生可以在其中填充“框架”的缺失部分。学生们以小组为单位重新实现所有Determinator的核心特性:多处理器调度、带有写时复制和Snap/Merge的虚拟内存、带有fork/join的用户级线程、带有版本控制和协调的用户空间文件系统，以及跨节点空间迁移。在他们的最终项目中，学生们使用图形、管道和远程shell等特性来扩展操作系统。这门课程很有挑战性，而且会带来沉重的编程负担，但匿名的学生评价由于其教育价值和感知的相关性而高度积极。
5.2.单节点多核性能
由于Determinator在硬件上“本地”运行用户级代码，而不是重写用户代码，8当运行粗粒度并行代码时，它的性能与现有系统相当，但是由于同步事件所需的系统调用、上下文切换和虚拟内存操作，它在细粒度并行代码上的成本更高。
图7展示了几个共享内存并行基准测试在Determinator上的性能，相对于在32位Ubuntu Linux 9.10上使用标准pthread进行的相同基准测试。粗粒度的基准Md5, matmult, qsort, blackscholes,fft执行类似于Linux下的非确定性执行，而细粒度陆基准测试显示了更高的性能成本。
图8显示了每个基准测试相对于在Determinator上单线程执行的速度提升。“高度平行”md5而且blackscholes具有良好的伸缩性,matmult而且fft在4个处理器之后趋于平稳(但仍然可以与Linux相比)，其余的基准测试扩展性很差。
5.3.分布式计算性能
为了评估跨节点空间迁移(第3.3节)，我们更改了md5而且matmult在保留Determinator的共享内存编程模型的同时，可以进行基准测试，将工作负载分布在最多32个单处理器节点上。由于缺乏适合本地测试的集群，我们在QEMU下运行Determinator，5在共享使用的Linux集群上。
图9在对数-对数尺度上显示了在Determinator中并行执行与单节点执行的对比。的md5-circuit基准测试串行迁移到fork工作线程的每个节点并收集结果md5-tree而且matmult-tree在二叉树结构中递归地Fork和join工人。“高度平行”md5-tree通过递归工作分配，可以很好地执行和扩展，同时matmult-tree承受使用Determinator的未优化的页面复制协议进行大型跨节点数据传输的代价。
作为图10显示，在Determinator上的共享内存基准测试的性能与在Linux上运行的不确定的分布式内存等量测试的性能相当。的Determinator版本的共享内存API的好处md5是Linux版本的63%(62行对99行)，Linux版本使用远程shell来协调工作人员。限定词的matmult是Linux版本的34%(90行vs 263行)，Linux版本使用TCP传递数据。
5.4.实现的复杂性
为了让大家了解实现的复杂性，表2显示了Determinator的源代码行数，以及它的PIOS指令子集，只计算包含分号的行。整个系统不到15,000行，其中大约一半是通用的C和数学库代码，主要用于方便地移植Unix应用程序。
6.结论
虽然Determinator只是一个概念的证明，但它表明操作系统可以提供一个普遍的、自然确定的环境。确定器避免在共享内存和文件系统访问、线程和进程同步以及整个API中引入数据竞争。实验表明，这样的环境可以高效地在多核机器上和跨集群运行粗粒度并行应用程序，尽管高效地运行细粒度应用程序可能需要硬件的改进。
致谢
我们感谢Zhong Shao、Ramakrishna Gummadi、Frans Kaashoek、Nickolai Zeldovich、Sam King和OSDI评审员的宝贵反馈。我们感谢ONR和NSF在N00014-09-10757和CNS-1017206赠款下的支持。
参考文献
1.Amza, C.等人。在工作站网络上的共享内存计算。IEEE计算机29， 2(1996年2月)，1828年。
2.Artho, C.， Havelund, K.， Biere, A.高水平数据竞赛。在企业资讯系统验证及验证工作坊(2003年4月),8293年。
3.张宇，张志强，张志强，张志强，张志强，张志强。工作空间一致性:一种共享内存并行性的编程模型。在第2届并行编程决定论与正确性研讨会(2011年3月)。
4.Aviram, A.， Hu, S.， Ford, B.， Gummadi, R.确定计算云中的定时通道。在ACM云计算安全研讨会(CCSW)(2010年10月)。
5.QEMU，一款快速便携的动态翻译软件USENIX年度技术会议加州阿纳海姆，2005年4月1015日。
6.刘志强，刘志强，刘志强。米里亚斯并行计算机系统的控制机制。第一版。架构师。新闻16， 4(1988年9月)，2130。
7.贝伦森等人。对ANSI SQL隔离级别的批评。在SIGMOD(1995年6月)。
8.Bergan, T.等。用于确定性多线程执行的编译器和运行时系统。在第15届编程语言与操作系统架构支持国际会议(ASPLOS)(2010年3月)。
9.Bergan, T.等。dOS中的确定性进程组。在第九届USENIX操作系统设计与实现研讨会(OSDI)(2010年10月)。
10.Boyd-Wickizer等人。科里:多核操作系统。在第八届USENIX操作系统设计与实现研讨会(OSDI)(2008年12月)。
11.卡斯特罗，M.，利斯科夫，B.实用的拜占庭容错。在第三届USENIX操作系统设计与实现研讨会(OSDI)(1999年2月),173186年。
12.邓拉普，G.W.等人。ReVirt:通过虚拟机日志和回放来启用入侵分析。在第五届USENIX操作系统设计与实现研讨会(2002年12月)。
13.邓拉普，G.W.等人。多处理器虚拟机的执行回放。在虚拟执行环境(VEE)(2008年3月)。
14.PIOS:并行教学操作系统，2010。http://zoo.cs.yale.edu/classes/cs422/pios．
15.Git:快速版本控制系统。http://git-scm.com/．
16.Haeberlen, A.， Kouznetsov, P.， Druschel, P. PeerReview:分布式系统的实际责任。在第21届ACM操作系统原理研讨会(SOSP)(2007年10月)。
17.Kaashoek, F.等人，6.828:操作系统工程。http://pdos.csail.mit.edu/6.828/．
18.一种简单的并行编程语言的语义"，在信息处理'74:IFIP大会论文集(1974),页471475。
19.Leblanc, t.j.， Mellor-Crummey, J.M.用即时重播调试并行程序。IEEE反式。第一版。C-36， 4(1987年4月)，471482。
20.李，e。线程的问题。电脑,39， 5(2006年5月)，3342
21.Musuvathi, M.等。并发程序中海森堡的发现与再现。在第八届USENIX操作系统设计与实现研讨会(OSDI)(伯克利，加州，美国，2008)，USENIX协会。
22.Olszewski, M.， Ansel, J.， Amarasinghe, S. Kendo:软件中的高效确定性多线程。在第14届编程语言与操作系统体系结构支持国际会议(2009年3月)。
23.OpenMP架构审查委员会。OpenMP应用程序接口3.0版，2008年5月。
24.帕克，小D.S.等人。分布式系统中相互不一致的检测。IEEE反式。软件中。SE-9， 3(1983年5月)。
25.魏军，蒲春梅，蒲春梅。unix风格文件系统中的TOCTTOU漏洞:一种解剖学研究。在第四届USENIX文件与存储技术会议(FAST)(2005年12月)。
数据
图1。用于锁步时间模拟的C伪代码，它在标准并发模型中包含数据竞争，但在Determinator下没有bug。
图2。的内核层次结构空间，每个包含私有寄存器和虚拟内存状态。
图4。平行使在unix和Determinator下:(a)和(b)具有无限并行度;(c)及(d)在用户级别设置2名工人的配额。
图5。每个进程维护共享文件系统的私有副本，使用文件版本控制在同步点协调副本。
图6。一个多线程进程，每个线程一个空间，主空间管理同步和内存协调。
图7。在使用并行基准测试的Linux下，确定相对于pthread的性能。
©2012 acm 0001-0782/12/0500 $10.00
如果您不是为了盈利或商业利益而制作或分发本作品的部分或全部，并在第一页注明本通知和完整引用，则允许您免费制作本作品的部分或全部数字或纸质副本，供个人或课堂使用。本作品的组成部分必须由ACM以外的其他人享有版权。信用文摘是允许的。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定的许可和/或费用。请求发布的权限permissions@acm.org或传真(212)869-0481。
数字图书馆是由计算机协会出版的。版权所有©2012 ACM股份有限公司
没有发现记录