Description
1.Task:
Write a program that simulates First Come First Serve (FCFS), Round Robin (RR), Narrow Round Robin
(NRR), and Feedback constant (FB) scheduling algorithms. For each algorithm, the program should list the
order and time of the jobs being loaded in the CPU and compute the turnaround time and waiting time for
every job as well as the average turnaround time and average waiting time for the set of processes.
The average values should be consolidated in a table for easy comparison (check the sample outputs).
Two sample input data sets and the corresponding outputs have been supplied. Additional datasets will be
used to test your program. The format of the input data will be the same as in the supplied sample files.
Each input data set contains the following information (check the sample input files for exact format):
1. Time for running the dispatcher (DISP) which can be zero or more
2. For each process: process id (ID) , arrival time (Arrive) and service time (ExecSize). It can be
assumed that process P_i will always arrive before or at the same time of process P_(i+1).
Dispatcher: It is assumed that the dispatcher runs to select the next process to run. The dispatcher should
behave as follows:
(i) The time to run the dispatcher (context switching time) is fixed and taken as input (DISP) from
the input file. No other time is wasted in switching between processes other than this.
(ii) If there is only one process running in the processor and no other process is waiting in the ready
queue then there is no need to switch the process and the dispatcher will NOT run. For example,
in RR scheduling if process P1 is running in the CPU and no other process is waiting in the ready
queue then P1 will continue even after its time quantum expires – no need to interrupt P1 to send
it back to ready queue after its time quantum expires and then run the dispatcher to reload P1
from the ready queue.
(iii) If the dispatcher starts at t1 and finishes at t2 (i.e. time to run the dispatcher is t2-t1) then in that
run it will choose from the processes that have arrived at or before t1. It will not consider any
process that arrives after t1 for dispatching in that run.
(iv) If a process P1 is interrupted at t1 and another process P2 arrives at the same time t1 then the
newly arrived process P2 is added in the ready queue first and the interrupted process P1 is added
after that.
(v) If two processes Px and Py have all other properties same (e.g. arrival time) then the tie between
them is broken using their ID i.e. Px will be chosen before Py if x<y.
Some details about the scheduling algorithms are as follows:
FCFS: Standard FCFS scheduling algorithm.
RR: Standard RR scheduling algorithm with time quantum of 4 milliseconds.
NRR: NRR Scheduling is a variant of the standard Round Robin (RR) scheduling in which each process has
its own time quantum q. Each process starts with q = 4ms and q is decreases by 1ms each time the process
goes through the round robin queue, until it reaches a minimum of 2 ms. Thus, long jobs get decreasingly
shorter time slices.
FB: Standard FB constant scheduling algorithm with time quantum of 4 milliseconds and a 6 level priority
(0 is highest priority and 5 is lowest priority). No priority boosting is used.
1.1. Additional Task for COMP6240 Students: [NOT for COMP2240 students]
In addition to the above simulations, you are to implement a Round Robin (RR) scheduling simulation for a
dual processor system. Assume that two processors share the same ready queue and the time quantum for
processor 1 is 2 milliseconds and for processor 2 is 3 milliseconds.
For dispatching a process, the dispatcher will run on the processor that is idle. If both processors are idle at
the same time and there are jobs in the ready queue then at first the dispatcher will run on processor 1 and it
will dispatch a process in processor 2, if there are more processes, it will be dispatched to processor 1 in the
same run of dispatcher. If one processor becomes idle, then the dispatcher will run in that processor and will
dispatch a process for it.
Output the same data as required for the other simulations. Additionally you will need to specify in which
processor a job is assigned at a specific time [i.e. instead of T1: p1 use P1-T1: p1 to clarify that the
process 1 (p1) is running in processor 1 (P1) starting at time 1 (T1)].
2.Other Submission Requirements:
Your submission must also conform to the follow considerations.
2.1. Programming Language:
The programming language is Java, versioned as per the University Lab Environment (Note this appears to
have been rolled back on the Lab machines, which means we’re currently targeting a subversion of Java 11
– so please be conscious of this). You may only use standard Java libraries as part of your submission.
2.2. User Interface:
The output should be printed to the console, and strictly following the output samples given in the assignment
package. While there are no marks allocated specifically for the Output Format, there will be a deduction
when the result format varies from those provided.
2.3. Input and Output:
Your program will accept data from an input file of name specified as a command line argument. The sample
files datafile1.txt and datafile2.txt (containing the set1 and set2 data) are provided to
demonstrate the required input file format. Hint: the Java Scanner Library is something you will likely want
to use here!
Your submission will be tested with the above data and will also be tested with other input files.
Your program should output to standard output (this means output to the Console). Output should be strictly
in the order FCFS, RR, NRR, FB, Summary.
The sample files datafile1_output.txt and datafile2_output.txt (containing output for
datafile1.txt and datafile2.txt respectively) are provided to demonstrate the required output
(and input) format which must be strictly maintained. If output is not generated in the required format
then your program will be considered incorrect.
Two Gantt charts are provided to explain the corresponding behaviour of different algorithms and the
dispatcher for the two sample data files.
2.4. Mark Distribution:
Mark distribution can be found in the assignment feedback document (Assign1Feedback2240.pdf and
Assign1Feedback6240.pdf).
2.5. Deliverable:
1. Your submission will contain your program source code with documentation and the report (below) in
the root of the submission. These files will be zipped and submitted in an archive named
c9876543.zip (where c9876543 is your student number) – do not submit a .rar, or a .7z, or
etc.
2. Your main class should be A1.java your program will compile with the command line javac
A1.java and your program will be executed by running java A1 input.txt.
…where input.txt can be any filename – do not hardcode filenames or extensions!
Note: If your program can not be compiled and executed in the expected manner (above) then please
add a readme.txt (containing any special instructions required to compile and run the source code)
in the root of the submission. Please note that such non-standard submissions will be marked with
heavy penalty.
3. Brief 1 page (A4) report, reviewing the results from your program and any interesting observations.
Specifically, write a note about the type of testing was done, the relative performance of the algorithms
based on your implemented versions of the algorithms, any unexpected behaviour you noticed in any
of the algorithms.
NOTES:
a) Assignments submitted after the deadline (11:59 pm 26th August 2022) will have the maximum marks
available reduced by 10% per 24 hours.
b) If your assignment is not prepared and submitted following above instructions then you will lose most
of your marks despite your algorithms being correct.
Nasim and Dan
v1.0 2022-08-05
