Due: Friday September 11, 11:59PM

Purpose

This assignment serves two purposes. The first purpose is to help you understand and scheduling algorithms. By using well known and straight forward algorithms, this assignment accomplishes a second purpose, evaluating your programming skills. If you cannot finish a working version of this assignment on time, we recommend that you take another programming course before you attempt this one.

Assignment

You will develop four schedulers: a first-come-first-serve (FCFS), a round-robin (RR), an approximation to shortest-job-first (SJF), and a multi-level feedback queue (MLFQ) scheduler with three queues. The details of RR, FCFS, SJF, and MLFQ are specified below in the implementation section.

For this and subsequent labs, you will be using a trace-driven simulator for an operating system.  Rather than implement a real operating system, which is both time-consuming and error-prone, many researchers use simulation to see if their ideas are worth implementing.  A trace is a representation of program activity, often gathered automatically from real programs.  We will be using traces to drive our simulation, that is, as input to the simulator. The simulator will interpret the trace input and drive your scheduling algorithm as appropriate.  In this lab, the trace format is close to the format for lab 4, the file system lab, so it has many features we will not use.  But this similarity will minimize the number of trace formats you will have to learn.

To test your code you should write new trace files and verify their output.  You are allowed to trade md5 checksums of trace files on the discussion boards and between people, but you are not allowed to trade output files.  DO NOT POST YOUR OUTPUT TO THE DISCUSSION BOARD.   For those not familiar, the program md5sum generates a secure checksum of a file.  Running md5sum -b <filename> on a Unix machine will generate a 128-bit hash (represented by ascii text).  It is VERY unlikely that two different files have the same md5 hash. So if H is the hash function, and H(m1) != H(m2) then it is very likely that m1 != m2. A hash acts like a fingerprint-nearly unique but much smaller than the original file. It allows you to compare output without posting the output.


Supplies (lab1.jar)

A working simulator (all source available!) which you should not change since we test your project with the original versions:

