Semaphore (computer science)
a semaphore (griech.: Semaphor) is a data structure for process synchronisation, thus for the solution by problems, for which several processes want to use operational funds, of which only limited a number (often only one copy) for order stands. With the kindthe operational funds can it itself around different resources (z. B.CCUs) or program sections (so-called critical sections) act.
Table of contents |
name origin
original designates the word semaphore a signal mast with mobile wings, as it for transmission of news in earlier centuries one used, later also a traffic light. Also on the railway the form signals were called semaphores. The computer scientist Edsger W.Dijkstra used semaphores for the first time in the year 1965 with the implementation of its operating system.
problems with several processes
in multi-process systems and multiprocessor systems arise the following problems, which can be solved by semaphores:
parts of global resources
- resourceslike printers, memory, processors is limited. Stand z. B. to three printer equal for the order, then that must be regulated access to these printers. Maximally three orders for pressure can be parallel implemented. If a fourth process wants to print, then it must wait for the end of an order.
interprocess communication/process synchronisation
- access to thread - global memory must become totally enclosed with possible access from several Threads. With unit processors are and. And. still cheat in the form of temporary suppressing of interrupts or task changes or atomic READ Modify Write instructions possible. At the latest with multiprocessor systems semaphores are accordingly andco-ordinated programs necessarily. On a data structure the following access methods are possible:
- one or more vintage Threads
- accurately a write Thread
- accesses
several write accesses do not lead simultaneous reading and a writing at the same time to inconsistent data, to inconsistencies of the read data. In order to prevent, data structures must around semaphores or criticalSections to be extended, which are gotten before access to the actual structure and returned again.
Dijkstras solution
the data structure possibly has over a counter and a process queue as well as the methods WAIT and signal. First Dijkstra used the designations P and V (Netherlands for passeren / vrijgeven (happen/release)).
It is specified, how many critical processes may exist, whereby each process stresses resources. The number of still free resources is held in the counter. Each WAIT - call reduces the counter. Is the counterafterwards smaller than zero, the calling process is waited the queue of the semaphore, otherwise it may enter the critical section. The method signal increases the counter. If the counter was before smaller than zero, the process present on the first position becomes from the queuereleased. Sometimes also the process waits with WAIT in a loop, if and as long as the counter is equal to zero, and reduces it only afterwards (in the meantime it again increased).
Stand z. B. three equal printers for the order, know the orders for pressure over a semaphore alsothe maximum value three to be administered. First each printer receives an order. If the number of the current orders exceeds the number of three, the surplus come into the queue.
In the simplest case a semaphore from a bit consists to be set, that can or not, which also binary semaphore or Mutex is called. A process, which enters a critical range, deletes the semaphore bit. This prevents an entering of the range by other processes. The semaphore is again set, if the process leaves the critical range. Waiting processes are then successively activated.
Another possibility forSynchronisation of critical processes are monitors.
implementation
a semaphore is a protected variable (or an abstract data type), which only over the following functions can be accessed:
P (semaphore s) { while (s <= 0) {}; // waits to s> 0, spin LOCK s= s-1; // as soon as occupy> s 0 resources} V (semaphore s) {s = s+1; } INIT (semaphore s, Int v) {s = v; }
The value of a semaphore is the number of free units of resources. The function P () waits, until oneResources are available, on which it stresses on it one directly.V () is the reverse function, which makes resources again available, after it is not no more used by the process. The functions P () and V () must be atomic, D. h. no other process can access the semaphore during their execution. The function V () becomes also as UP, which calls function P () down.
avoidance of waiting loops
waiting loops waste unnecessarily processor time (active compares a waiting). In order to avoid a waiting loop, can a semaphorea list by processes to be assigned. If a process the P () - function implements and the semaphore already is set to zero, then will the process of this list, the queue called is added. If a process the semaphore with the V () - function increases, and other processesin the waiting list are, then one of it is taken and continued by the list. This forms the basis of the monitor technology.
Queue queue; /* queue * P (semaphore s) {if (s< =0) haltean (queues); /* stopping the process, waiting queue * s = s-1; } V (semaphores) {s = s+1; wake up (queues); /* waking a process up with nonempty queue *} INIT (semaphore s, Int v) {s = v; }
With it it is to be noted however that with processors, which do not possess special instructions for the administration of lists again critical rangesarise to the implementation of the queues. These must be protected then with other methods (spin LOCK, preventing an interruption).
see also
Web on the left of
- teaching program about
- “executive: Programming of concurrent processes with semaphores “of Stefan Hilzinger
