采用增量检查点技术改进 Condor检查点机制的研究

张光辉,王丽娟,陈 姗

(河南农业大学信息与管理科学学院,河南郑州 450002)

检查点技术是实现分布∕并行系统容错的重要手段,同时也是实现进程迁移、作业切换和系统模拟的基础[1～3].运用检查点技术,在程序正常运行时将程序的状态信息写入到持久性存储设备上.当程序因为异常而崩溃需要重新启动时,就可以从最近保存的检查点文件中恢复到程序保存检查点时程序运行的状态,这样,就可以接着以前的进度继续执行,从而降低了程序崩溃所带来的损失[4,5].设置检查点的开销是影响系统性能的一个主要因素.如果一个应用程序在运行的整个周期内每隔一段时间就进行一次检查点操作,但这个程序直至运行完成也没有出现故障(没有使用检查点进行重启),这种情况下检查点操作就是完全多余的,不但加长了程序运行的时间,而且浪费了系统的计算资源.因此,设法降低检查点操作的开销,对于充分利用整个系统的计算资源是很有必要的.文章首先介绍了机群作业系统 Condor,然后分析了Condor系统里面检查点机制的实现原理.在此基础上,针对此系统里面检查点机制的不足,提出了改进方案.

1 Condor的工作原理

Condor是由美国威斯康星大学研究开发的一个全新的计算密集型作业的资源管理系统.该系统能有效地监视网络下的资源,并聚集空闲资源形成一个大吞吐量的计算环境[6].Condor系统里面的计算机分为 3类,中央管理主机、提交作业的主机和运行作业的主机.

图1 Condor系统的工作流程Fig.1 Work flow of Condor system

用户通过代理(schedd)提交作业.schedd进程把提交的作业在本地作业队列中进行维护管理,然后开始寻找满足作业要求并且愿意执行这个作业的计算资源.schedd进程会把作业对所需计算资源的类型描述发送给中央管理主机上运行的 collector进程,同时,愿意运行作业的主机会通过 startd进程向 collector发送自己的机器环境描述的信息.运行在中央管理主机上的 negotiator进程会把用户的需求与系统里面的计算资源相匹配,一旦发现匹配的组合,就会通知双方.schedd进程在找到满足作业执行要求的计算资源后,会主动联系这个计算资源上的 startd进程,以确认此计算资源确实可用.要真正的运行用户提交的作业,双方都必须产生一个新的进程.在提交作业的主机上,schedd进程创建 shadow进程,在将要运行作业的主机上,startd进程会创建 starter进程.starter进程用来为作业提供一个运行环境.shadow进程负责传输starter进程所需的作业信息和所有的数据文件,并且为用户作业的远程系统调用服务,允许作业透明的访问位于提交主机上的数据文件.作业执行完或者被放弃执行时,starter进程取消用户作业创建的所有子进程,向作业提交主机发送消息,该进程退出[6].

2 Condor检查点机制

检查点是一个用于进程卷回恢复的技术:一个正在运行程序的状态被周期性的写回到持久性存储媒介上,当程序因为异常而崩溃时,程序可以从最近 1次保存的检查点处重启.

检查点机制使得 Condor系统的调度模块可以自由的使用抢占式调度策略[7,8].如果调度模块决定收回已经分配给 1个作业的计算资源(例如,计算机的主人回来了,需要使用这台计算机),它可以对此作业进行一次保存检查点操作,然后终止作业的运行,这样不但没有影响到用户使用自己的计算机,而且由于我们使用检查点保存了作业最后的状态,这样,当调度模块重新为这个作业分配 1台新的机器继续运行时,这个作业就可以从最近保存的检查点文件重启.

Condor系统是通过信号处理模块来实现检查点机制的.当 Condor向正在运行的进程发送 1个进行检查点操作的信号后,Condor安装的信号处理模块就会开始执行,它会把进程的状态写到 1个文件里面或者通过网络写到另外 1台计算机上.这些状态信息包括:

1)进程的数据段和堆栈段

2)加载的动态可执行库的信息

3)进程打开的所有文件的信息,包括文件名、打开方式和文件当前的位移

4)寄存器里面的数据

5)进程所设置的信号信息

应用程序要使用 Condor提供的检查点机制,必须首先使用 Condor-compile命令与 Condor系统的库文件进行链接.图 2给出了一个与 Condor库文件链接后的应用程序在正常执行时的虚拟地址空间的布局.应用程序员写的模块与 Condor的模块共同存放在程序的指令段.已经初始化的全局数据、未初始化的全局数据和使用 sbrk系统调用动态分配的数据存在于程序的数据段.堆栈段存放着内核为每个进程都会分配的 1块数据结构和目前因为函数调用而产生的活动堆栈.因为 Condor必须在用户的代码执行前做一些初始化,所以在活动堆栈的最底部是 Condor的 MAIN模块.MAIN模块执行完初始化工作后,会调用用户程序的入口函数main[9].

Condor使用 SIGTSTP信号来通知应用程序进行检查点操作.MAIN模块里面的初始化代码会为此信号安装 1个信号处理函数.图 3是应用程序进行检查点操作时地址空间的布局.SIGTSTP信号处理函数通过使用 setjmp将与程序有关的寄存器状态(堆栈指针寄存器 sp、程序计数器 pc等)保存在jmp-buf结构中.然后,此函数会把上面提到的保存检查点时需要保存的所有状态信息写到检查点文件里面.当 Condor使用检查点文件重启程序的时候,会恢复数据段、堆栈段、打开文件状态等状态信息,同时会使用 longjmp从 jmp-buf结构里面恢复保存检查点操作时寄存器里面的信息,做过这些操作后,程序就可以从保存检查点的位置继续执行.

