Introduction
./
：
Requirement
2/7/2018 Programming Assignment 1 - Scheduling Simulation
1/5
Programming Assignment 1 ‐ Scheduling Simula?on
Due Monday by 11:59pm Points 100 Submitting a file upload File Types zip
Available until Feb 14 at 11:59pm
Submit Assignment
Updates
20180203: added information about output validator
20180130: updated sample outputs to fix bug in SPN output
Introduc?on
In this programming assignment, you’ll implement two scheduling algorithms (RoundRobin and Shortest
Job Next) and run them on a specified mix of processes. The input to the program will specify scheduler
parameters such as the time slice (for preemptive scheduling algorithms) and the length of time that a
process is unavailable to run when it blocks. Input will also include a list of processes to be scheduled.
Command Line
Your program should accept three arguments on the command line:
1. The input file name
2. block_duration: the decimal integer time length that a process is unavailable to run after it blocks
3. time_slice: the decimal integer length of the time slice for the RoundRobin scheduler
Input Format
The input file, specified as the first command line argument, contains the list of processes to schedule.
All numeric values in the input file are decimal integers. The time unit doesn’t matter; you can think of it as
milliseconds.
This input file will contain 1 line per process. Lines will be sorted in increasing order of arrival time in the
system. Each line will have the following format:
name arrival_time total_time block_interval
name is a sequence of nonblank characters representing the name of the process
arrival_time is the time at which the process arrives in the system
total_time is the total amount of CPU time which will be used by the process
2/7/2018 Programming Assignment 1 - Scheduling Simulation
2/5
block_interval is the interval at which the process will block for I/O. When a process blocks, it is
unavailable to run for the time specified by block_duration in the scheduler parameter file.
Programming Task
Your program should simulate the RoundRobin (preemptive) and Shortest Process Next (nonpreemptive)
scheduling algorithms. You’ll need to maintain a simulation time in your program, starting at 0. For each
interval, determine the process to run according to the scheduling algorithm, and determine when the
interval ends, depending on the CPU time left until the process blocks, the time slice length (for Round
Robin), and when the process terminates.
For either algorithm, processes which reenter the ready queue after being blocked or entering the system
should be placed on the end of the queue.
For Shortest Process Next (SPN), use the block_interval (or the total time left, whichever is shortest) of the
processes in the ready list to determine which process to run next. You don’t need to calculate the weighted
average of past CPU time usage, since the block_interval is fixed.
You may want to look at using std::priority_queue to maintain the blocked process list and the ready list for
SPN, but this is not required.
Output Format
All output should be written to standard output. For each scheduling algorithm, a set of lines should be
written consisting of:
A single line with the name of the scheduling algorithm (RR or SPN), followed by the block_duration (for
both algorithms) and time_slice (for RR) as specified on the command line. Values should be separated
by spaces.
One line for each interval during which a process is running or the system is idle. The line should consist
of a single space, followed by the current simulation time (starting at 0), followed by the process name
(or ““ if no process is running), the length of the interval, and a status code: “B” for blocked, “S” for
time slice ended, “T” if the process terminated, or “I” for an idle interval. The fields should be separated
by the tab character, ‘\t’.
After all jobs have terminated, write a line consisting of a single space, the simulation time at which the
last job terminated, a tab character, the string ““, another tab character, and the average
turnaround time of all processes (floating point value).
Sample Input and Output
Here is a sample input file, program1_sample1.txt :
A 0 100 25
B 1 50 20
C 2 90 45
2/7/2018 Programming Assignment 1 - Scheduling Simulation
3/5
Here is a sample output from running this sample with block_duration = 20 and time_slice = 10:
RR 20 10
0 A 10 S
10 B 10 S
20 C 10 S
30 A 10 S
40 B 10 B
50 C 10 S
60 A 5 B
65 C 10 S
75 B 10 S
85 A 10 S
95 C 10 S
105 B 10 B
115 A 10 S
125 C 5 B
130 A 5 B
135 B 10 T
145 5 I
150 C 10 S
160 A 10 S
170 C 10 S
180 A 10 S
190 C 10 S
200 A 5 B
205 C 10 S
215 C 5 T
220 5 I
225 A 10 S
235 A 10 S
245 A 5 T
250 204
SPN 20
0 A 25 B
25 B 20 B
45 A 25 B
70 B 20 B
90 A 25 B
115 B 10 T
125 C 45 B
170 A 25 T
195 C 45 T
240 185.667
Here’s a sample output from the same process list, with a block_duration of 50 and a time_slice of 10:
RR 50 10
0 A 10 S
10 B 10 S
20 C 10 S
30 A 10 S
40 B 10 B
50 C 10 S
60 A 5 B
2/7/2018 Programming Assignment 1 - Scheduling Simulation
4/5
65 C 10 S
75 C 10 S
85 C 5 B
90 10 I
100 B 10 S
110 B 10 B
120 A 10 S
130 A 10 S
140 C 10 S
150 A 5 B
155 C 10 S
165 C 10 S
175 B 10 T
185 C 10 S
195 C 5 T
200 5 I
205 A 10 S
215 A 10 S
225 A 5 B
230 50 I
280 A 10 S
290 A 10 S
300 A 5 T
305 229
SPN 50
0 A 25 B
25 B 20 B
45 C 45 B
90 A 25 B
115 B 20 B
135 5 I
140 C 45 T
185 B 10 T
195 A 25 B
220 50 I
270 A 25 T
295 224
More sample inputs and output will be supplied closer to the due date.
Valida?ng Your Output
Your output may vary slightly depending on the order in which you pick from multiple jobs which are eligible
to run next under the particular scheduling algorithm. Any valid schedule for the particular algorithm is
acceptable. The RoundRobin schedules may vary significantly depending on what order jobs are returned
to the ready list.
I have supplied a program which you can run to validate your RoundRobin output. The program will read
your output file, and report whether the RoundRobin schedule appears correct (it will catch most, but not all,
errors in the schedule and give an explanation of the error found).
2/7/2018 Programming Assignment 1 - Scheduling Simulation
5/5
To run the validation program, download and unzip this file inside your virtual
machine: RR_Validate_executable.zip. You’ll see two subdirectories, “32” and “64”. Each contains an
executable file named “rr_validate”. Use the version in the “64” subdirectory if you have a 64bit virtual
machine, and the version in the “32” subdirectory if you have a 32bit virtual machine. Copy the appropriate
version of rr_validate to the directory where your input and output files are located. Then run the command
with a first argument of the input file, and the second argument of your output file. The program will analyze
your output and report if your schedule is a valid RoundRobin schedule (it will ignore the SPN schedule).
For example:
./rr_validate program1_sample1.txt your_schedule.out
The analysis will be written to standard output.
Submi?ng Your Program
Export your project from NetBeans as a zip file called Program1.zip, using File > Export Project > To ZIP…
The resulting zip file should be submitted through Canvas.
Ques?ons?
Please post questions of general interest in the Programming Assignment 1 questions, problems, and
comments discussion.