• The simulation driver (ProcessTrace.java) interprets the input file, creates the processes, creates the scheduler, creates the CPUs (each running in its own thread), and drives the simulation.  

  The notion of time in the Simulator is represented by a unit (int) called a 'tick'.  The length of a quantum, a CPU burst, and I/O burst are expressed in ticks.  Think of a tick as the unit of granularity of the decrementer (timer) that's used to periodically interrupt the CPU to let it know some small amount of time has passed; something, perhaps, in the milli-second range.
  To extract the jar file:
  %> jar -xf lab1.jar
  To build the project:
  %> javac -sourcepath given:work given/*.java work/*.java
  To run the simulator: 
  %> java -cp given:work ProcessTrace xyz.properties   (where xyz is optional and the name of the configuration file, system.properties by default).  If you are running on cygwin under Windows substitute "given;work" for given:work.
  Better yet, use Eclipse, which is available on the CS Linux machines.  Running the lab as it is distributed will give you a runtime scheduling error.  That is your cue to start coding.

You can look at the provided system.properties for interesting properties.  The best ones are

• trace_file: a string with default value simple.tr
• sched_class: a string with default value FCFS
• verbose: yes/no with default yes

We also provide two trace files with their output for each scheduling algorithm.  Your output must match these EXCATLY, or your solution will be considered incorrect.  You can use a tool such as 'diff' to ensure your output is correct.

Implementation

You will implement your schedulers, by implementing the interface IScheduler.   You must fill in the implementation of FCFS.java, RR.java, SJF.java, and MLFQ.java.

FCFS: The implementation of FCFS should be non-preemptive with an infinite quantum, i.e., it should prevent scheduling events unless the process exits or performs I/O.  To accomplish this, be sure to set each Process's quantum to Integer.MAX_VALUE. The ready queue is FIFO, and processes are always inserted at the end of the queue.

RR: The implementation of RR is preemptive, i.e., it causes scheduling events when the process' quantum expires (or the process exits or performs I/O).  All additions to the ready queue should be at its tail.  You should use a quantum of 5 ticks (which is the default for each process).

SJF: The implementation of SJF approximates the optimal shortest job first algorithm by estimating the expected length of each process's next burst. Given the expected length of the kth burst, e(k), and the actual length of the kth burst, a(k), e(k+1) = 0.4*e(k) + 0.6*a(k).

Since this requires maintaining history for a process, be sure to look at PCB.set/getObject() methods.  This algorithm is non-preemptive, with new schedule operations happening only at quantum expiration or process blocking.  New processes are placed at the end of the queue.  You should assume the expected first burst of a new process is 5 ticks.  You should assign a quantum of the expected-burst (rounded up to the nearest integer) when dispatching a process.  So, if the expected-burst is 22.3, then assign a quantum of 23 ticks.  Continue to use the same quantum until the process's burst completes.  In other words, if the calculations call for a quantum of 10, and the process's burst doesn't complete in 10 ticks (and the quantumExpired() method is therefore called), when it comes time to dispatch the process again, use the same quantum of 10. The shortest job is defined by the smallest e(k), not the time quantum. Processes with the same expected burst should be scheduled FIFO from the ready queue (oldest first).

When you recalculate the quantum for a process, you should print a message indicating the expected burst time for the process. There is a family of functions provided for this purpose, all called Stat.printMessage that you must use to print these messages. We want you to use these function to make sure the format of your output is correct. The exact function that gets called depends on the arguments. The first parameter, called type can either be "recalc" or "expected". The following summarizes the types for these arguments.
Stat.printMessage("recalc", Integer, Integer, Double) The first Integer has the value process_id, the second ticks_used_by_process, and the Double is old_quantum.
Stat.printMessage("expected", Double) Here the second argument is a Double whose value is equal to new_quantum.
The variable process_id above refers to the id of the process you are recalculating the quantum for; ticks_used_by_process is the length of the process's previous CPU burst, which you are using to recalculate the quantum; old_quantum is the length of the quantum for the previous burst; new_quantum is the recalculated quantum, which will now be used for this process.

MLFQ: The implementation of MLFQ should have three queues with quantums 5, 10, and Infinite.  Each queue of the MLFQ scheduler uses a RR scheduler.  If there are any ready processes in queue 0, MLFQ executes them, otherwise queue 1 processes are allowed to run.  If there are no ready jobs in queues 0 and 1, then processes in queue 2 can run.  Newly created processes are inserted at the end of queue 0. 

Processes are demoted to the next "higher-numbered" queue whenever you detect that their burst exceeds the quantum of their current queue.  However, processes are always demoted, if possible, when their quantum expires. Processes are promoted to the next "lower-numbered" queue whenever their burst is <= the quantum of the next-lower queue.  (Processes move up/down one queue at a time.)

Processes can only be promoted at burst complete (i.e. blocked()).  Note that, for example, a process with bursts of exactly 8 ticks will start in queue0, and then remain in queue1.

Processes completing I/O get unblocked and are added to the end of the queue to which they should next be assigned (which was decided during the time they were blocked).  If a job enters a lower queue than the one whose process is currently running it causes the scheduler to preempt the running process (see ProcessTrace.setPreemptRequest()).   This could happen if a new process enters the system when a lower priority process is running or when a process is actually promoted (i.e., added to the end of a lower-numbered queue).

You must print a message whenever you promote, demote or preempt a process. You should use Stat.printMessage for this purpose.
However, for this scheduler the first argument type has different values, explained here. The value of the first argument are: "started", "unblocked", "expired", "blocked", "interrupted", and "promoted". The second argument, again, depends on the first.
Stat.printMessage("started", Integer) Here the second argument is an Integer whose value is equal to current_pid.
Stat.printMessage("unblocked", Integer) Here the second argument is an Integer whose value is equal to current_pid.
Stat.printMessage("expired", Integer, Integer) Here the second argument is an Integer whose value is equal to pid, the thirdis equal to new_queue.
Stat.printMessage("blocked", Integer, Integer) Here the second argument is an Integer whose value is equal to pid, the third is equal to new_queue.
Stat.printMessage("interrupted", Integer, Integer) Here the second argument is an Integer whose value is equal to pid, the third is equal to new_queue.
Stat.printMessage("promoted", Integer, Integer) Here the second argument is an Integer whose value is equal to pid, the third is equal to new_queue.
The variable current_pid is the currently running pid which will be preempted; pid denotes the process that was just blocked (or was interrupted or just finished its quantum) and new_queue is the index(0-2) of the new queue this process will be assigned to after promotion or demotion.

Trace Files

The trace file consists of a list of directives.  Each directive describes a system event. The format is as follows.

pid directive(arguments)

The pid of the initial process (called init) is zero.  Like a real operating system, as part of its initialization, your OS will start the init process running.  A well formed trace file starts with an action of process 0.   Look at the examples given in your lab1.jar.

Your system supports the following directives.  The prototypes are conceptual.  See the trace file and the code for the concrete details.

compute(int data, int tick_count) This directive represents the process computing for tick_count ticks.  The data parameter is currently ignored.  It must be provided, but you can use any 8-bit integer value.  This directive requires tick_count CPU ticks to process.

read(int fd, int size, int tick_count) This directive reads size bytes from the file referred to by the file descriptor numbered fd, and starts an I/O that takes tick_count ticks.  The value of the fd and size parameter are currently ignored.  This directive requires 1 CPU tick to process.

write(int fd, int size, int tick_count) This system call writes size bytes to the file referred to by the file descriptor numbered fd, and starts an I/O that takes tick_count ticks.  The value of fd and size parameter are currently ignored.  This directive requires 1 CPU tick to process.

proc_create(int pid)  This system call creates a process with an identifier equal to  pid.  Remember that 0 is the init process that you do not have to create explicitly. This directive requires 1 CPU tick to process.

proc_kill(int pid) This system call kills the process with the identifier equal to pid.  A process may only kill itself. This directive requires 1 CPU tick to process.

Output files

These are the correct verbose output files for each scheduler using traces simple.tr and complex.tr, respectively. The files contain messages printed by the OS simulator indicating what is going on at each time tick. Your code should not print anything out (except those specified for MLFQ and SJF) unless you are debugging. Your output should match these exactly if you want to receive credit.

(simple_output_FCFS.txt): md5sum = b50aa54b5d46d015ebf0358d5b4166a9; File Size =  2460 bytes

(simple_output_RR.txt): md5sum = ea851839239f0cc79bf5591e1eba0ac4; File Size =  3167 bytes

(simple_output_SJF.txt): md5sum = 56267747b9f39b3e6920c92fbf726bf0; File Size =  3266 bytes

(simple_output_MLFQ.txt): md5sum = 6bdc3754d728f3103663981014510d59; File Size =  3179 bytes

(complex_output_FCFS.txt): md5sum = 799ba2636837d2cbb8f6796f83718fee; File Size =  276343 bytes

(complex_output_RR.txt): md5sum = dea3242e2fa2ce3d73a82bb166f6d983; File Size =  3077268 bytes

(complex_output_SJF.txt): md5sum = e7eec671fd03300a285acb4cc8583aa4; File Size =  614719 bytes

(complex_output_MLFQ.txt): md5sum = 0d12665278fb9b82e8955a37a58a7154; File Size =  375672 bytes

Instructions on how to check outputs:

• Use "md5sum -b filename" to quick check: if your md5sum output matches the given md5sum output for each output file, then fine.
• If md5sum fails, use "diff filename1 filename2" to see the difference.  I like diff -U2

Other Details and Submission Instructions

Each student must do the assignment independently, 

• Only one person turns in the assignment.
• Write a README file.

In your README file, include the following.

Name     Section

Slip days used (this project): ______ Slip days used (total): ______

On my honor, name, this programming assignment is my own work.

Total hours spent on this project: ______ 

To turn in the project, go to the work directory, which should contain FCFS.java, RR.java, SJF.java, MLFQ.java, Makefile and your README file.  In that directory type the following:

%> make turnin

or you can do it "by hand" and type

%> turnin --submit naga86 lab1 MLFQ.java FCFS.java RR.java SJF.java README

---

Useful Links:

• CS105 Java Short Course Try out assignments on this page if you have not programmed in Java before.
• Introduction to Java. A good getting started with Java reference. (You do not have to read the part about turning your Java program into an applet, since you are not required to do that for this class.)
• A Java tutorial.
• Another Java tutorial.
• Java Lectures from CS371P
• Thinking in Java, 3rd Edition, Prentice Hall, Bruce Eckel, ISBN: 0-13-027363-5 (http://www.bruceeckel.com/) (cs machine electronic edition)