Portable Thread Synchronization Using C++
Jim Frost
Software Tool & Die
Copyright (c) 1995 Jim Frost
All Rights Reserved
Last changed February 17, 1995
Abstract
This document provides example C++ classes implementing a series of
synchronization objects useful for building portable multithreaded
applications.
This is a work in progress. Do not rely on the absolute
accuracy of the implementations.
Table Of Contents
Thread-aware operating systems are here, and are rapidly growing in
popularity. Today there are at least three popular multithreaded
operating systems -- Windows NT, OS/2, and Solaris 2.x -- and a POSIX
standard, Pthreads, is on the way.
While each of the operating systems provides very similar basic
synchronization objects, they do so with considerably variant syntax
and usage. As a result it is not trivial to write multithreaded
applications which port between the operating systems easily.
This document provides a series of C++ classes which implement both
basic and more complex synchronization objects, as well as several
useful data structures that use them. Implementations are provided
for both Win32 (Windows NT and Windows 95) and Solaris 2.x
environments.
The simplest synchronization object is the mutex, which is
used to allow only one thread at a time access to a resource (usually
a data structure).
The Mutex class implements a recursively
lockable mutex, one where a single thread may lock the same mutex
multiple times. In practice this is the safest and most useful form
of a mutex.
The interface to the Mutex class is:
class Mutex {
public:
Mutex(void);
void Lock(void);
void Unlock(void);
};
See:
Using the mutex class it is easy to create C++ classes which are
totally thread-safe. For example:
class SafeInteger : private Mutex {
private:
int value;
public:
void SetValue(int new_value) {
Lock();
value = new_value;
Unlock();
}
int GetValue(void) {
Lock();
int ret_value = value;
Unlock();
return ret_value;
}
};
Because the only access to the data member is through the member
functions of its class, it is impossible to accidentally
access the data unsafely.
The semaphore synchronization object is used so that one
thread may allow one or more other threads to pass a particular point
at a particular time.
The interface to the Semaphore class is:
class Semaphore {
public:
Semaphore(void);
Semaphore(int available);
~Semaphore(void);
void Wait(void);
void Post(void);
void Post(int how_many);
};
See:
Semaphores are most useful when threads are in a producer/consumer
relationship, as in the case of a queue. The following implements a
queue template class using the Semaphore class:
template class QueueEntry : public T {
public:
T value;
QueueEntry* next;
QueueEntry(const T& item_value) {
value = item_value;
next = (QueueEntry*)0;
}
};
template class Queue : private Semaphore : private Mutex {
private:
QueueEntry* head;
QueueEntry* tail;
public:
Queue(void) {
head = tail = (QueueEntry*)0;
}
void Add(const T& item_value) {
Lock();
if (tail == QueueEntry*)0)
head = tail = new QueueEntry(item_value);
else {
tail->next = new QueueEntry(item_value);
tail = tail->next;
}
Unlock();
Post(); // wake up any waiting threads
}
T Wait(void) {
Semaphore::Wait(); // wait for something to show up
Lock();
T value = head->value;
QueueEntry* old = head;
head = head->next;
delete old;
if (head == (QueueEntry*)0)
tail = (QueueEntry*)0;
Unlock();
return value;
}
};
Any number of threads may wait on a queue, and as data is added to
the queue they will be woken up one-at-a-time. If no threads are
waiting when data is added to the queue, any thread coming along at a
later time will simply pick up with waiting data immediately.
An event synchronization object is used to block one or
more threads from proceeding until some specified time, at which time
they are all released simultaneously.
The interface to the Event class is:
class Event {
public:
Event(void);
~Event(void);
void Signal(void);
void Wait(void);
};
See:
A gate is a synchronization object used to either stop all
threads from proceeding through a point or to allow them all to
proceed.
The interface to the Gate class is:
class Gate {
public:
Gate(void);
~Gate(void);
void Open(void);
void Close(void);
void Release(void);
void Wait(void);
};
See:
In many multithreaded applications a data structure may be accessed
by many threads, but modified only occasionally. Since it is safe for
many threads to access a structure simultaneously so long as they
don't change it, a readers/writer lock, which allows only one
thread to modify a structure but any number of threads to inspect it
when no modifications are taking place.
Many operating systems supply readers/writer locks as primitives,
but some do not. The following is a generic implementation of a
readers/writer lock, with writer-priority, implemented completely on
top of the classes described in this document.
class RWLock : private Mutex {
private:
Semaphore write_lock; // used as a one-at-a-time release valve
Gate read_barrier; // used to block/wakeup readers
unsigned int writer_count; // # of writers waiting for or holding the lock
unsigned int reader_count; // # of readers holding the lock
public:
ReadLock(void) {
writer_count = 0;
reader_count = 0;
}
void ReadLock(void) {
Mutex::Lock();
// wait until there are no more writers holding the lock
while (writer_count > 0) {
Mutex::Unlock();
read_barrier.Wait();
Mutex::Lock();
}
reader_count++;
Mutex::Unlock();
}
void WriteLock(void) {
Mutex::Lock();
writer_count++; // this stops new readers from getting a lock
write_lock.Wait(); // wait until the write lock is available
read_barrier.Close(); // give new readers something to wait for
Mutex::Unlock();
}
void Unlock(void) {
Mutex::Lock();
if (writer_count > 0) { // we must be a writer
writer_count--;
if (writer_count > 0) // another writer is waiting
writer_lock.Post(); // let it go
else
read_barrier.Open(); // open the floodgates
}
else {
reader_count--;
// if we're the last reader and a writer is waiting, let it go
if ((reader_count == 0) && (writer_count > 0)) {
writer_lock.Post();
}
Mutex::Unlock();
}
};
Note: The lack of an atomic
release-semaphore-and-wait-for-event primitive on some systems
requires the use of a Gate rather than an
Event so that the event is not lost between the release
of the structure lock by the reader(s) and the wait on the event.
Note: Solaris 2.x supplies readers/writer locks as
a primitive, making the implementation
much simpler.
In some cases a single data structure will be accessed very often
for both reading and writing. To avoid starvation of either the
readers or the writers, a fair-share lock can be used. A generic
implementation of the FairRWLock follows.
class FairRWLock : private Mutex {
private:
Semaphore access_lock; // used as a one-at-a-time release valve
Gate read_barrier; // used to block/wakeup readers
unsigned int is_write_lock; // nonzero if locked for writing
unsigned int writer_count; // # of writers waiting for or holding the lock
unsigned int reader_count; // # of readers holding the lock
unsigned int readers_waiting; // # of readers waiting for the lock
public:
ReadLock(void) : access_lock(1) {
is_write_lock = 0;
writers_waiting = 0;
reader_count = 0;
readers_waiting = 0;
}
void ReadLock(void) {
Mutex::Lock();
// if there is at least one writer using the lock or waiting for it,
// we need to wait for access
if (writer_count > 0)) {
if (readers_waiting++ == 0) // if we're the first reader in line
Mutex::Unlock();
access_lock.Wait(); // get the access lock
Mutex::Lock();
if (readers_waiting > 1) // then if there are other readers
read_barrier.Open(); // let them go
}
else {
Mutex::Unlock();
read_barrier.Wait(); // otherwise wait until someone lets us go
Mutex::Lock();
}
readers_waiting--;
}
reader_count++;
Mutex::Unlock();
}
void WriteLock(void) {
Mutex::Lock();
writer_count++; // one more writer
Mutex::Unlock();
access_lock.Wait(); // wait until the access lock is available
Mutex::Lock();
is_write_lock = 1; // lock is a write lock
read_barrier.Close(); // give readers something to wait for
Mutex::Unlock();
}
void Unlock(void) {
Mutex::Lock();
if (is_write_lock) { // if this is a write lock
is_write_lock = 0; // let it go
writer_count--; // one less writer
access_lock.Post(); // now let someone else have a chance
}
else if (--reader_count == 0) // if we're the last reader
access_lock.Post(); // release the access lock
Mutex::Unlock();
}
};
Note: The fairness of this implementation depends on
the fairness of the semaphore implementation.