Tyler Bletsch (tkbletsc [AT] unity.ncsu.edu)
North Carolina State University
For CSC714, Prof. Mueller
TSS is a schedulability analysis tool in Perl that supports EDF and DM scheduling policies, as well as the PIP and PCP priority schemes. By allowing "wildcard" variables in task definitions, this tool allows one to search a problem space for feasible task sets. Features:
The following table shows the analysis used for the various algorithms and situations.
| Scheduling algorithm | Analysis needed |
|---|---|
| EDF | System density (including blocking term) ≤ 1 |
| DM (regardless of if all Di≤pi) |
System density (including blocking term) ≤ URM(n) = n(21/n - 1) OR Generalized TDA (with blocking term) |
From this, we see that the following analysis is needed:
In order to go beyond what has been covered in class, I allow the user to specify something akin to "wildcards" within task specification. The system performs the analysis iteratively to discover which matching task sets are schedulable. Specifically, tasks can be input in the usual form:
<period>; <WCET>; [relative deadline]Each of those variables can be:
{2,3,5}; [3,5,0.1]
Means that this task could be any of:
2; 3 ; 3 2; 3.2 ; 3.2 2; 3.4 ; 3.4 2; 3.6 ; 3.6 2; 3.8 ; 3.8 2; 4 ; 4 3; 3 ; 3 3; 3.2 ; 3.2 3; 3.4 ; 3.4 3; 3.6 ; 3.6 3; 3.8 ; 3.8 3; 4 ; 4 5; 3 ; 3 5; 3.2 ; 3.2 5; 3.4 ; 3.4 5; 3.6 ; 3.6 5; 3.8 ; 3.8 5; 4 ; 4This allows the user to test a range of situations easily. Unfortunately, a combinatorial explosion is clearly possible, which will make the workload prohibitively large. This doesn't cause a problem in storage, as the system simply iterates the possibilities without constructing them all in memory. However, there is a potential for a major time hit. This could be combatted a number of ways:
Below is an informal specification for the problem specification file. Blue text is meant to be filled in, black text is literal. Items in [blue brackets] are optional, whereas items in <blue angle-braces> are required. Task parameters may take any of the forms described in the previous section.
The file first consists in one or more of the following line, such that each line describes a task:
task <period>; <WCET>; [relative_deadline] [/ lock_usage]The lock_usage variable consists in zero or more resource reservations of the form:
[<resource_name> <duration>]Here, resource_name is an arbitrary string and duration is the time to hold the lock.
After the task descriptors, one or more of the following lines are used to request an analysis on the tasks described:
try <EDF | DM> with <PCP | PIP>
Here is a simple example file:
task 2; 3 / [radio 1]
task 2; 3; 4 / [radio 2] [sensor 4]
task {2,3,5}; [3,5,0.1]
try EDF with PIP
try EDF with PCP
|
This example provides 3 tasks. The first has period 2, WCET 3, and relative deadline equal to WCET. It uses the resource called "radio" for 1 unit of time. The second task has period 2, WCET 3, and relative deadline 4. It uses the resource "radio" for 2 units of time, then the resource "sensor" for 1 unit of time. The third task uses no resources, but is the wildcard example from the previous section, so it expands to represent 18 different possible tasks. After defining these tasks, we apply EDF analysis with both forms of priority policy.