Composable Memory Transactions

Citation

@InProceedings{harris2005composable,
author = {Harris, Tim and Marlow, Simon and Peyton Jones, Simon},
title = {Composable memory transactions},
booktitle = {PPoPP '05: Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming},
year = {2005},
month = {January},
abstract = {Writing concurrent programs is notoriously difďŹcult, and is of increasing practical importance. A particular source of concern is that even correctly-implemented concurrency abstractions cannot be composed together to form larger abstractions. In this paper we present a new concurrency model, based on transactional memory, that offers far richer composition. All the usual beneďŹts of transactional memory are present (e.g. freedom from deadlock), but in addition we describe new modular forms of blocking and choice that have been inaccessible in earlier work.},
publisher = {ACM Press},
url = {https://www.microsoft.com/en-us/research/publication/composable-memory-transactions/},
pages = {48-60},
isbn = {1-59593-080-9},
edition = {PPoPP '05: Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming},
}

どんなもの？

そもそもの課題

並行処理を書くのは難しい！！！！（それはそう）

着目点1. 複数の操作をアトミックに行う

例えば、ある辞書がスレッドセーフだったとしても、2つの辞書への操作をアトミックに行おうとすると大変(p.2)。

// 辞書 t1 から A を削除
// delete 操作はアトミック
v := delete(t1, A);

// （もしこの間に他のスレッドに割り込まれたらどうしよう……）

// 辞書 t2 に t1 の A としてもともと入っていた内容を挿入
// insert 操作はアトミック
insert(t2, A, v);

ここで、削除して挿入するという操作をアトミックに行える関数をライブラリが提供すればいいのでは？ → 抽象化 is どこへ……

通常のプログラムでは、並行処理に対して安全なコードを高い抽象化度で書くことはできない。

着目点2. ブロッキング

例えば、キューがあるとして、キューに何かエンキューされるまで待つみたいな処理が書きたい！

dequeue() {
    // キューに1件以上入るまで待機
    wait until number_of_items > 0;

    // （ここで他のスレッドが dequeue することは許されない！）
    
    v := first_item; // キューの1個めを取得
    remove_first(); // キューの1個めを削除
    return v;
}

効率的なブロッキングの手段と着眼点1の要素が欲しい！

つくったもの

並行処理で発生するメモリ操作の原子性を保証し、その処理を簡単に合成できる言語拡張を Haskell 上に構築した（GHC 6.4 から搭載されている）。

ソフトウェアによって、メモリ操作の原子性を保証することから、これを Software Transactional Memory と呼ぶ。

この STM ライブラリを使って着眼点1のコードを書くとこんな感じに。

atomic (do {
    -- delete と insert はいい感じに STM モナドとして実装されているものとする
    v <- delete t1 A;
    insert t2 A v
})

着目点2のほうはこんな感じに。

atomic (do {
    i <- readTVar number_of_items;
    if (i > 0) then do {
        v <- readTVar first_item;
        -- remove_first はいい感じに STM モナドとして実装されているものとする
        remove_first;
        return v;
    }
    else retry
})

先行研究との比較

1. キャンセルできない操作

ネスト可能な atomic ブロックを持った言語が提案されたが、トランザクションのコミットに失敗しても、キャンセルできない操作（すなわち外部への I/O）についてはどうにもならないという問題があった
これに対し、ロックで対応した例もあった

本論文では、そもそも Haskell が I/O 操作を IO モナドで隔離しているのを利用して、 STM の中で I/O を実行できないことを型で保証した。

2. ブロッキング

本論文と似たような機能を持つ言語として Scheme 48 があったが、これは着眼点2で挙げたブロッキングについて何も提供されていない。

それに対し、本論文では、 retry を定義し、トランザクションログ内に参照した記録があるストレージ(TVar)に変更があったときに、 STM 操作を再実行する、という動作をすることで、効率よくブロッキングを行えるようになった。

この技術の重要なポイント

Figure 1 に示すインターフェイスによって、 STM 操作を隔離した。このことによって、 STM 操作中に I/O が発生しないことを保証しつつ、 do 構文によって簡単にプログラムが書けるようになっている。

STM モナドは、最終的に TVar への変更を行うので、実行結果は I/O である。 atomic 関数に STM モナドが渡されることで、 STM 操作が実行され、 IO モナドとして結果を得ることができる。

課題

1. スレッド間の1対1通信

Concurrent ML では、スレッド1とスレッド2が、相互に値を交換する、という操作が行える。本論文の仕組み、および例に出した MChan では、スレッドを特定するはできない。

2. 他の言語への組み込み

Haskell のような宣言型言語ではなく、命令型言語にも組み込めないだろうか？ → 不可逆 I/O を制限することができる言語が少ない厳しい

次に読むべき論文は？

atomic ブロックを導入した例として挙げられていた: Tim Harris and Keir Fraser. 2003. Language support for lightweight transactions.

メモ

retry は、他のスレッドが変化を加えない限り先に進めなくなるので、ブロッキングを表す。

Concurrent Haskell は OS のスレッドではなく、自分で制御しているので、ランタイムの C 関数が呼ばれている間にスレッドが切り替わることはない → STM ランタイムを実装する上で便利

Each entry contains a reference to the TVar involved, the old value held in the TVar when it was first accessed in the transaction

トランザクションを開始したときの値じゃないとまずくない？ → commit の仕組み的にそうでもない気がしてきた

例外が起きても、見ているメモリが最新でないならば retry する（それが原因の例外である可能性があるから）

条件違反を起こしたときに停止しなくなる場合があるから、スレッドが切り替わったときは必ず STMIsValid する

retry と評価される → キューに AtomicFrame とログを保存 → ほかのスレッドが STMCommit したときに、キューの中身に対して STMIsValid して False なら再スケジュール（True なら関係ある TVar が更新されていないので再実行しても無意味）