Using BOOL as threadlock

[mof]

Hello,

I've written my first multithreaded app (a directshow filter) but I have a question about the way I lock the data transfers. I am using a simple bool global variable: e.g.

thread1

while(lock == true) Sleep(1);
lock = true;
list.AddTail(dummy);
SetEvent(event);
lock = false;

thread2
//This is in a loop with a WaitForSingleObject

if(lock == false)
{
lock = true;
p = list.GetHead();
//I copy the variable into a new local variable
list.RemovHead();
lock = false;
}

It appears to work, but I'm concerned there might be a fundamental flaw to such an approach, like an infrequent race condition. Any advice would be appreciated, please also excuse the Windows stuff as they're not fundamental to the question.

[shacktar]

It appears to work, but I'm concerned there might be a fundamental flaw to such an approach, like an infrequent race condition.

Yes, this is always a concern when using standard data for locks. The problem would be if one thread gets the green light, goes to the line lock = true;, but then there's a context switch before that line executes. Then, another thread gets the green light. Who knows, maybe it will work all the time for this app, untouched? To be safe, use a synchronization object such as a mutex or a critical section.

[mof]

Thankyou.

Do you know how a synchronization object does its magic and avoids race conditions?

[m4ster r0shi]

Google and Wikipedia are very good places to search for answers to such questions.

Check this out -> http://en.wikipedia.org/wiki/Mutual_exclusion

Also, check this out:

#include <windows.h>
#include <process.h>

#include <algorithm>
#include <iostream>
#include <utility>

class Lock
{
    static const int max_threads = 10;

    static volatile bool entering[max_threads];
    static volatile int  priority[max_threads];

    int cur_thread_id;

public:

    static void Init()
    {
        for (int thread_id = 0; thread_id < max_threads; ++thread_id)
        {
            entering[thread_id] = false;
            priority[thread_id] = 0;
        }
    }

    Lock(int cur_thread_id_): cur_thread_id(cur_thread_id_)
    {
        entering[cur_thread_id] = true;

        priority[cur_thread_id] = 1 + *std::max_element(priority, priority + max_threads);

        entering[cur_thread_id] = false;

        for (int thread_id = 0; thread_id < max_threads; ++thread_id)
        {
            while (entering[thread_id]) Sleep(1);

            while (priority[thread_id] != 0
                   && (
                         std::pair<volatile int, int> (priority    [thread_id],     thread_id)
                       < std::pair<volatile int, int> (priority[cur_thread_id], cur_thread_id)
                       )
                   ) Sleep(1);
        }
    }

    ~Lock() { priority[cur_thread_id] = 0; }
};

volatile bool Lock::entering[Lock::max_threads];
volatile int  Lock::priority[Lock::max_threads];

#define MAKE_FUNCTION(i) \
void thread_ ## i (void *) \
{ \
    Lock lock(i); \
\
    std::cout << "this is thread " << i << std::endl; \
}

MAKE_FUNCTION(0) MAKE_FUNCTION(1) MAKE_FUNCTION(2) MAKE_FUNCTION(3) MAKE_FUNCTION(4)
MAKE_FUNCTION(5) MAKE_FUNCTION(6) MAKE_FUNCTION(7) MAKE_FUNCTION(8) MAKE_FUNCTION(9)

int main()
{
    Lock::Init();

    _beginthread(thread_0, 0, 0);
    _beginthread(thread_1, 0, 0);
    _beginthread(thread_2, 0, 0);
    _beginthread(thread_3, 0, 0);
    _beginthread(thread_4, 0, 0);
    _beginthread(thread_5, 0, 0);
    _beginthread(thread_6, 0, 0);
    _beginthread(thread_7, 0, 0);
    _beginthread(thread_8, 0, 0);
    _beginthread(thread_9, 0, 0);

    Sleep(100);

    return 0;
}

It's a simple (and hopefully correct) implementation of Lamport's bakery
algorithm. Try commenting out Lock lock(i); and see what happens.

[shacktar]

Also, when I said "critical section", I meant the Windows Critical Section object:
http://msdn.microsoft.com/en-us/library/ms682530(v=vs.85).aspx

Wikipedia's definition of "critical section" is just the code that touches one or more shared resources. The Windows "Critical Section" is more like a Mutex.

