Semaphore (computer science)

from Wikipedia, the free encyclopedia

A semaphore (from ancient Greek σῆμα sēma , German 'sign' and φέρειν pherein 'carry' - for example, “signal generator”) is a data structure that consists of an integer and the atomic usage operations “reserve / try” and “release”. It is particularly suitable for managing limited (countable) resources that several processes or threads should access, such as producers and consumers, and for coordinating asynchronous processes. In contrast to a lock or a mutex , the activity carriers that “reserve” and “release” do not have to be identical.

functionality

Usually the integer (counter) is initialized at the start of the semaphore with the numerical value of the maximum available resources or the maximum number of processes that can use the resource at the same time. A process that wants to access the resource must first call the "Reserve / Try" operation, and then, when it no longer needs the resource, the "Release" operation. The counter is counted down by 1 with each reservation, and increased by 1 when it is released. The counter must not drop below 0: If a reservation is made when the counter is 0, the reserving process waits until another process has released resources. There are also implementations that count in the negative. This shows how many processes are waiting for a release.

Semaphores can be used in programming for process synchronization , i.e. for solving tasks in which the parallel execution of several processes / threads requires that the execution be timed. With a limited number of resources, they are generally used to establish an order in which many threads share these scarce elements (e.g. resource: “CPU core”, number: 4). This can also be used to encapsulate access to shared data (resource: "Access rights to the data", number: only one at a time). Semaphores can also be used for communication between threads. They then mostly serve as counters for available information packages. The semaphore is started with "0 packages available" and then counted up (and back down to 0).

Origin of name

See also: semaphore (disambiguation)

Abandoned railway signal (semaphore)

The word semaphore goes back to the shape signals of mechanical railway signals . The semaphores used there indicate whether a train is occupying a resource, i.e. whether a section of track may be used or not.

Interactions between processes running in parallel

When processes are executed in parallel or at different times, implicit or explicit interactions occur.

In the case of implicit interactions, a process is not aware that the execution of actions will influence another process. This is e.g. This is the case, for example, when a process calls a system service that the operating system cannot process immediately because other processes have occupied the required resources. The process cannot continue its actions until the system service has been executed. Here the process interaction becomes visible as a blocking function call. A process cannot and must not take special precautions against blocking due to implicit interactions.

Explicit interactions between processes are:

competitor
Processes are in competition with one another if they simultaneously access an operating resource (e.g. memory structure, connection, device) that is only available in limited numbers and in which the use of a copy is only possible exclusively by a process, because it is otherwise erroneous results or inconsistent states occur, d. H. when there are critical sections in the programs of the processes.
cooperation
Processes cooperate when they consciously coordinate their actions, e.g. B. because they are in a client / contractor relationship.

Both reserve and release must be atomic operations. If a reservation cannot be satisfied, it can simply block (acquisition of the resource via race condition among those waiting), the semaphore queue up (usually blocking) or reject it (non-blocking). Often there is only one copy of the resource (so-called mutual exclusion ); the semaphore then coordinates the execution of the process actions over time. In the event of a competitive situation, sequencing the execution (of the critical sections) somehow designed ensures that the resource is not used by several processes in an arbitrarily changing manner. In the case of a cooperation situation, sequencing that corresponds to the situation ensures that the processes work together (e.g. a contractor does not try to start working on something even though the client has not yet placed an order).

Solution from Dijkstra

Semaphores as a mechanism for process synchronization were conceived by Edsger W. Dijkstra and presented in his 1965 article Cooperating sequential processes .

A semaphore is a data structure with an initialization operation and two usage operations. The data structure consists of a counter and a queue for recording blocked processes (here an example in C ): 

 typedef struct semaphor {
    int zaehler;
    Queue *queue; /* Warteschlange */
 } Semaphor;

The counter and the queue are protected and can only be changed using the semaphore operations. The effect of the usage operation can be summarized as follows:

  • Semaphores regulate interaction situations of processes by counting
  • Semaphores implement passive waiting for the processes if further execution cannot be permitted

