Subversion Repositories programming

/*******************************************************************************
 * Scheduler.java
 *
 * Holds the Scheduler class, which has a generic scheduler class, from which
 * all schedulers should be derived.
 *
 * Copyright (c) 2006, Ira W. Snyder (devel@irasnyder.com)
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 * IN THE SOFTWARE.
 ******************************************************************************/

import java.util.Vector;

/**
 * Base class for all of the specific Schedulers used in Project #1.
 *
 * @class CS431 Fall 2006
 * @author Ira W. Snyder (devel@irasnyder.com)
 */
public abstract class Scheduler
{
    /** The Processes currently waiting to enter the scheduler */
    protected Vector<Process> waiting_queue;

    /** The Processes that can currently be scheduled */
    protected Vector<Process> run_queue;

    /** A log of important transitions in the Scheduler */
    protected Vector<LogEntry> log;

    /** The current time in this scheduler */
    protected int cur_time = 0;

    /** The process that is currently running on the CPU */
    protected Process cur_proc;

    /**
     * Constructor of the Scheduler class.
     */
    public Scheduler ()
    {
        this.waiting_queue = new Vector<Process> ();
        this.run_queue = new Vector<Process> ();
        this.log = new Vector<LogEntry> ();
    }

    /**
     * This method must be overridden by an implementer of a Scheduler. It
     * will implement the specific behaivior of the specific Scheduler that
     * is being implemented.
     *
     * @return true if we have more things to do, false if we are done
     */
    protected abstract boolean step ();

    /**
     * Add a new process to the run queue.
     * <p>
     * If you need to support time-delayed processes, then you must override
     * this method, and handle pulling them into the run_queue yourself.
     *
     * @param proc the Process to add
     * @param add_time the time that this process should be added to the run queue
     */
    public void addProcess (Process proc, int add_time)
    {
        waiting_queue.add (new Process (proc.name, proc.timeslice, add_time));
    }

    /**
     * Expire the currently running process.
     * <p>
     * This removes the current process from the CPU and re-adds it to the
     * run_queue. It also logs the expiration.
     */
    protected void expireCurrent ()
    {
        assert (cur_proc.time_left > 0);

        cur_proc.finished_at = cur_time;

        run_queue.add (cur_proc);
        log.add (new LogEntry (cur_proc, cur_time, LogEntry.MsgType.EXPIRE));
        cur_proc = null;
    }

    /**
     * Terminate the currently running process.
     * <p>
     * This should be called if the process has no time left to run.
     */
    protected void completeCurrent ()
    {
        assert (cur_proc.time_left == 0);

        cur_proc.finished_at = cur_time;

        log.add (new LogEntry (cur_proc, cur_time, LogEntry.MsgType.COMPLETE));
        cur_proc = null;
    }

    /**
     * Move a process from the run_queue to the CPU. This removes it from the
     * run_queue. Then it adds a log entry.
     *
     * @param proc move this process from the run_queue to the CPU
     */
    protected void startProcess (Process proc)
    {
        cur_proc = proc;
        run_queue.remove (cur_proc);

        log.add (new LogEntry (cur_proc, cur_time, LogEntry.MsgType.START));
    }

    /**
     * Run the current process, increment the current time, and update the wait
     * times for all of the processes that are waiting.
     */
    protected void scheduleCurrent ()
    {
        /* Update the wait times for all waiting processes */
        for (Process p : run_queue)
            p.time_wait++;

        /* Run the current process for one tick */
        cur_proc.time_left--;

        /* Update the time */
        cur_time++;
    }

    /**
     * Pull any Process that was delayed into the Scheduler if it is the
     * appropriate time.
     */
    protected void queueWaitingProcesses ()
    {
        Vector<Process> wq_clone = (Vector<Process>)waiting_queue.clone ();

        for (Process p : wq_clone)
            if (p.entered_at == cur_time)
            {
                run_queue.add (p);
                waiting_queue.remove (p);
                log.add (new LogEntry (p, cur_time, LogEntry.MsgType.ADDED));
            }
    }

