Bankers_Algortihm.cpp

/*

Author: @karngyan
Roll: BE/10546/17
Date: April 5, 2019
Language: C++ 14 Recomended

*/

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using vll = std::vector< ll >;
const ll MAX = 1000;
ll n , m;

ll available[MAX];
ll mx[MAX][MAX];
ll allocation[MAX][MAX];
ll need[MAX][MAX];

void run_bankers()
{
	vector<bool> finish(n , 0);

	vector<ll> safe_sequence(n);

	vector<ll> work(m);
	for(ll i = 0 ; i<m ; ++i)
		work[i] = available[i];

	ll count = 0;

	while(count < n)
	{
		bool found = false;
		for(ll i = 0 ; i<n ; i++)
		{
			if(!finish[i])
			{
				ll j;
				for(j = 0 ; j<m ; j++)
					if(need[i][j] > work[j])
						break;

				if(j == m)
				{
					for(ll k = 0 ; k<m ; k++)
						work[k] += allocation[i][k];

					safe_sequence[count++] = i;
					finish[i] = true;
					found = true;
				}	
			}
		}

		if(!found)
		{
			cout << "System is not in safe state.\n"; 
			return;
		}
	}

	cout << "System is in a safe state.\n";
	for(ll i = 0 ; i<n ; ++i)
	{
		cout << "P"<<safe_sequence[i] <<" ";
	}
	cout<<endl;
	return;
}

signed main()
{
	// freopen("/home/karn/in", "r", stdin);
 //    freopen("/home/karn/out", "w", stdout);
////////////////////////////////////////////////////////////////////////////////////////////

    cout<<"\t--Bankers Algorithm--\n\n";
    cout<<"Enter number of process: ";
    cin >> n ;

    cout<<"Enter number of resources: ";
    cin >> m ;
   
   /*
		Available Resources Input
   */
    cout<<"\nEnter Available Resources: "<<endl;
    for(ll i = 0 ; i<m ; ++i)
    	cin >> available[i];

   /*
		Maximum ALlocation Input
   */
    cout<<"\nEnter Maximum Instance of each \nresource that a process can request(Matrix):\n";
    for(ll i = 0 ; i<n ;++i)
    {
    	for(ll j = 0; j<m ; ++j)
    	{
    		cin >> mx[i][j];
    	}
    }

    /*
		Current Allocation Input
    */
    cout<<"\nEnter Current Allocation(Matrix):\n";  
    for(ll i = 0 ; i<n ;++i)
    {
    	for(ll j = 0 ; j<m ; ++j)
    	{
    		cin >> allocation[i][j];
    	}
    }

    /*
		Need Calculation
    */
    for(ll i = 0 ; i < n ; ++i)
    {
    	for(ll j = 0 ; j < m ; ++j)
    	{
    		need[i][j] = mx[i][j] - allocation[i][j];
    	}
    }

    run_bankers();



////////////////////////////////////////////////////////////////////////////////////////////

    cout<<endl<<"Time Elapsed: " << 1.0*clock() / CLOCKS_PER_SEC << " sec"<<endl;
	
	return 0;
}