[Algorithm] Operating System Process Communication (Deadlock Prevention) Algorithm Dijkstra's Banker's Algorithm C Language Implementation

Today I completed yesterday's algorithm, the Banker's algorithm. If you are familiar with the operating system course, you should understand this. I was busy reviewing yesterday and today, but I still managed to complete the basic debugging in the afternoon. The debugging environment is GCC and TC. Now I am sharing the code with everyone.

Banker's algorithm explanation: Originally proposed by algorithm master Edsger Dijkstra, the Banker's algorithm, as the name suggests, is based on the management of deposit and loan issuance in a banking system. The bank (system) needs to allocate a certain amount of funds (resources) as loans (allocation) to N individuals (processes). Of course, credit is not a concern < '_'>. After a certain amount of money has been issued, each subsequent loan (resource allocation) by the bank (system) must ensure the safe operation of the bank (preventing deadlock) (you can understand it this way). Therefore, the banker needs to allocate and distribute the existing funds reasonably. The basic requirement is that the bank must maintain a certain amount of deposits that cannot fall below a certain limit (critical resources), and at the same time, it cannot refuse to issue loans, otherwise it will starve the customers (processes). After using the loan, the customer must return (release) the loan, of course, without interest, and then the bank will allocate it to the customer again until all the loan requests are satisfied.

For more details, please refer to http://baike.baidu.com/view/93075.htm

The code is as follows:

Banker's algorithm
code CG 2008 01 05
*/

#include"stdio.h"

#define FALSE 0
#define TRUE 1
#define W 10
#define R 20
int M ; /* Total number of processes /
int N ; / Number of resource types */

int ALL_RESOURCE[W];/* Total number of each resource type /
int MAX[W][R]; / Maximum resource demand of M processes for N resource types /
int AVAILABLE[R]; / Number of available resources in the system /
int ALLOCATION[W][R]; / Amount of N resources already obtained by M processes /
int NEED[W][R]; / Amount of N resources still needed by M processes /
int REQUEST[R]; / Number of requested resources */

Function name: output
Function: Output resource allocation situation
*/
void output()
{
int i,j;
printf("All Resource:\n");
for(j = 0 ; j < N ;j++)
printf("R%d: %d\n", j , ALL_RESOURCE[j]);

printf("Resource Available:\n");
for(j = 0 ; j < N ; j++)
printf("R%d: %d\n", j , AVAILABLE[j]);

printf("Process Resource Needed:\n");

printf("| PID |");
for(j = 0 ; j < N ; j++)
printf(" R%d |", j);
printf("\n");

for(i = 0 ; i < M ; i++)
{
printf("|%-5d|", i);
for(j = 0 ; j < N ; j++)
printf("%-4d|", NEED[i][j]);
printf("\n");
}

printf("Process Resource Allocated:\n");

printf("| PID |");
for(j = 0 ; j < N ; j++)
printf(" R%d |", j);
printf("\n");

for(i = 0 ; i < M ; i++)
{
printf("|%-5d|", i);
for(j = 0 ; j < N ; j++)
printf("%-4d|", ALLOCATION[i][j]);
printf("\n");
}
}/output/

Function name: modify
Function: Change the values of available resources, obtained resources, and needed resources
Parameter: int k, modify the data of process P with the number K
*/
void modify(int k)
{
int j;
for(j = 0 ; j < N ; j++){/Modify data/
AVAILABLE[j] = AVAILABLE[j] - REQUEST[j];/Modify available resources/
ALLOCATION[k][j] = ALLOCATION[k][j] + REQUEST[j];/Modify allocated resources/
NEED[k][j] = NEED[k][j] - REQUEST[j];/Modify resource needs/
}
}

