please break this synchronization algorithm

Question

P1 and P2 are processes or nodes in a cluster. f1 and f2 are their flags. Supposing strong memory model, and that both processes may be restarted at any moment, and that restarting a process clears it's flag, here's an algorithm that I came up with and couldn't yet break, but that bothers me for it's not theoretically proven and looks too simple compared with Peterson's.

P1 start:
set f1
if f2 set then clear f1, wait some, goto start
else enter critical section
do whatever
clear f1

P2 start:
set f2
if f1 set then clear f2, wait some, goto start
else enter critical section
do whatever
clear f2

Can anybody see a flow? Except may be that one of the processes may starve the other by quickly re-entering the section?

Answer 1

If the "if X set then clear Y" operation is not atomic, there's a potential race condition that could prevent either from getting inside the critical section. I've tried to outline the flow below:

P1: set f1
P2: set f2
P1: is f2 set?
P2: is f1 set?
P1: yes, clear f1
P2: yes, clear f2
P1: start wait
P2: start wait
P1: end wait
P2: end wait
P1: goto start
P2: goto start

This could potentially go on forever, until there's a difference in the allocation done by the task scheduler, or the wait times for the two P are different from one another.

Answer 2

Well, apart from the starvation issue, I don't see any other problems.

Peterson's algorithm, however, guarantees fairness - each process is guaranteed to get the critical section as soon as it is next available - which your algorithm doesn't provide.

I'm curious as to why you think Peterson's algorithm is less simple, though; it's not that different to what you have.

P1 start:
set f1
x = 2
while f2 and (x == 2) wait
enter critical section, etc.
clear f1

Answer 3

It's easy to prove that this algorithm guarantees mutual exclusion. If both processes are in the critical section at the same time, it means that both flags have been set and F1 had been set before F2 (from the code of P1), and also F2 had been set before F1 (from the code of P2). This is impossible, so mutual exclusion is guaranteed.

It is simpler than Peterson's, because it doesn't guarantee bounded wait - the scenario from another answer can be repeated indefinitely many times, albeit with probability that quickly converges to zero (assuming good randomness of the wait periods).