This is for my Comp. Architecture class, but I know the subject it is prevalent in Programming as well.

I'm having a hard time understanding a question for my class. We might have a question on it for our test so I'm hoping someone might be able to explain this to me.
I've tried googling for examples, but everything that comes up is program related. My book gives no examples, just explains what an up and down does.

Q: Make a table showing which of the processes P1, P2, and P3 are running and which are blocked as a function of time from 0 to 1000 msec.
All three processes perform up and down instructions on the same semaphore. When two processes are blocked and an up is done, the process with
the lower number is restarted, that is, P1 gets preferance over P2 and P3, and so on. Initially, all three are running and the semaphore is 1.

At t=100 P1 does a down
At t=200 P1 does a down
At t=300 P2 does an up
At t=400 P3 does a down
At t=500 P1 does a down
At t=600 P2 does an up
At t=700 P1 does a down
At t=800 P1 does an up
At t=900 P1 does an up

Solution:

I could explain the entire thing, but that takes a lot more work, and in truth, it may be better if you told us which part you don't understand. Perhaps all that's missing in your understanding is actually just a small thing (maybe even one of definition), so if you can tell us where you're stuck on, we can help you get unstuck so you can figure the rest out.

I think I just need to see it worked out. I don't understand the changes (RRR->SRR->RRR->etc). It says all 3 processors perform the up/down instructions on the same semaphore. So what happens exactly to the semaphore and P2/P3 when P1 does a down?

I'm sure if I saw the first 3 (t=100, t=200,t=300) I would understand.

This post was edited by Ryans on Dec 5 2012 01:29am

All 3 processors perform up/down on the same semaphore just means that no two processors can do the same operation in sequence -- not even the same processor doing the same thing twice.

That is, you can't have P1 do a down, followed by P2 doing a down, because the semaphore is already set to 0 after P1 does its down.

Here -- I'll work through the first few steps for you.

Opening state -- T=0-100, all processors running RRR, S = 1

at T100-T200 -> T100 P1 does a down -> P1 decrements S to 0 --> all 3 processors still running (RRR)
at T200-T300 -> T200 P1 does a down -> P1 can't decrement S because S is already 0, has to wait for another process to do an up --> P1 stopped, P2 P3 running (SRR)
at T300-T400 -> T300 P2 does an up -> P2 does the up and increments S to 1; P1 can now do its down, so it is unblocked and brings S back to 0 --> all 3 processors are running again (RRR)
at T400-T500 -> T400 P3 does a down -> P3 tries to do a down, but S is already 0 -> P3 halts (RRS)


--------------

Here's another way to think about it. The semaphore is a light switch. Your 3 processors are 3 dudes who are trying to either turn the light switch on or off.

If you tell the first dude to turn the light off, and then you tell him to turn it off again -- he can't. He has to wait for someone to turn the light on again before he can turn the light off for a second time. What the problem means when it talks about lower process # having priority, is that if Dude #1 and Dude #3 are both trying to turn the light off, and the light is already off... they have to wait for Dude #2 to turn the light on. And once Dude #2 turns the light on, Dude #1 has dibs and gets to go first. (Dude #3 is screwed and has to wait for Dude #1 or Dude #2 to turn the light on again *and* no other dude has to be waiting for the light to turn on either.)

This post was edited by irimi on Dec 5 2012 02:32am

Worth noting (and worthwhile exercise) that though it gets more complex to model the problem if you have two semaphores, the model/analogy above still works and the logic is just as simple as before.

What if the same sequence of operations were to occur, but you now have 2 semaphores (S1 and S2) instead of just one? (assume S1 = 1 and S2 = 1 at T=0)

You can look at this as the 3 dudes again, but now they have two light switches to work with. Whenever a dude gets an "up" or a "down" command, they can do it on either light switch -- whichever one is in a state that allows them to run their command.

This post was edited by irimi on Dec 5 2012 02:39am