提纲无锁编程概述动机 : 锁开销影响并行程序扩展性 What/Why/How 无锁编程实例无锁队列无锁编程研究问题事务内存无锁数据结构 2

Size: px

Start display at page:

Download "提纲无锁编程概述动机 : 锁开销影响并行程序扩展性 What/Why/How 无锁编程实例无锁队列无锁编程研究问题事务内存无锁数据结构 2"

川孟
5 years ago
Views:

1 无锁编程简介 An Intro to Lock-free Programming 吕慧伟 ASG 小组讨论班

2 提纲无锁编程概述动机 : 锁开销影响并行程序扩展性 What/Why/How 无锁编程实例无锁队列无锁编程研究问题事务内存无锁数据结构 2

3 Multicore Scaling Process Speedup 1.8x 3.6x 7x User code Multicore Unfortunately, not so simple [Maurice 08] Art of Multiprocessor Programming 3

4 Real-World Scaling Process Speedup 1.8x 2x 2.9x User code Multicore Parallelization and Synchronization require great care [Maurice 08] Art of Multiprocessor Programming 4

5 Asynchrony Sudden unpredictable delays Cache misses (short) Page faults (long) Scheduling quantum used up (really long) [Maurice 08] Art of Multiprocessor Programming 5

6 What: 什么是无锁编程? 如果一个共享数据结构的操作不需要互斥, 那么它是无锁的如果一个进程在操作中间被中断, 其他进程的操作不受影响 [Herlihy 1991] 并行算法同步的分类阻塞同步 (mutex,semaphore,...) 无阻塞同步 [LLF10] 无等待无锁无阻碍 wait-free lock-free obstruction-free 6

7 Why: 为什么要无锁? 性能考虑对一些应用性能更好避免锁的使用引起的错误和问题死锁 : 两个以上进程互等结束 Convoy : 多个进程反复竞争同一个锁, 抢占锁失败后强制上下文切换引起性能下降优先级反转 : 低优先级进程拥有锁时被抢占 7

8 How: 如何无锁? 方法 : 像事务一样操作 [DRD08], 知道谁拥有数据不同进程对私有数据更新互相隔离提交操作是原子的 : 或者成功, 或者丢弃一致性 : 确保从一个状态变到另一状态工具 : 原子指令使用注意点无锁算法要求从硬件并行的角度考虑算法设计通用无锁算法很困难, 一般只设计无锁的数据结构 8

9 提纲无锁编程概述无锁编程实例单生产者单消费者 FIFO : 不需要原子指令多生产者多消费者 FIFO : 原子指令无锁堆栈 ABA 问题无锁编程研究问题 9

10 Lamport's Lock-Free Ring Buffer [Lamport, Comm. of ACM, 1977] Operate on control variables: read and write, which resp. point to next read and write slots write read N-1 0 NEXT(x) = (x + 1) % N Insert(T element) 1: wait until NEXT(write)!= read 2: buffer[write] = element 3: write = NEXT(write) Extract(T* element) 1: wait until read!= write 2: *element = buffer[read] 3: read = NEXT(read) slide taken from [Lee10] 10

11 CAS(cmpxchg) slide taken from [CS380D] 11

12 多生产者多消费者 FIFO void enq(request, queue) { do{ local_head = queue->head; request->next = queue->head; val = cmpxchg(&queue->head, local_head, request); }while(val!= local_head) } 事务操作状态 Atomic & Consistency: cmpxchg Isolation: 私有数据 12

13 多生产者多消费者 FIFO void enq(request, queue) { do{ local_head = queue->head; request->next = queue->head; val = cmpxchg(&queue->head, local_head, request); }while(val!= local_head) } 事务操作状态 1 2 如果在执行 cmpxchg 时, queue->head == local_head 即在 1, 2 之间没有进程将 queue->head 更改了则 request 赋给了 queue->head 否则, 上述过程将重新进行

14 无锁堆栈 struct elem { elem *link any data; } elem *qhead; Push (elem *x) do old = qhead; x->link = old; new = x; cc = CAS(qhead, old, new); until (cc == old;) Pop () do old = qhead; new = old->link; cc = CAS(qhead, old, new); until (cc == old;) return old; 14

15 ABA 问题 A B C thread 1: pop() thread 2: pop() pop() push(a) 正确执行 : pop(); pop(); push(a); pop(); C pop(); pop(); pop(); push(a); A 15

16 ABA 问题 A B C pop() ret = A; next = B; // interrupted CAS(A,A,B) A = A B 16

17 ABA 问题 A B C pop() ret = A; next = B; // interrupted CAS(A,A,B) pop() ret = A; next = B; CAS(A,A,B) A = A A = A B B 17

18 ABA 问题 B C // interrupted CAS(A,A,B) pop() ret = B; next = C; CAS(B,B,C) return B; 18

