Doing a shortest job first algorithm in javascript

Question

I am trying to simulate shortest job first technique of os using javascript, given jobs/processes, arrival time and burst time:

Checkout this link : Shortest Job First - Concept. Now I have an array:

var arr = [
    {
        "job": "j4",
        "at": 0,
        "bt": 8
    },
    {
        "job": "j2",
        "at": 2,
        "bt": 4
    },
    {
        "job": "j3",
        "at": 2,
        "bt": 5
    },
    {
        "job": "j5",
        "at": 6,
        "bt": 4
    },
    {
        "job": "j1",
        "at": 8,
        "bt": 3
    }
];

And I wanted to create a new array containing objects of processes . .

e.g

[
   {"job": "j4", "range" : "0-2"},
   {"job": "j2", "range" : "2-6"},
   {"job": "j5", "range" : "6-10"},
   {"job": "j1", "range" : "10-13"},
   {"job": "j3", "range" : "13-18"},
   {"job": "j4", "range" : "18-24"}
]

so I tried doing it, but I'm super stuck and nowhere near what I want to achieve.

for(i = 0; i < arr.length; i++) {
   var temp = [];
    for(j = arr[i].at; j < arr[i].bt; j++) {
        var clone = arr.slice(0);
        var arrived = clone.splice(0, i).filter(function( obj ) {
            return obj.at == j;
        });
        var shorter = arr[i];
        for(k = 0; k < arrived.length; k++) {
            if(arrived[k].bt < arr[i].bt) {
                shorter = arrived[k];
                arr[i].bt - (j - arr[i].at);
            }
        }
        if(shorter != arr[i]) {
            j = arr[i].bt;
        }
    }
}

EDIT replaced the new array values with the real values if solved

Time Process
 0     j4(8)
 1 
 2     j4(6), j2`(4), j3(5)
 ...
 6     j4(6), j3(5), j5(4)         ::: j2 done
 7
 8     j5`(2), j4(6), j3(5), j1(3)
 9
 10                                ::: j5 done
 ...
 13                                ::: j1 done
 ...
 18                                ::: j3 done
 ...
 24                                ::: j4 done


so the new array will be

[
   {"job": "j4", "range" : "0-2"},
   {"job": "j2", "range" : "2-6"},
   {"job": "j5", "range" : "6-10"},
   {"job": "j1", "range" : "10-13"},
   {"job": "j3", "range" : "13-18"},
   {"job": "j4", "range" : "18-24"}
]

haha, yeah, that was just a random value, jeez, i'll solve it then :D sorry — Joey Hipolito
– Joey Hipolito, Commented Oct 15, 2013 at 16:42
I don't think a simple sort of the array will do what the op wants. Since the arrival time simulates the time at which a process is inserted, it needs to have it's burst time analysed and resources allocated to it until a process with a shorter burst time is introduced. — David Barker
– David Barker, Commented Oct 15, 2013 at 16:48
updated the question and simulated it by time and process :D — Joey Hipolito
– Joey Hipolito, Commented Oct 15, 2013 at 17:01

David Barker · Accepted Answer · 2013-10-15 20:46:27Z

Here's a working SJF example I've put together in JS. I've used jQuery to get data from the master array as it was mentioned in the tag. An active object is compared to a queue and elements are shifted in and out of the queue as needed and running time is added to a final array. Hope this example helps you out in getting your code working.

JSFiddle Example

var active = undefined,
    queue = [],
    final = [],
    totalBurst = 0;

// Get the total burst time
$.map(arr, function(job, index) {
    // Add a run time variable to 
    job.runTime = job.bt;
    totalBurst += job.bt + job.at;
});

// This loop simulates time
for (var i = 0; i < totalBurst; i+=1) {
    if (typeof active === 'object') {
        active.runTime -= 1;

        if (active.runTime < 1) {
            final.push({ job : active.job, start : active.start, end : i});
            active = undefined;
        }
    }

    // Get array of jobs recieved at this time signature
    var toProcess,
        jobs = $.grep(arr, function(job, index) {
            return job.at === i;
        });

    // Merge new jobs into queue
    queue = queue.concat(jobs);    
    // Sort the queue
    queue.sort(function(a,b) {
        return a.bt < b.bt ? -1 : 1;
    });

    // Get the job to process next
    toProcess = queue.splice(0,1)[0];

    if (typeof toProcess !== 'undefined') {
        // Process active job
        if (typeof active === 'undefined' && typeof toProcess !== 'undefined') {
            // Automatically start the first job in the queue
            toProcess.start = i;
            active = toProcess;
        } else if( typeof toProcess !== 'undefined' && active.bt > toProcess.bt ) {
            // Push active time to final array
            final.push({ job : active.job, start : active.start, end : i});
            // If active still has time to run add it to queue
            if (active.runTime > 0) {
                queue.push(active);
            }

            // Create new active process
            toProcess.start = i;
            active = toProcess;
        } else if( typeof toProcess !== 'undefined') {
            // Otherwise we still have an active process
            // Push the toProcess back on the queue
            queue.push(toProcess);
        }
    }    
}

that's really cool, you really put effort on your answer, thank you!

Reinstate Monica Cellio · Accepted Answer · 2013-10-15 16:45:10Z

3

If you just want to sort them by bt, shortest to longest, then this will do it...

var arr = [
    {
        "job": "j4",
        "at": 0,
        "bt": 8
    },
    {
        "job": "j2",
        "at": 2,
        "bt": 4
    },
    {
        "job": "j3",
        "at": 2,
        "bt": 5
    },
    {
        "job": "j5",
        "at": 6,
        "bt": 4
    },
    {
        "job": "j1",
        "at": 3,
        "bt": 3
    }
];

arr.sort(function(a, b) {
    return a.bt > b.bt;
});

answered Oct 15, 2013 at 16:45

Reinstate Monica Cellio

26.2k6 gold badges54 silver badges67 bronze badges

2 Comments

Joey Hipolito Over a year ago

uhm, do you know sjf?

Reinstate Monica Cellio Over a year ago

No, I just looked at your link and figure that you'd want sorting by burst time, if you wanted the shortest first.

Collectives™ on Stack Overflow

Doing a shortest job first algorithm in javascript

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related