计算机论文哪里有？本文通过实验验证所提数据结构和算法的可行性和有效性，同时利用理论分析数据结构和算法的正确性，但是由于时间和实验条件所限制，本文提出的数据结构和算法都存在一些缺陷有待改进。
第一章 绪论
1.2 国内外研究现状
上个世纪 70 年代以来，半导体技术的迅速发展使得处理器的运算速度不断提高，但从2005 年开始，由于功耗和散热等问题的加剧，提升处理器运算速度的步伐趋缓，摩尔定律遭遇挑战，处理器的发展趋势由单核转向多核。多核处理器在同一芯片内集成多个完全功能的核心，整个芯片作为一个整体对外提供计算服务，使得整个处理器可同时执行的线程数是单核处理器的数倍[2]。多核处理器的发展给数据结构的设计和使用带来了革命性变化，利用多线程技术提升程序的运行速度更加具有现实意义。多核处理器的广泛使用对主流软件开发也产生巨大影响，原有公共库中的数据结构和程序可能不具备伸缩性，程序开发者需要重新设计并实现支持并行的数据结构和程序，只有这样才能够利用多核处理器带来软件性能的提升。
最初使用各类线程锁实现数据同步，例如 POSIX 线程的 pthread_mutex、Windows API的 CreateMutex，以及读写锁和条件变量等。但是基于锁的同步往往伴随着性能缺陷以及数据竞争和死锁等问题，简单的粗粒度锁不具备伸缩性，不能发挥多核处理器的计算能力，而复杂的细粒度锁不仅实现复杂，而且容易产生死锁等严重问题，同时可能随着处理器核数的增加性能逐渐降低，不具备良好的伸缩性[5]。最近几十年以来，无锁数据结构一直是热门研究课题，使用 CAS 同步原语的无锁数据结构能够摆脱基于锁同步产生的数据竞争和死锁等问题，更重要的是无锁数据结构具备较好的伸缩性，可以充分发挥多核处理器的性能。
第三章 基于 FAA 的无锁队列 DQueue 设计及实现 ............................ 10
3.1 相关工作
由于在计算机领域的广泛应用，并行 FIFO 队列是目前热门研究课题[28]。Michael 等[29]提出的无锁队列 MS-Queue 被认为是经典的非阻塞队列[30]。MS-Queue 是一个维护头指针和尾指针的单链表，通过重试循环(Retry Loop)原子指令 CAS 执行入队和出队操作。在争用激烈的情况下，大多数 CAS 操作将失败，因此 MS-Queue 伸缩性不佳，不能在高并发环境下高效运行。Morrison 等将此称为 CAS 重试问题[31](Retry Problem)。David[32]提出的 SPSC 型无等待队列需要无限内存空间。SPSC 型队列 FastForward[33]用来提高流水线并行应用程序的性能，使用时间滑动避免缓存抖动和硬件缓存预取。然而，实际应用中滑动需要特定于系统的调优，并且通过访问队头索引和队尾索引触发抖动。
Kogan 等[7]基于 MS-Queue 提出了第一个真正意义的无等待队列。为了实现无等待，该队列使用一种基于优先级的帮助方案，速度较快的线程帮助速度较慢的线程完成操作。由于帮助机制的开销，大多数情况下该队列性能不佳。Kogan 等[34]提出了快路径-慢路径(fast-path-slow-path)方法，用于创建实用的无等待对象。由于无锁算法具备良好的性能，通常作为快路径；无等待算法的每个方法在有限步骤内完成，因此作为慢路径。每个操作尝试几次快路径，如果都失败则使用慢路径。采用这种方法的无等待队列使用 MS-Queue 作为其快路径，它的性能只和 MS-Queue 一样好。
第五章 基于 CCF 和 DQueue 的消息队列设计与实现
5.1 概述
许多数据库、路由器和存储系统使用近似集成员关系测试[59]来判定给定数据项是否在一个集合中，同时附带较低的假阳性[60](False Positive)概率。由于 Bloom 过滤器[61]存储效率比较高，因此广泛应用于该测试。过滤器常用于减少概率路由表所需空间[62]，完善网络状态管理和监控[63]，以及许多其他应用[64]。
标准 Bloom 过滤器[61]支持查询和插入两种操作，以及一个可调的假阳性概率，查询返回“肯定不是”或“可能是”。假阳性概率越低，过滤器所需的空间开销就越大。Counting Bloom过滤器[65]扩展Bloom过滤器以支持删除操作，使用计数器数组代替位数组导致空间开销巨大。
Blocked Bloom 过滤器[66]是由一系列小的 Bloom 过滤器组成，每个小 Bloom 过滤器大小与 CPU 缓存行一致。每个数据项存储在由散列函数确定的小 Bloom 过滤器中，每个查询最多导致一个缓存未命中，提高了查询性能。与 Bloom 过滤器一样，Blocked Bloom 过滤器也不支持删除操作。d-left Counting Bloom 过滤器[67]使用 d-left 哈希表[68]存储数据项的指纹，通过删除指纹来删除数据项。商过滤器[69](Quotient Filters)是支持删除操作的紧凑哈希表，使用类似于线性探测的技术来定位指纹，从而提供更好的空间局部性，但是每个数据项需要编码和解码，产生额外的时间和空间开销。
相比于标准 Bloom 过滤器，Fan 等[70]利用 Cuckoo 哈希表实现的 Cuckoo 过滤器不仅支持删除操作且空间开销低。Cuckoo 过滤器使用一种称为不完整键值(partial-key)Cuckoo 哈希技术实现动态地插入和删除元素。
5.2 消息队列设计
消息队列(CCF and DQueueBased Message Queue, CDMQ)主要是由两部分构成，无锁队列DQueue 和并发 Cuckoo 过滤器(Concurrent Cuckoo Filter, CCF)。CCF 的基本数据结构与 Cuckoo哈希表相似，设置两个哈希函数，分别记作 和 。插入元素时，每个元素有两个候选哈希桶，查询元素时，检查对应的两个哈希桶是否存储该数据项。由于 CDMQ 是基于 CCF和 DQueue 的消息队列，因此，多个生产者向队列并发写入数据，消费者读取数据前使用 CCF对数据进行过滤，如果数据通过过滤检验，则消费者读取该数据，否则丢弃该数据。
5.2.1 CCF设计
标准 Bloom 过滤器不支持删除操作，虽然有几种方法拓展了 Bloom 过滤器，但会导致额外的时间和空间开销。相比标准 Bloom 过滤器，Fan[70]提出的 Cuckoo 过滤器更加紧凑，查询效率更高，但是由于 Cuckoo 哈希表固有特征，写入操作的开销很大。因此根据第四章基于CAS 的 Cuckoo 哈希表提出并发 Cuckoo 过滤器 CCF。本节描述并发 Cuckoo 过滤器 CCF 执行插入、查询和删除操作的过程。
(1)插入操作：如第四章所述，在标准 Cuckoo 哈希表中，向哈希表写入新项需要一些访问已有项的方法，以便为新项腾出空间时将已有项迁移到备用位置。然而，Cuckoo 过滤器只存储指纹，因此无法重新哈希原始密钥以找到备用位置。本文使用不完整键值 Cuckoo 哈希技术，根据指纹推导数据项的备用位置。
(2)查询操作：并发 Cuckoo 过滤器 CCF 的查询过程如算法 5.2 所示。给定一个数据项 x，首先根据公式(5.1-5.3)计算 x 的指纹 f 和两个候选桶的索引号 和 ，然后读取这两个桶，如果任意一个桶中存在匹配的指纹，那么返回 true，否则返回 false。
(3)删除操作：并发 Cuckoo 过滤器 CCF 通过删除相应的指纹来删除插入的数据项，如算法 5.3 所示。检查给定数据项的两个候选桶，如果在任何桶中存在匹配的指纹，则从该桶中删除匹配指纹的一个副本。
第六章 总结与展望
6.2 研究展望
本文通过实验验证所提数据结构和算法的可行性和有效性，同时利用理论分析数据结构和算法的正确性，但是由于时间和实验条件所限制，本文提出的数据结构和算法都存在一些缺陷有待改进。下面列举几个方面的内容并加以讨论。
(1)本文提出的基于 FAA 的无锁队列 DQueue，为了减少写缓冲区频繁刷新使用普通访问语句代替昂贵的原子指令，但是该方案建立在 DQueue 是 MPSC 型队列的基础上，需要进一步研究使之能够应用在 MPMC 型队列或者哈希表上。
(2)本文提出的基于 CAS 的负载均衡 Cuckoo 哈希表 LBCHT，为了实时限制每个桶的负载率，需要计算哈希表整体负载率以及每个桶存储的数据量，该方案大量使用原子指令降低了哈希表的效率，需要进一步研究降低算法的时间开销。
(3)本文提出的基于 CAS 的局部性良好 Cuckoo 哈希表使用了 2 个哈希函数，且桶的大小为 4，当负载率较低时正向查询效率有一定的提升，但是当哈希表负载率较高时正向查询效率会降低，需要进一步改进算法，提升 Cuckoo 哈希表查询效率。
(4)本文提出的基于 CCF 和 DQueue 的消息队列 CDMQ，CDMQ 是将无锁数据结构 DQueue和 CCF 实践应用的原型，CDMQ 需要进一步改进其功能才能够获得实际应用。
(5)本文的实验具有局限性，由于条件的限制，使用随机生成的整数进行实验，与真实场景下的数据存在差异，实验结果也有所差异。将来可以继续改进本文提出的数据结构和算法，并将它们应用到真实环境中，以便对其进行更加完善的测试与评估。
参考文献（略）
