A short note on semaphores

As I mentioned in class, semaphores are a general technique that can be used to implement locks. They were originally proposed by Dijkstra as, essentially, a disciplined method for changing the value of an integer in which some operations block based on the state of the integer. One of the more mystifying aspects of semaphores though (at least, to native English speakers) is the terminology that accompanies them. The basic primitives are:

• s represents a semaphore value.
• P(s): If s is greater than zero, this operation will decrement the semaphore by one. If s is zero, it will block until the semaphore has a positive, non-zero value.
• V(s): If another thread is blocked on the semaphore, unblock that thread. Otherwise, increment s.

So, why P and V? The original papers on semaphores were written by Dijkstra in his native Dutch, so he chose terminology in that language instead of English. His chosen terms were Prolagen and Verhogen. Prolagen isn't a proper Dutch word, but a term derived from Probeer te verlagen, or "to try and decrease". Verhogen comes from the word meaning "to increase", or "to raise". So, the operations on semaphores are named based on their origin in Dijkstra's native language. Intersting, eh?

If you have the time or interest, I would highly recommend browsing the archive of Dijkstra's papers found here. In the world of concurrency and parallelism, Dijkstra is one of the founding fathers at the level, in my opinion (and that of many others), of where von Neumann and Turing stand for the fundamental theories of computation.

-matt / 10.24.08