胡元元，袁顺召

（长江航运总医院，武汉　430015）

分布式任务管理系统中检查点的设计

胡元元，袁顺召

（长江航运总医院，武汉430015）

0　引言

检查点是任务执行状态的一个瞬态图，使任务在必要时可以在同一点上重新开始执行。当集群环境的某一部分出现故障时，正在运行的程序可以从中间某点重新开始，而不需要从头开始。

在DMS系统中，有时会发生硬件或软件故障，这就需要在系统中具有处理故障恢复的有效机制。检查点就是这样一种机制，检查点将正在运行的任务的当前状态保存在一个文件中。可以使用这个文件在故障点重新运行任务。这些文件通常存储在可靠并共享的文件系统中。如果某个节点发生故障，任务可以在另一个有效的节点上继续运行。在需要进行任务迁移时，使用检查点可以使正在运行的任务先暂停，当任务迁移到另一个节点时再继续执行。

1　检查点

检查点技术是将正在运行的任务的状态保存在一个文件中。文件中包括从检查点处开始运行任务所需要的所有信息。文件中存储的基本信息包括和任务相关的寄存器、栈和堆中的信息。一般情况下，文件应包含等候信号、文件描述符、sockets和所有线程等信息。

当前主流的检查点技术按其实现层次可分为应用级检查点、用户级检查点和内核级检查点［1-2］三类。这三种检查点机制的透明度，效率和初始化检查点并恢复的机制各不相同。

2　DMS系统构成环境

计算机集群的出现和使用己经有十几年的历史。作为最早的集群技术设计师之一，G.Pfister对集群的定义是，“一种并行或分布式的系统，由全面互连的计算机集合组成，可作为一个统一的计算资源使用”［3］。

将数台服务器计算机组合成一个统一的集群，多台服务器将可以在用户或管理员不必了解细节的情况下分担计算负载。例如，如果服务器集群中的任何资源发生了故障，则不论发生故障的组件是硬件还是软件资源，作为一个整体的集群都可以使用集群中其他服务器上的资源来继续向用户提供服务［4］。

换言之，当资源发生故障时，和服务器集群连接的用户可能经历短暂的性能下降现象，但不会完全失去对服务的访问能力。当需要更高的处理能力时，管理员可以通过滚动升级过程来添加新资源。该过程中，集群在整体上将保持联机状态，它不仅可供用户使用，而且在升级后，其性能也将得到改善。

集群中的成员结点可以是同构的，也可以是异构的，或是两者的混合。一个集群可以被看成一个并行机，在批处理系统的参与下，集群中的一个结点可以运行多个任务，也可以将一个任务分布在多个结点上运行［5］。

组成这个集群系统的每一个计算机称为结点（Node）。为了保证可靠性，每个结点通过冗余的网络路径进行通信，每个结点都拥有一定的集群资源。集群中的结点能够对这些资源进行控制，包括启动、停止和资源转移。

一个集群系统映射自己独特的描述，这些特有的描述是用于客户端访问应用于每个结点的应用程序和服务程序，同时也被管理者用于进行管理集群系统［6］。由于拥有这些独特的描述，使得结点之间可以透明的进行应用程序的资源转移，也可以增加一个新的结点，但是网络客户把整个系统当作一个单独的服务器系统。图1是DMS系统的架构图。

客户端用来供用户访问Cluster的节点［7］，当用户提交任务的节点发生任何故障时，它提供节点通信连接方式的自动转换，并继续完成任务，但用户并不会感觉到任务运行位置的变迁。

管理器提供对Cluster的动态管理，包括增加和删除节点，以及对运行节点的动态监控。

图1　DMS系统构成环境

Cluster接收来自集群管理器的控制命令和信息，并管理Cluster节点上的资源，监控资源运行状态，控制故障任务的运行、停止和任务迁移。

共享磁盘阵列供任务运行时特有资源和恢复日志文件的存储，同时还提供Cluster上各节点的共享存储空间。本地磁盘存储任务的临时文件。

