Software Transactional Memory の雰囲気メモ
wikipedia の ( Software Transactional Memoryのページ ) を眺めたまとめのメモと、toy 実装をしてみた話。
stm の rust 実装 見ながら書いてたんだけど、そのまま rust で書くのもあれなのでなんとなく go で書いてみた。 ちなみに int にしか対応していない完全なトイ実装。
STM
並列プログラミングをする際に、共有メモリへのアクセスを制御するための機構のことで、ロックを使用した排他制御機構の代替として使用できる。 例えば、ロックを使用してスレッドセーフなプログラムを実現するには以下のようになる。
v := 1 m := new(sync.Mutex) go func() { m.Lock() v += 1 m.Unlock() }() go func() { m.Lock() v += 1 m.Unlock() }() ...
これを STM で実現すると以下のようになる(自分で実装した STM だけど大体ほかの実装もこんなシンタックスになってるはず)。
tvar := istm.NewTVar(1) go func() { tv, _ := istm.Atomically(func(t *istm.Transaction) (int, error) { v := tvar.Read(t) tvar.Write(t, v+1) return v, nil }) fmt.Printf("t1: %v\n", tv) }() go func() { tv, _ := istm.Atomically(func(t *istm.Transaction) (int, error) { v := tvar.Read(t) tvar.Write(t, v+1) return v, nil }) fmt.Printf("t2: %v\n", tv) }() ...
Atomically
のブロック内は必ずアトミックであることが保証されているので、STM の方ではロックを(シンタックス上は)使用せずにスレッドセーフなプログラムを書くことができる。
ロックを使用する問題点として、デッドロックやライブロックが発生するコードが書けてしまうこと、ロックし忘れてレースコンディションが発生する恐れがあること、
優先順位の逆転 が発生することなどがある。
STM はロックに比べて高いレベルの抽象化を提供しているので、そのあたり問題をいい感じに回避している。
また、STM の利点としてスケールしやすいという点もある。
ロックを用いた場合、大雑把にロックを取るとそこがボトルネックとなりスケールしないプログラムになってしまう(逆に細粒度にロックを取ろうとするとバグを生み出しやすいという問題もある)。
しかし、STM は変更をコミットする瞬間だけロックを取ることで大きなロックを取る必要がなくなりスケールするプログラムを意識しなくても書くことができる。
問題点もあって、コミットにする際に一貫性が取れていないとすべての処理をアボートして、再度処理を初めからすべて実行し直すためオーバヘッドが大きいというのがある。
実装
DB で言うところの楽観的ロックみたいな実装をしている。
アトミックなブロック中 (istm.Atomically
に渡されたクロージャ) での変更はトランザクションでログとして持っておき、ブロックが終了するときにまとめて変更をコミットする(このへん)。
コミット処理の際に一貫性を検査し、他のトランザクションと衝突していたら自分側の変更をすべて破棄する。これを成功するまで何度も再実行する。
参考
バリア同期の実装
Java Concurrency in Practice の 5.5.4 Barrier の話
バリア同期とは
バリア同期とは、各スレッドの実行の進行具合を合わせるために使用する同期機構のこと。 複数スレッドにまたがった依存関係のある計算(処理)の完了を待って、処理を実行する際に使用する。 たとえば、時間のかかる計算 A と B の処理を C で使用する時、C を実行する前に A と B の終了をバリア同期で待ってから実行するというような使用方法がある。
実装
実際に Ruby で表現すると以下のようになる。
イニシャライズ時に渡された数(n
)になるまでそのスレッドを待ち状態にしておき、待ち状態数が n
になったら @cv.broadcast
をして待ち状態のスレッドを起こすということをしている。
class CyclicBarrier def initialize(n) @n = n @wait_count = 0 @mutex = Mutex.new @cv = ConditionVariable.new end def wait @mutex.synchronize do @wait_count += 1 if @wait_count == @n @cv.broadcast else @cv.wait(@mutex) end end end end
使用部分は以下のようになる。
Runner#reduce_process
が別スレッドで走らせた Runner#process
の計算結果を使用するという例。
実際は sleep(i)
の部分に重たい処理が来ることになる。
実行結果を見るとわかるんだけど、 Runner#reduce_process
は Runner#process
の実行の終了を待ってから実行されていることがわかる。
class Runner def initialize(n) @n = n @cb = CyclicBarrier.new(n) @queue = Queue.new end def run (@n - 1).times.map do |i| Thread.start(i + 1) { |j| process(j) } end reduce_process end private def reduce_process puts "[Wait] reduce process" @cb.wait puts "[Start] reduce process" result = 0 until @queue.empty? result += @queue.pop end puts "[Done] result is #{ans}" end def process(i) puts "[Start] process #{i}" sleep(i) @queue << i puts "[Wait] process #{i}" @cb.wait end end Runner.new(4).run
実行結果
$ ruby runner.rb [Start] process 2 [Start] process 3 [Wait] reduce process [Start] process 1 [Wait] process 1 [Wait] process 2 [Wait] process 3 [Start] reduce process [Done] result is 6
コードは全体はこちら↓↓↓
Lock Striping についてとその実装
Java Concurrency in Practice の 5.2.1. ConcurrentHashMap にて Lock Striping というロックの方法が出てくる。 Lock Striping の説明と実装、および簡単にパフォーマンスを測ったのでそのメモ。
- 作者: Brian Goetz,Tim Peierls,Joshua Bloch,Joseph Bowbeer,David Holmes,Doug Lea
- 出版社/メーカー: Addison-Wesley Professional
- 発売日: 2006/05/09
- メディア: ペーパーバック
- 購入: 7人 クリック: 14回
- この商品を含むブログ (22件) を見る
Lock Striping とは
Lock Striping とは Array や HashMap などのオブジェクトに対して、複数スレッドから書き/読み込む場合に、そのオブジェクト全体のロックを取るのではなく部分的にロックを取ること。 例えば、Array オブジェクトの 0 から 9 は Mutex1、10 から 19 は Mutex2 が管理するようにすること。 このようにすることで、依存関係のない操作を複数スレッドで実行する際 (上の例なら Arrayオブジェクトの index 1 と 11 への書き込みなど) に互いの操作を待たなくて良くなり並列度が上がり、パフォーマンスの向上が見込める。
1 つの Mutex オブジェクトでロックする際の問題
Array や Map などのオブジェクトに対して、複数スレッドから書き込み/読み込みがある時にロックが必要になる。
同じキーに対して複数のスレッドから書き込んでしまった場合にレースコンディションが発生するからである。
1 つのオブジェクトに対して 1 つの Mutex オブジェクトを使用すると、ロックの粒度が適切でない時がある。
たとえば、以下のように Map オブジェクト dict
に Thread 1 (go の場合は goroutine) では "foo"
というキーに 値 1
をセットし、Thread 2 では "bar"
というキーに 2
をセットするとする。
この時 Thread 1 と Thread 2 の操作は互いに独立しており、並列に実行してもレースコンディションが発生しないためそれぞれの Thread を並列に実行できた方がパフォーマンスがよくなる。
しかし、dict
に対して 1 つの Mutex オブジェクトを使用すると、互いに独立している操作であっても dict
への操作は並列に実行することができなくなる。
dict := new(map[string]map) // In Thread 1 dict["foo"] = 1 // In Thread 2 dict["bar"] = 2
実装
Lock Striping な辞書の実装。
キーは文字列、値は数字のみにしている。
hash 関数に FNV prime を使っている。
Hash値(とbucket sizeの剰余)ごとに bucket
をもって、それごとにロックを管理している。
その為、ちがう bucket であれば並列に実行可能になる。
パフォーマンス
スペック
- OS: macOS Sierra
- Processor: Intel® Core™ i7-6567U CPU @ 3.30GHz
- Memory: 16 GB 2133 MHz LPDDR3
- go version: go1.8 darwin/amd64
計測したコード
結果
synchronizedDict~
が dict に対して 1 つのロックを取っている方で、 stripedDict~
が Striping Lock をしている方。
最後の数 (たとえば、synchronizedDictWriting1
の 1
) は Write する Worker の数を表している (1,3,5 でためした)。
だいたい予想通りの結果になっているようにみえる。
write する worker が 1 つのとき (並列に実行していない時) は hash 値の計算などのオーバヘッドがあるから若干 stripedDict のほうが遅くなっている。
それ以外はロックが分散されて、並列度が上がったためパフォーマンスがよくなっている。
Elapsed Time in synchronizedDictWriting1: 43.632465ms Elapsed Time in stripedDictWriting1: 35.341727ms Elapsed Time in synchronizedDictWriting2: 62.054392ms Elapsed Time in stripedDictWriting2: 48.307852ms Elapsed Time in synchronizedDictWriting5: 172.436661ms Elapsed Time in stripedDictWriting5: 89.864355ms
リポジトリごとに user.name と user.email を変更する
会社で Github Enterprise を使っているので、github.com の方の user.name
と user.email
でコミットしてしまわないようにリポジトリごとに設定を変更できるようにした。
gitconfig にあった user.name
と user.email
をけして、useConfigOnly
を true
にした。
こうすることで、リポジトリごとに user.name
と user.email
を設定しないと *** Please tell me who you are.
などといわれてコミットに失敗するようになり、誤ったユーザでのコミットを防げる。
変更前
[user] name = ganmacs email = ganmacs@gmail.com
変更後
[user] useConfigOnly = true
あとは、シェルに以下のような関数を定義しておけば良さそう。
function company() { git config user.name "namae" echo "Set user.name as $(git config --get user.name)" git config user.email "foo@bar.com" echo "Set user.email as $(git config --get user.email)" } function private() { git config user.name "ganmacs" echo "Set user.name as $(git config --get user.name)" git config user.email "ganmacs@gmail.com" echo "Set user.email as $(git config --get user.email)" }
その他
pre-commit hook などでディレクトリごとに自動で設定する方法も考えたが、大げさだなと思ってこの方法に落ち着けた。 もっといい方法があれば教えて欲しい。
Ruby の Monitor
Ruby には Monitor というクラスがあるんだけど、よく見るわりに Mutex との違いをよくわかっていなかった。 たまたま Java Concurrency in Practice を読んでいたら 2.3.2 Reentrancy で同じような概念の話が出てきて、少しわかった気がするのでそのメモ。
- 作者: Brian Goetz,Tim Peierls,Joshua Bloch,Joseph Bowbeer,David Holmes,Doug Lea
- 出版社/メーカー: Addison-Wesley Professional
- 発売日: 2006/05/09
- メディア: ペーパーバック
- 購入: 7人 クリック: 14回
- この商品を含むブログ (22件) を見る
Monitor とは
Ruby の Monitor は何度も lock 出来る Mutex とドキュメントに書いてある。
特になんの意味もない例だけど以下のようにロック中にさらにロックできる(もちろん同じスレッド内で)。
もしこのコードを Mutex を使用して m = Mutex.new
とした場合、2回めの m
のロックする部分(m.synchronize
)でデッドロックが発生するが Monitor を使用すると発生しない。
m = Monitor.new m.synchronize do m.synchronize do # your code end end
使い所
たぶん使い所は、すでにあるコードを組みわせてアトミックな処理をするところ。
下のようなコードのような感じ。もともと Nanika
クラスに sugoi
というスレッドセーフなメソッドがあったとする。
この時、メソッド内でアトミックに sugoi
を2回呼び出す ultra_sugoi
というメソッドを新たに追加しようとしたときに Monitor が使えそう。
Monitor ではなく Mutex を使用すると、ultra_sugoi
内でロックを取ってから sugoi
のメッソド呼び出しが発生して、 sugoi
内で またロックを取りに行きデッドロックが発生する。
しかし、Montior を使用すると何度でもロックが成功するので、 sugoi
をアトミックに2回呼び出せる。
class Nanika def initialize @monitor = Monitor.new @sugoi_value = 0 end def sugoi @monitor.synchronize do @sugoi_value += 1 end end def ultra_sugoi @monitor.synchronize do sugoi sugoi end end end nanika = Nanika.new [*1..2].map { Thread.new do nanika.ultra_sugoi end }.each(&:join)
その他
javaの本では reentrant という言葉で説明されていた。
reentrancy とは
Reentrancy means that locks are acquired on a per-thread rather than per-invocation basis.
リエントラント性とは、呼び出し単位ではなくスレッド単位でロックが取得される。
Lock with reentrant
同じスレッドであれば、何度でもロックを取得できる ロックしたスレッドとそのスレッド内でのロック保持数を記録しておく。Ruby の Monitor。
Lock without reentrant
呼び出し(処理)単位でロックを取っているので、同じスレッドであっても再度ロックを取れない。 単純にロックされているかどうかだけを見る。Ruby の Mutex。
RubyはGILが
そうね
リーダ選出: ring アルゴリズム
Raft Consensus Algorithm をみつけてリーダ選出とは、となったので調べてちょっと書いてみたメモ。なお、この記事では raft のことは書いてない。
リーダ選出とは
リーダ選出アルゴリズムとは、分散システム内で特別な役割を持ったノード(プロセス)を選出するためのアルゴリズムのこと。 リーダを決め、中央集権的にシステムを動かすことで、権限が分散している場合にくらべシステム内の一貫性を容易に保てる1。 たとえば、分散メモリがあるとすると、あるプロセスが分散メモリに値を書き込む際には、そのプロセスはロックを取ってから書き込みをしないとレースコンディションが発生する可能性がある。この時、一つのプロセスをリーダにし、そのプロセスが他のプロセスにロックを提供し、書き/読み込みをしたいプロセスがロックを取ってクリティカルコンディションに入ることで安全に分散メモリを操作できる。
ring アルゴリズム
ring 型のネットワークを考える。 ring型ネットワークとは、それぞれのプロセスが自分以外の2つのプロセスと結びついてる様なネットワーク。 要は以下の形をしたネットワーク。
CS 551: Synchronization, Token Ring Election Algorithm Exampleより
この記事での ring アルゴリズムは以下の話。wikipediaの分散システムのページを見てると、これは ring アルゴリズムの中でも Rings with unique IDs というやつっぽいのだけど、いまいち全体の世界観をつかめていないのでよくわかってない。
- アイデア : CS 551: Synchronization, A Token Ring Election Algorithm
- 図 : CS 551: Synchronization, Token Ring Election Algorithm Example
このアルゴリズムは election message を送るステップと coordinator message を送るステップの2つのステップに分かれる。
まず、現在のリーダが何かしらの理由 (通信不能になったり、プロセスが死んだり) で fail したところからリーダ選出が始まる。
リーダが fail したのを他のプロセスが検知して election message というメッセージを次のプロセスに送る。もし、次のプロセスが fail したリーダのプロセスだった場合はその次のプロセスに送る。
election message とは自分の id を追加した配列を含んでいるメッセージのこと。例えば、下の図の場合は P3 が自分の id である 3
というメッセージを、それを受け取った P5 は、受け取ったメッセージに自分の id である 5 を追加した 3,5
というメッセージを次のプロセス P0 に送る。
この 3
であったり、3,5
であったりを election message といっている。そして、election message が ring を一周して元のプロセス(図ではP3)に戻ってきたところで election message を送るステップは終了する。
CS 551: Synchronization, Token Ring Election Algorithm Exampleより
ここからが、次の coordinator message を送るプロセスになる。
election message が ring を一周して、最初にリーダの fail を検知したプロセスに戻ってきたとき、election message の中身は ringに所属しているプロセスのidが全て含まれている。この id の中から一番大きな値を選びだし、その id が次のリーダだということを他のプロセスに周知するメッセージが coordinator message になる。coordinator message が ring を一周して元のプロセスに戻ってきたところで coordinator message を送るステップも終了しリーダが決定する。
例えば下の図では、P3が最初にリーダの fail を検知したプロセスだとして、そこに返ってきた election message が 3,5,0,1,4
だとすると、この中から一番大きな数である 5 を次のリーダ(つまりプロセス P5 )とする。そこで P3 は 「次のリーダは P5 だ」というメッセージまた他のプロセスに送信する。このメッセージを coordinator message という。他のプロセスも自分の次のプロセスに「次のリーダは P5 だ」というメッセージをおくる。そして、P3 に戻ってきたところリーダ選出を終えて P5 がこのシステムのリーダとなる。
CS 551: Synchronization, Token Ring Election Algorithm Exampleより
作った
ring アルゴリズムを実装してみた。
ring アルゴリズム自体の実装は https://github.com/ganmacs/eve/blob/master/lib/eve/agent/ring.rb この辺にある。仕様的なものを見つけることができなかったので、上の図を見て気持ちを感じて実装した。
Linuxシステムプログラミング8章
Linuxシステムプログラミングの8章メモリ管理の雑なメモ。 下に行くほど雑になってそう。この本。
- 作者: Robert Love,ロバートラブ,千住治郎
- 出版社/メーカー: オライリージャパン
- 発売日: 2008/04/16
- メディア: 大型本
- 購入: 5人 クリック: 181回
- この商品を含むブログ (31件) を見る
プロセスアドレス空間
ページとページイン/アウト
- 仮想アドレス空間はページで構成される
- サイズはマシンによる 32だと4KB、64ビットマシンだと8KB
- ページには有効と無効という概念がある
- 有効なページは実際に対応する物理メモリ、またはディスク上のファイルがが存在する
- 無向なページはアクセスするとセグフォになる
- プログラムが物理メモリに存在せず二次記憶装置に存在するページにアクセスしようとすると、ページフォルトをMMUが発生させる
ページ共有とcopy-on-write
- (異なるプロセスの)異なる仮想アドレスから物理メモリ内のデータを共有できる
- 読み書き専用、読み取り専用どちらでも良い
- 書き込む処理は二種類ある
メモリ領域
動的メモリ割り当て
- 動的メモリは、コンパイル時ではなく実行時に割り当てるもの
- 実行時になるまで、実際のサイズなどはわからない
- cだと
malloc
で動的メモリ割り当て出来る- 成功すると、割り当てたメモリ領域の先頭アドレスを返す
配列割当
- 配列の割当には
calloc
をつかうmalloc
と違って0で初期化する
メモリ領域のサイズ変更
realloc
でメモリ領域のサイズを変更できる
動的メモリの解放
- 動的に割り当てたメモリは明示的に解放するまでプロセスアドレスの一部として存在し続ける
free
を使う- 開放しないとメモリリークする
- 解放後のメモリにアクセスしてはいけない(ダングリングポインタ)
アラインメント
- ハードウェアからみたメモリ領域とアドレスの関係
- データサイズの定数倍のメモリアドレスへ配置された変数を自然なアライメントという
- 32ビットの変数がメモリ上で4の倍数のアドレスに配置されているとき
アラインメントされたメモリの割当
- コンパイラとCライブラリがよしなに解決してくれる
- 32ビットシステムでは8バイト,64ビットだと16バイト境界にアライメントされる
posix_memalign
を使用すると、任意の倍数でアライメントされたsizeバイトの動的メモリを割り当てられる
他のアライメント問題
- 非標準の型
- 構造体のアライメントはメンバの最大サイズに合わせる
- 最大サイズを持つメンバが4バイト境界でアライメントされる32ビット整数なら、その構造体は4バイト以上のアライメント
- パディング(padding)が必要。
- char(1バイト)のあとにintのメンバ(4バイトでアライメントされる)がある場合、charの後ろに3倍とのパディングが必要
- 共用体のアライメントはメンバの最大サイズに合わす
- 配列アラインメントは要素に合わせる
- 構造体のアライメントはメンバの最大サイズに合わせる
- ポインタ
- 以下の例では、unsigned longは4 or 8バイト境界に割り当てられるのに、charはほぼ確実に1バイト
- そこで c をロードするとアラインメント違反
- 違反の結果はアーキテクチャ依存でクラッシュすることもある
char greeting[] = "Ahoy Matey"; char *c = greeting[1]; unsigned long badnews = *(unsigned long *) c;
データセグメントの管理(ヒープ領域)
- でたーセグメントを直接操作する関数はあるが、
malloc
などが使いやすく機能も豊富であるためほぼ使われていない brk
はデータセグメントの末尾(break point)を渡された場所を変更する
無名メモリマッピング
- 典型的な
malloc
はデータセグメントを2の累乗のサイズの領域が並んだ状態に分割し,要求されたサイズに最も近い領域を貸す- 直前の領域がフリーの場合はつなげて,一つの大きなフリー領域にする
- 戦闘だった場合は領域を縮めてカーネルに返す
- バディメモリ割り当てシステムという
- 内部フラグメンテーション - 要求されたメモリより大きなメモリ領域を返す問題
- 外部フラグメンテーション - サイズ分のメモリ領域があるにも関わらず,複数のメモリ領域に分断されている
領域Bと領域Aが隣接しており,領域Aがbreakpointに隣接している場合,Bを開放してもAが終わらない限り開放されない
巨大なメモリ割り当てをするとglibcはヒープを使用せす無名メモリマッピングをする
- ファイルを使わない
- 巨大で,0に初期化された領域を使用できる
- 本来のヒープの外にあるのでフラグメンテーションが発生しない
- メモリ領域はサイズ,アクセスパー密書の変更が可能
- 短所
- メモリのサイズがページングサイズの整数倍になる,要求サイズがページサイズより小さいと無駄な領域が発生する
- カーネルからのヒープ割当に比べてオーバヘッドが大きい
無名メモリマッピングの作成
munmap
システムコール(mmpa
に MAP_ANONYMOUSを指定しても行ける)
/dev/zero のマッピング
高度なメモリ割り当て
mallopt
を使用してカーネルパラメータを変更できる。
メモリ割り当てのデバッグ
メモリ割り当て統計情報
mallinfo
でメモリ割り当ての統計情報を得る
スタック上のメモリ割り当て
- スタックはプログラムのオート変数(automatic variable)を格納する場所
alloca
を使ってスタック上で動的にメモリ割り当てをする- メモリ領域はスタック上に取られる
- つまり、
alloca
を実行した関数がリターンしたら解放/破棄される -> freeしなくていいのでコードが簡潔に alloca
を関数コールのパラメータ内で使用すると、関数パラメータの用のスタック領域にメモリを割り当ててしまうため使用を避ける
スタック上へ文字列をコピー
- 文字列の一時的なコピー等に使える
- そのためのインターフェイスとして、
strdupa strndupa
がある
- そのためのインターフェイスとして、
メモリ割り当て方法の選択
- malloc
- 単純だが割り当てられたメモリがゼロクリアされていない
- calloc
- 配列の割当が容易でゼロクリアされてる、配列以外には使いづらい
- realloc
- メモリサイズを変更できる、ソレ以外使えない
- brk and sbrk
- ヒープを完全に制御できる、低位すぎるインターフェイス
- 無名メモリマッピング
- 共有可能、アクセスパーミッションもできる。サイズが大きいときにも使える。メモリが小さいと効率が落ちる
- posix_memalign
- 任意サイズの境界に従うメモリを割り当てる。移植性に難がある
- memalign and valloc
- alloca
- 高速なメモリ割り当て、解放不要、サイズの大きな割当には不向き。
- 可変サイズ配列
- allocaとほぼ同じ、スコープを抜けたときに解放される。配列に限り有効
メモリ操作
バイト設定
- memset(void *s,int c,size_t n) sのメモリ領域へcをnバイト分設定
バイト比較
- memcmp(s1,s2,n) s1の先頭からnバイトs2と比較
- 構造体は持つ内部にパディングを含むため正しく比較できない(パディングは不定値だから)
バイト移動
- memmove(dst,src,n) srcの先頭nバイトをdstへこぴー
- メモリ領域が重なっていない場合も正しく動く
- もともと重ならないとわかっている場合にはmemcpyを使用する
バイト検索
- memchrはメモリ領域内の指定されたバイトを検索する
メモリのロック
- linuxのカーネルは不要なページはスワップアウトして、必要に応じてスワップインするデマンドページングを使用している
- この操作は透過的に行われるのでアプリケーションは気にしなくて良い
- しかし意識したい場合もある
- 決定論
- 時間的な制約を持つアプリケーションではページフォルトしてディスクIOが発生して時間的制約を超過してしまう
- セキュリティ
- 機密情報がページアウトされてしまうと、暗号化されずディスクへ保存されてしまう
- 決定論
- 当然全体のパフォーマンスが落ちる可能性があるので気をつける
アドレス空間の一部をロック
- mlock(addr, len)でアドレスの範囲を指定して物理メモリ上にロックする
アドレス空間全体をロック
- mlockallで(カレントプロセスの)メモリ全体を物理メモリ上にロックする
メモリのアンロック
- munlock, munlockall
メモリの遅延割当
- カーネルへメモリの追加を要求すると,カーネルは実際には物理メモリを割り当てずに成功を返す(commit)
- 書き込んだ時点で初めて割り当てる(CoW)
- 遅延できる
- 実際に使用する分(割当要求分ではない)のみ物理メモリを使用する(ページ単位にする)
- コミットしたメモリサイズをシステムの持っているメモリよりも大きくすることが出来る。(overcommit)