Banker's Algorithm, Deadlock, Dijkstra's algorithm

Dijkstra’s Banker’s algorithm detailed explanation

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...

Arpit Mishra Author

7 mins December 17, 2016

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.

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:

How much of each resource each person could maximum request [MAX]
How much of each resource each person currently holds [Allocated]
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 ‘m’ be 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)
Process	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)
Process	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)
Process	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 ( );
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

#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!

About the author

Arpit Mishra Author

Empowering developers at HackerEarth | Fascinated with Recruiting, Candidate Experience, Branding | Digital Marketing | LinkedIn connections are awesome (Just saying!)

Dijkstra’s Banker’s algorithm detailed explanation

What is banker’s algorithm?

Banker’s algorithm explained

The second scenario – Deadlock explained

Banker’s Algorithm

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

Banker’s algorithm using C++

About the author

Related reads

Leave a Reply

Know what it takes to level up as a developer
in today's tech-powered world

Resources

Solutions

Company

Service & Support

Dijkstra’s Banker’s algorithm detailed explanation

What is banker’s algorithm?

Banker’s algorithm explained

The second scenario – Deadlock explained

Banker’s Algorithm

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

Banker’s algorithm using C++

About the author

Related reads

Leave a Reply

Know what it takes to level up as a developer in today's tech-powered world

Know what it takes to level up as a developer
in today's tech-powered world