FACTOID # 25: If you're tired of sitting in traffic on your way to work, move to North Dakota.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Semaphore (programming)

A semaphore is a protected variable (or abstract data type) and constitutes the classic method for restricting access to shared resources (e.g. storage), also known as mutual exclusion, in a multi-threaded programming environment. It was invented by Edsger Dijkstra and first used in the THE operating system. Semaphore can refer to: Another name for the optical telegraph invented for Napoleon Bonaparte, a system of communication used prior to the invention of the electrical telegraph by moving arms atop a tower Flag semaphore, a communication system by means of flags A mechanical device (a semaphore signal) used in... In computer science and mathematics, a variable (IPA pronunciation: ) (sometimes called a pronumeral) is a symbolic representation denoting a quantity or expression. ... In computing, an abstract data type (ADT) is a specification of a set of data and the set of operations that can be performed on the data. ... Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the simultaneous use of un-shareable resources by pieces of computer code called critical sections. ... Many programming languages, operating systems, and other software development environments support what are called threads of execution. ... Edsger Dijkstra Edsger Wybe Dijkstra (Rotterdam, May 11, 1930 – Nuenen, August 6, 2002; IPA: ) was a Dutch computer scientist. ... THE is an early computer Operating System, which was designed in 1968. ...


The value of the semaphore is initialized to the number of equivalent shared resources it is implemented to control. In the special case where there is a single equivalent shared resource, the semaphore is called a binary semaphore. The general case semaphore is often called a counting semaphore.


Semaphores are the classic solution to the dining philosophers problem, although they do not prevent all deadlocks. In computer science, the dining philosophers problem is an illustrative example of a common computing problem in concurrency. ... It has been suggested that Circular wait be merged into this article or section. ...

Contents

Introduction

Semaphores can only be accessed using the following operations:

 P(Semaphore s) { wait until s > 0, then s := s-1; /* must be atomic once s > 0 is detected */ } V(Semaphore s) { s := s+1; /* must be atomic */ } Init(Semaphore s, Integer v) { s := v; } 

} ...


