Operating system —— Banker algorithm (C language)

(1) Basic concepts

Deadlock: Multiple processes in execution, waiting for each other because of competing resources. Without an external force, these processes will never move forward. The system is in a deadlock state or a deadlock occurs.

Safe sequence: the system concurrent processes in a certain order so that they can achieve maximum resources and the sequence is safe.

Safe state: A state in which a safe sequence can be found is called a safe state, and a safe state does not cause a deadlock.

Unsafe state: If no security sequence exists in the current state, the system is in an unsafe state.

(2) Banker algorithm

As the name implies, the banker algorithm is derived from the lending business of the bank. A certain amount of principal needs to meet the borrowing turnover of multiple customers. In order to prevent the banker from failing in capital turnover, it is necessary to check whether each loan can be returned within a specified period.

There is a similar problem when studying the resource allocation strategy in the operating system. Limited resources in the system must be used by multiple processes, and it is necessary to ensure that the process of the obtained resources can return the resources within a limited time so that other processes can use the resources. If resources are not allocated properly, a deadlock occurs in which processes wait for resources in a loop, and no process can continue to execute.

When a process requests resources, the banker algorithm performs the following steps to decide whether to allocate resources to it:

1) Check whether the process needs more resources than it has declared.

2) Check whether the system has sufficient resources to meet the process’s requests.

3) The system tries to allocate resources to the process to get a new state.

4) Execute the security algorithm. If the new state is safe, the allocation is completed; If the new state is unsafe, restore the original state and block the process.

(3) Algorithm code

Processes in the Banker algorithm: the number of resources required by process Pi (also the maximum number of resources required, MAX)

Available indicates the number of free resources, that is, the resource pool (note: Number of remaining resources in the resource pool + number of resources allocated to all processes = Total resources in the system)

Header files required by the program:

#include “stdio.h”

#include “math.h”

 

Programmatically defined arrays:

ALL_RESOURCE[3] // Sum of resources

MAX[5][3] // Maximum resource demand for N resources by M processes

AVAILABLE[3] // Number of AVAILABLE resources in the system

ALLOCATION[5][3] //M processes are allocated the amount of class N resources

NEED[5][3] //M processes NEED the amount of class N resources

Request[20] // Number of requested resources

 

Program-defined methods:

Showdata () // The showdata function outputs the resource allocation

Changdata (int k) // Allocate resources

Rstordata (int k) // Restore site

Check (int s) // Function check to check for security

Bank () // Banker algorithm body

#include "stdio.h"
#include "math.h"
#define FALSE 0
#define TRUE 1

int M=5 ; // Total number of processes
int N=3 ; // Resource type
int ALL_RESOURCE[3] = {10.5.7};// The total number of resources
int MAX[5] [3] = {{7.5.3}, {3.2.2}, {9.0.2}, {2.2.2}, {4.3.3}}; // Maximum amount of N resources required by M processes
int AVAILABLE[3] = {4.4.4}; // Number of available resources in the system
int ALLOCATION[5] [3] = {{0.1.0}, {2.0.0}, {3.0.2}, {2.1.1}, {0.0.2}}; M processes have obtained the resource quantity of class N resources
int NEED[5] [3] = {{7.4.3}, {1.2.2}, {6.0.0}, {0.1.1}, {4.3.1}}; //M processes also require the amount of class N resources
int Request[20]; // Number of requested resources

