Synchronization(using Semaphores)-Producer Consumer

/*......
Before moving to the algorithm...I am writing the structutre of the program
we have created two threads p and c

pthread_create(&c,NULL,&consume,NULL); 
pthread_create(&p,NULL,&produce,NULL);
first argument is the address of the variable holding the address of the thread
second argument is priority of the thread which we have set to 0
third argument is the function name from where thread starts its execution
fourth argument is the parameter passed to the function...here we have no parameter hence we have written as NULL

NOW thread c will take handling consumer process and thread p will handle producer process


Consumer-Producer Problem
Here we have taken the bounded buffer of size 5
Three semaphores have been taken-:

mutex-Initial value is taken as 1,this has been used to implement lock ie. while producer is in 
making changes to buffer consumer cannot do and vice-versa

empty-Initial value is size of the buffer since in the beginning buffer will be empty hence number of empty slots will also be equal to buffer

 full-Initial value is 0 since at the beginning number of the filled slots are 0 

...........*/


#include<stdio.h>
#include<pthread.h>
#include<semaphore.h>
pthread_t p;
pthread_t c;
sem_t mutex,full,empty;
int bufferSize=5;
int buffer[5];
int nextProduce,nextConsume;
int in,out;

void *produce(void *p)
{

int i=0;
while(i<=10)
{
sem_wait(&empty);//if buffer is full number of empty slots will be 0 hence empty=0 and thread has to wait here untill consumer consumes some of the product
sem_wait(&mutex);//it locks the consumer function so that while p is in its critical section c cannot move to its critical section
nextProduce=(int)rand();
buffer[in]=nextProduce;
printf("\nProduced %d at %d",nextProduce,in);
in=((in+1)%bufferSize);
sem_post(&mutex);//releasing the lock
sem_post(&full);//increasing the value of the full since number of filled slots will increase
i++;
}//end of while
}//end of produce

void *consume(void *p)
{int i=0;
while(i<=10)
{

sem_wait(&full);
sem_wait(&mutex);
nextConsume=buffer[out];
printf("\nConsume %d at %d",nextConsume,out);
out=((out+1)%bufferSize);
sem_post(&mutex);
sem_post(&empty);
i++;
}//end of while
}//end of consume

int main()
{
sem_init(&mutex,0,1);
sem_init(&full,0,0);
sem_init(&empty,0,bufferSize);
pthread_create(&c,NULL,&consume,NULL);
pthread_create(&p,NULL,&produce,NULL);
pthread_join(p,NULL);
pthread_join(c,NULL);
}


For compilation gcc -pthread xyz.c

Bankers Algorithm(Deadlock Avoidance)

Bankers algorithm is Deadlock avoidance algorithm which capable of dealing with more than two or n process resource allocation.Everytime there is demand by the process for allocation algorithm is invoked by OS.
DATA STRUCTURES USED-:
Available-Vector to store resources available with the system
Max[i][j]-Max demand made by the ith process for jth resource
Allocated[i][j]-Number of instances of jth resources has been allocated to ith process
Need[][]-Max-Allocated

ALGO-:

• The process works on lines of bank management.Whenever there is the demand of resources allocation which cannot be completed by OS, process is asked to wait until some finished process release its resources.
• Released resources are added to Available list
• This Available list is compared with Need list of next process
• If Need is greater than Available, process is put on hold and same condition is checked for next process
• If Need is less than or Equal to Available then the Allocated resources are added to Available(since if condition is true process can successfully finish itself and can release its resources)
• All above process are repeated until all process have been completed or there is no process left for which Need <=Available. In the latter case system is not in SAFE state and in former safe sequence can be generated

#include<stdio.h>

#include<conio.h>
#include<stdlib.h>

int available[1][5];
int max[5][5];
int allocated[5][5];
int need[5][5];
int p[5]={0};
int n=5;//number of process
int m=3;
void input()
{
     int i,j;
     puts("Enter the Allocation Matrix");
     for(i=0;i<n;i++)
     {
        printf("P%d ",i);          
        for(j=0;j<m;j++)
        {
        scanf("%d",&allocated[i][j]);
     }//inner for
     printf("\n");
 }//outer for


 puts("Enter the MAX Matrix");
     for(i=0;i<n;i++)
     {
        printf("P%d ",i);          
        for(j=0;j<m;j++)
        {
        scanf("%d",&max[i][j]);
     }//inner for
     printf("\n");
 }//outer for

 puts("Enter the Available Matrix");
     for(i=0;i<m;i++)
     {
       scanf("%d",&available[0][i]);            
}


}//function end
void calc_need()
{
      int i,j;
      puts("NEED matrix");
     for(i=0;i<n;i++)
     {
             
        for(j=0;j<m;j++)
        {
        need[i][j]=max[i][j]-allocated[i][j];
         printf("%d ",need[i][j]);  
         }//inner for
     printf("\n");
     }//outer for
   
 }//end of calc_need
 int less_than_or_equal(int i)//to check if for process i need <=Available
 {
      int j;
      for(j=0;j<m;j++)
      {
                      if(need[i][j]<=available[0][j])
                      continue;
                      else
                      return 0;
      }//end of for
                      return 1;
   
  }
 void  increase_available(i)
  {
                     
      int j;
      for(j=0;j<m;j++)
      {
      available[0][j]=available[0][j]+allocated[i][j];  
                      }
}

