Sheet3_105329.pdf

Operating Systems Problem Set 3 Problem 1 Suppose two threads A and B are concurrent. List all the possible values of the variables when the code finishes executing (Assume atomic statements) program concurrency; var x : integer(:=0); var y : integer(:=0); procedure threadA(); begin x = 1; y =...

Operating Systems Problem Set 3 Problem 1 Suppose two threads A and B are concurrent. List all the possible values of the variables when the code finishes executing (Assume atomic statements) program concurrency; var x : integer(:=0); var y : integer(:=0); procedure threadA(); begin x = 1; y = y + x; end; procedure threadB(); begin y = 4; x = x + 5; end; begin parbegin threadA(); threadB(); parend end Problem 1 Order X Y 1, 2, 3, 4 6 4 1, 3, 2, 4 6 5 1, 3, 4, 2 6 10 3, 1, 4, 2 6 5 3, 1, 2, 4 6 10 3, 4, 2, 1 1 5 Problem 2 busy waiting wastes CPU time and may have unexpected effects. Consider two processes, H, with high priority, and L, with low priority. At a certain moment, with L in its critical region, H becomes ready to run. H now begins busy waiting, but since L is never scheduled while H is running, L never gets the chance to leave its critical region, so H loops forever. Does the same problem occur if round-robin scheduling is used instead of priority scheduling? Problem 2 No this problem will not occur with RR scheduling. Round Robin will give each process a time slice even if it has low priority. But during the time slices taken by H while L in the critical section, H will still spend them in busy waiting. Problem 3 Consider the following busy waiting approach to the mutual exclusion problem. Assume that the integer variable turn, which keeps track of whose turn it is to enter the critical section, is initially 0. while(TRUE) { while(turn != 0); critical_region(); turn = 1; noncritical_region(); } a) Process 0 while(TRUE) { while(turn != 1); critical_region(); turn = 0; noncritical_region(); } b) Process 1 Problem 3 Why this approach is not a serious candidate to solve the mutual exclusion problem even though it does avoid all races! (Your answer must include the shortcomings of the approach itself, not those of busy waiting.) while(TRUE) { while(turn != 0); critical_region(); turn = 1; noncritical_region(); } a) Process 0 while(TRUE) { while(turn != 1); critical_region(); turn = 0; noncritical_region(); } b) Process 1 Problem 3 This solution requires that the two processes strictly alternate in entering their critical regions. While this algorithm does avoid all races, it is not really a serious candidate as a solution because it violates condition 3. (doesn’t guarantee progress) No process running outside its critical region may block other processes. Problem 4 Does the busy waiting solution described in the previous problem work when the two processes are running on a shared-memory multiprocessor, that is, two CPUs sharing a common memory? Problem 4 Yes, no problem Problem 5 Find a counterexample that demonstrates that this solution is incorrect to solve mutex problem. 18 void main() 19 { 20 blocked = false; 21 blocked = false; 22 turn = 1; 23 parbegin(P(0), P(1)); 24 parend 25 } 01 boolean blocked; 02 int turn; 03 void P(int id) 04 { 05 while (true) 06 { 07 blocked[id] = true; 08 while (turn != id) 09 { 10 while (blocked[1 - id]); 11 turn = id; 12 } 13 14 blocked[id] = false; 15 16 } 17 } Problem 5 turn = 1 03 void P(0) 04 { 05 while (true) 06 { 07 blocked = true; 08 while (turn != 0) 09 { 10 while (blocked); 11 turn = 0; 12 } 13 14 blocked = false; 15 16 } 17 } blocked = 0 03 void P(1) 04 { 05 while (true) 06 { 07 blocked = true; 08 while (turn != 1) 09 { 10 while (blocked); 11 turn = 1; 12 } 13 14 blocked = false; 15 16 } 17 } 0 Problem 5 turn = 1 03 void P(0) 04 { 05 while (true) 06 { 07 blocked = true; 08 while (turn != 0) 09 { 10 while (blocked); 11 turn = 0; 12 } 13 14 blocked = false; 15 16 } 17 } blocked = 1 03 void P(1) 04 { 05 while (true) 06 { 07 blocked = true; 08 while (turn != 1) 09 { 10 while (blocked); 11 turn = 1; 12 } 13 14 blocked = false; 15 16 } 17 } 0 Problem 5 turn = 1 03 void P(0) 04 { 05 while (true) 06 { 07 blocked = true; 08 while (turn != 0) 09 { 10 while (blocked); 11 turn = 0; 12 } 13 14 blocked = false; 15 16 } 17 } blocked = 1 03 void P(1) 04 { 05 while (true) 06 { 07 blocked = true; 08 while (turn != 1) 09 { 10 while (blocked); 11 turn = 1; 12 } 13 14 blocked = false; 15 16 } 17 } 1 Problem 5 turn = 0 03 void P(0) 04 { 05 while (true) 06 { 07 blocked = true; 08 while (turn != 0) 09 { 10 while (blocked); 11 turn = 0; 12 } 13 14 blocked = false; 15 16 } 17 } blocked = 1 03 void P(1) 04 { 05 while (true) 06 { 07 blocked = true; 08 while (turn != 1) 09 { 10 while (blocked); 11 turn = 1; 12 } 13 14 blocked = false; 15 16 } 17 } 1 Problem 6 Show that an atomic exchange (between a register and a memory location) instruction can be used to implement a lock equivalent to the one implemented with the atomic testand-set (TAS) instruction. Problem 6 TSL enter: TSL R0, lock CMP R0, #0 JNE enter (critical section) leave: MOV lock, #0 XCH G enter: MOV R0, #1 XCHG R0, lock CMP R0, #0 JNE enter (critical section) leave: MOV lock, #0 Problem 7 Does Peterson’s solution to the mutual exclusion problem work when process scheduling is preemptive? How about when it is non-preemptive? Problem 7 It certainly works with preemptive scheduling. In fact, it was designed for that case. When scheduling is non-preemptive, it will work as well given that the want array in initialized to 0’s. Problem 8 Compare the following set of definitions of semaphores. Is there any difference in the effect of the two sets of definitions when used in programs? That is, could you substitute one set for the other without altering the meaning of the program? Problem 8 Definition 1 from lecture slides void semWait(s) { s.count--; if (s.count < 0) { s.queue.enqueue(P); block; } } void semSignal(s) { s.count++; if (s.count 0) { s.count--; } else { s.queue.enqueue(P); block; } } void semSignal(s) { // s is a semaphore if (len(s.queue) >= 1) { P=s.queue.dequeue(); wakeup(P); } else { s.count++; } } Problem 8 The two are equivalent. In the definition, when the value of the semaphore is negative, its value tells you how many processes are waiting. In the second definition, you don't have that information readily available. However, the two versions function the same. Problem 9 Given the following processes a. Insert semaphores to satisfy the properties: a. Print A before F b. Print F before C b. Insert semaphores such that only AGBFEC or AGFBEC P1 Print(A) P2 Print(G) Print(B) Print(F) Print(C) Print(E) Problem 9 Part a Note that s1 and s2 must start with initial value 0 Print(A) up(&s1) Print(B) down(&s2) Print(C) Print(G) down(&s1) Print(F) up(&s2) Print(E) Problem 9 Part b Note that s1, s2, s3, s4 and s5 must start with initial value 0. Print(A) up(&s1) down(&s2) Print(B) up(&s3) down(&s4) down(&s5) Print(C) down(&s1) Print(G) up(&s2) Print(F) up(&s4) down(&s3) Print(E) up(&s5) Problem 9 Part b another solution Note that s1, s2, s3 and s4 must start with initial value 0. Print(A) up(&s1) down(&s2) Print(B) up(&s3) down(&s4) Print(C) down(&s1) Print(G) up(&s2) Print(F) down(&s3) Print(E) up(&s4) Thank you