12/09/2009

Reader/Writer Locking and Beyond

The Reader/Writer problem[2.0] is a synchronization problem that deals with how to improve multi-threading program's overall performance. The core idea is improving concurrency - make as many as possible threads to run.

Reader/Writer lock is a mechanism to resolve this problem - shared access for readers, exclusive access for writers.

Part I - Considering Factors

The basic idea behind Reader/Writer lock is simple and implementation algorithms are published here and there[2.1][2.2][2.3], but there are various aspects to consider:

1. Spin Lock or Blocking Lock

Reader/Writer lock uses some basic synchronization primitive - lock/semaphore, there are two types of locks:[2.2]
- Busy-Wait lock is a proactive locking mechanism, the thread is waiting while holding the CPU (spin lock & barrier are the most popular constructs of this type)
- Blocking lock is yield waiting and scheduler-based blocking mechanism, the thread yield the CPU when waiting

2. Re-Entrance/Recursion

Whether a thread that already holds some lock can acquire other kind of lock? If so, the implementation is said to support recursion.

Roughly speaking, a typical reader/writer lock that supports recursion behaves like:
- thread holds read lock can't request write lock,
- thread holds read lock can be granted read lock without blocking
- thread holds write lock can be granted read lock without blocking
- thread holds write lock can be granted write lock without blocking

3. Time-Out

A lock requesting thread may want to set time limitation on how long to wait. Usually, time-outed APIs are named as TryXXX ...

4. Fairness/Preference

When multiple threads are waiting for some locks, which thread to wake up and grant corresponding access is very critical for fairness problem.

A reader-preferred policy will grant a reader to access if the resource is accessed by a reader

A writer-preferred policy will grant the longest waiting writer to access if there is any, requesting reader will be blocked if there is any writer waiting in the queue.

A fair policy usually ensure that:
1. reader arrives when some readers are being granted reader lock should be blocked if some writer is already waiting, i.e, it avoids writer starvation
2. if reader arrives before a writer, it should be granted access before the writer is granted to access, i.e, it avoids reader starvation

But what threads to grant when reader locks are allowed is another consideration factor:
- Consecutive, if there is a group of reader threads waiting longer than all waiting writer threads, that group will be assigned the read lock.
- All in One, when readers are allowed to access, all waiting reader will be enabled.

5. Upgradable Read(Update) Lock

As we had said, recursive r/w lock doesn't allow a reader(shared) lock holder to request writer(exclusive) lock (a.k.a. lock upgrade), but sometimes, this is a strong desired feature.

For instance, in database implementation, a UPDATE statement may first acquire reader lock on all table pages, when it finds some row need to be modified, a writer locks is requested on related page.

Simple implementation on lock upgrade may causes deadlocks (P556, Chapter 17, Database Management System 3E), so the idea of lock downgrade comes out - acquire writer(exclusive) locks at first, downgrade to reader(shared) lock when it is clear. Also this idea avoids many deadlocks, it limits the concurrency - it suggests acquire exclusive lock at first.

So people invented upgradable lock(a.k.a. update lock), it's compatible with reader(shared) lock, but not with update(upgradable) lock, nor writer(exclusive) lock. If one thread is granted update lock, it can read the resource and also has the right to upgrade its lock to write lock(may cause blocking). An update lock holder can also downgrade its lock to read lock. More explanation on upgradable lock can be found at [3.1.1]