void check()
{
     int j;
      for(j=0;j<n;j++)
      {
                      printf("%d",p[j]);
 }
}
main()
{
   
      int i;
      int f=0;
      input();//to take inputs for Allocated Max and Available
      calc_need();
      while(1)
      {
             if(f==n)
             break;
             f=0;
             for(i=0;i<n;i++)
             {
                           
                           
                              if((p[i]==0)&&(less_than_or_equal(i)))
                              {
                              increase_available(i);
                              p[i]=1;
                              printf("P%d ",i);
                              continue;
                              }
                              else
                              {
                                  f=f+1;
                                  continue;
                              }
           
             }//end of for
   
      }//end of while
      getch();
      check();
      getch();
}//end of main


OUTPUT
Safe Sequence
<P1,P3,P4,P0,P2>

Optimal Page Replacement

Since optimal page replacement is not used practically and is implement for comparing algos hence it doesn't need a dynamic queue or link list and hence here it has been implemented using arrays

let 70120304230321201701 be the sequence string
number of pages are 20
if frame size taken 3 number of page faults will be 9

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

int frame[100];//frame
int a[100];//to store pages
int Frame_size;//to store frame size;
int n;//to store number of pages to be input by user
int j=0;
int nulp()//function to return the index number of the page which will not be used for longest period ie..which is to removed from the frame
{
    int i=0;
    int jj=j+1;
    int max=-1;
    int pos;
  while(1)
  {
    while(1)
    {
      if(frame[i]==a[jj])
      {
        if(max<(jj-j))
        {
        max=jj-j;
        pos=i;
        }
        jj=j+1;  
        i++;
        break;    
      }
      else  
      {
             
               jj++;
               if(jj==n)
               {
               max=jj-n;
               pos=i;
               return i;
               jj=j+1;
               i++;
               break;
               }
      }
   
    }
    if(i==Frame_size)
      break;      
  }
  return pos;
}

int ifexist(int i)
{
    int j1;
    for(j1=0;j1<Frame_size;j1++)
    {
                             if(frame[j1]==i)
                             return 1;
    }
    return 0;
}
main()
{
      puts("Enter the number of pages");
      scanf("%d",&n);
      puts("Enter  pages");
      int i=0;
      for(i=0;i<n;i++)
      scanf("%d",&a[i]);
      puts("Eneter the Frame size");
      scanf("%d",&Frame_size);
   
   
   
      int Fault=0;//counting the number of page faults occur
      int counter=0;//to make sure size of frame is equal to the Frame_size as entered
   
      frame[counter]=a[j];
      counter++;
      j++;
      Fault++;//we can be sure when first element will be entered it will be a fault
      while(j<n)
      {
             if((counter<Frame_size)&&(!ifexist(a[j])))
             {
                frame[counter]=a[j];
                j++;
                counter++;
                Fault++;                          
             }
             if(ifexist(a[j]))
             j++;
             if((counter==Frame_size)&&(!ifexist(a[j])))
             {
             
               int i=nulp();//returns the index number of element which will not be utilized for longest period of time or page which has to be removed                                      
               frame[i]=a[j];
               j++;
               Fault++;
                                 
             }            
      }
      printf("%d",Fault);
      getch();    
}

Producing a mirror tree of given tree

Given Tree
                a                              
             /    \
            b      c
          /  \
         d    e
Mirror Tree

                a
             /    \
            c      b
                  /  \  
                e    d    

ALGO

Here we have simply traversed the tree in postfix manner and instead of printing the node we have switched it right child with left and vice versa
Per-order is used because root's child will be  switched at last




#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<time.h>//for producing random tree

