Page 123 - DCAP608_REAL TIME SYSTEMS

Real Time Systems

Notes  At time 2.9, J1, 2 completes.
 Processor executes J2, 1.
 At time 4, J1,3 is released with deadline 6, later than the deadline of J2,1, hence processor
keeps on executing J2,1
 At time 4.1, J2,1 completes, the processor starts to execute J1,3 and so on.
 The priority of T1 is higher than priority of T2 from time 0 until 4.
 T2 starts to have a higher priority at time 4.

 When the job J2, 2 is released, T2 again has a lower priority.
 Hence the EDF algorithm is a task-level dynamic priority algorithm.
 Once a job is placed in the ready job queue according to the priority assigned to it, its order
with respect to other jobs in the queue remains fixed.
 At time 0, the first jobs J1, 1 and J2, 1 of both tasks are ready. The absolute deadline of J1,1
is 2 and that of J2,1 is 5 so J1,1 is higher priority.

 At time 2, J1, 2 is released and its deadline is 4, earlier than J2, 1. Hence J2, 1 is placed ahead
of J2, 1 it preempts J2, 1 and executes.
 At time 2.9, J1, 2 completes. Processor executes J2, 1.

 At time 4, J1,3 is released with deadline 6, later than the deadline of J2,1, hence processor
keeps on executing J2,1.
 At time 4.1, J2,1 completes, the processor starts to execute J1,3 and so on.

 The priority of T1 is higher than priority of T2 from time 0 until 4.
 T2 starts to have a higher priority at time 4.
 When the jobJ2, 2 is released, T2 again has a lower priority.

 Hence the EDF algorithm is a task-level dynamic priority algorithm.
 Once a job is placed in the ready job queue according to the priority assigned to it, its order
with respect to other jobs in the queue remains fixed.

 Thus the EDF algorithm is a job-level fixed-priority algorithm.
 Another dynamic priory algorithm is Least-Slack-Time-First (LST).
 At time t, the slack of a job whose remaining execution time is x and whose deadline is d
is equal to d-t-x.

 The scheduler checks the slacks of all the ready jobs each time a new job is released and
orders the new job and the existing jobs on the basis of their slack.

 The smaller the slack, the higher the priority.
 Co-incidentally, the schedule of T1 and T2 in the discussed example happens to be identical.
 However the LST schedule of a system may differ in a fundamental way from the EDF
schedule.

 Consider and more complicated system that consists of three tasks; T1 = (2, 0.8) T2 = (5, 1.5)
and T3 = (5.1, 1.5).

118 LOVELY PROFESSIONAL UNIVERSITY