Due: Monday, March 3, 2025, at 10:00pm

Due: Monday, March 10, 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.)

Starter code: p3.tar

Parts of this assignment:

• Part 1: Generating a random task set
• Part 2: Testing schedulability under RM
• Part 3: Interpreting the results
• Part 4: Running your own experiments

Schedulability Tests

In order to perform large-scale schedulability tests, you need to be able to generate random task systems. Then, for hundreds or thousands (or more!) of these random task systems, typically for a given total system utilization value, you can test schedulability using some test (or set of tests). The fraction of schedulable task systems is reported as a data point. The final plot looks like the following. The different curves correspond to different distributions of per-task utilizations.

You can read this plot as follows. For a given data point, the x-value represents the total system utilization, and the y-value represents the fraction of task systems generated with that total utilization that were schedulable given some schedulability test. In this assignment, that test is the utilization-based test for RM. We want higher schedulability overall, so higher (or further right) is “better”.

Getting started

The starter code for this assignment should be the same as the starter code for P2, except that there is a new file: schedulability.py. You only need to copy this file over to your working directory. Also, note that having previous assignments’ code not quite working has no impact on your ability to complete this assignment.

To generate the plots needed for this assignment, you will need matplotlib. If you get an error from the line import matplotlib.pyplot as plt when you run schedulability.py, you can use a terminal command like the following to get matplotlib, the library needed for plotting:

pip3 install matplotlib

Part 1: Generating a random task set

Take a look through the code in schedulability.py. Note that the code will not run until you have completed Part 1.

You’ll implement several functions in this assignment. The first is generateRandomTaskSet. It takes a few parameters, so first we’ll walk through them:

• targetUtil is the utilization sum you want to have for the generated task set. As the comments state, if a task would have utilization that causes that sum to exceed targetUtil, you should cap that task’s utilization to avoid going over.
• utilFunc is the function you should use to select the utilization for a given task. The choices are defined a little higher in the file: lightUtilFunc, mediumLightUtilFunc, mediumUtilFunc. If you aren’t too familiar with lambda functions or passing functions as parameters, just ask!
• periodFunc is the function you should use to select the period for a given task. This is very similar to utilFunc.

def generateRandomTaskSet(targetUtil, utilFunc, periodFunc):
    """
    Generates a random task set with total utilization targetUtil.

    targetUtil: the utilization sum to have for the generated task set (a float)
    utilFunc: a function that takes no parameters, and returns a utilization (a float)
    periodFunc: a function that takes no parameters, and returns a period (a float)

    Returns: the generated task set as a list of Task objects (not the TaskSet type)
    """
    utilSum = 0

    # Generate tasks until the utilization target is met
    taskSet = []
    i = 0
    while utilSum < targetUtil:
        taskId = i+1

        # TODO:
        # Choose the utilization for the task based on the utilization function
        # given by utilFunc (you call it without parameters).
        # If the task's utilization would push it over the target, instead choose
        # its utilization to be the remaining utilization to reach the target sum.

        # Choose task parameters:
        # * offset
        # * period
        # * relative deadline
        # * WCET <-- calculate based on utilization and period

        # Build a dictionary for the task parameters
        taskDict = {}
        taskDict[TaskSetJsonKeys.KEY_TASK_ID] = taskId
        taskDict[TaskSetJsonKeys.KEY_TASK_PERIOD] = period
        taskDict[TaskSetJsonKeys.KEY_TASK_WCET] = wcet
        taskDict[TaskSetJsonKeys.KEY_TASK_DEADLINE] = relativeDeadline
        taskDict[TaskSetJsonKeys.KEY_TASK_OFFSET] = offset

        task = Task(taskDict)
        taskSet.append(task)

        # TODO: don't forget to update i and utilSum!

    return taskSet

As long as the target utilization is not reached, you should generate a new task and fill in the not-yet-specified task parameters period, wcet, relativeDeadline, and offset.

For this assignment, you should assume synchronous implicit-deadline tasks. The rest of the task parameters exist in case you wanted to extend this work. Also, the code you’re given just returns a list of Tasks as a “task set”, and you can leave it that way.

There is some testing code at the bottom of schedulability.py:

if __name__ == "__main__":
    # Test Part 1
    generateTasks()

    # Test Parts 2 and 3
    # testSchedulability()

    # Test Part 4
    # runMoreExperiments()

When you run the file, you should get output kind of like the following (but not identical, because of the use of pseudo-random numbers) :

