并发数据结构- 1.1.1 性能

原文链接译文链接,译者:俞升兵,校对:周可人

1.1.1 性能

一个运行在P个处理上的应用程序的加速度是它在单个处理器上的执行时间和在P个处理器的执行时间的比值。这是一种评价应用程序对于机器资源利用程度的衡量。理想情况下,我们想要的结果是线性加速度:当我们使用P个处理器的时候,我们希望可以获得P的加速度(译者注:例如一个应用程序在单处理器的执行时间是10秒,那么在双处理的执行时间理想情况下是5秒)。加速度随着P一起增加的数据结构我们称之为可扩展的数据结构。在设计可扩展的数据结构的时候,我们必须注意:为了同步使用简单的方法会严重破坏扩展性。

回到基于锁的计数器,我们会发现锁会带来顺序性的瓶颈:在任何时间点,最多只有一个fetch-and-inc操作是有用的,例如:递增变量X。这种顺序性的瓶颈会对本来能够到达的加速度造成令人惊讶的影响。顺序执行部分代码对性能带来的影响已经在基于Amdahl’s law的一个简单公式中阐明了。假设b是一个程序中顺序性瓶颈所占的百分比。假设在单处理器中运行这个程序需要1个时间单位,那么在P个处理器的环境中,执行顺序运行部分的代码需要b个时间单位,同时在最好的情况下,并发部分的代码消耗(1-b)/p个时间单位,那么加速度最多等于 1/(b+(1-b)/p) 。这意味中如果程序中只有10%是属于顺序性瓶颈的部分,那么在一个10个处理器的环境中,程序能达到的加速度最多只有5.3:我们的应用只利用了机器的一半性能。减少顺序性执行代码块的数量和长度对性能是至关重要的。在基于锁的上下文中,这意味着减少申请锁的次数,降低锁的粒度:一种用来表示在持有锁时,执行指令数目的衡量。

我们的简单计数器实现碰到的第二个问题是内存竞争:这是底层硬件为了多线程并发尝试访问相同的内存地址所造成的流量的开销。只有当你理解普通的共享内存多处理器架构一些方面,你才能意识到内存竞争。如果保护着我们计数器的锁就像很多简单锁一样,是使用单一地址实现的话,那么为了请求锁,线程必须重复尝试修改这个地址。以缓存一致性多处理器为例,包含着锁的cache line的独占所有权必须重复的从一个处理器传输到别的处理器上,这会导致每次尝试修改内存地址的操作都需要长时间的等待,失败的尝试获取锁的操作会进一步加重相应的内存流量。在1.1.7中我们会讨论针对不同类型的共享内存架构实现相应的锁,避免类似这样的问题.

基于锁的实现的计数器的第三个问题是:当持有锁的线程被延期了,那么所有尝试获取锁的线程都会被延期。这种现象称为阻塞,阻塞是多道程序设计(multiprogrammed)中特有的问题,每个处理器都有多个线程,操作系统会给拥有锁的线程优先权。对于很多的数据结构来说,这个问题可以通过设计非阻塞的算法来解决,在非阻塞算法中一个线程的延期不会导致其他线程的延期。根据定义而言,这些算法不能使用锁。

下面我们继续讨论我们的共享计数器的例子,分别讨论阻塞和非阻塞技术;我们会引入更多和性能相关的话题.

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 并发数据结构- 1.1.1 性能

sambean

on the way to be a real programmer

Latest posts by sambean (see all)

FavoriteLoading添加本文到我的收藏
  • Trackback are closed
  • Comments (3)
    • niko
    • 04/01. 2014 10:32am

    翻译有点烂,请问你是根据自己理解翻译的吗?

    • 煎鸡蛋
    • 04/04. 2014 10:57am

    这文章不知道是否还有下文,很不错,道出了写一个计数器的性能瓶劲点,如果我们用不同的数据结构就不会出现这些问题了,比如用二叉树结构就可以规避

    • 您好,有上下文的。

      文章来源是Nir Shavit的一篇并发数据结构导论。

      http://ifeve.com/cds-plan/

      事实上大部分内容我们都已经正在翻译了。这几天我正在校对后续内容。等所有内容都完了,我会整理这个专题,并且补充相关内容的。

      您刚才提到的性能瓶颈,将会在“阻塞技术”这篇中提到,事实上对于修改操作密集程度不同的数据结构,将会有不同的处理方式。您说的很对。

      敬请期待后续的文章,并希望您能给我们提出一些翻译上建议和意见!

      十分感谢您的关注!

You must be logged in to post a comment.

return top