Shortest-Job-First Scheduling (Preemptive)


♣ Try it Out ::
#include<iostream>
#include<cstdlib>
#include<cstdio>
#define FOR(i,N) for(int i=1;i<=N;i++)
#define MAX 51
using namespace std;

class CacheMemory {

public:
    string process;
    int burst_time, arrival_time;
} P[MAX];

void sortByBurst_time(int nop)
{
    FOR(i,nop)
        for(int j=i+1; j<=nop; j++)
            if(P[i].burst_time > P[j].burst_time)
                swap(P[i], P[j]);
}

int a_time[MAX], INF = 99999999;

void sortArrival_time(int n)
{
    FOR(i,n)
        for(int j=i+1; j<=n; j++)
            if(a_time[i] > a_time[j])
                swap(a_time[i], a_time[j]);
}

int main()
{
    //freopen("sjfs_p.in", "r", stdin);

    int n; cin>>n;

    FOR(i,MAX) a_time[i] = INF;

    FOR(i,n) {
        cin>>P[i].process>>P[i].arrival_time>>P[i].burst_time;

        a_time[i] = P[i].arrival_time;
    }

    sortByBurst_time(n);
    sortArrival_time(n);

    FOR(i,n)
        if(P[i].arrival_time == 0) {
            CacheMemory Key = P[i];

            for(int j=i; j<=n; j++)
                P[j] = P[j+1];

            for(int k=n-1; k>=1; k--)
                P[k+1] = P[k];

            P[1] = Key;

            break;
        }

    cout<<"\nGrantt chart of SJF:"<<endl<<endl;
    cout<<"Process\t\tTime (milliseconds)"<<endl;
    cout<<"-------\t\t-------------------"<<endl;

    int m=2, p=0, start_time=0, end_time=0;

    while(true)
    {
        FOR(i,n) {
            if(P[i].burst_time == 0) continue;

            start_time = end_time;

            if(P[i].arrival_time>=a_time[n]) {
                end_time += P[i].burst_time;
                cout<<P[i].process<<"\t\t"<<start_time<<" - "<<end_time<<endl;
                P[i].burst_time = 0;
            } else {
                if(P[i].burst_time >= a_time[m]) {
                    end_time += a_time[m];
                    P[i].burst_time = P[i].burst_time - (end_time - start_time);
                    cout<<P[i].process<<"\t\t"<<start_time<<" - "<<end_time<<endl;
                    m++;
                } else {
                    end_time += P[i].burst_time;
                    cout<<P[i].process<<"\t\t"<<start_time<<" - "<<end_time<<endl;
                    P[i].burst_time = 0;
                }
            }
            if(P[i].burst_time == 0) p++;
            break;
        }
       if(p==n) break;
       sortByBurst_time(n);
    }
}

♣ Sample Input ::
4
P1 0 8
P2 1 4
P3 2 9
P4 3 5

♣ Sample Output ::
Grantt chart of SJF:

Process         Time (milliseconds)
-------         -------------------
P1              0 - 1
P2              1 - 3
P2              3 - 5
P4              5 - 10
P1              10 - 13
P1              13 - 17
P3              17 - 26

♣ Source Codes ::

আবূ হুরাইরাহ (রাঃ) হতে বর্ণিত আছে, তিনি বলেন, নাবী (সাল্লাল্লাহু আলাইহি ওয়াসাল্লাম) বলেছেনঃ কবিরা যা বলেছে তার মধ্যে কবি লাবীদ যা বলেছে, তা ধ্রুব সত্যঃ "জেনে রেখো, আল্লাহ ছাড়া সব কিছুই মিথ্যা।" [বুখারীঃ ৩৮৪১, মুসলিমঃ ২২৫৬]

Popular posts from this blog

C++ :: Topological Sort Algorithm (using DFS)

How to Hack Facebook Account

C++ :: Strongly Connected Components Algorithm (SCC)