eLearning

The Banker's algorithm is a resource allocation & deadlock avoidance algorithm developed by Edsger Dijkstra that tests for safety by simulating the allocation of pre-determined maximum possible amounts of all resources, and then makes a "safe-state" check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue.

The algorithm was developed in the design process for the THE operating system and originally described (in Dutch) in EWD108[1]. The name is by analogy with the way that bankers account for liquidity constraints.

The Banker's algorithm is run by the operating system whenever a process requests resources.The algorithm prevents deadlock by denying or postponing the request if it determines that accepting the request could put the system in an unsafe state (one where deadlock could occur).

For the Banker's algorithm to work, it needs to know three things:

• How much of each resource each process could possibly request

• How much of each resource each process is currently holding

• How much of each resource the system has available

Some of the resources that are tracked in real systems are memory, semaphores and interface access.

Example

Available system resources:

A B C D

3 1 1 2

Processes (currently allocated resources):

A B C D

P1 1 2 2 1

P2 1 0 3 3

P3 1 1 1 0

Processes (maximum resources):

A B C D

P1 3 3 2 2

P2 1 2 3 4

P3 1 1 5 0

Safe and Unsafe States

A state (as in the above example) is considered safe if it is possible for all processes to finish executing (terminate). Since the system cannot know when a process will terminate, or how many resources it will have requested by then, the system assumes that all processes will eventually attempt to acquire their stated maximum resources and terminate soon afterward. This is a reasonable assumption in most cases since the system is not particularly concerned with how long each process runs (at least not from a deadlock avoidance perspective). Also, if a process terminates without acquiring its maximum resources, it only makes it easier on the system.

Given that assumption, the algorithm determines if a state is safe by trying to find a hypothetical set of requests by the processes that would allow each to acquire its maximum resources and then terminate (returning its resources to the system). Any state where no such set exists is an unsafe state.

Example

We can show that the state given in the previous example is a safe state by showing that it is possible for each process to acquire its maximum resources and then terminate.

1. P1 acquires 2 A, 1 B and 1 D more resources, achieving its maximum

o The system now still has 1 A, no B, 1 C and 1 D resource available

2. P1 terminates, returning 3 A, 3 B, 2 C and 2 D resources to the system

o The system now has 4 A, 3 B, 3 C and 3 D resources available

3. P2 acquires 2 B and 1 D extra resources, then terminates, returning all its resources

o The system now has 5 A, 3 B, 6 C and 6 D resources

4. P3 acquires 4 C resources and terminates

o The system now has all resources: 6 A, 4 B, 7 C and 6 D

5. Because all processes were able to terminate, this state is safe

Note that these requests and acquisitions are hypothetical. The algorithm generates them to check the safety of the state, but no resources are actually given and no processes actually terminate. Also note that the order in which these requests are generated – if several can be fulfilled – doesn't matter, because all hypothetical requests let a process terminate, thereby increasing the system's free resources.

For an example of an unsafe state, look at what would happen if process 2 were holding 1 more unit of resource B at the beginning.

When the system receives a request for resources, it runs the Banker's algorithm to determine if it is safe to grant the request. The algorithm is fairly straight forward once the distinction between safe and unsafe states is understood.

1. Can the request be granted?

o If not, the request is impossible and must either be denied or put on a waiting list

2. Assume that the request is granted

3. Is the new state safe?

o If so grant the request

o If not, either deny the request or put it on a waiting list

Whether the system denies an impossible or unsafe request or makes it wait is an operating system specific decision.

Continuing the previous examples, assume process 3 requests 2 units of resource C.

1. There is not enough of resource C available to grant the request

2. The request is denied

On the other hand, assume process 3 requests 1 unit of resource C.

1. There are enough resources to grant the request

2. Assume the request is granted

o The new state of the system would be:

Available system resources: A B C D

Free 3 1 0 2

Processes (currently allocated resources):

A B C D

P1 1 2 2 1

P2 1 0 3 3

P3 1 1 2 0

Processes (maximum resources):

A B C D

P1 3 3 2 2

P2 1 2 3 4

P3 1 1 5 0

1. Determine if this new state is safe

1. P1 can acquire 2 A, 1 B and 1 D resources and terminate

2. Then, P2 can acquire 2 B and 1 D resources and terminate

3. Finally, P3 can acquire 3 C resources and terminate

4. Therefore, this new state is safe

2. Since the new state is safe, grant the request

Finally, assume that process 2 requests 1 unit of resource B.

1. There are enough resources

2. Assuming the request is granted, the new state would be:

Available system resources:

A B C D

Free 3 0 1 2

Processes (currently allocated resources):

A B C D

P1 1 2 2 1

P2 1 1 3 3

P3 1 1 1 0

Processes (maximum resources):

A B C D

P1 3 3 2 2

P2 1 2 3 4

P3 1 1 5 0

1. Is this state safe? Assuming P1, P2, and P3 request more of resource B and C.

o P1 is unable to acquire enough B resources

o P2 is unable to acquire enough B resources

o P3 is unable to acquire enough C resources

o No process can acquire enough resources to terminate, so this state is not safe

2. Since the state is unsafe, deny the request

* The algorithm for the process is...........

1. Start.

2. Wait for the request.

3. If the request is for allocation then

i. Obtain the request.

ii. Check for safe state.

iii. If safe state detected then allocate resources.

Else put the request in the waiting stack.

Else (for deallocation)

i.Deallocate the resources.

ii. Process the request of the process in the

wait stack.

