Banking algorithm

The banker's algorithm (english Banker's algorithm ) goes to Edsger W. Dijkstra (1965) back and to avoid deadlocks (deadlock) used. The available resources and processes are listed for this purpose. The resources are divided into total resources and available resources . The processes also have two properties: On the one hand, the resources that are already occupied, and on the other hand, the resources that are still required.

Then all processes - if execution is possible - are processed one after the other and the allocated resources are added to the available resources. After executing the algorithm it is clear whether a deadlock can be avoided or not. If the banking algorithm comes to a successful conclusion, a deadlock may still arise due to the careless execution sequence of the processes.

Name origin

Just as a banker has only a limited amount of money available to satisfy the needs of his customers, so an operating system has only a limited number of resources available. The banker therefore always keeps enough money in his safe that he can still meet the full credit limit of at least one customer. That one customer (process) can then successfully close its deal and get the money used back into the bank. Now another customer can have it.

application

Even if the banking algorithm is always listed as an elegant solution to avoid deadlocks in the context of operating systems , it should be borne in mind that it is rarely used in practice. For example, the algorithm does not take into account that the number of processes and resources is variable. Furthermore, the algorithm assumes that all of the resources required by the processes at runtime are precisely known in advance, which is rarely the case in reality.

requirements

The following information must be given to run the algorithm:

• ${\displaystyle m}$, the number of different resources.
• ${\displaystyle n}$, the number of processes involved.
• ${\displaystyle E=\{E_{1},...,E_{m}\}}$The amount of the total existing ( e xisting) resources.
• ${\displaystyle A=\{A_{1},...,A_{m}\}}$, the amount of a vailable resources.
• ${\displaystyle C_{i}=\{C_{i1},...,C_{im}\}}$, the amount of currently ( c urrently) allocated resources to the process . ${\displaystyle i}$
• ${\displaystyle R_{i}=\{R_{i1},...,R_{im}\}}$, the amount of r equired resources still required by the process . ${\displaystyle i}$

If the algorithm finds a sequence in which the processes can be processed one after the other without deadlock, the system is in a safe state.

implementation

The following Python function implements the banking algorithm: All terminated processes are collected in a list. As long as this list does not yet contain all processes and no deadlock has occurred, the requirements of all processes that have not yet been processed are examined. If all required resources of a process can be covered by the resources still available (element by element ), this process is processed and its resources are then released again ( ). The order in which the processes are processed does not matter, as it only increases or remains unchanged. ${\displaystyle R_{i}\leq A}$ ${\displaystyle A=A+C_{i}}$ ${\displaystyle A}$

def bankierAlgorithmus(E,A,C,R):
    n,m = len(C), len(C[0])
    beendeteProzesse = []
    verklemmung = False
    while len(beendeteProzesse) < n and not(verklemmung):
        verklemmung = True
        for i in range(n):
            if i in beendeteProzesse:
                continue
            elif all([R[i][j] <= A[j] for j in range(m)]):
                # Angeforderte Ressourcen werden Prozess i zugewiesen
                # Prozess i wird beendet und gibt alle seine Ressourcen frei
                A = [C[i][j] + A[j] for j in range(m)]
                beendeteProzesse.append(i)
                verklemmung = False
                print i, A
    return not(verklemmung), beendeteProzesse

The function returns whether the determined state is safe ( True/False) and the order in which the processes can run.

Examples

With deadlock

Initial state:

A = [4, 3, 42, 7]
E = [8, 5, 49, 9]
C = [[1, 0, 3, 0], [0, 1, 0, 1], [3, 0, 4, 1], [0, 1, 0, 0]]
R = [[0, 4, 0, 0], [3, 0, 2, 1], [0, 5, 36, 3], [0, 0, 0, 9]]

Intermediate statuses during runtime after each process has been selected and scheduled: ${\displaystyle i}$

i   A
    [4, 3, 42, 7]
1   [4, 4, 42, 8]
0   [5, 4, 45, 8]

Deadlock , since none of the other requirements ( [0, 5, 36, 3], [0, 0, 0, 9]) can be covered by available resources ( [5, 4, 45, 8]). The state of the system is said to be unsafe .

Without deadlock

Initial state:

E = [6, 3, 4, 2]
A = [1, 0, 2, 0]
C = [[3, 0, 1, 1], [0, 1, 0, 0], [1, 1, 1, 0], [1, 1, 0, 1], [0, 0, 0, 0]]
R = [[1, 1, 0, 0], [0, 1, 1, 2], [3, 1, 0, 0], [0, 0, 1, 0], [2, 1, 1, 0]]

Intermediate statuses during runtime after each process has been selected and scheduled: ${\displaystyle i}$

i   A
    [1, 0, 2, 0]
3   [2, 1, 2, 1]
4   [2, 1, 2, 1]
0   [5, 1, 3, 2]
1   [5, 2, 3, 2]
2   [6, 3, 4, 2]

Success , all processes can be executed successfully in the order found . The state of the system is said to be safe . ${\displaystyle (3,4,0,1,2)}$

Individual evidence

1. ^ Andrew S. Tanenbaum : Modern Operating Systems, 4th Edition . Pearson, 2015, ISBN 0-13-359162-X , 6.5.4, pp. 454-455 .

Web links

• interactive exercise on the banking algorithm from the University of Oldenburg (applet) (German)