6
\$\begingroup\$

Overarching Problem

I am creating a threadsafe queue that will act as a shared buffer between two threads for a game I am developing. I need it to be threadsafe so that one thread can throw messages into the queue, and second thread can take them out for processing in real time. I have decided in order to really learn about concurrency and threading I would like to create my own threading library with the required synchronization structures(starting off with a mutex that is implemented as a spinlock). For now I am using the Poco Threading library in order to test and develop my mutex. I will move forward to creating a Windows/Linux threading environment after I have my basic synchronization structures.

Proposed Solution (mutex/spinlock)

Note: Sender and Receiver do not actually do any sending or receiving, or any queue work, they are just simply operating on numbers in tight for-loops to simulate work. I did not want to add extra variables to the test before I verified that my mutex implementation was working as expected.

Mutex.hpp

#ifdef WIN32
    #include <Windows.h>
    #define TARG_PLATFORM_WINDOWS
#else
    #include <unistd.h>
    #define TARG_PLATFORM_LINUX
#endif

//Constant values
const int MUTEX_LOCKED = 1;
const int MUTEX_UNLOCKED = 0;

class Mutex
{
private:
    volatile unsigned long long interlock;
public:
    Mutex();
    ~Mutex();
    void lock();
    void unlock();
};

Mutex.cpp

#include "Mutex.hpp"

Mutex::Mutex()
{
    interlock = 0;
}
Mutex::~Mutex()
{
}

void Mutex::lock()
{
    #ifdef TARG_PLATFORM_WINDOWS
        while(this->interlock == 1 || InterlockedCompareExchange(&this->interlock, 1, 0) == 1);
    #endif
    #ifdef TARG_PLATFORM_LINUX
        while(this->interlock == 1 || __sync_lock_test_and_set(&this->interlock, 1) == 1);
    #endif
}

void Mutex::unlock()
{
    this->interlock = 0;
    #ifdef TARG_PLATFORM_WINDOWS
    #endif
    #ifdef TARG_PLATFORM_LINUX
    #endif

}

Testing code Note: For easy reading I simply included one threads test code. The other thread has the exact same code except it is the "Receiver" and it only simply locks and unlocks no sleep() is called in thread 2. This should make it so they are both in similar starting areas when the work begins. Basically I am trying to make each thread do some work and then unlock the mutex to allow the other thread to do some work.

virtual void run()
{
    int table[2000000];
    std::cout<<"Thread1 Started"<<std::endl;

    mutex->lock();
    sleep(3) //Allow threads to both catch up to eacother
    mutex->unlock();

    mutex->lock();
    for(int i = 0; i < 2000000; i++)
    {
        table[i] = i/2;
    }
    std::cout<<"Sender block 1 done"<<std::endl;
    mutex->unlock();


    mutex->lock();
    for(int i = 0; i < 2000000; i++)
    {
        table[i] = i/2;
    }
    std::cout<<"Senderblock 2 done"<<std::endl;
    mutex->unlock();


    mutex->lock();
    for(int i = 0; i < 2000000; i++)
    {
        table[i] = i/2;
    }
    std::cout<<"Sender block 3 done"<<std::endl;
    mutex->unlock();
    //dequeue a msg
}

My Concerns

When I run the test, the threads seem to execute in order and not taking turns:

Thread1 started
Thread2 started
Sender Block 1 done
Sender block 3 done
Sender block 2 done
Receiver block 2 done
Receiver Block 1 done
Receiver block 3 done

I thought thread 2 would be able to acquire the lock before thread 1 could unlock() and lock() the mutex again. For the sake of testing I added a sleep for 100 milliseconds in the unlock() function in order to give the other thread time to acquire the lock. This worked and they alternated with the following output:

Thread1 started
Thread2 started
Sender Block 1 done
Receiver Block 1 done
Sender block 2 done
Receiver block 2 done
Sender block 3 done
Receiver block 3 done

