bankers_algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BankersAlgorithm:\n",
    "    def __init__(self, max_resources, allocated_resources, total_resources):\n",
    "        # Initialize the BankersAlgorithm class with the maximum resources required by each process,\n",
    "        # currently allocated resources for each process, and total available resources in the system.\n",
    "        self.max_resources = max_resources\n",
    "        self.allocated_resources = allocated_resources\n",
    "        self.total_resources = total_resources\n",
    "        self.num_processes = len(max_resources)   # Number of processes in the system\n",
    "        self.num_resources = len(total_resources) # Number of resource types in the system\n",
    "        \n",
    "        # Calculate the available resources by subtracting the currently allocated resources from the total resources\n",
    "        self.available_resources = [total_resources[j] - sum(allocated_resources[i][j] for i in range(self.num_processes))\n",
    "                                    for j in range(self.num_resources)]\n",
    "\n",
    "    def is_safe_state(self, request, process_id):\n",
    "        # Check if the requested resources exceed the maximum claim of the process\n",
    "        if any(request[j] > self.max_resources[process_id][j] for j in range(self.num_resources)):\n",
    "            return False\n",
    "\n",
    "        # Check if the requested resources exceed the available resources\n",
    "        if any(request[j] > self.available_resources[j] for j in range(self.num_resources)):\n",
    "            return False\n",
    "\n",
    "        # Temporarily allocate the requested resources to check for safety\n",
    "        for j in range(self.num_resources):\n",
    "            self.available_resources[j] -= request[j]\n",
    "            self.allocated_resources[process_id][j] += request[j]\n",
    "\n",
    "        # Perform safety check\n",
    "        is_safe = self.check_safety()\n",
    "\n",
    "        # Rollback the temporary allocation\n",
    "        for j in range(self.num_resources):\n",
    "            self.available_resources[j] += request[j]\n",
    "            self.allocated_resources[process_id][j] -= request[j]\n",
    "\n",
    "        return is_safe\n",
    "\n",
    "    def check_safety(self):\n",
    "        # Safety check to determine if the current system state is safe or not\n",
    "        work = self.available_resources[:]  # Make a copy of available resources\n",
    "        finish = [False] * self.num_processes  # Keep track of finished processes\n",
    "        safe_sequence = []  # To store the sequence of processes that can finish without deadlock\n",
    "\n",
    "        # Iterate until all processes are finished or deadlock is detected\n",
    "        while True:\n",
    "            found = False\n",
    "            for i in range(self.num_processes):\n",
    "                # Check if the current process can finish based on its needs and available resources\n",
    "                if not finish[i] and all(self.max_resources[i][j] - self.allocated_resources[i][j] <= work[j]\n",
    "                                         for j in range(self.num_resources)):\n",
    "                    # If the process can finish, update the work and finish arrays\n",
    "                    work = [work[j] + self.allocated_resources[i][j] for j in range(self.num_resources)]\n",
    "                    finish[i] = True\n",
    "                    safe_sequence.append(i)\n",
    "                    found = True\n",
    "            # If no process can finish in the current iteration, exit the loop\n",
    "            if not found:\n",
    "                break\n",
    "        \n",
    "        # If all processes are finished, the system is in a safe state\n",
    "        return all(finish)\n",
    "\n",
    "# The main function to demonstrate the Banker's algorithm\n",
    "if __name__ == \"__main__\":\n",
    "    # case 1\n",
    "    max_resources = [\n",
    "        [7, 5, 3],\n",
    "        [3, 2, 2],\n",
    "        [9, 0, 2],\n",
    "        [2, 2, 2],\n",
    "        [4, 3, 3]\n",
    "    ]\n",
    "\n",
    "    allocated_resources = [\n",
    "        [0, 1, 0],\n",
    "        [2, 0, 0],\n",
    "        [3, 0, 2],\n",
    "        [2, 1, 1],\n",
    "        [0, 0, 2]\n",
    "    ]\n",
    "\n",
    "    total_resources = [10, 5, 7]\n",
    "\n",
    "    banker = BankersAlgorithm(max_resources, allocated_resources, total_resources)\n",
    "    request = [1, 0, 2]\n",
    "    process_id = 1\n",
    "\n",
    "    if banker.is_safe_state(request, process_id):\n",
    "        print(\"Request is safe to be granted.\")\n",
    "    else:\n",
    "        print(\"Request may lead to a deadlock and cannot be granted.\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# case 2\n",
    "if __name__ == \"__main__\":\n",
    "    max_resources = [\n",
    "        [7, 5, 3],\n",
    "        [3, 2, 2],\n",
    "        [9, 0, 2],\n",
    "    ]\n",
    "\n",
    "    allocated_resources = [\n",
    "        [0, 1, 0],\n",
    "        [2, 0, 0],\n",
    "        [3, 0, 2],\n",
    "    ]\n",
    "\n",
    "    total_resources = [10, 5, 7]\n",
    "\n",
    "    banker = BankersAlgorithm(max_resources, allocated_resources, total_resources)\n",
    "    request = [5, 0, 0]\n",
    "    process_id = 0\n",
    "\n",
    "    if banker.is_safe_state(request, process_id):\n",
    "        print(\"Request is safe to be granted.\")\n",
    "    else:\n",
    "        print(\"Request may lead to a deadlock and cannot be granted.\")\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Alternative 2\n",
    "provides possible safe sequences"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_need(need, max_resources, allocated_resources):\n",
    "    # Calculate the need matrix for each process\n",
    "    for i in range(len(max_resources)):\n",
    "        for j in range(len(max_resources[0])):\n",
    "            # Need = Maximum resources required - Allocated resources\n",
    "            need[i][j] = max_resources[i][j] - allocated_resources[i][j]\n",
    "\n",
    "def is_safe_state(processes, available_resources, max_resources, allocated_resources):\n",
    "    # Initialize the need matrix with zeros\n",
    "    need = [[0 for _ in range(len(available_resources))] for _ in range(len(processes))]\n",
    "\n",
    "    # Calculate the need matrix for each process\n",
    "    calculate_need(need, max_resources, allocated_resources)\n",
    "\n",
    "    # Create a copy of available resources to keep track of available resources during simulation\n",
    "    work = available_resources[:]\n",
    "\n",
    "    # Create a list to keep track of finished processes, initially set to 0 (not finished)\n",
    "    finish = [0] * len(processes)\n",
    "\n",
    "    # Create an empty list to store the safe sequence of processes\n",
    "    safe_sequence = []\n",
    "\n",
    "    # Loop until all processes are finished or deadlock is detected\n",
    "    while True:\n",
    "        found = False\n",
    "        for p in range(len(processes)):\n",
    "            # Check if the process is not finished and if its needs can be satisfied with available resources\n",
    "            if not finish[p] and all(need[p][j] <= work[j] for j in range(len(available_resources))):\n",
    "                # Update the available resources by adding the allocated resources of the process\n",
    "                work = [work[j] + allocated_resources[p][j] for j in range(len(available_resources))]\n",
    "                # Mark the process as finished\n",
    "                finish[p] = 1\n",
    "                # Add the process to the safe sequence\n",
    "                safe_sequence.append(p)\n",
    "                found = True\n",
    "\n",
    "        # If no process can finish in the current iteration, exit the loop\n",
    "        if not found:\n",
    "            break\n",
    "\n",
    "    # If all processes are finished, the system is in a safe state\n",
    "    if all(finish):\n",
    "        print(\"System is in safe state.\")\n",
    "        print(\"Safe sequence is:\", safe_sequence)\n",
    "        return True\n",
    "    else:\n",
    "        print(\"System is not in safe state.\")\n",
    "        return False\n",
    "\n",
    "# Driver code\n",
    "if __name__ == \"__main__\":\n",
    "    processes = [0, 1, 2, 3, 4]\n",
    "    available_resources = [3, 3, 2]\n",
    "\n",
    "    max_resources = [\n",
    "        [7, 5, 3],\n",
    "        [3, 2, 2],\n",
    "        [9, 0, 2],\n",
    "        [2, 2, 2],\n",
    "        [4, 3, 3]\n",
    "    ]\n",
    "\n",
    "    allocated_resources = [\n",
    "        [0, 1, 0],\n",
    "        [2, 0, 0],\n",
    "        [3, 0, 2],\n",
    "        [2, 1, 1],\n",
    "        [0, 0, 2]\n",
    "    ]\n",
    "\n",
    "    # Check if the system is in a safe state using Banker's Algorithm\n",
    "    is_safe_state(processes, available_resources, max_resources, allocated_resources)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Alternative 3\n",
    "provides all possible safe sequences"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_available(process_id, allocated, max_resources, need, available):\n",
    "    # Check if all the available resources are greater than or equal to the process needs\n",
    "    return all(need[process_id][i] <= available[i] for i in range(len(available)))\n",
    "\n",
    "def safe_sequence(processes, allocated, max_resources, need, available, safe=[]):\n",
    "    # Check if a safe-sequence is found and display it, or recursively find more safe sequences\n",
    "    if len(safe) == len(processes):\n",
    "        # If a safe-sequence is found, display it\n",
    "        print(\"Safe sequence:\", \"->\".join(\"P\" + str(p + 1) for p in safe))\n",
    "    else:\n",
    "        for i in range(len(processes)):\n",
    "            if i not in safe and is_available(i, allocated, max_resources, need, available):\n",
    "                # Mark the process and update available resources\n",
    "                marked = safe + [i]\n",
    "                new_available = [available[j] + allocated[i][j] for j in range(len(available))]\n",
    "\n",
    "                # Recursively find safe sequences with the updated state\n",
    "                safe_sequence(processes, allocated, max_resources, need, new_available, marked)\n",
    "\n",
    "# Driver code\n",
    "if __name__ == \"__main__\":\n",
    "    # Define the processes, allocated resources, maximum resources, and available resources\n",
    "    processes = [0, 1, 2, 3]\n",
    "    allocated = [[0, 1, 0], [2, 0, 0], [3, 0, 2], [2, 1, 1]]\n",
    "    max_resources = [[7, 5, 3], [3, 2, 2], [9, 0, 2], [2, 2, 2]]\n",
    "    resources = [10, 5, 7]\n",
    "\n",
    "    # Calculate the need matrix and available resources\n",
    "    need = [[max_resources[i][j] - allocated[i][j] for j in range(len(resources))] for i in range(len(processes))]\n",
    "    available = [resources[j] - sum(allocated[i][j] for i in range(len(processes))) for j in range(len(resources))]\n",
    "\n",
    "    # Find and print all safe sequences\n",
    "    print(\"Safe sequences are:\")\n",
    "    safe_sequence(processes, allocated, max_resources, need, available)\n",
    "\n",
    "    # Calculate the total number of possible safe sequences\n",
    "    total_safe_sequences = 2 ** len(processes) - 1\n",
    "    print(\"Total safe sequences:\", total_safe_sequences)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Alternative 4\n",
    "With input"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def input_data():\n",
    "    global n, r, max_resources, allocated_resources, available_resources\n",
    "\n",
    "    print(\"********** Banker's Algorithm ************\")\n",
    "    n = int(input(\"Enter the number of Processes: \"))\n",
    "    r = int(input(\"Enter the number of resources instances: \"))\n",
    "\n",
    "    print(\"Enter the Max Matrix:\")\n",
    "    max_resources = []\n",
    "    for i in range(n):\n",
    "        max_resources.append(list(map(int, input().split())))\n",
    "\n",
    "    print(\"Enter the Allocation Matrix:\")\n",
    "    allocated_resources = []\n",
    "    for i in range(n):\n",
    "        allocated_resources.append(list(map(int, input().split())))\n",
    "\n",
    "    print(\"Enter the available Resources:\")\n",
    "    available_resources = list(map(int, input().split()))\n",
    "\n",
    "\n",
    "def show_data():\n",
    "    global n, r, max_resources, allocated_resources, available_resources\n",
    "\n",
    "    print(\"\\nProcess\\tAllocation\\tMax\\tAvailable\")\n",
    "    for i in range(n):\n",
    "        print(f\"\\nP{i+1}\\t {allocated_resources[i]} \\t{max_resources[i]}\", end=\" \")\n",
    "        if i == 0:\n",
    "            print(\"\\t\", *available_resources, end=\" \")\n",
    "\n",
    "\n",
    "def calculate_need():\n",
    "    global n, r, max_resources, allocated_resources, need\n",
    "\n",
    "    need = [[0] * r for _ in range(n)]\n",
    "\n",
    "    for i in range(n):\n",
    "        for j in range(r):\n",
    "            need[i][j] = max_resources[i][j] - allocated_resources[i][j]\n",
    "\n",
    "\n",
    "def is_available(process_id):\n",
    "    global need, available_resources\n",
    "\n",
    "    for j in range(r):\n",
    "        if need[process_id][j] > available_resources[j]:\n",
    "            return False\n",
    "\n",
    "    return True\n",
    "\n",
    "\n",
    "def banker_algorithm():\n",
    "    global n, r, max_resources, allocated_resources, available_resources, need\n",
    "\n",
    "    finish = [0] * n\n",
    "    safe_sequence = []\n",
    "    flag = True\n",
    "\n",
    "    while flag:\n",
    "        flag = False\n",
    "        for i in range(n):\n",
    "            if not finish[i] and is_available(i):\n",
    "                for j in range(r):\n",
    "                    available_resources[j] += allocated_resources[i][j]\n",
    "                finish[i] = 1\n",
    "                flag = True\n",
    "                safe_sequence.append(i)\n",
    "\n",
    "    if len(safe_sequence) == n:\n",
    "        print(\"\\nSafe sequence:\", end=\" \")\n",
    "        for i in safe_sequence:\n",
    "            print(f\"P{i+1}\", end=\"\")\n",
    "            if i != safe_sequence[-1]:\n",
    "                print(\" ->\", end=\"\")\n",
    "        print(\"\\n\\nThe system is in a safe state.\")\n",
    "    else:\n",
    "        print(\"\\nProcess P\", end=\"\")\n",
    "        for i in range(n):\n",
    "            if not finish[i]:\n",
    "                print(i + 1, end=\"\")\n",
    "                if i != n - 1:\n",
    "                    print(\" ->\", end=\"\")\n",
    "        print(\" is in deadlock.\")\n",
    "        print(\"\\n\\nThe system is in an unsafe state.\")\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    input_data()\n",
    "    show_data()\n",
    "    calculate_need()\n",
    "    banker_algorithm()\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.0"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}