[Java] An Inflatable SeqLock

原文はこちら。
https://blogs.oracle.com/dave/entry/an_inflatable_seqlock

---

以下の内容は、将来のJDKでの、Tupleという値タイプへのアトミックなアクセス方法の実装についてJohn Roleと議論したときにひらめいたものです。

John Rose @ Oracle
https://blogs.oracle.com/jrose/

基本的にはC++のatomic<POD>ファシリティに近いものを持ちます。

C++ Atomic Types and Operations
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2145.html

値タイプの読み取り（ロード）はアクセスの基本モードであることを期待されているので、SeqLocks（Sequential Lock）のようなものを使ってReaderが共有領域に書き込む必要がないようにしたいのです。

SeqLock
https://en.wikipedia.org/wiki/Seqlock
Process synchronization without long-term interlock
http://dx.doi.org/10.1145/800212.806505

しかし同時に、Writerにはクラシックなtest-and-set (TAS) シングルビットのSeqLockよりも洗練されたものを使ってほしいと考えています。
その目的のために、Inflatable SeqLockを使うことができるかもしれません。

davedice/InflatableSeqLock.cpp（Inflatable SeqLockの実装案）
https://gist.github.com/davedice/29178780e22be6ee67a8c21bc4cf5de5

各Tupleは、ワードサイズの、関連するInflatable SeqLockを持ちます。このSeqLockは書き込みのために下位2ビットを留保し、残りは通常のSeqLockバージョンフィールドとして利用します。Writerスレッドが待機している場合、フィールドの残りが待機中スレッドのスタックの先頭を指し示し、スタック上の最も古い要素が保持するバージョン番号が変化します。
この実装はTL2のようなソフトウェアトランザクショナルメモリの実装（STMs）を使うことももちろん可能でしょうが、オブジェクト内の一貫性を気にかける必要がない条件下では、ちょっとやり過ぎかな、と思います。

Software Transactional Memory -- Transactional Locking -- TL and TL2
https://blogs.oracle.com/dave/entry/software_transactional_memory_transactional_locking