Semaphores

One of the most significant advantage of having a machine doing your work for you is it's speed and blind trust with which it will obey your commands.

For most of us, the productivity of our computers is not limited by their ability but by our imagination. Talking loosely about myself, no matter how hard we try, the best we get out of a computer is hardly any feet for that machine. Computers are meant to work hard and fast. Our job is to provide them with challenges that are otherwise too long and elaborate for our liking or capability. One category of such challenges is multitasking. 

A computer (something with a single processor, and memory and other things.) can't perform two tasks at a time. Don't be smug, us humans can't either. In fact multitasking in computing and in the real world is an illusion. It's nothing but a combination of speed and flexibility to seamlessly switch between multiple tasks. And one thing all jugglers (the one's at the circus, the one's with multiple love interests and our computers) need the most is Synchronization. Synchronization as we all know is nothing but an agreement of faculties to coexist and function concurrently. The same things happens in a computer, multiple tasks which sometimes belong to the same process (threads) run concurrently and share the resources of the computer (like processor and memory) to achieve individual completion. As such this sharing of resource can often turn into a competition (not literally) which can take a violent turn forcing certain tasks to freeze (deadlock) and in effect hinder the progress of others as well. It's a whole story in its self.

So the million byte question is, how to make these threads coordinate with one another so that sharing is done synchronously. A specific answer to this very general question is Semaphores. Semaphores are a way of communicating using a very primitive set of alphabet. A common example of a semaphore is the traffic head light. It has only three colours which are used to communicate access to roads to the vehicles. 

In terms of computers (mainly operating systems) a semaphore can be thought of as a variable associated with a resource. The value of this variable determines whether a process can access that resource or not. The value of a semaphore is integer in nature. This value is never used directly by the programmer or the program. We can only increment it or decrement it, but never are we allowed access to it's value in calculations. What we can do is perform checks on this value like in case of any other variable. Corresponding to this, there are a couple of actions that a thread can do with respect to a resource semaphore. These are:

1. Ask for access to a resource. This is generally called as wait.
2. Relinquish control of a resource. This is commonly known as signal.

The wait action can result in either the grant of the access or a state of wait for the thread for some other thread currently using the resource to pass it over. The wait function decreases the value of the semaphore by one. And if after decrementing the value, the semaphore is still a positive quantity, the access is granted to that thread. A useful observation about this is that if the initial value of the semaphore is 10, then that means that 10 threads can call the function wait on this semaphore and all 10 will be granted access to that resource. This happens when there are 10 shareable copies of a resource. So in a way, the initial value of the semaphore indicates the number of available copies of a resource. If after decrementing the value, the semaphore becomes negative then that thread is forced to wait in queue for some other process to relinquish a copy of that resource. This means that the magnitude of the negative value of a semaphore can tell us the number of threads that are waiting for that resource at a given time. But of course as I said earlier, we are not allowed to directly access the value of the semaphore. But no one can stop us from making a mental note of this value (and explicitly count the number of increments and decrements of a semaphore to keep track of it's value since initialization). 

The signal function either increments the value of the semaphore by one (increments and decrements are mostly by one in case of semaphores) or it simply allows a waiting thread to take up it's copy of the resource. The former happens when there are no thread waiting for that resource and later is simply a result of a thread leaving a resource and then incrementing it's value followed by another waiting process to take up that resource and consequently decrementing the value again. 

Using only these two operations, semaphores have been used richly in writing many embedded softwares and softwares requiring heavy amounts of parallelism inside them selves.  

I would really like to one day find some time and write a proper beginners' tutorial on this. For now, I'd recommend the following book: The little book of Semaphores. Go google it. It's awesome.