Due: Monday, January 20, 2025, at 10:00pm

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 group of files on Gradescope. (See submission instructions, below.)

Throughout this course, we will build up a scheduling and synchronization software library. This library will make heavy use of JSON structures to respresent task systems and the resulting schedules. The JSON files are parsed into Python objects. For this assignment, you only need to know how the task set and schedule are represented in Python.

Starter code: p1.tar

Representing a task system

In class, we’ve mis-used notation a little bit. What I’ve typically called tasks are the actual execution instances themselves, which are usually called jobs.

Tasks are defined by the timing parameters of offset, period, WCET, and deadline. (We’ll talk about periods next week, but it just means that a task can repeat; aperiodic tasks are encoded here with a period of -1.) Each instance of the task, which is released at a time r_i and must complete execution by its absolute deadline d_i = r_i + D_i, is called a job. In general, we represent task parameters with capital letters, and job parameters with lowercase letters.

Tasks and jobs are defined in taskset.py. So far, we have only considered aperiodic tasks, so each task has only a single job.

A task set is comprised of multiple tasks. You can iterate through the tasks in a task set, as in the printTasks method of TaskSet:

class TaskSet(object):
    ...

    def printTasks(self):
        print("\nTask Set:")
        for task in self:
            print(task)

You can also retrieve a specific task using its ID via the getTaskById method.

A Task object contains all of the timing parameters we’ve discussed in class: WCET, offset, period, and deadline.

class Task(object):
    def __init__(self, taskDict):
        self.id = int(...)
        self.period = float(...)
        self.wcet = float(...)
        self.relativeDeadline = float(...)
        self.offset = float(...)

        ...

        self.jobs = []

You can iterate through the jobs of a task by calling the getJobs method. You can also request a specific job given the ID using the getJobById method. Again from TaskSet:

    def printJobs(self):
        print("\nJobs:")
        for task in self:
            for job in task.getJobs():
                print(job)

A job object contains the information about the task, as well as the job’s release time and absolute deadline.

class Job(object):
    def __init__(self, task, jobId, releaseTime):
        self.task = task
        self.id = jobId
        self.releaseTime = releaseTime
        self.deadline = releaseTime + task.relativeDeadline

Representing a schedule

In this assignment, you will not have to work through any scheduling decisions. Rather, you will be given the resulting schedule as a list of decisions made at given time instants. Each scheduling decision is represented by a Python ScheduleInterval object, in schedule.py:

class ScheduleInterval(object):
    def __init__(self, intervalDict):
        self.startTime = float(...)
        self.taskId = int(...)
        self.jobId = int(...)
        self.didPreemptPrevious = bool(...)

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

    def isIdle(self):
        return self.taskId == 0

A scheduling decision defines the start of an interval; the end of the interval is defined by the start of the next interval. As a result, a post-processing step after parsing the JSON scheduling decisions calls updateIntervalEnd to set the endTime and jobCompleted fields of each ScheduleInterval instance.

Additionally, each schedule ends with an “idle” interval, in which no job executes. It is also possible that a schedule may have idle intervals between task executions. You can check whether an interval is idle using the isIdle method.

A schedule itself is represented by the Schedule class. The constructor parses the JSON schedule and stores the intervals in the intervals field. You can see it used in the printIntervals method of Schedule:

    def printIntervals(self, displayIdle=True):
        print("\nScheduling intervals:")
        for interval in self.intervals:
            if not interval.isIdle() or displayIdle:
                print(interval)

Getting started

Download the starter code, and untar it to get the p1 folder:

tar xvf p1.tar

You will not need Pygame for this assignment, but you will in the future. You can run any of taskset.py, schedule.py, or display.py as-is, and it will choose the task set and schedule defined in tasksets/p1_test1.json and display some output (text for the first two, and a Pygame window for the third). You can provide a different JSON file by running it at the command line:

python3 schedule.py tasksets/p1_test2.json

Note: the command you run depends on your environment setup. It likely begins with python3, but it is possible to have configured your machine to use python to access Python 3 instead.

Part 1: Validating feasibility

In this part, you will validate that the schedule is feasible – that is, that no deadlines are missed. For this, you will need to implement the validateDeadlines method of the Schedule class. This method should return False if any deadline is missed, and True if no deadlines are missed.

    def validateDeadlines(self):
        """
        Returns a boolean indicating whether all deadlines are met.
        """
        ### TODO: Part 1
        ### replace this code with your implementation
        raise(NotImplementedError)

    def checkFeasibility(self):
        doesMeetDeadlines = self.validateDeadlines()
        if doesMeetDeadlines:
            print("This schedule is feasible!")
        else:
            print("This schedule is not feasible :(")

You have two test JSON files for this part: p1_test1.json has a feasible schedule, and the schedule in p1_test2.json is infeasible.

Hint: Given an interval, you can find the ID of the job and its corresponding task. Given those IDs, you can look up the task and then the job from the task set. Remember that a deadline is specific to an individual job of a task.

Part 2: Validating WCETs

For this part, you should fill in the implementation of the validateWcets method of the Schedule class in schedule.py. This method should check whether the total duration of all intervals for a given job respect that job’s WCET, as defined by its corresponding task. If any WCET is exceeded, the function should return False. Otherwise, it should return True.

    def validateWcets(self):
        """
        Returns a boolean indicating whether all jobs execute for
        at most their WCET value.
        """
        ### TODO: Part 2
        ### replace this code with your implementation
        raise(NotImplementedError)

    def checkWcets(self):
        areWcetsValid = self.validateWcets()
        if areWcetsValid:
            print("No WCETs are exceeded")
        else:
            print("A job exceeds its WCET :(")

Once again, there are a few test JSON files for this part: p1_test3.json features a schedule in which WCETs are respected, and p1_test4.json contains a schedule in which one of the jobs executes for more than its WCET.

Additionally, there are two test files featuring periodic tasks. The first, p1_test5.json, has WCETs respected for each job (make sure you haven’t added up all intervals for a given task, rather than for each job!). For p1_test6.json, however, the second job of task τ₁ exceeds the WCET for its task.

Update Jan. 17: There were minor bugs in the test files for p1_test5.json and p1_test6.json that involved idle intervals and weirdly labeled finish times. These have been fixed and updated test files also individually posted to Slack.

A few more test cases

There are a few more tests, corresponding to Problem 2 of W1:

• Test 7 should pass for both parts.
• For test 8, the WCET of τ₂ is decreased, so its WCET is exceeded.
• For test 9, both the WCET and relative deadline of τ₂ have been decreased, so it should fail both tests.

What you should submit

You should submit the following files to Gradescope:

• readme.txt (collaboration statement listing collaborators and form of collaboration)
• schedule.py
• any new .json files that you chose to create for testing, and want to share (optional)

An example readme.txt file might be the following:

Author: Lulu Amert

Collaboration statement:
* Cheddar - partner
* Marshmallow - discussed the difference between relative and absolute deadlines

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

Author: Hobbes Amert

Collaboration statement:
For this assignment, I worked alone.