Singleton

Singleton is one of the well known design patterns. It is used to ensure that there is only one instance of the class and provide a global access point to it.

Single-threaded version

A single-threaded version of singleton is provided by <<Design Patterns>>,  here is a similar but generic version :

template 
class Singleton
{
private:
        Singleton() { }
        ~Singleton() { }

public:
        static T &getInstance()
        {
                static T *_instance = 0;
                if(!_instance) {
                        _instance = new T;
                }
                return *_instance;
        }
}

Multi-threaded version


The variable "_instance" is shared among the threads. "_instance" should be written once only during lazy initialization when the first time the "getInstance()" method called. However, there can be situation that multiple threads call the "getInstance()" method simultaneously,  so "_instance" should be protected when writing data to it, otherwise, data race will happen.

The easiest and least efficient way is

static T &getInstance()
{
        static T *_instance = 0;
        // get LOCK
        if(!_instance) {
                _instance = new T;
        }
        // release LOCK
        return *_instance;
}

It is inefficient because:

1. lock and unlock have overhead
2. locking is need only during initialization, once initialized we dont need lock anymore.

Here comes Double Checked Locking Pattern:

static T &getInstance()
{
        static T *_instance = 0;
        if(!_instance) {
                // get LOCK
                if(!_instance) {
                         _instance = new T;
                }
                // release LOCK

        }
        return *_instance;
}

"_instance" is checked twice. The second time is used to ensure that the variable is not written by other threads when waiting for the lock. However, this pattern has a serious problem, the reading and writing to "_instance" is NOT synchronized, that means the reading outside the lock may get an uncompleted value.

How to make the write atomic? Compare And Swap(CAS) !!

static T &getInstance()
{
        static T *_instance = 0;
        if(!_instance) {
                T *n = new T;
                if(__sync_val_compare_and_swap(&_instance, 0, n)) {
                         delete n;
                }
        }
        return *_instance;
}

__sync_val_compare_and_swap() is a GCC atomic builtin to perform CAS.


Conclusion
Singleton is not a complicated pattern in serial programming, but once it comes multi-threaded, things become very complicated.
Locking is good to prevent data race, but it is expensive. Replace Locking with atomic operation if applicable.



Reference:

1. <<Design Patterns: Elements of Reusable Object-Oriented Software>>
2. GCC Atomic builtin: http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html
3. C++ and the Perils of Double-Checked Locking: http://www.aristeia.com/Papers/DDJ_Jul_Aug_2004_revised.pdf