Homework 4: Project Proposal

Tyler Bletsch (tkbletsc [AT] unity.ncsu.edu)
18 October 2005
CSC714, Prof. Mueller

Introduction

I intend to write a schedulability analysis tool that supports EDF and DM scheduling policies, as well as the PIP and PCP priority schemes. This tool will be written in Perl, and will build on the framework I developed previously while studying the analysis techniques discussed in class. The tool will accept input files that describe tasks, resources, and the scheduling/priority algorithms to analyze. For simplicity, all resources are assumed to be static and binary.

Techniques Needed

The following table shows the analysis needed for the various algorithms and situations.

Scheduling algorithm	Analysis needed
EDF	System density (including blocking term) ≤ 1
DM with all D_i≤p_i	System density (including blocking term) ≤ U_RM(n) = n(2^1/n - 1) OR TDA (with blocking term)
DM with some D_i>p_i	System density (including blocking term) ≤ U_RM(n) = n(2^1/n - 1) OR Generalized TDA (with blocking term)

From this, we see that the following analysis is needed:

Blocking term b_i calculation for PIP
Blocking term b_i calculation for PCP
System density (including blocking term)
TDA (with blocking term)
Generalized TDA (with blocking term)

Fortunately, all these techniques are presented in adequate depth in the course materials.

Task-space Search

In order to go beyond what has been covered in class, I propose to allow the user to specify something akin to "wildcards" within task specification. The system will then perform the analysis iteratively to discover which matching task sets are schedulable. Specifically, tasks can be input in the usual form:

	[phase]; <period>; <WCET>; [relative deadline]

Each of those variables can be:

A simple floating-point number, such as "6.5"
A set of numbers, such as "{1, 3, 6.5}"
A discrete interval of the form "[a, b, δ]", which means "the set of numbers from a to b stepping by δ". For example, "[1, 3, 0.5]" is equivalent to "{1, 1.5, 2, 2.5, 3}"
A discrete interval of the form "[a, b]", which behaves just as above with δ=1

Thus, the specification:

	{2,3,5}; [3,5,0.1]

Means that this task could be any of:

	0; 2; 3   ; 3  
	0; 2; 3.2 ; 3.2
	0; 2; 3.4 ; 3.4
	0; 2; 3.6 ; 3.6
	0; 2; 3.8 ; 3.8
	0; 2; 4   ; 4  
	0; 3; 3   ; 3  
	0; 3; 3.2 ; 3.2
	0; 3; 3.4 ; 3.4
	0; 3; 3.6 ; 3.6
	0; 3; 3.8 ; 3.8
	0; 3; 4   ; 4  
	0; 5; 3   ; 3  
	0; 5; 3.2 ; 3.2
	0; 5; 3.4 ; 3.4
	0; 5; 3.6 ; 3.6
	0; 5; 3.8 ; 3.8
	0; 5; 4   ; 4

This 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 could be combatted a number of ways:

If a signfiicant portion of cases are feasible, random sampling of the task space would allow the user to find subset of results quickly (in the average case).
The system could be parallelized across multiple machines. This can only divide the running time by a constant (the number of nodes), but it could be of some use
It may be possible to "home in" on favorable regions of the task space using a heuristic search such as A*, but it isn't clear at present what heuristic measure could be applied to guide the search in the right direction

I intend to implement one or more of the above solutions.

Input File Format

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 lock_usage variable has the same nested brackets syntax presented in lec6.ppt, slide 4.

The file first consists in one or more of the following line, such that each line describes a task:

	task [phase;] <period>; <WCET>; [relative_deadline] [/ lock_usage]

After this, one or more of the following lines are used to request an analysis on the tasks described above:

	try <EDF | DM> with <PCP | PIP>

Here is a simple example file:
task 1; 2; 3 / [1; 1] task 1; 2; 3; 4 / [1; 2 [2; 1]] task {2,3,5}; [3,5,0.1] try EDF with PIP try EDF with PCP

This example allows provides 3 tasks. The first has phase 1, period 2, WCET 3, and relative deadline equal to WCET. It uses resource 1 for 1 unit of time. The second task has phase 1, period 2, WCET 3, and relative deadline 4. It locks resource 1 for 2 units of time, then locks resource 2 for 1 unit of time, then releases both. The third task uses no resources, but is the wildcard example from the previous section, so it expands to represent 18 different possible tasks. Also note that the resource allocations after the slash have nothing to do with the intervals that can be specified before the slash. After defining these tasks, we apply EDF analysis with both forms of priority policy.

Milestones

24 Oct: TDA (without blocking term)
31 Oct: Generalized TDA (without blocking term)
7 Nov: System density (not including blocking term)
14 Nov: File parser
21 Nov: Blocking term b_i calculation for PIP and PCP
28 Nov: Add blocking term b_i to all analysis methods

References

The course text and lecture notes outline virtually all of the analysis techniques. Additional scholarly references do not seem necesssary at this time.
The Perl documentation will no doubt be accessed a great many times