Home
/
Blog
/
Developer Insights
/
Dijkstra's Banker's algorithm detailed explanation

Dijkstra's Banker's algorithm detailed explanation

Author
Arpit Mishra
Calendar Icon
December 12, 2016
Timer Icon
8 min read
Share

Even after reading many articles on Banker’s algorithm and Europe’s deadlock several times, I couldn’t get what they were about.

I didn’t understand how an algorithm could have solved with the debt crisis.

I realized I would have to go back to the basics of banking and figure out answers to these:

How do banks work? How do banks decide the loan amount? What is the Banker’s algorithm?

We will begin with the Banker’s algorithm, which will help you understand banking and “Deadlock.”

What is banker’s algorithm?

The Banker’s algorithm sometimes referred to as avoidance algorithm or Deadlock algorithm was developed by Edsger Dijkstra (another of Dijkstra’s algorithms!).

It tests the safety of allocation of predetermined maximum possible resources and then makes states to check the deadlock condition. (Wikipedia)

Banker’s algorithm explained

Let’s say you’ve got three friends (Chandler, Ross, and Joey) who need a loan to tide them over for a bit.

You have $24 with you.

Chandler needs $8 dollars, Ross needs $13, and Joey needs $10.

You already lent $6 to Chandler, $8 to Ross, and $7 to Joey.

So you are left with $24 – $21 (6+8+7) = $3

Even after giving $6 to Chandler, he still needs $2.Similarly, Ross needs $5 more and Joey $3.

Until they get the amount they need, they can neither do whatever tasks they have to nor return the amount they borrowed. (Like a true friend!)

You can pay $2 to Chandler, and wait for him to get his work done and then get back the entire $8.

Or, you can pay $3 to Joey and wait for him to pay you back after his task is done.deadlock, Banker's algorithm, Dijkstra's algorithm

You can’t pay Ross because he needs $5 and you don’t have enough.

You can pay him once Chandler or Joey returns the borrowed amount after their work is done.

This state is termed as the safe state, where everyone’s task is completed and, eventually, you get all your money back.

The second scenario –Deadlock explained

Knowing Ross needs $10 urgently, instead of giving $8, you end up giving him $10.

And you are left with only $1.

In this state, Chandler still needs $2 more, Ross needs $3 more, and Joey still needs $3 more, but now you don’t have enough money to give them and until they complete the tasks they need the money for, no money will be transferred back to you.

This kind of situation is called the Unsafe state or Deadlock state, which is solved using Banker’s Algorithm.

Let’s get back to the previous safe state.

You give $2 to Chandler and let him complete his work.

He returns your $8 which leaves you with $9. Out of this $9, you can give $5 to Ross and let him finish his task with total $13 and then return the amount to you, which can be forwarded to Joey to eventually let him complete his task.

(Once all the tasks are done, you can take Ross and Joey to Central Perk for not giving them a priority.)

The goal of the Banker’s algorithm is to handle all requests without entering into the unsafe state, also called a deadlock.

The moneylender is left with not enough money to pay the borrower and none of the jobs are complete due to insufficient funds, leaving incomplete tasks and cash stuck as bad debt.

It’s called the Banker’s algorithm because it could be used in the banking system so that banks never run out of resources and always stay in a safe state.

Banker’s Algorithm

For the banker’s algorithm to work, it should know three things:

  1. How much of each resource each person could maximum request [MAX]
  2. How much of each resource each person currently holds [Allocated]
  3. How much of each resource is available in the system for each person [Available]

So we need MAX and REQUEST.

If REQUEST is given MAX = ALLOCATED + REQUEST

NEED = MAX – ALLOCATED

A resource can be allocated only for a condition.

REQUEST<= AVAILABLE or else it waits until resources are available.

Let ‘n’ be the number of processes in the system and ‘mbe the number of resource types.

  • Available – It is a 1D array of size’m’. Available [j] = k means there are k occurrences of resource type Rj.
  • Maximum – It is a 2D array of size ‘m*n’ which represents maximum demand of a section. Max[i,j] = k means that a process i can maximum demand ‘k’ amount of resources.
  • Allocated – It is a 2D array of size ‘m*n’ which represents the number of resources allocated to each process. Allocation [i,j] =k means that a process is allocated ‘k’ amount of resources.
  • Need – 2D array of size ‘m*n’. Need [i,j] = k means a maximum resource that could be allocated.
    • Need [i,j] = Max [i,j] – Allocation[i,j]

