Time
2020.11.17
Research Objective
多核多线程
Problem Statement
- 多核CPU情况下，OS需要处理的问题有：
- 处理器/核之间的相关性;
- 线程与进程的调度，其中，线程的分配和调度是多核 OS 的关注点，其目的是根据数据共享情况，将其分配到合理的物理核上。
- Cache 一致性
- 处理器间通信
- 核内资源竞争
- 中断处理
- 多核多线程技术，核心问题是任务调度，需要从性能评估入手，从并行线程的规模数、数据竞争、锁竞争、线程安全、存储和数据组织等角度进行系统分析和优化。
- 多线程程序设计出现的问题，源于错误的任务分解方式
- 对共享数据的访问，会导致数据竞争。
- 多线程或多共享数据的存在，可能会导致锁竞争的频繁出现。
Method(s)
- 锁是最简单直接的一种解决数据竞争问题的同步策略
- 锁的分类包括：
- 互斥量( Mutex)
- 递归锁( Ｒecursive Lock)
- 读 写 锁 ( Ｒead-Write lock，又称共享独占锁 ( shared- exclusive lock ) )
- 多 读 单 写 锁 ( Multiple-Ｒead /Single-Write Lock)
- 非互斥信号量( Non-Mutual Exclusion Semaphore)
- 旋转锁( Spin Lock，一种非阻塞锁) 。
- 解决锁竞争的办法：
- “快锁”，用“快锁”代替“慢锁”
- 资源复制，通过“空间成本”来换取数据“不锁”
- “细粒度锁”，减少对锁的等待时间的最佳办法就是减少这个锁锁保护的范围，采用细粒度锁的方式，将竞争分散到多个锁上。代价就是增加锁空间的开销，频繁的请求和释放锁，还会增加额外的开销。下图给出锁的吞吐量与锁力度之间的关系。
- 不使用“锁”，采用非阻塞算法，通过数据结构来构建这种无阻塞算法。这种算法的本质是停止一个线程的执行，不会阻碍系统中其他执行实体的运行，可以避免优先级倒置和死锁等风险，是锁定的一个备用方案。
- 通过数据压缩，节省带宽，减少CPU与存储器之间的数据传输。
- 对 Cache 来讲，主要采用减少数据移动( 执行核和存储器之间，或执行核之间)的方式。要减少数据移动，可以采用 Cache 遗忘分块算法( Oblivious Blocking) 将问题划分成更小的子问题。
Evaluation
- 采用加速系数来衡量多处理器性能，加速系数定义如下：
Notes
- 片上多核处理器（CMP）采用两种高效的通信机制
- 基于总线共享的Cache结构
- 基于片上的互联结构
- 典型多核CPU硬件结构如图（采用总线共享方式）
- 多核对软件的要求包括对多核操作系统的要求和对应用软件的要求
- 任务的分配与调度研究方向有：
- 程序的并行研究
- 多进程的时间相关性研究
- 任务的分配与调度
- 缓存的错误共享
- 一致性访问研究以及内部资源竞争等。
- 并行计算涉及4个方面：
- 并行计算机体系结构( 处理器和硬件平台)
- 并行计算机系统软件( 操作系统和并行通信协议)
- 并行算法设计
- 并行应用开发
- 多线程技术早于多核CPU，但运行在单核平台的多线程技术来回切换所需要的时间和资源开销有时候还比不上单线程。
- Amdahl定律
按照 Amdahl 定律进行推论，可以说多核发展没有前景，因为串行比例直接决定了加速系数最大值为 1 /f，再多的核数也无法提升速度性能。 - Gustafson定律
按照 Gustafson 定律进行推论，加速系数几乎和处理器数/核数成正比。实际满足其假设条件的情况是困难的。显 然，这个定律过于乐观。 - 当软件线程数超过硬件线程数时，支持抢占式多任务处理的 OS 一般会采用时间片轮转调度方案，轮流为每个线程提供硬件线程时间片( time slice) ，若时间片结束时线程没完成，则被 OS 挂起，由另一个线程继续运行; 这种方式下发生了线程切换，被挂软件线程的上下文需要被保存，将被激活的软件线程的上下文要被加载。使用时间片机制时，保存和恢复线程所使用的Cache 的开销将变得更为敏感。因为 Cache 的命中率直接影
响 CPU 的性能。当发生线程切换时，新线程所需的数据可能还未填入到 Cache，这就会导致不同线程不断竞争 Cache，直接导致 CPU 性能降低。