It seems that the re-locking is too fast for the threads to take turns and I am concerned this may starve thread2 in a real application. But I do not want a sleep() in the unlock() function as this is a huge performance hit and causes context switching.

I did some reading and some people did performance tests of locking and relocking their mutex object so I tried the same for mine. It took 8-10 milliseconds for it to lock and unlcok 1 million times in a tight for loop. This seems to fast compared to other things I have read. Perhaps I am missing something?

Ultimate Questions

Should I be using a different type of lock? Is something off with my Mutex implementation? Is something invalidating the test I have written? If so what kind of test would you recommend?

Note I know this seems kind of like a Stack Overflow question but I figured since I had a solution and I wanted more of a review and possible suggestions on a solution that involves modifying code already written, this would be a better place for the question.

\$\endgroup\$
8
\$\begingroup\$

@William Morris mentioned the spinning on a lock issue (busy wait). This is a real problem that you should address.

Empty block at the end of while is non obvious to read.
You should comment on it so that people don't think it is a mistake:

while(this->interlock == 1 || InterlockedCompareExchange(&this->interlock, 1, 0) == 1);

// I would do:

while(this->interlock == 1 || InterlockedCompareExchange(&this->interlock, 1, 0) == 1)
{ /* Do Nothing. While we wait to get the lock */
}

Your lock is not exception safe:
Use RAII to guarantee that locks are correctly locked/unlocked in the presence of exceptions:

class Mutex
{
    private:
        volatile unsigned long long interlock;
    public:
        Mutex();
        ~Mutex();
    private:
        // These should be private to prevent locks being obtained
        // in a way that makes them exception unsafe.
        void lock();
        void unlock();

        // Need a friend that can lock and unlock the Mutex safely and correctly.
        friend class Locker;
};

class Locker
{
     Mutex&    m;
     public:
         Locker(Mutex& m): m(m) {m.lock();}
         ~Locker()              {m.unlock();}
};

// Usage
int main()
{
    Mutex    m;
    for(;;)
    {
        Locker lock(m);   // Locks the mutex (and gurantees it will be released)
                          // Even if there is an exception
    }
}

There are more than two types of platform.
You should make sure these are covered. If the code does not fall into a particular type then you should generate an error: http://nadeausoftware.com/articles/2012/01/c_c_tip_how_use_compiler_predefined_macros_detect_operating_system

#if  defined(WIN32)
    #include <Windows.h>
    #define TARG_PLATFORM_WINDOWS
#elif defined(__unix)
    #include <unistd.h>
    #define TARG_PLATFORM_LINUX
#else
    // Fail if this is a system you have not compensated for:
    #error "Unknown System Type"
#endif

Don't put conditional code into functions:

void Mutex::unlock()
{
    this->interlock = 0;
    #ifdef TARG_PLATFORM_WINDOWS
    #endif
    #ifdef TARG_PLATFORM_LINUX
    #endif

}

You should define macros based on your conditional tags in the header file. Use the macros in your code. This should make it clear what you are trying to achieve.

void Mutex::unlock()
{
    this->interlock = 0;
    UNLOCK_MY_MUTEX(interlock);
}

Then in the header file:

    #ifdef TARG_PLATFORM_WINDOWS
    #define UNLOCK_MY_MUTEX(x)      WindowsUnlockCode(x)
    #endif
    #ifdef TARG_PLATFORM_LINUX
    #define UNLOCK_MY_MUTEX(x)      /* Nothing required */ do {} while(false)
    // see http://codereview.stackexchange.com/a/1686/507
    #endif

You better have a good reason fir using a pointer:

mutex->lock();

Final Note:

Use an already implemented locking mechanism rather than rolling your own.

pthread_mutex      // Valid on Windows and Unix (if you get the libraries).

boost::spinlock    // http://www.boost.org/doc/libs/1_38_0/boost/detail/spinlock.hpp
\$\endgroup\$
  • \$\begingroup\$ Awesome answer. I like the level of detail presented for everything. Thanks. \$\endgroup\$ – Dean Knight Jul 6 '13 at 2:56