Take another Banker’s Algorithm example in the form of the table below

Where you have 4 processes, and 3 resources (A, B, C) to be allocated.

Process
Allocated Maximum Available Need (Maximum Allocated)
A B C A B C A B C A B C
P1 0 1 0 7 5 3 3 3 2 7 4 3
P2 2 0 0 3 2 2 1 2 2
P3 4 0 1 9 0 4 5 0 3
P4 2 1 1 2 2 2 0 1 1

Need P2<Available, so we allocate resources to P2 first.

After P2 completion the table would look as

Process
Allocated Maximum Available Need (Maximum Allocated)
A B C A B C A B C A B C
P1 0 1 0 7 5 3 5 3 2 7 4 3
P3 4 0 1 9 0 4 5 0 3
P4 2 1 1 2 2 2 0 1 1

Need P4<Available, so we allocate resources to P4.

After P4 completion

Process
Allocated Maximum Available Need (Maximum Allocated)
A B C A B C A B C A B C
P1 0 1 0 7 5 3 7 4 3 7 4 3
P3 4 0 1 9 0 4 5 0 3

And P3 will be allocated before P1, which gives us the sequence P2, P4, P3, and P1 without getting into deadlock.

A state is considered safe if it is able to finish all processing tasks.

Banker’s algorithm using C++

#include <iostream>
#define MAX 20
using namespace std;

class bankers
{
    private:
        int al[MAX][MAX],m[MAX][MAX],n[MAX][MAX],avail[MAX];
        int nop,nor,k,result[MAX],pnum,work[MAX],finish[MAX];

    public:
        bankers();
        void input();
        void method();
        int search(int);
        void display();
};

bankers::bankers()
{
    k=0;
    for(int i=0;i<MAX;i++)
    {
        for(int j=0;j<MAX;j++)
        {
            al[i][j]=0;
            m[i][j]=0;
            n[i][j]=0;
        }
        avail[i]=0;
        result[i]=0;
        finish[i]=0;
    }
}

void bankers::input()
{
    int i,j;
    cout << "Enter the number of processes:";
    cin >> nop;
    cout << "Enter the number of resources:";
    cin >> nor;
    cout << "Enter the allocated resources for each process: " << endl;
    for(i=0;i<nop;i++)
    {
        cout<<"\nProcess "<<i;
        for(j=0;j<nor;j++)
        {
            cout<<"\nResource "<<j<<":";
            cin>>al[i][j];
        }
    }
    cout<<"Enter the maximum resources that are needed for each process: "<<endl;
    for(i=0;i<nop;i++)
    {
        cout<<"\nProcess "<<i;
        for(j=0;j<nor;j++)
        {
            cout<<"\nResouce "<<j<<":";
            cin>>m[i][j];
            n[i][j]=m[i][j]-al[i][j];
        }
    }
    cout << "Enter the currently available resources in the system: ";
    for(j=0;j<nor;j++)
    {
        cout<<"Resource "<<j<<":";
        cin>>avail[j];
        work[j]=-1;
    }
    for(i=0;i<nop;i++)
        finish[i]=0;
}

void bankers::method()
{
    int i=0,j,flag;
    while(1)
    {
        if(finish[i]==0)
        {
            pnum =search(i);
            if(pnum!=-1)
            {
                result[k++]=i;
                finish[i]=1;
                for(j=0;j<nor;j++)
                {
                    avail[j]=avail[j]+al[i][j];
                }
            }
        }
        i++;
        if(i==nop)
        {
            flag=0;
            for(j=0;j<nor;j++)
                if(avail[j]!=work[j])

            flag=1;
            for(j=0;j<nor;j++)
                work[j]=avail[j];

            if(flag==0)
                break;
            else
                i=0;
        }
    }
}

int bankers::search(int i)
{
    int j;
    for(j=0;j<nor;j++)
        if(n[i][j]>avail[j])
            return -1;
    return 0;
}