3 Condor检查点机制的不足与改进方案

Condor系统中实现的检查点机制,对进程做的每 1次检查点操作,都会把上面提到的进程的所有状态信息保存下来.这样做使得检查点操作的时间开销太大,影响系统整体的效率[10～12].当执行检查点操作的时候,只有相对于上 1次检查点操作之后改变了的部分才需要保存,而相对于上 1次检查点操作后不变的部分可以从上 1次保存的检查点中恢复.这就是增量检查点技术[1],使用此技术可以减少每次保存的检查点文件的大小,进而降低进行检查点操作时的额外开销.

在 Condor的实现中,因为每次检查点操作得到的检查点文件都包含进程重启的时候所需的全部信息,因此,只需要保存 1个最新的检查点文件(每次得到 1个检查点后,旧的检查点文件就可以删除掉).相反,当使用增量检查点技术来进行检查点操作时,旧的检查点文件是不可以删除的,因为进程的状态信息分布在多个检查点文件中[1].针对于 Condor系统检查点机制存在的不足,使用增量检查点技术对其进行优化,提出下面的具体改进方案:使用页面保护技术确定哪些页面需要保存.也就是说,在 1次检查点操作完成之后,使用mprotect()系统调用来将进程的页面设置为只读.这样,当进程对这些设置为只读的页面进行写操作时,就会触发一个 SEGV信号.为这个信号安装信号处理函数,这个函数的功能是将这个只读页面改为可以读写的页面,并且标记此页面.这样,当下 1次进行检查点操作的时候,只有这些被标记的页面需要写到检查点文件中[13,14].

通过 1个具体实例,来比较一下使用上面的优化方案后带来的效率上的改进.考虑 1个矩阵运算里面经常会遇到的矩阵相乘的例子.例如,有 2个1 536×1 536的矩阵 A和B进行相乘运算,结果是一个 1 536×1 536的矩阵 C.在这个程序中数据段的空间主要是 A,B和 C这 3个矩阵所占用的空间.因此,忽略其它变量所占用的空间,并且分别在矩阵 C的第 256,512,768,1 024和 1 280列的值得到后进行保存检查点操作.由于在整个运算过程中,矩阵 A和 B的值一直不变,并且矩阵 C的列在求出后也不会在变化,所以得到表 1所示的数据(表中检查点文件大小的单位是以 1列作为标准单位,其中 1列所占用的空间是 1 536个矩阵元素所占用的空间;检查点操作时刻是结果矩阵 C的第 n列被计算得到的时刻).

表1 检查点文件大小对比Table1 Comparison of checkpoint file size

从表 1的数据可以发现,当第 1次保存检查点的时候,改进前与改进后的检查点大小一样,都是4 068.随后,当分别在 512,768,1 024和1 280列的值计算得到后保存检查点的时候,使用改进后的检查点策略只需要保存与上 1次保存时发生了变化的数据,也就是说改进后每次只需要保存的数据大小为 256.而没有采取改进方案时,需要保存的数据大小仍然是 4 608.由此,可以看到,使用改进后的检查点策略,可以很大程度上提高检查点操作的效率.

图4 检查点文件大小的比较Fig.4 Comparison of checkpoint file size

5 结论

检查点技术是容错计算机系统进行故障恢复的重要手段.本文在对 Condor检查点原理进行详细分析的基础上,针对其在进行检查点操作时存在的不足,提出了使用增量检查点技术对其进行优化的改进方案,通过矩阵运算的实例可以证明,使用此改进方案来优化 Condor系统的检查点机制,可大大提高系统检查点操作的效率.

[1] 王春露,汪东升.Unix进程检查点设置关键技术[J].计算机工程与应用,2002,38(1):90-94.

[2] CAO G H,MUKESH S.Checkpointing with mutable checkpoints[J].Theoretical Computer Science,2003,290:1127-1148.

[3] 门朝光,焦 亮,李 香,等.基于 Linux内核的进程检查点系统设计与实现[J].计算机科学,2009,36(4):192-195.

[4] FOSIER I,KESSELMAN C.网格计算[M].北京:机械工业出版社,2005.

[5] 杨 超,张伟哲,张宏莉.基于检查点算法的网格计算容错机制研究[J].微电子学与计算机,2006,23(9):82-84.

[6] 余丽琼,周振宇,郭绍忠,等.Condor系统在大吞吐量计算中的应用[J].信息工程大学学报,2004,5(1):77-79.

[7] 田 甜,祝永志.一种改进的同步检查点设置算法[J].计算机技术与发展,2009,19(8):124-126.

[8] 周恩强,卢宇彤,沈志宇.一个适合大规模集群并行计算的检查点系统[J].计算机研究与发展,2005,42(6):987-992.

[9] RONALD J.Leach,Setting checkpoints in legacy code to improve fault-tolerance[J].The Journal of Systems and Software,2008,81:920-928

[10]周小成,孙凝晖,霍志刚,等.一种降低并行程序检查点开销的方法[J].计算机工程,2007,33(12):84-86.

[11]张至柔.网格计算服务系统检查点算法研究[J].计算机工程与设计,2008,29(14):3596-3599.

[12]HIMADRI S P,AROBINDA G.Finding a suitable checkpoint and recovery protocol for a distributed application[J].Journal of Parallel and Distributed Computing,2006,66:732-749.

[13]隋翠翠,晏海华.一种基于高性能集群计算系统的检查点策略[J].微电子学与计算机,2008,25(10):162-165.

[14]鲁晓佩,廖湘科,卢宇彤.面向恢复的集群计算技术[J].计算机工程,2009,35(14):52-57.