3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Please add the Spinlock implementation for review also. \$\endgroup\$ – πάντα ῥεῖ Mar 18 '18 at 10:18
  • \$\begingroup\$ It uses the simple gcc __sync primitives. I don't think it is needed... \$\endgroup\$ – Shukant Pal Mar 18 '18 at 11:12
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Nice answer; but on the other hand - I've built atomic primitives too that use inline assembly to use the LOCK prefix. Is Atomic::dec(&onlineReaders); also efficient? \$\endgroup\$ – Shukant Pal Mar 19 '18 at 2:38
  • \$\begingroup\$ Also, your code doesn't certain that a reader coming after the writer will be denied, right? Because, enterAsWriter() will leave the lock in the loop, meanwhile the reader could pick it up and start reading, right? \$\endgroup\$ – Shukant Pal Mar 19 '18 at 2:39
  • \$\begingroup\$ Should I post my updated code, too? \$\endgroup\$ – Shukant Pal Mar 19 '18 at 2:41
  • \$\begingroup\$ @SukantKumar post your updated code in a different question if you want would like to receive more reviews. If it's for reference, post it as an answer \$\endgroup\$ – Blasco Mar 19 '18 at 10:36
  • \$\begingroup\$ Atomic instructions, such as with a LOCK prefix, may or may not be efficient. It depends on your CPU architecture, cache coherency, access patterns, cacheline sharing and so on. Even if it is more efficient, then the question is whether the compiler and or the CPU will preserve the order between spinlock operations and atomic operations on onlineReaders. I'd first get it to work using only your spinlocks, and look at further optimizations later. \$\endgroup\$ – G. Sliepen Mar 19 '18 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.