"Revocable locks for non-blocking programming"
Tim Harris
Microsoft Research Cambridge

Monday 9/12/2005, 11am
Gates Hall Room 104

Abstract:

In recent work we've been exploring the use of software transactional
memory (STM) as a mechanism for building general-purpose abstractions
for concurrent programming.  As part of this work we've developed a
new form of lock which makes it easier to build shared-memory data
structures that are safe for use by multiple threads on multiprocessor
machines while giving non-blocking progress guarantees.

Like ordinary mutexes, these revocable locks can only be held by a
single thread at a time.  This means that, while a thread holds a
lock, it can be certain that other threads won't be performing
operations that are protected by the same lock.  This makes it much
easier to build operations such as multi-word heap updates or
transactional memories.

However, unlike ordinary mutexes, if a thread A attempts to acquire a
lock held by thread B then the lock is passed to A and, atomically
with this, B's execution is displaced to a recovery function that it
specified when it acquired the lock.  Typically the recovery code
would either propagate revocation as a higher level failure, or it
would retry the operation after some form of contention management to
avoid livelocking with A.

If these revocable locks are implemented carefully then they can still
be used as a building block for algorithms that are technically
lock-free. I'll show how revocable locks can be used to build
queue-based data structures like lists and dequeues, and also how they
can be used to streamline the implementation of a word-based
transactional memory.  The results are perhaps surprising: most uses
of compare-and-swap can be replaced by direct memory updates and
per-operation dynamic memory allocation can often be avoided.


Bio
 Tim Harris is a Researcher at Microsoft Research Cambridge where
he works on concurrent algorithms and new abstractions for concurrent
programming. Previously he was a lecturer in the University of
Cambridge Computer Laboratory where he gained his BA and PhD
degrees. He is a co-author of the undergraduate textbook "Operating
Systems" published by Pearson and is a Teaching Fellow at Churchill
College, Cambridge, UK.