Page 63 - DCAP608_REAL TIME SYSTEMS
P. 63
Real Time Systems
Notes 5.5 Summary
Executions of jobs can often be interleaved.
The scheduler may suspend the execution of a less urgent job and give the processor to
more urgent job. The suspended job can be resumed again.
A job is pre-emptible if its execution can be suspended at any time to allow the execution
of other jobs and later it can be resumed from the point of suspension.
A job is non-pre-emptible if it must be executed from start to completion without
interruption. Consider jobs that model the transmission of data frames in a token ring.
If transmission of frame is interrupted before its completion then the entire frame must be
re-transmitted from the start.
A valid schedule is a feasible schedule if every job completes by its deadline.
We say that a set of jobs is schedulable according to a scheduling algorithm if when using
the algorithms the scheduler always produces a feasible schedule.
A hard real-time scheduling algorithm is optimal if the algorithms (scheduler) always
produce a feasible schedule if the given set of jobs has feasible schedules.
If an optimal algorithm fails to find a feasible schedule, we can conclude that the given set
of jobs cannot feasibly be scheduled by any algorithm.
In the case where all the jobs have the same release time and deadline, the problem of
scheduling the jobs to meet their deadline is in essence the same as that of scheduling to
minimize the completion time of the job which completes last among all jobs.
The response time of this job is the response time of the set of jobs as a whole and is often
called the makespan of the schedule.
If the makespan is less than or equal to the length of their feasible interval, the jobs can
meet their deadline.
5.6 Keywords
Conditional Block: The sub-graph that begins from a vertex representing a branch job and ends
at the vertex representing the associated join job is called a conditional block.
Conditional Process Graph (CPG): A graph captures both the flow of data and its control.
Job Resource Parameters: These are indicated processor and resource requirements (what, how
many and when).
Job: A unit of work scheduled and executed by system.
Non-pre-emptible Job: A job is non-pre-emptible if it must be executed from start to completion
without interruption.
Parameters: These are variables that used for run-time substitution in the properties of Resources.
Pre-emptible Job: A job is pre-emptible if its execution can be suspended at any time to allow the
execution of other jobs and later it can be resumed from the point of suspension.
Temporal Distance Constraint: Jobs are said to have temporal distance constraint, if their distance
must be no more than some finite value.
58 LOVELY PROFESSIONAL UNIVERSITY