并发数据结构及其在动态内存管理中的应用

摘要

随着多核处理器越来越广泛的应用，软件如何改变传统的串行设计理念以适应并发的挑战正变得越来越紧迫。作为应用程序基础的数据结构首当其冲，如何在保证数据结构正确性的同时提供更高的并发度和扩展性成为研究人员关注的重点问题。在这种情况下，无锁数据结构应运而生。无锁数据结构摆脱了锁的限制，能够避免优先级反转问题并承受线程的随机故障退出，提供了更高的并发度和更好的扩展性。但是，无锁数据结构所要应对的是由多核处理器引入的更多的并发线程，以及随之而来的更大数量的动态内存消耗和对运行时动态内存分配器的更加频繁的访问，容易在高并发情况下形成瓶颈。
　　本文从负载均衡的角度考察无锁数据结构相关的动态内存管理问题，将其抽象成“逆向”负载均衡问题，基于负载均衡的思想提出了两种并发队列并将这两种队列用作线程本地缓冲区构建了两种供无锁数据结构使用的内存池，来解决无锁数据结构的动态内存管理问题，具体工作如下：
　　①分析了并发数据结构领域的历史和现状，对该领域的各种常用技术和结构做了研究，指出了各自相对的优缺点和在多核时代面临的挑战。
　　②对共享内存多核处理器环境下的并发内存管理做了总结，分析了该领域的几种通用技术，指出了研究人员对于无锁数据结构动态内存管理问题特殊性的忽略，提出了用内存池解决无锁数据结构的动态内存管理问题。
　　③介绍了负载均衡思想在计算机系统任务调度领域的应用，分析了任务窃取和任务分担这两种常用的调度策略，研究了几种任务窃取相关数据结构的原理、设计和实现，并用负载均衡的思想将无锁数据结构的动态内存管理问题抽象为“逆向”均衡问题，提出用负载均衡的方法解决该问题。
　　④提出了两种支持窃取和/或归还操作的并发队列，并在这两种队列的基础上分别构建了两种供无锁数据结构使用的内存池。这两种内存池可以在运行时通过在线程本地缓冲区之间执行窃取和/或归还操作以实现内存资源在各线程间的均匀分布，以改善无锁数据结构的性能。
　　⑤将本文提出的两种内存池和普通内存池分别应用于无锁数据结构，并对它们的性能作了详细的测量和对比，证明本文提出的两种内存池的各个指标在广泛的并发水平下均明显优于普通内存池，同时，还通过实验测量并证明了窃取和归还这两个均衡操作的有效性。

目录

封面

中文摘要

英文摘要

目录

1 绪 论

1.1 概述

1.2 研究内容及主要贡献

1.3论文组织结构

2 研究背景

2.1 并发数据结构及多核时代

2.2 共享内存多核处理器环境下的动态内存管理

2.3 负载均衡及资源均衡的动机

2.4 本章小结

3 无锁资源窃取队列及无锁资源窃取内存池

3.1 无锁资源窃取队列

3.2 无锁资源窃取内存池

3.3 证明

3.4 本章小结

4 资源窃取与归还队列及资源均衡内存池

4.1 资源窃取队列（ Resource Stealing-Returning Queue ， NSRQueue）

4.2 资源均衡内存池（Resource Balancing Memory Pool，NSRPool）

4.3 证明

4.4 本章小结

5 实验结果及分析

5.1 实验方法及环境

5.2 集成方法

5.3 内存消耗

5.4 操作执行时间

5.5 平衡结果

5.6 本章小结

6 总结和展望

6.1 研究工作总结

6.2 未来展望

致谢

参考文献

附录

A 作者在攻读学位期间发表的论文