simple custom made mutex failing

Can you spot the error in the code? tickets ends up going below 0 causing long stalls.

struct SContext {
    volatile unsigned long* mutex;
    volatile long* ticket;
    volatile bool* done;
};

static unsigned int MyThreadFunc(SContext* ctxt) {

    // -- keep going until we signal for thread to close
    while(*ctxt->done == false) {

        while(*ctxt->ticket) { // while we have tickets waiting
            unsigned int lockedaquired = 0;
            do {
                if(*ctxt->mutex == 0) { // only try if someone doesn't have mutex locked
                    // -- if the compare and swap doesn't work then the function returns
                    // -- the value it expects
                    lockedaquired = InterlockedCompareExchange(ctxt->mutex, 1, 0);
                }
            } while(lockedaquired !=  0); // loop while we didn't aquire lock
            // -- enter critical section

            // -- grab a ticket
            if(*ctxt->ticket > 0);
                     (*ctxt->ticket)--;

            // -- exit critical section
      开发者_如何转开发      *ctxt->mutex = 0; // release lock
        }
     }

     return 0;
}

Calling function waiting for threads to finish

    for(unsigned int loops = 0; loops < eLoopCount; ++loops) {
        *ctxt.ticket = eNumThreads; // let the threads start!

        // -- wait for threads to finish
        while(*ctxt.ticket != 0)
            ; 
    }
    done = true;

EDIT:

The answer to this question is simple and unfortunately after I spent the time trimming down the example to post a simplified version I immediately find the answer after I post the question. Sigh..

I initialize lockaquired to 0. Then as an optimization to not take up bus bandwith I don't do the CAS if the mutex is taken.

Unfortunately, in that case where the lock is taken the while loop will let the second thread through!

Sorry for the extra question. I thought I didn't understand windows low level synchronization primitives but really I just had a simple mistake.

I see another race in your code: One thread can cause *ctxt.ticket to hit 0, allowing the parent loop to go back and re-set *ctxt.ticket = eNumThreads without holding *ctxt.mutex. Some other thread may already now hold the mutex (in fact, it probably does) and operate on *ctxt.ticket. For your simplified example this only prevents "batches" from being cleanly separated, but if you had more complex initialization (as in more complex than a single word write) at the top of the loops loop you could see strange behavior.

I posted a bug where I thought it was a legitimate multithreaded problem but really it was just bad logic. I solved the bug as soon as I posted. Here is the problem lines and answer

unsigned int lockedaquired = 0;

I initialized lockaquired to 0 and then after I added an if statement to skip the expensive operation of doing a CAS. This optimization caused it to fall out of the while loop and into the critical section. Changing the code to

unsigned int lockedaquired = 1;

Fixes the problem. There is another hidden problem in the code that I found as well(I really shouldn't code late at night anymore). Anyone notice the semicolon after the if statement in the critical section? Sigh...

if(*ctxt->ticket > 0);
    (*ctxt->ticket)--;

That should be

if(*ctxt->ticket > 0)

Also, Ben Jackson pointed out that a thread probably will be inside the critical section when we reset the ticket to eNumThreads. While this is perfectly fine in this sample code if you were to apply it to a problem where you needed to do more operations it might not be safe because the threads aren't running in lockstep so keep that in mind if you apply this to your code.

A final note, if anyone does decide to use this code for their own implementation of a mutex please remember that your main driver thread is spinning idle. If you are doing a large operation in the critical section that takes a deal of time and your ticket count is high consider yielding your thread to let other software make use of the CPU while its waiting. Also, consider using a spin lock if the critical section is large.

Thank you