Method and Data Structure for Concurrent Bi-Directional Traversal and Manipulation of a Doubly Linked List
Original Publication Date: 2004-Feb-05
Included in the Prior Art Database: 2004-Feb-05
A method is presented to allow iterators to concurrently traverse a doubly linked list in either direction without deadlocking. Each item in the list is protected by its own lock. Two types of iterators are described. Stable iterators hold locks and cannot have data at their current position altered by other iterators, but they can only move forward. Non-stable iterators release locks after each operation and can have data at their current position altered by other iterators, but they allow bi-directional traversal. When the list is modified at or near the current position of a non-stable iterator, the iterator must be adjusted to maintain its correct position and state. Stable iterators can be converted to non-stable iterators and vice versa.
Method and Data Structure for Concurrent Bi -Directional Traversal and Manipulation of a Doubly Linked List
Disclosed is a method and associated data structure to allow concurrent programs to traverse a doubly linked list bi-directionally without deadlocking. Iterators are used to traverse the list. An iterator maintains state that includes its current position and the last operation performed. As an iterator inserts or deletes items in the list, it updates the state of other iterators to maintain their correct position and operational semantics. Iterators can be stable or non-stable, depending on how they hold locks on list items. Details of how items are locked by the iterators to prevent deadlock and how the state of iterators is updated by other iterators are provided .
When a list is used in a multithreaded (concurrent) program it can be accessed in conflicting ways. For example, the item one iterator is positioned at might be deleted by another iterator. A common technique protects the list with a global lock but allows only one iterator to exist at a time. In the method disclosed here, each item in the list is protected by its own lock, and multiple iterators can be active simultaneously.
Operations on iterators include next and previous to position the iterator and insert and delete to modify the list. An iterator's state points to the item returned by next or to the item preceding the item returned by previous. Alternating calls to next and previous return the same item. This is the iterator's current position. The semantics of the iterators discussed here do not allow modification operations if the last operation performed was not a positioning operation. For this reason the state of the iterator also includes the last operation the iterator performed .
In order to insert and delete items an iterator locks the previous item as well as the current item so it can adjust the forward and backward pointing links of the doubly linked list when items are inserted or deleted. There are two types of iterators, stable and non-stable.
In some applications a stable iterator is required. A stable iterator holds the previous and current item locks between operations. This prevents other iterators from changing the list where the stable iterator is positioned. This type of iterator is called stable because the value of the current item cannot be changed by other iterators.
If a stable iterator (I1) were to move forward and encounter another stable iterator (I2), I1 would have to wait until I2 moved ahead, releasing locks on the items it has passed. If I2 is paused while its thread performs other lengthy computations, then I1 is blocked from advancing.
If a stable iterator I1 were to move forward while a stable iterator I2 moved backwards, when they met they would contend for the lock on the intervening item and become deadlocked. Note that a stable iterator cannot safely release its previous locks until it has acquired the locks for it...