Difference between Counting and Binary Semaphores

Question

What is the difference between Counting and binary semaphore.

What I have seen somewhere is that both can control N number of processes which have requested for a resource. Both have taken and Free states.

Is there any restriction on how many Resources a Binary semaphore and Counting semaphore can protect?

Both allow only One process to use a resource at a time...

Is there any other difference? Are the above mentioned properties correct?

Answer 1

The most basic difference between counting and binary semaphore is that:

1. Binary semaphore cannot handle Bounded wait as its just a variable that hold binary value. Counting semaphore It can handle bounded wait as it has converted a variable into a structure with a Queue.

2. Strcuture implementation Binary semaphore: int s;

   Counting Semaphore: Struct S { int s; Queue q; }

Using the counting semaphore now process once gained the CS(Critical Section) now has to wait for the other to get the CS, so not a single process strave. Each process get a chance for CS.

Answer 2

There are two essential concepts to building concurrent programs - synchronization and mutual exclusion. We will see how these two types of locks (semaphores are more generally a kind of locking mechanism) help us achieve synchronization and mutual exclusion.

A semaphore has two parts : a counter, and a list of tasks waiting to access a particular resource. A semaphore performs two operations : wait (P) [this is like acquiring a lock], and release (V)[ similar to releasing a lock] - these are the only two operations that one can perform on a semaphore. In a binary semaphore, the counter logically goes between 0 and 1. You can think of it as being similar to a lock with two values : open/closed. A counting semaphore has multiple values for count.

What is important to understand is that the semaphore counter keeps track of the number of tasks that do not have to block, i.e., they can make progress. Tasks block, and add themselves to the semaphore's list only when the counter is zero. Therefore, a task gets added to the list in the P() routine if it cannot progress, and "freed" using the V() routine.

Now, it is fairly obvious to see how binary semaphores can be used to solve synchronization and mutual exclusion - they are essentially locks.

ex. Synchronization:

thread A{
semaphore &s; //locks/semaphores are passed by reference! think about why this is so.
A(semaphore &s): s(s){} //constructor
foo(){
...
s.P();
;// some block of code B2
...
}

//thread B{
semaphore &s;
B(semaphore &s): s(s){} //constructor
foo(){
...
...
// some block of code B1
s.V();
..
}

main(){
semaphore s(0); // we start the semaphore at 0 (closed)
A a(s);
B b(s);
}

In the above example, B2 can only execute after B1 has finished execution. Let's say thread A comes executes first - gets to sem.P(), and waits, since the counter is 0 (closed). Thread B comes along, finishes B1, and then frees thread A - which then completes B2. So we achieve synchronization.

Now let's look at mutual exclusion with a binary semaphore:

thread mutual_ex{
semaphore &s;
mutual_ex(semaphore &s): s(s){} //constructor
foo(){
...
s.P();
//critical section
s.V();
...
...
s.P();
//critical section
s.V();
...

}

main(){
semaphore s(1);
mutual_ex m1(s);
mutual_ex m2(s);
}

The mutual exclusion is quite simple as well - m1 and m2 cannot enter the critical section at the same time. So each thread is using the same semaphore to provide mutual exclusion for its two critical sections. Now, is it possible to have greater concurrency? Depends on the critical sections. (Think about how else one could use semaphores to achieve mutual exclusion.. hint : do i necessarily only need to use one semaphore?)

Counting semaphore: A semaphore with more than one value. Let's look at what this is implying - a lock with more than one value? So open, closed, and ...hmm. Of what use is a multi-stage-lock in mutual exclusion or synchronization?

Let's take the easier of the two:

Synchronization using a counting semaphore: Let's say you have 3 tasks - #1 and 2 you want executed after 3. How would you design your synchronization?

thread t1{
...
s.P();
//block of code B1

thread t2{
...
s.P();
//block of code B2

thread t3{
...
//block of code B3
s.V();
s.V();
}

So if your semaphore starts off closed, you ensure that t1 and t2 block, get added to the semaphore's list. Then along comes all important t3, finishes its business and frees t1 and t2. What order are they freed in? Depends on the implementation of the semaphore's list. Could be FIFO, could be based some particular priority,etc. (Note : think about how you would arrange your P's and V;s if you wanted t1 and t2 to be executed in some particular order, and if you weren't aware of the implementation of the semaphore)

(Find out : What happens if the number of V's is greater than the number of P's?)

Mutual Exclusion Using counting semaphores: I'd like you to construct your own pseudocode for this (makes you understand things better!) - but the fundamental concept is this : a counting semaphore of counter = N allows N tasks to enter the critical section freely. What this means is you have N tasks (or threads, if you like) enter the critical section, but the N+1th task gets blocked (goes on our favorite blocked-task list), and only is let through when somebody V's the semaphore at least once. So the semaphore counter, instead of swinging between 0 and 1, now goes between 0 and N, allowing N tasks to freely enter and exit, blocking nobody!

Now, why would you need such a bizarre lock? Isn't the whole point of mutual exclusion to not let more than one guy access a resource?? Think. (Hint...You don't always only have one drive in your computer, do you...?)

To think about : Is mutual exclusion achieved by having a counting semaphore alone? What if you have 10 instances of a resource, and 10 threads come in (through the counting semaphore) and try to use the first instance?

Answer 3

Actually, both types are used to synchronize access to a shared resource, whether the entity which is trying to access is a process or even a thread.

The difference is as follows:

Binary semaphores are binary, they can have two values only; one to represent that a process/thread is in the critical section(code that access the shared resource) and others should wait, the other indicating the critical section is free.

On the other hand, counting semaphores take more than two values, they can have any value you want. The max value X they take allows X process/threads to access the shared resource simultaneously.

For further information, take a look at this link.
http://www.chibios.org/dokuwiki/doku.php?id=chibios:articles:semaphores_mutexes

EDIT
The max value that a counting semaphore can take is the the number of processes you want to allow into the critical section at the same time.
Again, you might have a case where you want exclusion over a certain resource, yet you know this resource can be accessed by a max number of processes (say X), so you set a counting semaphore with the value X.

This would allow the X processes to access that resource at the same time; yet the process X+1 would have to wait till one of the processes in the critical section gets out.