## This page includes some general hints regarding the completion time test as included in the Real Time Embedded Componets and Systems text.

### Some Hints From Sam

Remember, this test is necessary and sufficient and boils down to an interative method for applying the Lehoczky, Shah, Ding theorem by iterating over the longest period to determine if an RM policy schedule exists that causes no deadline over- runs. This is really equivalent to "can you draw a timing diagram" for this service set assuming RM policy for prio and preemption so that all services meet deadlines.

I would suggest that you take an example from class for 2 services (e.g. the 90% loading case in the lecture notes might be good), for which you already have a feasible timing diagram - step through your code using a single step debugger for this scenario and service set and make sure it works.

Next, make up a service set with 3 services that you know will work by first diagramming it. Step through again. Anything that you can draw that is feasible should also pass this test.

Remember too, when you draw diagrams, use the LCM of periods which will typically be longer than the longest period.

The 90% loading case for 2 services presented in class will of course fail RM LUB, but should pass completion test if it is implemented correctly.

### Some Hints from Dan for examining the pseudocode:

First of all, the loop will simply execute all instructions between brackets until the break condition.

Notice An's value on entry to the loop. It is the sum of execution times of all lower priority tasks. What does this time represent with respect to all lower priority tasks total execution time from a critical instant?

Next, notice Anext's value in the first loop statement (the current tasks execution time.)

The next for loop adds the ceil value of (An/T[j]) * C[j] for all lower priority tasks (j) where An (on the first loop) is the sum of exec times of all lower priority tasks. On the first loop execution, what would the result of this for loop be? Note that Ceil An/T[j] for a specific task j would give you the maximum number of task executions for task j that could occur in time An. Outside of the loop we were simply adding all C[j]'s to get An. Now we are adding C[j]'s multiplied by a number of executions in a given time period An to get Anext.

After the first loop, assuming Anext != An, the value of Anext is saved as An and the loop repeats, so the time period used by the for loop calcuation would increase, possibly giving us a larger # of task executions for one of the lower priority tasks.

Note that Anext must == An to exit this loop. How does this happen?

What does it mean if for a given task [i], upon exit of the loop, An > D[i]?