Semaphores terminology

Question

The usually talked of semaphores... Do they involve busy waiting? I am confused with the terminology. Please tell me which among the connclusions i was able to draw are true.

a)Spinlocks involve busy waiting, so to avoid that,we have semaphores.
b)Semaphores are a kind of spinlocks, but we can have semaphores without busy waiting
c)pthread_condition variables do the same thing as semaphores? If so,are they equivalent to semaphores from semaphore.h library. I am confused if both represent the same functionality.

Answer 1

Abstractly, a semaphore is a lock with a number of permits associated with it. Semaphores support two operations:

1. Up, which increases the number of permits, and
2. Down, which attempts to decrease the number of permits. If insufficient permits are available, then this operation waits until enough are available.

There are many ways to implement semaphores. Typically, though, semaphores are not implemented as spinlocks, and actually have the OS block the thread and have it sleep until the requested permit becomes available. That said, a perfectly legal implementation of a semaphore could have it busy-wait; I'm just not aware of any implementations that do this.

Condition variables represent a different concept. Typically, semaphores are designed to manage a resource where only so many copies exist. Each thread that wants the resource waits until the semaphore guarding access to it becomes available, and each thread using the resource owns one permit. Condition variables are typically used to allow threads to wait for certain events to occur. They usually support the operations

1. Wait, which blocks the thread until it is signaled,
2. Notify, which tells one thread waiting on the condition variable that it can proceed, and
3. Notify-all, which tells all threads waiting on the condition variable that they can proceed.

Condition variables and semaphores can (usually) be used interchangeably, with a suitable change to the design of the lock usage. However, sometimes semaphores are easier to work with, and sometimes condition variables are easier to work with, so we have both primitives available. Commonly, you'll choose to use one over the other because of the particular library or language you're using. For example, Java objects have built-in support for monitors (condition variables paired with a lock), so it's often useful to use condition variables in Java, though Java semaphores do exist. If you're programming in Windows, then semaphores are the preferred method of synchronization, though condition variables do exist.

Hope this helps!

Answer 2

spinlocks use busy waiting, hence the name spin - thread spins doing nothing.

What it does is "can I go in? can I go in? can I go in... etc" until the lock allows it in the critical section (CS)

semaphores: usually implemented with a signal/notify and a queue so when a thread steps on a semaphore it goes to sleep and into the queue if there is another thread in the critical section. If there is no other thread in the CS, the current thread enters it. All other threads who step on the semaphore while another thread is in the CS go in the queue. When the first thread exits the CS, it steps on the semaphore again. The semaphore now takes the first thread in its queue and awakens it, which in turns makes the thread enter the CS.

With a semaphore implemented with signal/wait, the thread says can I go in? If no, the it says wake me up when I can. If yes, it goes in.

EDIT: Semaphores vs Conditions

The wait and signal operations on conditions are very similar to the P and V operations on counting semaphores. The wait statement can block a thread’s execution while a signal statement can cause resumption of another thread. There are, however, differences between them. The P operation does not necessarily block a thread, since the semaphore counter may be greater than zero. The wait statement, however, always blocks a thread. The signal statement can make ready (unblock) a blocked thread on a condition just as a V operation makes ready a blocked thread on a semaphore. The difference is that a V operation always increments the semaphore counter; thereby affecting a subsequent P operation. A signal statement on an empty condition does not affect a subsequent wait statement, and therefore, is lost. Another difference is that multiple threads blocked on a semaphore can resume execution without delay if enough V operations are performed. In the mutex-type case, multiple signal statements do unblock multiple threads, but only one of these threads is able to execute because of the mutual-exclusion property of the mutex type.