Task set with goal utilization of 0.5:
task 1: (Φ,T,C,D) = (0.0, 16.486802068785813, 0.6978120663124631, 16.486802068785813)
task 2: (Φ,T,C,D) = (0.0, 29.254355845187888, 0.6132949468900103, 29.254355845187888)
task 3: (Φ,T,C,D) = (0.0, 9.05301339765479, 0.8021166102880495, 9.05301339765479)
task 4: (Φ,T,C,D) = (0.0, 27.85298807746814, 1.4968208736020272, 27.85298807746814)
task 5: (Φ,T,C,D) = (0.0, 23.498261545145812, 1.8416650917026316, 23.498261545145812)
task 6: (Φ,T,C,D) = (0.0, 6.430214648689571, 0.3677665976802528, 6.430214648689571)
task 7: (Φ,T,C,D) = (0.0, 24.16086193483285, 0.799361127008351, 24.16086193483285)
task 8: (Φ,T,C,D) = (0.0, 8.062414078622485, 0.7925481099541118, 8.062414078622485)
task 9: (Φ,T,C,D) = (0.0, 19.105954147642368, 0.5237605609915489, 19.105954147642368)
(total util: 0.5)

Task set with goal utilization of 1.4:
task 1: (Φ,T,C,D) = (0.0, 206.8546065629542, 35.835490335004, 206.8546065629542)
task 2: (Φ,T,C,D) = (0.0, 142.67584132352982, 52.060178995062905, 142.67584132352982)
task 3: (Φ,T,C,D) = (0.0, 102.79182865857214, 18.172230136946823, 102.79182865857214)
task 4: (Φ,T,C,D) = (0.0, 121.5802155083306, 14.14506826442725, 121.5802155083306)
task 5: (Φ,T,C,D) = (0.0, 152.692299083089, 22.2429844153009, 152.692299083089)
task 6: (Φ,T,C,D) = (0.0, 65.9963640960477, 23.624357660148167, 65.9963640960477)
task 7: (Φ,T,C,D) = (0.0, 177.1903070234649, 11.536679133738561, 177.1903070234649)
(total util: 1.4)

Part 2: Testing schedulability under RM

In order to have a meaningful schedulability study, we need a schedulability test. For this assignment, you will implement the simple utilization-based RM schedulability test.

def rmSchedulabilityTest(taskSet):
    """
    Performs the simple utilization-based schedulability test for RM.

    Only checks the total utilization sum against the U_lub bound.
    Does not check per-task.
    """
    # TODO
    return False # replace with your code

This function should take in a taskSet (as a list of Task objects), and return True if the total utilization does not exceed U_lub based on the number of tasks, or False otherwise. Recall that the value of U_lub is given by n * (2^1/n - 1) for a system of n tasks.

Once you can generate random task sets and check their schedulability, you should be able to generate plots. You will need to un-comment the call to testSchedulability() at the bottom of schedulability.py to finish this part.

Part 3: Interpreting the results

The default number of task sets for which to check schedulability for a given total utilization is 10 in the starter code. This doesn’t give very robust results. Once you have a graph in the general style of the one above, you should increase this number to at least 1000. (Note that any higher may get prohibitively long for your patience.)

def testSchedulability():
    random.seed(None) # seed the random library

    # Perform the schedulability tests
    utilVals, results = performTests(10) # TODO: change to a bigger number, like 1000

    # Plot the results
    plotResults(utilVals, results)

You should generate a plot similar to the one above. Then, in your readme.txt, include a description of what is going on in the plot. You should answer the following questions:

• What do the three lines represent?
• Why does medium drop off at such a higher utilization than the others?
• Why does light drop off where it does?
• Which of these lines represents the “best” schedulability, and why?

Part 4: Playing with periods

For the graph in Part 3, only the utilization varied, with the period always being chosen by shortPeriodFunc.

For this part, add your own function similar to performTests that uses a different set of utilization and/or period functions. You can put a call to this function in the blank runMoreExperiments. For example, you could generate a graph similar to that from Part 3, but with all curves based on choicePeriodFunc. For, you could pick a given utilization function and draw one curve for each period function.

Note: To see the plot for this part, make sure to un-comment the call to runMoreExperiments at the bottom of schedulability.py, and then either comment out testSchedulability() or close that plot after it pops up.

In your readme.txt, include a short description of your new function, as well as an observation about the plot, similar to those from Part 3.

What you should submit

You should submit the following files to Gradescope:

• readme.txt(collaboration statement listing collaborators and form of collaboration, as well as answers for Parts 3 and 4)
• schedulability.py (code for Parts 1, 2, and 4)
• plot.png (the schedulablity graph you generate for Part 4)

An example readme.txt file might be the following (in addition to your answers for Parts 3 and 4):

Author: Lulu Amert

Collaboration statement:
* Cheddar - partner
* Marshmallow - discussed how to call the utilization function

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

Author: Hobbes Amert

Collaboration statement:
For this assignment, I worked alone.