A simple and therefore highly usable non-blocking implementations of linked-lists can be provided using read, write, and CAS operations. Several realizations of linked-list based data-structures are described, which are non-blocking, linearizable, and exhibit disjoint-access for most operations. In other words, the realizations are non-blocking and linearizable while maintaining the property that operations on disjoint parts of the list do not interact, effectively lowering contention and increasing concurrency. We implement three exemplary data structures: sets, multi-sets, and ordered-sets. The exemplary implementations support insert, remove, and find operations, with natural semantics. An ordered-set implementation supports an additional removeGE operation.

 
Web www.patentalert.com

< Optional attribute generator for customized Java programming environments

< Application-level access to kernel input/output state

> System and method employing script-based device drivers

> Contested account registration

~ 00291