On 4/4/2011 1:56 AM, Kern Sibbald wrote: > On Thursday 31 March 2011 16:24:46 Josh Fisher wrote: >> On 3/30/2011 5:05 PM, Kern Sibbald wrote: >>> Hello, >>> >>> Thank you for your feature request. Unfortunately, I have no idea how to >>> implement it, so unless you can provide some new insight, it will not >>> help adding it to the projects file. >> This can be done with a "software transactional memory" (STM) approach, >> and has been described for red-black tree traversal. If interested, see >> the Herlihy and Koskenin paper at >> ftp://ftp.cs.brown.edu/pub/techreports/07/cs07-08.pdf > This is an interesting paper, and the technique seems promising, but given > that it references Java and more in particular a library that I am not > familiar with, it is not easy for my simple brain to figure out how it could > be useful in Bacula.
There is an open source implementation of a STM library in C called libCMT on SourceForge. You are right in all regards. It would be a paradigm change in Bacula, and it is promising for future reference, but not yet ready for a feature request. STM is basically used in place of lock-based synchronization for reader-writer applications. Instead of using locks, every read and write is logged in a similar manner as a file system journal. Everything occurs as transactions, for example adding a tree node, updating a tree node, reading a tree node, etc. Transactions begin by going ahead and reading or writing as if no other threads were running. Afterward, a check is performed to see if any other thread might have changed any of the nodes this transaction used/changed. If not, then the transaction is committed. If so, then the transaction is rolled back using the log (ie journal) and starts over. The disadvantage is the overhead of the journal and sync check. Below about 6 available processor cores, it is a net loss of performance due to overhead. The advantage is a finer grained synchronization that allows multiple simultaneous changes and/or searches without having to lock the entire tree for each write. As the core count increases, the increased concurrency outweighs the overhead, and the parallel red-black tree algorithm approaches O(N), (linear time), rather than the lock-based version's O(logN). Cheers, Josh ------------------------------------------------------------------------------ Create and publish websites with WebMatrix Use the most popular FREE web apps or write code yourself; WebMatrix provides all the features you need to develop and publish your website. http://p.sf.net/sfu/ms-webmatrix-sf _______________________________________________ Bacula-devel mailing list Bacula-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bacula-devel
