Assignment P2 - Uniprocessor Scheduling Algorithms

Due: Friday, January 24, 2020, at the start of class

You may work alone or with a partner, but you must type up the code yourself. You may also discuss the assignment at a high level with other students. You should list any student with whom you discussed the assignment, and the manner of discussion (high-level, partner, etc.) in a readme.txt file that you include with your submission.

You should submit your assignment as a .zip file on Moodle.

Parts of this assignment:

In the last programming assignment, you did some verification of existing schedules. For this assignment, you’ll be constructing the schedules yourself for three scheduling algorithms: FIFO, EDF, and RM.

Starter Code: .zip (updated instruction comments in _makeSchedulingDecision methods)

Representing a scheduling algorithm

Each scheduling algorithm you will implement is contained in a class that descends from the SchedulerAlgorithm class.

class SchedulerAlgorithm(object):
    def __init__(self, taskSet):
        self.taskSet = taskSet

        self.schedule = Schedule(None, taskSet)

In addition to the taskSet and schedule (which you’ll build by adding intervals) members, you will also have a priorityQueue member, as the first step of building the schedule is to initialize the priority queue, which calls into SchedulerAlgorithm._buildPriorityQueue. (This has been done for you.) The corresponding priority queue descends from the PriorityQueue class.

class PriorityQueue(object):
    def __init__(self, jobReleaseDict):
        """
        Builds the priority queue of all jobs.
        This will need to be sorted to match the scheduling algorithm.
        """
        self.jobs = []

        releaseTimes = sorted(jobReleaseDict.keys())
        for time in releaseTimes:
            for job in jobReleaseDict[time]:
                self.jobs.append(job)

        self._sortQueue()

    ...

    def _sortQueue(self):
        raise NotImplementedError

    def _findFirst(self, t):
        raise NotImplementedError

    def popNextJob(self, t):
        raise NotImplementedError

    def popPreemptingJob(self, t, job):
        raise NotImplementedError

Some of the PriorityQueue methods are implemented for you. Others must be implemented by all child classes. You can find more information about these in the docstrings for the methods in the child classes.

Getting started

If you want to view schedules for this assignment, you will want Pygame. You should be able to get it via pip using the command line / terminal. Here are some instructions that might help you out.

Once you have pygame, you can comment-in the lines at the bottom of each scheduler file that draw the resulting schedule. This is very helpful for debugging.

##    display = SchedulingDisplay(width=800, height=480, fps=33, scheduleData=schedule)
##    display.run()

The code for this assignmet is an extension of the code from assignment 1. However, there have been some minor changes along the way, so it is recommended that you start fresh with this code. You can replace the implementations of doesMeetDeadlines and areWcetsExceeded with your own, if you wish.

Problem 1: FIFO

The work of each scheduler is broken up into two methods. The creation of the entire schedule is handled by the buildSchedule method. This method should call _makeSchedulingDecision to determine the start of the next scheduling interval, and the job that will execute during it, if any.

For the FIFO scheduler, buildSchedule is implemented for you, as is the FifoPriorityQueue class. You should fill in the implementation of _makeSchedulingDecision:

class FifoScheduler(SchedulerAlgorithm):
    ...

    def _makeSchedulingDecision(self, t, previousJob):
        """
        Makes a scheduling decision after time t.

        t: the beginning of the previous time interval, if one exists (or 0 otherwise)
        previousJob: the job that was previously executing, and will either complete or be preempted

        returns: (ScheduleInterval instance, Job instance of new job to execute)
        """
        # TODO: make a scheduling decision at the next scheduling time point after time t.
        # Let's call this new time nextTime.
        #
        # If there was no previous job, be sure to choose the next job from the priority queue at or after time t.
        # If there was a previous job, choose the highest-priority job from the priority queue of those released at or before time nextTime.
        #
        # Note that if there was a previous job but when it finishes, no more jobs are ready (released prior to that time),
        # then there should be no job associated with the new interval.  The ScheduleInterval constructor will handle this, you
        # just have to provide it with None rather than a job.
        #
        # Once you have the new job to execute (if any), build the interval (which starts at nextTime) and return it and the new job.

        return interval, newJob

Make sure to carefully read the buildSchedule method so that you understand what is provided to the _makeSchedulingDecision method, and how its output is used.

Also, there are some new methods in the ScheduleInterval class that might help you out:

class ScheduleInterval(object):
    def __init__(self, intervalDict=None):
        if intervalDict is not None:
            # Parse the JSON dictionary
            ...
        else:
            # Default values, needs to be updated
            self.startTime = -1.0
            self.taskId = -1
            self.jobId = -1
            self.didPreemptPrevious = False

    def updateIntervalEnd(self, endTime, didJobComplete):
        self.endTime = endTime
        self.jobCompleted = didJobComplete and not self.taskId == 0 # "idle" jobs don't complete

    def intialize(self, startTime, job, didPreemptPrevious):
        self.startTime = startTime

        if job is not None:
            self.taskId = job.task.id
            self.jobId = job.id
        else:
            self.taskId = 0
            self.jobId = -1

        self.didPreemptPrevious = didPreemptPrevious

Problem 2: EDF (preemptive)

For the EDF scheduler, the priority queue is still given to you (including the change in logic to handle prioritizing by absolute deadline rather than release time, and the more complex popPreemptingJob).

However, you will have to implement both the buildSchedule and _makeSchedulingDecision methods of the EdfScheduler class. Make sure to spend some time thinking about how these methods need to differ from FIFO.

