DSM

本文是論文Treadmarks: Distributed Shared Memory on Standard Workstations and Operating Systems 的讀書筆記庆揪，水平有限障本，若有任何錯誤的地方膘婶，請不吝指出肢藐。

本文是mit 6.824 Schedule: Spring 2016的第12課，前面課程內(nèi)容可以在分布式找到，更多詳細資料可以到：distributed-system查看。

介紹

在并發(fā)編程中碱呼，我們需要處理兩個關鍵問題：

• 線程之間如何通信
• 線程之間如何同步

通信是指線程之間以何種機制來交換信息蒙挑，在命令式編程中，線程之間的通信機制有兩種：

• 共享內(nèi)存
• 消息傳遞

我們從通信和同步兩個維度來看共享內(nèi)存和消息傳遞愚臀。

在共享內(nèi)存的并發(fā)模型里忆蚀，線程之間共享程序的公共狀態(tài)，線程之間通過寫-讀內(nèi)存中的公共狀態(tài)來隱式進行通信姑裂。在消息傳遞的并發(fā)模型里馋袜，線程之間沒有公共狀態(tài)，線程之間必須通過明確的發(fā)送消息來顯式進行通信舶斧。
同步是指程序用于控制不同線程之間操作發(fā)生相對順序的機制欣鳖。在共享內(nèi)存并發(fā)模型里，同步是顯式進行的茴厉。程序員必須顯式指定某個方法或某段代碼需要在線程之間互斥執(zhí)行泽台。在消息傳遞的并發(fā)模型里，由于消息的發(fā)送必須在消息的接收之前矾缓，因此同步是隱式進行的怀酷。

通過上面的介紹我們知道了共享內(nèi)存是一種隱式的通信手段，需要顯示的方法來實現(xiàn)同步嗜闻。

而在分布式系統(tǒng)中蜕依，我們希望能夠的是能盡可能的利用普通的機器，來達到并行計算的目標琉雳，而distributed shared memory (DSM) 在分布式系統(tǒng)中實現(xiàn)了共享內(nèi)存样眠，讓所有process都共享一個全局地址空間，通過提供簡單的api翠肘，方便process的訪問吹缔。
先讓我們看下api

其中barrier，acquire和realease用于同步操作锯茄，一旦調(diào)用barrier等待所有process都到達這個點后才繼續(xù)執(zhí)行祖驱，acquire和realease則用于鎖的獲取和釋放。

設計

在實現(xiàn)DSM時妻献，主要考慮的兩個問題是：

• 一致性
• False Sharing

首先在分布式系統(tǒng)中糯耍，為了提高性能，往往會對同一份數(shù)據(jù)做本地緩存喂急，加快訪問格嘁，但是數(shù)據(jù)雖然有多份，但是需要保證數(shù)據(jù)的一致性廊移，同一份數(shù)據(jù)可能有多個副本糕簿，一旦數(shù)據(jù)做出了改變探入，需要通知所有持有副本的process，數(shù)據(jù)已經(jīng)改變了懂诗。

我們先來看下如果要實現(xiàn)這種嚴格的數(shù)據(jù)改變蜂嗽，就必須可見，系統(tǒng)需要怎么做殃恒？

如上圖所示植旧，每個寫操作一旦完成，必須要通知所有其他的進程該行為离唐，帶來的問題是：

• 消息數(shù)的增加
• 延遲

這種嚴格的一致性被稱為是：sequence consistency病附，一般系統(tǒng)為了其他一些因素，都會做出一些trade-off亥鬓，TreadMarks則是采取了release consistency完沪，只有在同步點上才要求數(shù)據(jù)同步，看圖：

使用release consistency的目標是：

• 減少消息數(shù)
• 減少延遲

那此處具體的同步點是什么時候呢嵌戈？
前面提到過TreadMarks提供了acquire和release兩個同步操作丽焊，當發(fā)生同步操作的時候，進行數(shù)據(jù)的同步咕别。

Eager

此時在release的時候技健，將在acquire和release之間的數(shù)據(jù)改變廣播給所有的持有數(shù)據(jù)副本的process，但是由于需要等待所有副本答復說已經(jīng)收到通知惰拱，release操作會比較耗時雌贱。

Lazy

• 只有當下次acquire鎖的時候才會去獲取改變
• 獲取再取有效的減少了消息數(shù)

Eager和Lazy在實際運行中減少的消息數(shù)偿短，可以通過下圖直觀的看到：

下一個需要解決的問題是：False Sharing欣孤，那什么是False Sharing？

• 采用copy-on-write機制
• 一旦某個進程被授權訪問write-shared的數(shù)據(jù)赞枕，將包含數(shù)據(jù)的頁標志為copy-on-write
• 第一次更改頁數(shù)據(jù)的時候，會創(chuàng)建一個備份：twin

圖片

當release操作的時候，TreadMarks會：

• 比較twin和修改過后的數(shù)據(jù)
• 將不同保存為diff
• 通知所有的副本（write notice）
• 當其他process訪問改頁的時候炕婶，會去請求diffs

創(chuàng)建diffs

TreadMarks在diffs的創(chuàng)建上姐赡，采取了Lazy的策略，只有當其他processor請求頁改變的時候柠掂，才會去創(chuàng)建diffs项滑。

數(shù)據(jù)結構

主要數(shù)據(jù)結構如上圖所示，包括了

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

此處PageArray中每個entry都是一個page陪踩，包含的數(shù)據(jù)有

• 頁的當前狀態(tài)：no access, read-only access, read-write access
• 當前持有當前頁的processor
• 一個以processor_id為index的array杖们，每個array index都是來自processor的write notice悉抵，并且以interval排序肩狂，如果write notice對應的diffs已經(jīng)創(chuàng)建，則會有一個指針指向

每個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，

圖片

圖片

P3也發(fā)生了本地事件钾恢，counter加1

圖片

圖片

現(xiàn)在我們再回到之前的例子：

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發(fā)送Vector timestamp給releaser P3

圖片

圖片

P3將其發(fā)送給P1

圖片

性能

略

參考

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

這是6.824: Distributed Systems的第12課鸟悴，你的鼓勵是我繼續(xù)寫下去的動力，期待我們共同進步奖年。