Subversion Repositories programming

Rev

Rev 416 | Rev 418 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 416 Rev 417
Line 33... Line 33...
33 
 * @class CS431 Fall 2006
 33 
 * @class CS431 Fall 2006
34 
 * @author Ira W. Snyder (devel@irasnyder.com)
 34 
 * @author Ira W. Snyder (devel@irasnyder.com)
35 
 */
 35 
 */
36 
public abstract class Scheduler
 36 
public abstract class Scheduler
37 
{
 37 
{
- 
 
 38 
    /** The Processes currently waiting to enter the scheduler */
- 
 
 39 
    protected Vector<Process> waiting_queue;
- 
 
 40 
 
38 
    /** The Processes that can currently be scheduled */
 41 
    /** The Processes that can currently be scheduled */
39 
    protected Vector<Process> run_queue;
 42 
    protected Vector<Process> run_queue;
40 
 
 43 
 
41 
    /** A log of important transitions in the Scheduler */
 44 
    /** A log of important transitions in the Scheduler */
42 
    protected Vector<LogEntry> log;
 45 
    protected Vector<LogEntry> log;
Line 50... Line 53...
50 
    /**
 53 
    /**
51 
     * Constructor of the Scheduler class.
 54 
     * Constructor of the Scheduler class.
52 
     */
 55 
     */
53 
    public Scheduler ()
 56 
    public Scheduler ()
54 
    {
 57 
    {
- 
 
 58 
        this.waiting_queue = new Vector<Process> ();
55 
        this.run_queue = new Vector<Process> ();
 59 
        this.run_queue = new Vector<Process> ();
56 
        this.log = new Vector<LogEntry> ();
 60 
        this.log = new Vector<LogEntry> ();
57 
    }
 61 
    }
58 
 
 62 
 
59 
    /**
 63 
    /**
Line 74... Line 78...
74 
     * @param proc the Process to add
 78 
     * @param proc the Process to add
75 
     * @param add_time the time that this process should be added to the run queue
 79 
     * @param add_time the time that this process should be added to the run queue
76 
     */
 80 
     */
77 
    public void addProcess (Process proc, int add_time)
 81 
    public void addProcess (Process proc, int add_time)
78 
    {
 82 
    {
79 
        run_queue.add (new Process(proc));
 83 
        waiting_queue.add (new Process (proc.name, proc.timeslice, add_time));
80 
    }
 84 
    }
81 
 
 85 
 
82 
    /**
 86 
    /**
83 
     * Expire the currently running process.
 87 
     * Expire the currently running process.
84 
     * <p>
 88 
     * <p>
Line 112... Line 116...
112 
    }
 116 
    }
113 
 
 117 
 
114 
    /**
 118 
    /**
115 
     * Move a process from the run_queue to the CPU. This removes it from the
 119 
     * Move a process from the run_queue to the CPU. This removes it from the
116 
     * run_queue. Then it adds a log entry.
 120 
     * run_queue. Then it adds a log entry.
117 
     *
121 
     *
118 
     * @param proc move this process from the run_queue to the CPU
 122 
     * @param proc move this process from the run_queue to the CPU
119 
     */
 123 
     */
120 
    protected void startProcess (Process proc)
 124 
    protected void startProcess (Process proc)
121 
    {
 125 
    {
122 
        cur_proc = proc;
 126 
        cur_proc = proc;
123 
        cur_proc.started_at = cur_time;
 - 
 
124 
        run_queue.remove (cur_proc);
 127 
        run_queue.remove (cur_proc);
125 
 
 128 
 
126 
        log.add (new LogEntry (cur_proc, cur_time, LogEntry.MsgType.START));
 129 
        log.add (new LogEntry (cur_proc, cur_time, LogEntry.MsgType.START));
127 
    }
 130 
    }
128 
 
 131 
 
Line 142... Line 145...
142 
        /* Update the time */
 145 
        /* Update the time */
143 
        cur_time++;
 146 
        cur_time++;
144 
    }
 147 
    }
145 
 
 148 
 
146 
    /**
 149 
    /**
- 
 
 150 
     * Pull any Process that was delayed into the Scheduler if it is the
- 
 
 151 
     * appropriate time.
- 
 
 152 
     */
- 
 
 153 
    protected void queueWaitingProcesses ()
- 
 
 154 
    {
- 
 
 155 
        Vector<Process> wq_clone = (Vector<Process>)waiting_queue.clone ();
- 
 
 156 
 
- 
 
 157 
        for (Process p : wq_clone)
- 
 
 158 
            if (p.entered_at == cur_time)
- 
 
 159 
            {
- 
 
 160 
                run_queue.add (p);
- 
 
 161 
                waiting_queue.remove (p);
- 
 
 162 
            }
- 
 
 163 
    }