5
\$\begingroup\$

This answer is a bit late but I felt there were a few oversights that should be mentioned.

@William Morris is quite correct about the spinlock. You will find that this is an unacceptable way to implement a critical low level function that you would want to base the environment of your project. Some platforms do supply a type of spinlock but even those will put the thread to sleep.

@Loki Astari is also quite correct about using the native mutex libraries for your platform.

These are the issues I see with your code.

  1. "unsigned long long" Never ever use this. It is a MS/Windows type for an unsigned 64 bit integer. It is not cross-platform. It's "unsigned long" on some and I've used systems where it's 128 bit to undefined. On one system you can cast a negative value (-1) and do a compare and on the other you can't because the sign extension will be different.

  2. Your example is not thread safe at all. Any thread can call the unlock whether they locked it first or not.

  3. Your example does not handle recursion. This is an essential mutex type. Subroutines may need to work on data and cannot assume they were not called from a process that either did or did not call the lock.

To create your own mutex class to be used in a real world project such as your game, it is going to need to support most of the same functionality of existing libraries. Your mutex needs to store the ID of the locking thread, and lock count if it's recursive.

Another thing about your spinlock and why it's more than a bad idea. Your assumption is that the other thread holds the mutex and it will eventually free it while you spin wait. That is a big assumption. For that to work, you must be running on a multi-core CPU and your other thread must be assigned to a different core or your busy wait will spin forever starving the other thread from processing. Depending on the OS, it may time slice multithreading or it may be cooperative. And lastly, you say you're planning on putting this in a game. Most games these days don't have spare CPU cycles they can afford to burn and run some of the most time critical code there is.

In addition to recommending using the native libraries for each system. I would also recommend that you spend some time learning the quirks of each and create your own cross platform class based on them. Your goal of having a cross-platform class is still a very good idea. In your shoes, I would want to make as much of the code as platform agnostic as is reasonable.

\$\endgroup\$
4
\$\begingroup\$

A mutex just protects against concurrent access but does not control what order things will happen in. That has more to do with the thread scheduling algorithm.

As far as the UNIX implementation is concerned, a thread that finds the mutex locked will busy-loop waiting for it to be free. This is very wasteful of CPU time. A better approach is to suspend the calling thread until the mutex is free. You would perhaps be better using POSIX threads, which will do that for you.

\$\endgroup\$
  • \$\begingroup\$ I like the idea and I plan on building on top of both Pthreads and win32 threads. But it seems like what you are suggesting would require use of signals (so I know when the mutex is free). I am okay with it spinning for now. It is not a huge deal performance-wise currently. If it does get to be a big deal I can always go back and add complexity(e.g. extra code for signal-like behavior) to up the performance. I just want to make sure both threads are able to enqueue and dequeue their data as needed with no starvation. I guess I will put together a full test with Queues to see if its an issue. \$\endgroup\$ – Dean Knight Jul 3 '13 at 17:33
  • \$\begingroup\$ There is no need for signals. pthread_mutex_lock will return once the lock has been obtained, suspending the thread in the meantime. You might also want to look at using condition variables with mutexes to coordinate writers and readers of your queue (eg pthread_cond_wait) \$\endgroup\$ – William Morris Jul 3 '13 at 19:12
  • 1
    \$\begingroup\$ I guess I am mixing up my thought process between high and lower level stuff. I need to settle on one level and implement from there. In my case I was wanting to implement something like the function pthread_mutex_lock itself. If I were to look underneath this abstraction there must be some sort of callback, interrupt, or signal happening for it to obtain a lock. If its suspended it has to be woken up properly to avoid spinning. Regardless, Linux and Windows both have sufficient locks and Thread API's. I will just wrap a framework around them and implement higher level abstractions. Thanks! \$\endgroup\$ – Dean Knight Jul 3 '13 at 19:46
  • \$\begingroup\$ Also, +1 and +Checkmark in a few days if no other answers come along. \$\endgroup\$ – Dean Knight Jul 3 '13 at 19:47

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.