A Simple Scheduler

due Friday, 3/15

This is the most difficult assignment in this course (which is why I assign it in the middle of the semester, so that you will not be busy with final projects in other classes when you are working on this!) For many of you this will be the first time you've worked extensively with another person's code. (In this case, mine.) Expect to spend more than twenty hours completing this assignment. The second part of the assignment will require another twenty hours.

Suggest using java.util.concurrent.ConcurrentLinkedQueue for readyQ

This is part 1 of a two part assignment in which you will implement a relatively complicated simulation of a process scheduler. In this assignment, you will implement just a simple first-come, first-serve (FCFS) scheduler for processes that do no I/O. Instances of the class named Job will be used to simulate the processes. Job will be a subclass of Thread. To test your code I will create a subclass of Job and see how well your scheduler executes my threads. The end result should be a Gannt chart based on the actual running times of the threads.

The Details:

All your code must be in a package named scheduler (note that the package name is not capitalized). Here is a description of the classes you should implement. You will certainly want to provide more methods than are listed here, but you must have at least these.

Job extends Thread. You must provide the methods below.

• private SystemSimulator myOS; Though my subclass won't be able to access this field, because it is private, you will need a field like this to implement Exit();
• protected int getBurstTime() An accessor, returning the CPU burst time of the job.
• synchronized protected boolean shouldRun() returns false when the Job's burst time has been exhausted.
• synchronized void pleaseStop() will be invoked when the burst time has been exhausted. This is a simple method that sets a flag which will eventually be accessed via a call to shouldRun(). I will use a timer object to call this method at the appropriate time.
• Job(String description, SystemSimulator s, String name) constructor. The description consists of two numbers x, y, where the x is a job ID (unique to each job) and y is the CPU burst duration.
• String getName() return name of the job. Note that you can choose to use the inherited Thread.getName, but if so, make sure you use the "name" argument appropriately in the Job constructor, above.
• run() Can do pretty much anything but must return after the CPU burst time has elapsed. (Note that the Job's run-clock should not start "ticking" until run() is invoked! I.e., you want to start your timer here.)
• Exit() should be last instruction in run(). Exit should eventually invoke myOS.Exit();

You should ensure that your program runs using the class (MattJob). I will replace the MattJob class with one of my own, but it is guaranteed to extend Job. My subclass will override the run() method, but it is guaranteed that my run() method will cause pleaseStop() to be invoked after the CPU burst has expired, and it will check the shouldRun() method about once every 10 milliseconds. Once shouldRun() returns false, my run()will call Exit(), just before returning (i.e., terminating).

JobTimer extends Thread: You will need this class to use my example class MattJob, though you'd need something like this anyway for your own Job class. A JobTimer has a simple purpose: once started, it runs for a fixed amount of time, at the end of which it invokes pleaseStop on a target Job. The assumption is that the target Job thread will regularly invoke shouldRun to determine when its JobTimer has "expired".

• private Job myJob
• public JobTimer(Job target, int msecs)
• public void run() Sleep for msecs. Upon awaking, invoke target.pleaseStop().

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.

• AddNewProcess(Job j) adds given job, j, to the ready set. Invoked by a Submittor. Keep in mind that j might not start running immediately, depending on whether another job is already running.
• 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.
• public 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.
• public 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").
• public long relativeTime() Return the number of milliseconds that have elapsed since this simulator began running.

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.

My boilerplate code for the driver, RunScheduler.java, is almost complete; you need only finish the file I/O component of the driver. Your driver class must be named RunScheduler. I will execute your program from the command line via: java Scheduler.RunScheduler

Input File:

The input file must be named "scheduleInput.txt". Each line of this file is of the form:

jobID delayTillSubmission CPUburst

The first argument will be an integer, and 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 CPUburst is the number of milliseconds that this Job should run until it terminates. Such time, of course, excludes any spent on the ready queue.

Here is a sample input file, scheduleInput.txt.

Output:

The output must end with some kind of a Gannt chart that identifies when each job was running. The bottom of this sample output provides an example, though your method could be different. The Gannt chart should start with the execution of the first job to arrive, and end with the termination of the last job specified in the input file. Note that it is possible that the Gannt chart must be able to show "idle" periods (if they exist), where no jobs are currently running, but the input file specifies that more are yet to arrive.

For example, suppose the input file was:

1 0 200
2 300 300
3 100 300

(Note that job #1 should finish at around time 200, but job #2 doesn't arrive until time 300.) Then the resulting Gannt chart might look something like (because you are using real-time timers, the numbers may fluctuate slightly):

GANNT CHART:
Time    TimeDelta	Job
----------------------------------------------
0	0			MattJob1
200	100			IDLE
300	300			MattJob2
600	300			MattJob3
900				Finished

Testing Your Program:

Make sure your code will compile and run using the versions of RunScheduler.java, MattJob.java, and MattJobCreator.java that are linked here. You should not have to make any changes to those files for your code to run. If your code runs properly with those, then it will probably run correctly with any other version of RunScheduler that I might provide.

To Hand In:

Submit to the assignment's drop box a zip file containing

1. All of your source code (make sure your name is in the headers of any files you have created or modified).

The source code can either be all of your .java files, or the Eclipse folder you used.

2. The testing input files you used, along with an output file consisting of the 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.

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.

At no time should Job's run() method invoke sleep(). Technically, I suppose you could, but my Job class won't, so you can't depend on an invocation of sleep() by a Job to get your system to work correctly. It's best simply to avoid using sleep() at all in this method. Note that you will be using sleep in several other classes, such as Submittor and JobTimer.

There are exactly two methods outlined above that "poke" the system (so that it can decide whether to start() another Job.) Can you see which two?

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.