ReadWriteSerializer

Question

I am developing a C++ kernel, and I've got the need for manipulating huge data structures before the task-scheduler runs - it means in a non-preemptive environment.

For this, I have developed a read-write serializer struct whose job is to allow readers to concurrently access the data. It's worthy to note here that any writer will gain exclusive control over the data and constrain any read attempts until all pending writes are complete. That will allow software to get the complete data and eliminate race conditions - in cases where the write operation didn't complete, due to locking before the reader came in.

I want to know how efficient this implementation is and if any improvements can be made. Thank You in advance.

NOTE: Spinlock is a primitive lock that is used by SpinLock and SpinUnlock functions. It is used in the code.

struct ReadWriteSerializer
{
    unsigned long onlineReaders;
    Spinlock criticalSection;

    void enterAsReader()
    {
        SpinLock(&criticalSection);
        ++(onlineReaders);
        SpinUnlock(&criticalSection);
    }

    void enterAsWriter()
    {
        SpinLock(&criticalSection);
        while(onlineReaders)
            asm volatile("nop");
    }

    void exitAsReader()
    {
        --(onlineReaders);
        __mfence // macro declared otherwhere - asm volatile("mfence");
    }

    void exitAsWriter()
    {
        SpinUnlock(&criticalSection);
    }
};

Explanation of how this lock works:

When software attempts to read/write, it will access ReadWriteSerializer::enterAsReader or ReadWriteSerializer::enterAsWriter. On entering as a reader, the code will immediately increment the total number of concurrent readers (onlineReaders) and then unlock the serializer. That means other read/write software can come and access the serializer.

But when a writer enters, it says nop :-), no more readers entering until I finish my work. It waits until all other readers exit the lock (by decrementing onlineReaders). Then it does its work. On exit, it will free the lock for others to come.

Answer 1

Spinlocks should only be held for a very short time

Spinlocks are expensive; they cause a thread that tries to take a lock to use 100% CPU time. So when you have the lock, you should release it as quickly as possible. When you call enterAsReader(), you do not release the lock. You indicated yourself that the work you do as a writer might be manipulating "huge" data structures, so that might take a lot of time, during which readers will spin.

onlineReaders is not atomic

You do not use a lock in exitAsReader() so there isn't any guarantee that the pre-decrement is atomic. Thus, if two threads call exitAsReader() at the same time, they will both read the current value, decrement one, and store the result back. This can result in onlineReaders being effectively only decremented once instead of twice.

If you protect exitAsReader() with a lock, then you will of course immediately run into a problem, because enterAsWriter() will take the lock, and block any other thread from calling exitAsReader(). So instead, it should look like:

void enterAsWriter() {
    while(true) {
        SpinLock(&criticalSection);
        if(!onlineReaders)
            break;
        SpinUnlock(&criticalSection);
    }
}

Writer starvation

After the fix, your code suffers from a classic problem: writer starvation. To solve this, you need to have two variables; one is the number of readers that are holding the lock and the other is a counter that indicates how many writers are waiting to take the lock. The writer increments the second counter first, then tries to grab the lock. When other readers try to take a read lock, they should wait until the counter of writers is zero.