Partial Solutions to Mid Term Exam
May, 2008
Dr. T.L. Yu

1. ( 10 points ) Two threads, T1() and T2() are accessing the same critical section ( CS ). They have to wait on two semaphores S1 and S2 before they can enter the CS. Consider the following piece of code for T1 and T2:

   T1: down ( S1 ); down ( S2 ); Enter_CS(); up ( S2 ); up ( S1 );

   T2: down ( S2 ); down ( S1 ); Enter_CS(); up ( S1 ); up ( S2 );

   a) Does the code achieve mutual exclusion?

   b) Is deadlock possible for T1 and T2? Why? If your answer is yes, modify the codes so that the two threads are deadlock free; if your answer is no, prove it.

   a)Yes, it is because a thread can enter the critical section if only it has acquired the two semaphores ( "keys" ). If one thread holds a semaphore, the other cannot have it.

   b)Yes. Because threads run concurrently, it could happen that T1 has executed down ( S1 ) and T2 has executed down ( S2 ) . So now T1 is waiting for T2 to release ( UP ) S2 and T2 is waiting for T1 to release S1 and thus they in deadlock.
   To prevent deadlock, we can simply require both T1 and T2 to 'lock' ( down ) semphores in the same order S1, S2 so that whoever has first locked S1 can proceed to lock S2 and the other thread has to wait on S1. The following is the modified code that is deadlock free:

   T1: down ( S1 ); down ( S2 ); CS(); up ( S2 ); up ( S1 );

   T2: down ( S1 ); down ( S2 ); CS(); up ( S2 ); up ( S1 );

2. ( 10 points ) Suppose a bank uses the Banker's Algorithm to ensure that it is always in the safe state. Initially, the bank has only 10 million dollars and five clients, A, B, C, D, and E who estimate that that at most they need the following amount of money to finish their projects.

   Client		max. need ( in million $ )
   A		6
   B		4
   C		3
   D		3.2
   E		0.5

   A a certain time, the bank has lent the following amount of money to the clients.

   Client		outstanding loan( in million $ )
   A		3
   B		2
   C		2
   D		1.5
   E		0.3

   a)Is the bank in a safe state? Why?
   b)Suppose client D asks for another $1 M ( million ), should the bank loan the money to her? Why? ( Show your steps clearly. )

   a) Yes, the bank is in a safe state. This is because the money available in the bank is

   available = 10 - ( 3 + 2 + 2 + 1.5 + 0.3 ) = 10 - 8.8 = 1.2
   So it has enough money to terminate E, who would return 0.3 to and available becomes
   available = 1.2 + 0.3 = 1.5
   It then has enough money to terminate C ( who may still need 1 ) then D and so on. Eventually, all clients can finish their projects. The following table shows the 'terminating' steps:

   Client	money loaned	max. need	still need	Avail > still need?	terminate order	new avail after terminate
   A	3	5	2	Yes ( 3.5 > 2 )	3	6.5
   B	2	4	2	Yes ( 6.5 > 2 )	4	8.5
   C	2	3	1	Yes ( 1.5 > 1 )	2	3.5
   D	1.5	3.2	1.7	Yes ( 8.5 > 1.7 )	5	10
   E	0.3	0.5	0.2	Yes ( 1.2 > 0.2 )	1	1.5

   b) No, the bank should not loan her because if the bank does so, it would have available = 0.2 and would be in an unsafe state since it could not 'terminate' all the clients as shown in the following table.

   Client	money loaned	max. need	still need	Avail > still need?	terminate order	new avail after terminate
   A	3	5	2	No ( 0.5 < 2 )	5	0.5
   B	2	4	2	No ( 0.5 < 2 )	4	0.5
   C	2	3	1	No ( 0.5 < 1 )	3	0.5
   D	2.5	3.2	0.7	No ( 0.5 < 0.7 )	2	0.5
   E	0.2	0.5	0.2	Yes ( 0.2 ≥ 0.2 )	1	0.5

3. ( 10 points ) Suppose the "Birman-Schiper-Stephenson Protocol" is used to enforce "Causal Ordering of Messages" of a system that has four processes, P₁, P₂, P₃, and P₄. With the help of diagrams, explain clearly what the process would do in each of the following cases.
   1. The current vector time of Process P₃ is C₃ when it recieved a message from P₂ along with vector time stamp t_m, where

      C3 =

      1 2 3 1

      tm =

      1 3 3 1

      Should P₃ deliver the message immediately? Why?

   2. Process P₂ with current vector time C₂ recieved a message from P₁ along with vector time stamp t_m, where

      C2 =

      1 2 3 4

      tm =

      2 2 3 5

      Should P₂ deliver the message immediately? Why?

   If P_j has received a message from P_i, it delivers the message immediately when two conditions are satisfied:

   1. C_j[i] = t_{m[i] - 1}
   2. C_j[k] ≥ t_m[k]     all k ≠ i
   a) Yes, P₃ should deliver the message immediately because the two conditions are satisfied ( note: i = 2 ):
   1. C₃[2] = 2 = 3 - 1 = t_m[2] - 1
   2. C₃[1] = 1 ≥ 1 = t_m[1],   C₃[3] = 3 ≥ 3 = t_m[3],   C₃[4] = 1 ≥ 1 = t_m[4],  

   b) No. Because condition 2 is violated ( Note: j=2, i=1 here ):

   2. C₂[4] = 4 < 5 = t_m[4],  
   You should draw the diagrams also.