通常在集群环境中，检查点存储在共享磁盘中。由于节点可能常常发生故障，检查点可以用来恢复任务继续运行。在共享磁盘中存储检查点有一些性能缺陷。首先，检查点可能非常大，这样很容易堵塞私有网络。这对使用私有网络进行通信的并行任务可能会造成性能损失。在进行检查点操作的过程中，任务可能会被阻塞，因此长时间的检查点操作可能会对任务本身造成性能损失。

在DMS系统中，检查点最主要的作用是进行容错，任务抢占调度和任务迁移。

3　检查点实现方法

同时使用共享磁盘和节点的本地磁盘存储检查点，可以降低网络负载并减少检查点操作的时间。基本思想是使用两种检查点间隔。每隔一段较短的期间在本地磁盘上创建检查点，每隔一段较长的期间创建共享磁盘上的检查点。

检查点在工作节点上建立。建立检查点时，将检查点的版本号作为检查点文件的文件名的一部分。使用版本号有两个好处，首先可以节省存储空间，因为只需要存储版本号最近的检查点。其次，当同一个任务的多个检查点在网络上传输时，由于只需要存储版本号最近的检查点，所以可以不用传输版本号较旧的检查点，可以节省带宽。创建检查点的速度可能会快于在网络上传输检查点和在共享磁盘上存储检查点的速度。在这种情况下，工作节点上会产生一个等待发送的检查点的队列。这个队列实际上是一个优先级队列，在队列中新检查点的优先级高于旧检查点。同一个任务的新检查点会将旧检查点从队列中删除。通常情况下，使用一个单独的线程传送检查点，这样，在传送检查点时，用户任务可以继续执行。但是，有时在任务继续执行之前，可能需要确定某个特定的检查点已经到达共享磁盘，这时，可以将检查点设置为阻塞模式。当检查点是阻塞模式时，只有当前一个检查点被传输到共享磁盘上，下一个检查点请求才会被响应。在非阻塞检查点情况下，检查点等待被发送的同时任务继续执行，很有可能在该检查点发送之前又创建了新的检查点，这时，删掉之前建立的检查点，只传送新的检查点以节省带宽。检查点可能会非常大，所以需要对存储的所有检查点文件进行检查，只有最近的检查点被保留下来。

在本文的方法中，为DMS系统设计了三类检查点：容错检查点，在任务抢占式调度后不进行进程迁移的检查点和在任务抢占式调度后进行进程迁移的检查点。下面各节具体描述每一种检查点方法。在下面的各图中，实线表示检查点操作，虚线表示恢复任务继续运行的操作。

3.1容错检查点

为了实现容错功能，需要定期记录任务的检查点。记录检查点的时间段取决于任务本身。如果任务需要运行几个月，合理的间隔期间应该是几个小时。相反地，较短的任务需要较短的期间。当任务的运行需要大量内存时，期间的选择必须非常谨慎，因为检查点操作也需要花费一些时间。

图2是这容错检查点的处理方法。检查点操作分为两个期间：TS和TL。期间TS一个较短的期间，它定义了两次检查点操作之间的时间间隔，TS存储在本地磁盘中（图2中的（1））。期间TL一段较长的期间，它定义了若干次检查点操作的时间间隔，TL存储在共享磁盘中（图2中的（2））。期间TL也可以表示为若干段较短的期间。使用本地磁盘可以降低网络负载，并且提高了检查点处理的速度。

如果一个节点失败了，查看检查点是多久之前存储的。如果是最近版本的检查点，从这个检查点开始在另外的可用的节点上恢复运行任务（图2的（3））。否则，等待一段时间来确定失败的节点是否会恢复。如果节点恢复了，任务在初始分配的节点上继续执行（图2的（4））。如果节点没有恢复，任务在另一个可用的节点上恢复运行，从在共享磁盘中存储的最后一个检查点处开始执行（图2的（3））。

图2　容错性检查点极其恢复

3.2不进行任务迁移的抢占式调度