[mof]

I took you advice shacktar and replaced "bool lock" with "lockMutex" and am using WaitForSingleObject() and ReleaseMutex(), works fine.
Thankyou m4ster also I'll have a indepth look at your code.

It's a pity this forum doesn't have a DirectShow area as I've tried the MSDN site but seem to luck out.

Thanks again.

[kbw]

Within a process you should use Critical Sections. See http://msdn.microsoft.com/en-us/library/ms686908%28v=vs.85%29.aspx

[shacktar]

Yes, and in theory they should be faster than Mutexes. Noticing the difference would depend on the application.

[mof]

Ok I'll look at critical sections.

I ran the program of m4sters and it was interesting. The lock is locking the console window to prevent overlap. But what does this mean?

volatile bool Lock::entering[Lock::max_threads];
volatile int Lock::priority[Lock::max_threads];

Does that ensure that all the lock classes use this same memory space? One variable for multiple instances? The rest of the code gives me headaches trying to understand especially the priority. Thanks

[shacktar]

Does that ensure that all the lock classes use this same memory space? One variable for multiple instances?

That's what the static modifier does. If a class has a static member variable, then that variable would have the same value for all instances of that class. If one instance modifies that variable, all instances would then see the same value. In this example, the Lock class also has a static method static void Init(). Such a method can only modify static member variables and is not attached to a particular instance (and cannot be called as instance.method). Notice how it's called in this example (it can also be called from within the body of a non-static method).

Lock::Init();

The rest of the code gives me headaches trying to understand especially the priority

This example uses the priority to determine which thread can resume (and thus leave the constructor). In this case, the example defines a priority of zero as "the thread is done". It assigns priorities to each thread as they enter the constructor as "1 greater than the max priority already assigned". i.e. the first thread would have a priority 1, the second thread would have a priority 2 (assuming the first thread did not complete. If it did, the second thread would have a priority 2), and so on. Once a thread finishes (and its priority gets set to zero), the next one "in line" gets the green light, leaves from the sleep cycle, leaves the constructor, and does its job (i.e. calls cout).

This is essentially where the magic happens:

for (int thread_id = 0; thread_id < max_threads; ++thread_id)
        {
            while (entering[thread_id]) Sleep(1);

            while (priority[thread_id] != 0
                   && (
                         std::pair<volatile int, int> (priority    [thread_id],     thread_id)
                       < std::pair<volatile int, int> (priority[cur_thread_id], cur_thread_id)
                       )
                   ) Sleep(1);
        }

This is where threads get placed "in line" and are not allowed to leave until all the threads with a lower priority value have finished their task. The destructor of the Lock class is called when a thread is done.

The first part:

while (entering[thread_id]) Sleep(1);

is there to ensure that a thread has been given a priority before checking if it can leave the line.

Great code, btw m4ster r0shi

[LB]

Are critical sections better to use in most cases? I'm only going to use multithreading for simple applications and I want to know what the best way to make the program threadsafe is.

[shacktar]

