Page 48 - DCAP608_REAL TIME SYSTEMS

Unit 4: A Reference Model of Real-time Systems

Job is released at time 3. Its (absolute) deadline is at time 10. Its relative deadline is 7. Its response Notes
time is 6. A time interval of length H is called a hyper period of the periodic tasks. It is the least
common multiple of p for i=1, 2, …n. The length of a hyper period of three periodic tasks with
i
periods 3, 4, 10 is 60
The maximum number N of jobs in each hyper period is equal to n  H/pi. The total number of
i=1
job in the hyper period is 41. The ratio u = e /p is the utilization of the task T U is equal to the
i i i i.. i
fraction of time a truly periodic task with period p and execution time e keeps a processor busy.
i i
The total utilization U of all the tasks in the system is the sum of the utilizations of the individual
tasks in it. If the execution times of the three periodic tasks are 1, 1, 3 and periods are 3,4,10 then
their utilizations are 0.33, 0.25 and 0.3. Total utilization is 0.88 (These tasks keep processor busy
88% of time).

Example: A periodic task T with r = 2, p = 5, e = 2, D =5 executes like this:
i i i i i

= job release = job deadline

4.3.2 Aperiodic and Sporadic Jobs

A task is aperiodic if the jobs in it have either soft deadlines or no deadlines. The task to adjust
radar’s sensitivity is an example. We want the system to be responsive, that is, to complete each
adjustment as soon as possible. But a late response is annoying but tolerable. We therefore want
to optimize the responsiveness of the system for the aperiodic jobs, but never at the expense of
hard real-time tasks has whose deadlines must be met at all timed. In contrast, an autopilot
system is required to response to a pilot’s command to disengage the autopilot and take over the
control manually within a specific time. The jobs that execute in response to these events have
hard deadlines. The jobs that execute in response to these events have hard deadlines. Tasks
containing jobs that are released at random time instants and have hard deadlines are sporadic
tasks.

4.4 Precedence Constraint and Data Dependency

Data and control dependencies among jobs may constrain the order in which they can execute.
The jobs are said to have precedence constraints if they are constrained to execute in some order.
If the jobs can execute in any order, they are said to be independent. Consider queries to an
information server. Suppose that before each query is processed and the requested information
retrieved, its authorization to access the requested information is first checked. The retrieval job
cannot begin execution until the authentication job completes. Similarly in a communication
system, the jobs that generate acknowledgements of a message and transmit the acknowledgement
message cannot begin until the job that receives and processes the message completes.
4.4.1 Precedence Graph and Task Graph

We use a partial-order relation <, called a precedence relation, over the set of jobs to specify the
precedence constraints among jobs. A job J is a predecessor of another job J if J cannot begin
i k k
execution until the execution of J completes. In short we can write J < J Ji is the immediate
i i k.
predecessor of Jk if Ji < Jk and there is no other job J such that J <J<J Two jobs are independent
j i j k.

LOVELY PROFESSIONAL UNIVERSITY 43