4. Stop.

/* Program to demonstrate the working of the BANKERS ALGORITHM.

* This program gives a general idea of how the operating system process allocates resources to the requesting processes.

* Here it is assumed that request are collected in a 'req_queue' whose type is stored in 'req_type'.

* It has been assumed that there are 3 processes which can request for 4 different types of resources say A,B,C & D.

* The program works with certain assumed values as shown below.........

* This module can be compiled using 'cc bankersalgorithm.c' and executed using './a.out'

//inculsion.

#include

//macro definition

#define cls() printf("\033[H\033[J")

#define delay() for(h=0;h<30000;h++){for(k=0;k<30000;k++){}}

//function prototype.

void getrequest(int);

int issafe();

void allocate(int);

void deallocate(int);

void display();

//global matrixes as shown above.

int available_res[4],cur_allocated_res[3][4],max_req_res[3][4],request[4];

int main()

{

int req_queue[10],wait_queue[10],req_type[10],i,j,h,k;

//inserting the assumed values.

available_res[0]=3; available_res[1]=1; available_res[2]=1; available_res[3]=2;

cur_allocated_res[0][0]=1;cur_allocated_res[0][1]=2;cur_allocated_res[0][2]=2;cur_allocated_res[0][3]=1;

cur_allocated_res[1][0]=1;cur_allocated_res[1][1]=0;cur_allocated_res[1][2]=3;cur_allocated_res[1][3]=3;

cur_allocated_res[2][0]=1;cur_allocated_res[2][1]=1;cur_allocated_res[2][2]=1;cur_allocated_res[2][3]=1;

max_req_res[0][0]=3; max_req_res[0][1]=3; max_req_res[0][2]=2; max_req_res[0][3]=2;

max_req_res[1][0]=1; max_req_res[1][1]=2; max_req_res[1][2]=3; max_req_res[1][3]=4;

max_req_res[2][0]=1; max_req_res[2][1]=1; max_req_res[2][2]=1; max_req_res[2][3]=0;

//assuming the request.

req_queue[0]=0;req_queue[1]=1;req_queue[2]=2;req_queue[3]=0;req_queue[4]=2;req_queue[5]=1;

req_type[0]=0;req_type[1]=0;req_type[2]=0;req_type[3]=1;req_type[4]=1;req_type[5]=1;

display();

i=0;j=0;

while(i<6)

{

cls();

printf("\n\t\t\tWaiting for the request.............\n");

delay();

printf("\n\tRequest obtained from the process P%d ",req_queue[i]+1);

if(req_type[i]==0)

{

printf("for resource allocation.\n");

printf("\nGetting request.....\n");

getrequest(req_queue[i]);

printf("\nChecking safe state.....\n");

delay();

if(issafe())

{

printf("\nSafe state detected....\nAllocating resources .......\n");

allocate(req_queue[i]);

}

else

{

printf("\nUnsafe state detected....\nInserting the process into waiting queue.\n");

j=j+1;

wait_queue[j]=req_queue[i];

}
}

else

{

printf("for resource deallocation.\n");

deallocate(req_queue[i]);

printf("\nDeallocation done.\n\n%d processes in the wait queue\n",j);

if(j>0)

{

while(j>0)

{

printf("\nConsidering the waiting queue process P%d\n",wait_queue[j]+1);

getrequest(wait_queue[j]);

printf("\nChecking safe state.\n");

delay();

if(issafe())

{

printf("\nSafe state detected\nResources allocated\n");

allocate(wait_queue[j]);

j--;

}

else

{

break;

}

}

}

}

delay();

i++;

}

}

void getrequest(int i)
{

int j;

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

{ request[j]=max_req_res[i][j]-cur_allocated_res[i][j];

}

}

int issafe()

{

int j;

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

{

if(request[j]>available_res[j])

{

return 0;

}

}

return 1;

}

void allocate(int i)

{

int j;

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

{

cur_allocated_res[i][j]=cur_allocated_res[i][j]+request[j];
available_res[j]=available_res[j]-request[j];

}

}

void deallocate(int i)

{

int j;

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

{

available_res[j]=available_res[j]+cur_allocated_res[i][j];

cur_allocated_res[i][j]=0;

}

}

void display()

{

int i,j;

char a[3];

cls();

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

printf("_______________________________________________________________");

printf("\n\n\n\n\t\t\t\tBANKERS ALGORITHM.\n");

printf("\t\t\t\t__________________\n\n\n");

printf("\n\n\n\n\t\tPRESS ENTER TO CONTINUE..................");

fgets(a,2,stdin);

cls();

printf("\n\n\t\t\t\tDETAILS.");

printf("\n\t\t\t\t________");

printf("\n\n\t\tNO OF PROCESSES:\tP1 P2 P3");

printf("\n\n\t\tNO OF RESOURCES:\tA B C D");

printf("\n\n\t\t\tThe status .............");

printf("\nThe available resources are.\n\t\tA B C D\n\t\t");

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

{

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

}

printf("\nThe currently allocated resources are...\n\t\t A B C D\n\t\t");

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

{

printf("P%d ",i+1);

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

{

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

}

printf("\n\t\t");

}

printf("\nThe maximum required resources are...\n\t\t A B C D\n\t\t");

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

{

printf("P%d ",i+1);

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

{

printf("%d ",max_req_res[i][j]);
}

printf("\n\t\t");

}

printf("\n\n\tPRESS ENTER TO START THE PROCESS...\n");

fgets(a,2,stdin);

}