⚠️ Warning: This is a draft ⚠️

This means it might contain formatting issues, incorrect code, conceptual problems, or other severe issues.

If you want to help to improve and eventually enable this page, please fork RosettaGit's repository and open a merge request on GitHub.


'''Semaphore''' is a synchronization object proposed by Edsger Dijkstra. A semaphore is characterized by a natural number ''k''. A [[task]] may atomically increase or decrease ''k''. When ''k'' reaches 0 the tasks attempting to decrease it are blocked. These are released in an unspecified order when other tasks increase ''k'', one per increment.

The natural number ''k'' works like a count of available slots for resources. When you (a task) want to use something (an object, a file, any resource) that can only be used by a limited number of tasks (usually one, but possibly more), you see if there are available slots (check the value of ''k''). If there are slots available (''k'' > 0), you take one (decrement ''k''). When you're done with the resource, you free your slot up (increment ''k''). If there were no slots available when you checked (''k'' = 0), you wait until one becomes available.

A semaphore is considered a low-level synchronization primitive. They are exposed to deadlocking, like in the problem of [[dining philosophers]].

See also [[mutex]], a variant of semaphore.

=Sample implementations / APIs=

==[[Ada]]== Here is an implementation of a semaphore based on protected objects. The implementation provides operations P (seize) and V (release), these names are usually used with semaphores.

protected type Semaphore (K : Positive) is
   entry P;
   procedure V;
   Count : Natural := K;
end Mutex;

The implementation of:

protected body Semaphore is
   entry P when Count > 0 is
      Count := Count - 1;
   end P;
   procedure V is
      Count := Count + 1;
   end V;
end Semaphore;


   S : Semaphore (5);
   S.P;    -- Acquire the semaphore
   S.V;    -- Release it
      S.P; -- Wait no longer than 0.5s
   or delay 0.5;
      raise Timed_Out;
   end select;
   S.V;    -- Release it

It is also possible to implement semaphore as a monitor task.



Here is an example of counting semaphores in C, using the "pthread" library. To make the code more readable, no error checks are made. A productive version of this implementation should check all the return values from the various function calls!

The example is divided into two parts: the "Interface" (usually the content of a *.h file)...

// Interface
typedef struct Sema *Sema;

Sema Sema_New (int init);
void Sema_P   (Sema s);
void Sema_V   (Sema s);

... and the "Implementation" (the *.c file):

// Implementation
#include <stdlib.h>
#include <pthread.h>

struct Sema {
    int value;
    pthread_mutex_t *mutex;
    pthread_cond_t  *cond;

Sema Sema_New (int init) {
    Sema s;

    s = malloc (sizeof (*s));
    s->value = init;
    s->mutex = malloc (sizeof (*(s->mutex)));
    s->cond = malloc (sizeof (*(s->cond)));
    pthread_mutex_init (s->mutex, NULL);
    pthread_cond_init (s->cond, NULL);

    return s;

void Sema_P (Sema s) {
    pthread_mutex_lock (s->mutex);
    while (s->value == 0) {
        pthread_cond_wait (s->cond, s->mutex);
    pthread_mutex_unlock (s->mutex);

void Sema_V (Sema s) {
    pthread_mutex_lock (s->mutex);
    if (s->value == 1) {
        pthread_cond_signal (s->cond);
    pthread_mutex_unlock (s->mutex);