Essentially, upgradeable lock is intended for cases where a thread usually reads from the protected resource, but might need to write to it if some condition is met. Exactly the same semantic of UPDATE statement is DBMS(that's why it is also named as Update Lock). Sql Server and DB2 supports Update Lock, while Oracle doesn't.[5.1][5.2][5.3][5.4]

Part II - A C++ Implementation

In implementing Reader/Writer Lock, we made the following decisions:
1. Spin Lock is useful when lock holding time is relatively short, we adopt block-waiting lock since how these locks are used is not cleared
2. It supports recursion
3. It supports time-out feature
4. For better flexibility, we implemented three RWLocks: reader preferred ReaderWriterLock, writer preferred WriterReaderLock, the fair FairSharedLock.
5. Currently, we don't support Update lock

Basic Algorithms for ReaderWriterLock and WriterReaderLock are that given in paper[2.1], recursion is supported by introducing current writer field and time-out is supported by using win32 wait functions.

Reader Preferred ReaderWriterLock Algorithm, from[2.1]

Writer Preferred WriterReaderLock Algorithm, from[2.1]

The fair shared lock is implemented using a lockword, which stores lock state and manipulated by Interlocked primitives, and a waiting thread queue, which queues waiting reader/writer threads to keep information for fairness judging. Some ideas are learned from Solaris[3.8.1] and Jeffery's OneManyResourceLock[3.1.2].

source code can be found at (Locking.h & Locking.cxx)

Part III - Some Multithreading Better Practices

1. Don't allow thread to transit from user mode to kernel mode
2. Use as few threads as possible (Ideally, equals to cpu/core count)
3. Use multiple threads for tasks that require different resources
4. Don't assign multiple threads to a single resource
[Reference]

Synchronization General Concepts

1.1 Synchronization
1.2 Lock
1.3 Mutex(Mutual Exclusion)
1.4 Semaphore
1.5 Monitor
1.6 Event
1.7 Barrier
1.8 Lock Convoy

General Reader/Writer Lock
2.0 The First, Second and Third Reader/Writer Problems

2.1 Paper: Concurrent Control with "Readers" and "Writers"
- It firstly introduced the reader/writer problem and gave 2 algorithms (R preferred/W preferred)
2.2 Paper: Algorithms for scalable synchronization on shared-memory multiprocessors
- It summarized busy-wait sync mechanism and introduced algorithm for Spin Lock based only on local memory spinning
2.3 Paper: Scalable RW Synchronization for SMP (Its Pseudocode & PPT)
- It introduced:
-- a. R-Preferred/W-Preferred/Fair RWLock using general Spin Lock on SMP machine
-- b. Improve a. by using algorithm that needs local spinning only Spin Lock
2.4 Paper: A Fair Fast Scalable Reader-Writer Lock
- Some Improvement on 2.2
2.5 Paper: Scalable Reader-Writer Locks
- Latest and some Summary on previous Works

2.6 Notes on Implementing a Reader/Writer Mutex
2.7. Scalable Read/Write Lock on SMP
2.8 Test Reader/Writer Lock Performance

Reader/Writer Lock Implementations on Various Platforms

- 1. .Net
3.1.1 Reader/Writer Lock in .Net (the Slim Version)
3.1.2 Jeffrey Richter on Reader/Writer Lock implementation
3.1.3 Joe Duffy on Reader/Writer Lock
3.1.4 Implementing Spin-Lock based Reader/Writer Lock and Its Analyzing

- 2. Java
3.2.1 Various Aspects on Java Reader/Writer Lock
3.2.2 Implementing Java Reader/Writer Lock
3.2.3 Java Doc on Java SE Reader/Writer Lock
3.2.4 Java Threading Book on Synchronization

- 3. Boost
3.3.1 DDJ on Boost Thread Library
3.3.2 Boost Thread Library Official Doc
3.3.3 Multithreading for C++0x

- 4. Apache Portable Runtime
3.4.1 APR RWLock Doc

- 5. PThread
3.5.1 PThread RWLock by IBM
3.5.2 PThread RWLock by Sco
3.5.3 PThread Doc

- 6. Intel TBB
3.6.1 Intel TBB Reader/Writer Lock

- 7. Win32
3.7.1 Synchronization Primitives New To Windows Vista
3.7.2 Slim Reader/Writer Lock
3.7.3 Win32 Native Concurrency (Part 1, Part 2, Part 3)

-8 Solaris
3.8.1 Reader/Writer Lock source code in Open Solaris

-9 Linux
3.9.1 simple doc on Linux kernel locking
3.9.2 Linux reader/writer lock implementation: header & source

- 10. Misc
3.10.1 Reader/Writer Lock Cxx Source Code (Header, Source)
3.10.2 An FIFO RWLock Source Code

Spin Lock

4.1 http://en.wikipedia.org/wiki/Spinlock
4.2 Spin Lock Implementation and Performance Comparison
4.3 Spin Wait Lock implementation by Jeffry Richter
4.4 User Level Spin Lock
4.5 Introduction on Spin Lock
4.6 Paper on FIFO Queued Spin Lock
4.7 InterlockedExchange atomic fetch_and_store on Windows
4.8 InterlockedCompareExchange atomic compare_and_swap on Windows
4.9 Ticket (Spin) Lock (wikipeida, in Linux Kernel, in Paper)
4.10 FIFO Ticket Spinlock in Linux Kernel
4.11 MCS Spin Lock Design & Implementation

Locking in Database

5.1 Understanding Locking in Sql Server
5.2 Oracle Locking Survival Guide5.3 DB2 Locking Mechanism
5.4 Sql Server Locking Types

Misc

6.1 MSDN Magazine Concurrent Affairs Column
6.2 Many Insights on Thread Synchronization and Scalable Application
6.3 ReaderWriterGate Lock by Jeffrey (R/W lock + Thread Pooling)
6.4 A Richer Mutex & Lock Convoy by Jeffery

1 comment:

Pilland said...

I arrived here just surfing.
Congratulations on Your nice site and best wishes from an Estonian living in Italy