精华内容
下载资源
问答
  • 深入理解并行编程pdf

    2018-07-22 20:39:00
    深入理解并行编程》首先以霍金提出的两个理论物理限制为引子,解释了多核并行计算兴起的原因,并从硬件的角度阐述并行编程的难题。接着,《深入理解并行编程》以常见的计数器为例,探讨其不同的实现方法及适用场景...

    下载地址:网盘下载

    《深入理解并行编程》首先以霍金提出的两个理论物理限制为引子,解释了多核并行计算兴起的原因,并从硬件的角度阐述并行编程的难题。接着,《深入理解并行编程》以常见的计数器为例,探讨其不同的实现方法及适用场景。在这些实现方法中,除了介绍常见的锁以外,《深入理解并行编程》还重点介绍了RCU的使用及其原理,以及实现RCU的基础:内存屏障。最后,《深入理解并行编程》还介绍了并行软件的验证,以及并行实时计算等内容。
    《深入理解并行编程》适合于对并行编程有兴趣的大学生、研究生,以及需要对项目进行深度性能优化的软硬件工程师,特别值得一提的是,《深入理解并行编程》对操作系统内核工程师也很有价值。
    Paul E. McKenney is the core contributor of Linux kernel .
    下载地址:网盘下载

    转载于:https://www.cnblogs.com/cf1774575641/p/9351318.html

    展开全文
  • 原文的下载地址:...中文版下载地址:深入理解并行编程V1.0(4.1M) 本书是linux内核大牛paul的力作,和鲁阳同学一起,花了两个月时间进行翻译。 目前没有翻译问答部分,主要是时间不够,也担心不能将这部分...

    原文的下载地址:http://kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html
    中文版下载地址:深入理解并行编程V1.0 (4.1M)

    本书是linux内核大牛paul的力作,和鲁阳同学一起,花了两个月时间进行翻译。
    目前没有翻译问答部分,主要是时间不够,也担心不能将这部分翻译准确。
    对内核深度发烧的同学可以看看。

    本书目录

    1. 简介…………………………………………………………………………………………… 14

    1.1. 导致并行编程困难的历史原因……………………………………………… 14

    1.2. 并行编程的目标…………………………………………………………………… 15

    1.2.1. 性能………………………………………………………………………………. 16

    1.2.2. 生产率…………………………………………………………………………… 17

    1.2.3. 通用性…………………………………………………………………………… 18

    1.3. 并行编程的替代方案……………………………………………………………. 20

    1.3.1. 顺序应用多实例化…………………………………………………………. 20

    1.3.2.使用现有的并行软件……………………………………………………… 21

    1.3.3. 性能优化……………………………………………………………………….. 21

    1.4. 是什么使并行编程变得复杂?……………………………………………… 22

    1.4.1. 工作分割……………………………………………………………………….. 22

    1.4.2. 并行访问控制………………………………………………………………… 23

    1.4.3. 资源分割和复制…………………………………………………………….. 24

    1.4.4. 与硬件交互……………………………………………………………………. 24

    1.4.5. 组合使用……………………………………………………………………….. 24

    1.4.6. 语言和环境如何对这样的任务进行支持?……………………… 25

    1.5. 本书导读……………………………………………………………………………… 25

    1.5.1. 小问题…………………………………………………………………………… 25

    1.5.2. 随书源码……………………………………………………………………….. 26

    2. 硬件的习性………………………………………………………………………………… 28

    2.1. 概述…………………………………………………………………………………….. 28

    2.1.1. CPU流水线 …………………………………………………………………… 29

    2.1.2. 内存引用……………………………………………………………………….. 30

    2.1.3. 原子操作……………………………………………………………………….. 31

    2.1.4. 内存屏障……………………………………………………………………….. 32

    2.1.5. Cache Miss …………………………………………………………………….. 33

    2.1.6. I/O操作 ………………………………………………………………………… 34

    2.2. 开销…………………………………………………………………………………….. 35

    2.2.1. 硬件体系结构………………………………………………………………… 36

    2.2.2. 操作的开销……………………………………………………………………. 37

    2.3. 硬件的免费午餐? …………………………………………………………………. 38

    2.3.1. 3D集成 …………………………………………………………………………. 39

    2.3.2. 新材料和新工艺…………………………………………………………….. 39

    2.3.3. 专用加速器……………………………………………………………………. 39

    2.3.4. 现有的并行软件…………………………………………………………….. 40

    2.4. 软件设计Implication ……………………………………………………………. 40

    3. 工具…………………………………………………………………………………………… 43

    3.1. 脚本语言……………………………………………………………………………… 43

    3.2. POSIX多进程 ……………………………………………………………………… 44

    3.2.1. POSIX进程创建和撤销 …………………………………………………. 44

    3.2.2. POSIX线程的创建和撤销 ……………………………………………… 46

    3.2.3. POSIX锁 ………………………………………………………………………. 48

    3.2.4. POSIX读写锁 ……………………………………………………………….. 52

    3.3. 原子操作……………………………………………………………………………… 55

    3.4. Linux内核中类似POSIX的操作 …………………………………………. 56

    3.5. 趁手的工具——该如何选择?……………………………………………… 58

    4. 计数…………………………………………………………………………………………… 59

    4.1. 为什么并发计数不可小看?…………………………………………………. 60

    4.2. 统计计数器………………………………………………………………………….. 62

    4.2.1. 设计………………………………………………………………………………. 62

    4.2.2. 基于数组的实现…………………………………………………………….. 62

    4.2.3. 结果一致的实现…………………………………………………………….. 64

    4.2.4. 基于每线程变量的实现………………………………………………….. 66

    4.2.5. 讨论………………………………………………………………………………. 69

    4.3. 近似上限计数器…………………………………………………………………… 69

    4.3.1. 设计………………………………………………………………………………. 69

    4.3.2. 简单的上限计数器实现………………………………………………….. 70

    4.3.3. 关于简单上限计数器的讨论…………………………………………… 76

    4.3.4. 近似上限计数器的实现………………………………………………….. 76

    4.3.5. 关于近似上限计数器的讨论…………………………………………… 77

    4.4. 精确上限计数器…………………………………………………………………… 77

    4.4.1. 原子上限计数器的实现………………………………………………….. 77

    4.4.2. 关于原子上限计数器的讨论…………………………………………… 86

    4.4.3. Signal-Theft上限计数器的设计 ……………………………………… 86

    4.4.4. Signal-Theft上限计数器的实现 ……………………………………… 87

    4.4.5. Signal-Theft上限计数器讨论 …………………………………………. 94

    4.5. 特殊的并行计数器……………………………………………………………….. 95

    4.6. 并行计数的讨论…………………………………………………………………… 96

    5. 分割和同步设计……………………………………………………………………….. 100

    5.1. 分割练习……………………………………………………………………………. 100

    5.1.1. 哲学家就餐问题…………………………………………………………… 100

    5.1.2. 双端队列……………………………………………………………………… 102

    5.1.3. 关于分割问题示例的讨论…………………………………………….. 111

    5.2. 设计准则……………………………………………………………………………. 111

    5.3. 同步粒度……………………………………………………………………………. 113

    5.3.1. 串行程序……………………………………………………………………… 114

    5.3.2. 代码锁…………………………………………………………………………. 116

    5.3.3. 数据锁…………………………………………………………………………. 117

    5.3.4. 数据所有权………………………………………………………………….. 120

    5.3.5. 锁粒度与性能………………………………………………………………. 121

    5.4. 并行快速路径…………………………………………………………………….. 121

    5.4.1. 读写锁…………………………………………………………………………. 122

    5.4.2. 层级锁…………………………………………………………………………. 123

    5.4.3. 资源分配器缓存…………………………………………………………… 125

    5.5. 性能总结……………………………………………………………………………. 131

    6. 锁…………………………………………………………………………………………….. 132

    6.1. 生存(staying alive) …………………………………………………………. 133

    6.1.1. 死锁…………………………………………………………………………….. 133

    6.1.2. 活锁…………………………………………………………………………….. 136

    6.1.3. 不公平…………………………………………………………………………. 137

    6.1.4. 低效率…………………………………………………………………………. 137

    6.2. 锁的类型……………………………………………………………………………. 137

    6.2.1. 互斥锁…………………………………………………………………………. 138

    6.2.2. 读写锁…………………………………………………………………………. 138

    6.2.3. Beyond Reader-Writer Locks …………………………………………. 138

    6.3. 基于锁的存在担保(existence guarantee) ………………………….. 138

    7. 数据所有者………………………………………………………………………………. 140

    8. 延迟处理………………………………………………………………………………….. 142

    8.1. 屏障…………………………………………………………………………………… 142

    8.2. 引用计数……………………………………………………………………………. 142

    8.2.1. 引用计数类型的实现……………………………………………………. 143

    8.2.2. 支持引用计数的Linux原语 …………………………………………. 150

    8.2.3. 计数器优化………………………………………………………………….. 151

    8.3. Read-Copy Update(RCU)………………………………………………… 151

    8.3.1. RCU基础 ……………………………………………………………………. 151

    8.3.2. RCU用法 ……………………………………………………………………. 163

    8.3.3. Linux内核中的RCU API……………………………………………… 176

    8.3.4. “玩具式”的RCU实现 ……………………………………………… 183

    8.3.5. RCU练习 ……………………………………………………………………. 206

    9. 使用RCU ………………………………………………………………………………… 207

    9.1. RCU和基于每线程变量的统计计数器 ……………………………….. 207

    9.1.1. 设计…………………………………………………………………………….. 207

    9.1.2. 实现…………………………………………………………………………….. 207

    9.1.3. 讨论…………………………………………………………………………….. 211

    9.2. RCU和可移除I/O设备的计数器 ……………………………………….. 211

    10. 验证:调试及分析……………………………………………………………………. 214

    11. 数据结构………………………………………………………………………………….. 216

    12. 高级同步………………………………………………………………………………….. 218

    12.1. 避免锁……………………………………………………………………………….. 218

    12.2. 内存屏障……………………………………………………………………………. 218

    12.2.1. 内存序及内存屏障…………………………………………………. 218

    12.2.2. 如果B在A后面, 并且C在B后面, 为什么C不在A后面? 220

    12.2.3. 变量可以拥有多个值……………………………………………… 221

    12.2.4. 能信任什么东西? …………………………………………………… 222

    12.2.5. 锁实现回顾……………………………………………………………. 229

    12.2.6. 一些简单的规则…………………………………………………….. 230

    12.2.7. 抽象内存访问模型…………………………………………………. 230

    12.2.8. 设备操作……………………………………………………………….. 233

    12.2.9. 保证………………………………………………………………………. 233

    12.2.10. 什么是内存屏障? …………………………………………………… 234

    12.2.11. 锁约束…………………………………………………………………… 247

    12.2.12. 内存屏障示例………………………………………………………… 248

    12.2.13. CPU ………………………………………………………………………. 251

    12.2.14. 哪里需要内存屏障? ……………………………………………….. 253

    12.3. 非阻塞同步………………………………………………………………………… 253

    12.3.1. 简单 NBS ……………………………………………………………… 253

    12.3.2. 冒险指针……………………………………………………………….. 253

    12.3.3. 原子数据结构………………………………………………………… 253

    12.3.4. “Macho” NBS………………………………………………………… 253

    13. 易于使用………………………………………………………………………………….. 254

    13.1. Rusty Scale for API Design ………………………………………………….. 254

    13.2. Shaving the Mandelbrot Set ………………………………………………….. 255

    14. 时间管理………………………………………………………………………………….. 258

    15. 未来的冲突………………………………………………………………………………. 259

    15.1. 可交易内存………………………………………………………………………… 259

    15.1.1. I/O 操作 ……………………………………………………………….. 260

    15.1.2. RPC 操作 ……………………………………………………………… 260

    15.1.3. 内存映射操作………………………………………………………… 261

    15.1.4. 多线程事务……………………………………………………………. 262

    15.1.5. 外部的事务访问…………………………………………………….. 263

    15.1.6. 延时………………………………………………………………………. 264

    15.1.7. 锁………………………………………………………………………….. 264

    15.1.8. 读者-写者锁 ………………………………………………………….. 265

    15.1.9. 持续性…………………………………………………………………… 266

    TM如何提供类似的持续性功能?……………………………………………………….. 266

    15.1.10. 动态链接装载………………………………………………………… 266

    15.1.11. 调试………………………………………………………………………. 267

    15.1.12. exec() 系统调用…………………………………………………….. 268

    15.1.13. RCU ……………………………………………………………………… 268

    15.1.14. 讨论………………………………………………………………………. 270

    15.2. 共享内存并行编程……………………………………………………………… 270

    15.3. 基于任务的并行编程………………………………………………………….. 270

    A. 重要问题………………………………………………………………………………….. 271

    A.1 “after“的含义是什么? …………………………………………………………. 271

    B. 同步原语………………………………………………………………………………….. 277

    B.1 初始化……………………………………………………………………………….. 277

    B.1.1 smp_init() …………………………………………………………………….. 277

    B.2 线程创建、销毁及控制………………………………………………………. 278

    B.2.1 create_thread() ……………………………………………………………… 278

    B.2.2 smp_thread_id() ……………………………………………………………. 278

    B.2.3 for_each_thread() ………………………………………………………….. 278

    B.2.4 for_each_running_thread() …………………………………………….. 279

    B.2.5 wait_thread() ………………………………………………………………… 279 深入理解并行编程

    B.2.6 wait_all_threads() …………………………………………………………. 279

    B.2.7 用法示例……………………………………………………………….. 279

    B.3 锁………………………………………………………………………………………. 280

    B.3.1 spin_lock_init() …………………………………………………………….. 280

    B.3.2 spin_lock() …………………………………………………………………… 280

    B.3.3 spin_trylock() ……………………………………………………………….. 281

    B.3.4 spin_unlock() ……………………………………………………………….. 281

    B.3.5 用法示例……………………………………………………………….. 281

    B.4 每线程变量………………………………………………………………………… 281

    B.4.1 DEFINE_PER_THREAD() ……………………………………………. 282

    B.4.2 DECLARE_PER_THREAD() ………………………………………… 282

    B.4.3 per_thread() ………………………………………………………………….. 282

    B.4.4 __get_thread_var() ………………………………………………………… 282

    B.4.5 init_per_thread() …………………………………………………………… 282

    B.4.6 用法示例……………………………………………………………….. 282

    B.5 性能…………………………………………………………………………………… 283

    C. 为什么使用内存屏障………………………………………………………………… 284

    C.1 Cache 结构………………………………………………………………………… 284

    C.2 缓存一致性协议…………………………………………………………………. 286

    C.2.1 MESI 状态 ………………………………………………………………….. 286

    C.2.2 MESI 协议消息 …………………………………………………………… 287

    C.2.3 MESI状态图 ……………………………………………………………….. 288

    C.2.4 MESI 协议示例 …………………………………………………………… 289

    C.3 不必要的存储延迟……………………………………………………………… 291

    C.3.1 Store Buffers ………………………………………………………………… 291

    C.3.2 Store Forwarding ………………………………………………………….. 292

    C.3.3 存储缓冲区及内存屏障………………………………………….. 293

    C.4 不必要的存储延迟……………………………………………………………… 296

    C.4.1 无效队列……………………………………………………………….. 296

    C.4.2 使无效队列及使无效应答………………………………………. 296

    C.4.3 无效队列及内存屏障……………………………………………… 297

    C.5 读和写内存屏障…………………………………………………………………. 300

    C.6 内存屏障示例…………………………………………………………………….. 300

    C.6.1 乱序体系结构………………………………………………………… 300

    C.6.2 示例 1 …………………………………………………………………… 301 深入理解并行编程

    C.6.3 示例 2 …………………………………………………………………… 302

    C.6.4 示例 3 …………………………………………………………………… 303

    C.7 特定CPUs的内存屏障指令 ……………………………………………….. 304

    C.7.1 Alpha …………………………………………………………………………… 306

    C.7.2 AMD64 ……………………………………………………………………….. 308

    C.7.3 ARMv7-A/R ………………………………………………………………… 309

    6 ISB();………………………………………………………………………………………………… 309

    C.7.4 IA64 ……………………………………………………………………………. 309

    C.7.5 PA-RISC ………………………………………………………………………. 310

    C.7.6 POWER / Power PC ……………………………………………………… 310

    C.7.7 SPARC RMO, PSO, and TSO ………………………………………… 311

    C.7.8 x86………………………………………………………………………………. 312

    C.7.9 zSeries …………………………………………………………………………. 313

    C.8 内存屏障是永恒的? ……………………………………………………………. 313

    C.9 对硬件设计者的建议………………………………………………………….. 314

    D. RCU实现 ………………………………………………………………………………… 315

    D.1 可睡眠 RCU 实现 ……………………………………………………………… 315

    D.1.1 SRCU 实现原理 ………………………………………………………….. 316

    D.1.2 SRCU API 及用法 ……………………………………………………….. 317

    D.1.3 实现………………………………………………………………………. 320

    D.1.4 SRCU 概述 …………………………………………………………………. 326

    D.2 分级 RCU 概述 ………………………………………………………………… 326

    D.2.1 RCU 基础回顾 ……………………………………………………………. 326

    D.2.2 经典 RCU 实现概要 ……………………………………………… 327

    D.2.3 RCU 迫切要解决的问题 ………………………………………………. 328

    D.2.4 可扩展RCU 实现 ………………………………………………….. 329

    D.2.5 迈向不成熟的RCU 实现 ……………………………………….. 332

    D.2.6 状态机…………………………………………………………………… 334

    D.2.7 用例………………………………………………………………………. 335

    D.2.8 测试………………………………………………………………………. 340

    D.2.9 结论………………………………………………………………………. 345

    D.3 分级 RCU代码走查 …………………………………………………………… 346

    D.3.1 数据结构及内核参数……………………………………………… 346

    D.3.2 外部接口……………………………………………………………….. 354

    D.3.3 初始化…………………………………………………………………… 362 深入理解并行编程

    D.3.4 CPU 热插拨 ………………………………………………………………… 367

    D.3.5 杂项函数……………………………………………………………….. 372

    D.3.6 Grace-Period检测函数 …………………………………………………. 373

    D.3.7 Dyntick-Idle 函数 ………………………………………………………… 385

    D.3.8 强制静止状态………………………………………………………… 390

    D.3.9 CPU-延迟检测 …………………………………………………………….. 397

    D.3.10 可能的缺陷及变更…………………………………………………. 400

    D.4 可抢占 RCU ……………………………………………………………………… 400

    D.4.1 RCU概念 ……………………………………………………………………. 401

    D.4.2 可抢占RCU算法概述 …………………………………………… 402

    D.4.3 验证可抢占 RCU …………………………………………………… 419

    E. 形式验证………………………………………………………………………………….. 422

    E.1 什么是 Promela 和 Spin? ………………………………………………….. 422

    E.2 Promela 示例: 非原子性递增 …………………………………………….. 423

    E.3 Promela 示例: 原子递增 ……………………………………………………. 426

    E.3.1 组合…………………………………………………………………………….. 427

    E.4 如何使用 Promela ……………………………………………………………… 428

    E.4.1 Promela 特性 ………………………………………………………………. 428

    E.4.2 Promela编程技巧 ………………………………………………………… 429

    E.5 Promela 示例: 锁 ………………………………………………………………. 430

    E.6 Promela 示例: QRCU …………………………………………………………. 433

    E.6.1 运行 QRCU 示例 ……………………………………………………….. 438

    E.6.2 到底需要多少读者和写者? …………………………………………… 439

    E.6.3 可选方法: 正确性校验 …………………………………………………. 439

    E.6.4 可选方法: 更多工具 …………………………………………………….. 440

    E.6.5 可选方法: 分而治之 …………………………………………………….. 440

    E.7 Promela Parable: dynticks 和可抢占 RCU …………………………… 440

    E.7.1 可抢占 RCU 和 dynticks介绍 …………………………………….. 441

    E.7.2 验证可抢占RCU和dynticks ………………………………………… 445

    E.7.3 回顾…………………………………………………………………………….. 466

    E.8 简单的避免形式校验………………………………………………………….. 467

    E.8.1 简单Dynticks 接口的状态变量 ……………………………………. 467

    E.8.2 进入和退出Dynticks-Idle 模式…………………………………….. 468

    E.8.3 从Dynticks-Idle 模式进入NMIs ………………………………….. 469

    E.8.4 Interrupts From Dynticks-Idle Mode ……………………………….. 470

    E.8.5 检查Dynticks 静止状态 ………………………………………………. 471

    E.8.6 讨论…………………………………………………………………………….. 473

    E.9 概要…………………………………………………………………………………… 473

    F. 问题答案………………………………………………………………………………….. 474

    G. 术语表……………………………………………………………………………………… 475

    H. 感谢…………………………………………………………………………………………. 476


    文章转自 并发编程网-ifeve.com

    展开全文
  • 深入理解并行编程

    2018-12-10 00:51:17
    这里写自定义目录标题并行编程并行编程的目标是什么使并行编程变得复杂工作分割并行访问控制资源分割和复制与硬件交互硬件的习性概述CPU 流水线内存引用原子操作内存屏障Cache MissI/O 操作开销硬件体系结构操作的...

    并行编程

    并行编程的目标

    相对于串行编程来说,并行编程有如下三个主要目标:
    性能
    生产率
    通用性

    是什么使并行编程变得复杂

    工作分割

    每个线程都会占用一些资源, 比如 CPU cache 空间。如果过多的线程同时执行,CPU cache将会溢出,引起过高的cache miss,从而降低性能。
    大量的线程可能会带来大量计算和 I/O 操作。
    合法的并行线程会大量增加程序的状态空间,导致程序难以理解,降低生产率。

    并行访问控制

    资源分割和复制

    与硬件交互

    硬件的习性

    概述

    CPU 流水线

    如果程序中带有许多循环,且循环计数都比较小;
    或者面向对象的程序中带有许多虚对象,每个虚对象都可以引用不同的实对象,而这些实对象都有频繁被调用的成员函数的不同实现,此时 CPU很难或者完全不可能预测某个分支的走向。
    这样CPU要么等待控制流进行到足以知道分支走向的方向时,要么干脆猜测——由于此时程序的控制流不可预测——CPU常常猜错。在这两种情况中,流水线都是空的,CPU需要等待流水线被新指令填充,这将大幅降低CPU的性能。

    内存引用

    虽然现代微型计算机上的大型缓存极大地减少了内存访问延迟,但是只有高度可预测的数据访问模式才能让缓存发挥最大效用。
    不幸的是,一般像遍历链表这样的操作的内存访问模式非常难以预测。

    原子操作

    有一些指令是流水线必须延迟甚至需要冲刷, 以便一条原子操作成功完成。

    内存屏障

    由于内存屏障的作用是防止CPU为了提升性能而进行的乱序执行,所以内存屏障几乎一定会降低CPU性能。

    spin_lock(&mylock);
    a = a + 1;
    spin_unlock(&mylock);
    

    Cache Miss

    现代CPU使用大容量的高速缓存来降低由于较低的内存访问速度带来的性能惩罚。
    但是,CPU高速缓存事实上对多CPU间频繁访问的变量起反效果。因为当某个CPU想去更改变量的值时,极有可能该变量的值刚被其他CPU修改过。在这种情况下,变量存在于其他CPU而不是当前CPU的缓存中,这将导致代价高昂的Cache Miss。

    I/O 操作

    I/O操作涉及网络、大容量存储器,或者(更糟的)人类本身,I/O操作对性能的影响远远大于之前提到的各种障碍。

    开销

    硬件体系结构

    系统硬件体系结构

    数据以“缓存线”为单位在系统中传输,“缓存线”对应于内存中一个2的 幂大小的字节块,大小通常为32到256字节之间。
    当CPU从内存中读取一个变量到它的寄存器中时,必须首先将包含了该变量的缓存线读取到CPU高速缓存。
    同样地,CPU将寄存器中的一个值存储到内存时,不仅必须将包含了该值的缓存线读到CPU高速缓存,还必须确保没有其他CPU拥有该缓存线的拷贝。

    操作的开销

    Operation Cost (ns) Ratio (cost/clock)
    Clock period 0.6 1.0
    Best-case CAS 37.9 63.2
    Best-case lock 65.6 109.3
    Single cache miss 139.5 232.5
    CAS cache miss 306.0 510.0
    Comms Fabric 5,000 8,330
    Global Comms 195,000,000 325,000,000

    工具

    脚本语言

    1、创建新进程的开销是很大的,它包括代价高昂的fork()和exec()系统调用。
    2、包括管道这样的共享数据操作,通常会包括代价高昂的文件I/O。
    3、脚本可用的同步原语,通常也包括代价高昂的文件I/O。

    POSIX 多进程

    POSIX进程创建和销毁

    进程通过fork()原语创建,使用kill()原语销毁,也可以用exit()原语自我销 毁。执行fork()的进程被称为新创建进程的“父进程”。父进程可以通过wait()原语等待子进程执行完毕。父进程和子进程并不共享内存。

    pid_t fork(void);
    pid_t wait(int *stat_loc);
    

    POSIX线程创建和销毁

    在一个已有的进程中创建线程,需要调用pthread_create()原语,pthread_join()原语是对进程的wait()的模仿,它一直阻塞到tid变量指定的线程返回。线程返回有两种方式,要么调用pthread_exit()返回, 要么通过线程的顶层函数返回。

    int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)(void *), void *arg);
    int pthread_join(pthread_t thread, void **value_ptr);
    

    POSIX 锁

    POSIX锁包括几个原语,其中最基础的是pthread_mutex_lock()和 pthread_mutex_unlock()。这些原语操作类型为pthread_mutex_t 的锁。该锁的静态声明和初始化由 PTHREAD_MUTEX_INITIALIZER完成,或者由pthread_mutex_init()原语来动态分配并初始化。

    POSIX 读写锁

    POSIX API提供了一种读写锁,用pthread_rwlock_t 类型来表示。和pthread_mutex_t一样,pthread_rwlock_t也可以由PTHREAD_RWLOCK_INITILIZER静态初始化,或者由pthread_rwlock_init()原语动态初始化。
    pthread_rwlock_rdlock()原语获取pthread_rwlock_t的读锁,pthread_rwlock_wrlock()获取它的写锁,pthread_rwlock_unlock()原语负责释放锁。
    在任意时刻只能有一个线程持有给定pthread_rwlock_t的写锁,但同时可以有多个线程持有给定pthread_rwlock_t的读锁,至少在没有线程持有写锁时是如此。

    在临界区较小时,读写锁性能未必有mutex好。

    由于所有想获取读锁的线程都要更新pthread_rwlock_t的数据结构。(读的数目)因此,一旦全部线程同时尝试获取读写锁的读锁,那么这些线程必须一个一个的更新读锁中的pthread_rwlock_t结构。

    原子操作

    读写锁在临界区最小时开销最大,考虑到这一点,那么最好能有其他手段来保护极其短小的临界区。

    gcc 编译器提供了许多附加的原子操作,__sync(如__sync_fetch_and_and())。

    有一对原语提供了经典的“比较并交换”操作, __sync_bool_compare_and_swap()和__sync_val_compare_and_swap()。

    __sync_synchronize()原语是一个“内存屏障”,它限制编译器和CPU对指令乱序执行的优化。

    在某些情况下,只限制编译器对指令的优化就足够了,CPU的优化可以保留,此时就需要使用**barrier()原语。在某些情况下,只需要让编译器不优化某个内存访问就行了, 此时可以使用ACCESS_ONCE()**原语。这两个原语不是由 gcc 直接提供的,可以如下实现:

    #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
    #define barrier() __asm__ __volatile__("": : : "memory")
    

    计数

    统计计数器

    统计计数一般以每个线程一个计数器的方式处理(或者在内核运行时,每个 CPU 一个),所以每个线程只更新自己的计数器。根据加法的交换律和结合律, 总的计数值就是所有线程计数器值的简单相加。

    基于每线程变量__thread的实现,因为线程退出变量就没了,所以要加锁(可用全局数组替代)。

    显然本节只是保持“结果一致性”。

    近似上限计数器

    维护一个每线程计数器的上限值。当超过这个上限时,线程将自己的计数加到全局计数器上。在减少计数值时利用上全局计数器,否则每线程计数器的值就可能降到0以下。

    如果这个上限(设为countermax)足够大,那么几乎所有的加减操作都是在每线程计数器中执行的,这就给我们带来了良好的性能和可扩展性。

    但是,每线程变量countermax 的使用表明即使未到达上限,加减操作也可能会失败(毕竟已经把max近似当做满荷了)。

    精确上限计数器

    原子上限计数器

    主要是精确计算每个线程内剩余计数,通过清零的方式。

    static void flush_local_count(void) 
    {
    	int c; int cm; int old; int t; int zero;
        	if (globalreserve == 0) return;
        	zero = merge_ctrandmax(0, 0); 
        	for_each_thread(t)
        		if (counterp[t] != NULL) {
        			old = atomic_xchg(counterp[t], zero); 			
        			split_ctrandmax_int(old, &c, &cm); 
        			globalcount += c;
        			globalreserve -= cm;
        		}
    }
    

    Signal-Theft 上限计数器

    这个思路其实是用信号量来完成状态机的状态通知。
    状态机

    状态机从 IDLE 状态开始,当进入慢速路径(需要计算别的线程剩余可用个数)时将每个线程的theft状态设置为 REQ(除非线程没有计数值,这样它就直接转为READY)。
    然后慢速路径向每个线程发送一个信号,对应的信号处理函数检查本线程的theft和counting状态。
    **一旦慢速路径发现某个线程的theft状态为READY,这时慢速路径有权窃取此线程的计数。**然后慢速路径将线程的theft状态设置为IDLE。

    static void flush_local_count(void)
    {
    	int t;
    	thread_id_t tid;
    
    	for_each_tid(t, tid)				
    		if (theftp[t] != NULL) {		
    			if (*countermaxp[t] == 0) {	
    				WRITE_ONCE(*theftp[t], THEFT_READY);
    				continue;
    			}
    			WRITE_ONCE(*theftp[t], THEFT_REQ);
    			pthread_kill(tid, SIGUSR1);
    		}
    	for_each_tid(t, tid) {
    		if (theftp[t] == NULL)
    			continue;	
    		while (READ_ONCE(*theftp[t]) != THEFT_READY) {
    			poll(NULL, 0, 1);
    			if (READ_ONCE(*theftp[t]) == THEFT_REQ)
    				pthread_kill(tid, SIGUSR1);
    		}
    		globalcount += *counterp[t];
    		*counterp[t] = 0;
    		globalreserve -= *countermaxp[t];
    		*countermaxp[t] = 0;
    		WRITE_ONCE(*theftp[t], THEFT_IDLE);
    	}
    }
    

    信号处理函数检查本线程的theft和counting状态。

    static void flush_local_count_sig(int unused)	
    {
    	if (READ_ONCE(theft) != THEFT_REQ)
    		return;
    	smp_mb();
    	WRITE_ONCE(theft, THEFT_ACK);
    	if (!counting) {
    		WRITE_ONCE(theft, THEFT_READY);	
    	}
    	smp_mb();
    }
    

    如果theft状态是ACK,当快速路径完成时,会将theft状态设置为READY(信号量何时中断线程未知,稍微思考下可能情况就好理解)。

    展开全文
  • 深入理解并行编程4

    2018-06-11 22:14:00
    如果同步开销可以忽略不计(比如程序使用了粗粒度的并行化),并且只有一小段临界区修改数据,那么让多个读者并行处理可以显著地增加可扩展性 层级锁 需要严格注意加锁顺序,防止死锁 额外的加解锁动作,会...

    分割和同步设计

    并发编程中的设计模式

    分割联系

    哲学家的就餐问题

    阻止饥饿

    Dijkstra解决方法

    • 使用一个全局信号量
      • 假设通信延迟忽略不计的话

    最新的解决办法:

    1. 给叉子编号
    2. 先拿盘子周围编号最小的叉子
    3. 然后再拿编号最高的叉子
    • 至少有一位肯定可以拿到两把叉子,则开始就餐

    为资源编号并按照编号顺序获取资源的通用技术在防止死锁上经常使用

    这类问题,都是这对资源争用,因此也可以称之为

    • 水平并行化
    • 数据并行化

    双端队列

    如果基于锁,要达到在双端队列两端进行并发操作是比较困难的。

    右手锁和左手锁

    左手锁

    • 控制左手端入列操作

    右手锁

    • 控制右手端入列操作

    4个以内的数据,重叠

    • 需要两个锁同时起作用
    复合双端队列

    用两个单独的双端队列串联在一起

    • 每个队列用自己的锁保护
    • 需要控制加锁层次的顺序一致
      • 避免死锁

    需要重新平衡两个队列的元素,带来额外的性能开销

    哈希永远是分割一个数据结构的最简单和最有效的方法。、

    可以根据元素在队列中的位置为每个元素分配一个序号,然后以此对双端队列进行哈希。

    为了避免死锁,只在获取链表锁之前获取下标锁,每种类型的锁(下标或者链表)每次从不获取超过一个

    讨论

    复合式在某种程度上比哈希式实现要复杂,但效果可能会好一些。

    • 没有考虑复杂的重新平衡机制

    不过,这种机制最多也就获得了两倍的扩展能力

    • 最多只能有两个线程并发的持有出列的锁
    • 关键点在于从共享队列中入列或者出列的巨大开销

    分割问题的讨论

    水平并行化/数据并行化

    • 同步开销小(接近0)

    垂直并行化/管道

    • 双端队列
    • 数据可以从一个线程转移到另一个线程
    • 需要密切的合作
      • 需要更多的工作来获得某种程度的效率

    设计准则

    并发编程的目标:

    • 性能
    • 生产率
    • 通用性

    设计模式

    • 这些准则被认为是设计中的阻力
    • 对这些阻力进行恰当权衡

    设计准则:

    • 加速
      • 顺序执行 / 并行执行
    • 竞争
      • 不是越多CPU越好
      • 资源竞争
        • 锁竞争
        • 内存竞争
    • 开销
      • 工作-同步比率
      • 消耗在同步原语上的时间都是不必要的开销
        • 缓存缺失
        • 消息延迟
        • 加解锁原语
        • 原子指令
        • 内存屏障
      • 同步开销与临界区代码的开销衡量
        • 更大的临界区能容忍更大的同步开销
    • 读写比率
      • 对不同操作采用不同的同步原语来保护
    • 复杂性
      • 需要维护更多状态
      • 还必须考虑
        • 同步原语
        • 消息传递
        • 锁的设计
        • 临界区识别
        • 死锁
      • 更高的开发/维护代价
      • 顺序执行还有优化的空间
      • 并行化只是众多优化中的一种,并不是唯一的
        • 主要应用于CPU瓶颈的优化

    建议:

    1. 程序在临界区上所花的时间越少,潜在加速就越大
      • Amdahl定律
      • 一个时刻只有一个CPU进入临界区
    2. 程序在某个互斥的临界区上所耗费的时间必须大大小于CPU数的倒数
      • 这样增加CPU数目才能达到加速
    3. 竞争效应所浪费的多余CPU和 / 本来该是加速的理想时间,应该少于可用CPU的数目
      • 差距越大,CPU的效率越低
    4. 如果可用的同步原语相较它们保护的临界区来说开销太大
      • 加速程序运行的最佳办法是减少调用这些原语的次数
        • 分批进入临界区
        • 数据所有权
        • RCU
        • 使用粒度更粗的设计
          • 代码锁
    5. 如果临界区相较守护这块临界区的原语来说开销太大
      • 加速程序运行的最佳办法是增加程序的并行化程度
        • 读写锁
        • 数据锁
        • RCU
        • 数据所有权
    6. 如果临界区相较守护这块临界区的原语来说开销太大,并且被守护的数据结构读多于写
      • 那么加速程序运行的最佳办法是增加程序的并行化程序
        • 读写锁
        • RCU
    7. 各种增加SMP性能的改动,减少锁竞争程度,能改善响应时间
      • 多核处理器

    同步粒度

    1. 串行程序

    2. 代码锁

      • 硬性的同步语句,加锁
      • 容易引起锁竞争
    3. 数据锁

      • 在数据结构中,分割一个锁结构
      • 每个数据都带有一把自己的锁
      • 避免全局锁的争用
      • 想要降低锁竞争,并且同步开销不是主要瓶颈时,适用
    4. 数据所有权

      • 按照线程或者CPU的个数分割数据结构
      • 每个线程/CPU都可以不需要任何同步开销的情况下访问属于它的子集
      • 数据/资源隔离
      • 需要考虑数据分割的平均
        • 避免分配不均,导致热点
      • 对于重要数据只读可以通过复制来让每一个线程/CPU拥有数据

      MIPS(Million Instructions Per Second):单字长定点指令平均执行速度 Million Instructions Per Second的缩写,每秒处理的百万级的机器语言指令数

    在数据结构的锁已经被获取时,防止数据结构被释放的几种解决办法:

    1. 适用静态分配的锁
      • 变相的全局锁
      • 导致高度的锁冲突
      • 降低性能和扩展性
    2. 使用静态分配的锁数组,将数据结构的地址进行哈希,以选择要获取的锁
      • 哈希函数要足够的高效
        • 扩展性的瓶颈点
      • 只读时,锁请求的开销降低性能
    3. 使用垃圾回收器
      • 在数据结构还有被引用时,不会被释放
      • 消除了存在性保证性的负担
      • 加重了垃圾回收的负担
    4. 作为垃圾回收机制的特例,使用一个全局的引用计数,或者一个全局的引用计数数组
    5. 使用冒险指针,它可以被视为一种inside-out引用计数
      • 基于冒险指针的算法,维护一个每线程的指针列表
        • 列表中的特定指针就是相应结构的引用
      • 有点类似智能指针
    6. 使用事务内存(TM)
      • 每一次对数据结构的引用和修改都被自动执行
    7. 使用RCU(Read-Copy Update)
      • 一种极其轻量级的,类似垃圾回收器的东西
      • 写者不允许释放那些仍然被读者所引用的数据结构
      • 对于那些大量用于读取的数据结构来说,RCU被大量使用

    并行快速路径

    细粒度的设计一般要比粗粒度的设计复杂。

    • 许多情况下,绝大部分开销只由一小部分代码产生
    • 不只是算法需要并行化,算法所属的工作负载也要并行化

    并行快速路径的设计模式

    • 读写锁
    • RCU
    • 分层多级锁
    • 分配器缓存(Allocator caches)

    读写锁

    如果同步开销可以忽略不计(比如程序使用了粗粒度的并行化),并且只有一小段临界区修改数据,那么让多个读者并行处理可以显著地增加可扩展性

    层级锁

    需要严格注意加锁顺序,防止死锁

    额外的加解锁动作,会带来开销

    可以考虑,不同的重量级别的锁,自旋,读写,互斥

    如:jdk 6 中的 4层锁结构, 自旋->轻量->重量->互斥

    资源分配器缓存

    并行,为每一个cpu分配一个独享的资源池。

    分级,独享的小空间(资源池);一个较大的共享资源池,实用代码锁保护。

    典型例子:

    • CPU的多级缓存
    • JVM中的多级GC空间

    防止随便,多个空间可以连续使用。

    • 分配器常规套路
    • jvm也有类似的设计

    其他难点:

    • 弹性的空间管理
    • 实际中,还需要处理各种不同的资源大小
    • 最大允许的空间阈值
    • 不同用途的空间,使用不同的管理策略
      • 不同级别的内存块组合
      • 如jvm中分配的空间单位,分成不同大小块的空间(资源池)
        • 这些不同大小的空间,可用于不同大小的Object空间分配
        • 更好的解决对齐
    等级锁类型目的
    每线程资源池数据所有权高速分配
    全局内存块资源池数据锁将内存块放在各个线程中
    组合数据锁将内存块放在页中
    系统内存代码锁获取、释放系统内存

    转载于:https://my.oschina.net/roccn/blog/1828454

    展开全文
  • 深入理解并行编程3

    2018-06-11 22:13:00
    共享内存式的并行化可要比 fork-join 式的并行化复杂的多 POSIX 线程的创建和撤销 创建 进程需要调用 pthread_create() 来创建一个线程 参数: 指向 pthread_t 结构的指针 用于存放将要创建线程的线程 ...
  • 深入理解并行编程2

    2018-04-24 21:31:00
    由于许多并行算法都要求,在更新多个数据元素时保证正确的执行顺序,因此绝大多数 CPU 都提供了 内存屏障 内存屏障 spin_lock(&mylock); // 1 a = a + 1; // 2 spin_unlock(&mylock); // 3 为了保障line 2的...
  • 深入理解并行编程1

    2018-04-16 22:07:00
    并行编程存在的问题 死锁 活锁 竞争条件 不确定性 扩展性限制 实时延迟 并行编程的目标 性能 性能方面的关注焦点已经从硬件转向并行软件 生产率 高效的利用开发者已经变得更为重要 ...
  • 深入理解并行编程-锁

    2016-04-08 16:37:21
    锁 在过去几十年并发研究领域的出版物中,锁总是扮演着坏人的角色,锁背负的指控包括引起死锁、锁封护(luyang注:lock convoying,多个同优先级的线程重复竞争同一把锁,此时大量虽然被...有趣的是,在共享内存并行...
  • 上面的章节中给出了三个并行编程的目标:性能、生产率和通用性。但是还需要更详细的设计准则来真正的指导真实世界中的设计,这就是本节将解决的任务。在真实世界中,这些准则经常在某种程度上冲突,这需要设计者小心...
  • 由于许多并行算法都需要在更新多个数据元素时,保证正确的执行顺序,大多数CPU都提供了内存屏障。 内存屏障 为了防止有害的乱序执行,锁操作原语必须包含或显式或隐式的内存屏障。由于内存屏障的作用是防止...
  • 历数过网络不少有价值的文章和牛人博客,从而也收藏不少有水平有... 本书是linux内核大牛paul的力作, 深入介绍了并行的技术。从内在到 RCU实现及数据结构高级同步,分割同步、阻塞与非阻塞的深入介绍。     ...
  • 原文链接 作者:paul 译者:谢宝友,鲁阳,陈渝 并行快速路径 细粒度的设计一般要比粗粒度的设计复杂。在许多情况,绝大部分开销只由一小部分代码产生[Knu73]。所以为什么不把精力放在...您必须理解这一点,不只算法...
  • 在上一章我们说过,您在编写并行软件时最重要的考虑是如何进行分割。正确的分割问题能够让解决办法简单、可扩展并且高性能,而 不恰当的分割问题则会产生缓慢且复杂的解决方案。 1.1分割练习 本节用...
  • 深入理解并行编程-分割和同步设计(一) 第 1.1节的小问题中,关于哲学家就餐问题最优解法的答案是“水平”并行化或者“数据并行化”的极佳例子。在这个例子中,同步开销接近于0(或者就是)。相 反,双端队列的实现...
  • 请注意,这并不意味这您应该在每个程序中使用多线程方式编程。我再一次说明,如果一个程序在单处理器上运行的很好,那么您就从SMP同步原语的开销和复杂性中解脱出来吧。图1.4中哈希表查找代码的简单之美强调了这一点...
  • 有序性 - 保证指令不会受 cpu 指令并行优化的影响 (从JMM层面可以更深刻理解线程安全的特性) 一.可见性 退不出的循环 先来看一个现象,main 线程对 run 变量的修改对于 t 线程不可见,导致了 t 线程无法停止: stat
  • 本节书摘来自华章计算机《深入理解大数据:大数据处理与编程实践》一书中的第1章,第1.1节,作者 主 编:黄宜华(南京大学)副主编:苗凯翔(英特尔公司),更多章节内容可以访问云栖社区“华章计算机”公众号查看。...
  • 深入理解nodejs中的异步编程

    千次阅读 2021-01-16 12:10:38
    因为javascript默认情况下是单线程的,这意味着代码不能创建新的线程来并行执行。但是对于最开始在浏览器中运行的javascript来说,单线程的同步执行...今天,我们将会深入的探讨一下各种异步编程的优缺点和发展趋势。
  • 并发与并行2. 阻塞与非阻塞3. 同步与异步4. 并发编程的实现方式5. 总结 1. 并发与并行 并发:concurrency 并行:parallelism 开发过程中,常常会接触并发有关的概念,比如并发计算(concurrent computing),并发...
  • 本节书摘来自华章计算机《深入理解大数据:大数据处理与编程实践》一书中的第1章,第1.3节,作者 主 编:黄宜华(南京大学)副主编:苗凯翔(英特尔公司),更多章节内容可以访问云栖社区“华章计算机”公众号查看。...

空空如也

空空如也

1 2 3 4 5 ... 15
收藏数 299
精华内容 119
关键字:

深入理解并行编程