Subject: Concurrency The question is from the book called \"The art of multiproc
ID: 664494 • Letter: S
Question
Subject: Concurrency
The question is from the book called "The art of multiprocessor programming"
Chapter 2
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
Let us prove by small example...
Let us consider coffee shop with three buttons. milk coffee tea. Now label1 with coffee was pressed. So it will invoke milk thread to mix coffee powder to ensure produce coffee. so now thread t1 and t3 are invoked.
Then immediately press tea button..so it has to invoke t2 thread and t3 thread. But t3 thread is already engaged with thread t1. So it has to wait. So with these scenario we can prove sequential time-stamp system does not work for three threads in the concurrent case.