class EdfScheduler(SchedulerAlgorithm):
    def __init__(self, taskSet):
        SchedulerAlgorithm.__init__(self, taskSet)

    def buildSchedule(self, startTime, endTime):
        self._buildPriorityQueue(EdfPriorityQueue)

        # TODO: build a scheduling using EDF, using _makeSchedulingDecision() to determine
        # the next decision to be made (think about how this differs from FIFO)

        return self.schedule

    def _makeSchedulingDecision(self, t, previousJob):
        """
        Makes a scheduling decision after time t.

        t: the beginning of the previous time interval, if one exists (or 0 otherwise)
        previousJob: the job that was previously executing, and will either complete or be preempted

        returns: (ScheduleInterval instance, Job instance of new job to execute)
        """
        # TODO: make a scheduling decision at the next scheduling time point after time t.
        # Let's call this new time nextTime.
        #
        # If there was no previous job, be sure to choose the next job from the priority queue at or after time t.
        # If there was a previous job, choose the highest-priority job from the priority queue of those released at or before time nextTime.
        # Make sure to handle preemptions properly!
        #
        # Note that if there was a previous job but when it finishes, no more jobs are ready (released prior to that time),
        # then there should be no job associated with the new interval.  The ScheduleInterval constructor will handle this, you
        # just have to provide it with None rather than a job.
        #
        # Once you have the new job to execute (if any), build the interval (which starts at nextTime) and return it and the new job.

        return interval, newJob

There are a couple of new methods in the Job class that might help you track the work of jobs that have been preempted:

class Job(object):
    def __init__(self, task, jobId, releaseTime):
        ...
        self.remainingTime = self.task.wcet

    def execute(self, time):
        executionTime = min(self.remainingTime, time)
        self.remainingTime -= executionTime
        return executionTime

    def executeToCompletion(self):
        return self.execute(self.remainingTime)

    def isCompleted(self):
        return self.remainingTime == 0

Problem 3: RM

For the Rate Monotonic scheduler, you should implement both the priority queue methods and the two methods in the RmScheduler class. Make sure to think very carefully about what needs to change between EDF and RM, given that both are preemptive scheduling algorithms.

class RmPriorityQueue(PriorityQueue):
    def __init__(self, jobReleaseDict):
        """
        Creates a priority queue of jobs ordered by period.
        """
        PriorityQueue.__init__(self, jobReleaseDict)

    def _sortQueue(self):
        # RM orders by period
        # TODO: implement this!
        raise NotImplementedError

    def _findFirst(self, t):
        """
        Returns the index of the highest-priority job released at or before t,
        or -1 if the queue is empty or if all remaining jobs are released after t.
        """
        # TODO: implement this!
        raise NotImplementedError

    def popNextJob(self, t):
        """
        Removes and returns the highest-priority job of those released at or after t,
        or None if no jobs are released at or after t.
        """
        # TODO: implement this!
        raise NotImplementedError

    def popPreemptingJob(self, t, job):
        """
        Removes and returns the job that will preempt job 'job' after time 't', or None
        if no such preemption will occur (i.e., if no higher-priority jobs
        are released before job 'job' will finish executing).

        t: the time after which a preemption may occur
        job: the job that is executing at time 't', and which may be preempted
        """
        # TODO: implement this!
        raise NotImplementedError

class RmScheduler(SchedulerAlgorithm):
    def __init__(self, taskSet):
        SchedulerAlgorithm.__init__(self, taskSet)

    def buildSchedule(self, startTime, endTime):
        self._buildPriorityQueue(RmPriorityQueue)

        # TODO: build a scheduling using RM, using _makeSchedulingDecision() to determine
        # the next decision to be made (think about how this differs from FIFO/EDF)

        return self.schedule

    def _makeSchedulingDecision(self, t, previousJob):
        """
        Makes a scheduling decision after time t.

        t: the beginning of the previous time interval, if one exists (or 0 otherwise)
        previousJob: the job that was previously executing, and will either complete or be preempted

        returns: (ScheduleInterval instance, Job instance of new job to execute)
        """
        # TODO: make a scheduling decision at the next scheduling time point after time t.
        # Let's call this new time nextTime.
        #
        # If there was no previous job, be sure to choose the next job from the priority queue at or after time t.
        # If there was a previous job, choose the highest-priority job from the priority queue of those released at or before time nextTime.
        # Make sure to handle preemptions properly!
        #
        # Note that if there was a previous job but when it finishes, no more jobs are ready (released prior to that time),
        # then there should be no job associated with the new interval.  The ScheduleInterval constructor will handle this, you
        # just have to provide it with None rather than a job.
        #
        # Once you have the new job to execute (if any), build the interval (which starts at nextTime) and return it and the new job.

        return interval, newJob

Try making your own test cases!

Take a look at the file hwp2_test1.json. This task set is based on Figure 4.13 in the textbook. Now that you have seen the notation for periodic tasks, you should easily be able to create your own test cases as .json files.

What you should submit

You should submit a single .zip file on Moodle. It should contain the following files:

  • readme.txt (collaboration statement listing collaborators and form of collaboration)
  • fifo.py
  • edf.py
  • rm.py
  • Any new .json files that you chose to create for testing (optional)

An example readme.txt file might be the following:

For this assignment, I collaborated with:
* Colin - partner
* Therese - discussed the difference between relative and absolute deadlines

If you did not collaborate with anyone, you should say so:

For this assignment, I worked alone.