Browse Prior Art Database

Wait-free read access to mutable dynamic blocks

IP.com Disclosure Number: IPCOM000127253D
Original Publication Date: 2005-Aug-18
Included in the Prior Art Database: 2005-Aug-18
Document File: 3 page(s) / 60K

Publishing Venue

IBM

Abstract

Conventionally, read-only access to mutable shared variables use mutual exclusion locks or reader-writer locks. Either type of lock requires writing to the lock variable that are actively shared by threads operating on the data, thus causing adverse cache performance among concurrent read-only accesses to the data. The hazard pointer method allows lock-free read access to mutable variables without writing to contended variables. Lock-free progress guarantees deadlock-freedom and livelock-freedon regardless of thread scheduling or thread failures. Wait-free progress guarantees lock-free progress as well as starvation-freedom. That is a wait-free operation is guaranteed to complete in a finite number of steps regardless of adverse thread scheduling and arbitrary thread termination. This article presents a wait-free mechanism for enabling read access to mutable shared variables without writing to contended shared variables by building on the hazard pointer method.

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

Page 1 of 3

Wait-free read access to mutable dynamic blocks

Introduction

Lock-free read-only access to mutable shared variables has significant performance advantages by avoiding writes by read-only operations to contended shared variables. Lock-free access guarantees deadlock-freedom and livelock-freedom. Wait-free access in addition guarantees starvation-freedom. The hazard pointer method [1] can be used to guarantee lock-free read-only access to shared dynamic blocks, however it does not guarantee wait-free access. A mechanism is needed to guarantee wait-free access. The reason is that a straigtforward application of hazard pointers tries to capture a specific dynamic block (i.e. prevent it from being reused prematurely). Consider the following example:

A dynamic block of type block_t contains a data item Data of type data_t.

A shared valiable X of type *block_t points to a dynamic block.

A read-only operation wants to read X->Data but since it is possible that between reading the pointer X and then dereferencing and reading the field Data, the block has been replaced from X and reused for a different purpose. Therefore, reader use a hazard pointer to try to prevent the premature reuse of the block as follows, where hp points to one of the executing thread's hazard pointers:

Read(X) : data_t ---------------------
do { local := X
HP_i := local } until (X == local) data := local->Data
HP_i := null return data

The hazard pointer method requires the writer who replace the dynamic block in X to check first the hazard pointers of readers before reusing the replaced block. So, a writer routine would proceed as follows (assuming a single writer for simplicity):

Write(X,data) ----------------
old := X b := NewBlock() b->Data := data
X := b pass the block at old to the hazard pointer method

It can be seen that the Read routine is only lock-free but not wait-free as it is repeatedly trying to capture a specific block (the block at local) and by the time it sets its hazard pointer, it may be too late after the writer has already replaced that block and the block has already gone through the hazard pointer method and was determined to be safe for reuse.

The method

The key observation is that if instead of trying to capture a specific block, the reader will definitely capture some block that was pointed to by X during the lifetime of the Read operation and the block still holds a valid value, then the read will be wait-free. The key is to develop a structure for the reader to announce to the writer(s) that it wants to capture some block with a valid value that is or was associated with X.

1

Page 2 of 3

The main data structures...