6. What are Semaphores, RTOS Semaphores, MQX Semaphores

I would try to explain

what are semaphores?
What you need to take care if you want to implement your own semaphores?
Though I have label this post as MQX. But description is more on general term.


Semaphores

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

Is their any alternative to Semaphores?
Yes there are few solutions know as n process synchronize(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 Semaphore?
They are synchronization tool. In a very abstract terms, 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++;
}

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) Example of using semaphores for Synchronization
Lets say, 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 Sem=0;

In process P1
{
   // Execute what ever you want to do
   // before executing P2
   S1;
   signal(Sem);

}

in process P2
{
     wait(Sem);
     S2;
}


Why not use Global Variables instead of semaphores to synchronize ?

Now if world was perfect, global variables can be used. You can write above mentioned functions in your C code to create semaphores. But(as its case with World anyway), 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

How OS/RTOS implement Semaphores.What is spin lock?

The very basic implementation which I showed above has one problem they also have busy waiting. This is not at very appreciated in real time environments where wasting CPU is crime, equivalent to murdering someone (i.e murdering in civilized society). These type of semaphores are called the spin-lock semaphores.

But spin-lock semaphores 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 functions. When ever 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 simply call wakeup() for that process.
You also have to make sure that you maintain queue for all blocked process.

 There is one more important point.  On wakeup() you are simply putting it on ready queue. Its up to CPU scheduler scheduling policy when that process will be executed.


Critical Section Problem of Semaphore implementation.
The 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 uni-processor environment, we can simply inhibit (disable) interrupts during the time that wait and signal operations are executing. This works very well in uni processor environment. Because, once interrupts are inhibited, there is no one, I mean literally no one (even 'the one' from matrix) can ask CPU to execute some thing else.

2)In multiprocessor env inhibiting of interrupts does not work. Instructions from different processors many be interleaved in some arbitrary way. We can  not employ any simple software solutions (not discussed here) for critical section problem.

I again emphasize what I said earlier, that MQX gives you two type of implementation one is called light weight implementation. When you call light weight implementation, MQX RTOS forgets about complexity of multiprocessor environment.