struct node
{int n;
struct node *left;
struct node *right;
};
int c=0;
 create(int d,struct node**m)
{
            struct node *q=*m;
       if(*m==NULL)
       {
       struct node *r=(struct node*)malloc(sizeof(struct node));

        r->n=d;
        r->left=NULL;
        r->right=NULL;
        *m=r;
       
        }
       
       else
           {
               if(q->n>d)
           create(d,&(q->left));            
           if(q->n<d)
           create(d,&(q->right));            
                                         
                         
                          }
                         
           }
        display(struct node *root)
       {
           
            if(root==NULL)
            return;
           
            else
            {
               
            display(root->left);
            display(root->right);
            printf("%d\n",(root->n));
            }
       
        }
       
        conversion(struct node *m)//code for creating mirror tree of the given tree
        {
                          struct node *n=m;
                          if(n==NULL)
                          return;
                          conversion(n->left);
                          conversion(n->right);
                          struct node *t=n->left;
                          n->left=n->right;
                          n->right=t;
                          
                          }
        
       
     
main()
{
      struct node *root=NULL;
      srand(time(NULL));
      int i;
     for(i=0;i<=5;i++)
      create((rand()%20),&root);
     
      display(root);//before conversion
      conversion(root);
      display(root);//after conversion
      getch();
     
    }
       

FIFO Page Replacement

//ALL there are three possibileties 
//first-: All frames are occupied and fault occurs, in such case we need to first deque and then enqueue the required page and variable counting the fault will be incremented
//second-: Some Frame is empty and fault occurs, in such we will enqueue the required page and increment the fault variable
//third-: if fault does not occur,in such case we will  move to next page 

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct que
{
       int data;
       struct que *next;
       };
     
        void enque(struct que **q,int a)
       {
                      struct que *t,*r;
                   
                      if(*q==NULL)
                      {        
                        t=(struct que*)malloc(sizeof(struct que));
                        t->data=a;
                        t->next=NULL;
                        *q=t;        
                               
                                  }
                                  else
                                  {
                                      t=*q;
                                      while(t->next!=NULL)
                                      t=t->next;
                                      r=(struct que*)malloc(sizeof(struct que));
                                      r->data=a;
                                      r->next=NULL;
                                      t->next=r;
                                      }
                     
                     
                             }
                                             
                     
     
 int deque(struct que **q)
{
     if(*q==NULL)
     {
     printf("que is underflow");
     return -999;
     }
     struct que *r;
     r=*q;
     int x;
     x=r->data;
     *q=r->next;
     free(r);
     return x;
   
 }
 int ifexist(struct que **q,int i)
 {
     struct que *t,*r;
     t=*q;
                                      while(t!=NULL)
                                      {
                                     
                                       if(t->data==i)
                                       return 1;                
                                      t=t->next;
                                      }
                                      return 0;
 }
main()
{
     int a[100];//page sequence;
     int n;
     int Frame_size;
     puts("Eneter the number of pages to be entered");//number of pages
     scanf("%d",&n);
     int i=0;
     for(i=0;i<n;i++)
     scanf("%d",&a[i]);
     puts("\nEnter the size of Frame");//number of frames
     scanf("%d",&Frame_size);
     struct que *p;
     p=NULL;
     int j=0;
     int counter=0;//to count the number of frames
     enque(&p,a[j]);//first element is to insert without any condition
     j=j+1;
     int fault=1;//first element will always produce fault
     counter=counter+1;
     while(j<n)
     {
      if((counter==Frame_size)&&(!ifexist(&p,a[j])))//if all frames are filled and fault occurs
      {
      deque(&p);
      enque(&p,a[j]);
                     j++;
                     fault=fault+1;
   
                                       
     }
                                       
     if(ifexist(&p,a[j]))//if no fault occurs
     j++;
   
     if((counter!=Frame_size)&&(!ifexist(&p,a[j])))//if all frame not filled and fault occurs
     {
     enque(&p,a[j]);
     j++;
     fault=fault+1;
     counter=counter+1;
     }                                  
                                       
                                         }                                                    
      printf("\nNumber of Page fault occurs %d",fault);
      getch();
   
   
   
      }

DFS Search

//Here we have used the Adjacnet Matrix method hence time complexity for the DFS is O(V^2)
//Since whole matrix of V^2 has to be searched for the adjacnet nodes
//If Adjacent list would have been used in that case complexiy would have been 0(V+E) since only only V vertices had been passed and E edges would have searched for
//Not an optimal solution...
//But saves lots of space
//if A[u][v]=1 it implies that there exist a path from u to v hence v is adjacent to u

DFS:A>B>D>F>C>G>E

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int V;//Number of vertices

int E;//number of Edges..not used since adjacent matrix  representation has been used

int A[10][10];//Adjacent matrix

