2012年9月19日 星期三

Software Transactional Memory

Software Transactional Memory

正在 survey STM，看了一下各語言的支援情形：
  • C#
    • 透過外掛修飾 class，讓這個 class 所有的 data member 都是 private，所有的 setter/getter 都是 virtual，看起來是要讓某個 class template 來 mock 那個 class，但是 setter/getter 是 atomic 的。可以作到 C++ 的 一樣的事情，但是沒有 transactional block 的能力。
    stackoverflow 上面有一篇討論，C# 沒有語言層面的支援，可以透過 library 來完成。
  • Java
    • 也是一樣，透過 library 完成。
  • Golang
    • 應該是沒打算提供 transactional memory，根據這篇討論，go 提供 message passing 作為取代。
  • C++
    • 有兩個 compiler 提供了 atomic block 的實作，一個是 Intel C++ compiler（真是太強了），另外一個是 g++（嘖嘖），大概最後還是選擇以類似 C++ 的形式為目標。

找到 gcc 的 transactional memory 的 spec，正在讀，作一點筆記。

__transaction_relaxed and __transaction_atomic

有兩個關鍵字：
  1. __transaction_relaxed
    2. 用來表示........ 其實我沒看懂。好，看到後面，懂了。這種 transaction 比較 weak，他只保證 transaction 「看起來」沒有跟別的 transaction 有交錯執行，但是，他還是可能跟別 thread 有交錯。舉例來說的話：
    Thread AThread B
    __transaction_relaxed {
    a = 1;
    b = a;
}

    a = 3;
    這樣 Thread A 的 b 有可能會是 4。因為被另外一個 Thread B 的 a = 3; 亂入了。但是呢，如果寫：
    Thread AThread B
    __transaction_relaxed {
    a = 1;
    b = a;
}

    __transaction_relaxed {
    a = 3;
}
    那 b 就保證會是 1 了。因為 relaxed transaction 有保證這個 transaction 看起來不會跟別的 transaction 交錯執行。
    這邊一直強調「看起來」是很重要的，因為實際上，根據實作的細節（且為了效率的考量），執行的過程本身可能還是交錯並行的，只是透演算法的控制，讓執行的結果跟沒有交錯一樣，所以程式設計師就可以很直覺的認定這段程式碼的形為就如同一般 single thread 一樣。
    特性：
    • 其他的 transaction 無法觀察到 __transaction_relaxed 的 partial result
    • 其他的 thread 有可能觀察到 __transaction_relaxed 的 partial result
    • __transaction_relaxed 有可能觀察到其他 thread 的 partial result，有的時候你會想要等待某一個 std::atomic 變數變化來作事情，所以 relaxed transaction 有其必要性
    • 沒有限制 operation 的種類，什麼都可以放進去（如果我沒誤解的話，第 8 頁 45 行）
    • 無法 cancel，因為（見規格書第 9 頁第 16 行）容許有 side effect 的動作（比方說IO）而這些動作無法撤銷
    • Relaxed transaction 可以 nested 含有 relaxed transaction

  2. __transaction_atomic
    3. 用來表示（跟 __transaction_relaxed 比起來）更嚴格的的 transaction。這大概是我們要做的，但不確定前一種要不要作 :P
    這邊現在我也看懂了，也就是說，在 atomic transaction 之下，即使只寫
    Thread AThread B
    __transaction_relaxed {
    a = 1;
    b = a;
}

    a = 3;
    我們也可以保證 b 百分之一是對的，會是 1。哇勒～！這種東西要怎麼作阿！！！
    特性：
    • 只有 "safe" code 可以放在裡面（等一下在 4.2 節說明）
    • 可以被 cancel
    • 不能有 side effect（比方說 IO）

transaction_safe

為了確保 transaction 是「可能」的，atomic block 裡面能寫的程式碼必須要加上一些限制，也就是 atomic block 裡面只能有 "safe" statements 。safe satements 所呼叫的 function 裡面，也只能含有 safe statements（這感覺很像 pure function ，一個 pure function 裡面只能呼叫 pure function）。
為了表明一個 function 是 safe function，需要在函數前面加上 attribute transaction_safe 修飾這個 function（safe 屬性在某些狀況下也有由 compiler 推導出來，見後續）。 transaction_unsafe 用來表明一個 function 不 safe，compiler 就可以阻止他被呼叫（比方說雖然現在這個 function safe，但是未來改版以後可能不 safe，我們知道他未來有不 safe 的可能性，所以我們希望現在就禁止他被使用）。
也可以直接修飾 class，這樣這個 class 所有的 member function 都會被修飾，然後每一個函數也可以各自修飾來 override safety。

