非阻塞算法和可伸缩的多核编程 已翻译 98%

oschina 投递于 2013/06/14 11:50 (共 43 段, 翻译完成于 07-02)
阅读 1395
收藏 6
0
加载中

探索基于锁的同步的一些替代方案

Samy Al Bahra, AppNexus

为了以一种很划算的方式来满足带有复杂服务质量保证的运营需求,现实世界中的系统可能就需要在吞吐量和延迟这二者之间寻求一个微妙的平衡点。当今商用多核(multicore)和众核(many-core)系统越来越普遍,成本也越来越低,为了满足日益增长的性能需求,这就使得并发和并行越来越成为必要的技术手段。很不幸,正确、高效、可伸缩的并发软件在设计和实现起来,通常都是一项非常艰巨的任务。

为了保证共享可变状态的一致性,商用多核处理器之上的并发系统往往都会依赖于基于锁的同步机制。然而,基于锁的同步具有多个局限,其中包括对任务抢占的敏感性和可能会导致死锁等等问题,这就使得在某些特定环境下变得或者不适用或者不实用。这并不意味着基于锁的同步是设计和实现高效可伸缩软件的障碍。

fbm
fbm
翻译于 2013/06/14 17:55
1

非阻塞式同步也许可以用于构建具有可预测性和弹性的系统,而且还能避免基于锁的同步所带来的问题。这类同步机制绝非银弹,特别是在原先定义它的性能属性的抽象模型的范围之外更是如此。同基于锁的同步机制相关的若干性能瓶颈和错误情况依然存在(虽然在形式上更加隐蔽);因此,为了保证正确性就需要更加复杂的验证方法,而且在有些情况下,非阻塞算法需要引入比较复杂的支撑系统。非阻塞式同步所带来的这些复杂性经常使得它成为了各种宣传资料的众矢之的,人们对它感到害怕、觉得不可靠并持有怀疑的态度。本文旨在为读者提供足够的知识,从而使得读者可以找出能够从非阻塞式同步机制中获益的使用场合。

fbm
fbm
翻译于 2013/06/14 18:14
1

通用原则

本节在详细阐述采用非阻塞数据结构的原因之前,着重说明要理解传统多线程模型可伸缩性需要了解的一些重要原则。不管是基于锁或者非阻塞的同步,其性能都源自这些原则。如果你已经非常熟悉缓存一致的多处理器、乱序执行、基于锁的同步对象的设计与实现,那么你完全可以跳过这一节。不过本节也不可能说的很详细,更进一步的内容可以去看参考资料。Paul E. McKenney介绍了如何去选择合适的基于锁的同步方式19。之前还有一些文章介绍了其他一些通用原则。6,15,21

zicode
zicode
翻译于 2013/06/14 21:09
1

竞争阻碍可伸缩性

并发程序中,共享对象的竞争是影响可伸缩性和可预测性的主要障碍。不管使用什么高层的同步机制,共享对象的竞争都会带来下层的某种形式的串行化,下层环境可能是编译语言运行时,或者是共享内存的多处理器。

Little定理 (L = λW) 是排队理论的基本原理,可以帮助我们更好的理解在序列化的资源上的竞争所带来的影响。定理指出,系统的平均输出请求数(L)是请求的有效到达率 (λ)和平均竞争时间 (W)的乘积。所谓的竞争,也就是有效到达率与共享资源请求数的乘积,会带来排队,这将直接影响系统的响应。

zicode
zicode
翻译于 2013/06/14 22:12
1

无论采用哪种同步方案,对共享数据的争用都会对并行应用的可伸缩性和可预测性(在延迟方面,有时也会在吞吐量方面)产生抑制作用。为了获得更高的性能,程序的设计者要负责将系统层的争用减少到最小的程度。系统选用的同步机制,不管是基于锁的还是非阻塞式的,在出现争用时都会出现性能方面的降低。

共享可变状态和争用

理解在多处理器之上如何提供一致性的保证机制是理解这种系统中出现的争用的先决条件。缓存一致性协议是在多缓存一致性处理器之上确保最终一致性最突出、最重要的机制。这些协议在缓存线(cache-line)级别实现了对一致性的保证。缓存线是从主内存中读取数据和向内存中写入数据的缓存单位(至少从一致性机制的角度看是这样的)。

fbm
fbm
翻译于 2013/06/15 01:11
1

商用处理器上三个最突出最重要的缓存一致性协议—MOESI, MESI, and MESIF—的缩写都来自它们为缓存线定义的各种状态:Modified(已修改), Owned(被占用),Exclusive(独占的), Shared(共享的), Invalid(无效的), and Forward(转发的)。缓存一致性协议在对内存确保最终一致性的内存一致性机制的帮助下对这些状态进行管理。图1所示是MOESI协议1相关的状态机。你可以将图中的各种探测转换(probe transition)理解为由来自其它核的外部内存访问所触发的状态转换。