int visited[10]={0,0,0,0,0,0,0,0,0,0};//visited array...initially all are set to zero since no node has been visited

void dfs(int u)
{
        visited[u]=1;//whatever node is passed to node is consider to be visited hence we make it visited
        printf("%c\t",(65+u));//printing the node visited..and nodes are in character form A,B,C..
        int i;
        for( i=0;i<V;i++)
        if(!visited[i]&&A[u][i])//if node is not visited and it is adjacent to the node passed as argument to the function then only we will visit it..the first adjacent node will be visited and the remaing adjacent node will be visited recursively
        {    
        dfs(i);
        }
}

main()
       {
           
             puts("Enter the number of Vertices and Graph");
             scanf("%d",&(V));
             scanf("%d",&(E));
           
           
             int i;
             int j;
             puts("Enter the Adjacent Matrix Row wise");
             for(i=0;i<V;i++)
             {
                for(j=0;j<V;j++)
                scanf("%d",&(A[i][j]));
             }                                
              i=0,j=0;        
              puts("Adjacent Matrix");        
             for(i=0;i<V;i++)
             {
                                 
                for(j=0;j<V;j++)
                printf("%d\t",(A[i][j]));
                printf("\n");
                   
             }
         
             dfs(0);//Here since graph is single componet we can take only one vertex and start dfs else in separate component then we have to do dfs for all the nodes

 getch();          
}

Sjf preemptive...with idle time

//first all the processes are taken in the array of structure  P[]
//THEN a[] contains the burst time of all the process in order of their arival
//min function calculates the minimum value in the array a[], beteen the  index number 0 to j where j is number of process which have arived
//maximum valu of j can be equal to number of process
//if the a[i] is 0 means burst time remain is 0 and hence that procee need not be processed hence we will ignore it
// if a[i] is 0 till i to j and j is not equal to the number of process then cpu is idle all the arrived porcess have been finished and waiting for new process
// if a[i] is 0 for all the process and j=number of process then all process have been finished
// Moment burst time of the process becomes 0 at that time of interval value of cl(clock) become completition time of that process



#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
struct process
{
       int at;
       int bt;
       int rt;
       int  c;//process completiotion time
       int wt;
       int trt;
       };
     
     
       int min(int *a,int j)
       {
           int min;
        int i=0;
        int flag=0;
        int pos;
        for(i=0;i<=j;i++)
        {
        if(a[i]==0)
        continue;
        min=a[i];
        pos=i;
        flag=1;
        break;
        }
        if(flag==0 &&j!=3)
        return -2;
        else if(flag==0)
        return -1;
        else
        for(i=0;i<=j;i++)
        {
        if(a[i]==0)
        continue;
        if(a[i]<min)
        {
        min=a[i];
        pos=i;
        }
       }
       return pos;
       }
void display(struct process *p)
{ 
    int i=1;
    for(i=0;i<4;i++)
    {
        printf("Arrival time%d  ",p[i].at);
        printf("Burst Time%d  ",p[i].bt);
        printf("comlete Time%d  ",p[i].c);
        printf("waiting Time%d  ",(p[i].c-p[i].at-p[i].bt));
        printf("\n\n");
}
      
  
}   
main()
{
      struct process p[100];
      int b[100];
      int a[4];//since number of process taken are four
      puts("Enetr the process arival time and burst time");
      int i=0;
      int j=0;
      while(1)
      {
    
      scanf("%d",&(p[i].at));
      scanf("%d",&(p[i].bt));
      a[j]=p[i].bt;
      j++;
      i++;
      if(i==4)
      break;
      }
    
      //array a[] contains the burst time of the process
    
      //array p[] contains the proceess
      
      int x=0;
      int y=0;
      int m;
       j=0;
       i=0;
       int cl=0;
       int pid=2;
       while(cl<p[0].at)
       {
       printf("idle  %d---",cl);
       cl++;
       printf("%d\n",cl);
    }
      while(x!=-1)
      {
        a[x]=a[x]-1;
        cl++;
        if(a[x]==0)
        p[x].c=cl;
      
        if(cl<p[i+1].at)
    {  
        x=min(a,j);
        if(x==-2)
        {
                 while(cl<p[i+1].at)
                 {
                 printf("idle  %d---",cl);
       cl++;
       printf("%d\n",cl);
                 }
               
         }
      
    }
        if(cl==p[i+1].at)
        {j++;
        x=min(a,j);
        i++;
         }
         if(i==4)
         x=min(a,3);
  
      
}  
      
    
    
    

      printf("\n\n");
     display(p);
      getch();
      }