Banker Algorithm

                              Banker Algorithm

The resource-allocation graph algorithm is suitable to a resource allocation system with single instances of each resource type. It is not suitable for multiple instance of each resource type. Banker’s algorithm is suitable to a resource allocation system with multiple instances of each resource type. The banker’s algorithm makes decisions on granting a resource based on whether or not granting the request will put the system into an unsafe state. Several data structures must be maintained to implement the banker’s algorithm. Let n be the number processes in the system and m be the number of resource types. We need the following data structures:
(1) Available (2) Max (3) Allocation (4) Need
1) Available: A vector of length m indicates the number of available resources of each type. If available [j] = k, there are k instances of resource type R available.
2)    Max: An n x m matrix defines the maximum demand of each process. If Max [i, j] = k, then process P. may request at most k instances of resource type R_r3)   Allocation: An n x m matrix defines the number of resources of each type currently allocated to each process. If allocation [i, j] = k, then P. is currently allocated k instances of resource type R
4)  Need: An n x m matrix indicates the remaining resource need of each process. If Need |i, j] = k, then process P. may need k more instances of resource type R, to complete its task. Need [i, j] – Allocation [i, j].
Safety algorithm: Safety algorithm is used to find the state of the system: That is, system may be safe state or unsafe state. Method for this is as follows:
1)   Let work and finish be vector of length m and n respectively. Initialize work = Available and Finish [i] = False for i = 1, 2, 3, 4, … n.
2)   Find an i such that both
a) Finish [i] = False b) Need fj] < work
If no such i exist, go to step 4.
3)    Work : = Work + Allocation i
Finish [i] = true to step 2
4)    If Finish [i] = true for all i, then the system is in a safe state. Resource-request algorithm: Let request, be the request vector for process P. If Request, fj] = k, then process P. wants k instances of resource type R.. When a request for resources is made by process P, the following actions are taken.
1)     If Request. < Need₍, then go to step 2. Otherwise, raise an eitor condition since the process has exceeded its maximum claim.
2)    If Request < Available, then go to step 3. Otherwise, P. must wait since the resources are not available.
3)        Available : = Available – Request.; Allocation : = Allocation + Request.; Need_; : = Need_t – Request.;
If the resulting resource allocation stale is safe, the transaction is completed and process P. is allocated its resources. If the new state is unsafe, then P. must wait to the Request, and the old resource allocation state is restored.

Coding

#include<stdio.h>
#include<stdlib.h>
struct bank
{
 int alloc[10];
 int max[10];
 int need[10];
 int c;
 }p[10];

 int av[10];
 int m,n;
 char res[5]={'D','E','B','A','S'};
 int safe[20];
 int grant[10];
 int g=0;


void read()
{
 printf("\nEnter the number of processes--");
 scanf("%d",&n);
 int i,j;
 printf("\nEnter the number of resorces--");
 scanf("%d",&m);
 for(i=0;i<n;i++)
 {
   p[i].c=0;
   printf("\n\nEnter the details of the process %d--\n",i+1);
   for(j=0;j<m;j++)
    {
      printf("\nEnter the instances of %c allocated--",res[j]);
      scanf("%d",&p[i].alloc[j]);
    }
   for(j=0;j<m;j++)
    {
      printf("\nEnter the instances of %c maximum",res[j]);
      scanf("%d",&p[i].max[j]);
      p[i].need[j]=p[i].max[j]-p[i].alloc[j];
    }

 }


 printf("\nEnter the total instances of available resources--\n");
 for(i=0;i<m;i++)
 {
 printf("%c\t",res[i]);
 scanf("%d",&av[i]);
 }
}


void display()
{
 int i,j;
 printf(" \t Alloc \t Max \t Need \t Avail \n");
 printf(" \t ");
 for(j=0;j<4;j++,printf("\t "))
 for(i=0;i<m;i++)
 printf("%c",res[j]);
 printf("\n");
 for(i=0;i<n;i++)
 {
   printf("P%d\t",i);
   for(j=0;j<m;j++)
   printf("%d",p[i].alloc[j]);
   printf("\t");
   for(j=0;j<m;j++)
   printf("%d",p[i].max[j]);
   printf("\t");
   //printf("dev test 1");
   for(j=0;j<m;j++)
   printf("%d",p[i].need[j]);
   printf("\t");
   if(i==0)
   {
   for(j=0;j<m;j++)
   printf("%d\t",av[j]);
   }
   printf("\n");
   }
   }


