Algorithm for Shortest Job First with Preemption

Posted by Shray on Programmers See other posts from Programmers or by Shray
Published on 2013-10-27T07:53:10Z Indexed on 2013/10/27 10:12 UTC
Read the original article Hit count: 334

Filed under:
|
|

I want to implement a shortest job first routine using C# or C++. Priority of Jobs are based on their processing time.

Jobs are processed using a binary (min) heap. There are three types of jobs.
Type 1 is when jobs come in between every 4-6 seconds, with processing times between 4-6.
Type 2 job comes in between 8-12 seconds, with processing times between 8-12.
Type 3 job comes in between 24-26 seconds, with processing times between 14-16.

So far, I have written the binary heap functionality, but Im kinda confused on how to start processing spawn and also the processor.

#include <iostream>
#include <stdlib.h>
#include <time.h>


using namespace std;
int timecounting = 20;

struct process{
int atime;
int ptime;
int type;
};

class pque{
private:
int count;

public:
process pheap[100];
process type1[100];
process type2[100];
process type3[100];
process type4[100];


pque(){
    count = 0;

}

void swap(int a, int b){

    process tempa = pheap[a];
    process tempb = pheap[b];
    pheap[b] = tempa;
    pheap[a] = tempb;

}
void add(process c){

    int current;
    count++;
    pheap[count] = c;
    if(count > 0){
        current = count;
        while(pheap[count/2].ptime > pheap[current].ptime){
            swap(current/2, current);
            current = current/2;
        }
    }

}

void remove(){
    process temp = pheap[1]; // saves process to temporary
    pheap[1] = pheap[count]; //takes last process in heap, and puts it at the root
    int n = 1;
    int leftchild = 2*n;
    int rightchild = 2*n + 1;

    while(leftchild < count && rightchild < count)
    {
        if(pheap[leftchild].ptime > pheap[rightchild].ptime)
        {
            if(pheap[leftchild].ptime > pheap[n].ptime)
            {
                swap(leftchild, n);
                n = leftchild;
                int leftchild = 2*n;
                int rightchild = 2*n + 1;
            }
        }
        else
        {
            if(pheap[rightchild].ptime > pheap[n].ptime)
            {
                swap(rightchild, n);
                n = rightchild;
                int leftchild = 2*n;
                int rightchild = 2*n + 1;
            }
        }
    }
}

void spawn1(){

    process p;
    process p1;

    p1.atime = 0;

    int i = 0;
    srand(time(NULL));
    while(i < timecounting)
    {


        p.atime = rand()%3 + 4 + p1.atime;
        p.ptime = rand()%5 + 1;
        p1.atime = p.atime;
        p.type = 1;
        type1[i+1] = p;



        i++;
    }
}

void spawn2(){

    process p;
    process p1;

    p1.atime = 0;

    srand(time(NULL));
    int i = 0;
    while(i < timecounting)
    {


        p.atime = rand()%3 + 9 + p1.atime;
        p.ptime = rand()%5 + 6;
        p1.atime = p.atime;
        p.type = 2;
        type2[i+1] = p;

        i++;
    }
}

void spawn3(){

    process p;
    process p1;

    p1.atime = 0;
    srand(time(NULL));
    int i = 0;
    while(i < timecounting)
    {


        p.atime = rand()%3 + 25 + p1.atime;
        p.ptime = rand()%5 + 11;
        p1.atime = p.atime;
        p.type = 3;
        type3[i+1] = p;

        i++;
    }
}

void spawn4(){

    process p;
    process p1;

    p1.atime = 0;
    srand(time(NULL));
    int i = 0;
    while(i < timecounting)
    {


        p.atime = rand()%6 + 30 + p1.atime;
        p.ptime = rand()%5 + 8;
        p1.atime = p.atime;
        p.type = 4;
        type4[i+1] = p;

        i++;
    }
}

void processor()
{
    process p;
    process p1;
    p1.atime = 0;
    int n = 1;
    int n1 = 1;
    int n2 = 1;

    for(int i = 0; i<timecounting;i++)
    {

        if(type1[n].atime == i)
        {
            add(type1[n]);
            n++;
        }

        if(type2[n1].atime == i)
        {
            add(type1[n1]);
            n1++;
        }
        if(type3[n2].atime == i)
        {
            add(type1[n2]);
            n2++;
        }


        /*
        if(pheap[1].atime <= i)
        {
            while(pheap[1].atime != 0){
                pheap[1].atime--;
                i++;
            }
            remove();
        }*/
    }

}

};

© Programmers or respective owner

Related posts about c#

Related posts about c++