ロック競合をなくすSafe Optimistic Lock Coupling、型システムで安全性を保証
CPUコア数の増加に伴い、並行データ構造のスケーラビリティが重要になっている。従来のlock couplingはルートノードのロック競合でスケールしないが、Optimistic Lock Couplingは読み取りを純粋な読み取り専用にし、バージョン番号で整合性を検証する。さらに、未検証の値を専用型でラップし、コンパイラに検証を強制させることで、競合状態を防ぎつつ高い性能を実現する。
コンパイラは、実行時に微妙な競合状態になるようなミスを検出してくれる。
- dichloromethane
でも、このコードは壊れているように見える。この種のロックフリー並列アルゴリズムの大きな課題は、常にライフタイムをどう扱い、use-after-freeを防ぐかだ(このツリーから何も解放したくないのでなければ、だが、それはあまり現実的ではない)。
根本的な問題は、ライターが free() したノードをリーダーが参照するのを防ぐものがないことだ。これを修正するには、RCU か Hazard pointers を追加する必要がある。
- PeterWhittaker
素人質問で恐縮だが、これは私の専門分野ではないので、Rust には RwLock がある。なぜ単純に RwLock を使って多数のリーダーと単一のライターを許可しないのか?
このアプローチはどのように RwLock を上回るのか(「上回る」の任意の解釈において)、そして RwLock はどのようにこのアプローチを上回るのか(同様に)?
- windenntw
よく書かれていて、内容も良く、ランダムなジャンクを売り込もうとしない、+10 また読みたい :)