并发数据结构与多核编程

课程编码：081202M05002H 英文名称：Concurrent Data Structures and Multicore Programming 课时：40 学分：2.00 课程属性：专业普及课 主讲教师：林惠民等

本课程从原理和实践两方面阐述了面向多核系统的程序设计方法。原理部分（前6章）涵盖并发程序设计的基本原理，重点是介绍经典的互斥问题、并发程序的正确性概念、共享存储器性质以及同步原语等并发程序设计的主要问题。实践部分（7-16章）讲述并发编程的具体方法，重点是分析并发程序的性能，讨论各种类型的同步模式，包括粗粒度锁、细粒度锁及无锁结构，以及并发数据结构的各种实现方法。通过本课程的学习，使学生掌握多核系统编程的基本思想，理解同步原语的表达能力和特性， 熟悉分析和设计各类并发数据结构和并发算法的方法，并能够应用于编程实践中。

离散数学、计算机系统结构、Java编程语言

第一章 绪论 3学时 林惠民
第1节 并发编程
第2节 阿姆达尔法则
第3节 互斥
第4节 LockOne
第二章 互斥算法 3学时 林惠民
第1节 彼得森算法（Peterson’s Algorithm）
第2节 过滤器算法（The Filter Algorithm）
第3节 面包房算法（Bakery Algorithm）
第4节 固有的代价
第三章 并发对象 3学时 林惠民
第1节 先进先出队列
第2节 无等待队列
第3节 顺序对象
第4节 可线性化（Linearizability）
第5节 形式化定义
第6节 可线性化与并发性
第7节 可线性化与顺序一致性
第8节 进展性
第四章 共享内存基础 3学时 吴鹏
第1节 引言
第2节 从安全SRSW布尔寄存器构建原子MRMW多值寄存器
第3节 原子快照
第五章 共识协议和同步操作原语 3学时 吴鹏
第1节 引言
第2节 寄存器和2-线程共识协议
第3节 双出队FIFO队列
第4节 共识数
第5节 多赋值数组
第6节 RMW寄存器（读-修改-写对象）
第7节 compareAndSet同步原语
第8节 通用的共识对象（Universality）
第9节 无锁通用构造
第10节 无等待通用构造
第六章 空转锁和争用 3学时 吴鹏
第1节 引言
第2节 TAS锁和TTAS锁
第3节 回退锁
第4节 队列锁
第5节 CLH队列锁
第6节 MCS队列锁
第7节 超时锁
第8节 总结
第七章 管程和阻塞同步 3学时 吴鹏
第1节 管程（Monitor）
第2节 读-写锁
第3节 可重入锁
第4节 信号量
第八章 链表：锁的应用 3学时 吴鹏
第1节 引言
第2节 集合和链表
第3节 并发推理
第4节 细粒度锁
第5节 乐观锁
第6节 惰性链表
第7节 无锁链表
第8节 性能分析和比较
第九章 并发队列和并发栈 3学时 杨潇潇
第1节 并发队列
第2节 并发栈
第十章 共享计数 3学时 杨潇潇
第1节 软件组合树
第2节 静态一致池和计数器
第3节 计数网
第4节 衍射树
第5节 扁平组合（Flat Combining）
第十一章 并发哈希和固有并行 3学时 杨潇潇
第1节 封闭寻址哈希集
第2节 无锁哈希集
第3节 开放哈希集
第十二章 调度和工作分配 3学时 杨潇潇
第1节 并行度分析
第2节 多处理器的实际调度
第3节 工作分配

林惠民，计算机软件与理论专家。1982年毕业于福州大学计算机系，1986年中国科学院软件所研究生毕业，获博士学位。中国科学院软件研究所研究员。长期从事计算机软件，特别是并发软件的形式语义学及形式化方法的研究。设计并实现了通用进程代数验证工具PAM/VPAM，对这类工具的发展产生了重要影响。与英国Hennessy教授合作提出，并独立发展了“符号互模拟”理论，为在计算机上对传值及移动并发进程进行分析、推理与验证建立了理论基础。曾获1996年中国科学院自然科学奖一等奖和1999年国家自然科学奖二等奖。1999年当选中国科学院院士。
吴鹏，副研究员、硕士生导师。2010年起任职于中国科学院软件研究所计算机科学国家重点实验室。2005年在中国科学院软件研究所获得博士学位（专业：计算机软件与理论），先后在法国巴黎高工从事博士后研究、在英国伦敦大学学院任research associate。2015年赴美国卡内基梅隆大学任访问学者。主要研究兴趣包括：并发理论、并发程序的形式化验证和测试、机器学习等。曾主持、参与多项国家自然科学基金项目、国家重点研发计划项目；在相关领域重要国际会议ATVA、ICECCS和期刊IEEE Transactions on Software Engineering、Information and Software Technology等发表多篇学术论文；曾担任中国科学院大学《多处理器系统编程》、《软件测试与安全分析》和《并发数据结构与多核编程》等课程的主讲教师。
杨潇潇，副研究员。2009年毕业于西安电子科技大学，获得博士学位（专业：计算机应用技术），获校级优秀博士学位论文。2009年在中国科学院软件研究所从事博士后研究。2012年起任职中国科学院软件研究所计算机科学国家重点实验室。2013-2015年获德国洪堡基金会资助成为洪堡学者，在德国亚琛工业大学从事研究工作。主要研究兴趣包括：形式化方法、并发数据结构、并发系统分析与验证等。在相关领域一流国际会议DSN、ICLP和国际知名期刊 Science of Computer Programming, Journal of Logic and Algebraic Programming, Mathematical Structures in Computer Science等发表多篇学术论文；曾于2013年春季担任中国科学院大学《多处理器系统编程》主讲教师。