Semaphores

Semaphores

When They are used
Semaphores are used for two purposes
1) Process Synchronization
2) Critical Section problem

Is there any alternative to Semaphores
Yes there are few solutions know as n process synchronization(software solutions) and Hardware solutions. Hardware solutions becomes complicated when number of process increases and secondly in all these you have busy waiting (it means you are eating CPU cycles when waiting and no other productive work can be done during this). So practically they are never used

What are they
They are synchronization tool. In a very abstract term semaphore is a global variables, which apart form initialization can be modified by only two operations wait() and signal().

Suppose S is semaphore
where wait is as simple as
wait(s)
{
while(s<=0)
; //do no operation
s--;
}

signal(S)
{
S++;
}

Why not Global Variables
Now if this was the only criteria you can simply use global variables and can write above mentioned functions in your C code to create semaphores. But its not that simple in addition to above things we need to ensure
1) Modification of S value must be done exclusively.
2) In addition checking of while(s<=0) in wait and possible modification S--, should also be done without interruption
3) Above implementation is having busy wait too

Example of Usage

1) n process critical section problem
put every process code like this
do {
wait (mutex);
critical section;
signal(mutex);
reminder section;

}while(1);

2) Synchronization
we can also use this for synchronization. e.g two concurrent process P1 and P2 having statements S1 and S2. We want in any case S1 should execute first. this can be achieved easily by
initialize S=0;
in P1 in P2
S1; wait(S);
signal(s); S2;

Implementation

The very basic implementation which I showed above has one problem they also have busy waiting. This is not at very appreciated in multiprogramming environments where wasting CPU is crime equivalent to murdering someone. These type of semaphores are called the spinlock semaphores.

But these semaphore have advantage too. There is no context switch required when process wait on Semaphore. Hence if waiting time is minimal this approach is very helpful.

How to overcome busy waiting.
you can modify wait and signal. when every you have to wait instead of looping you can block the current process. Bock is very common system call present in every Operating system.
in signal you simple call wakeup() for that process.
You also have to make sure that you maintain queue for all blocked process (i think list of PCB will do it)
There is one more important point on wakeup you are simply putting it on ready queue of Short term (or CPU scheduler).. its up to CPU scheduler scheduling policy when that process will be executed.


Critical Section Problem of Semaphore implementation
This is critical aspect of semaphore implementation that they are executed atomically. We must guarantee that no two processes can execute wait and signal operations on the same semaphores at same time. This is called critical section problem and can be solved in 2 ways

1) In uniprocessor environment we can simply inhibit (disable) interrupts during the time that wait and signal operations are executing. This works very well in uniprocessor env because, once interrupts are inhibited, instructions from different processes can not be interleaved.

2)In multiprocessor env inhibiting of interrupts does not work. Instructions from different processes many be interleaved income arbitrary way. We can employ any software solutions (not discussed here) for critical section problem, where critical section consists of wait and signal procedures(remember there it was modification of files, global variable etc). It must be admitted here that we are still using buy wait here but at least that is only on wait and signal and not on full process.