Shortest Job First (Preemptive) Scheduling in C++

#include <bits/stdc++.h>
using namespace std;
bool compare( const pair<long long int,long long int>& x, const pair<long long int, long long int>& y )
{

    return (x.second<y.second);

}
int main()
{
    vector<pair<long long int,long long int> >a;
    vector<pair<long long int,long long int> >z;
    vector<pair<long long int,long long int> >g;
    int y[100],s[100],wt[100],w[100];
    //freopen("sjfp.txt","r",stdin);
    while(1)
    {

    long long int n,i,j,b,c,x,k=0,f,m=1,l,sum=0,prev,u,tw=0,tt=0;
    cin>>n;

    if(n==0)
    {
        break;
    }

    for(i=1;i<=n;i++)
    {
        cin>>b>>c;
        a.push_back(make_pair(b,c));

    }
    j=1;
    z.push_back(make_pair(a[0].first,a[0].second));
    z[0].second=z[0].second-1;
    k=z[0].first+1;
    memset(y,0,sizeof y);
    memset(w,0,sizeof w);
    sum=sum+1;
    y[k]=sum;
    //cout<<y[k]<<endl;
    while(j!=n)
    {
        z.push_back(make_pair(a[j].first,a[j].second));
        stable_sort(z.begin(),z.end(),compare);
        z[0].second=z[0].second-1;
        k=z[0].first+1;
        //s[k]++;
        sum=sum+1;
        y[k]=sum;
        //cout<<k<<" "<<y[k]<<endl;
        j++;
    }

    for(l=0;l<n;l++)
    {
        //cout<<"P"<<l+1<<" "<<y[l+1]<<" "<<z[l].first<<" "<<z[l].second<<endl;
    }
    prev=y[k];
    g.push_back(make_pair(1,1));
    for(l=0;l<n;l++)
    {
        k=z[l].first+1;
        //cout<<"K="<<k<<endl;
        //cout<<z[l].second<<endl;
        y[k]=prev+z[l].second;
        prev=y[k];

        //cout<<"P"<<k<<"="<<y[k]<<endl;
        g.push_back(make_pair(k,y[k]));
    }
    cout<<"Grantt Chart"<<endl<<endl;
    for(l=0;l<g.size();l++)
    {
        cout<<"P"<<g[l].first<<"="<<g[l].second<<" --> ";
    }
    cout<<endl<<endl;
    g[0].second=1;
    for(l=0;l<g.size();l++)
    {
        u=g[l].first;
        //cout<<"AT="<<u<<"="<<a[u-1].first<<endl;
        if(l==0)
        {
            wt[1]=0;
        }
        if(l>0)
        {
            wt[u]=g[l-1].second-a[u-1].first;
        }

        //cout<<"WTP"<<u<<" "<<wt[u]<<endl;
    }
    for(l=0;l<g.size();l++)
    {
         u=g[l].first;
         w[u]++;
         //cout<<u<<w[u]<<endl;
         if(w[u]>1)
         {
             wt[u]=wt[u]-g[u-1].second;
         }
    }
    cout<<"P"<<"\t"<<"AT\t"<<"BT\t"<<"WT\t"<<"TT"<<endl;
    for(l=1;l<=n;l++)
    {
        cout<<l<<"\t"<<a[l-1].first<<"\t"<<a[l-1].second<<"\t"<<wt[l]<<"\t"<<a[l-1].second+wt[l]<<endl;
        tw=tw+wt[l];
        tt=tt+a[l-1].second+wt[l];


    }
    cout<<"\nAverage Waiting Time="<<(double)tw/n<<" ms"<<endl;
    cout<<"\nAverage Turn Around Time="<<(double)tt/n<<" ms"<<endl<<endl;

    /*vector<pair<long long int,long long int> >::iterator p;
    for(p=z.begin();p!=z.end();p++)
    {

        cout<<"P"<<(p->first)+1<<" "<<p->first<<" "<<p->second<<endl;
    }*/
    a.clear();
    z.clear();
    g.clear();


    }

    return 0;




}
Share on Google Plus

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge.
    Blogger Comment
    Facebook Comment

0 comments:

Post a Comment