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

{{trans|C}}

For simplicity, input checking is ignored:

 

fun main(args: Array<String>) {

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

}

 

Sample input/output:

Available Vector: 8 5 9 7

</pre>

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

Module BankerAlgo {

Form 80, 44

=FromWhere(What$ + "_max")-FromWhere(What$)-Many>=0

}

Function NewProcess {

Inventory Process

=Process

}

\\ Recource, Max, Available

Append Processes, "P2":=NewProcess("A", 1, 1, "B", 2, 0, "C", 3, 3, "D", 4,3)

Append Processes, "P3":=NewProcess("A", 1, 1, "B", 3, 2, "C", 5, 1, "D", 0,0)

RequestResource("P3", "C", 1) ' display Safe State

Status()

Sub Respond()

If SafeState Then {

Pen 15 {Print "Safe State"}

} Else Pen 13 {Print "Unsafe State"}

End Sub

Sub RequestResource(ProcessName$="" )

SafeState=True

Local pro=Processes(ProcessName$), ResourceName$, many as long

ClearAllRequest(pro)

}

} Else Print "Too many Recources for System" : Skip=True

}

If skip Else CheckNewState(&SafeState) : Respond()

Print ' just a new line

End Sub

Sub ApplyResources(Where as Inventory, What$, MaxValue, InitialValue)

If Instr(Eval$(M, M^),"_")=0 Then {

Return Where, Eval$(M,M^)+"_Request":=0

}

}

While M {

If Instr(Eval$(M, M^),"_")=0 Then Print Eval$(M, M^)+"="+Eval$(M),

}

Print

Print "Available Resources in System"

PrintResources(System)

Local M=Each(Processes)

While M {

End Sub

Sub CheckNewState(&Ok)

}

}

}

ClearAllRequest(System)

End Sub

}

 

=={{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 available vector is: 8 5 9 7

</pre>

 

{{omit from|Blast}}

{{omit from|GUISS}}

{{omit from|Openscad}}

{{omit from|TPP}}