在没有任务迁移的抢占式调度中，当要进行抢占调度时，首先记录被抢占的任务的检查点然后停止该任务。此后，一个新任务会在原来的节点上运行，当新任务完成后，原先的任务在该节点上恢复运行。被抢占的任务不能被迁移到其他节点上继续运行。当用户指定要使用某个节点而这个节点上正运行着其他的任务时会发生这种抢占调度。

图3　没有迁移的任务抢占调度极其恢复

3.3任务迁移检查点

在任务迁移的情况下，对任务进行检查点操作后，停止任务的运行并且在另一个节点上恢复运行任务（图4）。如前所述，在任务抢占调度和负载平衡时会发生任务迁移。

在这种情况下，当迁移发生时，把检查点存储在共享磁盘中（图4的（1））。由于任务被迁移到另一个节点上（图4的（2）），所以只需要在共享磁盘中存储检查点。

图4　任务迁移的检查点极其恢复

在这种情况下，只在本地磁盘上存储检查点（图 2的（1））。当新任务完成后，从本地磁盘系统中恢复先前的任务（图 3的（2））。由于任务不能被迁移到其他的节点上，所以没有必要将检查点存储在共享磁盘中。这种方法明显的降低了网络负载。另外，提高检查点操作速度的同时也提高了抢占式任务调度的速度。

4　检查点放置算法

4.1两个状态大小的检查点放置算法

检查点的开销取决于放置检查点的任务执行点。更具体的，检查点的开销取决于任务在该点的状态的大小。任务的状态大小随着内存的分配和释放而改变，检查点的开销也根据一些进程随着时间而改变。因此，固定期间的放置策略并不是最优的。

虽然不能预知任务的状态大小，但是可以通过监视内存的分配和释放来跟踪任务的状态大小。通过监视内存操作，可以知道任务当前的状态大小。因此，可以估算在当前放置检查点的开销。

本文的算法的主要思想是在任务的执行过程中寻找一点使得在这一点放置检查点最有益。该算法找到任务的状态大小较小的点，并使用这些点作为检查点。如果找到了这样的点，用较小的间隔在这些点上设置检查点，这样，故障后的再处理时间比较短。如果在一段时间内没有找到这样的点，在较高代价的点上设置检查点以避免需要较长的再处理时间。在这种情况下，检查点之间的间隔应该设置的比较长，以减少检查点开销。

下面的例子说明了对于检查点代价的了解可以改善检查点性能。设任务有两个可能的状态大小，S1和S2，令S1＜S2。设任务的状态大小为Si时，检查点的代价为Ci（C1＜C2）。任务的状态大小根据一个两状态的Markov链改变。

该算法的工作方式如下：定义两个时间点，t1和t2，令t1＜=t2。该算法根据下面的规则决定是否要在t点放置检查点，t是从上次检查点到当前时刻的时间：

（1）如果t1点的状态大小是s1，那么在t1点放置一个检查点。该检查点的代价是C1。

（2）如果t1点的状态大小是s2，系统等待直到状态大小变为s1，并在这一点放置检查点。该检查点的代价是C1。

（3）如果t1点的状态大小是S2，并且直到t2点，状态大小始终没有改变，那么在t2点放置一个检查点。这种情况下的检查点开销是C2。

为了避免检查点开销过高，检查点不能在t1点之前放置。同样，为了避免从检查点再处理时间过长，不能在t2点之后放置检查点。t1和t2的值会影响算法的性能。通过分析算法的开销比，可以找到使得开销比最小的t1和t2的值。

4.2多个状态大小的检查点放置算法

两状态大小的检查点放置算法可以被扩展为多状态大小的检查点放置算法。

假定任务可能的状态大小是S1，S2，…，Sn，并且状态大小为si时，检查点开销是Ci，这里C1＜=C2＜=…＜= Cn。每个状态大小si有一个与之相关的时间期间ti。该算法根据下面的规则决定是否在时间t放置一个检查点，t是从上一个检查点到当前时刻的时间。

（1）不在区间［0，ti）放置检查点。

（2）如果在某一点时区间［ti，ti+1）的状态大小为S1，S2，…，Si，在该点放置检查点。

（3）在tn时刻放置检查点，不考虑该点的状态大小。

