分布式系统中的检查点算法new

《分布式系统中的检查点算法new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第卷第期计算机学报年月分布式系统中的检查点算法魏晓辉鞠九滨吉林大学计算机科学系长春。。摘要检查点能够保存和恢复程序的运行状态它在进程迁移、容错、卷回调试等领域都有重要的应用本文对分布式系统中的检查点算法进行了详细的分类评述检查点算法可分为单进程和分布,式程序检查点算法分布式程序检查点算法又可分为异步检查点算法和一致检查点算法同时本文系统介绍了改进检查点算法性能的典型方法这些改进算法主要采用两个策略来减少算法的开销与延迟一是减少检查点文件中需要存储的信息量,如增量算法等二是提高检查点操作与目标程序运行的并行性,如主存算法等最后,文章讨论了目前检查点算法的局限性和进一步的工作,分布式,,一致检

2、查点算法关扭词检查点程序异步检查点算法分类号一一刀‘户,,,,一,,,一,,一,,,,,一,,一一,,,,一一,一,,本文。收到修改文。收到本课题得到国家自然科学基金编号为资助魏晓辉男年,,主要研究方向为分布式系统鞠九滨,男,,教授,,主要研究方向为分布生博士研究生年生博士生导师式系统©1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net计算机学报年,,,己口叠‘二二检查点能够保存恢复程序的运行状,它在许多领域都有重要的应用态,进程迁移目前大多数操作系统不能提

3、供进程迁移功能利用检查点可以保存进程在,然后在其某台机器上的运行状态它机器上恢复进程的运行以实现进程迁移容错分布式系统的故障率随系统机器数的增加而增加,长时间运行的作业若在每次,,出现机器故障都从头开始重新执行该作业将很难被执行完毕因此利用检查点实现多机系统容错成为人们日益关心的热点卷回调试在程序调试过程中,利用检查点保存程序在多个时刻的运行状态当错误,,以再次产发生时把程序卷回到所保存的某一时刻的状态重新向下运行生相同的错误来查找,错误发生条件的调试方法称为卷回调试分布式程序包含较多的不确定成份当发现运行错误,重新运行程序查找错误原因时同样的错误可能很难再次出现利用卷回调试会在很大程度上

4、提高错误再次发生的概率检查点算法是当前研究的热点,和难点检查点算法正在从研究阶段逐步走向实用化许多仁‘口,,一机群计算环境都利用检查点机制来增强系统的功能如巨,〕,仁〕,,仁」巨〕等检查点的基本概念和典型算法检查点用,于保存和恢复程序的运行状态检查点对程序状态进行保存的时刻称为检查点时刻根据检查点算法的适用范围可把目前的检查点算法分为两类单进程程序检查点算法和分布式程序检查点算法单进程程序检查点算法单进程程序检查点算法用于保存和恢复单进程程序的运行状态在内存中一个进程的运,不能保存行状态由用户区和核心区两部分组成检查点不是操作系统的一部分和恢复进程核,心区的全部信息因此检查点通常不能打断系

5、统调用的执行川系统的检查点算法是该类算法的代表该算法对程序的状态保存过程如下首先,,利把必要的进程核心区内容保存到进程的用户区之中用系统调用保存进程的,和指针等内容然后保存进程所打开的文件的打开方式及指针偏移最后利用进程此时的数据段、堆栈段和代码段信息组合成一个可执行的检查点文件当恢复程序运行状态时,只需,,执行程序的检查点文件检查点文件被执行时首先将程序恢复到检查点时刻的运行状态然后利用系统调用恢复进程的和指针使进程继续向下运行,该算法完全在操作系统外部实现了对程序状态的保存与恢复因此具有良好的可移植性,它实现了检查点对用户程序的完全透明性该算法的其次局限性主要有两个方面不允许©1994

6、-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net期魏晓辉等分布式系统中的检查点算法用户程序使用与进程派生、,因此不能直接用于保存进程通信有关的系统调用和恢复分布式程,序的运行状态用户程序须与检查点设备库静态链接这样只有程序可执行代码的用户就无法使用检查点功能分布式程序检变点算法该类检查点算法用于保存恢复分布式程序的运行状态,它是对单进程程序检查点算法的进一步发展分布式程序的运行状态由每个进程的运行状态和进程间的消息组成在全局检查,,点时刻每个进程不但要做局部检查点

7、以保存本进程的运行状态还要对进程间的消息进行记录分布式程序的检查点算法可分为两类异步检查点算法和同步检查点算法一致的检查点算法基本概念·一致的全局状态,,尸尸,⋯,尸‘。尸设分布式程序由进程组成为进程的第个检查点文件一个进程,间消息有两个与之相对应的事件消息发送事件和消息接收事件当,,任‘。进程发送消息的时刻早于进程做第个检查点的时刻称当进程,尸,二‘。‘二搂收消息的时刻早于进程做第个检查点的时刻称,,,,,二,⋯,尸定