void showdata() // The showdata function outputs the allocation of resources
{
   int i,j;

   printf("Allocation of resources for each process: \n");
   printf(\t resource 0 \t resource 1\t resource 2 \n");
   for (i=0; i<M; i++) { printf("P %d:",i);

     for (j=0; j<N; j++) printf(" %d\t",ALLOCATION[i][j]);
	 printf("\n");
   }
	printf("\n");
	printf("How much more resources each process needs (need): \n");
    printf(\t resource 0 \t resource 1\t resource 2\n");
   for (i=0; i<M; i++) { printf("P %d:",i);
     for (j=0; j<N; j++) printf(" %d\t",NEED[i][j]);
     printf("\n");
   }
   printf("\n");
}

void changdata(int k) // Allocate resources
{
   int j;
   for (j=0; j<N; j++) {AVAILABLE[j]=AVAILABLE[j]-Request[j]; ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j]; NEED[k][j]=NEED[k][j]-Request[j]; }}void rstordata(int k) // Restore the scene
{
   int j;
   for (j=0; j<N; j++) {AVAILABLE[j]=AVAILABLE[j]+Request[j]; ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j]; NEED[k][j]=NEED[k][j]+Request[j]; }}int check(int s) // Function check to check for security
{ int WORK,FINISH[10];
    int i,j,k=0;
    for(i=0; i<M; i++)FINISH[i]=FALSE;
    for(j=0; j<N; j++) { WORK=AVAILABLE[j];
        i=s;
        do
        {
			if(FINISH[i]==FALSE&&NEED[i][j]<=WORK)
            {
               WORK=WORK+ALLOCATION[i][j];
               FINISH[i]=TRUE;
               i=0;
            }
			else{ i++; }}while(i<M);
        for(i=0; i<M; i++)if(FINISH[i]==FALSE)
			{
				printf("\n Your input is wrong! Please re-enter! \n");
				return 1;
			}
     }
	printf("Request approved, resources allocated! \n");

    return 0;
}

void bank()   // Banker algorithm body
{
	int i=0,j=0,flag,k=0;
	while(k==0)
	{
		flag=0;
		showdata();
		i=- 1;
		while(i<0||i>=M)
		{
			printf("Please enter the process number (P0 to P%d, otherwise enter again! : P",M- 1);
			scanf("%d",&i);
			if(i<0||i>=M)
			printf("Entered process number does not exist, re-enter!");
		}
		printf("\n Please enter the number of resources requested by process P%d :",i);
		 for (j=0; j<N; j++) { printf("% d \ n resources.",j);
			scanf("%d",&Request[j]);
			if(Request[j]>NEED[i][j]) // If the number of resources requested is greater than the number of resources required by the process j class I resources
			{
				 printf("The number of resources requested by process P%d is greater than the number of resources required by process P%d. \n",i,i,j);
				 printf("Unreasonable application, error! Please choose again! \n");
				 flag=1; break;
			}

			if(Request[j]>AVAILABLE[j]) // If the number of requested resources is greater than the number of available resources
			{
				printf("The number of resources requested by process P%d is greater than the number of class % D resources available to the system! \n",i,j);
				printf("Unreasonable application, error! Please choose again! \n");
				flag=1; break; }}if(flag==0)
		 {
			changdata(i); // Call changData (I) to change the number of resources
			printf("Available: \n[");
			   for (j=0; j<N; j++) { printf("%d ".AVAILABLE[j]); }
			   printf("]\n\n");  

			if(check(i)) // If the system is secure
			{
				rstordata(i); // Call rstorData (I) to restore the number of resources
				showdata();   // Output the allocation of resources
			}
			else       // If the system is not secure
				showdata(); // Output the allocation of resources
		 }
		 printf("\n");
		 printf("Continue or not, press 0 to continue, 1:\t to end");
		 scanf("%d",&k); }}int main()
{
	int i,j;
	printf("Total number of resources (all): \n[");
   for (j=0; j<N; j++) { printf("%d ",ALL_RESOURCE[j]); }
   printf("]\n\n");

   printf("Available: \n[");
   for (j=0; j<N; j++) { printf("%d ".AVAILABLE[j]); }
   printf("]\n\n");  
	
   printf("Process maximum resource Demand (MAX): \n");
   for (i=0; i<M; i++) { printf("Process P%d",i);
	  for(j=0; j<N; j++) { printf("%d ",MAX[i][j]); 
	  
	  }
	  printf("\n");
	}
	printf("\n");
	bank();     
	
}
Copy the code