Function name: undo
Function: Restore the values of available resources, obtained resources, and needed resources
Parameter: int k, modify the data of process P with the number K
/
void undo(int k){
int j;
for(j = 0 ; j < N ; j++){/Modify data/
AVAILABLE[j] = AVAILABLE[j] + REQUEST[j]; /Modify available data/
ALLOCATION[k][j] = ALLOCATION[k][j] - REQUEST[j]; /Modify allocated resources/
NEED[k][j] = NEED[k][j] + REQUEST[j];/Modify resource needs/
}
}
/
Function name: chkerr
Function: Check if the modification operation is safe
*/
int chkerr(int s){
int WORK , FINISH[W];
int i , j;
for(i = 0 ; i < M ; i++)/Clear FINISH/
FINISH[i] = FALSE;
for(j = 0 ; j < N ; j++){/Check one by one/
WORK = AVAILABLE[j];
i = s;
do{
if(FINISH[i] == FALSE && NEED[i][j] <= WORK){/Meets the conditions?/
WORK = WORK + ALLOCATION[i][j];
FINISH[i] = TRUE;
i = 0;
}
else
i++;
}while(i < M);
for(i = 0 ; i < M ; i++)/If one does not satisfy, it is unsafe/
if(FINISH[i] == FALSE){
printf("Error: UnSafe Allocation!\n");
return 1;
}
}
printf("OK: Allocation OK\n");
return 0;
}

Function name: bank
Function: Implementation of the Banker's algorithm
*/
void bank()
{
int i , j;
int flag = TRUE;
printf("Use Ctrl+C to break..\n");
while(TRUE){
i = -1;
while(i < 0 || i >= M)
{
printf("Input Process to Allocate PID=");
scanf("%d", &i);
if(i < 0 || i >= M)
printf("Error: Invalid Input!\n");
}
printf("Input Resource Need\n");
for (j = 0 ; j < N ; j++)
{
printf("R%d=", j);
scanf("%d", &REQUEST[j]);
if(REQUEST[j] > NEED[i][j]){/Requested resource number is greater than requested resource/
printf("Error: Invalid Input!\n");
flag = FALSE;
}
else{
if(REQUEST[j]>AVAILABLE[j]){/If the requested resource number is greater than the available resource number/
printf("Error: Invalid Input!\n");
flag = FALSE;
}
}/else/
}/for/
```
  if(flag)
  {
      modify(i); /*Modify resource number*/
      if(chkerr(i)){/*Is it safe?*/
          undo(i); /*Restore resource number*/
          output();/*Output*/
      }
      else
          output(); /*Output*/
  }
  else
      output();
```
}/while/
}/bank/

/Main function/
int main(){
int i , j , p;
printf("Input Process Numbers M=");/Number of processes/
scanf("%d", &M);
printf("Input Resource Category N=");/Number of resource types/
scanf("%d", &N);
printf("Input Number of All Resource each Category:\n");/Number of resources/
for(i = 0 ; i < N ; i++)
scanf("%d", &ALL_RESOURCE[i]);
printf("Input Max Resource Process Need:\n");/Maximum resource demand/
for (i = 0 ; i < M ; i++){
for (j = 0 ; j < N ; j++){
do{
scanf("%d", &MAX[i][j]);
if (MAX[i][j] > ALL_RESOURCE[j])/Greater than the maximum available?/
printf("\nError: Invalid Input!\n");
}while (MAX[i][j] > ALL_RESOURCE[j]);
}
}/for/

printf("Input Resource Process Allocated:\n");
for (i = 0 ; i < M ; i++){
    for (j = 0 ; j < N ; j++){
        do{
            scanf("%d", &ALLOCATION[i][j]);
            if (ALLOCATION[i][j] > MAX[i][j])/*Greater than the maximum demand?*/
                printf("\nError: Invalid Input!\n");
        }while (ALLOCATION[i][j] > MAX[i][j]);
    }
}/*for*/

for(j = 0 ; j < N ; j++){
    p = ALL_RESOURCE[j];
    for(i = 0 ; i < M ; i++){
        p -= ALLOCATION[i][j];/*Subtract allocated resources*/
        AVAILABLE[j] = p;
        if(AVAILABLE[j]<0)
            AVAILABLE[j] = 0;/*Clean up data*/
    }/*for*/
}/*for*/
for (i = 0 ; i < M ; i++)
    for(j = 0 ; j < N ; j++)
        NEED[i][j] = MAX[i][j] - ALLOCATION[i][j];/*Calculate the remaining needed resources*/
output();
bank();/*Banker's algorithm*/
return 0;

}/main/