void bankers::display()
{
    int i,j;
    cout<<endl<<"OUTPUT:";
    cout<<endl<<"========";
    cout<<endl<<"PROCESS\t     ALLOTED\t     MAXIMUM\t     NEED";
    for(i=0;i<nop;i++)
    {
        cout<<"\nP"<<i+1<<"\t     ";
        for(j=0;j<nor;j++)
        {
            cout<<al[i][j]<<"  ";
        }
        cout<<"\t     ";
        for (j=0;j<nor;j++)
        {
            cout<<m[i][j]<<"  ";
        }
        cout<<"\t     ";
        for(j=0;j<nor;j++ )
        {
            cout<<n[i][j]<<"  ";
        }
    }
    cout<<"\nThe sequence of the safe processes are: \n";
    for(i=0;i<k;i++)
    {
        int temp = result[i]+1 ;
        cout<<"P"<<temp<<" ";
    }
    cout<<"\nThe sequence of unsafe processes are: \n";
    int flg=0;
    for (i=0;i<nop;i++)
    {
        if(finish[i]==0)
        {
        flg=1;
        }
        cout<<"P"<<i<<" ";
    }
    cout<<endl<<"RESULT:";
    cout<<endl<<"=======";
    if(flg==1)
        cout<<endl<<"The system is not in safe state and deadlock may occur!!";
    else
        cout<<endl<<"The system is in safe state and deadlock will not occur!!";
}

int main()
{
    cout<<" DEADLOCK BANKER’S ALGORITHM "<<endl;
    bankers B;
    B.input ( );
    B.method ( );
    B.display ( );
}

If you understood the process, congratulations on being a non-certified banker of the nation!

Subscribe to The HackerEarth Blog

Get expert tips, hacks, and how-tos from the world of tech recruiting to stay on top of your hiring!

Author
Arpit Mishra
Calendar Icon
December 12, 2016
Timer Icon
8 min read
Share

Hire top tech talent with our recruitment platform

Access Free Demo
Related reads

Discover more articles

Gain insights to optimize your developer recruitment process.

The Mobile Dev Hiring Landscape Just Changed

Revolutionizing Mobile Talent Hiring: The HackerEarth AdvantageThe demand for mobile applications is exploding, but finding and verifying developers with proven, real-world skills is more difficult than ever. Traditional assessment methods often fall short, failing to replicate the complexities of modern mobile development.Introducing a New Era in Mobile AssessmentAt HackerEarth, we're...

Revolutionizing Mobile Talent Hiring: The HackerEarth Advantage

The demand for mobile applications is exploding, but finding and verifying developers with proven, real-world skills is more difficult than ever. Traditional assessment methods often fall short, failing to replicate the complexities of modern mobile development.

Introducing a New Era in Mobile Assessment

At HackerEarth, we're closing this critical gap with two groundbreaking features, seamlessly integrated into our Full Stack IDE:

Article content

Now, assess mobile developers in their true native environment. Our enhanced Full Stack questions now offer full support for both Java and Kotlin, the core languages powering the Android ecosystem. This allows you to evaluate candidates on authentic, real-world app development skills, moving beyond theoretical knowledge to practical application.

Article content

Say goodbye to setup drama and tool-switching. Candidates can now build, test, and debug Android and React Native applications directly within the browser-based IDE. This seamless, in-browser experience provides a true-to-life evaluation, saving valuable time for both candidates and your hiring team.

Assess the Skills That Truly Matter

With native Android support, your assessments can now delve into a candidate's ability to write clean, efficient, and functional code in the languages professional developers use daily. Kotlin's rapid adoption makes proficiency in it a key indicator of a forward-thinking candidate ready for modern mobile development.

Breakup of Mobile development skills ~95% of mobile app dev happens through Java and Kotlin
This chart illustrates the importance of assessing proficiency in both modern (Kotlin) and established (Java) codebases.

Streamlining Your Assessment Workflow

The integrated mobile emulator fundamentally transforms the assessment process. By eliminating the friction of fragmented toolchains and complex local setups, we enable a faster, more effective evaluation and a superior candidate experience.

Old Fragmented Way vs. The New, Integrated Way
Visualize the stark difference: Our streamlined workflow removes technical hurdles, allowing candidates to focus purely on demonstrating their coding and problem-solving abilities.

Quantifiable Impact on Hiring Success

A seamless and authentic assessment environment isn't just a convenience, it's a powerful catalyst for efficiency and better hiring outcomes. By removing technical barriers, candidates can focus entirely on demonstrating their skills, leading to faster submissions and higher-quality signals for your recruiters and hiring managers.

A Better Experience for Everyone

Our new features are meticulously designed to benefit the entire hiring ecosystem:

For Recruiters & Hiring Managers:

  • Accurately assess real-world development skills.
  • Gain deeper insights into candidate proficiency.
  • Hire with greater confidence and speed.
  • Reduce candidate drop-off from technical friction.

