Help page for COSC 6384 -
Real-Time Systems,
Fall 1998

Assignment #3 (100 points + bonus): due midnight, Nov. 25, 1998

Here are the detail instructions for input, algorithm/mechanism, output, how to turn in, and other suggestions.

Updates (11/26/98)

(11/26/98 12:30AM) You can take 10 points deduction each day if you wish to turn in late.
(11/23/98) New deadline: midnight, Nov. 25, 1998. If you turn in by midnight, Nov. 24, 1998, you will receive 5 points BONUS.
(11/20/98) Another new example -- rts.input.7 has been posted which deals with 2 rendezvous tasks and the period of one task is not a multiple of the other task's period.
(11/20/98) Hint: You can use "strtok" to parse the input file if you use C/C++.
Also, the line for rendezvous:
```
task-name rendezvous task-name2 after (task-name,block1),...,(task-name,blockN)
```
You can assume the first task-name will be the same as second (third, fourth, ...) task-name in (task-name,block1),...(task-name,blockN).
(11/19/98) There was a typo in rts.input.3, "Task_1 rendezvous Task_3 after ..." should be "Task_1 rendezvous Task_2 after ...". Sorry about that.
Also, I have put 2 additional examples, rts.input.6.

Input:

  number-of-processors
  N
  task-name1  num-blocks1 (c(1,1), c(1,2),..., c(1,num-blocks1))  d(1)  p(1)
  task-name2  num-blocks2 (c(2,1), c(2,2),..., c(2,num-blocks2))  d(2)  p(2)
     :            :
  task-nameN  num-blocksN (c(N,1), c(N,2),..., c(N,num-blocksN))  d(N)  p(N)
  
  task-name  rendezvous  task-name  after  (task-name,block),...,(task-name,block)
     :            :
  task-name  rendezvous  task-name  after  (task-name,block),...,(task-name,block)

Specification:

number-of-processors: positive integral number, greater than 0 and less than 10
N: number of tasks, positive integral number, greater than 0 and less than 10
task-name: maximum length 16, first character is an alphabet (a-z,A-Z), 2nd-15th characters are one of alphabets (a-z,A-Z), numbers (0-9), and '_', case-sensitive. For example, "T121", "Task1", and "Task_100" are legal, and "1Task", "_myTask", and "Your$" is not legal.
number-blocksN: positive integral number, greater than 0 and less than 10
c(N,num-blockN): positive integral number, greater than 0 and less than 21
d(N): positive integral number, greater than 0 and less than 1000
p(N): positive integral number, greater than 0 and less than 1000
block in (task-name,block): positive integral number, greater than 0 and less than 10
Separators: space (" "), comma (","), and parentheses ("(" and ")").
All leading spaces and empty lines should be ignored.
Others:
- There will be at least one space between num-blocksN and (c(N,1),c(N,2),....).
- There will be at least one space between (c(N,1),...,c(N,num-blockN)) and d(N).
- There may or may not be a space before and after a comma (","), i.e., you will see cases like "1,2", "1, 2", and "1 ,2" and they are legal.
- There may or may not be a space at the opening end of parenthese, i.e., you will see cases like "1 (2,3) 4", "1 ( 2,3) 4", and "1 ( 2,3 ) 4".

Sample files:
sample input file #1,
sample input file #2,
sample input file #3,
sample input file #4,
sample input file #5 new,
sample input file #6, and
new sample input file #7 new

Algorithm/Mechanism:

A process cannot be executed on two or more processors at the same time. The processes have rendezvous constraints.
You can use Earlist Deadline (ED), Least Laxity (LL), Rate Monotonic Scheduling (RMS), or combination of ED/LL/RMS to implement your scheduler. You must indicate which scheduling algorithm(s) you use in your program(s), and output.
Your scheduler should allow preemption bewteen tasks (for rendezvous) and within a computational block (optional).
Your scheduler should be able to schedule tasks even GCD of their C/D's is not integral.
Your scheduler should provide minimal error messages, such as "file not found", "error decoding input file", "missing keyword", etc.

Output:

