作者归档

基于锁的并发算法 vs 无锁的并发算法

原文链接 作者:Martin Thompson  译者:曹姚君 校对: 方腾飞

上周在由Heinz Kabutz通过JCrete 组织的开放空间会议(unconference)上,我参加一个新的java规范 JSR166 StampedLock的审查会议。StampedLock 是为了解决多个readers 并发访问共享状态时,系统出现的内存地址竞争问题。在设计上通过使用乐观的读操作,StampedLock 比ReentrantReadWriteLock 更加高效;

在会议期间,我突然意思到两点:

  • 第一、我想是时候该去回顾java中锁的实现的现状。
  • 第二、虽然StampedLock 看上去是JDK很好的补充,但是它视乎忽略了一个事实,即在多个reader的场景里,无锁的算法通常是更好的解决方案。

阅读全文

Linux内核的内存屏障

原文链接 作者:David HowellsPaul E. McKenney 译者:曹姚君 校对:丁一

内容:

  1. 抽象的内存访问模型
  2. 什么是内存屏障?
  3. 显式内核屏障
  4. 隐式内核内存屏障
  5. CPU之间的锁屏障效应
  6. 什么地方需要内存障碍?
  7. 内核的I/O屏障效应
  8. 假想的最小执行顺序模型
  9. CPU缓存的影响
  10. CPU能做到的
  11. 使用示例
  12. 引用

阅读全文

合并写(write combining)

原文地址 译者:无叶 校对:丁一

现代CPU采用了大量的技术来抵消内存访问带来的延迟。读写内存数据期间,CPU能执行成百上千条指令。

多级SRAM缓存是减小这种延迟带来的影响的主要手段。此外,SMP系统采用消息传递协议来实现缓存之间的一致性。遗憾的是,现代的CPU实在是太快了,即使是使用了缓存,有时也无法跟上CPU的速度。因此,为了进一步减小延迟的影响,一些鲜为人知的缓冲区派上了用场。

本文将探讨“合并写存储缓冲区(write combining store buffers)”,以及如何写出有效利用它们的代码。

CPU缓存是一种高效的非链式结构的hash map,每个桶(bucket)通常是64个字节。这就是一个“缓存行(cache line)”。缓存行是内存交换的实际单位。例如,主存中地址A会映射到一个给定的缓存行C。

阅读全文

内存访问模型的重要性

在高性能的计算中,我们常说缓存失效(cache-miss)是一个算法中最大性能损失点。 近些年来,我们的处理器处理能力的增长速度已经大大超过了访问主内存的延迟的缩短。 通过更宽的,多通道的总线,到主内存的带宽已经大大增加,但延迟并没有相应显著减少。 为了减少延迟,处理器采用愈加复杂的多层的高速缓存子系统。
在1994年的一篇论文“Hitting the memory wall: implications of the obvious”中描述了这个问题,并且认为由于缓存失效(cache-miss)必定存在,缓存不能最终解决这个问题。我的目标是:向大家展示通过利用访问模型,它是对缓存层次结构的思考,上面的结论并不是必然的。
让我们带着问题,来看下面的例子, 我们的硬件试图通过一些技术来减少主内存的延迟。 内存访问模型主要基于下面三个规律:
1、时间局部性 :最近访问过的内存最可能立马再次被访问;
2、空间局部性:相邻的内存最可能立马再次被访问;
3、 跨越式:内存访问可能会遵循一种可预测的模式。
阅读全文

return top