（计算机应用技术专业论文）基于虚拟机的增量检查点和执行重放技术研究.pdf

浙江大学硕士学位论文摘要 摘要 交互式调试要求我们能重现测试过程中发现的b u g ，反复执行程序，逐步定 位错误的根源。然而，随着计算机体系结构、程序设计语言等的不断丰富，以及 计算机应用的快速发展，软件系统规模不断增大，任务复杂度不断提高，软件的 并发性不断加强，程序中存在着大量不确定性的因素导致b u g 难以复现。 为了解决这个问题，学术界提出了执行重放的方法，找出程序中所有不确定 因素，并在一次执行中将它们的表现记录下来，使得这些不确定因素始终按记录中 的方式表现。采用重放的方法支持软件调试与故障诊断具有实现成本低、调试效 果好等特点。 但是，现有的重放系统只关注于应用程序，无法支持系统级的重放，并且这 些技术往往需要修改操作系统或库函数。基于虚拟机扩展技术的重放技术不需要 修改应用程序与操作系统，系统的行为能够与真实情况下做到尽可能的一致，+ 对 于用户来说可以做到透明。因而我们采取这种方法来实现系统的重放，研发了全 系统重放系统b b r e p l a y e r ( b o c h s b a s e dr e p l a y e r ) 。b b r e p l a y e r 以较小的时间 ( 平均开销小于8 ) 和存储开销实现了全系统的精确回放。同时，为了在重放过 程快速高效重构系统状态并有效支持系统回退，b b r e p l a y e r 支持增量型检查点的 设置，对比相应的全量检查点，它在时间开销上减少了6 0 以上，存储开销上减 少了7 0 9 6 以上。 关键词：检查点，日志，执行重放，软件可靠性，虚拟机，b o c h s ，卷回恢复， 调试 浙江大学硕士学位论文 a b s t r a c t c y c l i cd e b u g g i n gr e q u i r eu s ：r e p r o d u c et h eb u g sf o u n di nt e s t ，r e - e x e c u t et h e p r o g r a ma n dl o c a t et h er o o tc a u s eo ft h eb u g h o w e v e r , w i t hc o n t i n u o u s l ye n r i c h e d c o m p u t e ra r c h i t e c t u r e ，p r o g r a m m i n gl a n g u a g e s ，a n dt h er a p i dd e v e l o p m e n to f c o m p u t e ra p p l i c a t i o n s ，t h e r ea r eal a r g en u m b e ro fu n c e r t a i nf a c t o r si nm o d e m s o f t w a r ew h i c hl e a d st o b u g sh a r dt or e p r o d u c e t os o l v et h i sp r o b l e m ，a , s o - c a l l e de x e c u t i o nr e p l a yt e c h n o l o g yh a v eb e e n d e v i s e d i t sm a i ni d e a ：d u r i n gt h ef i r s tp h a s e ，i n f o r m a t i o na b o u ta l ln o n d e t e r m i n i s t i c e v e n t sa r er e c o r d e di nt oat r a c ef i l e t h e nd u r i n gt h er e p l a yp h a s e ，m a k es a l et h e m e x h i b i tt h es a m ee f f e c t sa sw es a wi nt h er e c o r dp h a s e e x i s t i n ge x e c u t i o nr e p l a ys y s t e m sn e e dt oi n s t r u m e n ts y s t e ml i b r a r ya n dr e l i n k t h ep r o g r a mw h i c hl i m i tt h e i ra p p l i c a t i o n v i r t u a lm a c h i n ee x p a n s i o nb a s e dt e c h n o l o g y w i l ln o tn e e dt oc h a n g et h ep l a y b a c ka p p l i c a t i o n sa n do p e r a t i n gs y s t e m s ，t h es y s t e m c a na c ta n dd oa sm u c ha sp o s s i b l et h er e a lc i r c u m s t a n c e s ，u s e r sc a nb et r a n s p a r e n t s o w ed e v e l o p e daf u l ls y s t e mr e p l a y e r m b b r e p l a y e r , i tt a k e sal o wt i m ea n ds p a c e o v e r h e a d i no r d e rt or e c r e a t es y s t e ms t a t e q u i c k l yd u r i n gt h er e p l a yp h a s ea n d e f f i c i e n t l ys u p p o r ts y s t e mr o l l b a c k ，w ep r e s e n tam e t h o dt oi m p l e m e n ta ni n c r e m e n t a l c h e c k p o i n tb a s e do nt h eb o c h s k e y w o r d s ：c h e c k p o i n t ，l o g ，e x e c u t i o nr e p l a y , s o f t w a r er e l i a b i l i t y , v i r t u a lm a c h i n e ， b o c h s ，r o l l b a c kr e c o v e r y , d e b u g g i n g n 浙江大学硕士学位论文 图目录 图目录 图2 1 基于不确定事件类型的重放技术分类体系8 图2 2v m m 一1 1 图3 1 b o c h s 的总体结构图1 4 图3 2c p u 模拟的流程图15 图3 3 取指的流程图1 6 图3 4i a - 3 2 6 4 指令格式图17 图3 5 b o c h s 内存布局18 图3 6 i o 设备内存映射机制2 0 图3 7 中断系统2 1 图3 8 外设模型与p c 之间的交互2 3 图3 g b b r e p l a y e r 结构2 4 图3 1 0 b b r e p l a y e r 系统状态转移2 5 图3 1 1 b b r e p l a y e r 用户控制界面2 6 图4 1 内存页的检查点表示成重做日志和撤销日志3 0 图4 2 b b r e p l a y e r 检查点模型3 1 图4 3 检查点文件大小3 3 图4 4 系统启动时间3 4 图5 1 b o c h sc p u 的工作流程图3 7 图5 2 b b r e p l a y e r 中断重放的流程3 8 图5 3 重放输入指令3 9 图5 4 日志文件大小4 1 图5 5 日志文件增长率4 2 图5 6 压缩u s r 目录的时间4 2 h i 浙江大学硕士学位论文 表目录 表目录 表4 1 进程上下文2 7 表4 2 b o c h s 虚拟机上下文2 9 表4 3 测试环境3 2 i v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝姿盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者虢弓起 签字吼加q ? 年6 月g 日 学位论文版权使用授权书 本学位论文作者完全了解逝姿盘堂有权保留并向国家有关部门或机构 送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝姿盘鲎可 以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：3 起 导师签名： 布私 签字日期：加o g 年6 月又日 签字日期：k 川f 年月孑日 浙江大学硕士学位论文 第1 章绪论 第1 章绪论 1 1 引言 在设计程序时，总会或多或少地存在一些错误，因此调试是一个无法避免的环 节。调试就是一个从程序执行时的错误行为出发，利用一些工具和手段寻找程序中 的错误代码的过程。串行程序本身的简单性及确定性使得程序员能够比较容易地 理解和控制其执行过程，现有的各种串行调试工具极大地方便了调试工作的进行， 因此串行程序的调试相对而言比较简单。 然而，随着计算机体系结构、程序设计语言等的不断丰富，以及计算机应用 的快速发展。为了能够适应各种日益复杂的应用需求，软件系统规模不断增大， 任务复杂度不断提高，软件的并发性不断加强，软件潜在的b u g 已越来越难以捕 捉，由于软件错误直接造成系统失效的比率持续递增：据1 9 8 6 年的统计数据表 明，系统失效事件中诱因是软件错误的比率约占2 5 t 1 1 ，而到2 0 0 0 年，该比率 已超过4 0 1 2 l 。软件错误所导致的经济损失也已触目惊心，根据美国国家标准技 术研究所( n i s t ) 2 0 0 2 年6 月公布的调查表明，由于软件错误导致美国每年的 经济损失高达5 9 5 亿美元，约占g d p 的0 6 0 6 t 3 1 。 作为软件系统开发过程中用于可靠性保证的重要环节之一的软件调试支持 与故障诊断分析技术，仍然处于较原始的状态，传统的软件调试技术存在很大的 不足，无法全面完成所有类型的程序的有效调试。因而，全面加强软件调试手段， 提供有效的软件调试支持，并有效提高软件故障诊断的分析技术，具有较重要的 研究意义和实用前景，对于提高软件可靠性有很好的促进作用，也是前沿研究的 一个热点方向。 1 2 软件可靠性概述 1 2 1 软件可靠性的概念 根据i e e e 的定义，软件按规定的条件，在规定的时间内运行而不发生故障 的能力。同样，软件的故障是由于它固有的缺陷导致错误，进而使系统的输出不 浙江大学硕士学位论文第1 章绪论 满足预定的要求，造成系统的故障。所谓按规定的条件主要是指软件的运行( 使 用) 环境，它涉及软件运行所需要的一切支持系统及有关的因素。如支持硬件、 操作系统及其他支持软件、输入数据的规定格式和范围、操作规程等。 从软件系统发展的历史来看，二十年前软件系统设计主要考虑的目标是如何 实现软件的各种功能，十年前关注的是如何提高软件运行的效率，而现在软件系 统设计的目标开始转向如何使软件系统能够可靠地运行。 1 2 2 软件可靠性的管理 软件可靠性的管理是指通过软件错误的避免，软件错误的检测和去除，以及 通过软件项目的资源，进度，表现等手段来优化软件可靠性可靠性的过程。 从上面的定义可以看出软件可靠性的管理分为三方面的活动： 软件错误的避免 一软件错误的检测和去除 支持上述两方面的项目活动 1 2 3 保证软件可靠性的方法 在计算机领域，许多研究方向都与保证软件可靠性相关，包括软件工程，计 算机语言，计算机体系结构，操作系统和计算机安全等研究领域，因此也提出了 各种保证软件可靠性的方法。其中软件工程领域主要研究通过软件工程的方法来 保证软件可靠性，计算机编程语言研究语言的设计，语言对于可靠性的支持以及 程序的分析等，计算机体系结构研究通过体系结构来支持软件调试，操作系统和 计算机安全领域也有许多软件可靠性的研究。 1 3 现有调试技术的不足 经典的软件调试方法采用循环调试技术( c y c l i cd e b u g g i n g ) ，首先在代码片断 设置断点，在给定相同输入的条件下，多次反复运行程序，通过寄存器、变量、 堆栈等跟踪，从而逐步定位错误位置。 对于常规的串行程序，如果只有简单的用户输入即输入仅仅是从文件或 2 浙江大学硕士学位论文 第l 章绪论 键盘读入数据，没有频繁地与系统和外部程序进行数据和控制交互，重放程序的 行为是不难实现的。例如考虑如下程序，如果输入实参0 运行程序，最终将产生“被 0 除 的错误。如果程序用同样的输入再次运行一遍，程序将再次终结于“被0 除的错误。 然而，在实际的应用软件中，包含了大量影响程序运行过程的因素：用户输 入，操作系统调度，进程( 线程) 问通信，时间和随机性等，完全控制这些因素 是十分困难的。伴随而来的问题是，有些b u g 只是间歇性的出现。为此，调试人 员不得不耗费巨大的精力来复现问题，收效却往往甚微【4 】。 1 4 国内外发展现状 为了解决调试过程中b u g 难以重现的问题，需要移除程序执行过程中的不确 定性因素。由此设计了各种各样的被称为执行重放( e x e c u t i o nr e p l a y 1 5 】) 的系统， 他们有各自的优点和局限性。 目前，在软件可靠性工程领域中，对于大型的、复杂的、多任务并发系统而 言，采用重放的方法支持软件调试与故障诊断具有实现成本低、调试效果好等特 点，因而成为研究热点之一，在系统体系结构、操作系统设计、软件工程领域等 方面的国际顶尖会议与知名杂志中，如a s p l o s 、i s c a 、m i c r o 、s o s p 、i c s e 、 p l d i 在近年来，陆续发表了一些研究成果： 一m i c r o s o f t 的d r w a t s o n 【5 】和m o z i l l a 的t a l k b a c k 【6 1 通过采集和分析软件故 障前的系统镜像，通过记录软件执行信息，实现软件故障复现、重放， 有助于软件b u g 的故障诊断。 _ 美国加利福尼亚大学研制的b u g n e t 7 】系统，通过对系统体系结构进行扩 展，并辅助检查点信息记录，实现软件以及共享库执行的精确、连续重 3 浙江大学硕士学位论文第l 章绪论 放与故障重现。 _ 美国密西根大学的t t v m 8 1 系统，在l i n u x 虚拟机基础上，通过记录软件 执行信息，实现对操作系统内核调试过程的断点反向回退、快速前进等 功能，增强了内核调试与排错手段。 - 美国加利福尼亚大学的e x e c r e c o r d e r l 9 1 采用虚拟机的方法，并集成入侵检 测与分析工具，实现了全系统级别的执行过程日志记录、运行重放与故 障恢复功能。 u i u c 的f l a s h b a c k l l 川是一种采用纯软件的方式来实现系统的重放的轻量 级方法。f l a s h b a c k 通过更改操作系统的系统调用和库函数的行为来实现 进程的重放 b e r k e l e y 大学的l i b l o g 1 1 1 系统采用基于用户级共享库插桩的实现方案，用 来调试分布式c c + + 应用程序。它记录应用程序的执行，能够精确重放 竞争条件等不确定性事件，并提供详细的离线分析。 一i n s t a n tr e p l a y 1 2 】是一个精确重放，可以对高度并行的程序进行帮助调试 的一个工具。在程序的执行过程中，该系统按照相关顺序记录下被调试 的程序运行的一些重要事件( 相关的数据并不记载) 。该系统主要适合那 些交互性并不是很强的程序的重放。 但总体而言，执行重放对于软件调试与故障分析支持力度仍较为薄弱，远不 能满足高可靠性软件应用需求。并且现有系统在日志开销方面非常庞大，在技术 上还有很大的发展空间，因而在可见的将来执行重放技术仍将是计算机界的研究 热点之一。 1 5 论文研究背景和内容 本论文属于航天创新基金项目研究内容的一部分，主要研究目标是针对软件 系统中难以调试的故障，探索精细化调试支撑技术，提供较丰富的软件调试与诊 断系统级资源，故障复现与重放，进而，研究复杂软件系统的动态调试、故障定 位与诊断分析的智能化、自动化技术，从而为航天型号软件的研发提供有力的调 4 浙江大学硕士学位论文第l 章绪论 试与诊断支持。 基于虚拟机扩展技术的重放技术不需要修改应用程序与操作系统，因此对于 用户来说可以做到透明。同样由于不需要修改应用程序与操作系统，系统的行为 能够与真实情况下做到尽可能的一致。因而我们采取这种方法来实现系统的重 放，研发了基于检查点的全系统重放系统b b r e p l a y e r ( b o c h s - b a s e dr e p l a y e r ) 。 b b r e p l a y e r 运行于x 8 6 w m d o w s 平台上，通过扩展b o c h s 的体系结构，提供 检查点、记录重放等功能。检查点模块负责保存在某一时刻的系统状态的快照。 在记录阶段，记录重放模块负责记录检查点之后所有影响系统执行的不确定性事 件。重放阶段则利用之前的检查点与日志来重现系统的上一次运行过程。 b b r e p l a y e r 采用增量算法进行检查点的设置，以较小的时间和存储开销实现了系 统状态重构、重现系统运行等功能从而为软件调试和故障诊断提供了有力支撑。 1 6 本文的组织结构 论文共分六章。 第一章“绪论”，分析了提高软件可靠性的重要性，介绍了现有调试技术的 不足，对国内外采用重放的方法支持软件调试与故障诊断的研究现状做了简单介 绍。最后介绍了论文的研究背景和论文的组织结构。 第二章“虚拟平台上的执行重放的总体设计 ，概述了虚拟机技术，检查点 技术以及执行重放技术。 第三章“b b r e p l a y e r 总体结构设计 ，对b o c h s 的体系结构及系统原理做了深 入的剖析，给出了b b r e p l a y e r 的总体设计。 第四章“b b r e p l a y e r 增量型检查点设计与实现”，给出了b b r e p l a y e r 增量型检 查点的实现关键技术及总体架构。 第五章“虚拟平台上的执行重放技术设计与实现”，介绍b b r e p l a y e r 执行重放 技术实现的具体细节。 第六章“总结和展望 ，对全文的工作进行总结，对进一步的工作进行展望。 浙江大学硕士学位论文 第2 章相关技术综述 2 1 执行重放技术 第2 章相关技术综述 2 1 1 概述 记录与重放技术考虑的主要问题是程序的不确定性。一个具有不确定因素的 程序在不同的执行过程中，得到的状态序列可能不同，这给最基本的调试行为 循环调试带来困难。记录与重放的目的就是要保证循环调试的顺利进行。 记录与重放的基本原理是：如果能把一个执行过程完全记录下来，那么就可以 任意次地重复此执行过程。但是，完全记录程序的执行过程需要大量的存储及时间 开销，在实际系统中是最难以做到的。因此，需要作有选择的记录。重放方式有历 史重放和执行重放两种。 ( 1 ) 历史重放( t r a c er e p l a y 1 4 1 ) 它是指把记录的程序状态以某种方式重现出来， 在此重现过程中，可以对状态进行任意查询。由于历史重放并不重新执行程序，因 此重放速度随意可调，还可以跳到任意一点进行观察。历史重放的精确度取决于记 录的精确度。一般而言，历史重放方法以事件模型为基础，程序的执行过程就是一 个不断产生事件的过程，记录这个事件序列，就记录了程序执行的一个抽象过程。 重放也就是这个抽象过程的再现。 ( 2 ) 执行重放( e x e c u t i o nr e p l a y 1 5 1 ) 它是基于这样一个考虑：程序的不确定性行 为是由于其中存在一些不确定性的因素，如果能确定这些不确定性因素的表现，那 么就能确定程序执行的状态序列。这样，如果找出程序中所有不确定因素，并在一 次执行中将它们的表现记录下来，那么我们就有可能以某种方式控制以后的执行， 使得这些不确定因素始终按记录中的方式表现，这样，不记录所有的程序状态，也能 够重放整个执行过程。 执行重放在实现上有顺序重放和内容重放两类执行重放策略。顺序重放给每 个不确定的操作加上时戳，以记录操作间的偏序关系，重放时根据偏序关系确保这 些操作按原来的顺序发生，从而保证重放过程与初始执行过程等价。内容重放是针 对并行程序的某一个进程，把其它进程都看作它的环境。在执行时，记录该进程与 6 浙江大学硕士学位论文 第2 章相关技术综述 环境的所有输入和输出的内容；重放时，该进程的所有输入都从记录中读取。这种 方法的缺点是记录开销较大。 执行重放的基本思想是：监控系统中的各种不确定性事件，并将这些不确定 性事件进行记录，当需要重放时按照原先的时间片准确地模拟这些事情的发生， 从而实现系统的重放。执行重放包括两个阶段，第一个阶段称为记录阶段，重放 系统将不确定事件的信息保存于日志文件中。第二个阶段称为重放阶段，系统重 放不确定性事件，使它呈现出与初次运行相同的效果。 在现代计算机系统中，不确定事件包括如下三类【蚓： 1 ) 外部中断：在计算机系统中，中断用来通知c p u 外部事件的发生。典型 地，中断会修改程序计数器( p c ) 的内容，从而实现控制流的转移。此 外，中断还会改变状态寄存器和其它一些寄存器。中断的发生是异步的， 也就是说程序无法判定何时会发生中断。 2 ) i o 输入内容：很多处理器都有专用的机器指令来获取输入。这些指令与 外围设备( 硬盘、并口、鼠标、键盘、时钟等) 交互。它们通常改变一 个或多个寄存器的内容。外部设备的状态是不确定的，这导致了程序输 入的不确定性。 3 ) 多处理器竞争：在多处理器系统中，每个处理器对共享内存的操作是异 步的。 2 1 2 执行重放的技术分类 针对某个特定的不确定事件，可能有多种重放策略。从机器级的抽象层次看 输入事件是输入指令，例如x 8 6 系统的i n 指令。从程序的角度看系统调用则是另 一种形式的输入事件，因为系统调用的结果不取决与程序的当前状态。输入指令 的结果是由外部设备产生，外部设备不能由软件完全模拟，因此，我们必须记录 输入指令读入的内容。 有两种可行的方法记录输入指令的值：一种是对输入指令插装；另一种方法 是借助处理机的异常处理函数记录硬件输入。 7 浙江大学硕士学位论文 第2 章相关技术综述 系统调用的重放也有两种策略：一种是记录整个系统( 包括操作系统在内) 的状态，然后重放系统的执行；另一种方法是记录系统调用对程序内存的改变， 这样程序可以独立于操作系统进行重放。 通过记录中断发生的时间，然后在重放过程中的相同时间重放中断请求，可 以实现中断的重放。考虑到中断对系统产生的影响( 实现控制流的转移) ，我们 可以从一个更高的抽象层次上重放中断：重放调度。 在多处理机系统中，其它处理器可以通过多种方法干涉当前运行进程的共享 内存。 机器 指令 非确定事件 摹会li 中断 系统 调用 妻插恻蚓i 熬 剥懦ii 磊 记录重 放内存挡 作的顺月 其它处理 器的干涉 多 进程 记录，重 放内存读 的内容 图2 1 基于不确定事件类型的重放技术分类体系 协处 理器 记录重 我内存谤 的内容 多线程：所有处理器执行的代码是相同进程的一部分，为了解决无序的内存 操作产生的不确定性，可以使用基于内容的重放或基于顺序的重放。基于内容的 重放，将会记录所有l o a d 操作的值，这种方法会带来不必要的开销。基于顺序的 重放则只需记录内存操作的顺序。 多进程：其它处理器执行另外的进程。如果其它进程将当前运行进程的某些 8 浙江大学硕士学位论文 第2 章相关技术综述 内存映射到自己的地址空间，那么这些进程都可能改变共享内存。由于内存的改 变可能来源于进程之外，所以只能采用基于内容的重放。 协处理通常用来代替c p u 执行某些特定代码，协处理器操作的内存位置是确 定的，但是相应操作的精确注释并非总是确定的，因此，必须采用基于内容的重 放。 根据上面的分析，可以得出如图2 1 所示的重放技术分类体系。 2 2 检查点技术 2 2 1 检查点技术的分类 检查点是一种作业回溯和恢复的技术，它通过定期的保存作业的运行状态， 可以避免系统发生故障后重新提交作业从开始处运行，从而造成计算资源和时间 的浪费。它是一种重要的软件容错手段，是保证并行系统的高可用性的重要组成 部分。 检查点系统的内部实现机制可以分为两种级别：用户级和系统级。用户级是指 在进程的用户空间进行检查点状态保存恢复操作，主要用于实现内部状态检查和 触发式状态检查：系统级则是指在系统空间完成检查点操作，可用于实现外部状态 检查。 用户级支持的检查点系统功能上要弱于系统级检查点，但是其发展要早于系 统级检查点系统，因为早期检查点系统都是基于不开放源码的通用操作系统而设 计的，设计者们无法在核心中定制功能。这些用户级的设计模式中产生了许多优 秀的设计思想和解决方案，并在一定范围内得到了成功实现和应用。u n i v e r s i t yo f w i s c o n s i nm a d i s o n 的c o n d e r 就是成功的范例，而近年来在分布式资源管理领域 飞速发展起来的加拿大公司p l a t f o r m 也正是采取用户层中间件方式作为检查点的 解决方案。 尽管检查点系统应该是属于操作系统核心的容错子系统，但是由于检查点的 实现要求软件和硬件上都有一定的冗余，而且在机群系统的广泛应用之前，没有 足够的用户需求，所以它一直是各个o s 厂商所忽略的问题之一，系统级的检查 9 浙江大学硕士学位论文第2 章相关技术综述 点系统发展也就相应的晚于用户级检查点系统。随着机群系统的规模扩大和广泛 应用，检查点成为必不可少的技术环节，而用户级实现的检查点系统缺乏通用性， 很大程度上限制了应用程序的范围，这就带来了系统级检查点机制需求。 2 2 2 检查点技术的应用 检查点能够保存恢复程序的运行状态，它在许多领域都有重要的应用 容错分布式系统的故障率随系统机器数的增加而增加，长时间运行的作 业若在每次出现机器故障都从头开始重新执行，该作业将很难被执行完 毕。因此，利用检查点实现多机系统容错成为人们日益关心的热点。 _ 检查点在分布式系统中的一个主要应用是进程迁移1 2 o l 。其过程与单处 理器检查点的设置稍有不同，检查点状态不是被保存到稳定存储器中， 而是被发送给另一个处理器。然后在该处理器上执行恢复过程，并继续 运行，而在发送检查点的处理器上，则立即结束原进程运行。进程迁移 机制广泛应用于分布式系统的负载平衡 在多任务并发系统中，由于程序的执行具有不确定性，使得跟踪程序的 执行过程，确定程序在执行时的状态非常困难。如果上述过程中在适当 的位置设置检查点，则可以将当时的状态记录下来。这样的检查点不仅 可以用于分析，在需要的时候还可以将以前的状态恢复，并重放执行的 过程【3 1 1 。 2 3 虚拟机技术 2 3 1 虚拟机介绍 虚拟机监视器( v m m ) 是一个能够提供计算机硬件完整模拟的软件层，v m m 中创造的系统抽象就称之为虚拟机，它让使用虚拟机的操作系统( g u e s to s ) 认 为自己是直接运行于硬件之上的。v m m 中模拟的计算机硬件要做到跟真机的硬 件尽可能一致，这样应用程序和操作系统就可以在虚拟机透明地运行。v m m 可 以让多个虚拟机能够同时利用所有资源。v m m 起的作用就是提供一种抽象，可 l o 浙江大学硕上学位论文第2 章相关技术综述 以使得多个虚拟实例运行在一个硬件平台上。图2 2 是一般情况下的虚拟机监视 器和虚拟实例的关系图。 v m l a p p l i c a t i o n s g u e s t 0 s 戮黧互 v m m h o s tp l a t f o f i n 图2 2v m m a p p l i c a t i o n s g u e s t0 s ； 黪嬲譬”一 誊釜誊誊毒l 孟_ 础i 篮赫“ 2 3 2 虚拟机的分类 目前商业化和研究型的虚拟机技术大概可以分成三类：完全虚拟化、半虚拟 化、模拟器。 _ 完全虚拟化 完全虚拟化的典型代表产品是v m 3 7 0 和v m w a r e 。i b mv m 3 7 0 最先使用 了虚拟化技术以提供对早期代码的支持。v m w a r e 采用了将常用的p c 硬件进行 虚拟化的方法，允许多个操作系统在同一台主机上运行。所有这些例子都对底层 硬件( 至少是底层硬件的一个子集) 进行了完全虚拟化的实现，而并非是半虚拟化 的方法提供给g u e s to s 一个修改后的接口。完全虚拟化虽然能够更容易地支持商 业版本的操作系统，但是却大大降低了性能。其他常见的完全虚拟化软件包括微 软推出的v i r t u a ls e r v e r 和l i n u x 上的u m l ( u s e rm o d el i n u x ) 。 完全虚拟化技术最大的好处就是可以无需修改操作系统，直接移植到虚拟环 境中，支持多个g u e s to s 。但是完全虚拟化的缺点就是虚拟机的g u e s to s 的系 统性能会受到影响，而且往往比原的系统性能下降不少。尤其是在i a 3 2 等常见 体系结构上。类似v m w a r e 的软件往往性能下降特别严重。 - 半虚拟化 浙江大学硕士学位论文第2 章相关技术综述 因为完全虚拟化往往只能对特定硬件的特点进行虚拟，在虚存管理和设备管 理方面，往往需要花费大量的代码进行处理，这对软件运行的效率必定会产生极 大的影响，同时也增加了虚拟软件层的复杂度。因此，半虚拟化技术也应运而生。 半虚拟化技术通过对操作系统的内核做一定的修改，使得原本一些需要直接通过 c p u 执行的保护任务，可以在修改后的内核中直接执行，这样就有效的提高了虚 拟机的效率。这方面的典型代表就是d e n a l i 和x e n 。 模拟器 模拟器只是读取c p u 指令，对它们指令进行解释，并且模拟执行，保证这些 代码指令的执行效果。模拟器需要模拟硬件的各个寄存器和状态机的状态，往往 会耗费巨大的c p u 开销，严重影响性能。而虚拟化技术，不管是半虚拟化还是完 全虚拟化，都保证虚拟机可以直接执行c p u 指令。对于常规指令，可以像普通 o s 一样顺利执行，而对一些特权指令，则由v m m 虚拟抽象层捕获，负责解释 并执行，达到指令所需的效果。相对于虚拟机而言，模拟器有一个好处就是能够 监控上面运行指令的全部行为，包括指令执行路径，内存的读写，i o 设备的操 作等等，因此在模拟器上做系统资源的扩展可以大大加强系统调试软件的能力。 2 4 本章小结 本章对b b r e p l a y e r 系统实现过程中要用到的执行重放技术、检查点技术、虚 拟机技术展开综述。首先介绍了执行重放技术产生的背景，概述了重放执行技术 的基本思想，通过对现有重放执行技术进行总结，得出了执行重放技术的分类体 系。接着介绍了检查点技术的原理及其在软件可靠性领域的用途。最后介绍了虚 拟机的概念和分类。 1 2 浙江大学硕士学位论文 第3 章b b r e p l a y e r 总体结构设计 第3 章b b r e p l a y e r 总体结构设计 基于检查点的重放系统包含检查点和执行重放两个基本模块。客户机状态的 保存和恢复，虚拟平台上不确定性事件的捕获与重放需要虚拟硬件的支持。本章 将在对b o c h s 体系结构进行详细剖析的基础上，提出b b r e p l a y e r 的总体结构。 3 1b o c h s 体系结构分析 b o c h s 是一种开源且高度可移植的i a 3 2 ( x 8 6 ) p c 模拟器，用c + + 写成，能够 在大部分常见的平台上运行。它包括了对i n t e lx 8 6c p u ，通用i o 设备，和定制 b i o s 的模拟。b o c h s 可以模拟包括3 8 6 ，4 8 6 ，p e n t i u m ，p e n t i u mp r o ，a m d 6 4 等c p u ，包含了m m x ，s s e ，s s e 2 和3 d n o w ! 指令集。b o c h s 可以模拟多种操 作系统的运行，包括l i n u x ，d o s ，w i n d o w s 9 5 9 8a n dw i n d o w s n t 2 0 0 似p 在盘左盘 奇奇o b o c h s 项目是开源项目，遵守g n ul g p l ，并且现由s o u r c e f o r g e 维护，所 以获取b o c h s 项目的源代码和可执行应用程序不需要花费购买费用。另外，基于 b o c h s 调试器功能扩展的研究是纯基于软件的研究，不需要额外的硬件设备支持。 所以，总体而言，研发成本较低。 由于b o c h s 模拟器是对i n t e lx 8 6 体系的全模拟，它通过模拟i n t e rx 8 6 的指 令集实现虚拟机的功能。b o c h s 模拟器的调试器通过模拟的c p u ，m e m o 巧，c a c h e 等获取变量地址、堆栈信息用于调试。它采用的是命令行模式，类似于常用调试 器g d b ，支持逐过程、逐语句的调试、设置断点和寄存器操作等。通过熟悉i n t e lx 8 6 的指令集，分析b o c h s 模拟器的源代码，在原有的调试器功能的基础上添加新的 调试功能是可以实现的。此外，在b o c h s 模拟器自身提供的日志功能的基础上， 通过设计更为高效的轻量级的日志系统，将其与调试器的接口紧密结合，能够实 现高精确度的反向调试功能，包括反向断点的设置，反向逐过程和反向逐行运行。 3 1 1b o e h s 的总体结构 b o c h s 主要由c p u 模型，内存系统，时钟与中断系统，外设模型四部分构成。 浙江大学硕士学位论文 第3 章b b r c p l a y c r 总体结构设计 其中c p u 模型是b o c h s 的核心模块，负责c p u 指令的模拟执行，内存系统则负 责模拟虚拟机的r a m 和r o m 以及虚拟寻址的实现，时钟与中断系统主要控制 外部设备模拟发生的周期以及外部设备中断发生后的通知c p u 的机制。c p u 可 以通过两种手段访问外部设备。一是通过端口读取指令经外设模型直接读取外部 设备的寄存器。二是通过设备的内存映射机制经由内存系统访问到外部设备。外 部设备通过外设模型注册到系统之中后受到时钟与中断系统的控制，在每个c p u 周期中时钟与中断系统都会检查有无外设的模拟周期到达。如果模拟周期到达， 时钟与中断系统就会调用外设的模拟函数。当外部设备完成了模拟并且希望将设 备状态通过中断通知c p u 时，设备就会调用时钟与中断系统来设置c p u 的中断 引脚。各个部分之间的相互关系如图3 1 所示，下面将依次对各个部分进行分析。 图3 i b o c h s 的总体结构图 3 1 2c p u 模型 3 1 2 1c i ) u 模拟的主要流程 b o c h s 启动后，首先对各模拟硬件进行初始化，然后就入进入c p u 的模拟。 1 4 浙江大学硕士学位论文第3 章b b r c p l a y c r 总体结构设计 整个c p u 的模拟由一个大循环构成，依次进行中断处理，取指，译指，执行，四 个阶段。其流程图如图3 2 所示 3 1 2 2 中断处理 图3 2 c p u 模拟的流程图 c p u 的中断处理在每次循环的开头进行，首先检测是否有异步事件发生，如 果有的话就调用h a n d l e a s y n c e v e n t 函数进行处理，在h a n d l e a s y n c e v e n t 函数中会 读取相应的中断向量，并根据c p u 运行模式的不同进行指令流的跳转。 3 123 取指 取指是指根据当前的指令线性地址( c s ：e i p ) 通过计算取得指令在实际主机 上的地址，并最终读取指令的过程。取指的主要流程图3 3 所示，首先由c s ：e i p 浙江大学硕士学位论文第3 章b b r e p l a y e r 总体结构设计 计算获得指令的线性地址，然后再根据线性地址求到指令线性页的基地址和偏 移，线性页的基地址通过转换得到相应的虚拟机物理页的基地址，最终将虚拟机 物理页的基地址计算得到页在主机上的基地址。将页在主机上的基地址与指令在 页内的偏移相加得到指令在主机上的实际地址。 指令线性地址l l a d d r c s + 卜一c p u r i p i t r a n s l a t e _ l i n e a r ( ) ii & o x f f f f f 0 0 0 指令物理地址ip a d d r & o x 仟m 0 0 物理页基地址ip a d dr a 2 0 p a g e g e t h o s t m e m a d d r ( ) 甓慧产ie i p f e t c h p t r 的基地址i 。 。 i a o d d r f f s 曼e a t o g el 线性页基地址l 一一 i a d d r i a d dr p a a e o f f s e t o + e i p b i a s e di 指畜磊磊内 图3 3 取指的流程图 3 124 译指 译指指的是读取指令后，根据c p u 中的指令的格式规范( i a 3 2 6 4 的指令格 1 6 浙江大学硕士学位论文第3 章b b r e p l a y e r 总体结构设计 式规范如图3 4 所示) 来解析指令，得到指令的具体语义信息，这些语义信息被 保存在b xi n s t r u c t i o nc 结构中，每一个b xi n s t r u c t i o nc 实例代表了一条已经译码 后的指令。c p u 模型按照指令的格式得到指令的操作数与操作码，根据不同的操 作码，可以知道当时要运行的是哪条指令，并在b xi n s t u c t i o nc 结构中设定相应 的指令执行函数指针。而对于操作数来说，模拟器将根据指令格式的规范得到操 作数是寄存器还是内存，如果是内存则还需根据不同的内存寻址方式计算得到相 应的地址，最终将操作数的相关信息存入到b xi n s t r u c t i o nc 中供下一步指令执行 时使用。 需要注意的是，在b o c h s 中为了加快指令译码速度对于已经译码完成的指令 做了缓冲，这样当c p u 再次执行到之前的指令时就省去了复杂的译码过程了。 t 助玺口f o u r 1 一，bo f3 铆绝1b y t e 1b y t ea 镌陀豁l m l 豫d 磁e p l r 啤e 敝e s 蝴o f 卿够守嗍搿嘲? 剿嚣铲d 他a t ao 镰f4 脚l i o 嘲) 懒饼黼啪o f f t o f 凳 、 3 1 2 5 执行 图3 4i a 3 2 6 4 指令格式图 指令完成译码后就可以根据译码时所设定的相应指令执行函数指针跳转到 相应的指令执行函数来执行指令了。以一般的算术指令而言，执行函数从译码后 的b x i n s t r u c t i o n _ c 结构中读取到源操作数( 寄存器或内存) ，然后进行相应的 模拟计算，并将结果放入到目标操作数中，并根据运算结果设置相应的状态寄存 器。 浙江大学硕士学位论文第3 章b b r e p l a y e r 总体结构设计 3 1 3 内存系统 3 1 3 1b o c h s 内存系统的结构 b o c h s 内存系统通过在主机上分配一大块内存来模拟虚拟机上的r a m 和r o m ， 如图3 5 所示，分配的内存块的大小为r a m 的大小+ 2 5 6 k 的r o m + 4 0 9 6 。其中最后 增加的4 0 9 6 个字节是为了虚拟机的r a m 的0 地址能够在主机内存中按页对齐而 增加的，目的是为了加快虚拟机上内存的访问速度。因此在a c t u a l v e c t o r 这一 内存块中，第一个按页对齐的地址v e c t o r 就成