A Simple Scheduler, with I/O

due Thursday, Nov. 13.

This is part 2 of the scheduler assignment. You will modify your solution to the previous assignment to support I/O operations by the Jobs. In addition, you will also convert your scheduler to be round-robin, rather than FCFS. As before, the end result should be a Gannt chart based on the actual running times of the threads.

The Details:

By completing the previous assignment you should already have most of the major parts completed for this assignment, so there shouldn't be all that much code you have to write. Instead, you're going to have to modify your existing code a bit. Notably, you'll have to make more use of your Timer objects and interrupts.

Input File:

The input file will be named scheduleInput.txt, as before, but is a bit more complicated in this assignment. Each line of input is now of the form:

jobID delayTillSubmission CPUburst [IOburst CPUburst]*

Again, the first argument will be an integer, and this must somehow be used in the name of the Job (how is up to you). The second argument is the number of milliseconds that should elapse from the submission of the Job corresponding to the previous input line until this Job is submitted to the SystemSimulator via AddNewProcess. (If this is the first line of the file, then delayTillSubmissionshould be measured from the start time of the SystemSimulator itself.

The syntax of the above statement is borrowed from the help pages in Unix: the square brackets indicate optional arguments. The asterix is the Kleene Star, such as is found in regular expressions, representing 0 or more repetitions. In other words, the input lines are the same as in the previous assignment but with the possibility of any number of pairs of IOburst and CPU burst lengths at the end of each line, specified as integers. Here is a sample input file. (As before, the times are all given in milliseconds.) Your Job threads should run until their current CPU burst is complete (again, not counting time spent on the readyQ), and at that point begin an IO burst, during which time another Job may be able to run. Upon completing the IO burst, the Job should be placed on the readyQ. (You may need to interrupt the sleeping scheduler if there are no Jobs currently running.)

Here is the output that might be generated by running on that input.

Round-Robin:

Your scheduler should be round-robin with a quantum of 100msec. For most of you this should require but a simple modification to your scheduler: instead of having the SystemSimulator sleep for an indetermine amount of time, it should sleep for only 100msec at a time. Note that the Simulator can now be "awakened" either by an interrupt or by completing its sleep period. You can execute differerent code for these two possibilities:

      try {
        sleep(quantum);
        // If we get to here, quantum has expired without an exception occurring
        ....
      }
      // N.b: during this exception handling other exceptions may be lost...

      catch (InterruptedException e) {
        // Several ways to get here: poked by Job's call to Exit, or by Submittor's

        //  providing a new Job.  Is there a Job currently running?
        .... 
      }

A significant difficulty in this assignment is to figure out a way for the Simulator/Scheduler to cause a currently running Job to suspend itself (because a quantum has expired).

Modifications to Classes

As before, all your code must be in a package named Scheduler. Here is a description of the modifications you'll want to implement in your classes.

Job extends Thread. You must provide the methods below. I will provide my own subclass (here's a simple example, MattJob) with its own run method. My subclass will override your run() method, but it is guaranteed that it will invoke remainsCPUTime at least every 10msec. If current CPU burst has expired, it will call startingIOBurst or (if this was the Job's last CPU burst) Exit.

• protected SystemSimulator getOS(); Must return the SystemSimulator object.
• Job(String description, SystemSimulator s, String name) constructor. The description is a line from the input file. (Recall that Job's constructors should invoke its superclass' constructor, as is true in most inheritance situations.)
• protected void Exit() should be last instruction in run. Exit should eventually invoke myOS.Exit();
• protected boolean remainsCPUTime() If the Simulator has requested suspension, this is an opportunity for the Job to detect it. Return false if the current CPU burst has been exhausted, else return true. Note that it is possible that this method might be executed when both a suspension has been requested by the Simulator and the current CPU burst has just been exhausted.
• protected boolean burstsRemain() Return true if CPU or IO bursts remain for the Job, else return false.
• protected int startingIOBurst() Return the duration of the next IO burst. Note that this will always be invoked just as Job begins an IO burst. The code will look like: getOS().executeIO(startingIOBurst());
• void suspendYourself() is invoked by the system simulator to request that the Job suspend itself via a subsequent call to suspendIfNecessary. Should interract with remainsCPUTime in some way.
• void resumeYourself() is invoked by the system simulator to request that a Job resume execution. You'll probably want to call interrupt() here. Should interract with remainsCPUTime in some way.
• void startYourself() is invoked by the system simulator to request that a Job begin execution of its initial CPU burst. This might include the call to Thread.start().

You will almost certainly want to use some kind of timer threads, to handle the IO operations. In my implementation I called this class IOTimer, but you are free to call yours anything you want. At the beginning of an IO, the Job creates a timer and then goes to sleep. The timer will awaken after the IO burst has expired. It can then reinsert the Job onto the readyQ, then poke the Simulator.

Scheduler: simulates the scheduler

• private readyQ;
• add(Job j) Add new job to readyQ.
• makeRun() Make next job run. You may assume the job that was running has terminated. You should remove that job from the Scheduler.
• PrintGannt() prints a Gannt chart.

SystemSimulator extends Thread: this class simulates the operating system.

• void AddNewProcess(Job j) adds the given job, j, to the ready queue. Invoked by a Submittor. Keep in mind that j might not start running immediately, depending on whether another job is already running. The simulator will eventually start the Job by invoking startYourself() on it.
• void Exit() called by a Job to indicate that it is terminating. This should be the last instruction executed by a Job's run method. This method is meant to mimic a true system call to exit(). Note that because this method will be invoked by Job, a Thread, we can use the Thread.getCurrentThread() method to get a reference to the Job that is invoking this method.
• void noMoreJobsToSubmit() called by the Submittor when the last Job has been submitted. The simulator should use this information to eventually terminate when all Jobs have finished.
• void run() The basic structure of this method is straightforward: the simulator sits in a loop, sleeping. The simulator awakens only when it is interrupted ("poked").
• long relativeTime() Return the number of milliseconds that have elapsed since this simulator began running.
• void executeIO(int msecs) should be invoked by a Job to begin its next IO burst. This method returns when it is time for the Job to begin its next CPU burst, which in no case should be in less than msec milliseconds. Create a Timer object here that will move the Job onto the ready queue after msec milliseconds, then have the Job put itself to sleep. Eventually the system simulator can interrupt this job (causing it to return from this method) via a resumeYourself invocation.
• void suspending() should be invoked by a Job to acknowledge that it is suspending itself via a sleep(). The call to sleep should probably be in the implementation of this method.

Submittor extends Thread: should submit new jobs to a SystemSimulator from time to time. It will run at a higher priority than any Jobs, but lower than the SystemSimulator.

• private SystemSimulator mySystem;
  private JobCreator myJobCreator;
• void run() Sleeps for a bit, creates a job via myJobCreator, submits this job to its system simulator, and repeats. See my boilerplate code, Submittor.java.
• Submittor(ArrayList jobDescriptions, SystemSimulator s, JobCreator progenitor) each string in the argument defines a job as specified in the assignment.

JobCreator: this class exists for but a single purpose, to create Jobs via the createJob method. I will provide my own class that extends this one (here's a small example), and that class will provide its own createJob method that will return instances of my own subclass of your Job class.

• protected SystemSimulator mySystem; (I should have made this private and provided a protected accessor function!)
• public Job createJob(String description, SystemSimulator s, String name) creates a Job (or an instance of a subclass of Job) and returns it.

Testing Your Code

You should submit all of your java files as usual. Your code should make use of the MattJob and MattJobCreator classes. I reserve the right to substitute a different version of MattJob and MattJobCreator when I run your program, but these classes will conform to these strictures:

• My MattJob constructor will invoke Job's constructor.
• MattJobCreator's constructor will invoke JobCreator's.
• My run() method is guaranteed to invoke remainsCPUTime at least every 10msecs.
• My run() will invoke getOS().executeIO(startingIOBurst()) to start IO bursts.
• My run() will invoke Exit() when burstsRemain and remainsCPUTime are both false.

I will supply an input file, named scheduleInput.txt, sconforming to the syntax described above. I will run your program and examine the resulting Gannt chart.

To Hand In:

In addition to submitting your code electronoically, you must also submit hardcopy in class, consisting of:

1. A cover page, indicating your name.
2. Second page should be the last page of output generated by your program, including the Gannt chart. If your program does not run, or there are run-time errors, provide an explanation here.
3. Hardcopy of your code.

Hints:

Here is a short tutorial on using interrupts.

You may want to use Java's built-in StreamTokenizer class to read the input file. Check out the Java documentation. Alternatively, you can use String.split(" ") to break each input line into constituent substrings.

You might want to have your Jobs invoke sleep() as part of the simulation of an IO burst, otherwise they probably shouldn't call sleep() because it might allow another Job to run when it isn't supposed to. As before, you will be using sleep in several other classes, such as Submittor, Simulator and your IOTimers.

The creation of the Gannt chart requires that you record, somehow, the actual system time (via System.currentTimeMillis() ) when a Job begins and ends. You need to figure out a way for that recording to occur for my subclass of your Job class. Consider what methods my MattJob class will inherit or invoke as locations for this recording to occur.

This link is to a document explaining the potential for null reference exceptions resulting from invoking setPriority() and "dead" threads.