Visit Our UNIX and Linux User Community


How many semaphores?


 
Thread Tools Search this Thread
Top Forums UNIX for Advanced & Expert Users How many semaphores?
# 1  
Old 11-06-2007
How many semaphores?

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.
# 2  
Old 11-06-2007
Would it not be "n-1" where each semaphore is effectively creating the synchronisation for one arrow?
# 3  
Old 11-06-2007
Quote:
Originally Posted by porter
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.
# 4  
Old 11-07-2007
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.
# 5  
Old 11-07-2007
Quote:
Originally Posted by kahuna
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.
# 6  
Old 11-07-2007
Java

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);

?

Last edited by porter; 11-07-2007 at 10:25 PM..
# 7  
Old 11-08-2007
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

Previous Thread | Next Thread
Test Your Knowledge in Computers #176
Difficulty: Easy
Apple's first product was the Apple I, invented by Apple co-founder Steve Wozniak.
True or False?

10 More Discussions You Might Find Interesting

1. Solaris

Semaphores

Hi, Can somebody please explain me what semaphores are? there purpose? and there effects? Thanks in advance:) (0 Replies)
Discussion started by: Laxxi
0 Replies

2. Programming

about Semaphores

Hello Everybody, I am building a server. this server contains some data. Clients may modify this data or read this data. If a client is reading the data and at the same time another client is modifying the data then at this case the reading client may read some false data (some old mixed with... (1 Reply)
Discussion started by: Omar_Mokhtar
1 Replies

3. UNIX for Dummies Questions & Answers

semaphores

I am having problem with semaphores. I am trying to protect line where process prints so that every process with print in proper order.This is the code.. #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <sys/ipc.h> #include <sys/sem.h> #include <sys/types.h> union... (3 Replies)
Discussion started by: joker40
3 Replies

4. Programming

Problem with semaphores

Hello, I was doing an exercise of semaphores and shared memory, namely the barbers: -B number of barbers -S number of chairs -C number of customers. I have done already and I compiled the code, but when run I get an error segment. Can not be and it took several days. If anyone sees the error... (2 Replies)
Discussion started by: ciudadwifi
2 Replies

5. Programming

Semaphores Urgent

Hello, Iam trying to implement the sleeping barber problem using semaphores and running on UNIX machine. Iam linking it to the thread libraries : bash-2.03$ g++ sleepingBarber.cpp -lpthread -o sleeping but when i execute it i get the following error: bash-2.03$ sleeping Starting Program... (4 Replies)
Discussion started by: mohit.choudhary
4 Replies

6. Programming

semaphores using up and down

been searching around on how to use an up and down function with semaphores but i can't find an example. i looked into using: "semop" but i have no idea how to use it. I have been able to declared the semaphores using semget and initializing them using semctl. (7 Replies)
Discussion started by: ddx08
7 Replies

7. Shell Programming and Scripting

semaphores

Hi Friends, If i execute this command it comes back with 300 lines: ipcs|grep cerebrus >>> i would like to clear the semaphores but ipcrm can remove one id at a time. is there a quicker way of removing semaphores maybe using awk? Regards, (1 Reply)
Discussion started by: kekanap
1 Replies

8. Programming

semaphores

Hi there, Could someone please confirm which POSIX semaphore routines should be used for a multiprocess (and not multithreaded) environment? sys/sem.h definitely works. but the routines, semget, semctl, semop are pretty unwieldy. So, I am looking for an easier way out. From the man pages... (2 Replies)
Discussion started by: qntmteleporter
2 Replies

9. UNIX for Dummies Questions & Answers

Semaphores

Hi all, I am using HP 10.20 on A 9000/785. My question is: If I am the only person logged in as root at the moment, how many "semaphore proccesses" should I have?? Is it only one, or it is relevant to other system proccesses? Here is what I get listing the current semaphores # ipcs -sp... (1 Reply)
Discussion started by: guest100
1 Replies

10. Programming

Semaphores

Dear Reader, I'm in a multiprocess environment working with shared mem and semaphores as mutex.. The problem is -- If one of the process hooked up with the semaphore and accessing the shared mem, terminates abruptly ( or got killed ), other process which are in want of the semaphore are... (1 Reply)
Discussion started by: joseph_shibu
1 Replies

Featured Tech Videos