Menu
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
...
923
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.
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.
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.
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.
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.
191
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