For Candidates:

  • Enjoy a seamless, efficient assessment experience.
  • No need to switch between different tools or manage complex setups.
  • Focus purely on showcasing skills, not environment configurations.
  • Work in a powerful, professional-grade IDE.

Unlock a New Era of Mobile Talent Assessment

Stop guessing and start hiring the best mobile developers with confidence. Explore how HackerEarth can transform your tech recruiting.

Vibe Coding: Shaping the Future of Software

A New Era of CodeVibe coding is a new method of using natural language prompts and AI tools to generate code. I have seen firsthand that this change makes software more accessible to everyone. In the past, being able to produce functional code was a strong advantage for developers. Today,...

A New Era of Code

Vibe coding is a new method of using natural language prompts and AI tools to generate code. I have seen firsthand that this change makes software more accessible to everyone. In the past, being able to produce functional code was a strong advantage for developers. Today, when code is produced quickly through AI, the true value lies in designing, refining, and optimizing systems. Our role now goes beyond writing code; we must also ensure that our systems remain efficient and reliable.

From Machine Language to Natural Language

I recall the early days when every line of code was written manually. We progressed from machine language to high-level programming, and now we are beginning to interact with our tools using natural language. This development does not only increase speed but also changes how we approach problem solving. Product managers can now create working demos in hours instead of weeks, and founders have a clearer way of pitching their ideas with functional prototypes. It is important for us to rethink our role as developers and focus on architecture and system design rather than simply on typing c

The Promise and the Pitfalls

I have experienced both sides of vibe coding. In cases where the goal was to build a quick prototype or a simple internal tool, AI-generated code provided impressive results. Teams have been able to test new ideas and validate concepts much faster. However, when it comes to more complex systems that require careful planning and attention to detail, the output from AI can be problematic. I have seen situations where AI produces large volumes of code that become difficult to manage without significant human intervention.

AI-powered coding tools like GitHub Copilot and AWS’s Q Developer have demonstrated significant productivity gains. For instance, at the National Australia Bank, it’s reported that half of the production code is generated by Q Developer, allowing developers to focus on higher-level problem-solving . Similarly, platforms like Lovable enable non-coders to build viable tech businesses using natural language prompts, contributing to a shift where AI-generated code reduces the need for large engineering teams. However, there are challenges. AI-generated code can sometimes be verbose or lack the architectural discipline required for complex systems. While AI can rapidly produce prototypes or simple utilities, building large-scale systems still necessitates experienced engineers to refine and optimize the code.​

The Economic Impact

The democratization of code generation is altering the economic landscape of software development. As AI tools become more prevalent, the value of average coding skills may diminish, potentially affecting salaries for entry-level positions. Conversely, developers who excel in system design, architecture, and optimization are likely to see increased demand and compensation.​
Seizing the Opportunity

Vibe coding is most beneficial in areas such as rapid prototyping and building simple applications or internal tools. It frees up valuable time that we can then invest in higher-level tasks such as system architecture, security, and user experience. When used in the right context, AI becomes a helpful partner that accelerates the development process without replacing the need for skilled engineers.

This is revolutionizing our craft, much like the shift from machine language to assembly to high-level languages did in the past. AI can churn out code at lightning speed, but remember, “Any fool can write code that a computer can understand. Good programmers write code that humans can understand.” Use AI for rapid prototyping, but it’s your expertise that transforms raw output into robust, scalable software. By honing our skills in design and architecture, we ensure our work remains impactful and enduring. Let’s continue to learn, adapt, and build software that stands the test of time.​

Ready to streamline your recruitment process? Get a free demo to explore cutting-edge solutions and resources for your hiring needs.

Guide to Conducting Successful System Design Interviews in 2025

What is Systems Design?Systems Design is an all encompassing term which encapsulates both frontend and backend components harmonized to define the overall architecture of a product.Designing robust and scalable systems requires a deep understanding of application, architecture and their underlying components like networks, data, interfaces and modules.Systems Design, in its...

What is Systems Design?

Systems Design is an all encompassing term which encapsulates both frontend and backend components harmonized to define the overall architecture of a product.

Designing robust and scalable systems requires a deep understanding of application, architecture and their underlying components like networks, data, interfaces and modules.

Systems Design, in its essence, is a blueprint of how software and applications should work to meet specific goals. The multi-dimensional nature of this discipline makes it open-ended – as there is no single one-size-fits-all solution to a system design problem.

