Brief introduction of software transactional memory using the class Node

Tree-structure objects, consisting of Node and derived classes, work as software transactional memory (STM) by accessing through Transaction or Snapshot class.
STM is a recent trend in a many-processor era for realizing scalable concurrent computing. As opposed to pessimistic mutual exclusions (mutex, semaphore, spin lock, and so on), STM takes an optimistic approach for writing, and each thread does not wait for other threads. Instead, commitment of transactional writing could sometimes fail and the operation will be restarted. The benefits of this optimistic approach are scalability, composability, and freeness of deadlocks.
The class Transaction supports transactional accesses of data, which were implemented as Node::Payload or T::Payload in derived classes T, and also handles multiple insertion (hard-link)/removal (unlink) of objects to the tree. Transaction / Snapshot for subtree can be operated at any node at any time by lock-free means. Of course, transactions for separate subtrees do not disturb each other. Since this STM is implemented based on the object model (i.e. not of address/log-based model), accesses can be performed without huge additional costs. Snapshot always holds consistency of the contents of Node::Payload including those for the subnodes, and can be taken typically in O(1) time. During a transaction, unavoidable cost is to copy-on-write Payload of the nodes referenced by Transaction::operator[].
The smart pointer atomic_shared_ptr, which adds a support for lock-free atomic update on shared_ptr, is a key material in this STM to realize snapshot reading and commitment of a transaction.

Example 1 for snapshot reading: reading two variables in a snapshot.

{ Snapshot<NodeA> shot1(node1);
double x = shot1[node1].m_x;
double y = shot1[node1].m_y;
}


Example 2 for simple transactional writing: adding one atomically

node1.iterate_commit([](Transaction<NodeA> &tr1(node1)) {
tr1[node1].m_x = tr1[node1].m_x + 1;
});


Example 3 for adding a child node.

node1.iterate_commit_if([](Transaction<NodeA> &tr1(node1)) {
return tr1.insert(node2));
});


More real examples are shown in the test codes: transaction_test.cpp, transaction_dynamic_node_test.cpp, transaction_negotiation_test.cpp.

See Also
Node, Snapshot, Transaction.
atomic_shared_ptr.

Generated for KAME4 by  doxygen 1.8.3