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|Perl}}==

use warnings;

use feature 'say';

 

my @avail = (3, 1, 1, 2); # Available instances of resource

# Function to find the system is in safe state or not

sub isSafe {

}

}

 

my $count = 0;

my $found = 0;

for my $p (0..$P-1) {

# Check if for all resources of current P need is less than work

my $satisfied;

$satisfied = $j;

}

if ($satisfied == $R-1) {

$count += 1;

$found = 1

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

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

{{out}}

Message: Safe sequence is: 0 1 2</pre>

 

=={{header|Phix}}==

{{out}}

<pre>

Available resources: {3,0,1,2}

The processes are in an unsafe state.

</pre>

 

=={{header|Racket}}==

 

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

 

 

EOS

 

{{out}}

 

Available vector: '#(8 5 9 7)</pre>

 

=={{header|Rust}}==

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}}

The process is in safe state.

The available vector is: [8, 5, 9, 7]</pre>

 

{{omit from|Blast}}

{{omit from|GUISS}}

{{omit from|Openscad}}

{{omit from|TPP}}