操作系统随机自动机网络模型：基于性能评估和可靠性分析的研究

理论计算机科学电子笔记151（2006）131-149www.elsevier.com/locate/entcsNUMA Systems1R af aelCh a n i n 2MpacionicaCorrpacionea 3PauloFernandes 4Afonso Sales 5Roque Scheer 6 Avelino F. Zorzo7FaculdadedeInform'aticaPontif′ciaUniversidade Cato′licadoRioGrandedoSulPortoAlegre，Brazil摘要通过基准测试进行性能评估是衡量计算机系统性能的主要方法之一。然而，在系统的各个部分实现之前对其进行测量是很重要的。这可以通过对系统的分析性描述来实现，从而允许对系统性能进行分析。此外，分析模型可以扩展到考虑可靠性问题。 本文提出了一种基于随机自动机的操作系统调度器的通用模型网络（SAN）形式主义。SAN用于描述操作系统中的进程和处理器，以及当进程必须迁移时它们的行为。此外，处理器故障也被建模，以提供可靠性指标。该模型使用从4处理器的Itanium 2 SMP机器和12处理器的Itanium 2 NUMA机器获得的实际基准测试结果。关键词：效能评估、分析模型、随机自动机网路、作业系统排程。1介绍即使在网格和集群的最新进展，大型共享内存计算机仍然需要解决一些计算问题和运行某些应用程序。这些应用程序需要可扩展的操作系统来为它们提供一个可以处理所有计算需求的环境。通常，这种并行系统的性能是通过基准测试来衡量的主要1这项工作是与Hewlett-Packard Brazil R D合作开发的。2电子邮件：chanin@inf.pucrs.br3电子邮件：mcorrea@inf.pucrs.br4电子邮件：paulof@inf.pucrs.br（通讯作者。 由CNPq/巴西提供支持。5电子邮件：asales@inf.pucrs.br6电子邮件：roque. hp.com（Roque Scheer就职于惠普巴西研发部）7电子邮件：zorzo@inf.pucrs.br（由CNPq/Brazil提供支持）。1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.03.016132R. Chanin等人理论计算机科学电子笔记151（2006）131基准测试的概念涉及到运行一组计算机程序来测量机器的性能。已经开发了几个基准来测量计算机系统的不同功能。通常，基准测试可以同时测量机器和系统的特性 。 基 准 测 试 的 例 子 有 AIM Multiuser Benchmark - Suite VII [1] 、 LMBench[18] 、 SPEC Benchmark Suite [24] 、 NAS Parallel Benchmark [9] 和 LINPACKBenchmark [8]。基准点的选择取决于人们想要在系统或机器上评估的功能。尽管基准测试是一种非常有说服力的测量实际系统的方法，但基准测试和其他监控技术作为分析工具往往过于灵活。在几种情况下，修改系统配置并检查系统行为是否发生变化是很重要的实际的重新配置可能非常困难，大多数情况下，获得的结果并没有明确显示出优势，以证明所花费的所有努力是合理的。这个问题的一个解决方案是产生一个（理论）模型的系统评估和分析可能的配置。Markovian建模者经常使用简单模型来描述被评估系统的小部分[25，14]。另一个有效的选择是使用高级形式主义，例如网络[11，12]，它可以提供有关性能的见解，但有时它假设太不切实际的行为，例如。，无限排队。另一种可能的解决方案是使用结构化的形式主义[22，6，10，13]来描述系统的各个部分，然后将这些部分组合成完整的系统模型。此外，使用分析模型可以验证其他类型的指数，通常是可执行性指数[19]，例如：与故障的存在对系统性能的影响有关的指标性能和可靠性指标可以由不同的模型和工具产生。 在本文中，我们使用随机自动机网络（SAN）[21]形式主义来描述一些Linux操作系统算法的性能和可靠性指标。然而，任何其他形式主义，例如，、随机活动网络（SAN）[22]、进程代数[13]和随机Petri网（SPN）[6]。在对具有多个并行活动的系统进行建模时，SAN形式主义通常非常有吸引力。同样重要的是要注意，SAN提供了有效的数值算法来计算静态和瞬态测量[10，2]，利用结构化和模块化定义。以这种方式，SAN形式主义允许相当大的模型的解决方案，即，，拥有超过几百万个状态的模型本文展示了如何为NUMA（非均匀内存访问）机器建模Linux操作系统的各个部分。我们提出了一个SAN模型，从中可以提取的Linux调度算法的某些部分的性能和可靠性指标由于考虑NUMA机器中所有可能的进程和处理器的模型太大，我们将所有进程的行为概括为多处理器机器中单个进程的行为该通用模型考虑了操作系统中处理器故障、进程迁移和进程调度的可能性。此外，这种通用模型R. Chanin等人理论计算机科学电子笔记151（2006）131133根据所需的性能和可靠性指标进行简化本文的其余部分组织如下。在第二节中，我们简要地介绍了随机自动机网络的形式。第3节描述NUMA机器的Linux调度和负载平衡算法的行为。在第4节中，我们提出了这些算法的SAN模型，在第5节中，我们提出了从我们提出的模型得到的数值结果最后，第6节评估了未来的工作，并强调了本文的主要贡献2随机自动机网络SAN形式主义由Plateau [20]提出，其基本思想是通过具有独立行为（局部转换）和偶尔相互依赖性（功能速率和同步事件）的子系统的集合来表示整个系统。Plateau提出的框架定义了一种描述连续和离散时间马尔可夫模型的模块化方法[21]。然而，只有连续时间的SAN将在本文中考虑，虽然离散时间的SAN也可以采用不失任何一般性。SAN形式主义将完整的系统描述为相互交互的子系统的集合。每个子系统被描述为一个随机自动机，即。一种自动机，其中的转换标记有概率和定时信息。因此，我们可以建立一个连续时间随机过程相关的SAN，即。，SAN形式主义与马尔可夫链（MC）形式主义具有完全相同的应用范围[23，5]。SAN模型的状态，称为全局状态，由所有自动机的局部状态的有两种类型的事件可以更改模型的全局状态：本地事件和同步事件。本地事件将SAN全局状态从一个全局状态更改为另一个仅由一个本地状态区分的全局状态。另一方面，同步事件可以同时改变多于一个本地状态，即，两个或多个自动机可以同时改变它们的局部状态。换句话说，同步事件的发生迫使所有相关的自动机触发对应于该事件的转换。实际上，本地事件可以被看作是同步事件的一个特殊情况，只涉及一个自动机。每个事件都由标识符和发生率表示，它描述了给定事件发生的频率每个转换可以作为任何数量的事件发生的结果而被触发一般来说，可能的不同事件之间的非确定性（概率选择）是根据马尔可夫行为来处理的，即。，任何事件都可能发生，其发生率定义了每个事件发生的频率。然而，从一个给定的本地状态，如果一个给定的事件的发生可能会导致一个以上的状态，那么一个额外的路由概率必须提供。如果给定局部状态的事件只能触发一个转换，则可以容忍路由概率的缺失自动机之间相互作用的另一种可能性是使用功能速率。任何事件的发生率都可以用一个常数值（正实数）或其他自动机状态的函数来与Syn相反134R. Chanin等人理论计算机科学电子笔记151（2006）1310（1第一计时事件，功能速率是自动机之间的单向交互，因为它只影响它出现的自动机图1提出了一个SAN模型，其中包含两个自动机、四个本地事件、一个同步事件和一个功能速率。在图1的SAN模型1，事件速率e1不是恒定速率，而是由PEPS软件工具[3]采用的SAN符号描述的函数速率fe1函数的解释可以是被视为非类型化编程语言的表达式的求值，例如，C语言。每次比较的结果都是值1（true）或值0（false）。A类（1）A类（2）e2e1e3- 是的ΣΣ- 是的ΣΣf e1 =标准A（2）==0（2）λ+stA（2）==2（2）γFig. 1. SAN模型函数表达式的使用不限于事件速率。事实上，路由概率也可以表示为函数。函数的使用是SAN的一个强大的基础，因为它允许以非常紧凑的格式描述非常复杂的行为。随着SAN模型数值解的发展，处理功能速率的计算成本显著降低，例如：，广义张量积的算法[3]。3NUMA OS具有共享资源的系统需要实现一些策略来定义谁可以使用特定的资源。在操作系统中，进程调度器负责管理进程共享的所有系统处理器的使用。在过去的几年里，人们对单处理机上的排序问题进行了深入的研究。然而，在多处理器机器调度仍然提出了一些挑战。通常，共享内存多处理器机器可以分为对称多处理器（SMP）或非均匀内存访问（NUMA）[15]。SMP机器是多处理器系统，其中每个处理器在恒定时间内访问任何NUMA系统是以节点组织的多处理器系统。图2显示了一个8处理器的NUMA机器，它被组织成四个节点。节点1存储器CPU 1 CPU 2节点2存储器CPU 3 CPU 4节点3存储器CPU 5 CPU 6节点4存储器CPU 7 CPU 8图二. NUMA机每个节点都有一组处理器和部分主存。的距离0（2e4e2（π1）e2（π2）e5第二章第一类型事件发生率位置1fe1syne2μ位置3σ位置4δ位置5τR. Chanin等人理论计算机科学电子笔记151（2006）131135节点之间的内存区域是不一样的，因此从每个处理器到不同的内存区域有不同的访问时间。3.1Linux调度器Linux是为并行机实现调度算法的操作系统之一。从2.5版本开始，Linux调度器被称为O（1）调度器，因为它的所有例程都在恒定时间内执行，无论有多少处理器存在[17]。Linux调度程序的当前版本（内核版本2.6.11）为SMP和NUMA架构带来了许多改进。Linux调度程序是抢占式的，并与动态优先级队列一起工作。系统根据进程CPU利用率计算进程优先级。I/O绑定进程的大部分时间都在等待I/O请求，它的优先级高于CPU绑定进程的优先级，CPU绑定进程的大部分时间都在运行。由于I/O绑定的进程通常是交互式的，因此它们需要快速的响应时间，因此具有更高的优先级。CPU受限的进程运行频率较低，但运行时间较长。优先级是动态的;它根据进程行为而变化。进程时间片也是动态的，并根据进程优先级确定进程优先级越高，进程时间片就越高。虽然Linux以前的版本在整个系统中只有一个进程队列，但当前的O（1）调度程序为每个处理器保留一个进程队列（称为runqueue）。因此，如果一个进程被插入到一个特定处理器的运行队列中，它将只在该处理器上运行。这个属性叫做处理器的独立性。由于进程在同一个处理器中持续运行，因此该进程的数据可以在缓存中，因此系统不需要从主内存中检索这些数据，这显然是一个优势。由于访问高速缓冲存储器比访问主存储器更快每个运行队列包含两个优先级数组：active和expired。优先级数组是由一个优先级位图和一个数组组成的数据结构，该数组包含每个优先级的一个进程队列。优先级位图用于在运行队列中有效地找到最高优先级的进程。每个优先级都有一个位。当存在至少一个给定优先级的进程时，位图中的相应位被设置为值1。然后，调度程序通过在位图中搜索第一个等于值1的位来选择要运行的新进程，该位表示运行队列的最高优先级，并在队列中找到具有该优先级的第一个进程。图3描述了该算法的一部分[17]。每个运行队列有两个指向优先级数组的指针。当活动数组为空时，指针被切换：过期的数组成为活动数组，反之亦然。该操作的主要优点是避免将所有进程移动到活动优先级数组;在恒定时间内执行;并保持调度算法的O（1）复杂度。当一个进程完成它的时间片时，它的优先级和时间片被重新计算，并被移动到过期的优先级数组中。只有当活动数组为空时，也就是说，当运行队列的所有进程都完成了它们的时间片时，这个进程才会再次运行。136R. Chanin等人理论计算机科学电子笔记151（2006）131节点域CPU域1CPU域2CPU域3CPU域4CPU：8CPU：7CPU：6CPU：5CPU：4CPU：3个CPU：2CPU：1CPU：7、8CPU：5、6CPU：3、4CPU：1，2schedule（）位0（优先级0）sched_find_first_set（）位7（优先级7）按优先级列出位139（优先级139）140位优先级位图运行列表优先级7图三. 选择要运行当一个进程被创建时，它被插入到同一个运行队列中，并具有与其父进程相同的优先级。父进程的时间片在新进程和其父进程之间平分。然而，总是在同一个运行队列中插入新的进程会使处理器过载，而系统中的其他处理器可能是空闲的，或者有较少的进程要执行。这不是一个理想的场景，因为它增加了进程的平均执行时间为了避免这种情况，Linux调度程序实现了负载平衡算法。该算法试图保持系统的负载公平地分布在处理器之间。为了实现这个目标，Linux负载均衡器将进程从一个过载的处理器迁移到另一个需要执行较少进程的处理器。在SMP系统中，选择将进程从过载处理器迁移到空闲处理器不会引起任何主要的副作用。由于所有处理器和内存之间的距离是相同的，因此将进程从任何处理器迁移到另一个处理器不会影响进程的整体性能这在NUMA机器中不会发生;从同一节点中的处理器迁移进程比从另一个节点中的处理器迁移进程要好。如前所述，这是由于不同节点中的处理器之间的内存距离不同Linux负载平衡算法使用一种称为sched domain的数据结构来执行负载平衡[4]。基本上，sched域包含CPU组，这些CPU组定义了该域的负载平衡范围sched域是分层组织的，试图表示系统的拓扑结构。图4示出了由Linux创建到图1的NUMA机器的调度域二、见图4。 NUMA计算机的计划域最低层的域表示系统的节点。这些域称为CPU域，因为进程只能在CPU之间迁移，而不能在节点之间迁移。CPU域中的每个CPU组仅由一个CPU组成。更高级别的域代表整个系统，称为节点域R. Chanin等人理论计算机科学电子笔记151（2006）131137因为进程可以在节点之间移动。在节点域中，每个CPU组代表一个节点，因此由该节点的所有CPU组成通常，Linux O（1）调度器试图通过在三种不同的情况下将进程重新分配给处理器来尽可能地保持所有处理器的负载平衡：（i）当处理器空闲时;（ii）当进程执行exec或克隆系统调用时;（iii）定期地以针对每个sched域定义的特定间隔进行。当一个处理器空闲时，调用负载均衡器将进程从另一个处理器迁移到空闲的处理器。通常只有CPU域接受此事件的负载平衡，以便将进程保持在同一节点中，并更接近分配给它的内存。当进程执行exec或克隆系统调用时，可以为节点域执行负载平衡，因为需要为克隆进程创建新的内存映像，并且可以在新节点上分配该映像。由于空闲处理器事件通常仅在节点级别触发负载平衡，并且可能不会很快调用exec或clone在该周期性负载平衡中，在每个重新平衡刻度，系统检查是否应该在包含当前处理器的每个调度域中执行负载平衡，从最低域级别开始。负载平衡在特定调度域的处理器之间执行。由于负载平衡必须在特定的处理器上执行，因此平衡将在包含此处理器的sched域负载均衡器的第一个动作是确定当前域中最繁忙的处理器（从最低级别开始访问所有域），并验证它是否相对于当前处理器过载。选择要迁移的进程很简单。来自过期优先级阵列的进程是优选的，并且根据三个标准被移动：（i）进程不应该正在运行;（ii）进程不应该是高速缓存热的;以及(iii)该过程不应具有处理器冗余性。这种负载平衡算法是O（1）调度器的一部分，其目标是尽可能保持所有处理器的负载平衡，最小化进程执行的平均4该模型基准测试的使用对于测量复杂系统中的特性非常有用，例如：Linux调度算法。然而，如前所述，修改这样的系统以便再次检查它们并意识到所有的电子邮件都被浪费了，这可能是相反，分析建模可以用来描述和评估这些系统，只有当系统的新修改被预测为比以前的更好时，才能实现实际的实施在本节中，我们将描述如何使用SAN形式化来对Linux调度算法进行建模SAN所允许的模块化方法对于138R. Chanin等人理论计算机科学电子笔记151（2006）131由于它的并行行为，模型这样的系统。我们的方法的主要思想是在Linux系统中只对一个进程的行为进行建模，但要考虑其他进程的影响。我们提出了一个由P（i）个处理机和一个进程组成的系统模型。4.1过程图5显示了双处理器计算机中进程的SAN模型及其转换速率表。表1显示了所有可能改变自动机状态的事件事件描述锡奥伊进程将执行一个I/O操作菲奥岛进程已完成其I/O操作，并已移至第i个处理器中的就绪队列塞伊进程已在第i个处理器中调度FTSI进程在第i个处理器中完成了它的时间片Ri进程已经费伊这一过程已经完成伊季姆佩进程在第i个处理器的过期队列中，通过周期性负载平衡将其迁移到第j个米埃杰进程在第i个处理器的过期队列中，通过空闲负载平衡被迁移到第j个国际正义运动进程在第i个处理器的就绪队列中，通过周期性负载平衡将其迁移到第j个米尔伊季进程在第i个处理器的就绪队列中，通过空闲负载平衡被迁移到第j个EPI第i个处理器出现故障莫妮卡其他进程已通过空闲负载平衡迁移SPI将执行周期性负载平衡FPI已执行周期性负载平衡，但未执行检查进程IDI调度程序无法找到要调度的进程锡我调度器算法选择了另一个进程来执行民族阵线某个其他进程完成了它的时间片或它的执行表1所有可能的自动机事件进程自动机由以下状态组成：R（i）表示进程在第i个处理器的就绪队列中（等待调度）; Ep（i）表示进程在第i个处理器的过期队列中（它已经完成了它的时间片，并等待被“移动”到就绪队列）; Ex（i）表示进程在相应处理器中执行的情况; IO（i）表示进程正在等待输入/输出操作的情况; En表示进程已经完成了它的执行，它不再是系统的一部分。值得注意的是，图5显示了具有两个处理器（P（1）和P（2））的计算机中的进程行为。这样做是为了简化图中状态的数量;为了表示更多数量的处理器，有必要复制状态R（i），IO（i），Ex（i）和Ep（i）及其相应的R. Chanin等人理论计算机科学电子笔记151（2006）131139P（1）P（2）过程IO（1）FIO1SiO1R（1se1前（1）R1mpe21FTS1Ep（1）Fe1和平号21mir12mpr21Enmpe12 mie12R2中文（简的fe2FTS2SE2R（2前（2）FIO2的sio2IO（2）类型 事件率类型 事件率同步同步syn硅 1硅2英尺 1英尺2mpe12mpe21mie12mie21se1SE2rsio1rsio2rfts1rfts2rmpe12rmpe21rmie12rmie21rse 1rse2synsynsynsynsynlocklocklocklocfe1fe2mpr12mpr21mir12mir21fio1fio2r1R2rfe1rfe2rmpr12rmpr21rmir12rmir21rfio1rfio2rr 1rr2图五. 自动机过程及其事件转换表示在流程生存期内可能发生的事件例如，从Ex（i）到Ep（i）的转换意味着进程已经完成执行其时间片，并将存储在过期队列中。某些转换表示正在执行的负载平衡算法。例如，从Ep（1）或R（1）到R（2）的转换表示该进程位于来自处理器1的队列之一中，并且负载均衡器选择将该进程移动到处理器2的就绪这种移动表示处理器1相对于处理器2不平衡。第3节描述了负载均衡器的工作方式。一个重要的注意事项是，我们的方法允许不同类型的进程配置;例如，如果我们想分析I/O绑定进程的行为，只需要适当地调整速率。在这种情况下，从Ex（i）到IO（i）的转换速率将高于从Ex（i）到Ep（i）的转换速率，因为进程将执行更多的I/O操作。由于I/O受限进程接收比CPU受限进程更高的优先级，因此从R（i）到Ex（i）的转换速率也将增加。除了进程类型（I/O绑定和CPU绑定）之外，还可以定义其他进程特征，例如：、进程优先级、进程执行时间等。如前所述，每个集合R（i）、Ex（i）、Ep（i）和IO（i）都包含在系统中的每个处理器中。有必要为每个处理器建模一个IO（i）状态，即使它们表示完全相同的情况。如果进程自动机只有一个全局IO状态，那么当I/O操作结束时，就不可能知道进程应该插入哪个处理器队列。4.2处理器图6显示了使用SAN的建模处理器和相应的转换速率表。处理器可能处于以下状态之一：140R. Chanin等人理论计算机科学电子笔记151（2006）131额（1）ep1ep1EP1ep1PB（1）EP中文（简1mpr21mpe21SP1Sn1fn1ID1FP1IB（1）中文se1FTS1SiO1Fe1前（1）mie21moN1mir 21P（1）P（2）Σ Σfid =（st进程！= R（1））&&（st过程！= Ep（1））文件ID1Σ Σ1fid =（st进程！= R（2））&&（st过程！= Ep（2））文件ID2 2见图6。 处理器自动机及其事件处理器未被使用并且它正在执行负载平衡算法;Sc（i）表示处理器正在执行调度算法;PB（i）表示处理器正在执行周期性负载平衡算法;EN（i）表示处理器正在执行任何其它进程;Ex（i）表示处理器正在执行图5所示的进程;Er（i）表示发生了某个错误并且处理器不工作。重要的是要记住，当我们描述NUMA机器中的系统时，每个节点的内存延迟是不同的在我们的模型中，内存延迟由事件率fe表示，并且对于每个建模的处理器，它可以是不同的。这允许使用不同的内存延迟值来评估系统。例如，将进程从一个节点迁移到另一个节点将导致进程具有不同的内存访问时间。这对于检查迁移过程是否可以提高系统性能非常重要。如果一个处理器空闲而另一个处理器过载，那么最好移动一些进程，即使从内存访问其数据需要更长的时间。 我们的模型可以显示迁移比让处理器过载更好，反之亦然。4.3表演性关于可执行性指标，我们包括Er（i）状态来表示处理器中的故障。我们的故障模型只考虑故障静默行为，即。，当处理器出现故障时，它不会产生任何结果，并将永远处于该状态。 因为系统中可以有多个处理器，所以我们对系统继续正常工作的情况感兴趣。我们的目标是验证系统在存在故障时的行为（可执行性）[19]。这种方法的一个后果是，由于吸收态（Er（i）），我们无法计算模型的定态解过程自动机具有第1002章ep2ep2EP2ep2中文（简EP中文（简2mpr12mpe12SP2Sn2fn2ID2FP2IB（2）中文（简SE2FTS2的sio2前（2）Mie12 月N2月 12日类型事件syn同步同步synMie12Mie21率类型事件rmie12rmie 21mpr12rmpr12mpr21rmpr21和平号12和平rmir12rmir21mpe12rmpe12mpe21rmpe21synsynsynsynsynlocklocklocklocse1硒铁硅的sio2率类型事件发生率rse1rse2rfe1rfe2rsio1RSiO2月氮1 rmoN1钼氮rmoN2FTS1FTrfts1RFTS2SP1SPrsp1rsp2loc锁定锁定locFP1fp2id1id2ep1ep2sn1sn2fn1fn2rfp1rfp2fid1fid2rep1rep2rsn1rsn2rfn1rfn2R. Chanin等人理论计算机科学电子笔记151（2006）1311410的情况。8IJ0的情相同的特征。En状态是一种吸收状态。避免吸收状态的一个可能的解决方案是假设处理器可以被固定，返回到其正常操作，并且进程可以再次开始执行。4.4指定参数本节显示了分配给事件发生率的数值。一些参数取自基准测试，而另一些是Linux变量或常量，例如。时间片值。使用的基准测试是LMBench [18]，在4处理器的Itanium 2计算机和12处理器的HP Superdome上执行。使用的Linux内核版本是2.6.11（应用了ia64补丁我们还应用了另一个补丁，将额外的调度信息添加到/proc目录[16]。使用LMBench和Linux补丁，我们将以下值分配给事件率（所有速率均以毫秒为单位• rfts 和rfn：1。Linux认为时间片从10到300毫秒不等在我我时间片在我们的模型中，我们将I/O限制的时间片定义为200 ms，将CPU限制的时间片定义为200 ms。为100 ms;• rsp：1. Linux内核2.6.11中平衡间隔的默认值为200 ms;我200• r sni：1 −r sei.考虑调度时间为1 ms。因为要么选择模型化流程执行，要么调度任何其他流程运行，所以此值取决于r sei值;• rfpi 和rmoNi：1。考虑0.8 ms来执行负载均衡算法。当执行此算法时，并不意味着将发生迁移。只有在系统不平衡的情况下才会发生移徙• rmprij，rmirij，rmpeij关于RMie：1分。考虑N为进程NPNP是系统中处理器的数量;• r r：1N . 建模过程必须等到所有其他过程完成i时间片在它移动到R（i）状态之前，它们的时间片此外，一些速率和参数根据实际工艺实施来选择：• rsioi：如果进程是I/O受限的，则该速率必须大于rftsi，否则意味着该进程可能是CPU受限的;•1. 在几乎所有的模型中，我们都认为一个I/O操作需要1i1000二是要执行;•rse：1表示CPU受限进程，1表示I/O受限进程。 它是nec-i0.20. 7必须定义有多少进程具有更高、更低或相等的优先级模型化的过程。因此，rsei率是低优先级进程的执行概率与等优先级进程的执行概率的指数分布之和;•报告：1. 该比率用于性能分析，即：当我们想要分析我1如果一个或多个处理器发生故障，系统的行为;142R. Chanin等人理论计算机科学电子笔记151（2006）131• 注册ID：1 .为了触发此速率的事件，建模的流程不能我一万在R（i）或Ep（i）中;•参考：1. 此速率用于更改进程的总生存期。平均i600r过程的持续时间被计算为FE/时间片。rsioi+r ftsi5性能和可靠性指标如第4节所述，所提出的模型是一种通用方法，描述了Linux调度算法的一部分。根据被建模系统的大小，最终自动机可能相当大。然而，可以开发不太复杂的模型，可以更快地解决，基于通用模型。因此，可以直接获得具体的性能和可靠性指标。例如，为了获得一些迁移信息，例如流程第一次迁移需要多长时间，我们可以调整通用模型。在通用模型中（见图5），状态集R（i）、Ep（i）、Ex（i）和IO（i）表示第i个处理器中Process但是，有时候并不需要对所有处理器中的Process行为进行建模。对于该示例，期望仅具有迁移信息。在图7中，我们提出了一个简化模型，它表示处理器1中的Process，处理器2被建模为只有一个（吸收）状态（M（2））。P（1）过程见图7。 简化自动机流程在图7中，状态M（2）表示进程已经从处理器1迁移到处理器2。注意，同步事件mir12和mpr12都变成仅一个本地事件mr12。类似地，事件mie12和mpe12也变成仅一个本地事件me12。这种变化的发生是由于这样的事实，如前所述，没有必要对所有处理器建模。因此，这些同步事件没有在新的处理器自动机中表示（图11）。8）。然而，如果系统中存在其他处理器，则如果它们的迁移速率相同，则不需要添加新状态来表示新处理器。否则，必须为每个新处理器创建一个状态（不同的迁移率）。请注意，这种新方法大大减少了男（2）EnR（1）FIO1IO（1）se1SiO1前（1）第12章R1我12Ep（1）FTS1Fe1类型事件发生率synsio1synse1合成铁1同步器1位置fio11号位置12楼12号地块RSiO1rse1rfe1rfts1rfio1rr1rme12r先生12R. Chanin等人理论计算机科学电子笔记151（2006）131143P（1）额（1）ep1ep1EP1ep1PB（1）EP中文（简1SP1Sn1FP1fn1IB（1）ID1月氮1中文se1FTS1SiO1Fe1前（1）类型事件率类型事件率synse1rse1locSP1rsp1synFe1rfe1locFP1rfp1synFTS1rfts1locID1fid1synlocSiO1Sn1RSiO1rsn1locloc月氮1ep1rmoN1第1章locfn1rfn1Σ Σf id1=（st进程！= R（1））&&（st过程！= Ep（1））文件id1图8.第八条。简化自动机P（1）及其事件模型在一般模型中，过程自动机具有（4个NP）+1个状态，处理器自动机（P（i））具有6个NP状态，而在新模型中，过程自动机具有4 +（NP-1）+1个状态（对于具有不同迁移率的处理器）或4 + 1 + 1个状态（对于具有相同迁移率的处理器），一个处理器自动机有6个状态任何其他模型的基础上的一般一个可以导致更大或更小的减少。5.1数值结果在本节中，我们将第4节中介绍的分析模型应用于不同的NUMA机器。首先，我们在本节开始时所获得和展示的结果被应用于一个4处理器NUMA机器，该机器被组织成四个节点和两个内存访问级别。每个节点仅由一个处理器组成。一个进程在一个与它最初创建时不同的处理器（节点）中执行，它的执行速度将比在它开始执行时的处理器中慢25%。较慢的执行是由于进程访问其数据所花费的时间，这些数据存储在不同的节点中。图9显示了I/O绑定和CPU绑定过程的迁移概率。I/O绑定的进程执行更多的I/O操作（IO状态），而CPU绑定的进程执行时间较长，并且更频繁地进入过期队列（Ep状态）。如第3节所述，过期队列中的进程最好迁移到其他处理器。因此，CPU密集型进程往往比I/O密集型进程迁移得更早（见图10）。9）。由于I/O绑定进程执行I/O操作的时间更长，而在过期队列中的时间更短，因此将其移动到另一个处理器需要更长的时间。这种现象的发生是因为I/O绑定的进程倾向于在R和Ep状态中花费更少的时间，因此具有更少的迁移机会但是，请注意，经过很长一段时间后，I/O受限和CPU受限的进程具有类似的行为。出现这种情况是因为I/O绑定的进程将更频繁地执行（进入Ex状态）。因此，在很长一段时间内，I/O绑定的进程将更快地完成其时间片，因此这种类型的进程将更快地移动到过期队列（Ep状态）。这将导致I/O绑定进程在长时间之后的更高迁移概率8我们基于实际NUMA机器内存延迟的假设。144R. Chanin等人理论计算机科学电子笔记151（2006）13110.80.60.40.200 200 400 600 800 1000时间（秒）见图9。 进程迁移行为使用同一台机器，我们验证了一个I/O绑定的进程在不迁移到任何其他处理器的情况下完成其执行的概率（正常结束概率）。图10示出了低优先级和高优先级I/O绑定进程的结果。虽然有人会期望高优先级进程首先结束，但可以观察到，当迁移可能时，低优先级进程具有最高的正常结束概率。这是因为高优先级的进程往往执行得更频繁，它也往往迁移得更早。如果进程不能迁移，这种情况就不会发生。0.20.150.10.0500 200 400 600 800 1000时间（秒）见图10。不迁移的图11呈现了应用于以下的通用模型的正常结束概率： 我们的示例机器。在这个模型中，我们引入了故障的概念，在一个或多个处理器。我们已经验证了七种可能的错误情况：（i）K= 0（所有处理器工作）;（ii）K= 1（处理器1发生故障）;（iii）K= 1（一个处理器发生故障，处理器1除外）;（iv）K= 2（处理器1和2发生故障）;（v）K=2（两个处理器发生故障，处理器1除外）;（vi）K= 3（处理器1、2和3发生故障）;以及（vii）K=3（处理器2、3和4发生故障）。我们假设在处理器1中创建了一个进程，即：，它在其他处理器（2、3或4）中执行较慢。如前所述，由于内存延迟，进程在处理器2、3和4中的执行速度比在处理器1当一个处理器发生故障时，它的各个进程被转移到另一个处理器。没有进程CPU绑定I/O绑定I/O受限（低优先级）I/O受限（高优先级）迁移概率正常结束概率时间CPUI/O时间CPUI/O00.00000 0.00000500.72188 0.2423010.015270.007221000.879200.4146220.040290.014631500.91270 0.5421730.06656 0.021462000.91984 0.6366040.09247 0.027853000.92168 0.7582450.117690.033904000.92176 0.82489100.23289 0.061405000.921770.86142150.331610.086756000.921770.88143200.416180.111097000.92177 0.89240250.488630.134658000.921770.89841300.550700.157509000.921770.90171400.649420.2011710000.921770.90351时间低高时间低高00.000000.00000500.024990.0261710.002310.003151000.043830.0435720.003010.003711500.059400.0564630.003660.004252000.072280.0660040.004170.004793000.091720.0782850.004670.005334000.105010.08502100.007110.007945000.114090.08871150.009500.010476000.120300.09073200.011840.012927000.124540.09184250.014140.015298000.127440.09244300.016390.017609000.129420.09278400.020770.0220110000.130780.09296R. Chanin等人理论计算机科学电子笔记151（2006）13114510.80.60.40.2已经消失了00 5 10 15 20 25 30时间（秒）见图11。流程执行行为在故障场景K= 0、K= 1kHz、K= 2kHz和K= 3kHz下，过程性能几乎相同。由于处理器1不会发生故障，因此该过程可以更快地执行。因为不需要迁移到另一个处理器。然而，在场景K= 1、K= 2和K= 3中，性能会随着工作的处理器数量减少而降低。它是由于从故障处理器迁移到其他处理器而导致的过载而发生的。此外，进程将在远离进程内存区域的处理器中运行。因此，将需要更长的时间才能完成其执行。正如本节开始时所提到的，我们将我们的模型应用于不同的NUMA机器。为了将当前的负载平衡算法与我们的研究小组正在开发的新策略进行比较，我们将我们的模型应用于由四个单处理器节点组成的四处理器NUMA机器，但其中有三个单处理器节点。内存访问级别。当前版本的Linux负载平衡算法为此机器创建了两个Linuxsched域级别。为了更好地表示实际的计算机体系结构，我们建议改变Linuxsched domain实现，以考虑几个内存访问级别[7]。在我们的建议中，Linux负载平衡算法为此机器创建三个Linuxsched域级别10.80.60.40.200 5 10 15 20 25 30时间（秒）见图12。 3-水平NUMA机图12示出了当Linux仅识别两个存储器访问级别（3个存储器访问级别-2个Linux调度域级别）和当Linux识别实际计算机的拓扑（3个存储器访问级别- 3个Linux调度域级别）时运行的进程的性能。K=0K=1K=1*K=2