Nonblocking Algorithms and Scalable Multicore Programming
fbm
fbm
翻译于 2013/06/15 01:24
1
下面的例子展示的是缓存一致性多处理器中共享读写的生命周期。为了叙述简单起见,这个生命周期的状态机经过了简化处理。这个程序生成了一个线程,该线程要读取经过修改后的变量的值:
volatile int x = 443;

static void * thread(void *unused)
{
     fprintf(stderr, "Read: %d\n", x);
     return NULL;
}

int
main(void)
{
     pthread_t a;

     x = x + 10010;
     if (pthread_create(&a, NULL, thread, NULL) != 0) {
           exit(EXIT_FAILURE);
     }

     pthread_join(a, NULL);
     return 0;
} 


该例子假设所采用的一致性机制是总线窥探,它允许任何一个处理器都可以对对共享位置处的任意内存进行监视。系统的初始状态如下图所示。系统中有两个插槽,每个插槽中都有一个核,每个核都有一个拥有64字节的缓存线的256字节L2级直接映射后写缓存(参见图2)。

Nonblocking Algorithms and Scalable Multicore Programming
fbm
fbm
翻译于 2013/06/15 01:33
1

初始的进程执行于core 0之上。假设变量x的地址是0x20c4。将x的值加10010(x = x + 10010;)可以分解为以下三个步骤:

  • 将x从内存载入到CPU的一个寄存器之中。
  • 该寄存器的值加上10010。
  • 将该寄存器中的值保存到x所在的内存处。

x的地址是0x20c4,它被散列到了缓存线3之中。既然该缓存线的状态为modified,并且包含一个来自不同地址(0x00c0)的数据,所以它必须写回到主内存之中。其它插槽都没有包含0x20c4的缓存线,所以64字节的数据块(起始于0x20c0)就会被从主内存读到缓存线3之中,并将状态置为独占状态(参见图3)。保存到x中的这个动作会将缓存线3的状态转换从exclusive转换为modified,如图4所示。

Nonblocking Algorithms and Scalable Multicore Programming
Nonblocking Algorithms and Scalable Multicore Programming
fbm
fbm
翻译于 2013/06/15 01:52
1

新线程生成后最终会开始执行该线程的线程函数。假设其执行于core 1之上。线程函数从x的地址处载入数据,并将该数据作为输入参数对fprintf函数进行调用。这个载入动作会发出一个读取探测,要求从midified的状态转换为owned状态(如图5所示)。MOESI协议允许缓存到缓存的数据转移,在缓存的探测延迟比主内存的探测延时延迟低的情况下这是个优势,该操作涉及对一般都具有较高延迟的内存互连的探测(同插槽间缓存访问相比具有较高的延迟)。同该探测相关的延迟也受拓扑结构的影响。在具有非对称互连拓扑结构的比较大规模的机器上,内存访问可能会有比较显著的性能失配;有些插槽一个刷新周期就需要一次跳变(hop),而别的一些插槽可能还需要两次或多次跳变。

Nonblocking Algorithms and Scalable Multicore Programming

善用缓存的程序(能够以最小的一致性流量保留共享状态的程序)在当今缓存一致性多处理器平台之上将具有良好的可伸缩性。对活跃的共享状态进行突变会直接导致争用,这是因为缓存控制器要对缓存线的拥有权进行协调。

fbm
fbm
翻译于 2013/06/15 02:22
1

一致性的粒度

如前所述,缓存线是缓存一致性多处理器系统之上对一致性进行维护的最小粒度,同时这也是争用的最小单位。如果在逻辑上并不相干的可变对象共享了同一个缓存线,那么在这些对象上的操作就会出现争用,从而可能会成为可伸缩性的瓶颈。这种情况叫做伪共享(false sharing)

请看下面这段C代码。每个线程在counters数组中都有一个对应的唯一的索引(UNIQUE_THREAD_ID),每个线程都要对该数组进行读写。因为这些counter是按顺序平铺到内存和缓存中的,缓存线的拥有权就会在增加这些counter的值的所有处理器之间来回切换。缓存线在这样的invalid/shared/modified/owned状态之间来回切换的恶性循环就是伪共享造成的缓存线状态来回切换的一个例子。

#define N_THR 8

struct counter {
     unsigned long long value;
};

static volatile struct counter counters[N_THR];

void *
thread(void *unused)
{

     while (leave == false) {
           counters[UNIQUE_THREAD_ID].value++;
     }

     return NULL;
}
fbm
fbm
翻译于 2013/06/15 02:33
1
本文中的所有译文仅用于学习和交流目的,转载请务必注明文章译者、出处、和本文链接。
我们的翻译工作遵照 CC 协议,如果我们的工作有侵犯到您的权益,请及时联系我们。
加载中

评论(2)

红薯
红薯

引用来自“fbm”的评论

@红薯 请看一下,这篇文章分段有问题,第一段是空的

已经处理
fbm
fbm
@红薯 请看一下,这篇文章分段有问题,第一段是空的
返回顶部
顶部