19 ABA 问题 C // interrupted CAS(A,A,B) push(a) A->next = C; CAS(C,C,A) 19

20 ABA 问题 A // resumes CAS(A,A,B) C A = A B 20

21 ABA 问题 Bx // resumes CAS(A,A,B) 21

22 version number slide taken from [CS380D] 22

23 提纲无锁编程概述无锁编程实例无锁编程研究问题无锁数据结构 Transactional Memory 23

24 事务内存 Transactional Memory 24

为什么叫 Transactional Memory 从 Database 的核心概念 Transaction 借鉴 Database 一次 Transaction 过程 1. Begin the transaction 2. Execute several data manipulations and queries 3.

25 为什么叫 Transactional Memory 从 Database 的核心概念 Transaction 借鉴 Database 一次 Transaction 过程 1. Begin the transaction 2. Execute several data manipulations and queries 3. If no errors occur then commit the transaction and end it 4. If errors occur then rollback the transaction and end it ACI 特征 ( Atomicity, Consistency, Isolation ) Transaction State

26 Transactional Memory [TM M.K.] 1977 Lomet ( 发现一种 ) 保证共享数据的抽象机制 1993 Herlihy and Moss, ISCA Transactional Memory - architectural support for lock-free data structures 支持无锁数据结构的机制 ISCA, HPCA, PPoPP, PODC... Challenge: to build an efficient TM infrastructure

27 Herlihy and Moss, ISCA 1993 coined the term Transactional Memory 增加 6 种新指令供程序员构建无锁数据结构 load-transactional: 读数据到私有寄存器 [TM M.K.] load-transactional-exclusive: 读数据到私有寄存器, 如果 cache-miss, 请求数据所有权 store-transactional : 写到内存 (cache) 但其他进程在 commit 之前不可见 commit: 提交内存更改 abort: 丢弃写更改 validate: 查询当前事务状态

28 Herlihy and Moss, ISCA 1993 [TM M.K.] 处理器状态 flag 6 条新指令 : load-transactional, loadtransactional-exclusive, storetransactional, commit, abort, and validate. 新增一个 T Cache 缓存 TM 操作新的 3 个 bus 周期

29 Transactional Memory [TM M.K.] TM 如何解决线程级并行? 程序员把计算 wrap 成 transaction 不是万能药, 但是把同步操作从程序员转移到编译器运行环境和硬件目前主要的信心来自 transaction 解决了数据库的问题尚没有用 TM 来解决一般的并行编程问题目前还只是语义级别的 TM 定义 ( 尚没有编译器运行环境库的支持 ) TM 会和非 TM 的代码并存很长一段时间 TM 的成功取决于旧代码和新代码的无缝结合

30 小结无锁编程可以避免使用锁的一些常见错误, 并有可能带来性能提高设计通用的无锁算法很难, 目前常见的有一些无锁的数据结构无锁的数据结构要求按照事务处理的方式编程事务内存是对无锁的支持, 目前研究很热, 难点在于有效的实现 30

31 参考资料 [DRD08]Dr Dobbs, Writing Lock-Free Code: A Corrected Queue, [LLF10] 杨小华, 透过 Linux 内核看无锁编程, ux/l-cn-lockfree/ [Maurice 08]Maurice Herlichy and Nir Shavit, The Art of Multiprocessor Programming [TM M.K.] James R. Larus and Ravi Rajwar, Transactional Memory, published by Morgan Kaufman 31

32 参考资料 [Herlihy 1991]Maurice Herlihy, Wait-free Synchronization,1991 [NSYNC]Nonblocking synchronization bibliography, [Langdale05]Geoff Langdale, Lock-Free Programming, s05/lectures/l31_lockfree.pdf [Lee10]Patrick P.C. Lee, A Lock-Free, Cache-Efficient Multi-Core Synchronization Mechanism for Line-Rate Network Traffic Monitoring 32

33 参考资料 [CS380D]Wait-Free Synchronization Lecture, CS380D Distributed Computing, The University of Texas at Austin 33

A Preliminary Implementation of Linux Kernel Virus and Process Hiding

A Preliminary Implementation of Linux Kernel Virus and Process Hiding 邵俊儒翁健吉妍年月日学号学号学号摘要结合课堂知识我们设计了一个内核病毒该病毒同时具有木马的自动性的隐蔽性和蠕虫的感染能力该病毒获得权限后会自动将自身加入内核模块中劫持的系统调用并通过简单的方法实现自身的

提纲 无锁编程概述 动机 : 锁开销影响并行程序扩展性 What/Why/How 无锁编程实例 无锁队列 无锁编程研究问题 事务内存 无锁数据结构 2

提纲无锁编程概述动机 : 锁开销影响并行程序扩展性 What/Why/How 无锁编程实例无锁队列无锁编程研究问题事务内存无锁数据结构 2