CSCI 380 -- Lab 6

Schedulers

Due: Thursday, December 6 @ 1:10 PM

Handout

There is no handout code for this assignment; however, the trace files used for autograding are here

Objectives

• Implement various scheduling algorithms
• Design and engineer your own scheduling solutions in your choice of language

Problem Description

We have covered several different scheduling algorithms in class. You are tasked with implementing your own simulators for:

• First Come, First Serve (FCFS)
• Round Robin (RR) with specified time quantum
• Shortest Remaining Time First (SRTF) -- if there is a tie, revert to the order added (FCFS)
• Highest Priority First (HPF) -- if there is a tie in priority, revert to the order added (FCFS)

NOTE: Once a task has been scheduled for some amount of time, you do NOT need to interrupt it

Job Schedule Trace Format

Trace files have the following form:

<time1>,<duration1>,<priority1>,<tag1>
<time2>,<duration2>,<priority2>,<tag2>
<time3>,<duration3>,<priority3>,<tag3>
.
.
.
<timeN>,<durationN>,<priorityN>,<tagN>

• time -- schedule time of the job (note: this is when the job should first be introduced to the scheduler)
• duration -- how much runtime the job needs
• priority -- priority level of the job (used only for Highest Priority First [HPF])
• tag -- integer number indicating the job's ID

Output Format

Your scheduler should print out a "log" of events as a comma separated file (CSV) to stdout

We care about three types of events:

• Adding a job to the scheduler
• Running a job for a certain amount of time
• Removing a completed job from the scheduler

The output format should look like the following:

• <time>,+,<tag> -- add a job with ID <tag> to the scheduler at time <time>
• <time>,R,<tag> -- run a job with ID <tag> starting at time <time>
• <time>,-,<tag> -- remove completed job with ID <tag> from the scheduler at time <time>

NOTE: a job "completes" at the BEGINNING of the next timestep. Another job may begin execution at that time.

When multiple events occur during ONE timestep, list in the following order:

• Job completes
• Job(s) added
• Job runs

For example, the following INPUT file should yield the output further below with Round-Robin w/ Q = 10

INPUT

0,33,1,1
13,25,1,2
22,12,1,3

OUTPUT

0,+,1
0,R,1
10,R,1
13,+,2
20,R,2
22,+,3
30,R,1
40,R,3
50,R,2
60,R,1
63,-,1
63,R,3
65,-,3
65,R,2
70,-,2

Design and Implementation

I highly recommend creating some type of scheduler class where you are able to:

• add a job
• run a job for a specified amount of time
• remove a job

Ultimately, you are selecting which job to run next. You will need some sort of Queue (and perhaps a Priority Queue). You are welcome to use any standard library implementation

• std::queue or std::priority_queue in C++
• queue.Queue or queue.PriorityQueue in Python 3
• LinkedList or PriorityQueue in Java

Makefile

You need to write your own Makefile since I don't know what language you're using

Invoking make should compile/build all necessary executables

You are welcome to write a "single" program, four separate programs, or somewhere in between

NOTE: if you are writing in Python 3, you may omit Makefile

Run Scripts

You need to provide your own "wrapper" scripts for running each of the four schedulers:

• run_fcfs.sh <filename> -- scheduler with FCFS
• run_rr.sh <filename> <time_quantum> -- scheduler with RR
• run_srtf.sh <filename> -- scheduler with SRTF
• run_hpf.sh <filename> -- scheduler with HPF

For example, run_fcfs.sh could just be the following:

#!/usr/bin/env bash
java FCFS_Scheduler < $1
# this assumes your program is a Java program and reads from stdin rather than a file

And run_rr.sh could be the following:

#!/usr/bin/env bash
./rr_scheduler $1 $2
# this assumes your program is compiled and the parameter order is filename followed by time quantum

And run_hpf.sh could be:

#!/usr/bin/env bash
python hpf.py $1
# this assumes your program is a Python 3 script and the filename is passed as an argument

Submission

Include all required files:

• all source code
• Makefile
• run_fcfs.sh
• run_rr.sh
• run_srtf.sh
• run_hpf.sh

as a tar file (tar cvf <tarfile> <list_of_files>)

Upload/submit this tarfile to autolab.

Grading Criteria

This lab will be graded out of 100 points.

• 20pt -- FCFS
• 25pt -- RR
• 30pt -- SRTF
• 25pt -- HPF

My autograder essentially does the following:

make all

points = 0
for s in schedulers:
  for f in get_test_files_for(s):
    output = s.run(f)
    if output == gold_output(s, f):
      points += 5

print points