学位论文 > 优秀研究生学位论文题录展示

多线程复制系统的确定性调度框架MDSF的研究与实现

作　者: 张昱
导　师: 马严
学　校: 北京邮电大学
专　业: 计算机科学与技术
关键词: 多线程复制确定性静态分析代码转换 MDSF
分类号: TP311.52
类　型: 硕士论文
年　份: 2009年
下　载: 27次
引　用: 0次
阅　读: 论文下载

内容摘要

复制是分布式系统中容错的一种重要方法。多线程复制能够很好的利用多核CPU、多CPU资源,但也面临着如何保证确定性的问题。现有的几种多线程调度算法都在一定程度上支持多线程运行,但都采取了保守的方式来避免多线程所带来的不确定性,从而影响了多线程同步性的提高。本文在分析现有几种多线程调度算法之后,基于MAT算法提出改进算法—AMAT算法,该算法需要根据多线程运行期间提供的同步操作信息来对多线程进行调度。本文提出代码分析、转换的方式来达到这一目的。同时,代码分析、转换还能够完成对同步语句的截获,从而透明地完成非复制代码到复制代码的转换。这种方法可以避免修改底层操作系统、虚拟机所带来的复杂性,也不要求编程人员手动修改代码。本文提出一种多线程复制系统的确定性调度框架—MDSF,由两大部分组成:一个是在预编译阶段的代码分析模块和代码转换模块,另一个是运行时的线程调度模块。前者能够对多线程程序的源代码进行分析,并且根据分析结果修改源代码。修改过的源代码在编译之后部署到运行环境中,并与实现了AMAT算法的调度模块进行交互,调度模块会对多线程进行统一调度。经测试证明,该调度框架支持现有非复制代码的重用,并能实现多线程的高效调度。

全文目录

摘要  4-5
ABSTRACT  5-9
第一章概述  9-16
  1.1 研究背景  9-12
    1.1.1 复制  9-10
    1.1.2 对象复制  10-11
    1.1.3 多线程复制及确定性  11-12
  1.2 研究现状  12-14
    1.2.1 算法研究现状  12-13
    1.2.2 代码截获现状  13-14
  1.3 本文工作  14
  1.4 论文结构  14-16
第二章 MDSF框架  16-22
  2.1 框架简介  16-17
  2.2 系统模型  17-19
    2.2.1 通信模型  17
    2.2.2 同步模型  17-18
    2.2.3 同步机制细节  18-19
  2.3 同步操作的截获  19-22
第三章线程调度模块  22-39
  3.1 现有的确定性调度算法  22-24
    3.1.1 顺序请求执行算法(SRE)  22-23
    3.1.2 单一活动线程算法(SAT)  23
    3.1.3 松散同步算法(LSA)  23
    3.1.4 抢占确定性调度算法(PDS)  23-24
    3.1.5 多重活动线程算法(MAT)  24
  3.2 MAT算法详解  24-27
    3.2.1 数据结构  24-25
    3.2.2 算法细节  25-27
  3.3 MAT算法缺点  27-30
    3.3.1 最后锁定的释放  28-30
    3.3.2 无冲突锁  30
  3.4 AMAT算法  30-39
    3.4.1 算法前提  31
    3.4.2 算法思想  31-33
    3.4.3 确定性保证  33-34
    3.4.4 算法优点  34
    3.4.5 锁参数的分析  34-39
第四章代码分析、转换目标  39-47
  4.1 调度模块接口  39-42
  4.2 简单示例  42-44
  4.3 分析、转换思路  44-47
    4.3.1 入口方法  44-45
    4.3.2 目标方法  45
    4.3.3 同步操作  45
    4.3.4 锁参数的预测  45-47
第五章代码分析模块  47-61
  5.1 静态代码分析  47-49
    5.1.1 方法调用关系图  47
    5.1.2 数据流分析  47-49
  5.2 Soot简介  49-52
    5.2.1 基本的实体类  49-50
    5.2.2 CallGraph类  50-51
    5.2.3 数据流分析框架  51-52
  5.3 工作流程  52-53
  5.4 实现细节  53-61
    5.4.1 数据结构  53-56
    5.4.2 方法实现  56-61
第六章代码转换模块  61-69
  6.1 Eclipse AST简介  61-64
    6.1.1 AST类  62
    6.1.2 ASTNode类  62-63
    6.1.3 ASTVisitor类  63
    6.1.4 ASTRewrite类  63-64
  6.2 工作流程  64
  6.3 实现细节  64-69
第七章测试结果  69-77
  7.1 功能测试  69-71
    7.1.1 代码分析、转换模块功能测试  69-70
    7.1.2 线程调度模块功能测试  70-71
  7.2 线程调度模块性能测试  71-73
    7.2.1 测试用例  71
    7.2.2 测试结果  71-72
    7.2.3 结果分析  72-73
  7.3 代码分析模块性能测试  73-74
    7.3.1 测试用例  73-74
    7.3.2 测试结果  74
    7.3.3 结果分析  74
  7.4 代码转换模块性能测试  74-77
    7.4.1 测试用例  75
    7.4.2 测试结果  75
    7.4.3 结果分析  75-77
第八章总结和展望  77-79
  8.1 论文总结  77
  8.2 下一步工作  77-79
参考文献  79-81
致谢  81-82
攻读学位期间发表的学术论文目录  82

多线程复制系统的确定性调度框架MDSF的研究与实现

内容摘要

全文目录

相似论文