4.3实现问题

在系统中实现时，使用计时器来决定放置下一个检查点的时间，每次状态大小改变时更新计时器。放置了一个检查点后，计时器被初始化为ti，si是放置检查点时的状态大小，计时器开始减数计时。当每次内存分配或释放操作使得任务的状态大小从si变为sj时，计时器的值增加一个tj-ti。当计时器的值小于或等于0时放置检查点。

本文的算法假设任务的状态大小处于一个有限的离散的集合中。事实上，任务的状态大小是连续变化的。这一问题可以通过量化来解决［8］，可以将状态大小量化为最接近的大小。如果量化误差不大，量化对于算法性能的影响可以达到最小。

5　结语

检查点对于支持容错功能的系统是十分重要的功能。在网络作业管理系统环境中，为了实现作业抢占调度和作业迁移，必须进行检查点操作。

本文首先描述了网络作业管理系统中进行检查点操作会产生的两个主要问题，即网络负载和检查点操作所造成的性能损失。然后，提出了避免这些问题的方法，就是使用节点的本地磁盘存储检查点。

［1］Neil Cafferkey，Philip D.Healy，David A.Power and John P.Morrison.Job Management in WebCom.Sixth International Symposium on Parallel and Distributed Computing（ISPDC'07）.

［2］Adam Jamison Oliner.Cooperative Checkpointing for Supercomputing Systems.Submitted to the Department of Electrical Engineering and Computer Science，on May 19，2005，in Partial Fulfillment of the Requirements for the Degree of Master of Engineering in Computer Science and Engineering.

［3］Norihiro Fujii，Nobuhiko Koike.Multi-user/Multi-Test-Bed Remote Hardware Laboratory with Job Management System.2007 IEEE International Conference on Microelectronic Systems Education（MSE'07）.

［4］LUAN Cui-ju，SONG Guang-hua，ZHENG Yao.A Flexible Architecture for Job Management in a Grid Environment，Luan et al.Zhejiang Univ Sci A 2007 8（1）：95-105，Sept.28，2006.J.

［5］Antonio Cunei Jan Vitek.A New Approach To Real-Time Checkpointing，VEE'06 June 14-16，2006，Ottawa，Ontario，Canada.

［6］Bidyut Gupta，Shahram Rahimi.A Novel Roll-Back Mechanism for Performance Enhancement of Asynchronous Checkpointing and Recovery，Informatica 31，2007，1-13.

［7］Greg Bronevetsky，Daniel Marques，Keshav Pingali，Application-level Checkpointing for Shared Memory Programs，ASPLOS'04，October 9-13，2004，Boston，Massachusetts，USA.

［8］Jonathan M.Smith，A Survey of Process Migration Mechanisms，Computer Science Department，Columbia University，22 May 2001.

Distributed；Business；Checkpoint；Cluster

The Checkpoint Design of Distributed Business Management System

HU Yuan-yuan，YUAN Shun-zhao
（General Hospital of Yangtze River shipping，Wuhan 430015）

1007-1423（2015）31-0003-05

10.3969/j.issn.1007-1423.2015.31.001

胡元元（1983-），女，湖北当阳人，硕士，工程师，从事领域为软件工程

袁顺召（1986-），男，湖北利川人，硕士，从事领域为行政管理

通过对检查点的设计，提高分布式任务管理系统的性能。介绍检查点及DMS系统构成环境，然后提出检查点实现的三种方法，即容错检查点，不进行任务迁移的抢占式调度，及任务迁移检查点。设计两个状态大小的检查点放置算法和多个状态大小的检查点放置算法，降低网络负载和检查点操作所造成的性能损失。

分布式；任务；检查点；集群

Performance of Business Management System Distributed（DMS）is improved by the design of Checkpoint.Introduces the Checkpoints and the DMS system，and then proposes three methods，namely，fault tolerance Checkpoint，preemptive scheduling of tasks，and task migration Checkpoint.Designs two state size checking points placement algorithm and multiple state size，reduces the performance loss caused by network load and checkpoint operation.