Notice that incrementing the variable s must not be interrupted, and the P operation must not be interrupted after s is found to be nonzero. This can be done using a special instruction such as test-and-set (if the architecture's instruction set supports it), or (on uniprocessor systems) ignoring interrupts in order to prevent other processes from becoming active. In computer science, the test-and-set instruction is an instruction used to atomically write to a memory location. ... It has been suggested that some sections of this article be split into a new article entitled instruction set architecture. ... In computing, an interrupt is an asynchronous signal from hardware or software indicating the need for attention. ...


The canonical names P and V come from the initials of Dutch words. V stands for verhoog, or "increase". Several explanations have been given for P (including passeer "pass", probeer "try", and pakken "grab"), but in fact Dijkstra wrote that he intended P to stand for the made-up portmanteau word prolaag,[1] short for probeer te verlagen, or "try-and-decrease".[2][3] (A less ambiguous, and more accurate, English translation would be "try-to-decrease.") This confusion stems from the unfortunate characteristic of the Dutch language that the words for increase and decrease both begin with the letter V, and the words spelled out in full would be impossibly confusing for non–Dutch-speakers. This article is about blends. ...


The value of a semaphore is the number of units of the resource which are free. (If there is only one resource, a "binary semaphore" with values 0 or 1 is used.) The P operation busy-waits (or maybe sleeps) until a resource is available, whereupon it immediately claims one. V is the inverse; it simply makes a resource available again after the process has finished using it. Init is only used to initialize the semaphore before any requests are made. The P and V operations must be atomic, which means that no process may ever be preempted in the middle of one of those operations to run another operation on the same semaphore. The binary numeral system, or base-2 number system, is a numeral system that represents numeric values using two symbols, usually 0 and 1. ... It has been suggested that this article or section be merged with Polling (computer science). ... ...


In the programming language ALGOL 68, in the Linux kernel[1], and in some English textbooks, the P and V operations are called, respectively, down and up. In software engineering practice they are called wait and signal, or acquire and release, or pend and post. A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ... ALGOL 68 (short for ALGOrithmic Language 1968) is an imperative computer programming language that was conceived as a successor to the ALGOL 60 programming language, designed with the goal of a much wider scope of application and a more rigorously defined syntax and semantics. ... The Linux kernel is a Unix-like operating system kernel. ...


To avoid busy-waiting, a semaphore may have an associated queue of processes (usually a FIFO). If a process performs a P operation on a semaphore which has the value zero, the process is added to the semaphore's queue. When another process increments the semaphore by performing a V operation, and there are processes on the queue, one of them is removed from the queue and resumes execution. A queue (pronounced /kuː/) is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position and removal of entities from the front terminal position. ... FIFO is an acronym for First In, First Out. ...


Semaphores today as used by programmers

Semaphores remain in common use in programming languages that do not intrinsically support other forms of synchronization. They are the primitive synchronization mechanism in many operating systems. The trend in programming language development, though, is towards more structured forms of synchronization, such as monitors and channels. In addition to their inadequacies in dealing with deadlocks, semaphores do not protect the programmer from the easy mistakes of taking a semaphore that is already held by the same process, and forgetting to release a semaphore that has been taken. A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ... // An operating system (OS) is the software that manages the sharing of the resources of a computer. ... A monitor is an approach to synchronizing two or more computer tasks that use a shared resource, usually a hardware device or a set of variables. ...


Example usage

Since semaphores can have a count associated with them, they may be employed when multiple threads need to achieve an objective cooperatively. Consider this example:

We have a thread A that needs information from two databases before it can proceed. Access to these databases is controlled by two separate threads B, C. These two threads have a message-processing loop; anybody needing their use posts a message into their message queue. Thread A initializes a semaphore S with init(S,-1). A then posts a data request, including a pointer to the semaphore S, to both B and C. Then A calls P(S), which blocks. The other two threads meanwhile take their time obtaining the information; when each thread finishes obtaining the information, it calls V(S) on the passed semaphore. Only after both threads have completed will the semaphore's value be positive and A be able to continue. A semaphore used in this way is called a "counting semaphore."

Apart from a counting semaphore we also have a "blocking semaphore". A blocking semaphore is a semaphore that is initialized to zero. This has the effect that any thread that does a P(S) will block until another thread does a V(S). This kind of construct is very useful when the order of execution among threads needs to be controlled.


The simplest kind of semaphore is the "binary semaphore", used to control access to a single resource, which is essentially the same as a mutex. A binary semaphore is always initialized with the value 1. When the resource is in use, the accessing thread calls P(S) to decrease this value to 0, and restores it to 1 with the V operation when the resource is ready to be freed. Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the concurrent use of un-shareable resources by pieces of computer code called critical sections. ...


See also

The cigarette smokers problem is a concurrency problem, originally described in 1971 by S. S. Patil. ... In computer science, the dining philosophers problem is an illustrative example of a common computing problem in concurrency. ... In computer science, the first and second readers-writers problems are examples of a common computing problem in concurrency. ... In computer science, the sleeping barber problem is a classic inter-process communication and synchronization problem between multiple operating system processes. ...

References

  1. ^ Kernel hacking howto on linuxgrill.com

External links


  Results from FactBites:
 
Semaphore (programming) Summary (2001 words)
A P operation on the semaphore grants access to a process, and decrements the value of the semaphore by 1; the V operation on a semaphore is used by a process to reset the semaphore (increment its value by 1) after it is done using the restricted resource.
Semaphores are also considered to be ill-advised in user-level programs even in uniprocessors because of this, and because they tend to slow things down due to busy waiting.
Semaphores are the classic solution to the dining philosophers problem, although they do not prevent all deadlocks.
Semaphore Programming Assignment (1076 words)
Your assignment is to write a multi-class multithreaded Java program that simulates the movement of the people in the building and their use of the elevator.
Your program will have an elevator class from which an elevator object containing the elevator thread is instantiated, and a person class from which person objects containing a person thread each are instantiated.
The input data to your Java program are the number of people in the building, the maximum person building wander time (napping time), the number of floors in the building, the simulation running time, and a flag for deterministic mode.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m