__transaction_cancel

可以用 __transaction_cancel 放棄一個 transaction。__transaction_cancel 也可以跟 throw 一起使用，發出一個 cancel-and-throw，也會放棄 transaction。

outer

transaction 可以 nested，也可以用 outer 修飾來阻止被 nested-inside。另外 outer 也可以用來修飾 throw，讓最外圍的 transaction 被 cancle。只有被 outer 修飾的 transaction 可以被這樣 cancel（目前還沒看到為什麼這麼限制的原因，但應該有原因，後面可能會講到），且 function 也需要標上 transaction_may_cancel_outer 來修飾，不然不能發出 outer throw。
exception 被丟出 transaction，且不是使用 cancel-and-cancel 的話，transaction 有效！（這點跟 wiki 上面提到的不一樣，看樣子這個設計不是普世價值）

Safe and Unsafe

單位是 statement。safe statement 或是 unsafe statement。
只有 safe 的 function 可以被呼叫，這些 function 叫做 transaction-safe function，另外一類叫做 transaction-unsafe function。一個 function safe 不 safe 是型別的一部分，所有寫到這個函數的地方都必須一致，不能有的地方 safe 有的地方不 safe。
你可以用一個 unsafe 的 function pointer 指到一個 safe 的 function。但是不能用一個 safe 的 function pointer 指到一個 unsafe 的 function（有點類似 const 的觀念）。

Lambda 也有 safe/unsafe。

如果一個 statement 有以下任何一個特性，那他就是 unsafe：
  • 他是一個 relaxed transaction
  • 他是一個 outer atomic transaction
  • 初始化一個 volatile 或 assign to 一個 volatile 或 read from 一個 volatile 變數
  • 他是一個 unsafe asm，但是什麼 asm 是 unsafe 則是看 implementation dep
  • 呼叫一個函數，但是這個函數不是 transaction-safe 或是 may-cancel-outer（It contains a function call to a function not known to have a transaction-safe or may-cancel-outer function type）到底在講什麼...

一般的 function 宣告，如果你沒有特別指定，他 implicit 根據裡面有沒有含有 unsafe 的 statement 來決定自己 implicit 宣告成 safe 還是 unsafe。但是「直接呼叫自己」的 recursive 函數是 unsafe（應該是說 compiler 會偵測 directly recursive call，但是 indirectly call 就不管），但是你也可以 explicitly 指定 recursive funciton 是 safe。

template function 一樣也會自動推導則，但是，是具現化以後才推導，會看內含 statement safe 不 safe，如果有 unsafe 的 statement，那就 implicit unsafe，如果全部的 statement 都是 safe，那就 implicit safe。

Ctro 跟 Dtor，user defined 的當然就是作一般 (template) function，compiler generated 的，就看 base class 跟 non-static data member 的 Ctor/Dtor 是不是 safe。

Transaction Expression

SomeType myObj = __transaction_atomic ( expr );
SomeType myObj = __transaction_relaxed ( expr );

作用於 expression 求值的過程。也就這個求值的過程，會是 trasactional 的。

transaction expression 不能 nested。也不允許用 outer 修飾，也不能含有 transaction statement，也不能含有 cancel，也不能含有 cancel-and-throw，因為 C++ 不允許 expression 含有 statement。接下來還有一堆超饒舌的，先跳過，看了實在好想吐 orz 18 頁第 1 行。

Function Transaction Blocks

void f() __transaction_relaxed {
}
void f() __transaction_atomic {
}

意思就是這個 function body 內部的執行，會是 transactional。

如果這個 function 剛好是 Ctor/Dtor 的話，那個 base class 跟 member class 的初始化也都是 transactional 的。下面一個例子，比方說這個 class 的每個物件都有一個流水號，根據一個 global variable 來的。

class Foo {
    static size_t _count = 0;
    size_t _id;
    Foo() __transaction_atomic {
        _id = _count++;
    }
}

function transaction block 也可以跟 try block 混在一起。

try __transaction_atomic : Foo() {
}
catch (...) {} // catch 不是 transaction 的一部分

__transaction_atomic try : Foo() {
}
catch (...) {} // catch 是 transaction 的一部分

__transaction_cancel

可以用來放棄一個 transaction，只能寫在 atomic transaction 裡面。transactional expression 不能 cancel，function transactional block 也不能 cancel。

__transaction_cancel [[outer]];

outer cancel statement 只能寫在被標明為 transaction_may_cancel_outer 的 atomic transaction 或是 function block transaction 裡面。

幹……怎麼會這麼多……後面還有……好想哭……
張貼者： 於 2 則留言:
訂閱： 文章 (Atom)