evaluating the logic of processes in an Operating System

Consider a uniprocessor system executing concurrently two processes P and Q. Each process executes the code listed below, process P – procedure P, and process Q – procedure Q. Both processes arrive within a very short time of each other, but no assumptions can be made about the time they start execution and their relative speed. All statements used in the code below from A to K are atomic ie. they either execute completely or not at all. The execution of the processes is synchronised by two binary semaphores S1 and S2. The semaphore S1 is initialised to 1, and the semaphore S2 is initialised to 0. The code executed by the processes is as follows:

procedure P
begin 
A; 
wait(S1); 
B; 
signal(S1); 
C; 
D; 
signal(S2); 
E; 
end

procedure Q 
begin 
F; 
wait(S1); 
G; 
H; 
J; 
signal(S1); 
wait(S2); 
K; 
end

a.Give at least four possible orders of execution for statements A to K.

A,C,D,E,K

A,D,C,E,K

F,C,D,E,K

F,D,C,E,K

b. What is the function of each of the sem开发者_如何转开发aphores S1 and S2 in the given example?

S1 – used for waiting

c. Is it possible for statement E to execute before statement F? Justify your answer.

Yes, (but i am not so sure, can someone confirm?)

d. Is it possible for statement K to execute before statement A? Justify your answer.

---

a. I wonder why you've left out statements B, F, G, H and J. Do you suppose that they don't get executed? I think that once you've answered b you'll easily answer a.

b. All semaphores can wait, but that's how they work, not what they're for. Can you be more specific? Semaphores can be used for synchronization (foo must happen after bar) and for exclusion (between these two sections of code, only one may execute at a time). What do you think the two semaphores are being used for here?

c. What would be required for E to possibly execute before F? Is that condition present? Or, look at it the other way: What would be required to keep E from executing before F? Is that condition present?

d. See c.

---

Here is a semaphore being used to ensure that bar happens after foo:

S = 0
process 1:
  foo
  signal(S)
process 2:
  wait(S)
  bar

And here is a semaphore being used to ensure that only one of two sections of code is executed at a time:

S = 1
process 1:
  wait(S)
  foo
  signal(S)
process 2:
  wait(S)
  bar
  signal(S)

Do you see the difference? Reexamine the code in your homework and see if it makes more sense now.