What is semaphore

Before  understanding semaphore we should first discuss the critical section.

critical section is a piece of code that can be executed by two or more process at a time. Because of the simultaneous access of code our data might get inconsistent. To avoid this inconsistency we use synchronization methods.

so semaphore is one of the synchronization technique. It is  a locking mechanism which is use to provide a lock for the access of critical section. If a process wants to access the critical section it has to acquire the lock first and free the lock once it has completed their work. When one process is already having the lock and other process try to acquire the lock then that process has to wait for the time till the lock is freed by previous process.

suppose we have total n number of same object and for that we have n number of lock. if a process try to acquire a lock and lock is available then the value of lock will be decreased by one or if lock is not available then that process has to wait till the time any lock is available. we can understand this by following example.

total number of objects = 3

total number of locks available =3

Process           Step                   Lock available                     Lock value        Status   

 P1                acquire                       Yes                                    2                Acquired             

 P2                acquire                       Yes                                    1                Acquired

 P3                acquire                       Yes                                    0                Acquired

 P4                acquire                       No                                     0                  Wait

 P2                release                       Yes                                    1                Released

 P4                acquire                      Yes                                     0                Acquired

Program to Solve Maze Problem

This is one of the important problem which is mostly asked in  technical interviews or technical tests
Lets understand the maze problem first then we will write a C program to solve the maze problem.
Maze is a matrix of N*N which is filled with 1 or 0.In Maze problem a rat starts from (0,0) and has to reach at (n-1,n-1) which is the exit point of maze.Rat can move up, down ,left , right if there is a way to go.
Let assume we have following 4*4 matrix.


                                     1  1   0   0
                                   0  1   0   0
                                   1  1   0   0
                                   1  1   1   1

Above is the given maze matrix filled 1 or 0 . 1 indicates the allowed  move and 0 indicates not allowed to move.Rat starts from (0,0) and checks the value of left,right,up and down one by one till its find the 1.Once it find the possible move it moves to that cell and go ahead one by one after checking the possible moves at each step.If at any step rat find that there is no possible move ahead and still it has not reached the exit point ,then it moves back one step and check the other alternatives and choose accordingly till its find the path to exit.
from the above maze we can see that first rat starts at (0,0) and then check for the right position which is 1.So it moves to that cell and check the right cell which is zero and then checks the down cell which is 1.So it moves to the down cell and continue till it reach the exit point. So path from starting point to exit will be

                           (0,0) -> (0,1) -> (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3)

As we have understand the maze problem.Lets Write the C Program to solve this.


#include<stdio.h>
#include<conio.h>
#define V 4                          /*size of matrix */
int isSafe(int x,int y,int G[V][V],int Sol[V][V])         /* to check the safe move */
{
if(x>=0 && x<V && y>=0&&y<V && G[x][y]==1 && !Sol[x][y])
return 1;
else
return 0;
}
int MazeRecur(int G[V][V], int Sol[V][V], int x,int y)   /* checking for the path to our exit point */
{
if(x==V-1 &&y==V-1)
      {
Sol[x][y]=1;
return 1;
      }
       if(isSafe(x,y,G,Sol)==1)
       {  Sol[x][y]=1;
 if(MazeRecur(G,Sol,x,y+1)==1)                                    /* right move possible */
return 1;
 if(MazeRecur(G,Sol,x+1,y)==1)                                   /* down move possible */
return 1;
 if(MazeRecur(G,Sol,x,y-1)==1)                                    /* left move possible  */
return 1;
 if(MazeRecur(G,Sol,x-1,y)==1)                                   /* up move possible   */
return 1;
 Sol[x][y]=0;
       }
       return 0;
}
int main()
{
clrscr();
int G[V][V]={{1,1,0,0},                                                /* initialize the maze matrix */
    {0,1,0,0},
    {1,1,0,0},
    {1,1,1,1}};
int sol[V][V] = {0};
if(MazeRecur(G,sol,0,0)==1)
{
printf("Solution Exists\n");
for(int i=0; i<V;i++)
 {
  for(int j=0; j<V; j++)
    printf("%d\t",sol[i][j]);
  printf("\n");
 }
}
else
   printf("No Solution Exists");
getch();
return 0;
}

If you have any queries feel free to ask me.............  :)