UNIX for Advanced & Expert Users

Hello, first of all I apologize if this thread is not in the correct section of this forum, but this one just seemed the most appropriate.
The question I have does not concern Unix specifically, it applies to virtually any OS, however it is in Unix where I learned about this problem.

So, the question is: What is the least number of semaphores needed to guarantee that n processes will run in a specified order ("chain of processes"), like this:

P1 -> P2 -> P3 -> ...... -> Pn ?

It means that P2 will not be allowed into critical section before P1 has exited it, P3 will not go before P2, and so on.

I would really appreciate if you could comment on this, since I am trying to get the correct answer for quite some time and nobody I asked could provide the answer.
Thank you.

Would it not be "n-1" where each semaphore is effectively creating the synchronisation for one arrow?

No, I'm afraid not. A process can wait on more than one semaphore, so we don't need that many of them. I am told it is even less than log(n) with base 2 (!), although I cannot prove it.

Is the requirement that only semaphores be used? It seems to me that all it would take is single semaphore that guards access to a memory location that indicates the last process completed. Each process would wait on the semaphore and once it got access, would check to see if its predecessor had run. If so it would execute and update the last process completed. If not, it would release the semaphore and try again.

Yes, it is. This is a problem given by my Operating Systems teacher a couple of weeks ago. It was a lesson on which he described the use of semaphores and an example that preceded this problem contained a pseudocode like this:

Code:

Process1()
{
    down(s1);down(s2);       // waits on 2 semaphores
    DoWork();                // performs job
    up(s2);up(s3);           // signals some semaphores
}

so I suppose we are to determine how can those semaphores be arranged in a way such that the least number of them is used.

1. Are the semaphores binary? Or can it start off at a value of n and will let you until it gets down to zero?

2. Can the process do

Code:

up(s1);
down(s2);
up(s3)
down(s4)

doWork();

up(s4);
down(s3);
up(s2);
down(s5);

?

You can do this with only one semaphore and a bit of code.

Basically, you have one semaphore that defines the locked sequence and a variable which holds the current (or last) executed process.


Yours faithfully, Tim