Browse Prior Art Database

Use of transactional memory for linked lists without locks

IP.com Disclosure Number: IPCOM000245536D
Publication Date: 2016-Mar-15
Document File: 5 page(s) / 69K

Publishing Venue

The IP.com Prior Art Database

Abstract

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.

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

Page 01 of 5

1 Abstract

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.

2 Background

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...

Issues:


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.


2.1.2 Read-copy-update

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...