Page 76 - DCAP608_REAL TIME SYSTEMS

Unit 7: Commonly used Algorithm to Real-time Scheduling

If there is only one processor then Notes
 Effective Release time: of a job without predecessors is equal to its given release time. The
effective release time of a job with predecessors is equal to the maximum value among its
given release time and the effective release times of all of its predecessors.
 Effective Deadline: without a successor is equal to its given deadline. The effective deadline
of a job with successors is equal to the minimum value among its given deadline and the
effective deadlines of all of its successors.
Here in figure,

 The numbers are the release times and deadlines.
 As J1 and J2 have no predecessors, their effective release times are 2 and 0.
 Release time of J3 is 1, but that of J2 is 2. Hence, its effective release time is 2.

 Effective release times of the rest of the jobs are 4, 2, 4, 6 respectively.
 J6 and J7 have no successors so their effective deadlines are 20 and 21.
 No issue with deadlines of J4 and J5 as well.
The given deadline of J3 is equal to 12 which is larger than 8 and 9, Hence its effective deadline
is 8 and that of J1 and J2 8 and 7.
 The effective deadline of a job should be as early as the deadline of each of its successors
minus the execution time of the successor.

 The effective release time of a job is that of its predecessor plus the execution time of the
predecessor

 The more accurate calculating is unnecessary if there is only one processor.
 It has been shown that it is feasible to schedule any set of jobs on a processor according to
their given release times and deadlines if and only if it is feasible to schedule the set
according to their effective release times and deadlines just defined.
 Not true for multiple processors.

Task Draw the effective timing constraints process.
Self Assessment

Fill in the blanks:
1. A real-time operating system is a system that schedules execution of tasks in a timely
deterministic manner, and is ………………

2. The ……………… follows a set of algorithms that determine which task executes at each
moment.
3. ……………… priority-based scheduling is a mandatory property of the operating system
we evaluate for use in our application.
4. An ……………… is an asynchronous exception of which the source is an internal or external
hardware device.

LOVELY PROFESSIONAL UNIVERSITY 71