Please solve this question. Book : The art of Multiprocessor Programming chapter
ID: 3680065 • Letter: P
Question
Please solve this question.
Book : The art of Multiprocessor Programming
chapter 2 exercise 18
Exercise 18. Prove, by way of a counterexample, that the sequential time-stamp
system T 3, started in a valid state (with no cycles among the labels), does not work
for three threads in the concurrent case. Note that it is not a problem to have two
identical labels since one can break such ties using thread IDs. The counterexample
should display a state of the execution where three labels are not totally
ordered.
Explanation / Answer
Assume that each thread can read the graph atomically and they move its token atomically.
Here read and write operations together are not atomic. Lets assume three threads t1,t2 and t3.
Then assume thread t1 in 01, t2 in 02 and t3 in 03.
Initially, Thread t1 reads the graph and prepares to move to 11.
then, Thread t2 reads the graph and moves to 11.
again, Thread t3 reads the graph and moves to the next location 12.
Thread t2 reads the graph and moves to vacant space 10 and.
then, t1 moves to 11.
From this it is understood that the tokens are not totally ordered.