Software Transactional Memoryの論文を読んだ

Posted on 2020-12-22 , Tags: STM

Software Transactional Memory(STM) の論文を読んだので、メモを公開しておく

Software Transactional Memory

前回、Haskell の STM 実装から TMVar を参考にして、Ractor::TMVar を作成した。
その後、STM についてもう少し理解してみたいと思い、論文を読んだ。軽くまとめたメモレベルではあるが、今後の自分が参考にするためにも、ここに公開しておく。

論文

背景

  • 並行処理の同期処理について、単純に排他制御するブロッキングな方法だと問題がある。
    • デッドロックへの配慮が必要になる。
  • ノンブロッキングな方法がこの時点でもいくつか提案されていた。

既存手法の課題

  • 既存手法では、独自の命令セットを追加することで解決するものが多い。
    • この時点では Load Linked/Store Conditional くらいの命令しかない CPU がほとんどだった。
    • Load Linked/Store Conditional とは
      • Atomic な Read-Modify-Write を提供するための命令
      • Load Linked で共有メモリからロードしたデータを書き変えて Store Conditional で共有メモリに書き戻す。
      • Store Conditional は、Load Linked 移行にメモリの値が変わっていたら失敗する。
      • ちなみに x86 は Load Linked/Store Conditional の変わりに CAS(Compare & Swap)という命令があるとのこと。
    • Load Linked/Store Conditional で並行処理の制御を行っている既存研究もあった。「協調(cooperative)」な手法。
      • あるプロセス P が a, b を書き換えようとしてプロセス Q が b を持っていたら、先に Q の処理を協力しておわらせて、a, b の処理に戻る。
      • このとき他のプロセス R が a にアクセスしたいとすると、R は P を待たないといけないため、再帰的に待ちプロセスが発生してしまう

STM とは

  • Hardware Transactional Memory をソフトウェアで実現できるようにしたもの
  • Hardware Transactional Memory は Transactional Memory 用の命令を追加する想定の手法

STM の新規性

  • Load Linked/Store Conditional のみをサポートしている CPU でも k-word compare and swap が実現できるようにしたこと

STM の動きの概要

  • 論文中に疑似コードがあるので、それを見るとよい。以下にかなり大雑把にまとめる。
  • 共有メモリの番地ごとに、version、ownership 情報を持てるようにしておく。
    • memory[i] に対して version[i]、ownership[i]があるようなイメージ
  • まず、操作したいメモリの所有権(ownership)を取得
    • Load Linkd(LL)で所有権情報取得 -> version チェック -> Store Conditional(SC)で所有権情報を書き込み
  • 現状の書き込み対象の共有メモリの値をローカル用メモリにコピー
    • LL でローカル用メモリ取得 -> version チェック -> SC で共有メモリの値を書き込み
  • ローカル用メモリに新しい値を書き込み
  • 共有メモリに書き込み
    • LL で共有メモリ取得 -> version チェック -> SC でローカル用メモリの値を書き込み
  • 所有権の開放
    • LL で所有権情報取得 -> version チェック -> SC で所有権情報を空にする
  • version++
  • 「version チェック」 では、開始時の version から version が変わってないかチェックし、変わっていたら最初からやりなおす
    • LL と SC の間で実行することで他のプロセスと競合しないことを保証する

実験結果

パフォーマンスについて、既存手法と比べて、おおむねよかったようだ。
元々 transactional memory は共有メモリ操作の衝突は現実では少ない、という仮定を置いているので、少ない共有メモリを複数のプロセスで触るような場合は極端に性能が落ちる。(例えば、同じメモリ番地にある数値を複数プロセスでカウントアップしていく場合など)

まとめ

STM が当初 LL/SC 向けに作られていたことを知らず、勉強になった。さらに言うと、LL/SC もぼんやりとしか理解できていなかったので、この機会に復習できた。x86 は Compare and Swap があるので、現代の STM はどうしているのかと思ったが、例えば Haskell(GHC)ではここで cas 関数を定義して、そちらを使っているようだ。C/C++にあまり詳しくないが、これが CAS や LL/SC の CPU 命令に変換されると推測している。