What is a System Design Interview?

Conducting a System Design interview requires recruiters to take an unconventional approach and look beyond right or wrong answers. Recruiters should aim for evaluating a candidate’s ‘systemic thinking’ skills across three key aspects:

How they navigate technical complexity and navigate uncertainty
How they meet expectations of scale, security and speed
How they focus on the bigger picture without losing sight of details

This assessment of the end-to-end thought process and a holistic approach to problem-solving is what the interview should focus on.

What are some common topics for a System Design Interview

System design interview questions are free-form and exploratory in nature where there is no right or best answer to a specific problem statement. Here are some common questions:

How would you approach the design of a social media app or video app?

What are some ways to design a search engine or a ticketing system?

How would you design an API for a payment gateway?

What are some trade-offs and constraints you will consider while designing systems?

What is your rationale for taking a particular approach to problem solving?

Usually, interviewers base the questions depending on the organization, its goals, key competitors and a candidate’s experience level.

For senior roles, the questions tend to focus on assessing the computational thinking, decision making and reasoning ability of a candidate. For entry level job interviews, the questions are designed to test the hard skills required for building a system architecture.

The Difference between a System Design Interview and a Coding Interview

If a coding interview is like a map that takes you from point A to Z – a systems design interview is like a compass which gives you a sense of the right direction.

Here are three key difference between the two:

Coding challenges follow a linear interviewing experience i.e. candidates are given a problem and interaction with recruiters is limited. System design interviews are more lateral and conversational, requiring active participation from interviewers.

Coding interviews or challenges focus on evaluating the technical acumen of a candidate whereas systems design interviews are oriented to assess problem solving and interpersonal skills.

Coding interviews are based on a right/wrong approach with ideal answers to problem statements while a systems design interview focuses on assessing the thought process and the ability to reason from first principles.

How to Conduct an Effective System Design Interview

One common mistake recruiters make is that they approach a system design interview with the expectations and preparation of a typical coding interview.
Here is a four step framework technical recruiters can follow to ensure a seamless and productive interview experience:

Step 1: Understand the subject at hand

  • Develop an understanding of basics of system design and architecture
  • Familiarize yourself with commonly asked systems design interview questions
  • Read about system design case studies for popular applications
  • Structure the questions and problems by increasing magnitude of difficulty

Step 2: Prepare for the interview

  • Plan the extent of the topics and scope of discussion in advance
  • Clearly define the evaluation criteria and communicate expectations
  • Quantify constraints, inputs, boundaries and assumptions
  • Establish the broader context and a detailed scope of the exercise

Step 3: Stay actively involved

  • Ask follow-up questions to challenge a solution
  • Probe candidates to gauge real-time logical reasoning skills
  • Make it a conversation and take notes of important pointers and outcomes
  • Guide candidates with hints and suggestions to steer them in the right direction

Step 4: Be a collaborator

  • Encourage candidates to explore and consider alternative solutions
  • Work with the candidate to drill the problem into smaller tasks
  • Provide context and supporting details to help candidates stay on track
  • Ask follow-up questions to learn about the candidate’s experience

Technical recruiters and hiring managers should aim for providing an environment of positive reinforcement, actionable feedback and encouragement to candidates.

Evaluation Rubric for Candidates

Facilitate Successful System Design Interview Experiences with FaceCode

FaceCode, HackerEarth’s intuitive and secure platform, empowers recruiters to conduct system design interviews in a live coding environment with HD video chat.

FaceCode comes with an interactive diagram board which makes it easier for interviewers to assess the design thinking skills and conduct communication assessments using a built-in library of diagram based questions.

With FaceCode, you can combine your feedback points with AI-powered insights to generate accurate, data-driven assessment reports in a breeze. Plus, you can access interview recordings and transcripts anytime to recall and trace back the interview experience.

Learn how FaceCode can help you conduct system design interviews and boost your hiring efficiency.

Top Products

Explore HackerEarth’s top products for Hiring & Innovation

Discover powerful tools designed to streamline hiring, assess talent efficiently, and run seamless hackathons. Explore HackerEarth’s top products that help businesses innovate and grow.
Frame
Hackathons
Engage global developers through innovation
Arrow
Frame 2
Assessments
AI-driven advanced coding assessments
Arrow
Frame 3
FaceCode
Real-time code editor for effective coding interviews
Arrow
Frame 4
L & D
Tailored learning paths for continuous assessments
Arrow
Get A Free Demo