next up previous contents
Next: Hardware Support Up: Related Work Previous: Lock-Free Operating Systems

Methodologies for Implementing Concurrent Data Objects

Herlihy [14] presents a methodology for converting sequential implementations of data structures into wait-free concurrent implementations. The goal is to provide a specification and transformation that is provably correct and can be applied automatically to sequential code. It converts a sequential implementation of any data structure into a wait-free, concurrent one, just using CAS (or, slightly more efficiently [14] using load-linked and store-conditional). However, this method involves copying the entire data structure, modifying the copy, and then atomically replacing the old copy with the new copy using CAS, and retrying the entire copy and modifying if there is a conflict. Performance can be improved using other, more ad-hoc, techniques [14], but these techniques tend to add hard-to-catch subtle synchronization problems and are still expensive. Overall, we regard this approach as impractically expensive because of the copy overhead.

In contrast, our contribution is a set of general techniques that the programmer incorporates in the software design and implementation, allowing the software to be used in both sequential and parallel execution with no modification and with acceptable performance.

Barnes [3], Turek [23], and Valois [24] provide techniques for increasing the concurrency with some non-blocking synchronization. However, the cost of concurrent updates appears to outweigh the actual benefit, because the low rates of contention in our system. Studies such as [22], which also reported a low level of contention on kernel data structures, suggest that this phenomenon might be more widely true than just in the Cache Kernel.



next up previous contents
Next: Hardware Support Up: Related Work Previous: Lock-Free Operating Systems



Michael Greenwald
Thu Sep 19 12:18:20 PDT 1996