[go: up one dir, main page]
Scribd
Upload
357 views12 pages

Real-Time Scheduling Algorithms

The document discusses the optimality and non-optimality of the Earliest Deadline First (EDF) and Least Slack Time (LST) scheduling algorithms. It states that EDF and LST are optimal for scheduling jobs on a single processor when preemption is allowed and jobs do not contend for resources. However, it also notes that EDF and LST are not optimal when scheduling jobs on multiple processors if preemption is not allowed. The document provides proofs of optimality for EDF and LST on a single processor and examples where their schedules are non-optimal on multiple processors without preemption. It also discusses differences between dynamic and static scheduling systems.

Uploaded by

Mohammed Muzzamil
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
357 views12 pages

Real-Time Scheduling Algorithms

The document discusses the optimality and non-optimality of the Earliest Deadline First (EDF) and Least Slack Time (LST) scheduling algorithms. It states that EDF and LST are optimal for scheduling jobs on a single processor when preemption is allowed and jobs do not contend for resources. However, it also notes that EDF and LST are not optimal when scheduling jobs on multiple processors if preemption is not allowed. The document provides proofs of optimality for EDF and LST on a single processor and examples where their schedules are non-optimal on multiple processors without preemption. It also discusses differences between dynamic and static scheduling systems.

Uploaded by

Mohammed Muzzamil
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 12

Dynamic Vs Static System

Optimality of EDF and LST algo


Non-Optimality of EDF and LST algo

By
Mohammed Muzzamil
Optimality of EDF and LST
These algorithms are optimal
– i.e. they will always produce a feasible schedule if one
exists
– Constraints: on a single processor, as long as preemption
is allowed and jobs do not contend for resources
Theorem:
When pre-emption is allowed and jobs do not contend for
resources, the EDF algorithm can produce a feasible
schedule of a set j of jobs with arbitrary release times and
deadlines on a processor if and only if J has feasible
schedules.
Optimality of EDF and LST: Proof
1. Any feasible schedule can be transformed into an EDF
schedule
 If Ji is scheduled to execute before Jk, but Ji’s
deadline is later than Jk’s either:
-- The release time of Jk is after the Ji completes ⇒
they’re already in EDF order
-- The release time of Jk is before the end of the
interval in which Ji executes:
Optimality of EDF and LST: Proof

Swap Ji and Jk (this is always possible, since Ji’s


deadline is later than Jk’s)

Move any jobs following idle periods forward into the


idle period
Latest Release Time
Let us consider the jobs J1 3(0,6), J2 2(5,8) and J3 2(2,7)
Where for J1 3 is the execution time, 0 is the release time
and 6 is the deadline
When they are scheduled by the LRT

J1 J3 J2

0 2 4 6 8
Optimality of EDF and LST: Proof
Corollary:
When pre-emption is allowed and jobs do not contend
for resources, the LRT algorithm can produce a
feasible schedule of a set J of jobs with arbitrary
release times and deadlines on a processor if and only
if feasible schedules of J exist.
Least Slack Time (LST)
Slack Time=deadline – t – time required to complete the
remaining portions of a job
Smallest slack – highest priority
Theorem :
When pre-emption is allowed and jobs do not contend
for resources the LST algorithm can produce a feasible
schedule of a set J of jobs with arbitrary release times
and deadlines on a processor if and only if feasible
schedules of J exist
Non-optimality of the EDF and LST algo
Constraints: on a multi processor and
preemption is not allowed
These are some EDF schedules which are non-
optimal
r1 r2 r3 d1 d3 d2

0 2 4 10 14
r1,r2 r3 d2 d3

0 1 2 6
Non-optimality of the EDF and LST algo
Non EDF schedule

J1 J3 J2

LST

Proc 1 J1 J2

Proc 2 J3
Non-optimality of the EDF and LST algo
Dis- advantage of LST:
But the LST require the knowledge of the execution time
but EDF doesn’t. Some the execution times are often not
known until the jobs complete.
Dynamic vs. Static Systems
 If jobs are scheduled on multiple processors, and a job can be
dispatched from the priority run queue to any of the processors, the
system is dynamic
 A job migrates if it starts execution on one processor and is
resumed on a different processor
 If jobs are partitioned into subsystems, and each subsystem is
bound statically to a processor, we have a static system
 Expect static systems to have inferior performance (in terms of
overall response time of the jobs) relative to dynamic systems
– But it is possible to validate static systems, whereas this is not
always true for dynamic systems
– For this reason, most hard real time systems are static
Thank you

You might also like