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
   58   59   60   61   62   63   64   65   66   67   68