How does semaphore work?

Question

Can the semaphore be lower than 0? I mean, say I have a semaphore with N=3 and I call "down" 4 times, then N will remain 0 but one process will be blocked?

And same the other way, if in the beginning I call up, can N be higher than 3? Because as I see it, if N can be higher than 3 if in the beginning I call up couple of times, then later on I could call down more times than I can, thus putting more processes in the critical section then the semaphore allows me.

If someone would clarify it a bit for me I will much appreciate.

Greg

Answer 1

Calling down when it's 0 should not work. Calling up when it's 3 does work. (I am thinking of Java).

Let me add some more. Many people think of locks like (binary) semaphores (ie - N = 1, so the value of the semaphore is either 0 (held) or 1 (not held)). But this is not quite right. A lock has a notion of "ownership" so it may be "reentrant". That means that a thread that holds a lock, is allowed to call lock() again (effectively moving the count from 0 to -1), because the thread already holds the lock and is allowed to "reenter" it. Locks can also be non reentrant. A lock holder is expected to call unlock() the same number of times as lock().

Semaphores have no notion of ownership, so they cannot be reentrant, although as many permits as are available may be acquired. That means a thread needs to block when it encounters a value of 0, until someone increments the semaphore.

Also, in what I have seen (which is Java), you can increment the semaphore greater than N, and that also sort of has to do with ownership: a Semaphore has no notion of ownership so anybody can give it more permits. Unlike a thread, where whenever a thread calls unlock() without holding a lock, that is an error. (In java it will throw an exception).

Hope this way of thinking about it helps.

Answer 2

(Using the terminology from java.util.concurrent.Semaphore given the Java tag. Some of these details are implementation-specific. I suspect your "down" is the Java semaphore's acquire() method, and your "up" is release().)

Yes, your last call to acquire() will block until another thread calls release() or your thread is interrupted.

Yes, you can call release() more times, then down more times - at least with java.util.concurrent.Semaphore.

Some other implementations of a semaphore may have an idea of a "maximum" number of permits, and a call to release beyond that maximum would fail. The Java Semaphore class allows a reverse situation, where a semaphore can start off with a negative number of permits, and all acquire() calls will fail until there have been enough release() calls. Once the number of permits has become non-negative, it will never become negative again.

Answer 3

Hi Greg consider following example :

public static void main(String [] args) throws InterruptedException {

        Semaphore available = new Semaphore(1, true);

        available.acquire();
        System.out.println("Acquire : " +available.availablePermits());

        available.release();
        System.out.println("Released : " +available.availablePermits());

        available.release();
        System.out.println("Released : " +available.availablePermits());

        available.release();
        System.out.println("Released : " +available.availablePermits());

        available.release();
        System.out.println("Released : " +available.availablePermits());

        available.acquire();
        System.out.println("Acquire : " +available.availablePermits());

        available.acquire();
        System.out.println("Acquire : " +available.availablePermits());

        available.acquire();
        System.out.println("Acquire : " +available.availablePermits());

        available.acquire();
        System.out.println("Acquire : " +available.availablePermits());

        available.acquire();
        System.out.println("Acquire : " +available.availablePermits());
    }

If you see the output u will get following :

Acquire : 0
Released : 1
Released : 2
Released : 3
Released : 4
Acquire : 3
Acquire : 2
Acquire : 1
Acquire : 0

And wait is going on.

So basically permit will increase on every release and acquire will decrease it until 0. Once it reached 0 it will wait until release is called on same object :)

Answer 4

Yes, a negative value means you have processes waiting for the semaphore to be released. A positive value means you can call acquire that many times before the semaphore blocks.

You could think of the value in this way: a positive number means there are that many resources available. A negative value means there are that many entities needing a resource when all resources are taken at the moment. When you acquire a resource you decrement the value, when you release it you increase the value. If the value is still >= 0 after the decrement you get the resource, otherwise your entity is put into a queue.

A nice explanation of semaphores in Wikipedia: http://en.wikipedia.org/wiki/Semaphore_(programming)

Answer 5

Just see N as the counter that counts your limited resource. Since you can not have a negative number of resources, N remains >= 0. If the number of your available resources changes, the maximum N has to be changed, too. I wouln't consider it good style to increment n without decrementing it first in any other case.

Answer 6

Using java.util.concurrent.Semaphore with methods acquire() and release(), I think permits will always be >=0. Let's say you want to synchronize threads so that only 1 thread can be inside for loop. If sem is type of Semaphore that has initial value 1, this will not work for more than 2 threads.

while(true){            

    sem.wait(); // wait is acquire

    for(int i=0; i<=5; i++){

        try {
            Thread.sleep(250);
        }catch (InterruptedException e) {}

        System.out.println("Thread "+ threadname+ " " + i);

             }
    sem.signal(); // signal is release }

However, you can implement the Semaphore class from java and make your own class that allows this.

package yourpackage;

import java.util.concurrent.Semaphore;

public class SemaphoreLayer {
public Semaphore s=null;
public String name;
private int val;

public SemaphoreLayer(int i){
    s=new Semaphore(i); val=i;
}

public void wait(){
 try {
     val--;
     s.acquire();

  } catch (InterruptedException e) {
    System.out.println("Error signal semaphorelayer");
}}

public void signal(){
    if(val<0){val++;}{
        s.release();
        val++;
    }
}

}

Now val can be negative. However, I am not sure that this is completely safe, because if we have signal from one thread and wait from the other and they try val++ and val-- this can be bad. (chances for this are very small but stil they exist, so if you are coding and you have to be 100% no error, I don't recommend using this code ) In conclusion this is why it is better to use concept of monitors in java and key word synchronized.