int over()
{
  int i,j;
  for(i=0;i<n;i++)
  for(j=0;j<m;j++)
  if(p[i].need[j]!=0)
  return 1;
  return 0;
  }
void banker()
{
  int i,j,k,l;
  for(i=0,l=0;;i++,l++,i=i%n)
  {
   if(over()==0)
    {
     printf("\nAll processes complete\n\nNo Deadlock");
     printf("\n\nSafe state<");
     for(i=0;i<g;i++)
     printf("P%d",safe[i]);
     printf(">");
     break;
  }
  //printf("debasis");
  else
  {
    if(p[i].c==0)
    {
      for(j=0;j<m;j++)
      if(p[i].need[j]>av[j])
      break;
      if(j==m)
      {
        safe[g]=i;
        g++;
        p[i].c=1;
        for(j=0;j<m;j++)
         {
           av[j]=av[j]-p[i].need[j];
           p[i].need[j]=0;
           p[i].alloc[j]=p[i].max[j];
         }
        printf("\n\nProcess P%d is executing---\n\n",i);
        display();
        for(j=0;j<m;j++)
        {
         av[j]=av[j]+p[i].alloc[j];
         p[i].alloc[j]=0;
         p[i].max[j]=0;
        }
        printf("\n\nProcess P%d is completed---\n\n",i);
        display();
        }
 }
 }
 if(l==25)
 {
  printf("---Deadlock---");
  break;
  }
  }
  }


void req()
{
  int i,j,k=0;
  printf("\nEnter the process number--");
  scanf("%d",&i);
  for(j=0;j<m;j++)
  {
   printf("\nEnter the number of instances of resource %c--",res[j]);
   scanf("%d",&grant[j]);
  }
 for(j=0;j<m;j++)
 if(p[i].need[j]<grant[j])
 k=1;
 for(j=0;j<m;j++)
 if(av[j]<grant[j])
 k=2;
 if(k==1)
 {
  printf("Need is less than request cannt be allocated--");
  }
 if(k==2)
 {
  printf("Available is less than reuest cannot be allocated");
 }
 if(k==0)
 {
  for(j=0;j<m;j++)
  {
   p[i].alloc[j]+=grant[j];
   p[i].need[j]-=grant[j];
   av[j]-=grant[j];
   }
   }
   banker();
 }

  main()
  {
   int ch;
   do
   {
    printf("\n\nDEVS TEST BANKERS ALGORITHM");
    printf("\n1.Read devs input data file \n2.Display devs Input data file\n3.Generate devs Safe sequence\n4.Request for resource\n5.Exit\nEnter you choice dev :-)");
    scanf("%d",&ch);
    switch(ch)
    {
     case 1:read();break;
     case 2:display();break;
     case 3:banker();break;
     case 4:req();break;
     case 5:break;
    }
  }while(ch!=5);
 }

Graph Coloring Technique

   GRAPH COLORING TECHNIQUE

DEFINATION:-

A coloring of a graph means assigning of a color to each vertex of the graph so that no two adjacent vertices are given the same color.In order to accomplish this we need the minimum number of colors to color the adjacent vertices which is called as the Chromatic Number of the graph.

PROCEDURE:-

Lets consider a un-directed graph G having V number of vertices and E number of  edges.

--> Enter the number of vertices of the graph.

--> Create an adjacency matrix of the above un-directed graph representing the             connected adjacent vertices.

  

--> Assign  Color 1 the nth vertices.

--> Check whether nth vertex is connected to any of previous (n-1) vertices 
      using  backtracking.

-->If connected then assign a color x[i]+1 where x[i] is the color of i th vertex          that is connected with nth vertex.

 SOURCE CODE USING C :-

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

int col[100];
int adj[100][100];

void chkcolour(int v)
{
        int i;
        col[v]=1;
        for(i=0;i<v;i++)
        {
                if(adj[v][i]!=0 && col[v]==col[i])
                {
                        col[v]=col[i]+1;
                }
        }
}
void print_color(int v)
{
        int i;
        printf(" Printing the vertex colours:\n");
        for(i=0;i<v;i++)
        {
                 printf("Nodevertex-->[%d] has color --> :%d\n",i+1,col[i]);
        }

}