With the initialization operation, the counter is set to a non-negative value (≥ 0) and the queue i. d. Usually set to empty. 

 void
 init(Semaphor  *s, int v)
 {
    s->zaehler = v;
    s->queue->empty(s->queue);
 }

If a semaphore is used to organize competitive situations, it is initialized with a positive value. A semaphore for a cooperation situation, on the other hand, is initialized with 0 (see application examples ).

The usage operations were labeled P and V by Dijkstra . These are initials of Dutch words or suitcase words for prolaag ( prober te verlagen = try to lower) and Verhoog . Further, common explanations are passeer (pass), proberen (check) and vrijgeven (release), condemned (increase). Programming interfaces use more mnemonic terms such as wait (wait), acquire (acquire) or down (below) for the P operation and signal (signal), release (release), post (send) or up (above) for the V operation .

The counter is decremented when the P operation is called. If the counter is then greater than or equal to 0, the process continues its actions. However, if the counter is less than 0, the control flow does not return from the operation. The calling process is blocked and placed in the semaphore's queue. When the V operation is called, the counter is incremented. A process is removed from the queue and unblocked if the queue is not empty. The unblocked process then continues its actions with those who followed the P call that blocked the process. The functionality of the semaphore operations explained here allows you to easily determine whether there are processes that are blocked on the semaphore: if the semaphore counter is less than 0, there are still blocked processes. These processes called the P operation when the counter was already zero or less. The check is explicitly noted here in order to clarify the effect of the V-operation on other processes. Concrete implementations can also move a check for non-empty queues to the queuing method. 

/* down() */
 void
 P(Semaphor *s)
 {
   s->zaehler = s->zaehler - 1;
   if (s->zaehler < 0)
      selbst_blockieren(s->queue); /* Blockieren des Prozesses, Einreihung in Warteschlange */
 }

/* up() */
 void
 V(Semaphor *s)
 {
   s->zaehler = s->zaehler + 1;
   if (s->zaehler <= 0)
      einen_entblocken(s->queue); /* Entblockieren eines Prozesses aus der Warteschlange */
 }

Semaphores whose counters can assume a "1" as the largest positive value due to the initialization and use are often also referred to as binary semaphores or mutex locks. Semaphores whose counters can have positive values ​​greater than "1" are called counting semaphores.

Both operations must be atomic , atomic actions. This guarantees that after a semaphore operation has been called, no other process can access the same semaphore to modify it by means of an operation call before the semaphore operation called first has been fully executed. The indivisibility is necessary to organize the synchronization and to avoid race situations when executing the semaphore operations by parallel processes.

The above explanation of the mode of operation is one of several possible. These differ in the sequence of the check for blocking / unblocking and the increment / decrement operation. In some representations, the counter does not take negative values. (The counter value described above is obtained by subtracting the length of the queue from the actual.) In this case, the name binary semaphore then becomes obvious. However, the effect of the operations on processes is independent of the type of implementation. The above explanation was given preference because of a simple interpretation of the counter: If the counter is greater than 0, its value indicates how many processes can still call the P operation without blocking. If the counter is negative, its absolute value indicates how many processes called the P operation and were blocked in the process.

Semaphores eliminate the disadvantage of actively waiting for other synchronization solutions such as special machine commands or spinlocks , since a process is blocked until the reason for the blockage no longer applies. The definition leaves open which blocked process is removed from the queue during the execution of the V operation. A semaphore a real queue after -served basis ( Engl. "First first come, served" ) warrants is sometimes referred to as a strong semaphore. A weak semaphore, on the other hand, does not guarantee the chronologically correct processing of the queue. So z. B. in real-time operation, the unblocking of processes is tied to their priority instead of their blocking time.

