Banker's algorithm: Difference between revisions

The '''Banker's algorithm''' is a [[wp:resource allocation|resource allocation]] and [[wp:deadlock|deadlock]] avoidance [[wp:algorithm|algorithm]] developed by [[wp:Edsger Dijkstra|Edsger Dijkstra]] that tests for safety by simulating the allocation of predetermined maximum possible amounts of all [[wp:resource (computer science)|resources]], and then makes a "s-state" check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue.

 

Total resources in system:

P2 0 2 0 1

P3 0 1 4 0

 

=={{header|C}}==

 

There are two <code>main()</code> functions to choose from (look for <code>#define BIG_EXAMPLE</code>), one is for task example, the other is a much heavier duty test case.

#include <stdbool.h>

 

 

return 0;

{{out|Input and Output}}

<pre>Enter the number of resources: 4

The process is in safe state.

Available vector: 8 5 9 7</pre>

 

=={{header|Go}}==

 

This solution is more inspired by EWD-623 than WP. EWD-623, while it talks of finding a permutation of processes, notes that the "ordering effort" can be stopped as soon as the process requesting resources happens to be found satisfiable. The solution here attempts to make this finding as soon as possible by moving the process to the front of a list of unsatisfied processes. Also since the solved permutation of satisfied processes has no use, it is not kept which simplifies the algorithm a bit.

 

import (

perm[h] = perm[m]

}

 

import (

fmt.Println("\nP3 request:")

fmt.Println(b.Request("P3", bank.RMap{"A": 1, "B": 2, "C": 1}))

{{out}}

<pre>

The task description currently does not define the process being run. So we follow the example set by other implementations and have each process free all resources after successfully being run. Also, since this is a demo, we give a blow-by-blow description of what's happening as it runs.

 

'MAX ALLOC TOTAL'=. y

todo=.(#ALLOC)#1

end.

echo 'DONE'

 

Definitions for task example:

 

alloc=: 1 2 2 1,1 0 3 3,:1 2 1 0

total=:6 5 7 6

NB. left arg: newly available resources, right: previously available

NB. result: resources freed

 

Example run:

 

currently available: 3 1 1 2

running process 0, allocating 2 1 0 1

running process 2, allocating 0 1 4 0

process 2 freeing 1 3 5 0

 

=={{header|Julia}}==

{{trans|Kotlin}}

print(query, ": ")

entry = uppercase(strip(readline(stdin)))

 

testbankers()

<pre>

Enter the number of resources: 4

{{trans|C}}

For simplicity, input checking is ignored:

 

fun main(args: Array<String>) {

println("\nAvailable Vector: ${avl.joinToString(" ")}")

}

 

Sample input/output:

 

=={{header|M2000 Interpreter}}==

Module BankerAlgo {

Form 80, 44

End Sub

}

 

=={{header|Nim}}==

{{trans|Kotlin}}

 

stdout.write "Enter the number of resources: "

 

echo "\nThe process is in a safe state."

 

{{out}}

=={{header|Perl}}==

{{trans|Raku}}

use warnings;

use feature 'say';

my($safe_state,$status_message) = isSafe(\@avail, \@maxm, \@allot);

say "Safe state? " . ($safe_state ? 'True' : 'False');

{{out}}

<pre>available resources: 4 3 3 3

 

=={{header|Phix}}==

{{out}}

<pre>

 

=={{header|Python}}==

def main():

 

 

 

allocated = [0] * resources

for j in range(resources):

allocated[j] += currently_allocated[i][j]

 

available = [max_resources[i] - allocated[i] for i in range(resources)]

 

running = [True] * processes

break

if executing:

running[i] = False

count -= 1

break

if not safe:

break

 

 

 

if __name__ == '__main__':

main()

{{out}}

<pre>

 

 

 

 

 

 

</pre>

 

=={{header|Racket}}==

 

(require racket/block racket/pretty racket/port racket/vector)

 

 

EOS

 

{{out}}

Based on the Python3 solution by Shubham Singh found

[https://www.geeksforgeeks.org/program-bankers-algorithm-set-1-safety-algorithm/ here]

my @maxm = <3 3 2 2>, <1 2 3 4>, <1 3 5 0>; # Maximum resources that can be allocated to processes

my @allot = <1 2 2 1>, <1 0 3 3>, <1 2 1 0>; # Resources allocated to processes

my ($safe-state,$status-message) = isSafe @avail, @maxm, @allot;

say "Safe state? $safe-state";

{{out}}

<pre>available resources: 4 3 3 3

Adapted from the C language version. It crashes for invalid input.

 

fn read_numbers<T>() -> Vec<T>

where T: std::str::FromStr {

println!();

}

 

{{out|Input and Output}}

The process is in safe state.

The available vector is: 8 5 9 7

</pre>

 

=={{header|Swift}}==

 

 

print("Enter the number of resources: ", terminator: "")

 

print("The available vector is: \(available)")

 

{{out|Input and Output}}

=={{header|Wren}}==

{{trans|Kotlin}}

 

System.write("Enter the number of resources: ")

System.write("\nThe process is in a safe state.")

System.print("\nAvailable Vector: %(avl.join(" "))")

 

{{out}}

Available Vector: 8 5 9 7

</pre>

 

{{omit from|Blast}}