Browse Prior Art Database

A Concurrent Multiway Tree using a Lazy Locking mechanism

IP.com Disclosure Number: IPCOM000250409D
Publication Date: 2017-Jul-11

Publishing Venue

The IP.com Prior Art Database

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 14% of the total text.

A Concurrent Multiway Tree Using a Lazy Locking Mechanism Concurrency and synchronization are fundamental issues critical for the design of applications that allow concurrent threads to access shared resources. Concurrent access to a data structure shared among several threads must be synchronized in order to avoid interference between conflicting operations. Such concurrent data structures are widely used in the concurrent applications that fully exploit today’s multiprocessor and multicore systems. Concurrent data structures are far more difficult to design than sequential, because concurrently executing threads may interleave steps in many ways, each with a different and potentially unexpected outcome [1]. Linked-lists are the fundamental building blocks for concurrent data structures and the basis for many types of search and dictionary data types [2]. A linked list is a linear collection of data elements. It is among the simplest and most common data structures. Linked lists can be used to implement several other abstract data structures, such as stacks and queues. Apart from globally locking the linked-list to prevent concurrent manipulation, the most popular approach to concurrent lock-based linked lists is hand- over-hand locking (also called lock coupling) [3]. This is the earliest lock-based concurrent linked-list approach invented by Bayer and Schkolnick. In this approach, each node has an associated lock. A thread traversing the linked list releases a node’s lock only after acquiring the lock of the next node in the list, thus preventing overtaking which may cause unnoticed removal of a node. This approach gains better concurrency than a global lock by reducing lock granularity, but successive locks make it undesirable and block other threads from proceeding during traversal of the list. Valois [4] suggested the first effective non-blocking implementation of concurrent linked lists based on the Compare-And-Swap synchronization primitive. It uses a special auxiliary node in between each regular node to prevent undesirable phenomenon while insertion and deletion are interleaving. Harris [5] proposed another efficient lock-free approach which uses a special “deleted” bit that is accessed automatically with node pointers in order to signify that the node has been logically deleted. M. Michael [6] later presented another lock-free list based on Harris’ linked-list algorithms and the algorithm is used in Java Concurrency Package of JDK 1.6.0. Herlihy and Shavit proposed a locked-based approach, optimistic-list [7], which reduced the locking overhead by allowing searching the list without acquiring locks until the target node is found. Verification of the nodes is needed before executing insertion or deletion operations. Heller et al [2] proposed the lazy-list approach, which further improved the optimistic-list approach by assimilating the idea from Harris’ approach [5]. Instead of stealing a bit from the reference, the lazy- list appro...