- 
 
 164 
 
- 
 
 165 
    /**
- 
 
 166 
     * Check if the Scheduler is finished running.
- 
 
 167 
     *
- 
 
 168 
     * @return true if the scheduler is finished, false otherwise
- 
 
 169 
     */
- 
 
 170 
    protected boolean schedulerFinished ()
- 
 
 171 
    {
- 
 
 172 
        if (cur_proc == null && run_queue.isEmpty() && waiting_queue.isEmpty())
- 
 
 173 
            return true;
- 
 
 174 
 
- 
 
 175 
        return false;
- 
 
 176 
    }
- 
 
 177 
 
- 
 
 178 
    /**
147 
     * Print a Gantt Chart detailing the results of this scheduler's run.
 179 
     * Print a Gantt Chart detailing the results of this scheduler's run.
148 
     */
 180 
     */
149 
    protected void printGanttChart ()
 181 
    protected void printGanttChart ()
150 
    {
 182 
    {
151 
        Vector<String> t = new Vector<String> ();
 183 
        Vector<String> t = new Vector<String> ();
Line 225... Line 257...
225 
        System.out.printf ("Average wait time: %d wait time / %d procs = %.2f\n",
 257 
        System.out.printf ("Average wait time: %d wait time / %d procs = %.2f\n",
226 
                totalwait, numprocs, (float)totalwait / (float)numprocs);
 258 
                totalwait, numprocs, (float)totalwait / (float)numprocs);
227 
    }
 259 
    }
228 
 
 260 
 
229 
    /**
 261 
    /**
- 
 
 262 
    * Find the average turnaround time of this scheduler.
- 
 
 263 
    * <p>
- 
 
 264 
    * Turnaround time is defined as the mean time from submission
- 
 
 265 
    * until completion of a process.
- 
 
 266 
    */
- 
 
 267 
    protected void printTurnaroundTimes ()
- 
 
 268 
    {
- 
 
 269 
        int totalturnaround = 0;
- 
 
 270 
        int totalprocs = 0;
- 
 
 271 
 
- 
 
 272 
        for (LogEntry e : log)
- 
 
 273 
        {
- 
 
 274 
            if (e.msg == LogEntry.MsgType.COMPLETE)
- 
 
 275 
            {
- 
 
 276 
                totalturnaround += (e.proc.finished_at - e.proc.entered_at);
- 
 
 277 
                totalprocs++;
- 
 
 278 
            }
- 
 
 279 
        }
- 
 
 280 
        System.out.printf ("Average Turnaround time: %.2f\n",
- 
 
 281 
                (float)totalturnaround / (float)totalprocs);
- 
 
 282 
    }
- 
 
 283 
 
- 
 
 284 
    /**
230 
     * Run the simulation of the scheduler. Note that this only works once,
 285 
     * Run the simulation of the scheduler. Note that this only works once,
231 
     * if you try to run it twice, it is unlikely that it will work.
 286 
     * if you try to run it twice, it is unlikely that it will work.
232 
     */
 287 
     */
233 
    public void run ()
 288 
    public void run ()
234 
    {
 289 
    {
Line 236... Line 291...
236 
        while (step ())
 291 
        while (step ())
237 
            ; // do nothing
 292 
            ; // do nothing
238 
 
 293 
 
239 
        /* Verbose print of each log entry */
 294 
        /* Verbose print of each log entry */
240 
        //for (LogEntry e : log)
 295 
        //for (LogEntry e : log)
241 
        //   System.out.println (e);
 296 
        //    System.out.println (e);
242 
 
 297 
 
243 
        /* Gantt Chart */
 298 
        /* Gantt Chart */
244 
        printGanttChart ();
 299 
        printGanttChart ();
245 
 
 300 
 
246 
        /* Print time taken */
 301 
        /* Print time taken */
247 
        printWaitTimes ();
 302 
        printWaitTimes ();
- 
 
 303 
        printTurnaroundTimes ();
248 
        System.out.println ("Simulation took " + cur_time + " time units to complete!");
 304 
        System.out.println ("Simulation took " + cur_time + " time units to complete!");
249 
    }
 305 
    }
250 
}
 306 
}
251 
 
 307 
 
252 
/* vim: set ts=4 sts=4 sw=4 expandtab: */
 308 
/* vim: set ts=4 sts=4 sw=4 expandtab: */