Application examples

  • Use in competitive situations I
    In a critical section ka_A, process A changes a data structure that the process shares with a process B. Process B changes the data structure in its critical section ka_B. A semaphore with an exclusion function is used to ensure that processes A and B are never in their critical sections at the same time. For this purpose, the semaphore is initialized with 1, so a binary semaphore is used:
       Gemeinsam von A und B genutzter Semaphor: mutex
       Initialisierung: init (mutex, 1)  /* Es gibt 1 Ressourcen-Exemplar "Recht auf Betreten eines kritischen Abschnitts" (k. A.) */

       Prozess A           Prozess B
          …              ...
          P (mutex) P (mutex) /* versuche "Betreten-Recht" zu reservieren (blockierend) */
          ka_A             ka_B
          V (mutex) V (mutex) /* freigeben des "Betreten-Rechts" */
          …              ...
  • Use in competitive
    situations II If processes each exclusively need a resource that is only available in a limited number, a counting semaphore is used to ensure that a process is blocked when all resources are in use. The semaphore is initialized with the number of available resources:
       Semaphor zur Betriebsmittelverwaltung: s_available
       Initialisierung: init (s_available, n)

       Prozess
          ...
          P (s_available) /* Anzeige des Nutzungswunschs; warte bis "für mich reserviert wurde" */
          … /* Nutzung des Betriebsmittels */
          V (s_available) /* Anzeige des Nutzungsabschlusses, freigeben */
          ...
  • Use in cooperation
    situations Process A contains a program section C_I, in which a data structure is initialized which is then processed by process B in a program section C_V. Obviously, C_I must be executed before C_V under all circumstances. A semaphore is used in the signaling function:
       Gemeinsam von A und B genutzter Semaphor: s_inform
       Initialisierung: init (s_inform, 0)

       Prozess A           Prozess B
          …              ...
          C_I              P (s_inform)
          V (s_inform) C_V
          …              ...

Process B tries to reserve and has to wait until process A has counted up to 1 ("1 data record available") by means of release s_inform.

implementation

An implementation of the semaphore mechanisms is conceptually located in the operating system, since it has to work closely with the process management. A realization of the indivisibility on monoprocessor systems can then, for. B. be done by means of an interrupt lock. In the case of multiprocessor systems, the instruction sequences of the semaphore operations must be bracketed by spin locks . Implementation by the operating system also enables several processes with their actually disjoint address spaces to be able to share a semaphore.

If semaphores are offered by a thread package that runs in the user address space (user-level threads), the implementation of indivisibility is more complex. It must take any interruptions into account and depends on the information available about user-level threads in the core.

Related topics

  • Mutex - generic term for processes that enable mutual exclusion of data access.
  • Monitor - a programming language concept for process synchronization.
  • Jacketing - the ability to bypass a blocking system call.
  • Bolt variable - variant of the semaphore for more flexible implementation of a read-write lock .

literature

  • Andrew S. Tanenbaum: Modern Operating Systems (=  Pearson Studies - IT ). Third updated edition. Addison-Wesley Verlag, 2009, ISBN 978-3-8273-7342-7 , pp. 1248 (English, original title: Modern Operating Systems .).
  • James H. Anderson, Yong-Jik Kim, Ted Herman: Shared-memory mutual exclusion: major research trends since 1986 . In: Distrib. Comput. tape 16 , no. 2-3 . Springer-Verlag, September 2003, ISSN  0178-2770 , p. 75-110 , doi : 10.1007 / s00446-003-0088-6 .
  • M. Raynal, D. Beeson: Algorithms for mutual exclusion . MIT Press, Cambridge MA 1986, ISBN 0-262-18119-3 .

Web links

Individual evidence

  1. ↑ Semaphores: Basic Concepts . In: The Linux Programmer's Guide
  2. ↑ cs.utexas.edu EW Dijkstra Archive (Dutch)
  3. ↑ a b Abraham Silberschatz, Peter B. Galvin, Greg Gagne: Operating system concepts . 7th edition. John Wiley & Sons, Hoboken NJ 2005, ISBN 0-471-69466-5 , 6.5 Semaphores, pp. 200 (English).
  4. ↑ pubs.opengroup.org
  5. ^ Abraham Silberschatz, Peter B. Galvin, Greg Gagne: Operating system concepts . 7th edition. John Wiley & Sons, Hoboken NJ 2005, ISBN 0-471-69466-5 , 6.5 Semaphores, pp. 201 (English).