Skip to main content

Shortest Job First Scheduling using HEAP







// Input is from the file "input.txt" in the form (a1,t1),(a2,t2),(a3,t3)  (arrival time, time to complete ie, burst time)




import java.io.*;
import java.util.*;

public class SJFHeap {
    static class point {
        double time;
        double run;
        int no;
        double total;

        point(int i, double a, double b) {
            no = i;
            time = a;
            run = b;
            total = 0;
        }
    }

    static class MHeap {
        private point[] Heap;
        private int maxsize;
        private int size;
        public MHeap(int max) {
            maxsize = max;
            Heap = new point[maxsize];
            size = 0;
        }

        private int leftchild(int pos) {
            return 2 * pos;
        }

        private int rightchild(int pos) {
            return 2 * pos + 1;
        }

        private int parent(int pos) {
            return pos / 2;
        }

        private boolean isleaf(int pos) {
            return ((pos > size / 2) && (pos <= size));
        }

        private void swap(int pos1, int pos2) {
            point tmp;
            tmp = Heap[pos1];
            Heap[pos1] = Heap[pos2];
            Heap[pos2] = tmp;
        }

        public void insert(point elem) {
            size++;
            Heap[size] = elem;
            int current = size;
            int paren = parent(current);
            if (paren >= 1)
                while (Heap[current].run < Heap[paren].run) {
                    swap(current, paren);
                    current = parent(current);
                }
        }

        public void print() {
            int i;
            for (i = 1; i <= size; i++)
                System.out.println("(" + Heap[i].time + "," + Heap[i].run + ")");
        }

        public point removemin() {
            swap(1, size);
            size--;
            if (size != 0)
                pushdown(1);

            return Heap[size + 1];
        }

        private void pushdown(int position) {
            int smallestchild;
            while (!isleaf(position)) {
                smallestchild = leftchild(position);
                if ((smallestchild < size)
                        && (Heap[smallestchild].run > Heap[smallestchild + 1].run))
                    smallestchild = smallestchild + 1;
                if (Heap[position].run <= Heap[smallestchild].run)
                    return;
                swap(position, smallestchild);
                position = smallestchild;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        MHeap h = new MHeap(10);
        FileInputStream fstream = new FileInputStream("input.txt");
        DataInputStream in = new DataInputStream(fstream);
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        point ele;
        String strLin;
        strLin = in.readLine();
        StringTokenizer st = new StringTokenizer(strLin, " (,)");
        int mp = st.countTokens();
        point[] task = new point[mp / 2];
        point[] tem = new point[mp / 2];
        int l = 0, num;
        while (st.hasMoreTokens())
        {
            String x = st.nextToken();
            double x1 = Double.parseDouble(x);
            String y = st.nextToken();
            double y1 = Double.parseDouble(y);
            point pt = new point(l + 1, x1, y1);
            task[l] = pt;
            l++;
        }
        num = l;
        int j = 0, i = 0, killed = 0;
        double now = 0, prev = 0, diff, kill = 0;
        point pt = task[0];
        while (i != num)
        {
            now = task[i].time;
            if (i == 0)
            {
                h.insert(task[i]);
                i++;
                prev = now;
            }
            else
            {
                pt = h.removemin();
                diff = now - prev;
                if (pt.run > diff)
                {
                    pt.run = pt.run - diff;
                    h.insert(pt);
                }
                else
                {
                    pt.total = prev + pt.run - pt.time;
                    kill = prev + pt.run;
                    pt.run = 0;
                    tem[j++] = pt;
                }
                h.insert(task[i]);
                prev = kill > 0 ? kill : now;
                i++;
            }
        }

        h.insert(h.removemin());
        while (h.size != 0)
        {
            pt = h.removemin();
            pt.total = prev + pt.run - pt.time;
            tem[j++] = pt;
            prev = prev + pt.run;
        }
        for (i = 0; i < j; i++)
            System.out.println("Process-" + tem[i].no + " processed for " + tem[i].total);
    }
}

Comments

Popular posts from this blog

Ubuntu: Access a usb flash drive from the terminal

    1. Find what the drive is called You'll need to know what the drive is called to mount it. To do that fire off: sudo fdisk -l You're looking for a partition that should look something like:   /dev/sdb1 . Remember what it's called. 2. Create a mount point Create a new directory in   /media   so you can mount the drive onto the filesystem: sudo mkdir /media/usb 3. Mount! sudo mount /dev/sdb1 /media/usb When you're done, just fire off: sudo umount /media/usb Source: StackOverflow

Karabiner: Mouse/keyboard customizer for OS X

For beginners, or the one who migrated from Windows environment, Natural Gestures (Scrolling and Swiping) might be bit confusing. But, once you get familiarized with them, it may feel like "What was I doing, all those days?". It all changed, when I connected external mouse to my Macbook. When you start using that WHEEL, you will be confused. Luckily there is a setting for mouse, to change scroll behavior (natural or the other way). But, here's the catch. If you toggle that setting, it also toggles the same for TRACKPAD!!!!! I've seen that many people were freaked out and even raised BUG report to Apple. But, all those reports were closed, saying that is not a bug, but intentional feature!!! For those, who can't leave with such one-sided settings, here is a simple util, which came to my rescue: Karabiner It's simple, powerful and stable mouse/keyboard customizer for OSX. Without going into much detail, here's the configuration I used to ret

Java: Use BigInteger in for-loop

In my previous post , I mentioned a way to handle large integers by using BigInteger. Now I'm going to provide a very important usage of it. We often use for-loop. So here is the way to use it: Ordinary integers: for(int i = 1; i <= n; i++) {  //Task to do } BigInteger: for (BigInteger bi = BigInteger.valueOf(1);                 bi.compareTo(n) <= 0;                 bi = bi.add(BigInteger.ONE)) { //Task to do } here n is a BigInteger variable.