race condition algorithm

As an alternative implemen开发者_高级运维tation, it is proposed to use the following code fragment which has a shared int variable turn, initialised to 0. The two threads have the local int constant mine set to 0 and 1 respectively.

while (turn != mine);
critical_region();
turn = (1-mine);

Explain clearly any possible problems and restrictions with this second alternative.

i just dont get the part, "turn = (1-mine)" i mean initially, T1 will enter cause "mine" is 1. when it exits, turn will still remain 0. so T0, won't never be able to enter the critical region?

turn = (1-mine) is relatively easy to explain. Let's say thread 0 (the one where mine is set to 0) has the critical section. When it's finished, it will set turn to 1 - mine, or 1, letting the other thread run.

When thread 1 (the one where mine is set to 1) has the critical section. When it's finished, it will set turn to 1 - mine, or 0, letting the other thread run.

This is actually a token-passing system where each thread allows the other to run by setting the variable.

The main disadvantage of something like this is that it is a token passing system. It doesn't scale well to more threads since the token is always passed to a specific thread.

By way of example, let's say thread 0 has finished with the token so sets turn to 1. But thread 1 is off doing some intensive calculations and doesn't need the token right now.

But thread 2 does need the token since it wants to do some critical section work. It has to wait until thread 1 passes it the token, not a good situation to be in.

But, in fact, that's even a problem for two threads. Once you've passed the token, you cannot re-enter the critical section until the other thread gives you the token back, regardless of whether or not it actually needs it.

just dont get the part, "turn = (1-mine)" i mean initially, T1 will enter cause "mine" is 1. when it exits, turn will still remain 0. so T0, won't never be able to enter the critical region?

First of all, the formatting of that code disguises a nasty trick - it might be better to write it like:

while (turn != mine)
    ; //spin
critical_region();
turn = (1-mine);

So the important thing to note is that when turn == mine, the thread will proceed and carry out the computation.

So, let's call our threads T0 and T1.

When T0 finishes, what will turn be set to?

When T1 finishes, what will turn be set to?