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: */