基于无锁算法的并行协议栈任务分配优化

论文摘要

随着多核处理器架构的发展和普及,越来越多的硬件平台使用多核处理器作为处理单元。协议栈作为网络处理核心却没有达到与之匹配的效率。如何将协议栈中的重要模块针对多核处理器的特点进行并行化改造以提高网络性能是本文的主要研究内容。并行数据结构技术是多核技术中的一个研究热点,其中的无锁算法以低开销和非阻塞的特点而备受关注。本文在对协议栈和多核环境下的多线程编程进行了简单介绍后,阐述了无锁编程的基本原理和方法。随后以FreeBSD协议栈实现为基础,对连接级别并行和数据包级别并行模型,使用无锁算法进行优化。针对连接级别并行方式的特点,本文使用单生产者-单消费者无锁队列算法消除了任务队列的头指针和尾指针的耦合关系,降低了队列相关操作的开销,同时减少了线程阻塞带来的开销。针对数据包级别并行方式的特点,本文对PCB队列的锁粒度进行了改进,并使用MS-queue算法改进PCB下的任务队列。经仿真测试,在负载均衡情况下,连接级别并行比数据包级别并行效率高7%；在负载不均衡的情况下,数据包级别并行能够自行调节任务调度达到更高的效率。经过优化后,两种并行方法都达到了约3.6的加速比。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景和现状
• 1.1.1 协议栈的起源
• 1.1.2 无锁算法的发展与现状
• 1.1.3 协议栈优化现状
• 1.2 研究的目的和意义
• 1.3 本文工作与结构
• 第二章 协议栈并行化基础
• 2.1 协议栈的基本概念
• 2.1.1 OSI模型与TCP/IP模型
• 2.1.2 主要协议原理
• 2.2 FREEBSD协议栈简介
• 2.3 无锁编程基础
• 2.3.1 多核架构带来的问题
• 2.3.2 多线程编程基础
• 第三章 无锁算法
• 3.1 单消费者-单生产者无锁队列算法实现
• 3.1.2 并发环境下的队列
• 3.1.2 无锁算法实现
• 3.2 MS-QUEUE算法设计与实现
• 3.2.1 MS-queue算法基础:CAS原子操作
• 3.2.2 MS-queue算法设计
• 3.2.3 MS-queue算法实现
• 第四章 协议栈优化方法设计
• 4.1 数据包级别的并行方法设计
• 4.2 连接级别并行方法设计
• 4.3 非并行优化
• 第五章 性能测试与分析
• 5.1 实验平台及主要数据
• 5.1.1 实验的硬件平台和软件平台
• 5.1.2 主要数据
• 5.2 基于消息传递的实现与测试
• 5.2.1 方法描述
• 5.2.2 测试数据生成说明
• 5.2.3 测试结果与分析
• 5.3 基于共享地址空间的实现与测试
• 5.3.1 共享地址空间编程与无锁队列
• 5.3.2 连接级别并行方法实现
• 5.3.3 数据包级别并行方法实现
• 5.3.4 测试结果与分析
• 前景展望
• 致谢
• 参考文献