分布式共享内存

作者: 小聪明李良才 | 来源:发表于2016-11-22 10:19 被阅读853次
    DSM

    本文是论文Treadmarks: Distributed Shared Memory on Standard Workstations and Operating Systems 的读书笔记,水平有限,若有任何错误的地方,请不吝指出。

    本文是mit 6.824 Schedule: Spring 2016的第12课,前面课程内容可以在分布式找到,更多详细资料可以到:distributed-system查看。

    介绍

    在并发编程中,我们需要处理两个关键问题:

    • 线程之间如何通信
    • 线程之间如何同步

    通信是指线程之间以何种机制来交换信息,在命令式编程中,线程之间的通信机制有两种:

    • 共享内存
    • 消息传递

    我们从通信和同步两个维度来看共享内存和消息传递。

    在共享内存的并发模型里,线程之间共享程序的公共状态,线程之间通过写-读内存中的公共状态来隐式进行通信。在消息传递的并发模型里,线程之间没有公共状态,线程之间必须通过明确的发送消息来显式进行通信。
    同步是指程序用于控制不同线程之间操作发生相对顺序的机制。在共享内存并发模型里,同步是显式进行的。程序员必须显式指定某个方法或某段代码需要在线程之间互斥执行。在消息传递的并发模型里,由于消息的发送必须在消息的接收之前,因此同步是隐式进行的。

    通过上面的介绍我们知道了共享内存是一种隐式的通信手段,需要显示的方法来实现同步。

    而在分布式系统中,我们希望能够的是能尽可能的利用普通的机器,来达到并行计算的目标,而distributed shared memory (DSM) 在分布式系统中实现了共享内存,让所有process都共享一个全局地址空间,通过提供简单的api,方便process的访问。
    先让我们看下api



    其中barrier,acquire和realease用于同步操作,一旦调用barrier等待所有process都到达这个点后才继续执行,acquire和realease则用于锁的获取和释放。

    设计

    在实现DSM时,主要考虑的两个问题是:

    • 一致性
    • False Sharing

    首先在分布式系统中,为了提高性能,往往会对同一份数据做本地缓存,加快访问,但是数据虽然有多份,但是需要保证数据的一致性,同一份数据可能有多个副本,一旦数据做出了改变,需要通知所有持有副本的process,数据已经改变了。

    我们先来看下如果要实现这种严格的数据改变,就必须可见,系统需要怎么做?



    如上图所示,每个写操作一旦完成,必须要通知所有其他的进程该行为,带来的问题是:

    • 消息数的增加
    • 延迟

    这种严格的一致性被称为是:sequence consistency,一般系统为了其他一些因素,都会做出一些trade-off,TreadMarks则是采取了release consistency,只有在同步点上才要求数据同步,看图:



    使用release consistency的目标是:

    • 减少消息数
    • 减少延迟

    那此处具体的同步点是什么时候呢?
    前面提到过TreadMarks提供了acquire和release两个同步操作,当发生同步操作的时候,进行数据的同步。


    Eager

    此时在release的时候,将在acquire和release之间的数据改变广播给所有的持有数据副本的process,但是由于需要等待所有副本答复说已经收到通知,release操作会比较耗时。


    Lazy
    TreadMarks在实现release consistency采用了Lazy Release Consistency,
    • 只有当下次acquire锁的时候才会去获取改变
    • 获取再取有效的减少了消息数

    Eager和Lazy在实际运行中减少的消息数,可以通过下图直观的看到:



    我们看到P和Q都是操作同一个page,但是P是写x,而Q是读y,但是由于P写完x后通知了Q改页已经数据更改了,失效了保存在Q中的副本,因此Q再去访问y的时候,必须要去P处获取该页的数据,加重了数据的传输成本。那解决办法有什么呢?采用 multiply writer protocol,具体来讲就是
    • 采用copy-on-write机制
    • 一旦某个进程被授权访问write-shared的数据,将包含数据的页标志为copy-on-write
    • 第一次更改页数据的时候,会创建一个备份:twin
    创建diffs

    TreadMarks在diffs的创建上,采取了Lazy的策略,只有当其他processor请求页改变的时候,才会去创建diffs。

    数据结构


    主要数据结构如上图所示,包括了

    • Page Array
    • Proc Array
    • write notice records
    • diff pool

    此处PageArray中每个entry都是一个page,包含的数据有

    • 页的当前状态:no access, read-only access, read-write access
    • 当前持有当前页的processor
    • 一个以processor_id为index的array,每个array index都是来自processor的write notice,并且以interval排序,如果write notice对应的diffs已经创建,则会有一个指针指向

    每个ProcArray则是记录了processor知道的intervals records,每个interval records指向了当前intervals知道的write notices。

    下面举个例子:

    M0: a1 x=1 r1  a2 y=9 r2
    M1:              a1 x=2 r1
    M2:                           a1 a2 z = x + y r2 r1
    

    有M0,M1,M2,3个进程,其中a和r代表acquire和release,那此时M2中获取到x的值是M0设置的x=1还是M1设置的x=2呢?

    这就要引入一个叫vector clock的东西,通过一组图来看下是怎么回事。


    图片

    起初P1,P2,P3开始counters都是0,


    图片
    当有本地事件发生的时候,P1对应的counter加1
    图片

    P3也发生了本地事件,counter加1


    图片
    当P1收到P3发送来的消息的时候,本地counter加1,其余counter进行更新
    图片
    P1发送事件自己的counter加1,P2接收事件,自己的counter加1,其余counter进行更新;
    上面的图基本上就说明了vector clock是怎么回事,维护了分布式系统中的一个因果关系。

    现在我们再回到之前的例子:

    M0: a1 x=1 r1  a2 y=9 r2
    M1:              a1 x=2 r1
    M2:                           a1 a2 z = x + y r2 r1
    

    此时M2怎么知道x等于几?当M2在获取锁1的时候,会去请求前一个释放锁的进程,可能是M1也可能是M0,并将自己的vector clock传递过去,然后锁的前一个releaser同自己的vector clock比较,将改变传递过来,具体通过一个图来说明:


    图片

    P1发送Vector timestamp给releaser P3


    图片
    P3对于已经更新的counters附上invalidations
    图片

    P3将其发送给P1


    图片
    P1收到invalidation后,请求diffs,并将diffs应用到page。

    性能

    参考

    Treadmarks: Distributed Shared Memory on Standard Workstations and Operating Systems - PowerPoint PPT
    TreadMarks - PowerPoint PPT Presentation

    这是6.824: Distributed Systems的第12课,你的鼓励是我继续写下去的动力,期待我们共同进步。

    相关文章

      网友评论

        本文标题:分布式共享内存

        本文链接:https://www.haomeiwen.com/subject/dweppttx.html