第 1 章 绪论
1.1 研究背景与意义
多核时代的到来给数据结构的设计和使用方式带来巨大的变化。随着多核处理器的普遍使用，高并发数据结构变得越来越重要[1]。并发数据结构是现代多核处理器的基础组成部分，是影响软件性能高低的重要因素之一。
由于多核处理器的普遍使用以及众核处理器设计技术的兴起给软件研发带来了新的挑战，为了充分发挥多核/众核处理器的性能，研发人员必须编写可扩展的并发程序才能使其在多核环境下具有高的性能。而编写可扩展程序的关键在于使用高并发的数据结构。研发人员在整个编写过程中要以弹性思维的方式考虑宏观与微观两个方面的问题，从而在这两个方面都达到相对理想的效果，然后采用程序设计模型、语言和工具开发新的软件；并发程序不仅可以使程序的运行时间变短，执行效率变高，而且能够将多核处理器的性能优势展现出来[2]。多线程的方式被现代操作系统普遍采用来提高并发，本文无锁二叉搜索树算法的数据结构设计以多线程并发为模型，完成异步共享内存系统下的各种操作。
针对并发程序编写存在的一个重要的问题是多个线程对共享资源的同步访问问题[4]。在并发数据结构中，多个线程通过共享内存中的数据来进行通信和同步。Java语言中有两种同步机制：锁和原子操作。锁的使用存在以下缺点：1) 容易导致锁竞争问题。由于竞争导致程序串行执行，程序运行效率降低，并损害程序的可伸缩性；2) 容易导致死锁和活锁的问题。它们会引起线程的等待，从而使程序的执行效率降低。而原子操作是不会被线程的任何其它任务或事件而中断的操作，不仅可以防止加锁操作产生的问题，更重要的是可以使程序的性能得到提升，有效避免线程之间的冲突[5]。
为了解决上述问题，提高并发程序的性能。研究人员提出了无锁的方法，其中二叉搜索树(BST)的实现最具有代表性。从目前研究现状来看，基于共享内存的并发树形数据结构已成为研究人员关注的热点，并且进行了深入的研究，但仍存在一些问题，例如使用诸如 CAS 的标准原语实现无锁二叉搜索树的数据结构，效率不高。所以本文主要针对无锁二叉搜索树的算法进行研究，实现对二叉搜索树的搜索、插入和删除等并发操作，并保证其正确性。该算法可以提高程序的运行效率，能够有效的避免线程之间发生冲突，降低线程之间发生阻塞的机率，解决了多线程对数据资源的竞争以及死锁的问题。
.........................
3.1 实现原理概述 ···················· 171.1 研究背景与意义
多核时代的到来给数据结构的设计和使用方式带来巨大的变化。随着多核处理器的普遍使用，高并发数据结构变得越来越重要[1]。并发数据结构是现代多核处理器的基础组成部分，是影响软件性能高低的重要因素之一。
由于多核处理器的普遍使用以及众核处理器设计技术的兴起给软件研发带来了新的挑战，为了充分发挥多核/众核处理器的性能，研发人员必须编写可扩展的并发程序才能使其在多核环境下具有高的性能。而编写可扩展程序的关键在于使用高并发的数据结构。研发人员在整个编写过程中要以弹性思维的方式考虑宏观与微观两个方面的问题，从而在这两个方面都达到相对理想的效果，然后采用程序设计模型、语言和工具开发新的软件；并发程序不仅可以使程序的运行时间变短，执行效率变高，而且能够将多核处理器的性能优势展现出来[2]。多线程的方式被现代操作系统普遍采用来提高并发，本文无锁二叉搜索树算法的数据结构设计以多线程并发为模型，完成异步共享内存系统下的各种操作。
针对并发程序编写存在的一个重要的问题是多个线程对共享资源的同步访问问题[4]。在并发数据结构中，多个线程通过共享内存中的数据来进行通信和同步。Java语言中有两种同步机制：锁和原子操作。锁的使用存在以下缺点：1) 容易导致锁竞争问题。由于竞争导致程序串行执行，程序运行效率降低，并损害程序的可伸缩性；2) 容易导致死锁和活锁的问题。它们会引起线程的等待，从而使程序的执行效率降低。而原子操作是不会被线程的任何其它任务或事件而中断的操作，不仅可以防止加锁操作产生的问题，更重要的是可以使程序的性能得到提升，有效避免线程之间的冲突[5]。
为了解决上述问题，提高并发程序的性能。研究人员提出了无锁的方法，其中二叉搜索树(BST)的实现最具有代表性。从目前研究现状来看，基于共享内存的并发树形数据结构已成为研究人员关注的热点，并且进行了深入的研究，但仍存在一些问题，例如使用诸如 CAS 的标准原语实现无锁二叉搜索树的数据结构，效率不高。所以本文主要针对无锁二叉搜索树的算法进行研究，实现对二叉搜索树的搜索、插入和删除等并发操作，并保证其正确性。该算法可以提高程序的运行效率，能够有效的避免线程之间发生冲突，降低线程之间发生阻塞的机率，解决了多线程对数据资源的竞争以及死锁的问题。
.........................
1.2 国内外研究现状
由于传统的数据结构（如链表、堆栈等）简单、研究时间长，已经完成无锁并发数据结构的设计。但是针对数据结构中更高级别的研究（如无等待并发的实现），因为研究难度大，正处于初步阶段。因此，近年来研究人员逐渐开始对并发树形结构进行研究。
由于传统的数据结构（如链表、堆栈等）简单、研究时间长，已经完成无锁并发数据结构的设计。但是针对数据结构中更高级别的研究（如无等待并发的实现），因为研究难度大，正处于初步阶段。因此，近年来研究人员逐渐开始对并发树形结构进行研究。
Fraser 采 用 MCAS(multiword compare-and-swap) 操 作 的 方 式 完 成 非 阻 塞BST(Binary Search Tree)结构的设计，因为 MCAS 操作并不支持所有的硬件系统，因此该结构的应用范围很小[9]。Bronson 提出了一种并发平衡二叉树的数据结构，该二叉树结构采用乐观并发的技术，通过控制版本号进行冲突的辨别：若操作冲突，则算法从根节点重新执行；反之，操作结束[10]。Afek 等人实现自调整二叉搜索树的算法[11]。Crain 等人采用 STM(Software Transactional Memory)技术完成红黑树算法的设计，由于程序员不用考虑多线程并发的同步问题，所以它的实现使无阻塞编程的难度变得相对简单[12]。但是，STM 的开销比较大，它的性能很容易被非阻塞的二叉树结构超过。
Barnes 提出一种合作帮助技术，它是一种将基于锁定的实现转换为非阻塞实现的方法[13]。Ellen 等人首次提出基于 Barnes 合作帮助技术的无锁二叉搜索树算法[14]。他们的算法使用外部（或面向叶）搜索树，只用叶节点来存储实际的键值，删除时只需对叶节点以及父节点进行删除处理。Howley 和 Jones 基于类似的技术提出一种无锁定的面向节点的 BST；他们算法的搜索操作比 Ellen 等人算法的搜索操作更快，
因为通常搜索路径在面向节点的 BST 中比在面向叶的 BST 中更短[15]。算法操作是将待移除节点的后继节点移动到待移除节点，若后继节点只有一个孩子，则将其移除，反之，保留其节点。Natarajan 和 Mittal 提出了一种无锁面向叶 BST，它标记的是边缘而不是节点[16]。他们的算法比以前的方法更高效，因为突变操作在树的较小部分上并且执行较少的原子指令。
Drachsler 等人改进了二叉树中的查找操作（主要指的是需要对节点进行定位），
主要使用的是逻辑有序(Logical Ordering)的方式，它可以把插入等操作当中的查找行为以及查询操作当中的查找行为分开，从而使查找操作的执行速度变快，进而提高其执行效率。以二叉搜索树算法的研究为前提，Brown 等人扩大了研究的范围，进行了多叉树(K-ary Tree)的研究，并重点针对多核环境下的范围查找问题进行了详细的探讨，实验数据表明在查找范围不是很大时，使用 CAS 操作方式会比其他方式效果更好。
...........................
第 2 章 并发数据结构理论基础
2.1 并发数据结构
数据结构的设计和使用方法因多核处理器的遍及产生巨大的变化，因而具有多线程访问的快速高效以及在高负载环境下的可扩展能力特点的数据结构变得至关重要。为了更清楚的了解数据结构的应用功效，应该对并发的数据结构进行详细的研究，以便对数据结构进行更好地应用。
数据结构是一种存储和组织数据的方法，以便线程可以访问并对数据进行有效地修改。由于在多核环境下可以在不同的内核中执行多个线程，因此并发数据结构必须同时处理多个数据的访问和修改。这可以通过使用同步机制实现对共享数据结构的访问。
数据结构是计算机学科算法和软件设计的基础，数据结构的知识在计算机范围内应用广泛，一般涉及程序的地方都会用到[36]。集合、线性、树形和图状四类是数据结构的基本形式，而树形结构在客观世界的应用更为普遍，如社会中的家族关系和组织关系都可用树形结构进行展现[37]。树形结构在计算机领域的涉及范围也很广泛，例如树用在编译程序中展现源程序的语法结构；在数据库系统中信息的重要展现方式之一便是树形结构。
............................
2.2 并发数据结构的技术原理
2.2.1 基于锁的实现
基于锁的实现(lock-based)是目前多核并发编程中采用最为广泛的技术。这种技术在堆栈队列、哈希表等简单数据结构中得到了广泛的应用[38]。当多线程并发访问共享资源时，基于锁的技术能够使共享资源的数据不被多个线程访问和修改，保证了线程的安全。因而操作系统中广泛运用一些特殊设计的锁(如：自旋锁(spinlock)、读写锁(readwritelock))。
下面以自旋锁为例进行说明。使用自旋锁的线程会始终进行新的尝试直到获取锁进入临界区。自旋锁的本质是进行互斥操作的 0/1 变量，如图 2-1 所示，线程调用Lock方法尝试进入临界区，若失败则进行新的尝试直到成功或者超时退出；Unlock方法进行锁状态的重置。因此，同一时刻只能有一个内核任务拥有自旋锁，临界区中也只存在一个线程。
虽然基于锁的技术在简单数据结构中得到广泛的应用，但在多核的树形数据结构设计中实现效果不是很好。基于锁的实现对树中的节点进行加锁操作，同时在共 享区只能有一个线程进行操作以确保证共享数据的安全，在一定程度上会对并发的更新操作产生影响，降低了数据结构的高并发性。
........................
第 3 章 无锁二叉搜索树算法 ···················· 17
...........................
第 2 章 并发数据结构理论基础
2.1 并发数据结构
数据结构的设计和使用方法因多核处理器的遍及产生巨大的变化，因而具有多线程访问的快速高效以及在高负载环境下的可扩展能力特点的数据结构变得至关重要。为了更清楚的了解数据结构的应用功效，应该对并发的数据结构进行详细的研究，以便对数据结构进行更好地应用。
数据结构是一种存储和组织数据的方法，以便线程可以访问并对数据进行有效地修改。由于在多核环境下可以在不同的内核中执行多个线程，因此并发数据结构必须同时处理多个数据的访问和修改。这可以通过使用同步机制实现对共享数据结构的访问。
数据结构是计算机学科算法和软件设计的基础，数据结构的知识在计算机范围内应用广泛，一般涉及程序的地方都会用到[36]。集合、线性、树形和图状四类是数据结构的基本形式，而树形结构在客观世界的应用更为普遍，如社会中的家族关系和组织关系都可用树形结构进行展现[37]。树形结构在计算机领域的涉及范围也很广泛，例如树用在编译程序中展现源程序的语法结构；在数据库系统中信息的重要展现方式之一便是树形结构。
............................
2.2 并发数据结构的技术原理
2.2.1 基于锁的实现
基于锁的实现(lock-based)是目前多核并发编程中采用最为广泛的技术。这种技术在堆栈队列、哈希表等简单数据结构中得到了广泛的应用[38]。当多线程并发访问共享资源时，基于锁的技术能够使共享资源的数据不被多个线程访问和修改，保证了线程的安全。因而操作系统中广泛运用一些特殊设计的锁(如：自旋锁(spinlock)、读写锁(readwritelock))。
下面以自旋锁为例进行说明。使用自旋锁的线程会始终进行新的尝试直到获取锁进入临界区。自旋锁的本质是进行互斥操作的 0/1 变量，如图 2-1 所示，线程调用Lock方法尝试进入临界区，若失败则进行新的尝试直到成功或者超时退出；Unlock方法进行锁状态的重置。因此，同一时刻只能有一个内核任务拥有自旋锁，临界区中也只存在一个线程。
虽然基于锁的技术在简单数据结构中得到广泛的应用，但在多核的树形数据结构设计中实现效果不是很好。基于锁的实现对树中的节点进行加锁操作，同时在共 享区只能有一个线程进行操作以确保证共享数据的安全，在一定程度上会对并发的更新操作产生影响，降低了数据结构的高并发性。
........................
第 3 章 无锁二叉搜索树算法 ···················· 17
3.2 无锁算法 ·············· 20
第 4 章 无锁二叉搜索树的正确性证明 ·················· 31
4.1 结构不变性 ················ 31
4.2 无锁和无等待性的证明 ················ 33
4.3 无锁二叉搜索树的线性化 ····················· 35
第 5 章 无锁二叉搜索树的实现和实验分析 ············· 37
5.1 实验环境与工具 ················· 37
5.2 无锁二叉搜索树的实现 ···················· 38
5.3 实验数据分析 ······················ 39
第 5 章 无锁二叉搜索树的实现和实验分析
5.1 实验环境与工具 实验设置：本文在一台处理器Intel(R) Core(TM)i7-3630QM CPU @ 2.40GHz 机器上进行实验，该处理器 8 个内核，每个处理核均支持超线程，8GB RAM，基于x64的处理器。在软件方面，使用 64 位Windows 7 操作系统，JDK版本：1.8.0_144。
本文的无锁二叉搜索树算法是使用 Eclipse 工具实现的。Eclipse 是一款基于 Java语言编写的集成开发环境(Integrated Development Environment，IDE)，本质上，它由框架和一组服务构成，通过插件组件的方式完成开发环境的构建。虽然它本身拥有的用户功能比较少，但它能够采用插件的方式完成具备的功能，Eclipse 包括一个标准的插件集，以及 Java 开发工具(Java Development Kit，JDK)，其拥有开放的源码，非常易于扩展。
本文的无锁二叉搜索树算法是使用 Eclipse 工具实现的。Eclipse 是一款基于 Java语言编写的集成开发环境(Integrated Development Environment，IDE)，本质上，它由框架和一组服务构成，通过插件组件的方式完成开发环境的构建。虽然它本身拥有的用户功能比较少，但它能够采用插件的方式完成具备的功能，Eclipse 包括一个标准的插件集，以及 Java 开发工具(Java Development Kit，JDK)，其拥有开放的源码，非常易于扩展。
Java 编程的基本工具包 JDK(Java Development Kit)是提供开发、运行 Java 程序的基本软件，它支持 Windows 等平台的使用。涵盖了 Java 运行环境(Java Runtime Environment)、工具以及基本的类库。
下面介绍 Java 程序的开发步骤：
1) 程序的编辑：通过选定适合的文本编辑器编写 java 代码到扩展名为.java 的文件里面。
2) 程序的编译：采用 javac.exe 的编译工具对 java 源文件进行编译，生成扩展名为.class 的字节码文件。
3) 程序的运行：成功编译的字节码文件调用 java.exe 运行工具执行。
..........................
下面介绍 Java 程序的开发步骤：
1) 程序的编辑：通过选定适合的文本编辑器编写 java 代码到扩展名为.java 的文件里面。
2) 程序的编译：采用 javac.exe 的编译工具对 java 源文件进行编译，生成扩展名为.class 的字节码文件。
3) 程序的运行：成功编译的字节码文件调用 java.exe 运行工具执行。
..........................
结论
随着多核处理器时代的到来，并发数据结构的研究备受关注。同时给数据结构的设计和使用方式带来巨大的变化。可扩展的并发程序才能在多核环境下具有高的性能。近年来，该领域的学者做出许多研究成果。由于树的应用范围比较广泛，并发树形结构的实现是该领域最为关注的研究方向，本文提出了一种新颖而且实用的无锁外部二叉搜索树算法，并通过实验进行验证和分析，证明该算法的性能更好，
随着多核处理器时代的到来，并发数据结构的研究备受关注。同时给数据结构的设计和使用方式带来巨大的变化。可扩展的并发程序才能在多核环境下具有高的性能。近年来，该领域的学者做出许多研究成果。由于树的应用范围比较广泛，并发树形结构的实现是该领域最为关注的研究方向，本文提出了一种新颖而且实用的无锁外部二叉搜索树算法，并通过实验进行验证和分析，证明该算法的性能更好，
更具有竞争力，并且该并发 BST 算法是线性化的，能有效的避免线程之间发生冲突和死锁，以及多线程对数据资源的竞争问题。本文的主要工作如下：
1) 本文采用无锁 CAS 技术实现二叉搜索树的搜索、插入以及删除的操作，并给出详细的算法原理和实现的细节描述。
2) 本文对无锁二叉搜索树算法的正确性进行了证明。指出了该算法在并发环境下满足结构不变性，是可线性化的。
3) 本文对编写的算法进行实验，与 Bronson 等人基于锁的算法，Ellen 等人基于无锁的算法做了非常详细的对比。实验表明，当争用很高（树大小或工作负载不同）时，本文的算法明显优于其他两种并发 BST 算法，其性能更好，更具有竞争力。同时还进行了有锁与无锁性能对比实验，通过比较，无锁编程一定范围内比有锁编程更有优势，更有力地说明了本文采用无锁方式的正确性。
参考文献（略）
2) 本文对无锁二叉搜索树算法的正确性进行了证明。指出了该算法在并发环境下满足结构不变性，是可线性化的。
3) 本文对编写的算法进行实验，与 Bronson 等人基于锁的算法，Ellen 等人基于无锁的算法做了非常详细的对比。实验表明，当争用很高（树大小或工作负载不同）时，本文的算法明显优于其他两种并发 BST 算法，其性能更好，更具有竞争力。同时还进行了有锁与无锁性能对比实验，通过比较，无锁编程一定范围内比有锁编程更有优势，更有力地说明了本文采用无锁方式的正确性。
参考文献（略）