Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Variant of Dekker's algorithm confusion

This program execute two different threads and tell me who the winner of the "race" is.

Unexpectedly sometimes BOTH threads "wins" (I expected someone or no one to win). Is this expected behaviour and why? I'm obviously missing something fundamental here.

class Program
{
    public volatile static int a = 0; 
    public volatile static int b = 0;

    public static void Main()
    {
        for(int i = 0; i < 1000; i++)
        {
            a = 0; 
            b = 0;

            Parallel.Invoke(delegate { a = 1; if (b == 0) Console.WriteLine("A wins"); },
                            delegate { b = 1; if (a == 0) Console.WriteLine("B wins"); });

            Console.WriteLine(System.Environment.NewLine);

            Thread.Sleep(500);
        }
    }
}

Results:

A wins

B wins

A wins
B wins

A wins

...
like image 923
JK. Avatar asked Oct 04 '12 10:10

JK.


People also ask

What is Dekker’s algorithm?

To obtain such a mutual exclusion, bounded waiting, and progress there have been several algorithms implemented, one of which is Dekker’s Algorithm. To understand the algorithm let’s understand the solution to the critical section problem first.

What is Dekker’s solution?

It avoids the strict alternation of a naïve turn-taking algorithm, and was one of the first mutual exclusion algorithms to be invented. Although there are many versions of Dekker’s Solution, the final or 5th version is the one that satisfies all of the above conditions and is the most efficient of them all.

What is Dekker’s third version of the mutual exclusion problem?

Third Version of Dekker’s Solution – To re-ensure mutual exclusion, it sets the flags before the entry section itself. The problem with this version is a deadlock possibility. Both threads could set their flag as true simultaneously and both will wait infinitely later on.

How to remove lockstep synchronization from Dekker’s algorithm?

In Second version of Dekker’s algorithm, lockstep synchronization is removed. It is done by using two flags to indicate its current status and updates them accordingly at the entry and exit section.


1 Answers

You're using volatile incorrectly:

declaring the variables volatile is not enough, you need to make sure that everywhere you read/write them, you use Thread.VolatileRead(ref myVar)/Thread.VolatileWrite(ref myVar)

Also, volatile does NOT ensure read/write order (from different threads), even if used correctly. Browse SO for information on the topic. EDIT: it seems to do on a x86 single core machine

You could simply use the lock statement, but if you want to get to the bottom of this, I recommand reading, understanding, then reading again this free e-book

ADDITIONS:
I just browsed through the Parallel class in .NET 4, and nowhere the volatile keyword is used.
They also copy the array of Action<T> before looping over it for some reason, but I doubt that impacts you.

like image 191
Louis Kottmann Avatar answered Oct 21 '22 04:10

Louis Kottmann