int main()
{
        int i,j,v;
        printf("enter the no of vertices:\n");
        scanf("%d",&v);
       printf("Start entering the values for adjacency matrix:\n");
        printf("________________________________________________\n");
        for(i=0;i<v;i++)
        {
                for(j=0;j<v;j++)
                {
                        scanf("%d",&adj[i][j]);
                }
        }

        printf("_______________________________\n");

        printf("The entered adjacency matrix is:\n ");
        for(i=0;i<v;i++)
        {
                for(j=0;j<v;j++)
                {
                        printf("%d",adj[i][j]);
                }
                printf("\n");
        }
        for(i=0;i<v;i++)
        {
                chkcolour(i);
        }
        chkcolour(v);
        printf("_______________________________\n");
        print_color(v);
        printf("_______________________________\n");


        return 0;
}



OUTPUT:

enter the no of vertices:
7
Start entering the values for adjacency matrix:
________________________________________________
0 1 1 0 1 1 1
1 0 1 0 0 0 0
1 1 0 1 1 0 0
0 0 1 0 1 1 0
1 0 1 1 0 1 0 
1 0 0 1 1 0 1
1 0 0 0 0 1 0
_______________________________
The entered adjacency matrix is:
 0110111
1010000
1101100
0010110
1011010
1001101
1000010
_______________________________
 Printing the vertex colours:
Nodevertex-->[1] has color --> :1
Nodevertex-->[2] has color --> :2
Nodevertex-->[3] has color --> :3
Nodevertex-->[4] has color --> :1
Nodevertex-->[5] has color --> :2
Nodevertex-->[6] has color --> :3
Nodevertex-->[7] has color --> :2

_______________________________

**********************************************************************************

Computational Geometry Problem To Find Out The Closest Set Of Points.

Closest Set Of Points Promblem

The closest pair of points problem is a problem of computational geometry promblem: given n points in metric space, find a pair of points with the smallest distance between them. 

suppose we are given an array of n points in the plane, and the problem is to find out the closest pair of points in the array. Recall the following formula for distance between two points p and q.

This problem arises in a number of applications. For example, in air-traffic control, you may want to monitor planes that come too close together, since this may indicate a possible collision so we need to track out the closest pair between them.

we know that the closest pair of points can be computed in O (n²) time by performing a brute-force approach. To do that, one could compute the distances between all the n(n − 1) / 2 pairs of points, then pick the pair with the smallest distance, as illustrated below.

minDist = infinity
for i = 1 to length(P) - 1
 for j = i + 1 to length(P)
  let p = P[i], q = P[j]
  if dist(p, q) < minDist:
   minDist = dist(p, q)
   closestPair = (p, q)
return closestPair

Although we can design it in various number of ways here is one of the possible ways where time complexity is O(n x (Logn)^2)

process:-

Input: An array of n points P[]
Output: The smallest distance between two points in the given array.

1) Find the middle point in the sorted array.

2) Divide the given array in two halves. The first subarray contains points from arr[0] to arr[n/2]. The second subarray contains points from arr[n/2+1] to arr[n-1].

3) Recursively find the smallest distances in both subarrays. Let the distances be dl and dr. Find the minimum of dl and dr. Let the minimum be d.

4) From above 3 steps, we have an upper bound d of minimum distance. Now we need to consider the pairs such that one point in pair is from left half and other is from right half. Consider the vertical line passing through passing through arr[n/2] and find all points whose x coordinate is closer than d to the middle vertical line. Build an array strip[] of all such points.

5) Sort the array strip[] according to y coordinates. This step is O(nLogn). It can be optimized to O(n) by recursively sorting and merging.

6) Find the smallest distance in S. 

c code to implement the closest set of points:-

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

typedef struct

{

int x,y;

}point;

int main()

{

point *p;

int i,j,**d,n,min,s,t;

printf("\n Enter the no of points::\n");

scanf("%d",&n);

d=(int **)malloc(n*sizeof(int *));

        for(i=0;i<n;i++)

        {

                d[i]=(int*)malloc(n*sizeof(int));

        }

p=(point*)malloc(n*sizeof(point));

printf("\n enter %d no of (x,y) co-ordinate points \n ",n);

for(i=0;i<n;i++)

{

scanf("%d %d",&p[i].x,&p[i].y);

}

printf("the distance matrix is:\n");

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

d[i][j]=sqrt(pow((p[i].x-p[j].x),2)+pow((p[i].y-p[j].y),2));

printf(" \t %d",d[i][j]);

 

}

printf("\n");

}

min=9999;