4. ( 10 points )Consider a cut C = { c₁,c₂,c₃ } where c₁,c₂, and c₃ are the cut events with vector clocks C₁,C₂,C₃ respectively. Suppose

   C1 =

   1 0 0

   C2 =

   2 2 0

   C3 =

   0 1 3

   (i) Calculate T_C = sup ( C₁, C₂,C₃ ).
   (ii) Is C a consistemt cut? Why? ( You may apply a theorem that you have learned in the class. )

   (i)

   TC =

   2 2 3

   (ii)No, it is not a consistent cut. The Theorem states that if C = { c₁, c₂, ... ,c_n } is a cut with vector time T_C, then the cut is consistent iff

   TC =

   C1[1] C2[2] . . Cn[n]

   But here T_C[1] = 2 ≠ 1 = C₁[1]. Therefore, it cannot be a consistent cut.

5. ( 15 points ) A banking system uses Chandy-Lamport global state recording protocol ( Snapshot Algorithm ) to record the global state; markers are sent along channels where FIFO is assumed. The system has three branches P₁, P₂, and P₃ and are connected by communication channels C_ij, where i, j = 1, 2, 3. Suppose LS_i denote the local state ( the money the branch possesses at the time of recording ) of branch P_i.

   P₁ initiated the recording process and right before P₁ sent out the marker, a $1 transaction is in transit on C₁₂, a $2 transit on C₂₁, a $3 transit on C₁₃, and a $4 transit on C₂₃ ( assume that the units are in million dollars ) and branches P₁, P₂, and P₃ have money $6, $8, $10 respectively ( not including any money in transit ). Assume that during the recording process, after a branch has received the money in transit, it has not sent out any additional money. With the help of diagrams, answer the following questions.

   a) When P₂ received a marker from P₁ on C₁₂, what was the state ( the amounts of money ) LS₂, and the state of C₁₂ that P₂ would record?
   b) When P₃ received a marker from P₁ on C₁₃, what was the state LS₃, and the state of C₁₃ that P₃ would record?
   c) When P₃ received a marker from P₂ on C₂₃, what was the state LS₃, and the state of C₂₃ that P₃ would record?
   d) When P₁ received a marker from P₂ on C₂₁, what was the state of C₂₁ that P₁ would record?
   e) At the end of the algorithm, what were LS₁, LS₂, LS₃, and the states of C_ij, i, j = 1, 2, 3. Please tabulate your results in the format:

   State	money
   LS1	..
   LS2	..
   LS3	..
   C12	..
   C13	..
   C21	..
   C23	..
   C31	..
   C32	..

   For details, please refer to your notes.

   Answers:

   State	money
   LS1	$6
   LS2	$9
   LS3	$13
   C12	0
   C13	0
   C21	$2
   C23	$4
   C31	0
   C32	0

6. ( 10 points ) Suppose Process P₁ has events e₁₁, e₁₂, e₁₃, e₁₄, e₁₅ e₁₆ P₂ has events e₂₁, e₂₂, e₂₃, e₂₄, e₂₅, e₂₆, P₃ has events e₃₁, e₃₂, e₃₃, e₃₄, e₃₅ e₃₆ There are message transits from e₁₂ to e₂₂, e₂₁ to e₃₂, e₂₄ to e₁₅, e₃₅ to e₂₅. Suppose the vector time clocks for e₁₁, e₂₁, and e₃₁ are

   1 0 0

   ,

   0 1 0

   ,

   0 0 1

   respectively.

   a) Draw a diagram to show all the transitions and events.

   b) Find the vector clocks of events e₁₆, e₂₆ and e₃₆.

   c) Draw on your diagram and state explicitly to give an example for each of the following global states. Your global state should be consisted of the the events given ( e.g. e₁₁ ) but should not contain any event that is sending ( e.g. e₁₂ ) or receiving a message ( e.g. e₂₂ ).

   i) a strongly consistent global state
   ii) a consistent but not strongly consistent global state
   iii) an inconsistent global state

   b)

   C(e₁₆) = (6, 4, 0 )
   C(e₂₆) = (2, 6, 5 )
   C(e₃₆) = (0, 1, 6 )

   c)

   1. {e₁₃, e₂₃, e₃₃ }
   2. {e₁₄, e₂₆, e₃₆ }
   3. {e₁₁, e₂₃, e₃₄ }

7. ( 3 points ) Which of the following about deadlock of a system which consists of both consumable and reusable resources is not true? ( Choose the best answer. ) a) The system state is deadlock free if the corresponding resource graph is reducible.
   b) If the system state is deadlock free, the corresponding resource graph is reducible.
   c) If the system is in deadlock state, there is a circular wait among some processes.
   d) For deadlock to occur, no preemption is allowed.
   e) For deadlock to occur, mutual exclusion is required.

8. ( 2 points ) Which of the following regarding a distributed system is not true. Suppose → denotes the "happened before" relation and C(a) is the Lamport's clock timestamp of event a. a) event a causually affects b if a → b
   b) if a → b and b → c then a → c
   c) for any two events a, b in a system, either a → b or b → a or a || b
   d) if a → b then C(a) < C(b)
   e) if C(a) < C(b), then a → b