    /**
     * Check if the Scheduler is finished running.
     *
     * @return true if the scheduler is finished, false otherwise
     */
    protected boolean schedulerFinished ()
    {
        if (cur_proc == null && run_queue.isEmpty() && waiting_queue.isEmpty())
            return true;

        return false;
    }

    /**
     * Print a Gantt Chart detailing the results of this scheduler's run.
     */
    protected void printGanttChart ()
    {
        Vector<String> t = new Vector<String> ();
        Vector<String> l = new Vector<String> ();

        String timeline = new String();
        String labels = new String();
        String add1 = new String();
        String add2 = new String();

        int exptime = 0;
        int templen;

        for (LogEntry e : log)
        {
            if (e.msg == LogEntry.MsgType.ADDED)
                continue;

            if (e.msg == LogEntry.MsgType.EXPIRE || e.msg == LogEntry.MsgType.COMPLETE)
            {
                exptime = e.time;
                continue;
            }

            add1 = "|---" + e.proc.name + "---";
            add2 = "" + e.time;

            for (int i=0; add2.length() < add1.length(); i++)
                add2 += " ";

            if (timeline.length() + add1.length() > 79)
            {
                t.add (timeline + "|");
                templen = labels.length() - String.valueOf(exptime).length();
                labels = labels.substring (0, templen+1) + String.valueOf(exptime);
                l.add (labels);

                /* Clear the current timeline and labels */
                timeline = new String();
                labels = new String();
            }

            timeline += add1;
            labels += add2;
        }

        /* Done, add the last values of timeline and labels to the Vectors */
        t.add (timeline + "|");
        templen = labels.length() - String.valueOf(exptime).length();
        labels = labels.substring (0, templen+1) + String.valueOf(exptime);
        l.add (labels);

        assert (l.size() == t.size());

        for (int i=0; i<l.size(); i++)
        {
            System.out.println (t.elementAt (i));
            System.out.println (l.elementAt (i));
            System.out.println ();
        }
    }

    /**
     * Find the average wait time of processes.
     */
    protected void printWaitTimes ()
    {
        int numprocs = 0;
        int totalwait = 0;

        for (LogEntry e : log)
        {
            if (e.msg == LogEntry.MsgType.COMPLETE)
            {
                numprocs++;
                totalwait += e.proc.time_wait;
            }
        }

        System.out.printf ("Average wait time: %d wait time / %d procs = %.2f\n",
                totalwait, numprocs, (float)totalwait / (float)numprocs);
    }

    /**
    * Find the average turnaround time of this scheduler.
    * <p>
    * Turnaround time is defined as the mean time from submission
    * until completion of a process.
    */
    protected void printTurnaroundTimes ()
    {
        int totalturnaround = 0;
        int totalprocs = 0;

        for (LogEntry e : log)
        {
            if (e.msg == LogEntry.MsgType.COMPLETE)
            {
                totalturnaround += (e.proc.finished_at - e.proc.entered_at);
                totalprocs++;
            }
        }
        System.out.printf ("Average Turnaround time: %.2f\n",
                (float)totalturnaround / (float)totalprocs);
    }

    /**
     * Run the simulation of the scheduler. Note that this only works once,
     * if you try to run it twice, it is unlikely that it will work.
     */
    public void run ()
    {
        /* Keep step()ing until we're done */
        while (step ())
            ; // do nothing

        /* Verbose print of each log entry */
        //for (LogEntry e : log)
        //    System.out.println (e);

        /* Gantt Chart */
        printGanttChart ();

        /* Print time taken */
        printWaitTimes ();
        printTurnaroundTimes ();
        System.out.println ("Simulation took " + cur_time + " time units to complete!");
    }
}

/* vim: set ts=4 sts=4 sw=4 expandtab: */