Algorithm for Shortest Job First with Preemption
- by Shray
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();
}*/
}
}
};
