hkucuk

Banker's Algorithm: Anti-Deadlock Algorithm

March 27, 2024 • ☕️ 4 min read • 🏷 computer, software, algorithm, os

Translated by author into: English


The Banker’s Algorithm is an algorithm used in operating systems that helps reduce the possibility of deadlocks. Deadlock is a situation that occurs as a result of processes or resources that need each other waiting for each other and prevents progress in the system. The Banker’s Algorithm is designed to prevent such deadlocks and is especially used in systems that require resource management.

The Banker’s Algorithm tracks the resources in a system and the amounts of those resources requested by transactions. The total amount of resources in the system at any given time is known. The algorithm tracks the amount of resources requested for each transaction and limits how long or amounts transactions can request certain resources. These limits ensure that the available resources in the system are capable of meeting the requested amount of resources.

Working Steps

The working steps of the Banker’s Algorithm are as follows:

  1. Initially, the total amount of resources in the system and the maximum amount of resources that each process can request are determined.
  2. When a process contacts the Banker’s Algorithm to request resources, the amount of resources available in the system is compared with the amount of resources requested by the process.
  3. If the available resources in the system can meet the resources requested by the process, the process is run and the resources are used by the process. Otherwise, the process is put into standby mode.
  4. When a process releases resources, the released resources are made available to other processes.
  5. The minimum amount of resources required for transactions at any time in the system is calculated. As a result of this calculation, the use of resources in the system is optimized and the risk of deadlock is reduced.

Algorithm Complexity

The time complexity of the Banker’s Algorithm is O(n^2) or less, where n represents the number of transactions in the system.

Usage areas

Banker’s Algorithm is especially used in multiprocessor systems and distributed systems. For example, in multi-user operating systems, resources can be requested by more than one user at the same time. The Banker’s Algorithm manages these demands and optimizes performance in the system by allocating resources effectively.

Another example is database management systems. Multiple users may require database resources, and these resources need to be managed effectively. The Banker’s Algorithm can be used to reduce the risk of deadlocks in database systems.

Banker’s Algorithm implementation in GoLang:

package main

import "fmt"

// Function to check if the system is in a safe state
func isSafe(processes [][]int, avail []int, need [][]int, finish []bool) bool {
    work := make([]int, len(avail))
    copy(work, avail)

    for count := 0; count < len(processes); count++ {
        found := false
        for p := 0; p < len(processes); p++ {
            if !finish[p] {
                canAllocate := true
                for r := 0; r < len(avail); r++ {
                    if need[p][r] > work[r] {
                        canAllocate = false
                        break
                    }
                }
                if canAllocate {
                    for r := 0; r < len(avail); r++ {
                        work[r] += processes[p][r]
                    }
                    finish[p] = true
                    found = true
                }
            }
        }
        if !found {
            return false
        }
    }
    return true
}

func main() {
    // Example data
    processes := [][]int{{0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}}
    avail := []int{3, 3, 2}
    max := [][]int{{7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 3, 3}}

    // Calculate need matrix
    need := make([][]int, len(processes))
    for i := range need {
        need[i] = make([]int, len(avail))
        for j := range need[i] {
            need[i][j] = max[i][j] - processes[i][j]
        }
    }

    // Initialize finish array
    finish := make([]bool, len(processes))

    // Check if system is in a safe state
    safe := isSafe(processes, avail, need, finish)

    // Print result
    if safe {
        fmt.Println("Safe state")
    } else {
        fmt.Println("Unsafe state")
    }
}

When the program is run, its output will be as follows.

Safe state or Unsafe state

The working version of the program can be accessed here.

Banker’s Algorithm is an important algorithm that helps reduce the possibility of deadlock. However, it may not always work and may affect system performance in some cases. Therefore, the system and conditions in which it will be used should be carefully evaluated. Additionally, the complexity and feasibility of the algorithm should be considered.

Resources