for(i=0;i<n;i++)

        {

                for(j=0;j<n;j++)

                {

                        if(i!=j)

{

if(min>d[i][j])

{

min=d[i][j];

s=i;

t=j;

}

}

                }

        }

 

printf("\n FROM  %d   to  %d  is the minimum distance =  %d ",s+1,t+1,min);

}

*********************************************************************************************************************

ieee representation of floating point numbers

IEEE REPRESENTATION OF FLOATING POINT NUMBER

An IEEE-754 float (4 bytes) or double (8 bytes) has three components (there is also an analogous 96-bit extended-precision format under IEEE-854):

-> a sign bit telling whether the number is positive or negative, 

->an exponent giving its order of magnitude,

->an mantissa specifying the actual digits of the number. 

Using single-precision floats(32 bit) as an example, here is the bit layout:-

we have to represent it in form of ->1.M *2^(+/-E)

where:-

 ->M is the mantissa which is to be represented in 23 bit for single precision number.

->E is the exponent  which is to be represented in 8 bit for single precision number.

eg 1:

now suppose the floating point no: is 11.27

->signbit in 1 bit is: 1

->mantissa in 23 bit is: :0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 1 1 1 0 1 0 1 1 

->exponent is 8 bit: 10000010

eg 2:

now suppose the floating point no: is 157.38
->signbit in 1 bit is: 1

->mantissa in 23 bit is: :0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 

->exponent is 8 bit: 10000110

C CODE FOR IEEE REPRESENTATION OF FLOATING POINT NUMBER

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

static int r[23],mant[24];

int dec2bin(int n,int *arr)

{

int i,p;

p=n;

for(i=0;i<23;i++)

arr[i]=0;

i=22;

do

{

arr[i]=n%2;

n=n/2;

i--;

}

while(n!=0);

if(p<0)

{

printf("****negative number****\n");

printf("do enter a positive number\n");

}

else

{

printf("the binary equivalent of %d is:",p);

for(i=0;i<23;i++)

printf("%d",arr[i]);

}

printf("\n");

}

int dec2bin4exp(int n,int *arr)

{

        int i,p;

        p=n;

        for(i=0;i<8;i++)

        arr[i]=0;

        i=7;

        do

        {

                arr[i]=n%2;

                n=n/2;

                i--;

        }

        while(n!=0);

                printf("the binary equivalent of %d is ",p);

printf("(i.e the exponent part in 8 bit is:)");

                for(i=0;i<8;i++)

                printf("%d",arr[i]);

        

                printf("\n");

}

int sign(float n)

{

int sign;

if(n>0)

sign=0;

else

sign=1;

printf("the signbit=%d\n",sign);

}

int rep(int *arr)

{

    

     int i,j,z=0,t=0,l,flag=0,power,sign,bias,k=0;

     for(i=0;i<23;i++)

     {

            if(arr[i]==1)

            z=i;

   if(z>0)

   {

for(l=z+1;l<23;l++)

 mant[k++]=arr[l];

     break;

   }

     }

      bias=k+127;

      //printf("K=%d",k);

for(j=0;j<23;j++)

{

mant[k++]=r[j];

    }

printf("the mantissa part in 23 bit is:");

for(i=0;i<23;i++)

{

printf("%d ",mant[i]);

}

printf("\n");

printf("------------------------------------------------------\n");

printf(" bias value is=%d\n",bias);

dec2bin4exp(bias,r);

}

void pt2bin(double d)

{

int i;

static double ar[23],f=0.0;

ar[0]=d;

// printf("\nar=%f\n",ar[0]);

for(i=0;i<23;i++)

{

f=ar[i] *2;

r[i]=(int)f;

ar[i+1]=f-r[i];

}

printf("The binary equivalent of %lf is:",d);

int ii;

for(ii=0;ii<23;ii++)

printf("%d ",r[ii]);

printf("\n");

}

int main()

{

double f,deci;

int real,arr[23],arr1[5];

printf("enter a floating point number\n");

scanf("%lf",&f);

real=f;

deci=f-real;

printf("------------------------------------------------------\n");

printf("the real part of the number is:=%d\n",real);

printf("the decimal part of the number is:=%lf\n",deci);

printf("------------------------------------------------------\n");

dec2bin(real,arr);

pt2bin(deci);

printf("------------------------------------------------------\n");

sign(f);

rep(arr);

printf("------------------------------------------------------\n");

return 0;

}