(talking Windows here) I would venture to say that Mutexes are better to use in most cases than Critical Sections, because of the fact that they can be used across processes and the fact that you can declare a timeout when acquiring them (read: they're the safer choice). Critical Sections, essentially work using atomic operations in user space and go to kernel space only if they need to, hence the potential speed improvement. If speed is critical, and you don't need cross-process locking, what I would do is implement a Critical Section and Mutex solution side-by-side (you can #ifdef between them), and compare performance to see if Critical Sections offer any benefit.

[mof]

Thanks for the explanation shacktar, the priority makes more sense now. But why the 'volatile' declarations, since my guess was misplaced. I've seen it before and didn't understand it then either.

Had to change the Sleep(100) to Sleep(1000) to allow all the threads to execute.

Also what is the best way to share variables between processes'? Am using File/Mem mapping but is there a better way? I assume the method is OS dependent.

[LB]

Sleep(0) is better because it allows however much time needed before returning to it, instead of you having to guess.

@shacktar: thanks, I'll check it out :)

[andywestken]

On Windows, a memory mapped file is probably the best way to share bulkier data between processes.

Some applications use the registry for small amounts of data, when they're not in a hurry. You can monitor the registry value for changes using RegNotifyChangeKeyValue.

Or you can define shared variables, with Visual C++, using #pragma data_seg

#pragma data_seg("Shared")

DWORD g_dwThreadIdApp = 0;

#pragma data_seg()

// Instruct the linker to make the Shared section
// readable, writable, and shared.
#pragma comment(linker, "/section:Shared,rws") 

[shacktar]

But why the 'volatile' declarations

The volatile modifier tells the compiler to not do funny things with the variable for optimization purposes, such as caching it, doing operations involving it out of order, or even completely removing its operations, among other things.

Observe the following:

//Code A

bool someBool = false; //Line 1

someBool = false; //Operation A

if(someBool) //Operation B
{
     doSomeStuff();
}
else
{
     doSomeOtherStuff();
}

If you were a compiler optimizing for speed, what would you do if you saw Operations A and B above? Well, at Operation A, someBool was already set to false. And presumably, someBool did not change between Line 1 and Operation A. A compiler optimizing for speed would simply remove Operation A entirely (effectively removing a needless move instruction at the assembly level). What about Operation B? someBool is guaranteed to be false here, because presumably, someBool did not change between Operations A and B, so why do the if statement at all? This will save a jump instruction at the assembly level.

Now, our optimized code is the following:

//Code B

bool someBool = false;

doSomeOtherStuff();

Much nicer isn't it?

Now, if we had declared bool someBool as volatile bool someBool, we would have a guarantee that all operations involving someBool would be just as they are in code. If we had typed in Code A above, then the compiler would leave it alone.

Now, volatile comes into play with multi-threaded code. Let's say we have Code A above, and then the compiler optimized it to Code B. Now, let's also say that this code is accessed by multiple threads. Let's say one thread sets someBool to false but then there's a context switch right before Operation B (which got optimized out!) What if some other thread sets someBool to true? Well, we would have a synchronization issue because the first thread would come back and call doSomeOtherStuff when it should have called doSomeStuff! If someBool were declared volatile this type of synchronization problem wouldn't happen.

You know how I said the following above?

shacktar wrote:

And presumably, someBool did not change between Line 1 and Operation A. A compiler optimizing for speed would simply remove Operation A entirely

shacktar wrote:

because presumably, someBool did not change between Operations A and B, so why do the if statement at all?

In a nutshell, with multithreaded code, the above assumptions are invalid and thus compiler optimizations can lead to synchronization problems.

Had to change the Sleep(100) to Sleep(1000) to allow all the threads to execute

Maybe you have a slower CPU than m4ster r0shi.

Also what is the best way to share variables between processes'? Am using File/Mem mapping but is there a better way?

That's one way to do it. Another way is to have one process open a socket and listen at a particular port and have the processes communicate data through that connection.

[andywestken]

Incidentally, DirectShow provides it's own little CCritSect class. You use it in conjunction with the CAutoLock class. See DirectShow part of MSDN for info.

[mof]

Thanks for all the great advice and instruction. It's helping to fill some of the many holes in my C++ knowledge.

volatile bool Lock::entering[Lock::max_threads];
volatile int Lock::priority[Lock::max_threads];

So these declarations are just to make these variables 'volatile' so that they are threadsafe?
'static' in the Class to ensure only 1 copy 'volatile' outside to prevent optimisations.

[helios]

So these declarations are just to make these variables 'volatile' so that they are threadsafe?

volatile doesn't ensure thread-safety. It merely tells the compiler to try to write back results as quickly as possible. This is like a weak thread safety, as it merely reduced the probability of race conditions. For proper thread-safety, you need to use synchronization objects.

[shacktar]

So these declarations are just to make these variables 'volatile' so that they are threadsafe?

Volatility alone is not sufficient to ensure thread safety. What ensures thread safety in this example is the locking mechanism (the Lock class). I ran this example with volatile removed and there was still no contention for the output stream. However, it is good practice to declare memory that may be accessed by multiple threads as volatile to side-step any potential compiler-imposed synchronization breaking.

'static' in the Class to ensure only 1 copy

For static member variables, yes there is only one copy shared amongst all instances of that class. Also, remember that static member variables and static methods can be used without ever instantiating the class (if declared public).