Semaphore

From Rosetta Code

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.

[edit] Sample implementations / APIs

[edit] 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;
private
   Count : Natural := K;
end Mutex;

The implementation of:

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

Use:

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