Tag Info

4

Here's a tricky interleaving. R1,R2 denote the independent logical registers used by the threads, while count is the shared variable in memory. Thread 1 starts its first iteration, performing only a read. count=0, R1=0, R2=? Thread 2 performs 99 iterations. count=99, R1=0, R2=99 Thread 1 completes its first iteration (increment and write). count=1, R1=1, R2=...

1

Looks like this modification is correct. Proof is similar to proof of Lamport algorithm and follows. Consider two processes $P_i$ and $P_k$ who entered critical sections at moments $e$ and $f$, correspondingly, requested them at moments $e'$ and $f'$, and exited at moments $e''$ and $f''$. At moment $e$ process $P_i$ have received a confirmation from $P_k$....

1

I believe the purpose is to fulfill the first condition of entering the critical section (site $S_i$ must receive a message from all other sites with timestamp greater than its own request) in case some other site never requests to enter the critical section. If $S_i$ sends a critical section request to $S_j$, but $S_j$ never requests the critical section ...

Only top voted, non community-wiki answers of a minimum length are eligible