Mutual exclusion for an asynchronous thread using primitive operators in c++

Question

I've been trying to use c++ primitives operators and variables, like int, if, and while to develop a thread-safe mechanism.

My idea is to use two integers variables called sync and lock, incrementing and checking the sync and after that incrementing and checking the lock. If all the checkings are successful, then the lock is guarantee, but it tries again if the checking is unsuccessful.

It seems that my idea is not working properly as it is asserting in the final verification.

#include <assert.h>
#include <iostream>
#include <string>
#include <thread>
#include <vector>

class Resource {
    // Shared resource to be thread safe.
    int resource;

    // Mutual exclusion variables.
    volatile int lock;
    volatile int sync;

    public:
        Resource() : resource( 0 ), lock( 0 ), sync( 0 ) {}
        ~Resource() {}

        int sharedResource() {
            return resource;
        }

        void sharedResourceAction( std::string id ) {
            bool done;

            do {
                int oldSync = sync;
                // ++ should be atomic.
                sync++;
                if ( sync == oldSync + 1 ) {
                    // ++ should be atomic.
                    lock++;
                    if ( lock == 1 ) {

                        // For the sake of the example, the read-modify-write
                        // is not atomic and not thread safe if threre is no
                        // mutex surronding it.
                        int oldResource = resource;
                        resource = oldResource + 1;

                        done = true;
                    }
                    // -- should be atomic.
                    lock--;
                }

                if ( !done ) {
                    // Pseudo randomic sleep to unlock the race condition
                    // between the threads.
                    std::this_thread::sleep_for(
                             std::chrono::microseconds( resource % 5 ) );
                }
            } while( !done );
        }
};

static const int maxThreads = 10;
static const int maxThreadActions = 1000;

void threadAction( Resource& resource, std::string& name ) {
    for ( int i = 0; i < maxThreadActions; i++) {
        resource.sharedResourceAction( name );
    }
}

int main() {
    std::vector< std::thread* > threadVec;
    Resource resource;

    // Create the threads.
    for (int i = 0; i < maxThreads; ++i) {
        std::string name = "t";
        name += std::to_string( i );

        std::thread *thread = new std::thread( threadAction,
                                               std::ref( resource ),
                                               std::ref( name ) );

        threadVec.push_back( thread );
    }

    // Join the threads.
    for ( auto threadVecIter = threadVec.begin();
          threadVecIter != threadVec.end(); threadVecIter++ ) {
        (*threadVecIter)->join();
    }

    std::cout << "Shared resource is " << resource.sharedResource()
              << std::endl;

    assert( resource.sharedResource() == ( maxThreads * maxThreadActions ) );

    return 0;
}

Is there a thread-safe mechanism to protect shared resources using only primitives variables and operators?

Answer 1

No, there are a few reasons why this doesn't work

Firstly the standard describes it not to work. You've (explicitly) got a read/write and write/write race condition and the standard forbids this.

Secondly, ++i is in no way atomic. Even on mainstream intel processors it isn't - it'll usually be an inc instruction when it needs to be a lock inc instruction.

Thirdly, volatile has no threading meaning in c++ like it does in java or c#. Its neither necessary nor sufficient to achieve anything to do with threadsafety (outside of nasty compiler extensions like volatile:/ms). See this answer for more information about volatile in c++.

There may be more issues in your code but this list should be enough to dissuade you.

Edit: And to actually answer your final question - no I dont think its possible to implement thread safety mechanisms from primitive types and operations in a standard compliant way. Basically you need to get the memory-subsytem, cpu AND compiler to all agree not to perform some kinds of transformations when implementing thread safety mechanisms. This generally means you need to use compiler hooks or guarantees outside of the standard and also knowledge of the final target CPUs guarantees or intrinsics to achieve it.

Answer 2

volatile is absolutely no good for multithreading:

Within a thread of execution, accesses (reads and writes) through volatile glvalues cannot be reordered past observable side-effects (including other volatile accesses) that are sequenced-before or sequenced-after within the same thread, but this order is not guaranteed to be observed by another thread, since volatile access does not establish inter-thread synchronization.

In addition, volatile accesses are not atomic (concurrent read and write is a data race) and do not order memory (non-volatile memory accesses may be freely reordered around the volatile access).

If you want to have atomic operations on an integer, the proper way to do it is with std::atomic<int>. That gives you guarantees on memory ordering that will be observed by other threads. If you really want to do this sort of lock-free programming, you should sit and absorb the memory model documentation, and, if you're anything like me, strongly reconsider attempting lock-free programming as you try to stop your head exploding.