Use of transactional memory for linked lists without locks
Publication Date: 2016-Mar-15
The IP.com Prior Art Database
Disclosed is a computer implemented method that makes use of transactional execution / transactional memory to provide algorithms to use and manipulate linked lists without locking. The method provides a set of simple means to manipulate linked lists in such a way, that no lock recovery or handling of failing locks and no fallback code is required. The method provides for multiple updaters and multiple readers of the linked list in parallel.
Page 01 of 5
Disclosed is a computer implemented method that makes use of transactional execution / transactional memory to provide algorithms to use and manipulate linked lists without locking.
The method provides a set of simple means to manipulate linked lists in such a way, that no lock recovery or handling of failing locks and no fallback code is required. The method provides for multiple updaters and multiple readers of the linked list in parallel.
Linked Lists are often used to organize data in an efficient way. In a multi processor system it may happen that multiple processors use linked lists in parallel. Parallel read-accesses are allowed and desirable. Write accesses to a linked list however are problematic, if another processor is reading the list in parallel. This may result in inconsistent data or even a broken chain.
2.1 Existing solutions
2.1.1 Traditional Locking
Traditionally some kind of locking mechanism is used, if multiple processors need to access a linked list: Mutex, ReaderWriterLocks, InUse counters, etc...
• Deadlock potential
◦ The granularity and scope of locks needs to be carefully designed, so no deadlocks can occur.
• Lock recovery
◦ What happens I a processor becomes unavailable or is restarted (i.e. because of a program check) while it is holding a lock? One solution is to define recovery strategies that clean up locks after such incidents.
• Hanging lock: What can be done by the code who detects a hanging lock? Possible strategies are:
◦ Recover the owner of the lock
◦ break the lock
◦ find out if the owner really is still using the list.
While such a fine-tuned locking design can be efficient and tailored to the needs, it requires a lot of expertise and usually results in complex and error-prone code.
See e.g Wikipedia. A synchronization mechanism that handles linked lists without locks. Only one updater, but multiple readers.
Page 02 of 5
Removing an element by:
prevElement->next = prevElement->next->next
Works for one updater; as long as element is not deleted, ongoing read-accesses are not a problem (see Figure2.1). However, a mechanism is required to detect when the last reader has finished and the element can actually be deleted.
Figure2.1: RCU Remove one element
Problem with multiple updaters of a linked list:
Figure 2.2: RCU Remove 2 elements simultaneously
While this mechanism is very elegant and useful, it has the restriction that there must be only one updater of the linked list. See Figure 2.2 for an example of a broken chain, when two elements are removed simultaneously.
2.1.3 Atomic operations like 'Compare and Swap'
Can be used to atomically update up to a quadword of data. Is often used as part of locking strategies, e.g. to atomically update a lock or to atomically move a pointer.
2.1.4 Transactional memory
Transactional memory is a methodology that attempts to simplify concurrent programming by allowing a group of load an...