Your output should indicate which algorithm(s) you use.
If your scheduler find a feasible schedule for the given set of tasks, the output should use a Gantt Chart / Timing Diagram representation.
The output should have minimal number of iterations which can show the predicatable behavior from that point on.
If your schduler cannot find a feasible schedule for the given set of tasks, the output should show which task(s) miss their deadline(s) at what time on which processor.

Output suggestions:
These are output suggestions, not limit to.

Graphical output in X11/xfig/BMP/other graphic formats (BONUS 10 points).

Text output in horizontal. For example in Gantt Chart,

        0   1   2   3   4   5   6   7   8   9   10
        +---+---+---+---+---+---+---+---+---+---+
        |C11|C21|C12|C3 |C22|C11|  C22  |C12|
        +---+---+---+---+---+---+---+---+---+---+

Or in Timing Diagram,

        0   1   2   3   4   5   6   7   8   9   10
        +---+---+---+---+---+---+---+---+---+---+
    T1  |C11|   |C12|           |C11|C12|
        S---+---+---D---+---P---+---+---D---+---+
    T2      |C21|   |    C22    |
        S---+---+---+---+---+---+---+---+---+---D
    T2                                  |C3 |
        S---+---+---+---+---+---+---+---+---D---P

Where S, D, and P stand for Starting time, Deadline, and Period, respetively.

Text output in vertical. For example in Gantt Chart,

        +-----+ 0
        | C11 |
        +-----+ 1
        | C21 |
        +-----+ 2
        | C12 |
        +-----+ 3
        | C3  |
        +-----+ 4
        | C22 |
        +-----+ 5
        | C11 |
        +-----+ 6
        |     |
        + C22 + 7
        |     |
        +-----+ 8
        | C12 |
        +-----+ 9

Or in Timing Diagram,

          T1         T2         T3
        S-----+    S     +    S     + 0
        | C11 |    |     |    |     |
        +-----+    +-----+    +     + 1
        |     |    | C21 |    |     |
        +-----+    +-----+    +     + 2
        | C12 |    |     |    |     |
        D-----+    +-----+    +     + 3
        |     |    |     |    |     |
        +     +    +     +    +     + 4
        |     |    | C22 |    |     |
        P     +    +     +    +     + 5
        |     |    |     |    |     |
        +-----+    +-----+    +     + 6
        | C11 |    |     |    |     |
        +-----+    +     +    +     + 7
        | C12 |    |     |    |     |
        D-----+    +     +    +-----+ 8
        |     |    |     |    | C3  |
        +     +    +     +    D-----+ 9
        |     |    |     |    |     |
        +     +    D     +    P     + 10

Where S, D, and P stand for Starting time, Deadline, and Period, respetively.

Text output in vertical. For example in Gantt Chart,

How to turn in:

New Deadline: midnight, Nov. 25, 1998.
Program(s): with a header including your name, SSN, and alogrithm(s) used, plus minimal documentation for each function/procedure (couple sentences will do) and descriptions for important variables/structures/arrays.
Sample input/output: generate couple sample inputs/outputs.
Instructions to compile/run: Please include instructions to compile and run your program(s), including on what plantform (UNIX/PC/others), what kind of compiler (gcc/VC++/others), and how to view output if it's not in text format.
Things to turn in: Please put instructions to compile/run and sample input/output in one file (let's call it "report.txt" or whatever you want to call it). E-mail your program(s) and "report.txt" (using attachment in pine) to tihuang at cs . uh . edu before deadline. Also, turn in a hard copy of your programs and "report.txt" (or in better format) to 591-PGH by midnight, Nov. 25, 1998. Please slip it under the door if no one inside.

Other suggestions:

Use command line input if possible (instead of interative mode). For example, run your program like "scheduler input_file".
Start earlier. You never know what would happen the day before the deadline, power failure, computer crash, etc..

Last update: 11/26/1998
Please send suggestion/question to tihuang at cs . uh . edu

Help page for COSC 6384 - Real-Time Systems, Fall 1998

Assignment #3 (100 points + bonus): due midnight, Nov. 25, 1998

Updates (11/26/98)

Input:

Algorithm/Mechanism:

Output:

How to turn in:

Other suggestions:

Help page for COSC 6384 -
Real-Time Systems,
Fall 1998