Explanation:
This program is to demonstrate banker's algorithm. If All process execute completely using resources, without deadlock, we say system is in safe state and display state sequence(order in which process gets executed).
Note: In this program, I don't know at what extent I have been successful in expressing what I know. If you get what I'm trying to express, kindly post a review to support this post so that Google's indexing of this page improves. Thereby supporting my work. Thanks :)
#include<stdio.h>
struct process
{
int all[6],max[6],need[6],finished;
}p[10];
int avail[6],sseq[10],ss=0,check1=0,check2=0,n,work[6];
int nor;
Include header files.
Define a structure to hold the values of a process. i.e.,
- all[6] is an array to hold allocated resource number for 6 resources at max.
- similarly, max[6], need[6] for maximum resources required for execution and needed resource.
- finished, for checking whether execution for that function is completed or not. if 1, then completed. Not otherwise.
- avail[6] is an array for defining the system's total resources.
- sseq[10] for storing state sequence, the order of execution of processes.
- n for asking the number of processes.
- nor for asking the number of resources.
int safeseq(void);
int main()
{
int ch,i=0,j=0,k,pid,ch1;
do
{
printf("\n\n\t 1. Input");
printf("\n\n\t 2. Safe State or Not");
printf("\n\n\t 3. print");
printf("\n\n\t 4. Exit");
printf("\n\n\t Enter ur choice :");
scanf("%d",&ch);
safeseq() is the function declaration. we will see to it later.
next is main function.
declare required variables. show the menu. ask for choice ch. Until ch<4, we keep on executing the menu, using do while loop.
switch(ch)
{
case 1:
printf("\n\n\t Enter number of processes : ");
scanf("%d",&n);
printf("\n\n\t Enter the Number of Resources : ");
scanf("%d",&nor);
if case 1, then ask for input.
ask the number of processes and resources and store them in 'n' and 'nor' separately.
printf("\n\n\t Enter the Available Resouces : ");
for(j=0;j<n;j++)
{
for(k=0;k<nor;k++)
{
if(j==0)
{
printf("\n\n\t For Resource type %d : ",k);
scanf("%d",&avail[k]);
}
p[j].max[k]=0;
p[j].all[k]=0;
p[j].need[k]=0;
p[j].finished=0;
}
}
Since we declared a structure variable, we need to initialize all the objects of that variable to 0 initially. also we need to ask for the Computer's total resources (that is the total available resource when no process are there).
- for j=0 to n, perform k loop.
- for k=0 to nor for each process, initialize all variables to 0.
- Also when j=0 (the first iteration of this loop), we ask and store the total available resources if the system in an array avail[k]. this is inside k loop because, there are nor number of resources in total.
for(i=0;i<n;i++)
{
printf("\n\n\t Enter Max and Allocated resources for P %d : ",i);
for(j=0;j<nor;j++)
{
printf("\n\n\t Enter the Max of resource %d : ",j);
scanf("%d",&p[i].max[j]);
printf("\n\n\t Allocation of resource %d :",j);
scanf("%d",&p[i].all[j]);
if(p[i].all[j]>p[i].max[j])
{
printf("\n\n\t Allocation should be less < or == max");
j--;
}
else
p[i].need[j]=p[i].max[j]-p[i].all[j];
avail[j]=avail[j]-p[i].all[j];
}
}
break;
This is the actual input phase. We ask and store max resource and already allocated resource of each resource for each process.
- i loop is for each process.
- j loop is for each resource.
- ask for max and allocated resource for each such pair. if allocated is greater than maximum resource that is need to complete the execution, it is meaningless. so we ask the user to enter again. This is done by the statement j--. so that when j loop does j++. the j value is same, and user can actually enter j'th resource values again.
- Otherwise, we calculate the need[k] for that process. by the formula, need=max-allocated.
- also we update total available resource, avail[k]. (avail[j]=avail[j]-p[i].all[j];) because we allocated some resource for p[j].all[i].
- Input done. hope you are clear. Without being clear, don't continue, read again in that case.
case 2:
if(safeseq()==1)
printf("\n\n\t The System is in safe state ");
else
printf("\n\n\t The System is Not in safe state ");
break;
This is second option of the menu. That is to check whether the system is in safe state or now. We call safeseq() and based on its return value (1 for True or 0 False), we display appropriate message. Logic of function is explained near definition.
case 3:
printf("\n\n\t Number of processes : %d",n);
printf("\n\n\t Number of Resources : %d",nor);
printf("\n\n\t Pid \t Max \t Allocated \t Need ");
for(i=0;i<n;i++)
{
printf("\n\n\t P%d : ",i);
for(j=0;j<nor;j++)
printf(" %d",p[i].max[j]);
printf("\t");
for(j=0;j<nor;j++)
printf("%d",p[i].all[j]);
printf("\t");
for(j=0;j<nor;j++)
printf("%d",p[i].need[j]);
}
printf("\n\n\t Available :");
for(i=0;i<nor;i++)
printf("%d",avail[i]);
break;
This is to display the data entered along with total number of available resources.
for each process i=0 to n,
for each process, for each resource j=0 to nor,
we print max, allocated, need variables in the form of table.
This code is simple and understandable. So I will leave it to you.
case 4:
break;
}while(ch<4);
}
Case 4 is Exit. Simply break.
until our choice was less than 4, We will continue showing the Menu.
Safeseq Logic()
int safeseq()
{
int tj,tk,i,j,k;
ss=0;
for(j=0;j<nor;j++)
work[j]=avail[j];
for(j=0;j<n;j++)
p[j].finished=0;
- Return type is integer, if system is in safe state, we return 1, else 0.
- Declare some variables for looping.
- First, take backup of the avail[] array into a new array work[], which is used for calculation. This is done for each resource's available value, (for j=0 to nor).
- also assign each process's finished to 0, indicating that process is yet to be finished. (for each process i=0 to n).
for( tk=0;tk<=nor;tk++)
{
This is interesting. Since in banker's algorithm we consider process execution in a cyclic manner (if that process can't be provided with resources now, we come back to that process again only in a cyclic manner, that is after all the next process are given a chance). Since we don't know how many time to cycle between all the processes. We consider a cycle for each resource. (because this is the maximum limit within which all the processes must be executed). so we run cyclic executions for tk=0 to nor.
for(j=0;j<n;j++)
{
if(p[j].finished==0)
{
check1=0;
for(k=0;k<nor;k++)
if(p[j].need[k]<=work[k])
check1++;
For each process j (from j=0 to n, indicating one round of check for all the processes)
we check whether that process can be provided with resources that it needs ( i.e., for all the resources that process is requesting, systems available resource must be greater than the number of resource the process is requesting). we do that as follows,
- If a process isn't completed, (p[j].finished==0), then we assign a variable for counting, check1=0.
- Then for each resource, we check whether process's need is less than the system's available resource. If true, then we increment check1 by 1. So at the end when all the resources are checked, if check1==nor (the total number of resources), it means all the need's can be provided. That is done in the next snippet.
{
for(k=0;k<nor;k++)
{
work[k]=work[k]+p[j].all[k];
p[j].finished=1;
}
sseq[ss]=j;
ss++;
} //end of if
} //end of outer if
} //end of j loop
} //end of tk loop
Same thing as told above, if check1==nor, it means we can execute that process, so we execute it. Now the already allocated resource for that process can be released, and can be added to system's total available resources, so that other processes can use them. That's what is done here.
Also, since this process was executed, we append its process number to sseq array (order of execution). then increment ss (index variable for sseq array) for storing next executed process in next index.
Then close all the flower brackets (see the comment lines in snippet).
check2=0;
for(i=0;i<n;i++)
if(p[i].finished==1)
check2++;
printf("\n\n\t");
So that way, all process's needs are checked and executed. At the end when the for( tk=0;tk<=nor;tk++) loop ends, we need to check whether all the processes are executed, only then we can say that system is in safe state, so Check 2 is performed.
The logic is like this,
- Assign a variable check2=0.
- For each process i=0 to n, check whether it's finished==1. If true, increment check2 by 1.
- So at the end if check2==n, then we say system is in safe state. That's done ahead.
{
printf("\n\n\t The system is in safe state");
for( tj=0;tj<n;tj++)
printf("P%d,",sseq[tj]);
return 1;
}
Same thing as told above, If check2>=n, we display "Safe state" message and display the state sequence array sseq. Then return 1 to the main function(see case 2: explanation above).
else
printf("\n\n\t The system is Not in safe state");
return 0;
}
Otherwise system is not in safe state, we display the same and return 0 to the main function.
Done!
BANKER ALGORITHM FOR'YA!
Share your views about this article!